Which S_m have a complement in S_n?, revisited

I recently went back to revise, verify, and expand two unpublished group theory expository papers from decades ago—one originally drafted in 1997 and the other in 2000—with the help of AI refereeing workflows and Python verification scripts. Although the two notes started from completely different questions, expanding them in 2026 revealed a shared thread: in both settings, rigid subgroup intersection properties govern induced representations and produce Baker–Norine harmonic morphisms between graphs.

The first paper, Which S\sb{m} have a complement in S\sb{n}?, began in 1997 with an email from Herbert Kociemba, the author of the well-known Rubik’s Cube solving program. Because a Rubik’s Cube has 12 edges and 8 corners, a solver has to index elements of S\sb{12} and S\sb{8} efficiently. If a group splits as an exact factorization G = HK with H \cap K = 1 (without needing either subgroup to be normal), every element g \in G can be stored as a unique pair of coordinates (h, k). Kociemba asked me whether the standard subgroup S\sb{8} has a complement in S\sb{12}.

It turns out that complements to the standard subgroup S\sb{m} \leq S\sb{n} are rare because a subgroup K \leq S\sb{n} complements S\sb{m} if and only if K acts sharply (n-m)-transitively on \{1, \dots, n\}. Feeding the classical classification of sharply multiply transitive groups into this criterion settles the problem completely:

  • Universal complements: For every n \geq 3, the cyclic group C\sb{n} complements S\sb{n-1} and the alternating group A\sb{n} complements S\sb{2}.
  • Prime-power families: For n > 12, the only other complements are \rm{AGL}\sb{1}(n) when m = n-2 (n a prime power) and \rm{PGL}\sb{2}(n-1) when m = n-3 (n-1 a prime power).
  • Low-degree exceptions: For n \leq 12, the Mathieu groups M\sb{10}, M\sb{11}, and M\sb{12} contribute sharp 3-, 4-, and 5-transitive complements.
  • A three-factor substitute for S\sb{12}: Because S\sb{8} has no complement in S\sb{12}, I constructed a bijective ordered factorization S\sb{12} = P C S\sb{8} using P \cong \rm{PGL}\sb{2}(11) and C \cong C\sb{9}.

In the new final section, I translated the complement question into algebraic graph theory via the arrangement graph T(n,k) on ordered k-tuples and the Johnson graph J(n,k) on unordered k-subsets. Because S\sb{n-k} is a vertex stabilizer in T(n,k), any complement K acts regularly on the vertices, turning T(n,k)—and every S\sb{n}-invariant coset graph on S\sb{n}/S\sb{n-k}—into a Cayley graph of K whose connection set is a union of k subgroups minus the identity. Curiously, the converse fails for six specific pairs—(9,4), (33,4), (8,5), (9,6), (32,29), and (33,30)—where T(n,k) is a Cayley graph via a subgroup of \rm{Aut}(T(n,k)) \cong S\sb{n} \times S\sb{k} even though S\sb{n-k} has no complement in S\sb{n}. Using the Cayley structure, the Fourier blocks of the adjacency matrix become sums of projections, bounding all eigenvalues below by -k and giving the exact spectrum of T(q,2) by hand. Finally, taking the quotient by the free coordinate action of S\sb{k} produces a k!-fold unramified covering T(n,k) \to J(n,k), a clean example of a harmonic morphism.

The second note, The representation theory of finite commutation transitive groups, dates back to a preliminary draft from August 2000. That project grew out of conversations with Jill McGowan, Dennis Spellman, and my friend (and then-colleague at the USNA) Tony Gaglione. It was through Tony that I got to know Ben Fine, who had coined the term “commutative transitive” (CT) in 1983 while studying Fuchsian and Kleinian groups, and who collaborated extensively with Tony and Dennis on CT groups and the commutative transitive kernel.

