Difference dynamics discussion

Before you read this article you are advised to try the Difference Dynamics investigation. Start with a finite sequence, for example  (25, 42, 6). The differences between your numbers give you three new numbers (17, 36, 19). Repeat this operation to give a sequence of sequences. In this example the sequence of sequences continues: (19, 17, 2),  (2, 15, 17),  (13, 2, 15),  (11, 13, 2),  (2, 11, 9) , (9, 2, 7),  (7, 5, 2),  (2, 3, 5),  (1, 2, 3),  (1, 1, 2),  (0,1,1) etc. You can produce chains of sequences like this for sequences of any length. The rule for generating these sequences is that you take the moduli of the differences between adjacent terms, taking the difference between the last term and the first term, to get the next sequence in the chain and repeat this process to get a sequence of sequences.

Read no further. You can try this for yourself, starting with a sequence of any length. Carry out your own investigation, make some conjectures about the behaviour of the sequences that you observe, at least for sequences of two, three and four terms, and try to prove your conjectures. When you tire of your own thoughts and you want to know what others have done with these ideas then read on.

 

This investigation is well known and has a long history. The problem is attributed to the Italian Enrico Ducci in the late 1800's, and the first proof of the theorem that is proved in this article seems to have appeared in 1937. The usual proof involves, among other things, expanding a sum of matrices by the binomial theorem over the field $\mathbb{Z}_2$. However, as the problem can be tackled by school students, it seems desirable to have elementary proofs of the conjectures they might make. The purpose of this article is to provide such proofs. 

 

A little experimentation leads to sequences that repeat in a cyclic pattern or to the sequence of sequences stopping with the zero sequence $(0, 0, ...0)$ which we call a fixed point of this iteration. This behaviour is typical of dynamical systems which are very important in mathematics.

There are many situations in which we want to measure something that changes with time, either discretely (say every week) or continuously. For example, we may count the number of elephants in Africa each year or record the temperature continuously at some spot in London. A dynamical system is a mathematical model of such a system, and dynamical systems are often used to predict population growth, weather, and so on. The essential feature of this type of system is that there is a set of all the possibilities for the measurements, together with some mathematical rule which tells us how our measurement will change with time. An important feature in any such model are the fixed points in the model: if the measurement is $X_n$ and the rule is $X_{n+1}=f(X_n)$ for some function $f$, then a fixed point is a measurement $X$ such that $f(X) = X$. In this case, if some $X_n$ takes the value $X$ then $X_{n+1}=X_n=X$ and the population (for example) will remain at this fixed value for ever.  A more general situation is when the sequence of measurements oscillates like for example, $A,B,A,B,A,...$ or $A,B,C,A,B,C,A,...$ giving cycles of periods two and three. Measurements in nature are often seen to follow cyclic patterns.

 

In this Difference Dynamics investigation, many sequences converge to repeating cycles such as$ (k, k, 0), (0, k, k), (k, 0, k), (k, k, 0)$ and some sequences end with the zero sequence $(0, 0, 0, ... 0)$ making it a fixed point for this iteration. So which sequences of sequences end with the zero sequence? Do all other sequences end in cycles?

As a first step let us prove that if this process does not produce a sequence of zeros then it must lead to a repeating cyclic pattern. Notice that after the first sequence all the numbers in the sequences are positive so without loss of generality we'll consider sequences with positive terms. Then taking differences in this iterative process makes sure that the largest number in the sequence stays the same or gets smaller.

The proof depends on the same reasoning as you can use to prove that if your school is big enough then there are at least two people in the school who have the same birthday. As there are only 366 possible birthdays, if there are more than 366 people in your school then at least two people must share a birthday.

The sequence we used as an example started with (25, 42, 6) so no number in any of the subsequent sequences can be bigger than 42. It follows that  there are at most 43 choices (0 to 42) for each number in the sequences making at most $43^3$ different possible sequences. There are not an infinite number of possibilities, so just as with the birthday example, sooner or later the iteration must repeat a sequence that has appeared earlier and repeat the earlier pattern. The same argument applies for any finite starting sequence of any length and so we have proved that these sequences always end in the zero sequence or in cycles. 

 

You will no doubt have noticed that all sequences of length 2 and 4 seem to end with the zero sequence and all non-constant sequences of length 3 end in cycles and you may have conjectured that there is a significant difference for sequences of odd and even length. This is not so as you will have discovered if you tried sequences of length 6. If you pursued the investigation far enough you may have noticed the result in the theorem below for which we give a proof that uses nothing more than school mathematics.

