Chapter 01 — Free Groups and Their Subgroups

Proofs omitted. Hover over highlighted terms to see their Lean types.

1.1 — Introduction

Definition 1.1.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-1-1: A subset X of a group F is a basis of a free group structure on F when every function from X to any group extends uniquely to a homomorphism from F.

universe u v -- Declarations for this item will be appended below by the statement pipeline. variable {F : Type u} [Group F] {X : Set F} -- Layer triage: -- `source-facing`: the textbook subset-style universal property for a basis of a free group. -- `core/canonical`: `FreeGroupBasis X F` is the owner abstraction for a free group with chosen -- basis indexed by `X`. -- `bridge/view`: the inclusion `Subtype.val : X → F` identifies the source subset with that owner -- basis data. -- -- Domain sampling: -- 1. `FreeGroupBasis.ofUniqueLift` is the canonical owner constructor from a unique-extension -- universal property. -- 2. `FreeGroupBasis.isFreeGroup` is the canonical owner theorem that a chosen basis makes the -- ambient group free. -- 3. `FreeGroupBasis.lift` and `FreeGroupBasis.ext_hom` are the owner APIs behind the reverse -- bridge from a chosen basis to the textbook subset property. -- -- Primitive vs. derived: -- the primitive source data are only the subset `X` and its unique-extension universal property. -- The chosen owner-side basis and the ambient `IsFreeGroup F` instance are derived from that -- source-facing predicate. def IsFreeGroupBasis (X : Set F) : Prop := ∀ {H : Type u} [Group H] (φ : X → H), ∃! φStar : F →* H, ∀ x : X, φStar x.1 = φ x

Proposition 1.1.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-1-2: If X₁ and X₂ are bases of the free groups F₁ and F₂, then F₁ and F₂ are isomorphic if and only if X₁ and X₂ have the same cardinality.

universe u open scoped Cardinal -- Declarations for this item will be appended below by the statement pipeline. -- Layer triage: -- `source-facing`: the subset-style basis hypotheses `IsFreeGroupBasis X₁` and -- `IsFreeGroupBasis X₂`. -- `core/canonical`: `FreeGroupBasis ι F` is the owner abstraction for a group with a chosen free -- basis. -- `bridge/view`: `FreeGroupBasis.ofUniqueLift X Subtype.val` turns the textbook subset universal -- property into the owner basis data. -- -- Domain sampling: -- 1. `FreeGroupBasis.ofUniqueLift` is the canonical bridge from the source universal property to a -- chosen basis. -- 2. `FreeGroupBasis.map` transports a chosen basis across a group isomorphism. -- 3. `FreeGroupBasis.reindex` transports a chosen basis across an equivalence of indexing types. -- 4. `FreeGroupBasis.cardinal_eq` is the chapter owner theorem that any two bases of the same -- free group have the same cardinality. -- -- Primitive vs. derived: -- the primitive source data are only the two subset-style basis hypotheses. The chosen owner-side -- bases arise canonically from `FreeGroupBasis.ofUniqueLift`, and the group isomorphism in the -- reverse direction is derived by reindexing one chosen basis along an equivalence of the index -- types. theorem free_group_mulEquiv_iff_basis_cardinal_eq {F₁ : Type u} {F₂ : Type u} [Group F₁] [Group F₂] {X₁ : Set F₁} {X₂ : Set F₂} (hX₁ : IsFreeGroupBasis X₁) (hX₂ : IsFreeGroupBasis X₂) : Nonempty (F₁ ≃* F₂) ↔ #X₁ = #X₂

Corollary 1.1.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-1-3: Any two bases of the same free group have the same cardinality. This common cardinality is the rank of the free group.

universe u v w open scoped Cardinal -- Declarations for this item will be appended below by the statement pipeline. theorem FreeGroupBasis.cardinal_eq {F : Type u} [Group F] {ι : Type v} {κ : Type w} (b₁ : FreeGroupBasis ι F) (b₂ : FreeGroupBasis κ F) : Cardinal.lift.{w} #ι = Cardinal.lift.{v} #κ

Proposition 1.1.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-1-4: if a group G is generated by a subset S, then G is canonically isomorphic to the quotient of the free group on S by the kernel of the canonical lift.

universe u open QuotientGroup variable {G : Type u} [Group G] variable (S : Set G) -- Layer triage: -- `source-facing`: a group `G`, a subset `S ⊆ G`, the hypothesis that `S` generates `G`, and the -- resulting quotient description of `G`. -- `core/canonical`: the homomorphism `FreeGroup.lift (Subtype.val : S → G)`, its kernel, and the -- first-isomorphism owner theorem `QuotientGroup.quotientKerEquivOfSurjective`. -- `bridge/view`: the generating hypothesis is converted into surjectivity of the canonical lift by -- `FreeGroup.closure_eq_range`, and the textbook quotient description is then exactly the kernel -- quotient supplied by the owner theorem. -- -- Domain sampling: -- 1. `FreeGroup.lift` is the canonical map out of the free group determined by the generator -- function `Subtype.val : S → G`. -- 2. `FreeGroup.closure_eq_range` identifies the subgroup generated by `S` with the range of that -- canonical lift. -- 3. `MonoidHom.range_eq_top` is the owner-level bridge from a top-range statement to -- surjectivity. -- 4. `QuotientGroup.quotientKerEquivOfSurjective` is the canonical first-isomorphism equivalence. -- -- Primitive vs. derived: -- the primitive source data are only `S` and the hypothesis `Subgroup.closure S = ⊤`; -- surjectivity of the canonical lift and the quotient equivalence are derived API. noncomputable def quotient_freeGroup_of_generating_set (hS : Subgroup.closure S = (⊤ : Subgroup G)) : (FreeGroup S ⧸ (FreeGroup.lift (Subtype.val : S → G)).ker) ≃* G := quotientKerEquivOfSurjective (FreeGroup.lift (Subtype.val : S → G)) (lift_subtype_surjective S hS)

Definition 1.1.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-1-5: a projective group is a projective object of GrpCat, equivalently a group whose homomorphisms lift along surjective homomorphisms.

universe u open CategoryTheory open CategoryTheory.Projective #check (Projective : GrpCat → Prop)

Definition 1.1.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-1-6: a subgroup is a retract of G exactly when its inclusion is split.

universe u variable {G : Type u} [Group G] open CategoryTheory namespace Subgroup theorem subtype_isSplitMono_iff_exists_leftInverse (S : Subgroup G) : IsSplitMono (GrpCat.ofHom S.subtype) ↔ ∃ ρ : G →* S, Function.LeftInverse ρ S.subtype

Proposition 1.1.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-1-7: A group is projective exactly when it is isomorphic to a retract subgroup of some free group.

universe u open CategoryTheory open CategoryTheory.Projective theorem projective_group_iff_isomorphic_to_retract_of_free_group {P : Type u} [Group P] : Projective (GrpCat.of P) ↔ ∃ F : GrpCat.{u}, IsFreeGroup F ∧ ∃ R : Subgroup F, ∃ _ : P ≃* R, IsSplitMono (GrpCat.ofHom R.subtype)

Corollary 1.1.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-1-8: A group is projective exactly when it is free.

universe u open CategoryTheory theorem projective_group_iff_free_group {G : Type u} [Group G] : Projective (GrpCat.of G) ↔ IsFreeGroup G

Proposition 1.1.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-1-9: the canonical free group on X has the basis on the textbook generator-image subset Set.range (FreeGroup.of : X → FreeGroup X), obtained by reindexing the standard basis FreeGroupBasis.ofFreeGroup X along its range.

universe u open scoped Cardinal -- Layer triage: -- `source-facing`: the image in `FreeGroup X` of the canonical generators `FreeGroup.of x`. -- `core/canonical`: the owner basis `FreeGroupBasis.ofFreeGroup X`. -- `bridge/view`: `FreeGroupBasis.reindexRange`, which reindexes that owner basis by its image -- subset in the ambient group. -- -- Domain sampling: -- 1. `FreeGroupBasis.ofFreeGroup X` is the canonical owner basis on `FreeGroup X`. -- 2. `FreeGroupBasis.reindexRange` is the chapter owner bridge from a basis to its image subset. -- 3. `FreeGroupBasis.reindexRange_apply` is the companion pointwise lemma for that bridge. -- -- Primitive vs. derived: -- the only primitive data here are the canonical basis `FreeGroupBasis.ofFreeGroup X` and its -- generator map `FreeGroup.of`. The basis indexed by the generator-image subset is derived -- canonically by `reindexRange`, so this file does not introduce a parallel owner declaration. variable (X : Type u) #check (show FreeGroupBasis (Set.range (FreeGroup.of : X → FreeGroup X)) (FreeGroup X) from (FreeGroupBasis.ofFreeGroup X).reindexRange)

Corollary 1.1.10

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-1-10: For any set X, the canonical generators of FreeGroup X form a basis of the free group on X.

universe u theorem free_group_on_has_basis (X : Type u) : IsFreeGroupBasis (Set.range (FreeGroup.of : X → FreeGroup X))

Proposition 1.1.11

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-1-11: if a homomorphism sends S bijectively onto a free basis X, then the subgroup of G generated by S is free with basis given by the corresponding subset of Subgroup.closure S.

universe u variable {G : Type u} [Group G] variable {F : Type u} [Group F] {S : Set G} {X : Set F} -- Layer triage: -- `source-facing`: a subset `S ⊆ G`, a basis subset `X ⊆ F`, and a homomorphism `φ : G →* F` -- that restricts to a bijection `S ≃ X`. -- `core/canonical`: `FreeGroupBasis X F` and -- `FreeGroupBasis {x : Subgroup.closure S | (x : G) ∈ S} (Subgroup.closure S)` are the owner -- basis objects, while `IsFreeGroupBasis` is the chapter's subset-style bridge. -- `bridge/view`: Proposition `1-1-11` transports the owner basis on `X` across the subtype -- equivalence induced by `hφS`, then reads the result back on the generated subgroup via the -- inclusion `{x : Subgroup.closure S | (x : G) ∈ S} → Subgroup.closure S`. -- -- Domain sampling: -- 1. `FreeGroupBasis.ofUniqueLift` from Definition `1-1-1` is the owner bridge from the textbook -- subset universal property to a chosen basis object. -- 2. `FreeGroupBasis.reindex` is the canonical owner transport along the subtype equivalence -- induced by the bijection `S ≃ X`. -- 3. `FreeGroupBasis.map` is the owner transport along the induced isomorphism between -- `Subgroup.closure S` and `F`. -- 4. `FreeGroupBasis.isFreeGroupBasis` turns the resulting owner basis back into the -- subset-style conclusion stated below. -- -- Primitive vs. derived: -- the primitive source data are `φ`, the basis witness `hX`, and the bijection witness `hφS`. -- The subgroup `Subgroup.closure S` and the subtype basis -- `{x : Subgroup.closure S | (x : G) ∈ S}` are derived owner-side objects. theorem closure_preimage_isFreeGroupBasis_of_bijOn (φ : G →* F) (hX : IsFreeGroupBasis X) (hφS : Set.BijOn φ S X) : IsFreeGroupBasis {x : Subgroup.closure S | (x : G) ∈ S}

Proposition 1.1.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-1-12, owner form: the subset of Subgroup.closure X cut out by X is a free basis exactly when the canonical homomorphism from the free group on X into G is injective.

universe u open FreeGroup variable {G : Type u} [Group G] theorem closure_preimage_isFreeGroupBasis_iff_injective_lift (X : Set G) : IsFreeGroupBasis {x : Subgroup.closure X | (x : G) ∈ X} ↔ Function.Injective (FreeGroup.lift (Subtype.val : X → G))

1.2 — Nielsen’s Method

Definition 1.2.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-2-1: an elementary Nielsen move on a finite vector of group elements is one of the three operations (T1), (T2), or (T3): invert one entry, replace one entry by its product with a distinct entry, or delete an entry equal to 1.

universe u variable {G : Type u} [Group G] def elementary_nielsen_move (U V : List G) : Prop := invert_elementary_nielsen_move U V ∨ multiply_elementary_nielsen_move U V ∨ delete_elementary_nielsen_move U V

Proposition 1.2.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-2: if a finite list U is carried into V by a Nielsen transformation, then the subgroup Gp(U) generated by the entries of U equals the subgroup Gp(V) generated by the entries of V.

universe u variable {G : Type u} [Group G] theorem generated_subgroup_eq_of_nielsen_transforms_to {U V : List G} (hUV : nielsen_transforms_to U V) : Subgroup.closure (Set.range U.get) = Subgroup.closure (Set.range V.get)

Definition 1.2.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

The symmetrization U^{±1} of a set of group elements.

universe u open scoped Pointwise namespace Set def symmetrization {α : Type*} [Group α] (U : Set α) : Set α := U ∪ U⁻¹

Proposition 1.2.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-4: Every finite list of words in a free group can be carried by a Nielsen transformation to an N-reduced list.

universe u variable {X : Type u} [DecidableEq X] theorem exists_nielsen_transform_to_n_reduced (U : List (FreeGroup X)) : ∃ V, nielsen_transforms_to U V ∧ FreeGroup.IsNReduced (Set.range V.get)

Proposition 1.2.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-5: if U satisfies Nielsen's conditions (N0) through (N2), then one can associate to each u ∈ U^{±1} a prefix word a u and a nontrivial middle segment m u whose letters survive in reduced products with no adjacent inverse cancellation.

universe u open FreeGroup open scoped Pointwise Symmetrization variable {X : Type u} [DecidableEq X] namespace FreeGroup.IsNReduced variable {U : Set (FreeGroup X)} local notation "mk" => FreeGroup.mk local notation "NoCancellation" => List.IsChain (fun u v : FreeGroup X ↦ u * v ≠ 1) theorem exists_prefix_middle_segments (hU : IsNReduced U) : ∃ a m : FreeGroup X → List (X × Bool), (∀ ⦃u : FreeGroup X⦄, u ∈ U^{±1} → m u ≠ []) ∧ (∀ ⦃u : FreeGroup X⦄, u ∈ U^{±1} → u.toWord = a u ++ m u ++ invRev (a u⁻¹)) ∧ ∀ (s t : List (FreeGroup X)) (u : FreeGroup X), (∀ v ∈ s ++ u :: t, v ∈ U^{±1}) → NoCancellation (s ++ u :: t) → (s ++ u :: t).prod.toWord = ((s.prod * mk (a u)).toWord ++ m u ++ (mk (invRev (a u⁻¹)) * t.prod).toWord)

Corollary 1.2.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-2-6: If U satisfies (N0) through (N2), then any product w = u₁ ... u_t with letters in U^{±1} and no adjacent inverse cancellation has reduced length at least t.

universe u open FreeGroup open scoped Pointwise Symmetrization variable {X : Type u} [DecidableEq X] namespace FreeGroup.IsNReduced variable {U : Set (FreeGroup X)} theorem norm_list_prod_ge_length (hU : IsNReduced U) (w : List (FreeGroup X)) (hwU : ∀ u ∈ w, u ∈ U^{±1}) (hchain : List.IsChain (fun u v ↦ u * v ≠ 1) w) : w.length ≤ w.prod.norm

Proposition 1.2.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-7: if a subset U of a free group satisfies Nielsen's conditions (N0) through (N2), then the subgroup Gp(U) = Subgroup.closure U is free with basis given by the elements of U viewed inside Subgroup.closure U.

universe u open FreeGroup variable {X : Type u} [DecidableEq X] theorem closure_preimage_isFreeGroupBasis_of_isNReduced (U : Set (FreeGroup X)) (hU : FreeGroup.IsNReduced U) : IsFreeGroupBasis {x : Subgroup.closure U | (x : FreeGroup X) ∈ U}

Proposition 1.2.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-8: every finitely generated subgroup of a free group is itself free. This source-facing item is a specialization of the canonical Nielsen-Schreier owner theorem subgroupIsFreeOfIsFree; finite generation is not primitive data for the freeness conclusion, so the file keeps a direct recall instead of a weaker local wrapper.

#check subgroupIsFreeOfIsFree

Proposition 1.2.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-9 (1): if a free group F has a basis indexed by Fin n, then any finite generating set of F has at least n elements.

universe u open scoped Cardinal variable {F : Type u} [Group F] -- Primary domain: finite-rank free groups and finite generating sets. -- `source-facing`: a finite generating subset of a free group with chosen finite basis. -- `core/canonical`: `FreeGroupBasis ι F`, `Group.rank`, and `IsFreeGroupBasis`. -- `bridge/view`: a finite generating set `U : Finset F` is recorded by -- `Subgroup.closure (↑U : Set F) = ⊤`. -- -- Domain sampling: -- 1. `FreeGroupBasis.cardinal_eq` is the chapter owner theorem equating the cardinalities of two -- free bases of the same group. -- 2. `Subgroup.rank_closure_finset_le_card` is mathlib's owner inequality bounding the rank of a -- finitely generated subgroup by the size of a chosen finite generating set. -- 3. `Group.rank` is the canonical owner for finite generation rank, so finite-generator -- inequalities should pass through it rather than through ad hoc local wrapper data. -- 4. `IsFreeGroupBasis` is the chapter's source-facing owner for “this displayed subset itself is -- a basis”. -- -- Primitive vs. derived: -- the primitive public data are a chosen finite basis `basis : FreeGroupBasis ι F` and a finite -- subset `U : Finset F`. The rank bound and the criterion that `U` itself is a basis are derived -- API and belong at the owner level; the specialized `Fin n` formulations below are source-facing -- wrappers around those owner declarations. variable {n : ℕ} theorem rank_le_card_of_generating_finset (basis : FreeGroupBasis (Fin n) F) (U : Finset F) (hgen : Subgroup.closure (U : Set F) = ⊤) : n ≤ U.card

Proposition 1.2.10

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-10: for an N-reduced subset U of the free group on X, the basis generators and inverse basis generators lying in Gp(U) = Subgroup.closure U are exactly the elements of U^{±1} that are basis generators or inverse basis generators.

universe u open FreeGroup open scoped Pointwise Symmetrization variable {X : Type u} [DecidableEq X] local notation "basis" => FreeGroupBasis.ofFreeGroup X local notation "basisSet" => Set.range basis theorem free_group_generator_symmetrization_inter_closure_eq (U : Set (FreeGroup X)) (hU : FreeGroup.IsNReduced U) : (basisSet^{±1} ∩ (Subgroup.closure U : Set (FreeGroup X))) = (basisSet^{±1} ∩ U^{±1})

Proposition 1.2.11

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-11: if a subgroup G of a free group is strictly totally ordered by a relation refining reduced-word length, then the elements not generated by their predecessors form an N-reduced subset of the ambient free group.

universe u open FreeGroup variable {X : Type u} variable (G : Subgroup (FreeGroup X)) (r : G → G → Prop) theorem predecessorIndependentSet_isNReduced [DecidableEq X] [IsStrictTotalOrder G r] (h_length : ∀ ⦃g h : G⦄, norm (g : FreeGroup X) < norm (h : FreeGroup X) → r g h) : FreeGroup.IsNReduced (predecessorIndependentSubset G r)

Proposition 1.2.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-12: if a subgroup G of a free group is well ordered by a relation r refining the free-group word length, then the elements of G not generated by their predecessors form a free basis of G.

universe u variable {X : Type u} [DecidableEq X] theorem predecessorIndependentSet_isFreeGroupBasis (G : Subgroup (FreeGroup X)) (r : G → G → Prop) [IsWellOrder G r] (h_length : ∀ ⦃g h : G⦄, FreeGroup.norm (g : FreeGroup X) < FreeGroup.norm (h : FreeGroup X) → r g h) : IsFreeGroupBasis (predecessorIndependentSet G r)

Proposition 1.2.13

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-13: every subgroup of a free group is free. This source-facing item is exactly the canonical Nielsen-Schreier owner theorem already available in mathlib, so the file keeps a direct recall of subgroupIsFreeOfIsFree rather than introducing any parallel local wrapper.

