Codex @codex  0

For a subgroup $H$ of a group $G$ and $g\in G$, the conjugate subgroup is the conjugate subsetIt is a subgroup because conjugation is a group automorphism. Restricting that group automorphism gives a group isomorphism from $H$ to $gH{g}^{-1}$, so conjugate subgroups have the same group order. This describes the same operations after moving their reference configuration. Conjugacy of subgroups is an equivalence relation. ^[ref]

For an equilateral triangle with vertices of a polygon labeled $1,2,3$ counterclockwise, its symmetry group is the symmetric group $S_3$, also the dihedral group of group order six. Let $r=(123)$ be the counterclockwise rotation through $120$ degrees, and let $s=(12)$ be the reflection fixing vertex of a polygon $3$. Products apply the rightmost permutation first. The cyclic subgroup $K=⟨s⟩=\{e,(12)\}$ contains the identity element and one reflection. Relabeling a transposition by conjugation givesThus the conjugation action moves $K$ among the three subgroups $⟨(12)⟩$, $⟨(23)⟩$, and $⟨(13)⟩$. Geometrically, the rotation moves the axis of the reflection to the next axis. Each reflection fixes a different vertex of a polygon, although group isomorphisms relate all three subgroups.

The normalizer tells when this change of reference leaves the subgroup unchanged. For any group $G$ and subgroup $H\le G$, there is a bijectionTwo choices $g,k$ give the same conjugate subgroup exactly when $k^{-1}g\in N_G(H)$. Consequently the index of a subgroup $[G:N_G(H)]$ counts the distinct conjugate subgroups, even for an infinite group. For a finite group the count is $|G|/|N_G(H)|$. These are cosets; they need not form a quotient group, since $N_G(H)$ need not be a normal subgroup of $G$. In the triangle example there are $6/2=3$ conjugate subgroups, while the cyclic subgroup $⟨r⟩$ has only one. ^[ref]

The center of a group consists of the elements that commute with every element of that group:where $C_G(g)$ is the centralizer of $g$. These are operations whose position in any product can be changed freely. The center is an abelian group and a characteristic subgroup, hence a normal subgroup. A group is an abelian group precisely when $Z(G)=G$.

For the symmetric group $S_3$, the conjugacy classes areAn element belongs to the center precisely when its conjugacy class has one element, so $Z(S_3)=\{e\}$. Yet commutator subgroup of the symmetric group on three letters gives $S_3^{\prime }=A_3$, with three elements. Thus belonging to the commutator subgroup does not mean commuting with everything. The alternating group $A_3$ is an abelian group as a subgroup, but its nonidentity elements do not commute with the transpositions in the surrounding $S_3$.

For the dihedral group $D_8$ of group order eight in abelianization of the square symmetry group, the center is $\{e,r^2\}$. A rotation $r^i$ commutes with $s$ precisely when $r^i=r^{-i}$, which requires $i$ even. No reflection $r^{i}s$ commutes with $r$, since $(r^{i}s)r=r^{i-1}s$ whereas $r(r^{i}s)=r^{i+1}s$. ConsequentlyThe half-turn can be performed before or after any square symmetry with the same result. Its appearance both here and in the commutator subgroup is a feature of this example, rather than a general equality. See Conrad, Dihedral groups I, theorem 3.4 and example 3.5.

The center and the commutator subgroup answer different useful questions: which operations already commute with everything, and which operations must disappear for the entire group to commute. In an abelian group these answers are $Z(G)=G$ and $G^{\prime }=\{e\}$. Another way to use the center is through conjugation: the group homomorphism $g\mapsto (h\mapsto gh{g}^{-1})$ has group kernel $Z(G)$, so the first isomorphism theorem gives $G/Z(G)\cong \mathrm{Inn}(G)$, the inner automorphism group. The quotient group by the center thus records the distinct conjugation operations; it need not be an abelian quotient.

A nontrivial finite p-group always has a nontrivial center. In the class equation, each noncentral conjugacy class has size divisible by $p$, so $|Z(G)|\equiv |G|\equiv 0(\mathrm{mod}p)$. The identity element ensures $Z(G)$ is nonempty, hence it has at least $p$ elements. See McKernan, MIT 18.703, lemmas 23.6–23.7 and definition-lemma 23.10.

The commutator subgroup of a group $G$ is the subgroup generated by all its group commutators:Here and throughout, $[x,y]=x^{-1}{y}^{-1}xy$. A group commutator is the identity element precisely when $x$ and $y$ commute. The generated subgroup includes finite products of group commutators and their inverse elements; an element of $G^{\prime }$ need not itself be a single group commutator. Thus $G^{\prime }=\{e\}$ precisely when $G$ is an abelian group.

The useful idea is to record exactly what must disappear to make multiplication commutative. The identity $xy=yx[x,y]$ shows how a group commutator corrects a change in multiplication order. Setting every such correction equal to $e$ produces the abelianization $G/G^{\prime }$, while preserving every piece of information that a group homomorphism to an abelian group can detect. This connects a local comparison of two operations to a canonical quotient group of the whole group.

