Образователни технологии
ERDÖS’ DISTINCT DISTANCES PROBLEM
Резюме. In discrete geometry, the Erdös’ distinct distances problem states that between \(n\) distinct points in a plane there are at least \(n^{1-o(1)}\) distinct distances. The problem was posed by Paul Erdös in 1946. In 2010, Larry Guth and Net Hawk Katz claimed to have a solution. The solution was published in 2015 in the Annals of Mathematics. This article aims at popularizing this problem to young students in mathematics, therefore no big background in mathematics is needed to understand it. It is open to every reader and shall be improved with any remarks or questions.
Ключови думи: geometry; the Erdös’ distinct distances problem; young students
I. Introduction
Let’s consider 3 points. We will consider the problem in a plane.
Figure 1. 3 points in a plane
Those 3 points constitute a triangle, and we can wonder how many distinct distances we can make with those 3 points. If the triangle has nothing special and is random, we can find 3 distinct distances.
Figure 2. 3 distinct distances – random (arbitrary) triangle
However, if we consider an isosceles triangle, it has only 2 distinct distances.
Figure 3. 2 distinct distances – isosceles triangle
Besides, if we consider another special type of triangle, we can manage to have only one single distance for each point. This case corresponds to equilateral triangle.
Figure 4. One single distance between all points – equilateral triangle
In that configuration all distances have same value. The minimum number of distinct distances is 1.
Summary:
Given 3 points, the minimum number of distinct distances is 1.
II. Problem formulation and Overview
With this little overview of the problem considering 3 points, we can formulate the following general problem:
Given number \(n\), what is the minimum number of distinct distances between \(n\) points in a plane?
Definition. \(d(n)\) is the minimum number of distinct distances between \(n\) points.
We will consider the problem by dealing with the following points:
– Short biography
– Great dependency on initial points
– Combinatorial geometry
– Asymptotic approximations
The problem is about estimating the minimum number of distinct distances between \(n\) points, where \(n\) is a given number. With the example in (ii), we will see that given a number \(n\), we can have different positioning that give different number of distinct distances.
i – Short Biography \({ }^{1)}\)
Figure 5. Paul Erdös
Paul Erdös (26 March 1913 / 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians of the 20th century. He was known both for his social practice of mathematics (he engaged more than 500 collaborators) and for his eccentric lifestyle.
Erdös published around 1,500 mathematical papers during his lifetime, a figure that remains unsurpassed. He firmly believed mathematics to be a social activity, living an itinerant life style with the sole purpose of writing mathematical papers with other mathematicians. Erdös’ prolific output with co-authors prompted the creation of the Erdös number, the shortest path between a mathematician and Erdös in terms of co-authorships. Erdös pursued and proposed problems in discrete mathematics, graph theory, number theory, mathematical analysis, approximation theory, set theory, and probability theory.
Ii – Initial Points Dependency
Considering \(n n\) points with coordinates \((k, 0)\) for \(k\) in \(\{1, \ldots, n\}\) :
Figure 6. Regular spacing between n points
The number of distinct distances is \(n-1\).. However, if we consider \(n\) points with coordinates \(\left(2^{k}, 0\right)\) for \(k\) in \(\{1, \ldots, n\}\)
Figure 7. Regular spacing between n points
The number of distinct distances is \(\tfrac{n(n-1)}{2}\). Indeed, we can prove that each distance is different from another. One can observe that these two examples show the dependency on initial points when considering the number of distinct distances. The problem will consist in determining the minimum number of distinct distances, therefore, we may consider changing positions for \(n\) given points.
Iii – Combinatorial Geometry
Combinatorial geometry is a blending of principles from the areas of combinatorics and geometry. It deals with combinations and arrangements of geometric objects and discrete properties of these objects. It is concerned with such topics as packing, covering, coloring, folding, symmetry, tiling, partitioning, decomposition, and illumination problems. Although combinatorial geometry was studied by classical mathematicians such as Euler and Kepler, many advances have been made since the middle of the 20th century. This topic was one which drew the interest of the late prolific mathematician Paul Erdös \({ }^{1}\).
Iv – Asymptotic approximations
For small values of \(n n\), it will be easy to determine the minimum number of different distances. But for larger values, we will need to use estimates of the value we are looking for. Therefore, we will define rapidly useful notations when doing asymptotic approximations. Those notations are popularized for a large public.
Let \(g\) and \(f\) be functions of \(N\) (i.e. \(g(N)\) and \(f(N)\) are two numbers which both depend on \(N\) ).
- \(g(N)=O(f(N))\) if and only if \(|g(N) / f(N)|\) is bounded from above (i.e we can find \(M\) so that \(|g(N) / f(N)| \lt M\) ) when \(N\) becomes "large enough". (We say that \(N \rightarrow+\infty\) )
- \(g(N) \sim f(N)\) if and only if \(|g(N) / f(N)|\) is as close as we want to 1 , when \(N\) becomes "large enough". (We say that \(N \rightarrow+\infty\) )
Those notations will be used after we have seen first examples with small values of \(n\), where \(n\) is the number of given points.
III. Examples for small values of \(n\)
Before trying to determine values for small values of \(n n\), we can make the following observations:
● \(n\) is a positive integer
● For \(n\) points in a plane, we can find \(\tfrac{n(n-1)}{2}\) possible distances. Indeed, it is easy to understand that for each point among \(n\) possible ones, it can be linked to another among \(n-1\) possible ones. But counting this way implies to count each distance twice. Therefore, the result has to be divided by 2. With reference to the problem with \(d(n)\), where \(d(n)\) is the minimum number of distinct distances, we can observe that:
(1) \(d(n) \leq \cfrac{n(n-1)}{2}\)
● We can also easily state that the minimum number of distances is at least 1, knowing that we will consider at least two points \(n \geq 2\), thus \(d(n) \geq 1\)
● Last but not least, if we add one point to a disposition of \(n\) points, the minimum number of different distances is easily larger than the minimum number of different distances with \(n\) points:
(2) \[ d(n) \leq d(n+1) \]
For \(n=2\), there are only two points, therefore \(d(2)=1\).
Figure 8. 2 points
For \(n=3 n\), as we have seen, \(d(3)=1\),
Figure 9. 3 points
For \(n=4\), we know that \(d(4) \geq 1\). But is it possible to have \(d(4)=1\) ?
Proof Reduction Ad Absurdum. Let’s suppose that \(d(4)=1\). Therefore, only one distance is available to set points. Let’s sketch the figure. If we set two points, it will determine the only distance we can use when placing the other points.
It is only possible to place the third point in one of those two intersections (i.e C or D), otherwise one distance between two points among three of those will be different.
Without lost of generality, let’s place it in D, we then obtain the following figure (to obtain the other one, just reverse the figure).
Therefore, we have built the 3 first points, and still have to place the 4th one, i.e the last one. Since only one possible distance is to be used, the 4th point has to be at same distance to A and B, therefore has to be C. But if it is C, then the distance with \(D\) will be different (see the next figure).
Thus, this disposition is impossible, and C is not the 4-th point. We can use same reasoning for E and F, and therefore conclude that we cannot have only one possible distance to set 4 points at same distance to each other. We conclude that \(d(4)=1\) is absurd, and therefore \(d(4) \geq 2\).
We can now find a positioning where we only use two different distances. This positioning is the one using a square, with one distance being the side of the square, and the other one being the diagonal of the square.
Figure 10. 4 points, using two different distances
Since we have \(d(4) \geq 2\) with the previous proof and considering this positioning, we can therefore conclude that for \(n=4, d(4)=2\).
For \(\mathrm{n}=5\), we know that \(d(5) \geq d(4)\) by using equation (2). Can we find a solution with 5 points using only 2 different distances?
Figure 11. 5 points, using two different distances
It is indeed possible with a regular pentagon. One distance is the side, the other one is the diagonal.
For \(n=6,7\) it is left as an exercise to the reader.
Hint: Prove that it is impossible to have \(d(6)=2\) and then find figures where \(d(6)=3, d(7)=3\).
IV. Erdös Conjecture
The popularized principle of Erdös conjecture would be that the number \(d(n)\) is "nearly close" to \(n\) when \(n\) grows.
We will try to popularize the mathematical formulation, though:
Conjecture. For any \(a \lt 1\) we can find \(C \gt 0\) for which \(d(n) \gt C . n^{a}\) for \(n\)“big enough". \((n \rightarrow+\infty)\). Let's first explain what \(n^{a}\) means, where \(a\) is a real number.
i – Real number exponents
Let’s first make a reminder.
Definition. Let \(n\) be a positive integer.
\(a^{n}=a * a \ldots * a\)
\(n\) times
\(a^{-n}=\tfrac{1}{a^{n}}\)
Then, we introduce the following definition.
Definition. Let \(p\) and \(q\) be positive integers.
\(a^{\tfrac{p}{q}}\) is the number \(b\) for which we have:
\(a^{p}=b^{q}\)
It is therefore now comprehensible to \(2,{ }^{167}\) write as \(1,67=\tfrac{167}{100}\) and therefore we can write it \(2^{\tfrac{167}{100}}\). We can also explain that rational numbers (i.e. those which can be written in the form \(\tfrac{p}{q}\) where \(p\) is an integer and \(q\) is a strictly positive integer) are dense among real numbers, and we can "approximate" any real number by a rational one. We now understand the notation \(n^{a}\) in Erdös conjecture.
Ii - Proof for \(\alpha=1 / 2\)
Proof that \(d(n) \geq C \sqrt{n}\). Let's consider \(n n\) points
\(A_{1}, A_{2}, \ldots A_{\mathrm{n}}\) and we will focus on \(A_{1}\) and \(A_{2}\).
Figure 12. n points with A1 and A2
Let’s consider circles with centers \(A_{1}\) or \(A_{2}\) passing through \(A_{3}, \ldots, A_{n}\). Let \(C_{1}\) denote the number of circles thus obtained centered at \(A_{1}\) (i.e. redones) and \(C_{2}\) the number of those centered at \(A_{2}\) (i.e. black ones)
Figure 13. A1 and A2 with circles
We assume, without loss of generality (even if we change the names of the two points), that \(C_{1} \geq C_{2}\). Since two circles with different centers have at most two points of intersection, there are at most \(2 c_{1} c_{2}\) points of intersec1c2 points of intersection in thefigure (\(c_{1}\) choice for the first circle, \(c_{2}\) c2 choice for the second and at most 2 choices for theintersection). Now, by construction, each of the remaining \(n-2\) poin – 2points of our starting set belong both to a circle centered at \(A_{1}\) and to a circle centered at \(A_{2}\), so each of them is a point of the intersection between the two circles. We thus have \(n-2 \leq 2 c_{1} c_{2}\) from which we deduce \(n-2 \leq 2 c_{1}{ }^{2}\). Therefore,
\[ c_{1} \geq \sqrt{\tfrac{n-2}{2}} \]
and we also know that \(d(n) \geq c_{1}\). Thus, \[ d(n) \geq \sqrt{\tfrac{n-2}{2}} \]
Using asymptotic approximations from II.iv, we can show easily that \(n-2 \sim n\), and therefore, when \(n\) is big enough, we eventually have:
\[ d(n) \geq C \sqrt{n} \]
Where \(C=1 / \sqrt{2}\).
Iii-Proof for \(\alpha=2 / 3\)
Proof that \(d(n) \geq C . n^{2 / 3}\). Let’s consider \(n\) points \(A_{1}, A_{2}, \ldots, A_{\mathrm{n}}\) such that the minimum distance is reached between \(A_{1}\) and \(A_{2}\). The line (\(A_{1}, A_{2}\) ) separates this cloud of points into two parts. One contains at least \(\tfrac{n-2}{2}\) points, using the pigeon hole principle. From now on, it is limited to those points.
Figure 14. n points separated by (A1,A2)
We now sketch successive half-crowns centered on the midpoint of \(\left[A_{1} A_{2}\right]\) of width \(A_{1} A_{2}\) until we cover all the remaining points.
Figure 15. n points separated by half-crowns
Let us divide these half-crowns modulo 3 into three sets.
Figure 16. Half-crowns modulo 3
At least one of these sets contains \(\tfrac{n-2}{6}\) points, by using pigeonhole principle again. It is now limited to these points.
Note that points belonging to distinct half-crowns (among remaining ones) cannot be at the same distance of \(A_{1}\) (respectively \(A_{2}\) ).
Figure 17. Half-crowns modulo 3, containing \(\cfrac{n-2}{6}\) points
By using same reasoning than the first proof ( \(\alpha=1 / 2\) ) we obtain that the \(n_{i}\) points of the half-crown \(i\) define at least \(\sqrt{n_{i}}\) distances to \(A_{1}\) or \(A_{2}\). Thus, the number of distinct distances \(\tilde{d}(n)\) for this configuration is greater or equal to (the sum relates to the half-crowns chosen) \(\sum_{i} \sqrt{n_{i}}\). Therefore,
\[ \tfrac{n-2}{6} \leq \sum_{i} n_{i} \leq \sqrt{\max \left(n_{i}\right)} \sum_{i} \sqrt{n_{i}} \leq \sqrt{\max \left(n_{i}\right)} \tilde{d}(n) \]
Now we consider the half-crown containing \(\max \left(n_{i}\right)\) points, then half of the crown containing the majority of the points that is to say at least \(\tfrac{1}{2} \max \left(n_{i}\right)\). Let \(P\) be a minimal ordinate point in this zone. A rapid calculation shows that if \(Q\) and \(R\) are equidistant from P in this half-crown, then \( \lt 2 A_{1} A_{2}\).
Figure 18. Quarter-crown containing \(\cfrac{1}{2}\max (n_i)\) ) points, with Q and P
There are thus at most two points of the zone at the same distance from P , which gives us at least \(\tfrac{1}{2}\left(\tfrac{1}{2} \max \left(\mathrm{n}_{\mathrm{i}}\right)-1\right)\) distinct distances. Hence, \(\max \left(n_{i}\right) \leq 4 \tilde{d}(n)+2\).
By deferring to previous inequality:
\(\tfrac{n-2}{6} \leq \sqrt{\max \left(n_{i}\right)} \tilde{d}(n)\) we now obtain:
\[ \tfrac{n-2}{6} \leq \tilde{d}(n) \sqrt{4 \tilde{d}(n)+2} \]
We now use asymptotic approximations knowing that \(\tilde{d}(n) \rightarrow+\infty\), when \(n\) becomes big enough, the left term of the inequality is equivalent to \(n\) and the right term is equivalent to \(2 \tilde{d}(n)^{3 / 2}\), therefore, we have:
\(C n^{2 / 3} \leq \tilde{d}(n)\)
and eventually with general configuration:
\[ d(n) \geq C \cdot n^{2 / 3} . \] where \(C=1 / 3^{\tfrac{2}{3}}\)
V. Latest results
We will now give an overview of the latest results, with firstly a popularization of logarithm:
i-Logarithm
Logarithm is a function which takes only strictly positive real numbers as arguments.
-We remember that 2.2.2 \(=8\), therefore \(2^{3}=8\). The number 3 is actually called common logarithm of 8 in base 2 .
- Likewise, 10.10.10.10=10000
\(10^{4}=10000\)
The number 4 is called common logarithm of 10000 in base 10 .
-e is a special number, \(\mathrm{e}=2,718 \ldots\)
– Definition. \(\ln (n)\) is number \(x\) for which \(e^{x}=n\).
– \(x=\ln (n)\) may not be an integer, and can be negative
ii – Latest results
Notation. We write \(f(n)=\Omega(g(n))\) when we can find \(C\gt 0\) 0 for which \(f(n)\gt Cg(n)\) for \(n\)
"big enough".
Paul Erdös' 1946 lower bound of \(d(n)=\Omega\left(n^{\tfrac{1}{2}}\right)\) was successively improved to:
- \(d(n)=\Omega\left(n^{\overline{3}}\right)\) (Leo Moser, 1952)
- \(d(n)=\Omega\left(n^{\tfrac{5}{7}}\right) \quad(\) Chung 1984)
- \(d(n)=\Omega\left(n^{\tfrac{4}{5}} \ln (n)\right)\) (Chung, Szemerédi and Trotter 1992)
- \(d(n)=\Omega\left(n^{\tfrac{4}{5}}\right) \quad\) (Székely 1993)
- \(d(n)=\Omega\left(n^{\tfrac{6}{7}}\right) \quad\) (Solymosi and Tóth 2001)
- ...
- \(d(n)=\Omega\left(\tfrac{n}{\ln (n)}\right) \quad\) (Guth and Katz 2015)
Note that the latest result is interesting because it is commonly known that for any \(a \gt 0\) we have:
\[ \tfrac{\ln (n)}{n^{\alpha}} \rightarrow 0 \]
\(\ln (n)\) is "weaker" than any \(n^{a}\) and we thus obtain the sharp exponent in the problem of Erdös.
NOTES
1. Paul Erdös Biography, Wikipedia.
2. Combinatorial Geometry, accessible at: http://mathworld.wolfram.com/ CombinatorialGeometry.html
REFERENCES
Erdös, P. (1986). On some metric and combinatorial geometric problems. Discrete Mathematics, 60, 147 – 153.
Mansuy, R. (2014). Les distances d’ Erdös. Images des Mathématiques, CNRS.
Mansuy, R. (2013). Le probléme des distances d’Erdös.Erdös, P. (1946). On sets of distances of \(n\) points. The American Mathematical Monthly, 53, 248 – 250.
Guth, L. & N. H. Katz (2015). On the Erdös distinct distance problem in the plane. ArXiV.