A Property of the Powers of 2

A combinatorial result due to Paul Erdös and John Selfridge has been discussed by R. Honsberger in his In Pólya's Footsteps.

Given a finite collection of numbers

the sums of different members of A taken by two form another collection

(1)	A2 = {ai + aj: ai, aj A, i j}.

(Note that the numbers in A, and even more so in A₂, are not required to be distinct. Thus, the term "collection" here is used in liew of the more common "multiset". Multiset is similar to set in that the order of its terms is not important; it differs from set in that its terms may come with multiplicities greater than 1. These multiplicities are as important for distinction between multisets as the sets of their elements. If two identical terms in two multisets have different multiplicities, the multisets are different.)

In the definition (1), the two sums a_i + a_j, with i j, are considered as the same term in A₂. Thus more accurately (1) could be written as

(1')	A2 = {ai + aj: ai, aj A, i < j}.

For example, if A = {2, 3, 6, 9} and B = {1, 4, 7, 8}, then

This example also shows that it is possible to have A₂ = B₂ for different A and B. We have a curious result:

Theorem

If A₂ = B₂ for different A and B, then A and B are of the same size n and, furthermore, n is a power of 2.

The fact that A and B are bound to have the same size in order for

to hold is rather obvious. It follows from the observation that the number C(k, 2) = k(k-1)/2 of distinct unordered pairs of terms from a collection of k objects is a strictly increasing function of k.

Below I include two copies of the same applet to help you verify the second part of the theorem.

(In the left upper corner of the applet, in blue, you see A terms. Each could be modified by clicking a little of its vertical center line. Beneath it, in black, the applet lists the terms of A₂ in a nondecreasing order. The size of A could be changed in the same manner. The terms of A₂ could be displayed, if so desired, in a separate window by clicking on the "Pop frame" button. I'll explain the purpose of the two remaining controls - "#summonds" and "Economize" shortly.)

Now let's turn to the proof of the second part of the theorem: (2) implies n = 2^r, for a positive integer r. Assume (2) holds and introduce the generating functions

f(x) = xa1 + ... + xan = Sxai and g(x) = xb1 + ... + xbn = Sxbi,

where i ranges from 1 through n. Squaring gives

[f(x)]2 = (xa1 + ... + xan)2   = (xa1)2 + ... + (xan)2   + 2(xa1 + a2 + xa1 + a3 + ... + xan-1 + an)

In other words,

(3)	[f(x)]2 = S(x2)ai + Sxai + aj, i j.

Or,

(3a)	[f(x)]2 = S(x2)ai + 2Sxai + aj, i < j.

And similarly,

(3b)	[g(x)]2 = S(x2)bi + 2Sxbi + bj, i < j.

Since, by our assumption, (2) holds and implies Sx^{a_i + a_j} = Sx^{b_i + b_j}, subtraction of (3_b) from (3_a) gives

Recalling the definition of f(x) and g(x), this is equivalent to

Factoring the left hand side, we have

After setting h(y) = f(y) - g(y) the latter transforms into

Assume A and B are not identical, such that f(x) differs from g(x) and, therefore, h(x) is not identically zero. Then, of course, h(x) can be written in the form

where p(x) is not divisible by (1 - x), i.e., p(1) 0. (5) implies

and (4'') becomes

From the definition, f(1) = g(1) = n, so that (7) yields

where p(1) 0, from which

This is the desired identity, and we are almost done, but not quite yet. To better appreciate the remaining step, let's observe that all the derivation above admits a generalization.

Indeed, from the outset we could have formed the collection A_s considering the sums of s (s > 2) terms. So, let's do that. There is no change in the definition of f(x) and g(x), but instead of squares, we now consider their s^th powers assuming A_s = B_s. (3) then is replaced by a sum of two terms: the sum S(x^s)^a_i and another one whose terms are best described as having exponents a_i1 + ... + a_is, where not all indices i_j are the same. Instead of (4) we obtain

With the same definition of h(x), (6) becomes

and (7) is replaced by

where again we substitute x = 1:

so that, finally,

Which appears to support a generalization: if A_s = B_s, then A = B, provided n is a power of s.

The applet above allows one to change s by clicking on the number labeled "#summonds". The general case is different from the case of two summonds in that the tuples (i₁, ..., i_s), where not all indices are equal, appear in different quantities that depend on the distribution of indices in the tuple. There is no easy way to replace an analogue of (3) with an analogue of (3_a). However, it is clear that the latter has considerably fewer terms than the former. The "Economize" check box is used to display all the relevant terms avoiding those that are obtained by cycling the indices.

As we saw at the beginning of the page, there does exist an example with n = 4 where A₂ = B₂. You may try to find an example of A₃ = B₃, for either n = 3 or n = 9. (Or think of whether this is at all possible.)

Now let's return to the proof of our theorem.

Assume that (1) holds for two different multisets A and B, as above. Then it is quite obvious that (1) will also hold for

for any number m (different from 0). Since (2) holds trivially for A = {1, 4} and B = {2, 3}, we conclude, by induction, that for any n which is a power of 2, there exist distinct collections A and B that satisfy (1).

The curious thing is that while the derivation of the generalization did go through, in the absence of specific A and B that satisfy A_s = B_s, it is not actually clear what had been proved.

(Powers of 2 have another interesting and unexpected property.)

References

1. R. Honsberger, In Pólya's Footsteps, MAA, 1999, pp. 243-246.

Generating Functions

1. A Property of the Powers of 2
2. An USAMTS problem with light switches
3. Examples with series of figurate numbers
4. Euler's derivation of the binary representation
5. Examples with finite sums with binomial coefficients
6. Fast Power Indices and Coin Change
7. Number of elements of various dimensions in a tesseract
8. Straight Tromino on a Chessboard
9. Ways To Count

Copyright © 1996-2009 Alexander Bogomolny