algebra – Page 2 – mathstoshare

Sums of Squares – Part 1: Optimization

About a year ago I had the pleasure of having a number of conversations with Abhishek Bhardwaj about the area of mathematics his PhD is on. This pair of posts is based on the fond memories I have of these conversations. Part two can be found here.

Optimization and Summing Squares

Optimization is a huge area of both pure and applied mathematics. Many questions and problems can be reduced to finding the minimum or maximum value of some function. That is we have a function \(f : \mathbb{R}^n \to \mathbb{R}\) and we wish to find the number \(\lambda\) such that

\(\lambda = \min \{ f(x_1,\ldots, x_n) \mid (x_1,\ldots, x_n) \in \mathbb{R}^n \}\),

\(\lambda = \max \{ f(x_1,\ldots, x_n) \mid (x_1,\ldots, x_n) \in \mathbb{R}^n \}\).

By considering the function \(-f\) we can reduce finding the maximum of \(f\) to finding the minimum of another function. Minimizing a function isn’t always easy. Even when the function \(f\) is a relative simple function such as a polynomial, it can be a very difficult problem.

A different way of thinking about the problem of minimizing the function \(f\), is to instead think about the function \(f – \lambda\) were \(\lambda\) is a real number. The minimum of \(f\) is the largest value of \(\lambda\) such that the function \(f – \lambda\) is non-negative for all values \(x \in \mathbb{R}^n\). Thus we have a reduced our optimization problem into the problem of working out for which values of \(\lambda\) is the function \(f-\lambda\) non-negative.

An example

Suppose our function \(f\) was the following function that takes in two variables

\(f(x,y) = 2x^2 + 4y^2-4xy-4x+4y+7\).

To minimize this function we can look at the function \(g = f – \lambda\) which is equal to

\(g(x,y) = 2x^2 + 4y^2-4xy-4x+4y+7 – \lambda\).

We wish to work for which values of \(\lambda\) is this function \(g\) non-negative. By doing the following algebraic manipulations we can rewrite \(g\) like so

\(g(x,y) = (x^2-2x+1)+(x^2+4y^2+1-4xy-2x+4y)+5-\lambda \),

which is in turn equal to

\(g(x,y) = (x-1)^2+(-x+2y+1)^2 +(5-\lambda)\)

Since \((x-1)^2\) and \((-x+2y+1)^2\) are both squares of real numbers, they are both non-negative. Furthermore at the point \((x,y) = (1,0)\), we have that \((x-1)^2+(-x+2y+1)^2=0\). Thus \(g\) is non-negative if and only if \((5-\lambda) \ge 0\), that is if and only if \(\lambda \le 5\). Thus we can conclude that the minimum of \(f\) is \(5\).

Sums of Squares

Note that the number \(5-\lambda\) can be written as \((\sqrt{5-\lambda})^2\) if and only if \(\lambda \ge 5\). Thus, in the above example we have that \(g\) is non-negative if and only if \(g\) can be written as a sum of squares. That is \(g\) is non-negative if and only if \(g\) can be written as \(\sum_{i=1}^n h_i^2\) for some polynomials \(h_1, h_2, \ldots, h_n\).

In general, if a polynomial can be written as a sum of squares of other polynomials, then the polynomial must be non-negative. A natural question to ask is if every non-negative polynomial can be written as a sum of squares. This would make our optimization problem a lot easier. To minimize \(f\), we can check for which values of \(\lambda\) can \(f-\lambda\) be written as a sum of squares.

This question of whether every non-negative polynomial can be written as a sum of squares was answered in the negative by David Hilbert in 1888. However, Hilbert’s proof was non-constructive, it didn’t give an explicit example of such a polynomial. The proof only showed that such polynomials exist out there somewhere. It took nearly nearly 80 years for the first explicit example to be given by the mathematician Theodore Motzkin in 1967. We will take a look at Motzkin’s polynomial in the next blog post.

The Outer Automorphism of S6

This blog post is about why the number 6 is my favourite number – because the symmetric group on six elements is the only finite permutation group that contains an outer automorphism. In the post we will first look at why there are no other symmetric groups with outer automorphisms and then we will define an outer automorphism of \(S_6\).

Inner and Outer Automorphisms

