From:           tim@maths.tcd.ie (Timothy Murphy)
Newsgroups:     sci.math
Subject:        Re: 2 related geometry problems, probably simple
Date:           27 Jul 1994 18:11:17 +0100
Organization:   Dept. of Maths, Trinity College, Dublin, Ireland.


bs@gauss.mitre.org (Robert D. Silverman) writes:

>In article <TFB.94Jul27154622@boyd.cogsci.ed.ac.uk> tfb@cogsci.ed.ac.uk (Tim Bradshaw) writes:
>:> :Problem 1: how many points can you place in n-dimensional real
>:> :euclidian space s.t there are only 2 distinct interpoint distances,
>:> :and neither of them is zero?
>:> :
>:> :(my guess is 2n+1 from trying it out in 1 & 2 dimensions, but I have
>:> :no idea if that's right or how one would show this anyway).

>3 and 5 are clearly maximum for 1 and 2 dimensions. But I can't find
>a construction for 7 in 3-d. I can only find 6. It is clear that adding
>a dimension gives at least one more point, but it is not clear that it
>gives 2 more.

This may be nonsense, but ...
Take n+1 points P_i distance 1 apart in n dimensions,
and n+1 points Q_j distance 1 apart in "another" n dimensions.
Consider the (n+1)^2 points (P_i,Q_j) in 2n dimensions.
Aren't these either distance 1 or \sqrt{2} apart?

--
Timothy Murphy
e-mail: tim@maths.tcd.ie
tel: +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland


To:             tim@maths.tcd.ie, rdsilverman@qed.com, tfb@cogsci.ed.ac.uk
Subject:        Sets of points forming only two distances
Date:           Wed, 31 Jul 1996 15:46:27 -0700
From:           David Eppstein <eppstein@ICS.UCI.EDU>


About two years ago all three of you posted messages to sci.math about
the following:

: Problem 1: how many points can you place in n-dimensional real
: euclidian space s.t there are only 2 distinct interpoint distances,
: and neither of them is zero?

The best answer I saw at the time was to take the cartesian product of
floor(n/2)- and ceil(n/2)-dimensional regular simplices, giving (n/2 +
1)^2 points for n even and (n^2-1)/4 points for n odd.  However one can
do about a factor of two better by taking the edge midpoints of a single
simplex, giving (n+1 choose 2) points (this can also be viewed as a
certain slice through a hypercube).  E.g. in 4d the product construction
gives 9 points while the edge midpoint construction gives 10.

In 3d both constructions give the same number of points (6),
and there are two different 6-point pentagonal pyramids that also work.

In 5d you can get 16 points by taking every other point on a hypercube,
slightly beating the 15 points produced by the edge midpoint construction.

Did any of you make any more progress on the problem?  How about upper
bounds?  Something like 4^n follows from Ramsey theory, and n + 2^(n+1)
is not hard to prove (every point is determined to within two positions
by its vector of distances from some n-tuple), but still seems very
weak.  Is O(n^2) the right answer?
--
David Eppstein		UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu	http://www.ics.uci.edu/~eppstein/


To:             tim@maths.tcd.ie, rdsilverman@qed.com, tfb@cogsci.ed.ac.uk
Subject:        follow-up on 2-distance set problem
Date:           Thu, 01 Aug 1996 13:37:48 -0700
From:           David Eppstein <eppstein@ICS.UCI.EDU>


Re the message I sent you yesterday about the 2-distance set problem --
I found it today while looking up something else in Croft, Falconer, and
Guy, Unsolved Problems in Geometry, Springer, 1991 (it's problem F3,
p. 152).  They mention the d(d+1)/2-point (edge-midpoint-of-simplex
solution as well as some slightly better solutions for d=6 and d=22.
(They don't mention my 16-point solution for d=5.)  They also cite an
upper bound of (d+1)(d+2)/2.  Apparently the exact optimum solution is
not known for d>3, but these upper and lower bounds are within a factor
of 1+o(1) of each other.