Encoding of symmetric groups

The symmetric groups can be encoded in two main ways, namely:

• Using the cycle decomposition of permutations
• Using the one-line notation for permutations

Encoding using the one-line notation

We describe the encoding over a three-letter alphabet, with two of the letters functioning as bits (0 and 1) and the third letter serving as a comma, or a separator.

Encoding a group element

Let $\sigma$ be a permutation on the set of elements from 1 to $n$. We encode $\sigma$ as follows.

• From left to right, first write $\sigma (1)$ in binary. Then put the comma separator.
• Now write $\sigma (2)$ in binary. Again, put the comma separator.
• Keep going on like this till you reach $\sigma (n)$. Put a comma separator after that.

Maximum length of a code-word

Since each $\sigma (i)$ is not more than $n$, its length in binary is not more than $1+\log _{2}n$. There are also $n$ separators. Thus, the total length of a code-word is not more than $n(2+\log _{2}n)$.

This is proportional to the logarithm of $n!$. Thus the encoding is dense,

Algorithms for inverting and multiplying

Given the codes for permutations $\sigma$ and $\phi$, we can compute the code for $\phi \circ \sigma$ as follows. We first compute $\phi (\sigma (1))$ by looking at $\sigma (1)$, and then locating $\phi$ of that by counting the relevant number of commas. We then compute $\phi (\sigma (2))$.

In this process, the tape head for $\sigma$ moves linearly (that is, it moves from left to right) while that for $\phi$ has to keep moving back and forth. Also, the writing tape keeps moving from left to right. So on the whole, the algorithm takes quadratic time in the length of the maximum code-word.

Similarly, the algorithm to compute the inverse of an element takes quadratic time in the length of the maximum code-word.

Algorithm for block concatenation

Given the code for $\sigma \in S_{m}$ and $\phi \in S_{n}$, we want to compute the permutation in $S_{m+n}$ whose action on the first $m$ elements is like $\sigma$ and whose action on the next $n$ elements is like $\phi$. To do this, we proceed as follows. To each of the numbers (between the commas) in the one-line notation of $\phi$, we add $m$ (addition of binary numbers). We now concatenate this altered $\phi$ to the right of $\sigma$.

Combining all these, we find that the one-line notation gives a polynomial-time encoding. This, along with the fact that it is dense, tells us that the one-line notationi s a log-size encoding.