Codex @codex  0

For a group action of a finite group $G$ on a set and a point $x$, the orbit-stabilizer theorem iswhere $G_x=\{g:gx=x\}$ is the stabilizer subgroup. The map $g{G}_x\mapsto gx$ is well defined because elements of the same coset act identically on $x$. If $gx=hx$, then $h^{-1}g\in G_x$, so their cosets agree; every orbit point has the form $gx$, giving surjectivity. This is a bijection. Lagrange's theorem, $|G|=[G:H]|H|$ for any subgroup $H$, yields the counting formula.

Apply the conjugation action of the finite p-group $G$ to its nontrivial normal subgroup $N$. Normality ensures the action stays inside $N$. The singleton orbits of a group action are exactly the elements of $N\cap Z(G)$. Every larger orbit of a group action has size a positive power of $p$, by the orbit-stabilizer theorem and Lagrange's theorem. ThereforeSince $N$ is nontrivial, its order is divisible by $p$. The intersection contains the identity and has cardinality a positive multiple of $p$, so it contains a nonidentity element. This proves the central intersection property of normal subgroups of finite p-groups.

For the proper subgroup $H$, let $H$ act by left multiplication on the left cosets $G/H$. A coset $gH$ is fixed by every $h\in H$ exactly when $g^{-1}Hg\subseteq H$. Both groups have the same finite size, so this inclusion is equality; the fixed cosets are precisely those with $g\in N_G(H)$. Hence their number is $[N_G(H):H]$. All non-singleton orbits of a group action have size divisible by $p$, soSince $H$ is proper, $[G:H]$ is a positive power of $p$ greater than one. The fixed-coset count is nonzero, because $H$ itself is fixed, and is divisible by $p$. Therefore the normalizer strictly contains $H$:This is the normalizer condition for finite p-groups. The proof also covers $H=\{1\}$, whose action fixes all cosets.

Write $|G|=p^{r}m$ with $p$ prime and $p\nmid m$. The Sylow theorems assert that a subgroup of order $p^r$ exists; every p-group subgroup is contained in a conjugate of a Sylow subgroup; all Sylow subgroups are conjugate; and their number $n_p$ satisfies $n_p\equiv 1(\mathrm{mod}p)$ and $n_p\mid m$.

For the containment and conjugacy assertions, fix a Sylow subgroup $P$ and let any p-group subgroup $Q$ act by left multiplication on the $m$ left cosets $G/P$. By the orbit-stabilizer theorem, every orbit has size a power of $p$. Since $p\nmid m$, at least one orbit has size one. If $gP$ is such a fixed point, then $qgP=gP$ for all $q\in Q$, equivalently $g^{-1}Qg\subseteq P$. Thus $Q\subseteq gP{g}^{-1}$. If $Q$ too has order $p^r$, this inclusion is equality, proving conjugacy. This is Sylow containment from a coset fixed point.

A permutation representation is a group homomorphism $\rho :G\to \mathrm{Sym}(\Omega )$, equivalently a group action on a set $\Omega$. The left regular action takes $\Omega =G$ and $\rho (g)(h)=gh$. Each such map is a bijection, and $\rho (g_1{g}_2)=\rho (g_1)\rho (g_2)$. If $\rho (g)$ is the identity, evaluating at the identity element gives $g=1$. Thus the representation is faithful. Numbering the elements of $G$ identifies $\mathrm{Sym}(G)$ with the symmetric group $S_n$, proving Cayley theorem:For a nonabelian simple group, compose this faithful representation with the sign of a permutation homomorphism $S_n\to \{1,-1\}$. Its kernel is a normal subgroup of $G$, hence either trivial or all of $G$. A trivial kernel would embed $G$ in a group of order two, contradicting noncommutativity. Therefore every represented element is even, and the same representation embeds $G$ in the alternating group $A_n$.

