Ducci sequence

A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers (a₁,a₂,...,a_n), the next n-tuple in the sequence is formed by taking the absolute differences of neighbouring integers:

$(a_1,a_2,...,a_n) \rightarrow (|a_1-a_2|, |a_2-a_3|, ..., |a_n-a_1|)\, .$

Another way of describing this is as follows. Arrange n integers in a circle and make a new circle by taking the difference between neighbours, ignoring any minus signs; then repeat the operation. Ducci sequences are named after Enrico Ducci, the Italian mathematician credited with their discovery.

Ducci sequences are also known as the Ducci map or the n-number game. Open problems in the study of these maps still remain.^[1]

Properties

From the second n-tuple onwards, it is clear that every integer in each n-tuple in a Ducci sequence is greater than or equal to 0 and is less than or equal to the difference between the maximum and mimimum members of the first n-tuple. As there are only a finite number of possible n-tuples with these constraints, the sequence of n-tuples must sooner or later repeat itself. Every Ducci sequence therefore eventually becomes periodic.

If n is a power of 2 every Ducci sequence eventually reaches the n-tuple (0,0,...,0) in a finite number of steps.^{[1] [2] [3]}

If n is not a power of two, a Ducci sequence will either eventually reach an n-tuple of zeros or will settle into a periodic loop of 'binary' n-tuples; that is, n-tuples which contain only two different digits.

An obvious generalisation of Ducci sequences is to allow the members of the n-tuples to be any real numbers rather than just integers. The properties presented here do not always hold for these generalisations. For example, a Ducci sequence starting with the n-tuple (1, q, q², q³) where q is the (irrational) positive root of the cubic x³ − x² − x − 1 = 0 does not reach (0,0,0,0) in a finite number of steps, although in the limit it converges to (0,0,0,0).^[4]

Examples

Ducci sequences may be arbitrarily long before they reach a tuple of zeros or a periodic loop. The 4-tuple sequence starting with (0, 653, 1854, 4063) takes 24 iterations to reach the zeros tuple.

$(0, 653, 1854, 4063) \rightarrow (653, 1201, 2209, 4063) \rightarrow (548, 1008, 1854, 3410) \rightarrow$ $\cdots \rightarrow (0, 0, 128, 128) \rightarrow (0, 128, 0, 128) \rightarrow (128, 128, 128, 128) \rightarrow (0, 0, 0, 0)$

This 5-tuple sequence enters a period 15 binary 'loop' after 7 iterations.

$\begin{matrix} 1 5 7 9 9 \rightarrow & 4 2 2 0 8 \rightarrow & 2 0 2 8 4 \rightarrow & 2 2 6 4 2 \rightarrow & 0 4 2 2 0 \rightarrow & 4 2 0 2 0 \rightarrow \\ 2 2 2 2 4 \rightarrow & 0 0 0 2 2 \rightarrow & 0 0 2 0 2 \rightarrow & 0 2 2 2 2 \rightarrow & 2 0 0 0 2 \rightarrow & 2 0 0 2 0 \rightarrow \\ 2 0 2 2 2 \rightarrow & 2 2 0 0 0 \rightarrow & 0 2 0 0 2 \rightarrow & 2 2 0 2 2 \rightarrow & 0 2 2 0 0 \rightarrow & 2 0 2 0 0 \rightarrow \\ 2 2 2 0 2 \rightarrow & 0 0 2 2 0 \rightarrow & 0 2 0 2 0 \rightarrow & 2 2 2 2 0 \rightarrow & 0 0 0 2 2 \rightarrow & \cdots \quad \quad \\ \end{matrix}$

The following 6-tuple sequence shows that sequences of tuples whose length is not a power of two may still reach a tuple of zeros:

$\begin{matrix} 1 2 1 2 1 0 \rightarrow & 1 1 1 1 1 1 \rightarrow & 0 0 0 0 0 0 \\ \end{matrix}$

Modulo two form

When the Ducci sequences enter binary loops, it is possible to treat the sequence in modulo two. That is^[5]:

$(|a_1-a_2|, |a_2-a_3|, ..., |a_n-a_1|)\ = (a_1+a_2, a_2+a_3, ..., a_n + a_1)\ mod 2$

This forms the basis for proving when the sequence vanish to all zeros.

Cellular automata

The linear map in modulo 2 can further be identified as the cellular automata denoted as rule 102 in Wolfram code and related to rule 90 through the Martin-Odlyzko-Wolfram map.^[6][7] Rule 102 reproduces the Sierpinski triangle.^[8]

Other related topics

The Ducci map is an example of a difference equation, a category that also include non-linear dynamics, chaos theory and numerical analysis. Similarities to cyclotomic polynomials have also been pointed out.^[9] While there are no practical applications of the Ducci map at present, its connection to the highly applied field of difference equations led ^[4] to conjecture that a form of the Ducci map may also find application in the future.

References

1. ^ ^{a b} Chamberland, Marc; Thomas, Diana M. (2004). "The N-Number Ducci Game". Journal of Difference Equations and Applications (London: Taylor & Francis) 10 (3): 33–36. http://www.math.grinnell.edu/~chamberl/papers/ducci_survey.pdf. Retrieved 2009-01-26. 
2. ^ Chamberland, Marc (2003). "Unbounded Ducci sequences". Journal of Difference Equations and Applications (London: Taylor & Francis) 9 (10): 887–895. doi:10.1080/1023619021000041424. http://www.math.grinnell.edu/~chamberl/papers/ducci_unbounded.pdf. Retrieved 2009-01-26. 
3. ^ Andriychenko, Oleksiy; Chamberland, Marc (2000). "Iterated Strings and Cellular Automata". The Mathematical Intelligencer (New York, NY: Springer Verlag) 22 (4): 33–36. doi:10.1007/BF03026764. 
4. ^ ^{a b} Brockman, Greg (2007). "Asymptotic behaviour of certain Ducci sequences". Fibonacci Quarterly. http://www.cut-the-knot.org/Curriculum/Algebra/GregBrockman/GregBrockmanDucciSequencesPaper.pdf. 
5. ^ Florian Breuer, "Ducci sequences in higher dimensions" in INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007) [1]
6. ^ S Lettieri, JG Stevens, DM Thomas, "Characteristic and minimal polynomials of linear cellular automata" in Rocky Mountain J. Math, 2006.
7. ^ M Misiurewicz, JG Stevens, DM Thomas, "Iterations of linear maps over finite fields", Linear Algebra and Its Applications, 2006
8. ^ Weisstein, Eric W. "Rule 102." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Rule102.html
9. ^ F. Breuer et al. 'Ducci-sequences and cyclotomic polynomials' in Finite Fields and Their Applications 13 (2007) 293–304

External links

• Ducci Sequence
• Integer Iterations on a Circle at Cut-the-Knot