Let $(a_1,\ldots,a_n)$ be a sequence of integers, and let $\theta$ be the operation $$\theta: (a_1,\ldots,a_n) \mapsto (|a_1-a_2|,\ldots,|a_{n-1}-a_n|, |a_n-a_1|).$$ Throughout we write $\mathbf{a} = (a_1,\ldots,a_n)$, and so on, and $\mathbf{0}=(0,\ldots,0)$. Clearly, we need only consider sequences with non-negative elements (since this will be so after just one application of $\theta$), so all sequences in this discussion will be assumed to have non-negative integral elements. For a positive integer $q$, $\theta^q$ denotes the $q$-th iterate of $\theta$. 

First, suppose that $\theta(\mathbf{a}) =\mathbf{b}$. We show that  $\mathbf{a}$ is a constant sequence if and only if $\mathbf{b}$ is the zero sequence. Clearly if  $\mathbf{a}$ is a constant sequence then $\mathbf{b}$ is the zero sequence. Now suppose that $\mathbf{b}$ is the zero sequence so we have $|a_j - a_{j+1}|= b_j = 0$ for all $j$. Thus $a_1 = a_2 = ... = a_n$ so that  $\mathbf{a}$ is a constant sequence.  Can $\mathbf{b}$ be a constant sequence without being the zero sequence? Now if $n$ is even and $\theta(\mathbf{a}) =\mathbf{b}$ it is possible for $\mathbf{b}$ to be a constant non-zero sequence, for example if  $\mathbf{a} =(1,2)$ then $\mathbf{b}= (1,1)$.  However if $n$ is odd, this is not possible as we show below.     

 

Theorem Every sequence $(a_1,\ldots,a_n)$ eventually maps to $(0,\ldots,0)$ under repeated applications of $\theta$ if and only if $n=1, 2, 4, 8, 16 ... $, that is $n=2^m$ for some integer $m$.

 

We divide our proof into three cases: (i) $n$ is odd, (ii) $n$ has an odd factor, and (iii) $n=2^m$ for some $m$.

Section (i) $n$ is odd 

We suppose that $n$ is odd. Suppose $\theta(\mathbf{a})$ is constant, say $(b,b,\ldots,b)$. Then, for $j=1,\ldots,n$, we have $|a_j-a_{j+1}|=b$ (where we put $a_{n+1}=a_1$). Thus we can write $a_j-a_{j+1} = \varepsilon_jb$, where $\varepsilon_j = \pm 1$, and $b(\varepsilon_1+\cdots +\varepsilon_n)=0$. Since the sum of the $\varepsilon_j$ cannot be zero (because $n$ is odd), we see that $b=0$. Thus $\theta(\mathbf{a})=\mathbf{0}$. Hence, from above, $\mathbf{a}$ is constant. These facts show that only constant sequences map to constant sequences under $\theta$ or, equivalently, that non-constant sequences map to non-constant sequences. Thus if $n$ is odd, and if we start with a sequence that is not constant, then it will never reach $\mathbf{0}$.  

Section (ii) $n$ has an odd factor   

We shall give the argument for $n=6$ (which has $3$ as an odd factor), and this clearly generalises to any $n$ with an odd factor. We know from Section (i) for any non-constant sequence $(a_1,a_2,a_3)$ we have $\theta^p(a_1,a_2,a_3) \neq (0,0,0)$ for any integer $p$. Now if $\theta^p(a_1,a_2,a_3) = (b_1,b_2,b_3)$, then $$\theta^p(a_1,a_2,a_3,a_1,a_2,a_3) = (b_1,b_2,b_3,b_1,b_2,b_3),$$ and it follows from this that $\theta^p(a_1,a_2,a_3,a_1,a_2,a_3) \neq (0,0,0,0,0,0)$ for any $p$. In general, if $n$ has an odd factor then there is a sequence $\mathbf{a}$ which will never reach $\mathbf{0}$. We have now shown that if all sequences eventually reach $\mathbf{0}$, then $n$ cannot have an odd factor, so that $n=2^m$ for some $m$.   

Section (iii) $n$ is a power of $2$ 

We now assume that $n=2^m$. Our proof uses the following lemma.

