en>Adius at 22:07, 11 January 2014

2014-01-11T22:07:06Z

New page

The '''Erdős–Anning theorem''' states that an [[Infinite set|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.<ref>{{citation
| first1 = Norman H.
| last1 = Anning
| first2 = Paul
| last2 = Erdős
| authorlink2 = Paul Erdős
| title = Integral distances
| journal = [[Bulletin of the American Mathematical Society]]
| volume = 51
| pages = 598–600
| year = 1945
| url = http://www.ams.org/bull/1945-51-08/S0002-9904-1945-08407-9/
| doi = 10.1090/S0002-9904-1945-08407-9
| issue = 8}}.</ref>

==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 number]]s. For instance, on the [[unit circle]], let ''S'' be the set of points <math>(\cos\theta,\sin\theta)</math> for which <math>\tan\frac{\theta}{4}</math> is a rational number. For each such point, both <math>\sin\frac{\theta}{2}</math> and <math>\cos\frac{\theta}{2}</math> are themselves both rational, and if <math>\theta</math> and <math>\phi</math> define two points in ''S'', then their distance is the rational number <math>|2\sin\frac{\theta}{2}\cos\frac{\phi}{2}-2\sin\frac{\phi}{2}\cos\frac{\theta}{2}|</math>. More generally, a circle with radius <math>\rho</math> contains a dense set of points at rational distances to each other if and only if <math>\rho^2</math> is rational.<ref name="kw">{{citation
| last1 = Klee | first1 = Victor | author1-link = Victor Klee
| last2 = Wagon | first2 = Stan | author2-link = Stan Wagon
| contribution = Problem 10 Does the plane contain a dense rational set?
| isbn = 978-0-88385-315-3
| pages = 132–135
| publisher= Cambridge University Press
| series = Dolciani mathematical expositions
| title = Old and New Unsolved Problems in Plane Geometry and Number Theory
| url = http://books.google.com/books?id=tRdoIhHh3moC&pg=PA132
| volume= 11
| year = 1991}}.</ref>

For any finite set ''S'' of points at rational distances from each other, it is possible to find a [[Similarity (geometry)|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 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.

It remains unknown whether there exists a set of points at rational distances from each other that forms a dense subset of the [[Euclidean plane]].<ref name="kw"/>

==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 <math>\delta</math>, then at most <math>4(\delta+1)^2</math> points at integer distances can be added to the set.

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 <math>\delta</math>, and let <math>d(A,B)</math>, <math>d(A,C)</math>, and <math>d(B,C)</math> be the three distances between these three points. Let ''X'' be any other member of ''S''. From the [[triangle inequality]] it follows that <math>|d(A,X)-d(B,X)|</math> is a non-negative integer and is at most <math>\delta</math>. For each of the <math>\delta+1</math> integer values ''i'' in this range, the locus of points satisfying the equation <math>|d(A,X)-d(B,X)|=i</math> forms a [[hyperbola]] with ''A'' and ''B'' as its foci, and ''X'' must lie on one of these <math>\delta+1</math> hyperbolae. By a symmetric argument, ''X'' must also lie on on one of a family of <math>\delta+1</math> hyperbolae having ''B'' and ''C'' as foci. Each pair of distinct hyperbolae, one defined by ''A'' and ''B'' and the second defined by ''B'' and ''C'', can intersect in at most four points,
and every point of ''S'' (including ''A'', ''B'', and ''C'') lies on one of these intersection points. There are at most <math>4(\delta+1)^2</math> intersection points of pairs of hyperbolae, and therefore at most <math>4(\delta+1)^2</math> points in ''S''.

==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]].

==References==
{{reflist}}

==External links==
*{{mathworld | urlname = Erdos-AnningTheorem | title = Erdos-Anning Theorem}}

{{DEFAULTSORT:Erdos-Anning theorem}}
[[Category:Theorems in discrete mathematics]]
[[Category:Articles containing proofs]]
[[Category:Theorems in discrete geometry]]
[[Category:Paul Erdős|Anning theorem]]

ASCIIMathML - Revision history

en>Adius at 22:07, 11 January 2014