If \(G\) is any group, then we can construct a new group \(\text{Aut}(G)\) consisting of all bijective group homomorphism \(\phi : G \to G\). This set forms a group under function composition. There is a natural map from \(G\) to \(\text{Aut}(G)\). A group element \(g \in G\) is taken to the function \(\gamma_g : G \to G\) given by \(\gamma_g(h) = ghg^{-1}\). Thus \(\gamma_g\) is conjugation by \(g\).

The kernel of \(g \mapsto \gamma_g\) is called the center of \(G\) and is denoted by \(Z(G)\). That is \(Z(G)\) is the subgroup consisting of group elements that commute with every other group element. The image of this map is denoted by \(\text{Inn}(G) \subseteq \text{Aut}(G)\). An automorphism which is in \(\text{Inn}(G)\) is called an inner automorphism. One can check that the subgroup of inner automorphisms is a normal subgroup. Indeed if we have a group element \(g \in G\) and an automorphism \(\phi \in \text{Aut}(G)\), then \(\phi \circ \gamma_g \circ \phi^{-1} = \gamma_{\phi(g)}\). Thus we can form the quotient \(\text{Aut}(G)/\text{Inn}(G)\) which we will call the outer automorphisms of \(G\) and denote by \(\text{Out}(G)\).

Thus the inner automorphisms of \(G\) are those which come from \(G\) in the form of conjugation. The outer automorphisms of \(G\) are equivalence classes of all the automorphisms of \(G\). Two automorphisms \(\phi, \phi’\) are equivalent in \(\text{Out}(G)\) if there is an inner automorphism \(\gamma_g\) such that \(\gamma_g \circ \phi = \phi’\).

The Symmetric Group

For a natural number \(n \in \mathbb{N}\), \(S_n\) will denote the group of permutations of the set \(\{1,2,\ldots,n\}\). Any permutation \(\sigma \in S_n\) can be written as product of disjoint cycles which we will call its cycle type. For instance, if \(n=5\) and \(\sigma(1)=3\), \(\sigma(2)=5\), \(\sigma(3)=4\), \(\sigma(4)=1\) and \(\sigma(5)=2\), then \(\sigma\) can be written in cycle notation as \((1,3,4)(2,5)\). Cycle notation is very useful for describing conjugation in \(S_n\). If we have two permutations \(\sigma, \tau \in S_n\) and we know the cycle notation for \(\sigma\), then the cycle notation for \(\tau \sigma \tau^{-1}\) can be derived by applying \(\tau\) to every entry in the cycle notation of \(\sigma\). For instance, with \(\sigma = (1,3,4)(2,5)\), we have

\(\tau(1,3,4)(2,5)\tau^{-1} = (\tau(1),\tau(3),\tau(4))(\tau(2),\tau(5))\).

To see why this result about conjugation is true, note the following. If \(\sigma(i)=j\) for some \(i,j \in \{1,2,\ldots,n\}\), then

\((\tau\sigma\tau^{-1})\tau(i)=\tau(\sigma(\tau^{-1}(\tau(i))))=\tau(\sigma(i))=\tau(j)\).

Thus two permutations \(\sigma, \sigma’\) are conjugate to one another if and only if \(\sigma\) and \(\sigma’\) have the same cycle type (ie they have the same number of cycles of any given size). This implies that for \(n \ge 3\), the centre of \(S_n\) must be trivial as for any non-identity \(\sigma \in S_n\), there is at least one other element of the same cycle type. Hence the map \(\sigma \mapsto \gamma_\sigma\) from \(S_n\) to \(\text{Aut}(S_n)\) is injective for \(n \ge 3\).

Counting Conjugacy Classes

Before constructing an outer automorphism for \(S_6\), we will see why such a map is special. In particular we will learn that \(\text{Aut}(S_n)\) consists entirely of inner automorphism for \(n \neq 6\). The argument is based off studying the size of different conjugacy classes in \(S_n\). This is important because if \(\phi\) is an automorphism of \(S_n\) and \(\sigma,\sigma’ \in S_n\) are two permutations, then \(\sigma\) is conjugate to \(\sigma’\) if and only if \(\phi(\sigma)\) is conjugate to \(\phi(\sigma’)\).

In \(S_n\) we know that two elements are conjugate if and only if they have the same cycle type. We can use this to count the size of different conjugacy classes of \(S_n\). In particular the number of permutations with \(n_k\) cycles of size \(k\) for \(k = 1,2,\ldots, n\) is

\(\displaystyle \frac{\displaystyle n!}{\displaystyle \prod\limits_{k=1}^n n_k! k^{n_k}}\).

