Math 395: Geometric Group Theory

Third Friday: Free Subgroups and Sunshine

Posted on October 3, 2022 by John Eichelberger

Today’s lecture was held outside, in the lovely warmth and sunlight. We considered two ways to approach the following statement.

Claim. If $H \leq F_n$ , then $H$ is free.

A Geometric Group Theory Proof

Instead of proving this claim directly, we started with a more general statement.

Theorem. If $G \curvearrowright X$ freely and without edge inversions, then $G$ is free.

Proof. Let $T$ be a tree, and consider an action $G \curvearrowright T$ such that the action is free and without edge inversions. Let $\mathcal{F}$ be a fundamental domain of $T$ over this action.

If $\mathcal{F} \cap g \mathcal{F} \neq \emptyset$ , then this intersection must consist exactly of points $v$ such that $v$ is the midpoint of an edge. This follows from how we construct fundamental domains and the definition of a tree.

In particular, since trees have no cycles, the fundamental domain of a tree must consist of endpoints, edges, and half-edges. If endpoints or edges were shared between two fundamental domains, then $\mathcal{F}$ would no longer be a partition $T$ . However, if $\mathcal{F}$ contains a half-edge, then the other half of the half-edge must belong to some multiple $g\mathcal{F}$ , again since we’re partitioning all of $T$ . If the midpoint of the edge belonged to one or neither, we wouldn’t be able to multiply any $h\mathcal{F}$ to obtain the midpoint, so the midpoint $v$ must belong to exactly two fundamental domains.

We want to use these midpoints to prove that $G$ is acting freely. To that end, we’ll seek to show that $S$ generates a (free!) basis for $G$ . Symbolically, we want to show that for

$S = \{g \in G \ | \ \mathcal{F} \cap g\mathcal{F} \neq \emptyset\},$

that $\langle S \ | \ \rangle = G$ .

Since $G$ acts freely on $T$ , we expect any for $e \neq t \in T$ that $g \cdot t \neq t$ , and by definition of a fundamental domain for an action, we expect for $t \in \mathcal{F}$ and $g \neq e$ that $t \notin g\mathcal{F}$ . Therefore every $g \in G$ satisfies $\mathcal{F} \cap g\mathcal{F} \neq \emptyset$ , and so $S$ contains all of $G$ .

We additionally seek to show that no freely-reduced non-trivial word $s = s_1 \ldots s_n \in S$ is trivial in $T$ . Toward that goal, consider some midpoint on our tree, an arbitrary $v_0 \in V(T)$ . We may consider the path generated by “building up” to $s$ , or more precisely, the sequence of vertices generated by

$s_n v = v_1$

$s_{n-1}s_n v = v_2$

$\ldots$

$sv = v_n$

With these midpoints on our tree in mind, we can consider the unique reduced path generated by connecting $v_0$ to $v_1$ , $v_1$ to $v_2$ , and so on. We’ll name these paths $\gamma_1, \gamma_2$ , and so on. Trees have pretty rigid structure; we can take advantage of this structure in order to make some pretty rigorous statements about each $\gamma_i$ . Toward a contradiction, suppose that we have a loop, or more precisely that the same $v_i$ occurs more than once in the path from $v_1$ to $v_n$ . Since $T$ is a tree and thus contains no cycles, the loop implies we must have backtracked:

But we see that a backtrack implies that three separate fundamental domains all shared the same midpoint edge; this contradicts the definition of an edge midpoint. Instead, it must be the case that every non-trivial word in $S$ corresponds to a non-trivial action. Thus we know that freely-reduced non-trivial words in $S$ are non-trivial on $T$ , and so $S$ is indeed a basis of $G$ , and since our basis includes no relators, $G$ is free. $\square$

Our original claim, that subgroups of free groups are themselves free, follows as a corollary. In particular, if $G$ is free and $H \leq G$ , then $G$ and $H$ both act freely on the Cayley graph of $G$ . Since $H$ acts freely, $H$ is free. $\square$ .

A Topological Proof

For the second part of the lecture, we considered a topological proof of our original claim that subgroups of free groups are free.

Definition. Given a space $X$ and a point $p \in X$ , a fundamental group $\pi_1 (X, p)$ is the group formed by the equivalence class of loops that start at $p$ over the operation of concatenation.

Example. Consider the torus $\mathbb{T}$ , and some point $p \in \mathbb{T}$ . We have (at least) two loops, one given by the vertical circle in red, and one given by the horizontal circle in blue:

Fact. For any graph $\Gamma$ , it’s the case that $\pi_1(\Gamma)$ is free.

I have very little background in topology, but I think this relates to the idea of thinking of free groups as little “bouquets” of loops. In some sense, I suspect this is what it means to be a free group.

Definition. Let $X$ and $Y$ be spaces, with a map

$f: Y \to X$

such that $f$ is continuous, surjective, and locally homeomorphic. Then $Y$ covers, or is a cover of, the space $X$ .

Fact. For some spaces $X, Y$ where $Y$ is a cover of $X$ , $\pi_1(Y)$ satisfies $Y \trianglelefteq X$ , and every $H \leq Y$ corresponds to an open cover of $X$ . This property is known as Galois Correspondence.

We can use this assortment of facts and definitions to show that subgroups of free groups are free. For some $\Gamma$ , it’s the case that $F_n = \pi_1(\Gamma)$ . By Galois Correspondence, we know that any $H \leq F_n$ implies $H$ is a cover of $\Gamma$ , and so $\pi_1(\Gamma)$ must be free.

Posted in Uncategorized | 2 Comments

Third Wednesday: More Free Groups

Posted on September 30, 2022 by Horace Fusco

I’ll begin my second (!) blog post about free groups by recalling a proposition that cuts right to the heart of what a free group is.

Universal property. Let $S$ be a generating set. Then $F_S$ is the unique froups os that for any $G$ gnerated by $S$ there exists a unique homomorphism $f: F_s \to G$ such that the diagram below commutes.

This tells us that every group on some generating set is the surjected image of a free group, and hence we can think of the group as a quotient of that free group. This exactly what a group presentation is: in the set of relators we specify all the elements which normally generate (i.e. form a normally generated subgroup which is) the kernel of the map from $F_S \to G$ .

I’ll restate a puzzle which has to do with this fact: Prove that a group $G$ has a surjection to $\mathbb{Z}$ if and only if $G$ has a presentation in which the sum of the exponents on every relator is $0$ . I won’t spoil the puzzle for anyone who’s working on it but for a slightly cryptic hint you can read the following sentence backwards: STNEMELE HCUS GNINIAMER EHT YB TUO DOM.

Next up we address the following postponed theorem:

Theorem: For free groups given by generating sets $S$ and $T$ , we have $F_S \cong F_T$ if and only if $|S| = |T|$ .

The proof of this theorem relies on the observation that much of the difficulty in working with free groups comes from the lack of commutativity. A surprisingly effective way of dealing with this problem is to create an abelian quotient group by forcing elements which would be zero if the generators did commute into the kernel of a quotient map. To see this in rigorous terms we need a few definitions.

For elements $a, b \in G$ the element $[a,b] := aba^{-1}b^{-1}$ is called a commutator. The subgroup of G generated by the set of commutators is called the commutator subgroup and is denoted $[G:G] \in G$ . To see that this subgroup is normal, let $c_1 \ldots c_n \in [G:G]$ , where the $c_i$ are commutators. We must show that for all $g \in G$ , we have $g c_1 \ldots c_n g^{-1} = g c_1 g^{-1} g c_2 g^{-1} \ldots g c_n g^{-1} \in [G:G]$ . To do so we need only show $gc_ig^{-1} = g [a,b]g^{-1} \in [G:G]$ which we can do by writing this element as a product of commutators: $g [a,b]g^{-1} = [ga, b] [b, gb]$ . The resulting group $\overline{G} := G / [G:G]$ is called the ablianization of $G$ , and it is, as its name suggests, abelian.

