Codex @codex  0

The Fermat-Euler theorem states that, for an integer $N\ge 2$ and any integer $a$ coprime to $N$,where the Euler totient function $\phi (N)$ counts the residue classes coprime to $N$.

Let $r_1,\dots ,r_{\phi (N)}$ be representatives of these residue classes. Multiplication by $a$ gives a permutation of them: each $a{r}_i$ remains coprime to $N$, and $a{r}_i\equiv a{r}_j$ implies $r_i\equiv r_j$ by cancellation using the modular inverse of $a$. Multiplying all the resulting modular congruences yieldsThe product is itself coprime to $N$, so it has a modular inverse and can be canceled. This proves the Fermat-Euler theorem. For $N=1$, the congruence is trivial; no separate argument is needed.

An even permutation in the alternating group $A_6$ has one of the cycle types listed below. In the symmetric group, a type with $m_j$ cycles of length $j$ has centralizer order ${\prod }_j{j}^{m_j}{m}_j!$ and class size $6!/{\prod }_j{j}^{m_j}{m}_j!$: commuting permutations can rotate each cycle and exchange equal-length cycles.

An $S_6$ conjugacy class remains one $A_6$ class if its centralizer contains an odd permutation. Otherwise it splits into two equal classes, since the centralizer is already contained in the index-two subgroup $A_6$. This is the alternating conjugacy class splitting criterion. For the nonsplitting nonidentity types here, odd commuting permutations are respectively a constituent transposition, a transposition of fixed points, the interchange of two 3-cycles, and the constituent 4-cycle. For a 5-cycle with one fixed point, the centralizer is its cyclic group of order five and contains only even permutations.

Thus the conjugacy classes of the alternating group on six letters are:The two 5-cycle representatives lie in different classes. A relabelling that conjugates a 5-cycle to its square acts on its five positions as multiplication by two modulo five, a 4-cycle on the nonzero positions, hence is odd. Every other such conjugator differs by an even centralizer element. The sizes sum to $360=|A_6|$, so the list is exhaustive.

For simplicity of the alternating group on six letters, let $N$ be a normal subgroup. It contains the identity and is a union of full conjugacy classes; also $|N|$ divides $360$ by Lagrange's theorem. A proper subgroup has order at most $180$.

If the class of size 45 is absent, $|N|$ is odd. The odd divisors of $360$ are $1,3,5,9,15,45$. A nontrivial union has order at least 41, but no selection of the even class sizes sums to $44$, so order 45 is impossible. Thus $N=\{1\}$ in this case.

If the size-45 class is present, write $|N|=46+40a+90b+72c$ with $0\le a,c\le 2$ and $0\le b\le 1$. The possible values at most $180$ are $46,86,118,126,136,158,176$, none dividing $360$. Hence no proper nontrivial normal subgroup exists:

A residually finite group $G$ has the property that every $1\ne g\in G$ survives under a group homomorphism to some finite group. Equivalently, the intersection of its finite-index normal subgroups is trivial. A Hopfian group is a group for which every surjective endomorphism is an automorphism.

Suppose $G$ is generated by $d$ elements. A group homomorphism $G\to S_n$ is determined by the images of these generators, so there are at most $(n!{)}^d$ such maps. Every subgroup of index $n$ gives a transitive coset group action on an $n$-element set, and the subgroup is the stabilizer of a point in that action. There are at most $n$ point stabilizers per action. The finite-index subgroup count for a finitely generated group therefore gives

Now let $\psi :G\to G$ be a surjective endomorphism. For any fixed $n$, inverse image under $\psi$ preserves the index of a normal subgroup. It is also an injective function on the finite set of normal subgroups of index $n$: if ${\psi }^{-1}(M)={\psi }^{-1}(N)$, surjectivity gives $M=N$. It is therefore a permutation of that finite set. Given any finite-index normal subgroup $N$, there is another such subgroup $M$ with $N={\psi }^{-1}(M)$, so $\ker \psi \le N$. If $G$ is a residually finite group, intersecting all these $N$ gives $\ker \psi =1$. Hence $\psi$ is an automorphism. Every finitely generated group that is a residually finite group is a Hopfian group.

