$\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.



Indecomposable contracting maps on the integers
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](https://mathoverflow.net/a/422987/18060) (and disproving a prediction of [myself)](https://mathoverflow.net/questions/422985/indecomposable-contracting-maps-on-the-integers/422994#comment1087029_422985).


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.


