Many years ago my former doctoral adviser Peter Neumann introduced me to an intriguing problem on number sequences. I believe he had seen it somewhere in a notorious article by John Hammersley: "On the enfeeblement of mathematical skills by ‘Modern Mathematics’ and by similar soft intellectual trash in schools and universities". Wow! That's a provocative title if ever there was one! It was published in the Bulletin of the Institute of Mathematics and its Applications, Volume 4 (1968), pages 66–85. It's a serious article and well worth reading. Hammersley mentioned this problem as an example of the kind he thought educators would find useful to introduce as part of a course designed to teach mathematical problem-solving. I'm describing it in this post because it is indeed a pretty problem which should be better known and Hammersley's more detailed follow-up article ("Sequences of Absolute Differences", SIAM Review, volume 11, pages 73–74) is (for me) hidden behind a paywall. See also this Wikipedia article for the origin of the problem.
The problem is about integer sequences and a certain operation that turns one sequence into another. Here's an absolutely trivial example with the sequence 2 4 1. We form another sequence by taking the differences of successive terms (the first term succeeding the last term), always taking the positive value. Thus 2 4 1 transforms in 2 3 1 (4-2=1, 4-1=3, and 2-1=1). Then we apply this same process again and again. We get
1 2 1, 1 1 2, 0 1 1, 1 0 1, 1 1 0, 0 1 1, 1 0 1, 1 1 0. Now we are in an infinite loop
1 1 0, 0 1 1, 1 0 1, 1 1 0.
It seems somewhat unnatural to always take the positive value of the difference but we'll see the reason soon. What is clear is that, no matter which sequence we start with, and no matter how long it is, the process will eventually settle into a loop (because in each interim sequence the maximum term cannot get larger as we go from one sequence to the next).
Let's try another sequence, this time of length 4, say 3 1 4 1. The sequence of sequences is now
3 1 4 1, 2 3 3 2, 1 0 1 0, 1 1 1 1, 0 0 0 0
This time we have actually reached a stationary point. Here's another length 4 example:
2 1 4 3 , 1 3 1 1, 2 2 0 0, 0 2 0 2, 2 2 2 2, 0 0 0 0
Another stationary point. One more length 4 example:
5 1 2 4, 4 1 2 1, 3 1 1 3, 2 0 2 0, 2 2 2 2 , 0 0 0 0.
Now a length 5 example
2 7 1 8 2, 5 6 7 6 0, 1 1 1 6 5, 0 0 5 1 4, 0 5 4 3 4, 5 1 1 1 4, 4 0 0 3 1, 4 0 3 2 3
4 3 1 1 1, 1 2 0 0 3, 1 2 0 3 2, 1 2 3 1 1, 1 1 2 0 0, 0 1 2 0 1, 1 2 2 1 0, 1 0 1 1 1
1 1 0 0 1, 0 1 0 1 0, 1 1 1 1 0, 0 0 0 1 1, 0 0 1 0 1, 0 1 1 1 0, 1 0 0 1 0,
and we have reached a cycle of length 7.
After a lot of similar exploration it turns out that cycles can be quite long and, while there is a lot of work on what they can be, there doesn't seem to be any significant interest in this exploration.
Except for just one amazing fact: in lengths 2, 4, 8, and any power of 2, the only cycle is the singleton cycle of all zeros. In the rest of this post I'll explain the reason for this.
From now on we'll be considering sequences of length n where n=2m is a power of 2. To begin with we'll regard the components of the sequences to be reduced modulo 2 - elements of the field of 2 elements. In this field addition and subtraction are the same so the basic transformation T (which is linear) takes a vector
v = (v1, v2, ..., vn)
into
T(v) = (v1+v2, v2+v3, ..., vn-1+vn, vn+v1) = v + S(v) where
S(v1,v2...,vn-1, vn) = (v2,v3, ..., vn,v1)
and S is the (linear) shift operator. Thus, with I denoting the identity operator, we have
T(v) = (I + S)(v)
Then, because I and S commute and we are working modulo 2,
Then T2(v) = (I + S)2(v) = (I2 + 2IS + S2) = (I + S2)(v). Similarly
T2k(v) = (I + S)2k(v) = (I+ S2k)(v), for all k.
In particular, when k=m, and n=2m, Sn=I
showing that Tn(v) = (I + I)(v) = 0.