April 2002
Part 1:
For k=1,2,4,8 (or any power of 2), the answer is no.
The lifetime of any initial state is bounded by (k*log N).
Let j denote the highest power of 2 not exceeding N.
After k steps all entries in the vector will be divisible by 2
(see the explanation below);
after another k steps, they will be divisible by 4;
after the third round of k steps, they will be divisibly by 8;
and after (log N) rounds of k steps, they will be divisible by j.
Since no entry ever exceeds N, the vector will contain only 0 and j, so it will be a final state. (Another k steps will bring it to the 0 vector.)
In fact for k=1 the lifetime is 0, since each initial state is already a final state. For k=2 the lifetime is at most 1: the initial state (a,b) leads, in one step, to the final state (|a-b|,|a-b|). But for k=4, the maximum lifetime really does behave like c*log N for some positive constant c.
To see why all entries must be even after k steps (if k is a power of 2), consider the entries modulo 2 (we will just care whether they are even or odd). Starting with vector {x(i)}, after one step the vector is {x(i) + x(i+1), mod 2}. (Modulo 2, each of a+b, a-b, b-a, |b-a| has the same parity. Also the indices wrap around, so that index k+1 is considered to be the same as index 1.)
After 2 steps the vector is {x(i) + x(i+2), mod 2}.
After 4 steps it is {x(i) + x(i+4), mod 2} .
After 8 steps it is {x(i) + x(i+8), mod 2} ; etc., until
after k steps it is
{x(i) + x(i+k), mod 2} = {x(i) + x(i), mod 2} = {0, mod 2}.
That is, after k steps all the entries are even.
By considering the integer vector formed by halving all the entries x(i) obtained after k steps, and applying the above argument again, we see that after k more steps these halved entries x(i)/2 will also become even, so that x(i) have become divisible by 4.
After (k*log N) steps they are all divisible by j, so they are either 0 or j, and we have reached a final state.
For k=3,5,6,7,9,10,11,12, the answer is yes.
For k=3, consider the initial state (N,N-1,1).
As long as N is at least 3, the state (N,N-1,1) is followed by the state (1,N-2,N-1), and then by (N-3,1,N-2), which (after rotation, which doesn't matter) is just (N-2,N-3,1).
It has taken two steps to reach a state similar to the initial state but with N decreased by 2.
Clearly it will take N-2 similar steps to reduce us to (2,1,1), and the next step gives the final state (1,0,1).
So the lifetime of (N,N-1,1) is N-1.
We can take c(3)=1 and d(3)=1, and the desired inequality holds.
For k=6, use the initial state (N,N-1,1,N,N-1,1); indeed, whenever k is a multiple of 3, just repeat the (N,N-1,1) enough times to fill out the vector.
The lifetime is still N-1.
For k=5 and N large enough, the initial state (1,N,N,1,0) yields, after three steps, a state which is a rotation of (1,N-2,N-2,1,0).
We can take c(5)=3/2 and d(5)=2.
Again we can handle any multiple of 5 as well.
For k=7 and N large enough, the initial state (1,N,N,1,0,0,0) yields,
after seven steps, a state which is a rotation of (1,N-4,N-4,1,0,0,0).
Take c(7)=7/4 and d(7)=5.
For k=11 and N large enough, the initial state (0,1,1,1,3,N,N,3,1,1,1) yields, after 31 steps, a rotation of (0,1,1,1,3,N-24,N-24,3,1,1,1).
Take c(11)=31/24 and d(11)=24.
For k=13 the linear lifetimes still exist, but for some reason they are harder to find. With an initial state of (0, n, 2, 1, 0, n, n, n, n, 0, 1, 2, n), after 63 steps we get a similar state with n diminished by 334.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com