The set of numbers 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 th powers.

For example, for :

can be partitioned as

so that

and, lastly,

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

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 , then the condition of having the same size may be rephrased as having equal sums of zeroth powers.

Example 1 ()can be partitioned as

so that

Example 2 ()can be partitioned as

so that

Example 3 ()can be partitioned as

so that

Example 4 ()can be partitioned as

so that

Example 5 ()can be partitioned as

so that

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

Given the multiset (or sequence)

Define the multisets (or sequences)

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

Example 6 (initial general expansions)

Definition 2

Considering multiset union

*Proof:* (By induction on .)

Considering multiset intersection

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

*Proof:* (By induction on .)

Lemma 3(Sum Partition — magnitude)

In fact:

*Proof:* (By induction on .)

Proposition 4 (Multi-partition Power Sum Theorem)Given any , and with and as in definition 1:

*Proof:*

Base case: :

The only to consider is . But .

Inductive case.

Suppose the theorem holds for , and consider the case .

Part 1. Consider .

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

Part 2. Consider .

From parts 1 and 2, we have, respectively,

Thus

which completes the proof.

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

Example 7 (particular power expansions)

Definition 3Let

And now … the main result:

Corollary 5 (Partition Power Sum Theorem)

*Proof:*

Let . Let for .

Let , .

By proposition 4, the sets and satisfy

We have

By lemmas 1, 2 and 3, , form a partition of . That is, and form a partition of , which completes the proof.

The sets are sets of so-called EVIL numbers; the sets are sets of ODIOUS numbers.

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

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

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

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

Wednesday, 9 March 2016 at 23:13 |

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