In solving a puzzle related to linear algebra over $\mathbb{Z}/2\mathbb{Z}$, I came across the function $\varphi:\mathbb{Z}^n\rightarrow \mathbb{Z}^n$ given by $$(x_1, x_2, \dots, x_n)\mapsto(|x_1-x_n|, |x_2-x_1|, |x_3-x_2|, \dots, |x_n-x_{n-1}|)$$ I have solved most of my puzzle, but I am stuck on proving the following.
Claim: For any input $(x_1, x_2, \dots, x_n)$ such that
- Each $x_j$ is non-negative
- There are at least two distinct positive entries in our input. So for example, my claim applies to $(7,1,0)$ but not $(1,1,0)$. $$\max_i\varphi^n(x)_i<\max_ix_i$$ In other words, the largest entry of my vector after I apply $\varphi$ consecutively $n$ times will be strictly less than the maximum entry of the input vector.
Observations & Progress
- I can prove this claim when $n$ is a power of $2$, but I have checked it for many inputs with $n$ up to 10, and I really want a clean proof of this claim that handles all cases at once.
- Using usual inequality business, we can see that $\max_i\varphi(x)_i\leq\max_ix_i$
- If we have a single maximum entry $x_j$ next to two entries strictly between $0$ and $x_j$ then we can check that the claim holds
- Intuitively, even when we are not in the above case, applying $\varphi$ $n$ times will shift us into the previous case
Any help formalizing my above reasoning to handle the various edge cases or suggesting some sort of invariant would be greatly appreciated.