Indecomposable contracting maps on the integers

Question

$\def\ZZ{\mathbb{Z}}$Call a function $f : \ZZ \to \ZZ$ "contracting" if $$|f(j) - f(i)| \leq |j-i|$$ for all $i$, $j \in \ZZ$. The contracting functions form a monoid under composition; call it $C$. An element of a monoid is called a "unit" if it is invertible; the units of $C$ are the functions $x \mapsto \pm x + k$. An element of a monoid is called ``irreducible" if it is not a unit and cannot be factored as the composition of two non-units.

Question 1: What are the irreducibles of $C$?

To give two nonobvious examples, the maps $x \mapsto |x|$ and $x \mapsto \begin{cases} x & x \geq 0 \\ x+1 & x < 0 \end{cases}$ are both irreducible.

The problem which I actually want the answer to is a slight variant of $C$: Define $C_2$ to be the monoid of maps $f : \ZZ \to \ZZ$ which are contracting and obey $f(i) \equiv i \bmod 2$. So what I would really like to know is:

Question 2: What are the irreducibles of $C_2$?

If you prefer finite monoids, I am fine with you working with $\{ 0,1,2,\ldots,n \}$ instead of $\ZZ$ for either question.

Answer 1

I'll solve question 2, on $C_2$.

I will prove the irreducibles are those that only have one or two bends, verifying a prediction of Nate (and disproving a prediction of myself).

Call a "run" a maximal interval on which $f$ is linear. Clearly $f$ is linear on $[a,b]$ if and only if we either have $f(i)=i+1$ for all $i= a,\dots, b-1$, or $f(i) = i-1$ for all $i= a,\dots, b-1$. Then $[a,\dots, b]$ is maximal if, in addition, we have $f(a-1) = f(a)+1$ and $f(b+1) =f(b-1)$ in the first case or $f(a-1)=f(a)-1$ and $f(b+1)=f(b-1)$ in the second case.

I'll show that if $f$ is irreducible and $f$ has a run then $f$ has exactly one run. The number of runs is the number of bends minus one, so this is equivalent to Nate's claim.

The length $b-a$ of a run is a nonnegative integer, so if there is any run, there is a run of minimal length. If $[a,a+k]$ is a run of minimal length, then $f$ must be linear on $[a-k,a]$ and $[a+k,a+2k]$ as otherwise these intervals would contain a shorter run (the longest linear subinterval touching $[a,a+k]$).

Assume wlog the run of minimal length is increasing. Then $f( a-i ) = f(a)+i = f(a+i)$ for $0\leq i \leq k$ and $f(a+k-i) =f(a+k)-i = f(a+k+i)$ for $0 \leq i \leq k$.

So if we let $g(n)$ be given by the rule that $g(n) = n $ for $n \leq a$, $g(n) = 2a-n$ for $a\leq n \leq a+k$, and $g(n) = n-2k$ for $n\geq a+k$, and $h(n) = f(n)$ for $n \leq a$ and $h(n) = f(n+2k)$ for $n \geq a$, then $f =g \circ g$.

So if $f$ is irreducible, since $h$ is certainly not invertible (we have $k\geq 1$ since runs have length at least $1$), $g$ must be invertible, i.e. translation or reflection. So $f$ has the same number of runs as $h$, i.e., one.

Answer 2

Too long for a comment, but not completely thought out:

Call a point $x$ a "bend" if $f(x-1) = f(x+1)$. I think if we restrict to the subclass of $C_2$ with finitely many bends then the only irreducible ones are those with $1$ or $2$ bends. Here is an idea for a proof:

If $f(x)$ has an odd number of bends then up to flipping sign it must have a global minimum $m$. If we take the right most $y$ point attaining that minimum. The claim is that we can write $f$ as a composition $g \circ f'$ where $g(x) = |x-y| - m$ and $f'$ is in $C_2$ with one fewer bend.

If $f(x)$ has an even number $2n$ of bends with $n > 1$ then the claim is that we can write it as a composition of $h \circ k$ with $k$ having just 2 bends and $h$ having $2n-2$ bends. The idea being that $k$ accounts for the leftmost pair of bends, and $h$ accounts for the rest, just shifted.