Ducci sequences – Part one – Cogito, ergo math

In previous post we explained what Ducci sequences are. In this article we will prove several properties.

First of all let’s do some exploration and try several things. We will be interested in long term behaviour. For that define Ducci map $D: \mathbb Z^n \rightarrow \mathbb Z^n$ as $D(v) = (∣v_1-v_2∣,∣v_2-v_3∣,…,∣v_n-v_1∣)$ . Now what will happen if we will use $D$ repeatedly?

If $v$ is zero vector, it is simple, $D^k(v) = (0, 0,..., 0)$ for any $k$ . If we take only one non zero component, we get for example this $D^2((1,0)) = D((1, 1)) = (0,0)$ . Do we always get zero vector? No, for example $D^4((1, 0, 0)) = D^3((1, 0, 1)) = D^2((1, 1, 0)) = D((0, 1, 1)) = (1, 0, 1)$ and we get a cycle (starting with $(1, 0, 1)$ ).

What if we try some more complicated vector, like $(3, 5, 2)$ . Then we get by repeated applying of Ducci map -> $(2, 3, 1) \rightarrow (1, 2, 1) \rightarrow (1, 1, 0)$ . Again, we got just binary vector! Does that happen always?

Unfortunately no, for example

$(10, 20, 30) \rightarrow (10, 10, 20) \rightarrow (0, 10, 10) \rightarrow (10, 0, 10) \rightarrow (10, 10, 0) \rightarrow (0, 10, 10)$

and we obtain a cycle. But notice that everything in the cycle is scalar multiple of binary vector! So our first hypothesis would be that after some time we get a binary vector or its multiple.

We will use two theorems to prove it.

Theorem 1: Let $v$ be vector with integer components $v = (v_1, v_2,..., v_n)$ and let weight be maximum of these components, ie. $w = max\{v_1, v_2, ..., v_n\}$ . Then applying Ducci operation cannot increase this weight.

Proof of Theorem 1. Let $w$ be weight of some vector $(v_1, ..., v_n)$ . After applying Ducci once, we get another vector $(|v_1-v_2|, ..., |v_n-v_1|$ . But we know that $|v_i - v_j| \leq max(v_i, v_j)$ , from which the conclusion follows. QED

Now we know that weight is not increasing. In order to prove our claim about having binary vector, we have to think about non binary vectors which are not multiples of binary vectors. If we look for example at $(5, 0, 2)$ , there are two possibilities that can come to your mind. If the weight does not decrease, all entries will have to be zero and one of them will have to be $5$ . Second thought is that weight always decreases for vectors like these. This thought is the right one.

Theorem 2:
Let $n \geq 2$ be an integer, and let $v=(v_1,v_2,…,v_n)$ be a vector with integer components and weight m, which is not binary nor scalar multiple of it. After finitely many iterations of $D$ , the weight decreases; that is, $W(D^k(v))<m$ for some $k \geq 1$ .

Proof of Theorem 2. The main idea behind this proof is that either the weight decreases or the maximum number of zeroes after maximum decreases. Because both can happen finitely many times, it proves our theorem.
To be more specific, if you have non zero number right after maximum, this entry decreases in the very next step. If not, then there are several zeroes next to it, so it looks like this $(b, m, 0,..., 0, c)$ , where $b$ is any number $\leq m$ , $m$ is maximum and $c$ is any number $\leq m$ . Look at the number of zeroes next to $m$ – after this many steps plus one the $m$ decreases by $c$ .

The problem of course is – what if after $m$ decreases, another entry increased to $m$ ? For example if you begin by $(0, 10, 2, 0)$ , you get to $(2, 6, 2, 10)$ . But it is not problematic, since the number of zeroes decreases in a vector that is not binary nor multiple of binary vector.

So because of these facts, we can work only with binary vectors since we know we would always get to them after finitely many steps or to multiples of them, but they behave exactly the same.

Leave a Reply Cancel reply