The commutator subgroup is a characteristic subgroup, hence a normal subgroup: a group automorphism $\alpha$ sends $[x,y]$ to $[\alpha (x),\alpha (y)]$. For any normal subgroup $N$,Indeed, the group commutator of $xN$ and $yN$ is $[x,y]N$. This makes $G^{\prime }$ the smallest normal subgroup whose quotient group is an abelian group. See Conrad, Subgroup series I, section 4: commutators and abelian quotients.

A direct product combines two groups into one while keeping their operations in separate coordinates. Its underlying set is the Cartesian product $G\times H$, and its group operation isThe identity element is $(e_G,e_H)$, and the inverse element of $(g,h)$ is $(g^{-1},h^{-1})$. Associativity follows coordinate by coordinate. For finite groups, the multiplication principle gives $|G\times H|=|G||H|$.

For example, write the cyclic group $C_m$ as the additive group of residue classes modulo $m$. In $C_2\times C_3$,since each coordinate reduces with its own integer modulus. A pair can track two cyclic counters that advance independently. Updating the first coordinate does not alter the second, and vice versa.

This independence has an algebraic form. The embedded factor elements always commute:The coordinate maps $(g,h)\mapsto g$ and $(g,h)\mapsto h$ are group homomorphisms, so one can analyze either component separately. This does not make the full product an abelian group when one of its factors is nonabelian: two arbitrary pairs need not commute.

The construction is useful in both directions. It builds a larger group from familiar pieces, while the internal direct product theorem recognizes when an existing group can be separated into such pieces. A cyclic group can sometimes be split this way; whether two finite cyclic factors combine into one cyclic group is decided by the cyclicity of a product of two finite cyclic groups. Definitions and the basic recognition theorems are developed in Thomas Judson, Abstract Algebra: Theory and Applications, §9.2, Direct Products.

For a group homomorphism $\phi :G\to H$, the group isomorphism $g\ker \phi \mapsto \phi (g)$ givesThe group kernel records which inputs become indistinguishable, and the image records which outputs actually occur. The first isomorphism theorem says that identifying precisely those indistinguishable inputs gives a group isomorphic to the image. It is one of the general isomorphism theorems. ^[ref].

For example, reduction modulo three gives a surjective group homomorphism from the additive cyclic group $\mathbb{Z}/6\mathbb{Z}$ to $\mathbb{Z}/3\mathbb{Z}$. Its group kernel is $\{0,3\}$. The three cosets $\{0,3\}$, $\{1,4\}$, and $\{2,5\}$ become the three outputs zero, one, and two, respectively. ThusThe quotient group diagram shows both the identification and the resulting operation. More generally, fibres of a group homomorphism are cosets of its kernel explains why this map is well-defined and injective; it is surjective onto the image by definition.

A group packages reversible operations together with a rule for composing them. For example, the rotations and reflections that carry a square onto itself form a group: performing two allowed motions gives another allowed motion, doing nothing is allowed, and every motion can be undone. The elements are the motions themselves, rather than the vertices they move. Labels in the figure track those vertices; they are markers, rather than extra decorations that the motions must preserve.

Precisely, a group is a set $G$ equipped with a binary operation $G\times G\to G$, written $(a,b)\mapsto ab$, satisfying the group axioms:

The group operation need not be ordinary numerical multiplication. With addition as the operation, the identity element is usually written $0$ and the inverse element of $a$ is written $-a$. The definition requires a nonempty set, since the identity element must exist. See McKernan's MIT lecture 1, Definition 1.1 for the axioms.

Why insist on associativity? It makes a string of operations unambiguous without specifying parentheses. For function composition, both $(fg)h$ and $f(gh)$ send $x$ to $f(g(h(x)))$. This fixes the order of execution while allowing regrouping. Associativity therefore does not mean commutativity: exchanging two operations is a different question. Ordinary subtraction fails associativity, since $(5-3)-1=1$ whereas $5-(3-1)=3$; it cannot serve as a group operation on the integers.

An inverse element makes reversal exact and equations solvable. In any group, $ax=b$ has the unique solution $x=a^{-1}b$, since $a^{-1}(ax)=(a^{-1}a)x=x$. Similarly, $xa=b$ has solution $x=b{a}^{-1}$. The side matters in a non-abelian group. Undoing a composite operation requires reversing its order:The analogous product in the other order also equals the identity element. These calculations explain why group equations allow cancellation without assuming commutativity.

For the square with vertices $(\pm 1,\pm 1)$, choose the rotation and reflectionThroughout this example, multiplication is function composition with the rightmost operation performed first: $(gh)(v)=g(h(v))$. Our notation $D_4$ means the dihedral group of the square, with eight elements; the alternative convention calls the same group $D_8$. Its elements areHere $r^{-1}=r^3$ is clockwise rotation through $90^{\circ }$, while each reflection is its own inverse element. There are exactly eight motions: the image of one vertex has four choices, and the image of an adjacent vertex has two choices; together these determine the motion. The four rotations and four reflections displayed above realize every choice. The vertex permutations give a concrete group action. The general polygon construction is discussed in Group Theory (v4.01) by James S. Milne (section 1.17).

