Erdős–Anning theorem

Dense points on a unit circle generated by rotations of a 3–4–5 right triangle. All pairwise distances among these points are rational numbers. Scaling any finite subset of these points by the least common denominator of their distances produces an arbitrarily large finite set of points at integer distances from each other.

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.[1] 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.[2] 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.[3]

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.[2] 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.[1]

Illustration for a proof of the Erdős–Anning theorem. Given three non-collinear points A, B, C with integer distances from each other (here, the vertices of a 3–4–5 right triangle), the points whose distances to A and B differ by an integer lie on a system of hyperbolas and degenerate hyperbolas (blue), and symmetrically the points whose distances to B and C differ by an integer lie on another system of hyperbolas (red). Any point with integer distance to all three of A, B, C lies on a crossing of a blue and a red curve. There are finitely many crossings, so finitely many additional points in the set. Each branch of a hyperbola is labeled by the integer difference of distances that is invariant for the points on that branch.

Shortly after the original publication of the Erdős–Anning theorem, Erdős provided the following proof.[4] It is simpler than the original proof. Additionally, it relates the maximum size of an integer-distance set to the maximum distance between the points (the diameter of the set).[5] More specifically, if a set of three non-collinear points have integer distances, all at most some number ${\displaystyle \delta }$, then at most ${\displaystyle 4(\delta +1)^{2}}$ points (including the three given points) have integer distances from all three. Therefore, any set of non-collinear points, all at integer distances at most ${\displaystyle \delta }$ from each other, can have at most ${\displaystyle 4(\delta +1)^{2}}$ points in total.[4]

The proof involves finding a system of curves so that each point of the set lies on a crossing of two of the curves, and bounding the number of crossings. Let ${\displaystyle A}$, ${\displaystyle B}$ and ${\displaystyle C}$ be any three non-collinear members of a set ${\displaystyle S}$ of points with integer distances, and let ${\displaystyle d}$ denote the Euclidean distance function. Let ${\displaystyle X}$ be any other member of ${\displaystyle S}$. From the triangle inequality it follows that ${\displaystyle |d(A,X)-d(B,X)|}$ is a non-negative integer and is at most ${\displaystyle d(A,B)\leq \delta }$. For each of the ${\displaystyle d(A,B)+1}$ integer values ${\displaystyle i}$ in this range, the points satisfying the equation ${\displaystyle |d(A,X)-d(B,X)|=i}$ lie on a hyperbola with ${\displaystyle A}$ and ${\displaystyle B}$ as its foci, and ${\displaystyle X}$ must lie on one of these ${\displaystyle d(A,B)+1}$ hyperbolae. By a symmetric argument, ${\displaystyle X}$ must also lie on one of a family of ${\displaystyle d(B,C)+1}$ hyperbolae having ${\displaystyle B}$ and ${\displaystyle C}$ as foci. Each pair of distinct hyperbolae, one defined by ${\displaystyle A}$ and ${\displaystyle B}$ and the second defined by ${\displaystyle B}$ and ${\displaystyle C}$, can intersect in at most four points, by Bézout's theorem. Every point of ${\displaystyle S}$ (including ${\displaystyle A}$, ${\displaystyle B}$ and ${\displaystyle C}$) lies on one of these intersection points. There are at most ${\displaystyle 4(\delta +1)^{2}}$ intersection points of pairs of hyperbolae, and therefore at most ${\displaystyle 4(\delta +1)^{2}}$ points in ${\displaystyle S}$.[4]

The quadratic dependence of this bound on ${\displaystyle \delta }$ can be improved: every non-collinear point set with integer distances and diameter ${\displaystyle \delta }$ has size ${\displaystyle O(\delta )}$. However, it is not possible to replace ${\displaystyle \delta }$ by the minimum distance between the points: there exist arbitrarily large non-collinear point sets with integer distances and with minimum distance two.[5]

Five-vertex Erdős–Diophantine graph

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.[6]