Prov that function is eventually periodic to origin.

Question

Let $f:\mathbb{Z}^4 \rightarrow \mathbb{Z}^4$ by

$f(w,x,y,z) = (\mid w-x \mid,\mid x-y \mid,\mid y-z \mid,\mid z-w \mid)$

1. Prove that for any $(w,x,y,z) \in \mathbb{Z}^4$ there is $n>0$ such that $f^n(w,x,y,z)=(0,0,0,0)$
2. Prove that there is no $n$ such that $f^n(w,x,y,z)=(0,0,0,0)$ for all $(w,x,y,z) \in \mathbb{Z}^4$

---

I wrote a computer code in R that can execute this function for any integers $w,x,y,z$ and $n$. See below:

rm(list = ls())  
myfun=function(w,x,y,z){  
outcome <- c(abs(w-x), abs(x-y), abs(y-z),abs(z-w))  
return(outcome)  
}  
w<-1  
x<-3  
y<-534  
z<-3  
n=6  

outcome <- matrix (nrow=n, ncol=4)  
for (i in 1:n){  
outcome[i,] <- myfun(w,x,y,z)  
w <- outcome[i,1]  
x <- outcome[i,2]  
y <- outcome[i,3]  
z <- outcome[i,4]  
}  
outcome  

---

After executing 100's of points I see that after, $n=5$ we see the function going to $(0,0,0,0)$. I tried using brute force and applied the function 6 times by hand to see if it cancels out but I've end up with a very complex function. There must be a cleaner way of proving this question. Point me in the right direction please.

Answer 1

1. Let us show that $f^n(v)\to 0$, $n\to\infty$, for any $v=(a,b,c,d)\in \mathbb{R}^4$. It is enough to consider non-negative vectors. It is clear that $f$ does not increase the maximum of the numbers, which we denote by $||v||$. Therefore, there exists the limit $\lim_{n\to\infty} ||f^n(v)||$. In particular, the sequence $\{f^n(v),n\ge 1\}$ has a limit point, say, $v_0$.

Clearly, $||f^m(v_0)|| = ||v_0||$ for any $m\ge 0$. Also, extracting a convergent subsequence for preimages of elements converging to $v_0$, $v_0 = f(u_0)$.

Assume that $v_0\neq 0$. Let $a>0$ be the maximal coordinate of $f(v_0)$, wlog the first. Then $v_0$ has either the form $(a,0,*,*)$ or $(0,a,*,*)$. Moreover, the sum of the remaining coordinates must be $a$ due to the fact that $v_0 = f(u_0)$.

Case a Both remaining coordinates are less that $a$ (and therefore positive). Then we have either (here $c$ means any number less then $a$) $$(a,0,c,c)\to (a,c,c,c) \to (c,c,c,c),$$ or $$(0,a,c,c)\to (a,c,c,c) \to (c,c,c,c),$$ which contradicts to $||f^m(v_0)|| = ||v_0||$.

Case b One of the remaining coordinates is $a$ (and the other is zero). Then we have essentially two possibilities $$ (a,0,a,0)\to (a,a,a,a)\to (0,0,0,0), $$ and $$ (0,a,a,0)\to (a,0,a,0)\to (a,a,a,a)\to (0,0,0,0), $$ both contradicting the assumption.

Therefore, $v_0=0$, hence, $\lim_{n\to\infty} f^n(v) = 0$, as claimed.

