Avoiding chazakah with the Prouhet-Thue-Morse sequence

Ingredients of today’s mathematical stew include beans, boats, never-ending chess-games, a composer who’s into aperiodic percussion, an ABBA from Scandinavia that’s not the famous pop group, a Jewish camp song, and a way to calculate 0² − 1² − 2² + 3² − 4² + 5² + 6² − 7² using calculus. Oh, and did I mention beans?

During college, I learned about the traditional Jewish tenet that if you perform some voluntary religious observance three times in a row, you’re obliged to keep doing it forever — that through force of repetition, what was formerly a mere custom becomes as binding as a commandment (or, some say, you’ve effectively made a vow to do it forever, even if you didn’t intend to). The word for this phenomenon is chazakah, or “strengthening”.

For example, consider the question of whether, on the Sabbath, one should light the candles from left to right (option A) or from right to left (option B). The Babylonian rabbis Hillel and Shammai, usually a reliable source of contrary rulings on issues of all kinds (they clashed over the proper order in which to light Hanukah candles), were silent on the question of the right way to light shabbat candles since the practice didn’t become a tradition until later.  Subsequent arbiters of halachah don’t seem to have considered the shabbat candles question either, so one can do as one pleases, at least at the start. But: once one does it the same way three times in a row (AAA or BBB), a fastidious adherence to the concept of chazakah would oblige one to continue the pattern forever (AAAA… or BBBB…).

(I’m oversimplifying Jewish law quite a bit, but since this is a pedagogical example, I’m going to stick to my oversimplification and omit any further apology.)

I have some experience raising kids, and I think a similar “rule of three” applies there.  If you do something three times the same way, your child will want it to be done that way forever after.  For instance, say you regularly serve your fussy child puréed beans.  If at some rushed dinnertime you skip the puréeing, your kid is likely to pipe up that you’re not doing it “the always-always way”.

One strategy for dealing with this is to alternate.  You could serve puréed beans one night, unpuréed beans the next night, and so on.  But then, heaven help you if the kid notices the pattern and you serve unpuréed beans two nights in a row.  “No fair! I had unpuréed beans LAST night!  We’re supposed to alternate!”

Likewise, for the shabbat candle-lighting problem, if you alternate between left-to-right (A) and right-to-left (B) three times (ABABAB), then you’ve created a chazakah and, arguably, you’re obligated to continue alternating forever (ABABABAB…).

What to do?

JEWISH SUMMER CAMP AND A FAMOUS SEQUENCE

As it happens, a Hebrew call-and-response song I learned before I went to college has the seeds of an answer.  I don’t know if it has an official name, but we might as well call it “the Abba-Eema song” (abba means father and eema means mother). It spread through the Jewish community by way of Jewish summer camps. If anyone has a link to a recording of the song, please let me know! It goes like this:

CALL: Abba!
RESPONSE: Eema!
CALL: Eema!
RESPONSE: Abba!
CALL: Abba eema!
RESPONSE: Eema abba!
CALL: Eema abba!
RESPONE: Abba eema!
CALL: Abba eema eema abba!
RESPONSE: Eema abba abba eema!
CALL: Eema abba abba eema!
RESPONSE: Abba eema eema abba!

Some callers will drag it out even longer:

CALL: Abba eema eema abba eema abba abba eema!
RESPONSE: Eema abba abba eema abba eema eema abba!
CALL: Eema abba abba eema abba eema eema abba!
RESPONSE: Abba eema eema abba eema abba abba eema!

I’ve never heard the song taken beyond the level of an 8-word call and an 8-word response, but there’s no reason it needs to stop at 8; the song could move on to blocks of 16 words, then blocks of 32 words, and so on.  If we replace “abba” by “A” and “eema” by “B” for brevity, so that the last call-and-response pair given above are ABBABAAB and BAABABBA (it’s an amusing coincidence that ABBA, in addition to being the pattern that governs the song, is also the first word of the song!), and we write down the first 1-word call, the first 2-word call, the first 4-word call, etc. we get

A
AB
ABBA
ABBABAAB
ABBABAABBAABABBA
ABBABAABBAABABBABAABABBAABBABAAB
…