We can now return to the question of settling the isomorphism classes of free groups. On the one hand, if $\abs{T} = \abs{S}$ , there exists a bijection between $S$ and $T$ which can be used to induce an isomorphism $\phi : F_S \to F_T$ . For the harder direction, we note that taking if $F_S \cong F_T$ , then their abelianizations must be isomorphic, $\overline{F_S} = \overline{F_T}$ , and those are much easier to understand. Namely,

$\overline{F_S} = \mathbb{Z}^{|S|}.$

And hence we find that under our assumptions $\mathbb{Z} ^{|S|} = \mathbb{Z}^{|T|}$ . Which is only true if $|S| = |T|$ . We can illustrate this fact in the finite case by noting that $\mathbb{Z}^n$ contains an isomorphic copy of $\mathbb{Z}$ , the quotient with which is $\mathbb{Z}^{n-1}$ . Performing successive mods of these subgroups will reduce $\mathbb{Z}^n$ to the identity after exactly $n$ steps, a fact which uniquely identifies this group with the integer $n$ , and prevents it from being isomorphic to $\mathbb{Z}^m$ for $m \neq n$ . The details are left to be sorted out.

We move now to the surprising fact that subgroups of finitely generated groups are not necessarily finitely generated. The proof is constructive, and it works by offering a subgroup of $F_2$ which is not finitely generated, namely

$S = \{ a^n b a^{-n} | n \in \mathbb{Z} \} \subseteq F_2.$

To see that $<S>$ is not finitely generated, we must show that no freely reduced word in is the identity. Towards a contradiction, suppose that

$s_1 \ldots s_n = e = (a^{k_1}b^{\pm 1}a^{-k_1})(a^{k_2}b^{\pm 1}a^{-k_2}) \ldots (a^{k_n}b^{\pm 1}a^{-k_n}).$

For the above to be true, there must be some sequence of cancellations that reduces the right hand expression to the identity, which means there is a pair of $b$ and $b^{-1}$ which are immediately adjacent except for the powers of $a$ which cancel with each other, and hence must be part of an expression of the form $(a^{k_i}b^{\pm 1}a^{-k_i}) (a^{k_i}b^{\mp 1}a^{-k_i})$ which in turn looks like $s_i s_i^{-1}$ in the original word, meaning that it was not freely reduced with respect to our generating set, contradicting our assumption that there is such a freely reduced word which equals the identity. We have shown that $<S> \cong F_S$ , which is the free group on countably many generators.

We only need to modify this argument slightly to conclude that $F_2$ has subgroups isomorphic to $F_n$ for every integer $n$ . Indeed take the generating set $\{ a^m b a^{-m} | -n \leq m \leq n \}$ .

To contrast with this surprising fact, we note that every quotient group of $F_n$ is finitely generated, since we can use the image of its generators under the natural surjection $\eta : F_n \to F_n / H$ , where the same idea holds in any finitely generated group. In practice this looks like using the “same” generators for the quotient group.

Since we’ve started down the path of analyzing subgroups of $F_n$ , and I’ve mentioned a surprising fact followed but an underwhelming fact, I’ll conclude the post by mentioning a surprising plan of attack on a somewhat reasonable fact. In choosing a subgroup of the free group $F_n$ , we have the freedom to choose its generators, but not to introduce any relators, this makes it seem that the resulting group, whatever the cardinality of a minimal generating set happens to be, should probably be free.

Theorem: If $H \subseteq F_n$ then $H$ is a free group.

This fact is true, but the proof is surprisingly difficult, it turns out that the key idea is to use a seemingly more difficult theorem that invokes the geometric structure of $F_n$ and its actions.

Theorem: A group $F$ acts freely on a tree $T$ without edge inversions if and only if that group is free.

The proof of the first theorem now becomes simple. We simply state that $F_n$ acts on the tree $\Gamma_{F_n, S}$ (without edge inversion), and therefore each of its subgroups $H$ act on $\Gamma_{F_n, S}$ , and indeed by the above theorem this makes $H$ free.

This is a beautiful result of the Cayley graph machinery we’ve seen so far. It raises another question about what it means when we find $F_3 \subseteq F_2$ , but the graph $\Gamma_{F_2, S}$ has degree four at every vertex whereas the the graph $\Gamma_{F_3, S}$ has degree six at every vertex. There certainly can’t be such a tree contained as a sub-tree of $\Gamma_{F_2, S}$ , but we do have a geometric object which is essentially a disjoint union of paths which we can treat as such a “sub-tree.” An illustration of this tree in red and orange is given below.

We take the subgroup generators $F_3 \cong < aba^{-1} , a^2 b a^{-2}, a^3 b a^{-3} > \subseteq F_2$ .

Here we can imagine that the tendrils drawn in blue are symmetrically extending in an identical manner at each vertex at the ends of the blue baths. The symmetries of this set of paths are exactly the symmetries of the tree of degree $6$ .

Posted in Uncategorized | 5 Comments

Week Three Monday : The Ping Pong Lemma and Free Groups in the Mathematical Wild

Posted on September 28, 2022 by Akash Ganguly

Monday’s class brought us back to a claim we made last Wednesday, before our fun Coxeter group excursion. MurphyKate noted that this problem showcased a few things: notably free groups being sneaky and hiding in places we might not expect, ‘peak geometric group theory’, and mathematicians’ eternal inability to name things properly.

With that, let’s get started!

Claim : Let $G = SL_2(\mathbb{Z})$ , and let $H \leq G$ generated by

we’ll call our first element l and the next r

We claim that $H \cong F_2$

How do we go about this? The tricky part about showing that our $S$ is a basis for $F_2$ comes in the second clause for a basis: that no nontrivial word in our basis will be trivial in the group.

We take a geometric approach! Seeing as $H$ is a subgroup of a linear group, we look at the action of $H$ on $\mathbb{R}^2$ through linear transformations. Let’s subdivide our plane into 4 sections with the lines $y=x$ and $y=-x$ and see how each element of $H$ moves these sections. Note that these sections are open!

To make this easier, let’s calculate what our elements do a given vector

With these, we can start to fill in our picture. Let’s look at what happens under the action of $l$ .

movement of sections of the plane under l

Note that everything gets pushed into the section we’re calling $x_l$ . Everything except for $x_{l^{-1}}$ , that is! Weird things happen with that section, and I’d encourage you guys to play around with random vectors in that section. Horace mentioned in class that it’s a good idea to look at the boundaries of our sections — this leads us to see that one boundary for $x_{l^-1}$ is fixed (the one that is along the x-axis), and our other one goes to $y=3x$ , which means that our new boundaries encapsulate many sections of our plane. Anyways, I think it is fine to not completely understand what happens with vectors in that area, as it is not integral to our proof. In fact, the much more important part is that every other section gets mapped into $x_l$ !

This is not a coincidence! We can fill out a table that captures all motion under our generators.

The main idea from this table is that $s(x_y)\subset x_s$ , for some $s$ in our generating set, as long as $s \not= y^{-1}$ .

It’s here where the value of looking at these as actions comes in. We want to show that any nontrivial freely reduced word in our basis is nontrivial in our group too, so this is equivalent to asking whether or not our nontrivial freely reduced word actually moved nothing.

Well, let’s look at such a word $w = w_1 ... w_{n-1}w_n$ . Let’s now pick a section of our plane for our word to act on. Since we’re given the choice, it’s important that we don’t pick our one ugly choice — that being $x_{w^{-1}}$ , as that’s the choice that messes everything up.

This gives us

$w(x_{w_n}) = w_1 ... w_{n-1}w_n(x_{w_n})$

With our handy table we see that, our point is now contained completely in $(x_{w_n})$

$w(x_{w_n}) = w_1 ... w_{n-1}(x_{w_n})$

We repeat this process

$w(x_{w_n}) = w_1 ... (x_{w_{n-1}})$

Note that we avoid the ugly case of two consecutive elements being inverses, as that would imply that our word was not freely reduced! Sweet! If we follow this process to completion we get that

$w(x_{w_n}) \subset x_{w_1}$

Here’s where the containment not being strict is helpful — it guarantees that something is moved! So our w is nontrivial and H really is isomorphic to $F_2$ !

