Grigorchuk's group

In a previous post we constructed a rather intricate counterexample to the Generalized Burnside Problem using the Golod-Shafarevich criterion for the infinite dimensionality of algebras.
In this post, we will look at a famous group introduced by Grigorchuk which will also be a counterexample to the generalized Burnside problem. Namely, it will be an infinite, finitely generated, $2$-group. The construction is amazingly elementary.

Start with an infinite rooted binary tree $T$, which we visualize growing downward.

         

The non-root nodes of the tree are in 1-1 correspondence with finite sequences of $0$'s and $1$'s. $0$ means head left while $1$ means head right.  The Grigorchuk group $G$ is a subgroup of the automorphism group of $T$. Let $a\in\mathrm{Aut}(T)$ be the involution which exchanges the left and right branches of the tree. On the level of finite bitstrings, it just flips the first bit. We define three other automorphisms $b$, $c$, and $d$ as follows:

    So each of $b,c,d$ fixes the rightmost chain of nodes and alternates acting by $a,a,1$ on the sequence of trees branching off to the left.

If an automorphism fixes the two nodes adjacent to the root, it can be written as a pair of autmorphisms $(x,y)$, each acting on a tree isomorphic to $T$. In other words, let $\mathrm{stab}_1$ denote the group of automorphisms fixing the two nodes of distance $1$ from the root. Then $\mathrm{stab}_1\cong \mathrm{Aut}(T)\times \mathrm{Aut}(T)$. With this convention, we see that $$b=(a,c), c=(a,d), d=(1,b).$$ Moreover one can take these as recursive definitions for $b,c,d$! It is easy to see that $\{1,b,c,d\}$ form a Klein 4-group.

Definition: Grigorchuk's group $G$ is the subgroup of $\mathrm{Aut}(T)$ generated by $\{a,b,c,d\}$.

By definition, $G$ is finitely generated. We also want so show that it is infinite and torsion.

To see that it is infinite, calculate $aba=(c,a), aca=(d,a)$ and $ada=(b,1)$. Thus $H=\mathrm{stab}_1\cap G$ contains elements with $a,b,c,d$ as their first coordinates. So $H$ surjects onto $G$ itself. But $H$ is a proper subgroup of $G$ (in fact index $2$) so the only way this could happen is if $G$ is infinite.

Now we show that $G$ is a torsion group. Any element of $G$ can be written as a product of generators which alternate between $a$ and non-$a$ letters. Moreover any such word is conjugate to one which begins with $a$ and ends with a non-$a$ letter. So consider a word
$$g=au_1au_2\ldots au_k,$$ where $u_i\in\{b,c,d\}$. We proceed by induction on the length $2k$. (If $k=1$, it is not hard to check that $ab,ac,ad$ are all torsion.) We consider two cases: $k$ even and $k$ odd. If $k$ is even, then $g\in\mathrm{stab}_1$, so we can write $g=(x,y)$. But $x$ and $y$ are now both words of length $\leq k$. For example, $$abac=(aba)c=(c,a)(a,d)=(ca,ad).$$ So we have reduced to a smaller case. Now suppose that $k$ is odd. Then $g\not\in\mathrm{stab}_1$, so we can't quite do the same thing. However $g^2\in\mathrm{stab}_1$. Now $g^2=(x,y)$ where $x$ and $y$ have length $\leq|g|$, so it doesn't look like we've made progress. However, if $d$ appears as one of the letters, then the length of each $x,y$ does go down. For example, if $g=abacad$, then
$\begin{align*} g^2&=(aba)c(ada)b(aca)d\\ &=(c,a)(a,d)(b,1)(a,c)(d,a)(1,b)\\ &=(cabad,adcab) \end{align*}$
The point is that $d$ appears (at least) twice and parity considerations show that it puts a copy of $1$ into the first and second coordinates. Thus $g^2$ is torsion, and hence so is $g$, by induction.