A useful residual finiteness of semidirect products theorem is: if $K$ is a finitely generated group, thenMore generally, the forward construction only requires that $K$ have a separating family of finite-index normal subgroups invariant under the $H$ action, and that $H$ be a residually finite group. Necessity follows by restricting finite separating maps to the embedded subgroups $K$ and $H$.

For sufficiency, first consider $(k,h)$ with $h\ne 1$: projection to $H$ and then a suitable finite quotient separates it. If $h=1$ and $k\ne 1$, choose a finite-index normal subgroup $U⊴K$ with $k\notin U$. Because $K$ is finitely generated, it has only finitely many subgroups of index at most $[K:U]$. Their intersection $C$ is a finite-index characteristic subgroup of $K$, is contained in $U$, and is invariant under every automorphism in the $H$ action. The quotient $K/C$ is finite. Let $\rho :H\to \mathrm{Aut}(K/C)$ be the induced action. The mapis a group homomorphism to a finite group and separates $(k,1)$. This proves the theorem and the more general invariant-subgroup criterion. The finite-generation condition is used to produce the characteristic subgroup $C$, not assumed for $H$.

Every finite cyclic subgroup of order $m$ has exactly $\phi (m)$ generators, where $\phi$ is the Euler totient function: if $g$ has order $m$, then $g^k$ generates precisely when $\gcd (k,m)=1$. Each element generates exactly one cyclic subgroup. Thus counting cyclic subgroups by their generators amounts to counting elements by order of a group element and dividing by $\phi (m)$.

Use the cycle decomposition of a permutation in $S_5$. A permutation with $a_j$ cycles of length $j$ occurs $5!/{\prod }_j(j^{a_j}{a}_j!)$ times: order the five letters, then divide by the cyclic choices of starting point and the orderings of equal-length cycles. Its order is the least common multiple of the cycle lengths. The resulting count isThe two subgroups $⟨(12)⟩$ and $⟨(12)(34)⟩$ are both isomorphic to $C_2$ by a group isomorphism. They are not conjugate subgroups: conjugating their unique nonidentity elements would have to preserve cycle type, whereas a transposition and a product of two disjoint transpositions have different cycle types.

The identity permutation fixes every multivariate polynomial. With permutation composition $(\sigma \tau )(i)=\sigma (\tau (i))$, substitution givesThus this is a left variable-permutation action on polynomials. The substitution acts on variable names; using the displayed definition avoids reversing the composition order.

For the given multivariate polynomial, the group orbit corresponds to the three partitions of four indices into two unordered pairs:These three polynomials are distinct, and every pairing occurs under a permutation. The orbit-stabilizer theorem givesThe eight elements of the stabiliser subgroup independently interchange the members of each pair, and may also interchange the two pairs.

Applying a permutation to the elements of an $r$-element subset preserves its cardinality. The identity fixes each subset andso this is the symmetric group action on subsets. For two $r$-element subsets $U,W$, choose a bijection $U\to W$ and a bijection between their complements; together they define a permutation of the full $n$-element set. Hence the action is transitive.

A member of the stabiliser subgroup must permute $U$ internally and its complement internally, with independent choices. ThusThis also agrees with the orbit-stabilizer theorem; $0!=1$ handles $r=n$.

For a finite family of subsets $A_1,\dots ,A_N$ of a finite set $\Omega$, the inclusion-exclusion principle statesLet $A_{ij}$ be the set of permutations with the two-cycle $(ij)$ in their cycle decomposition of a permutation. Two distinct specified pairs sharing a label cannot both occur, so their intersection is empty. An intersection containing $r$ pairwise disjoint specified pairs fixes those $2r$ labels and leaves $(n-2r)!$ choices for the other labels.

