Generating Functions for Point Set Distances
Does the multi-set of point-to-point distances between N points on a
line uniquely determine the configuration of points (up to reflection)?
For N=2 or 3 the answer is obviously yes. What about N=4? In other
words, can there exist two distinct configurations of points on the
unit interval such as
0 a b 1 0 u v 1
|------|---|--------| |---|--------|------|
with the same multi-set of point-to-point distances? Neglecting the
distance 1 common to both, these two configurations have the sets of
distances
{ a , b , b-a , 1-a , 1-b }
{ u , v , v-u , 1-u, 1-v }
If the two configurations are to have the same multi-set of distances,
the elementary symmetric functions of the elements of these two sets
must be identical. Equating the sums of the two sets gives 2-a+b =
2-u+v, which implies that (b-a) = (v-u). Deleting those elements
from their respective sets leaves us with
{ a , b , 1-a , 1-b }
{ u , v , 1-u, 1-v }
Clearly the largest element of the first set must be either b or 1-a,
and the largest element of the second set must be either v or 1-u.
If we identify b with v then the equation (b-a)=(v-u) implies a=u, so
the configurations are identical. On the other hand, if we identify
b with 1-u then the equation (b-a)=(v-u) implies a=1-v, so the
configurations are reflections of each other. These two cases cover
the identifications of 1-a with v and 1-a with 1-u as well, so it
follows that the multi-set of distances between four points on a line
uniquely determines the configuration (up to reflection).
Now what 5 points? Suppose there are two distinct (ordered)
configurations of 5 points on the unit interval
[0 a b c 1] [0 q r s 1]
The point-to-point distances for the first set are
a, b, c, 1, b-a, c-a, 1-a, c-b, 1-b, 1-c
and the distances for the second set are
q, r, s, 1, r-q, s-q, 1-q, s-r, 1-r, 1-s
If the two sets are isospectral then these are the same ten numbers
as for the first set, possibly in some different order, so the sums
of these two sets of distances should be equal. This leads to
4-2a+2c = 4-2q+2s, from which it follows that
c-a = s-q (1)
Now, notice that the largest distance in each set is 1-0, and the 2nd
largest distance in the first set must be either c or 1-a. Likewise
the 2nd largest distance in the second set must be s or 1-q. So there
are four possibilities
(I) If c=s then by (1) a=q and so b=r, and the sets are identical.
(II) If 1-a=1-q then a=q and by (1) c=s, and so b=r, and the sets
are again identical.
(III) If c=1-q then (1) implies (1-q)-a=s-q, which gives s=1-a and
so b=1-r, and the sets are just reflections of each other.
(IV) If 1-a=s then by (1) c=1-q and so b=1-r, and the sets are again
just reflections of each other.
Notice that in each of the four cases we've established the
correspondence between four of the five points, so the 5th point
in the middle must also fall into the same pattern. Since all
four cases are symmetrical, consider just Case I, where we have
established a=q and c=s. All the other distances match up and
we're just left with the four quantities involving b and r
b, b-a, c-b, 1-b and r, r-a, c-r, 1-r
which must be the same four numbers, possibly permuted in some way.
Equating the sum of every product of two of them gives
b(1+c-3b) = r(1+c-3r)
which implies either b=r or b=(c+1)/3 - r. On the other hand, equating
the sum of every product of three of them gives
(1+c-a)b^2 - 2cb = (1+c-a)r^2 - 2cr
and if we substitute b = (c+1)/3 - r this equation says r=(c+1)/6,
so again b=r. Likewise the other three cases lead to either
equivalent or reflected sets, so the two sets are equivalent up
to reflections.
So we've established that the multi-set of point-to-point distances
for N=2,3,4, or 5 points on a line uniquely determines the
configuration up to reflection. On the other hand, it does NOT
determine the configuration for N=6 points, as shown by the two
sets of linear lattice points
0 1 2 6 8 11
|-|-|- - - -|- -|- - -|
0 1 6 7 9 11
|-|- - - - -|-|- -|- -|
Two distinct configurations of points on a line with identical multi-
sets of point-to-point distances are called "isospectral". Another
example of isospectral configurations of six points is shown below.
0 1 4 10 12 17
|-|- - -|- - - - - -|- -|- - - - -|
0 1 8 11 13 17
|-|- - - - - - -|- - -|- -|- - - -|
Incidentally, these two point-sets are not only isospectral, they also
have no duplicated point-to-point distances. Such point-sets are
sometimes called Golomb rulers, although some people reserve that
term for sets of N points that have the distances 1,2,3,...,N(N-1)/2.
Other people refer to these latter sets as "perfect Golomb rulers".
A conjecture of Picard is that if X and Y are two Golomb rulers (not
necessarily perfect) of size N (not equal to 6) with the same set of
point-to-point distances, then X=Y.
There are 36 "isospectral pairs" of linear lattice point sets with
max distance less than or equal to 14. Of these 36 pairs there are
3, 5, 4, 23, and 1 for N = 6, 7, 8, 9, and 10 points respectively.
The smallest example for each of these values of N is listed below
N = 6: { 0 1 2 6 8 11 }
{ 0 1 6 7 9 11 }
N = 7: { 0 1 3 6 7 8 12 }
{ 0 1 5 6 7 9 12 }
N = 8: { 0 1 3 4 7 8 9 13 }
{ 0 1 5 6 7 9 10 13 }
N = 9: { 0 1 2 3 4 6 7 8 11 }
{ 0 1 4 5 6 7 8 9 11 }
N =10: { 0 1 2 3 5 7 8 9 11 14 }
{ 0 1 3 6 7 8 9 10 12 14 }
This raises several interesting questions. For example, if we let
f(N) denote the size of the smallest isospectral pair of linear
lattice N-point sets, what can we say about the values of f(N)?
They clearly aren't monotonic, as already shown by f(9) < f(8).
Asymptotically, does f(N) increase linearly with N? Also, what
is the smallest isospectral TRIPLE of linear lattice points?
Another interesting aspect of these point sets concerns their
representations as polynomials. For example, the point set
{0,1,2,6,8,11} corresponds to the polynomial
p(x) = 1 + x + x^2 + x^6 + x^8 + x^11
It's clear that the generating function for the point-to-point
distances is given by the product p(x)p(1/x), because the coefficient
of x^k in this product is just the number of times the difference
between two exponents of x equals k. Of course, this counts each
distance twice, positive and negative k, and also counts each of
the "zero" distances between each point and itself.
Notice that this applies just as well to point sets with more than
one point at each location on the line. The coefficients of p(x)
can be any value. In fact, they can even be fractional, irrational,
and/or complex. This allows us to represent the probability density
distribution f(z) on the line by the polynomial
p(x) = f(0)x^0 + f(1)x^1 + f(2)x^2 + ... + f(k)x^k + ...
and then the density of the difference between two samples from this
distribution can be found from the product p(x)p(1/x).
Of course we can "normalize" the polynomial p(1/x) by multiplying
it by x^d where d is the degree of p. Let's let p'(x) denote this
normalized polynomial x^d p(1/x). Thus, given the polynomial p(x)
corresponding to the six-point set, we have
p'(x) = 1 + x^3 + x^5 + x^9 + x^10 + x^11
and the product p(x) p'(x) gives a shifted version of the point-to-
point distances. Notice that if we set x=2 these polynomials can
be regarded as binary numbers. For example, the set {0,1,2,6,8,11}
corresponds to the number
2^0 + 2^1 + 2^2 + 2^6 + 2^8 + 2^11
or, in ordinary binary notation, 100101000111, which is equal to
2375 in decimal and corresponds to p(x). Reversing the digits gives
the binary number 111000101001, which equals 3625 and corresponds to
p'(x). Now recall that xxx is isospectral with the distinct point
set {0,1,6,7,9,11}. Expressing this as a polynomial q(x) and its
normalized reflection by q'(x), and converting to binary numbers,
these two polynomials correspond to the decimal integers 2755 and
3125 (which happens to equal 5^5).
Now, since {0,1,2,6,8,11} and {0,1,6,7,9,11} have the same multi-set
of point-to-point distances, we know that
p(x) p'(x) = q(x) q'(x)
which implies in particular that p(2) p'(2) equals q(2) q'(2).
In other words, we have (2375)(3625) = (2755)(3125). This occurs
because these individual numbers factor as
p = (5^3)(19) q = (5*29)(19)
p'= (5^2)(5*29) q'= (5^2)(5^3)
A similar factorization results for every pair of isospectral sets.
Here are a couple more examples
p = (191)(5^2) q = (191)(29)
p'= (11*23)(29) q'= (11*23)(5^2)
p = (37)(131) q = (41)(131)
p'= (41)(193) q'= (37)(193)
In general, if X and Y are two integers corresponding to isospectral
point sets, then there are integers a,b,c,d > 1 such that
X = ab Y = ac
X'= cd Y'= bd
The first 12 non-trivial isospectral pairs of individual points on a
line are represented by the pairs of decimal integers
X Y
---- ----
2375 2755
2527 3059
4555 4835
4847 5371
4775 5539
5819 5995
4959 6099
6575 6775
9035 9635
9179 9715
9115 9955
9135 11235
Anyway, we know that two point sets p and q are isospectral if and
only if p(x)p'(x) = q(x)q'(x), and it follows that if p and q are
isospectral we must have p(2)p'(2)=q(2)q'(2). However, is the
converse true?
Somewhat surprisingly, it appears that the converse IS true, at least
over the range of numbers that I've checked. This is unexpected because
in general we lose information when reducing the formal polynomial p(x)
to a specific value such as p(2). On the other hand, the evaluations
increase so rapidly that it's unlikely two unrelated polynomials would
give the same value at x=2. So we would expect counter-examples to
be rare, but this still leaves open the quesion of whether they exist
at all. I've checked all point sets (with integer coordinates) with
max distance less than 16, and the condition xx'=yy' is both necessary
and sufficient for this range, which includes 73 non-trivial isospectral
pairs of point sets consisting of up to 12 points in each set. I'd be
interested to see a counter-example, i.e., a pair of integers x,y
such that xx'=yy' but for which the corresponding point sets are NOT
isospectral.
The above generalizes nicely to other bases, i.e., a relation between
distance sets for points on a line and ordinary digit reversal and
multiplication. Specifically, if XX' = YY' where U' denotes the
number produced by reversing the digits of U in the base b, then the
point sets corresponding to X and Y (and X' and Y') in the base b
are isospectral. For example, consider the case x=5589 and y=4761.
The base 4 representations of these numbers are
X=1113111 Y=1212201
and the digit reversals of these numbers are
X'=1113111 Y'=1022121
which have the decimal values X'=5589 (because X happens to be
palindromic, but that's not typical) and Y'=6561. Notice that
XX'=YY'=31236921, so we expect that the point sets corresponding
to X and Y in base 4 are isospectral. The point set corresponding to
a given number u in the base b is produced by placing d_i points at
a distance i from the origin, where d_i is the ith digit of u. Thus
the particular number x above corresponds to a set with one point at
coordinate 0, one point at coordinate 1, one point at coordinate 2,
THREE points at coordinate 3, one point at coordinate 4, one point at
coordinate 5, and one point at coordinate 6. In other words, the ith
digit signifies how many points to place at coordinate i on the line.
Now determine the set of distances between each point and each other
point in this set. If we do this for the point sets corresponding
to X and Y above we find that they have the same multi-set of point-
to-point distances. So this nicely generalizes the base-2 case (where
we just have at most one point at each coordinate). The smallest
isospectral pairs in the first few bases are shown below (as decimal
numbers)
2 {2375,2755}
3 {935,1199}
4 {414,486}
5 {814,1342}
Again this raises the question of whether the numerical relation
XX'=YY' for any particular base is sufficient as well as necesary
for X and Y to be isospectral. I know of no reason that it should
be sufficient, but I also haven't found any counter-examples.
Return to MathPages Main Menu
Сайт управляется системой
uCoz