Word problem for symmetric group is linear on RAM
Linear time algorithm for symmetric group
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.
The following is a O(n+l) algorithm for the word problem for symmetric groups on RAM.
- Produce an array
aof size n, Such thata[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] == ifor all i. If true, returntrue, else returnfalse.
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.
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.
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.
A(w) = A'(w) and runs in O(\ell 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(\ell n^4) time.