2. First we prove this for real numbers. Notice that the polynomial $(x-1)(x+1)^3+1$ has a positive root $\lambda \approx 0.83929$. Set $(t,u,v,w) = (1,1+\lambda,(1+\lambda)^2,(1+\lambda)^3)$. Then $$f(t,u,v,w) = (\lambda,\lambda(1+\lambda),\lambda(1+\lambda)^2,(1+\lambda)^3-1)\\ = (\lambda,\lambda(1+\lambda),\lambda(1+\lambda)^2,\lambda(1+\lambda)^3)=\lambda\cdot (t,u,v,w).$$ (I'll not write the vector here, since $\lambda$ is a cumbersome root of a cubic equation, and $(t,u,v,w)$ is even more cumbersome; the numerical values are $(t,u,v,w)\approx (1, 1.8393, 3.383, 6.2223)$.) Therefore, for any $n\ge 1$ $f^n(t,u,v,w) = \lambda^n\cdot (t,u,v,w)\neq 0$.

Now by way of contradiction assume that there exists $n\ge 1$ such that $f^n(a,b,c,d) = 0$ for any integer $a,b,c,d$. Then, obviously, $f^n(a,b,c,d) = 0$ for any rational $a,b,c,d$. In view of continuity, $f^n(a,b,c,d) = 0$ for any real $a,b,c,d$, which contradicts the previous paragraph.

---

This proof also gives a way to construct integer quadruples leading to arbitrarily long iteration sequences: one just needs to multiply $(t,u,v,w)$ by a large number and take integer parts. Say, the approximate values $(10000,18393,33830,62223)$ lead to a $24$-step iteration sequence.

---

The application of this method for triples (perhaps, unsurprisingly) leads to funny example of long iteration triples: $(F_{n-2},F_{n-1},F_n)$, where $F_n$ is the $n$th Fibonacci number.

Answer 2

$\bf{First\ part}$. We prove the statement given by Paul Sinclair in a comment:

The max element never grows (other then the first time when the arguments can be negative) and it decreases after at most 4 applications, if you start at a non-zero quadruple.

1. We assume that $f:\Bbb{N}_0^4\to \Bbb{N}_0^4$.

2. Then clearly $Max(f(V))\le Max(V)$ for all $V$.

3. If $Max(f(V))= Max(V)$, for some $V\ne 0$, then one of the entries of $V$ is $0$ and it is adjacent to the maximal value $m$ (note that we consider the first entry adjacent to the fourth, due to invariance under rotation).

4. Consequently, if all values of $V$ are different to its adjacent values, then none of the entries of $f(V)$ is zero, hence $Max(f(f(V)))< Max(f(V))\le Max(V)$.

Now start with a $0\ne V\in \Bbb{N}_0^4$, and we have to prove that $Max(f^k(V))<Max(V)$ for some $k\in\{1,2,3,4\}$.

If $Max(f(V))<Max(V)$, there is nothing to prove.

Else we can assume by 3. that $V=(m,0,a,b)$ with $0\le a,b\le m$.

If $0\ne a$, $a\ne b$ and $b\ne m$, then by 4. we have $Max(f(f(V)))<Max(V)$ and we are done.

Hence we have to consider the three cases $$ V=(m,0,0,b),\quad V=(m,0,a,a)\quad\text{and}\quad V=(m,0,a,m). $$ In the first case, if $b=0$, then $f^4(V)=(0,0,0,0)$; if $b=m$ or $b=m/2$, then $f^3(V)=(0,0,0,0)$ and if $b\ne 0,m/2,m$, then all elements of $f(V)$ are different, hence by 4. we have $Max(f(f(f(V))))<Max(V)$.

In the second case, if $a=m$ or $a=0$, then $f^4(V)=(0,0,0,0)$, and else all entries of $f(V)$ are different from the adjacent entries, hence by 4. we have $Max(f(f(f(V))))<Max(V)$.

In the third case, if $a=0$, then $f^3(V)=(0,0,0,0)$; if $a=m$ or $a=m/2$, then $f^4(V)=(0,0,0,0)$ and if $a\ne 0,m/2,m$, then all elements of $f(V)$ are different, hence, by 4., $Max(f(f(f(V))))<Max(V)$.

This proves the assertion. Note that for $V=(m,0,0,0)$ we have $Max(f^3(V))=m=Max(V)$. Hence, if you start with any quadruple in $\Bbb{N}_0^4$ with $Max(V)=m$, after at most $4m$ steps it goes to zero, i.e., $f^{4m}(V)=(0,0,0,0)$.

${\bf{Conclusion\ of\ the\ first\ part:}}$ If you start with $(x,y,z,t)\in \Bbb Z^4$, then $V=f((x,y,z,t))\in \Bbb N_0^4$, hence $f^n(x,y,z,t)=0$ for $n=4 Max(V)+1$.

$\bf{Second\ part}$. If a quadruple $V=(v_1,v_2,v_3,v_4)$ satisfies $v_1\le v_3$ and $\Delta:=v_4−(v_1+v_2+v_3)\ge 0$, then the cuadruple $C:=(0,2v_1+\Delta,2v_4−2v_3,2v_4+\Delta)$ satisfies $f(f(C))=2f(V)$, and also $c_1\le c_3$ and $c_4−(c_1+c_2+c_3)\ge 0$.

If $\Delta$ is even, then we can take $\overline C:=\frac 12 (0,2v_1+\Delta,2v_4−2v_3,2v_4+\Delta)$, and then $f(f(\overline C))=f(V)$.

Starting from any $V=(v_1,v_2,v_3,v_4)$ satisfying $v_1\le v_3$ and $\Delta:=v_4−(v_1+v_2+v_3)\ge 0$, such that $V$ needs $n$ steps to go to zero ($f^n(V)=(0,0,0,0)$ and $f^{n-1}(V)\ne (0,0,0,0)$), we can construct (iterating the construction above) an infinite family $V_k$ with $V_0=V$ and $V_1=C$ (or $V_1=\overline C$), such that $V_k$ needs $n+k$ steps to go to zero. This proves the second part.

For example, we can consider $V_0=V=(0,0,1,2)$, which needs four steps to go to zero. Then $V_3=(0,1,3,7)$ needs seven steps to go to zero.

If we set $V=V_0=(0,0,0,1)$, then $V_3=(0,1,2,4)$ needs 7 steps and $V_{11}=(0,20,57,125)$ needs 15 steps.

${\bf{Edit:}}$ Via OEIS on the last entry of the last example ($V_0=(0,0,0,1)$) I found that the problem is solved completely in http://www.maa.org/sites/default/files/pdf/pubs/AMM-May05_Boxes.pdf

There they found $(0,1,q^2-q,q)$ as a fixpoint of the operation on certain equivalence classes, with $q^3-q^2-q-1=0$, which is related to the $\lambda$ in the answer of zhoraster via $q=\lambda+1$.