The Partition Sum of Powers Theorem

The set of numbers {S = \{ 0, 1, 2, \dots, 2^{n+1}-1 \}} can be partitioned into two subsets of the same size, such that the two sets have equal sums, sums of squares, sums of cubes, …, up to sums of {n}th powers.

For example, for {n=2}:

\displaystyle S = \{ 0, 1, 2, 3, 4, 5, 6, 7 \}

can be partitioned as

\displaystyle A = \{ 0, 3, 5, 6 \}, B = \{ 1, 2, 4, 7 \}

so that

\displaystyle |A| = |B| = 4

\displaystyle 0 + 3 + 5 + 6 = 1 + 2 + 4 + 7 = 14

and, lastly,

\displaystyle 0^2 + 3^2 + 5^2 + 6^2 = 1^2 + 2^2 + 4^2 + 7^2 = 70

Amazingly, this can be done for any non-negative integer {n}.

Having equal sums is the same as having equal sums of first powers.

If, just for the course of this article, we accept a convention that {0^0 = 1}, then the condition of having the same size may be rephrased as having equal sums of zeroth powers.

Example 1 ({n=0})

\displaystyle S = \{ 0, 1 \}

can be partitioned as

\displaystyle A = \{ 0 \}, B = \{ 1 \}

so that

\displaystyle A \cap B = \emptyset

\displaystyle A \cup B = S

\displaystyle \Sigma A^0 = |A| = 1 = |B| = \Sigma B^0

Example 2 ({n=1})

\displaystyle S = \{ 0, 1, 2, 3 \}

can be partitioned as

\displaystyle A = \{ 0, 3 \}, B = \{ 1, 2 \}

so that

\displaystyle A \cap B = \emptyset, A \cup B = S

\displaystyle \Sigma A^0 = 1 + 1 = 2 = 1 + 1 = \Sigma B^0

\displaystyle \Sigma A^1 = \Sigma A = 0 + 3 = 3 = 1 + 2 = \Sigma B = \Sigma B^1

Example 3 ({n=2})

\displaystyle S = \{ 0, 1, 2, 3, 4, 5, 6, 7 \}

can be partitioned as

\displaystyle A = \{ 0, 3, 5, 6 \}, B = \{ 1, 2, 4, 7 \}

so that

\displaystyle \Sigma A^0 = 4 = \Sigma B^0

\displaystyle \Sigma A^1 = 0 + 3 + 5 + 6 = 14 = 1 + 2 + 4 + 7 = \Sigma B^1

\displaystyle \Sigma A^2 = 0^2 + 3^2 + 5^2 + 6^2 = 70 = 1^2 + 2^2 + 4^2 + 7^2 = \Sigma B^2

Example 4 ({n=3})

\displaystyle S = \{ 0, 1, 2,\dots, 15 \}

can be partitioned as

\displaystyle A = \{ 0, 3, 5, 6, 9, 10, 12, 15 \}

\displaystyle B = \{ 1, 2, 4, 7, 8, 11, 13, 14 \}

so that

\displaystyle \Sigma A^0 = 8 = \Sigma B^0

\displaystyle \Sigma A^1 = 0^1 + 3^1 + 5^1 + 6^1 + 9^1 + 10^1 + 12^1 + 15^1 = 60

\displaystyle = 1^1 + 2^1 + 4^1 + 7^1 + 8^1 + 11^1 + 13^1 + 14^1 = \Sigma B^1

\displaystyle \Sigma A^2 = 0^2 + 3^2 + 5^2 + 6^2 + 9^2 + 10^2 + 12^2 + 15^2 = 620

\displaystyle = 1^2 + 2^2 + 4^2 + 7^2 + 8^2 + 11^2 + 13^2 + 14^2 = \Sigma B^2

\displaystyle \Sigma A^3 = 0^3 + 3^3 + 5^3 + 6^3 + 9^3 + 10^3 + 12^3 + 15^3 = 7200

\displaystyle = 1^3 + 2^3 + 4^3 + 7^3 + 8^3 + 11^3 + 13^3 + 14^3 = \Sigma B^3

Example 5 ({n=4})

\displaystyle S = \{ 0, 1, 2,\dots, 31 \}

can be partitioned as

\displaystyle A = \{ 0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30 \}

\displaystyle B = \{ 1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31 \}

so that

\displaystyle \Sigma A^0 = 16 = \Sigma B^0

