4 ms·
60-degree angles on a lattice
- tomsmeding 8y agoAfter constructing the two rays at an angle of approximately 60 degrees, the author goes about constructing an actual (approximate) equilateral triangle by drawing two perpendiculars. That might be useful if one needs a triangle of precisely that size, but given a pair of compasses (or a straightedge with two markings), one gets any ≈equilateral triangle by just marking the two intersection points of any circle around the origin with the two rays. I believe this method doesn't give anything less precise than the method outlined in the post. Given that the idea was to make the construction simple and small, I'm surprised the compasses method wasn't chosen.
- Timothee 8y agoI was confused as well, but I think the idea is that he's using only graph paper and a straightedge without measurement. (or markings) So he has to place points with integer coordinates on the graph paper, and draw lines between them.
- rocqua 8y agoThat's an interesting number set. The set of all points that can be produced from a straight-edge and the grid of integers. I'm pretty sure this is just the grid of rational numbers. Interestingly, this is a subset of the 'constructible' numbers. That is, the numbers that can be produced from a compass and straight-edge (without even needing a grid).
- joppy 8y agoIt’s not so surprising, since once you have a compass, straightedge, and a line segment you call “unit length”, you can construct all of the integer valued points in the plane.
- deleted 8y ago[deleted]
- svat 8y agoThe post is titled “60-degree angles on a lattice”, and links to “how to draw a good approximation to an equilateral triangle on a piece of graph paper” — that is, the problem being considered is one where all coordinates have to be integers. If you're willing to use compasses and get arbitrary coordinates, you don't need any of this, not even the first part — it's an entirely different (and much simpler) problem.
- tomsmeding 8y agoRight, of course; thanks for noting.
- joefkelley 8y agoThe (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 agoWhy are they all >60? (The idea is just to find the closest to 60, right?)
- joefkelley 8y agoNo 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 agoTechnically these should be reduced to (1,-1), (1,2) and (2,-2), (1,3) which should have angles >60.
- svat 8y agoTook 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.
- deleted 8y ago[deleted]
- hardmath123 8y agoOh, wow, beautiful. I wonder if there's a way to rephrase this as a diophantine approximation problem? If one ray must be axis-aligned then of course it's just the convergents for √3, but with two rays it's a little trickier.
- Snawoot 8y agoOne can build arbitrary approximate angles using lattices. Lets assume we need 50 degrees angle and we have piece of paper with 100x100 cells. We can construct rightangled triangle and seek for closest legs proportion which gives desired angle between one of legs and hypotenuse. Desired proportion must be rational number closest to tan(50 deg). We can find such rational number by seeking Farey sequence limited with denominator less than 100. So, for this case triangle with 87 and 73 cell legs will give us 50.000644597558434 degrees angle. Looks pretty good result to me. I think, in case with two non-aligned rays we can reduce it to first case by building two triangles and constructing angle between hypotenuses. Useful links: https://en.wikipedia.org/wiki/Farey_sequence https://en.wikipedia.org/wiki/Farey_sequence https://www.oreilly.com/library/view/python-cookbook/0596001673/ch17s17.html https://www.oreilly.com/library/view/python-cookbook/0596001... - python implementation of search in Farey sequence.
- svat 8y agoWe can indeed relate this problem to the “usual” Diophantine approximation problem of approximating a number α by a rational number p/q, but there's a twist. The “usual” problem, where we want p/q to be close to a real number α, can be thought of as finding Gaussian integers (q + ip) that lie close to the line y=αx in the complex plane, i.e. points z on the lattice such that Im(z)/Re(z) ≈ α. Here, with α=√3, we want to solve the same problem, i.e. find rational numbers p/q close to α, except that p/q must further be of the form (ad-bc)/(ac+bd) for some (a, b, c, d). Here's the thing: this is precisely the same as saying that (q + ip) is not a Gaussian prime! This is because (a-ib)(c+id) = (ac+bd) + i(ad-bc). (https://en.wikipedia.org/w/index.php?title=Brahmagupta%E2%80%93Fibonacci_identity&oldid=863796842 https://en.wikipedia.org/w/index.php?title=Brahmagupta%E2%80...) So any (q + ip) of the form (ac+bd) + i(ad-bc) can be written as the product of two Gaussian integers, and vice-versa. So the relation between the Diophantine approximation problem and this one is that while there we want to find Gaussian integers close to the line Im(z)=αRe(z), here we want to find composite Gaussian integers close to the line Im(z)=αRe(z). (Note we can get different "best" approximations depending on how we measure closeness; see my other comment here: https://news.ycombinator.com/item?id=18555240 https://news.ycombinator.com/item?id=18555240 Also, I expect that as denominators get larger, the primes get sparser, so this becomes closer to the usual problem. Of course in the original post linked here, the goal is to find small solutions, so the difference matters.)