universe u #check (subgroupIsFreeOfIsFree : ∀ {G : Type u} [Group G] [IsFreeGroup G] (H : Subgroup G), IsFreeGroup H)

Proposition 1.2.14

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-14: a surjective homomorphism from a finitely generated free group onto a free group splits the domain as free factors F₁ * F₂, with the restriction to F₁ bijective and the restriction to F₂ trivial. The source's finite-rank hypothesis is redundant for this owner-level splitting statement, so it is not exposed in the refined API. Unpacking Subgroup.AreFreeFactors F₁ F₂ recovers the textbook basis partition Z = Z₁ ⊔ Z₂.

universe u variable {F G : Type u} [Group F] [IsFreeGroup F] [Group G] [IsFreeGroup G] theorem exists_free_factor_decomposition_of_surjective_to_free (φ : F →* G) (hφ : Function.Surjective φ) : ∃ F₁ F₂ : Subgroup F, Subgroup.AreFreeFactors F₁ F₂ ∧ Function.Bijective (φ.comp F₁.subtype) ∧ φ.comp F₂.subtype = 1

Proposition 1.2.15

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-15: if w is a product of factors from U^{±1} with no adjacent inverse cancellation and U is N-reduced, then the reduced length of the product is at least the number of factors and dominates the reduced length of every factor.

universe u open FreeGroup open scoped Pointwise Symmetrization variable {α : Type u} [DecidableEq α] theorem nielsen_reduced_prod_norm_bounds {U : Set (FreeGroup α)} (hU : FreeGroup.IsNReduced U) (w : List (FreeGroup α)) (hwU : ∀ u ∈ w, u ∈ U^{±1}) (hchain : List.IsChain (fun u v ↦ u * v ≠ 1) w) : w.length ≤ norm w.prod ∧ ∀ u ∈ w, norm u ≤ norm w.prod

Proposition 1.2.16

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-16: a free group has solvable conjugacy problem, equivalently conjugacy is a decidable relation on F.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] noncomputable instance decidableIsConjOfIsFreeGroup : DecidableRel (IsConj : F → F → Prop)

Proposition 1.2.17

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-17 on the canonical free-group model: if the reduced word of w is cyclically reduced, then every power is represented by the concatenation of the expected number of copies of that reduced word.

universe u v open FreeGroup namespace FreeGroup variable {α : Type u} theorem toWord_pow_of_isCyclicallyReduced (w : FreeGroup α) (hw : IsCyclicallyReduced w.toWord) (n : ℕ) : toWord (w ^ n) = (List.replicate n w.toWord).flatten

Proposition 1.2.18

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-18: a free group is torsion free.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] instance : IsMulTorsionFree F

Proposition 1.2.19

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-19: if nonzero powers of a and b commute in a free group, then a and b are powers of a common element.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem exists_common_zpowers_generator_of_commute_zpow (a b : F) (m n : ℤ) (hm : m ≠ 0) (hn : n ≠ 0) (h : Commute (a ^ m) (b ^ n)) : ∃ c : F, a ∈ Subgroup.zpowers c ∧ b ∈ Subgroup.zpowers c

Proposition 1.2.20

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-20: in a free group, commuting defines an equivalence relation on the nonidentity elements.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem commute_equivalence_on_nontrivial_elements : Equivalence (fun a b : {x : F // x ≠ 1} ↦ Commute a.1 b.1)

Proposition 1.2.21

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-21: the normalizer of the cyclic subgroup generated by a nontrivial element of a free group is cyclic.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem normalizer_zpowers_isCyclic (w : F) (hw : w ≠ 1) : IsCyclic (Subgroup.normalizer (Subgroup.zpowers w : Set F))

Proposition 1.2.22

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-22 (2): given two elements of a free group, it is decidable whether they commute.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] noncomputable instance decidableCommuteOfIsFreeGroup : DecidableRel (Commute : F → F → Prop)

Proposition 1.2.23

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-23: for a finite subset U of a free group, membership in the subgroup Gp(U) = Subgroup.closure (U : Set F) is decidable. The public API stays centered on the source-facing subgroup-membership problem. Its implementation reuses the chapter/mathlib owner abstractions FreeGroup.IsNReduced, exists_nielsen_transform_to_n_reduced, generated_subgroup_eq_of_nielsen_transforms_to, IsFreeGroup.toFreeGroup, Subgroup.mem_map_iff_mem, and MonoidHom.map_closure. After transporting to the canonical free-group model, it first replaces the finite generating set by an Nielsen-equivalent N-reduced list and only then invokes the internal bounded search justified by the chapter's Nielsen norm estimates.

universe u open FreeGroup variable {F : Type u} [Group F] [IsFreeGroup F] @[reducible] noncomputable def generated_subgroup_membership_decidable (U : Finset F) : DecidablePred (fun x : F ↦ x ∈ Subgroup.closure (U : Set F))

Proposition 1.2.24

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-24: in a free group, it is decidable whether the subgroup generated by U is conjugate into the subgroup generated by V. The public statement keeps the source-facing subgroup-conjugation problem. Its owner-side implementation searches basis tuples for the finitely generated subgroup Gp(U) and checks conjugacy on those tuples using the chapter's canonical common-conjugator owner exists_common_conjugator_decidable, while subgroup-membership side conditions are handled by generated_subgroup_membership_decidable. The search uses only the finitely many letters appearing in the finite input sets, so no ambient Group.FG hypothesis belongs in the public statement.

universe u v open FreeGroup open MulAction open scoped Pointwise namespace Proposition_1_2_24 variable {F : Type u} [Group F] [IsFreeGroup F] noncomputable def generated_subgroup_conjugate_into_decidable (U V : Finset F) : Decidable (∃ g : F, generated_subgroup_conjugate_into_by g U V)

Proposition 1.2.25

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-25 (1): in a free group, it is decidable whether one element conjugates each generated subgroup U i into the corresponding generated subgroup V i for a finite family. This public API keeps the source-facing family predicate. Its implementation searches finite tuple presentations of the finitely generated subgroups Gp(U i) and uses the chapter owner abstraction exists_common_conjugator_decidable to test whether one conjugator works for the concatenated tuple family. The search only uses letters that actually occur in the finite input subsets, so no ambient finite-rank hypothesis appears in the public statement. The companion bridge theorem exists_conjugator_for_generated_subgroup_family_le_iff_exists_smul_le identifies the proposition with the canonical diagonal ConjAct F action on the family of generated subgroups.

universe u open MulAction open Proposition_1_2_24 open scoped Pointwise -- Declarations for this item will be appended below by the statement pipeline. variable {F : Type u} [Group F] [IsFreeGroup F] {ι : Type*} [Fintype ι] noncomputable def exists_conjugator_for_generated_subgroup_family_le_decidable (U V : ι → Finset F) : Decidable (∃ g : F, ∀ i, generated_subgroup_conjugate_into_by g (U i) (V i))

Proposition 1.2.26

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-26: it is decidable whether two n-tuples admit a common conjugator. The public statement keeps the source-facing free-group decision problem. Its canonical owner is still the diagonal conjugation-action orbit relation on Fin n → F, exposed by the companion bridge theorem exists_common_conjugator_iff_orbitRel. The bounded-search construction is exposed owner-side through decidableRel_commonConjugatorOrbitRel, and this source-facing declaration is the corresponding bridge back to the textbook existential predicate.

universe u open FreeGroup open MulAction variable {F : Type u} [Group F] {n : ℕ} noncomputable def exists_common_conjugator_decidable [IsFreeGroup F] (u v : Fin n → F) : Decidable (∃ w : F, ∀ i, w⁻¹ * u i * w = v i) := decidable_of_iff (orbitRel (ConjAct F) (Fin n → F) v u) (exists_common_conjugator_iff_orbitRel u v)

Proposition 1.2.27

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-27: let basis : FreeGroupBasis ι F be a finite basis of the free group F, and let A be a nonempty subset of F contained in some free basis. Then F has a basis A ∪ B such that every element of B has basis-length bounded by the basis-length of some element of A. This is the source-faithful formulation of the statement that the longest element of B is no longer than the longest element of A.

universe u v namespace FreeGroupBasis variable {ι : Type v} {F : Type u} [Group F] [Finite ι] theorem exists_completion_with_length_bound (basis : FreeGroupBasis ι F) (A : Set F) (hA : A.Nonempty) (hpart : ∃ S : Set F, A ⊆ S ∧ IsFreeGroupBasis S) : ∃ B : Set F, IsFreeGroupBasis (A ∪ B) ∧ ∀ b ∈ B, ∃ a ∈ A, (basis.repr b).norm ≤ (basis.repr a).norm

Definition 1.2.28

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-2-28: The subgroups F₁ and F₂ are free factors of F, equivalently F is the free product F₁ * F₂, when there are generating sets X₁ and X₂ with Subgroup.closure X₁ = F₁, Subgroup.closure X₂ = F₂, X₁ ∩ X₂ = ∅, and X₁ ∪ X₂ a basis of F.

universe u variable {F : Type u} [Group F] open CategoryTheory namespace Subgroup def AreFreeFactors (F₁ F₂ : Subgroup F) : Prop := ∃ X₁ X₂ : Set F, closure X₁ = F₁ ∧ closure X₂ = F₂ ∧ Disjoint X₁ X₂ ∧ IsFreeGroupBasis (X₁ ∪ X₂)

Proposition 1.2.29

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-29, source-facing finite criterion: for a finite subset U of a finitely generated free group, the subgroup Gp(U) is a free factor exactly when either U is empty or, after replacing U by a bounded generating set for the same subgroup, one can complete it to a basis of the ambient group using only elements whose word lengths are bounded by the total basis-word length of U.

universe u v open FreeGroup open Proposition_1_2_29 variable {ι : Type v} {F : Type u} [Group F] variable (basis : FreeGroupBasis ι F) [Finite ι] theorem generated_subgroup_free_factor_iff_exists_bounded_completion (U : Finset F) : let m := U.sum fun u ↦ (basis.repr u).norm (∃ K : Subgroup F, (Subgroup.closure ↑U).AreFreeFactors K) ↔ U = ∅ ∨ ∃ W V : Finset F, Subgroup.closure ↑W = Subgroup.closure (↑U : Set F) ∧ IsFreeGroupBasis (↑(W ∪ V) : Set F) ∧ (∀ w ∈ W, (basis.repr w).norm ≤ m) ∧ ∀ v ∈ V, (basis.repr v).norm ≤ m

Proposition 1.2.30

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-2-30 on the canonical free-group model: if u and w do not commute, then there is an integer from which onward the reduced-word lengths of the conjugates w^{-m} * u * w^m form a strictly increasing sequence.

universe u v open FreeGroup variable {ι : Type v} {F : Type u} [Group F] namespace FreeGroup theorem exists_conjugate_power_tail_strictMono_norm_of_not_commute (u w : FreeGroup ι) (huw : ¬ Commute u w) : ∃ n : ℤ, StrictMono fun k : ℕ ↦ norm (w ^ (-(n + k : ℤ)) * u * w ^ (n + k : ℤ))

1.3 — Subgroups of Free Groups

Proposition 1.3.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-1: a free group of rank greater than 1 contains a subgroup that is not finitely generated, equivalently a free subgroup of infinite rank.

universe u variable {F : Type u} [Group F] variable [IsFreeGroup F] theorem exists_non_fg_subgroup_of_rank_gt_one (hRank : Nontrivial (IsFreeGroup.Generators F)) : ∃ H : Subgroup F, ¬ H.FG

Proposition 1.3.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-2: if each successor F (i + 1) is a subgroup of F i containing no element of any basis of F i, then every nontrivial element of F i has b-word length at least i + 1.

universe u v variable {G : Type u} [Group G] theorem wordLength_lower_bound_of_descending_subgroups_avoiding_bases (F : ℕ → Subgroup G) (hdesc : ∀ i, F (i + 1) ≤ F i) (havoid : ∀ i {w : F i}, IsPrimitiveElement w → (w : G) ∉ F (i + 1)) {ι : Type v} [DecidableEq ι] (b : FreeGroupBasis ι G) {i : ℕ} {w : F i} (hw : w ≠ 1) : i + 1 ≤ FreeGroup.norm (b.repr w)

Proposition 1.3.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-3: for a descending chain of subgroups of a free group, if each successor is a proper characteristic subgroup of its predecessor, then the intersection of the chain is trivial.

universe u open Subgroup variable {G : Type u} [Group G] variable {F : Type u} [Group F] [IsFreeGroup F] theorem iInf_eq_bot_of_descending_proper_characteristic_subgroups (FSeries : ℕ → Subgroup F) (hproper : ∀ i, FSeries (i + 1) < FSeries i) (hchar : ∀ i, ((FSeries (i + 1)).subgroupOf (FSeries i)).Characteristic) : (⨅ i, FSeries i) = ⊥

Proposition 1.3.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-4: the intersection of all terms in the derived series of a free group is trivial.

universe u open Subgroup variable {F : Type u} [Group F] [IsFreeGroup F] theorem iInf_derivedSeries_eq_bot_of_isFreeGroup : (⨅ n : ℕ, derivedSeries F n) = ⊥

Proposition 1.3.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-5: every surjective endomorphism of a finitely generated free group is bijective, so every finitely generated free group is Hopfian.

universe u variable {G : Type u} [Group G] variable {F : Type u} [Group F] [IsFreeGroup F] [Group.FG F] theorem surjective_endomorphism_bijective (φ : F →* F) (hφ : Function.Surjective φ) : Function.Bijective φ

Proposition 1.3.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-6 (Takahasi): an ascending chain of free subgroups of uniformly bounded finite rank in a free group eventually stabilizes.

universe u namespace Subgroup variable {F : Type u} [Group F] [IsFreeGroup F] variable (H : ℕ →o Subgroup F) theorem exists_stabilizing_index_of_bounded_rank (r : ℕ) (hfg : ∀ n, (H n).FG) (hrank : ∀ n, letI : Group.FG (H n) := group_fg_of_subgroup_fg (hfg n) Group.rank (H n) ≤ r) : ∃ N, ∀ n, N ≤ n → H n = H N

Proposition 1.3.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-7 (1): for a Schreier transversal T, two nontrivial generators γ(t₁x₁) and γ(t₂x₂) coincide only when the transversal elements and letters agree.

universe u open FreeGroup variable {X : Type u} [DecidableEq X] variable {H : Subgroup (FreeGroup X)} {T : H.RightTransversal} theorem schreierGenerator_eq_of_ne_one (hT : HasInitialSegments (T : Set (FreeGroup X))) {t₁ t₂ : ↥(T : Set (FreeGroup X))} {x₁ x₂ : X} (hγ : schreierGenerator T.2.toRightFun t₁ x₁ = schreierGenerator T.2.toRightFun t₂ x₂) (hγ_ne : schreierGenerator T.2.toRightFun t₁ x₁ ≠ 1) : t₁ = t₂ ∧ x₁ = x₂

Proposition 1.3.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-8: every subgroup of a free group is free. This source-facing item is exactly the canonical Nielsen-Schreier theorem already available in mathlib as subgroupIsFreeOfIsFree, so the file keeps a direct recall of that theorem rather than introducing a parallel local wrapper.

#check subgroupIsFreeOfIsFree

Proposition 1.3.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-9: a finite-index subgroup H of a finite-rank free group F satisfies the exact Schreier rank-index formula Group.rank H - 1 = H.index * (Group.rank F - 1).

universe u variable {F : Type u} [Group F] [IsFreeGroup F] [Group.FG F] theorem finiteIndex_subgroup_rank_sub_one_eq (H : Subgroup F) [H.FiniteIndex] : Group.rank H - 1 = H.index * (Group.rank F - 1)

Remark 1.3.10

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Remark 1-3-10: the Schreier rank-index formula from the preceding proposition has a geometric interpretation, and this interpretation is closely related to the Riemann-Hurwitz formula. This source item is a forward-looking prose remark rather than a standalone theorem. To keep the formalization source-faithful without inventing a surrogate proposition, the file keeps only a direct recall of the preceding chapter theorem that already states Schreier's rank-index formula in the canonical owner variables Group.rank and Subgroup.index.

#check finiteIndex_subgroup_rank_sub_one_eq

Proposition 1.3.11

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-11: if F is a free group, A is a finite subset of F, and H is a finitely generated subgroup of F disjoint from A, then there exists a finite-index subgroup G ≤ F that is still disjoint from A and in which H is a free factor.

universe u open CategoryTheory variable {F : Type u} [Group F] [IsFreeGroup F] variable (A : Finset F) (H : Subgroup F) theorem exists_finiteIndex_overgroup_disjoint_from_finset_with_free_factor (hfg : H.FG) (hA : Disjoint (A : Set F) (H : Set F)) : ∃ G : Subgroup F, G.FiniteIndex ∧ Disjoint (A : Set F) (G : Set F) ∧ H.IsFreeFactorOf G

Proposition 1.3.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-12: a finitely generated subgroup of a free group that contains a nontrivial normal subgroup of the ambient free group has finite index.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem finiteIndex_of_fg_of_contains_nontrivial_normal (H N : Subgroup F) (hfg : H.FG) (hN_le : N ≤ H) (hN_normal : N.Normal) (hN : N ≠ ⊥) : H.FiniteIndex

Proposition 1.3.13

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-13: every nontrivial finitely generated normal subgroup of a free group has finite index. Layer triage: - source-facing: a nontrivial finitely generated normal subgroup N : Subgroup F. - core/canonical: the subgroup owner Subgroup F together with the owner predicates Subgroup.FG, Subgroup.Normal, and Subgroup.FiniteIndex. - bridge/view: Proposition 1-3-13 is exactly the specialization H = N of Proposition 1-3-12, which already expresses the canonical owner theorem for a finitely generated subgroup containing a nontrivial normal subgroup. Domain sampling: 1. Subgroup.FG in Mathlib/GroupTheory/Finiteness is the owner predicate for finite generation of a subgroup. 2. Subgroup.fg_iff in Mathlib/GroupTheory/Finiteness shows that finite generation is derived from the canonical subgroup owner via closure of a finite set, not from extra packaged data. 3. Subgroup.FiniteIndex in Mathlib/GroupTheory/Index is the owner predicate for finite index, and finiteIndex_iff_finite_quotient is its standard quotient-level bridge. 4. finiteIndex_of_fg_of_contains_nontrivial_normal in Proposition 1-3-12 is the chapter owner theorem whose diagonal specialization H = N is exactly this proposition. Best owner abstraction: the public mathematics already lives at the canonical subgroup-owner level of Proposition 1-3-12; this proposition adds no new owner data beyond the diagonal specialization H = N. Primitive vs. derived: the primitive mathematical data are just the subgroup N and the owner predicates N.FG, N.Normal, and N ≠ ⊥; the finite-index conclusion is derived. Since Proposition 1-3-12 already consumes exactly those owner-level inputs after the canonical inclusion N ≤ N = le_rfl, keeping a separate local theorem would duplicate the API surface without adding mathematics. Accordingly, this file keeps only the exact diagonal recall term rather than a parallel local specialization theorem.

universe u #check (fun {F : Type u} [Group F] [IsFreeGroup F] (N : Subgroup F) (hfg : N.FG) (hN_normal : N.Normal) (hN : N ≠ ⊥) ↦ finiteIndex_of_fg_of_contains_nontrivial_normal N N hfg le_rfl hN_normal hN : ∀ {F : Type u} [Group F] [IsFreeGroup F] (N : Subgroup F), N.FG → N.Normal → N ≠ ⊥ → N.FiniteIndex)

Proposition 1.3.14

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-14: the intersection of two finitely generated subgroups of a free group is itself finitely generated.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem fg_inf_of_fg (H K : Subgroup F) (hH : H.FG) (hK : K.FG) : (H ⊓ K).FG

Proposition 1.3.15

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-15 (1): in the group <x, y | x⁻¹ y² x = y²>, the normal closure of x is a free subgroup of rank 2.

universe u open Subgroup -- Layer triage: -- `source-facing`: the one-relator group `<x, y | x⁻¹ y² x = y²>` together with the normal -- closures of the images of `x` and `z = xy`. -- `core/canonical`: `PresentedGroup`, `normalClosure`, `commutator`, and -- `FreeGroupBasis`. -- `bridge/view`: the distinguished elements `x`, `y`, and `z = xy` inside the presented group. -- Domain sampling: -- 1. `PresentedGroup R` is mathlib's owner abstraction for a group given by generators and -- relators. -- 2. `normalClosure S` is the canonical owner for the normal subgroup generated by a subset. -- 3. `commutator G` is the owner for the derived subgroup `[G, G]`. -- 4. `FreeGroupBasis ι H` is the canonical owner for an explicit free basis of a group. -- Primitive vs. derived: -- the primitive source data are the two generators and the single relator; the ambient presented -- group, the two normal closures, and the commutator subgroup are canonical constructions derived -- from those data. open CentralizingSquare theorem x_normalClosure_has_basis_fin_two : Nonempty (FreeGroupBasis (Fin 2) normalClosureX)

Proposition 1.3.16

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-16: a finitely generated subgroup of a free group that is contained in no overgroup of infinite rank has finite index.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem finiteIndex_of_all_overgroups_fg (H : Subgroup F) (hover : ∀ ⦃K : Subgroup F⦄, H ≤ K → K.FG) : H.FiniteIndex

Proposition 1.3.17

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-17: if H is a finite-index subgroup of a free group F of rank greater than 1, then any overgroup G of H with rank at least that of H must already equal H.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] [Group.FG F] theorem eq_of_le_of_rank_ge_of_finiteIndex_subgroup (hF_rank : 1 < Group.rank F) {H G : Subgroup F} [H.FiniteIndex] (hHG : H ≤ G) [Group.FG G] (h_rank : Group.rank H ≤ Group.rank G) : G = H

