23
$\begingroup$

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) $$
     Circle5
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."

$\endgroup$
7
  • 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$ Jul 17, 2013 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$ Jul 17, 2013 at 7:18
  • 4
    $\begingroup$ Or for $n=4$ or $n=6$. $\endgroup$
    – user25199
    Jul 17, 2013 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$ Jul 17, 2013 at 15:37
  • 3
    $\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$ Jul 19, 2013 at 0:18

3 Answers 3

13
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is there a published reference for the "famous unsolved problem" at the end of the link? $\endgroup$
    – user25199
    Jul 17, 2013 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$ Jul 17, 2013 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, 2013 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, 2013 at 13:40
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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