That slick containment strategy was actually an application of the Ping Pong Lemma, which MurphyKate calls ‘peak geometric group theory’. It’s exploiting the action of a group and observing geometrically how it acts on that space to tell us something about the group itself! The Ping Pong Lemma as stated in class (it’s a little different in our book) is as follows:

Let $S = S \cup S^{-1} \subseteq G$ . If there exists disjoint open regions such that $s(x_p) \subset (x_s)$ for all $s \not= p^{-1}$ , then $\langle s \rangle \leq G$ is free.

This example was also especially powerful because it showed how free groups hide in some other groups. Very sneaky. Our good friend Jacques Tits also thought this was sneaky of them so he got angry and looked for more of these hidden free subgroups and proved the Tits Alternative. It states that every finitely generated linear group either has a free subgroup, or is virtually solvable. As I was in the process of writing this blog post, I realized that everyone in the class has had some experience with Galois Theory, so you guys will recall that a solvable group is one that has a derived series ending in the trivial group.

A derived series is a series of subgroups such that each consecutive subgroup is the commutator subgroup. Let’s look at the derived series of $D_6$ .

$D_6 \rhd \langle r \rangle \rhd e$

This series terminates in the trivial group so $D_6$ is solvable.

This is really crazy to me! It characterizes such a wide variety of groups!

We were actually supposed to see some more applications of the Ping Pong Lemma, but those were postponed to our next class. So stay tuned for next class where we’ll use the Ping Pong Lemma to discover the meaning of life and to solve all of our problems. Thank you for reading!

Posted in Uncategorized | 4 Comments

Week Two Friday: Reflections and Coxeter Groups

Posted on September 26, 2022 by Sam Hiken

Today, we had an exciting guest lecture by Dr. Kasia Jankiewicz, a professor at the University of California, Santa Cruz. Dr. Jankiewicz discussed reflections, which give us a geometric interpretation for elements of certain groups. For instance, (at least) half of the elements of the dihedral group of order $D_n$ can be interpreted as reflections of the regular $n$ -gon. Below is a summary of the topics Dr. Jankiewicz discussed.

Consider a reflection $r$ across a line $L$ in $\mathbb{R}^2$ :

Such a reflection brings a point $p \in \mathbb{R}^2$ to a point $r(p)$ on the other side of $L$ .

Similarly, in $\mathbb{R}^3$ we can consider a reflection over a plane $P$ :

More generally, in $\mathbb{R}^n$ there exists a reflection across any copy of $\mathbb{R}^{n-1}$ . Our goal for today is to look at groups generated by reflections.

Consider a regular pentagon on the plane. Let $r$ and $s$ be reflections across the lines $L_r$ and $L_s$ which intersect at angle $\pi / 5$ .

How do each of these reflections permute the vertices $\{ v_1,v_2,v_3,v_4,v_5\}$ ?

$r: v_1$ , $v_2$ ⟷ $v_5$ , $v_3$ ⟷ $v_4$ .

$s: v_3$ , $v_2$ ⟷ $v_4$ , $v_1$ ⟷ $v_5$ .

What does $rs$ do?

$rs: v_1$ ⟶ $v_2$ ⟶ $v_3$ ⟶ $v_4$ ⟶ $v_5$ ⟶ $v_1$ …

Therefore, $rs$ is a rotation by $\frac{2\pi}{5}$ about the center of the pentagon. Because we know $r$ and $rs$ generate $D_{10}$ , we can conclude that $r$ and $s$ generate $D_{10}$ as well, giving us the the group presentation:

$D_{10} = \langle r,s | r^2 = s^2 = (rs)^5 = e \rangle$

We can generalize the above conclusions. If $r$ and $s$ are reflections about lines intersecting at the angle $\frac{\pi}{n}$ , then $rs$ is a rotation about the intersecting point by angle $\frac{2\pi}{n}$ .

Let’s look at another group generated by reflections. Consider the real line. Let $r$ denote the reflection across $x = 0.5$ , and $s$ denote the reflection across $x = -0.5$ .

How do these reflections transform points on the line?

$r: 0$ ⟷ $1$ , $-1$ ⟷ $2$ , $-2$ ⟷ $3$ ,…

$s: 0$ ⟷ $-1$ , $1$ ⟷ $-2$ , $2$ ⟷ $-3$ ,…

In general, $r(x) = 1-x$ and $s(x) = -1-x$ . Composing $r$ and $s$ yields a translation across the real line:

$rs(x) = 1-(-1-x) = x+2$

In general, if $r$ and $s$ are reflections about non-intersecting lines $L_r$ and $L_s$ at distance $k$ from each other, then $rs$ is a translation by distance $2k$ orthogonal to those lines. We call the group generated by two such reflections the infinite dihedral group, denoted

$D_{\infty} = \langle r,s | r^2 = s^2 = e \rangle$

Note that the direction in which $rs$ shifts points on the line depends on the relative positions of $L_r$ and $L_s$ . If $L_r$ lies to the right of $L_s$ , then $rs(x)$ lies to the right of $x$ .

Now, let’s look at an example of a group generated by reflections in $\mathbb{R}^3$ . Consider the cube with corners $(\pm 1, \pm 1, \pm 1)$ . Let $r$ , $s$ , and $t$ be reflections across the planes $x = 0$ , $y = 0$ , and $z = 0$ respectively.

The planes $x = 0$ and $y = 0$ intersect at angle $\pi/2$ , so $rs$ is a rotation about the $x$ -axis by angle $\pi$ . This yields the following presentation of the group of symmetries of a cube:

$\langle r, s, t | r^2 = s^2 = t^2 = (rs)^2 = (st)^2 = (tr)^2 \rangle$

Note that, given the above abstract presentation alone, you may not be able to distinguish between generators that change the orientation of the cube and ones that preserve it.

Now, let’s consider another infinite group generated by reflections. Consider an equilateral triangle in $\mathbb{R}^2$ and reflections about the lines bordering its edges. We’ll say that three edges corresponding to the reflections $r$ , $s$ , and $t$ are colored red, blue, and green respectively. In the drawing below, the red, green, and blue edges lie along red, green, and blue lines:

The angle between the red and blue lines is $\pi / 3$ , so $(rs)^3 = e$ . When we perform a reflection along one edge, observe that the lines along which the other edges lie are rotated. The transformations of the equilateral triangle yielded by flipping along edges can form a group. For instance, if we consider the group generated by flipping across the edges $r$ and $s$ , we get six triangles forming a hexagon:

However, the group generated by $r$ , $s$ , and $t$ together gives a tessellation of the plane with equilateral triangles, yielding the following presentation:

$\langle r, s, t | r^2 = s^2 = t^2 = (rs)^3 = (st)^3 = (tr)^3 \rangle$

For a more detailed treatment of the above group, see chapter 2 of John Meier’s Groups, Graphs, and Trees. This group is an example of a triangle group, a group generated by reflections of a triangle across its edges. It is also an example of a Coxeter group!

Definition: A Coxeter group $W$ is a group with a presentation of the form:

$W = \langle s_1, s_2, ..., s_n | s_i^2, (s_i s_j)^{m_{i,j}} \rangle$

where $m_{i,j} = m_{j,i} \in \{ 2, 3, ...\} \cup \{ \infty \}$ . If we say $m_{i,j} = \infty$ , we mean that there is no relation of the form $(s_i s_j)^k$ for $k \in \mathbb{R}$ .

If you’re interested in learning more about the abstract geometric constructions described by Coxeter groups, see buildings, Coxeter complexes, the Davis complex, or Tits representations.

Here are a couple more neat facts that we briefly touched on regarding Coxeter groups:

All the data in a Coxeter group can be encoded in a labelled graph, whose vertices correspond to generators and whose edges are labelled by the finite $m_{i,j}$ s. In other words, if $(s_i s_j)^{m_{i,j}}$ is a relation in the presentation of a Coxeter group, there is an edge of weight $m_{i,j}$ between $s_i$ and $s_j$ . Note that, because $m_{i,j} = m_{j,i}$ for all $i,j$ , we don’t need to orient the edges of this graph.
Coxeter groups are linear, meaning any Coxeter group is isomorphic to a group of invertible matrices under matrix multiplication. It is not immediately apparent to me why this is the case, but it seems pretty neat.