\displaystyle \Sigma A^1 = 0^1 + 3^1 + 5^1 + 6^1 + 9^1 + 10^1 + 12^1 + 15^1 + 17^1 + 18^1 + 20^1 + 23^1 + 24^1 + 27^1 + 29^1 + 30^1 = 248

\displaystyle = 1^1 + 2^1 + 4^1 + 7^1 + 8^1 + 11^1 + 13^1 + 14^1 + 16^1 + 19^1 + 21^1 + 22^1 + 25^1 + 26^1 + 28^1 + 31^1 = \Sigma B^1

\displaystyle \Sigma A^2 = 0^2 + 3^2 + 5^2 + 6^2 + 9^2 + 10^2 + 12^2 + 15^2 + 17^2 + 18^2 + 20^2 + 23^2 + 24^2 + 27^2 + 29^2 + 30^2 = 5208

\displaystyle = 1^2 + 2^2 + 4^2 + 7^2 + 8^2 + 11^2 + 13^2 + 14^2 + 16^2 + 19^2 + 21^2 + 22^2 + 25^2 + 26^2 + 28^2 + 31^2 = \Sigma B^2

\displaystyle \Sigma A^3 = 0^3 + 3^3 + 5^3 + 6^3 + 9^3 + 10^3 + 12^3 + 15^3 + 17^3 + 18^3 + 20^3 + 23^3 + 24^3 + 27^3 + 29^3 + 30^3 = 123008

\displaystyle = 1^3 + 2^3 + 4^3 + 7^3 + 8^3 + 11^3 + 13^3 + 14^3 + 16^3 + 19^3 + 21^3 + 22^3 + 25^3 + 26^3 + 28^3 + 31^3 = \Sigma B^3

\displaystyle \Sigma A^4 = 0^4 + 3^4 + 5^4 + 6^4 + 9^4 + 10^4 + 12^4 + 15^4 + 17^4 + 18^4 + 20^4 + 23^4 + 24^4 + 27^4 + 29^4 + 30^4 = 3098760

\displaystyle = 1^4 + 2^4 + 4^4 + 7^4 + 8^4 + 11^4 + 13^4 + 14^4 + 16^4 + 19^4 + 21^4 + 22^4 + 25^4 + 26^4 + 28^4 + 31^4 = \Sigma B^4

In order to prove the Sum of Powers Partition Theorem, we will prove a slightly more general, but somewhat less-interesting, result, the Multi-partition Power Sum Theorem.

Definition 1

Given the multiset (or sequence)

\displaystyle S = S_\omega = \left< s_0, s_1, s_2, \dots, s_k, \dots \right>

Define the multisets (or sequences)

\displaystyle S_n = \left< s_0, s_1, s_2, \dots, s_n \right>

\displaystyle E_0 = \langle 0 \rangle

\displaystyle D_0 = \langle s_0 \rangle

\displaystyle E_{n+1} = E_n \cup \left< d + s_{n+1} \: | \: d \in D_n \right>

\displaystyle D_{n+1} = D_n \cup \left< e + s_{n+1} \: | \: e \in E_n \right>

The sets {E_j} are sets of EVEN sums, i.e. sums of an even number of summands; the sets {D_j} are sets of ODD sums.

Example 6 (initial general expansions)

\displaystyle S = S_\omega = \left< s_0, s_1, s_2, \dots \right>

\displaystyle E_0 = \langle 0 \rangle

\displaystyle D_0 = \langle s_0 \rangle

\displaystyle E_1 = E_0 \cup \left< d + s_1 \: | \: d \in D_0 \right> = \langle 0 \rangle \cup \left< d + s_1 \: | \: d \in \langle s_0 \rangle \right> = \langle 0, s_0 + s_1 \rangle

\displaystyle D_1 = D_0 \cup \left< e + s_1 \: | \: e \in E_0 \right> = \langle s_0 \rangle \cup \left< e + s_1 \: | \: e \in \langle 0 \rangle \right> = \langle s_0, s_1 \rangle

\displaystyle E_2 = E_1 \cup \left< d + s_2 \: | \: d \in D_1 \right> = \langle 0, s_0 + s_1 \rangle \cup \left< d + s_2 \: | \: d \in \langle s_0, s_1 \rangle \right> = \langle 0, s_0 + s_1, s_0 + s_2, s_1 + s_2 \rangle