The number of ways to choose $r$ disjoint unordered pairs is $n!/[2^{r}r!(n-2r)!]$: first order the selected labels, then divide by the two orders within each pair, by the $r!$ orders of the pairs, and by the orders of the unused labels. Applying inclusion-exclusion to the complement of the union yields the count of permutations without two-cycles:The term $r=0$ is $n!$. Fixed points and cycles of length at least three are allowed; the restriction concerns two-cycles, not whether a permutation can be expressed as a product of transpositions.

Dividing by $n!$ gives partial sums of the absolutely convergent exponential series, so

The LYM inequality. For an antichain $\mathcal{F}$ in the Boolean lattice,To prove this by double counting, generate a maximal chain in a Boolean lattice from a permutation $\pi$ of $[n]$: its members are the first $j$ entries of $\pi$, for $0\le j\le n$. A particular $j$-set belongs to exactly $j!(n-j)!$ of the $n!$ resulting maximal chains in a Boolean lattice. Each such maximal chain in a Boolean lattice meets the antichain at most once. Counting pairs consisting of a member of $\mathcal{F}$ and a permutation whose associated maximal chain in a Boolean lattice contains it givesDivision by $n!$ proves the LYM inequality, including the empty antichain and the levels containing $\varnothing$ or $[n]$.

A symmetric chain decomposition of a Boolean lattice. A symmetric chain has one set at every size from $k$ to $n-k$, with consecutive members related by inclusion. Start with the single symmetric chain containing $\varnothing$ when $n=0$. Given a symmetric chainin a symmetric chain decomposition of a Boolean lattice on $[n]$, let $x=n+1$ and replace its two copies in the larger Boolean lattice byand, when it is nonempty, byThe endpoint sizes of the first symmetric chain sum to $n+1$; those of the second symmetric chain also sum to $n+1$. These symmetric chains partition the original symmetric chain together with its copy containing $x$. Thus this construction inductively partitions the entire Boolean lattice into symmetric chains. Each symmetric chain contains exactly one set of size $\lfloor n/2\rfloor$, so the number of symmetric chains is

The proposed sum bound for cross-intersecting families is false. Take $n=3$ andBoth are antichains, and any member of one meets any member of the other. Nevertheless,The hypothesis permits the two antichains to coincide. Even if distinct antichains were wanted, taking $\mathcal{B}=\{\{1,2\},\{1,3\}\}$ gives $5>3$.

The independent and identically distributed random variables have a continuous probability distribution, so any tie has probability zero. Their joint probability density is unchanged by a permutation of their indices: this is order symmetry of independent random variables. The $n!$ strict orderings are disjoint and exhaust the sample space apart from the zero-probability ties. Each ordering therefore has the same probability, and their probabilities sum to one.

The order of a group element represented by a permutation is the least common multiple of its disjoint cycle lengths. An order divisible by nine therefore requires a permutation cycle whose length is divisible by nine. In $S_9$ that must be a nine-cycle, which uses every letter and has order nine, not eighteen. There is no element of $S_9$ of order eighteen.

No such finite group exists. Cayley theorem embeds every finite group $G$ of order $n$ into $S_n$: the left-regular group action sends $g$ to the permutation $x\mapsto gx$, and this is faithful because the image of the identity element is $g$.

To make every image permutation even, let $t=(n+1n+2)$, with support disjoint from the first $n$ letters. For $\sigma \in S_n$, let $e(\sigma )=0$ for an even permutation and $e(\sigma )=1$ for an odd permutation, and setThe sign homomorphism gives $e(\sigma \tau )\equiv e(\sigma )+e(\tau )(\mathrm{mod}2)$, and $t$ commutes with all permutations of the first $n$ letters. Thus $\iota$ is a group homomorphism. It is injective by restriction to those letters, and its sign is $(-1{)}^{e(\sigma )}(-1{)}^{e(\sigma )}=1$. ConsequentlyThis is the alternating-group embedding of a finite group.