Posted in Uncategorized | Tagged coxeter groups, reflections, triangle groups | 1 Comment

Second Wednesday: Free Groups

Posted on September 23, 2022 by Horace Fusco

Free groups are a wonderful source of examples, counterexamples, and play a crucial role in some pretty slick constructions. For instance, the famous Banach-Tarski paradox utilizes a construction which, at its heart, boils down to a fact about free groups, and that you can find a subgroup of the symmetries of $\mathbb{R}^3$ which is isomorphic to a free group.

We’ll begin the process of defining a free group. Let $S$ be some set. We define a word on $S$ as follows. Concatenate a finite sequence of elements of $S$ , formally raised to integral powers. For example if $S = { a , b}$ we may form the words $a, ab, a^2bb, aa^{-1}, abaab^{-10}a^{5}b^{65}b$ , and so on. Note we are really adding in the formal inverse of everything in $S$ , which can be neatly encapsulated in the expression $S = S \cup S^{-1}$ . Now we might have the feeling that these objects, namely the words on $S$ , could benefit from extra structure. For instance, the expression $aa$ looks a little clumsy, we would rather see this as $a^2$ . We will say that consecutive powers of the same sign can just be summed together for notational convenience. Furthermore, if we have the construction of a group as our end goal, then we want $aa^{-1}$ to collapse to some identity element. To this end we define the empty word, which is denoted $1$ , and which has the property that whenever it is concatenated to another word, it leaves that word unchanged.

We may now establish some rules governing equivalence among the words formed from $S$ . We allow ourselves to sum the powers of a single generator which appears in two consecutive positions in the string, where $ss^{-1} = 1$ for all $s \in S$ . We define a word to be freely reduced if it contains no sub strings $s s^{-1}$ for any $s \in S$ , and observe that every word can be simplified to a freely reduced word by sequentially cancelling substrings of this form. For instance the word $aabb^{-1}a^{-1}abb^{-1}a^{-1}a^{-1}$ reduces to the empty word $1$ after we cancel until there are no more strings available. It is a subtle point but the integrity of the group we are forming rests on the fact that every word reduces to a unique word regardless of which order available cancellations are made. Finally, we say two words are equivalent under $\sim$ if they each reduce to the same freely reduced word. We may now take the set $W$ of words on $S$ and form the equivalence classes $W/ \sim$ , which will be the ground set of our soon to be group.

Definition: The free group $F_S$ on some set $S$ is the ground set $W/ \sim$ with the operation of concatenation.

The closure and associativity properties of this group can be verified by inspection. The existence and good behavior of our identity elements can also be relatively checked. It is important to note here that the formation of equivalence classes modulo free reduction is absolutely essential for the group structure, since it is what guarantees that there are inverses for every element, following only from the definition that $s s^{-1} = 1$ for all $s \in S$ . One can compute said inverses by reversing the order of multiplication and negating powers, as is usually done.

Now that we have defined a free group, we should describe the simplest free group that really looks like a free group, namely the free group on the generators $S = { a, b}$ , or any other set of cardinality $2$ , which is often denoted $F_2$ . The freely reduced words here take the form $a^{k_1}b^{k_2}a^{k_3} … b^{k_n}$ , where the $k_i$ are integers such that $k_2, …, k_{n-1}$ are nonzero, and $k_1$ and $k_2$ may be zero to allow for every possible word shape. We’ll use this group as a running example to explain the definitions and theorems to follow.

The next step in our journey is to characterize the way in which the isomorphism class of a free group depends only on the cardinality of its generating set. We won’t be able to complete this project in this blog post alone, but it begins with the following definition.

Definition: A basis for a free group $F_s$ is a set of elements that generate $F_s$ such that no non-trivial word on the basis elements is trivial in $F_s$ .

Let’s unpack the second part of this definition. We will show that the sets ${a, a^2, b, c}$ and ${a, ab^2, c}$ are NOT bases for $F_2$ while the sets ${a, b, c}$ and ${a, ab, c}$ are. Both the non examples illustrate how a non-trivial word on some basis elements can be trivial in $F_2$ . For the first non basis, consider the relabelling $x = a, y = a^2, z = b, w = c$ , the word $x^{-2}y$ is non trivial with respect to this labelling, but when substituting to compute the value in $F_2$ , this word becomes $a^{-2} a^2 = 1$ . The second basis has this issue as well as the issue that it doesn’t generate $F_2$ since there is no way to write $b$ alone using only these elements.

We will state without proof a fact which will probably come up in later posts.

Theorem: Every basis of $F_n$ has $n$ elements. More generally, if $| X | = | S |$ , then $F_X \cong F_S$ for sets of any cardinality.

Now we can get closer (at least I suspect) to the heart of what a geometric group theorist thinks about when they think about free groups.

Theorem: The free group $F_n$ acts freely on some true $T$ .

To prove this theorem we take $T = T_{2n}$ and note that for some basis $S = {a, b }$ we have that the underlying graph of $\Gamma_{F_n, S}$ is $T_{2n}$ and note that groups act freely on their cayley graphs.

To back up the claim that $\Gamma_{F_n, S}$ does indeed have undirected graph $T_{2n}$ , we can note that elements of $F_2$ define paths through the Cayley graph, where reduced elements correspond to reduced paths, and furthermore we have defined $T_{2n}$ to be precisely a graph which is $2n$ regular and contains no cycles, meaning unique reduced paths between every pair of vertices.

For example, we pose the following outstanding drawing of the Cayley graph of $F_2$ . Note that unlike the graph for $\mathbb{Z}_2$ , the smaller blue edges do not meet up.

To see this graph in slightly more of its full glory.

With this image you can visualize how the group action of $F_2$ translates the Cayley graph. For instance, multiplication by $aba^{-1}$ takes the identity to the vertex at the end of the path specified below, where all the branches of the tree are along for the ride.

This is an opportunity to observe a subtle detail about how this group action works, namely that completing the action by successive actions does NOT drag the identity element along the specified path as one might inspect. Instead, the group action is defined by right multiplication so we can break down the action by $aba^{-1}$ as follows:

$aba^{-1} \cdot e = a \cdot (b \cdot (a^{-1} \cdot e)) = a \cdot (b \cdot a^{-1}) = a \cdot ba^{-1} = aba^{-1}$

Here we can track the identity vertex as it gets mapped to the vertex $aba^{-1}$ and note that it doesn’t follow the indicated path, instead moving first to $a^{-1}$ , next to $ba^{-1}$ and finally to $aba^{-1}$ .

If you want to hear some cool facts and constructions that involve free groups ask me after class some time because I have a few tucked away.

Posted in Uncategorized | 5 Comments

Week 2, Existence of Fundamental Domain and Some Applications

Posted on September 20, 2022 by Shuhang Xue

In this blog, we aim to show 1) the existence of fundamental domains, 2) fundamental domains in Cayley graphs, and 3) a one-to-one correspondence between the transversal of subgroups and components of a fundamental domain of subgroups.

1. Existence of Fundamental Domains

Last week, we introduced the notion of a fundamental domain of an action $G \curvearrowright \Gamma$ . To remind ourselves, I repeat the definition here.

Definition 1.1 If a group $G$ acts on a connected graph $\Gamma$ , then we say a subset of $\Gamma$ , denoted as $\mathcal{F}$ , is a fundamental domain of $G \curvearrowright \Gamma$ if the following three conditions are satisfied: 1) $\mathcal{F}$ is closed (in the topological sense), 2) the union $\bigcup_{g\in G} g\cdot \mathcal{F}=G$ , and 3) $\mathcal{F}$ is minimal meaning that no subsets of $\mathcal{F}$ satisfy 1) and 2).

Given this definition, we saw last week that we could construct fundamental domains of $\mathbb{Z}/6\mathbb{Z}$ on a hexagon. Indeed, fundamental domains are not unique, as we have seen from the very same example.

