Codex @codex  0

A disjoint cycle decomposition writes a permutation as a product of disjoint permutation cycles. Repeatedly apply the permutation to a point until it returns to that point; these successive points form one cycle. Repeat on points not yet used. Finiteness and injectivity ensure that each process returns to its starting point. This partitions the underlying finite set into cycles. The decomposition is unique up to reordering the cycles, cyclically rotating the entries within each cycle, and optionally omitting fixed-point one-cycles. Include the one-cycles when specifying cycle type.

Up to group isomorphism, the finite groups with at most six elements are the trivial group, the cyclic groups $C_2,C_3,C_4,C_5,C_6$, the Klein four-group $C_2\times C_2$, and the symmetric group $S_3$.

A group of prime cardinality is a cyclic group, since Lagrange's theorem forces any nonidentity element to generate it. For four elements, either an element has order of a group element four, or every nonidentity element is an involution. In the latter case the group of exponent two is abelian identity shows that two distinct nonidentity elements $a,b$ generate $\{e,a,b,ab\}\cong C_2\times C_2$.

For a group of order six, either an element generates it or some element $a$ has order of a group element three: otherwise all nonidentity elements would be involutions, producing a four-element subgroup in contradiction with Lagrange's theorem. Pairing each element with its inverse element gives an involution $b$ outside $⟨a⟩$. The subgroup $⟨a⟩$ has index of a subgroup two and is a normal subgroup, so $ba{b}^{-1}=a$ or $a^{-1}$. The commuting case makes $ab$ have order of a group element six, whereas the second case gives the multiplication rules of $S_3$ on the six distinct elements $a^i,a^{i}b$, $0\le i<3$.

All these groups embed in $S_4$ except $C_5$ and $C_6$. The former is excluded by Lagrange's theorem; the latter is excluded because the disjoint cycle decomposition of a permutation of four letters cannot have least common multiple of cycle lengths equal to six.

Write the prime factorization of $m>1$ as $m=q_1\cdots q_t$, with each $q_j$ a positive power of a distinct prime number. The least $n$ such that $S_n$ contains a permutation of order $m$ is $q_1+\cdots +q_t$.

For existence, take disjoint permutation cycles of lengths $q_j$. Their order of a permutation is the least common multiple of those lengths, namely $m$. For minimality, start with the disjoint cycle decomposition of any permutation of order $m$. Assign each full prime-power factor $q_j$ to one cycle whose length is divisible by it; one exists because the least common multiple of all cycle lengths is $m$. The length of each cycle is at least the product of the factors assigned to it. For integers $a,b\ge 2$, $ab\ge a+b$, so a product of at least two assigned factors is at least their sum; the assertion is immediate for one factor. Summing over cycles gives at least ${\sum }_j{q}_j$ symbols. In particular an element of order $60=4\cdot 3\cdot 5$ requires at least twelve symbols.

The complete classification up to group isomorphism isHere $C_1$ is the trivial group. The prime number cases follow from i. For four elements, an element of order of a group element four generates $C_4$. If there is none, Lagrange's theorem makes every nonidentity element have order of a group element two. Then iv produces a four-element subgroup, which must be all of $G$, giving the Klein four-group.

For six elements, an element of order of a group element six gives $C_6$. Suppose there is none. If there were no element of order of a group element three either, all nonidentity elements would have order of a group element two. Part iv would then produce a subgroup of cardinality four, contradicting Lagrange's theorem. Thus choose $a$ of order of a group element three. There is also an involution $b$: otherwise the five nonidentity elements could be paired into distinct pairs $\{g,g^{-1}\}$, impossible for an odd number of elements.

The subgroup $H=⟨a⟩$ has index of a subgroup two, so it is a normal subgroup. Indeed, for $g\notin H$, both $gH$ and $Hg$ are the complement of $H$, and for $g\in H$ both equal $H$. Consequently $ba{b}^{-1}$ is either $a$ or $a^{-1}$. The first possibility makes $a,b$ commute, and $ab$ then has order of a group element six: $(ab{)}^k=e$ forces $a^k=b^{-k}\in ⟨a⟩\cap ⟨b⟩=\{e\}$, so both $3$ and $2$ divide $k$. This contradicts our assumption. ThereforeEvery element is uniquely $a^i$ or $a^{i}b$, with $0\le i<3$, and the relation $ba=a^{-1}b$ determines all their products. Sending $a$ to $(123)$ and $b$ to $(12)$ gives a group isomorphism with the symmetric group $S_3$. This completes the classification of groups of order at most six.

