The 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.
Contents
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. The (still unsolved) Erdős–Ulam problem asks whether there can exist a dense set of points in the plane at rational distances from each other.
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. Therefore, there exist 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 translated to infinite sets of points at integer distances.
Proof
To prove the Erdős–Anning theorem, it is helpful to state it more strongly, by providing a concrete bound on the number of points in a set with integer distances as a function of the maximum distance between the points. More specifically, if a set of three or more non-collinear points have integer distances, all at most some number
To see this, let A, B and C be three non-collinear members of a set S of points with integer distances, all at most
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.