Each block is obtained by taking the preceding block and appending to it its “gender reversal”, with all A’s replaced by B’s and vice versa. If we take this to the limit, we get an infinite sequence of A’s and B’s, which you could also write as an infinite sequence of 1’s and 2’s if you’re inclined to be more arithmetical about it:

12212112211212212112122112212112…

This sequence was independently invented by French mathematician Eugène Prouhet (pronounced halfway between “proo-ay” and “proo-eh”), Norwegian mathematician Axel Thue (pronounced halfway between “too-uh” and “too-eh”), and American mathematician Marston Morse (pronounced, you know, like “Morse”). It used to be called the Thue-Morse sequence before Prouhet’s priority was recognized; now it’s often called the Prouhet-Thue-Morse sequence. (If any you can find a photo of Prouhet, please let me know!)

Axel Thue

Marston Morse

A great place to start learning about the PTM sequence is by watching Matt Parker’s video.  A more technical discussion is available at the Wikipedia page, and hardy mathematical souls should check out “The ubiquitous Prouhet-Thue-Morse sequence” by Jean-Paul Allouche and Jeffrey Shallit.

The PTM sequence solves our problem of how to avoid creating a chazakah, that is, how to have a long finite sequence of A’s and B’s in which no fixed pattern of A’s and B’s occurs three or more times in direct succession. For instance, the sequence contains the letter-string ABBA, and it contains the doubled string ABBAABBA (the “square” of ABBA), but it doesn’t contain the tripled string ABBAABBAABBA (the “cube” of ABBA). The same goes for every other string of A’s and B’s; if you’re interested in seeing a proof, check out the discussion of the “Thue-Morse cube-freeness theorem” on the math stackexchange.

Of course, some would say that following any fixed rule, such as the PTM sequence, more than three times establishes a chazakah — so that if you light your shabbat candles in accordance with the Prouhet-Thue-Morse sequence for three weeks in a row, then you’re obligated to do so forever after.  So you haven’t really gained anything besides having a more complicated rule to follow. Oh well!

