# Background on the Andrews-Curtis Conjecture

## Groups

A group is a set $S$ and an operation $\cdot: S\times S \rightarrow S$ that satisfies the following properties:

* the operation is associative, that is $\forall g, h, i \in S: (g\cdot h)\cdot i = g\cdot (h\cdot i)$
* S contains a unique element $e$, called the identity, such that $\forall g\in S: e\cdot g = g\cdot e = g$
* every element $g\in S$ contains a unique inverse $g^{-1}$such that $g\cdot g^{-1} = g^{-1} \cdot g = e$.

## Free groups

A free group $F_S$ over a set $S$ is a group over elements that can be composed from members of $S$ (called the **generators**) using a group operation $\cdot$. Members of $F_S$ are uniquely represented by a *word* of the following form:

$$
s_1^{\epsilon_1}\cdot s_2^{\epsilon_2}\ \cdots s_n^{\epsilon_n}
$$

Where each $s_i\in S$ and $\epsilon_i$ are $\pm 1$.

A group $G$ (as defined above) is called free, if there exist a set $S$ such that $G$ is isomorphic to $F_S$ (meaning there's a one to one mapping between elemets of $G$ and $F_S$ that preserves the relationships defined by the operation).

The size of $S$ is called the rank of the free group, i.e. $S$ is finite and it contains $n$ elements, we call $F_S$ a rank-$n$ free group.

Not all groups are free.

For example, the set of integers with $+$ as the group operation forms a free group or rank $1$. The generator set is ${1}$. Every integer $k$ can be written uniquely as the word $1^k$, where $s^k$ now means repeated application of $+$. In this free group $0$ is the identity element.

However, if we consider the group over set ${1, \cdot, k}$ with mod-$k$ addition as the group operation, this group is no longer free. It still has a single generator element $1$, however each element can now be generated in non-unique ways. In this modular group

$$
1 = 1^{k+1}
$$

Or, writing it out with the group operation

$$
1 \equiv \underbrace{1+1+1+1+1+1+1+1}_{k+1\text{ times}} \mod k
$$

When the group elements cannot be written uniquely as words, the group is not free.

## Presentation of a non-free group

Presentations are an elegant way of writing non-free groups also in terms of *generators*, and so called *relators*.

The generators serve the same purpose as before, these are the 'basis' we can use to generate write all elements in the group as words. However, the element to word mapping is now one to many.

This also means that one can write the identity element $e$ in multiple ways. In the modular addition example, one can write $1^k = e$. Turns out, we can describe a non-free group in terms of generator elements $x_1, x_2, \ldots$ and a list of words that evaluate to the identity element $e$, called the *relators*.

A presentation is thus a set $S$ of generators, and a set $R$ of relations between these generators. For example, the cyclic group of mod-$k$ addition can be described as:

$$
\langle a \vert a^{k+1} = a \rangle
$$

or, equivalently

$$
\langle a \vert a^{k} = e \rangle
$$

or, since the relations can always be normalised to the form where it's something equals the identity, we can drop the $=e$ bit and simply write

$$
\langle a \vert a^{k}\rangle
$$

In a group described by a presentation like this, each element of the group can be represented by a word, uniquely up to the relations specified in the presentation.

Presentations of groups are not unique. The same group may have lots of presentations that turn out to be equivalent - similar to how knots can be represented by several different braid/knot diagrams.

## Trivial group

The trivial group is a group over a set with one element, which is also the identity element for the group operation. This has a presentation of the form

$$
\langle a \vert a\rangle
$$

But, equally, one can present this same group with two generators as

$$
\langle a, b \vert a, b\rangle
$$

In this case, the two generators coincide, since $a = b = e$.

The above presentation is an example of trivial presentations $\langle S \vert S\rangle$ of the trivial group. This also shows

## Braid group

We can also revisit braids in this context. Equivalence classes of braids form a group under the concatenation operation. The braid group can be described by the following presentation:

$$
\langle \sigma_1,\ldots,\sigma_{n-1}\vert \sigma_i\sigma_{i+1}\sigma_i = \sigma_{i+1}\sigma_i\sigma_{i+1}, \sigma_i\sigma_j = \sigma_j\sigma_i\rangle
$$

where the first relation holds $\forall 1\leq i < n-1$ and the second holds for all $\vert i-j \vert>1$.

This representation has $n-1$ generators and $2n-4$ relations.

So this makes it clear that when we use braid relation 1 or braid relation 2 on a braid word, we are in fact moving within the equivalence class of words which describe the same braid equivalence class. Meanwhile, when using conjugation and stabilisation, we are moving between non-equivalent braids but whose closure nevertheless describes the same link equivalence class.

## Balanced presentations

Balanced presentations are simply presentations where the number of generators and the number of relators matches exactly.

## Andrews-Curtis conjecture

The conjecture is analogous to the Markov theorem for braids representing equivalent knots or links.

The AC conjecture states that a balanced presentation $\langle x_1, \ldots, x_n \vert r_1, \ldots, r_n\rangle$ describes the trivial group if and only if it can be transformed to a trivial presentation $\langle x_1, \ldots, x_n \vert x_1, \ldots, x_n \rangle$ by applying the following three moves, called AC-moves:
* (AC1) for some $i\neq j$ replace $r_i$ by $r_ir_j$.
* (AC2) for some $i$, replace $r_i$ by $r_i^{-1}$
* (AC3) for some $i, j$ replace $r_i$ by $x_jr_ix_j^{-1}$ or $x_j^{-1}r_ix_j$.

There is a weaker version of the AC conjecture which allows for additional moves that change the number of generators.

When one finds a finite sequence of these moves that takes a presentation to the trivial presentation, we say the presentation has been AC-trivialised.

## Counterexamples and difficulty

The AC-conjecture is apparently believed to be false. This, however, has not been proven. There are a number of hypothesized counterexamples, which have never been successfully AC-trivialised. It is not known whether these counterexamples really are counterexamples, or merely very difficult examples to trivialise.

Writing an algorithm that can trivialise some of these hypothesized counterexamples would therefore be an interesting research goal.

There are lower bounds on the worst-case shortest path as a function of the word length of the presentation (total length of the relator words), and these bounds are superexponential. This means that even relatively small presentations might require extremely long exploration.