Generating Functions for Point Set Distances 

Does the multiset of pointtopoint 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 multiset of pointtopoint 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 multiset of distances, the elementary symmetric functions of the elements of these two sets must be identical. Equating the sums of the two sets gives 2a+b = 2u+v, which implies that (ba) = (vu). Deleting those elements from their respective sets leaves us with 

_{} 

Clearly the largest element of the first set must be either b or 1a, and the largest element of the second set must be either v or 1u. If we identify b with v then the equation (ba) = (vu) implies a = u, so the configurations are identical. On the other hand, if we identify b with 1u then the equation (ba) = (vu) implies a = 1v, so the configurations are reflections of each other. These two cases cover the identifications of 1a with v and 1a with 1u as well, so it follows that the multiset 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 pointtopoint 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 42a+2c = 42q+2s, from which it follows that 

_{} 

Now, notice that the largest distance in each set is 10, and the 2nd largest distance in the first set must be either c or 1a. Likewise the 2nd largest distance in the second set must be s or 1q. 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 1a = 1q then a = q and by (1) c = s, and so b = r, and the sets are again identical. 
(III) If c = 1q then (1) implies (1q) a = sq, which gives s = 1a and so b = 1r, and the sets are just reflections of each other. 
(IV) If 1a = s then by (1) c = 1q and so b = 1r, 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 multiset of pointtopoint 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 multisets of pointtopoint distances are called "isospectral". Another example of isospectral configurations of six points is shown below. 


Incidentally, these two pointsets are not only isospectral, they also have no duplicated pointtopoint distances. Such pointsets are sometimes called Golomb rulers, although some people reserve that term for sets of N points that have the distances 1, 2, 3, ..., N(N1)/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 pointtopoint 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 Npoint 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 pointtopoint 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 sixpoint set, we have 

_{} 

and the product p(x) p'(x) gives a shifted version of the pointtopoint 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^5). 

Now, since {0,1,2,6,8,11} and {0,1,6,7,9,11} have the same multiset of pointtopoint 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 nontrivial 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 counterexamples 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 nontrivial isospectral pairs of point sets consisting of up to 12 points in each set. I'd be interested to see a counterexample, 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 multiset of pointtopoint distances. So this nicely generalizes the base2 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 counterexamples. 

Incidentally, the existence of distinct isospectral arrangements of points in onedimensional space can also be expressed in terms of a combinatorial proposition involving sequences of integers. Given a finite ordered set of nonzero integers A = {a_{1}, a_{2}, ... a_{k}}, let S{A} denote the multiset of all the sums of consecutive elements of A. Also, define the "reversal" of A as A' = {a_{k}, ... a_{2}, a_{1}}. (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. 
