
The Erdős–Anning theorem states that, whenever an
infinite number of points in the plane all have
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
distances, the points lie on a
straight line
In geometry, a straight line, usually abbreviated line, is an infinitely long object with no width, depth, or curvature, an idealization of such physical objects as a straightedge, a taut string, or a ray of light. Lines are spaces of dimens ...
. The same result holds in higher dimensional
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
s.
The theorem cannot be strengthened to give a finite bound on the number of points: there exist arbitrarily large finite sets of points that are not on a line and have integer distances.
The theorem is named after
Paul Erdős
Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
Norman H. Anning, who published a proof of it in 1945. Erdős later supplied a simpler proof, which can also be used to check whether a point set forms an
Erdős–Diophantine graph
An Erdős–Diophantine graph is an object in the mathematical subject of Diophantine equations consisting of a set of integer points at integer distances in the plane that cannot be extended by any additional points. Equivalently, in geometric ...
, an inextensible system of integer points with integer distances. The Erdős–Anning theorem inspired the
Erdős–Ulam problem on the existence of
dense point sets with rational distances.
Rationality versus integrality

Although there can be no infinite non-
collinear
In geometry, collinearity of a set of Point (geometry), points is the property of their lying on a single Line (geometry), line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, t ...
set of points with integer distances, there are infinite non-collinear sets of points whose distances are
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example,
The set of all ...
s. For instance, the subset of points on a
unit circle
In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucli ...
obtained as the even multiples of one of the
acute angles of an integer-sided
right triangle
A right triangle or right-angled triangle, sometimes called an orthogonal triangle or rectangular triangle, is a triangle in which two sides are perpendicular, forming a right angle ( turn or 90 degrees).
The side opposite to the right angle i ...
(such as the
triangle with side lengths 3, 4, and 5) has this property. This construction forms a
dense set
In topology and related areas of mathematics, a subset ''A'' of a topological space ''X'' is said to be dense in ''X'' if every point of ''X'' either belongs to ''A'' or else is arbitrarily "close" to a member of ''A'' — for instance, the ...
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
Stanisław Marcin Ulam ( ; 13 April 1909 – 13 May 1984) was a Polish and American mathematician, nuclear physicist and computer scientist. He participated in the Manhattan Project, originated the History of the Teller–Ulam design, Telle ...
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
In mathematics, the lowest common denominator or least common denominator (abbreviated LCD) is the lowest common multiple of the denominators of a set of fractions. It simplifies adding, subtracting, and comparing fractions.
Description
The lo ...
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 assumes a given set of points with integer distances, not all on a line. It then proves that this set must be finite, using a system of curves for which each point of the given set lies on a crossing of two of the curves. In more detail, it consists of the following steps:
*Arbitrarily choose a triangle
formed by three of the given points. The figure shows an example for which these three chosen points form a
right triangle
A right triangle or right-angled triangle, sometimes called an orthogonal triangle or rectangular triangle, is a triangle in which two sides are perpendicular, forming a right angle ( turn or 90 degrees).
The side opposite to the right angle i ...
(yellow) with edge lengths 3, 4, and 5.
*Let
denote the
Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of the line segment between them. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, and therefore is o ...
function. For any given point
, the integer
is at most
, by the
triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
This statement permits the inclusion of Degeneracy (mathematics)#T ...
. Thus,
lies on one of
hyperbola
In mathematics, a hyperbola is a type of smooth function, smooth plane curve, curve lying in a plane, defined by its geometric properties or by equations for which it is the solution set. A hyperbola has two pieces, called connected component ( ...
s, defined by equations of the form
with
. These are shown in blue in the figure. For
this equation instead defines two
rays
Ray or RAY may refer to:
Fish
* Ray (fish), any cartilaginous fish of the superorder Batoidea
* Ray (fish fin anatomy), the bony or horny spine on ray-finned fish
Science and mathematics
* Half-line (geometry) or ray, half of a line split at an ...
extending in opposite directions on the line through
and
(also shown in blue); this pair of rays can be treated as a
degenerate hyperbola for the purposes of the proof.
*By a symmetric argument,
must also lie on one of
hyperbolas or degenerate hyperbolas defined by equations of the form
with
. These are shown in red in the figure.
*The blue and red hyperbolas containing
cannot coincide, because they have different pairs of
foci
Focus (: foci or focuses) may refer to:
Arts
* Focus or Focus Festival, former name of the Adelaide Fringe arts festival in East Australia Film
* ''Focus'' (2001 film), a 2001 film based on the Arthur Miller novel
* ''Focus'' (2015 film), a 201 ...
. Thus,
must be a point where they intersect. Each pair of a blue and red hyperbola have at most four intersection points, by
Bézout's theorem
In algebraic geometry, Bézout's theorem is a statement concerning the number of common zeros of polynomials in indeterminates. In its original form the theorem states that ''in general'' the number of common zeros equals the product of the de ...
.
* Because each given point must be one of these intersection points, the number of given points is at most the product of the number of pairs of hyperbolas and the number of intersections per pair. This is at most
points, a finite number.
The same proof shows that, when the
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...
of a set of points with integer distances is
, there are at most
points. The quadratic dependence of this bound on
can be significantly improved: if a set with integer distances and diameter
is collinear, it obviously has at most
points, and if it is not collinear, it has size
, where the
uses
big O notation
Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
. 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
An Erdős–Diophantine graph is an object in the mathematical subject of Diophantine equations consisting of a set of integer points at integer distances in the plane that cannot be extended by any additional points. Equivalently, in geometric ...
.
The proof of the Erdős–Anning theorem can be used in an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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 hyperbolas used in the proof, and check whether any of the resulting points also have integer coordinates and integer distances from the given set.
Higher dimensions
As Anning and Erdős wrote in their original paper on this theorem, "by a similar argument we can show that we cannot have infinitely many points in
-dimensional space not all on a line, with all the distances being integral."
References
{{DEFAULTSORT:Erdos-Anning theorem
Arithmetic problems of plane geometry
Theorems in discrete mathematics
Articles containing proofs
Theorems in discrete geometry
Anning theorem