Proposition 1.3.18

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-18: a finitely generated subgroup of a free group that meets every nontrivial normal subgroup nontrivially has finite index.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem finiteIndex_of_fg_of_inf_ne_bot_with_every_nontrivial_normal (H : Subgroup F) (hfg : H.FG) (hinter : ∀ N : Subgroup F, N.Normal → N ≠ ⊥ → H ⊓ N ≠ ⊥) : H.FiniteIndex

Proposition 1.3.19

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-19: a finite-index subgroup of a free group has nontrivial intersection with every nontrivial subgroup.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem inf_ne_bot_of_finiteIndex_of_ne_bot (H K : Subgroup F) [H.FiniteIndex] (hK : K ≠ ⊥) : H ⊓ K ≠ ⊥

Proposition 1.3.20

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-20: for a subgroup H of the free group on X, if T is a minimal Schreier transversal for H, then the nontrivial Schreier generators γ(tx) form an N-reduced set. Together with the companion basis theorem above, this is the textbook statement that they form an N-reduced basis of H.

universe u open FreeGroup open QuotientGroup variable {X : Type u} [DecidableEq X] variable {H : Subgroup (FreeGroup X)} -- Layer triage: -- `source-facing`: the subgroup `H` together with the textbook Schreier generators `γ(tx)`. -- `core/canonical`: Proposition `1-3-7` already owns the free-basis statement for the subgroup -- generated by a Schreier transversal with initial segments. -- `bridge/view`: this theorem specializes that owner basis theorem to the ambient subgroup `H` -- by using the owner minimality predicate `T.IsMinimalSchreier` to obtain `HasInitialSegments` -- and the owner-level subgroup identity `T.closure_schreierGeneratorSet_eq`. -- Proof sketch: minimality gives the initial-segment property, so Proposition `1-3-7` supplies a -- free basis of the subgroup generated by the Schreier generators. The canonical bridge -- `T.closure_schreierGeneratorSet_eq` then identifies that generated subgroup with `H`. namespace Subgroup.RightTransversal theorem schreierGeneratorSet_isNReduced {T : H.RightTransversal} (hT : T.IsMinimalSchreier) : FreeGroup.IsNReduced (schreierGeneratorSet (T : Set (FreeGroup X)) T.2.toRightFun)

Proposition 1.3.21

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-21: a right transversal of a subgroup of a free group whose chosen representative in each right coset is minimal for a trichotomous relation compatible with word length is a minimal Schreier transversal in the sense of Proposition 1-3-20, hence in particular a Schreier transversal. For the textbook well-order criterion, the well-foundedness part is redundant in this implication.

universe u open FreeGroup open QuotientGroup variable {X : Type u} [DecidableEq X] variable (H : Subgroup (FreeGroup X)) variable {r : FreeGroup X → FreeGroup X → Prop} [Std.Trichotomous r] variable (T : H.RightTransversal) variable (h_length : ∀ ⦃w w' : FreeGroup X⦄, r w w' → norm w ≤ norm w') (hmin : ∀ ⦃t w : FreeGroup X⦄, t ∈ (T : Set (FreeGroup X)) → rightRel H t w → ¬ r w t) theorem minimal_rightTransversal_isMinimalSchreier (h_length : ∀ ⦃w w' : FreeGroup X⦄, r w w' → norm w ≤ norm w') (hmin : ∀ ⦃t w : FreeGroup X⦄, t ∈ (T : Set (FreeGroup X)) → rightRel H t w → ¬ r w t) : Subgroup.RightTransversal.IsMinimalSchreier T

Proposition 1.3.22

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-22: if U is an N-reduced basis of a subgroup H of the free group on X, and S chooses one isolated half from each balanced basis element as in the textbook construction, then the resulting set T = T₁ \ S underlies a Schreier right transversal for some subgroup G containing H as a free factor.

universe u open FreeGroup open Subgroup open scoped Pointwise Symmetrization variable {X : Type u} [DecidableEq X] theorem pruned_initial_half_segment_set_is_schreier_transversal_with_free_factor (H : Subgroup (FreeGroup X)) (U S : Set (FreeGroup X)) (hU : U ⊆ H) (hBasis : IsFreeGroupBasis {x : H | (x : FreeGroup X) ∈ U}) (hNReduced : FreeGroup.IsNReduced U) (hSelection : IsolatedPartSelection U S) : ∃ G : Subgroup (FreeGroup X), H.IsFreeFactorOf G ∧ ∃ T : G.RightTransversal, (T : Set (FreeGroup X)) = prunedInitialHalfSegmentSet U S ∧ HasInitialSegments (T : Set (FreeGroup X))

Proposition 1.3.23

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-3-23: any right transversal of G realizes the source Schreier-cardinality formula, and under the same Hall-Schreier hypotheses H has finite index in F exactly when that formula holds.

universe u v w variable {F : Type u} [Group F] variable {X : Type v} {U : Type w} variable [Finite X] [Finite U] variable {H G : Subgroup F} theorem finite_index_iff_schreier_cardinality_formula (basisX : FreeGroupBasis X F) (hX : 1 < Nat.card X) [G.FiniteIndex] (basisU : FreeGroupBasis U H) (hFreeFactor : H.IsFreeFactorOf G) (T : G.RightTransversal) : H.FiniteIndex ↔ (Nat.card X - 1) * Nat.card (T : Set F) = Nat.card U - 1

1.4 — Automorphisms of Free Groups

Proposition 1.4.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-1: the subgroup generated by the elementary Nielsen automorphisms is dense in Aut(F) for the pointwise topology on finite families, meaning that every automorphism can be matched on any prescribed finite family of elements.

universe u v variable {F : Type u} [Group F] {X : Type v} namespace FreeGroupBasis theorem exists_elementaryNielsenAutomorphism_eq_on_finite_family (basis : FreeGroupBasis X F) {ι : Type*} [Finite ι] (u : ι → F) (α : MulAut F) : ∃ β ∈ basis.elementaryNielsenAutomorphismSubgroup, ∀ i, β (u i) = α (u i)

Proposition 1.4.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-2: the elementary Nielsen subgroup for basis is exactly the subgroup of automorphisms moving only finitely many elements of that chosen basis.

universe u v variable {F : Type u} [Group F] {X : Type v} namespace FreeGroupBasis theorem elementaryNielsenAutomorphismSubgroup_eq_finiteMovedSubgroup (basis : FreeGroupBasis X F) : basis.elementaryNielsenAutomorphismSubgroup = basis.finiteMovedSubgroup

Remark 1.4.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Remark 1-4-3: if a free group has a countably infinite basis, then its full automorphism group is uncountable, while the subgroup Aut_f(F) attached to that basis is countable.

universe u v open FreeGroup variable {F : Type u} [Group F] {X : Type v} -- Layer triage: -- `source-facing`: the contrast between the cardinalities of `Aut(F)` and the subgroup -- `Aut_f(F)` attached to a countably infinite basis `basis : FreeGroupBasis X F`. -- `core/canonical`: `MulAut F`, the chosen-basis owner `FreeGroupBasis X F`, and the basis-owned -- finite-support subgroup `basis.finiteMovedSubgroup`. -- `bridge/view`: Proposition `1-4-2` identifies `Aut_f(F)` with that owner subgroup, while -- permutations of the basis index type transport through `basis.repr` into `MulAut F` for the -- uncountability argument. -- Domain sampling: -- 1. `FreeGroupBasis X F` in `Mathlib/GroupTheory/FreeGroup/IsFreeGroup` is the owner -- abstraction for a chosen free basis of `F`. -- 2. `MulAut F` is the canonical automorphism group of `F`. -- 3. `FreeGroupBasis.finiteMovedSubgroup` from Proposition `1-4-2` is the chapter owner for the -- finite-support subgroup on a chosen basis. -- 4. `elementaryNielsenAutomorphismSubgroup_eq_finiteMovedSubgroup` is the source-to-owner bridge -- identifying `Aut_f(F)` with that finite-support subgroup, and `basis.repr` together with -- `freeGroupCongr` gives the canonical permutation action used below. -- Primitive/derived split: -- the primitive public data are the ambient group `F` and an explicit basis -- `basis : FreeGroupBasis X F`; the finite-support subgroup `basis.finiteMovedSubgroup` and the -- source-facing subgroup `basis.elementaryNielsenAutomorphismSubgroup` are derived owner-level -- constructions, while infinitude and countability of `X` enter only in the cardinality theorems. variable [Countable X] theorem automorphism_group_cardinality_contrast (basis : FreeGroupBasis X F) [Infinite X] : Uncountable (MulAut F) ∧ Countable ↥(basis.elementaryNielsenAutomorphismSubgroup)

Proposition 1.4.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-4: if F is a free group of finite rank greater than 1, then Aut(F) is complete, meaning that its center is trivial and every automorphism of Aut(F) is inner.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] variable [Group.FG F] namespace MulAut theorem center_eq_bot_of_fg_and_rank_gt_one (h_rank : 1 < Group.rank F) : Subgroup.center (MulAut F) = ⊥

Proposition 1.4.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-5: for a finitely generated free group F, the natural map from Aut(F) to the automorphism group of its abelianization is surjective.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] [Group.FG F] theorem abelianization_surjective_of_fg : Function.Surjective (MulAut.abelianization F)

Proposition 1.4.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-6: if F is a free group of rank 2, then the kernel of the natural map from Aut(F) to the automorphism group of its abelianization is the subgroup of inner automorphisms. Via a basis of Abelianization F, the target identifies with GL(2, ℤ).

universe u variable {F : Type u} [Group F] [IsFreeGroup F] -- Primary domain: automorphisms of a rank-two free group and the induced action on its -- abelianization. -- Domain sampling: -- 1. `MulAut F` is the canonical owner abstraction for `Aut(F)`. -- 2. `MulAut.abelianization F` from Proposition `1-4-5` is the owner map to the automorphism -- group of the abelianization. -- 3. `MulAut.IA F` and `MulAut.innerAutomorphismSubgroup F` are the chapter owner subgroups for -- the kernel and the inner automorphisms. -- 4. `Group.rank` from `Mathlib/GroupTheory/Rank` is the intrinsic chapter owner for the source -- phrase “free group of rank `2`”, while `FreeGroupBasis (Fin 2) F` is only auxiliary proof -- data used to compare the abelianization with `GL (Fin 2) ℤ`. -- Layer triage: -- `source-facing`: the intrinsic rank-two hypothesis `Group.rank F = 2` and the textbook -- statement that the kernel of the abelianization action equals the subgroup of inner -- automorphisms. -- `core/canonical`: `MulAut.abelianization F`, `MulAut.IA F`, -- `MulAut.innerAutomorphismSubgroup F`, and the owner invariant `Group.rank`. -- `bridge/view`: a chosen basis `basis : FreeGroupBasis (Fin 2) F` is internal bridge data used -- to identify the abelianization with the free abelian group on `Fin 2`. -- Primitive vs. derived: -- the source-facing primitive datum is the rank hypothesis `Group.rank F = 2`; any chosen -- `FreeGroupBasis (Fin 2) F` realizing that rank is derived bridge data and should not appear in -- the public API. variable [Group.FG F] theorem ia_eq_inner_of_rank_eq_two (h_rank : Group.rank F = 2) : MulAut.IA F = MulAut.innerAutomorphismSubgroup F

Proposition 1.4.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-7: in the automorphism group of a rank-two free group, every finite-order automorphism has order 1, 2, 3, or 4.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] -- Primary domain: finite-order automorphisms and their conjugacy classes in a rank-two free group. -- Domain sampling: -- 1. `MulAut F` is the canonical owner abstraction for `Aut(F)`. -- 2. `IsOfFinOrder α` is mathlib's owner predicate for finite-order automorphisms. -- 3. `ConjClasses (MulAut F)` together with `ConjClasses.mk` is the owner abstraction for -- conjugacy classes in `Aut(F)`. -- 4. `Group.rank` is the intrinsic owner for the source phrase “rank-two free group”, while -- `FreeGroupBasis (Fin 2) F` with `basis.toGL : MulAut F →* GL (Fin 2) ℤ` is auxiliary proof -- data used internally for the matrix classification. -- Layer triage: -- `source-facing`: finite-order elements of `Aut(F)` and their conjugacy classes in a free group -- of intrinsic rank `2`. -- `core/canonical`: `FreeGroupBasis (Fin 2) F`, `Group.rank`, `MulAut F`, `IsOfFinOrder`, -- `orderOf`, `ConjClasses (MulAut F)`, and `ConjClasses.mk`. -- `bridge/view`: a chosen basis `basis : FreeGroupBasis (Fin 2) F` obtained from -- `exists_basis_fin_two_of_rank_eq_two h_rank` is internal bridge data used to pass to -- `basis.toGL`; the basis-relative classification lemmas below stay private because the public -- textbook content is the intrinsic rank-two statement. variable [Group.FG F] variable (h_rank : Group.rank F = 2) include h_rank theorem orderOf_eq_one_or_two_or_three_or_four_of_finite_order {α : MulAut F} (hα : IsOfFinOrder α) : orderOf α = 1 ∨ orderOf α = 2 ∨ orderOf α = 3 ∨ orderOf α = 4

Lemma 1.4.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-4-8: if α ∈ IA(F) and some positive power of α is inner, then for every chosen basis element basis x and every lower-central-series term lowerCentralSeries F n, there is some k in that term such that α (basis x) is conjugate to (basis x) * k.

universe u v variable {F : Type u} [Group F] [IsFreeGroup F] namespace FreeGroupBasis theorem exists_isConj_basisElement_mul_of_mem_IA_of_pow_mem_inner {X : Type v} (basis : FreeGroupBasis X F) (α : MulAut F) (x : X) (n : ℕ) {N : ℕ} (hN : 0 < N) (hIA : α ∈ MulAut.IA F) (hInner : α ^ N ∈ JA(F)) : ∃ k : lowerCentralSeries F n, IsConj (α (basis x)) (basis x * k)

Proposition 1.4.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-9: if u and v are not conjugate in a free group F, then for every prime p there is a finite p-group quotient of F in which the images of u and v are still not conjugate. This is the quotient-owner form of the textbook surjective statement, recovered canonically from the quotient-by-kernel presentation of a surjective homomorphism.

universe u open QuotientGroup variable {F : Type u} [Group F] [IsFreeGroup F] theorem exists_finite_pGroup_quotient_separating_nonconjugate (p : ℕ) [Fact p.Prime] (u v : F) (huv : ¬ IsConj u v) : ∃ N : FiniteIndexNormalSubgroup F, IsPGroup p (F ⧸ N.toSubgroup) ∧ ¬ IsConj (u : F ⧸ N.toSubgroup) (v : F ⧸ N.toSubgroup)

Proposition 1.4.10

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-10: if u and v are not conjugate in the free group F, then for some index n their images in the quotient by the nth term of the lower central series are not conjugate.

universe u open QuotientGroup variable {F : Type u} [Group F] [IsFreeGroup F] theorem exists_lowerCentralSeries_quotient_separating_nonconjugate (u v : F) (huv : ¬ IsConj u v) : ∃ n : ℕ, ¬ IsConj ((u : F ⧸ Subgroup.lowerCentralSeries F n)) (v : F ⧸ Subgroup.lowerCentralSeries F n)

Lemma 1.4.11

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-4-11: if α ∈ IA(F) and some positive power of α is inner, then α sends every chosen basis element of F to a conjugate of itself.

universe u v open QuotientGroup variable {F : Type u} [Group F] [IsFreeGroup F] theorem isConj_basisElement_of_mem_IA_of_pow_mem_inner {X : Type v} (basis : FreeGroupBasis X F) (α : MulAut F) (x : X) {N : ℕ} (hN : 0 < N) (hIA : α ∈ MulAut.IA F) (hInner : α ^ N ∈ JA(F)) : IsConj (α (basis x)) (basis x)

Proposition 1.4.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem mem_inner_of_mem_IA_of_pow_mem_inner (α : MulAut F) (N : ℕ+) (hIA : α ∈ MulAut.IA F) (hInner : α ^ (N : ℕ) ∈ JA(F)) : α ∈ JA(F)

Corollary 1.4.13

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-4-13: for a free group F, the quotient of IA(F) by its inner automorphism subgroup is torsion free.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem ia_quotient_inner_isMulTorsionFree : IsMulTorsionFree (MulAut.IA F ⧸ (JA(F)).subgroupOf (MulAut.IA F))

Corollary 1.4.14

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-4-14: if F is a free group, then IA(F) is torsion free.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] theorem ia_isMulTorsionFree : IsMulTorsionFree (MulAut.IA F)

Corollary 1.4.15

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-4-15: after choosing a rank-n basis of the free group F, the natural map from Aut(F) to GL (Fin n) ℤ carries each finite subgroup of Aut(F) isomorphically onto its image subgroup of GL (Fin n) ℤ, via the canonical owner equivalence MonoidHom.ofInjective (toGL_restrict_injective_of_finite_subgroup basis G).

universe u open LinearMap variable {F : Type u} [Group F] variable {n : ℕ} -- Layer triage for Corollary 1-4-15: -- `source-facing`: a basis `basis : FreeGroupBasis (Fin n) F` and a finite subgroup -- `G ≤ MulAut F`. -- `core/canonical`: the restricted homomorphism `basis.toGL.restrict G` and mathlib's owner -- equivalence `MonoidHom.ofInjective` from an injective homomorphism to its range. -- `bridge/view`: `FreeGroupBasis.toGL` from Corollary `1-4-16`. -- -- Domain sampling: -- 1. `FreeGroupBasis.toGL` is the chapter owner map from `MulAut F` to `GL (Fin n) ℤ`. -- 2. `Subgroup.orderOf_coe` is the canonical comparison between element orders in a subgroup and -- in the ambient group. -- 3. `MonoidHom.ofInjective` is the owner equivalence from a group to the range of an injective -- homomorphism, with owner companion lemma `MonoidHom.ofInjective_apply`. -- -- Primitive vs. derived: -- the primitive source data are the chosen basis and the finite subgroup `G`; injectivity of the -- restricted representation is the substantive theorem, while the isomorphism onto the image is -- derived canonically from `MonoidHom.ofInjective`. #check (fun (basis : FreeGroupBasis (Fin n) F) (G : Subgroup (MulAut F)) [Finite G] ↦ (MonoidHom.ofInjective (toGL_restrict_injective_of_finite_subgroup basis G) : G ≃* (basis.toGL.restrict G).range))

Corollary 1.4.16

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-4-16: if a free group of rank n has an automorphism of positive finite order N, then GL (Fin n) ℤ has an element of order N.

universe u open LinearMap.GeneralLinearGroup Matrix.GeneralLinearGroup MulEquiv variable {F : Type u} [Group F] variable {n N : ℕ} theorem exists_gl_element_of_order_of_free_group_automorphism (basis : FreeGroupBasis (Fin n) F) (hN : 0 < N) (hF : ∃ φ : MulAut F, orderOf φ = N) : ∃ g : GL (Fin n) ℤ, orderOf g = N

Definition 1.4.17

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-4-17: a cyclic word on the alphabet X is a cyclically ordered list of letters from X^{±1}, understood by default to be reduced. The owner abstraction is the rotation quotient List.Cycle (X × Bool), with cyclic reduction imposed as a predicate on the quotient.

open scoped BigOperators universe u v open List abbrev CyclicWord (X : Type u) := { w : Cycle (X × Bool) // w.IsCyclicallyReduced }

Proposition 1.4.22

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-22: if a cyclic word w' is the image of a cyclic word w under an automorphism α of the free group and w' is no longer than w, then α factors as a product of Whitehead automorphisms whose nontrivial prefix images of w never exceed the original cyclic length, and are strictly shorter whenever the terminal image is strictly shorter.

universe u variable {X : Type u} open scoped Whitehead theorem exists_whitehead_factorization_of_cyclicWord_image_length_le (w w' : CyclicWord X) (α : MulAut (FreeGroup X)) (himage : α • w = w') (hlen : w'.length ≤ w.length) : ∃ τs : List (MulAut (FreeGroup X)), τs.reverse.prod = α ∧ (∀ τ ∈ τs, τ ∈ Ω) ∧ (∀ i : ℕ, 0 < i → i < τs.length → (Whitehead.prefixAut τs i • w).length ≤ w.length) ∧ (w'.length < w.length → ∀ i : ℕ, 0 < i → i < τs.length → (Whitehead.prefixAut τs i • w).length < w.length)

Proposition 1.4.24

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-24: for a finitely generated free group F, it is decidable whether two elements lie in the same automorphism orbit.

universe u v open MulAction variable {F : Type u} [Group F] [IsFreeGroup F] [Finite (IsFreeGroup.Generators F)] noncomputable def automorphism_orbitRel_decidable (w₁ w₂ : F) : Decidable (orbitRel (MulAut F) F w₂ w₁)

Proposition 1.4.25

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-4-25: if the automorphic image of a finite family of cyclic words under α has minimal total cyclic length among all automorphic images, then α admits a factorization into Whitehead automorphisms such that the successive prefix images strictly decrease total cyclic length until the terminal minimum is reached, and thereafter keep that minimum fixed.

universe u variable {X : Type u} -- Domain sampling for Whitehead automorphisms: -- 1. `MulAut (FreeGroup X)` is the owner abstraction for automorphisms of the ambient free group. -- 2. `SignedLetter X` is the project owner vocabulary for signed basis letters. -- 3. `FreeGroup.mk [x]` is the canonical ambient free-group element represented by one signed -- letter `x : SignedLetter X`. -- 4. `SignedLetter` carries the owner involution on signed letters, written as `x⁻¹`. -- Primitive data for Whitehead automorphisms of the second kind are therefore a multiplier -- `a : SignedLetter X` together with a subset `A ⊆ X^{±1}` satisfying the textbook constraints -- `a ∈ A` and `a⁻¹ ∉ A`; the four word-shapes are derived from the membership pattern of -- `x` and `x⁻¹`. open scoped Whitehead theorem exists_whitehead_factorization_of_minimal_cyclic_word_total_length {ι : Type*} [Fintype ι] (w : ι → CyclicWord X) (α : MulAut (FreeGroup X)) (hmin : ∀ α' : MulAut (FreeGroup X), CyclicWord.totalLength (α • w) ≤ CyclicWord.totalLength (α' • w)) : ∃ τs : List (MulAut (FreeGroup X)), τs.reverse.prod = α ∧ (∀ τ ∈ τs, τ ∈ Ω) ∧ ∀ i : ℕ, i < τs.length → let prefixLength := CyclicWord.totalLength (Whitehead.prefixAut τs i • w) let nextLength := CyclicWord.totalLength (Whitehead.prefixAut τs (i + 1) • w) let targetLength := CyclicWord.totalLength (α • w) nextLength ≤ prefixLength ∧ (prefixLength ≠ targetLength → nextLength < prefixLength)

1.5 — Stabilizers in Aut(F)

Proposition 1.5.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-5-1 (1): every automorphism of a rank-two free group carries the commutator cyclic word to itself or to its inverse.

open MulAction Matrix.GeneralLinearGroup open scoped commutatorElement universe u v variable {F : Type v} [Group F] open RankTwoFreeGroup namespace FreeGroupBasis -- Layer triage: -- `source-facing`: a rank-two basis `basis : FreeGroupBasis (Fin 2) F` and the cyclic word -- determined by the commutator of its two basis elements. -- `core/canonical`: the basis-induced action `basis.cyclicWordMulAction` on `CyclicWord (Fin 2)`, -- the owner subgroup `MulAction.stabilizer`, the bridge `basis.toGL : MulAut F →* GL (Fin 2) ℤ`, -- and the determinant morphism on `GL (Fin 2) ℤ`. -- `bridge/view`: `commutatorCyclicWord` is the standard rank-two commutator word, while the -- textbook subgroup `SA(F)` is expressed directly by the determinant-one kernel -- `(det.comp basis.toGL).ker`. -- -- Domain sampling: -- 1. `CyclicWord X` and the induced action from Proposition `1-5-2` are the chapter owner API for -- cyclic words and their automorphic images. -- 2. `MulAction.stabilizer` is mathlib's owner subgroup for automorphisms fixing a cyclic word. -- 3. `FreeGroupBasis.toGL` from Corollary `1-4-16` is the canonical bridge from automorphisms of -- a rank-two free group to `GL (Fin 2) ℤ`. -- 4. `Matrix.GeneralLinearGroup.det` is the owner determinant morphism on `GL (Fin 2) ℤ`. -- -- Primitive vs. derived: -- the primitive source data are only the chosen rank-two basis; the commutator cyclic words come -- from the source-facing owner declarations `RankTwoFreeGroup.commutatorCyclicWord` and -- `RankTwoFreeGroup.inverseCommutatorCyclicWord` imported from Proposition `1-5-2`. The -- stabilizer subgroup and the determinant-one kernel `(det.comp basis.toGL).ker` are derived -- owner constructions built from those data. theorem smul_commutatorCyclicWord_eq_or_eq_inverse (basis : FreeGroupBasis (Fin 2) F) (α : MulAut F) : letI := basis.cyclicWordMulAction α • commutatorCyclicWord = commutatorCyclicWord ∨ α • commutatorCyclicWord = inverseCommutatorCyclicWord

Proposition 1.5.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-5-2: let w be a nontrivial cyclic word in a free group of rank at least 2. If w is not the cyclic word of a nonzero power of a basic commutator in rank 2, then the image of its stabilizer in Aut(F) / JA(F) has infinite index.

universe u v open MulAction QuotientGroup open scoped commutatorElement variable {X : Type u} theorem cyclicWord_stabilizer_image_in_JAQuotient_index_eq_zero_of_not_rankTwo_commutator_power (w : CyclicWord X) (hX : 1 < Nat.card X) (hw : w.toConjClasses ≠ ConjClasses.mk 1) (hcomm : ¬ ∃ e : X ≃ Fin 2, ∃ k : ℤ, k ≠ 0 ∧ w.toConjClasses = ConjClasses.mk ((FreeGroup.freeGroupCongr e.symm RankTwoFreeGroup.commutator) ^ k)) : (Subgroup.map (mk' (JA(FreeGroup X))) (stabilizer (MulAut (FreeGroup X)) w)).index = 0

Theorem 1.5.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Theorem 1-5-3: for words of the form x₁^{a₁} ⋯ xₘ^{aₘ} and x₁^{b₁} ⋯ xₙ^{bₙ} with all exponents at least 2, the two basis words lie in the same automorphism orbit if and only if the exponent lists are permutations of one another, equivalently if and only if they have the same length and the bᵢ are a permutation of the aᵢ.

universe u open MulAction variable {F : Type u} [Group F] theorem orderedBasisPowerWord_orbitRel_iff_perm (basis : FreeGroupBasis ℕ F) (a b : List ℕ) (ha : ∀ n ∈ a, 2 ≤ n) (hb : ∀ n ∈ b, 2 ≤ n) : orbitRel (MulAut F) F (basis.orderedBasisPowerWord b) (basis.orderedBasisPowerWord a) ↔ List.Perm a b

Proposition 1.5.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-5-5: if F is a finitely generated free group and α is an automorphism of finite order, then the subgroup of elements fixed by α is a free factor of F.

universe u open CategoryTheory variable {F : Type u} [Group F] [IsFreeGroup F] [Group.FG F] namespace MulAut local notation "Fix[" α "]" => MonoidHom.eqLocus (α : F →* F) 1 theorem fixed_eqLocus_isFreeFactorOf_top_of_isOfFinOrder (α : MulAut F) (hα : IsOfFinOrder α) : (Fix[α]).IsFreeFactorOf (⊤ : Subgroup F)

Proposition 1.5.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-5-6: if the canonical reduced word of g : FreeGroup X has minimal length in its Aut(F(X))-orbit, then every automorphic image of g has at least as many distinct basis letters in its canonical reduced word. Equivalently, if exactly n basis letters occur in the canonical reduced word of g, then at least n basis letters occur in every automorphic image.

universe u variable {X : Type u} open CyclicWord theorem reducedWord_support_card_le_automorphic_image_support_card_of_minimal_length (g : FreeGroup X) (hmin : ∀ α : MulAut (FreeGroup X), g.toWord.length ≤ (α g).toWord.length) (α : MulAut (FreeGroup X)) : (reducedWordSupport g).card ≤ (reducedWordSupport (α g)).card

Proposition 1.5.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Owner-level formulation of Proposition 1-5-7: if an element g of a free group has minimal reduced length among its automorphic images with respect to the chosen basis basis, and every basis generator occurs in the canonical reduced word of g, then the stabilizer of g in Aut(F) is torsion-free.

universe u open MulAction variable {X : Type u} {F : Type u} [Group F] namespace FreeGroupBasis theorem stabilizer_isMulTorsionFree_of_minimal_length_and_full_support (basis : FreeGroupBasis X F) (g : F) (hmin : ∀ α : MulAut F, (basis.repr g).toWord.length ≤ (basis.repr (α g)).toWord.length) (hcontains : ∀ x : X, basisLetterOccurs basis x g) : IsMulTorsionFree (stabilizer (MulAut F) g)

Proposition 1.5.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-5-8: if w is a cyclic word of minimal cyclic length in its automorphism orbit with respect to a chosen free basis of F, if every basis letter occurs in w, and if a finite-order automorphism α fixes w, then the order of α divides the cyclic length of w.

universe u v open MulAction variable {X : Type u} {F : Type v} [Group F] namespace FreeGroupBasis theorem orderOf_dvd_cyclicWord_length_of_fixed_minimal_word (basis : FreeGroupBasis X F) (w : CyclicWord X) (α : MulAut F) (hcontains : w.HasFullSupport) (hmin : letI := basis.cyclicWordMulAction ∀ β : MulAut F, w.length ≤ (β • w).length) (hfix : letI := basis.cyclicWordMulAction α ∈ stabilizer (MulAut F) w) (hα : IsOfFinOrder α) : orderOf α ∣ w.length

Proposition 1.5.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-5-9: for a free group F with finite basis X and a finite set S of cyclic words over X, the subgroup of automorphisms fixing every member of S admits a finite presentation.

universe u v open MulAction variable {X : Type u} {F : Type v} [Group F] variable [Finite X] theorem cyclicWordFinsetFixingSubgroup_isFinitelyPresented (basis : FreeGroupBasis X F) (S : Finset (CyclicWord X)) : letI := basis.cyclicWordMulAction Group.IsFinitelyPresented (fixingSubgroup (MulAut F) (S : Set (CyclicWord X)))

1.6 — Equations over Groups

Proposition 1.6.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-1: every family of elements of a group admits simultaneous prescribed positive roots after embedding the group into a larger group.

universe u v variable {G : Type u} [Group G] {ι : Type v} theorem exists_embedding_with_prescribed_roots (g : ι → G) (m : ι → ℕ+) : ∃ (H : Type (max u v)) (_ : Group H) (f : G →* H), Function.Injective f ∧ ∃ roots : ι → H, ∀ i, roots i ^ (m i : ℕ) = f (g i)

Proposition 1.6.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-2: a group can be embedded in an overgroup containing one element that simultaneously conjugates every g i to g' i if and only if the generated subgroups Gp{g_i} and Gp{g_i'} are isomorphic by a map carrying each g i to g' i.

universe u v variable {G : Type u} [Group G] {ι : Type v} theorem exists_embedding_with_common_conjugator_iff (g g' : ι → G) : (∃ (H : Type u) (_ : Group H) (f : G →* H) (x : H), Function.Injective f ∧ ∀ i, x⁻¹ * f (g i) * x = f (g' i)) ↔ ∃ φ : Subgroup.closure (Set.range g) ≃* Subgroup.closure (Set.range g'), ∀ i, (φ ⟨g i, Subgroup.subset_closure (Set.mem_range_self i)⟩ : G) = g' i

Proposition 1.6.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-3: if G is a finite nontrivial group, X is an infinite cyclic group, and w is an element of the free product G ∗ X, then the quotient of G ∗ X by the normal closure of w is nontrivial.

universe u v open scoped Monoid.Coprod open Subgroup variable {G : Type u} [Group G] [Finite G] [Nontrivial G] variable {X : Type v} [Group X] [IsCyclic X] [Infinite X] -- Layer triage: -- `source-facing`: the quotient of the free product `G ∗ X` by the normal closure of one element. -- `core/canonical`: `Monoid.Coprod` for the ambient free product, -- `Subgroup.normalClosure` for the relator subgroup, and `QuotientGroup.nontrivial_iff` for the -- quotient-side nontriviality criterion. -- `bridge/view`: an explicit generator of the infinite cyclic factor would come from -- `intCyclicMulEquiv X : Multiplicative ℤ ≃* X`, but the proposition itself only needs the -- intrinsic owner assumptions `[IsCyclic X] [Infinite X]`. -- Domain sampling: -- 1. `Monoid.Coprod` with notation `G ∗ X` is mathlib's owner abstraction for the free product of -- two groups. -- 2. `Subgroup.normalClosure` is the owner construction for the normal closure of a subset, hence -- of a singleton relator, so the relator subgroup is canonically `Subgroup.normalClosure {w}`. -- 3. `QuotientGroup.mk'` and `QuotientGroup.nontrivial_iff` are the canonical quotient-group API -- for passing from the ambient free product to the quotient and reading its nontriviality. -- 4. `intCyclicMulEquiv` shows that an infinite cyclic group is canonically equivalent to -- `Multiplicative ℤ`, so a separate chosen-generator wrapper for `X` would duplicate owner API. -- Primitive vs. derived: -- the primitive source data are the finite nontrivial group `G`, the infinite cyclic group `X`, -- and the relator `w : G ∗ X`; the relator subgroup `Subgroup.normalClosure {w}` and the quotient -- `((G ∗ X) ⧸ Subgroup.normalClosure {w})` are derived canonically from that data. theorem freeProduct_quotient_normalClosure_singleton_nontrivial (w : G ∗ X) : Nontrivial ((G ∗ X) ⧸ normalClosure {w})

Proposition 1.6.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-4: the irreducibility rank of a free product is the sum of the irreducibility ranks of the two factors.

universe u open scoped Monoid.Coprod open scoped GroupIr variable {G G₁ G₂ : Type u} [Group G] [Group G₁] [Group G₂] theorem groupIr_freeProduct_eq_add : Ir(G₁ ∗ G₂) = Ir(G₁) + Ir(G₂)

Lemma 1.6.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-6-5: let q > 1, let A be an n × m matrix over a field K, and suppose K contains an element ω with ω ^ q = -1. If for every q-tuple of row indices the sum of the corresponding q-fold column products is zero, then the rank of A is at most m / 2.

open scoped BigOperators -- Layer triage: -- `source-facing`: a matrix over a field whose associated diagonal `q`-linear column-sum form -- vanishes on every `q`-tuple of rows, together with the resulting rank bound. -- `core/canonical`: `Matrix (Fin n) (Fin m) K` and the owner invariant `Matrix.rank`. -- `bridge/view`: the textbook tuple `(i₁, …, i_q)` is represented canonically by a function -- `Fin q → Fin n`. -- Domain sampling: -- 1. `Matrix.rank` is mathlib's owner invariant for matrix-rank statements. -- 2. `Matrix.rank_eq_finrank_span_row` is the direct owner bridge from matrix rank to the -- dimension of the row space, which is the linear-algebra owner viewpoint used in the -- textbook proof. -- 3. `Matrix.rank_le_width` is the canonical ambient width bound for matrices -- `Matrix (Fin n) (Fin m) K`. -- 4. `MultilinearMap.mkPiRing` is the canonical owner declaration for the `q`-fold product map -- on `K`, so the diagonal `q`-linear form belongs proof-side rather than as a separate public -- wrapper around the matrix statement. -- -- Best owner abstraction: -- the public statement should live on the matrix owner itself, as a theorem in namespace -- `Matrix`. The vanishing `q`-fold column-product condition is primitive source data, while the -- diagonal multilinear form and row-space reformulation stay proof-side derived API. -- -- Primitive vs. derived: -- the primitive source data are the matrix `A`, the existence of an element `ω` with `ω^q = -1`, -- and the vanishing of all `q`-fold column products. The diagonal multilinear form on rows and -- the rank bound are derived owner-level constructions attached to `A`. namespace Matrix variable {K : Type*} [Field K] {q n m : ℕ} theorem rank_le_half_width_of_vanishing_qfold_column_products (A : Matrix (Fin n) (Fin m) K) (hq : 1 < q) (hω : ∃ ω : K, ω ^ q = -1) (hvanish : ∀ rows : Fin q → Fin n, ∑ j, ∏ t, A (rows t) j = 0) : A.rank ≤ m / 2

Proposition 1.6.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-6: if N > 1 and the ordered product u₁^N ⋯ u_m^N is trivial in a free group, then the subgroup generated by u₁, …, u_m has rank at most m / 2.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] {m N : ℕ} theorem rank_closure_range_le_half_of_prod_powers_eq_one (u : Fin m → F) (hN : 1 < N) (hprod : (List.ofFn (fun i ↦ u i ^ N)).prod = 1) : Group.rank (Subgroup.closure (Set.range u)) ≤ m / 2

Corollary 1.6.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-6-7: for every n ≥ 0 and N > 1, some group contains an element that is a product of exactly n Nth powers, in the sense that it lies in the n-fold pointwise product of Set.range (fun g ↦ g ^ N) but in no smaller such product.

open scoped Pointwise theorem exists_group_element_mem_nthPowerSet_pow_not_mem_lower_powers (n N : ℕ) (hN : 1 < N) : ∃ (G : Type) (_ : Group G) (w : G), w ∈ (Set.range fun g : G ↦ g ^ N) ^ n ∧ ∀ m < n, w ∉ (Set.range fun g : G ↦ g ^ N) ^ m

Proposition 1.6.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-8: if F has a basis indexed by Fin g ⊕ Fin g, so that the basis elements form g ordered pairs, and the product of those g commutators equals a product of m commutators, then m >= g.

universe u open scoped commutatorElement variable {F : Type u} [Group F] namespace FreeGroupBasis -- Layer triage: -- `source-facing`: a chosen basis of `F` with `2g` elements grouped into `g` ordered pairs, and -- an equality between the corresponding product of `g` commutators and a product of `m` -- commutators built from an arbitrary finite family of pairs of elements. -- `core/canonical`: the owner abstraction `FreeGroupBasis (Fin g ⊕ Fin g) F` for the basis and -- the standard commutator-element notation `⁅a, b⁆`. -- `bridge/view`: the textbook list `x_1, ..., x_{2g}` is represented by the two summands of -- `Fin g ⊕ Fin g`, so pair `i` is `(basis (Sum.inl i), basis (Sum.inr i))`. -- Domain sampling: -- 1. `FreeGroupBasis (Fin g ⊕ Fin g) F` is the mathlib owner abstraction for the chosen basis. -- 2. `basis.repr : F ≃* FreeGroup (Fin g ⊕ Fin g)` is the canonical transport to the standard -- free-group model used in commutator-length arguments. -- 3. `⁅a, b⁆` from `commutatorElement` is the owner notation for group commutators. -- Primitive vs. derived: -- the primitive source data are the chosen basis, the finite family `u : Fin m → F × F` of -- commutator pairs on the right, and the asserted equality; the paired basis elements -- `basis (.inl i)` and `basis (.inr i)` are derived directly from the owner indexing type -- `Fin g ⊕ Fin g`. theorem genus_le_of_commutator_product_eq {g m : ℕ} (basis : FreeGroupBasis (Fin g ⊕ Fin g) F) (u : Fin m → F × F) (hrel : basis.pairedCommutatorProduct = (List.ofFn fun j : Fin m ↦ ⁅(u j).1, (u j).2⁆).prod) : g ≤ m

Proposition 1.6.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-9, written with the explicit mathlib reindexing of the lower central series: if w is a product of two square elements of a free group F and w ∈ Γ n, then the image of w in the quotient Γ n / Γ (n + 1) is a square. Here the Lean index n corresponds to the textbook index n + 1, since mathlib sets lowerCentralSeries F 0 = F.

universe u variable {F : Type u} [Group F] [IsFreeGroup F] local notation "Γ" => Subgroup.lowerCentralSeries F -- Layer triage: -- `source-facing`: an element `w` of a free group which is both a product of two square elements -- and a member of one textbook lower-central-series term `F_{n + 1}`, together with the induced -- square class in the next textbook quotient `F_{n + 1} / F_{n + 2}`. -- `core/canonical`: the owner lower central series `Γ`, the subgroup quotient -- `Γ n ⧸ (Γ (n + 1)).subgroupOf (Γ n)`, -- the canonical quotient coercion from `lowerCentralSeries F n`, and the canonical predicate -- `IsSquare`. -- `bridge/view`: mathlib indexes the lower central series one step earlier than the textbook -- convention used in combinatorial group theory: `Γ 0 = F` and `Γ 1 = [F, F]`. Thus the -- textbook term `F_{n + 1}` is realized by `Γ n`, with the Lean parameter `n` explicitly -- recording this reindexing. -- Domain sampling: -- 1. `lowerCentralSeries F` in mathlib is the owner abstraction for the descending central series, -- written locally here as `Γ`. -- 2. `lowerCentralSeries_zero` and `lowerCentralSeries_one` show the indexing offset: -- `lowerCentralSeries F 0 = F` and `lowerCentralSeries F 1 = [F, F]`. -- 3. `IsSquare` together with `isSquare_iff_exists_sq` is the owner API for the square factors in -- the source hypothesis. -- 4. The quotient coercion from `Γ n` is the owner-derived image of `w`, and -- `Subgroup.subgroupOf` is the canonical way to regard `Γ (n + 1)` as a subgroup of `Γ n`. -- Primitive vs. derived: -- the primitive source data are the element `w`, the hypothesis that `w` is a product of two -- squares, and the membership hypothesis `w ∈ Γ n`; any chosen square factors witnessing that -- decomposition are auxiliary bridge data, while the image class of `w` in the corresponding -- lower-central-series quotient is derived canonically from the owner subgroup. theorem isSquare_in_lowerCentralSeries_subquotient_of_product_two_squares (w : F) (n : ℕ) (hw_square : ∃ a b : F, IsSquare a ∧ IsSquare b ∧ w = a * b) (hw : w ∈ Γ n) : IsSquare ((⟨w, hw⟩ : Γ n) : Γ n ⧸ (Γ (n + 1)).subgroupOf (Γ n))

Proposition 1.6.10

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-10: for positive rank n, the paired commutator product determined by a basis of F can be written as a product of m squares if and only if m ≥ 2n + 1.

universe u variable {F : Type u} [Group F] namespace FreeGroupBasis -- Layer triage: -- `source-facing`: a chosen basis of `F` with `2n` basis elements grouped into `n` ordered -- pairs, a positive-rank hypothesis `0 < n`, together with a product of `m` squares representing -- the corresponding product of paired commutators. -- `core/canonical`: the owner abstraction `FreeGroupBasis (Fin n ⊕ Fin n) F`, the owner-derived -- paired-commutator element `basis.pairedCommutatorProduct` from Proposition `1-6-8`, and finite -- families `Fin m → F`. -- `bridge/view`: the textbook basis elements `x₁, …, x₂n` are encoded by the two summands of -- `Fin n ⊕ Fin n`, so pair `i` is `(basis (.inl i), basis (.inr i))`. -- Domain sampling: -- 1. `FreeGroupBasis (Fin n ⊕ Fin n) F` is the chapter and mathlib owner abstraction for a -- chosen free basis grouped into `n` ordered pairs. -- 2. `basis.pairedCommutatorProduct` from Proposition `1-6-8` is the chapter owner-derived -- element encoding the textbook product `∏[i < n] [x₂i₊₁, x₂i₊₂]`. -- 3. `basis.repr : F ≃* FreeGroup (Fin n ⊕ Fin n)` is the canonical transport to the standard -- free-group model behind the textbook normal-form arguments. -- 4. Proposition `1-6-8`, `genus_le_of_commutator_product_eq`, already uses the same owner -- abstraction for paired commutator products, so this item should refine to that same basis -- interface rather than introducing a parallel wrapper. -- Primitive vs. derived: -- the primitive source data are the chosen basis, the positive rank `n`, and the finite family of -- square factors; the paired basis commutators are derived directly from the owner indexing type -- `Fin n ⊕ Fin n`. theorem pairedCommutatorProduct_eq_square_product_iff {n m : ℕ} (basis : FreeGroupBasis (Fin n ⊕ Fin n) F) (hn : 0 < n) : (∃ u : Fin m → F, basis.pairedCommutatorProduct = (List.ofFn fun j ↦ u j ^ 2).prod) ↔ 2 * n + 1 ≤ m

Proposition 1.6.11

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-11: for a nontrivial element w of the free group of rank n, the singleton relator set {w} has irreducibility rank n - 1 if and only if w lies in the normal closure of some primitive element of the ambient free group.

open scoped RelatorSetIr open Subgroup -- Layer triage: -- `source-facing`: a nontrivial relator `w` in a free group of rank `n`, viewed as the singleton -- relator set `{w}`, together with the criterion that `Ir({w}) = n - 1` exactly when `w` belongs -- to the normal closure of a primitive element. -- `core/canonical`: the relator-set owner notation `Ir(W)`, the mathlib owner abstraction -- `IsPrimitiveElement` for “belongs to some basis”, and the subgroup owner -- `Subgroup.normalClosure`. -- `bridge/view`: the textbook phrase “lies in the normal closure of an element in a basis for -- `Φ`” is a basis-witness specialization of the owner predicate `IsPrimitiveElement`, via -- `FreeGroupBasis.isPrimitiveElement`. -- Domain sampling: -- 1. `Ir(W)` from Proposition `1-6-13` is the chapter owner abstraction for irreducibility rank. -- 2. `IsPrimitiveElement` in `CombinatorialGroupTheory.Basic` is the project owner abstraction -- for “belongs to some free basis”. -- 3. `FreeGroupBasis.isPrimitiveElement` is the canonical bridge from a chosen basis element to -- that owner predicate. -- 4. `Subgroup.normalClosure` is the canonical owner construction for the normal closure of a -- singleton subset. -- Primitive vs. derived: -- the primitive source data are only the rank parameter `n` and the nontrivial relator `w`; the -- singleton relator set and the primitive-element normal closure are derived canonically from the -- owner predicate `IsPrimitiveElement`; any explicit basis witness is auxiliary bridge data. theorem ir_singleton_eq_pred_iff_mem_normalClosure_of_isPrimitiveElement (n : ℕ) (w : FreeGroup (Fin n)) (hw : w ≠ 1) : Ir(({w} : Set (FreeGroup (Fin n)))) = n - 1 ↔ ∃ p : FreeGroup (Fin n), IsPrimitiveElement p ∧ w ∈ normalClosure ({p} : Set (FreeGroup (Fin n)))

Proposition 1.6.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-12: let W be the singleton relator set in the free group on n + 1 generators generated by w = ξ_(n+1)^(-k) * w₁(ξ₁, …, ξ_n) * ξ_(n+1)^k, with k > 1, where w₁ lies in no basis of the smaller free group on ξ₁, …, ξ_n and is not a proper power there. Then Ir(W) < n.

open FreeGroup open scoped RelatorSetIr -- Layer triage: -- `source-facing`: a singleton relator set `W = {w}` in the free group on `n + 1` generators, -- where `w` is obtained by conjugating a word in the first `n` generators by a positive power of -- the last generator, together with the textbook hypotheses that the inner word lies in no basis -- and is not a proper power in that smaller free group. -- `core/canonical`: the relator-set owner notation `Ir(W)`, the presented-group owner -- `PresentedGroup W` behind that definition, the primitive-element owner `IsPrimitiveElement`, the -- automorphism owner `MulAut.conj`, and the canonical inclusion -- `map Fin.castSucc : FreeGroup (Fin n) →* FreeGroup (Fin n.succ)`. -- `bridge/view`: the textbook generators `ξ₁, …, ξₙ` are represented by `Fin n.succ`; the inner -- word `w₁` lives in `FreeGroup (Fin n)` and is viewed in the ambient rank-`n + 1` free group via -- `map Fin.castSucc`, while the source phrase “lies in no basis” is expressed canonically by -- `¬ IsPrimitiveElement w₁`; the outer conjugation is then expressed by `MulAut.conj`, and the -- source phrase “`w₁` is not a proper power” is expressed by -- `¬ IsProperPower w₁`. -- Domain sampling: -- 1. `Ir(W)` from Proposition `1-6-13` is the chapter owner abstraction for irreducibility rank. -- 2. `PresentedGroup` in mathlib is the canonical owner object on which `Ir(W)` is built. -- 3. `IsPrimitiveElement` in `CombinatorialGroupTheory.Basic` is the project owner abstraction -- for “belongs to some basis”, so its negation is the canonical owner-level form of “lies in -- no basis”. -- 4. `map Fin.castSucc` in mathlib is the canonical way to view a word in the first `n` -- generators inside the free group on `n + 1` generators. -- Primitive vs. derived: -- the primitive source data are the inner word `w₁`, its non-primitive and non-proper-power -- hypotheses in the smaller free group, and the exponent `k`; the singleton relator set in the -- ambient free group is derived canonically from those data via `map Fin.castSucc` and -- `MulAut.conj`. theorem ir_singleton_conjugate_lt_of_nonprimitive_not_properPower (n : ℕ) (w₁ : FreeGroup (Fin n)) (hw₁_nonprimitive : ¬ IsPrimitiveElement w₁) (hw₁_not_properPower : ¬ IsProperPower w₁) (k : ℕ) (hk : 1 < k) : Ir(({MulAut.conj (((of (Fin.last n)) ^ k)⁻¹) (map Fin.castSucc w₁)} : Set (FreeGroup (Fin n.succ)))) < n

Proposition 1.6.13

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-13: if W' is the image of a relator set W under an automorphism of the ambient free group, then Ir(W') = Ir(W).

universe u variable {ι : Type u} open scoped RelatorSetIr -- Layer triage: -- `source-facing`: the irreducibility rank `Ir(W)` of a relator set `W`, and its invariance under -- automorphisms of the ambient finite-rank free group. -- `core/canonical`: the chapter owner `groupIr (PresentedGroup W)`, the presented-group owner -- `PresentedGroup W`, the owner automorphism group `MulAut (FreeGroup ι)`, and set image -- `α '' W`. -- `bridge/view`: the induced isomorphism -- `PresentedGroup W ≃* PresentedGroup (α '' W)` is the canonical quotient transport supplied by -- `QuotientGroup.congr` together with `Subgroup.map_normalClosure`, while the source-facing -- textbook notation `Ir(W)` is a thin notation for the canonical owner value -- `groupIr (PresentedGroup W)`. -- Domain sampling: -- 1. `groupIr` from Proposition `1-6-4` is the chapter owner abstraction for irreducibility rank. -- 2. `PresentedGroup W` is the canonical owner object attached to a relator set `W`. -- 3. `QuotientGroup.congr` is the canonical quotient-level transport induced by an ambient -- automorphism preserving the distinguished normal subgroup. -- 4. `Subgroup.map_normalClosure` is the canonical proof that the transported normal closure is -- exactly the normal closure of the image relator set. -- Primitive vs. derived: -- the primitive source data are only the relator set `W`; the presented group, its -- irreducibility invariant in `ℕ∞`, the transformed relator family `α '' W`, and the induced -- presented-group isomorphism are all derived canonically from that data. theorem ir_image_eq (W : Set (FreeGroup ι)) (α : MulAut (FreeGroup ι)) : Ir(α '' W) = Ir(W)

Proposition 1.6.14

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-14: if W is a set of words in the free group on Fin n, and the specialized set is obtained from W by setting the generator i equal to 1, then Ir(W) ≥ Ir(W°).

universe u open scoped RelatorSetIr -- Layer triage: -- `source-facing`: the specialized relator set obtained by setting one distinguished generator -- equal to `1`, together with the induced monotonicity statement for the irreducibility rank -- `Ir`. -- `core/canonical`: the relator-set owner notation `Ir(W)`, the quotient owner -- `PresentedGroup W`, `FreeGroup.lift`, `QuotientGroup.map`, and the surviving-generator subtype -- `{j : ι // j ≠ i}`. -- `bridge/view`: the set-level specialization is the image of the relators under the unique -- free-group homomorphism that kills the generator `i` and sends every other generator to the -- corresponding generator of the smaller free group. -- Domain sampling: -- 1. `Ir(W)` from Proposition `1-6-13` is the chapter owner abstraction for irreducibility rank. -- 2. `PresentedGroup W` is the ambient owner object on which `Ir(W)` is built. -- 3. `FreeGroup.lift` is the owner construction for a homomorphism defined by its values on -- generators, so the primitive specialization data should be the homomorphism itself. -- 4. `QuotientGroup.map` and `PresentedGroup.generated_by` give the quotient-level bridge from the -- free-group specialization to the induced surjective map of presented groups. -- Primitive vs. derived: -- the primitive source data are only the distinguished generator `i`; the specialized relator set -- and the induced map of presented groups are derived canonically from the specialization -- homomorphism. variable {n : ℕ} theorem ir_ge_specializeWordSetAtGenerator (W : Set (FreeGroup (Fin n))) (i : Fin n) : Ir(W) ≥ Ir(specializeWordSetAtGenerator i W)

Proposition 1.6.15

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-6-15: Ir(W) equals the rank of the ambient free group minus the minimum number of singular transformations in a sequence attached to W and reducing W to triviality.

universe u open scoped RelatorSetIr variable {n : ℕ} theorem ir_eq_rank_sub_minSingularReductionCount (W : Set (FreeGroup (Fin n))) : Ir(W) = n - minSingularReductionCount W

1.7 — Quadratic Sets of Words

Proposition 1.7.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-1: for a symbol-occurrence relation between X and S, there exists a partition of S into occurrence-connected pieces, namely the equivalence classes of wordComponents occurs, and a corresponding partition of X into the isolated symbols X₀ and the nonempty symbol subsets carried by those word components.

universe u v variable {X : Type u} {S : Type v} open Relation -- Layer triage: -- `source-facing`: a set `X` of symbols, a set `S` of words, and the incidence relation -- `occurs : X → S → Prop`, together with the resulting decomposition of `S` into connected word -- components and of `X` into the isolated symbols plus the symbols appearing in those components. -- `core/canonical`: the owner abstractions `wordComponents occurs : Setoid S` and -- `symbolComponents occurs : Setoid X`, whose classes are the occurrence-connected word and symbol -- components. -- `bridge/view`: the partitions `(wordComponents occurs).classes` and -- `(symbolComponents occurs).classes`, together with the source-facing description of the latter in -- terms of `isolatedSymbols occurs` and `symbolsOfWords occurs c`. -- Domain sampling: -- 1. `Relation.EqvGen.setoid r` is mathlib's owner abstraction for the equivalence relation -- generated by repeated adjacency steps. -- 2. `Setoid.classes` and `Setoid.isPartition_classes` are the canonical partition API attached to -- an equivalence relation. -- 3. `Setoid.eq_of_mem_classes` is the canonical class-equality API used to pass from a chosen -- class representative to the corresponding source-facing subset. -- 4. `Setoid.IsPartition` is the owner predicate for the source-facing partition view once the -- pieces are expressed as sets of words or symbols. theorem exists_occurrence_component_partition (occurs : X → S → Prop) : Setoid.IsPartition (wordComponents occurs).classes ∧ ∃ symbolClasses : Set (Set X), Setoid.IsPartition symbolClasses ∧ ∀ A, A ∈ symbolClasses ↔ (A = isolatedSymbols occurs ∧ A.Nonempty) ∨ ∃ c ∈ (wordComponents occurs).classes, A = symbolsOfWords occurs c ∧ A.Nonempty

Lemma 1.7.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-7-2: a tree with an infinite path admits an orientation whose reverse-edge relation is well-founded and in which every vertex has an outgoing edge.

universe u -- Layer triage: -- `source-facing`: a tree together with an injective infinite ray, and an orientation in which -- every vertex has an outgoing edge. -- `core/canonical`: `SimpleGraph.IsTree`, `Digraph.toSimpleGraphInclusive`, `Std.Asymm`, and -- `WellFounded`. -- `bridge/view`: the theorem packages the source orientation condition by requiring that the -- forgetful map `D.toSimpleGraphInclusive` recover the given tree and by reading the -- no-opposite-direction condition through the canonical relation predicate `Std.Asymm D.Adj`. -- Domain sampling: -- 1. `SimpleGraph.IsTree` is mathlib's owner predicate for trees. -- 2. `Digraph.toSimpleGraphInclusive` is mathlib's owner map from digraphs to the underlying -- unoriented simple graph. -- 3. `Std.Asymm D.Adj` is the canonical owner predicate for the source condition that oriented -- edges never occur in both directions. -- 4. `SimpleGraph.fromRel_adj` shows that equality with `toSimpleGraphInclusive` expresses exactly -- the "one of the two directions is present" part of an orientation. -- 5. `WellFounded D.Adj` is the canonical owner predicate for the well-foundedness of the reverse -- edge relation induced by the orientation. -- Primitive vs. derived: -- the primitive source data are the tree `T`, an injective ray `p : ℕ → V` with adjacent -- consecutive vertices, and the digraph `D`; the fact that `D` orients `T` should be expressed -- via the owner map `D.toSimpleGraphInclusive = T` rather than a parallel local orientation -- predicate. variable {V : Type u} {T : SimpleGraph V} -- Proof sketch: choose a vertex on an infinite ray, orient every edge in the union of all -- infinite rays from it away from that vertex, orient each complementary component toward its -- unique attachment point, and then show the resulting orientation is well-founded and has no -- maximal vertex. theorem tree_exists_orientation_wellFounded_noMaximal (hT : T.IsTree) (h_infinite : ∃ p : ℕ → V, Function.Injective p ∧ ∀ n : ℕ, T.Adj (p n) (p (n + 1))) : ∃ D : Digraph V, D.toSimpleGraphInclusive = T ∧ Std.Asymm D.Adj ∧ WellFounded D.Adj ∧ ∀ v : V, ∃ w : V, D.Adj v w

Lemma 1.7.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-7-3: if X₀ is a partially ordered subset of a chosen basis basis : FreeGroupBasis X F satisfying the descending chain condition, and for each x : X₀ the words p x and q x only involve basis elements from X₀ that are strictly smaller than x, then there is an automorphism of F sending each basis element x ∈ X₀ to p x * x * q x and fixing the basis elements outside X₀. Specializing basis := FreeGroupBasis.ofFreeGroup X recovers the standard free-group model statement.

universe u v variable {X : Type u} {F : Type v} [Group F] namespace FreeGroupBasis theorem exists_automorphism_mul_generator_of_descending_support (basis : FreeGroupBasis X F) (X₀ : Set X) [PartialOrder X₀] [WellFoundedGT X₀] (p q : X₀ → F) (hp : ∀ x : X₀, basis.HasDescendingSupport X₀ x (p x)) (hq : ∀ x : X₀, basis.HasDescendingSupport X₀ x (q x)) : ∃ α : MulAut F, (∀ x : X₀, α (basis x) = p x * basis x * q x) ∧ ∀ x ∈ X₀ᶜ, α (basis x) = basis x

Proposition 1.7.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-4: if S is quadratic over the basis X, connected via its incidence graph, and infinite, then some automorphism of F carries S into the chosen basis subset.

universe u v variable {X : Type u} {F : Type v} [Group F] theorem exists_automorphism_image_subset_basis_range_of_quadratic_connected_infinite (basis : FreeGroupBasis X F) (S : Set F) (hquadratic : IsQuadraticWordSet basis S) (hconnected : (wordIncidenceGraph basis S).Connected) (hinfinite : S.Infinite) : ∃ α : MulAut F, α '' S ⊆ Set.range basis

Proposition 1.7.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-5: if S is quadratic over the chosen basis, not strictly quadratic, finite, and connected, then some automorphism of F sends S into the chosen basis subset.

universe u v variable {X : Type u} {F : Type v} [Group F] theorem exists_automorphism_image_subset_basis_range_of_quadratic_connected_finite_nonstrict (basis : FreeGroupBasis X F) (S : Set F) (hquadratic : IsQuadraticWordSet basis S) (hnotstrict : ¬ IsStrictlyQuadraticWordSet basis S) (hfinite : S.Finite) (hconnected : (wordIncidenceGraph basis S).Connected) : ∃ α : MulAut F, α '' S ⊆ Set.range basis

Proposition 1.7.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-6 (1): a finite connected strictly quadratic set of words in FreeGroup X is automorphically equivalent to one whose members are singleton generators together with one terminal word x₁ ⋯ xₖ q, where q is either a product of commutators or a product of squares on generators disjoint from the singleton part.

universe u open scoped commutatorElement open FreeGroupBasis variable {X : Type u} [DecidableEq X] local notation "basis" => FreeGroupBasis.ofFreeGroup X -- Layer triage: -- `source-facing`: finite connected strictly quadratic word systems in `FreeGroup X`, their -- automorphic normalization, and the attached elementary transformation relation used in -- Proposition `1-7-6 (2)`. -- `core/canonical`: `FreeGroupBasis.ofFreeGroup X`, `IsQuadraticWordSet`, -- `IsStrictlyQuadraticWordSet`, `wordIncidenceGraph`, -- `basis.elementaryNielsenTransvection`, `Finset.image`, `List.IsInfix`, and -- `Relation.ReflTransGen`. -- `bridge/view`: the finite-set strictness predicate below is the thin bridge from -- `Finset (FreeGroup X)` to the owner Section 7 API on `Set (FreeGroup X)` for the canonical -- basis of `FreeGroup X`. -- Domain sampling: -- 1. `FreeGroupBasis.ofFreeGroup X` is the canonical basis owner of `FreeGroup X`. -- 2. `IsQuadraticWordSet` from Proposition `1-7-4` is the owner predicate for the per-word -- quadraticity and two-word incidence conditions. -- 3. `IsStrictlyQuadraticWordSet` from Proposition `1-7-5` is the owner predicate for the -- `0-or-2` word-incidence condition on each basis generator. -- 4. `basis.elementaryNielsenTransvection` from Proposition `1-4-1`, -- `wordIncidenceGraph`, `List.IsInfix`, and `Relation.ReflTransGen` are the canonical owners -- for attached regular Nielsen steps, connectedness, contiguous reduced subwords, and finite -- transformation sequences. -- Primitive vs. derived: -- the primitive source data are the finite word system `S : Finset (FreeGroup X)` and, for the -- second clause, the one-step attached elementary transformation relation. Strict quadraticity, -- connectedness, automorphic images, and finite-step reachability are derived from the owner -- abstractions above. theorem exists_automorphicImage_standardQuadraticForm (S : Finset (FreeGroup X)) (hS : IsStrictlyQuadraticSet S) (hconn : (wordIncidenceGraph basis (S : Set (FreeGroup X))).Connected) : ∃ α : MulAut (FreeGroup X), IsStandardQuadraticWordSystem (S.image α)

Proposition 1.7.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-7: if a finite strictly quadratic word system S is connected, is minimal, and contains every generator of X, then its Whitehead graph Σ(S) is connected.

universe u variable {X : Type u} local notation "basis" => FreeGroupBasis.ofFreeGroup X open FreeGroup.Finset -- Layer triage: -- `source-facing`: a finite strictly quadratic word system `S : Finset (FreeGroup X)` together -- with the textbook connectedness, minimality, and full-support hypotheses. -- `core/canonical`: `Finset (FreeGroup X)` together with `IsStrictlyQuadraticSet`, -- `FreeGroup.Finset.sigmaGraph`, `FreeGroup.Finset.IsMinimal`, -- `FreeGroup.Finset.ContainsAllGenerators`, and the owner connectedness predicate -- `(wordIncidenceGraph basis (S : Set (FreeGroup X))).Connected` from the surrounding Section 7 -- files. -- `bridge/view`: the Whitehead-move proof sketch is mediated by the canonical owner predicate -- `FreeGroup.Finset.IsMinimal`, whose automorphic-orbit formulation is the chapter's stable -- interface for -- minimality. -- -- Domain sampling: -- 1. `IsStrictlyQuadraticSet` from Proposition `1-7-6` is the chapter owner predicate for the -- strict quadraticity hypothesis of Section 7. -- 2. `wordIncidenceGraph basis` from Proposition `1-7-4` is the owner graph construction for the -- connectedness of a finite word system. -- 3. `FreeGroup.Finset.sigmaGraph` from Proposition `1-7-8` is the owner construction for the -- Whitehead graph attached to such a system. -- 4. `FreeGroup.Finset.IsMinimal` and `FreeGroup.Finset.ContainsAllGenerators` from Proposition -- `1-7-8` are the canonical owner predicates for minimality in the automorphic orbit and for -- full generator support. -- Best owner abstraction: -- the Section 7 finite-word-system API on `Finset (FreeGroup X)` consisting of -- `IsStrictlyQuadraticSet`, `sigmaGraph S`, `IsMinimal S`, `ContainsAllGenerators S`, and the -- owner connectedness predicate `(wordIncidenceGraph basis (S : Set (FreeGroup X))).Connected`. -- -- Primitive vs. derived: -- the primitive data here are only the finite word system `S` and the source-facing hypotheses of -- strict quadraticity, connectedness, minimality, and full support; the Whitehead graph is reused -- from the existing owner API. theorem sigmaGraph_connected_of_connected_minimal_contains_all_generators [Finite X] (S : Finset (FreeGroup X)) (hstrict : IsStrictlyQuadraticSet S) (hconnected : (wordIncidenceGraph basis (S : Set (FreeGroup X))).Connected) (hminimal : IsMinimal S) (hcontains : ContainsAllGenerators S) : (sigmaGraph S).Connected

Proposition 1.7.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-8 (1): if the Whitehead graph Σ(S) of a finite strictly quadratic system is connected, then the system S is connected.

universe u open scoped BigOperators variable {X : Type u} local notation "basis" => FreeGroupBasis.ofFreeGroup X namespace FreeGroup namespace Finset theorem sigmaGraph_connected_implies_connected [Finite X] (S : Finset (FreeGroup X)) (hσ : (sigmaGraph S).Connected) : (wordIncidenceGraph basis (S : Set (FreeGroup X))).Connected

Proposition 1.7.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-9: if σ is an attached elementary Nielsen transformation of the finite strictly quadratic set S of reduced cyclic words, then either |Sσ| = |S| and k(Sσ) = k(S), or |Sσ| = |S| - 2 and k(Sσ) = k(S) - 1.

universe u open scoped Classical open FreeGroupBasis variable {X : Type u} local notation "basis" => FreeGroupBasis.ofFreeGroup X open CyclicWord.Finset theorem attachedElementaryNielsenTransformation_totalLength_cycleCount_outcome {S S' : Finset (CyclicWord X)} (hstrict : IsStrictlyQuadratic S) (hstep : AttachedElementaryNielsenTransformation S S') : (totalLength S' = totalLength S ∧ cycleCount S' = cycleCount S) ∨ (totalLength S' = totalLength S - 2 ∧ cycleCount S' = cycleCount S - 1)

Proposition 1.7.10

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-10: if S is a finite strictly quadratic system of cyclic words, and S' is obtained from S by deleting a part l l⁻¹, then k(S') = k(S) - 1 provided that the exceptional word l l⁻¹ is not itself a member of S. The source hypothesis that S is not reduced is omitted from the interface because it already follows from the deletion hypothesis.

universe u open Finset List SimpleGraph open scoped BigOperators variable {α : Type u} [DecidableEq α] -- Layer triage for Proposition 1-7-10: -- `source-facing`: finite strictly quadratic systems of signed cyclic words, deletion of one -- adjacent cancellation part `l l⁻¹`, and the Whitehead-graph component count `k(S)`. -- `core/canonical`: `SignedLetter α` from Proposition `1-7-8`, `Cycle (SignedLetter α)` for the -- unreduced cyclic-word model, and the reduced-system owner `CyclicWord.Finset.cycleCount` from -- Proposition `1-7-9`. -- `bridge/view`: the raw `Cycle` support and edge formulas from Proposition `1-7-11` are reused -- only because this proposition is genuinely about the unreduced side of the cancellation move; -- no extra local reduced-system packaging is kept here. -- Domain sampling: -- 1. `SignedLetter α` from Proposition `1-7-8` is the shared signed-letter vocabulary for -- Section 7 cyclic-word constructions. -- 2. `Cycle.whiteheadEdges` from Proposition `1-7-11` is the raw one-word edge formula reused -- only because this proposition is stated for unreduced cyclic systems. -- 3. `Cycle.whiteheadSupport` from Proposition `1-7-11` is the corresponding raw support -- construction, so the system support is likewise a finite union. -- 4. `CyclicWord.Finset.cycleCount` from Proposition `1-7-9` is the chapter owner once a system -- is already reduced, so this file should avoid keeping a parallel reduced-system bridge API. -- Primitive vs. derived: -- the primitive data here are only `S`, `S'`, and the signed letter `l`; the Whitehead edges of -- one word are reused from Proposition `1-7-11`, while system strict quadraticity, the -- Whitehead graph, and one-step cancellation deletion are derived directly on the raw -- finite-system owner `Cycle.Finset`. open Cycle Cycle.Finset theorem cycleCount_eq_sub_one_of_delete_cancellation_part (S S' : Finset (Cycle (SignedLetter α))) (l : SignedLetter α) (hquad : IsStrictlyQuadratic S) (hdelete : DeletesCancellationPart S l S') (hnot_exceptional : cancellationPair l ∉ S) : cycleCount S' = cycleCount S - 1

Proposition 1.7.11

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-11: if q is a minimal strictly quadratic cyclic word and x occurs in q, then setting x equal to 1 either makes the cyclic length drop by 2 and changes k by at most 1, or makes the cyclic length drop by 4 and leaves k unchanged.

universe u open Finset List SimpleGraph open scoped BigOperators variable {X : Type u} theorem specializeAtOne_length_cycleCount_outcome (q : CyclicWord X) (x : X) (hq : q.IsMinimalStrictlyQuadratic) (hx : x ∈ q.letters) : ((CyclicWord.specializeAtOne q x).length = q.length - 2 ∧ |(CyclicWord.specializeAtOne q x).cycleCount - q.cycleCount| ≤ 1) ∨ ((CyclicWord.specializeAtOne q x).length = q.length - 4 ∧ (CyclicWord.specializeAtOne q x).cycleCount = q.cycleCount)

Proposition 1.7.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-12: if q is a minimal strictly quadratic cyclic word and q' is obtained from q by a Section 7 attached-transformation sequence containing exactly one singular transformation, then the cyclic length drops by 2 or by 4.

universe u variable {X : Type u} -- Layer triage: -- `source-facing`: minimal strictly quadratic cyclic words together with the Section 7 counted -- attached-transformation sequences. -- `core/canonical`: `CyclicWord X`, its canonical length function, the canonical cyclic-word -- action `CyclicWord.map`, the owner specialization `specializeAtOne` from Proposition `1-7-11`, -- and `Relation.ReflTransGen` as the owner of finite step sequences. -- `bridge/view`: the regular one-word step is the singleton specialization of the set-level -- attached Nielsen move from Proposition `1-7-9`, while singular steps directly use the owner -- specialization operation from Proposition `1-7-11` together with the explicit occurrence -- condition on the specialized generator. -- Domain sampling: -- 1. `AttachedElementaryNielsenTransformation` from Proposition `1-7-9` is the chapter owner -- pattern for regular attached transformations on cyclic-word sets; the counted step relation -- below reuses it through singleton sets. -- 2. `CyclicWord.specializeAtOne` and `CyclicWord.IsMinimalStrictlyQuadratic` from Proposition -- `1-7-11` -- provide the chapter owner specialization language and the main single-word hypothesis. -- 3. `specializeAtOne_length_eq_sub_two_or_sub_four` from Proposition `1-7-11` is the -- chapter's exact single-word length-drop theorem reused at the singular step. -- 4. `Relation.ReflTransGen` from mathlib is the canonical owner for finite transformation -- sequences. -- Primitive vs. derived: -- the primitive Section 7 data are the regular singleton attached move and the owner -- specialization `specializeAtOne`, assembled into the one-step relation -- `AttachedTransformationStep`. The counted sequence relation then reuses the same primitive data -- with the singular-step count adjoined before applying `Relation.ReflTransGen`. theorem length_eq_sub_two_or_sub_four_of_minimal_strictly_quadratic_and_single_singular_sequence {q q' : CyclicWord X} (hq : q.IsMinimalStrictlyQuadratic) (hqq' : AttachedTransformationSequenceWithSingularCount q 1 q') : q'.length = q.length - 2 ∨ q'.length = q.length - 4

