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

  • 2
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    May 20 at 19:22
  • 1
    $\begingroup$ @WillSawin You and Nate seem to have incompatible intuitions (compare his last paragraph to your comment). $\endgroup$ May 20 at 20:43
  • 2
    $\begingroup$ @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. $\endgroup$ May 21 at 13:30
  • 2
    $\begingroup$ 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 $\endgroup$ May 21 at 20:51
  • 1
    $\begingroup$ The buzzword for the finite case is contractions on a finite chain $\endgroup$ May 21 at 21:53

2 Answers 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.