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.