Read-back: represents_word_exponents

0. What kind of statement this is

A single implication, universally quantified over two objects — a tree diagram $d$ and an order-automorphism $f$ of the unit interval — both of which are implicit arguments, so the statement is: for every $d$ and every $f$, if $f$ is represented by $d$ then a certain equation between elements of a group holds. There are no typeclass hypotheses and no other side conditions; every ingredient below is a concrete definition, not a parameter.

Everything the statement refers to has to be unfolded, so the whole of the setting is spelled out first, and the assertion itself appears in §8.

---

1. The ambient group $G$

Write

$$I \;=\; [0,1] \;=\; \{x \in \mathbb{R} \;:\; 0 \le x \le 1\},$$

regarded as a set of real numbers carrying the order it inherits from $\mathbb{R}$ (so $x \le y$ for elements of $I$ means exactly $x \le y$ in $\mathbb{R}$).

Let

$$G \;=\; \{\,\text{order isomorphisms } I \to I\,\}.$$

An element of $G$ is a bijection $I \to I$ together with the property that $u \le v$ if and only if the images satisfy the same inequality; equivalently, an increasing bijection of $[0,1]$ onto itself. Every such map necessarily fixes $0$ and $1$.

$G$ is a group. The group operations are, verbatim:

• the product $g \cdot h$ is the composite $g \circ h$, i.e. $(g\cdot h)(x) = g\bigl(h(x)\bigr)$: in a product, the rightmost factor is applied to the point first and the leftmost factor last;
• the identity element $1$ is the identity map of $I$;
• $g^{-1}$ is the inverse order isomorphism;
• for a natural number $c$, $g^{c}$ is the $c$-fold composite of $g$ with itself, with $g^{0} = 1$.

This convention matters for reading §3, §4 and §8, and it is the one used throughout.

2. The two distinguished elements $A$ and $B$ of $G$

$A \in G$ is the piecewise-linear increasing bijection of $[0,1]$ given by

$$A(z) \;=\; \begin{cases} \tfrac{1}{2} z, & 0 \le z \le \tfrac12,\\[2pt] z - \tfrac14, & \tfrac12 \le z \le \tfrac34,\\[2pt] 2z - 1, & \tfrac34 \le z \le 1. \end{cases}$$

(The three formulas agree at $z = \tfrac12$, where both give $\tfrac14$, and at $z = \tfrac34$, where both give $\tfrac12$; and $A(0)=0$, $A(1)=1$. So $A$ carries $[0,\tfrac12]$ onto $[0,\tfrac14]$, $[\tfrac12,\tfrac34]$ onto $[\tfrac14,\tfrac12]$, and $[\tfrac34,1]$ onto $[\tfrac12,1]$, with slopes $\tfrac12, 1, 2$.)

$B \in G$ is the piecewise-linear increasing bijection of $[0,1]$ given by

$$B(z) \;=\; \begin{cases} z, & 0 \le z \le \tfrac12,\\[2pt] \tfrac12 z + \tfrac14, & \tfrac12 \le z \le \tfrac34,\\[2pt] z - \tfrac18, & \tfrac34 \le z \le \tfrac78,\\[2pt] 2z - 1, & \tfrac78 \le z \le 1. \end{cases}$$

(Again the formulas agree at the breakpoints: $B(\tfrac12) = \tfrac12$, $B(\tfrac34) = \tfrac58$, $B(\tfrac78) = \tfrac34$, $B(1) = 1$. So $B$ is the identity on $[0,\tfrac12]$ and is a copy of $A$ rescaled to $[\tfrac12,1]$.)

Both are defined in the source by first writing down an increasing bijection of the whole real line that is the identity outside $[0,1]$ and then restricting it to $[0,1]$; the displayed formulas are the restrictions.

3. The family of generators $X_n$, $n \in \mathbb{N}$

An element $X_n \in G$ is defined for every natural number $n \ge 0$ by

$$X_0 = A, \qquad X_{n+1} \;=\; \bigl(A^{\,n}\bigr)^{-1}\cdot B \cdot A^{\,n} \;=\; A^{-n} B A^{\,n} \quad (n \ge 0).$$

In particular

$$X_0 = A,\quad X_1 = B,\quad X_2 = A^{-1} B A,\quad X_3 = A^{-2} B A^{2},\quad\ldots,$$

so for $n \ge 1$ one has $X_n = A^{-(n-1)} B A^{\,n-1}$. With the composition convention of §1, $X_{n+1}$ is the map $x \mapsto A^{-n}\bigl(B\bigl(A^{n}(x)\bigr)\bigr)$.

4. The word attached to a finite list of natural numbers