\displaystyle D_2 = D_1 \cup \left< e + s_2 \: | \: e \in E_1 \right> = \langle s_0, s_1 \rangle \cup \left< e + s_2 \: | \: e \in \langle 0, s_0 + s_1 \rangle \right> = \langle s_0, s_1, s_2, s_0 + s_1 + s_2 \rangle

\displaystyle E_3 = \langle 0, s_0 + s_1, s_0 + s_2, s_1 + s_2, s_0 + s_3, s_1 + s_3, s_2 + s_3, s_0 + s_1 + s_2 + s_3 \rangle

\displaystyle D_3 = \langle s_0, s_1, s_2, s_0 + s_1 + s_2, s_3, s_0 + s_1 + s_3, s_0 + s_2 + s_3, s_1 + s_2 + s_3 \rangle

 

Definition 2

\displaystyle {\mathbb{P}}_\Sigma S = \left< \Sigma T \: | \: T \subseteq S \right>

Lemma 1 (Sum Partition — {\cup})

Considering multiset union

\displaystyle E_n \cup D_n = {\mathbb{P}}_\Sigma S_n

 

Proof: (By induction on {n}.) \Box

Lemma 2 (Sum Partition — {\cap})

Considering multiset intersection

\displaystyle E_n \cap D_n = \emptyset

(We may also regard this in terms of ordinary sets if the sums above are considered as formal sums, and the symbols {s_i} are pairwise distinct.)

 

Proof: (By induction on {n}.) \Box

Lemma 3 (Sum Partition — magnitude)

\displaystyle |E_n| + |D_n| = | {\mathbb{P}}_\Sigma S_n |

In fact:

\displaystyle |E_n| = |D_n| = 2^n

\displaystyle | {\mathbb{P}}_\Sigma S_n | = 2^{n+1}

Proof: (By induction on {n}.) \Box

Proposition 4 (Multi-partition Power Sum Theorem)

Given any {n \in \mathbb{N}_0}, {S_n = \langle s_0, s_1, s_2, \dots, s_n \rangle} and with {E_n} and {D_n} as in definition 1:

\displaystyle \forall \, 0 \le k \le n \cdot \sum_{e \in E_n} e^k = \sum_{d \in D_n} d^k \ \ \ \ \ (1)

 

Proof:

Base case: {n = 0}:

\displaystyle E_0 =_{\mathrm{(def)}} \langle 0 \rangle

\displaystyle D_0 =_{\mathrm{(def)}} \langle s_0 \rangle

The only {k} to consider is {k = 0}. But {0^0 = {s_0}^0}.

Inductive case.

Suppose the theorem holds for {n}, and consider the case {n+1}.

\displaystyle E_{n+1} =_{\mathrm{(def)}} E_n \cup \left< s_{n+1} + d \: | \: d \in D_n \right>