If $d$ doesn't appear in $g$, then similar parity considerations will show that every appearance of $b$ in $g$ will put a copy of $c$ into $x$ and $y$, while every appearance of $c$ will put a copy of $d$ into $x$ and $y$. That is $g^2=(x,y)$ where $x$ and $y$ now have either a $c$ or $d$ in both. If there is a $d$, then $x$ and $y$ are both torsion, and so therefore is $g^2$ and $g$. If there is a $c$, then $$g^4=(x^2,y^2)=((\alpha_1,\alpha_2),(\alpha_3,\alpha_4)),$$ where $d$ appears in each $\alpha_i$, so $g^4$ is torsion here as well.

Thus we have shown that $G$ is torsion (in fact a $2$-group)!

Niven's proof of the irrationality of Pi (Edited)

There is a beautiful short proof of $\pi$'s irrationality due to Ivan Niven, which I'd like to present here. In some sense, one could just read Niven's short one page paper, but I'd like to go over it anyway, if only to assure myself that there are no hidden details! I have presented this proof to a couple of my undergraduate classes, and I am editing this post to try to address some of the points where students tended to get confused.

As with most proofs of irrationality, we assume toward a contradiction that $\pi=a/b$ for some positive integers $a,b$. In other words, we suppose that $\pi=a/b$ and get a contradiction, i.e. a false statement. Since we get a false statement, it means that our initial assumption has to have been incorrect, and so $\pi$ cannot possibly equal $a/b$ for any $a,b$ integers.

Our strategy will be to use $a,b$ to construct a "magic" function, one so magical that it can't possibly exist! Our function will have the following two properties:

1. $\int_0^\pi f(x)\sin x\,dx$ is a positive integer.
2. $0<\int_0^\pi f(x)\sin x\,dx<1$

This is of course impossible, and is the desired contradiction. 

Now define the magic function to be of the form $$f(x)=\frac{x^n(a-bx)^n}{n!}$$
where $n$ is a positive integer which we will now determine. Let us look at $f(x)$ on the interval $[0,\pi]$. The biggest $x^n$ can be is $\pi^n$, whereas the biggest $(a-bx)^n$ can be is $a^n$ (when $x=0$). So $f(x)\leq \frac{\pi^na^n}{n!}$. This is a crude upper bound, it is not the exact maximum, but that's okay. Also, $f(x)>0$ when $0<x<\pi=a/b$ since one can easily see that $(a-bx)>0$ for $x<\pi$. So we have
$$0<\int_0^\pi f(x)\sin x\,dx \leq \frac{\pi^na^n}{n!}\cdot \pi,$$
because the integrand is bounded by $\frac{\pi^na^n}{n!}$ and the length of the interval is $\pi$. It is a calculus exercise to show that $\lim_{n\to\infty} \pi\frac{\pi^na^n}{n!}=0$. One way to solve this exercise is to note that this limit is equal to $\pi\lim_{n\to\infty} \frac{c^n}{n!}$ for $c=\pi a$, and $\sum_{n=0}^\infty \frac{c^n}{n!} =e^c$ is a power series which converges everywhere. So in particular $\lim_{n\to\infty} \frac{c^n}{n!}=0$. So now that we know the limit is $0$, we may pick a large $n$ so that $\int_0^\pi f(x)\sin x\,dx<1$ since the integral is bounded by a sequence tending to $0$. This establishes the second property we want for our "magic" function $f$.