For a finite list of natural numbers $c = (c_0, c_1, \ldots, c_{k-1})$, define

$$\operatorname{word}(c) \;=\; X_0^{\,c_0}\, X_1^{\,c_1}\, X_2^{\,c_2}\cdots X_{k-1}^{\,c_{k-1}} \;\in\; G .$$

That is: the $i$-th entry of the list (counting from $i = 0$) is used as the exponent of the generator $X_i$ — the generator index advances by exactly one for each step along the list — and the factors are multiplied in that left-to-right order in $G$. The empty list gives $\operatorname{word}(\,) = 1$.

Because the entries $c_i$ are natural numbers, only non-negative powers of the $X_i$ occur; no inverse of any $X_i$ appears inside $\operatorname{word}(c)$. As a function on $I$, by §1 the factor $X_{k-1}^{\,c_{k-1}}$ is applied first and $X_0^{\,c_0}$ last.

5. Finite binary trees, their leaf count, and their marks

A tree here means a finite rooted binary tree in which every node either is a leaf or has exactly two children, a left child and a right child. Write $\ell(t)$ for the number of leaves of $t$; thus $\ell(\text{leaf}) = 1$ and $\ell(t_1 \wedge t_2) = \ell(t_1) + \ell(t_2)$, where $t_1 \wedge t_2$ denotes the tree with root having left subtree $t_1$ and right subtree $t_2$.

Marks. Assign to each node of $t$ a closed subinterval of $[0,1]$: the root is assigned $[0,1]$, and a node assigned $[a,b]$ gives its left child $\bigl[a, \tfrac{a+b}{2}\bigr]$ and its right child $\bigl[\tfrac{a+b}{2}, b\bigr]$. The marks of $t$ are then the list

$$\operatorname{marks}(t) \;=\; \bigl(x_0, x_1, \ldots, x_{\,\ell(t)}\bigr), \qquad 0 = x_0 < x_1 < \cdots < x_{\ell(t)} = 1,$$

consisting of $0$, then the midpoints of the intervals assigned to the internal nodes of $t$ listed in in-order (left subtree, node, right subtree) — which is increasing order — and finally $1$. Equivalently, the consecutive intervals $[x_{i-1}, x_i]$ are exactly the intervals assigned to the leaves of $t$, read left to right.

The list $\operatorname{marks}(t)$ has $\ell(t) + 1$ entries. For the one-leaf tree, $\operatorname{marks}(\text{leaf}) = (0,1)$. Examples: $\operatorname{marks} = (0,\tfrac12,1)$ for the two-leaf tree; $(0,\tfrac14,\tfrac12,1)$ for the tree whose left subtree is a caret and whose right subtree is a leaf; $(0,\tfrac12,\tfrac34,1)$ for the mirror tree; $(0,\tfrac14,\tfrac12,\tfrac34,1)$ for the balanced four-leaf tree.

6. The two integer lists attached to a tree: left-runs and exponents

Two lists of natural numbers are attached to each tree. Let $\frown$ denote concatenation of lists, and let $\mathrm{inc}$ be the operation that adds $1$ to the first entry of a list, leaving all other entries alone (and sending the empty list to itself).

Left-runs.

$$\mathrm{lr}(\text{leaf}) = (0), \qquad \mathrm{lr}(t_1 \wedge t_2) \;=\; \mathrm{inc}\bigl(\mathrm{lr}(t_1)\bigr) \frown \mathrm{lr}(t_2).$$

Exponents.

$$e(\text{leaf}) = (0), \qquad e(t_1 \wedge t_2) \;=\; \mathrm{lr}(t_1) \frown e(t_2).$$

These two recursions are different, and the difference is exactly the point at which care is needed: at a node, left-runs recurses with left-runs on both subtrees and increments the first entry of the left subtree's list, whereas exponents recurses with left-runs on the left subtree — with no increment — and with exponents on the right subtree. Iterating the second recursion down the right spine of $t$: if $t_1, t_2, \ldots, t_m$ are the left subtrees hanging off the right spine of $t$, read from the root downwards ($m$ being the length of that spine), then

$$e(t) \;=\; \mathrm{lr}(t_1) \frown \mathrm{lr}(t_2) \frown \cdots \frown \mathrm{lr}(t_m) \frown (0).$$

Both lists have exactly $\ell(t)$ entries, and the last entry of each is always $0$.

A closed description of the entries. Address each leaf of $t$ by the word in the alphabet $\{L, R\}$ recording the left/right steps taken from the root to that leaf, and list the leaves in left-to-right order. Then, entry by entry:

• the entry of $\mathrm{lr}(t)$ at a leaf is the length of the maximal terminal block of $L$'s in that leaf's address (i.e. the number of consecutive left steps immediately preceding the leaf);
• the entry of $e(t)$ at a leaf is that same number, reduced by $1$ exactly when the leaf's address has the form $R^{s}L^{a}$ with $a \ge 1$ (all right steps followed by all left steps), and equal to it otherwise. The rightmost leaf, whose address is $R^{s}$, gets $0$.

For example, for the ten-leaf tree

$$t \;=\; \Bigl(\bigl((\text{leaf} \wedge (\text{leaf}\wedge\text{leaf})) \wedge \text{leaf}\bigr)\Bigr) \wedge \Bigl(\bigl(\text{leaf} \wedge ((\text{leaf}\wedge\text{leaf})\wedge\text{leaf})\bigr) \wedge (\text{leaf}\wedge\text{leaf})\Bigr)$$

one has $e(t) = (2,1,0,0,1,2,0,0,0,0)$ while $\mathrm{lr}(t) = (3,1,0,0,2,2,0,0,1,0)$.

For the right-hand comb $\text{leaf}\wedge(\text{leaf}\wedge(\cdots))$ with $n+1$ leaves, $e = (0,0,\ldots,0)$ while $\mathrm{lr} = (1,1,\ldots,1,0)$; for the left-hand comb with $n+1$ leaves, $e = (n-1, 0, \ldots, 0)$ for $n \ge 1$ while $\mathrm{lr} = (n,0,\ldots,0)$.

Only $e$, the exponents list, appears in the statement being read back; $\mathrm{lr}$ enters only through the recursion that defines $e$.

7. Tree diagrams, the group $F$, extension to $\mathbb{R}$, and "represents"

Tree diagram. A tree diagram $d$ consists of three pieces of data: a tree $d_{\mathrm{dom}}$ (the domain tree), a tree $d_{\mathrm{ran}}$ (the range tree), and a proof that the two have the same number of leaves,

$$\ell(d_{\mathrm{dom}}) \;=\; \ell(d_{\mathrm{ran}}).$$

That equality is part of the datum $d$, hence part of the hypothesis of the statement. In particular $\operatorname{marks}(d_{\mathrm{dom}})$ and $\operatorname{marks}(d_{\mathrm{ran}})$ have the same number of entries, namely $\ell(d_{\mathrm{dom}}) + 1$.

Dyadic numbers. A real number $x$ is dyadic if $x = m/2^{k}$ for some integer $m$ (any sign) and some natural number $k$.

The distinguished subset of $G$. Call $g \in G$ Thompson when there is a finite set $\mathcal{B}$ of real numbers, all of them dyadic, such that for every pair $u, v \in I$ with $u < v$ and with the open interval $(u,v)$ disjoint from $\mathcal{B}$, there exist an integer $n$ (possibly negative) and a real number $c$ with

$$g(z) \;=\; 2^{\,n} z + c \qquad \text{for every } z \in I \text{ with } u \le z \le v .$$

So a Thompson element is an increasing self-bijection of $[0,1]$ that is affine with slope an integer power of $2$ on each interval free of the finitely many dyadic breakpoints.

The group $F$. $F$ is the subgroup of $G$ generated by the set of Thompson elements: the smallest subgroup of $G$ containing every Thompson element. Membership $f \in F$ therefore means that $f$ lies in every subgroup of $G$ that contains all Thompson elements; equivalently, $f$ is a finite product of Thompson elements and inverses of Thompson elements. It does not literally say that $f$ is itself Thompson.

Extension to the line. For $f \in G$ let $\widetilde{f} : \mathbb{R} \to \mathbb{R}$ be

$$\widetilde{f}(x) \;=\; \begin{cases} f(x), & 0 \le x \le 1,\\ x, & \text{otherwise}, \end{cases}$$

i.e. $f$ extended by the identity off $[0,1]$. This is an increasing bijection of $\mathbb{R}$.

Affine on the pieces of a list. For an increasing bijection $L$ of $\mathbb{R}$ and a finite list of reals $(x_0, x_1, \ldots, x_k)$, say that $L$ is affine on the pieces of that list when for each consecutive pair $(x_{i-1}, x_i)$, $1 \le i \le k$, there exist real numbers $a$ and $c$ (depending on $i$) with

$$L(z) \;=\; a z + c \qquad\text{for all } z \text{ with } x_{i-1} \le z \le x_i .$$

No condition is placed on $a$ beyond being real: it is not required to be positive, nor a power of $2$. Lists with fewer than two entries satisfy the condition vacuously.

Represents. Finally, $d$ represents $f$ means the conjunction of three conditions:

1. $f \in F$;
2. $\widetilde{f}$ is affine on the pieces of $\operatorname{marks}(d_{\mathrm{dom}})$ — the domain tree's marks;
3. applying $\widetilde{f}$ to each entry of $\operatorname{marks}(d_{\mathrm{dom}})$ yields $\operatorname{marks}(d_{\mathrm{ran}})$, as an equality of lists of real numbers. Since the two lists have equal length (by the leaf-count datum in $d$), this says precisely

$$\widetilde{f}(x_i) \;=\; y_i \quad\text{for } i = 0, 1, \ldots, \ell(d_{\mathrm{dom}}),$$

where $(x_i)$ and $(y_i)$ are $\operatorname{marks}(d_{\mathrm{dom}})$ and $\operatorname{marks}(d_{\mathrm{ran}})$. Because all the marks lie in $[0,1]$, this is the same as $f(x_i) = y_i$ for all $i$.

8. The assertion

For every tree diagram $d$ and every order isomorphism $f$ of $[0,1]$, if $d$ represents $f$ in the sense of §7, then

$$f \;=\; \operatorname{word}\bigl(e(d_{\mathrm{ran}})\bigr)\cdot > \operatorname{word}\bigl(e(d_{\mathrm{dom}})\bigr)^{-1}$$

as elements of $G$.

Reading off the conventions of §1 and §4: the first factor is the word built from the exponents list of the range tree, the second factor is the inverse of the word built from the exponents list of the domain tree, and they appear in that order, the range word on the left. Pointwise this says

$$f(x) \;=\; \operatorname{word}\bigl(e(d_{\mathrm{ran}})\bigr) \Bigl(\operatorname{word}\bigl(e(d_{\mathrm{dom}})\bigr)^{-1}(x)\Bigr) \qquad\text{for all } x \in [0,1],$$

i.e. the domain word is undone first and the range word applied afterwards. Written out with $e(d_{\mathrm{dom}}) = (p_0, \ldots, p_{k-1})$ and $e(d_{\mathrm{ran}}) = (q_0, \ldots, q_{k-1})$ (these two lists have the same length $k = \ell(d_{\mathrm{dom}}) = \ell(d_{\mathrm{ran}})$), the claimed identity is

$$f \;=\; \bigl(X_0^{\,q_0} X_1^{\,q_1}\cdots X_{k-1}^{\,q_{k-1}}\bigr)\, \bigl(X_0^{\,p_0} X_1^{\,p_1}\cdots X_{k-1}^{\,p_{k-1}}\bigr)^{-1},$$

with all $p_i, q_i \ge 0$ and $p_{k-1} = q_{k-1} = 0$.

It is an equality of elements of $G$, i.e. of order isomorphisms of $[0,1]$, hence an equality of functions on $[0,1]$ (and of their inverses).

9. Degenerate and edge cases silently included

• The hypothesis is satisfiable, not vacuous. Taking $d$ to be the diagram whose domain and range trees are both the one-leaf tree and $f$ the identity: $\operatorname{marks} = (0,1)$ on both sides, the identity lies in $F$, its extension is the identity of $\mathbb{R}$ (affine with $a=1$, $c=0$), and $(0,1)$ maps to $(0,1)$. So $d$ represents $f$. In that case $e(\text{leaf}) = (0)$, $\operatorname{word}((0)) = X_0^{0} = 1$, and the claimed conclusion reads $f = 1\cdot 1^{-1} = 1$, which is the case.

• One-leaf trees give trivial words. Because $e(\text{leaf}) = (0)$ and the last entry of $e(t)$ is always $0$, the final factor $X_{k-1}^{\,0}$ of each word is always the identity.

• No reducedness assumption. Nothing in the hypothesis requires the diagram $d$ to be reduced (i.e. to have no common cancelling caret in the two trees); the claim is asserted for all diagrams that represent $f$, reduced or not. Consequently, if several diagrams represent the same $f$, the statement asserts the same equation for each of them.

• Both exponent lists are read from the same tree diagram $d$, and the statement fixes which tree goes where: range tree on the left factor, domain tree in the inverted factor.

• The affineness condition in the hypothesis is stated only for the domain tree's marks, and imposes no slope restriction; the power-of-two slope restriction enters the hypothesis only indirectly, through membership in the group $F$ generated by the Thompson elements.

• Natural-number exponents only. Since $e(t)$ is a list of natural numbers, negative powers of the $X_i$ occur in the conclusion only through the single explicit inversion of the whole domain word.

• The two lists $e(d_{\mathrm{dom}})$ and $e(d_{\mathrm{ran}})$ have equal length, which is the common leaf count; so the same set of generator indices $X_0, \ldots, X_{k-1}$ is available to both words.