The transpositions \((j,k)\) for \(1 \le j < k\le n\) generate \(S_n\) and form a conjugacy class which we call \(T\). For any automorphism \(\phi \in \text{Aut}(S_n)\) , the set \(\phi(T)\) must be a conjugacy class that is also of size \(| T | = n(n-1)/2\). Since automorphism preserve order, the elements of \(\phi(T)\) must all be of order two. Thus the cycle type of the conjugacy class \(\phi(T)\) must contain only cycles of size two or size one. Also there must be an odd number of two cycles. If there was an even number of two cycles, then we would have that \(\phi(T)\) is contained in the subgroup \(A_n \subseteq S_n\). However this would imply that \(\phi(S_n) \subseteq \phi(A_n)\) which contradicts the fact that \(\phi : S_n \rightarrow S_n\) is a bijection. Thus the following lemma implies that \(\phi(T)=T\) when \(n \neq 6\).

Lemma: Fix \(n \neq 6\) and an odd number \(k\) such that \(k > 1\) and \(2k \le n\). Let \(m_k\) denote the number of permutations \(\sigma \in S_n\) which have \(k\) cycles of size two and \(n-2k\) cycles of size one, then \(m_k \neq n(n-1)/2\).

Proof: This claim can be manually checked for \(n < 6\). For \(n > 6\), assume in order to get a contradiction that \(m_k = \frac{n(n-1)}{2}\). Note that \(m_k\) is equal to \(\frac{n!}{k! 2^k(n-2k)! 1^{n-2k}}=\frac{n!}{k! (n-2k)! 2^k}\). Thus we have \(\frac{n(n-1)}{2} = \frac{n!}{k!(n-2k)!2^k}\) and hence

\(2^{k-1} = \frac{(n-2)(n-3)\ldots(n-2k+1)}{k!}\).

Now if \(k \ge 5\), then \((n-4)(n-5)\ldots(n-2k+1)\) is a product of at least \(k\) consecutive integers and hence divisible by \(k!\) (see here). Thus

\(2^{k-1} = \frac{(n-2)(n-3)\ldots(n-2k+1)}{k!} = (n-2)(n-3)\frac{(n-4)(n-5)\ldots(n-2k+1)}{k!}\)

and hence \(\frac{(n-2)(n-3)\ldots(n-2k+1)}{k!}\) is divisible by an odd number other than one (either \(n-2\) or \(n-3\)). Thus \(\frac{(n-2)(n-3)\ldots(n-2k+1)}{k!}\) cannot be a power of \(2\), contradicting the above equation.

When \(k = 3\), the above equation becomes:

\(4= \frac{(n-2)(n-3)(n-4)(n-5)}{3!} = (n-2)\frac{(n-3)(n-4)(n-5)}{3!} = \frac{(n-2)(n-3)(n-4)}{3!}(n-5)\).

Thus if \(n\) is odd, \(n-2\) is an odd number other than \(1\) that divides 4, a contradiction. If \(n\) is even, then since \(n > 6\), \(n-5\) is an odd number other than \(1\) that divides \(4\), which is again a contradiction. Thus we cannot have any case when \(m_k = \frac{n(n-1)}{2}\).

\(S_n\) does not have an outer automorphism if \(n \neq 6\)

With the above lemma we can now prove that all the automorphism of \(S_n\) for \(n \neq 6\) are inner. First note that the only automorphism of \(S_2 = \{ \text{id}, (12)\}\) is the identity which is an inner automorphism. When \(n \ge 3\), the map \(\sigma \mapsto \gamma_\sigma\) from \(S_n\) to \(\text{Aut}(S_n)\) is injective. Thus there are exactly \(n!\) inner automorphisms of \(S_n\). We will show that for \(n \neq 6\) there are exactly \(n!\) automorphisms. Hence there can be no outer automorphisms.

Let \(\phi\) be an automorphism of \(S_n\). The symmetric group \(S_n\) is also generated by the \(n-1\) transpositions \(\sigma_i = (i,i+1)\) (for \(i =1, \ldots, n-1\)). By the previous lemma we know that if \(n \neq 6\), then each \(\phi(\sigma_i)\) must be a transposition \((j_i,k_i)\) for some \(j_i, k_i \in \{1,\ldots, n\}\) such that \(j_i \neq k_i\). As the collection \(\sigma_1,\ldots,\sigma_{n-1}\) generates \(S_n\), the automorphism \(\phi\) is determined by the transpositions \(\phi(\sigma_i)= (j_i,k_i)\). We will now show that there are exactly \(n!\) choices for these transpositions.