Proposition 1.7.13

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-13: if q is a minimal strictly quadratic cyclic word and q uses every generator of the ambient alphabet, then the irreducibility rank of its represented relator set is the greatest integer in one quarter of the cyclic length of q.

universe u open scoped RelatorSetIr variable {X : Type u} -- Layer triage: -- `source-facing`: a single minimal strictly quadratic cyclic word `q`, together with the -- hypothesis that `q` uses every generator of the ambient alphabet, and the irreducibility rank -- of the represented relator set. -- `core/canonical`: `CyclicWord X`, its canonical length `CyclicWord.length`, -- `CyclicWord.HasFullSupport`, `ConjClasses (FreeGroup X)` with the owner set view -- `ConjClasses.carrier`, and the relator-set owner notation `Ir(W)` in the ambient free group. -- `bridge/view`: a single cyclic word determines its represented relator set -- `(q.toConjClasses).carrier`, obtained from the canonical conjugacy-class bridge -- `q.toConjClasses`; the full-support hypothesis is the bridge ensuring that this ambient free -- group has no unused generators beyond the letters of `q`. -- Domain sampling: -- 1. `CyclicWord` from Definition `1-4-17` is the chapter owner abstraction for cyclic words. -- 2. `CyclicWord.toConjClasses` from Definition `1-4-17` is the canonical bridge from one cyclic -- word to its conjugacy class in `FreeGroup X`. -- 3. `ConjClasses.carrier` with `ConjClasses.mem_carrier_iff_mk_eq` is the canonical owner API -- for the represented relator set of a conjugacy class. -- 4. `CyclicWord.HasFullSupport` from Definition `1-4-17` is the owner predicate asserting that -- the ambient alphabet contributes no unused free generators. -- 5. `CyclicWord.IsMinimalStrictlyQuadratic` from Proposition `1-7-11` is the chapter owner -- predicate for the textbook single-word hypothesis. -- 6. `Ir(W)` from Proposition `1-6-13` is the existing relator-set owner abstraction for -- irreducibility rank, so this file should reuse it directly rather than introduce a parallel -- cyclic-word owner with the wrong ambient alphabet. -- Primitive vs. derived: -- the primitive data here are only the cyclic word `q`; the represented relator set -- `(q.toConjClasses).carrier` and its irreducibility rank are canonical derived owner views. namespace CyclicWord theorem ir_eq_length_div_four_of_minimal_strictlyQuadratic (q : CyclicWord X) (hq : q.IsMinimalStrictlyQuadratic) (hfull : q.HasFullSupport) : Ir((q.toConjClasses).carrier) = ↑(q.length / 4)

Proposition 1.7.14

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-7-14: if S is a finite minimal strictly quadratic set of cyclic words, then its irreducibility rank is one quarter of its total cyclic length, rounded down.

open scoped BigOperators Classical open scoped RelatorSetIr universe u variable {X : Type u} -- Layer triage: -- `source-facing`: a finite set `S` of cyclic words, its minimality under regular -- transformations, its strict quadraticity, and the associated irreducibility rank `Ir(S)`. -- `core/canonical`: `Finset (CyclicWord X)` as the finite-set owner, `CyclicWord.Finset` from -- Proposition `1-7-9`, `CyclicWord.toConjClasses` as the canonical passage from cyclic words to -- conjugacy classes in `FreeGroup X`, `ConjClasses.carrier` as the canonical relator-set view of -- one conjugacy class, and `Ir(W)` from Proposition `1-6-13`. -- `bridge/view`: a finite set of cyclic words determines the relator set of all free-group -- elements whose conjugacy classes are represented by members of the set; minimality is measured -- by the total cyclic length along the canonical automorphism action on cyclic words. -- Domain sampling: -- 1. `Finset (CyclicWord X)` is the canonical owner abstraction for a finite set of cyclic words. -- 2. `CyclicWord.Finset.totalLength` and `CyclicWord.Finset.IsStrictlyQuadratic` from -- Proposition `1-7-9` are the finite-system owner invariants used here. -- 3. `CyclicWord.toConjClasses` is the canonical bridge from a cyclic word to one conjugacy -- class in `FreeGroup X`. -- 4. `ConjClasses.carrier` with `ConjClasses.mem_carrier_iff_mk_eq` is the canonical owner API -- for the represented relator set of one conjugacy class. -- 5. `Ir(W)` from Proposition `1-6-13` is the existing owner abstraction for irreducibility rank. -- Primitive vs. derived: -- the primitive data are only the finite set `S` of cyclic words. The ambient relator set, -- irreducibility rank, total cyclic length, strict quadraticity, and the orbitwise minimality -- predicate are derived canonically from that data. namespace CyclicWord namespace Finset theorem ir_eq_totalLength_div_four_of_minimal_strictlyQuadratic (S : Finset (CyclicWord X)) (hminimal : IsMinimal S) (hstrict : IsStrictlyQuadratic S) : ir S = ((totalLength S / 4 : ℕ) : ℕ∞)

1.8 — Equations in Free Groups

Proposition 1.8.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-8-1: if a Section 8 ambient word maps to 1 under every induced homomorphism coming from a split retraction of R onto the infinite cyclic group, and those induced maps separate points of F ∗ R, then the word itself is 1.

universe u v open scoped Monoid.Coprod open Monoid.Coprod variable {F : Type u} {R : Type v} variable [Group F] [Group R] -- Primary domain: Section `8` ambient words in the free product `F ∗ R` and the canonical induced -- coproduct maps obtained from split retractions of the parameter group `R` onto the infinite -- cyclic group. -- Layer triage: -- `source-facing`: a Section `8` ambient word `w : F ∗ R` together with the assertion that if all -- its specializations along split retractions `R ⟶ Multiplicative ℤ` are trivial, then `w = 1`. -- `core/canonical`: `F ∗ R` is the owner ambient object, `map (MonoidHom.id F)` is the canonical -- induced coproduct map from a homomorphism on the parameter factor, and a split retraction is -- recorded canonically by its homomorphism, section, and the identity `hom.comp section_ = id`. -- `bridge/view`: later one-variable evaluation in Proposition `1-8-3` composes this canonical -- induced map with `lift (MonoidHom.id F) (zpowersHom F x)`, but that evaluation layer is derived -- from the coproduct owner map below. -- Domain sampling: -- 1. `F ∗ R` is the chapter/mathlib owner for Section `8` parametric words; compare Proposition -- `1-8-3`. -- 2. `map (MonoidHom.id F)` is the canonical induced map on a coproduct word when only the -- parameter factor changes. -- 3. The canonical algebraic content of a split retraction is a homomorphism with a specified -- section and identity equation, avoiding the earlier existential witness packaging. -- 4. Proposition `1-8-3` evaluates parametric words by first applying exactly this coproduct map -- and then the one-variable evaluation homomorphism. -- Primitive vs. derived: -- the primitive source data are the ambient word `w : F ∗ R` and the split retractions of `R` -- onto `Multiplicative ℤ`. The induced coproduct homomorphism is derived canonically by -- `Monoid.Coprod.map`; there is no extra wrapper predicate in the public API beyond the -- proposition's own statement. theorem eq_one_of_forall_induced_retraction_eq_one (hsep : (inducedRetractionMaps F R).SeparatesPoints) (w : F ∗ R) (hw : ∀ ρ : SplitToInfiniteCyclic R, inducedSplitRetraction ρ w = 1) : w = 1

Proposition 1.8.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-8-2: in the Section 8 ambient free product F ∗ R, the word problem is decidable once one can decide whether a word maps to 1 under every induced homomorphism coming from a split retraction of R onto the infinite cyclic group, provided those induced maps separate points of F ∗ R.

universe u v open scoped Monoid.Coprod variable {F : Type u} {R : Type v} variable [Group F] [Group R] -- Layer triage: -- `source-facing`: the word problem in the Section `8` ambient free product `F ∗ R`, tested via -- the canonical induced coproduct maps attached to split retractions of `R`. -- `core/canonical`: Proposition `1-8-1` is the owner implication from the universal induced test -- to `w = 1` under the canonical point-separation hypothesis on those maps, -- `inducedSplitRetraction` is the induced coproduct map, `inducedRetractionMaps` is the -- associated family of functions, and `DecidablePred` is Lean's canonical interface for -- decidability of the word problem. -- `bridge/view`: the universal induced-retraction test is the contraposed form of Proposition -- `1-8-1`, derived internally here rather than exposed as a second public owner theorem. -- Domain sampling: -- 1. Proposition `1-8-1` supplies the owner implication from the universal test to `w = 1`. -- 2. `SplitToInfiniteCyclic R` is the chapter owner vocabulary for the split retractions tested in -- Section `8`. -- 3. `Set.SeparatesPoints` is mathlib's owner abstraction for the missing separation hypothesis on -- a family of functions. -- 4. `DecidablePred` is the canonical owner API for a solvable yes/no problem on a fixed type. @[reducible] def word_problem_decidable_of_decidable_induced_retraction_test (hsep : (inducedRetractionMaps F R).SeparatesPoints) (htest : DecidablePred fun w : F ∗ R ↦ ∀ ρ : SplitToInfiniteCyclic R, inducedSplitRetraction ρ w = 1) : DecidablePred fun w : F ∗ R ↦ w = 1

Proposition 1.8.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-8-3: for a one-variable equation equation : F ∗ Multiplicative ℤ over a free group F, there exists a finite set of Section 8 parametric words whose value sets cover exactly the solution set of equation.

universe u v open scoped Monoid.Coprod open Monoid.Coprod variable {F : Type u} [Group F] theorem exists_finite_parametric_word_set [IsFreeGroup F] (equation : F ∗ Multiplicative ℤ) : ∃ W : Set (ParametricWord F), W.Finite ∧ (⋃ paramWord ∈ W, paramWord.valueSet) = equationSolutionSet equation

Proposition 1.8.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-8-4: an element of a free group is a commutator exactly when some cyclically reduced conjugate has cyclic word u v w u⁻¹ v⁻¹ w⁻¹ for suitable blocks u, v, and w. The statement is phrased using the canonical cyclic word of the conjugacy class of g.

universe u variable {X : Type u} -- Layer triage: -- `source-facing`: an element `g : FreeGroup X` together with a cyclically reduced conjugate whose -- canonical cyclic word has the textbook Wicks form `u v w u⁻¹ v⁻¹ w⁻¹`. -- `core/canonical`: mathlib's owner notion `commutatorSet (FreeGroup X)` for “`g` is a -- commutator”. -- `bridge/view`: the chapter owner `CyclicWord X` for cyclically reduced conjugacy data, together -- with `CyclicWord.conjClassesEquiv` and the cycle quotient `Cycle (X × Bool)`. -- Domain sampling: -- 1. `commutatorSet (FreeGroup X)` with `mem_commutatorSet_iff` is the owner abstraction for the -- statement that `g` is a commutator. -- 2. `CyclicWord X` from Definition `1-4-17` is the chapter owner abstraction for cyclically -- reduced words modulo cyclic permutation. -- 3. `CyclicWord.toConjClasses` is the canonical bridge from a reduced cyclic word to the -- conjugacy class it represents. -- 4. `CyclicWord.conjClassesEquiv` is the owner equivalence showing that the cyclic-word witness -- is canonically determined by the conjugacy class of `g`, so an existential witness should -- not remain primitive public data. -- Primitive vs. derived: -- the primitive data are only the element `g` and the Wicks-form predicate on its canonical cyclic -- word. The concrete six-block list is bridge-level data inside the cyclic-word owner, and the -- cyclic-word witness itself is derived from `CyclicWord.conjClassesEquiv`. theorem mem_commutatorSet_iff_exists_reduced_triple_factorization (g : FreeGroup X) : g ∈ commutatorSet (FreeGroup X) ↔ (CyclicWord.conjClassesEquiv.symm (ConjClasses.mk g)).HasWicksTripleFactorization

Proposition 1.8.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-8-5: for a fixed binary word w, there is an algorithm deciding whether a signed word on X represents an element of the value set of w in the canonical free group FreeGroup X.

universe u v open MulEquiv variable {F : Type u} {G : Type v} [Group F] [Group G] -- Layer triage: -- `source-facing`: a binary word `w : FreeGroup (Fin 2)` together with its value set in the free -- group `F` under all substitutions of the two generators. -- `core/canonical`: `FreeGroup (Fin 2)` is the owner object of binary words, `FreeGroup.lift` is -- the owner abstraction turning a substitution `Fin 2 → F` into the corresponding evaluation -- homomorphism, and `Set.range` is the canonical owner of the resulting value set in `F`. -- `bridge/view`: the equivalent homomorphism-level formulation -- `∃ φ : FreeGroup (Fin 2) →* F, φ w = g`, and transport of the value set across `MulEquiv`s. -- Domain sampling: -- 1. `FreeGroup (Fin 2)` is the canonical owner of words in two generators. -- 2. `FreeGroup.lift` is the canonical evaluation map determined by a substitution -- `Fin 2 → F`. -- 3. `Set.range` is the chapter/mathlib owner construction for a value set; compare -- `ParametricWord.valueSet` in Proposition `1-8-3`. -- 4. `FreeGroup.mk` is the canonical bridge from signed words to elements of a concrete free -- group, and `ComputablePred` is the chapter owner for algorithmic membership on such coded -- inputs. -- Primitive vs. derived: -- the primitive source data are only the word `w`, the ambient group `F`, and a substitution -- `x : Fin 2 → F`; the homomorphism `FreeGroup.lift x`, the existential homomorphism -- formulation `∃ φ, φ w = g`, and any later computability interface on coded free-group words are -- derived API from the owner set below. variable {X : Type u} [Primcodable X] theorem computable_represents_element_of_binaryWordValueSet (w : FreeGroup (Fin 2)) : ComputablePred fun L : List (X × Bool) ↦ FreeGroup.mk L ∈ binaryWordValueSet w

1.9 — Abstract Length Functions

Proposition 1.9.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-9-1 (1): a group carrying an abstract length function satisfying axioms A0 through A4 is a free group.

universe u open scoped Classical variable {G : Type u} [Group G] open scoped AbstractLengthFunction theorem isFreeGroup_of_abstractLengthFunction (length : G → ℕ) [IsAbstractLengthFunction length] : IsFreeGroup G

Proposition 1.9.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-9-2: a group carrying a Section 9 length function satisfying axioms A1 through A5 admits an injective homomorphism into a free product whose canonical syllable-length restricts to the given length function.

universe u v w open scoped AbstractLengthFunction variable {G : Type u} [Group G] theorem exists_freeProduct_embedding_preserving_length (length : G → ℕ) [IsFreeProductLengthFunction length] : ∃ (ι : Type v) (factors : ι → Type w), ∃ _ : ∀ i, Group (factors i), ∃ φ : G →* Monoid.CoprodI factors, Function.Injective φ ∧ ∀ g : G, length g = Monoid.CoprodI.syllableLength (φ g)

Proposition 1.9.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-9-3: in the abstract-length-function setting of Section 9, every maximal abelian subgroup is additively isomorphic to an additive subgroup of ℝ.

universe u open AddSubgroup open scoped IsMulCommutative variable {G : Type u} [Group G] theorem maximal_abelian_subgroup_addEquiv_addSubgroup_real (length : G → ℕ) [IsAbstractLengthFunction length] (A : Subgroup G) (hA : IsMulCommutative A) (hcentralizer : Subgroup.centralizer (A : Set G) ≤ A) : ∃ H : AddSubgroup ℝ, Nonempty (Additive A ≃+ H)

Proposition 1.9.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Canonical strengthening of Proposition 1-9-4: the subgroup generated by a and b is itself free. The textbook disjunction is obtained by taking the left branch.

universe u open scoped IsMulCommutative variable {G : Type u} [Group G] theorem two_generated_subgroup_isFreeGroup_of_abstractLengthFunction (L : G → ℕ) [IsAbstractLengthFunction L] (a b : G) : IsFreeGroup (Subgroup.closure ({a, b} : Set G))

1.10 — Representations of Free Groups; the Fox Calculus

Proposition 1.10.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-10-1: if F is free on the basis basis : FreeGroupBasis (Fin n) F, then the Magnus map sending basis i to 1 + X i in the noncommutative formal power series Magnus target is injective, hence identifies F with a subgroup of its unit group.

universe u open FreeMonoid variable {n : ℕ} variable {F : Type u} [Group F] theorem foxMagnusHom_injective (basis : FreeGroupBasis (Fin n) F) : Function.Injective (foxMagnusHom basis)

Proposition 1.10.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-10-2: the intersection of the terms of the descending central series of a free group is trivial. In mathlib's indexing this is the infimum of lowerCentralSeries F m, since lowerCentralSeries F 0 = F and lowerCentralSeries F (m + 1) = ⁅lowerCentralSeries F m, ⊤⁆. The textbook finite-rank hypothesis and the choice of a basis are redundant for this statement, so the theorem is stated directly under the owner assumption [IsFreeGroup F].

universe u open QuotientGroup variable {F : Type u} [Group F] [IsFreeGroup F] theorem iInf_lowerCentralSeries_eq_bot_of_isFreeGroup : (⨅ m : ℕ, Subgroup.lowerCentralSeries F m) = (⊥ : Subgroup F)

Proposition 1.10.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-10-3, first inclusion: the (n + 1)st textbook lower-central term lies in the Magnus/Fox filtration term L_{n + 1}(G).

universe u variable {G : Type u} [Group G] theorem lowerCentralSeries_le_foxMagnusSeries (n : ℕ) : lowerCentralSeries G n ≤ foxMagnusSeries G (n + 1)

Definition 1.10.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-10-4: a Fox derivation of the integral group ring of the free group on X is a ℤ-linear endomorphism satisfying the Fox product rule D (u * v) = ε(v) • D u + u * D v for all u and v, where ε is the augmentation morphism of the group ring. This rule already forces D 1 = 0; see IsFoxDerivation.map_one_eq_zero.

universe u -- Declarations for this item will be appended below by the statement pipeline. variable {X : Type u} local notation "R" => FreeGroupRing X local notation "ε" => Bialgebra.counitAlgHom ℤ R def IsFoxDerivation (D : Module.End ℤ (FreeGroupRing X)) : Prop := ∀ u v : R, D (u * v) = ε v • D u + u * D v

Definition 1.10.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-10-5: the Fox derivative of w with respect to the generator x, defined as the x-coordinate of the universal Fox differential from Proposition 1-10-6.

universe u variable {X : Type u} local notation "R" => FreeGroupRing X abbrev foxDerivative (x : X) (w : FreeGroup X) : R := foxUniversalDifferential w x

Proposition 1.10.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-10-6 lies in Fox calculus for free groups. Layer triage: - source-facing: the faithful Fox triangular representation of FreeGroup X. - core/canonical: MonoidAlgebra.comapDistribMulActionSelf, the induced Finsupp action on the Fox module, FreeGroup.lift, and SemidirectProduct.rightHom. - bridge/view: the universal differential as the left coordinate of the triangular map, together with the pair formula (d w, w). Domain sampling: 1. MonoidAlgebra.comapDistribMulActionSelf is the mathlib owner for left multiplication of FreeGroup X on its integral group ring. 2. X →₀ FreeGroupRing X inherits the coefficientwise owner action from that ring action, so the previous hand-written smul helper was duplicate surface. 3. FreeGroup.lift is the owner abstraction for defining the representation from its generator values. 4. SemidirectProduct.rightHom is the owner projection detecting faithfulness. Primitive vs. derived: the primitive public data are the Fox module, the semidirect-product target, and the triangular representation; the universal differential and the pair description are derived coordinate API.

universe u instance (X : Type u) : DistribMulAction (FreeGroup X) (FreeGroupRing X)

Definition 1.10.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-10-7: the second Magnus representation is the canonical Fox triangular representation of the free group.

universe u variable {X : Type u} #check foxTriangularRepresentation

1.11 — Free Products with Amalgamation

Remark 1.11.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Remark 1-11-1: for the example group G* = <a, d | a^3, d⁻¹ a d = a⁻¹>, the quotient by its center has the same cardinality as DihedralGroup 3.

namespace OrderThreeInversionExample open OrderThreeInversionGenerator theorem centerQuotient_natCard_eq_dihedral_natCard : Nat.card centerQuotient = Nat.card (DihedralGroup 3)

Definition 1.11.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Definition 1-11-2: for a chosen transversal in an amalgamated product, the length of an element is the number of non-base syllables in its normal form; equivalently, elements of the amalgamated subgroup have length 0.

universe u v w open Monoid namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} noncomputable abbrev syllableLength (d : NormalWord.Transversal φ) (u : PushoutI φ) : ℕ := let _ : DecidableEq ι := Classical.decEq ι let _ : ∀ i, DecidableEq (G i) := fun i ↦ Classical.decEq (G i) let w : NormalWord d := NormalWord.equiv u w.syllableLength

Lemma 1.11.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-3 (1): if A p_t < A q_t and |h_t| = 0, then the full word factors as z * q_t * a_t for some prefix z.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord variable {n : ℕ} variable (d : Transversal φ) (A_lt : PushoutI φ → PushoutI φ → Prop) variable (u a p h q : Fin (n + 1) → PushoutI φ) theorem exists_prefix_mul_last_q_mul_last_a_of_terminal_drop_case (hchain : IsSection11ReductionChain d A_lt u a p h q) (hdrop : A_lt (p (Fin.last n)) (q (Fin.last n))) (hhlast : syllableLength d (h (Fin.last n)) = 0) : ∃ z : PushoutI φ, interleavedProd u a = z * q (Fin.last n) * a (Fin.last n)

Lemma 1.11.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-4: if g is a Section 11 bridge step for v, and v = r⁻¹ * k * s is a balanced decomposition with k either in one factor range outside the amalgamated subgroup or equal to 1, then g * v admits a decomposition with the same right factor s, the left factor either unchanged or shifted to r * g⁻¹, the same syllable length as r, and the middle term staying in the same factor subgroup outside the amalgamated subgroup unless both middle terms are trivial.

universe u v w namespace Monoid.PushoutI open Monoid open NormalWord variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} theorem exists_left_mul_decomposition_of_eq_inv_mul_of_factor_or_one (d : Transversal φ) {g v r k s : PushoutI φ} (hg : IsSection11BridgeStep d v g) (hv : v = r⁻¹ * k * s) (hrs : syllableLength d r = syllableLength d s) (hk : (∃ ν : ι, k ∈ (of ν).range ∧ k ∉ (base φ).range) ∨ k = 1) : ∃ r' k' : PushoutI φ, g * v = r'⁻¹ * k' * s ∧ (r' = r ∨ r' = r * g⁻¹) ∧ syllableLength d r' = syllableLength d r ∧ ((∃ ν : ι, (k ∈ (of ν).range ∧ k ∉ (base φ).range) ∧ k' ∈ (of ν).range ∧ k' ∉ (base φ).range) ∨ (k = 1 ∧ k' = 1))

Proposition 1.11.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-11-5 in primitive form: any common predecessor of C₁ and C₂ receives the intersection subgroup Γ C₁ ⊓ Γ C₂.

universe u v namespace Subgroup variable {G : Type u} [Group G] variable {α : Type v} [Preorder α] theorem inf_le_of_common_predecessor {Γ : α → Subgroup G} (hΓ : Antitone Γ) {C₁ C₂ D : α} (hDC₁ : D ≤ C₁) (hDC₂ : D ≤ C₂) : Γ C₁ ⊓ Γ C₂ ≤ Γ D

Proposition 1.11.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-11-6: saying that G has presentation (U; R₁, R₂) adds no new owner beyond mathlib's canonical presented-group construction. Accordingly, the file keeps the direct recall PresentedGroup (R₁ ∪ R₂) ≃* G rather than a parallel local wrapper for “G has presentation (U; R₁, R₂)”.

universe u v variable {U : Type u} (G : Type v) [Group G] variable (R₁ R₂ : Set (FreeGroup U)) #check (PresentedGroup (R₁ ∪ R₂) ≃* G)

Lemma 1.11.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-7 (1): if u = p⁻¹ * h * p and v = q⁻¹ * k * q are conjugates of elements in factor ranges but outside the amalgamated subgroup, their product lies in the Section 11 subset U, and the conjugators p and q have the same syllable length, then the two core elements come from the same factor.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord theorem equal_length_conjugates_share_factor_of_product_mem_U (d : Transversal φ) {μ ν : ι} {u v h k p q : PushoutI φ} (hu : u = p⁻¹ * h * p) (hv : v = q⁻¹ * k * q) (hhμ : h ∈ (of μ).range) (hhA : h ∉ (base φ).range) (hkν : k ∈ (of ν).range) (hkA : k ∉ (base φ).range) (huv : u * v ∈ shortSyllableConjugates d) (hpq : syllableLength d p = syllableLength d q) : μ = ν

Lemma 1.11.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-8: if u = p⁻¹ * h * p, if |h| = 1, and if u * a belongs to the Section 11 subset U, then the conjugate a^p lies in the amalgamated subgroup A. Here the canonical owner translation is: - |.| = syllableLength d, - A = (base φ).range, - U = shortSyllableConjugates d, - a ∈ A is represented primitively by a : H, - a^p = p⁻¹ * a * p is represented directly by the ambient group product.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord theorem conjugate_base_mem_base_range_of_mul_mem_shortSyllableConjugates (d : Transversal φ) {u h p : PushoutI φ} (a : H) (hu : u = p⁻¹ * h * p) (hh : syllableLength d h = 1) (hua : u * base φ a ∈ shortSyllableConjugates d) : p⁻¹ * base φ a * p ∈ (base φ).range

Lemma 1.11.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-9: if u = p⁻¹ * h * p and v = q⁻¹ * k * q are conjugates of elements from factor ranges but outside the amalgamated subgroup, and conjugation of u by v does not increase syllable length, then either u * v lies in the Section 11 subset U, or q is shorter than p and v⁻¹ * u * v is the conjugate of h by p * v, whose length is at most that of p.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord theorem mul_mem_U_or_conjugate_with_shorter_conjugator_of_conjugate_length_le (d : Transversal φ) {u v h k p q : PushoutI φ} (hu : u = p⁻¹ * h * p) (hv : v = q⁻¹ * k * q) (hh : ∃ μ : ι, h ∈ (of μ).range) (hhA : h ∉ (base φ).range) (hk : ∃ ν : ι, k ∈ (of ν).range) (hkA : k ∉ (base φ).range) (hshort : syllableLength d (v⁻¹ * u * v) ≤ syllableLength d u) : u * v ∈ shortSyllableConjugates d ∨ syllableLength d q < syllableLength d p ∧ syllableLength d (p * v) ≤ syllableLength d p ∧ v⁻¹ * u * v = (p * v)⁻¹ * h * (p * v)

Lemma 1.11.10

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-10: if an amalgamated-product element u is a conjugate p⁻¹ * h * p of a syllable-length-one element h, and conjugating u by a base element a strictly shortens its syllable length, then u itself has syllable length 1 and that base conjugate lies in the amalgamated subgroup.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord theorem syllableLength_eq_one_and_mem_base_of_conj_eq_of_lengthOne_of_baseConjugate_shorter (d : Transversal φ) {u h p : PushoutI φ} (hu : u = p⁻¹ * h * p) (hh : syllableLength d h = 1) (a : H) (hshort : syllableLength d ((base φ a)⁻¹ * u * base φ a) < syllableLength d u) : syllableLength d u = 1 ∧ (base φ a)⁻¹ * u * base φ a ∈ (base φ).range

Proposition 1.11.11

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-11-11, source-facing form: N is the tree product of Δ when there exists a compatible generating cocone of vertex embeddings over Δ with the tree-product universal property.

universe u v w x variable {Δ : TreeProductDiagram.{u, v, w}} {N : Type x} [Group N] namespace TreeProductDiagram variable (Δ : TreeProductDiagram.{u, v, w}) (N : Type x) [Group N] def IsTreeProductOf : Prop := ∃ T : TreeProductCocone Δ N, IsTreeProduct T

Lemma 1.11.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-12: Section 11's left-multiplication step is already encoded directly by the owner theorem on Monoid.PushoutI.

universe u v variable {G : Type u} [Group G] variable {I : Type v} #check Monoid.PushoutI.exists_left_mul_decomposition_of_eq_inv_mul_of_factor_or_one

Lemma 1.11.13

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-13 adds no new API beyond the owner theorem from Lemma 1-11-4, so this file keeps only a direct recall of that theorem.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord #check Monoid.PushoutI.exists_left_mul_decomposition_of_eq_inv_mul_of_factor_or_one

Lemma 1.11.14

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-14: if u belongs to the Section 11 subset U, v is strictly shorter than u, and the product u * v has length at most that of v, then the conjugate v⁻¹ * u * v is strictly shorter than u.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} theorem syllableLength_conj_lt_of_mem_shortSyllableConjugates_of_lt_of_mul_le (d : NormalWord.Transversal φ) {u v : PushoutI φ} (hu : u ∈ shortSyllableConjugates d) (hv : syllableLength d v < syllableLength d u) (huv : syllableLength d (u * v) ≤ syllableLength d v) : syllableLength d (v⁻¹ * u * v) < syllableLength d u

Lemma 1.11.15

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-15: if u belongs to the section-11 subset U and both v and u * v are strictly shorter than u, then the conjugate v⁻¹ * u * v is strictly shorter than u.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord -- Layer triage: -- `source-facing`: the Section `11` subset `U`, realized here by `shortSyllableConjugates d`, -- and the syllable-length inequalities on `u`, `v`, `u * v`, and the conjugate `v⁻¹ * u * v`. -- `core/canonical`: the amalgamated product owner `Monoid.PushoutI φ`, its group structure, and -- the canonical normal-form owner `NormalWord`. -- `bridge/view`: the chosen transversal `d`, which supplies the actual normal-form representative -- and hence the derived chapter length `syllableLength d`. -- -- Domain sampling: -- 1. `Monoid.PushoutI` is the mathlib/project owner abstraction for the amalgamated product. -- 2. `Monoid.PushoutI.NormalWord.Transversal` is the canonical chapter owner for the chosen -- normal-form data. -- 3. `Monoid.PushoutI.syllableLength` from Definition `1-11-2` is the owner length API attached -- to that transversal. -- 4. `Monoid.PushoutI.shortSyllableConjugates` from Lemma `1-11-14` is the upstream source-facing -- subset `U`, so this file should reuse it directly rather than restating the subset locally. -- -- Primitive vs. derived: -- the primitive data remain the pushout diagram `φ` and the chosen transversal `d`; the subset -- `shortSyllableConjugates d` and the length comparisons are derived API on that owner -- abstraction, so this lemma stays theorem-level and does not introduce any new wrapper data. -- Proof sketch: write `u = p⁻¹ * h * p` with `syllableLength h ≤ 1`, so `u` is a source-side -- element of `U`. The hypothesis `syllableLength v < syllableLength u` forces the terminal -- overlap of the normal form of `v` to lie strictly inside the conjugating word `p`. The further -- inequality `syllableLength (u * v) < syllableLength u` implies that one additional syllable -- cancels in `p * v`, producing a shorter conjugating word `p'` with -- `v⁻¹ * u * v = p'⁻¹ * h * p'`. Hence the conjugate has strictly smaller syllable length. theorem syllableLength_conj_lt_of_mem_shortSyllableConjugates_of_lt_of_mul_lt (d : Transversal φ) {u v : PushoutI φ} (hu : u ∈ shortSyllableConjugates d) (hv : syllableLength d v < syllableLength d u) (huv : syllableLength d (u * v) < syllableLength d u) : syllableLength d (v⁻¹ * u * v) < syllableLength d u

Lemma 1.11.16

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-16: in the Section 11 setup, if every v ∈ W satisfies v * g ∈ U and syllableLength d v < syllableLength d (v * g), and if W is disjoint from the left-translate preimage of the auxiliary subset U*, then every v ∈ W satisfies syllableLength d v < syllableLength d (v * g * v).

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} -- Layer triage: -- `source-facing`: the Section `11` element `g`, the distinguished subset `W`, the upstream -- subset `U = shortSyllableConjugates d`, the auxiliary subset `U*`, and the length comparison -- for `v`, `v * g`, and `v * g * v`. -- `core/canonical`: the amalgamated-product owner `Monoid.PushoutI φ`, the chosen normal-form -- data `NormalWord.Transversal φ`, the derived owner length `syllableLength d`, and the canonical -- set operators `Set.preimage` and `Disjoint`. -- `bridge/view`: `U*` is the source-facing auxiliary subset derived from the canonical owner -- subset `shortSyllableConjugates d` by recording the concrete Section `11` situation in which a -- cyclic shift `v⁻¹ * u * v` is produced from some `u ∈ U` with a shorter right factor `v`. -- -- Domain sampling: -- 1. `Monoid.PushoutI` is the chapter/mathlib owner abstraction for the amalgamated product. -- 2. `Monoid.PushoutI.NormalWord.Transversal` is the canonical chosen normal-form data. -- 3. `Monoid.PushoutI.syllableLength` from Definition `1-11-2` is the chapter owner declaration -- for the Section `11` length. -- 4. `Monoid.PushoutI.shortSyllableConjugates` from Lemma `1-11-14` is the upstream owner for -- the source subset `U`, so the auxiliary subset `U*` should be derived from it rather than -- introduced as an abstract set parameter. -- -- Primitive vs. derived: -- the primitive public data are the pushout diagram `φ`, the chosen transversal `d`, the Section -- `11` subset `W`, the middle element `g`, and the source hypotheses that for `v ∈ W` the word -- `v * g` lies in `U` and is longer than `v`. The auxiliary subset `U*` is derived API from the -- canonical owner subset `shortSyllableConjugates d`, so it should not remain primitive data in -- the main theorem statement. theorem length_lt_middle_product_of_mem_W (d : NormalWord.Transversal φ) (g : PushoutI φ) (W : Set (PushoutI φ)) (hmemU : ∀ ⦃v : PushoutI φ⦄, v ∈ W → v * g ∈ shortSyllableConjugates d) (hshort : ∀ ⦃v : PushoutI φ⦄, v ∈ W → syllableLength d v < syllableLength d (v * g)) (hW : Disjoint W ((fun v : PushoutI φ ↦ g * v) ⁻¹' shortSyllableConjugatesStar d)) {v : PushoutI φ} (hv : v ∈ W) : syllableLength d v < syllableLength d (v * g * v)

Lemma 1.11.17

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-17: in the Section 11 setup, if every v ∈ W satisfies v * g ∈ U and syllableLength d v < syllableLength d (v * g), then for each v ∈ W either syllableLength d v < syllableLength d (v * g * v) or the cyclic shift g * v = v⁻¹ * (v * g) * v belongs to the auxiliary subset U*.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord -- Layer triage: -- `source-facing`: the Section `11` element `g`, the distinguished subset `W`, the textbook -- middle product `v * g * v`, and the cyclic shift `g * v = v⁻¹ * (v * g) * v`. -- `core/canonical`: the amalgamated-product owner `Monoid.PushoutI φ`, the chosen normal-form -- data `NormalWord.Transversal φ`, the owner length `syllableLength d`, and the auxiliary subset -- `shortSyllableConjugatesStar d` from Lemma `1-11-16`. -- `bridge/view`: this item is the one-step case split used by Lemma `1-11-16`, before imposing -- the disjointness hypothesis that rules out the `U*` alternative. -- -- Domain sampling: -- 1. `Monoid.PushoutI` is the chapter owner abstraction for the amalgamated product. -- 2. `Monoid.PushoutI.NormalWord.Transversal` is the canonical chosen normal-form data. -- 3. `Monoid.PushoutI.syllableLength` from Definition `1-11-2` is the Section `11` length. -- 4. `Monoid.PushoutI.shortSyllableConjugatesStar` and -- `Monoid.PushoutI.conj_mem_shortSyllableConjugatesStar_of_mem_shortSyllableConjugates_of_lt_of_mul_le` -- from Lemma `1-11-16` are the upstream owner declarations for the source auxiliary subset -- `U*` and the criterion placing a cyclic shift in it. -- -- Primitive vs. derived: -- the primitive public data are the pushout diagram `φ`, the chosen transversal `d`, the fixed -- element `g`, and the distinguished subset `W`. The hypotheses that `v * g ∈ U` and -- `syllableLength d v < syllableLength d (v * g)` for `v ∈ W` are the substantive Section `11` -- assumptions for this bridge theorem. The auxiliary subset `U*` is already owned by -- `shortSyllableConjugatesStar d`, so it should not remain a second abstract set parameter here. theorem syllableLength_lt_middle_product_or_mul_mem_shortSyllableConjugatesStar_of_mem_W (d : Transversal φ) (g : PushoutI φ) (W : Set (PushoutI φ)) (hmemU : ∀ ⦃v : PushoutI φ⦄, v ∈ W → v * g ∈ shortSyllableConjugates d) (hshort : ∀ ⦃v : PushoutI φ⦄, v ∈ W → syllableLength d v < syllableLength d (v * g)) {v : PushoutI φ} (hv : v ∈ W) : syllableLength d v < syllableLength d (v * g * v) ∨ g * v ∈ shortSyllableConjugatesStar d

Lemma 1.11.18

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-18: in the two-step Section 11 reduction-chain situation, the larger of the two endpoint syllable lengths is bounded by the syllable length of the middle product u₀ * a₀ * u₁.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord variable {d : Transversal φ} {A_lt : PushoutI φ → PushoutI φ → Prop} variable {u a p h q : Fin 2 → PushoutI φ} theorem max_syllableLength_le_mul_middle_of_reductionChain (hchain : IsSection11ReductionChain d A_lt u a p h q) : max (syllableLength d (u 0)) (syllableLength d (u 1)) ≤ syllableLength d (u 0 * a 0 * u 1)

Lemma 1.11.19

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Lemma 1-11-19: in the two-step Section 11 reduction-chain situation, if the left decomposition satisfies A p < A q, then the right syllable is strictly shorter than the middle product u₀ * a₀ * u₁.

universe u v w namespace Monoid.PushoutI variable {ι : Type u} {H : Type v} {G : ι → Type w} variable [Group H] [∀ i, Group (G i)] variable {φ : ∀ i, H →* G i} open NormalWord theorem syllableLength_right_lt_mul_middle_of_A_lt (d : Transversal φ) (A_lt : PushoutI φ → PushoutI φ → Prop) (u a p h q : Fin 2 → PushoutI φ) (hchain : IsSection11ReductionChain d A_lt u a p h q) (hpq : A_lt (p 0) (q 0)) : syllableLength d (u 1) < syllableLength d (u 0 * a 0 * u 1)

Proposition 1.11.20

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-11-20, owner form: a distinguished subset W has nontrivial noncancelling products when every nonempty finite word in letters from W with no adjacent cancellation has nonidentity total product.

universe u v w variable {G : Type u} [Group G] namespace Set class HasNontrivialNoncancellingProducts (W : Set G) : Prop where prod_ne_one {us : List G} (hus : us ≠ []) (hW : ∀ u ∈ us, u ∈ W) (hchain : us.IsChain (fun u v ↦ u * v ≠ 1)) : us.prod ≠ (1 : G)

Corollary 1.11.21

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Corollary 1-11-21: if S generates F, is disjoint from its inverse set, and every nonempty noncancelling word in letters from S ∪ S⁻¹ has nontrivial product, then S is a basis for the free group F.

universe u open FreeGroup open scoped Pointwise -- Layer triage: -- `source-facing`: the ambient group `F`, the subset `S`, the generation hypothesis -- `Subgroup.closure S = ⊤`, the inverse-disjointness hypothesis `Disjoint S S⁻¹`, and the -- Section `11` owner property on `S ∪ S⁻¹`. -- `core/canonical`: `IsFreeGroupBasis S` from Definition `1-1-1`, -- `closure_preimage_isFreeGroupBasis_iff_no_trivial_reduced_word` from Proposition `1-1-12`, -- `Set.HasNontrivialNoncancellingProducts (S ∪ S⁻¹)` from Proposition `1-11-20`, and -- `Subgroup.closure`. -- `bridge/view`: none. The long quantified word hypothesis is already owned by the Section `11` -- subset property, and the inverse-disjointness hypothesis is the source-facing bridge from -- Section `11` noncancelling words to the Chapter `1-1` reduced-word owner criterion. -- -- Domain sampling: -- 1. `IsFreeGroupBasis` is the chapter owner abstraction for the textbook claim that `S` is a -- basis of the ambient free group. -- 2. `Subgroup.closure S = ⊤` is the canonical way to state that `S` generates `F`. -- 3. `closure_preimage_isFreeGroupBasis_iff_no_trivial_reduced_word` is the chapter owner bridge -- from reduced words in the letters of `S` to the basis conclusion. -- 4. `Set.HasNontrivialNoncancellingProducts` from Proposition `1-11-20` is the owner -- abstraction for the Section `11` nontrivial-word hypothesis. variable {F : Type u} [Group F] theorem isFreeGroupBasis_of_closure_eq_top_of_nontrivial_noncancelling_products (S : Set F) (hgen : Subgroup.closure S = ⊤) (hdisj : Disjoint S S⁻¹) (hprod : Set.HasNontrivialNoncancellingProducts (S ∪ S⁻¹)) : IsFreeGroupBasis S

Proposition 1.11.22

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-11-22: if 1 → N → G* → F → 1 is an extension and the quotient F is free, then the extension splits. Equivalently, the quotient map G* → F admits a homomorphic section, and hence G* is canonically identified with a semidirect product via s.semidirectProductMulEquiv.

universe u v w open GroupExtension variable {N : Type u} {GStar : Type v} {F : Type w} [Group N] [Group GStar] [Group F] theorem GroupExtension.exists_splitting_of_free_quotient (S : GroupExtension N GStar F) [IsFreeGroup F] : Nonempty S.Splitting

Proposition 1.11.23

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-11-23 (1): if G = PushoutI φ is the free product of the factors Hᵢ with the subgroup A amalgamated and G* is a subgroup of G, then the normal subgroup N of G* generated by all conjugate intersections p⁻¹ Hᵢ p ∩ G* is a tree product of a certain family of these groups.

universe u v w x open Monoid open scoped Pointwise variable {ι : Type u} {A : Type v} {H : ι → Type w} variable [Group A] [∀ i, Group (H i)] variable (φ : ∀ i, A →* H i) theorem exists_treeProduct_of_generatedConjugateFactorNormalSubgroup (hφ : ∀ i, Function.Injective (φ i)) (GStar : Subgroup (PushoutI φ)) : ∃ Δ : TreeProductDiagram, Δ.IsTreeProductOf (generatedConjugateFactorNormalSubgroup φ GStar) ∧ (∀ a : Δ.Vertex, ∃ p : PushoutI φ, ∃ i : ι, Nonempty (Δ.vertexGroup a ≃* conjugateFactorIntersectionSubgroup φ GStar p i))

Proposition 1.11.24

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-11-24: if G = PushoutI φ is the free product of the factors Hᵢ with the subgroup A amalgamated and G* intersects every conjugate of A trivially, then G* is the free product of certain actual conjugate-intersection subgroups p⁻¹ Hᵢ p ∩ G* together with one free subgroup factor.

universe u v w x y open Monoid open scoped Pointwise variable {ι : Type u} {A : Type v} {H : ι → Type w} variable [Group A] [∀ i, Group (H i)] variable (φ : ∀ i, A →* H i) theorem exists_freeProduct_decomposition_of_disjoint_base_conjugates (hφ : ∀ i, Function.Injective (φ i)) (GStar : Subgroup (PushoutI φ)) (htriv : ∀ p : PushoutI φ, Disjoint GStar (MulAut.conj p⁻¹ • (PushoutI.base φ).range)) : ∃ (κ : Type x) (K : κ → Subgroup GStar) (F : Subgroup GStar) (e : CoprodI (kuroshFactorFamily F K) ≃* GStar), IsKuroshFactorDecomposition GStar K F e ∧ ∀ j, ∃ p : PushoutI φ, ∃ i : ι, K j = conjugateFactorIntersectionSubgroup φ GStar p i

Proposition 1.11.25

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Proposition 1-11-25: every finite subset of the indexed free product can be carried by a Nielsen transformation to a finite subset satisfying the free-product length dichotomy from the text.

universe u v open Monoid open Monoid.CoprodI open scoped Symmetrization namespace Monoid.CoprodI variable {ι : Type u} {factors : ι → Type v} [∀ i, Group (factors i)] theorem exists_nielsen_image_with_length_dichotomy (X : Finset (CoprodI factors)) : ∃ Y : Finset (CoprodI factors), NielsenTransformsTo X Y ∧ HasNielsenLengthDichotomy (Y : Set (CoprodI factors))

Supporting modules

These source modules support the indexed items and are listed separately so the chapter inventory remains complete.

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source