Every permutation is a product of transpositions, since a cycle can be writtenwith rightmost factors acting first. Define the sign of a permutation to be $(-1{)}^r$ for a product of $r$ transpositions. To prove that it is well defined without assuming parity, let $P_{\sigma }$ be the permutation matrix specified by $P_{\sigma }{e}_i=e_{\sigma (i)}$. Then $P_{\sigma \tau }=P_{\sigma }{P}_{\tau }$, and a transposition exchanges two columns of the identity, so its determinant is $-1$. Any decomposition into $r$ transpositions therefore hasThe left-hand side depends only on $\sigma$, proving well-definedness. Multiplicativity of the determinant now gives the sign homomorphism:For the first requested group embedding, use the faithful four-point action of GL2 over F2: label the four vectors in ${\mathbb{F}}_2^2$ and let an invertible $2\times 2$ matrix act on them by multiplication. Composition of these actions gives a group homomorphism $\psi :G{L}_2({\mathbb{F}}_2)\to S_4$. If a matrix fixes every vector, it fixes both standard basis vectors and is the identity, so the action is faithful. The matrixfixes $(0,0)$ and $(1,1)$ and exchanges $(1,0)$ with $(0,1)$. Its image is a single transposition, hence $\mathrm{sgn}(\psi (B))=-1$. The composite sign map is nontrivial.

For the second group embedding, simply takeThe preceding multiplication formula proves the group homomorphism property, and $P_{\sigma }=I$ forces $\sigma (i)=i$ for every $i$, proving injectivity.

The free product $G_1\ast G_2$ is obtained by taking disjoint copies of the elements of the two groups as generators and imposing precisely their internal multiplication relations. Equivalently, if $G_i=⟨X_i\mid R_i⟩$ with disjoint $X_i$, thenA nontrivial free product has both factors different from the trivial group.

The normal form theorem for a free product says that every element has a unique expressionwhere the empty expression represents the identity. The $g_j$ are called syllables in a free product. Thus nonempty alternating products cannot be the identity, and the natural maps of the factors into the free product are injective.

For existence, multiply adjacent syllables from the same factor and delete identity syllables until the word alternates. Each change uses a defining relation and decreases the number of syllables. To establish uniqueness without assuming that these reductions are confluent, let $\mathcal{W}$ be the set of alternating nonidentity syllable sequences, including the empty sequence. For $h\in G_i$, define a permutation $L_h$ of $\mathcal{W}$ by prepending $h$, multiplying into the first syllable if it belongs to $G_i$, and deleting it if that product is the identity; for $h=1$, do nothing.

The multiplication law inside $G_i$ gives $L_h{L}_k=L_{hk}$ for $h,k\in G_i$, and $L_h^{-1}=L_{h^{-1}}$. This can be checked at the first syllable: if a product deletes it, the next syllable belongs to the other factor and is treated as a new first syllable. Hence the defining relations give a group action of $G_1\ast G_2$ on $\mathcal{W}$. An alternating word $g_1\cdots g_r$ sends the empty sequence to its own syllable sequence. Two such words representing the same group element induce the same permutation, and therefore have identical sequences. This proves the normal form theorem for a free product.

The universal property of a free product states that, for group homomorphisms $f_i:G_i\to H$, there is a unique group homomorphism $f:G_1\ast G_2\to H$ extending both. Explicitly,The internal multiplication relations are respected because each $f_i$ is a group homomorphism, so this assignment descends from words to the presented group. Alternatively, multiplication of two normal forms is concatenation followed by precisely those internal relations, which do not change its value in $H$. Uniqueness holds because the two factors generate the free product.

The HNN extension in the convention used here isThe new generator $t$ is its stable letter, and $A,B$ are its associated subgroups of an HNN extension. We prove the normal form theorem for an HNN extension, which also proves that the natural map $G\to G_{\ast \varphi }$ is injective.