To establish the first property, we use integration by parts to calculate  $\int_0^\pi f(x)\sin x\,dx$.
$$\begin{align*}  \int f(x) \sin x\,dx&= -f(x)\cos x+\int f'(x)\cos x\,dx\\ &=-f(x)\cos x+f'(x)\sin x -\int f''(x)\sin x\,dx\\ &=-f(x)\cos x+f'(x)\sin x + f''(x)\cos x -\int f'''(x)\cos x\,dx\\ &\vdots\\ &=-f(x)\cos x+f'(x)\sin x + f''(x)\cos x-f''(x)\sin x+\cdots \pm f^{(2n)}(x)\cos x \end{align*}$$
The reason this eventually terminates is that $f(x)$ is a polynomial of degree $2n$. So $f^{(2n+1)}(x)=0$.  We now have an antiderivative for $f(x)\sin x$, which we can use to calculate $\int_0^\pi f(x)\sin x\,dx$  by plugging in $\pi$ and subtracting off the value at $0$. Notice that all the $\sin$ terms disappear since $\sin(0)=\sin(\pi)=1$. We get
$\begin{multline*} \int_0^\pi f(x)\sin x\,dx= f(\pi)-f^{(2)}(\pi)+f^{(4)}(\pi)-\cdots\pm f^{(2n)}(\pi)\\  +f(0)-f^{(2)}(0)+\cdots \mp f^{(2n)}(0) \end{multline*}$

Hence, in order to show $\int_0^\pi f(x)\sin x\,dx$ is an integer, it will suffice to show that all derivatives of $f$ evaluated at $\pi$ and $0$ are integers. In fact, it is not difficult to check that $f(\pi-x)=f(x)$ using that $\pi=a/b$ by direct algebraic computation. Taking the derivative of both sides, using the chain rule, we get:
$$\begin{align*} f(\pi-x)&=f(x)\\ -f'(\pi-x)&=f'(x)\\ f''(\pi-x)&=f''(x)\\ &\vdots\\ (-1)^kf^{(k)}(\pi-x)&=f^{(k)}(x) \end{align*}$$
Plugging in $x=\pi$, we get $(-1)^k f^{(k)}(0)=f^{(k)}(\pi)$. So if we can show that $f^{(k)}(0)$ are integers, then it will automatically follow that $f^{(k)}(\pi)$ are integers, since they differ only by a sign.

So, now our proof will finally be done if we can show that $f^{(k)}(0)$ are integers. There is a nice trick for computing $f^{(k)}(0)$ for polynomials $f(x)$. Taylor's theorem says the coefficient of $x^k$ is $f^{(k)}(0)/k!$, or to put it another way $$f^{(k)}(0)=k! \times \text{ coefficient of }x^k.\,\,(\dagger)$$
We can compute the coefficients of powers of $x$ in $f(x)$ using the binomial theorem. First of all, because we are multiplying by $x^n$, the powers of $x$ in $f(x)$ range from $x^n$ to $x^{2n}$. So $f^{(k)}(x)=0$ for all $k<2n$.  Now, for $0\leq d\leq n$, the term involving $x^d$ in $(a-bx)^n$ is given by $\binom{n}{d}(-bx)^da^{n-d}=\binom{n}{d}(-b)^da^{n-d} x^d$. So the coefficient of $x^{n+d}$ in $\frac{1}{n!} x^n(a-bx)^n$ is given by
$\frac{1}{n!}\binom{n}{d}(-b)^da^{n-d}$. So, by the above formula $(\dagger)$ for calculating derivatives, we have
$$f^{(n+d)}(0)=\frac{(n+d)!}{n!}\binom{n}{d}(-b)^da^{n-d}.$$
This is an integer because $\frac{(n+d)!}{n!}=\frac{(n+d)(n+d-1)\cdots (n+1)n(n-1)\cdots 1}{n(n-1)\cdots1}=(n+d)(n+d-1)\cdots (n+1)$ is an integer. 

So in summary, the polynomial $f(x)$ only has nonzero derivatives $f^{(k)}(0)$ for $n\leq k\leq 2n$ and these derivatives have the explicit form given in the above formula, establishing that they are integers.

 It would be interesting to figure out exactly what was needed about $\pi$ to make this argument work. Can it be modified to show other numbers are irrational?

Edit: Matt Baker's Blog has a discussion on how to generalize this in a motivated way.  

Burnside Problems

I am sitting in on a nice class given by Efim Zelmanov at UCSD and I thought I'd talk a little bit on this blog about some of the stuff he has covered. This post will be about the Burnside problems:

Generalized Burnside Problem: Suppose that $G$ is a finitely generated group where every element has finite order. Is $G$ a finite group?

Burnside Problem: Suppose that $G$ is a finitely generated group, such that there exists an $N$ for which $g^N=1$ for all $g\in G$. Is $G$ finite?

It turns out that the answer to both these questions is no, and in this blog post we will explore how using a detour through the theory of algebras will help us settle this question!

In 1941, Kurosh formulated the following question. Suppose that $F$ is a field, $A_F$ is an associative $F$ algebra (not assuming a unit) and that $A$ is finitely generated. An element $a\in A$ is said to be nilpotent if $\exists n\geq 1 \,\,a^n=0$, and an algebra is called a nilalgebra if all of its elements are nilpotent. The Kurosh problem is

Kurosh nilalgebra problem: Is every finitely generated nilalgebra finite dimensional?

Kurosh noticed that if there is a counterexample to this question for a field of positive characteristic, then there is a counterexample to the Generalized Burnside Problem. Here is the argument for that.

Theorem: If there is a counterexample to the Kurosh problem, there is counterxample to the generalized Burnside problem.
 [Proof]
Suppose that there is some finitely generated infinite-dimensional nilalgebra over $F$ where $\mathrm{char}(F)=p>0$. Let $A=\langle a_1,\ldots, a_m\rangle$ be such an example. Let $\hat{A}=A\oplus F\cdot 1$ be the unital hull of $A$: the algebra you get by adding a unit. (Since $A$ was nil, it couldn't possibly have had a unit to begin with!) Now notice that for all $a\in A$, $1+a$ is invertible since $1-a+a^2-a^3+\cdots$ is a finite sum and an inverse. Thus $1+a\in G(\hat A)$, the group of units of $\hat A$. Consider the subgroup of the group of units
$$G=\langle 1+a_1,\ldots,1+a_m\rangle\subset 1+A\subset G(\hat{A}).$$
Now every element in $1+A$ is torsion: we know there is some $n(a)$ where $a^{n(a)}=0$. Choose $k$ so that $p^k\geq n(a)$. Then $$(1+a)^{p^k}=1+a^{p^k}=1$$ since we are in characteristic $p$. Therefore $G$ is a finitely generated torsion group. If we can show it is infinite, we have a counterexample to the Generalized Burnside Problem.

Suppose to the contrary that $|G|=d$. Let $g_1\ldots g_d$ be a product of elements of $G$. Then $\{1,g_1,g_1g_2,\ldots,g_1\ldots g_d\}$ is a set of $d+1$ elements, and by the pigeonhole principle two of the elements must coincide: say $g_1\ldots g_i=g_1\ldots g_j$ $(j>i)$. Then $g_{i+1}\ldots g_j=1$. So we can remove a segment from the original word $g_1\ldots g_d$ without changing the group element it represents. In particular any element of $G$ is a product of $<d$ generators (we don't need inverses because the group is torsion).
In other words,
$$\forall g\in G\,\, g=(1+a_{i_1})\cdots (1+a_{i_k})\,\,\,\,(k<d)$$
But now consider an arbitrary product of $d$ generators of $A$: $a_{i_1}\ldots a_{i_d}$. Then
$$(1+a_{i_1})\cdots (1+a_{i_d})=(1+a_{j_1})\cdots(1+a_{j_k})\,\,\,\, k<d.$$
Now expanding this out, we see that $a_{i_1}\ldots a_{i_d}$ is a linear combination of products of generators of length $<d$. This implies $A$ is finite dimensional, which is a contradiction. $\Box$

So it now suffices to find a counterexample to the Kurosh problem. We begin with some graded algebra conventions. Let $F\langle X\rangle$ be the free associative algebra on a finite alphabet $X=\{x_1,\ldots ,x_m\}$. This is graded by length of words:
$$F\langle X\rangle =F\cdot 1+F\langle X\rangle_1+F\langle X\rangle_2+\cdots$$ .
 We say a subspace $H\subseteq F\langle X\rangle$ is graded if $H=\sum_i(H\cap F\langle X\rangle_i)$. If $R$ is a graded subspace, we can form the quotient algebra $\langle X\,|\, R=(0)\rangle$. Then since the ideal generated by $R$, $I=\mathrm{id}(R)$, is also graded, the factor algebra $$A=F\langle X\rangle/I=F\cdot 1+A_1+A_2+\cdots$$ is graded as well. (Note we assume all relations have degree $\geq 2$.)

Definition: Given a graded vector space $V=\oplus_{i\geq 0} V_i$ in which each graded summand is finite dimensional, define the Hilbert series $H_V(t)=\sum_{i\geq 0} (\mathrm{dim} V_i)t^i$. Note this is a formal power series.

We can order formal power series lexicographically by coefficients.

Proposition (Golod-Shafarevich): In the situation above, $$H_A(t)(1-mt+H_R(t))\geq 1,$$ where the comparison is of formal power series.

We will come back to the proof of this proposition at the end of the post. According to Zelmanov, it was given to Golod as a homework problem by Shafarevich!

Now, suppose that the proposition is true, and moreover suppose that we can find a $t_0$ with $0<t_0<1$ such that

1. $H_R(t_0)$ converges.
2. $1-mt_0+H_R(t_0)<0$.

Then the above proposition shows that $H_A(t_0)$ does not converge, so that $A$ must be infinite. (The formal inequality implies the numerical inequality when both sides converge.)

The construction of a finitely generated nilalgebra which is infinite dimensional:

Let $F$ be a countable field. Then the free algebra on $X$ without identity is also countable:
$$F_0\langle X\rangle =\{f_1,f_2,\ldots,\}.$$
Let $d_1=2$. Let $d_2>\mathrm{deg}(f_1^{d_1})$, and $d_3>\mathrm{deg}(f_2^{d_2})$ etc. Let $R$ be the set of homogeneous components of $f_i^{d_i}$. By choice of the $d_i$'s, every degree occurs no more than once.

Therefore $H_R(t)\leq t^2+t^3+\cdots$, and so $H_R(t)$ converges when $0<t<1$. In order to satisfy the criterion 2. above, we need $1-mt_0+H_R(t_0)<0$, which will be satisfied if
$1-mt_0+t_0^2+t_0^3+\cdots<0$ for some $0<t_0<1$. This is an easy precalculus exercise!

So the algebra $A=\langle F_0\langle X\rangle\,|\, R=(0)\rangle$ is infinite dimensional. Moreover it is nil by construction. Every element of $F_0\langle X\rangle$ has a power which is trivial.

Returning to the proof of the Golod-Shafarevich inequality:

Let $r_i=\mathrm{dim}(R_i), \mathrm{dim}(A_i)=a_i$ and, letting $I=\mathrm{id}(R)$, $b_i=\dim(I_i)$. Note that $a_i+b_i=\mathrm{dim} F_0\langle X\rangle_i=m^i$. The Golod-Shafarevich inequality can now be rewritten as
$$a_n-ma_{n-1}+\sum_{i+j= n} a_ir_j\geq 0$$

We use the following basic observation: $I\subseteq XI+RF\langle X\rangle$. This follows since a general element of $I$ is a linear combination of elements of the form $u_iRv_i$. If $R$is not at the left of the word, then $u_iRv_i\in XI$. Otherwise, it is in $RF\langle X\rangle$. Now choose a complementary graded subspace $S$ so that $F\langle X\rangle=I+S$. Then $\mathrm{dim}(S_i)=a_i$. Moreover, we can now say
$$I\subseteq XI+RS$$
Thus $b_n\leq mb_{n-1}+\sum_{i+j=n}r_ia_j$, which is $$(m^n-a_n)\leq m(m^{n-1}-a_{n-1})+\sum_{i+j=n}r_ia_j,$$
which is equivalent to the desired inequality.