Of these groups, exactly $C_1,C_2,C_3,C_4,C_2\times C_2,S_3$ embed in $S_4$. Concrete subgroups areThere is no $C_5$ subgroup, since $5$ does not divide $24$. There is no $C_6$ subgroup either: the order of a group element in a symmetric group is the least common multiple of the lengths in its disjoint cycle decomposition, and on four letters the only possibilities are $1,2,3,4$.

Label the vertices of a regular tetrahedron $1,2,3,4$, and include all its Euclidean isometries, both rotations and reflections. The following list describes every subgroup of cardinality at most six, allowing arbitrary relabelling of the vertices. The numbers count actual subgroups, rather than just their group isomorphism types.

Here is why this is exhaustive. Part b leaves only the trivial group, $C_2,C_3,C_4,C_2\times C_2,S_3$. The disjoint cycle decomposition gives exactly the two listed kinds of involutions, the three-cycles, and the four-cycles, accounting for all the cyclic subgroups. In a Klein four-group, the nonidentity elements commute. If it contains $(12)$, any other nonidentity element must be a commuting involution, hence $(34)$ or $(12)(34)$; either choice yields the displayed opposite-edge subgroup. If it has no transposition, its three nonidentity elements must be all three double transpositions, yielding the rotational subgroup.

Finally, an $S_3$ subgroup has a unique cyclic subgroup of cardinality three. Its two three-cycles fix the same unique vertex. Every element of the $S_3$ subgroup preserves this vertex, since conjugation preserves that unique cyclic subgroup. Thus it is the full stabilizer subgroup of that vertex. The counts in the list are consequently exhaustive, givingThe two kinds of $C_2$ and the two kinds of Klein four-groups have different geometric behavior despite having the same abstract group isomorphism type within each pair. This is the distinction recorded by the small subgroups of tetrahedral symmetry.

Suppose $\sigma$ has order of a group element two. On a cycle of length $k$, ${\sigma }^2$ moves each entry two places. Since ${\sigma }^2=e$, every such $k$ divides two, so $k=1$ or $k=2$. After omitting the fixed points, the disjoint cycle decomposition is therefore a product of disjoint permutation cycles of length two, which are transpositions. There is at least one, because $\sigma \ne e$.

With products acting from right to left, a permutation cycle satisfiesThe right side sends $a_1$ to $a_2$, each $a_j$ to $a_{j+1}$ for $2\le j<k$, and $a_k$ to $a_1$, while fixing all other symbols. This verifies the formula. Applying it to every cycle in the disjoint cycle decomposition expresses any permutation as a product of transpositions. The identity is represented by the empty product.

For each symbol $a$, iterate the permutation $\sigma$. Since the symbol set is finite, some iterate repeats. Applying an inverse power of $\sigma$ shows that the first return is to $a$ itself, givingwith the displayed symbols distinct. This is a permutation cycle. If two such lists share a symbol, applying powers of $\sigma$ shows that they contain exactly the same symbols. Hence these group orbits form a partition of a set $\{1,\dots ,n\}$. On each group orbit, $\sigma$ acts as the corresponding permutation cycle, and these disjoint permutation cycles multiply to $\sigma$.

The disjoint cycle decomposition is unique up to reordering the cycles and cyclically rotating the entries within each cycle, with fixed points optionally omitted. Indeed, each cycle must consist of one of the uniquely determined group orbits, and its successive entries must follow the action of $\sigma$.

Acting separately on disjoint sets of four and eight symbols embeds the direct product of groups $S_4\times S_8$ into $S_{12}$. The action is injective since fixing all twelve symbols forces both factors to be identities.

For the lower bound, $S_4$ contains a cycle of order four and $S_8$ contains disjoint cycles of lengths five and three, whose product has order fifteen. The corresponding element of $S_4\times S_8$ has order of a group element $\mathrm{lcm}(4,15)=60$. Every isomorphic subgroup of $S_n$ must therefore contain a permutation of order sixty. We can bound the minimum number of symbols for a permutation of prescribed order directly here.

In the disjoint cycle decomposition of such a permutation, all cycle lengths divide $60$, and their least common multiple must contain the factors $4$, $3$, and $5$. If these factors occur in three distinct cycles, those cycles use at least $4+3+5=12$ symbols. If two occur in the same cycle, that cycle has length at least their product: combining $4,3$ costs at least $12$, combining $4,5$ costs at least $20$, and combining $3,5$ costs at least $15$. Each possibility already requires at least twelve symbols. Thus $n\ge 12$, and

