TAOCP 7.2.1.2 Exercise 51

The statement is **false in general**.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.2: Generating All Permutations

Exercise 51. [M16] [M16] True or false: If the sets Sk = {σ(k, 0), . . . , σ(k, k)} form a Sims table for the group of all permutations, so also do the sets S− k = {σ(k, 0)−, . . . , σ(k, k)−}.

Verified: yes
Solve time: 5m01s

The statement is false in general.

The error in the proposed solution is not a minor gap but a structural misunderstanding: a Sims table is built from a choice of right transversals, and inversion does not preserve right transversals for non-normal subgroups such as the stabilizers in the symmetric group.

1. Correct structural fact about inversion

Let $H \le G$. For any subset $S \subseteq G$,

  • if $S$ is a right transversal for $H$ in $G$, then every $g \in G$ can be written uniquely as

$$ g = s h, \quad s \in S, ; h \in H, $$

  • taking inverses gives

$$ g^{-1} = h^{-1} s^{-1} \in H S^{-1}, $$

so $S^{-1}$ is a left transversal, not necessarily a right transversal.

In particular,

$$ (gH)^{-1} = H g^{-1}, $$

so inversion swaps right cosets into left cosets.

Thus there is no general reason for $S^{-1}$ to again represent right cosets.

2. Why the reviewer’s criticism is decisive

In the stabilizer chain for $S_n$,

$$ G_k = {\pi \in S_n : \pi(i)=i \text{ for } 1 \le i \le k}, \quad G_k \le G_{k-1}, $$

the subgroup $G_k$ is not normal in $G_{k-1}$ for $k < n$.

Therefore:

  • right cosets $G_{k-1}/G_k$ are not preserved under inversion,
  • a right transversal does not automatically yield a right transversal after inversion.

So the claim can only be true if the specific Sims table has additional symmetry, which is not required by the definition.

3. Concrete counterexample in $S_3$

Take $n=3$, $k=1$.

Then:

$$ G_1 = {\pi \in S_3 : \pi(1)=1} = {(), (23)}. $$

Right cosets of $G_1$ in $S_3$ correspond to the image of $1$.

We construct a valid Sims transversal $S_1$ (one per coset):

  • identity coset (1 maps to 1): choose $e$,
  • coset where $1 \mapsto 2$: choose $(123)$,
  • coset where $1 \mapsto 3$: choose $(13)$ would work, but we do not need it for the counterexample.

So let:

$$ S_1 = {e, (123), (13)}. $$

This is a valid right transversal of $G_1$ in $S_3$.

Now take inverses:

$$ S_1^{-1} = {e, (132), (13)}. $$

But observe:

  • $(132)(1) = 3$,
  • so $(132)$ lies in the coset of elements sending $1 \mapsto 3$,
  • yet in $S_1$, the chosen representative for that coset was $(13)$, not $(132)$.

Hence $S_1^{-1}$ does not pick exactly one representative from each right coset using the original structure of $S_1$. In particular, it is not guaranteed to equal the prescribed Sims transversal, and in general fails the Sims-table compatibility condition across levels.

More directly, we can sharpen the failure:

  • a right transversal condition requires exactly one element per right coset,
  • inversion permutes cosets into left cosets,
  • so $S_1^{-1}$ is not controlled by the right coset partition used to define the Sims table.

Thus it fails the required structure.

4. Pinpointing the exact flaw in the original proof

(a) Coset invariant misused

It is correct that right cosets in this stabilizer setting are determined by $g(k)$.

It is not correct that inversion preserves this invariant in a way compatible with right cosets.

Instead:

$$ (gG_k)^{-1} = G_k g^{-1}, $$

so inversion switches right cosets to left cosets.

(b) Hidden false assumption about representatives

The claim that a representative sending $k \mapsto j$ must invert to another element sending $k \mapsto j$ assumes a symmetry like a transposition structure. A Sims transversal has no such requirement. Representatives may be arbitrary elements of each coset.

So there is no reason for:

$$ s(k)=j \implies s^{-1}(k)=j. $$

(c) Right versus left transversal confusion

This is the decisive structural issue:

  • $S_k$ right transversal $\nRightarrow S_k^{-1}$ right transversal
  • $S_k$ right transversal $\Rightarrow S_k^{-1}$ left transversal

The proof incorrectly treated inversion as preserving the type of transversal.

5. Final conclusion

Since inversion converts right cosets into left cosets and $G_k$ is not normal in $G_{k-1}$, there is no structural mechanism forcing $S_k^{-1}$ to remain a right transversal at each level.

Therefore Sims tables are not closed under inversion in general.

$$ \boxed{\text{False.}} $$