Word problem for symmetric group is linear on RAM

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} = ⟨ x_{1}, x_{2}, \dots, x_{n} ∣ x_{i}^{2} = 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 ∣ \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.

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.

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 $π$ in the 2 line notation. wlog, assume $π (j) = i$ and $π (k) = i + 1$ .

$(1 π (1) \dots \dots j i \dots \dots k i + 1 \dots \dots n π (n)) (i i + 1) = (1 π (1) \dots \dots j i + 1 \dots \dots k i \dots \dots 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.

Remark

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 \in S_{n}$ is $w = u_{1} u_{2} \dots u_{n}$ , such that $u_{i} \in U_{i}$ , and $U_{i} = {1, x_{n}, x_{n} x_{n - 1}, \dots, x_{n} \dots 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}$ .

Theorem3

$A (w) = A^{'} (w)$ and runs in $O (ℓ 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 (ℓ n^{4})$ time.

Posted by Chao Xu on 2011-06-21.

Tags: BSU REU, computational complexity, group theory.