Since \(\sigma_1\sigma_{2} = (1,2,3)\), we know that \(\phi(\sigma_1)\phi(\sigma_2) = (j_1,k_1)(j_2,k_2)\) must be a three cycle. Thus one of \(j_2,k_2\) must be equal to one of \(j_1,k_1\) and the other must be distinct. By relabeling if necessary, we will require that \(k_1=j_2\) and \(j_1 \neq k_2\). Thus there are \(n\) choices for \(j_1\), \(n-1\) choices for \(k_1=j_2\) and \(n-2\) choices for \(k_2\). This gives us \(n(n-1)(n-2)\) choices for the first two transpositions. Continuing in this manner, we note that \(\sigma_1\sigma_3 = (1,2)(3,4)\) and \(\sigma_2\sigma_3 = (2,3,4)\), we get that one of \(j_3,k_3\) is equal to one of \(k_2\) and the other one is distinct from \(j_1,k_1=j_2,k_2\), thus giving us \(n-3\) choices for the third transposition. In general we will have that \(\sigma_{i-1}\sigma_i\) is a three cycle and \(\sigma_l\sigma_i\) is a pair of disjoint two cycles if \(l < i-1\). Thus one can show inductively that there are \(n-i\) choices for the transposition \(\phi(\sigma_i)\). Hence there are \(n(n-1)(n-2)\ldots 1 = n!\) choices for all the transpositions \(\phi(\sigma_i)\) and hence \(n!\) choices for \(\phi\). Thus, if \(n \neq 6\), all automorphisms of \(S_n\) are inner.

The outer automorphism of \(S_6\).

The key part of showing that \(S_n\) didn’t have any outer automorphisms when \(n \neq 6\) was showing that any automorphism must map transpositions to transpositions. Thus to find the outer automorphism of \(S_6\) we will want to find an automorphism that does not preserve cycle type. In particular we will find one which maps transpositions to the cycle type \((a,b)(c,d)(e,f)\). There are \(\frac{6!}{3!2^3} = 15\) such triple transpositions which is exactly \(\frac{6\cdot 5}{2}\) – the number of single transpositions.

The outer automorphism, \(\psi\), will be determined by the values it takes on \(\sigma_1,\sigma_2,\sigma_3,\sigma_4\) and \(\sigma_5\) (where again \(\sigma_i = (i,i+1)\)). Each of these transpositions will get to a different triple transposition \((a,b)(c,d)(e,f)\). To extend \(\psi\) to the rest of \(S_6\) it suffices to check the Coxeter relations \(\psi(\sigma_k)^2 = (\psi(\sigma_i)\psi(\sigma_{i+1}))^3 = (\psi(\sigma_i)\psi(\sigma_j))^2=\text{id}\) for \(k = 1,2,3,4,5\), \(i =1,2,3,4\) and \(j \ge i+2\).

The relation \(\psi(\sigma_k)^2=\text{id}\) will hold for any triple transposition \(\psi(\sigma_k)\). The other relations are a bit trickier. If we have two triple transpositions \(\tau = (a,b)(c,d)(e,f)\) and \(\tau’ = (a’,b’)(c’,d’)(e’,f’)\), then \(\tau\tau’\) will be a product of two three cycles if none of the transpositions of \(\tau\) is a transposition of \(\tau’\). If \(\tau\) and \(\tau’\) share exactly one transposition, then \(\tau\tau’\) is a product of two two cycles. If \(\tau\) and \(\tau’\) share two or more transpositions they must actually be equal and hence \(\tau\tau’\) is the identity.

With this in mind, one can verify that following assignment extends to a valid group homomorphism from \(S_6\) to \(S_6\):

\(\psi(\sigma_1) = (1,2)(3,4)(5,6)\),
\(\psi(\sigma_2) = (1,3)(2,5)(4,6)\),
\(\psi(\sigma_3) = (1,5)(2,6)(3,4)\),
\(\psi(\sigma_4) = (1,3)(2,4)(5,6)\),
\(\psi(\sigma_5) = (1,6)(2,5)(3,4)\).

