Manifesto | Index | What's new | rss feed

| Bookmark |

| Follow us

| Recommend | Contact |

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. The problem was also discussed by Savchev and Andreescu in the wonderful Mathematical Miniatures.

Given a finite collection of numbers

A = {a₁, ..., a_n},

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

(1)	A₂ = {a_i + a_j: a_i, a_j 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')	A₂ = {a_i + a_j: a_i, a_j A, i < j}.

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

A₂ = {5, 8, 9, 11, 12, 15} and
B₂ = {5, 8, 9, 11, 12, 15}.

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

(2)

A₂ = B₂

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.)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Buy this applet
What if applet does not run?

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) = x^{^a₁} + ... + x^{^a_n} = ∑x^{^a_i} and

g(x) = x^{^b₁} + ... + x^{^b_n} = ∑x^{^b_i},

where i ranges from 1 through n. Squaring gives

[f(x)]²	= (x^{^a₁} + ... + x^{^a_n})²
	= (x^{^a₁})² + ... + (x^{^a_n})²
	+ 2(x^{^{a₁ + a₂}} + x^{^{a₁ + a₃}} + ... + x^{^{a_n-1 + a_n}})

In other words,

(3)	[f(x)]² = ∑(x²)^{^a_i} + ∑x^{^{a_i + a_j}}, i ≠ j.

Or,
(3_a) [f(x)]² = ∑(x²)^{^a_i} + 2∑x^{^{a_i + a_j}}, i < j.

And similarly,
(3_b) [g(x)]² = ∑(x²)^{^b_i} + 2∑x^{^{b_i + b_j}}, i < j.

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

[f(x)]² - [g(x)]² = ∑(x²)^{^a_i} - ∑(x²)^{^b_i}.

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

(4)	[f(x)]² - [g(x)]² = f(x²) - g(x²).

Factoring the left hand side, we have

(4')	(f(x) + g(x))(f(x) - g(x)) = f(x²) - g(x²).

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

(4'')

(f(x) + g(x))·h(x) = h(x²).

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

(5)	h(x) = (1 - x)^kp(x),

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

(6)

h(x²)	= (1 - x²)^kp(x²)
	= (1 - x)^k(1 + x)^kp(x²),

and (4'') becomes

(7)	(f(x) + g(x))·p(x) = (1 + x)^kp(x²).

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

2n·p(1) = (1 + 1)^kp(1),

where p(1) ≠ 0, from which

n = 2^k-1.

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

∑(x^s)^{^a_i}

and another one whose terms are best described as having exponents a_i₁ + ... + a_{i_s}, where not all indices i_j are the same. Instead of (4) we obtain

[f(x)]^s - [g(x)]^s = f(x^s) - g(x^s).

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

h(x^s)	= (1 - x^s)^kp(x^s)
	= (1 - x)^s(1 + x + ... + x^s-1)^kp(x^s),

and (7) is replaced by

(f^s-1(x) + f^s-2g(x) + f^s-3g²(x) + ... + g^s-1(x))·p(x) = (1 + x + ... + x^s-1)^kp(x^s),

where again we substitute x = 1:

sn^s-1·p(1) = s^kp(1),

so that, finally,

n^s-1 = s^k-1.

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

A = {a₁, ..., a_n, b₁+m, ..., b_n+m} and
B = {b₁, ..., b_n, a₁+m, ..., a_n+m},

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.

(A little different construct and modifications are also discussed elsewhere. Powers of 2 have another interesting and unexpected property.)

References

R. Honsberger, In Pólya's Footsteps, MAA, 1999, pp. 243-246.
S. Savchev, T. Andreescu, Mathematical Miniatures, MAA, 2003, pp. 193-196

Generating Functions

40618558