Lemma For any starting sequence $\mathbf{a}$, $\theta^n(\mathbf{a})$ has even components.

Let us assume this lemma for the moment, and show how it enables us to complete the proof of the theorem. Take any $\mathbf{a}$ and choose an integer $p$ such that each component of $\mathbf{a}$ is strictly less than $2^p$. Now, by our Lemma, we can write $\theta^n(\mathbf{a}) = 2\mathbf{a}_1$, where $\mathbf{a}_1$ is some sequence. In the same way, we can write $\theta^n(\mathbf{a_1}) = 2\mathbf{a}_2$, and so on, until we reach $\theta^n(\mathbf{a}_{p-1}) = 2\mathbf{a}_p$. It is now clear that $ \theta^{np}(\mathbf{a}) = 2^p\mathbf{a}_p. $ Now, for any $\mathbf{x}$, the maximum component of $\theta(\mathbf{x})$ is at most the maximum component of $\mathbf{x}$. Because the maximum component of $\theta^{np}(\mathbf{a})$ is strictly less than $2^p$, we must have $\mathbf{a}^p = \mathbf{0}$; thus $\theta^{np}(\mathbf{a}) =\mathbf{0}$ and so if the lemma holds we have proved the theorem.

It remains to prove the lemma and we do this by considering a function $\rho$ that is closely related to $\theta$. The function $\rho$ acts on infinite sequences of non-negative integers as follows: $$\rho(a_1,a_2,a_3,\ldots) = (|a_1-a_2|,|a_2-a_3|, |a_3-a_4|,\ldots).$$

Notice that the action of $\theta$ on sequences of length $n$ can be obtained from $\rho$ by taking the sequence $(a_1,a_2,\ldots)$ to be periodic of period $n$ so this proof works for all values of $n$. Now $$\rho^2(a_1,a_2,a_3,\ldots) = (\big||a_1-a_2|-|a_2-a_3|\big|,\ldots).$$ The key observation now is that if $q$ is an integer then $q$ and $|q|$ have the same parity (both odd or both even). Thus $\big||a_1-a_2|-|a_2-a_3|\big|$ has the same parity as $a_1-2a_2+a_3$, which has the same parity as $a_1+a_3$. If we now use the notation $(a_1,a_2,\ldots)\sim (b_1,b_2,\ldots)$ to mean that $a_j$ and $b_j$ have the same parity for all $j$, then we see that $$\rho^2(a_1,a_2,a_3,\ldots) \sim (a_1+a_3,a_2+a_4,a_3+a_5,\ldots).$$ If we now apply $\rho^2$ to the sequence on the right we find that $$\rho^4(a_1,a_2,a_3,\ldots) \sim (a_1+a_5,a_2+a_6,a_3+a_7,a_4+a_8,a_5+a_9,\ldots).$$ Next, we apply $\rho^4$ to the sequence on the right: this gives $$\rho^8(a_1,a_2,a_3,\ldots) \sim (a_1+a_9,a_2+a_{10},\ldots).$$ Quite generally, this shows that $$\rho^{2^p}(a_1,a_2,a_3,\ldots) \sim (a_1+a_{1+2^p},a_2+a_{2+2^p},a_3+a_{3+2^p},\ldots).$$ Now suppose that the original sequence $(a_1,a_2,\ldots)$ is periodic with period $2^m$. Then $a_j=a_{j+2^m}$ for all $j$, so that $$\rho^{2^m}(a_1,a_2,a_3,\ldots) \sim (2a_1,2a_2,2a_3,\ldots)\sim (0,0,0,\ldots).$$ Clearly this implies that $\theta^{2^m}(a_1,\ldots,a_{2^m})$ has all components even, and the lemma (and hence the theorem) is proved. 

 

References  

(1) Ciamberlini, C. and Maregoni, A., Su una interessante curiosit\`a numerica, {\sl Period. Mat. Ser. 4} 17 (1937), 25-30.

 

(2) Honsberger, R., {\sl Ingenuity in Mathematics}, Random House, New York, 1970.

 

(3) Lotan, M., A problem in difference sets, {\sl Amer. Math. Monthly} 56 (1949), 535-541.

 

(4) Miller, R., A game with $n$ numbers, {\sl Amer. Math. Monthly} 85 (1978), 183-185.

 

(5) Zvengrowski, P., Iterated absolute differences, {\sl Math. Mag.} 52 (1979), 36-37.