\displaystyle D_{n+1} =_{\mathrm{(def)}} D_n \cup \left\{ s_{n+1} + e \: | \: e \in E_n \right>

Part 1. Consider {0 \le k \le n < n+1}.

up_to_n

\displaystyle \sum_{e \in E_{n+1}} e^k =_{\mathrm{(def)}} \sum_{e \in E_n} e^k + \sum_{d \in D_n} \left( s_{n+1} + d \right)^k

\displaystyle \sum_{d \in D_{n+1}} d^k =_{\mathrm{(def)}} \sum_{d \in D_n} d^k + \sum_{e \in E_n} \left( s_{n+1} + e \right)^k

The left summands are equal by inductive hypothesis, so we must show equality of the right summands.

\displaystyle \sum_{d \in D_n} \left( s_{n+1} + d \right)^k

\displaystyle =_{\mathrm{(binomial)}} \sum_{d \in D_n} \sum_{j=0}^{k} \binom{k}{j}{s_{n+1}}^{k-j} \cdot d^j

\displaystyle = \sum_{j=0}^{k} \binom{k}{j}{s_{n+1}}^{k-j} \cdot \sum_{d \in D_n} d^j

\displaystyle =_{\mathrm{(hypothesis)}} \sum_{j=0}^{k} \binom{k}{j}{s_{n+1}}^{k-j} \cdot \sum_{e \in E_n} e^j

\displaystyle = \sum_{e \in E_n} \sum_{j=0}^{k} \binom{k}{j}{s_{n+1}}^{k-j} \cdot e^j

\displaystyle =_{\mathrm{(binomial)}} \sum_{e \in E_n} \left( s_{n+1} + e \right)^k

Part 2. Consider {k = n+1}.

n_plus_1

\displaystyle \sum_{e \in E_{n+1}} e^k

\displaystyle =_{(k=n+1)} \sum_{e \in E_{n+1}} e^{n+1}

\displaystyle =_{\mathrm{(def)}} \sum_{e \in E_n} e^{n+1} + \sum_{d \in D_n} \left( s_{n+1} + d \right)^{n+1}

\displaystyle =_{\mathrm{(binomial)}} \sum_{e \in E_n} e^{n+1} + \sum_{d \in D_n} \sum_{j=0}^{n+1} \binom{n+1}{j}{s_{n+1}}^{(n+1)-j} \cdot d^j

\displaystyle = \sum_{e \in E_n} e^{n+1} + \sum_{j=0}^{n+1} \binom{n+1}{j}{s_{n+1}}^{(n+1)-j} \cdot \sum_{d \in D_n} d^j

\displaystyle =_{\mathrm{(split)}} \sum_{e \in E_n} e^{n+1} + \sum_{j=0}^{n} \binom{n+1}{j}{s_{n+1}}^{(n+1)-j} \cdot \sum_{d \in D_n} d^j + \binom{n+1}{n+1}{s_{n+1}}^{0} \cdot \sum_{d \in D_n} d^{n+1}

\displaystyle = \sum_{e \in E_n} e^{n+1} + \sum_{j=0}^{n} \binom{n+1}{j}{s_{n+1}}^{(n+1)-j} \cdot \sum_{d \in D_n} d^j + \sum_{d \in D_n} d^{n+1}

\displaystyle =_{\mathrm{(swap)}} \sum_{d \in D_n} d^{n+1} + \sum_{j=0}^{n} \binom{n+1}{j}{s_{n+1}}^{(n+1)-j} \cdot \sum_{d \in D_n} d^j + \sum_{e \in E_n} e^{n+1}

\displaystyle =_{\mathrm{(hypothesis)}} \sum_{d \in D_n} d^{n+1} + \sum_{j=0}^{n} \binom{n+1}{j}{s_{n+1}}^{(n+1)-j} \cdot \sum_{e \in E_n} e^j + \sum_{e \in E_n} e^{n+1}

\displaystyle = \sum_{d \in D_n} d^{n+1} + \sum_{j=0}^{n} \binom{n+1}{j}{s_{n+1}}^{(n+1)-j} \cdot \sum_{e \in E_n} e^j + \binom{n+1}{n+1}{s_{n+1}}^{0} \cdot \sum_{e \in E_n} e^{n+1}

\displaystyle =_{\mathrm{(join)}} \sum_{d \in D_n} d^{n+1} + \sum_{j=0}^{n+1} \binom{n+1}{j}{s_{n+1}}^{(n+1)-j} \cdot \sum_{e \in E_n} e^j

\displaystyle = \sum_{d \in D_n} d^{n+1} + \sum_{e \in E_n} \sum_{j=0}^{n+1} \binom{n+1}{j}{s_{n+1}}^{(n+1)-j} \cdot e^j

\displaystyle =_{\mathrm{(binomial)}} \sum_{d \in D_n} d^{n+1} + \sum_{e \in E_n} \left( s_{n+1} + e \right)^{n+1}

\displaystyle =_{\mathrm{(def)}} \sum_{d \in D_{n+1}} d^{n+1}

\displaystyle =_{(k=n+1)} \sum_{d \in D_{n+1}} d^k

From parts 1 and 2, we have, respectively,

\displaystyle \forall \, 0 \le k \le n \cdot \sum_{e \in E_{n+1}} e^k = \sum_{d \in D_{n+1}} d^k

\displaystyle (k = n+1) \cdot \sum_{e \in E_{n+1}} e^{n+1} = \sum_{d \in D_{n+1}} d^{n+1}

Thus

\displaystyle \forall \, 0 \le k \le n+1 \cdot \sum_{e \in E_{n+1}} e^k = \sum_{d \in D_{n+1}} d^k

which completes the proof.

Note that the (swap) step in this proof, above, is required as, generally,

\displaystyle \sum_{e \in E_n} e^{n+1} \not\equiv \sum_{d \in D_n} d^{n+1}

\Box

Example 7 (particular power expansions)

\displaystyle S = S_\omega = \left< s_0, s_1, s_2, \dots \right>

\displaystyle | E_0 | = \Sigma {E_0}^0 = \Sigma \langle 0^0 \rangle = 1

\displaystyle | D_0 | = \Sigma {D_0}^0 = \Sigma \langle {s_0}^0 \rangle = 1

\displaystyle \Sigma E_1 = \Sigma \langle 0, s_0 + s_1 \rangle = s_0 + s_1

\displaystyle \Sigma D_1 = \Sigma \langle s_0, s_1 \rangle = s_0 + s_1

\displaystyle \Sigma E_2 = \Sigma \langle 0, s_0 + s_1, s_0 + s_2, s_1 + s_2 \rangle = 2 s_0 + 2 s_1 + 2 s_2

\displaystyle \Sigma D_2 = \Sigma \langle s_0, s_1, s_2, s_0 + s_1 + s_2 \rangle = 2 s_0 + 2 s_1 + 2 s_2

\displaystyle \Sigma {E_2}^2 = \Sigma \langle 0^2, (s_0 + s_1)^2, (s_0 + s_2)^2, (s_1 + s_2)^2 \rangle = 2 {s_0}^2 + 2 {s_1}^2 + 2 {s_2}^2 + 2 s_0 s_1 + 2 s_0 s_2 + 2 s_1 s_2

\displaystyle \Sigma {D_2}^2 = \Sigma \langle {s_0}^2, {s_1}^2, {s_2}^2, (s_0 + s_1 + s_2)^2 \rangle = 2 {s_0}^2 + 2 {s_1}^2 + 2 {s_2}^2 + 2 s_0 s_1 + 2 s_0 s_2 + 2 s_1 s_2

\displaystyle {E_3}^k = \langle 0^k, (s_0 + s_1)^k, (s_0 + s_2)^k, (s_1 + s_2)^k, (s_0 + s_3)^k, (s_1 + s_3)^k, (s_2 + s_3)^k, (s_0 + s_1 + s_2 + s_3)^k \rangle

\displaystyle =_{({\mathrm{for}} \: k \in \{0, 1, 2, 3\})}

\displaystyle {D_3}^k = \langle {s_0}^k, {s_1}^k, {s_2}^k, (s_0 + s_1 + s_2)^k, {s_3}^k, (s_0 + s_1 + s_3)^k, (s_0 + s_2 + s_3)^k, (s_1 + s_2 + s_3)^k \rangle

 

Definition 3 Let

\displaystyle \mathbf{2}_{n} = \{ 0, 1, 2, \dots, 2^{n}-1 \}

And now … the main result:

Corollary 5 (Partition Power Sum Theorem)

\displaystyle \forall n \in \mathbb{N}_0 \cdot \exists \; {\mathrm {partition}} \; A, B \; {\mathrm {of}} \; \mathbf{2}_{n+1} \cdot \forall \, 0 \le k \le n \cdot \sum_{a \in A} a^k = \sum_{b \in B} b^k \ \ \ \ \ (2)

 

Proof:

Let {n \in {\mathbb N}_0}. Let {s_j = 2^j} for {0 \le j \le n}.

Let {A=E_n}, {B=D_n}.

By proposition 4, the sets {A} and {B} satisfy

\displaystyle \forall \, 0 \le k \le n \cdot \sum_{a \in A} a^k = \sum_{b \in B} b^k

We have

\displaystyle {\mathbb{P}}_\Sigma S_n = {\mathbb{P}}_\Sigma \langle 2^0, 2^1, 2^2, \dots, 2^n \rangle = \langle 0, 1, 2, \dots, 2^{n+1}-1 \rangle

By lemmas 1, 2 and 3, {E_n}, {D_n} form a partition of {{\mathbb{P}}_\Sigma S_n}. That is, {A} and {B} form a partition of {\mathbf{2}_{n+1}}, which completes the proof.

\Box

The sets {A=E_j} are sets of so-called EVIL numbers; the sets {B=D_j} are sets of ODIOUS numbers.

Conjecture 6 The partition in (2) is unique (up to exchange of {A} and {B}).

There is empirical evidence for this. A brute-force search by computer finds only (and exactly) one solution for cases up to {n = 4}.

To disprove the conjecture, only a single counterexample need be found.

A proof of the conjecture might be found by a descent approach, perhaps.

 

PDF version of this article.

Advertisements

One Response to “The Partition Sum of Powers Theorem”

  1. Rob Says:

    2016-03-09 updated with corrections; PDF also updated.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: