Chapter 02 — Generators and Relations
Proofs omitted. Hover over highlighted terms to see their Lean types.
2.1 — Introduction
Definition 2.1.1
Lean contributors (project-level attribution): Zichen Wang.
Definition 2-1-1: a presentation of G with defining generators X and defining relators R is a chosen multiplicative equivalence from the canonical presented group PresentedGroup R to G. The file uses the canonical type expression PresentedGroup R ≃* G directly rather than introducing a duplicate alias.
universe u v
-- Declarations for this item will be appended below by the statement pipeline.
-- Layer triage:
-- `source-facing`: a group `G`, a type `X` of defining generators, a set `R` of relators in the
-- free group on `X`, and the assertion that `(X; R)` presents `G` via a chosen equivalence
-- `PresentedGroup R ≃* G`.
-- `core/canonical`: `PresentedGroup R`, `PresentedGroup.of`, `PresentedGroup.closure_range_of`,
-- `PresentedGroup.mk_eq_one_iff`, and `Subgroup.normalClosure`.
-- `bridge/view`: the chosen presentation equivalence transports the canonical generators of
-- `PresentedGroup R` to the defining generators in `G`, and `FreeGroup.lift` evaluates words in
-- those generators.
-- Domain sampling:
-- 1. `PresentedGroup R` is mathlib's owner abstraction for a group given by generators `X` and
-- relators `R`.
-- 2. `PresentedGroup.of` is the canonical image of a defining generator in the presented group.
-- 3. `PresentedGroup.closure_range_of` is the canonical statement that these images generate the
-- presented group.
-- 4. `PresentedGroup.mk_eq_one_iff` identifies the consequences of the relators with the normal
-- closure of `R`.
-- Primitive vs. derived:
-- the primitive source data are the generators `X`, the relator set `R`, and the chosen
-- identification `PresentedGroup R ≃* G`; the defining-generator subset of `G` and the
-- relator/consequence equations are derived from that canonical owner-side datum, so no parallel
-- alias for the equivalence is introduced.
variable {G : Type u} [Group G] {X : Type v} {R : Set (FreeGroup X)}
#check (PresentedGroup R ≃* G)Definition 2.1.2
Lean contributors (project-level attribution): Zichen Wang.
Definition 2-1-2 (1): a presentation is finitely generated exactly when its generator type is finite.
universe v
-- Layer triage:
-- `source-facing`: a presentation datum consisting of a generator type `X` and a relator set
-- `R : Set (FreeGroup X)`, together with the textbook finiteness terminology for that datum.
-- `core/canonical`: `Finite X` for finiteness of the generator type and `Set.Finite R` for
-- finiteness of the relator set.
-- `bridge/view`: the textbook phrase "finite presentation" is exactly the conjunction of these
-- two owner predicates.
-- Domain sampling:
-- 1. `PresentedGroup R` is mathlib's owner abstraction for generators-and-relations data from
-- Definition `2-1-1`, but the present item adds only finiteness conditions on the source data.
-- 2. `Finite X` is the canonical finiteness predicate for a type of generators.
-- 3. `Set.Finite R` is the canonical finiteness predicate for a relator set.
-- Primitive vs. derived:
-- the primitive source data are only `X` and `R`; the three textbook finiteness phrases below are
-- direct uses of the owner predicates above, so the file keeps the raw canonical predicates
-- `Finite X` and `Set.Finite R` rather than introducing parallel names such as
-- `GroupPresentation.IsFinitelyGenerated` or `GroupPresentation.IsFinitelyRelated`.
namespace GroupPresentation
variable {X : Type v} {R : Set (FreeGroup X)}
#check (Finite X)Definition 2.1.3
Lean contributors (project-level attribution): Zichen Wang.
Definition 2-1-3: a presentation with generators indexed by X and relator set R : Set (FreeGroup X) is recursive when the set of finite signed words whose image under FreeGroup.mk lies in R is recursively enumerable.
universe u
namespace GroupPresentation
variable {X : Type u} [Primcodable X]
-- Layer triage:
-- `source-facing`: a presentation datum consisting of a generator type `X` and relator set
-- `R : Set (FreeGroup X)`, together with the textbook condition that the relators are recursively
-- enumerable from finite signed words.
-- `core/canonical`: the chapter owner namespace `GroupPresentation` for presentation-level
-- properties, `FreeGroup.mk` as the canonical map from signed words to the free group, and
-- `REPred` as mathlib's recursively enumerable predicate.
-- `bridge/view`: the source phrase "the presentation `(X; R)` is recursive" is expressed by the
-- predicate on signed words sending `L` to `FreeGroup.mk L ∈ R`.
-- Domain sampling:
-- 1. `Finite X` and `Set.Finite R` from Definition `2-1-2` are the canonical finiteness
-- predicates on the underlying generator type and relator set.
-- 2. `FreeGroup.mk` is the canonical word-to-element map on the free group.
-- 3. `REPred` is mathlib's owner predicate for recursively enumerable subsets of a `Primcodable`
-- type.
-- Primitive vs. derived:
-- the primitive source data are only `X` and `R`; the recursively enumerable word-membership
-- predicate is the derived owner-side API, so no separate wrapper around the presentation data is
-- introduced.
def IsRecursive (R : Set (FreeGroup X)) : Prop :=
REPred (fun L : List (X × Bool) ↦ FreeGroup.mk L ∈ R)Definition 2.1.4
Lean contributors (project-level attribution): Zichen Wang.
Definition 2-1-4: a presentation has solvable word problem when the set of finite signed words whose image in the canonical presented group is trivial is computable.
universe u
namespace GroupPresentation
variable {X : Type u} [Primcodable X]
-- Layer triage:
-- `source-facing`: a presentation datum `(X; R)` together with the textbook assertions that
-- triviality and conjugacy of words on the generators are algorithmically decidable from finite
-- signed-word input.
-- `core/canonical`: the chapter owner namespace `GroupPresentation`, the word model
-- `List (X × Bool)` with canonical evaluation `FreeGroup.mk`, the canonical normal form map
-- `FreeGroup.toWord`, and the canonical owner quotient `PresentedGroup R` with its map
-- `PresentedGroup.mk`.
-- `bridge/view`: quotient triviality is the source-facing word problem, normal-closure membership
-- is the equivalent owner-side reformulation given by `PresentedGroup.mk_eq_one_iff`, and
-- quotient-level decidability of conjugacy is only a derived view obtained by choosing word
-- representatives through `PresentedGroup.mk_surjective`.
-- Domain sampling:
-- 1. Definition `2-1-2` keeps the finiteness conditions for presentations at the canonical owner
-- predicates `Finite X` and `Set.Finite R`, while Definition `2-1-3` adds the presentation-
-- level predicate `IsRecursive` in the `GroupPresentation` namespace.
-- 2. `FreeGroup.mk` is the canonical map from finite signed words to `FreeGroup X`.
-- 3. `PresentedGroup R` with `PresentedGroup.mk` is the owner abstraction for the quotient by the
-- normal closure of `R`.
-- 4. `PresentedGroup.mk_eq_one_iff` is the canonical bridge from quotient triviality to
-- membership in `Subgroup.normalClosure R`.
-- 5. `ComputablePred` is mathlib's canonical computability predicate on coded finite input.
-- 6. `FreeGroup.toWord` is the canonical reduced-word representative of a free-group element.
-- Primitive vs. derived:
-- the primitive data are the generator type `X` and relator set `R`; the owner-side computable
-- predicates are quotient triviality on signed words and quotient conjugacy on pairs of signed
-- words, while normal-closure membership and quotient-level decidability are derived bridges.
def HasSolvableWordProblem (R : Set (FreeGroup X)) : Prop :=
ComputablePred fun L : List (X × Bool) ↦ PresentedGroup.mk R (FreeGroup.mk L) = 12.2 — Finite Presentations
Proposition 2.2.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-2-1: two finite presentations define isomorphic groups if and only if they are related by a finite sequence of Tietze transformations.
universe u
namespace GroupPresentation
-- Layer triage:
-- `source-facing`: a finite presentation consists of a finite generator type together with a
-- finite relator set, and Tietze transformations are the elementary operations on such data.
-- `core/canonical`: `PresentedGroup` is the owner object attached to a relator set,
-- `Group.IsFinitelyPresented` is mathlib's owner predicate for the abstract group-level notion,
-- and `Relation.EqvGen` is the canonical owner for equivalence closure of elementary steps.
-- `bridge/view`: the proposition identifies equality up to a finite Tietze sequence on the
-- source-facing data with isomorphism of the associated canonical presented groups.
-- Domain sampling:
-- 1. `PresentedGroup rels` is mathlib's canonical group attached to generators and relations.
-- 2. `PresentedGroup.toGroup` and `PresentedGroup.equivPresentedGroup` are the owner transport
-- maps for changing generators and relators while preserving the presented group.
-- 3. `Group.IsFinitelyPresented` is the canonical abstract owner predicate for the existence of a
-- finite presentation.
-- 4. `Relation.EqvGen` is mathlib's canonical equivalence closure for a primitive one-step
-- relation, so a separate inductive closure API is unnecessary here.
-- 5. Definition `2-1-2` in this chapter already identifies "finite presentation" with the
-- primitive owner predicates `Finite X` and `Set.Finite R`, so no parallel wrapper structure
-- is needed here.
-- Primitive vs. derived:
-- the primitive source data are the generator type and relator set together with the owner
-- finiteness predicates `Finite X` and `Set.Finite R`, together with the one-step
-- source-facing Tietze expansion relation; the presented group, the abstract
-- finite-presentation property, and Tietze equivalence are derived owner-side API.
variable {X Y Z : Type u}
variable {R : Set (FreeGroup X)} {S : Set (FreeGroup Y)} {T : Set (FreeGroup Z)}
-- Proof sketch: choose an equivalence between the finite generator type `X` and some `Fin n`,
-- transport the relator set `R` across that equivalence using
-- `PresentedGroup.equivPresentedGroup`, and use the finiteness of the transported relator set to
-- instantiate `Group.IsFinitelyPresented`.
theorem presentedGroup_mulEquiv_iff_tietzeEquivalent [Finite X] [Finite Y]
(hR : R.Finite) (hS : S.Finite) :
Nonempty (PresentedGroup R ≃* PresentedGroup S) ↔ TietzeEquivalent R SProposition 2.2.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-2-2, core form: along an isomorphism between two presented groups with finite generating types, solvability of the word problem and of the conjugacy problem are invariant. By Definition 2-1-2, this applies in particular to finite presentations.
universe u v
namespace GroupPresentation
variable {X₁ : Type u} {X₂ : Type v}
variable {R₁ : Set (FreeGroup X₁)} {R₂ : Set (FreeGroup X₂)}
local notation "G₁" => PresentedGroup R₁
local notation "G₂" => PresentedGroup R₂
-- Layer triage:
-- `source-facing`: two finite presentations of the same group, together with the claim that
-- solvability of the word problem or of the conjugacy problem does not depend on which finite
-- presentation is chosen.
-- `core/canonical`: the owner objects `PresentedGroup R₁` and `PresentedGroup R₂`, the chapter
-- owner predicates `HasSolvableWordProblem` and `HasSolvableConjugacyProblem`, and the owner
-- conjugacy relation `IsConj` on a group.
-- `bridge/view`: "presentations of the same group" is expressed canonically by a multiplicative
-- equivalence `G₁ ≃* G₂`; the internal transport lemmas below isolate the owner-side transport,
-- while the public theorem surface keeps only the invariant presentation-level statements.
-- Domain sampling:
-- 1. `PresentedGroup R` is the mathlib owner abstraction for a group given by generators and
-- relators.
-- 2. `HasSolvableWordProblem R` from Definition `2-1-4` is the chapter owner predicate for the
-- word problem of a presentation.
-- 3. `HasSolvableConjugacyProblem R` is the matching chapter owner predicate for solvability of
-- the conjugacy problem.
-- 4. `IsConj` is the owner relation for conjugacy in a group.
-- 5. `MulEquiv` is the canonical bridge for transporting group-theoretic decidability data
-- between isomorphic presented groups.
-- Primitive vs. derived:
-- the primitive data for the owner-level transport are the two relator sets and an isomorphism
-- between their presented groups; solvable word and conjugacy problems are the chapter's
-- presentation-level computability predicates on coded words, while finiteness of the generator
-- types is the only extra effective hypothesis used by the transport. The source phrase "finite
-- presentation" from Definition `2-1-2` adds relator finiteness as a separate source-facing
-- condition, but that condition is inert for the invariance statement proved here.
variable [Primcodable X₁] [Primcodable X₂] [Finite X₁] [Finite X₂]
-- Proof sketch: the one-way word-problem bridge only needs finiteness of the target generator
-- type, so applying it to `e` and `e.symm` gives a symmetric statement once both generator types
-- are finite. The conjugacy bridge has the same effective transport shape, so it becomes
-- symmetric under the same pair of finiteness hypotheses.
theorem solvable_word_and_conjugacy_problems_iff_mulEquiv
(e : G₁ ≃* G₂) :
(HasSolvableWordProblem R₁ ↔ HasSolvableWordProblem R₂) ∧
(HasSolvableConjugacyProblem R₁ ↔ HasSolvableConjugacyProblem R₂)Proposition 2.2.3
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-2-3: if generators : Fin n → G generates G and M is a finite m-by-n relation matrix presenting Abelianization G relative to the images of those generators, then G admits a presentation on the same generators Fin n with relators r₀, r₁, ... such that the first m relators have the prescribed images in the abelianization of the free group, while every later relator is trivial modulo the commutator subgroup.
open scoped BigOperators
open GroupPresentation
universe u
-- Layer triage:
-- `source-facing`: a group `G` equipped with a chosen generating `n`-tuple
-- `generators : Fin n → G`, its abelianization `Abelianization G`, a finite integer matrix
-- `M : Matrix (Fin m) (Fin n) ℤ` presenting that abelianization relative to those generators, and
-- a group presentation on the same `n` generators whose relators lift the rows of `M` modulo the
-- commutator subgroup of the free group.
-- `core/canonical`: `PresentedGroup`, `Abelianization`, `FreeAbelianGroup`, `Matrix`, and the
-- standard free `ℤ`-module `FreeAbelianGroup (Fin n)`, together with the chapter owner map
-- `GroupPresentation.generatorImage`.
-- `bridge/view`: the abelian relation matrix determines the canonical quotient module
-- `FreeAbelianGroup (Fin n) ⧸ relationMatrixSubmodule M`; the chosen generators induce the
-- canonical classes `Additive.ofMul (Abelianization.of (generators j))`, and the relator
-- congruences are expressed by equalities in the additive owner
-- `FreeAbelianGroup (Fin n) = Additive (Abelianization (FreeGroup (Fin n)))`.
-- Domain sampling:
-- 1. `PresentedGroup rels` is mathlib's owner abstraction for a presentation on generators
-- indexed by a type.
-- 2. `Abelianization.of` is the canonical map recording equality modulo the commutator subgroup.
-- 3. `GroupPresentation.generatorImage P` is the chapter owner map from defining generators in a
-- presentation to their images in the ambient group.
-- 4. `FreeAbelianGroup.of` and `FreeAbelianGroup.lift` are the canonical owner maps for linear
-- combinations of generators in the free abelian group.
-- 5. `FreeAbelianGroup (Fin n) ⧸ relationMatrixSubmodule M` is the canonical quotient module
-- presented by the rows of `M`.
-- 6. `Matrix (Fin m) (Fin n) ℤ` is the owner abstraction for a finite integer relation matrix.
-- Primitive vs. derived:
-- the primitive extra data are the chosen generating `n`-tuple `generators : Fin n → G`, its
-- closure hypothesis, and the matrix rows as elements of the free abelian group on `n`
-- generators together with the induced quotient by their span; the presentation equivalence, its
-- compatibility with `generators`, and the additive abelianized relator formulas are the derived
-- existential conclusion.
theorem exists_presentation_with_abelianized_relation_matrix {m n : ℕ}
(G : Type u) [Group G] (generators : Fin n → G)
(hgenerators : Subgroup.closure (Set.range generators) = ⊤) (M : Matrix (Fin m) (Fin n) ℤ)
(hM : ∃ e : (FreeAbelianGroup (Fin n) ⧸ relationMatrixSubmodule M) ≃ₗ[ℤ]
Additive (Abelianization G),
∀ j : Fin n,
e (Submodule.Quotient.mk (FreeAbelianGroup.of j)) =
Additive.ofMul (Abelianization.of (generators j))) :
∃ relators : ℕ → FreeGroup (Fin n),
∃ P : PresentedGroup (Set.range relators) ≃* G,
generatorImage P = generators ∧
(∀ i : Fin m, Additive.ofMul (Abelianization.of (relators i)) = relationMatrixRow M i) ∧
∀ k : ℕ, m ≤ k → Additive.ofMul (Abelianization.of (relators k)) = 0Proposition 2.2.4
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-2-4: for a finite presentation G = (X; R), the deficiency question asks whether there is a subset X₀ ⊆ X such that |R| + |X₀| = |X|, and whose image in G is a basis of the free subgroup generated by that image, with the chosen generators mapping bijectionally onto that image subset.
universe u v
open scoped Classical
namespace GroupPresentation
variable {G : Type u} [Group G] {X : Type v} {R : Set (FreeGroup X)}
-- Layer triage:
-- `source-facing`: a finite presentation `G = (X; R)` together with the deficiency question from
-- Proposition `2-2-4`.
-- `core/canonical`: `PresentedGroup R ≃* G`, the chapter owner map
-- `GroupPresentation.generatorImage`, `Subgroup.closure`, and the subset-style basis predicate
-- `IsFreeGroupBasis`.
-- `bridge/view`: the selected subset `X₀ ⊆ X` is transported into `G` by `generatorImage P`;
-- the source generators must remain distinguishable, and that relation to the image subset is
-- recorded canonically by `Set.BijOn (generatorImage P) X₀ (generatorImage P '' X₀)` before the
-- image is regarded as a basis subset of the subgroup it generates.
-- Domain sampling:
-- 1. `PresentedGroup R ≃* G` is the canonical presentation datum from Definition `2-1-1`.
-- 2. `GroupPresentation.generatorImage` is the chapter owner map sending each generator to its
-- image in `G`.
-- 3. `Subgroup.closure` is the canonical subgroup generated by a subset of a group.
-- 4. `IsFreeGroupBasis` is the project's source-faithful basis predicate for a subset of a group.
-- Primitive vs. derived:
-- the primitive source data are the presentation equivalence `P`, the owner finiteness predicates
-- `Finite X` and `Set.Finite R`, and a subset `X₀ ⊆ X`; the numerical deficiency is then the
-- derived cardinal `Nat.card X₀`, while the bijection from `X₀` onto its image under
-- `generatorImage P`, its generated subgroup, and the corresponding subset of that subgroup are
-- all derived from `generatorImage P`.
def finitePresentationDeficiencyQuestion (P : PresentedGroup R ≃* G) : Prop :=
let gen : X → G := generatorImage P
Finite X ∧
Set.Finite R ∧
∃ X₀ : Set X,
let Y : Set G := gen '' X₀
Nat.card R + Nat.card X₀ = Nat.card X ∧
Set.BijOn gen X₀ Y ∧
IsFreeGroupBasis { g : Subgroup.closure Y | (g : G) ∈ Y }Theorem 2.2.5
Lean contributors (project-level attribution): Zichen Wang.
Theorem 2-2-5: in the Baumslag-Solitar group ⟨x, y | x⁻¹ y² x = y³⟩, the pair x and z = y⁴ generates the whole group, but there is no presentation on these two generators with only one defining relator.
universe u
-- Declarations for this item are recorded in this dedicated item file.
-- Primary domain: groups presented by generators and relators, specialized to two-generator
-- one-relator presentations.
-- Layer triage:
-- `source-facing`: the specific Baumslag-Solitar group `⟨x, y | x⁻¹ y² x = y³⟩`, the element
-- `z = y⁴`, and the assertion that `{x, z}` generates the group but is not the defining-generator
-- set of any two-generator one-relator presentation.
-- `core/canonical`: the chosen-presentation owner datum `PresentedGroup R ≃* G`, together with
-- the chapter API `GroupPresentation.generatorImage`,
-- `GroupPresentation.closure_range_generatorImage_eq_top`, and `Subgroup.closure`.
-- `bridge/view`: a subset `S ⊆ G` is compared with the canonical defining-generator set of a
-- two-generator one-relator presentation via a chosen equivalence.
-- Domain sampling:
-- 1. `PresentedGroup R ≃* G` from Definition `2-1-1` is the chapter owner abstraction for a
-- chosen presentation of `G`.
-- 2. `GroupPresentation.generatorImage` is the canonical map sending a defining generator to its
-- image in `G`.
-- 3. `Set.range (GroupPresentation.generatorImage P)` is the canonical defining-generator subset
-- attached to a chosen presentation.
-- 4. `GroupPresentation.closure_range_generatorImage_eq_top` is the owner generation theorem for
-- those images.
-- 5. `Subgroup.closure` is the owner construction for the subgroup generated by a set of
-- elements.
-- Primitive vs. derived:
-- the source-facing primitive data are the specific presentation of `BS(2, 3)` and the
-- generating set `{x, y⁴}` inside that group. The property of admitting a one-relator
-- presentation on that generating set is a bridge property derived from the owner-side defining
-- generator set, so no ordered-coordinate wrapper around presentations is introduced.
open BaumslagSolitar23
theorem baumslag_solitar23_yFourth_generating_pair_not_one_relator :
Subgroup.closure ({x, z} : Set BaumslagSolitar23.Group) = ⊤ ∧
¬ GroupPresentation.HasOneRelatorPresentationOn ({x, z} : Set BaumslagSolitar23.Group)Definition 2.2.6
Lean contributors (project-level attribution): Zichen Wang.
Definition 2-2-6: Conway's group F_n is the group presented by cyclically indexed generators x_i with relators x_i x_{i+1} = x_{i+2} for all i : ZMod n, which reproduces the textbook list x₁ x₂ = x₃, ..., x_{n-1} x_n = x₁, x_n x₁ = x₂.
open FreeGroup
-- Layer triage:
-- `source-facing`: Conway's family of groups `F_n`, given by `n` generators with the cyclic
-- relators `x_i x_{i+1} = x_{i+2}`.
-- `core/canonical`: `PresentedGroup` is mathlib's owner abstraction for groups given by
-- generators and relators, and `ZMod n` is the clean cyclic indexing type for the generator
-- family.
-- `bridge/view`: the textbook list
-- `x₁ x₂ = x₃, ..., x_{n-1} x_n = x₁, x_n x₁ = x₂`
-- is encoded as the uniform cyclic relator family indexed by `i : ZMod n`.
-- Domain sampling:
-- 1. `PresentedGroup rels` is the canonical quotient attached to a relator set in the free group.
-- 2. `PresentedGroup.of` supplies the canonical generators in the quotient.
-- 3. `PresentedGroup.one_of_mem` is the owner lemma saying a listed relator becomes trivial in the
-- presented group.
-- Primitive vs. derived:
-- the primitive data are the cyclic relators in the free group; the group `F_n` is the derived
-- canonical quotient by those relators, so no auxiliary wrapper structure is introduced.
namespace Conway
abbrev F (n : ℕ+) : Type :=
PresentedGroup (relators n)Definition 2.2.7
Lean contributors (project-level attribution): Zichen Wang.
Definition 2-2-7: F_{r,n} is the group presented by cyclically indexed generators x_i with relators x_i x_{i+1} ... x_{i+r-1} = x_{i+r} for all i modulo n.
open FreeGroup
-- Layer triage:
-- `source-facing`: the cyclically indexed presentation `F_{r,n}` with `n` generators and the
-- relators `x_i x_{i+1} ... x_{i+r-1} = x_{i+r}`.
-- `core/canonical`: `PresentedGroup` is mathlib's owner abstraction for a group given by
-- generators and relators, and `ZMod n` is the canonical cyclic index type.
-- `bridge/view`: the displayed cyclic list of relators is encoded uniformly by a relator family
-- indexed by `i : ZMod n`, using a list product for the left-hand side word.
-- Domain sampling:
-- 1. `PresentedGroup rels` is the canonical group attached to a relator set in `FreeGroup`.
-- 2. `PresentedGroup.mk` and `PresentedGroup.one_of_mem` express that listed relators become
-- trivial in the quotient.
-- 3. `Conway.F` from the previous item is the `r = 2` specialization of the same owner-side
-- presentation pattern, so the generalized file should bridge back to it explicitly.
-- Primitive vs. derived:
-- the primitive data are the cyclic relator words indexed by `r : ℕ`; positivity of `r` is not
-- part of the canonical construction, while the group `F_{r,n}` is the derived quotient by those
-- relators, so no auxiliary package around the presentation is introduced.
namespace Conway.Generalized
abbrev F (r : ℕ) (n : ℕ+) : Type :=
PresentedGroup (relators r n)2.3 — Fox Calculus, Relation Matrices, Connections with Cohomology
Theorem 2.3.1
Lean contributors (project-level attribution): Zichen Wang.
Theorem 2-3-1: for a surjection π : F →* G from a free group, Hopf's formula identifies the second integral homology of G with the quotient (ker π ∩ [F, F]) / [F, ker π] by exhibiting an isomorphism in ModuleCat ℤ.
open CategoryTheory groupHomology Rep
-- Primary domain: low-degree group homology attached to a free presentation.
-- Layer triage:
-- `source-facing`: a free presentation `π : F →* G` with `F` free, kernel `N = π.ker`, and the
-- Hopf-formula identification of the second integral homology with `(N ∩ [F, F]) / [F, N]`.
-- `core/canonical`: the bundled trivial representation `Rep.trivial ℤ G ℤ`, the low-degree owner
-- object `groupHomology.H2` together with its `≅`-valued comparison API such as
-- `groupHomology.H2Iso`, the commutator subgroup `_root_.commutator F`, and the subgroup
-- commutator `⁅(⊤ : Subgroup F), π.ker⁆`.
-- `bridge/view`: the source quotient is viewed as an object of `ModuleCat ℤ` via `Additive`; a
-- helper commutativity instance records that this quotient is abelian.
-- Domain sampling:
-- 1. `groupHomology.H2` and the comparison isomorphism pattern `groupHomology.H2Iso` are the
-- owner-side API for second group homology.
-- 2. `Rep.trivial ℤ G ℤ` is the canonical trivial integral `G`-representation.
-- 3. `_root_.commutator F` is the owner-side commutator subgroup `[F, F]`.
-- 4. `⁅(⊤ : Subgroup F), π.ker⁆` is the ambient-group realization of `[F, N]`.
-- 5. `Subgroup.subgroupOf` is the canonical way to form the denominator subgroup inside
-- `π.ker ⊓ commutator F`.
-- Primitive vs. derived:
-- the primitive source data are the free group `F`, the presentation map `π`, and the
-- surjectivity hypothesis. The quotient appearing in Hopf's formula is derived directly from
-- `π.ker` and the commutator constructions, so no wrapper around presentation data is introduced.
-- The later prose in the source item about free and amalgamated products is bibliographic
-- motivation rather than a separate atomic theorem statement, so only the explicit Hopf formula is
-- formalized here.
variable {F G : Type} [Group F] [IsFreeGroup F] [Group G]
theorem hopf_formula_second_homology_of_free_presentation
(π : F →* G) (hπ : Function.Surjective π) :
Nonempty (H2 (trivial ℤ G ℤ) ≅
ModuleCat.of ℤ (Additive (hopfFormulaQuotient π)))Proposition 2.3.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-3-2: for G = F / N, the canonical right ℤG-modules 𝓡² / 𝓡³, 𝓕𝓡 / 𝓕𝓡², 𝓡 / 𝓡², 𝓕 / 𝓕𝓡, ℤ[F / N], and ℤ occur as the first displayed terms of a projective resolution of the trivial right module ℤ over the quotient-ring owner quotientGroupRingRight N. The named boundary maps are the low-degree differentials of that resolution; in particular the degree-0 augmentation is the named counit quotientGroupRingCounit N. The four displayed quotient modules are free over ℤG.
open scoped MonoidAlgebra
universe u
variable {X : Type u} (N : Subgroup (FreeGroup X)) [N.Normal]
local notation "R" => FreeGroupRing X
local notation "F" => augmentationIdeal X
local notation "Rel" => relationIdeal N
local notation "S" => quotientGroupRingRight N
theorem relation_ideal_free_resolution :
Module.Free S (relationIdealSquareQuotient N) ∧
Module.Free S (augmentationRelationQuotient N) ∧
Module.Free S (relationIdealQuotient N) ∧
Module.Free S (augmentationQuotient N) ∧
∃ P : CategoryTheory.ProjectiveResolution (quotientGroupRingTrivialModule N),
∃ e4 : relationIdealSquareQuotient N ≃ₗ[S] P.complex.X 4,
∃ e3 : augmentationRelationQuotient N ≃ₗ[S] P.complex.X 3,
∃ e2 : relationIdealQuotient N ≃ₗ[S] P.complex.X 2,
∃ e1 : augmentationQuotient N ≃ₗ[S] P.complex.X 1,
∃ e0 : S ≃ₗ[S] P.complex.X 0,
e3.toLinearMap.comp (relationIdealSquareBoundary N) =
(P.complex.d 4 3).hom.comp e4.toLinearMap ∧
e2.toLinearMap.comp (augmentationRelationBoundary N) =
(P.complex.d 3 2).hom.comp e3.toLinearMap ∧
e1.toLinearMap.comp (relationBoundary N) =
(P.complex.d 2 1).hom.comp e2.toLinearMap ∧
e0.toLinearMap.comp (augmentationBoundary N) =
(P.complex.d 1 0).hom.comp e1.toLinearMap ∧
((P.π.f 0).hom.comp e0.toLinearMap = quotientGroupRingCounit N)2.4 — The Reidemeister-Schreier Method
Proposition 2.4.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-4-1: if H ≤ PresentedGroup R and T is a right transversal of the inverse-image subgroup H̃ ≤ FreeGroup X whose underlying set has initial segments, then H admits the Reidemeister-Schreier presentation with generators the owner Schreier set schreierGeneratorSet (T : Set (FreeGroup X)) T.2.toRightFun and relators τ(t r t⁻¹), and the chosen defining-generator map is the canonical map from each Schreier-generator symbol to its image in H.
universe u
namespace ReidemeisterSchreier
open FreeGroup
open GroupPresentation
-- Layer triage:
-- `source-facing`: a presentation `G = F / ⟪R⟫` with `F = FreeGroup X`, a subgroup `H ≤ G`, the
-- inverse-image subgroup `H̃ ≤ F`, a right transversal `T` for `H̃` satisfying the Schreier
-- initial-segment condition, the rewriting map `τ`, and the relators `τ(trt⁻¹)`.
-- `core/canonical`: `PresentedGroup R`, `PresentedGroup.mk R`, `Subgroup.comap`,
-- `Subgroup.RightTransversal`, the chapter-1 Schreier owner layer
-- `HasInitialSegments` / `schreierGenerator` / `schreierGeneratorSet`, and the chapter-2
-- presentation owner map `GroupPresentation.generatorImage`.
-- `bridge/view`: the textbook representative `\bar w` is the canonical right-coset selector
-- `T.2.toRightFun w`, while the textbook nontrivial Schreier generators are the chapter-1 owner
-- set `schreierGeneratorSet (T : Set (FreeGroup X)) T.2.toRightFun`.
-- Domain sampling:
-- 1. `PresentedGroup R` and `PresentedGroup.mk R` are the owner quotient-presentation API.
-- 2. `Subgroup.comap` is the canonical inverse-image construction for `H̃`.
-- 3. `HasInitialSegments` is the project owner property for the Schreier prefix condition.
-- 4. `schreierGeneratorSet` is the project owner set of nontrivial Schreier generators.
-- Primitive vs. derived:
-- the primitive source data are the relator set `R`, the subgroup `H`, and the chosen right
-- transversal `T`; the subgroup `H̃`, the textbook condition `1 ∈ T`, the Schreier generator
-- alphabet, the rewriting map `τ`, and the induced relator set are all derived from that owner
-- data.
variable {X : Type u} [DecidableEq X] {R : Set (FreeGroup X)}
variable {H : Subgroup (PresentedGroup R)}
variable {T : (preimageSubgroup H).RightTransversal}
theorem reidemeister_schreier_presentation_presentedGroup
(hT : HasInitialSegments (T : Set (FreeGroup X))) :
∃ P : PresentedGroup (schreierRelators T) ≃* H,
generatorImage P = schreierGeneratorImage TProposition 2.4.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-4-2: a finite-index subgroup of a finitely presented group is finitely presented.
universe u
variable {G : Type u} [Group G] (H : Subgroup G)
-- Primary domain: finite-index subgroups of finitely presented groups, expressed through the
-- canonical owner predicate `Group.IsFinitelyPresented`.
-- Layer triage:
-- `source-facing`: a finite-index subgroup `H` of a group `G`, together with the inheritance of
-- finite generation and finite presentability from `G` to `H`.
-- `core/canonical`: `H.FiniteIndex` and `Group.IsFinitelyPresented H`.
-- `bridge/view`: clause (1) is exactly mathlib's Schreier instance
-- `Subgroup.fg_of_index_ne_zero`; clause (2) passes through the chapter-owner
-- Reidemeister-Schreier presentation theorem from Proposition `2-4-1` and the owner theorem
-- `GroupPresentation.isFinitelyPresented_presentedGroup` for finite presentations, then
-- transports along the resulting equivalence via `Group.IsFinitelyPresented.equiv`.
-- Domain sampling:
-- 1. `Subgroup.fg_of_index_ne_zero` is mathlib's canonical Schreier theorem for finite
-- generation of finite-index subgroups.
-- 2. Proposition `2-4-1` is the chapter owner theorem producing the subgroup presentation from
-- a Schreier transversal.
-- 3. `GroupPresentation.isFinitelyPresented_presentedGroup` is the chapter owner bridge from a
-- finite presentation to `Group.IsFinitelyPresented`.
-- 4. `Group.IsFinitelyPresented.equiv` transports finite presentability across multiplicative
-- equivalences.
-- Primitive vs. derived:
-- the primitive source data are only `G`, `H`, the finite-index hypothesis on `H`, and the
-- finite-presentability hypothesis on `G`; the Schreier presentation of `H` is derived bridge
-- data supplied by Proposition `2-4-1`, so no parallel local presentation wrapper belongs here.
namespace Subgroup
instance isFinitelyPresented_of_finiteIndex [Group.IsFinitelyPresented G] [H.FiniteIndex] :
Group.IsFinitelyPresented H2.5 — Groups with a Single Defining Relator
Proposition 2.5.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-1: if r is cyclically reduced with respect to the chosen basis basis : FreeGroupBasis X F and the basis generator x occurs in r, then every nontrivial element of the normal closure of r also contains x.
universe u v
variable {X : Type u} {F : Type v} [Group F]
open Subgroup (normalClosure)
namespace FreeGroupBasis
-- Primary domain: one-relator groups, free bases, and normal closures.
--
-- Layer triage:
-- `source-facing`: a free group `F` with basis `basis : FreeGroupBasis X F`, a cyclically reduced
-- relator `r`, and a basis generator `x` occurring in `r`.
-- `core/canonical`: `FreeGroupBasis X F`, `FreeGroup.IsCyclicallyReduced`, and
-- `Subgroup.normalClosure`.
-- `bridge/view`: `basis.repr` reads elements of `F` in the canonical free-group model, and
-- `basisLetterOccurs` is the chapter's owner-side occurrence predicate for basis generators.
--
-- Domain sampling:
-- 1. `FreeGroupBasis X F` is the canonical owner abstraction for a chosen basis of a free group.
-- 2. `FreeGroup.IsCyclicallyReduced` is mathlib's owner predicate for cyclically reduced words in
-- the concrete free-group model.
-- 3. `Subgroup.normalClosure` is the owner construction for the normal closure of a relator.
-- 4. `basisLetterOccurs` from Proposition `1-7-4` is the established bridge predicate expressing
-- that a basis generator occurs in the reduced word of an element.
--
-- Primitive vs. derived:
-- the primitive source data are the basis `basis`, the relator `r`, and the chosen generator
-- `x`; cyclic reduction and generator occurrence are both read canonically through `basis.repr`,
-- so no parallel wrapper around reduced words is introduced.
theorem basisLetterOccurs_of_mem_normalClosure_singleton_of_isCyclicallyReduced
(basis : FreeGroupBasis X F) {r w : F} {x : X}
(hr : FreeGroup.IsCyclicallyReduced (basis.repr r).toWord)
(hx : basisLetterOccurs basis x r)
(hw : w ∈ normalClosure {r}) (hw_ne : w ≠ 1) :
basisLetterOccurs basis x wProposition 2.5.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-2: in a staggered presentation, any consequence whose generators all lie in the interval α ≤ i ≤ ω is already a consequence of the relators whose generators lie in that same interval.
universe u v w
-- Declarations for this item are recorded in this dedicated item file.
namespace GroupPresentation
variable {ι : Type u} [LinearOrder ι]
variable {Y : ι → Type v}
variable {J : Type w}
open Subgroup
local notation "Generators" => Σ i, Y i
variable [Preorder J]
theorem consequence_of_interval_relators_of_staggered_presentation
(r : J → FreeGroup Generators)
(hstaggered : IsStaggeredRelatorFamily r)
{α ω : ι} {w : FreeGroup Generators}
(hw : w ∈ normalClosure (Set.range r))
(hsupp : SupportedOnInterval α ω w) :
w ∈ normalClosure (relatorsSupportedOnInterval r α ω)Proposition 2.5.3
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-3: if F is a free group, w : Fin n → F is a family of nontrivial elements, and a : Fin n → ℤ is a family of nonzero integers, then F embeds in a group containing an element g for which the alternating word w₁ t^{a₁} ··· wₙ t^{aₙ} evaluates to the identity.
open scoped Monoid.Coprod
open Monoid.Coprod
-- Declarations for this item will be appended below by the statement pipeline.
universe u
variable {F : Type u} [Group F]
-- Primary domain: one-relator overgroups of free groups.
-- Layer triage:
-- `source-facing`: a finite ordered family `w : Fin n → F` of nontrivial coefficients in the free
-- group `F`, a parallel family `a : Fin n → ℤ` of nonzero exponents, and the alternating
-- one-variable equation `w₁ t^{a₁} ··· wₙ t^{aₙ} = 1`.
-- `core/canonical`: the owner object for a one-variable equation over `F` is the free product
-- `F ∗ Multiplicative ℤ`, evaluated in an overgroup by
-- `lift φ (zpowersHom G g) : F ∗ Multiplicative ℤ →* G`.
-- `bridge/view`: the source data determine the coproduct equation below; the overgroup witness is
-- still an injective homomorphism `φ : F →* G` together with an element `g : G` at which that
-- source-facing equation evaluates to `1`.
-- Domain sampling:
-- 1. `IsFreeGroup F` is mathlib's owner abstraction for the hypothesis that `F` is free.
-- 2. `F ∗ Multiplicative ℤ` together with `inl`, `inr`, and `lift` is the chapter/mathlib owner
-- API for one-variable words and their evaluation.
-- 3. `zpowersHom G g` is the canonical map sending the free variable to `g`.
-- 4. Proposition `1-8-3` already treats `F ∗ Multiplicative ℤ` as the owner type of one-variable
-- equations, so the local bridge should align with that owner vocabulary rather than introducing
-- a parallel evaluation API.
-- 5. `List.ofFn` and `List.prod` encode the ordered product matching the textbook equation word
-- `w₁ t^{a₁} ··· wₙ t^{aₙ}` inside the coproduct owner.
-- Primitive vs. derived:
-- the primitive source data are the free group `F`, the ordered coefficient family `w`, and the
-- ordered exponent family `a`, assembled directly into the canonical coproduct word
-- `w₁ t^{a₁} ··· wₙ t^{aₙ}`. The overgroup `G`, the injective homomorphism `φ`, and the chosen
-- element `g : G` are witness data in the proposition, and their evaluation map is derived from
-- the owner coproduct API.
theorem exists_embedding_realizing_alternating_relator [IsFreeGroup F] {n : ℕ}
(w : Fin n → F) (a : Fin n → ℤ) (hw : ∀ i, w i ≠ 1) (ha : ∀ i, a i ≠ 0) :
∃ (G : Type u) (_ : Group G) (φ : F →* G),
Function.Injective φ ∧
∃ g : G,
lift φ (zpowersHom G g) (alternatingEquation w a) = 1Proposition 2.5.4
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-4: every presentation with a single defining relator has solvable word problem. In the owner formulation, the singleton relator set {r} has decidable trivial-word problem in its presented group.
universe u
namespace GroupPresentation
variable {X : Type u} [Primcodable X]
theorem hasSolvableWordProblem_singleton (r : FreeGroup X) :
HasSolvableWordProblem ({r} : Set (FreeGroup X))Proposition 2.5.5
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-5: if G = (X; r) is a one-relator group, X₀ ⊆ X is recursive, and G₀ is the subgroup generated by the image of X₀, then one can decide whether a signed word on X represents an element of G₀.
universe u
namespace GroupPresentation
variable {X : Type u} [Primcodable X]
-- Layer triage:
-- `source-facing`: a one-relator group `G = (X; r)`, a recursive subset `X₀ ⊆ X`, the subgroup
-- `G₀` generated by the image of `X₀`, and the decision problem of whether a word in the free
-- group represents an element of `G₀`.
-- `core/canonical`: `PresentedGroup ({r} : Set (FreeGroup X))`, `PresentedGroup.mk`,
-- `PresentedGroup.of`, `Subgroup.closure`, and `ComputablePred`.
-- `bridge/view`: a signed word `L : List (X × Bool)` represents an element of `G₀` exactly when
-- its image under the canonical quotient map belongs to
-- `Subgroup.closure (PresentedGroup.of '' X₀)`.
-- Domain sampling:
-- 1. `PresentedGroup ({r} : Set (FreeGroup X))` is mathlib's canonical one-relator quotient.
-- 2. `PresentedGroup.mk ({r} : Set (FreeGroup X))` is the canonical quotient map from
-- `FreeGroup X`.
-- 3. `PresentedGroup.of` is the canonical map from defining generators into that quotient.
-- 4. `Subgroup.closure` is the owner construction for the subgroup generated by a subset.
-- 5. `ComputablePred` is the chapter's canonical computability interface for decidability on
-- coded words.
-- Primitive vs. derived:
-- the primitive mathematical data are the relator `r`, the recursive subset `X₀`, and the signed
-- word `L`; the subgroup generated by the image of `X₀` is a derived owner-side object, so the
-- statement uses `Subgroup.closure (PresentedGroup.of '' X₀)` directly rather than a parallel
-- local wrapper.
-- Proof sketch: apply the standard one-relator subgroup-membership algorithm to the subgroup
-- generated by the image of the recursive subset `X₀`; the recursive hypothesis gives an
-- effective test for whether a defining generator lies in `X₀`, so signed words can be decided
-- for membership in the corresponding subgroup of the quotient.
theorem computable_represents_element_of_generatorImageSubgroup
(r : FreeGroup X) (X₀ : Set X) (hX₀ : ComputablePred fun x : X ↦ x ∈ X₀) :
ComputablePred fun L : List (X × Bool) ↦
PresentedGroup.mk ({r} : Set (FreeGroup X)) (FreeGroup.mk L) ∈
Subgroup.closure (PresentedGroup.of '' X₀)Proposition 2.5.6
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-6: if X₁ and X₂ are recursive subsets of the chosen basis basis : FreeGroupBasis X F, F₁ and F₂ are the subgroups they generate in the ambient free group F, and N is the normal closure of r, then the subset F₁ N F₂ of F has decidable membership for signed words on the basis alphabet X.
open scoped Pointwise
open Subgroup
universe u v
variable {X : Type u} {F : Type v} [Group F] [Primcodable X]
variable (basis : FreeGroupBasis X F) (X₁ X₂ : Set X) (r : F)
local notation "F₁" => closure (basis '' X₁)
local notation "F₂" => closure (basis '' X₂)
local notation "N" => normalClosure (Set.singleton r)
-- Layer triage:
-- `source-facing`: an ambient free group `F` equipped with a chosen basis
-- `basis : FreeGroupBasis X F`, recursive subsets `X₁`, `X₂` of that basis, the generated
-- subgroups `F₁`, `F₂`, the normal closure `N` of a relator `r : F`, and the decision problem for
-- the subset `F₁ N F₂` of `F`.
-- `core/canonical`: Proposition `2-5-5`'s owner theorem
-- `GroupPresentation.computable_represents_element_of_generatorImageSubgroup`, transported through
-- `basis.repr`, together with `Subgroup.closure`, `Subgroup.normalClosure`,
-- `Subgroup.mul_normal`, `MonoidHom.map_closure`, `FreeGroup.mk`, and `ComputablePred`.
-- `bridge/view`: a signed word `L : List (X × Bool)` encodes the ambient element
-- `basis.repr.symm (FreeGroup.mk L)`, and the source product `F₁ N` is expressed canonically as
-- the subgroup join `F₁ ⊔ N` via `Subgroup.mul_normal`; after quotienting by `N`, membership in
-- `F₁ N F₂` is read as membership in the product of the two canonical generated subgroups of the
-- one-relator quotient, then pulled back along `basis.repr`.
-- Domain sampling:
-- 1. `FreeGroupBasis X F` is the chapter and mathlib owner abstraction for a chosen basis of an
-- ambient free group.
-- 2. `basis.repr : F ≃* FreeGroup X` is the canonical transport between intrinsic basis-level
-- elements of `F` and coded words on `X`.
-- 3. Proposition `2-5-5`'s
-- `GroupPresentation.computable_represents_element_of_generatorImageSubgroup` is the chapter's
-- owner theorem for recursive generated-subgroup membership in a one-relator quotient.
-- 4. `Subgroup.closure` and `Subgroup.normalClosure` are the owner constructions for generated
-- subgroups and normal closures.
-- 5. `Subgroup.mul_normal` is the owner theorem identifying the source product `F₁ N` with the
-- subgroup join `F₁ ⊔ N` when `N` is normal.
-- 6. `ComputablePred` is the project's canonical interface for algorithmic decidability on coded
-- words.
-- Primitive vs. derived:
-- the primitive source data are the chosen basis `basis`, the recursive subsets `X₁`, `X₂`, and
-- the relator `r`; the subgroup owners `F₁`, `F₂`, `N`, and the joined factor `F₁ ⊔ N` are
-- derived from that data and are therefore kept only as owner-side local notation built from
-- `Subgroup.closure`, `Subgroup.normalClosure`, and subgroup join.
theorem computable_represents_element_of_generated_subgroup_mul_normalClosure_mul_generated_subgroup
(hX₁ : ComputablePred fun x : X ↦ x ∈ X₁)
(hX₂ : ComputablePred fun x : X ↦ x ∈ X₂) :
ComputablePred fun L : List (X × Bool) ↦
basis.repr.symm (FreeGroup.mk L) ∈
(((F₁ ⊔ N : Subgroup F) : Set F) * F₂)Proposition 2.5.7
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-7: if two elements of a free group have the same singleton normal closure, then one is conjugate to the other or to its inverse.
universe u
variable {F : Type u} [Group F] [IsFreeGroup F]
open Subgroup
-- Layer triage:
-- `source-facing`: two elements `r₁ r₂ : F` in a free group with equal normal closures.
-- `core/canonical`: `Subgroup.normalClosure` for the normal subgroup generated by one element and
-- `IsConj` for conjugacy.
-- `bridge/view`: the source phrase “the same normal closure” is rendered canonically as equality
-- of the singleton normal closures `Subgroup.normalClosure {r₁}` and
-- `Subgroup.normalClosure {r₂}`.
-- Domain sampling:
-- 1. `Subgroup.normalClosure` is mathlib's owner construction for the normal closure of a subset.
-- 2. `IsConj` is mathlib's owner relation for conjugacy in a group.
-- 3. The surrounding chapter already states free-group results on abstract groups `[IsFreeGroup F]`
-- rather than only on the concrete model `FreeGroup X`, so the same owner level is used here.
-- 4. `conjugate_or_conjugate_inv_of_normalClosure_eq` is itself the chapter owner theorem for
-- this Magnus conclusion, so no extra wrapper or basis-level restatement belongs here.
-- Primitive vs. derived:
-- the primitive data are just the two elements and the equality of their singleton normal
-- closures; no extra presentation package or chosen basis belongs in the statement.
-- Proof sketch: this is Magnus's conjugacy theorem for one-relator normal closures in a free
-- group. One analyzes cyclic reductions of `r₁` and `r₂`; equality of their normal closures
-- forces the reduced relators to agree up to cyclic permutation and inversion, which is exactly
-- conjugacy to `r₂` or to `r₂⁻¹`.
theorem conjugate_or_conjugate_inv_of_normalClosure_eq
(r₁ r₂ : F)
(hclosure : normalClosure ({r₁}) = normalClosure ({r₂})) :
IsConj r₁ r₂ ∨ IsConj r₁ r₂⁻¹Proposition 2.5.8
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-8: if r₁ and r₂ are elements of a free group and, for some positive integer n, the power r₁ ^ n lies in the normal closure of r₂ ^ n, then r₁ lies in the normal closure of r₂.
universe u
variable {F : Type u} [Group F] [IsFreeGroup F]
open Subgroup
-- Layer triage:
-- `source-facing`: elements `r₁ r₂ : F` of an arbitrary free group and a positive power relation
-- between their singleton normal closures.
-- `core/canonical`: `Subgroup.normalClosure` on singleton subsets of the ambient group.
-- `bridge/view`: the singleton normal closure is the source-facing relation, while the associated
-- one-relator quotient is only an auxiliary view; no separate quotient wrapper belongs in the
-- public statement.
-- Domain sampling:
-- 1. `Subgroup.normalClosure` is mathlib's owner construction for the normal subgroup generated by
-- a subset, so it is the correct owner abstraction for “is a consequence of `r₂`”.
-- 2. `Subgroup.normalClosure_subset_iff` is mathlib's canonical bridge from subset membership to
-- an inclusion of normal closures, so the singleton-inclusion reformulation is already
-- upstream and does not need a parallel local theorem here.
-- 3. `IsFreeGroup` is mathlib's owner abstraction for the intrinsic notion that the ambient group
-- is free, so the proposition stays on an abstract free group rather than choosing a basis.
-- 4. `conjugate_or_conjugate_inv_of_normalClosure_eq` from Proposition `2-5-7` is the chapter's
-- owner theorem for equality of singleton normal closures in an abstract free group, so the
-- current item should stay at the same owner level rather than introducing a quotient wrapper.
-- 5. `conjugate_or_conjugate_inv_of_mem_normalClosure_of_isPrimitiveElement` from Proposition
-- `2-5-14` is the adjacent chapter owner theorem for source-facing membership in a singleton
-- normal closure, confirming that normal-closure membership itself is already the right public
-- surface here.
-- Primitive vs. derived:
-- the primitive public data are only `r₁`, `r₂`, the positive integer `n`, and the hypothesis
-- that `r₁ ^ n` lies in the singleton normal closure generated by `r₂ ^ n`; passing to a
-- one-relator quotient is a derived proof view rather than primitive API data. The associated
-- singleton-normal-closure inclusion is likewise derived owner-level API, and its canonical
-- formulation already comes from `Subgroup.normalClosure_subset_iff`.
theorem mem_normalClosure_singleton_of_pow_mem_normalClosure_pow_singleton
(r₁ r₂ : F) (n : ℕ+)
(hpow : r₁ ^ (n : ℕ) ∈ normalClosure ({r₂ ^ (n : ℕ)})) :
r₁ ∈ normalClosure ({r₂})Proposition 2.5.9
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-9: if the one-relator group G = (X; r) is free, then either r = 1 or r is primitive in the ambient free group on X.
universe u
variable {X : Type u} (r : FreeGroup X)
local notation "G" => PresentedGroup (Set.singleton r : Set (FreeGroup X))
-- Layer triage:
-- `source-facing`: a one-relator group `G = (X; r)`, rendered canonically as the quotient
-- `PresentedGroup (Set.singleton r : Set (FreeGroup X))`, together with the hypothesis that this quotient is
-- itself
-- free.
-- `core/canonical`: `PresentedGroup` for one-relator presentations, `IsFreeGroup` for the
-- ambient freeness hypothesis on the quotient, and `IsPrimitiveElement` as the chapter owner for
-- the statement that `r` belongs to some basis of the ambient free group on `X`.
-- `bridge/view`: `IsPrimitiveElement r` records a same-universe basis witness for `r`; an
-- arbitrary chosen basis is canonically reindexed to its range via
-- `FreeGroupBasis.reindexRange`, so
-- the source wording is recovered without a duplicate existential wrapper theorem.
-- Domain sampling:
-- 1. `PresentedGroup R` is mathlib's canonical owner for a group defined by generators and
-- relators.
-- 2. `IsFreeGroup` is mathlib's owner predicate for freeness of a group.
-- 3. `FreeGroupBasis X F`, together with the owner bridge `FreeGroupBasis.reindexRange`, is the
-- canonical API for chosen free bases and the corresponding basis subset in the ambient group.
-- 4. `IsPrimitiveElement` from `CombinatorialGroupTheory.Basic` is the project owner for the
-- recurring “belongs to some basis”
-- conclusion, while basis witnesses are bridge data.
-- Primitive vs. derived:
-- the primitive data are only the generator type `X`, the relator `r`, and the freeness
-- hypothesis on the quotient; primitivity of `r` is the derived conclusion, while explicit basis
-- witnesses are companion API.
theorem relator_eq_one_or_isPrimitiveElement_of_presentedGroup_isFree
(hfree : IsFreeGroup G) :
r = 1 ∨ IsPrimitiveElement rProposition 2.5.10
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-10: let G = (X; r) be a one-relator group on a finite generator set X. If G can be generated by fewer elements than X has, then the relator r is primitive in the ambient free group on X.
universe u
variable {X : Type u} [Finite X] (r : FreeGroup X)
local notation "G" => PresentedGroup (Set.singleton r)
-- Layer triage:
-- `source-facing`: a one-relator group on a finite generator set `X`, with relator
-- `r : FreeGroup X`, whose quotient can be generated by fewer elements than `X` has.
-- `core/canonical`: the quotient owner `PresentedGroup (Set.singleton r)`, the invariant
-- `Group.rank`
-- measuring the minimum size of a generating set, the finite cardinal `Nat.card X` of the ambient
-- generator type, and `IsPrimitiveElement` for the primitive relator conclusion.
-- `bridge/view`: the source phrase “`|X| = nMinusOne + 1` and `G` is generated by `nMinusOne`
-- elements” is expressed by the owner-level inequality
-- `Group.rank (PresentedGroup (Set.singleton r)) < Nat.card X`. The public statement keeps the
-- source-facing `Nat.card X` form rather than replacing it by `Group.rank (FreeGroup X)`, while
-- the source conclusion “`r` is a member of some basis” is expressed by `IsPrimitiveElement r`.
-- Domain sampling:
-- 1. `PresentedGroup R` is mathlib's canonical owner abstraction for a group with generators and
-- relators; in this file the one-relator quotient is the owner-level object `G`.
-- 2. `PresentedGroup.instFG` from Definition `2-1-1` is the chapter owner bridge that supplies
-- the finite-generation instance required to form `Group.rank G`.
-- 3. `Group.rank` is the chapter's canonical owner invariant for “generated by at most `n`
-- elements”; compare Proposition `1-6-6`.
-- 4. `Nat.card X` is the chapter's intrinsic finite-cardinality owner for a generator type,
-- avoiding any public dependence on an ordered `Fin` indexing.
-- 5. `IsPrimitiveElement` from `CombinatorialGroupTheory.Basic` is the project owner for the
-- recurring
-- “belongs to some basis” conclusion.
-- Primitive vs. derived:
-- the primitive source data are only the finite generator type `X`, the ambient relator `r`, and
-- the owner-level rank comparison between the quotient and the ambient generator cardinality; the
-- primitive conclusion about `r` is derived, and any explicit basis witness is auxiliary data
-- behind the owner predicate.
theorem isPrimitiveElement_of_one_relator_group_generated_by_fewer_elements
(hrank : Group.rank G < Nat.card X) :
IsPrimitiveElement rProposition 2.5.11
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-11: if r₁ and r₂ lie in the same automorphism orbit of the free group and each has minimal reduced-word length under Aut(F(X)), then the same number of generators occur in their canonical reduced words.
universe u
open MulAction
variable {X : Type u}
theorem reducedWord_support_card_eq_of_orbitRel_of_minimal_length
(r₁ r₂ : FreeGroup X)
(hmin₁ : ∀ α : MulAut (FreeGroup X), r₁.toWord.length ≤ (α r₁).toWord.length)
(hmin₂ : ∀ α : MulAut (FreeGroup X), r₂.toWord.length ≤ (α r₂).toWord.length)
(hequiv : orbitRel (MulAut (FreeGroup X)) (FreeGroup X) r₂ r₁) :
(reducedWordSupport r₁).card = (reducedWordSupport r₂).cardProposition 2.5.12
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-12: if the relator r in the one-relator presentation (x₁, …, xₙ; r) has minimal reduced-word length in its automorphism orbit and its reduced-word support is exactly the first k generators, then the presented group splits as the free product of the one-relator group on those k generators and a free group on the remaining generators, and the smaller one-relator factor is freely indecomposable.
open scoped Monoid.Coprod
open FreeGroup
universe u v w
-- Declarations for this item are recorded in this dedicated item file.
-- Primary domain: one-relator groups and free-product decompositions.
-- Layer triage:
-- `source-facing`: a one-relator presentation on generators `x₁, …, xₙ`, together with the
-- hypothesis that the relator has minimal reduced length in its automorphism orbit and uses
-- exactly the first `k` generators.
-- `core/canonical`: `PresentedGroup` for one-relator presentations, `MulAut (FreeGroup (Fin n))`
-- for automorphisms of the ambient free group, `reducedWordSupport` for reduced-word support, and
-- `Monoid.Coprod` for the free-product decomposition.
-- `bridge/view`: the source phrase “`G₁ = (x₁, …, x_k; r)`” is encoded by the canonical relator
-- obtained from `r` by the owner map `FreeGroup.lift` that keeps the first `k` generators and
-- sends the remaining ambient generators to `1`.
-- Domain sampling:
-- 1. `PresentedGroup ({r} : Set (FreeGroup (Fin n)))` is the canonical one-relator owner object.
-- 2. `MulAut (FreeGroup (Fin n))` is the owner abstraction for `Aut(F)`.
-- 3. `reducedWordSupport` from Proposition `1-5-6` is the project's owner abstraction for the
-- basis letters occurring in the canonical reduced word of a free-group element.
-- 4. `Fin.castLE` and `Fin.castLEEmb` are the canonical initial-segment inclusions `Fin k ↪ Fin n`
-- used to embed the smaller relator support into the ambient free group.
-- 5. `Monoid.Coprod` with notation `G₁ ∗ G₂` is mathlib's owner abstraction for free products.
-- Primitive vs. derived:
-- the primitive data are the relator `r`, the cutoff `k`, and the two source hypotheses. The
-- smaller relator, the induced one-relator factor on the first `k` generators, and the free
-- factor are derived canonical presentation-level objects.
variable {n k : ℕ} (hk : k ≤ n) (r : FreeGroup (Fin n))
local notation "r₀" => initialSegmentRelator k r
local notation "G" => PresentedGroup (Set.singleton r)
local notation "G₁" => PresentedGroup (Set.singleton r₀)
local notation "G₂" => FreeGroup (Fin (n - k))
-- Proof sketch: use the minimal-length hypothesis together with the exact support condition to
-- isolate the first `k` generators as the unique support of the relator. Rewrite the original
-- one-relator presentation as the free product of the smaller one-relator presentation on those
-- generators and the free group on the remaining generators. Then apply Magnus's
-- freely-indecomposable theorem to the smaller factor.
theorem one_relator_group_freeProduct_decomposition
(hmin : ∀ α : MulAut (FreeGroup (Fin n)),
r.toWord.length ≤ (α r).toWord.length)
(hsupp : reducedWordSupport r = (Finset.univ : Finset (Fin k)).map (Fin.castLEEmb hk)) :
∃ e : G ≃* (G₁ ∗ G₂), IsFreelyIndecomposable G₁Proposition 2.5.13
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-13, in owner form: every surface group is freely indecomposable.
open FreeGroup
universe u v
-- Layer triage:
-- `source-facing`: the standard orientable and nonorientable one-relator surface groups, the
-- property that an arbitrary group is isomorphic to one of them, and the assertion that such a
-- group is freely indecomposable.
-- `core/canonical`: `PresentedGroup` for the one-relator presentations and
-- `FreeGroupBasis.pairedCommutatorProduct` for the orientable surface relator, together with
-- `IsFreelyIndecomposable` from Proposition `2-5-12` for the ambient free-product conclusion.
-- `bridge/view`: group isomorphisms transporting the source-facing surface-group and
-- freely-indecomposable predicates.
-- Domain sampling:
-- 1. `PresentedGroup` is mathlib's owner abstraction for groups defined by generators and
-- relators, so the standard surface presentations should be recorded directly with that owner.
-- 2. `(FreeGroupBasis.ofFreeGroup (Fin g ⊕ Fin g)).pairedCommutatorProduct` from Proposition
-- `1-6-8` is the chapter owner for the orientable genus-`g` commutator relator, so the target
-- file should reuse that expression directly inside the orientable presentation.
-- 3. `IsFreelyIndecomposable` is the chapter owner abstraction for saying a group admits no
-- nontrivial free-product decomposition.
-- 4. Multiplicative equivalences `G ≃* H` are the canonical bridge for invariance statements
-- about the source-facing surface presentations.
-- Primitive vs. derived:
-- the primitive data are the nonorientable surface relator word together with the chapter owner
-- `FreeGroupBasis.pairedCommutatorProduct` for the orientable relator, and the owner predicate
-- `IsFreelyIndecomposable`; the corresponding singleton-relator `PresentedGroup`s and the
-- surface-group property are derived directly from that data.
open SurfaceGroup
theorem surface_group_not_proper_free_product (G : Type u) [Group G] (hG : IsSurfaceGroup G) :
IsFreelyIndecomposable GProposition 2.5.14
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-14: if the normal closure of q in a free group contains a primitive element p, then q is conjugate to p or to p⁻¹.
universe u
variable {F : Type u} [Group F] [IsFreeGroup F]
open Subgroup
theorem conjugate_or_conjugate_inv_of_mem_normalClosure_of_isPrimitiveElement
{p q : F} (hp : IsPrimitiveElement p) (hmem : p ∈ normalClosure {q}) :
IsConj q p ∨ IsConj q p⁻¹Proposition 2.5.15
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-15: if q and a primitive element p of a free group have singleton normal closures whose intersection is not contained in the commutator subgroup, then q is conjugate to p or to p⁻¹.
universe u
variable {F : Type u} [Group F] [IsFreeGroup F]
open Subgroup (normalClosure)
-- Primary domain: primitive elements in free groups, singleton normal closures, and conjugacy.
theorem conjugate_or_conjugate_inv_of_inf_normalClosure_not_le_commutator_of_isPrimitiveElement
(p q : F) (hp : IsPrimitiveElement p)
(hinter :
¬ normalClosure ({q} : Set F) ⊓ normalClosure ({p} : Set F) ≤ commutator F) :
IsConj q p ∨ IsConj q p⁻¹Proposition 2.5.16
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-16 (1): if G = (X; r) with r = s ^ m for m maximal, then the image of s in PresentedGroup ({r} : Set (FreeGroup X)) has order m.
universe u
variable {X : Type u}
variable (r s : FreeGroup X) (m : ℕ+)
local notation "rels" => (Set.singleton r : Set (FreeGroup X))
local notation "q" => PresentedGroup.mk rels
-- Layer triage:
-- `source-facing`: a one-relator group `G = (X; r)` with a maximal root decomposition
-- `r = s ^ m`.
-- `core/canonical`: `PresentedGroup ({r} : Set (FreeGroup X))` for the one-relator quotient,
-- `PresentedGroup.mk` for the image of `s`, `orderOf` and `IsOfFinOrder` for torsion, and
-- `IsConj` for conjugacy.
-- `bridge/view`: the textbook element `s̄` is rendered by the canonical quotient map
-- `q s`.
-- Domain sampling:
-- 1. `PresentedGroup ({r} : Set (FreeGroup X))` is the project's owner abstraction for a
-- one-relator group with relator `r`.
-- 2. `PresentedGroup.mk` is the canonical image map from the ambient free group to that quotient.
-- 3. `orderOf` and `IsOfFinOrder` are mathlib's owner APIs for exact order and finite order.
-- 4. `IsConj` is mathlib's canonical relation for conjugacy in a group.
-- Primitive vs. derived:
-- the primitive data are the relator `r`, its chosen maximal root `s`, the exponent `m`, and the
-- maximality hypothesis; the source-side condition `r ≠ 1` is redundant here, since no maximal
-- positive power decomposition can exist for `r = 1`. The image of `s` and the torsion-conjugacy
-- conclusions are derived owner-side statements on the presented group.
theorem orderOf_root_image_eq_maximal_exponent
(hroot : r = s ^ (m : ℕ))
(hmax : ∀ ⦃t : FreeGroup X⦄ ⦃n : ℕ+⦄, r = t ^ (n : ℕ) → n ≤ m) :
orderOf (q s) = mProposition 2.5.17
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-17: if G = (X; r) is a one-relator group and the relator r is not a proper power in FreeGroup X, then the quotient group PresentedGroup (Set.singleton r) is torsion free.
universe u
theorem isMulTorsionFree_presentedGroup_singleton_of_relator_not_properPower
{X : Type u} (r : FreeGroup X)
(hr : ¬ IsProperPower r) :
IsMulTorsionFree (PresentedGroup (Set.singleton r))Proposition 2.5.18
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-18: if a one-relator group has defining relator s ^ m with m maximal among all power decompositions of that relator, and if u is not a power of s, then the cyclic subgroup generated by the image of s in the quotient is disjoint from its conjugate by the image of u.
universe u
open scoped Pointwise
variable {X : Type u}
variable (s u : FreeGroup X) (m : ℕ+)
local notation "relator" => s ^ (m : ℕ)
local notation "rels" => ({relator} : Set (FreeGroup X))
local notation "q" => PresentedGroup.mk rels
-- Layer triage:
-- `source-facing`: a one-relator group `G = (X; r)` with `r = s^m`, where `m` is maximal among
-- power decompositions of `r`, together with an element `u` that is not a power of `s`.
-- `core/canonical`: `PresentedGroup ({s ^ (m : ℕ)} : Set (FreeGroup X))` for the one-relator
-- quotient and `Subgroup.zpowers` for the cyclic subgroups generated by the images of `s` and of
-- `u⁻¹ * s * u`.
-- `bridge/view`: the textbook phrase “the images of `s` and of `u⁻¹su` in `G`” is expressed by the
-- canonical quotient homomorphism `PresentedGroup.mk ({s ^ (m : ℕ)} : Set (FreeGroup X))`.
-- Domain sampling:
-- 1. `PresentedGroup ({r} : Set (FreeGroup X))` is the chapter's owner abstraction for a
-- one-relator group.
-- 2. `PresentedGroup.mk` is the canonical map from the ambient free group to the one-relator
-- quotient.
-- 3. `Subgroup.zpowers` is mathlib's canonical cyclic subgroup generated by a given group element.
-- 4. `MulAut.conj g • H` is mathlib's canonical subgroup-conjugation owner, so the cyclic
-- subgroup generated by the image of `u⁻¹ * s * u` should be treated as the conjugate of the
-- cyclic subgroup generated by the image of `s`, not as a second primitive object.
-- Primitive vs. derived:
-- the primitive source data are the root `s`, the exponent `m`, the maximality hypothesis for the
-- power decomposition of the relator, and the non-membership hypothesis `u ∉ Subgroup.zpowers s`.
-- The cyclic subgroup generated by the image of `s` is canonical derived data, and the cyclic
-- subgroup generated by the image of `u⁻¹ * s * u` is the further derived conjugate subgroup.
theorem disjoint_zpowers_image_root_and_conjugateSubgroup_of_not_mem_zpowers
(hmax :
∀ ⦃t : FreeGroup X⦄ ⦃n : ℕ+⦄, relator = t ^ (n : ℕ) → n ≤ m)
(hu : u ∉ Subgroup.zpowers s) :
Disjoint
(Subgroup.zpowers (q s))
((MulAut.conj (q u))⁻¹ • Subgroup.zpowers (q s))Proposition 2.5.19
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-19: if the one-relator group G = (X; r) has defining relator r = [u, v] = ⁅u, v⁆ for some words u and v, then G is torsion free.
open scoped commutatorElement
universe u
theorem presentedGroup_commutatorRelator_isMulTorsionFree
{X : Type u} (u v : FreeGroup X) :
IsMulTorsionFree (PresentedGroup ({⁅u, v⁆} : Set (FreeGroup X)))Proposition 2.5.20
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-20: every one-relator group G = (X; r) has a torsion-free normal subgroup of finite index. In the canonical owner form Q = PresentedGroup (Set.singleton r), this is expressed by a bundled finite-index normal subgroup whose underlying subgroup is torsion free.
universe u
variable {X : Type u}
variable (r : FreeGroup X)
local notation "Q" => PresentedGroup (Set.singleton r)
theorem exists_torsionFree_finiteIndexNormalSubgroup_of_oneRelator
: ∃ N : FiniteIndexNormalSubgroup Q, IsMulTorsionFree N.toSubgroupProposition 2.5.21
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-21 (1): if a one-relator group G = (X; r) has at least three generators, then its center is trivial.
universe u
variable {X : Type u}
variable (r : FreeGroup X)
local notation "rels" => (Set.singleton r : Set (FreeGroup X))
local notation "G" => PresentedGroup rels
local notation "Z" => Subgroup.center G
theorem center_eq_bot_of_oneRelator_card_ge_three
(hX : 3 ≤ Cardinal.mk X) :
Z = ⊥Proposition 2.5.22
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-22: there is an algorithm deciding whether a signed word on the generators of a one-relator group represents an element of the center of that group.
universe u
namespace GroupPresentation
variable {X : Type u} [Primcodable X]
variable (r : FreeGroup X)
-- Layer triage:
-- `source-facing`: a one-relator group `G = (X; r)` together with the decision problem of whether
-- a signed word on `X` represents an element of the center of `G`.
-- `core/canonical`: the owner quotient `PresentedGroup ({r} : Set (FreeGroup X))`, its center
-- `Subgroup.center (PresentedGroup ({r} : Set (FreeGroup X)))`, and the computability predicate
-- `ComputablePred` on signed words.
-- `bridge/view`: a signed word `L : List (X × Bool)` represents a central element exactly when
-- its image under the canonical quotient map `PresentedGroup.mk ({r} : Set (FreeGroup X))` lies
-- in `Subgroup.center (PresentedGroup ({r} : Set (FreeGroup X)))`.
-- Domain sampling:
-- 1. `PresentedGroup ({r} : Set (FreeGroup X))` is the canonical one-relator quotient attached to
-- the relator `r`.
-- 2. `Subgroup.center (PresentedGroup ({r} : Set (FreeGroup X)))` is mathlib's canonical owner of
-- the center of that quotient group.
-- 3. `FreeGroup.mk` is the canonical evaluation of a finite signed word in the free group.
-- 4. `ComputablePred` is the project's canonical interface for algorithmic decidability on coded
-- words.
-- Primitive vs. derived:
-- the primitive data are only the generator type `X` and the relator `r`; the center is a
-- derived canonical subgroup of the presented group, so the public statement is the computability
-- of center-membership for represented words rather than a new wrapper around one-relator groups.
-- Proof sketch: use the classical algorithm describing centralizers in one-relator groups. For a
-- signed word `L`, first pass to its image under
-- `PresentedGroup.mk ({r} : Set (FreeGroup X))` in the canonical one-relator quotient; then apply
-- the effective classification of centralizers in one-relator groups to decide whether that image
-- commutes with every generator, equivalently whether it lies in the center.
theorem computable_represents_central_element_singleton_relator :
ComputablePred fun L : List (X × Bool) ↦
PresentedGroup.mk ({r} : Set (FreeGroup X)) (FreeGroup.mk L) ∈
Subgroup.center (PresentedGroup ({r} : Set (FreeGroup X)))Proposition 2.5.23
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-23 (1): if the one-relator quotient defined by the relator r is abelian, then X has at most two generators.
open scoped commutatorElement
universe u v
variable {X : Type u}
local notation "RankTwoFreeAbelian" => Multiplicative (FreeAbelianGroup (Fin 2))
-- Layer triage:
-- `source-facing`: the one-relator group `PresentedGroup ({r} : Set (FreeGroup X))` and the
-- hypothesis that it is abelian.
-- `core/canonical`: `PresentedGroup ({r} : Set (FreeGroup X))`, `IsMulCommutative`, `IsCyclic`,
-- `RankTwoFreeAbelian`, and the chapter's canonical generator-cardinality layer `Cardinal.mk X`.
-- `bridge/view`: only part (2) needs a chosen basis `basis : FreeGroupBasis X F` of an ambient
-- free group `F`, because the source there compares the abstract relator in `F` with the
-- canonical rank-two normal forms `b` and `⁅a, b⁆`.
--
-- Domain sampling:
-- 1. `PresentedGroup ({w} : Set (FreeGroup X))` is the chapter's canonical owner for the
-- one-relator quotient with defining relator `w`.
-- 2. `center_eq_bot_of_oneRelator_card_ge_three` from Proposition `2-5-21` is the preceding
-- owner-side obstruction behind part (1).
-- 3. `abelian_subgroup_of_one_relator_group_classification` from Proposition `2-5-25` is the
-- later owner-side classification result living at the same one-relator owner level as part
-- (3).
-- 4. `Cardinal.mk X` is the chapter's owner abstraction for generator cardinality, already used in
-- Proposition `2-5-21`.
-- 5. `IsMulCommutative`, `IsCyclic`, and `RankTwoFreeAbelian` give the library-facing
-- formulations of the textbook abelianity hypothesis and the alternatives
-- “cyclic” and “free abelian of rank `2`”.
--
-- Primitive vs. derived:
-- for parts (1) and (3), the primitive public data are only the relator `r : FreeGroup X` and
-- the abelianity assumption on the corresponding one-relator quotient. Part (2) additionally uses
-- a chosen basis `basis : FreeGroupBasis X F` to compare an abstract relator in an ambient free
-- group with the canonical rank-two model.
theorem card_le_two_of_abelian_presentedGroup
(r : FreeGroup X)
(hab : IsMulCommutative (PresentedGroup ({r} : Set (FreeGroup X)))) :
Cardinal.mk X ≤ 2Proposition 2.5.24
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-24: if H is a subgroup of the one-relator group PresentedGroup ({r} : Set (FreeGroup X)) and H satisfies a nontrivial law, then the torsion-free case forces H to be locally cyclic or of the form ⟨x, y | x⁻¹ y x = y^n⟩, while the presence of torsion in the ambient group forces H to be cyclic or infinite dihedral.
universe u v
-- Declarations for this item are recorded in this dedicated item file.
-- Primary domain: one-relator groups and subgroup structure under group laws.
-- Layer triage:
-- `source-facing`: a subgroup of a one-relator group satisfying a nontrivial law, together with
-- the torsion-free versus torsion dichotomy for the ambient one-relator group.
-- `core/canonical`: `PresentedGroup ({r} : Set (FreeGroup X))` for the one-relator owner,
-- `Subgroup` for the subgroup owner, `SatisfiesNontrivialLaw` for the intrinsic law hypothesis on
-- the subgroup type,
-- `IsMulTorsionFree` and `IsOfFinOrder` for the torsion split, `IsCyclic` for cyclicity, and
-- `DihedralGroup 0` for the infinite dihedral group. The exceptional Baumslag-Solitar branch is
-- source-facing through the named owner `BS(1, n)`.
-- `bridge/view`: a chosen presentation equivalence
-- `PresentedGroup ({r} : Set (FreeGroup X)) ≃* G` transports the canonical owner-level theorem to
-- an arbitrary ambient group `G`; the Baumslag-Solitar exceptional family is compared by
-- isomorphism with the named owner `BS(1, n)`.
-- Domain sampling:
-- 1. `PresentedGroup ({r} : Set (FreeGroup X))` is the chapter owner abstraction for one-relator
-- groups throughout nearby propositions `2-5-25`, `2-5-26`, and `2-5-29`.
-- 2. Definition `2-1-1` uses `PresentedGroup R ≃* G` directly as presentation data, so a chosen
-- equivalence is the right bridge layer, not the main owner-level statement.
-- 3. A law is intrinsically a property of a group, so the subgroup hypothesis is best expressed
-- on the subgroup type `H` itself rather than as extra structure on the ambient `Subgroup G`.
-- 4. Nearby Theorem `2-2-5` packages `BS(2, 3)` in the source-facing owner namespace
-- `BaumslagSolitar23`, so the standard family `BS(1, n)` should likewise be named at the owner
-- level rather than exposed only through a raw presentation expression.
-- 5. Nearby Proposition `2-5-25` already renders “locally cyclic” directly as
-- `∀ K : Subgroup H, K.FG → IsCyclic K`, so that owner-level form is reused here.
-- Primitive vs. derived:
-- the primitive public data are the relator `r`, the subgroup `H`, the law satisfied by `H`, and
-- the source-facing Baumslag-Solitar owner `BS(1, n)`; the locally cyclic, cyclic, and
-- infinite-dihedral alternatives are derived conclusions.
notation "BS(1," n ")" => BaumslagSolitarOne.Group n
variable {X : Type u} (r : FreeGroup X)
local notation "Q" => PresentedGroup (Set.singleton r)
theorem subgroup_with_nontrivial_law_classification_in_one_relator_group
(H : Subgroup Q)
(hHlaw : SatisfiesNontrivialLaw H) :
(IsMulTorsionFree Q →
(∀ K : Subgroup H, K.FG → IsCyclic K) ∨
∃ n : ℤ, Nonempty (H ≃* BS(1, n))) ∧
((∃ g : Q, g ≠ 1 ∧ IsOfFinOrder g) →
IsCyclic H ∨ Nonempty (H ≃* DihedralGroup 0))Proposition 2.5.25
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-25 (1): if H is an abelian subgroup of a one-relator group, then either every finitely generated subgroup of H is cyclic and each nontrivial element of H is a pth power for only finitely many primes p, or H is free abelian of rank 2.
universe u
variable {X : Type u} (r : FreeGroup X)
local notation "Q" => PresentedGroup (Set.singleton r)
local notation "RankTwoFreeAbelian" => Multiplicative (FreeAbelianGroup (Fin 2))
theorem abelian_subgroup_of_one_relator_group_classification
(H : Subgroup Q) (hab : IsMulCommutative H) :
((∀ K : Subgroup H, K.FG → IsCyclic K) ∧
(∀ g : H, g ≠ 1 →
Set.Finite {p : ℕ | Nat.Prime p ∧ ∃ x : H, x ^ p = g})) ∨
Nonempty (H ≃* RankTwoFreeAbelian)Proposition 2.5.26
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-26 (1): every subgroup of a one-relator group either contains a free subgroup of rank 2 or is solvable.
universe u
variable {X : Type u}
variable (r : FreeGroup X)
local notation "Q" => PresentedGroup (Set.singleton r)
theorem subgroup_of_oneRelator_contains_rankTwoFree_or_isSolvable
(H : Subgroup Q) :
(∃ K : Subgroup Q, K ≤ H ∧ Nonempty (K ≃* FreeGroup (Fin 2))) ∨ IsSolvable HProposition 2.5.27
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-27: if u and v represent the same element of the one-relator group PresentedGroup (Set.singleton (s ^ n)), where n > 1 and the root s is cyclically reduced, and some generator x occurs in u but not in v, then u contains a consecutive subword that is also a consecutive subword of the relator s ^ n or of its inverse, and whose length is greater than (n - 1) * |s|.
universe u
variable {X : Type u}
local notation "basis" => FreeGroupBasis.ofFreeGroup X
variable (s : FreeGroup X) (n : ℕ)
local notation "q" => PresentedGroup.mk (Set.singleton (s ^ n))
-- Layer triage:
-- `source-facing`: a one-relator quotient `G = (X; s ^ n)` with `s` cyclically reduced, together
-- with two free-group elements `u` and `v` that have the same image in `G`, and a basis letter
-- `x` that occurs in `u` but not in `v`.
-- `core/canonical`: `PresentedGroup (Set.singleton (s ^ n))` for the one-relator quotient, `q`
-- for the quotient
-- map, `List.IsInfix` for consecutive subwords of the canonical reduced words,
-- `basisLetterOccurs basis` for generator occurrence, and `FreeGroup.norm` for reduced-word
-- length.
-- `bridge/view`: the source phrase “the letter `x` occurs in `u` but not in `v`” is read through
-- the chapter's owner-side predicate `basisLetterOccurs` specialized to the canonical basis
-- `basis`, with no auxiliary presentation wrapper.
-- Domain sampling:
-- 1. `PresentedGroup (Set.singleton r)` is the chapter's canonical owner for the
-- one-relator group on generators `X`.
-- 2. `PresentedGroup.mk` is the canonical map identifying when two ambient free-group elements
-- represent the same element of the quotient.
-- 3. `List.IsInfix` from mathlib is the owner predicate for a consecutive subword of a reduced
-- word.
-- 4. `basisLetterOccurs basis` from Proposition `1-7-4` is the chapter's owner-side occurrence
-- predicate for generators in the concrete free-group model.
-- 5. `FreeGroup.IsCyclicallyReduced` is the chapter's owner predicate for the cyclically reduced
-- root hypothesis needed by the Newman--Greendlinger conclusion for the relator `s ^ n`.
-- 6. `FreeGroup.norm` is the canonical reduced-word length on `FreeGroup X`, so the textbook
-- quantity `|s|` is rendered directly as `FreeGroup.norm s`.
-- Primitive vs. derived:
-- the primitive source data are the root word `s`, the exponent `n`, the two representative words
-- `u` and `v`, the cyclically reduced root hypothesis on `s`, and the letter-occurrence
-- discrepancy for `x`. The quotient equality and the long common subword with the relator or its
-- inverse are the derived owner-level conclusions.
theorem exists_long_common_part_with_relator_of_eq_in_power_relator_quotient
(u v : FreeGroup X) {x : X} (hn : 1 < n)
(hs : FreeGroup.IsCyclicallyReduced s.toWord)
(heq : q u = q v)
(hxu : basisLetterOccurs basis x u)
(hxv : ¬ basisLetterOccurs basis x v) :
∃ part : List (X × Bool),
part <:+: u.toWord ∧
(part <:+: (s ^ n).toWord ∨ part <:+: ((s ^ n)⁻¹).toWord) ∧
part.length > (n - 1) * s.normProposition 2.5.28
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-28: if r is cyclically reduced with respect to the chosen basis basis : FreeGroupBasis X F, then any proper subword of r lying in its singleton normal closure is trivial.
universe u v
variable {X : Type u} {F : Type v} [Group F]
open Subgroup (normalClosure)
namespace FreeGroupBasis
-- Layer triage:
-- `source-facing`: a chosen free basis `basis : FreeGroupBasis X F`, a cyclically reduced relator
-- `r : F`, and an element `s : F` whose canonical reduced word is a nonempty proper consecutive
-- subword of the reduced word of `r`.
-- `core/canonical`: the owner namespace `FreeGroupBasis`, together with
-- `FreeGroup.IsCyclicallyReduced`, `Subgroup.normalClosure`, the reduced-word map
-- `FreeGroup.toWord`, and `List.IsInfix`.
-- `bridge/view`: the textbook phrase “proper subword of `r`” is read directly through the owner
-- reduced-word map `(basis.repr ·).toWord`, so no parallel wrapper around reduced words or normal
-- closures is introduced.
--
-- Domain sampling:
-- 1. `FreeGroupBasis X F` is the canonical owner abstraction for a chosen basis of a free group,
-- and nearby Chapter II Magnus theorems with basis data already live in
-- `namespace FreeGroupBasis`.
-- 2. `FreeGroup.IsCyclicallyReduced` is the owner predicate for cyclically reduced reduced words.
-- 3. `Subgroup.normalClosure` is the canonical owner for the normal closure of a relator.
-- 4. `FreeGroup.toWord` is the owner reduced-word API on the canonical free-group model.
-- 5. `List.IsInfix` from mathlib is the canonical consecutive-subword predicate on reduced words.
--
-- Primitive vs. derived:
-- the primitive public data are the basis `basis`, the relator `r`, the candidate subword list
-- `part`, and the corresponding free-group element `s`; “proper subword of `r`” is expressed
-- directly through the owner reduced-word equality `(basis.repr s).toWord = part`,
-- `List.IsInfix`, and the strict length inequality, so no extra wrapper predicate is kept.
theorem eq_one_of_mem_normalClosure_singleton_of_hasPart_of_isCyclicallyReduced
(basis : FreeGroupBasis X F) {r s : F} {part : List (X × Bool)}
(hr : FreeGroup.IsCyclicallyReduced (basis.repr r).toWord)
(hs_word : (basis.repr s).toWord = part)
(hpart : part <:+: (basis.repr r).toWord)
(hpart_ne : part ≠ [])
(hproper : part.length < (basis.repr r).toWord.length)
(hs : s ∈ normalClosure ({r} : Set F)) :
s = 1Proposition 2.5.29
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-29: if a one-relator group has torsion, then the centralizer of every nontrivial element is cyclic. For the canonical quotient Q := PresentedGroup ({r} : Set (FreeGroup X)), torsion is expressed by a nontrivial finite-order element of Q.
universe u
variable {X : Type u}
variable (r : FreeGroup X)
local notation "rels" => (Set.singleton r : Set (FreeGroup X))
local notation "Q" => PresentedGroup rels
theorem centralizer_nontrivial_isCyclic_of_torsion_oneRelator
(htorsion : ∃ t : Q, t ≠ 1 ∧ IsOfFinOrder t) (g : Q) (hg : g ≠ 1) :
IsCyclic (Subgroup.centralizer {g})Proposition 2.5.30
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-30: let G = (a, b; s ^ m) with 1 < m, where s is not conjugate in the free group on {a, b} to any power of a or of b. Then for all sufficiently large n, the pair consisting of the image of a and the image of b ^ n is a free basis of the subgroup of G that it generates.
universe u
open LargePowerFreeSubgroupGenerator
variable (s : FreeGroup LargePowerFreeSubgroupGenerator) {m : ℕ}
local notation "G" => PresentedGroup (Set.singleton (s ^ m))
local notation "gen" => (PresentedGroup.of : LargePowerFreeSubgroupGenerator → G)
-- Layer triage:
-- `source-facing`: the two-generator one-relator group `G = (a, b; s ^ m)` with `1 < m`, together
-- with the hypothesis that the relator root `s` is not conjugate to any power of `a` or of `b`,
-- and the conclusion that the pair `a, b ^ n` is eventually a basis for the subgroup it
-- generates.
-- `core/canonical`: `PresentedGroup (Set.singleton (s ^ m))`
-- for the one-relator quotient, `IsConj` for conjugacy in the ambient free group, and
-- `IsFreeGroupBasis` for the textbook basis claim inside the generated subgroup.
-- `bridge/view`: the textbook generators `a` and `b` are represented by the constructors of
-- `LargePowerFreeSubgroupGenerator`, and their images in the one-relator quotient are the
-- canonical elements `gen .a` and `gen .b`.
-- Domain sampling:
-- 1. `PresentedGroup` is the canonical owner for one-relator groups in this chapter.
-- 2. Because this proposition works directly in that canonical quotient, the owner-side generator
-- map is `PresentedGroup.of` itself rather than the later bridge API
-- `GroupPresentation.generatorImage` for an arbitrary chosen presentation equivalence.
-- 3. `IsConj` is mathlib's owner relation for conjugacy in a group.
-- 4. `IsFreeGroupBasis` is the project's source-faithful basis predicate for a subset of a group.
-- Primitive vs. derived:
-- the primitive public data are the relator root `s`, the exponent `m`, and the non-conjugacy
-- hypotheses excluding powers of `a` and of `b`; the subgroup generated by the images of `a` and
-- `b ^ n` is derived canonically from those elements.
theorem exists_threshold_a_and_bpow_isFreeGroupBasis
(s : FreeGroup LargePowerFreeSubgroupGenerator) {m : ℕ} (hm : 1 < m)
(hsa : ∀ k : ℤ, ¬ IsConj s (FreeGroup.of a ^ k))
(hsb : ∀ k : ℤ, ¬ IsConj s (FreeGroup.of b ^ k)) :
∃ N : ℕ,
∀ n : ℕ, N ≤ n →
let Y : Set G := {gen a, gen b ^ n}
IsFreeGroupBasis {g : Subgroup.closure Y | (g : G) ∈ Y}Proposition 2.5.31
Lean contributors (project-level attribution): Zichen Wang.
Proposition 2-5-31: a one-relator group on at least three generators is SQ-universal.
universe u v w
-- Layer triage:
-- `source-facing`: a one-relator group on generators `X` with defining relator `r`, together with
-- the hypothesis that `X` has cardinality at least three.
-- `core/canonical`: `PresentedGroup (Set.singleton r)` for the one-relator owner,
-- `Cardinal.mk X` for the cardinality lower bound, `Subgroup G` for subgroup data, and quotient
-- groups `S ⧸ N`.
-- `bridge/view`: a chosen equivalence `PresentedGroup (Set.singleton r) ≃* G` transports
-- the owner-level `SQ`-universality statement to an arbitrary ambient group `G`.
-- Domain sampling:
-- 1. `PresentedGroup (Set.singleton r)` is the chapter's canonical owner for a group with
-- generators `X` and a single defining relator `r`.
-- 2. `Cardinal.mk X` is the universe-stable way to encode “at least three generators”.
-- 3. `Subgroup G` and `S ⧸ N` are the canonical mathlib owners for subgroups and quotient groups.
-- 4. Definition `2-1-1` uses `PresentedGroup R ≃* G` directly as presentation data, so a chosen
-- equivalence belongs at the bridge layer rather than as primitive owner data for this item.
-- Primitive vs. derived:
-- the primitive owner-level data are only the relator `r` and the lower bound on the cardinality
-- of the generator type; `SQ`-universality is the derived property of admitting every countable
-- group as a subquotient, and invariance under multiplicative equivalence supplies the separate
-- bridge theorem for arbitrary isomorphic ambient groups.
variable {X : Type v} (r : FreeGroup X)
local notation "Q" => PresentedGroup (Set.singleton r)
-- Proof sketch: apply the classical Magnus--Lyndon theorem that a one-relator group with at least
-- three generators is `SQ`-universal directly to the canonical owner `Q`.
theorem isSQUniversal_of_three_generator_one_relator_group (hX : 3 ≤ Cardinal.mk X) :
IsSQUniversal Q2.6 — Magnus’ Treatment of One-Relator Groups
Theorem 2.6.1
Lean contributors (project-level attribution): Zichen Wang.
Theorem 2-6-1: if r is a cyclically reduced relator in the free group on X, and Y ⊆ X omits a generator x that occurs in r, then in the one-relator quotient (X; r) the images of the generators from Y remain distinct and form a free basis of the subgroup they generate. This is the Freiheitssatz.
universe u
variable {X : Type u}
variable (r : FreeGroup X)
local notation "basis" => FreeGroupBasis.ofFreeGroup X
local notation "G" => PresentedGroup (Set.singleton r)
local notation "gen" => (PresentedGroup.of : X → G)
-- Layer triage:
-- `source-facing`: Magnus's Freiheitssatz for the one-relator quotient `G = (X; r)`, a subset
-- `Y ⊆ X` omitting a generator `x` that occurs in the cyclically reduced relator `r`, and the
-- conclusion that the images of `Y` in `G` stay distinct and form a free basis of the subgroup
-- they generate.
-- `core/canonical`: `FreeGroupBasis.ofFreeGroup X`, `PresentedGroup (Set.singleton r)`,
-- `PresentedGroup.of`, `Subgroup.closure`, and `IsFreeGroupBasis`.
-- `bridge/view`: `basisLetterOccurs basis x r` is the established occurrence predicate for a
-- basis generator in a free-group element, and the subgroup-basis conclusion is expressed in the
-- canonical subset form used by `closure_preimage_isFreeGroupBasis_of_bijOn`.
--
-- Domain sampling:
-- 1. `FreeGroupBasis.ofFreeGroup X` is the owner basis of the ambient free group `FreeGroup X`.
-- 2. `basisLetterOccurs` from Proposition `1-7-4` is the chapter's canonical bridge from the
-- basis owner to the source phrase “the generator `x` occurs in `r`”.
-- 3. `PresentedGroup (Set.singleton r)` together with `PresentedGroup.of` is the canonical owner
-- abstraction for the one-relator quotient `(X; r)`.
-- 4. `FreeGroup.map`, `FreeGroup.range_lift_eq_closure`, and `MulEquiv.ofBijective` are the
-- canonical owner-side APIs for embedding the free group on `Y` into `FreeGroup X`, identifying
-- its image subgroup in the quotient, and transporting the canonical free basis along the
-- resulting equivalence.
--
-- Primitive vs. derived:
-- the primitive source data are the relator `r`, the subset `Y`, the omitted generator `x`, and
-- the cyclic-reduction and occurrence hypotheses on `r`. The image subset `gen '' Y`, the
-- subgroup it generates in `G`, and the corresponding subtype-level basis assertion are derived
-- owner-side objects, so the theorem states them directly rather than through a parallel wrapper.
-- Proof sketch: this is Magnus's Freiheitssatz. One proves first that every nontrivial element of
-- the singleton normal closure of a cyclically reduced relator still contains each basis letter
-- occurring in that relator. Applying this to a subset `Y` omitting such a letter `x` shows that
-- no nontrivial reduced word in the images of `Y` can become trivial in the one-relator quotient,
-- so those images remain distinct and satisfy the universal property of a free basis for the
-- subgroup they generate.
theorem freiheitssatz_injOn_presentedGroup_of_and_isFreeGroupBasis
(Y : Set X) {x : X} (hr : FreeGroup.IsCyclicallyReduced r.toWord)
(hx : basisLetterOccurs basis x r)
(hxY : x ∉ Y) :
Set.InjOn gen Y ∧
IsFreeGroupBasis {g : Subgroup.closure (gen '' Y) | (g : G) ∈ gen '' Y}Theorem 2.6.2
Lean contributors (project-level attribution): Zichen Wang.
Theorem 2-6-2: this item is Magnus's proof of formula (5.8), namely that if two elements of a free group have the same singleton normal closure, then one is conjugate to the other or to its inverse. Since this textbook entry is proof text rather than a new independent construction, the file keeps only a direct recall of the chapter's canonical owner theorem instead of restating its full type.
#check conjugate_or_conjugate_inv_of_normalClosure_eq