We now just need to justify that the group homomorphism \(\psi\) is an automorphism. Since \(S_6\) is a finite group, \(\psi\) is a bijection if and only if \(\psi\) is an injection. Recall that only normal subgroups of \(S_6\) are the trivial subgroup, \(A_6\) and \(S_6\). Thus to prove injectivity of \(\psi\), it suffices to show that \(\psi(\tau) \neq \text{id}\) for some \(\tau \in A_6\). Indeed \(\psi(\sigma_1\sigma_3) = (1,6)(2,5) \neq \text{id}\) as required. Thus we have our outer automorphism!

This isn’t the most satisfying way of defining the outer automorphism as it requires using the generators of the symmetric group. There are many more intrinsic ways to define this outer automorphism which will hopefully be the topic of a later blog post!

References

The proof I give that for \(n \neq 6\), the group \(S_n\) has no outer automorphisms is based off the one given in this paper On the Completeness of Symmetric Group.

Combing groups

Two weeks ago I gave talk titled “Two Combings of \(\mathbb{Z}^2\)”. The talk was about some material I have been discussing lately with my honours supervisor. The talk went well and I thought it would be worth sharing a written version of what I said.

Geometric Group Theory

Combings are a tool that gets used in a branch of mathematics called geometric group theory. Geometric group theory is a relatively new area of mathematics and is only around 30 years old. The main idea behind geometric group theory is to use tools and ideas from geometry and low dimensional topology to study and understand groups. It turns out that some of the simplest questions one can ask about groups have interesting geometric answers. For instance, the Dehn function of a group gives a natural geometric answer to the solvability of the word problem.

Generators

Before we can define what a combing is we’ll need to set up some notation. If \(A\) is a set then we will write \(A^*\) for the set of words written using elements of \(A\) and inverses of elements of \(A\). For instance if \(A = \{a,b\}\), then \(A^* = \{\varepsilon, a,b,a^{-1},b^{-1},aa=a^2,abb^{-1}a^{-3},\ldots\}\) (here \(\varepsilon\) refers to the empty word). If \(w\) is a word in \(A^*\), we will write \(l(w)\) for the length of \(w\). Thus \(l(\varepsilon)=0, l(a)=1, l(abb^{-1}a^{-3})=6\) and so on.

If \(G\) is a group and \(A\) is a subset of \(G\), then we have a natural map \(\pi : A^* \rightarrow G\) given by:

\(\pi(a_1^{\pm 1}a_2^{\pm 1}\ldots a_n^{\pm 1}) = a_1^{\pm 1}\cdot a_2^{\pm 1} \cdot \ldots \cdot a_n^{\pm 1}\).

We will say that \(A\) generates \(G\) if the above map is surjective. In this case we will write \(\overline{w}\) for \(\pi(w)\) when \(w\) is a word in \(A^*\).

The Word Metric

The geometry in “geometric group theory” often arises when studying how a group acts on different geometric spaces. A group always acts on itself by left multiplication. The following definition adds a geometric aspect to this action. If \(G\) is a group with generators \(A\), then the word metric on \(G\) with respect to \(A\) is the function \(d_G : G \times G \rightarrow \mathbb{R}\) given by

\(d_G(g,h) = \min \{ l(w) \mid w \in A^*, \overline{w} = g^{-1}h \}.\)

That, is the distance between two group elements \(g,h \in G\) is the length of the shortest word in \(A^*\) we can use to represent \(g^{-1}h\). Equivalently the distance between \(g\) and \(h\) is the length of the shortest word we have to append to \(g\) to produce \(h\). This metric is invariant under left-multiplication by \(G\) (ie \(d_G(g\cdot h,g\cdot h’) =d_G(h,h’)\) for all \(g,h,h’ \in G\)). Thus \(G\) acts on \((G,d_G)\) by isometries.

Words are Paths

Now that we are viewing the group \(G\) as a geometric space, we can also change how we think of words \(w \in A^*\). Such a word can be thought of as discrete path in \(G\). That is we can think of \(w\) as a function from \(\mathbb{N}\) to \(G\). This way of thinking of \(w\) as a discrete path is best illuminated with an example. Suppose we have the word \(w = ab^2a^{-1}b\), then

\(w(0) = e,\)
\(w(1) = \overline{a}\)
\(w(2) = \overline{ab}\)
\(w(3) = \overline{ab^2}\)
\(w(4) = \overline{ab^2a^{-1}}\)
\(w(5) = \overline{ab^2a^{-1}b}\)
\(w(t) = \overline{ab^2a^{-1}b},\) \(t \ge 5\).