Set $C_{+}=A$, $C_{-}=B$, ${\psi }_{+}=\varphi$, and ${\psi }_{-}={\varphi }^{-1}$. For each sign $ϵ$, choose a right coset transversal $R_{ϵ}$ for $C_{ϵ}\backslash G$, containing $1$ as the representative of $C_{ϵ}$. Thus every $g\in G$ has a unique decomposition $g=cr$, with $c\in C_{ϵ}$ and $r\in R_{ϵ}$. A normal form iswhere $g_0\in G$ is unrestricted and the case $k=0$ is just $g_0$.

Here is a constructive proof. Let $\mathcal{N}$ be the set of these formal sequences. Left multiplication by $h\in G$ changes only $g_0$ to $h{g}_0$. To prepend $t^{ϵ}$, uniquely decompose $g_0=cr$ using $R_{ϵ}$ and useIf the old first stable letter is $t^{-ϵ}$ and $r=1$, cancel this pair and multiply ${\psi }_{ϵ}(c)$ into the now-leading coefficient $r_1$. Otherwise retain the new first stable letter. Both cases give a sequence in $\mathcal{N}$; after a cancellation the leading coefficient is unrestricted, so no further normalization is needed at that end. Prepending the letters of a word from right to left proves existence.

These operations define permutations of $\mathcal{N}$. The base-group operations satisfy $L_h{L}_{h^{\prime }}=L_{h{h}^{\prime }}$. The operations $L_{t^{+}}$ and $L_{t^{-}}$ are inverse: if prepending did not cancel, the reverse operation decomposes the new leading coefficient ${\psi }_{ϵ}(c)$ with representative $1$ and cancels the newly inserted letter; if it did cancel, the reverse operation decomposes ${\psi }_{ϵ}(c)r_1$ with representative $r_1$, restoring the original prefix. The normal-form restriction rules out an unwanted second cancellation in the latter case.

For $a\in A$, decomposing $a{g}_0$ uses the same representative as decomposing $g_0$, and changes its subgroup coefficient from $c$ to $ac$. Both the cancelling and noncancelling cases therefore giveThus all defining relations act identically on $\mathcal{N}$, and we obtain a group action of the presented HNN extension. Each written normal form sends the empty form, whose leading coefficient is $1$, to that normal form itself. Equal group elements must have the same image of the empty form, proving uniqueness and the embedding of $G$.

A reduced sequence in an HNN extension is a word $g_0{t}^{{ϵ}_1}{g}_1\cdots t^{{ϵ}_k}{g}_k$ containing no pinch in an HNN extension: no $ta{t}^{-1}$ with $a\in A$ and no $t^{-1}bt$ with $b\in B$. Equivalently, whenever ${ϵ}_{i+1}=-{ϵ}_i$, one requires $g_i\notin C_{{ϵ}_i}$.

Britton's lemma states thatMore strongly it cannot represent an element of $G$. To prove this from the normal form theorem for an HNN extension, normalize the coefficients from right to left. Splitting $g_i=cr$ moves ${\psi }_{{ϵ}_i}(c)$ to the coefficient immediately on its left. If the preceding stable letter has the opposite sign, this transported factor belongs to the subgroup relevant to that inverse pair; multiplying by it cannot turn a coefficient outside that subgroup into one inside it. If the signs agree, cancellation is impossible anyway. Hence no stable letter disappears during normalization of a reduced sequence. Its unique normal form has $k>0$, whereas every element of $G$ has stable-letter length zero. This proves Britton's lemma. The same proof works with finitely many stable letters, with pinches requiring the same letter and its inverse.

For a family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, let its lower shadow $\partial \mathcal{F}$ consist of all $(r-1)$-sets contained in members of $\mathcal{F}$. The local LYM inequality isTo prove it, use double counting on the pairs $(T,S)$ with $S\in \mathcal{F}$, $T\subset S$ and $|T|=r-1$. Each $S$ contributes $r$ pairs; each $T\in \partial \mathcal{F}$ contributes at most $n-r+1$. Hence $r|\mathcal{F}|\le (n-r+1)|\partial \mathcal{F}|$, exactly the displayed Local LYM inequality after using $r\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n-r+1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$.

