Thue-Morse and fair sharing

Matt Parker on “the fairest sharing sequence”, the Thue-Morse sequence. The sequence is

0110 1001 1001 0110 1001 0110 0110 1001…

which is generated as follows:

at the first step, start with 0
invert the sequence, replacing all 0s with 1s and vice versa, and concatenate this to the original sequence

So this gives, in sequential steps: 0, 01, 0110, 01101001, …

It’s an interesting sequence, but why the title?

This is a follow-up to a video in which he proposes a puzzle: partition the numbers 0 through $2^{k+1}-1$ into two groups such that the sum of the 1st, 2nd, …, kth powers of each group are the same. For example, for $k = 3$ we have $0 + 3 + 5 + 6 = 1 + 2 + 4 + 7$ and $0^2 + 3^2 + 5^2 + 6^2 = 1^2 + 2^2 + 4^2 + 7^2$ .

The solution, as you may have guessed, is that the numbers on one side of the equality should be the positions of 0s among the first $2^{k+1}$ elements of the Thue-Morse sequence, and the numbers on the other side should be the positions of the 1s, where indexing starts at 0. This fact is proven in Allouche and Shallit’s paper “The ubiquitous Prouhet-􏰀Thue-􏰀Morse sequence” – see section 5.1.

So why is this about fair sharing? Let’s consider the $k = 2$ case again. We have $0^k + 3^k + 5^k + 6^k = 1^k + 2^k + 4^k + 7^k$ for $k = 0, 1, 2$ . That means, then, that we have

$f(0) + f(3) + f(5) + f(6) = f(1) + f(2) + f(4) + f(7)$

for any quadratic polynomial $f$ . So say that we’re divvying up some goods and I get the 0th, 3rd, 5th, and 6th most valuable item while you get the 1st, 2nd, 4th, and 7th. (We are computer scientists so we start counting from zero.) Then if we can write the value of the $n$ th item as a quadratic in $n$ , then we end up with the same value.

(How does this generalize to the case where $f$ is not polynomial? That seems relevant – for example what if $f(x) = e^{-x}$ or $1/(x+1)$ ? In a paper which independently rediscovered the Thue-Morse sequence, Robert Richman did some experiments which suggests that this still holds as long as $f$ isn’t “too far” from polynomial. This got written up in the Guardian as how to pour the perfect cup of coffee. Thue was Norwegian, and I hear Norwegians like coffee, so I think he’d approve.