Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 !---

share|cite|improve this question
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
up vote 9 down vote accepted

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

share|cite|improve this answer
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
Sorry about that, I obviously read your proof too fast and misread it... – AlexPof Aug 22 '11 at 19:52
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
I'm so sorry, I just realized I never accepted your answer. I actually thought the bounty system would have taken care of this... I just did now so I hope you won't mind... – AlexPof Sep 27 '11 at 15:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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