Now, if you belong to a (purely fictional) ultra-stringent Orthodox sect that says that doing something merely twice in a row creates a chazakah, then I have bad news and good news for you. The bad news is that, for a binary choice (A versus B), every infinite sequence of A’s and B’s will create a chazakah after at most 4 terms (see Endnote #1).  The good news is that for a three-way choice you can avoid creating a chazakah forever, and the PTM sequence can help you do it.  For each term of the numerical PTM sequence starting from the second, record whether it is less than, greater than, or equal to the next term:

This new sequence of <‘s, =’s, and >’s is “square-free”, that is, it does not contain anywhere within it two consecutive appearances of any fixed string of symbols.

All of the above was worked out by Axel Thue. It’s unclear what inspired him; Allouche and Shallit report that “Thue explained he had no particular application in mind, but he thought the problem was interesting enough in itself to deserve attention.” Other mathematicians found Thue’s line of inquiry compelling, and it gave rise to a whole new subsubfield of mathematics called “combinatorics on words”. For more information see the Wikipedia pages on Square-free words and on combinatorics on words more broadly.

FRACTALS

The PTM sequence is a self-similar object, showing the same behavior at different scales.  In one direction, if you remove every other term of the PTM sequence starting with the 2nd, you get the PTM sequence back again:

A B B A B A A B B A A B A B B A …
becomes
A     B    B     A     B    A    A    B   …

In the other direction, if you take every “A” in the PTM sequence A,B,B,A,B,A,A,B,…  and replace it by the two-letter pattern “AB” while simultaneously replacing each “B” in the PTM sequence by the two-letter pattern “BA”, you’ll get — you guessed it — the PTM sequence again:

A  B  B  A   B  A  A  B    B  A  A  B    A  B  B  A …
becomes
ABBABAABBAABABBABAABABBAABBABAAB…

One-third of a Koch snowflake

This sort of self-similarity may remind you of fractals, and indeed, the PTM sequence is intimately connected with a famous fractal called the Koch snowflake curve.  If you program a LOGO turtle to make turns in accordance with the PTM sequence and to draw its trajectory while it does so, and you give your turtle enough room, chances are good that it’ll draw a path that, viewed from afar, looks a lot like a segment of a Koch snowflake.  For more about this, see this blog entry by Zachary Abel  or the (anonymous?) video “The Thue-Morse Sequence: A Turtle Graphics”. And for background on the Koch snowflake,  you could do worse than hear how Salman Khan explains it.

MUSIC AND POETRY

Since the Prouhet-Thue-Morse sequence does such a good job of avoiding repetition without seeming random you can imagine it would be of interest to composers, especially the kind whose starting point is some sort of compositional procedure rather than, say, a tune.  They need a procedure that will strike a balance between pure disorder and pure order, both of which are boring to listen to.

The Norwegian composer Per Nørgård (Tom Service wrote a very enjoyable Guardian article about the man and his work) is a fan of the PTM sequence, and his “Drumbook” has exercises for percussion ensembles in which the players play the PTM sequence at different speeds in a way that highlights the self-similar character of the sequence.

Exercise 8 from Per Norgard’s “Drumbook”

For his large-scale compositions, Nørgård sought a sequence that, like the PTM sequence, would be non-repetitive, but wouldn’t be limited to such a small “alphabet”.  The souped-up version of the PTM sequence that he devised for his purposes, and which has been part of the armature for many of his major works, is what he calls the “infinity series”.  You can check out Nørgård’s own page about it, or hear what it sounds like, or read what mathematicians have proved about it.

A different artistic embodiment of the PTM sequence, or at least its first eight terms, is found in certain sonnets, such as the original version of Stephane Mallarme’s “Le Pitre Châtié” (1864), Arthur Rimbaud’s “Voyelles” (1871), and Paul Valery’s “Je ne veux pas que tu sois triste” (1945); in each of these three sonnets, the first eight lines use the rhyme scheme “abba baab”.  See the Oulipo page on the abba baab rhyme-scheme for a listing of many poems of this kind.

APPLICATIONS

One of the early applications of the PTM sequence was to the theory of chess.  Chess games between good players can last hundreds of moves before one player resigns or both players agree to a draw.  But what if neither player is willing to agree to a draw?  Must a chess game, if played according to the rules, necessarily ultimately end?  The answer depends on the rules of play.  One rule designed to prevent games from going on forever, sometimes called the “German Rule”, was that a game is deemed a draw if the same sequence of moves — with all pieces at the same positions — appears three times in a row. In 1929 the Dutch mathematician and chess player Max Euwe (re-)invented the PTM sequence and used it to construct a legal chess-game that goes on forever in spite of the German Rule is used, thereby demonstrating the Rule’s limitations.

Another sort of application is to competitive rowing, and the question of how to arrange rowers so as to minimize the amount of “wiggle”.  Placing rowers in the pattern RLLRLRRL (where R represents a rower who pulls on the right side of the boat and L represents a rower who pulls on the left side of the boat) has potential advantages over the more common RLRLRLRL pattern. See Mathematician Solves Rowing Boat “Wiggle” Problem and John D. Barrow’s Rowing and the Same-Sum Problem Have Their Moments and Jeff Shallit’s blog-post Rowing and the Thue-Morse Sequence.

For more applications, see the article by Allouche and Shallit.

EVIL AND ODIOUS NUMBERS

Suppose you wanted to know the 2017th term of the PTM sequence.  How much work would you have to do?  Would you have to figure out all the preceding terms as well?  It turns out there’s a shortcut.  You subtract 1 from 2017, obtaining 2016; then express that number in base two, obtaining 11111100000; then count the number of 1’s, obtaining 6; and then, depending on whether the number of 1’s is even or odd, output an A or a B (since 6 is even, the 2017th term in the PTM sequence is an A).

What the heck is going on here?  Before we can discuss that, let’s introduce some whimsical but useful terminology coined by John Conway and Ingrid Daubechies.  It’s a variation on the familiar way of discriminating between the counting numbers according to their “parity” (odd versus even).  In this new game, we discriminate between the counting numbers according to their “perfidy” (“odious” versus “evil”).  A counting number is odious if it has an odd number of 1s in its binary expansion, and evil if it has an even number of 1s in its binary expansion. So for instance 17 is evil since its binary expansion 10001 contains an even number of 1’s.

There’s a nice description of the Prouhet-Thue-Morse sequence in terms of perfidy, but to get it to be really nice, we have to imagine that the starting term of the sequence is counted as the 0th term, that the term after that is counted as the 1st term, and so on. Once we make that recalibration, there’s a crisp description of the PTM sequence: it’s nth term is A if n is evil and B if n is odious. Check it out for the integers between 0 and 7:

0 = 000: 0 1’s: 0 is even: A
1 = 001: 1 1  : 1 is odd : B
2 = 010: 1 1  : 1 is odd : B
3 = 011: 2 1’s: 2 is even: A
4 = 100: 1 1   : 1 is odd : B
5 = 101: 2 1’s: 2 is even: A
6 = 110: 2 1’s: 2 is even: A
7 = 111: 3 1’s: 3 is odd : B

Try it for 0 through 15, and you’ll probably see what’s going on, and why perfidy governs the PTM sequence.

Here’s a puzzle for you that relates to Eugène Prouhet’s original concerns: can you divide the eight numbers from 101 to 108 into two sets A and B, each having four elements, such that
(1) the sum of the elements of A equals the sum of the elements of B, and
(2) the sum of the squares of the elements of A equals the sum of the squares of the elements of B?
Can you do it without a calculator to help you?

You might want to chew on this puzzle before reading further. See Endnote #2 for the solution.

Prouhet solved this puzzle and infinitely many others like it.  For instance, given any sixteen consecutive integers, Prouhet showed that you could divide them into two sets A and B, each having eight elements, such that
(1) the sum of the elements of A equals the sum of the elements of B,
(2) the sum of the squares of the elements of A equals the sum of the squares of the elements of B, and
(3) the sum of the cubes of the elements of A equals the sum of the cubes of the elements of B.
More generally, given any 2^N consecutive numbers, you can divide them into two equal-sized sets A and B such that the sum of the kth powers of the elements of A equals the sum of the kth powers of the elements of B for all k from 1 up through N−1.

Matt Parker discusses this in his “Share the Power Puzzle” video and presents the answer in his “Fairest Sharing Sequence” video but he doesn’t explain why the answer works.  I’ll give you more of a sense of what’s going on and what sorts of tricks would play a role in a full proof, focusing on the case N=3 for the sake of concreteness.

PROVING PROUHET PERFIDIOUSLY

Let’s go back to the case of dividing eight consecutive numbers into two groups of four, and for simplicity let’s think about 0 through 7 instead of 101 through 108.  As you might guess from my choice of notation (or from the opening paragraph of this essay), if we assign the numbers 0 through 7 to the sets A through B in accordance with the pattern ABBABAAB, we get sets A and B that not only have the same sum but have the same sum when each number is replaced by its square: that is, 0 + 3 + 5 + 6 = 1 + 2 + 4 + 7 and also 0² + 3² + 5² + 6² = 1² + 2² + 4² + 7².

You could of course just verify these equations the obvious way, but what you’d learn from this wouldn’t help you with Prouhet’s broader questions.  So we want a less computational, more conceptual way to understand these equations.  A good way to see why these equations hold is to write each number as a sum of powers of two (which is of course closely related to writing each number in binary).  The equation
3 + 5 + 6 = 1 + 2 + 4 + 7
becomes the equation
(2+1) + (4+1) + (4+2) = (1) + (2) + (4) + (4+2+1),
and you can check that each summand that occurs here (1, 2, and 4) occurs just as many times on the left as it does on the right.

You can similarly prove
3² + 5² + 6² = 1² + 2² + 4² + 7².
by writing it as
(1+2)² + (1+4)² + (2+4)² = (1)² + (2)² + (4)² + (1+2+4)²,
expanding it by the distributive law, and matching up terms. Or, if you like “algebra that looks like algebra”, prove (x+y)² + (x+z)² + (y+z)² = (x)² + (y)² + (z)² + (x+y+z)², and then replace x, y, and z by 1, 2, and 4.

It may strike you as perverse to prove a statement in arithmetic using algebra in this way, but (a) this approach has the virtue that it generalizes to higher values of N in Prouhet’s general problem (because for each type of term we can find an exact formula for how many times it occurs), and (b) fasten your seat belts, because later on I’m going to prove the same equation using calculus, not algebra! (See Endnote #3.)

Those who don’t love algebra and don’t love (or don’t know) calculus might be inclined to seek a geometric proof of 3² + 5² + 6² = 1² + 2² + 4² + 7² by showing how to take a 3-by-3 square, a 5-by-5 square, and a 6-by-6 square, cut them into pieces, and then rearrange the pieces to form a 1-by-1 square, a 2-by-2 square, a 4-by-4 square, and a 7-by-7 square. Of course you can do it with 70 pieces (just divide each square up into 1-by-1 squares), but that would be tedious. Are there any particularly elegant ways to do it? Send me your solutions or post them to the comments! I’ll insert details in Endnote #4 (currently empty).

Likewise, can any of you find a pleasing way to prove that 1² + 4² + 6² + 7² = 2² + 3² + 5² + 8² using a geometric dissection?

In both cases, feel free to explore dissections that use oblique angles.

AN INFINITE PRODUCT

Here’s my last “public menu” offering for today. (Other dishes — tasty to those who have a taste for such things — can be found in the “secret menu”, that is, in the Endnotes.) Consider the fractions
1/2, 3/4, 5/6, 7/8, 9/10, 11/12, 13/14, 15/16, …
Align them with the successive terms of the PTM sequence ABBABAAB…, and flip the fractions that line up with A’s (shown below in boldface):
2/1, 3/4, 5/6, 8/7, 9/10, 12/11, 14/13, 15/16, …
What do you get when you multiply these fractions together, in the limit as the number of factors goes to infinity? Try it, and see if you notice the amazing answer! See Endnote #5.

Thanks to Eric Angelini, Jean-Paul Delahaye, Noam Elkies, Bill Gosper, Sandi Gubin, Michael Kleber, Mike Lawler, Joe Malkevitch, Henri Picciotto, Ted Propp, Jeff Shallit, and Glen Whitney.

Next month (Feb. 17): Three-point-one cheers for pi !

ENDNOTES

#1: If you start with AA, you get a chazakah and must continue doing A forever.  What if you start instead with AB?  You’d better not continue with a B, because ABB creates a chazakah (you must continue doing B forever).  So you’d better continue with an A, giving ABA.  What next?  You’re sunk; either you do ABAA (which obliges you to do A forever) or you do ABAB (which obliges you to do AB forever). That handles all sequences that start with A; sequences that start with B are similar.

#2: Apply the ABBABAAB pattern to get A = {101,104,106,107} and B = {102,103,105,108}.  Check:
101 + 104 + 106 + 107 = (101 + 0) + (101 + 3) + (101 + 5) + (101 + 6) =
= (101 + 1) + (101 + 2) + (101 + 4) + (101 + 7) = 102 + 103 + 105 + 108,
where the middle equality follows from 0+3+5+6 = 1+2+4+7 (which we proved earlier).

To prove the equation
(101 + 0)² + (101 + 3)² + (101 + 5)² + (101 + 6)² = (101 + 1)² + (101 + 2)² + (101 + 4)² + (101 + 7)²
first expand it out by the distributive law; the resulting messy equation can be derived by adding the three simpler equations
101² + 101² + 101² + 101² = 101² + 101² + 101² + 101²,
2 × 101 × (0 + 3 + 5 + 6) = 2 × 101 × (1 + 2 + 4 + 7), and
0² + 3² + 5² + 6² = 1² + 2² + 4² + 7².

What we did with the numbers 101 through 108 can be applied to any eight consecutive numbers. We could, if we’re feeling silly, apply it to the numbers −2 through 5, obtaining
(−2)² + (1)² + (3)² + (4)² = (−1)² + (0)² + (2)² + (5)²; if we cancel the (−2)² on the left with the (2)² on the right, and the (1)² on the left with the (−1)² on the right, and ditch the (0)², we’re left with just 3² + 4² = 5², a fact well-known to Pythagoras. And what is Pythagoras known for, other than his famous theorem? Founding a cult known, among other things, for proscribing the eating of beans. Which has nothing to do with Prouhet-Thue-Morse, but I couldn’t pass up an opportunity to mention beans again.

#3: Here’s my favorite way to think about 0² + 3² + 5² + 6² = 1² + 2² + 4² + 7²; suitably generalized, it gives the easiest proof I know of Prouhet’s result.  If you’re comfortable with polynomials and calculus, you just might like it too.  Or even if you don’t like it, knowing that I like it may tell you something about the way pure mathematicians’ minds work.

First, let me remind you why the numbers 0, 3, 5, and 6 appear on the left while the numbers 1, 2, 4, and 7 appear on the left: the first four numbers are evil while the other four numbers are odious.  That is, each of the first four numbers can be written as the sum of an EVEN number of different powers of 2 (in the case of 0, there are zero even numbers in the sum, and zero is an even number) while each of the other four numbers can be written as the sum of an ODD number of different powers of 2.

Second, let me rewrite the equation I’m trying to prove in a form that suggests the games we’re about to play with it:
0² − 1² − 2² + 3² − 4² + 5² + 6² − 7² = 0.

Third, let me introduce a soon-to-be-helpful polynomial that resembles that last left-hand-side, at least as far as the order of pluses and minuses is concerned:
x⁰ − x¹ − x² + x³ − x⁴ + x⁵ + x⁶ − x⁷.
You might prefer to write this as 1 − x − x² + x³ − x⁴ + x⁵ + x⁶ − x⁷.

Fourth, check that the preceding polynomial factors as (1−x¹)(1−x²)(1−x⁴).  To see this, write it as
(1+(−x¹)) (1+(−x²)) (1+(−x⁴)), use the distributive law with wild abandon, and then simplify, refraining from the temptation to carry out the additions in the exponents; you get
1 − x¹ − x² − x⁴ + x¹⁺² + x¹⁺⁴ + x²⁺⁴ − x¹⁺²⁺⁴
If, after doing this calculation, you step back from it, you can see that each term x^k comes with a plus sign when k is a sum of an even number of distinct powers of two and comes with a minus sign when k is a sum of an odd number of distinct powers of two; that is, we’re taking a sum of evil powers of x and subtracting from them a sum of odious powers of x.

So, let’s take stock of where we are: we’ve got
1 − x − x² + x³ − x⁴ + x⁵ + x⁶ − x⁷ = (1−x¹) (1−x²) (1−x⁴).
The right hand side is product of three factors that each vanish when you plug in x=1, so
(1)   1 − x − x² + x³ − x⁴ + x⁵ + x⁶ − x⁷ has a triple root at x=1.
Now differentiate:
(2)   −1 − 2x¹ + 3x² − 4x³ + 5x⁴ + 6x⁵ − 7x⁶ has a double root at x=1
(here I’m using the fact that the derivative of a function with a triple root somewhere has a double root at that same x value).  Now multiply that polynomial by x:
(3)   − x¹ − 2x² + 3x³ − 4x⁴ + 5x⁵ + 6x⁶ − 7x⁷ has a double root at x=1
(here I’m using the fact that if a function of x has a double root somewhere, multiplying the function by x gives a new function that still has a double root at that same x value).  Now differentiate again:
(4)   − 1² − 2²x + 3²x² − 4²x³ + 5²x⁴ + 6²x⁵ − 7²x⁶ has a simple root at x=1
(here I’m using the fact that the derivative of a function with a double root somewhere has a simple root at that same x value).  Now just plug in x=1:
(5)   − 1² − 2² + 3² − 4² + 5² + 6² − 7² = 0
(here I’m using the fact that if a function of x has a root at x=c for some c, then plugging in x=c makes the function take the value 0; that’s what “having a root” means!).

This is an application of the technique of generating functions, and it’s one of my all-time favorite tricks for solving problems about numbers. We introduce an x into a problem about numbers, manipulate some equations, and then at the end stick in x=1 or x=0 or something like that. You might wonder “If you’re just going to set x equal to 1 at the end, why not just set x equal to 1 at the start?”, but that won’t work. (You can differentiate with respect to x, but it makes no sense to differentiate with respect to 1!)

In the method of generating functions we see x taking on a new and ghostly kind of existence. In middle school, x is an unknown that we solve for; in high school, x becomes a variable that takes on a range of values; but here, x is more like a place-holder, a prop that we throw away once it’s served its purpose. It’s like a magical servant that we summon, command, and then send back to whence it came.

Why would anyone prefer this kind of proof of an equation like 0² + 3² + 5² + 6² = 1² + 2² + 4² + 7²? It’s all about what’s sitting around inside your brain. If you’re a high school student, you get lots of practice with arithmetic, so you’ll probably just want to square the numbers, add the squares, and compare the sums numerically — it’s what you’re used to. On the other hand, if you’re a theoretical mathematician, you get lots of practice with thinking about polynomials and functions and roots and derivatives, so those are the tools you’re likely to turn to first. (And maybe you’re also not very good at arithmetic; see Ben Orlin’s post “Why are mathematicians so bad at arithmetic?”.) But above all, this kind of proof, although it’s overkill for proving any specific proposition like 0² + 3² + 5² + 6² = 1² + 2² + 4² + 7², is exactly what you need for proving infinitely many equations of this kind, with more and more terms on each side, the way you do when proving Prouhet’s theorem.

#4: I’ll insert pictures of dissections once I’ve got some to show you!

#5: The rational numbers
(2/1),
(2/1)×(3/4),
(2/1)×(3/4)×(5/6),
(2/1)×(3/4)×(5/6)×(8/7), …
converge to the square root of 2! This beautiful fact was first noticed by D. R. Woods and proved by David Robbins. Jeff Shallit observed that, rather than starting with the PTM sequence and deriving the square root of 2 from it, one can play the game in reverse. Specifically, start with the sequence of fractions
1/2, 3/4, 5/6, 7/8, 9/10, 11/12, 13/14, 15/16, …
and an initial approximation to the square root of 2, namely 1. To get successive approximations, multiply your current approximation by the first not-yet-used fraction in this list or its reciprocal, depending on whether the current estimate is too low or too high. You’ll end up with
2/1 × 3/4 × 5/6 × 8/7 × 9/10 × 12/11 × 14/13 × 15/16 × …
from which the PTM sequence is easily found. Shallit’s observation was conjectural; it was proved by Allouche and Cohen a few years later.

#6: One (somewhat anachronistic) way to think about Prouhet’s theorem is with the concept of quasirandomness. If you chose four numbers between 0 and 7 at random, either with or without replacement, you’d expect their sum to be 14 (on average) and you’d expect the sum of their squares to be 70 (on average). The set {0,3,5,6} has the property that its elements add up to 14 and the squares of its elements add up to 70. So you might say that in this sense, the set {0,3,5,6} is quasirandom: it mimics the average-case behavior of a random 4-element subset of {0,1,2,3,4,5,6,7}.

#7: Divergent series are a whole topic unto themselves, and one that’s often treated in popular mathematics in an overly cavalier way (I’m thinking especially of videos about the divergent series 1+2+3+… that create more bafflement than insight). So I’m reluctant to dip my toe into these waters here, and to do what I’ve complained about other people doing: presenting “magical” formulas without presenting their context or answering questions like “Why are you trying to define this sum?”, “How do propose to define it?”, and “What gives you the right to to do this?” But I’m going to give in to temptation and talk about the series 1−2−3+4−5+6+7−8−… that you get by adding all the positive integers using signs that come from the PTM sequence (+−−+−++−…). This series diverges in the ordinary sense, but it “converges in the sense of Abel“: that is, for every x strictly between 0 and 1, the series 1−2x−3x²+4x³−5x⁴+6x⁵+7x⁶−8x⁷−… converges to some number we can call f(x), and as x approaches 1, f(x) approaches 0. So in the sense of Abel summation, 1−2−3+4−5+6+7−8−… evaluates to 0. What’s more, for any positive integer exponent k, 1^k−2^k−3^k+4^k−5^k+6^k+7^k−8^k−… evaluates to 0 (in the sense of Abel) as well. See my MathOverflow post “A Family of Divergent Series”.

REFERENCES

Jean-Paul Allouche and Jeffrey Shallit, “The ubiquitous Prouhet-Thue-Morse sequence”.

John D. Barrow, Rowing and the Same-Sum Problem Have Their Moments.

Martin Gardner, pages 29−30 and 244−247 of “The Magic Numbers of Dr. Matrix”.