On 9/11/09, Mike Stay <metaweta@gmail.com> wrote:
I'm thinking about the problem of designing gear trains for a lego orrery which I'd like to be fairly accurate. The standard gear sizes are 8, 16, 24, 40, so I have ratios of 1:2:3:5 to work with. I figure that since lg(3) (where lg is log base 2) is irrational, you can get arbitrary accuracy out of a gear train. I think I need a + b lg(3) + c lg(5) ~= lg(period), with a, b, c small. Is LLL the right tool for solving this kind of thing?
After flailing around for a fortnight, I stubbed my toe on the key to the inhomogeneous box of delights while looking the other way, and am now left wondering how I failed to see it straight away. Example: Given [-log(7), log(2), log(3), log(5)] with 10 decimal digits, GAMP2 delivers [1, 55, -30, -2] --- the inner product equals -0.000059714. Of course, the feasibility of building a train of 88 Lego cogs for the sake of a 7:1 ratio to 4 decimal places is another question entirely ... All that was required was duality: instead of constructing lattice primes (hyperplanes) in n-space near to a real target point at infinity --- so locking into the homogeneous case --- simply map the input vector, complete with its nonzero RHS, to a real target prime --- passing through the origin when the problem is homogeneous, but not otherwise --- and construct nearby lattice points. Instead of furling an umbrella of points about a target shaft, GAMP2 proceeds by unfurling an umbrella of primes onto a target prime, with a crucial extra degree of freedom. After initialising a basis of lattice primes with the n coordinate primes and the prime at infinity, represented projectively by the order-(n+1) unit matrix, the algorithm rattles on almost as before: choose a candidate prime in cyclic order (excluding oo), temporarily swap it for the target prime, invert the resulting matrix and multiply by the candidate to obtain coordinates with respect to the modified basis, subtract the truncated (integer) combination from the candidate to yield a refined basis. Then iterate till converge, or shot down by rounding error in the input, in time linear in the precision. The extra twist is that the above stage refines only angles: the constant (RHS) component has to be adjusted separately, so that the refined lattice prime meets the target prime as close as possible to the foot of the perpendicular line from origin to target. Finally, invert the converged basis matrix into a dual basis of lattice points, the first of which lies close to the target prime; the other points approximate the homogeneous prime instead, but may be added to the first to yield a basis of (approximate) inhomogeneous relations. The in-radius of the (n-1)-space polytope, formed by the parallelotope of basis primes intersecting the target prime, is trivial to compute and gives a lower bound on the length of any potential exact relation which the existing precision is insufficient to detect --- the orrery application has no need of such bounds, which is just as well as these are disappointingly conservative. Fred Lunnon [01/10/09]