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

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

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

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

The point-to-point distances for the first set are

and the distances for the second set are

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

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

which must be the same four numbers, possibly permuted in some way. Equating the sum of every product of two of them gives

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

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

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.

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

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 triples 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

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

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

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

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 the point set {0,1,2,6,8,11} 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⁵).

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

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

A similar factorization results for every pair of isospectral sets. Here are a couple more examples

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

The first 12 non-trivial isospectral pairs of individual points on a line are represented by the pairs of decimal integers

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 question 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

and the digit reversals of these numbers are

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)

Again this raises the question of whether the numerical relation XX′ = YY′ for any particular base is sufficient as well as necessary 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.

Incidentally, the existence of distinct isospectral arrangements of points in one-dimensional space can also be expressed in terms of a combinatorial proposition involving sequences of integers. Given a finite ordered set of non-zero integers A = {a₁, a₂, ... a_k}, let S{A} denote the multi-set of all the sums of consecutive elements of A. Also, define the "reversal" of A as A′ = {a_k, ... a₂, a₁}. (Obviously we have S{A} = S{A′}.) A pair of distinct isospectral arrangements of points corresponds to a pair of distinct ordered sequences A and B such that S{A} = S{B}.

An application of generating functions to higher dimensional configurations is discussed in Isospectral Point Sets in Higher Dimensions.

Return to MathPages Main Menu