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