Thus the path \(w : \mathbb{N} \rightarrow G\) is given by taking the first \(t\) letters of \(w\) and mapping this word to the group element it represents. With this interpretation of word in \(A^*\) in mind we can now define combings.

Combings

Let \(G\) be a group with a finite set of generators \(A\). Then a combing of \(G\) with respect to \(A\) is a function \(\sigma : G \rightarrow A^*\) such that

For all \(g \in G\), \(\overline{\sigma_g} = g\) (we will write \(\sigma_g\) for \(\sigma(g))\).
There exists \(k >0\) such that for all \( g, h \in G\) with \(g \cdot \overline{a} = h\) for some \(a \in A\), we have that \(d_G(\sigma_g(t),\sigma_h(t)) \le k\) for all \(t \in \mathbb{N}\).

The first condition says that we can think of \(\sigma\) as a way of picking a normal form \(\sigma_g \in A^*\) for each \(g \in G\). The second condition is a bit more involved. It states that if the group elements \(g, h \in G\) are distance 1 from each other in the word metric, then the paths \(\sigma_g,\sigma_h : \mathbb{N} \rightarrow G\) are within distance \(k\) of each other at any point in time.

An Example

Not all groups can be given a combing. Indeed if we have a combing of \(G\), then the word problem in \(G\) is solvable and the Dehn function of \(G\) is at most exponential. One group that does admit a combing is \(\mathbb{Z}^2 = \{(m,n) \mid m,n \in \mathbb{Z}\}\). This group is generated by \(A = \{(1,0),(0,1)\} = \{\beta,\gamma\}\) and one combing of \(\mathbb{Z}^2\) with respect to this generating set is

\(\sigma_{(m,n)} = \beta^m\gamma^n\).

The first condition of being a combing is clearly satisfied and the following picture shows that the second condition can be satisfied with \(k = 2\).

A Non-Example

The discrete Heisenberg group, \(H_3\), can be given by the following presentation

\(H_3 = \langle \alpha,\beta,\gamma \mid \alpha\gamma = \gamma\alpha, \beta\gamma = \gamma\beta, \beta\alpha = \alpha\beta\gamma \rangle\).

That is, the group \(H_3\) has three generators \(\alpha,\beta\) and \(\gamma\). The generator \(\gamma\) commutes with both \(\alpha\) and \(\beta\). The generators \(\alpha\) and \(\beta\) almost commute but don’t quite as seen in the relation \(\beta\alpha = \alpha\beta\gamma\).

Any \(h \in H_3\) can be represented uniquely as \(\sigma_h = \alpha^p\beta^m\gamma^n\) for \(p,m,n \in \mathbb{Z}\). To see why such a representation exists it’s best to consider an example. Suppose that \(h = \overline{\gamma\beta\alpha\gamma\alpha\beta\gamma}\). Then we can use the fact that \(\gamma\) commutes with \(\alpha\) and \(\beta\) to push all \(\gamma\)’s to the right and we get that \(h = \overline{\beta\alpha\alpha\beta\gamma^3}\). We can then apply the third relation to switch the order of \(\alpha\) and \(\beta\) on the right. This gives us that that \(h = \overline{\alpha\beta\gamma\alpha\beta\gamma^3}=\overline{\alpha\beta\alpha\beta\gamma^4}\). If we apply this relation once more we get that \(h = \overline{\alpha^2\beta^2\gamma^5}\) and thus \(\sigma_h = \alpha^2\beta^2\gamma^5\). The procedure used to write \(h\) in the form \(\alpha^p\beta^m\gamma^n\) can be generalized to any word written using \(\alpha^{\pm 1}, \beta^{\pm 1}, \gamma^{\pm 1}\).

The fact the such a representation is unique (that is if \(\overline{\alpha^p\beta^m\gamma^n} = \overline{\alpha^{p’}\beta^{m’}\gamma^{n’}}\), then \((p,m,n) = (p’,m’,n’)\)) is harder to justify but can be proved by defining an action of \(H_3\) on \(\mathbb{Z}^3\). Thus we can define a function \(\sigma : H_3 \rightarrow \{\alpha,\beta,\gamma\}^*\) by setting \(\sigma_h\) to be the unique word of the form \(\alpha^p \beta^m\gamma^n\) that represents \(h\). This map satisfies the first condition of being a combing and has many nice properties. These include that it is easy to check whether or not a word in \(\{\alpha,\beta,\gamma\}^*\) is equal to \(\sigma_h\) for some \(h \in H_3\) and there are fast algorithms for putting a word in \(\{\alpha,\beta,\gamma\}^*\) into its normal form. Unfortunately this map fails to be a combing.