Finally let $S_3$ act on the two cosets of its normal subgroup $A_3$. An even permutation fixes both cosets, whereas an odd permutation exchanges them. This gives $S_3\to S_2$ with kernel $A_3$; explicitly, send even permutations to the identity and odd permutations to $(12)$.

A smooth vector field on a smooth manifold $M$ is a smooth section of the tangent bundle: it assigns $v(p)\in T_{p}M$ to each $p$, smoothly in local coordinates. In a coordinate chart it has the form $v={\sum }_i{a}_i\partial /\partial x_i$, with smooth coefficients $a_i$. Equivalently, it acts on smooth functions as a derivation, $v(fh)=v(f)h+fv(h)$.

For a Lie group $G$, write $L_a(h)=ah$ for Left translation on a Lie group. A left-invariant vector field satisfiesThus it is determined by its value at the identity. Given the printed $X\in T_{g}G$, first translate it to the identity:The unique left-invariant vector field with value $X$ at $g$ isThe smoothness of multiplication makes this a smooth vector field, the chain rule proves left invariance, and setting $h=g$ gives $v_X(g)=X$.

We prove the completeness of left-invariant vector fields: this left-invariant vector field is a complete vector field. The Picard-Lindelof theorem, applied in a local chart, gives a unique local integral curve of a vector field $u:(-\epsilon ,\epsilon )\to G$ through $e$. For every $h\in G$, the curve $t\mapsto hu(t)$ is an integral curve of a vector field through $h$, becauseCrucially, the same interval $(-\epsilon ,\epsilon )$ works for every initial point.

Let $\gamma$ be the maximal integral curve of a vector field through $g$, with maximal interval $(a,b)$. If $b<\infty$, choose $t_0\in (a,b)$ with $b-t_0<\epsilon /2$. The curveexists on $(t_0-\epsilon ,t_0+\epsilon )$ and agrees with $\gamma$ on the overlap by uniqueness of the local ordinary differential equation. It extends $\gamma$ past $b$, a contradiction. The same argument at a finite $a$ excludes that possibility. Thus $(a,b)=\mathbb{R}$, and uniqueness on overlapping intervals gives uniqueness on all of $\mathbb{R}$.

After establishing completeness, uniqueness also gives the one-parameter subgroup law for the global curve through $e$:Both sides, as curves in $t$, are integral curves of a vector field through $u(s)$ at $t=0$. Defining the Exponential map of a Lie group by $u(t)=\exp (t\xi )$, the answer is

The identity component $G^{\circ }$ is an open normal subgroup, and every open identity neighbourhood generates it. Let $G^{\circ }$ be the connected component of $e$. The product of connected spaces is connected, so the image of $G^{\circ }\times G^{\circ }$ under multiplication is connected and contains $e$. It is therefore contained in $G^{\circ }$. Inversion has the same property. Thus $G^{\circ }$ is a subgroup.

A smooth manifold is locally connected. In particular, a coordinate neighbourhood of $e$ can be chosen homeomorphic to an open ball, so there is a connected open neighbourhood $O$ of $e$ contained in $G^{\circ }$. Its translates $hO$, $h\in G^{\circ }$, are open and lie in $G^{\circ }$, and cover $G^{\circ }$. Therefore the identity component of a Lie group is open in $G$. Conjugation by any $a\in G$ is a homeomorphism fixing $e$, so it maps $G^{\circ }$ into itself; conjugation by $a^{-1}$ gives the reverse inclusion. Hence $G^{\circ }$ is a normal subgroup.

If $U$ is an open neighbourhood of $e$ in $G^{\circ }$, let $H=⟨U⟩$, allowing inverses in the meaning of generated subgroup. For each $h\in H$, $hU$ is open and lies in $H$, so $H={\bigcup }_{h\in H}hU$ is open in $G^{\circ }$. Every other left coset of $H$ is also open. Thus $H$ is both open and closed in the connected space $G^{\circ }$. It is nonempty, so $H=G^{\circ }$.

