The Art Gallery Guardian

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 = \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.

\displaystyle \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(l 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(l) 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(ln!), 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(l,n)) time., then one can always make it into an algorithm taking O(l 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(l 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(l n^4) time.

Posted by Chao Xu on 2011-06-21.
Tags: BSU REU, computational complexity, group theory.