# Integer-distance sets

Let $S$ be a set of points in $\mathbb{R}^d$; I am especially interested in $d=2$. Say that $S$ is an integer-distance set if every pair of points in $S$ is separated by an integer Euclidean distance.

What are examples of maximal integer distance sets? (Maximal: no point can be added while retaining the integer-distance property between all pairs.)

Of course the lattice points along any one line parallel to a coordinate axis in $\mathbb{R}^d$ constitute a countably infinite integer-distance set. What is an example of an infinite integer-distance set of noncollinear points?

I know that Euler established that every circle contains a dense rational-distance set. Scaling any one circle by a large common denominator provides a rich, but finite integer-distance set. For example, these five points on a circle are all separated by integer distances: $$(1221025, 0), (781456, 586092), (439569, 586092), (270400, 507000), (180625, 433500)$$

I'm sure this is all known... Thanks for enlightening me!

(This is tangentially related to my earlier question, "Rational points on a sphere in $\mathbb{R}^d$.")

Update1. It turns out that determining the integer-distance sets is fundamentally open. What is known is nicely summarized by Robert Israel and "Daniel m3." In particular, via the Kreisel & Kurz paper, it is unknown (or was unknown in 2008) whether or not there exists an 8-point integer-distance set in $\mathbb{R}^2$, with no three of the points collinear and no four cocircular.

Update2. Also open is a related problem identified by Nathan Dean: How many non-cocircular integer-distance points can be found on a parabola, a scaling of $y = x^2$? Nathan proved there are infinitely many sets of three such points; Garikai Cambell proved there are infinitely many sets of four such points. But the existence of five such points seems open. I just learned the parabola problem from this MSE question.

Update3 (21 Jul 2013). I ran across this just-published paper, which explores the in-some-sense obverse of the question I asked: What are the largest point sets in $\mathbb{R}^d$ that avoid points an integral distance apart.

Kurz, Sascha, and Valery Mishkin. "Open Sets Avoiding Integral Distances." Discrete & Computational Geometry (2013): 1-25. (Springer link)

Update4 (29 Nov 2014). There is a nice article at Dick Lipton's blog on Ulam's 70-year-old un-resolved conjecture:

If $S$ is an rational-distance set, then it is not dense in the plane.

And that article cites the Kurz-Mishkin paper above.

-
I think an open problem is whether the vertices of a square are a maximal such set. Here is a throwaway conjecture: for all n excepting those less than 4 and n=6, the vertices of a regular n-gon are a maximal example. – The Masked Avenger Jul 17 '13 at 0:46
The vertices of a regular $n$-gon can't be an integer distance set for $n=5$ or for $n\ge6$. – Gerry Myerson Jul 17 '13 at 7:18
Or for $n=4$ or $n=6$. – Carl Jul 17 '13 at 7:44
Ah yes. . Slightly different unsolved problem from Joseph's, are there any points at rational distances from tthe 4 vertices of a unit square? Apologies for the conflation. – The Masked Avenger Jul 17 '13 at 15:37
I have posted a (partial) answer to the m.se question; Jozsef Solymosi and Frank de Zeeuw proved that no irreducible algebraic curve other than a line or a circle contains an infinite rational set. – Gerry Myerson Jul 19 '13 at 0:18

See e.g. http://www.ics.uci.edu/~eppstein/junkyard/integer-distances.html for a proof (originally due to Erdos) that there is no infinite non-collinear integer-distance set in the plane.

-
Is there a published reference for the "famous unsolved problem" at the end of the link? – Carl Jul 17 '13 at 7:51
Well, that's a surprise, that there are no infinite noncollinear integer-distance sets in the plane! Could there be in higher dimensions? – Joseph O'Rourke Jul 17 '13 at 12:31
@Carl: It is not an unsolved problem anymore. Such a set has been constructed by T. Kreisel and S. Kurz in 2008: arxiv.org/abs/0804.1303v1 – Daniel m3 Jul 17 '13 at 12:56
@Joseph O'Rourke: The answer is the same in $\mathbb{R}^d$ with $d \ge 3$. See e.g. the original paper by N. H. Anning and P. Erdős: ams.org/journals/bull/1945-51-08/S0002-9904-1945-08407-9/… – Daniel m3 Jul 17 '13 at 13:40

RE: Daniel's and Carl's comments above, the "famous unsolved problem" is problem D20 from Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 187, 1994. The famous unsolved problem asks about six points, the "end of the link" mentions seven points, and currently eight points is still an open question.

I think "rational distances from the 4 vertices of a unit square" is problem D19.

-