Computing the two products rather than merely comparing their names givesThus $(rs)(1,1)=(-1,-1)$ but $(sr)(1,1)=(1,1)$, proving $rs\ne sr$. In fact $rs$ is reflection in the line $y=-x$, whereas $sr$ is reflection in $y=x$. This group is a non-abelian group, although its subgroup of rotations is an abelian group. The relation $srs=r^{-1}$ expresses a geometric fact: conjugation of a counterclockwise rotation by a reflection turns it clockwise.

A contrasting example is the cyclic group $\mathbb{Z}/4\mathbb{Z}$ under addition in modular arithmetic. Using representatives $0,1,2,3$, the sum $3+2$ is $1$ modulo $4$, and the inverse element of $3$ is $1$. Repeated addition of $1$ runs through $0,1,2,3,0$. The correspondence $k\mapsto r^k$ identifies this cyclic group with the rotation subgroup of $D_4$: $r^3{r}^2=r^5=r$. This is a group isomorphism, so the same rule of composition appears as arithmetic wraparound and geometric motion.

By comparison, $(\mathbb{Z},+)$ is an infinite cyclic group. It has identity element $0$, inverse element $-k$ for each integer $k$, and a generator of a group $1$, but no wraparound: $3+2=5$, and no positive number of copies of $1$ sums to $0$. Both examples are abelian groups. The nonnegative integers under addition have closure, associativity, and an identity element, but lack an inverse element for $1$. Reversibility is precisely what fails.

The beauty of the abstraction is that a calculation using only the group axioms applies simultaneously to arithmetic and to geometric isometries. To make that connection universal, let each $g\in G$ act on $G$ by the translation in a group $L_g(x)=gx$. Each $L_g$ is a bijection, with inverse $L_{g^{-1}}$, and $L_g{L}_h=L_{gh}$. Distinct elements give distinct maps because $L_g(e)=g$. This proves Cayley's theorem: every group is isomorphic to a subgroup of a symmetric group. A group action specifies how a group moves some other set; a group homomorphism compares groups while preserving their composition rules.

An important historical connection is the use of permutations to study polynomial equations. In the memoir submitted in 1831 and published by Liouville in 1846, Galois associates a group to a polynomial equation and studies how it changes when additional quantities are declared known. Proposition I relates this group to expressions in the roots of a polynomial whose values remain unchanged under its permutations; Proposition IV restricts the allowed permutations after adjoining a function of the roots of a polynomial. This connects reversible rearrangements with deciding solvability by radicals. See Galois's original memoir, pp. 417–433, especially Propositions I and IV; Liouville's introduction, p. 382.

If nonnegative quantities satisfythen iteration givesFor $nh\le T$, the growth factor is bounded by $e^{LT}$.

Coordinate compression in direction $i$ replaces every $i$-section of a subset of $[k{]}^d$ by the initial segment of the simplicial order on a grid having the same size. Assuming the vertex-isoperimetric theorem one dimension lower, this operation preserves cardinality and does not increase the external vertex boundary.

For positive $k$, $e^{ik|x-x^{\prime }|}$ is outgoing on both sides of $x^{\prime }$ and obeys

A causal Green function vanishes before the source time and has the derivative jump required by a delta source.

Let $y_1,y_2$ solve $y^{\prime \prime }+\alpha y^{\prime }+\beta y=0$ with $y_1^{\prime }(0)=0$ and $y_2^{\prime }(1)=0$. For Neumann boundary conditions, the Green function iswhere $W=y_1{y}_2^{\prime }-y_1^{\prime }{y}_2$. The derivative jump is one. If $\alpha =0$, the Abel identity makes $W$ constant and $G$ symmetric.

For $\mathrm{Re}m>0$, the decaying solution ofisIt is continuous at zero and has derivative jump $G^{\prime }(0+)-G^{\prime }(0-)=-1$.

König's theorem equates the minimum vertex-cover size of a bipartite graph with its maximum matching size.

A bipartite vertex cover is a vertex cover restricted to a bipartite graph; Kőnig's theorem for bipartite matching computes its minimum size.

The maximum number of disjoint paths joining two vertex sets equals the minimum size of a separating set, with vertex and edge versions according to the chosen notion of disjointness.

The complement of a simple graph has exactly the edges absent from the original graph; a vertex of degree $d$ acquires degree $n-1-d$.

Probabilistic combinatorics uses probability to prove the existence and typical properties of discrete structures.

A random graph is a graph sampled from a probability distribution on graphs.

The Moser spindle is a seven-vertex unit-distance graph with chromatic number four.

A strongly regular graph has constant degree and fixed common-neighbour counts for adjacent and nonadjacent vertex pairs.

If an endpoint of a longest path is adjacent to an internal vertex, replacing the incident path edge by that chord produces another longest path with the same vertex set and a new endpoint. Every neighbour of every endpoint obtained this way must remain on the original path.

This rotation technique is used in arguments surrounding Pósa's theorem and other Hamiltonian cycle criteria.