[math-fun] distinct distances
Hi math-funsters, I got an interesting problem lately and neither I nor the proposer know the solution. Perhaps it is an open question? Given n points in d dimensions with k different pairwise distances, how can you tell if there are 0, a finite number, or an infinite number of possible arrangements of the points up to similarity? And if the answer is a finite number, how many arrangements are there? Any special cases that you can help me out with would be nice too. I'm particularly interested in knowing the minimum value of k for each n. Examples (all in 2-D): For 3 points, with 1 different distance you have only 1 arrangement, the equilateral triangle. With 2 different distances you get the infinite family of isosceles triangles. For 4 points, you must have at least 2 different distances, and I think there are exactly 6 distinct arrangements but I don't have a proof. For 5 points, the regular pentagon works to give exactly 2 distinct distances, and I'm pretty sure that's unique. For n points, the regular n-gon gives floor(n/2) different distances, and I conjecture that is the fewest possible distinct distances (based on not much evidence!), but in general that arrangement is not unique (e.g. for n = 7 the regular heptagon works but so does the regular hexagon plus the point in the middle, and maybe there are lots more possible arrangements. How many?). (And if my floor(n/2) conjecture is correct, we should add something about this to the relevant entry in OEIS, and if it's not correct, sounds like a great sequence to me!) This problem was suggested to me as the basis of a problem set for http://jrmathfestival.org ... and I think it'll make a great one. The festival (of which I am the director) has funding for people who write problem sets, and also for those of you in the SF Bay area who would like to spend a day at Google or Pixar, you can sit down with some kids (grades 6-12) and work on a problem set with them (and we can also pay you some token amount to thank you for volunteering, but not nearly enough to make it worth the time if you don't already like helping kids work on interesting problems). If you are interested, let me know and I'll send you some sample problem sets. Thanks, --Joshua Zucker
You may already know that this problem belongs to the very large and active field called Discrete (or Combinatorial) Geometry. It has many books and at least one journal. Steve Gray -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Joshua Zucker Sent: Saturday, March 29, 2008 7:57 AM To: math-fun Subject: [math-fun] distinct distances Hi math-funsters, I got an interesting problem lately and neither I nor the proposer know the solution. Perhaps it is an open question? Given n points in d dimensions with k different pairwise distances, how can you tell if there are 0, a finite number, or an infinite number of possible arrangements of the points up to similarity? And if the answer is a finite number, how many arrangements are there? Any special cases that you can help me out with would be nice too. I'm particularly interested in knowing the minimum value of k for each n. Examples (all in 2-D): For 3 points, with 1 different distance you have only 1 arrangement, the equilateral triangle. With 2 different distances you get the infinite family of isosceles triangles. For 4 points, you must have at least 2 different distances, and I think there are exactly 6 distinct arrangements but I don't have a proof. For 5 points, the regular pentagon works to give exactly 2 distinct distances, and I'm pretty sure that's unique. For n points, the regular n-gon gives floor(n/2) different distances, and I conjecture that is the fewest possible distinct distances (based on not much evidence!), but in general that arrangement is not unique (e.g. for n = 7 the regular heptagon works but so does the regular hexagon plus the point in the middle, and maybe there are lots more possible arrangements. How many?). (And if my floor(n/2) conjecture is correct, we should add something about this to the relevant entry in OEIS, and if it's not correct, sounds like a great sequence to me!) This problem was suggested to me as the basis of a problem set for http://jrmathfestival.org ... and I think it'll make a great one. The festival (of which I am the director) has funding for people who write problem sets, and also for those of you in the SF Bay area who would like to spend a day at Google or Pixar, you can sit down with some kids (grades 6-12) and work on a problem set with them (and we can also pay you some token amount to thank you for volunteering, but not nearly enough to make it worth the time if you don't already like helping kids work on interesting problems). If you are interested, let me know and I'll send you some sample problem sets. Thanks, --Joshua Zucker _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Joshua Zucker -
Stephen Gray