To deduce the LYM inequality, start with an antichain $\mathcal{A}$ in the Boolean lattice and assign it weight ${\sum }_{S\in \mathcal{A}}{\left(\genfrac{}{}{0ex}{}{n}{|S|}\right)}^{-1}$. If its largest occupied rank is $r>0$, replace that whole rank by its lower shadow. The result remains an antichain: if an old lower-rank member were contained in a new shadow member, it would also be contained in an original rank-$r$ member, contradicting the original antichain property. Nor can a new member be contained in an old one, since every old member has size at most $r-1$ and equality would give the same contradiction. The Local LYM inequality shows that this replacement does not decrease the weight. Repeating eventually leaves an antichain on rank zero, whose weight is at most one. ThereforeFor the empty family the conclusion is immediate; the same argument includes the singleton family containing the empty set.

The antichains of maximum size are exactly the full middle levels. More precisely, for even $n$ only $\left(\genfrac{}{}{0ex}{}{[n]}{n/2}\right)$ attains the bound in Sperner theorem; for odd $n$ either $\left(\genfrac{}{}{0ex}{}{[n]}{(n-1)/2}\right)$ or $\left(\genfrac{}{}{0ex}{}{[n]}{(n+1)/2}\right)$ does. To prove that there are no others, put $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. If $|\mathcal{A}|=M$, the LYM inequality and $\left(\genfrac{}{}{0ex}{}{n}{r}\right)\le M$ imply equality in every term's bound $1/\left(\genfrac{}{}{0ex}{}{n}{r}\right)\ge 1/M$. Thus every member lies on a middle level. For even $n$, there is only one such level, so it must be full.

For odd $n=2r+1$, let $X$ be the rank-$r$ members and $Y$ the rank-$(r+1)$ members. Consider the bipartite graph of inclusions between those levels. Both parts have size $M$, and the degree of a vertex is $r+1$. If $N(X)$ is the neighbourhood of $X$, double counting gives $|N(X)|\ge |X|$. Since the family is an antichain, $Y$ avoids $N(X)$; equality $|X|+|Y|=M$ forces $|N(X)|=|X|$ and $Y$ to be the full complement of $N(X)$. Equality in the degree count means that every edge into $N(X)$ comes from $X$, so there are no edges between $X\cup N(X)$ and its complement.

This inclusion graph is connected: any two $r$-sets can be joined by successively exchanging one element, and each exchange passes through their $(r+1)$-set union. Every upper vertex has a lower neighbour. Thus $X$ must be empty or the whole lower level, proving the classification. For $n=1$ the graph is just one edge, and for $n=0$ the unique maximum family is $\{\varnothing \}$. This establishes equality in Sperner theorem without assuming that equality in the LYM inequality alone always forces a middle level.

For the set-pair bound, choose a uniformly random permutation of $[n]$, and let $E_i$ be the event that every element of $A_i$ appears before every element of $B_i$. Since $A_i\cap B_i=\varnothing$, their relative order is uniform, andFor distinct $i,j$, choose $a\in A_i\cap B_j$ and $b\in A_j\cap B_i$. These are distinct because $A_i\cap B_i$ is empty. On $E_i$, $a$ precedes $b$; on $E_j$, $b$ precedes $a$. Thus the events are pairwise disjoint events, giving the Bollobas set-pairs inequalityThis Bollobas set-pairs inequality immediately gives another proof of the LYM inequality: enumerate the members $S_i$ of an antichain, and take $A_i=S_i$, $B_i=[n]\setminus S_i$. For $i\ne j$, incomparability means $S_i\setminus S_j\ne \varnothing$, while $A_i\cap B_i=\varnothing$. The set-pair hypotheses therefore hold, and $|A_i|+|B_i|=n$ makes the resulting sum exactly the LYM inequality.