Ducci Sequences

By Greg Brockman

Some Background

This applet demonstrates the behavior of arbitrary vector-length Ducci sequences over the real numbers. (For the case of integers, see Integer Iterations on a Circle.) So just what does that mean? Well, first of all, we start with any list of n numbers, or a vector of length n. Next, we build a new vector by replacing each number by the absolute value of the difference between it and its neighbor to the right (we think about these vectors as being cyclic). We can repeat this process, and the sequence of vectors thus obtained is called a Ducci sequence.

More formally, let f: Rⁿ → Rⁿ be defined by

f(ν₁, ..., ν_n) = (|ν₁ - ν₂|, |ν₂ - ν₃|, ..., |ν_n - ν₁|).

Then the Ducci sequence of an n-vector ν is defined as {fⁱ(ν)}, where i = 1, 2, 3, ... (fⁱ is the iterated f. For example, f²(ν) = f(f(ν)).)

Now, since when generating successive elements in a Ducci sequence, we wrap a vector as if cyclic, it can be helpful to think of a vector in a Ducci sequence as simply some numbers arranged around a circle. I have taken this approach in this applet.

Instructions

So here's how to run the applet: First of all, click "Add Circle" to begin. There are now two modes: Edit and Run. By default, you start out in Edit mode.

Options for Edit Mode

Add Slot (green button): Each new circle you add corresponds to increasing the length of the corresponding vector by 1.
You can select a given circle by clicking on it. If it's already selected, then nothing happens.
To add a value to the selected circle, enter values into the text boxes at the top. Values in the selected circle will automatically update, or you can press "Enter" if you wish.
You can remove the selected circle by pushing the "Del" key.
When ready, click "Play Ducci!" to enter Run mode.

Options for Run Mode

Next Step calculates the next vector in the Ducci sequence. If animation is enabled, then you get a cool movie effect.
The Automate button automatically runs Next Step multiple times.
If you want to skip to a certain generation number (for example, maybe you want to find the 507^th vector in the Ducci sequence under consideration), you can use the "See generation number" box. Just type in the number you want and press enter.
The buttons at top are fairly self-explanatory: Reset Values takes you back to the 0^th vector (the starting one); Edit Values switches you back to Edit Mode; and Create New Game completely deletes all information and starts you with a fresh vector.

Common Options

Toggling Display Exact/Show Approx. changes whether the exact values of numbers in circles are displayed or whether a decimal approximation is shown.

Hint
If you aren't sure what a button does, you can always hold your mouse over it and wait for the tooltip.

Note
The Ducci sequences are calculated using 300 digit precision on π, e, and √2. Thus, after about 1000 generations, your typical Ducci sequence incorrectly starts behaving like a homogeneous one (for the meaning of this term, see my paper) rather than a heterogeneous one. The program automatically shows a warning after 1000 generations.
The color of a circle indicates its magnitude relative to the maximum element in the current vector. This color is blue for the maximum element and becomes (linearly) darker as the element's magnitude shrinks.

Some Suggestions of What To Do

My paper discusses under what conditions Ducci sequences of odd length vectors start repeating. You can use the applet to examine the behavior of various Ducci sequences. What happens if you start out with an irrational, but then replace it by a good rational approximation to it? Can you get any non-repeating sequences that don't go to the zero vector (the answer to this question is actually unknown; such sequences exist in general, but the known ones cannot be built using the given input method)?

Some cool phenomena, connected with papers before mine, show up when you work with vectors of length 4. Can you find a vector that never actually hits the zero vector? If not, can you build any that take a long time to get there? (Spoiler—using the given input tools, you won't be able to build a vector that never actually hits the zero vector. But given sufficient cleverness, it's possible to built vectors that take arbitrarily long to get there.)

You should also take a look at the exact values, and see as they behave as you iterate. How quickly do the coefficients on the various numbers grow? Under what conditions must they grow without bound?

On the whole, there is an essentially unlimited spectrum of questions that one can ask. I recommend using this applet to get an intuition of how Ducci sequences over the real numbers behave.

About the Author

Greg Brockman is currently an undergraduate student at Harvard University. This paper was the result of a research project during his junior year of high school supervised by University of North Dakota math professor Dr. Ryan Zerr. Brockman received 6^th place in the Intel Science Talent Search Competition for his work on this project. You can contact him directly by emailing him at gregx007@yahoo.com.

71536897