3 ms·

Regarding the angle between (a-b) and b: you can repeat the process until you end up with two vectors that cannot be reduced with respect to one another. Eventu

Regarding the angle between (a-b) and b: you can repeat the process until you end up with two vectors that cannot be reduced with respect to one another. Eventually the angle will be between 60 and 120 degrees (because you can always negate a vector which turns an angle of x degrees into 180-x degrees). So this process of basis reduction does not make the angle closer to 60 necessarily, but merely puts the angle somewhere within the [60,120] range 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.

svat 8y ago
You're still not addressing the main question: how do you prove that the closest approximation, among vectors of a given magnitude — whether you take this to be the infinity norm (max coordinate), the Euclidean norm, total length, whatever — will never approximate 60 degrees from below? 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 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.)

svat 8y ago

You're still not addressing the main question: how do you prove that the closest approximation, among vectors of a given magnitude — whether you take this to be the infinity norm (max coordinate), the Euclidean norm, total length, whatever — will never approximate 60 degrees from below? 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 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.)