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.

  • 3
    $\begingroup$ 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. $\endgroup$ – The Masked Avenger Jul 17 '13 at 0:46
  • 1
    $\begingroup$ The vertices of a regular $n$-gon can't be an integer distance set for $n=5$ or for $n\ge6$. $\endgroup$ – Gerry Myerson Jul 17 '13 at 7:18
  • 3
    $\begingroup$ Or for $n=4$ or $n=6$. $\endgroup$ – user25199 Jul 17 '13 at 7:44
  • 2
    $\begingroup$ 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. $\endgroup$ – The Masked Avenger Jul 17 '13 at 15:37
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Is there a published reference for the "famous unsolved problem" at the end of the link? $\endgroup$ – user25199 Jul 17 '13 at 7:51
  • $\begingroup$ Well, that's a surprise, that there are no infinite noncollinear integer-distance sets in the plane! Could there be in higher dimensions? $\endgroup$ – Joseph O'Rourke Jul 17 '13 at 12:31
  • 4
    $\begingroup$ @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 $\endgroup$ – Daniel m3 Jul 17 '13 at 12:56
  • 5
    $\begingroup$ @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/… $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.