Some time ago, one of my facebook friends posted a quote of a result by Paul Erdös:
If an infinite set of points in the plane determines only integer distances, then all the points lie on a straight line.
When a mathematician reads something like this, after realizing that it is a nice result, the first question that comes to his mind is: is it possible to construct a finite set of n points in the plane that do not lie in a straight line, and whose distances are all integers?
Well, it is easy to see that one can do that for n=3 (just consider any Pythagorean triple, such as the triangle with sides 3, 4, and 5). But is it possible to do that for an arbitrary n? The answer is not obvious at first, unless you have thought about the problem before (although that this is probably a very well established result). Actually, the proof of the statement above, called the Erdös-Anning theorem, was published in 1945, and the proof already contains a solution to the case with finitely many points. However, although beautiful, the example that the paper provides is overcomplicated, from my point of view.
Plus, I didn't know the answer to this question, and I realized that many of my fellows didn't know it either, so I started to try to construct examples of sets of non-aligned points with integer distances between them.
From the example of the triangle, it was easy to construct a set of n=4 points with this property, just by considering the rectangle of sides 3 and 4 (whose diagonal has length 5). But again, being able to do it for n=4 points doesn't mean that it can be done for any number of points, and I didn't see how to generalize that construction.
Plus, I didn't know the answer to this question, and I realized that many of my fellows didn't know it either, so I started to try to construct examples of sets of non-aligned points with integer distances between them.
From the example of the triangle, it was easy to construct a set of n=4 points with this property, just by considering the rectangle of sides 3 and 4 (whose diagonal has length 5). But again, being able to do it for n=4 points doesn't mean that it can be done for any number of points, and I didn't see how to generalize that construction.
After n=4, my goal was to construct a set with many other points. One idea that came to my mind was to consider a regular hexagon inscribed in a circumference, together with its center, a set with n=7 points. I considered this example, because in order to have control on the distances, it is better to have as much symmetry as possible in our set of points. Unfortunately, I realized that it is impossible to construct a regular hexagon whose distances are all integers, no matter what the distance between two adjacent points is (the distance between two non-consecutive points in the hexagon is always an irrational number if the side of the hexagon is an integer).
Hence I decided to come back to the idea of using Pythagorean triples, constructing some kind of symmetric set of points. I realized that an easy way to construct a set of n=5 points was by using four triangles with sides 3, 4, and 5 to form a rhombus with sides of length 5. The vertices of the rhombus together with the intersection of the two diagonals are a set of 5 points with the desired property.
Hence I decided to come back to the idea of using Pythagorean triples, constructing some kind of symmetric set of points. I realized that an easy way to construct a set of n=5 points was by using four triangles with sides 3, 4, and 5 to form a rhombus with sides of length 5. The vertices of the rhombus together with the intersection of the two diagonals are a set of 5 points with the desired property.
With this construction in mind, I realized that if we add points in the big diagonal of the rhombus at some integer distance l from the center (i.e., from the intersection of the two diagonals), in such a way that its distance x to the points in the small diagonal is also an integer, then we get a construction with more than n=5 points that do not lie in a line and whose distances are all integers. Unfortunately, it is not possible to do that with the Pythagorean triple that I chose, because the smallest side of the triangle, 3, doesn't have enough divisors (it is prime).
That's why I decided to try this construction with a rhombus build from four triangles with sides 8, 15, and 17. Since we want the distances x and l to be integer, when applying the Pythagorean theorem to the triangle with sides 8, l, and x, we get x²=l²+8², hence 8²=x²-l²=(x+l)(x-l), so we have to consider all the possible solutions where x+l and x-l are factors of 8²=64. It turns out that this system has one non-trivial solution for l=6 (hence x=10), so we can add two points in the big diagonal at distance 6 from the center, creating a set of n=7 points with the desired properties.
That's why I decided to try this construction with a rhombus build from four triangles with sides 8, 15, and 17. Since we want the distances x and l to be integer, when applying the Pythagorean theorem to the triangle with sides 8, l, and x, we get x²=l²+8², hence 8²=x²-l²=(x+l)(x-l), so we have to consider all the possible solutions where x+l and x-l are factors of 8²=64. It turns out that this system has one non-trivial solution for l=6 (hence x=10), so we can add two points in the big diagonal at distance 6 from the center, creating a set of n=7 points with the desired properties.
Similarly, if the rhombus is build out of four triangles with sides 12, 35, and 37, with sides of length 37, we can add six points in the big diagonal at distances 5, 9, and 16 from the center respectively, creating a set of n=11 points with the desired property.
It seems reasonable that this method can be generalized, and that given a Pythagorean triple with a small side with sufficiently many divisors, we might be able to construct a set with this properties with a number of points n as large as we want. Actually, we could do an analogous construction by adding points to the small diagonal (the key idea is that we only add points in one of the diagonals, to avoid having to deal with too many possibly non-integer distances). Doing it for a general Pythagorean triple seems difficult (we don't have enough control on the divisors); however, we can do it in the particular case where one of the cathetus is a power of 2.
First of all, notice that any power of 2, say 2^k, is the length of the cathetus of a Pythagorean triangle, the Pythagorean triple being (2^(p+q+1), 2^(2p)-2^(2q), 2^(2p)+2^(2q)), where n=p+q+1 and p>q are integers. The way I came up with this triple is by using Euclid's formula to generate Pythagorean triples. Now, we can use the same method as before to add points in the cathetus of length 2^(2p)-2^(2q).
If a point is added at distance l from the center, and x represents de distance to the top (or the bottom) vertex, by the Pythagorean theorem we have 2^(2k)+l² = x², so we have the equation 2^(2k) = (x+l)(x-l). Since we want x and l to be integers, we have to solve the systems of equations x+l = 2^(2k-i), x-l=2^i, for i any integer between 0 and k (since we can assume x+l>x-l, restricting to l>0). This system always has a solution; however, some of the solutions are not valid for our purposes, namely when i=k (in which case l=0), when i=2q+1 (in which case we get a point that we already had), and when i=0 (in which case we get a non-integer). Hence, at the end of the day, we can add 2(k-2) points to the rhombus, which already has 5 points, so we get an example with n=2k+1 points. Of course, this is the case as long as all the solutions that we get are different; but this is something not too difficult to prove (you can see the details in the notes for the talk that I gave in the Math Club at UCR).
Hence, this proves that it is possible, using this construction, to get a set with any odd number of non-aligned points in the plain whose distances are integer numbers. By removing one of the points, we get the result for any even number of points, thus for any number.
After proving that, the Erdös-Anning theorem becomes even more interesting and mysterious!
First of all, notice that any power of 2, say 2^k, is the length of the cathetus of a Pythagorean triangle, the Pythagorean triple being (2^(p+q+1), 2^(2p)-2^(2q), 2^(2p)+2^(2q)), where n=p+q+1 and p>q are integers. The way I came up with this triple is by using Euclid's formula to generate Pythagorean triples. Now, we can use the same method as before to add points in the cathetus of length 2^(2p)-2^(2q).
If a point is added at distance l from the center, and x represents de distance to the top (or the bottom) vertex, by the Pythagorean theorem we have 2^(2k)+l² = x², so we have the equation 2^(2k) = (x+l)(x-l). Since we want x and l to be integers, we have to solve the systems of equations x+l = 2^(2k-i), x-l=2^i, for i any integer between 0 and k (since we can assume x+l>x-l, restricting to l>0). This system always has a solution; however, some of the solutions are not valid for our purposes, namely when i=k (in which case l=0), when i=2q+1 (in which case we get a point that we already had), and when i=0 (in which case we get a non-integer). Hence, at the end of the day, we can add 2(k-2) points to the rhombus, which already has 5 points, so we get an example with n=2k+1 points. Of course, this is the case as long as all the solutions that we get are different; but this is something not too difficult to prove (you can see the details in the notes for the talk that I gave in the Math Club at UCR).
Hence, this proves that it is possible, using this construction, to get a set with any odd number of non-aligned points in the plain whose distances are integer numbers. By removing one of the points, we get the result for any even number of points, thus for any number.
After proving that, the Erdös-Anning theorem becomes even more interesting and mysterious!
| Notes_Talk_DiscoveringATheoremByErdos_MathClubUCR.pdf |
RSS Feed
