Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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. 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)

share|improve this question
2  
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
1  
Or for $n=4$ or $n=6$. –  Carl Jul 17 '13 at 7:44
1  
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
1  
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
show 1 more comment

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
    
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
3  
@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
4  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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