## 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}$.

$\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}$.

$\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.

### One Response to “The Partition Sum of Powers Theorem”

1. Rob Says:

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