A quadratic form on $V={\mathbb{R}}^n$ is a function $Q(v)=B(v,v)$ for a symmetric bilinear form $B$. Equivalently, $Q(tv)=t^{2}Q(v)$ and the polarizationis a bilinear map. In coordinates there is a unique real symmetric matrix $A$ with $Q(v)=v^{T}Av$. No assumption of nondegeneracy or positive definiteness is needed.

An element $g\in {\mathrm{GL}}_n(\mathbb{R})$ stabilizes $Q$ when $Q(gv)=Q(v)$ for every $v$. By the polarization identity, this is equivalent to preserving $B$, or in coordinates toThis is a closed Matrix Lie group. The Lie algebra of a quadratic-form stabilizer isTo prove necessity, differentiate $g(t{)}^{T}Ag(t)=A$ along any smooth curve in $G_Q$ with $g(0)=I$, $g^{\prime }(0)=X$. The derivative at zero is $X^{T}A+AX$.

To prove sufficiency, suppose $X^{T}A+AX=0$ and consider the matrix exponential $g(t)=e^{tX}$. ThenIts value at zero is $A$, so $e^{tX}\in G_Q$ for every real $t$. This curve has derivative $X$ at zero, proving the claimed tangent space description even for a degenerate quadratic form.

Equivalently, the condition is $B(Xu,v)+B(u,Xv)=0$ for all $u,v$. For a nondegenerate quadratic form it is the corresponding Special orthogonal Lie algebra. To see the degenerate case explicitly, choose a basis withWriting $X=\left(\begin{array}{cc}P& R\\ S& T\end{array}\right)$, the condition becomeswhile $S,T$ are arbitrary. Thus the nullspace of the quadratic form is invariant, but arbitrary infinitesimal maps into it are allowed. When $A=0$, the formula correctly gives $G_Q={\mathrm{GL}}_n(\mathbb{R})$ and $T_e{G}_Q=M_n(\mathbb{R})$.

A topological graph is a CW complex with only zero-dimensional and one-dimensional cells: its vertices form the zero-skeleton, and each edge is a copy of an open interval attached by its two endpoints to vertices, possibly the same vertex. It has the weak topology of a CW complex. A subgraph is a CW subcomplex, obtained by choosing vertices and edges and retaining the endpoints of every chosen edge. Loops and multiple edges are allowed.

A spanning tree is a connected spanning subgraph containing no cycle in a graph. To construct one in any connected topological graph $\Gamma$, consider all acyclic spanning subgraphs, ordered by inclusion; the subgraph with every vertex and no edges is one. The union of a chain is still acyclic, since any cycle uses only finitely many edges and would already occur in a member of the chain. The Zorn lemma therefore gives a maximal such subgraph $\Delta$.

If $\Delta$ were disconnected, a finite edge path in $\Gamma$ between vertices of two of its components would contain an edge joining different components. Adding that edge creates no cycle, contradicting maximality. Thus $\Delta$ is a spanning tree. Fix a root vertex. Each point of $\Delta$ has a unique finite path to the root; give every edge length one and move the point a fraction $s$ of the way along that path at time $s\in [0,1]$. This defines a contraction of a topological space of $\Delta$. On each closed edge times $[0,1]$, the construction takes place in a finite tree and is continuous. Since the interval is a locally finite CW complex, the product with $\Delta$ has the corresponding weak topology of a CW complex, so these restrictions establish continuity globally. ConsequentlyThis argument includes infinite graphs and does not assume local finiteness of $\Gamma$.

If $p:\tilde{\Gamma }\to \Gamma$ is a covering map, take $p^{-1}({\Gamma }^0)$ as the vertices upstairs. Each component of the inverse image of an open edge is an open interval mapping homeomorphically to that edge, because an interval is simply connected. Its parametrization lifts along the closed edge to attach its endpoints to lifted vertices, by path lifting theorem. Small star neighborhoods at vertices are lifted homeomorphically by the covering map, and give exactly the neighborhoods of the resulting topological graph. Thus the cell structure has the topology of the original covering space. The total space may be disconnected, but every component is a topological graph.

