5 ms·

The (7,2), (1,4) solution is surprisingly good. I did a really dumb brute force search and you have to get a decent ways out before you get anything better. Her

The (7,2), (1,4) solution is surprisingly good. I did a really dumb brute force search and you have to get a decent ways out before you get anything better. Here are pairs of points for which there are no other better pairs with a lower max coordinate: (4,1), (1,4): 61.92751306414705 (5,1), (1,3): 60.25511870305778 (6,2), (1,5): 60.255118703057775 (7,2), (1,4): 60.018360631150664 (17,3), (4,11): 60.00891367665869 (18,7), (2,13): 60.00333223031155 (19,5), (3,11): 60.001318460471495 (26,7), (4,15): 60.00009466237024 (59,21), (9,49): 60.000006796458415 (97,26), (15,56): 60.00000048796379

yesenadam 8y ago
Why are they all >60? (The idea is just to find the closest to 60, right?)
- joefkelley 8y ago
  No idea. I guess technically I omitted: (2,1), (1,2): 36.86989764584401 (3,1), (1,3): 53.13010235415599 So I don't think it's a bug in my code, but that is pretty odd.
  - PseuRanAcc 8y ago
    Technically these should be reduced to (1,-1), (1,2) and (2,-2), (1,3) which should have angles >60.
  - svat 8y ago
    Took me a while, but I think I figured it out! 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.
    - svat 8y ago
      Can't edit the above post, but when trying to write this up more carefully I realized it's not correct: (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.
- PseuRanAcc 8y ago
  This is something that has to do with Lattice basis reduction (https://en.wikipedia.org/wiki/Lattice_reduction https://en.wikipedia.org/wiki/Lattice_reduction). Rough explanation: if the angle is less than 60, then subtracting the smaller vector of the larger vector will produce one with smaller coefficients.
  - svat 8y ago
    Is it something special about 60 degrees, that causes this? 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?
    - PseuRanAcc 8y ago
      Yes, using some linear algebra: - The inner product (or dot product) of two vectors is related to the angle (a,b) = |a||b|cos(angle). - 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.
      - svat 8y ago
        Thanks. I guess what you've shown is that if two vectors a and b are at an angle such that cos(angle) > 1/2, then (a-b) is shorter than a. Don't we also need to say something about the angle between (a-b) and b? It's late at night and I can't figure out what that is. :-) I imagine we'd have to say that it's no further from 60° than the angle between a and b was (but actually that's not true, so I guess the claim is something else?) 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.
myWindoonn 8y ago
I suspect that the quality of the solution is due to the connection between continued fractions and best approximants. The author notes that the approximants alternate between being usable and non-usable, which is characteristic of continued-fraction-generated approximants, which "flip" every time and have a sort of parity as a result.

yesenadam 8y ago

Why are they all >60? (The idea is just to find the closest to 60, right?)

joefkelley 8y ago
No idea. I guess technically I omitted: (2,1), (1,2): 36.86989764584401 (3,1), (1,3): 53.13010235415599 So I don't think it's a bug in my code, but that is pretty odd.
- PseuRanAcc 8y ago
  Technically these should be reduced to (1,-1), (1,2) and (2,-2), (1,3) which should have angles >60.
- svat 8y ago
  Took me a while, but I think I figured it out! 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.
  - svat 8y ago
    Can't edit the above post, but when trying to write this up more carefully I realized it's not correct: (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.
PseuRanAcc 8y ago
This is something that has to do with Lattice basis reduction (https://en.wikipedia.org/wiki/Lattice_reduction https://en.wikipedia.org/wiki/Lattice_reduction). Rough explanation: if the angle is less than 60, then subtracting the smaller vector of the larger vector will produce one with smaller coefficients.
- svat 8y ago
  Is it something special about 60 degrees, that causes this? 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?
  - PseuRanAcc 8y ago
    Yes, using some linear algebra: - The inner product (or dot product) of two vectors is related to the angle (a,b) = |a||b|cos(angle). - 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.
    - svat 8y ago
      Thanks. I guess what you've shown is that if two vectors a and b are at an angle such that cos(angle) > 1/2, then (a-b) is shorter than a. Don't we also need to say something about the angle between (a-b) and b? It's late at night and I can't figure out what that is. :-) I imagine we'd have to say that it's no further from 60° than the angle between a and b was (but actually that's not true, so I guess the claim is something else?) 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.

myWindoonn 8y ago

I suspect that the quality of the solution is due to the connection between continued fractions and best approximants. The author notes that the approximants alternate between being usable and non-usable, which is characteristic of continued-fraction-generated approximants, which "flip" every time and have a sort of parity as a result.