The reason why \(\sigma : H_3 \rightarrow \{\alpha,\beta,\gamma\}^*\) fails to be a combing can be seen back when we turned \(\overline{ \gamma\beta\alpha\gamma\alpha\beta\gamma }\) into \( \overline{\alpha^2\beta^2\gamma^5} \). To move \(\alpha\)’s on the right to the left we had to move past \(\beta\)’s and produce \(\gamma\)’s in the process. More concretely fix \(m \in \mathbb{N}\) and let \(h = \overline{\beta^m}\) and \(g = \overline{\beta^m \alpha} = \overline{\alpha \beta^m\gamma^m}\). We have \(\sigma_h = \beta^m\) and \(\sigma_g = \alpha \beta^m \gamma^m\). The group elements \(g\) and \(h\) differ by a generator. Thus, if \(\sigma\) was a combing we should be able to uniformly bound \(d_{H_3}(\sigma_g(t),\sigma_h(t))\) for all \(t \in \mathbb{N}\) and all \(m \in \mathbb{N}\).

If we then let \(t = m+1\), we can recall that

\(d_{H_3}(\sigma_g(t),\sigma_h(t)) = \min\{l(w) \mid w \in \{\alpha,\beta,\gamma\}^*, \overline{w} = \sigma_g(t)^{-1}\sigma_h(t)\}.\)

We have that \(\sigma_h(t) = \overline{\beta^m}\) and \(\sigma_g(t) = \overline{\alpha \beta^m}\) and thus

\(\sigma_g(t)^{-1}\sigma_h(t) = (\overline{\alpha\beta^m})^{-1}\overline{\beta^m} = \overline{\beta^{-m}\alpha^{-1}\beta^m} = \overline{\alpha^{-1}\beta^{-m}\gamma^{m}\beta^m}=\overline{\alpha^{-1}\gamma^{m}}.\)

The group element \(\overline{\alpha^{-1}\gamma^{m}}\) cannot be represented as a shorter element of \(\{\alpha,\beta,\gamma\}^*\) and thus \(d_{H_3}(\sigma_g(t),\sigma_h(t)) = m+1\) and the map \(\sigma \) is not a combing.

Can we comb the Heisenberg group?

This leaves us with a question, can we comb the group \(H_3\)? It turns out that we can but the answer actually lies in finding a better combing of \(\mathbb{Z}^2\). This is because \(H_3\) contains the subgroup \(\mathbb{Z}^2 \cong \langle \beta, \gamma \rangle \subseteq H_3\). Rather than using the normal form \(\sigma_h = \alpha^p \beta^m \gamma^n\), we will use \(\sigma’_h = \alpha^p \tau_{(m,n)}\) where \(\tau : \mathbb{Z}^2 \rightarrow \{\beta,\gamma \}^*\) is a combing of \(\mathbb{Z}^2\) that is more symmetric. The word \(\tau_{(m,n)}\) is defined to be the sequence of \(m \) \(\beta\)’s and \(n\) \(\gamma\)’s that stays closest to the straight line in \(\mathbb{R}^2\) that joins \((0,0)\) to \((n,p)\) (when we view \(\beta\) and \(\gamma\) as representing \((1,0)\) and \((0,1)\) respectively). Below is an illustration:

This new function isn’t quite a combing of \(H_3\) but it is the next best thing! It is an asynchronous combing. An asynchronous combing is one where we again require that the paths \(\sigma_h,\sigma_g\) stay close to each other whenever \(h\) and \(g\) are close to each other. However we allow the paths \(\sigma_h\) and \(\sigma_g\) to travel at different speeds. Many of the results that can be proved for combable groups extend to asynchronously combable groups.

References

Hairdressing in Groups by Sarah Rees is a survey paper that includes lots examples of groups that do or do not admit combings. It also talks about the language complexity of a combing, something I didn’t have time to touch on in my talk.

Combings of Semidirect Products and 3-Manifold Groups by Martin Bridson contains a proof that \(H_3\) is asynchornously combable. He actually proves the more general result that any group of the form \(\mathbb{Z}^n \rtimes \mathbb{Z}^m\) is asynchronously combable.

Thank you to my supervisor, Tony Licata, for suggesting I give my talk on combing \(H_3\) and for all the support he has given me so far.