\part{Fundamentals}

Group theory
Enumerative combinatorics


\chapter{Free groups}


In combinatorial group theory, there is one structure  to rule them all; free groups.

Recall how we could generate subgroups from one group element. We will now study how to do this with an arbitrary subset of a group, and eventually, we will form a group from just an arbitrary set!

Let's find a way to generate the smallest subgroup containing some arbitrary subset $X$, rather than just an element. SInce we know that taking interesections preserves the criterion for a group, we can take the intersection of all subgroups containing $X$. In the end, we obtain the smallest subgroup containing $X$.

\begin{definition}[Subgroup generated by $X$]
The \emph{subgroup generated by $X \subseteq G$} is the following subgroup, generated by taking the intersection of all subgroups containing $X$.
\[\Lambda = \{H \leq G : X \subseteq H\}\]
\[\langle X \rangle = \bigcap_{H \in \Lambda} H\]
\end{definition}


\begin{proposition}
\[ \langle X \rangle = \{ \prod_{i \in I} x_{i}^{n_i} : x_i \in X \land n_i \in \mathbb{N} \} \].
\end{proposition}


Inspired by this result, one may wish to find a way to generate a group with just some arbitrary set.

A \emph{word}
An \emph{empty word}
A \emph{reduced word}


An \emph{elementary word reduction algorithm}
Disjoint reductions $u_1 y_1 y^{-1}_{1} u_2  y_2 y^{-1}_{2} u_3$
start from either left or right
Overlapping reductions $u_1 y y^{-1} y u_2$
pair with left or right element

All Elementary word reduction algorithms have the same effect



A \emph{free group} $F(X)$ is a group generated by some set $X$ such that every non-empty reduced word is a nontrivial element of $F(X)$
\[\{x_i\}_{i=1}^{n} : [1,n]\cap \mathbb{N} \to X \cup X^{-1}\]
\[\{p_i\}_{i=1}^{n} : [1,n]\cap \mathbb{N} \to \mathbb{Z}\]
\[F(X) = \{ \prod_{i=1}^{n} x_{i}^{p_{i}} \}\]
This technique can be used for generating a group with one element too, however the definition given is usually more powerful.