However, we would like to ask whether fundamental domains exist for any $G \curvearrowright \Gamma$ . At the first glance, it seems that we can naively start with some candidate $\mathcal{F}'$ such that condition 1) and 2) are satisfied. Then, we gradually shrink $\mathcal{F}'$ until the minimality condition 3) is satisfied. However, this may not work since there is no way to guarantee that the shrunk subset of $\mathcal{F}'$ is still closed.

Note that in the above example, if we start with the highlighted subset and performance the removing procedure, the minimal subset would not be closed. However, if one tries to take the closure, the minimality is not guaranteed again. There, we have to seek another way. Indeed, we state the existence of fundamental domains as a theorem. In its proof, we instead start with a minimal subgraph (warning: this is stronger than a subset!) that covers all vertices upon performing group actions, shown using Zorn’s Lemma. Then, we add some closed half-edges to cover all edges in a minimal fashion.

Theorem 1.2 If $G \curvearrowright \Gamma$ , where $\Gamma$ is connected, then there exists a fundamental domain $\mathcal{F}.$

Proof. We start by defining a poset set with minimal structure. Pick any vertex $v\in \Gamma.$ Define $P=\{\text{connected closed subgraphs of } \Gamma \mid v\in P, \text{and if } x\neq y \in P, \text{such that } g\cdot x =y \implies g=e .\}$ In other words, we would like to contain a minimal amount of vertices concerning how the group action can move things around.

Next, with the sets defined, we specify our partial order as the usual set inclusion. To use Zorn’s Lemma, we check that $P$ is nonempty since the singleton $\{v\}\in P$ . Then, we want to show that every chain has a maximal element. We assume that we have the following chain:

$\Gamma_0\subset \Gamma_1 \subset \Gamma_2 \subset \dots .$

Then, we let $\hat{\Gamma}=\bigcup \Gamma_i$ ranging over all $\Gamma_i$ in the chain. We claim that $\hat{\Gamma} \in P.$

To prove the claim, we first quickly observe that $v\in \hat{\Gamma}$ . Then, we assume that $x\neq y \in P, \text{such that } g\cdot x =y$ . There must exist $i\in \mathbb{N}$ such that $x,y\in \Gamma_i$ . Thus, by assumption, we conclude that $\hat{\Gamma} \in P.$

Therefore, we apply Zorn’s lemma to obtain a maximal element in $P$ with respect to inclusion, and we call it $\mathcal{F}'$ . We claim that $V(\bigcup g\cdot \mathcal{F}') = V(\Gamma)$ ; in other words, upon group actions, $\mathcal{F}'$ covers all vertices of $\Gamma.$

Towards a contradiction, we let $w\in V(\Gamma)$ such that $w\notin \bigcup g\cdot \mathcal{F}'$ . Thus, since $\Gamma$ is connected, there exists a vertex path from $w$ to any vertex in $\bigcup g\cdot \mathcal{F}'$ . Without loss of generality, we take the shortest path $\gamma$ . Let $w'$ be the last vertex before arriving in $\bigcup g\cdot \mathcal{F}'$ . Then, we claim that $\mathcal{F}' \cup \{w'\} \in P$ is a larger set than $\mathcal{F}'$ . To prove the claim, it suffices to show that there is no nontrivial $g\in G$ such that $g\cdot x=w'$ , which is an exact rephrase of $w'\notin \bigcup g\cdot \mathcal{F}'$ . Therefore, we have the desired contradiction.

**Diagram 1.** Illustrate that $w'$ should be contained in $\mathcal{F}'$ .

Next, we would like to extend our $\mathcal{F}'$ in a minimal fashion so that the entire graph can be covered. Here, edges are our only concerns since all vertices have been covered. Consider any edge $e$ that is not covered in $\bigcup g\cdot \mathcal{F}'$ . Observe that two endpoints of $e$ , which we call $v,w$ , should satisfy $v\in g \cdot \mathcal{F}', w\in h \cdot \mathcal{F}'$ , where $g\neq h$ . Without loss of generality, we may append the half-edge containing $v$ to $g c\dot \mathcal{F}'$ for any $e$ with endpoints $v$ and $w$ . Note that this process is equivariant up to the union of all $g \cdot \mathcal{F}'$ , so we may as well consider the extension on $e\cdot \mathcal{F}'$ , which we give the name $\mathcal{F}$ . As a quick remark here, $\mathcal{F}$ is not unique itself, which gives us the freedom to make suitable fundamental domains. (This would be a great opportunity to make some comments, like backtracking this process with the example of a hexagon.)

Finally, we check that $\mathcal{F}$ is a fundamental domain of $G \curvearrowright \Gamma$ . First, it is closed since throughout the construction, we only used unions of countably many closed subsets (I suppose we need to assume the graph $\Gamma$ is locally finite here since locally finite graphs have countably many vertices and edges on my rough inspection. But this is definitely worth commenting on.)

Second, it covers all $\Gamma$ by construction. Third, it is minimal since adding any more points on the half edges would result in repetitions equivariantly. ▭

2. Fundamental Domains of Cayley Graphs.

We can obtain many insights from the proof of Theorem 1.2. For example, we may understand the fundamental domains on different graphs. First, we introduce the following definition of vertex transitivity.

Definition 2.1 For $G$ acting on $X$ , we say that the action is (vertex)-transitive if for any $x,y\in X$ , there exists $g\in G$ such that $g\cdot x=y$ .

Remark 2.2 Groups acting on their Cayley graphs vertex-transitively. We say the underlying group is $G$ , then for any vertices $v_g,v_h$ , where $g,h\in G$ , note that $hg^{-1} \cdot v_g=v_h$ .

Then, we present a Corollary of Theorem 1.2.

Corollary 2.3 If $G$ acts on a graph transitively, then a fundamental domain of this action is a star of half edges.

Proof. We start by observing that in the construction, by fixing a vertex $v$ , any other vertex is connected through $v$ through group action. Thus, in our notation, $\mathcal{F}=\{v\}.$ Then, by attaching half-edges, we obtain a star-like fundamental domain.

Corollary 2.4 For any group acting on its Cayley group on the left, there exists a fundamental domain that’s a star of half edges.

Proof. This result trivially follows from Remark 2.2 and Corollary 2.3.

We see this corollary in action through an example.

Example 2.5 We consider the Cayley graph of $S_3.$ Note that in the following picture, I draw the Cayley graph of $S_3$ generated by $\{(12), (123).\}$ Here, I denote the black color as the edges corresponding to $(1 2 3)$ and the blue color as the edges corresponding to $(1 2)$ . Then, the two red highlighted portions denote two fundamental domains of $S_3$ acting on this Cayley graph (forgetting the labels and directed edges).

3. Fundamental domains of subgroups.

In this section, my discussion will give a different treatment than what was covered in the lecture. First, we introduce the orbit and stabilizer. And then, we realize the one-to-one correspondence between the transversal of subgroups and components of a fundamental domain of subgroups as a corollary of the Orbit-Stabilizer Theorem.

Definition 3.1 Let $G$ act on $X$ . For any $x\in X$ , the stabilizer of $x$ is defined as

Stab $(x)=\{g\in G \mid g\cdot x=x.\}$

We say that an element $x\in X$ is moved freely by $G$ if the stabilizer is trivial. If every element of $X$ is moved freely, then $G$ acts freely on $X$ .

Remark 3.1′ In Diagram 1, if $x$ is in the intersections of multiple $g_i\mathcal{F}'$ , then those $g_i$ are exactly the stabilizer of the vertex $x$ .

Definition 3.2 Let $G$ act on $X$ . For any $x\in X$ , the orbit of $x$ is defined as

Orb $(x)=\{y\in X \mid y= g\cdot x.\}$

Remark 3.3 As a quick remark, in the proof of Theorem 1.2, when we define $P$ , we basically require that the subgraph does not contain any two vertices from the same orbit to obtain minimality.

