# Word problem for symmetric group is linear on RAM

# 1 Linear time algorithm for symmetric group

**Input:** $w$ is a word
of length $l$ from the presentation $S_{n}=⟨x_{1},x_{2},…,x_{n}∣x_{i}=1,x_{i+1}x_{i}x_{i+1}=x_{i}x_{i+1}x_{i},x_{i}x_{j}=x_{j}x_{i}⟩$ where
$∣i−j∣=1$.

**Output:** Return `true`

if $w$ is the identity, else return
`false`

.

The representation was crucial for coming up with a linear time algorithm respect to $n$ and $l$. This is not a word problem on one group, but on a set of group.

The following is a $O(n+l)$ algorithm for the word problem for symmetric groups on RAM.

- Produce an array
`a`

of size $n$, Such that`a[i] = i`

. (Array start with index 1) - Reading the word letter by letter. If one encounters $x_{i}$,
`swap(a[i],a[i+1])`

. - Test if the
`a[i] == i`

for all $i$. If true, return`true`

, else return`false`

.

The algorithm takes $O(n+l)$ time is obvious. The correctness needs to be justified.

$x_{i}$ can be represented as the transposition $(ii+1)$. Define $(nn+1)=(n1)$.

Represent a element of the group as a permutation $π$ in the 2 line notation. wlog, assume $π(j)=i$ and $π(k)=i+1$.

$(1π(1) ⋯⋯ ji ⋯⋯ ki+1 ⋯⋯ nπ(n) )(ii+1)=(1π(1) ⋯⋯ ji+1 ⋯⋯ ki ⋯⋯ nπ(n) )$

If we call $j$ the index of $i$ if $π(j)=i$. Then each transposition is a swap of indices.

The value of `a[i]`

in the algorithm stores the index of
$i$. Array `a`

represent the
identity iff `a[i] = i`

for all $i$.

This proves the the correctness of the algorithm.

The algorithm can be modified so it runs in $O(ℓn!)$ time for a Turing machine. For each fixed $n$, a Turing machine $M$ can construct another Turing machine $M_{n}$, such that it store the state of the array as the state of the Turing machine.

This proves every symmetric group is automatic. For any fixed $S_{n}$, the Turing machine $M_{n}$ can solve the problem in $O(ℓ)$ time without writing anything to the tape and can only move to the right, which is equivalent to a finite state automata.

Automatic is a property of a group, not a set of groups. That’s why $n$ is ignored in the $O(ℓn!)$, because it’s fixed for each $S_{n}$. I was confused for a while before I read a concrete definition.

# 2 Algorithms on reduce the word to normal form

The normal form of a word $w∈S_{n}$ is $w=u_{1}u_{2}…u_{n}$, such that $u_{i}∈U_{i}$, and $U_{i}={1,x_{n},x_{n}x_{n−1},…,x_{n}…x_{1}}$.

One can construct a purely symbolic algorithm that apply only the group relations. We measure the time by the amount of group relations used.

Siegel proposed an $O(l_{2})$ algorithm to solve this problem.

If there exist an algorithm $A(w)$ that write the word $w$ of length $l$ in normal form in $O(f(ℓ,n))$ time., then one can always make it into an algorithm taking $O(ℓf(n_{2},n))$ time.

Observe that $w=w_{′}yz$ where $y$ and $z$ are words in normal form, and the length of $∣z∣$ is maximized. $A(w)=A(w_{′}A(yz))$. Here $y$ can be worst case, one single letter, it doesn’t change the complexity. Let’s introduce two algorithms. A’ and A’’.

$A_{′}(w)$ first find the $z$ in the description, then returns the value of $A_{′′}(w_{′},A(x_{i}z))$, where $w=w_{′}x_{i}z$.

Recursively calculate $A_{′′}(w,z)$ with the following definition. $A_{′′}(1,z)=z$. $A_{′′}(w,z)=A_{′′}(w_{′},A(x_{i}z))$, where $w=w_{′}x_{i}$.

$A(w)=A_{′}(w)$ and runs in $O(ℓf(n_{2},n))$ time.

$A_{′′}(w,z)$ can ran at most $l$ times, each time it makes a call to $A(w)$, contribute the factor $O(f(n_{2},n))$.

In particular, Siegel’s algorithm can be modified to run in $O(ℓn_{4})$ time.