# Indecomposable contracting maps on the integers

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

• Consider a function that increases linearly up to $-n$, then zigzags up and down irregulary between $-n$ and $n$ for much more than $n$ steps, then increases linearly to $\infty$. If we consider a "random" such function in some sense, it seems believable to me that the function is irreducible with high, but not quite $1$, probability. So there might not be a classification of irreducibles, any more than there is a classification of irreducible polynomials in two or more variables - they're just all the ones that don't happen to be reducible. May 20 at 19:22
• @WillSawin You and Nate seem to have incompatible intuitions (compare his last paragraph to your comment). May 20 at 20:43
• @DavidESpeyer, maybe this is no longer relevant. The papers on the finite case all seem to start from dergipark.org.tr/tr/download/article-file/435131. May 21 at 13:30
• In the finite case it seems that every noninvertible element is fixed by an nonidentity idempotent on the left so you should maybe replace irreducible by maximal in the J-order. This is proved in arxiv.org/pdf/1804.10057.pdf but note they with with the opposite semigroup because they act on the right May 21 at 20:51
• The buzzword for the finite case is contractions on a finite chain May 21 at 21:53

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.

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.