Subgroups and Lagrange's Theorem

2022. DeepMind publishes AlphaFold2 - a model that solved the protein folding problem biologists had worked on for 50 years. The press covered the neural network. Quietly backstage stood different mathematics: the group SE(3) and its subgroups. The model cannot predict a physically impossible molecular conformation - not because it learned to avoid them, but because the architecture inhabits a space where impossible conformations do not exist. That is the power of subgroups.

• SE(3)-equivariant networks in molecular ML - protein symmetries as subgroups of rotation groups
• Diffie-Hellman and ECDSA: security rests on subgroup structure in $\mathbb{Z}_p^*$ and elliptic curve groups
• Convolutional neural networks: weight sharing is factoring by the translation subgroup $\mathbb{Z}^2$
• Lagrange's theorem explains why hash table sizes of prime $p$ have better distribution properties

Предварительные знания

• Groups: First Steps into Abstract Algebra

Subgroup: A Group Within a Group

AlphaFold2 predicts protein structure with atomic accuracy - error smaller than the width of an atom. Behind the neural network sits another layer of mathematics: the special Euclidean group SE(3) of rotations and translations in 3D space. The physically allowed configurations of amino acids are **subgroups** of SE(3). The model cannot predict an impossible molecular shape - not because it learned to avoid them, but because the architecture lives in a space where impossible configurations do not exist.

A subset $H \subseteq G$ is called a **subgroup** of $G$ (written $H \leq G$) if $H$ is itself a group under the same operation. Three conditions suffice: $H$ is non-empty, closed under the operation, and contains the inverse of each element.

**One-step subgroup criterion.** $H \leq G$ if and only if $H$ is non-empty and for all $a, b \in H$ one has $a \cdot b^{-1} \in H$. One condition replaces three axioms: the identity follows by setting $a = b$, the inverse by setting $a = e$.

Every group $G$ contains two **trivial** subgroups: $\{e\}$ and $G$ itself. All others are **proper** subgroups. One striking consequence: if $|G| = p$ is prime, there are no proper subgroups at all. This is precisely what cryptography exploits.

Cosets: Partitioning Without Remainder

Convolutional networks do not notice a shift in the image. A cat on the left is the same cat on the right. This is not a clever heuristic - it is **equivariance** to the translation group $\mathbb{Z}^2$. Weight sharing in a Conv layer is mathematically equivalent to partitioning the feature space into cosets of the translation subgroup. The partition is the mechanism. Understanding cosets means understanding why CNN works at all.

The **left coset** of element $a$ with respect to subgroup $H$ is the set $aH = \{a \cdot h \mid h \in H\}$. The **right coset** is $Ha = \{h \cdot a \mid h \in H\}$. In abelian groups they coincide. The fundamental property: any two cosets are either identical or completely disjoint.

**Left coset does not equal right coset** in general. If $aH = Ha$ for all $a \in G$, the subgroup is called **normal** ($H \trianglelefteq G$). Normal subgroups are precisely those over which quotient groups can be formed. Example of a non-normal subgroup: the rotation subgroup $\{e, r\}$ inside the symmetry group $S_3$ of a triangle.

Lagrange's Theorem: Order Divides Order

Why does Diffie-Hellman use a prime $p$? Lagrange's theorem is the answer. In the group $\mathbb{Z}_p^*$ of order $p-1$, the order of any element divides $p-1$. Choosing a generator $g$ of prime order $q$ creates a subgroup of exactly $q$ elements. An attacker must search through all $q$ possibilities - there is no shortcut, because there are no non-trivial subgroups of an order that does not divide $q$.

**Lagrange's theorem.** If $G$ is a finite group and $H \leq G$, then $|H|$ divides $|G|$. More precisely: $|G| = |H| \cdot [G:H]$, where $[G:H]$ is the number of cosets, called the **index** of $H$ in $G$. The proof is elegant: all cosets have the same size $|H|$ and are pairwise disjoint - they literally tile $G$.

**The converse is false.** If $d$ divides $|G|$, a subgroup of order $d$ need not exist. Counterexample: $A_4$ (even permutations of four elements) has order 12 but has no subgroup of order 6, despite $6 \mid 12$. Lagrange's theorem is a constraint, not a guarantee.

In Geometric Deep Learning (Cohen et al., 2016), subgroups define admissible symmetries. E(3)-equivariant networks respect subgroups of the 3D Euclidean group: rotations SO(3), reflections, translations. AlphaFold2 uses an SE(3)-equivariant Invariant Point Attention module. Lagrange's theorem ensures the discrete symmetries of a protein form a subgroup with predictable structure - no physically impossible shape can emerge from a geometrically consistent model.

Key Ideas

• $H \leq G$ - subgroup: non-empty subset closed under the operation and inverses. Criterion: $a, b \in H \Rightarrow ab^{-1} \in H$
• Trivial subgroups: $\{e\}$ and $G$. A group of prime order has no others
• Left coset $aH = \{ah \mid h \in H\}$ - a translate of the subgroup by element $a$
• Cosets partition $G$ into disjoint parts, each of size $|H|$
• **Lagrange's theorem**: $|H|$ divides $|G|$; index $[G:H] = |G|/|H|$
• Consequences: element order divides $|G|$; prime-order groups are cyclic; Fermat's Little Theorem

What's Next

Subgroups are the foundation. Homomorphisms, quotient groups, and ultimately Galois theory - which explains why the quintic equation has no closed-form solution - all build on what was introduced here.

• Homomorphisms and Isomorphisms — The kernel of a homomorphism is a normal subgroup; the image is a subgroup
• Quotient Groups — The quotient group G/H is constructed from the cosets of H
• Sylow's Theorems — Partial converse of Lagrange's theorem for subgroups of prime-power order
• Algebra and Cryptography — Subgroup structure directly determines the security of cryptographic protocols

Вопросы для размышления

• Why can cosets never intersect? Try proving this by contradiction: if $a \in xH \cap yH$, what can be said about $xH$ and $yH$?
• If $|G| = 12$, what orders can elements of $G$ have? Which orders are impossible - and why?
• In SE(3)-equivariant networks, predictions do not change when a molecule is rotated. What plays the role of the subgroup in that construction?

Связанные уроки

• aa-03-homomorphisms — The kernel of a homomorphism is a normal subgroup - builds directly on this lesson
• aa-06-quotient — Quotient group G/H is constructed from cosets of H
• aa-07-sylow — Sylow's theorems are a deep generalization of Lagrange's theorem
• aa-21-algebra-crypto — Diffie-Hellman and ECDSA directly exploit subgroup structure
• aa-30-algebra-ml — SE(3)-equivariance in AlphaFold2 - subgroups of 3D symmetries
• nt-03