Integer-distance sets

Question

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.

Update5 (11 Mar 2024). Greenfeld, Rachel, Marina Iliopoulou, and Sarah Peluse. "On integer distance sets." arXiv:2401.10821 abstract (2024).

"Our main result is that any integer distance set in the Euclidean plane has all but a very small number of points lying on a single line or circle. From this, we deduce a near-optimal lower bound on the diameter of any non-collinear integer distance set..."

"It turns out that all so-far-known integer distance sets ... are of a similar special form: they have all but up to four of their points lying on a single line or circle. In this paper, we develop a new approach to the study of integer distance sets that enables us to prove a structure theorem partially explaining this phenomenon."

Answer 1

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.

Answer 2

There has been recent progress concerning finitary integer distance sets in the plane. Greenfeld, Iliopoulou, and Peluse prove that if $P\subset [-N,N]^2$ is an integer distance set not contained inside a single line, then $$ |P| \le O(N^{C/\log\log(N)})$$ for some absolute constant $C$. This is tight (up to the constant $C$). Furthermore, their result reduces the problem of determining this constant $C$ to two cases:

• $P$ lies entirely inside one circle;
• all but one point of $P$ lies inside some line.

See https://arxiv.org/abs/2401.10821 for further details.

Answer 3

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.