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: ww is a word of length ll from the presentation Sn=x1,x2,,xnxi2=1,xi+1xixi+1=xixi+1xi,xixj=xjxiS_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 ij1|i-j|\neq 1.

Output: Return true if ww is the identity, else return false.

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

Theorem2

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

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

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

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

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

(1jknπ(1)ii+1π(n))(i i+1)=(1jknπ(1)i+1iπ(n))\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 jj the index of ii if π(j)=i\pi(j) = i. Then each transposition is a swap of indices.

The value of a[i] in the algorithm stores the index of ii. Array a represent the identity iff a[i] = i for all ii.

This proves the the correctness of the algorithm.

The algorithm can be modified so it runs in O(ln!)O(l n!) time for a Turing machine. For each fixed nn, a Turing machine MM can construct another Turing machine MnM_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 SnS_n, the Turing machine MnM_n can solve the problem in O(l)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 nn is ignored in the O(ln!)O(ln!), because it's fixed for each SnS_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 wSnw\in S_n is w=u1u2unw = u_1u_2\ldots u_n, such that uiUiu_i\in U_i, and Ui={1,xn,xnxn1,,xnx1}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(l2)O(l^2) algorithm to solve this problem.

If there exist an algorithm A(w)A(w) that write the word ww of length ll in normal form in O(f(l,n))O(f(l,n)) time., then one can always make it into an algorithm taking O(lf(n2,n))O(l f(n^2,n)) time.

Observe that w=wyzw = w'yz where yy and zz are words in normal form, and the length of z|z| is maximized. A(w)=A(wA(yz))A(w) =A(w'A(yz)). Here yy can be worst case, one single letter, it doesn't change the complexity. Let's introduce two algorithms. A' and A''.

A(w)A'(w) first find the zz in the description, then returns the value of A(w,A(xiz))A''(w',A(x_iz)), where w=wxizw = w'x_iz.

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

Theorem3

A(w)=A(w)A(w) = A'(w) and runs in O(lf(n2,n))O(l f(n^2,n)) time.

Proof

A(w,z)A''(w,z) can ran at most ll times, each time it makes a call to A(w)A(w), contribute the factor O(f(n2,n))O(f(n^2,n)).

In particular, Siegel's algorithm can be modified to run in O(ln4)O(l n^4) time.

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