 # 1 Linear time algorithm for symmetric group

Problem1The word problem for symmetric groups

Input: $w$ is a word of length $l$ from the presentation $S_n = \langle x_1,x_2,\ldots,x_n \mid x_i^2 = 1, x_{i+1}x_ix_{i+1} = x_ix_{i+1}x_i, x_ix_j = x_jx_i \rangle$ where $|i-j|\neq 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.

Theorem2

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

1. Produce an array a of size $n$, Such that a[i] = i. (Array start with index 1)
2. Reading the word letter by letter. If one encounters $x_i$, swap(a[i],a[i+1]).
3. Test if the a[i] == i for all $i$. If true, return true, else return false.
Proof

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

$x_i$ can be represented as the transposition $(i~i+1)$. Define $(n~n+1) = (n~1)$.

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

$\begin{pmatrix} 1 & \cdots &j & \cdots & k& \cdots & n \\ \pi(1) & \cdots & i & \cdots & i+1 & \cdots & \pi(n)\end{pmatrix}(i~i+1) = \begin{pmatrix} 1 & \cdots &j & \cdots & k& \cdots & n \\ \pi(1) & \cdots & i+1 & \cdots & i & \cdots & \pi(n)\end{pmatrix}$

If we call $j$ the index of $i$ if $\pi(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(\ell 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(\ell)$ time without writing anything to the tape and can only move to the right, which is equivalent to a finite state automata.

Remark

Automatic is a property of a group, not a set of groups. That’s why $n$ is ignored in the $O(\ell 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\in S_n$ is $w = u_1u_2\ldots u_n$, such that $u_i\in U_i$, and $U_i = \{1, x_n, x_nx_{n-1}, \ldots, x_n\ldots 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(\ell,n))$ time., then one can always make it into an algorithm taking $O(\ell 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_iz))$, where $w = w'x_iz$.

Recursively calculate $A''(w,z)$ with the following definition. $A''(1,z) = z$. $A''(w,z) = A''(w', A(x_iz))$, where $w = w'x_i$.

Theorem3

$A(w) = A'(w)$ and runs in $O(\ell f(n^2,n))$ time.

Proof

$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(\ell n^4)$ time.

Posted by Chao Xu on .
Tags: BSU REU, computational complexity, group theory.