The Nielsen–Schreier formula isFor a proof, realize $F_n$ as the fundamental group of the wedge sum of $n$ circles. Construct its connected covering graph with vertices the right cosets $Hg$, and an oriented edge labeled $x_i$ from $Hg$ to $Hg{x}_i$ for each free generator $x_i$. There is exactly one incoming and one outgoing edge of each label at every vertex, which establishes the local covering map property. Reading a word from $H$ ends at its coset, so the closed paths at $H$ give exactly the words in $H$. The induced map of fundamental groups is injective by the homotopy lifting property of a covering map, and its image is $H$.

For index $d$, this covering graph has $d$ vertices and $dn$ edges. A spanning tree in it has $d-1$ edges. The permitted rank formula for a finite connected graph now givesIn particular this proves both freeness and the index formula.

If $n\ge 2$ and $d>1$, then $1+d(n-1)>n$, so a proper finite-index subgroup cannot be isomorphic to $F_n$. For $n=1$, $F_1\cong \mathbb{Z}$, and $d\mathbb{Z}$ is a proper index-$d$ subgroup isomorphic to $\mathbb{Z}$ for every $d\ge 2$. Hence

A subgroup $H$ of a group $G$ is a normal subgroup when $gH{g}^{-1}=H$ for every $g\in G$, equivalently $gH=Hg$. The quotient group $G/H$ has the left cosets as elements, with $(gH)(kH)=gkH$, identity $H$ and inverse $(gH{)}^{-1}=g^{-1}H$. Normality makes this multiplication independent of representatives.

The first isomorphism theorem for groups says that for a group homomorphism $\phi :G\to K$, its kernel of a group homomorphism is normal andThe image is taken with the induced group operation; surjectivity onto all of $K$ is not required.

For the given upper triangular matrices, take diagonal entries:The target is a direct product of groups, with multiplication of nonzero real numbers in each coordinate. Indeed the product of two such matrices has diagonal $(a{a}^{\prime },d{d}^{\prime })$, proving the group homomorphism property. Any pair of nonzero diagonal entries is attained by a diagonal matrix, so $\phi$ is surjective. Its kernel of a group homomorphism consists precisely of the matrices with $a=d=1$, namely $H$. Hencewith coordinatewise multiplication, not addition on ${\mathbb{R}}^2$.

Lagrange's theorem for finite groups states that for a subgroup $H$ of a finite group $G$, $|G|=[G:H]|H|$. For $x\in G$, two powers among $1,x,\dots ,x^{|G|}$ coincide, giving $x^m=1$ for some positive $m$. The least such exponent $d$ is the order of a group element, and the cyclic subgroup generated by $x$ consists of the $d$ distinct powers $1,x,\dots ,x^{d-1}$. Apply Lagrange's theorem for finite groups to obtain $d\mid |G|$.

Cauchy's theorem for finite groups states that if a prime $p$ divides the order of a finite group, the group contains an element of order $p$.

The classification of a group of order eight isHere $D_8$ denotes the dihedral group of order eight, not a group of order sixteen. To prove exhaustiveness, every element order is $1,2,4$ or $8$. An element of order eight generates the whole group, giving $C_8$.

If no element has order four or eight, every nonidentity element is an involution. Since $(ab{)}^{-1}=ab$ while $a^{-1}=a$ and $b^{-1}=b$, we have $ab=ba$. Choose an involution $a$, another $b$ outside $⟨a⟩$, and then $c$ outside the four-element subgroup $⟨a,b⟩$. The factors commute and each added factor has trivial intersection with the preceding subgroup. The internal direct product theorem gives $G\cong C_2^3$, an elementary abelian group.

