From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: An Erdos Problem Date: 29 Mar 1999 18:58:51 GMT Newsgroups: sci.math Keywords: Points in the plane with only two distances between them In article , A.B. Cdef wrote: >Let there be given 5 distinct points in the plane. >Suppose they determine only two distances. >Is it true that they are the vertices of >a regular pentagon. >(Paul Erdos) I guess so. This is implicit in "Unsolved problems in Geometry" (Croft, Falconer, & Guy), section F1 (where they state, in passing, that "r(5)=1"). I don't really see that this is obvious, but it's provable. As a first step we need to consider the possible combinatorial arrangements. Among five points there are 10 pairs and hence 10 possible distances. If you want these distances to take only two values, you must ask for the ways to partition the 10 pairs into 2 subsets. Of course, there are 2^10=1024 such partitions, but many are the same up to renumbering (i.e., they are in the same orbit under the obvious action of Sym(5).) I used Maple to look for representatives of the distinct cosets, and found 18, that is, there are 18 distinct partitions of the 10 distances among 5 points. To describe them, I list for each a set of pairs; these pairs are to have one length, and all other pairs are to have the other. Here are the 18 configurations -- get scratch paper ready: {} {{1,2}} {{1,2}, {2,3}} {{1,2}, {3,4}} {{1,2}, {2,3}, {3,1}} {{1,2}, {2,3}, {3,4}} {{1,2}, {1,3}, {1,4}} {{1,2}, {2,3}, {4,5}} {{1,2}, {2,3}, {3,4}, {4,1}} {{1,2}, {2,3}, {3,4}, {4,5}} {{1,2}, {2,3}, {3,1}, {4,5}} {{1,2}, {1,3}, {1,4}, {1,5}} {{1,2}, {2,3}, {3,1}, {1,4}} {{1,2}, {1,3}, {1,4}, {4,5}} {{1,2}, {2,3}, {3,1}, {1,4}, {1,5}} {{1,2}, {2,3}, {3,4}, {4,1}, {1,5}} {{1,2}, {2,3}, {3,1}, {1,4}, {3,5}} {{1,2}, {2,3}, {3,4}, {4,5}, {5,1}} The last is the partition of edges in the regular pentagon. The question is, which of the others are realizable by points in the plane (and, for the last one, are there any other configurations other than the regular pentagon with these sets of distances equal)? For example, it is clear that the first configuration is impossible, since it calls for five equidistant points, which is not even realizable in R^3, let alone R^2. For any of these configurations, we can determine all arrangements of points in R^2 with the appropriate distances as follows. By translation, scaling, and rotation, we may assume point 1 is at the origin and point 2 is at (1,0). Then there are 6 variables (x3,y3), (x4,y4), (x5,y5) representing the positions of the other three points. Each configuration yields 8 quadratic equations in these variables. For example, the last configuration may be written dist(1,2)^2 = ... = dist(5,1)^2, dist(1,3)^2=...=dist(4,1)^2, or (simplifying the two sets of 4 equations somewhat) each of 2*x3 - x3^2 - y3^2 1 - 2*x3 + 2*x3*x4 - x4^2 + 2*y3*y4 - y4^2 x3^2 - 2*x3*x4 + y3^2 - 2*y3*y4 + 2*x4*x5 - x5^2 + 2*y4*y5 - y5^2 x4^2 - 2*x4*x5 + y4^2 - 2*y4*y5 x3^2 + y3^2 - 1 + 2*x4 - x4^2 - y4^2 1 - 2*x4 + x4^2 + y4^2 - x3^2 + 2*x3*x5 - x5^2 - y3^2 + 2*y3*y5 - y5^2 x3^2 - 2*x3*x5 + x5^2 + y3^2 - 2*y3*y5 + y5^2 - x4^2 - y4^2 x4^2 + y4^2 - x5^2 + y2*x5 - 1 - y5^2 must vanish. As a general rule we expect any eight equations in six unknowns to be overconstrained, so it's certainly believable that each of the 18 configurations cannot be realized in the plane (or at least, has very few solutions.) Indeed, we can take any six of the equations in each set and -- with elimination theory, say -- determine all the solutions to those six equations (there should be only finitely many, in general); we then just check to see whether or not the last two equations also hold at each of those solutions. (On the other hand, we can repeat this experiment in R^3 where we may also assume z3=0 and so have 8 equations now in _eight_ variables; thus in general we would think each of the configurations is realizable in a finite number of geometrically distinct ways in space. As the first configuration shows, that number might be zero.) So anyway, this problem is certainly resoluble with a finite calculation. My prefered tool for solving this is Magma but I don't have access to this right now. Perhaps someone else can run the 2-D and 3-D computations for the 18 cases and report the finitely many configurations. (Note that fixing some of the coordinates does not completely eradicate geometrically identical solutions, unless we add, say, y3>0 etc.) Of course, I don't think the algebraic approach is necessarily the best one. For example, the ninth configuration begins with a rhombus, and a pretty geometrical argument might find all the configurations with four or more of the remaining six lengths equal. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: An Erdos Problem Date: 29 Mar 1999 23:57:27 GMT Newsgroups: sci.math In article , A.B. Cdef wrote: >Let there be given 5 distinct points in the plane. >Suppose they determine only two distances. >Is it true that they are the vertices of >a regular pentagon. Dave Rusin wrote: >I guess so. [...] >As a first step we need to consider the possible combinatorial arrangements. [...] >The question is, which [...] are realizable by points in the plane There's a short way to conclude the argument. For each of these combinatorial arrangements, we have d( p_i, p_j )^2 = 0, if i=j = 1, if {i,j} is one of the pairs in one set of edges = d, say, otherwise. With one point at the origin, we can then compute the inner products M_ij = of the other points in pairs, as M_ij = ( || p_i ||^2 + || p_j ||^2 - || p_i - p_j ||^2 )/2, which will be one of a few linear functions of d as appropriate. On the other hand, if there is an embedding of the points into R^k consistent with these inner products, write the coordinates of the 4 points into columns to get a k x 4 matrix A; this will have the property that A^t A = M. In particular, M will have rank at most rank(A) <= k. (Conversely, if M is symmetric and nonnegative semi-definite, there is such a k x 4 matrix A iff M has rank k or less. If you don't mind complex matrices A, the rank is the only constraint.) Thus, except for possible positivity constraints, the realizability condition becomes the vanishing of the last few terms of the characteristic polynomial of M. For most of the 18 configurations listed in the previous post, we may quickly compute that there is a positive value of d which makes det(M) vanish; for this d, M then has rank 3 and so there is an embedding into R^3 consistent with the distance information. The one exception is the first configuration, which asks for five equidistant points. This is possible in R^4 but not in R^3, consistent with the observations about M. On the other hand, an embedding into R^2 is nearly always impossible. This would require that the last _two_ coefficients of the characteristic polynomial of M vanish. We can compute the gcd of these two polynomials in d, and deduce that no such d exists except in a few degenerate cases (in configurations 2, 3, 5, 7, 9, and 12 on my list, we find the gcd of these two coefficients to be a power of d itself, that is, we can find an "embedding" of five points in the plane where the appropriate distances are either 1 or d=0. Of course, this isn't really a set of 5 distinct points in that case.) The one remaining case is of course the last one: the gcd of the last two coefficients in the characteristic polynomial of M is d^2-3d+1, that is, for these two values of d the matrix M has rank 2 and so may be written as A^t A for a 2 x 4 matrix A. (it is easily checked that A is real, that is, M is nonnegative semidefinite). (For the embeddings into R^2 I did in fact easily compute the varieties mentioned in the previous post, and came up with the same conclusion: there are some degenerate cases in which the varieties are nonempty, but only when some of the points coincide.) Naturally this procedure can be extended somewhat: you can consider the possible embeddings of N points into R^k with only r interpoint distances, by asking that a certain (N-1)x(N-1) symmetric matrix whose entries are linear expressions in r-1 variables have rank at most k (together with some inequalities). This is likely to be true for some combinations of the r distances iff r + k is at least equal to N, in general. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: An Erdos Problem (sets of points with two distances) Date: 6 Apr 1999 21:41:35 GMT Newsgroups: sci.math In article , A.B. Cdef wrote: >Let there be given 5 distinct points in the plane. >Suppose they determine only two distances. >Is it true that they are the vertices of >a regular pentagon. I followed up with two messages, with this theme: >I guess so. [...] >As a first step we need to consider the possible combinatorial arrangements. [...] >The question is, which [...] are realizable by points in the plane ...and I concluded the points had to be in a pentagon. Now writes: >Sorry to reopen this thread, but i tried some of the above calculations, and >something is very wrong: i have alreay found five distinct arrangements of 6 >(yes, six) points in R^3, and i suspect the list to be much longer (and i >would not even be really surprised to find a seven point configuration) So: >some questions: > >1) What was exactly the initial Erdös conjecture? 2) Does anybody knows the >complete list in R^3? 3) Why six points, given that the equations indeed give >only "rigid" 5 points solutions (in R^3, of course) 4) Is there any other way >to find all solutions (using something like Maple, of course) than solving >those equations (especially in higher dimensions)? > >And, of course, you can still have fun in finding all those configurations (by >the way, a classical Ramsey theorem proves they all contain an equilateral >triangle!) The original discussion concerned only points in the plane, but with no real change we can look for arrangements in space. Let's see, among 6 points, there are 15 pairs, and then 32768 sets of pairs, meaning 16384 partitions of the pairs into two sets. I asked Maple to discard partitions which are conjugate under the action of the symmetric group Sym(6) ; it found 78 remaining partitions. Here's a portion of that list: [] [{1, 2}] [{2, 3}, {1, 3}] [{3, 4}, {1, 2}] [{1, 3}, {1, 2}, {1, 4}] [{5, 6}, {3, 4}, {1, 2}] (*) ... [{2, 3}, {1, 4}, {2, 4}, {1, 5}, {3, 5}] (*) ... [{1, 3}, {3, 6}, {4, 6}, {2, 4}, {1, 5}, {2, 5}] (*) ... [{5, 6}, {2, 6}, {3, 6}, {2, 4}, {1, 5}, {2, 5}] (*) ... [{2, 3}, {1, 3}, {1, 2}, {2, 4}, {3, 4}, {1, 5}, {2, 5}] As in the previous post, for each of these partitions we may ask whether it's possible to have six points p_i in R^k with dist(p_i,p_j)^2 equal to: 0, if i=j; 1, if {i,j} is in the partition d, if {i,j} is not in the partition. Use these values to compute a 6x6 matrix D, then compute a 5x5 matrix M with M_ij = (D_i6 + D_j6 - D_ij)/2. Then the embeddings of the configuration into R^k having point p_6 at the origin are in one-to-one correspondence with the 5xk matrices A having A A^t = M. In particular, the minimal embedding dimension of the configuration is the rank of M. The first listed configuration asks for 6 points in R^k with all interpoint distances equal to d. This is impossible unless k>= 5; indeed, M is nonsingular (for all d). For all 77 other configurations there is at least one value of d which makes M singular, as is found by setting the determinant (a quintic polynomial in d) equal to zero. Thus there is an embedding of each of these into R^4. (A quick check verifies that there is a _positive_ d with det(M)=0, which is necessary for our application.) In order to have an embedding into R^3, we need a value of d which makes the last _two_ coefficients of the characteristic polynomial of M vanish. There are quite a few configurations for which the gcd of these polynomials is a power of d, but setting d=0 would give a degenerate map of the set of six points into R^3. We reject those. As it turns out, there remain only four configurations with a nonconstant gcd; these are the starred partitions above. In the first and third cases the gcd is d-1/2, that is, the only possibility is to have the indicated edges have length 1 and all other edges have length 1/sqrt(2). The first of these is then a set of three mutually perpendicular crossed line segments. The second is a pair parallel equilateral triangles. In the other two cases the gcd is d^2-3d+1. The roots of this polynomial are the lengths of the sides [resp. diagonals] of a regular pentagon in which the diagonals [resp. sides] have length 1. Indeed, the top configuration is just a pentagonal pyramid (of two different possible heights corresponding to two possible values of d). The other configuration appears to be a pair of parallel equilateral trangles of different sizes. None of the configurations can be embedded into the plane, of course; that's apparent from the descriptions above, and also follows from the calculuation that the gcd of the last _three_ coefficients of the characteristic polynomial of M is always constant. I must be a few cups of coffee short today, because I don't quite see how to reconcile this count, and in particular the description of the last configuration, with the answer given in "Solved and Unsolved Problems in Geometry", section F3: "The answer is ... six [points] in R^3 ([forming] the vertices of a regular octahedron, or of a regular triangular prism, or of a regular pentagon with a suitable point on its axis)." The six points in my last configuration (for d=(3+sqrt(5))/2) are roughly at [ -.467086179, .467086179, +.809017] [ -.467086179, .467086179, -.809017] [ -.467086179, -.934172359, 0 ] [ +.467086179, .288675135, +.5 ] [ +.467086179, .288675135, -.5 ] [ +.467086179, -.577350269, 0 ] The quoted comment implies there is no set of 7 points in R^3 with only two interpoint distances. I didn't really check this. In a seven-point configuration we could remove two points and have a configuration with the property that there is more than one possible position for a sixth point. Checking the five-point sub-configurations shows that each is contained in a unique six-point configuration in general, making it easy to check that in fact the sixth point is uniquely determined. However, both the second and fourth configurations contain a partition equivalent to [{1,2},{2,3},{3,4}], so with points 1-5 in place, the sixth point could be in two positions, with distance to p_i equal to 1 precisely for i={1,4} (configuration #2) or i={2,3,5} (configuration #4). This really does occur: the first five listed points, together with the point [-1.044436447, .577350269, 0 ] form a pentagonal pyramid. But the sixth and seventh points are too far apart to form a seven-point configuration. dave