Xavier Ramos Olivé
  • Home
  • Research
    • Recorded Talks
  • Teaching
    • Student Evaluation Selection
    • Previous quarters
    • A-term 2019
  • About Me
    • AWM involvement
  • Blog

Integer distances in the plane

4/5/2016

5 Comments

 
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?
Picture
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.
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.
Picture
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.
Picture
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.
Picture
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!
Notes_Talk_DiscoveringATheoremByErdos_MathClubUCR.pdf
File Size: 1730 kb
File Type: pdf
Download File

5 Comments
Borja Sánchez
4/6/2016 01:39:08 pm

I have just read your text and I liked how you worked through the problem. I thought that you would probably like to know ( if you don't already know it ) the results that come after 2 theorems: The Huff's Theorem and Anning-Erdös Theorem ( in which you base your text ).

The Huff's Theorem constructs an infinite set, infinite many points on the x axis and 4 symetrical points on the y axis, where all distances between points are a rational number.

By considering only 2 symetrical points out of the 4 in the y axis, and finite many points of those on the x axis ( as much points as you want out of the infinite many points given ), you get a rhombus like the ones you show ( with all distances beeing rational ). All distances can become integer numbers by making our rhombus bigger ( just apply an homothecy with the appropiate ratio ).

One result that comes along the Anning-Erdös article, builds a set of n points, with integer distances between any 2 points, lying the whole set on a circle. The part you talk about regular hexagons reminds me to that set, by ignoring the 'regular' condition. You maybe would like to think about some examples of such set and show your work here too :)

I can provide to you the results I mentioned and more if you like, since the first one can be specially hard to find. I have a summary of both too ( in spanish ).

Thank you for your post !

Reply
Xavier Ramos
4/6/2016 02:28:34 pm

Thank you Borja!

Nice! I wasn't aware of Huff's Theorem! From what you say, it seems that this construction would give us constructions a little bit more "asymmetric" of n points in the plane with integer distances (just keeping a finite amount of them, without necessarily taking out the 4 in the y-axis, and doing a homothecy as you said, would give us solutions).

I checked the proof of Anning from 1945, and as you mentioned, they construct the example on a circle (without assumptions of regularity in the n-gon obtained). This proof shows that the construction can be done with the additional property of not having any 3 points in a line. Although that, I think that the construction above is more elementary. :)

I have seen people commenting that all the solutions for the finite case have either a lot of points in a line or a lot of points in a circle; I wonder if it is possible to do some more complicated constructions. In that sense, maybe Huff's theorem provides some idea (although most points still lie in a straight line). Do you know where can I find the Theorem of Huff?

Thanks for your comment!

Reply
Borja Sánchez
4/6/2016 04:02:38 pm

Hi Xavier. The question you last posted is an open question, once asked by Erdös:

Erdös' conjecture ( or problem ): "For every integer n, there exists a set of n points of the plane where all distances are integer numbers, with no 3 points on a line, nor 4 points on a circle."

We only have seen this for n lower than 8 so far. Ironically, we have found thousands of sets of 7 points achieving the Erdös conditions, but not a single one having 8 points.

Can 7 be the limit? It's a weird number to stop at :D

Also, the smallest example of an Erdös 7 points set reaches a distance of 22270 between 2 of the points, wich we call the diameter ( proved to be the lowest diameter possible for this kind of sets ). For the 6 points sets, it's just 174. The growth of the diameter looks exponential.

I think you can find the Huff's Theorem by searching the title of the article: "Eliptic Curves and Rational Distance Sets" by W.D.Peeples, one of his students. However, the article is more related to the Ulam's conjecture, that focuses rational sets of the plane instead.

The text isn't easy to read in my opinion. If you want a summary ( in spanish ) of it, I can send it to you if you tell me where. I guess you have my email adress in that case.

I recommend you to check this:

http://www.isthe.com/chongo/tech/math/n-cluster/

Considering the topic we are talking about, you can jump the n_k-cluster information and just read about n_2-clusters. I am sure you will find it as much interesting as i did :D

Don't doubt to contact me if you want my translated work of the issue. Goodbye!

Reply
Derk Pik
9/17/2022 05:16:47 am

Dear Xavier, A beautiful construction, nice post.
I wrote on this subject in the Dutch math youth magazine Pythagoras, in 2015: https://www.pyth.eu/pythagoras-archief
https://pyth.eu/uploads/user/ArchiefPDF/Pyth54-4.pdf
There we construct finitely many points with integer distance on a circle. The more points you get, the larger the circle gets.
Also the general problem is addressed in an (advanced) high school way.
Best regards, Derk

Reply
Anthony Lee link
10/17/2022 02:31:36 pm

Expect work sense current treatment point husband. Have authority decide what day school. Air in body change.

Reply



Leave a Reply.

    The author

    I am a Postdoctoral Scholar in the Department of Mathematical Sciences at Worcester Polytechnic Institute.

    Archives

    August 2020
    July 2018
    November 2016
    April 2016
    January 2016
    October 2015
    September 2015
    August 2015

    Categories

    All
    Category Theory
    Geometric Flows
    Gromov-Hausdorff
    Intrinsic Flat Convergence
    Metric Geometry
    MFO
    Relativity
    UCR

    RSS Feed

Powered by Create your own unique website with customizable templates.