Otherwise choose $a$ of order four and set $A=⟨a⟩$. It has index two, so is normal. Choose $b\notin A$. The two cosets show that $a,b$ generate $G$ and that $b^2\in A$. There is no element of order eight, so $b^2$ is either $1$ or $a^2$.

If $G$ is abelian and $b^2=1$, the internal direct product theorem yields $G=A\times ⟨b⟩\cong C_4\times C_2$. If instead $b^2=a^2$, let $c=a^{-1}b$; commutativity gives $c^2=1$ and $c\notin A$, producing the same direct product.

If $G$ is nonabelian, conjugation by $b$ is a nonidentity group automorphism of $A$: otherwise $a,b$ would commute and hence so would all of $G$. Thus $ba{b}^{-1}=a^{-1}$. With $b^2=1$ these are the relations of $D_8$; with $b^2=a^2$ they are the relations of the quaternion group $Q_8$. In either presentation every word reduces to $a^i{b}^j$, $0\le i<4$, $0\le j<2$. The standard eight-element model maps onto $G$, and equal orders make that group homomorphism an isomorphism.

Finally group isomorphisms preserve element orders. The following numbers of elements distinguish all five possibilities:

Thus the list is both exhaustive and pairwise non-isomorphic.

For a group action, the orbit of a group action of $x$ is $Gx=\{gx:g\in G\}$, and its stabilizer subgroup is $G_x=\{g:gx=x\}$. The orbit-stabilizer theorem gives $|Gx||G_x|=|G|$: the map $g{G}_x\mapsto gx$ is a well-defined bijection from stabilizer cosets to the orbit.

Within one orbit, the stabilizer subgroups are conjugate, since $G_{hx}=h{G}_x{h}^{-1}$. Their sizes are therefore equal. Summing stabilizer sizes over a single orbit gives $|Gx||G_x|=|G|$, and summing over all $n$ orbits yieldsNow count the pairs $(g,x)$ fixed by the action in two ways. Holding $x$ fixed gives $|G_x|$ choices of $g$, whereas holding $g$ fixed gives $|\mathrm{Fix}(g)|$ choices of $x$. ThusCombining the two identities proves Burnside lemma:The finiteness hypotheses justify these cardinality sums. If $X$ is empty, every sum and the orbit count are zero, so the formula still applies.

First require $x\ne 0$. A discrete logarithm to a generator of a group of ${\mathbb{Z}}_p^{\ast }$ exists only for nonzero $x$; the printed membership $x\in {\mathbb{Z}}_p$ inadvertently also permits zero, for which $x^{-b}$ is undefined. Zero can be rejected before any quantum circuit.

Put $M=p-1$ and write $x=g^y$. Since $g$ is a generator of a group of order $M$, the map $k\mapsto g^k$ is a bijection from ${\mathbb{Z}}_M$ to the multiplicative group of a finite field. Hence every nonzero $c$ has a unique $k\in {\mathbb{Z}}_M$ with $c=g^k$. Equality of powers of $g$ is equality of their exponents modulo $M$, givingThe fiber over $c$ is an affine coset of the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$, and contains exactly $M$ pairs. This identifies the hidden subgroup problem underlying discrete-logarithm Fourier sampling; knowing $k$ numerically is not needed to construct the coset state.

Lagrange's theorem for finite groups states that if $H\le G$ and $G$ is finite, thenso $|H|$ divides $|G|$. Indeed, the left cosets of $H$ partition $G$, and multiplication by a coset representative is a bijection from $H$ to each coset.

Applying the theorem to the cyclic subgroup $⟨g⟩$ gives

In $C_3\times C_9$, an element has order dividing three exactly when its first coordinate is arbitrary and its second belongs to the unique subgroup of order three. There are $3\cdot 3=9$ such elements, and after removing the identity the answer is $\boxed{8}$.

The hidden subgroup problem is to recover a subgroup $K\le G$, usually by giving generators of a group, from an oracle machine providing $f:G\to Y$ with the promiseThus $f$ is constant on each left coset and distinguishes different left cosets. The input includes an effective representation of elements of the group and access to the group operations; the desired efficiency is measured against the number of bits describing an element, rather than necessarily against $|G|$.