A group G is commutative transitive (CT) if commuting is transitive on non-identity elements—equivalently, every non-identity element has an abelian centralizer. It is commutation transitive if the same holds for all non-central elements. Non-abelian CT groups always have trivial center Z(G) = 1, whereas groups like Q\sb{8}, D\sb{8}, \rm{GL}(2,k), and \rm{SL}(2,k) are commutation transitive with non-trivial center. By classical results of Weisner, Suzuki, Brauer–Suzuki–Wall, and Wu, every finite CT group is either abelian, a Frobenius group N \rtimes H with abelian kernel N and cyclic complement H \neq 1, or \rm{PSL}(2, \mathbb{F}\sb{2^f}) for f \geq 2. Along the way, I framed several tempting guesses as “naive conjectures” and settled them: for odd q, \rm{PGL}(2, \mathbb{F}\sb{q}) is never CT, \rm{PSL}(2, \mathbb{F}\sb{q}) is CT only for q \in \{3, 5\}, and passing from \rm{GL}(2, \mathbb{F}\sb{q}) to \rm{PGL}(2, \mathbb{F}\sb{q}) shows that quotienting by the center can destroy commutation transitivity.

Because distinct conjugate centralizers meet only in the center (C \cap xCx^{-1} = Z(G)), inducing linear characters \mu \in \widehat{C} from centralizers organizes the representation theory remarkably well:

  • Short character sums: On non-central elements meeting C, the induced character \rm{Ind}\sb{C}^G \mu collapses to an orbit sum over W(C) = N\sb{G}(C)/C.
  • Irreducibility: In a non-abelian finite CT group, Mackey’s criterion implies \rm{Ind}\sb{C}^G \mu is irreducible if and only if C \trianglelefteq G and \mu \neq \mathbf{1}, so never in \rm{PSL}(2, \mathbb{F}\sb{2^f}).
  • Supports and spanning: Representative permutation characters \mathbf{1}\sb{A\sb{i}}^G are linearly independent, centralizer support vectors in \mathbb{F}\sb{2}^{G\sb{\ast}} span dimension at most 3, and \rm{Ind}\sb{C}^G \mu spans the full character ring R(G) over \mathbb{Z}.

On the graph side, the commuting graph \Gamma(G) on G \setminus Z(G) splits into disjoint complete graphs C \setminus Z(G). Because W(C) acts freely on C \setminus Z(G), sending each element to its conjugacy class gives a harmonic morphism \varphi\sb{G} \colon \Gamma(G) \to \Delta(G) onto the commuting conjugacy class graph. By contrast, on the complementary non-commuting graph \Gamma^c(G), collapsing each centralizer part to a vertex is harmonic only when all non-central centralizers have the same order—which works for Q\sb{8} and D\sb{8} (folding the octahedron K\sb{2,2,2} onto a triangle K\sb{3}), but fails for every non-abelian CT group.

Putting both revisions side by side highlights four sharp mathematical contrasts across group actions, linear groups, characters, and graphs:

  • Two kinds of trivial intersection: The symmetric group paper relies on two different subgroups meeting trivially (H \cap K = 1) to build global coordinates and Cayley graphs. The CT paper relies on a single subgroup meeting its distinct conjugates trivially modulo the center (C \cap xCx^{-1} = Z(G)) to tame Mackey double cosets.
  • Characteristic-free vs. characteristic 2: In the complement paper, \rm{AGL}\sb{1}(q) and \rm{PGL}\sb{2}(q) supply sharp transitivity across all prime powers q. In the CT paper, characteristic 2 is decisive: \rm{PSL}(2, \mathbb{F}\sb{2^f}) is CT for all f \geq 2, whereas odd characteristic q \geq 7 introduces non-abelian dihedral centralizers.
  • Diagonalizing matrices vs. spanning R(G): For arrangement graphs, inducing the trivial character \rm{Ind}\sb{H}^G \mathbf{1} and restricting to a complement K gives the regular representation \mathbb{C}[K], diagonalizing adjacency spectra. For CT groups, permutation characters \mathbf{1}\sb{C}^G cannot separate classes like 5A and 5B in A\sb{5}, making non-trivial characters \mu \in \widehat{C} essential to span R(G).
  • Unramified coverings vs. vertical collapses: Both papers showcase the octahedron—first as J(4,2) doubly covered by the cuboctahedron T(4,2) with no vertical edges, and second as \Gamma^c(Q\sb{8}) folding onto K\sb{3}. Meanwhile, the CT class map \Gamma(G) \to \Delta(G) stays harmonic even when centralizer sizes vary, precisely because conjugate commuting elements absorb the size differences into collapsed vertical edges.