# Groups of homeomorphisms of the real line

Consider the group of homeomorphisms of the real line (under composition) generated by the functions $f$ and $g$, where $$f\colon x\longmapsto x-1$$ and $$g\colon x\longmapsto \left\{\begin{array}{ll}x & \text{if }x\leq 0,\\ \frac{x}{2} &\text{if }x\gt 0. \end{array}\right.$$ Does anyone have a nice description of this group?

(It is similar to the Thompson group, except that the the 1/2 slope extends to infinity)

Edit :

It seems the following set of relations works for this group : $g^{-1}f^ng^{-1}f^{-n}=f^{2n}g^{-1}f^{-2n}g^{-1}$ for n>1

How can I check if this determines the group entirely ? (by the way, how to answer this question for any group ?)

---I'm really interested in the answer of those two questions, so I'm offering a +100 bounty for this. Thanks !---

-
are there any non trivial relations you know of? – Olivier Bégassat Aug 11 '11 at 18:53
@Olivier: There must be because it is a subgroup of the Thompson group $F$ and the latter is of course known not to have non-abelian free subgroups. .@AlexPof: Jim Belk was around here for a while (haven't seen him lately, though), he would probably be able to answer that question immediately. In the meantime, you might want to look at Belk-Browns's Forest diagrams the forest diagrams might help in managing this group. – t.b. Aug 11 '11 at 19:33
@Theo Buehler but $f$ and $g$ don't commute: $g\circ f(1)=0$ while $f\circ g(1)=-1/2$. EDIT: I just realized you wrote non-abelian subgroups, my bad! – Olivier Bégassat Aug 11 '11 at 19:37
@Olivier: The important point in my previous comment is nonabelian free – t.b. Aug 11 '11 at 19:43
@Olivier: I think you've got the relation $gfg = fgf^{-1}gf$, namely, if you squeeze, shift left, then squeeze again you'll get the same thing as if you shift left, squeeze, shift right, squeeze, and then shift left again. It's a very Thompson group-esque relation since you're sort of choosing which order you're doing certain transformations (akin to adding carets to a forest diagram in different orders). – MartianInvader Aug 11 '11 at 21:23

The group, $G$, generated by the homeomorphisms $f,g\colon\mathbb{R}\to\mathbb{R}$ as described in the question satisfies the relations \begin{align} f^{-n}gf^ng=gf^{-2n}gf^{2n}&&{\rm(1)} \end{align} for all $n\ge0$. In fact, the relations (1) for $n\in\{1,2\}$ are enough to completely describe the group. In other words, $$G=\left\langle f,g\;\big\vert\;f^{-1}gfg^2=gf^{-2}gf^{2}g=g^2f^{-4}gf^{4}\right\rangle.$$ So, $G$ is finitely presented. Furthermore, this is a minimal complete set of relations.

We can also describe $G$ as the set of piecewise linear functions $u\colon\mathbb{R}\to\mathbb{R}$ with finitely many nondifferentiable points such that

• The set of $x$ at which $u(x)$ is nondifferentiable are contained in the dyadic rationals $\mathbb{D}=\left\{2^rs\colon r,s\in\mathbb{Z}\right\}$.
• The gradient of $u$ at each differentiable point is an integer power of $2$.
• There exists an $m\in\mathbb{Z}$ such that $u(x)=x-m$ for all $x$ to the left of the nondifferentiable points of $u$.

The homeomorphisms $f$ and $g$ are in the group of piecewise linear functions just described and, as I will show, do generate this group.

Let's start by finding a unique representation of the elements of $G$. To this end, define the homeomorphisms $\theta_p\colon\mathbb{R}\to\mathbb{R}$ for dyadic rationals $p$ $$\theta_p(x)=\begin{cases} x,&\textrm{if }x\le p,\\ 2x-p,&\textrm{if }x\ge p. \end{cases}$$ Then, for integers $m,n,r_1,r_2,\ldots,r_n$ with $n\ge0$ and dyadic rationals $p_1 < p_2 < \cdots < p_n$, consider the function \begin{align} u=f^m\theta_{p_1}^{r_1}\theta_{p_2}^{r_2}\cdots\theta_{p_n}^{r_n}&&{\rm(2)} \end{align} (exponents and 'products' of homeomorphisms represent function composition). It can be seen that $u(x)$ is piecewise linear with nondifferentiable points $\{p_1,p_2,\ldots,p_n\}$, $u(x)=x-m$ for $x$ to the left of the set of nondifferentiable points and $u$ has gradient $2^{r_1+r_2+\cdots+r_k}$ just to the right of point $p_k$. So, letting $G^\prime$ be the group of piecewise linear functions as described above (which I will show is equal to $G$), we see that every $u\in G^\prime$ is uniquely described by an expression of the form (2). For dyadic rationals $p < q$, we have the following relations \begin{align} \theta_pf&=f\theta_{p+1}.&{\rm(3)}\\ \theta_q\theta_p&=\theta_p\theta_\frac{p+q}2.&{\rm(4)} \end{align} Iteratively applying these relations gives \begin{align} \theta^r_pf^s&=f^s\theta^r_{p+s}.\\ \theta^r_q\theta^s_p&=\theta^s_p\theta^r_{p+2^{-s}(q-p)}. \end{align} for all $r,s\in\mathbb{Z}$. Given any element of $G^\prime$ expressed in terms of $f$ and $\theta_{p_i}$ we can use these identities to first move all powers of $f$ to the left, then move powers of $\theta_{q_1}$ to the left (for $q_1=\min_ip_i$) and so on. This puts the expression in the form (2), which is sufficient to be able to tell if two expressions in terms of $f$ and $\theta_p$ are equal. So, (3,4) give a complete set of relations for $G^\prime$ with generators $f$ and $\{\theta_p\colon p\in\mathbb{D}\}$. As we have $\theta_0=g^{-1}$ then, for positive dyadic rationals $p=2^rs$, $$\theta_p=\theta_0^r\theta_s\theta_0^{-r}=\theta_0^rf^{-s}\theta_0f^s\theta_0^{-r}\in G.$$ Also, for a non-positive dyadic rational $p$, then $\theta_p=f^r\theta_{p+r}f^{-r}\in G$ for any integer $r$ with $p+r > 0$. So, $G^\prime=G$.

We can now show that equations (1) for $n\ge1$ gives a complete set of relations for the group $G$ for generators $f,g$. The idea is to show that that these relations imply the existence of elements $\{\theta_p\colon p\in\mathbb{D}\}$ of $G$ satisfying $\theta_0=g^{-1}$ and the relations (3,4) which, as we have just shown, fully describes $G$. First, for non-negative integers $n$, define $\theta_n=f^{-n}g^{-1}f^n$. Relations (1) give \begin{align} \theta_{2n}\theta_0=\theta_0\theta_n&&{\rm(5)} \end{align} for $n\ge1$. Next, for $p=2^{-r}s$ with integer $r,s$ and $r\ge0$, $s\ge1$ define $\theta_p=\theta_0^{-r}\theta_s\theta_0^r$. We need to check that this is consistent, giving the same value if we express $p=2^{-r-1}(2s)$, $$\theta_{2^{-r-1}(2s)}=\theta_0^{-r-1}\theta_{2s}\theta_0^{r+1}=\theta_0^{-r}\theta_s\theta_0^r=\theta_{2^{-r}s}$$ (using (5) with $n=s$). This defines $\theta_p$ for nonnegative dyadic rationals such that $\theta_0^{-1}\theta_p\theta_0=\theta_\frac{p}2$. For dyadic rationals $0\le p < q$ and writing $p=2^{-r}s, q=p+2^{1-r}t$ for nonnegative $r,s$ and positive $t$, $$\theta_q\theta_p=\theta_0^{-r}f^{-s}(\theta_{2t}\theta_0)f^s\theta_0^r =\theta_0^{-r}f^{-s}(\theta_0\theta_t)f^s\theta_0^r =\theta_p\theta_\frac{p+q}2.$$ So (4) is satisfied for nonnegative dyadic rationals. We need to show that (3) holds. We know that it is true for integer $p$ so, by induction, it just needs to be shown that if (3) holds then it also holds for $p$ replaced by $p/2$. $$\theta_\frac p2f=\theta_0^{-1}\theta_p\theta_0f=f\theta_1^{-1}\theta_{p+1}\theta_1=f\theta_\frac{p+2}2=f\theta_{\frac p2+1}.$$ So (3,4) hold for nonnegative dyadic rationals. Using (3) we can define $\theta_p=f^r\theta_{p+r}f^{-r}$ for all dyadic rationals $p$ and integer $r$ with $p+r\ge0$. Finally, sandwiching each side of (4) within $f^{-r}\cdot f^r$ terms reduces it to the case of nonnegative dyadic rationals, so (3,4) hold. Therefore, (1) is a complete set of relations for the group $G$ generated by $f,g$.

Now, we can show that (1) gives a complete set of relations even if we restrict to $n=1,2$. For any integer $n$, set $\theta_n=f^{-n}g^{-1}f^n$ as above, so equation (1) is equivalent to (5). Sandwiching each side of (5) inside $f^{-m}\cdots f^m$ gives \begin{align} \theta_{2n+m}\theta_m=\theta_m\theta_{n+m}.&&{\rm(6)} \end{align} Let us suppose that $N\ge3$ is such that (1), and hence (6), hold for all positive $n < N$. Choose $r\in\{1,2\}$ such that $N-r$ is even and set $N=2M+r$. Then, \begin{align} \theta_{2N}\theta_0\theta_r&=\theta_{2N}\theta_{2r}\theta_0&&{\rm using\ (6)\ with\ }m=0,n=r&\\ &=\theta_{2r}\theta_{N+r}\theta_0&&{\rm using\ (6)\ with\ }m=2r,n=2M\\ &=\theta_{2r}\theta_0\theta_{M+r}&&{\rm using\ (6)\ with\ }m=0,n=M+r\\ &=\theta_0\theta_r\theta_{M+r}&&{\rm using\ (6)\ with\ }m=0,n=r\\ &=\theta_0\theta_N\theta_r&&{\rm using\ (6)\ with\ }m=r,n=M. \end{align} So $\theta_{2N}\theta_0=\theta_0\theta_N$ and (1) holds for $n=N$. By induction, if (1) holds for $n=1$ and $n=2$ then it holds for all positive $n$.

Finally, I can show that the complete set of relations (1) for $n\in\{1,2\}$ is minimal. That is, for any $N\in\{1,2\}$ there is a group $G$ with elements $f,g$ satisfying (1) for $n=N$ but not for $n\in\{1,2\}\setminus\{N\}$.

First, consider $N=2$. To find a case where (1) is satisfied for $n=2$ but not $n=1$, it is enough for $f,g$ to be such that $f^2,g$ commute but $f,g$ do not commute. For example, taking $G=GL_2(\mathbb{R})$ to be the group of invertible 2x2 matrices then $$A=\left(\begin{array}{cc}0&1\\1&0\end{array}\right),\ B=\left(\begin{array}{cc}1&0\\0&-1\end{array}\right)$$ anticommute ($AB=-BA$) and $f=A$, $g=B$ gives the required example.

Now, consider $N=1$. I'm not sure if there is a simple finite-dimensional example where (1) is satisfied for $n=1$ but not $n=2$. For an infinite-dimensional example, let $V$ be the vector space $(\mathbb{C}^2)^\mathbb{Z}$ of functions $v\colon\mathbb{Z}\to\mathbb{C}^2$. Also, let $M_k\in GL_2(\mathbb{C})$ ($k\in\mathbb{Z}$) be a sequence of 2x2 invertible matrices. Then let $G=GL(V)$ be the group of invertible linear maps on $V$ with \begin{align} fv(k)&=M_kv(k),\\ gv(k)&=v(k+1). \end{align} for all $v\in V$. Then, \begin{align} f^{-n}gf^ngv(k)&=M^{-n}_kM^n_{k+1}v(k+2),\\ gf^{-2n}gf^{2n}v(k)&=M^{-2n}_{k+1}M^{2n}_{k+2}v(k+2). \end{align} So, (1) reduces to the identity \begin{align} M^{-n}_kM^n_{k+1}=M^{-2n}_{k+1}M^{2n}_{k+2}.&&{\rm(7)} \end{align} In order to force (1) to be satisfied for $n=1$, we can choose $M_0,M_1\in GL_2(\mathbb{C})$ however we like and then inductively define \begin{align} M^2_{k+2}&=M^{2}_{k+1}M^{-1}_kM_{k+1},&(k\ge0)\\ M_k&=M_{k+1}M^{-2}_{k+2}M^2_{k+1}.&(k < 0) \end{align} For the first of these two recurrence relations, you need the fact that every element of $GL_2(\mathbb{C})$ has a square root. Now suppose that $M_0=A$ and $M_1=B$ are the anticommuting matrices above. Then, using the expression above for $M_2^2$ shows that $M_2^2,M_1$ anticommute and $M_2^2,M_1^2$ commute. Squaring expression (7) for $k=0,n=1$ gives $$M_0^{-2}M_1^2=-(M_0^{-1}M_1)^2=-(M_1^{-2}M_2^2)^2=-M_1^{-4}M_2^4.$$ So (7) fails for $k=0,n=2$, and relation (1) does not hold for $n=2$.

-
Thanks for this very detailed explanation... I just have one single question before accepting this answer : when you write "In fact, the relations (1) for n∈{1,2} are enough to completely describe the group", how do you actually ensure that these relations are indeed sufficient ? – AlexPof Aug 22 '11 at 19:07
@AlexPof: That's explained in the final section of my answer. The relations for $n\in\{1,2\}$ generate the relations for all other $n$ which, as I showed, is a complete set of relations. – George Lowther Aug 22 '11 at 19:12
I added even more, showing that the set of relations (1) for $n\in\{1,2\}$ is minimal. – George Lowther Aug 22 '11 at 21:27