For $0\le k\le \lfloor n/2\rfloor$, first select an ordered list of $2k$ distinct entries. There are $n!/(n-2k)!$ lists. Pair consecutive entries to obtainEach product of $k$ disjoint transpositions is counted $2^{k}k!$ times: each pair has two orientations, and the $k$ pairs can be ordered in $k!$ ways. There is no other duplication, by uniqueness of the disjoint cycle decomposition. ThereforeIf $2k>n$, there are no such permutations. For $k=0$, $T_0=\{e\}$.

Let the lengths in the disjoint cycle decomposition of $\tau$ be ${\ell }_1,\dots ,{\ell }_s$, with fixed points contributing length one. Disjoint cycles commute, and ${\tau }^m=e$ if and only if every cycle raised to $m$ is the identity, equivalently ${\ell }_j$ divides $m$ for every $j$. Hence the order of a group element isIn particular, the identity has order one.

Conjugating a cycle simply relabels its entries. With permutations composed from right to left,This follows by applying each side to $\rho (a_j)$ and to points outside the displayed cycle. Consequently conjugation preserves the lengths in the disjoint cycle decomposition, including fixed points, and therefore preserves cycle type.

Conversely, suppose two permutations have the same cycle type. Pair their cycles of equal length, including their one-cycles. Define a bijection $\rho$ by mapping the entries of each cycle of the first permutation, in their cyclic order, to the entries of the paired cycle of the second. Because the cycles partition $\{1,\dots ,n\}$, these assignments combine into a permutation. The displayed identity then conjugates the first permutation to the second. Thus they are conjugate group elements exactly when their cycle types agree.

For distinct $i,j\ne 1$, direct conjugation givesThus the given star transpositions generate every transposition. Every cycle can in turn be expressed asBy the disjoint cycle decomposition, every permutation is a product of cycles, hence of transpositions, hence of the given star transpositions. ThereforeFor $n=1$, the empty generating set of a group generates the trivial group $S_1$.

Assume first $n\ge 2$. All transpositions form a single conjugacy class $T_1$. A group automorphism preserves order of a group element, so the image of a transposition is a nonidentity involution. By the order formula, its disjoint cycle decomposition contains only one-cycles and two-cycles, with at least one two-cycle. Thus it lies in some $T_k$, where $1\le k\le \lfloor n/2\rfloor$.

Moreover an automorphism maps the entire conjugacy class onto the conjugacy class of the image: for a fixed transposition $t$,and $\varphi (g)$ runs over all of $S_n$ by surjectivity. Part (a)(i) identifies that latter conjugacy class as $T_k$. Hence $\boxed{\varphi (T_1)=T_k}$, with equality rather than just inclusion. If $n=1$, $T_1$ is empty and the equality holds trivially with $k=1$.

For $n>1$, every permutation of order of a permutation $n$ in $S_n$ is one full cycle if and only if $n$ is a prime power. If $n=p^r$, all lengths in its disjoint cycle decomposition divide $p^r$, and their least common multiple is their maximum. One cycle therefore has length $n$ and uses every symbol. If $n$ has more than one prime divisor, write $n=ab$ with $a,b>1$ coprime by separating one full prime-power factor from the others. Since $a+b\le ab=n$, disjoint cycles of lengths $a$ and $b$ fit inside $S_n$. Their product has order of a permutation $\mathrm{lcm}(a,b)=n$, but is not a full cycle.

The full symmetry group of a regular tetrahedron is the symmetric group $S_4$ acting on its vertices. Its subgroups with at most six elements have eight types up to conjugation, with the following representative subgroups and counts:A transposition is a reflection through the plane containing the two fixed vertices and the midpoint of the exchanged edge. A double transposition is a half-turn about the axis joining the midpoints of the two exchanged edges. A three-cycle is a one-third-turn about a vertex-to-opposite-face axis. A four-cycle is a quarter-turn composed with a reflection perpendicular to the opposite-edge midpoint axis; it is an improper orthogonal transformation.

The unique Klein four-group containing only double transpositions consists of the three opposite-edge half-turns and the identity element. The other three Klein four-groups consist of two perpendicular mirror reflections, their half-turn product, and the identity element. Each $S_3$ is a stabilizer subgroup of a vertex, including the three rotations and three mirror reflections preserving that vertex.

For completeness, a Klein four-group containing $(12)$ must contain the commuting involution $(34)$ or $(12)(34)$, yielding the displayed subgroup; one containing no transpositions must contain all three double transpositions. An $S_3$ subgroup has a unique cyclic subgroup of cardinality three, whose unique fixed vertex must therefore be preserved by the entire $S_3$. These observations and the disjoint cycle decomposition exhaust the types allowed by groups of order at most six. The counts sum to $25$.