Theorem 3.4 Let $G$ act on $X$ and any $x\in X$ , there is a one-to-one correspondence between the set Orb $(x)$ and left cosets of $Stab(x)$ given by $g\cdot x \to g \cdot$ Stab $(x).$

Proof. We observe that $g\cdot x=h\cdot x$ if and only if $h^{-1}g\cdot x =x \iff h^{-1}g \in \text(Stab)(x).$ Thus, two elements in the orbit are the same if and only if their induced cosets are the same.

Coming back to the picture of fundamental domains, we wish to realize this nice result when the set $X$ is a graph $\Gamma$ .

Theorem 3.5 Let $G$ act on $\Gamma$ with a fundamental domain $\mathcal{F}$ . We assume that no group action fixes $\mathcal{F}$ nontrivially. Then, if $H$ is a subgroup of $G$ and a fundamental domain of $H$ is a union of $n$ copies of $\mathcal{F}$ (where $n$ can also be infinity), the index of $H$ in $G$ is $n.$

Proof. Since no group action fixes $\mathcal{F}$ nontrivially, we deduce that there is some point in $\mathcal{F}$ that is moved freely by $G$ . Therefore, we have a bijection between elements of $G$ and points in Orb $(x)$ . By assumption, we note that

$\mathcal{F}_H=\bigcup_{i=1}^n g_i \mathcal{F},$ where $n$ can also take on infinity.

Since $\mathcal{F}_H$ is a fundamental domain for the action $H$ , we can deduce $g\cdot x=g_ih\cdot x$ for one of the $g_i$ mentioned above. Using Theorem 3.4 to come back to the group side, we conclude that $\{g_i\}$ forms a transversal of $H$ in $G$ . Hence, we prove the theorem.

Posted in Uncategorized | Tagged Fundamental Domain, Week 2 | 10 Comments

Friday of Week 1: Cayley’s “Better” Theorem and Fundamental Domains

Posted on September 19, 2022 by Osip Surdutovich

Class got a bit more technical on this fine Friday morning! We began with Cayley’s Good Theorem and went into details about graph theory. Furthermore, we learned about fundamental domains as a building block to representing infinite groups through graphs.
Cayley’s Theorem

Theorem. If $G$ is finitely generated then there exists a labelled oriented graph $\Gamma$ such that SYM $^+(\Gamma)\cong G$ .

This is massive because now if we have any finitely generated group, we can can represent it using our graph theory tool box. The term finitely generated when referring to groups group is tied to locally finite when we discuss graphs. Throughout the course we will deal with locally finite graphs so, in essence, this theorem presents us with the dream.
Before we go any further, I’d like to review some of the terminology. Namely SYM $^+$ , a permutation of a graph which moves vertices to vertices and edges to edges in a one to one manner, while preserving the relationship between all aspects of a graph.
Before we prove Cayley’s theorem we need to develop a bit of machinery in order to make more sense of it all. We introduce a somewhat new idea for groups and generating sets.

Definition. A group $G$ with a generating set $S$ and Cayley graph $\Gamma_{G,S}$ has
1. $ V(\Gamma)=G, $

2. $E(\Gamma)={(g,gs)| s\in S},$
where $(g,gs)$ has labels and orientation.

It is important to note that $s$ acts on G from the right, which will be standard notation throughout the course. This is most easily described through the figures drawn below of the representation of $\mathbb{Z}$ through different generating sets.

As it becomes clear, we can portray the same group in different ways, depending on the generating set that we choose.

We can also do the same thing for finite groups, as shown below for $\mathbb{Z}/6\mathbb{Z}$ .

As an aside, I find these representations really cool! The structure reminded me a bit of Murray Gell-Mann’s Eightfold Way which is an organization scheme for hadrons which were essential to the formation of the quark model in particle physics.

Anyways, these new representations which we are able to assemble bring us to some big questions about infinity. First and foremost, when is a graph $\Gamma_{G,S}$ finite? The answer must be when the group is finite, stemming from the first part of the definition: $v(\Gamma)=G$ .
Other questions asked were when we can say that $\Gamma_{G,S}$ is locally finite? When the generating set is finite! When is it finitely connected? Always! (since we can always act on an element of the generating set with the composition of its inverse and any other element). Finally, when does $\Gamma_{G,S}$ have a finite amount of relaters? When it is sufficient to have a finite amount in order to get to all desired points in the graph.
All of these questions are important to think about as we advance through the course.

Keeping the definitions and questions in mind we now can prove Cayley’s theorem!

Proof. We prove the equivalence statement given in the theorem in both directions. We begin the proof by first showing that $G$ is a subgroup of SYM $^+(\Gamma)$ .
$(\implies)$ This direction requires us to show that $G$ acts on $\Gamma_{G,S}$ faithfully. We have already shown in the previous class that $G$ acts faithfully on $V(\Gamma)$ so all we must do is verify that the action on edges, meaning that the action induces a map in $E$ . We define the action as $g\cdot v_x=v_{gx}$ , for $g\in G$ , $x\in S$ , and $v_x,v_{gx}\in V(\Gamma_{G,S})$ . Now let’s take and edge $(v_x,v_s)$ and let $g$ act on both vertices. We obtain $g\cdot(v_x,v_s)=(v_{gx},v_{gs})\in E$ , so the action preserves the edge. Moreover, the result has the same label and orientation as $(v_x,v_{xs})$ where the label and orientation are all determined by the generating set $S$ . This verifies that action which has faithfulness implied from the definition of SYM $^+(\Gamma)$ .
$(\Longleftarrow)$ For the other direction we must show that SYM $^+(\Gamma)$ is a subgroup of $G$ . We go about this by induction, however, for time purposes we will show only the base case and leave the induction step for another time. We choose an arbitrary map $\phi\in$ SYM $^+(\Gamma)$ and consider $\phi(v_e)=v_g$ for $v_e,v_g\in V(\Gamma_{G,S})$ and $e,g\in G$ . The hypothesis will be that our map $\phi$ acts exactly the same as $g\in G$ on vertices and edges. As the base case consider $N(v_e)$ , defined as the unconnected neighborhood. Since each vertex in $V(\Gamma_{G,S})$ has exactly one adjacent edge along with a given label and orientation pair. By definition of SYM $^+(\Gamma)$ $\phi$ is one to one
and respects the labeling and pairing. Thus we have that $\phi(v_e,v_{es})=(v_g,v_{gs})$ . It follows that $\phi$ and $g$ agree in $N_1(v_e)$ .
We could now proceed to induct and conclude our proof. □

A few takeaways from the proof of this magnificent theorem are on the definitions behind Cayley graphs, which we will discuss later in the course. First of all, Cayley graphs are dependent on the generating set (up to something). This is rather vague — but as I said we will get to it later on! Second, groups act on Cayley graphs; however, if for two groups $G,H$ we have $G$ acting on $\Gamma_{H,S}$ for some generating set $S$ . This DOES NOT imply that $G\cong H$ . Finally, a more general statement about Cayley graphs is that we can read off relaters and equivalent words from that paths in a graph.
An addition piece of information that I have briefly read about is the question of transitivity of Cayley graphs. In fact, all Cayley graphs are transitive, however, not all transitive graphs are Cayley. Maybe we will learn more about this as the term goes on but it certainly seems to be a big deciding factor on whether a graph is Cayley or not.
Fundamental Domain
Let’s begin, as always, with the definition.

Definition Let $G$ act on $\Gamma$ . A \textit{fundamental domain} of the action is a minimal subset $\mathcal{F}\subseteq \Gamma$ such that $\mathcal{F}$ is closed and $\bigcup g\cdot \mathcal{F}=\Gamma$ .

Once again, the figures below of several examples of groups explain the concept quite clearly. In essence, we are minimizing the necessary information needed in order to identify the group action. As groups get bigger (to infinity and beyond) we will want to express all the necessary information as concisely as possible as opposed to trying to draw infinity.
We cover two quick but important theorems which are fundamental (no pun intended) to our understanding.

Theorem. Let $G$ act on $\Gamma$ , a connected graph with fundamental domain $\mathcal{F}$ . Then the set $S={g\in G|\mathcal{F}\bigcap g\mathcal{F}\neq \emptyset}$ generates all of $G$ .

