Kerodon

Proof. Let $S$ denote the collection of all elementary dyadic contractions. We verify that $S$ satisfies conditions $(1)$ through $(4)$ of Definition 6.2.5.4:

$(1)$

For every integer $n \geq 0$, the identity morphism $\operatorname{id}: [0,n] \xrightarrow {\sim } [0,n]$ is an elementary dyadic contraction. This is immediately from the definitions.

$(2)$

Suppose we are given a commutative diagram of dyadic contractions

\[ \xymatrix@R =50pt@C=50pt{ & [0,m] \ar [dr]^{g} & \\[0,k] \ar [ur]^{ f } \ar [rr]^{h} & & [0,n]. } \]

Assume that $g$ and $h$ are elementary; we wish to show that $f$ is also elementary (in fact, the assumption that $g$ is elementary will not be needed). Choose a point $x \in [0,k]$ at which $f$ is differentiable; we wish to show that $f'(x) \geq 1/2$ (see Remark 8.5.9.17). Replacing $x$ by a nearby point if necessary, we may assume that $g$ is differentiable at the point $y = f(x)$. Since $g$ is a dyadic contraction and $h$ is an elementary dyadic contraction, we have $g'(y) \leq 1$ and $h'(x) \geq 1/2$. Applying the chain rule, we obtain inequalities $f'(x) \geq f'(x) \cdot g'(y) = h'(x) \geq 1/2$.

$(3)$

Let $f: [0,m] \xrightarrow {\sim } [0,n]$ be a dyadic contraction. We wish to show that $f$ admits an $S$-optimal factorization (in the sense of Definition 6.2.5.1). Let $P$ denote the collection of all subsets $\{ 1, 2, \cdots , n \} $ having the property that the composition $(b_ J \circ f): [0,m] \rightarrow [0, n+|J|]$ is a dyadic contraction; here $b_ J$ denotes the dyadic homeomorphism introduced in Notation 8.5.9.16. Unwinding the definitions, we can identify $P$ with the set of factorizations $f = s \circ g$, where $g$ is a dyadic contraction and $s$ is an elementary dyadic contraction (the identification carries a set $J \in P$ to the pair $(s,g) = ( b_{J}^{-1}, b_{J} \circ f)$). Under this identification, a factorization $f = s \circ g$ is $S$-optimal if and only if $J$ is a largest element of $P$. We conclude by observing that $P$ has a largest element $J_{\mathrm{max}}$, given by the collection of those integers $j \in \{ 1,2, \cdots , n \} $ having the property that the inverse homeomorphism $f^{-1}$ has derivative $\geq 2$ at every point $x \in [j-1,j]$ where $f^{-1}$ is differentiable (alternatively, $J_{\mathrm{max}}$ can be described as the set of integers $1 \leq j \leq n$ which satisfy $f^{-1}(j) > f^{-1}( j-1) + 1$).

$(4)$

Let $f: [0,m] \rightarrow {\sim } [0,n]$ be a dyadic contraction. Let us define the length of $f$ to be the smallest nonnegative integer $k$ such that $f'(x) \geq 1/2^ k$ for every point $x \in [0,m]$ where $f$ is differentiable. We claim that, if this condition is satisfied, then $f$ can be written as a composition $s_1 \circ s_2 \circ \cdots \circ s_ k$, where each $s_ i$ is an elementary dyadic contraction. Our proof proceeds by induction on $k$. If $k = 0$, then $f$ is an identity morphism and there is nothing to prove. Let us therefore assume that $k > 0$, and let $f = s_1 \circ g$ be an $S$-optimal factorization of $f$. We claim that $g$ can be written as a composition of elementary contractions $s_2 \circ \cdots \circ s_ k$. By virtue of our inductive hypothesis, it will suffice to show that $g$ has length $k-1$, which follows from the proof of $(3)$.