The ős–Erdős–Anning theorem states that an infinite number of points in the plane can have mutual integer distances only if all the points lie on a straight line. It is named after Paul Erdős and Norman H. Anning, who published a proof of it in 1945.
Rationality versus integrality
Although there can be no infinite non-collinear set of points with integer distances, there are infinite non-collinear sets of points whose distances are rational numbers. For instance, the subset of points on a unit circle obtained by repeatedly rotating by the sharp angle in a 3–4–5 right triangle has this property. It forms a dense set in the circle. The (still unsolved) Erdős–Ulam problem asks whether there can exist a set of points at rational distances from each other that forms a dense set for the whole Euclidean plane. According to Erdős, Stanisław Ulam was inspired to ask this question after hearing from Erdős about the Erdős–Anning theorem.
For any finite set S of points at rational distances from each other, it is possible to find a similar set of points at integer distances from each other, by expanding S by a factor of the least common denominator of the distances in S. By expanding in this way a finite subset of the unit circle construction, one can construct arbitrarily large finite sets of non-collinear points with integer distances from each other. However, including more points into S may cause the expansion factor to increase, so this construction does not allow infinite sets of points at rational distances to be transformed into infinite sets of points at integer distances.
Proof
Shortly after the original publication of the Erdős–Anning theorem, Erdős provided the following simpler proof.
The proof involves finding a system of curves so that each point of the set lies on a crossing of two of the curves. Given a set of points with integer distances, not all on a line, arbitrarily choose a triangle formed by three of the points. Let denote the Euclidean distance function. For any given point , the integer is at most , by the triangle inequality. Thus, lies one of hyperbolae, defined by equations of the form with . By a symmetric argument, must also lie on one of hyperbolae defined by equations of the form . The two hyperbolae containing cannot coincide, so must be a point where they intersect. There are choices of and , and at most four intersection points for each choice, by Bézout's theorem. Because each given point must be one of these intersection points, the given set of points must contain at most points, a finite number.
The same proof shows that, when the diameter of a set of points with integer distances is , there are at most points. The quadratic dependence of this bound on can be improved, using a similar proof but with a more careful choice of the pairs of points used to define families of hyperbolae: every point set with integer distances and diameter has size . However, it is not possible to replace by the minimum distance between the points: there exist arbitrarily large non-collinear point sets with integer distances and with minimum distance two.
Maximal point sets with integral distances
An alternative way of stating the theorem is that a non-collinear set of points in the plane with integer distances can only be extended by adding finitely many additional points, before no more points can be added. A set of points with both integer coordinates and integer distances, to which no more can be added while preserving both properties, forms an Erdős–Diophantine graph.
The proof of the Erdős–Anning theorem can be used in an algorithm to check whether a given set of integer points with integer distances forms an Erdős–Diophantine graph: merely find all of the crossing points of the hyperbolae used in the proof, and check whether any of the resulting points also have integer coordinates and integer distances from the given set.