Once more the theorem is concerned with generating $G$ … I’m sensing a pattern here. The proof is brief and shown below.

Proof. Let $g\in G$ , $v\in V(\Gamma)$ , and $\gamma$ a path from $v$ to $g\circ v$ . Notice, since $\bigcup g\cdot \mathcal{F}=\Gamma$ $\gamma$ is covered by the set ${g_i\mathcal{F}}$ . As in the theorem conditions, we assume that $g_1\mathcal{F} \cap g_{i+1} \mathcal{F}\neq \emptyset$ for some $i$ which is valid since $\mathcal{F}$ is by definition closed.
Now observe that $g_1\in S$ and $g_2g_1^{-1}\in S$ . We can thus in duct on this patter to find that $g_{i+1}g_i^{-1}\in S$ for all $i$ . It follows that $g=g_n=(g_n g_{n-1}^{-1})(g_{n-1} g_{n-2}^{-1})...(g_2 g_{1}^{-1})g_1$ and thus we can generate all of $G$ with elements in $S$ . □

The figure below represents how we can envision the set $S$ generating $G$ .
A final theorem for the day gives us an additional property of the fundamental domain and lets us conclude with good foresight into the future.

Let $G$ act on connected graph $\Gamma$ and let $H$ be a subgroup of $G$ . If the fundamental domain $\mathcal{F}$ of the action of $G$ on $\Gamma$ is a union of $n$ copies of the action of $H$ on $G$ then $[G:H]=n$ . □
Theorem
Here, $[G:H]$ represents the degree of $G$ over $H$ . This theorem gives us information about the groups internal subgroup structure and a very useful tool for representation of a group’s subgroups through graphs. In addition, it reminds of Galois theory ideas through computing the degree of the group over its subgroup.
The theorem uses the term copies which is closely related to the term coset which are able to form pictures or copies of parts of the group. For our purposes we will use the term \textit{transversal} of $H\subseteq G$ .

Definition. A transversal of $H\subseteq G$
$begin{equation} {e,g_1,g_2,... g_n}$
is a set of $g_i\in G$ such that $\bigcup g_i H = G$ and if $g_i H \bigcap g_j H\neq\emptyset$ then $i=j$ .

With this, we conclude this blog post! The proof of this final theorem will be covered in Monday’s lecture and the next major topic will be putting fundamental domains to use. Sure, we know what they are by definition, but how can we actually represent complex groups using them?

Sources:

Chapter 1 from J. Meier Groups, Graphs, and Trees
Generators & Cayley graphs from Cornell University — http://pi.math.cornell.edu/~mec/2008-2009/Victor/part3.htm

Posted in Uncategorized | 3 Comments

First Wednesday: Groups, Graphs, and Symmetries

Posted on September 16, 2022 by John Eichelberger

Wednesday’s class was a review of groups, a “whirlwind-review” of the basics of graphs and trees, and a look at actions on symmetry groups of geometric object.

Groups, Reviewed

To begin with, we reviewed group presentations, of form $G = \langle S \ | \ R \rangle$ . For instance, the integers over addition can be conceived of as

$\mathbb{Z} = \langle t \ | \ \rangle = \{\ldots, t^{-2}, t^{-1}, e, t, t^{2}, \ldots\}$

In particular, we note that exponentiation works as expected, where exponentiation represents addition:

$t^m t^n = t^{m+n}$

What is “the” representation of \mathbb{Z} \times \mathbb{Z}? In short, it depends; there are infinitely many valid representations. For instance,

$\mathbb{Z} \times \mathbb{Z} &= \langle t, s \ | \ st = ts \rangle$
$\langle (1, 1), (0, 1) \ | \ \text{some relator} \rangle$
$\langle st, t \ | \ \text{some relator} \rangle$
$\langle st, t \ | \ \text{some relator} \rangle$
$\langle s, t, u \ | \ u = s^2, st = s \rangle$

However, while these are all representations of the same group, we cannot just “simplify” one into another. It’s true that generators are analogous to a basis in linear algebra, in the sense that groups are constructed by combinations of generators just as a vector space is constructed from its constituent vectors. But the analogy is strained when it comes to a “minimal basis”. Consider the following example:

$\mathbb{Z}/30\mathbb{Z} &= \langle 2, 3, 5 \ | \ \text{some relators}\rangle \cong \langle 1 \ | \ 1^{30} \rangle$

These both represent the same group; the first has three generators, and the second only has one. Yet in both cases the removal of any generator means we no longer have the same group.

This warm-up leads us to several key, enduring questions across geometric group theory:

For a group $G$ , is $G$ finitely presented? Is it finitely generated?
When is a presentation trivial? Given a presentation, when does it represent $\{e\}$ ?
Given a word $w \in S$ , does $w = e$ ?

Group Actions

Definition. A group $G$ acts on a set $X$ where for every $g \in G$ ,

$g: X \to X, \text{ and } g: x \mapsto g \cdot x$

with the following properties satisfied:

$gh \cdot x = g \cdot (h \cdot x)$
$e \cdot x = x$

We want to think about this definition in a deeper way, thinking about symmetry. So for an object $X$ , consider Sym $X$ , the group of symmetries on $X$ . (This is often referred to as Aut $X$ , the automorphisms on $X$ .) We can think of $G$ acting on $X$ as a homomorphism

$\varphi: G \to \text{Sym}X$

In other words, we want to assign the behaviors of elements of $G$ to the behaviors the groups that arise in $X$ .

We have a faithful group action if $\varphi$ is injective. Equivalently, $G$ acts faithfully if $g \neq e$ implies that there is some $x \in X$ such that $g \cdot x \neq x$ , or in other words, that every non-identity element of $g$ does something to some element of $X$ under the action. For an example of a faithful action, consider actions on a square, letting $G = \langle t \ | \ t^4\rangle$ . We define the action as $\varphi: t \mapsto r_{90}$ . This action is faithful, because every non-identity $g$ will permute the corners of the square.

For an example of an action that is not faithful, we’ll consider the trivial case: for any $X$ and any $G$ acting on $X$ , we can define the action by $g \cdot x = x$ . In other words, every configuration of $X$ maps to itself under every action of $G$ .

Theorem. Every group $G$ can be faithfully represented by a group action on the symmetries of an object $X$ .

Proof. Let the object $X$ be given by the set of elements of $G$ . We’ll define our action $g \cdot x$ as the multiplication operator of $G$ , which is to say $gx$ . This action will be associative because $g, x \in G$ , and because $G$ is (also) a group, elements under its operator associate; it likewise follows that our action will have an identity, since $G$ is a group. Finally, consider some $g \neq e \in G$ , and let $x = g^{-1}$ . We have that $g \cdot x = e \neq x$ , so for every $g \in G$ there is some $x \in X$ such that $g \cdot x \neq x$ , as desired.

The following corollary serves as a generalization of Cayley’s Theorem from Abstract I, that every finite group is a subgroup of a symmetric group.

Corollary. $G \subseteq \text{Sym}X$ for some $X$ .

Proof. It follows from the above theorem that $\varphi: G \to \text{Sym}X$ is injective. Thus

$G \cong \varphi(G)/\text{ker}\varphi \cong \varphi(G) \subseteq \text{Sym}X$

A Whirlwind of Graph Theory

The following are some foundational definitions for graph theory.

Definition. A graph $\Gamma$ is a set containing

$V(\Gamma)$ , a set of vertices,

$E(\Gamma)$ , a multiset of edges

Below is an example graph $\Gamma$ .

Definition. A path is a collection of edges and vertices that begins and ends with a vertex, with each edge connected to the previous vertex.

Note. The length of a path is given by the number of edges.

Definition. A path with the same initial and final vertex is a cycle.

Definition. A path is considered reduced if it contains no backtracks.

Definition. A graph is considered connected if there exists a path between any pair of vertices.

Definition. A graph is considered finite if $|V(\Gamma)|$ and $|E(\Gamma)|$ are finite.