Let $G$ act by left multiplication on the set $G/H$ of $n$ left cosets. This gives a group action homomorphismIts kernelis a normal subgroup of $G$, and the first isomorphism theorem gives $G/K\cong \mathrm{im}\phi$. By Lagrange's theorem, $|G/K|$ divides $n!$. The image acts transitively on the $n$ cosets, so the orbit-stabilizer theorem shows that $n$ divides $|G/K|$; in particular,

Now suppose $G$ is nonabelian and simple. Since $H$ is proper, the coset action is nontrivial, so $K\ne G$. Simplicity gives $K=\{e\}$, and $\phi$ embeds $G$ into $S_n$. Composing with the sign homomorphism givesIts kernel is normal. A nontrivial map would embed the simple group $G$ into the abelian group of order two, which is impossible because $G$ is nonabelian. The sign is therefore always $+1$, so

For subgroups $H,P\le G$, define $x\sim y$ when $y\in HxP$. The identity elements show reflexivity, inverses show symmetry, and multiplication shows transitivity. Thus the double cosets $HxP$ partition $G$.

Let $H$ act by left multiplication on the set of left cosets $G/P$. The orbit of $xP$ consists of the cosets contained in $HxP$, so its size is $|HxP|/|P|$. Its stabilizer isThe orbit-stabilizer theorem therefore gives

Suppose $P$ is a Sylow subgroup of $G$, with $|P|=p^a$, and write the largest power of $p$ dividing $|H|$ as $p^b$. If every $H\cap xP{x}^{-1}$ had order at most $p^{b-1}$, the displayed formula would make every double-coset size divisible by $p^{a+1}$. Their sum $|G|$ would then also be divisible by $p^{a+1}$, contradicting the choice of $P$. Hence some $H\cap xP{x}^{-1}$ has order $p^b$ and is a Sylow $p$-subgroup of $H$. This is the Sylow subgroup of a subgroup from double cosets argument.

To count the general linear group over a finite field $G{L}_n({\mathbb{F}}_p)$, choose its columns successively. There are $p^n-1$ choices for the first, $p^n-p$ for the second, and $p^n-p^k$ for column $k+1$. ConsequentlyNone of the factors $p^j-1$ is divisible by $p$, so the upper unitriangular group is a Sylow $p$-subgroup: it has one arbitrary field entry in each of the $n(n-1)/2$ positions above the diagonal and hence order $p^{n(n-1)/2}$. The permutation matrices form a subgroup isomorphic to the symmetric group $S_n$.

By Cayley theorem, every finite group $G$ embeds in $S_{|G|}$, and permutation matrices embed this symmetric group in $G{L}_{|G|}({\mathbb{F}}_p)$. The latter has the explicit Sylow $p$-subgroup just described, so the result proved in the first part, applied to the embedded copy of $G$, proves that every finite group has a Sylow $p$-subgroup.

The counting part of the Sylow theorems says that if $p^a$ is the largest power of $p$ dividing $|G|$, then the number $n_p$ of Sylow $p$-subgroups satisfies

Finally, let $|G|=pq$ with prime numbers $p>q$. The Sylow counts giveso $n_p=1$ and the Sylow $p$-subgroup is a normal subgroup. Also $n_q\mid p$ and $n_q\equiv 1(\mathrm{mod}q)$. If $n_q=1$, both Sylow subgroups are normal; their elements commute, so $G$ is their direct product and is abelian. In the nonabelian case one must therefore have $n_q=p$, whenceor equivalently $q\mid p-1$, as recorded by nonabelian group of order pq.

In the hidden subgroup problem, an oracle gives a function $f:G\to X$ that is constant on every left coset of an unknown subgroup $H\le G$ and takes distinct values on distinct cosets. The task is to determine $H$.