Why are they all >60? (The idea is just to find the closest to 60, right?)
(2,1), (1,2): 36.86989764584401
(3,1), (1,3): 53.13010235415599
At first this was pretty surprising to me, and I was pretty sure it must be a bug in the code. Well, I tried it myself and got the same results. :-)
After a few false starts, here's what I think is the probable explanation. Note that we're trying to approximate √3 by a fraction of the form (ad-bc)/(ac+bd). The closest fractions we get (among a, b, c, d below a given magnitude) could be either below or above √3.
Consider an angle of (π/3+ε). If you look tan(π/3+ε)-tan(π/3), it works out to be (tan(ε) + 3ε) / (1 - ε√3). When ε is replaced by -ε, if you look at tan(π/3)-tan(π/3-ε), it works out to be (tan(ε) + 3ε) / (1 + ε√3).
For small ε, the former, namely (tan(ε) + 3ε) / (1 - ε√3), is larger than the latter, namely (tan(ε) + 3ε) / (1 + ε√3). (More generally, this boils down to the fact that the second derivative of tan(x) is positive.)
This means that it's easier (you're allowed a larger difference in the angle) to achieve a given closeness of the fraction (ad-bc)/(ac+bd) to √3 by picking the angle to be greater than π/3 (=60°) than if the angle is less than π/3.
For larger denominators, √3 becomes about as easy to approximate to a given closeness from below as from above (by fractions of the form (ad-bc)/(ac+bd)), but among roughly equally distant approximations, the ones from above are closer in angle than the ones from below.
(1) For one thing, the difference in epsilon is very small: the ratio (1 + ε√3)/(1 - ε√3) is 1+2√3ε+O(ε²), that is, we're comparing something like 4ε+4√3ε² versus 4ε-4√3ε², which is probably too small to matter.
(2) The argument looks like it applies to all angles, but in fact experimentation shows the same phenomenon does not appear, and finally,
(3) Here are the next two terms after:
(211,14), (94,191): 60.000000269 (253,140), (1,55): 59.999999869 (265,71), (41,153: 60.000000035
where we see that one term is less than 60 degrees.
Rough explanation: if the angle is less than 60, then subtracting the smaller vector of the larger vector will produce one with smaller coefficients.
And could you elaborate? For example, take (11, 5) and (1, 10), which make an angle of roughly 59.845 degrees. Subtracting the smaller vector from the larger vector here gives (10, -5)… then what?
- The cosine of 60 degrees is 1/2 (and it is increasing from 60 degrees to 0 degrees, where it is 1)
- The square Euclidean norm of the vector a-b is (a-b,a-b) = (a,a) - 2(a,b) + (b,b) = |a|^2 + |b|^2 - 2|a||b|cos(angle) - Now let's |b| = x|a| for some x<1. Then the above becomes (1+x)|a|^2 - 2(x|a|^2)cos(angle)
- If cos(angle) > 1/2, then the result is less than |a|^2, which means that a-b is shorter than a
In your example, the angle between (10,-5) and (1,10) is approx 110 degrees, which means they are reduced with respect to each other and you cannot make them smaller.
Perhaps it would be easiest to understand with the example: we want to say that, though (11, 5) and (1, 10) make an angle very close to 60° (specifically, about 59.845°), there must exist a pair of vectors that make an angle even closer to 60°, and with smaller coordinates. What is this pair of vectors, and how do we arrive at it? (If one of them is their difference namely (10, -5), what is the other one?)
Also, I think the top-level comment here (by joefkelley) considered only vectors with positive coordinates (maybe?), so we may need to take that into account and/or explain why the coordinates are always positive.
When approximating 60 degrees from below, you will always be able to 'reduce' the length of the vectors (which likely reduces the individual coordinates due to the relation of the infinity norm and the Euclidian norm). This means you will need a different approach to the brute-force than taken in the top-level comment.
Only positive coordinates means that you are restricted to one of the quadrants. I suspect (but do not have time to figure out/prove right now, and it might not be true) that when your lattice contains vectors with optimal angle close to 60 degrees, that you can either rotate or otherwise find an isomorphic lattice that has only positive coordinates in its basis vectors. However, it may just be a side-effect of how the original list was produced.
Yes, as you've said, when the angle between two vectors is less than 60 degrees, you can always “reduce” the length of the vectors, but what good is this reduction, if the angle actually gets farther away from 60 degrees? All it does is preserve the lattice, but that's not our goal here.
Thanks for explaining lattice basis reduction to me. Now I know more about it, which is great. I just don't see how it has any bearing on the question asked here (https://news.ycombinator.com/item?id=18538456): why is it that, when we enumerate the “best” solutions among those under a given magnitude, they always (after the first two) approximate 60° from above? Is it coincidence and does the pattern break down (will we see 59.999...x° eventually as an angle that cannot be beaten by smaller vectors), or is there a proof?
And if there is a proof, can you please illustrate with the example of (11, 5) and (1, 10), how to (procedurally) get a pair of vectors with smaller magnitude, but angle at least as close to 60° as in this pair? (Note that the lattice reduction step you gave takes the angle further away from 60°, so as far as I can tell it's not helpful.)