Definition. A graph is considered locally finite if deg $(v)$ is finite for all $v \in V(\Gamma)$ .

Definition. A tree is a connected graph with no cycles.

Note. We denote $T_n$ as the regular tree, given by a tree where every vertex connects to $n$ edges. Similarly, $T_{n, m}$ refers to a tree in which every vertex has either $n$ or $m$ vertices.

Theorem. The following are equivalent:

$T$ is a tree.
There exists a unique reduced path for all $v, w \in V(T)$ .
For all $e \in E(T)$ , $T - e$ is disconnected.

These can be shown to follow by contradiction.

Symmetries on Graphs

With this setup, we can consider actions on graphs! Similar to rigid symmetries, we require that a symmetry $\varphi \in \text{Sym}(\Gamma)$ must be a bijective map of edges and vertices, and that $\varphi$ must preserve some sense of structure in the graph, what MurphyKate calls “preserving gluing.”

To get a sense for what this means, consider two graphs. $K_4$ is the graph of four points, each connected to every other point by an edge.

By numbering the points, we see that we can swap any pair of points as we please and preserve the shape of the graph. Therefore the group of symmetries on $K_4$ is isomorphic to $S_4$ , the symmetries on four elements.

On the other hand, consider the graph $\Gamma$ .

If we swapped 1 and 4, we would lose the property of “gluedness”. Similarly, we aren’t allowed to swap 2 and 4. Therefore we have that Sym $\Gamma \subset S_4$ . It turns out that Sym $\Gamma$ , with its four points and four edges, is isomorphic to $D_8$ , the rigid symmetries of a square.

But we can kick it up a notch with multiedges. The colors in $\Gamma'$ below mark where each part of its symmetry group come fromm and are not considered decorations:

But we can kick it up another notch with digraphs!

Definition. A directed graph (aka digraph) is a graph where every edge has an orientation toward a vertex. For instance:

That example has only one symmetry, formed by swapping the left and right multiedges. But we can kick it up again with colors! We can color every edge:

This example has only the trivial symmetry. So when considering a graph, we can consider separately Sym $(\Gamma)$ , as previously established, and Sym $^+(\Gamma)$ , the symmetry group that preserves orientation and color.

Theorem. For any graph $\Gamma$ , Sym $^+(\Gamma) \subseteq \text{Sym}(\Gamma)$ .

Proof. Left as an exercise. <3

And weighing in at five pages in Google docs, that wraps up my notes. Friday we’ll talk about Cayley graphs, and if I’m reading the textbook chapter headers correctly, the topic of group actions on the symmetry groups of graphs will last us most of the term.

Posted in Uncategorized | 12 Comments

Week 1 Monday: Groups and Group Presentations

Posted on September 14, 2022 by Michaela Polley

Welcome to Geometric Group Theory! As today was the first day of class we began by reviewing the syllabus and discussing expectations for the term before diving into the material.

Review of Groups

Definition: A group is a set with a binary operation $G$ that satisfies three conditions:

$G$ contains an identity element: $\exists e\in G$ such that $eg=ge=g$ for all $g\in G$ .
Every element in $G$ has an inverse: $\forall g\in G$ $\exists g^{-1}$ such that $gg^{-1}=g^{-1}g=e$
The group operation is associative: $\forall g,h,k \in G (gh)k=g(hk)$

$G$ can refer to both the set of elements or the group (including the operation). Some authors separate these two uses by denoting the group $(G,\cdot)$ . However, in this class we will generally use $G$ to refer to both the set and the group and make clear which one we are referring to.

Let us see this in action. The dihedral group of order 8, called either $D_4$ or $D_8$ depending on the text, will be our example. We will call it $D_8$ . The eight elements of the group are:

Since a group is defined by both the set of elements and the group operation, it is not enough to simply list the elements of the group. Instead, we give the “multiplication table” for the group or the Cayley Table. The Cayley Table for the group is shown below.

Group Presentations

A Cayley Table, while helpful, can also be a little bit unwieldy as a way to represent a group. Instead, we give a group presentation, which is a set of generators and relators. Our notation will be $G = \langle s_1,\dots,s_n | r_1,\dots,r_k\rangle$ where each $s_i$ is called a generator and each $r_j$ is called a relator. The set $s_1,\dots,s_n$ is also called the generating set.

Definition: A generating set for $G$ is a set of elements in $G$ such that for all $g\in G$ , $g = s_{i_1}^{m_1}s_{i_2}^{m_2}\dots s_{i_n}^{m_n}$ .

While a generating set may be infinite, each element in $G$ must be the product of a finite number of generators. A product of generators is called a word.

Each of our relators is a word which equals the identity. For example, for $D_8$ . some relators are $V^2, H^2,$ and $(R_{90})^4$ . Relators can also show the relationship between two elements such that $R_{90}^2=R_{180}$ .

Each group has at least one presentation, since we can always include every element in the group in our generating set. However, this is often not necessary, since we can generate some elements from a set of basis elements. This is similar to finding a basis in linear algebra. For $D_8$ we know that we don’t need any rotation elements other than $R_{90}$ since each of the other rotations is a power of $R_{90}$ . Similarly, we do not need any flips other than $V$ since we can combine $V$ and $R_{90}$ to attain any of the other flips. Thus, our generating set is $\{V, R_{90}\}$ . By tradition we do not include $e$ in our generating set. For our relators we need to know both how $V$ and $R_{90}$ relate to $e$ and how they relate to each other. Thus, we get $V^2, R_{90}^4,$ and $VR_{90}V=R_{90}^{-1}$ as our set of relators. Therefore, our final group presentation is $D_8 = \langle V, R_{90}|V^2,R_{90}^4, VR_{90}V=R_{90}^{-1}\rangle$ . Next time we will discuss how we know that this is enough to represent the entire group!

Posted in Uncategorized | 5 Comments

Introduction

Posted on August 29, 2022 by MurphyKate

The majority of this page will be a student-generated repository of class notes for a class on Geometric Group Theory, taught primarily from John Meier’s Groups, Graphs, and Trees.

You can find the course information (including a syllabus and information on homework) at the Course Info page. There is also a link located along the top menu.

Some Notes on Formatting

We have QuickLaTeX enabled on our site. This allows you to type inline and display math mode, and use some environments (such as align), as well as labels and references. Just like in a LaTeX document, you have to tell WordPress when you want something to be in “math mode.” The way you do this is by using dollar signs, just like in a LaTeX document: For example, I can write: “$ f(x) $” and this will be output as $f(x)$ .

Warning: Any use of a dollar sign will result in math mode!

If you want to include something more complicated, like a commutative diagram, it may be better to use some other method to typeset your work (for example, an online equation editor, or LaTeXiT) and include it as an image.

QuickLaTeX does not allow you to use Theorem, Proof, Definition, etc environments. To include a Theorem or Definition, you must set it on its own line and bold the title yourself, as in the following example:

Theorem: A group $G$ is free if and only if it acts freely on a tree.

Proof: You should also set proofs yourself, and end them yourself. You can use the command \square to mark the end of a proof. $\square$

There is no need to number theorems or definitions unless you need to refer to them later in the post.

Posted in Uncategorized | Leave a comment

Third Friday: Free Subgroups and Sunshine

Third Wednesday: More Free Groups

Week Three Monday : The Ping Pong Lemma and Free Groups in the Mathematical Wild

Week Two Friday: Reflections and Coxeter Groups

Second Wednesday: Free Groups

Week 2, Existence of Fundamental Domain and Some Applications

In this blog, we aim to show 1) the existence of fundamental domains, 2) fundamental domains in Cayley graphs, and 3) a one-to-one correspondence between the transversal of subgroups and components of a fundamental domain of subgroups.

1. Existence of Fundamental Domains

2. Fundamental Domains of Cayley Graphs.

3. Fundamental domains of subgroups.

Friday of Week 1: Cayley’s “Better” Theorem and Fundamental Domains

First Wednesday: Groups, Graphs, and Symmetries

Week 1 Monday: Groups and Group Presentations

Introduction

Some Notes on Formatting

Recent Posts

Recent Comments