Chapter 03 — Geometric Methods
Proofs omitted. Hover over highlighted terms to see their Lean types.
3.2 — Complexes
Definition 3.2.1
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-2-1: A graph, or 1-complex, consists of a vertex set, an edge set, endpoint maps, and a fixed-point-free involution on edges that reverses orientation.
universe u v
-- Layer triage:
-- `source-facing`: a `1`-complex with an explicit set of vertices, an explicit set of oriented
-- edges, and a fixed-point-free orientation-reversing involution on edges.
-- `core/canonical`: mathlib's `Quiver` is the owner abstraction for directed multigraph-style
-- edge data, and `Quiver.IsStronglyConnected` on the symmetrified quiver is the owner predicate
-- for zigzag-connectedness.
-- `bridge/view`: a `1`-complex canonically induces a quiver on its vertex type by taking arrows
-- from `v` to `w` to be edges whose initial and terminal vertices are `v` and `w`.
-- Domain sampling:
-- 1. `Quiver` is mathlib's owner abstraction for directed multigraph-style edge data.
-- 2. `Quiver.IsStronglyConnected (Quiver.Symmetrify C)` is the owner predicate for connectedness
-- by zigzags in a reversible graph.
-- 3. `Quiver.RootedConnected` is the owner class for based reachability, so no extra local
-- wrapper around it belongs in the public API.
-- 4. `Digraph` is too coarse here because it forgets the edge set and cannot distinguish
-- parallel edges.
-- 5. `SimpleGraph.Dart` models oriented edges in an undirected simple graph, but the present item
-- starts from a primitive edge set rather than deriving darts from an underlying simple graph.
-- Primitive vs. derived:
-- the primitive data are the vertex type, edge type, endpoint maps, and inverse-edge map; the
-- induced quiver structure and zigzag-connectedness properties are derived.
structure OneComplex where
/-- The vertices of the 1-complex. -/
Vertex : Type u
/-- The oriented edges of the 1-complex. -/
Edge : Type v
/-- The initial vertex of an oriented edge. -/
initial : Edge → Vertex
/-- The terminal vertex of an oriented edge. -/
terminal : Edge → Vertex
/-- The edge with the opposite orientation. -/
edgeInv : Edge → Edge
/-- Reversing orientation twice gives back the original edge. -/
edgeInv_involutive : Function.Involutive edgeInv
/-- No edge is equal to its oppositely oriented edge. -/
edgeInv_ne (e : Edge) : edgeInv e ≠ e
/-- The inverse edge starts at the terminal vertex of the original edge. -/
initial_edgeInv (e : Edge) : initial (edgeInv e) = terminal eDefinition 3.2.2
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-2-2: in a 1-complex C, a path from v to w is a finite composable sequence of oriented edges from v to w. This notion is already owned by Quiver.Path on the quiver underlying C, so the file keeps only direct recalls of the canonical owner API.
universe u v
-- Layer triage:
-- `source-facing`: for a `1`-complex `C`, a path from `v` to `w` is a finite composable sequence
-- of oriented edges in `C`, together with the vertex-specific empty path and the inverse path
-- obtained by reversing edges.
-- `core/canonical`: `Quiver.Path` is mathlib's owner abstraction for finite composable edge
-- sequences, and it already carries the empty path and length API.
-- `bridge/view`: Definition `3-2-1` equips every `OneComplex` with the quiver structure and
-- involutive edge reversal needed to read the textbook notion directly as `Quiver.Path` and its
-- canonical reverse operation.
-- Domain sampling:
-- 1. `Quiver.Path` is the canonical owner for finite composable edge sequences.
-- 2. `Quiver.Path.nil` gives the empty path at each vertex.
-- 3. `Quiver.Path.length` is the canonical length function on paths.
-- 4. `Quiver.Path.reverse` is the canonical inverse-path operation once arrow reversal is
-- available through `Quiver.HasReverse`.
-- Primitive vs. derived:
-- the primitive owner is `Quiver.Path` itself; the empty path, length, and inverse path are
-- derived canonical API and should be recalled directly rather than repackaged by local wrappers.
variable (C : OneComplex.{u, v})
#check (Quiver.Path : C → C → Type _)Definition 3.2.3
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-2-3 (1): the cyclic path determined by a loop is its cyclically ordered edge sequence, with the basepoint forgotten.
universe u v
open List Quiver
-- Layer triage:
-- `source-facing`: cyclic permutations of a loop, cyclic paths, reduced paths, and cyclically
-- reduced loops in a `1`-complex.
-- `core/canonical`: `Quiver.Path` is the owner abstraction for finite composable edge sequences,
-- `Quiver.Total` is the owner abstraction for arrows remembered together with their endpoints,
-- and `Cycle.Chain` is the canonical owner predicate for cyclic adjacency on the rotation
-- quotient of total arrows.
-- `bridge/view`: a loop presents a cyclic path by forgetting its basepoint and retaining only its
-- cyclically ordered edge sequence, while path decomposition via `Quiver.Path.comp` expresses the
-- source-facing cyclic-permutation relation on representatives.
-- Domain sampling:
-- 1. `Quiver.Path` is the canonical owner for finite composable paths.
-- 2. `Quiver.Total` is mathlib's canonical type of arrows together with their source and target.
-- 3. `Cycle α` is mathlib's canonical rotation quotient of lists, with `Cycle.Chain` the owner
-- predicate for cyclic adjacency conditions.
-- 4. `Quiver.Path.comp`, together with `List.IsRotated`, is the bridge from a based loop to its
-- intrinsic cyclic edge sequence.
namespace Quiver.Path
variable {V : Type u} [Quiver.{v} V]
abbrev cyclicPath (p : Loop V) : CyclicPath V :=
⟨edgeList p.2, edgeList_chain p.2⟩Definition 3.2.4
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-2-4: A 2-complex consists of a 1-skeleton, a set of oriented faces with a fixed-point-free inverse-face involution, and a boundary map assigning to each face a cyclically reduced cycle in the 1-skeleton such that the inverse face has the inverse boundary cycle.
universe u v w
open Quiver
open Quiver.Path
-- Layer triage:
-- `source-facing`: a 2-complex with its 1-skeleton, oriented faces, boundary cycles, inverse
-- faces, and the derived notions of a vertex lying on a face and of a boundary path.
-- `core/canonical`: `OneComplex` is the owner for the 1-skeleton, while
-- `Quiver.Path.CyclicPath`, `Quiver.Path.cyclicPath`, and the predicates from
-- Definition 3-2-3 are the owner API for cyclic boundary data in that skeleton.
-- `bridge/view`: the inverse-edge operation on a `OneComplex` induces the quiver-reversal
-- structure needed to talk about inverse loops and inverse boundary cycles in the skeleton.
-- Domain sampling:
-- 1. `OneComplex` is the project owner abstraction for the textbook 1-skeleton.
-- 2. `Quiver.Path.Loop` is the canonical owner for based loops in the induced quiver.
-- 3. `Quiver.Path.CyclicPath` is the project owner for the basepoint-free cyclic boundary object.
-- 4. `Quiver.Path.IsCyclicallyReducedCycle` is the owner predicate for cyclically reduced
-- boundary cycles, while `Quiver.Path.IsSimple` remains the owner predicate on representatives
-- used to define simple boundary.
structure TwoComplex where
/-- The underlying 1-skeleton of the 2-complex. -/
skeleton : OneComplex
/-- The oriented faces of the 2-complex. -/
Face : Type w
/-- The boundary cycle attached to a face. -/
boundary : Face → CyclicPath skeleton
/-- Each face boundary is a cyclically reduced cycle in the 1-skeleton. -/
boundary_cyclicallyReduced (D : Face) : IsCyclicallyReducedCycle (boundary D)
/-- The inverse face with the opposite orientation. -/
faceInv : Face → Face
/-- Inverting the orientation of a face twice returns the original face. -/
faceInv_involutive : Function.Involutive faceInv
/-- A face is distinct from its inverse face. -/
faceInv_ne (D : Face) : faceInv D ≠ D
/-- The boundary of the inverse face is the inverse of the original boundary cycle. -/
boundary_faceInv (D : Face) : boundary (faceInv D) = inverseCycle (boundary D)Definition 3.2.5
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-2-5: for a 2-complex C, the set Π(C) of all paths in the 1-skeleton carries the canonical quiver-path multiplication by juxtaposition of composable paths. This source-facing algebraic structure is exactly mathlib's path concatenation operation Quiver.Path.comp, specialized to the quiver of the 1-skeleton.
#check Quiver.Path.compDefinition 3.2.6
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-2-6: two paths are 1-equivalent when one can pass from one to the other by a finite succession of insertions or deletions of subpaths of the form ee⁻¹.
universe u v
open CategoryTheory
open Quiver
-- Layer triage:
-- `source-facing`: the `1`-equivalence relation on paths and the resulting fundamental groupoid
-- `Π¹(C)`.
-- `core/canonical`: `CategoryTheory.Paths` is the owner abstraction for the path category,
-- `Relation.EqvGen` is the owner abstraction for generated equivalence relations, and
-- `CategoryTheory.Quotient` is the owner abstraction for quotient categories.
-- `bridge/view`: `Quiver.Path.pathOneHomRel` packages the source relation as a categorical
-- congruence so that `Π¹(C)` is a thin source-facing notation for the quotient category.
-- Domain sampling:
-- 1. `Relation.EqvGen` and `Relation.EqvGen.setoid` encode the generated equivalence relation.
-- 2. `CategoryTheory.Paths` is mathlib's owner category for paths in a quiver.
-- 3. `CategoryTheory.HomRel` and `CategoryTheory.Congruence` are the owner abstractions for a
-- quotient relation compatible with composition.
-- 4. `CategoryTheory.Quotient` is the canonical owner for the quotient category surface.
-- Primitive vs. derived:
-- the primitive source data are the elementary cancellation step and the generated
-- `path_one_equiv`; the quotient-category surface and the resulting groupoid structure are
-- derived from that relation.
namespace Quiver.Path
variable {V : Type u} [Quiver.{v} V] [Quiver.HasInvolutiveReverse V]
def path_one_equiv {a b : V} (p q : Quiver.Path a b) : Prop :=
Relation.EqvGen path_one_reduction_step p qDefinition 3.2.7
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-2-7: two paths are 2-equivalent when one can pass from one to the other by a finite succession of insertions or deletions of spurs ee⁻¹ and of boundary paths of faces.
universe u v w
open CategoryTheory
open Quiver
open Quiver.Path
open scoped Quiver.Path
-- Layer triage:
-- `source-facing`: the `2`-equivalence relation on paths in a `2`-complex, its quotient
-- fundamental groupoid `π(C)`, and the canonical map from the `1`-skeleton groupoid to `π(C)`.
-- `core/canonical`: `TwoComplex` is the owner abstraction for the `2`-complex data,
-- `Quiver.Path` is the owner abstraction for paths, `Relation.EqvGen` is the owner abstraction
-- for the generated equivalence relation, and `CategoryTheory.Category` / `Groupoid` are the
-- owner abstractions for the quotient groupoid.
-- `bridge/view`: the fundamental groupoid of the `1`-skeleton is the already defined
-- `Π¹(C.skeleton)`, and the present item adds the quotient functor collapsing
-- boundary paths of faces.
-- Domain sampling:
-- 1. `TwoComplex.BoundaryPath` is the project owner for the based closed boundary paths allowed in
-- `2`-dimensional reduction.
-- 2. `Quiver.Path.path_one_equiv` is the earlier owner relation generated by cancellation of
-- spurs `ee⁻¹`.
-- 3. `Relation.EqvGen` is the canonical owner for the generated congruence relation.
-- 4. `CategoryTheory.Functor` is the canonical owner for the homomorphic image map
-- `π(C¹) ⥤ π(C)`.
namespace TwoComplex
variable (C : TwoComplex)
def path_two_equiv {a b : C.skeleton} (p q : Quiver.Path a b) : Prop :=
Relation.EqvGen (C.path_two_reduction_step) p qDefinition 3.2.8
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-2-8: for a vertex v of a 2-complex C, the fundamental group π(C, v) is the vertex group at v in the fundamental groupoid π(C). The unquotiented loop set Π(C, v) is the endomorphism monoid of v in the path category of the 1-skeleton, while the quotient group is the endomorphism group End (⟨v⟩ : C.pi).
universe u v w
open CategoryTheory
-- Layer triage:
-- `source-facing`: for a vertex `v` of a `2`-complex `C`, the loops at `v` in the `1`-skeleton
-- form a semigroup, and their image in the fundamental groupoid is the fundamental group
-- `π(C, v)`.
-- `core/canonical`: `CategoryTheory.Paths C.skeleton` is the canonical path category of the
-- `1`-skeleton, `C.pi` is the already defined fundamental groupoid, and `CategoryTheory.End` is
-- the canonical owner for vertex loops in both settings.
-- `bridge/view`: the textbook notations `Π(C, v)` and `π(C, v)` are expressed by the
-- endomorphism types at `v` before and after quotienting by `2`-equivalence.
-- Domain sampling:
-- 1. `CategoryTheory.Paths.categoryPaths` is the canonical category structure on quiver paths.
-- 2. `CategoryTheory.End` is the canonical owner of loops at a chosen object.
-- 3. `CategoryTheory.End.monoid` gives the multiplicative structure on loops in a category.
-- 4. `CategoryTheory.End.group` upgrades this to a group when the ambient category is a groupoid.
namespace TwoComplex
variable (C : TwoComplex) (v : C.skeleton)
#check (CategoryTheory.End (⟨v⟩ : C.pi))Proposition 3.2.9
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-2-9: if C is a 1-complex and v is any vertex of C, then the fundamental group π(C, v) is free. The proof passes to the connected component of ⟨v⟩ in the fundamental groupoid Π¹(C), applies the canonical free-groupoid theorem there, and transports the resulting free group structure back along the fully faithful inclusion of that component. No global connectedness hypothesis belongs in the public statement.
open CategoryTheory
open CategoryTheory.ObjectProperty
open IsFreeGroupoid
namespace OneComplex
-- Layer triage:
-- `source-facing`: a `1`-complex `C`, a vertex `v : C`, and the textbook claim that the
-- fundamental group `π(C, v)` is free.
-- `core/canonical`: `CategoryTheory.ConnectedComponents.Component` is the canonical owner for the
-- connected component of a chosen object, and `IsFreeGroup` is the owner predicate for freeness of
-- a group.
-- `bridge/view`: the chapter-local `OneComplex.fundamentalGroup C v`, written `π(C, v)`, is the
-- source-facing owner for the loop group at `v`; its proof is obtained by restricting the free
-- groupoid structure on `Quiver.Path.pi1 C` to the connected component of `⟨v⟩` and then
-- transporting freeness back along the fully faithful inclusion.
-- Domain sampling:
-- 1. `OneComplex.fundamentalGroup` is the chapter owner for the based fundamental group `π(C, v)`.
-- 2. `CategoryTheory.ConnectedComponents.Component` is the canonical connected-component owner for
-- reducing a loop-group statement to a connected groupoid.
-- 3. `IsFreeGroupoid.endIsFreeOfConnectedFree` is the core freeness theorem for loop groups in a
-- connected free groupoid.
-- 4. `Functor.FullyFaithful.mulEquivEnd` is the canonical bridge transporting the loop group on a
-- connected component back to the ambient endomorphism group.
-- Primitive vs. derived:
-- the primitive data are the `1`-complex `C` and the chosen vertex `v`; the connected component of
-- `⟨v⟩`, the restricted free-groupoid structure on that component, and the endomorphism-group
-- equivalence induced by the inclusion are all derived proof-internal bridge data.
theorem fundamentalGroup_isFree (C : OneComplex) (v : C) :
IsFreeGroup (π(C, v))Proposition 3.2.10
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-2-10: if C is a connected 1-complex with finitely many oriented edges and v is a base vertex, then the fundamental group π(C, v) has rank γ₁ - γ₀ + 1. Here γ₁ is expressed canonically as Nat.card (GeometricEdge C) and γ₀ as Nat.card C. The intrinsic owner hypothesis hconnected : Quiver.IsStronglyConnected (Quiver.Symmetrify C) replaces the bridge-level rooted-connectedness assumption, while still providing the rooted connectivity needed internally for the spanning-tree argument. Edge finiteness together with connectedness forces the vertex type to be finite, so no separate vertex-finiteness binder belongs in the source-facing statement.
universe u
open CategoryTheory CategoryTheory.SingleObj Quiver
open IsFreeGroupoid
open IsFreeGroupoid.SpanningTree
namespace OneComplex
theorem fundamentalGroup_rank_eq_card_geometricEdges_sub_card_vertices_add_one
(C : OneComplex.{u, v}) [Finite C.Edge]
(hconnected : Quiver.IsStronglyConnected (Quiver.Symmetrify C)) (v : C) :
Nat.card (IsFreeGroup.Generators (π(C, v))) =
Nat.card (GeometricEdge C) - Nat.card C + 1Proposition 3.2.11
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-2-11: if the based fundamental group of a presentation complex K(X; R) is the quotient of FreeGroup X by the normal closure of the relators R, then that fundamental group is canonically isomorphic to the presented group PresentedGroup R.
universe u
open QuotientGroup
-- Declarations for this item will be appended below by the statement pipeline.
-- Layer triage:
-- `source-facing`: an actual `2`-complex `C`, a base vertex `v : C.skeleton`, and a
-- presentation map `φ : FreeGroup X →* π(C, v)` whose kernel is exactly the normal closure of the
-- relators `R`; the proposition states that the based fundamental group of this presentation
-- complex is the presented group on `(X; R)`.
-- `core/canonical`: `TwoComplex.fundamentalGroup`, written `π(C, v)`, is the chapter owner for
-- the based fundamental group, `PresentedGroup R` is mathlib's owner for the group presented by
-- relators `R`, and `Subgroup.normalClosure R` is the canonical relator subgroup.
-- `bridge/view`: `quotientKerEquivOfSurjective` and `quotientMulEquivOfEq` provide the quotient
-- comparison proving the source-facing identification.
-- Primitive vs. derived:
-- primitive data: the actual `TwoComplex`, the base vertex, the surjective map
-- `φ : FreeGroup X →* π(C, v)`, and the kernel description `φ.ker = Subgroup.normalClosure R`;
-- derived API: the canonical presentation equivalence `PresentedGroup R ≃* π(C, v)` and its
-- generator-image companion theorem.
-- Domain sampling:
-- 1. `TwoComplex.fundamentalGroup`, written `π(C, v)`, from Definition `3-2-8` is the chapter
-- owner for the based fundamental group.
-- 2. `PresentedGroup R`, together with `PresentedGroup.mk` and `PresentedGroup.of`, is the
-- canonical quotient owner for generators-and-relations groups.
-- 3. `Subgroup.normalClosure R` is the canonical owner for the relator subgroup of `FreeGroup X`.
-- 4. `quotientKerEquivOfSurjective` and `quotientMulEquivOfEq` are the canonical quotient
-- equivalences turning the kernel calculation into an actual multiplicative equivalence.
namespace TwoComplex
noncomputable def fundamentalGroupMulEquivPresentedGroup
{X : Type u} {R : Set (FreeGroup X)} (C : TwoComplex) (v : C.skeleton)
(φ : FreeGroup X →* π(C, v))
(hφ : Function.Surjective φ)
(hker : φ.ker = Subgroup.normalClosure R) :
PresentedGroup R ≃* π(C, v) :=
(quotientMulEquivOfEq hker.symm).trans (quotientKerEquivOfSurjective φ hφ)3.3 — Covering Maps
Proposition 3.3.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-3-1: if f : C' → C is a covering map of 1-complexes and v' is a vertex of C', then the induced homomorphism f.inducedFundamentalGroupHom v' : π(C', v') →* π(C, f.toVertex v') is injective, hence a monomorphism of fundamental groups.
universe u v
open CategoryTheory
open Quiver
open Quiver.Path
open scoped Quiver.Path
-- Layer triage:
-- `source-facing`: a morphism of `1`-complexes, the covering-map condition on outgoing oriented
-- edges, and the induced monomorphism on based fundamental groups.
-- `core/canonical`: `OneComplex.Hom` is the chapter owner for morphisms of `1`-complexes,
-- `Quiver.Prefunctor.IsCovering`, `Π¹(C)`, `CategoryTheory.Cat.freeMap`,
-- `CategoryTheory.Quotient.functor`, and `CategoryTheory.Functor.mapEnd` are the owners for the
-- covering condition, the fundamental groupoid, the induced path-category and quotient functors,
-- and the resulting based fundamental group homomorphism, while `Function.Injective` is the owner
-- API for a monomorphism of groups.
-- `bridge/view`: a `1`-complex morphism induces a quiver prefunctor and hence the canonical path
-- and quotient maps; the proposition is stated on `π(C, v)` rather than on raw loop
-- representatives.
-- Domain sampling:
-- 1. `Quiver.Prefunctor` and `Prefunctor.mapPath` are mathlib's owners for maps of quivers and
-- their induced path maps.
-- 2. `Quiver.Prefunctor.IsCovering` is the owner abstraction for coverings of quivers, and in a
-- `1`-complex its star-bijectivity presentation matches the textbook local covering condition.
-- 3. `Quiver.Path.path_one_equiv`, `Quiver.Path.pathOneHomRel`, and `Π¹(C)` are the owners for
-- backtracking-cancellation classes of paths and the resulting quotient groupoid.
-- 4. `CategoryTheory.Cat.freeMap` and `CategoryTheory.Quotient.functor` are the canonical owners
-- for the induced functor on path categories and the resulting map of fundamental groupoids.
-- 5. `OneComplex.fundamentalGroup`, written `π(C, v)`, is the chapter owner for the based
-- fundamental group, and `CategoryTheory.Functor.mapEnd` is the owner for the induced
-- homomorphism on the endomorphism monoids of base objects.
namespace OneComplex
namespace Hom
variable {C D : OneComplex.{u, v}} (f : Hom C D)
theorem inducedFundamentalGroupHom_injective_of_isCovering
(hf : f.toPrefunctor.IsCovering) (v' : C) :
Function.Injective (f.inducedFundamentalGroupHom v')Proposition 3.3.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-3-2: every subgroup H ≤ π(C, v) is realized by a connected covering 1-complex over C, with a chosen vertex over v, such that the induced homomorphism π(C', v') → π(C, v) has image exactly H. Injectivity is the canonical downstream consequence of Proposition 3-3-1 for covering maps.
universe u v
namespace OneComplex
theorem exists_connected_covering_inducing_subgroup
(C : OneComplex.{u, v}) (hconnected : Quiver.IsStronglyConnected (Quiver.Symmetrify C))
(v : C) (H : Subgroup (π(C, v))) :
∃ (C' : OneComplex.{u, v})
(_ : Quiver.IsStronglyConnected (Quiver.Symmetrify C')) (φ : Hom C' C)
(_ : φ.toPrefunctor.IsCovering) (v' : C') (hv' : φ.toVertex v' = v),
(φ.inducedFundamentalGroupHomOver v' v hv').range = HProposition 3.3.3
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-3-3: 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. The geometric covering-space proof sketched in the text gives an alternative derivation, but it does not change the public statement, so this item stays a direct recall of the canonical theorem rather than introducing a parallel wrapper.
#check subgroupIsFreeOfIsFreeProposition 3.3.4
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-3-4: for any subgroup H ≤ π(C, v) of the fundamental group of a connected 2-complex C, there exists a connected covering 2-complex C' → C with a chosen vertex v' over v whose induced homomorphism π(C', v') → π(C, v) has image exactly H; injectivity is the canonical consequence of the covering-map owner.
open CategoryTheory
open Quiver.Path
namespace TwoComplex
theorem exists_connected_covering_inducing_subgroup
(C : TwoComplex) (hconnected : Quiver.IsStronglyConnected (Quiver.Symmetrify C.skeleton))
(v : C.skeleton)
(H : Subgroup (π(C, v))) :
∃ (C' : TwoComplex)
(_ : Quiver.IsStronglyConnected (Quiver.Symmetrify C'.skeleton)) (φ : Hom C' C)
(_ : Hom.IsCoveringMap φ) (v' : C'.skeleton) (hv' : φ.toVertex v' = v),
(φ.inducedFundamentalGroupHomOver v' v hv').range = HProposition 3.3.5
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-3-5: if a 2-complex C is the union of a family of subcomplexes indexed by I, all containing the same base vertex v, and distinct subcomplexes meet only in that vertex, then the fundamental group π(C, v) is isomorphic to the indexed free product of the fundamental groups of the subcomplexes.
universe u v w uI
open Monoid
open Quiver.Path
namespace TwoComplex
theorem fundamentalGroup_nonempty_mulEquiv_coprodI_of_subcomplex_cover
{I : Type uI} (C : TwoComplex.{w}) (pieces : I → Subcomplex C) (v : C.skeleton)
(hv : ∀ i, v ∈ (pieces i).skeleton.vertexSet)
(hcover_vertex : ∀ x : C.skeleton, ∃ i, x ∈ (pieces i).skeleton.vertexSet)
(hcover_edge : ∀ e : C.skeleton.Edge, ∃ i, e ∈ (pieces i).skeleton.edgeSet)
(hcover_face : ∀ D : C.Face, ∃ i, D ∈ (pieces i).faceSet)
(hinter_vertex :
∀ {i j : I} (hij : i ≠ j) {x : C.skeleton},
x ∈ (pieces i).skeleton.vertexSet →
x ∈ (pieces j).skeleton.vertexSet →
x = v)
(hdisjoint_edge :
∀ {i j : I} (hij : i ≠ j) {e : C.skeleton.Edge},
e ∈ (pieces i).skeleton.edgeSet →
e ∈ (pieces j).skeleton.edgeSet →
False)
(hdisjoint_face :
∀ {i j : I} (hij : i ≠ j) {D : C.Face},
D ∈ (pieces i).faceSet →
D ∈ (pieces j).faceSet →
False) :
Nonempty (π(C, v) ≃* CoprodI (fun i ↦ π((pieces i).complex, ⟨v, hv i⟩)))Proposition 3.3.6
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-3-6: every subgroup of an indexed free product is itself a free product of one free group together with subgroup factors lying in the subgroup and equal in the ambient free product to conjugates of subgroups of the original free factors.
universe u v w
open Monoid
open scoped Pointwise
variable {ι : Type u} (G : ι → Type v) [∀ i, Group (G i)]
-- Layer triage:
-- `source-facing`: a subgroup `H` of the indexed free product `CoprodI G`, together with a
-- decomposition of `H` as a free product of one free group and subgroup factors of `H` whose
-- ambient images are conjugates of subgroups of the ambient free factors.
-- `core/canonical`: `CoprodI` is mathlib's owner for indexed free products, `IsFreeGroup` is the
-- owner predicate for freeness, and subgroup conjugation is expressed using `MulAut.conj`
-- together with `Subgroup.map`.
-- `bridge/view`: the Chapter 1 owner `IsKuroshFactorDecomposition` packages the distinguished
-- free subgroup together with the subgroup factors into a `CoprodI` decomposition; the extra
-- source-facing content here is only the ambient conjugacy description of the factors.
-- Domain sampling:
-- 1. `CoprodI` and `CoprodI.of` are the canonical indexed free-product owners.
-- 2. `IsFreeGroup` is the canonical owner for the free group factor in the decomposition.
-- 3. `IsKuroshFactorDecomposition` from Proposition `1-11-24` is the project owner for the
-- underlying free-product decomposition data.
-- 4. `Subgroup.map`, `Subgroup.subtype`, and `MulAut.conj` are the standard subgroup and
-- conjugation APIs needed to express the Kurosh factors.
-- Primitive vs. derived:
-- the primitive source-facing data are the subgroup `H`, the distinguished free subgroup factor
-- `F ≤ H`, the subgroup-factor family `K : J → Subgroup H`, and the free-product equivalence
-- `CoprodI (kuroshFactorFamily F K) ≃* H`; the ambient conjugacy description of each `K j` is the
-- extra source-facing property asserted in this proposition.
theorem exists_kurosh_freeProduct_decomposition
(H : Subgroup (CoprodI G)) :
∃ (J : Type w) (K : J → Subgroup H) (F : Subgroup H)
(e : CoprodI (kuroshFactorFamily F K) ≃* H),
IsKuroshFactorDecomposition H K F e ∧
∀ j, ∃ i : ι, ∃ g : CoprodI G, ∃ L : Subgroup (G i),
Subgroup.map H.subtype (K j) =
MulAut.conj g • Subgroup.map (CoprodI.of : G i →* CoprodI G) LProposition 3.3.7
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-3-7: if a finitely generated free group F surjects onto a nonempty indexed free product CoprodI A, then F splits as an indexed free product of subgroup factors whose images under the surjection are exactly the canonical factor subgroups of CoprodI A.
universe u v w
open Monoid
variable {ι : Type v} {F : Type u} {A : ι → Type w}
variable [Group F] [IsFreeGroup F] [Group.FG F]
variable [∀ i, Group (A i)]
-- Primary domain: indexed free products of groups and free-group decompositions.
--
-- Layer triage:
-- `source-facing`: a finitely generated free group `F`, a surjection `φ : F →* CoprodI A`
-- onto an indexed free product, and a family of subgroup factors in `F` mapping onto the given
-- factors.
-- `core/canonical`: `IsFreeGroup` is the owner predicate for free groups, `CoprodI` is the
-- owner abstraction for indexed free products, and `Subgroup.map` expresses the image of each
-- subgroup factor under `φ`.
-- `bridge/view`: the equality `F = * F_λ` is rendered by an isomorphism from the indexed free
-- product of subgroup factors onto `F` whose canonical inclusions agree with the subgroup
-- embeddings.
-- Domain sampling:
-- 1. `CoprodI` with its canonical inclusions `CoprodI.of` is the owner abstraction
-- for indexed free products.
-- 2. `CoprodI.lift` is the universal-property owner that would control the eventual proof.
-- 3. `IsFreeGroup` together with `[Group.FG F]` is the chapter/mathlib owner interface for a
-- finitely generated free group; any chosen finite basis is derived data.
-- 4. `Subgroup.map` is the canonical owner for the image condition `F_λ φ = A_λ`.
--
-- Primitive vs. derived:
-- the primitive public data are the finitely generated free group `F`, the factor family `A`, and
-- the surjection `φ : F →* CoprodI A`; the subgroup family `H`, the free-product equivalence
-- `CoprodI (fun i ↦ H i) ≃* F`, and the factor-image equalities are all derived API.
theorem exists_freeProduct_subgroup_family_lifting_surjection_to_indexed_freeProduct
(hι : Nonempty ι) (φ : F →* CoprodI A) (hφ : Function.Surjective φ) :
∃ H : ι → Subgroup F, ∃ e : CoprodI (fun i ↦ H i) ≃* F,
(∀ i, e.toMonoidHom.comp CoprodI.of = (H i).subtype) ∧
∀ i, Subgroup.map φ (H i) = (CoprodI.of : A i →* CoprodI A).rangeLemma 3.3.8
Lean contributors (project-level attribution): Zichen Wang.
Lemma 3-3-8: in the labelled free-product setting, if the common intersection ⋂ K_λ is not connected, then any two distinct factors produce a binding tie in the chosen i-factor. The source-facing data are the family K_λ, the ambient vertex-labelling into the indexed free product, and the standard free-product property that endpoint displacements inside K_λ land in the λ-factor subgroup. The trivial-image condition is derived by comparing the same endpoint pair through two distinct factors, rather than assumed as an extra bridge hypothesis.
universe u v w x
open Monoid
open Quiver
namespace OneComplex
namespace Subcomplex
variable {ι : Type w} {K : OneComplex.{u, v}}
-- Layer triage:
-- `source-facing`: an ambient `1`-complex `K`, a family of subcomplexes `K_λ`, a vertex-labelling
-- into an indexed free product, and the resulting notion of a binding tie.
-- `core/canonical`: `OneComplex`, `OneComplex.Subcomplex`, `OneComplex.Hom`,
-- `Quiver.IsStronglyConnected (Quiver.Symmetrify _)`, `Quiver.Path (Quiver.Symmetrify _)`,
-- `CoprodI`, and `MonoidHom.range` are the owner abstractions for the ambient graph, the
-- subcomplexes, connectedness, ambient and
-- internal zigzag paths, and the target free product.
-- `bridge/view`: `Subcomplex.toOneComplex` and the canonical hom
-- `Subcomplex.iInterInclusion` convert the
-- source-facing subcomplex data to the canonical ambient/path owners.
--
-- Domain sampling:
-- 1. `OneComplex.Subcomplex` is the source-facing owner for the subcomplexes `K_λ`.
-- 2. `OneComplex.Hom` from Proposition `3-3-1` is the chapter owner for maps of carried
-- `1`-complexes, so the intersection inclusion should be phrased through that owner rather
-- than as a raw quiver prefunctor.
-- 3. `Quiver.IsStronglyConnected (Quiver.Symmetrify _)` is the canonical owner for connectedness
-- of a reversible `1`-skeleton.
-- 4. `Quiver.Path (Quiver.Symmetrify K)` is the canonical path owner specialized to
-- symmetrified `1`-complexes.
-- 5. `CoprodI`, `CoprodI.of`, and `MonoidHom.range` are the owner abstractions for
-- the indexed free product and its canonical factor subgroups.
variable {A : ι → Type x} [∀ i, Group (A i)]
theorem exists_bindingTie_of_intersection_not_connected
(Ksub : ι → Subcomplex K) (label : K → CoprodI A)
(hlabel : IsFreeProductLabelledFamily Ksub label)
(i j : ι) (hij : i ≠ j)
(hnot :
¬ Quiver.IsStronglyConnected (Quiver.Symmetrify ((⋂ i, Ksub i).toOneComplex))) :
∃ tie : BindingTie Ksub label, tie.index = i3.4 — Cayley Complexes
Proposition 3.4.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-4-1: if the edge labels generate G, then every automorphism of the labelled Cayley complex C(X; R) that preserves the generator and relator labels has the same action on vertices, oriented edges, and oriented faces as a unique left translation by some h : G. In the chosen Cayley coordinates, that translation acts by g ↦ h * g, (g, y) ↦ (h * g, y), and on geometric faces by (g, r) ↦ (h * g, r).
universe u v w
-- Layer triage:
-- `source-facing`: a labelled Cayley complex `C(X; R)` realized as an actual `TwoComplex`,
-- together with its chosen relator-face boundary paths at the identity vertex, its
-- label-preserving complex automorphisms, and the canonical left-translation automorphisms.
-- `core/canonical`: `TwoComplex.Hom` is the chapter owner for maps of `2`-complexes,
-- `TwoComplex.Aut` is the owner for invertible self-maps of a `2`-complex, `Equiv.Perm` is the
-- owner for induced permutations on the vertex/edge/face carriers, `TwoComplex.BoundaryPath` is
-- the owner for a chosen based face boundary, `Equiv.mulLeft` is the canonical left-translation
-- permutation of a group, and `Subgroup.closure (Set.range edgeLabel)` is the canonical subgroup
-- generated by the edge labels.
-- `bridge/view`: the induced permutations on `G`, `G × Y`, and `G × Rel`, together with the
-- label-preservation predicates, are the coordinate views derived from the actual Cayley-complex
-- owner.
-- Domain sampling:
-- 1. `TwoComplex.Hom` from Proposition `3-3-4` is the owner abstraction for maps of `2`-complexes.
-- 2. `TwoComplex.Aut` is the correct owner abstraction for automorphisms of a `2`-complex.
-- 3. `TwoComplex.BoundaryPath` from Definition `3-2-4` is the owner abstraction for a chosen
-- based boundary of a relator face.
-- 4. `SignedLetter X` is the chapter owner for a generator together with an orientation sign, and
-- `SignedLetter.value` below is the canonical evaluation of such a signed letter in a group.
-- 5. `Equiv.Perm` and `Equiv.mulLeft` are the canonical owners for carrier permutations and left
-- translations on a group.
-- 6. `Subgroup.closure` and `Set.range` express that the chosen edge labels generate `G`.
-- Primitive vs. derived:
-- the primitive data are the ambient `TwoComplex`, its genuine automorphisms, and the chosen
-- Cayley-coordinate identifications together with the involution on the oriented edge-label type
-- and the chosen identity-based relator-face boundary paths. The induced permutations on `G`,
-- `G × Y`, and `G × Rel`, the translated relator-face boundaries, the coordinate
-- label-preservation predicates, and the coordinate formulas for the canonical left translations
-- are derived API.
namespace CayleyComplex
variable {G : Type u} [Group G]
variable {Y : Type v} {Rel : Type w}
theorem automorphism_cellAction_eq_leftTranslation {C : TwoComplex} {edgeLabel : Y → G}
(coords : Coordinates C edgeLabel Rel) (α : TwoComplex.Aut C)
(hgen : Subgroup.closure (Set.range edgeLabel) = ⊤)
(hedge : coords.PreservesEdgeLabels α) (hface : coords.PreservesFaceLabels α) :
∃! h : G,
coords.vertexPerm α = coords.vertexPerm (coords.leftTranslation h) ∧
coords.edgePerm α = coords.edgePerm (coords.leftTranslation h) ∧
α.facePerm = (coords.leftTranslation h).facePermProposition 3.4.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-4-2: a 2-complex equipped with the standard Cayley coordinates over PresentedGroup R is simply connected.
universe u
namespace CayleyComplex.Coordinates
variable {X : Type u} {R : Set (FreeGroup X)} {C : TwoComplex}
theorem isSimplyConnected
(coords : PresentationCoordinates C R) :
TwoComplex.IsSimplyConnected CProposition 3.4.3
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-4-3 (1): the Cayley complex C(X; R) is the universal covering of the presentation complex K(X; R).
universe u v
namespace CayleyComplex.Coordinates
variable {X : Type u} {R : Set (FreeGroup X)} {C : TwoComplex}
namespace PresentationMap
variable {coords : PresentationCoordinates C R}
theorem toPresentation_isUniversalCovering
(P : PresentationMap coords) :
P.toPresentation.IsCoveringMap ∧
TwoComplex.IsSimplyConnected C ∧
Quiver.IsStronglyConnected (Quiver.Symmetrify C.skeleton)3.5 — Planar Cayley Complexes
Proposition 3.5.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-5-1: if a Cayley complex C(X; R) is planar and S is a chosen relator-root family for R, then S is quadratic over X.
universe u
open GroupPresentation
namespace CayleyComplex.Coordinates
variable {X : Type u} {R : Set (FreeGroup X)} {C : TwoComplex}
theorem quadraticWordSet_of_planar
(coords : PresentationCoordinates C R)
(hplanar : C.EmbedsInPlane)
{S : Set (FreeGroup X)}
(hS : IsRelatorRootSet R S) :
IsQuadraticWordSet (FreeGroupBasis.ofFreeGroup X) SDefinition 3.5.3
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-5-3: an F-group is a group admitting a finite presentation G = (X; R) whose finite chosen relator-root system S is strictly quadratic over X and has cyclic star graph.
universe u
variable {X : Type u}
open FreeGroup.Finset
-- Layer triage:
-- `source-facing`: a group together with a finite presentation `G = (X; R)` and a finite chosen
-- relator-root family `S`, with `S` strictly quadratic and having cyclic star graph.
-- `core/canonical`: `PresentedGroup R` for groups given by generators and relations, `Finite X`
-- for the finite generator datum, `Set.Finite R` as the derived finiteness predicate for relator
-- families coming from finite root systems, `SignedLetter X` for the
-- signed-basis vocabulary, `IsStrictlyQuadraticSet` from Proposition `1-7-6`,
-- `FreeGroup.Finset.sigmaGraph` from Proposition `1-7-8`, and `SimpleGraph.IsCycles` for the
-- graph-theoretic cycle condition.
-- `bridge/view`: the textbook phrase "the chosen set `S` of relator roots" is
-- expressed by `GroupPresentation.IsRelatorRootSet`; the star-graph condition is
-- expressed directly by the owner predicates `(sigmaGraph S).Connected` and
-- `(sigmaGraph S).IsCycles`.
-- Domain sampling:
-- 1. `PresentedGroup R`, together with `Finite X`, is the
-- canonical owner layer for finite presentations.
-- 2. `IsStrictlyQuadraticSet` from Proposition `1-7-6` is the chapter owner for strict
-- quadraticity of finite free-group word systems, so this file reuses it directly.
-- 3. `FreeGroup.Finset.sigmaGraph` from Proposition `1-7-8` is the chapter owner construction
-- for the star graph attached to a finite system of reduced words.
-- 4. `GroupPresentation` from Chapter `2` is the natural owner namespace for auxiliary
-- presentation-level predicates, so the relator-root and relator-power relations live there
-- rather than as bare globals.
-- 5. `Set.Finite.image` is the canonical finiteness API showing that a relator set realized as the
-- image of a finite root family under `s ↦ s ^ m s` is finite, so that finiteness is derived
-- rather than stored as primitive data.
-- 6. `SimpleGraph.IsCycles` is mathlib's owner predicate for graphs whose nonisolated vertices all
-- have degree `2`, so together with connectedness it captures the textbook "cyclic graph"
-- condition.
-- Primitive vs. derived:
-- the primitive source data are the finite presentation `(X; R)` and the finite chosen relator
-- root system `S`, expressed source-facing by `GroupPresentation.IsRelatorRootSet` and canonically
-- by a multiplicity witness for `GroupPresentation.IsRelatorPowerFamily`. The finiteness of `R`,
-- strict quadraticity, and the star graph are derived through the owner predicates already
-- available upstream.
class IsFGroup (G : Type u) [Group G] : Prop where
/-- An `F`-group admits finite presentation data whose finite chosen relator-root system is
strictly quadratic and has cyclic star graph. -/
exists_presentation :
∃ (X : Type u) (_ : Finite X) (R : Set (FreeGroup X)) (S : Finset (FreeGroup X)),
∃ _ : PresentedGroup R ≃* G,
GroupPresentation.IsRelatorRootSet R S ∧
IsStrictlyQuadraticSet S ∧
(sigmaGraph S).Connected ∧
(sigmaGraph S).IsCyclesProposition 3.5.4
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-5-4: every F-group admits either an orientable standard presentation with relator family x_i ^ {m_i} together with x_1 ... x_p [y_1, y_2] ... [y_{2g-1}, y_{2g}], or a nonorientable standard presentation with relator family x_i ^ {m_i} together with x_1 ... x_p y_1^2 ... y_g^2, with all exponents m_i > 1.
universe u
open scoped Classical
open FreeGroupBasis
namespace FGroupPresentation
variable {G : Type u} [Group G]
theorem exists_standard_surface_presentation_of_isFGroup (hG : IsFGroup G) :
(∃ (p g : ℕ) (m : Fin p → ℕ),
∃ _ : PresentedGroup (orientableStandardRelators p g m) ≃* G,
∀ i, 1 < m i) ∨
(∃ (p g : ℕ) (m : Fin p → ℕ),
∃ _ : PresentedGroup (nonorientableStandardRelators p g m) ≃* G,
∀ i, 1 < m i)Proposition 3.5.5
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-5-5: every group admitting a presentation whose Cayley complex embeds in a 2-manifold is either an F-group or a free product of cyclic groups.
universe u v w z
local notation "𝔼²" => EuclideanSpace ℝ (Fin 2)
local notation "𝔻²" => Metric.closedBall (0 : 𝔼²) 1
variable {G : Type u} [Group G]
variable {X : Type v} {R : Set (FreeGroup X)} {C : TwoComplex}
theorem isFGroup_or_isFreeProductOfCyclicGroups_of_cayleyComplex_embedsInTwoManifold
(coords : CayleyComplex.Coordinates.PresentationCoordinates C R)
(e : PresentedGroup R ≃* G) (hC : C.EmbedsInTwoManifold) :
IsFGroup G ∨ IsFreeProductOfCyclicGroups GProposition 3.5.6
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-5-6 (1): if G is either an F-group or a free product of at most countably many cyclic groups, and G is finite, then G has a presentation whose Cayley complex embeds in the 2-sphere.
universe u v w z
local notation "𝔼²" => EuclideanSpace ℝ (Fin 2)
local notation "𝕊²" =>
{ x : EuclideanSpace ℝ (Fin 3) // x ∈ Metric.sphere (0 : EuclideanSpace ℝ (Fin 3)) 1 }
variable {G : Type u} [Group G]
theorem exists_spherical_cayley_presentation
(hG : IsFGroup G ∨ IsCountableFreeProductOfCyclicGroups G)
(hfin : Finite G) :
∃ (X : Type v) (R : Set (FreeGroup X)) (C : TwoComplex)
(coords : CayleyComplex.Coordinates.PresentationCoordinates C R)
(e : PresentedGroup R ≃* G), C.EmbedsInSphereLemma 3.5.7
Lean contributors (project-level attribution): Zichen Wang.
Lemma 3-5-7: if every ball Bₙ(C, 1) in the Cayley graph of the presentation (X; R) has finite, effectively constructible vertex set, then the presentation has solvable word problem. In the owner formulation, each intrinsic ball WordMetricBall R n is already an actual 1-complex, and the effective hypothesis supplies only the vertex-side data used by the word-problem argument: a finite codable structure on the genuine ball vertices together with the computable source-facing evaluation map from bounded signed words into that intrinsic ball.
universe u
namespace GroupPresentation
-- Layer triage:
-- `source-facing`: the word-metric balls around `1` in the Cayley graph of a presentation
-- `(X; R)`, and the consequence that effective finite construction of all such balls yields a
-- solution to the word problem.
-- `core/canonical`: `PresentedGroup R` is mathlib's owner for the group presented by `R`,
-- `HasSolvableWordProblem R` is the chapter owner predicate for decidability of the word problem,
-- `cayleyOneComplex R` below is the intrinsic Cayley `1`-skeleton of the presentation, and
-- `OneComplex.Subcomplex` is the chapter owner for the ball `Bₙ(C, 1)` as a genuine `1`-skeleton.
-- `bridge/view`: `wordMetricBallSubcomplex R n` is the source-facing ball inside the ambient
-- Cayley `1`-skeleton, while `WordMetricBall R n` is the derived `1`-complex carried by that
-- subcomplex.
-- Domain sampling:
-- 1. `PresentedGroup R` is mathlib's owner abstraction for the group with presentation `(X; R)`.
-- 2. `HasSolvableWordProblem R` from Definition `2-1-4` is the project owner predicate for the
-- conclusion of the lemma.
-- 3. `OneComplex.Subcomplex` from Lemma `3-3-8` is the chapter owner for intrinsic `1`-skeleton
-- subobjects, so the ball should be expressed as a genuine subcomplex of the Cayley graph.
-- 4. `SignedLetter.inv` and `SignedLetter.value` are the chapter owners for orientation reversal
-- and evaluation of a signed generator, so the intrinsic Cayley graph should reuse them rather
-- than keeping parallel local copies.
-- 5. `FreeGroup.norm` is the canonical owner for reduced-word length on `FreeGroup X`, so the
-- textbook metric ball is organized around that owner rather than raw list length.
-- Primitive vs. derived:
-- the primitive data are the relator set `R`, the radius `n`, and the actual Cayley `1`-skeleton;
-- `wordMetricBallSubcomplex R n` is the source-facing ball object, `WordMetricBall R n` is the
-- derived `1`-complex it carries, and the extra effective data needed for Lemma `3-5-7` are only
-- a finite codable structure on the actual vertex carrier of that intrinsic ball together with the
-- computable source-facing evaluation map sending a bounded signed word to its canonical ball
-- vertex. The oriented-edge carrier of the same ball remains derived structure of the owner
-- `1`-complex, not primitive public data of the effective hypothesis.
variable {X : Type u}
variable [Primcodable X]
theorem hasSolvableWordProblem_of_finite_effective_wordMetricBalls
(R : Set (FreeGroup X))
(hball : ∀ n, HasFiniteConstructibleWordMetricBall R n) :
HasSolvableWordProblem RProposition 3.5.9
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-5-9: if the Cayley complex of a finite presentation (X; R) satisfies the maximum principle, then the presentation has solvable word problem.
universe u
open Quiver.Path
namespace CayleyComplex.Coordinates
variable {X : Type u} {R : Set (FreeGroup X)} {C : TwoComplex}
variable [Primcodable X] [Finite X]
theorem hasSolvableWordProblem_of_maximumPrinciple
(coords : PresentationCoordinates C R) (hR : Set.Finite R)
(hmax : SatisfiesMaximumPrinciple coords) :
GroupPresentation.HasSolvableWordProblem R3.6 — F-Groups Continued
Proposition 3.6.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-6-1 (1): a nontrivial left-translation automorphism of a Cayley complex fixes no vertex.
universe u v w
local notation "𝔼²" => EuclideanSpace ℝ (Fin 2)
namespace CayleyComplex.Coordinates
variable {G : Type u} [Group G]
variable {Y : Type v} {Rel : Type w}
variable {C : TwoComplex} {edgeLabel : Y → G}
local notation "GeometricEdge" => OneComplex.GeometricEdge C.skeleton
theorem leftTranslation_fixes_no_vertex
(coords : Coordinates C edgeLabel Rel) {g : G} (hg : g ≠ 1)
(v : C.skeleton) :
(coords.leftTranslation g).vertexPerm v ≠ vProposition 3.6.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-6-2: every nontrivial finite-order element of a planar group PresentedGroup R is conjugate to a unique proper positive power of the unique primitive relator root lying under its face stabilizer, and the full set of conjugators is a left coset of the cyclic subgroup generated by that primitive root image.
universe u
open GroupPresentation
open scoped Pointwise
namespace CayleyComplex.Coordinates
variable {X : Type u} {R : Set (FreeGroup X)} {C : TwoComplex}
variable {S : Set (FreeGroup X)}
variable (coords : PresentationCoordinates C R) (hplanar : C.EmbedsInPlane)
variable (m : FreeGroup X → ℕ+) (hR : IsPrimitiveRelatorPowerFamily R S m)
local notation "G" => PresentedGroup R
local notation "q" => PresentedGroup.mk R
theorem existsUnique_primitiveRelatorRoot_power_conjugatorLeftCoset_of_nontrivial_isOfFinOrder
{g : G} (hg : g ≠ 1) (hfin : IsOfFinOrder g) :
∃! s : FreeGroup X,
IsPrimitiveRelatorRoot S s ∧
∃! b : ℕ,
0 < b ∧
b < (m s : ℕ) ∧
IsConj g ((q s) ^ b) ∧
∃ u : G,
{v : G | g = v * (q s) ^ b * v⁻¹} = u • (Subgroup.zpowers (q s) : Set G)3.7 — Fuchsian Complexes
Proposition 3.7.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-1 (1): every Fuchsian complex of G admits a modified presentation whose modified Cayley complex is dual to it.
universe u v w x y
variable {G : Type u} [Group G]
theorem exists_modifiedPresentation_with_dual_modifiedCayleyComplex
(K : FuchsianComplex G) :
∃ (P : ModifiedPresentation G) (C : ModifiedCayleyComplex P)
(dual : C.complex.Duality K.complex),
C.RealizesFuchsianDuality K dualProposition 3.7.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-2: a finite modified presentation together with a strictly planar modified Cayley complex admits a dual Fuchsian complex, and that dual complex is without reflections exactly in the ordinary case.
universe u
namespace ModifiedCayleyComplex
variable {G : Type u} [Group G]
variable {P : ModifiedPresentation G} [Finite P.X] [Finite P.J] [Finite P.Rel]
variable (C : ModifiedCayleyComplex P)
local notation "Complex" => C.complex
theorem exists_dualFuchsianComplex_of_strictlyPlanar
(hplanar : TwoComplex.EmbedsInPlane Complex)
(hsimple : ∀ D : C.complex.Face, TwoComplex.HasSimpleBoundary Complex D) :
∃ K : FuchsianComplex G, ∃ dual : TwoComplex.Duality Complex K.complex,
C.RealizesFuchsianDuality K dual ∧ (K.WithoutReflections ↔ P.IsOrdinary)Proposition 3.7.3
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-3: if K is a Fuchsian complex for a group G and H is a subgroup of G, then every chosen planar realization of K induces a Fuchsian complex L for H whose geometric faces are unions of geometric faces of K in that realization.
universe u v
local notation "𝔼²" => EuclideanSpace ℝ (Fin 2)
open TwoComplex
variable {G : Type u} [Group G]
theorem exists_faceUnionRefinement_fuchsianComplex_of_subgroup
(K : FuchsianComplex G)
(hconnected : Quiver.IsStronglyConnected (Quiver.Symmetrify K.complex.skeleton))
(hsimply : IsSimplyConnected K.complex)
(fineEmbedding : TwoManifoldEmbedding K.complex 𝔼²)
(H : Subgroup G) :
∃ L : FuchsianComplex H,
Quiver.IsStronglyConnected (Quiver.Symmetrify L.complex.skeleton) ∧
IsSimplyConnected L.complex ∧
∃ coarseEmbedding : TwoManifoldEmbedding L.complex 𝔼²,
∀ D : GeometricFace L.complex,
∃ facePieces : Set (GeometricFace K.complex),
coarseEmbedding.geometricFaceSet D =
fineEmbedding.geometricFaceUnion facePiecesProposition 3.7.4
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-4 (1): every finite-index subgroup of an F-group is again an F-group.
universe u
variable {G : Type u} [Group G]
variable (H : Subgroup G)
theorem isFGroup_of_finiteIndex_subgroup
(hG : IsFGroup G)
[H.FiniteIndex] :
IsFGroup HProposition 3.7.5
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-5: if two subcomplexes with simple boundaries in a planar complex intersect only in a common boundary arc, then the associated area measure is additive on their union.
universe u v w
open Quiver
open Quiver.Path
namespace TwoComplex
variable {C : TwoComplex.{w}}
namespace AngleMeasure
theorem associatedAreaMeasure_union_eq_add_of_intersectsOnlyInCommonBoundaryArc
(α : AngleMeasure C) (hplanar : C.EmbedsInPlane)
(S₁ S₂ : Subcomplex C) (hS₁ : S₁.HasSimpleBoundary) (hS₂ : S₂.HasSimpleBoundary)
(hinter : S₁.IntersectsOnlyInCommonBoundaryArc S₂) :
α.associatedAreaMeasure (S₁.union S₂) =
α.associatedAreaMeasure S₁ + α.associatedAreaMeasure S₂Corollary 3.7.6
Lean contributors (project-level attribution): Zichen Wang.
Corollary 3-7-6: if a subcomplex S of a planar complex K is the union of an ordered list of faces D₁, …, Dₙ, every nonempty initial union D₁ ∪ ⋯ ∪ Dᵢ is bounded by a simple closed curve in a chosen planar embedding, and faceArea records the associated area of each listed geometric face via the canonical one-face subcomplexes of S, then α(S) is the sum of the areas of the listed faces.
universe u
namespace TwoComplex
local notation "𝔼²" => EuclideanSpace ℝ (Fin 2)
local notation "𝕊¹" => Metric.sphere (0 : 𝔼²) 1
theorem associatedAreaMeasure_subcomplex_eq_sum_faceAreas_of_prefix_simpleClosedBoundary
(K : TwoComplex.{u})
(embedding : TwoManifoldEmbedding K 𝔼²)
(α : AngleMeasure K)
(faceArea : GeometricFace K → ℝ)
(S : Subcomplex K)
(faces : List K.Face)
(hcover : ∀ D : K.Face, D ∈ S.faceSet ↔ ∃ E ∈ faces, D = E ∨ D = E⁻¹)
(hpairwise : faces.Pairwise fun D E ↦ D ≠ E ∧ D ≠ E⁻¹)
(hprefix :
∀ i : ℕ, 1 ≤ i → i ≤ faces.length →
embedding.IsBoundedBySimpleClosedCurve (S.listedPrefixSubcomplex faces hcover i))
(hfaceArea :
∀ (D : K.Face) (hD : D ∈ faces),
α.associatedAreaMeasure (S.restrictFace D (mem_faceSet_of_mem_list hcover hD)) =
faceArea (⟦D⟧ : GeometricFace K)) :
α.associatedAreaMeasure S =
(faces.map fun D ↦ faceArea (⟦D⟧ : GeometricFace K)).sumProposition 3.7.7
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-7: every Fuchsian complex for G admits an angle measure that is invariant under the action of G.
universe u
namespace FuchsianComplex
variable {G : Type u} [Group G]
theorem exists_invariant_angleMeasure (K : FuchsianComplex G) :
∃ α : AngleMeasure K, α.IsInvariantProposition 3.7.8
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-8: for a Fuchsian complex attached to a strictly quadratic power presentation, the curvature of the boundary of any face with respect to an invariant angle measure is 2π (|X| - ∑_{s ∈ S} 1 / m(s)).
universe u v w
open scoped BigOperators
variable {G : Type u} [Group G]
namespace FuchsianComplex
theorem boundaryCurvature_eq_two_pi_mul_card_generators_sub_sum_reciprocal_multiplicity
(P : FGroupPowerPresentation G) (K : FuchsianComplex G) (Γ : FaceBoundaryGeometry K)
(α : AngleMeasure K) (hα : α.IsInvariant) (Δ : Γ.Face) :
Γ.boundaryCurvature α Δ =
2 * Real.pi *
((Nat.card P.X : ℝ) -
P.S.sum (fun s ↦ (1 : ℝ) / ((P.multiplicity s : ℕ) : ℝ)))Proposition 3.7.9
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-9: if H is a finite-index subgroup of the F-group G, then Proposition 3-7-4 makes H into an F-group again, and any Section 7 Fuchsian measures μ(G) and μ(H) satisfy the multiplicative index formula μ(H) = index(H) * μ(G).
universe u
open scoped BigOperators
variable {G : Type u} [Group G]
open FGroupPresentation
variable (H : Subgroup G) [H.FiniteIndex] {μG μH : ℚ}
theorem finiteIndex_subgroup_fuchsianMeasure_eq_index_mul
(hμG : IsMeasure G μG) (hμH : IsMeasure H μH) :
μH = (H.index : ℚ) * μGProposition 3.7.10
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-10: every abelian subgroup of a presented group admitting a planar Cayley realization is either cyclic or free abelian of rank 2. The source continues with a classification of the planar groups containing a rank-two free abelian subgroup; that exceptional-family list is not present in the current excerpt, so only the visible subgroup dichotomy is formalized here.
universe u
namespace CayleyComplex.Coordinates
variable {X : Type u} {R : Set (FreeGroup X)} {C : TwoComplex}
local notation "PG" => PresentedGroup R
local notation "RankTwoFreeAbelian" => Multiplicative (FreeAbelianGroup (Fin 2))
theorem abelian_subgroup_of_planar_presentedGroup_isCyclic_or_freeAbelian_rank_two
(coords : PresentationCoordinates C R)
(hplanar : C.EmbedsInPlane)
(H : Subgroup PG) (hab : IsMulCommutative H) :
IsCyclic H ∨ Nonempty (H ≃* RankTwoFreeAbelian)Proposition 3.7.11
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-11: every abelian subgroup of a planar group is either cyclic or free abelian of rank 2.
universe u v
open FGroupPresentation
open CayleyComplex.Coordinates
variable {G : Type u} [Group G]
variable {X : Type v} {R : Set (FreeGroup X)} {C : TwoComplex}
local notation "PG" => PresentedGroup R
local notation "RankTwoFreeAbelian" => Multiplicative (FreeAbelianGroup (Fin 2))
theorem abelian_subgroup_of_planar_group_isCyclic_or_freeAbelian_rank_two
(coords : PresentationCoordinates C R)
(e : PG ≃* G) (hplanar : C.EmbedsInPlane)
(H : Subgroup G) (hab : IsMulCommutative H) :
IsCyclic H ∨ Nonempty (H ≃* RankTwoFreeAbelian)Proposition 3.7.12
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-12: every finitely generated subgroup of SL(n, F) is residually finite.
universe u
open scoped MatrixGroups
variable {F : Type u} [Field F]
variable {n : ℕ}
-- Layer triage:
-- `source-facing`: a finitely generated subgroup `H` of the special linear group `SL(n, F)`.
-- `core/canonical`: the subgroup owner `Subgroup (SL(n, F))`, together with the owner predicates
-- `Subgroup.FG` for finite generation and `Group.ResiduallyFinite` for residual finiteness.
-- `bridge/view`: `Matrix.SpecialLinearGroup.toLin'_equiv` identifies the matrix group `SL(n, F)`
-- with the intrinsic module-level special linear group on `Fin n → F`, but this bridge does not
-- replace the source-facing matrix formulation of the proposition.
-- Domain sampling:
-- 1. `SL(n, F)` from `Matrix.SpecialLinearGroup` is the chapter's source-facing realization of the
-- special linear group.
-- 2. `Matrix.SpecialLinearGroup.toLin'_equiv` is the canonical bridge from the matrix
-- presentation to the module-level owner `SpecialLinearGroup F (Fin n → F)`.
-- 3. `Subgroup (SL(n, F))` is the canonical owner abstraction for the subgroup named in the
-- proposition.
-- 4. `Group.FG` on the subgroup carrier and `Group.ResiduallyFinite` are mathlib's owner
-- predicates for the two mathematical properties appearing in the statement.
-- 5. `Group.fg_iff_subgroup_fg` is the canonical bridge between the subgroup-facing finite
-- generation predicate `H.FG` and the owner instance `Group.FG H`.
-- Best owner abstraction:
-- keep the public statement at the subgroup-owner level `Subgroup (SL(n, F))`. The finitely
-- generated linear-group input is exactly the owner instance `Group.FG H`, and the matrix-to-
-- module bridge for `SL(n, F)` remains proof infrastructure rather than a second public owner.
-- Primitive vs. derived:
-- the primitive public content is the owner instance `Group.ResiduallyFinite H` for a finitely
-- generated subgroup `H ≤ SL(n, F)`, with `Group.FG H` as the only extra owner-level input. The
-- explicit theorem below is the source-facing bridge back to the textbook formulation using
-- `H.FG`. The ambient field `F` and size parameter `n` are inferred from `H`, and the module-
-- level special linear group equivalence is derived bridge data rather than additional primitive
-- content. There is no upstream theorem in the project or mathlib giving Mal'cev's
-- residual-finiteness result for finitely generated linear subgroups. The source restriction
-- `n ≥ 1` is mathematically redundant here, since `SL(0, F)` is trivial and hence residually
-- finite.
variable (H : Subgroup (SL(n, F)))
theorem residuallyFinite_of_fg_subgroup_specialLinearGroup (hH : H.FG) :
Group.ResiduallyFinite HProposition 3.7.13
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-13: every F-group contains a torsion-free subgroup of finite index.
universe u
variable {G : Type u} [Group G]
theorem exists_torsionFree_finiteIndex_subgroup_of_isFGroup
(hG : IsFGroup G) :
∃ H : Subgroup G, H.FiniteIndex ∧ IsMulTorsionFree HProposition 3.7.14
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-7-14: if a torsion-free group contains a central free abelian subgroup of finite index, then the ambient group is itself free abelian.
universe u v w
open Subgroup
variable {G : Type u} [Group G] [IsMulTorsionFree G]
theorem exists_mulEquiv_freeAbelianGroup_of_torsionFree_of_central_freeAbelian_subgroup_finiteIndex
(A : Subgroup G) [A.FiniteIndex] (hAcentral : A ≤ center G)
(hAfree : Nonempty (Σ ι : Type v, A ≃* Multiplicative (FreeAbelianGroup ι))) :
Nonempty (Σ κ : Type w, G ≃* Multiplicative (FreeAbelianGroup κ))3.8 — Planar Groups with Reflections
Definition 3.8.1
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-8-1: an NEC group is a group admitting a connected simply connected planar Fuchsian complex whose action is regular on a nonempty set of geometric faces.
universe u v
open MulAction TwoComplex
class IsNECGroup (G : Type u) [Group G] : Prop where
/-- An NEC group admits a planar simply connected connected Fuchsian complex with a regular
geometric-face action of `G`. -/
exists_fuchsianComplex :
∃ K : FuchsianComplex.{u, v} G,
Quiver.IsStronglyConnected (Quiver.Symmetrify K.complex.skeleton) ∧
TwoComplex.IsSimplyConnected K.complex ∧
K.complex.EmbedsInPlane ∧
K.action.IsRegularOnGeometricFacesDefinition 3.8.2
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-8-2: a nontrivial element is a reflection in a geometric edge when the action fixes that geometric edge.
universe u
namespace FuchsianComplex
variable {G : Type u} [Group G]
variable (K : FuchsianComplex G)
local notation "Edge" => OneComplex.Edge K.complex.skeleton
local notation "GeometricEdge" => OneComplex.GeometricEdge K.complex.skeleton
def IsReflectionIn (g : G) (e : GeometricEdge) : Prop :=
g ≠ 1 ∧ (K.action g).geometricEdgePerm e = eProposition 3.8.3
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-8-3: every NEC group admits a finite presentation G = (X ∪ J; R₀ ∪ R₁ ∪ R₂) in which J is a disjoint union of ordered blocks J_j = (x_{j1}, …, x_{jn_j}), R₀ consists of the involution relators x_{jh}², R₁ consists of the power relators t_{jh}^{m_{jh}} = (x_{jh} a_{jh} x_{j,h+1} a_{jh}^{-1})^{m_{jh}}, R₂ consists of the power relators s_k^{m_k} on words in X, and the combined family of words a_{jh} and s_k is strictly quadratic over X.
universe u v w x
variable {G : Type u} [Group G]
-- Proof sketch: start from the planar simply connected `2`-complex with regular face action given
-- by the NEC-group structure. Choose representatives for the boundary cycles of the quotient
-- orbifold, record the edge-reflection generators `x_{jh}`, read the conjugating words `a_{jh}`
-- from connecting paths between consecutive reflections, and collect the remaining elliptic
-- relators as the words `s_k^{m_k}`. The resulting relator family presents `G`, and the planar
-- incidence argument shows that the combined auxiliary word system is strictly quadratic.
theorem exists_necPresentation_of_isNECGroup (hG : IsNECGroup G) :
∃ (X : Type v) (_ : Finite X)
(BoundaryComponent : Type w) (_ : Finite BoundaryComponent)
(boundaryLength : BoundaryComponent → ℕ+)
(InteriorRelator : Type x) (_ : Finite InteriorRelator)
(connectorWord : (j : BoundaryComponent) → Fin (boundaryLength j : ℕ) → FreeGroup X)
(boundaryMultiplicity : (j : BoundaryComponent) → Fin (boundaryLength j : ℕ) → ℕ+)
(interiorWord : InteriorRelator → FreeGroup X)
(interiorMultiplicity : InteriorRelator → ℕ+)
(e :
PresentedGroup
(necRelatorSet boundaryLength connectorWord boundaryMultiplicity interiorWord
interiorMultiplicity) ≃* G),
IsStrictlyQuadraticSet (necOrdinaryWordSystem boundaryLength connectorWord interiorWord)3.9 — Singular Subcomplexes
Proposition 3.9.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-9-1: every singular subcomplex admits a finite component normal form in which each component is either a singular disc with an explicit reduced boundary cycle or a singular sphere.
universe w
open Quiver.Path
namespace TwoComplex.Subcomplex
variable {C : TwoComplex.{w}}
theorem exists_disc_or_sphere_component_normalForm_of_singularSubcomplex
(S : Subcomplex C) (hS : IsSingularSubcomplex S) :
∃ (ι : Type*) (_ : Fintype ι) (components : ι → Subcomplex C),
IsComponentDecomposition S components ∧
∀ i : ι,
(∃ boundary : CyclicPath (components i).skeleton.toOneComplex,
IsSingularDisc (components i) boundary) ∨
IsSingularSphere (components i)Proposition 3.9.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-9-2: if a reduced word w represents an element of the normal closure of the relators R, then there is a simple singular disc carried by an actual Cayley 2-complex for (X; R) whose boundary label, read in the chosen Cayley coordinates, is exactly w.
universe u
open Quiver.Path
open CayleyComplex.Coordinates
open TwoComplex.Subcomplex
namespace GroupPresentation
variable {X : Type u}
theorem exists_cayleySingularDisc_of_reduced_mem_normalClosure
(R : Set (FreeGroup X)) (w : List (SignedLetter X))
(hw_reduced : FreeGroup.IsReduced w)
(hw_normal : FreeGroup.mk w ∈ Subgroup.normalClosure R) :
∃ (C : TwoComplex) (coords : PresentationCoordinates C R)
(S : TwoComplex.Subcomplex C) (p : Loop S.skeleton.toOneComplex),
S.IsSingularDisc (cyclicPath p) ∧
boundaryLabel coords (S.skeleton.inclusion.mapLoop p) = wProposition 3.9.3
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-9-3: if P lies in the subgroup generated by the basis subset Y, Q lies in the subgroup generated by Z, and Q is contained in the normal closure of P, then there is a set M in the subgroup generated by Y ∩ Z which still lies in the normal closure of P and whose normal closure contains Q.
universe u v
open Subgroup (closure normalClosure)
variable {X : Type u} {F : Type v} [Group F]
namespace FreeGroupBasis
variable (basis : FreeGroupBasis X F)
local notation "Gp[" Y "]" => closure (basis '' Y)
-- Layer triage:
-- `source-facing`: a free group `F` equipped with a chosen basis `basis : FreeGroupBasis X F`,
-- basis subsets `Y, Z : Set X`, relator sets `P, Q : Set F` lying in the generated subgroups
-- `Gp(Y)` and `Gp(Z)`, and the existence of an intermediate relator set `M` supported on
-- `Y ∩ Z`.
-- `core/canonical`: the owner namespace `FreeGroupBasis`, together with `Subgroup.closure` and
-- `Subgroup.normalClosure`.
-- `bridge/view`: the source subgroup notation `Gp(Y)` is rendered by the local notation `Gp[Y]`
-- backed by the canonical owner `closure (basis '' Y)`, while the normal closure remains the
-- owner expression `normalClosure P`.
-- Domain sampling:
-- 1. `FreeGroupBasis X F` is the canonical owner for a free group together with a specified
-- basis, and nearby basis-dependent Magnus theorems already live in `namespace FreeGroupBasis`.
-- 2. `Subgroup.closure` is the canonical owner for the subgroup generated by a subset.
-- 3. `Subgroup.normalClosure` is the canonical owner for the normal closure of a subset.
-- Primitive vs. derived:
-- the primitive data are the chosen basis, the two basis subsets, and the relator sets `P` and
-- `Q`; the generated subgroups and normal closures are derived canonically from those data, so no
-- extra wrapper around the three subset conditions is needed.
-- Proof sketch: reduce to the case where `Y ∪ Z` is the whole basis and `Q` is a singleton
-- cyclically reduced word. Fill that word by a simple van Kampen diagram over the relators `P`,
-- delete interior edges, and let `M` be the set of boundary labels of the resulting faces. Those
-- boundary labels lie in the subgroup generated by `Y ∩ Z`, remain in the normal closure of `P`,
-- and their normal closure contains the original set `Q`.
theorem exists_intersection_relator_set_of_subset_normalClosure
(Y Z : Set X) (P Q : Set F)
(hP : P ⊆ Gp[Y])
(hQ : Q ⊆ Gp[Z])
(hQncl : Q ⊆ normalClosure P) :
∃ M : Set F,
M ⊆ Gp[Y ∩ Z] ∧
M ⊆ normalClosure P ∧
Q ⊆ normalClosure MProposition 3.9.4
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-9-4: for the canonical basis of FreeGroup X, this is exactly Proposition 2-5-1. The source phrase “x occurs in a word” is already captured by basisLetterOccurs basis x, so this item is a direct recall of the upstream owner theorem rather than a duplicate free-group-only wrapper.
universe u
variable {X : Type u}
local notation "basis" => FreeGroupBasis.ofFreeGroup X
-- Layer triage:
-- `source-facing`: Proposition 3-9-4 is the free-group specialization of Magnus's normal-closure
-- occurrence theorem for a cyclically reduced relator.
-- `core/canonical`: `FreeGroupBasis.ofFreeGroup X`, `basisLetterOccurs`,
-- `FreeGroup.IsCyclicallyReduced`, and `Subgroup.normalClosure`.
-- `bridge/view`: specializing the basis-level theorem to the canonical basis of `FreeGroup X`
-- recovers the textbook wording that a generator occurring in `r` must also occur in any
-- nontrivial consequence `w` of `r`.
--
-- Domain sampling:
-- 1. `FreeGroupBasis.ofFreeGroup X` is the canonical basis owner for `FreeGroup X`.
-- 2. `basisLetterOccurs` from Proposition `1-7-4` is the chapter owner predicate for the source
-- phrase “the generator `x` occurs in a word”.
-- 3. `FreeGroupBasis.basisLetterOccurs_of_mem_normalClosure_singleton_of_isCyclicallyReduced`
-- from
-- Proposition `2-5-1` is the already-canonical Magnus statement at the correct owner level.
-- 4. `FreeGroup.IsCyclicallyReduced` and `Subgroup.normalClosure` are the canonical reduced-word
-- and normal-closure constructions on which that theorem is built.
--
-- Primitive vs. derived:
-- the primitive data remain the relator `r`, the normal-closure element `w`, and the generator
-- `x`; the occurrence relation is derived owner-side API through the canonical basis, so this
-- file does not keep a second public theorem phrased by raw membership in `toWord.map Prod.fst`.
#check
(FreeGroupBasis.basisLetterOccurs_of_mem_normalClosure_singleton_of_isCyclicallyReduced basis :
∀ {r w : FreeGroup X} {x : X},
FreeGroup.IsCyclicallyReduced r.toWord →
basisLetterOccurs basis x r →
w ∈ Subgroup.normalClosure ({r} : Set (FreeGroup X)) →
w ≠ 1 →
basisLetterOccurs basis x w)Proposition 3.9.5
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-9-5: if r is a staggered presentation relative to X₀ and a nontrivial word w lies in the normal closure of r, then w contains generators of X₀; choosing the least and greatest such generators xₐ and x_b, the word already lies in the normal closure of the relators whose distinguished generators from X₀ all lie between xₐ and x_b.
universe u v
namespace GroupPresentation
variable {X : Type u} [LinearOrder X]
variable {J : Type v} [Preorder J]
open Subgroup
theorem exists_extreme_distinguished_support_and_interval_normalClosure
(X₀ : Set X) (r : J → FreeGroup X) (hstaggered : IsStaggeredPresentation X₀ r)
{w : FreeGroup X} (hw : w ∈ normalClosure (Set.range r)) (hwne : w ≠ 1) :
∃ xₐ x_b : X,
HasExtremeDistinguishedSupport X₀ w xₐ x_b ∧
w ∈ normalClosure (relatorsSupportedOnDistinguishedInterval X₀ r xₐ x_b)Proposition 3.9.6
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-9-6: let coords : PresentationComplex.Coordinates K X (Set.range r) realize the presentation complex of a staggered relator family r, let S be a singular disc, let φ : S.complex → K be a diagram over that complex, and let p be a loop carrying the boundary cycle of S. If x is either the greatest or the least distinguished generator from X₀ occurring on the edges of S.complex, then x already occurs in the boundary word read from p.
universe u v w z
open Quiver.Path
open GroupPresentation
namespace PresentationComplex.Coordinates
variable {X : Type u} {R : Set (FreeGroup X)} {K : TwoComplex.{v}}
variable {D : TwoComplex.{v}}
variable [LinearOrder X]
variable {J : Type z} [Preorder J]
local notation "basis" => FreeGroupBasis.ofFreeGroup X
-- Proof sketch: the staggered ordering and the disc-diagram topology force an extremal
-- distinguished face to survive on the outer boundary. The chapter owner
-- `TwoComplex.Subcomplex.IsSingularDisc` packages the source disc together with the fact that the
-- chosen loop `p` carries its boundary cycle. Reading the resulting boundary word through
-- `coords.boundaryLabel φ p`, the extremal generator therefore occurs in that canonical word.
theorem basisLetterOccurs_boundaryLabel_of_isGreatest_or_isLeast
(X₀ : Set X) (r : J → FreeGroup X) (hstaggered : IsStaggeredPresentation X₀ r)
{C : TwoComplex.{v}} (S : TwoComplex.Subcomplex C)
{K : TwoComplex.{v}} (coords : Coordinates K X (Set.range r))
(φ : TwoComplex.Hom S.complex K) (p : Loop S.skeleton.toOneComplex)
(hS : TwoComplex.Subcomplex.IsSingularDisc S (cyclicPath p)) {x : X}
(hx : IsGreatest (X₀ ∩ coords.occurringGenerators φ) x ∨
IsLeast (X₀ ∩ coords.occurringGenerators φ) x) :
basisLetterOccurs basis x (FreeGroup.mk (coords.boundaryLabel φ p))Proposition 3.9.7
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-9-7: if r is a staggered relator family on the indexed generators Σ i, Y i, then any actual presentation complex K(Σ i, Y i; range r) admits no reduced spherical diagram over it.
universe u v w
open GroupPresentation
variable {ι : Type u} [LinearOrder ι]
variable {Y : ι → Type v}
variable {J : Type w} [Preorder J]
local notation "Generators" => Σ i, Y i
-- Proof sketch: argue by contradiction from a reduced spherical diagram over the presentation
-- complex. A staggered relator family admits an extremal face in any spherical diagram; the local
-- injectivity of `TwoComplex.Hom.mapBoundaryStar` at each source vertex forbids the cancellation
-- that such an extremal face would force, so no reduced spherical diagram can exist.
theorem no_reduced_spherical_diagram_over_staggered_presentation
(r : J → FreeGroup Generators) (hstaggered : IsStaggeredRelatorFamily r) {K : TwoComplex}
(coords : PresentationComplex.Coordinates K Generators (Set.range r)) :
¬ ∃ (D : TwoComplex) (φ : TwoComplex.Hom D K),
D.IsSphericalDiagram ∧
∀ v : D.skeleton, Function.Injective (φ.mapBoundaryStar v)3.10 — Spherical Diagrams
Definition 3.10.1
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-10-1 (1): a spherical diagram over (X; R) is a finite combinatorial sphere together with a dimension-preserving map into the actual Cayley complex C(X; R).
universe u
open Quiver.Path
open CayleyComplex.Coordinates
namespace CayleyComplex.Coordinates
variable {X : Type u} {R : Set (FreeGroup X)} {C : TwoComplex}
structure SphericalDiagram
(coords : PresentationCoordinates C R) where
/-- The finite combinatorial sphere underlying the spherical diagram. -/
source : TwoComplex
/-- The dimension-preserving map into the Cayley complex `C(X; R)`. -/
map : TwoComplex.Hom source C
/-- The source has finitely many vertices. -/
finite_vertex : Finite source.skeleton
/-- The source has finitely many oriented edges. -/
finite_edge : Finite source.skeleton.Edge
/-- The source has finitely many oriented faces. -/
finite_face : Finite source.Face
/-- The source is a combinatorial sphere. -/
spherical : source.IsSphericalDiagramDefinition 3.10.2
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-10-2: the textbook first-kind Peiffer transformation is the converse relation Function.swap List.IsAdjacentConjugatingSwap of the chapter owner relation.
universe u
namespace List
variable {G : Type u} [Group G]
#check Function.swap IsAdjacentConjugatingSwapDefinition 3.10.3
Lean contributors (project-level attribution): Zichen Wang.
Definition 3-10-3: the displayed second-kind Peiffer transformation is the chapter owner relation List.IsAdjacentConjugatingSwap. Its basic invariants are part of that owner API, so this file recalls the canonical declaration directly.
universe u
namespace List
variable {G : Type u} [Group G]
#check IsAdjacentConjugatingSwapProposition 3.10.4
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-10-4: the actual Cayley complex C(X; R) is aspherical exactly when the relator family R admits no nontrivial identity among relations.
universe u
namespace GroupPresentation
variable {X : Type u}
theorem isAspherical_iff_no_nontrivial_identities_among_relations
{R : Set (FreeGroup X)} {C : TwoComplex}
(coords : CayleyComplex.Coordinates.PresentationCoordinates C R) :
CayleyComplex.Coordinates.IsAspherical coords ↔
¬ HasNontrivialIdentityAmongRelations RCorollary 3.10.5
Lean contributors (project-level attribution): Zichen Wang.
Corollary 3-10-5: if G = (X; R) is aspherical and no relator is a proper power, then the relation module is a free G-module.
universe u
namespace GroupPresentation
variable {X : Type u} {R : Set (FreeGroup X)}
local notation "N" => Subgroup.normalClosure R
local notation "S" => quotientGroupRingRight N
theorem relationIdealQuotient_free_of_isAspherical_of_relators_not_properPower
{C : TwoComplex}
(coords : CayleyComplex.Coordinates.PresentationCoordinates C R)
(_ : CayleyComplex.Coordinates.IsAspherical coords)
(_ : ∀ r ∈ R, ¬ IsProperPower r) :
Module.Free S (relationIdealQuotient N)Corollary 3.10.6
Lean contributors (project-level attribution): Zichen Wang.
Corollary 3-10-6: if G = (X; R) is aspherical and no relator is a proper power, then the canonical trivial ℤG-module has projective dimension at most 2.
universe u
open CategoryTheory Limits
namespace GroupPresentation
variable {X : Type u} {R : Set (FreeGroup X)}
local notation "N" => Subgroup.normalClosure R
local notation "T" => quotientGroupRingTrivialModule N
theorem hasProjectiveDimensionLE_two_trivialModule_of_isAspherical_of_relators_not_properPower
{C : TwoComplex}
(coords : CayleyComplex.Coordinates.PresentationCoordinates C R)
(hAspherical : CayleyComplex.Coordinates.IsAspherical coords)
(hproper : ∀ r ∈ R, ¬ IsProperPower r) :
HasProjectiveDimensionLE T 2Proposition 3.10.7
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-10-7: if condition (I.2) holds, so that the normal closure of the relators has the conjugacy-transversal basis described above, then every actual Cayley complex C(X; R) is aspherical.
universe u v
variable {X : Type u}
theorem isAspherical_of_hasConjugacyTransversalBasis
(R : Set (FreeGroup X)) (hI2 : HasConjugacyTransversalBasis R) {C : TwoComplex}
(coords : CayleyComplex.Coordinates.PresentationCoordinates C R) :
CayleyComplex.Coordinates.IsAspherical coords-
Proposition 3.10.8 — no statement yet (Lean source)
Lean contributors (project-level attribution): Zichen Wang.
3.11 — Aspherical Groups
Proposition 3.11.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-11-1: every actual Cayley complex C(X; Set.range r) of a staggered presentation (X₀; r) is aspherical.
universe u v
namespace GroupPresentation
variable {X : Type u} [LinearOrder X]
variable {J : Type v} [Preorder J]
-- Proof sketch: start with `Δ : CayleyComplex.Coordinates.SphericalDiagram coords` and use the
-- reduction owner from Definition `3-10-1` to delete extremal two-face subdiscs. Once no further
-- reduction is possible, the resulting reduced spherical diagram would contradict Proposition
-- `3-9-7` in the staggered setting. Hence every spherical diagram reduces to the empty one, which
-- is exactly `coords.IsAspherical`.
theorem isAspherical_of_staggered_presentation
(X₀ : Set X) (r : J → FreeGroup X) (hstaggered : IsStaggeredPresentation X₀ r)
{C : TwoComplex}
(coords : CayleyComplex.Coordinates.PresentationCoordinates C (Set.range r)) :
CayleyComplex.Coordinates.IsAspherical coordsProposition 3.11.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-11-2: if every nontrivial element of the relator subgroup has a reduced-word segment longer than half the cyclic length of some element of the source symmetrized relator family R*, then the normal closure N = Subgroup.normalClosure R has a basis consisting of conjugates of elements of R.
universe u v
namespace GroupPresentation
variable {X : Type u}
theorem exists_relator_conjugate_basis_of_normalClosure_of_long_relator_segments
(R : Set (FreeGroup X))
(hsegment : ∀ ⦃w : FreeGroup X⦄ (_ : w ∈ Subgroup.normalClosure R) (_ : w ≠ 1),
HasLongRelatorSegment R w) :
∃ ι : Type v, ∃ basis : FreeGroupBasis ι (Subgroup.normalClosure R),
∀ i : ι, ∃ r : R, IsConj (basis i : FreeGroup X) rProposition 3.11.3
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-11-3: if the Cayley complex C(X; R) of an actual Cayley-complex realization is equipped with a planar embedding whose face images fill the plane, then the relator subgroup N = Subgroup.normalClosure R has a free basis consisting of conjugates of relators from R.
universe u v
namespace CayleyComplex.Coordinates
open GroupPresentation
variable {X : Type u} {R : Set (FreeGroup X)} {C : TwoComplex}
local notation "𝔼²" => EuclideanSpace ℝ (Fin 2)
local notation "N" => Subgroup.normalClosure R
-- Proof sketch: choose a plane-filling embedding from `hfill`, then use that geometric filling
-- hypothesis to show that every nontrivial element of `Subgroup.normalClosure R` has a reduced
-- word segment longer than half of some symmetrized relator. This is exactly the owner
-- hypothesis `HasLongRelatorSegment` required by Proposition `3-11-2`.
theorem normalClosure_has_basis_of_relatorConjugates_of_fillsPlane
(coords : PresentationCoordinates C R)
(embedding : TwoComplex.TwoManifoldEmbedding C 𝔼²)
(hfill : embedding.FillsPlane) :
∃ ι : Type v, ∃ basis : FreeGroupBasis ι N,
∀ i : ι, ∃ r : R, IsConj (basis i : FreeGroup X) rProposition 3.11.4
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-11-4: if (X₀; r) is staggered, every term of a formal product π is a positive relator conjugate, and the total product π.prod contains distinguished generators only from the interval [xₐ, x_b], then Peiffer transformations carry π to a formal product all of whose relator terms are supported in that same interval.
universe u v
namespace GroupPresentation
variable {X : Type u} [LinearOrder X]
variable {J : Type v} [Preorder J]
open Subgroup
-- Proof sketch: each elementary Peiffer step from Proposition `3-10-4` preserves the list
-- product; compose those equalities along the reflexive-transitive closure.
theorem exists_peiffer_reduction_to_interval_supported_positive_relators
(X₀ : Set X) (r : J → FreeGroup X) (hstaggered : IsStaggeredPresentation X₀ r)
(xₐ x_b : X) (π : List (FreeGroup X))
(hπ : π.Forall (fun p ↦ ∃ j, IsConj p (r j)))
(hsupp : SupportedOnDistinguishedInterval X₀ xₐ x_b π.prod) :
∃ π' : List (FreeGroup X),
Relation.ReflTransGen PeifferStep π π' ∧
π'.Forall
(fun q ↦ ∃ j, SupportedOnDistinguishedInterval X₀ xₐ x_b (r j) ∧ IsConj q (r j))3.12 — Coset Diagrams and Permutation Representations
Proposition 3.12.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-12-1: if G is generated by n elements and H has finite index in G, then H is generated by at most H.index * (n - 1) + 1 elements.
universe u
variable {G : Type u} [Group G] [Group.FG G]
theorem finiteIndex_subgroup_rank_le_schreier_bound
(H : Subgroup G) [H.FiniteIndex] {n : ℕ} (hG : Group.rank G ≤ n) :
Group.rank H ≤ H.index * (n - 1) + 1Remark 3.12.2
Lean contributors (project-level attribution): Zichen Wang.
Remark 3-12-2 in source-facing form: one algorithmic step chooses the first pending pair (k, i), completes the corresponding relator-word-labelled row using recorded-equal or fresh labels, and records the resulting equation.
universe u
open Relation (EqvGen)
open List (finRange)
namespace CosetTable
variable {α : Type u} (R : List (List α))
namespace State
variable {R}
def Step (s t : State R) : Prop :=
∃ k i row,
s.nextTask? = some (k, i) ∧
s.IsNextRow k i row ∧
t = s.recordRow i rowProposition 3.12.3
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-12-3: if two subgroup factors acting on Ω satisfy the alternating ping-pong hypotheses on disjoint nonempty subsets Ω₁ and Ω₂, then the subgroup they generate is either their free product, or both factors have order 2 and the generated subgroup is dihedral.
universe u v
open scoped Pointwise
open scoped Monoid.Coprod
open Monoid.Coprod
variable {G : Type u} {Ω : Type v} [Group G] [MulAction G Ω]
variable (G₁ G₂ : Subgroup G)
variable
(Ω₁ Ω₂ : Set Ω)
(hdisjoint : Disjoint Ω₁ Ω₂)
(hΩ₁ : Ω₁.Nonempty)
(hΩ₂ : Ω₂.Nonempty)
(h₁ : ∀ g : G₁, g ≠ 1 → (g : G) • Ω₁ ⊆ Ω₂)
(h₂ : ∀ g : G₂, g ≠ 1 → (g : G) • Ω₂ ⊆ Ω₁)
include hdisjoint hΩ₁ hΩ₂ h₁ h₂
theorem freeProduct_or_dihedral_of_two_subgroup_pingPong
:
Nonempty (G₁ ∗ G₂ ≃* ↥(G₁ ⊔ G₂)) ∨
Nat.card G₁ = 2 ∧ Nat.card G₂ = 2 ∧
∃ n : ℕ, Nonempty (DihedralGroup n ≃* ↥(G₁ ⊔ G₂))Proposition 3.12.4
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-12-4: the matrices A = !![1, 2; 0, 1] and B = !![1, 0; 2, 1] form a free basis of the subgroup of SL(2, ℤ) that they generate.
open scoped MatrixGroups
local notation "A" => sanovMatrixA
local notation "B" => sanovMatrixB
local notation "S" => ({A, B} : Set (SL(2, ℤ)))
theorem sanov_matrices_form_free_basis :
IsFreeGroupBasis {g : Subgroup.closure S | (g : SL(2, ℤ)) ∈ S}Proposition 3.12.5
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-12-5: if G is generated by subgroups G₁ and G₂, their intersection is a proper subgroup of each and is not of index 2 in both, and the action of G on Ω satisfies the two-set ping-pong hypotheses on disjoint nonempty subsets Ω₁ and Ω₂, then G is the amalgamated free product of G₁ and G₂ over G₁ ∩ G₂.
universe u v
open scoped Pointwise
open Monoid
variable {G : Type u} {Ω : Type v} [Group G] [MulAction G Ω]
variable (G₁ G₂ : Subgroup G)
local notation "H" => (G₁ ⊓ G₂ : Subgroup G)
local notation "φ" =>
(fun b : Bool ↦
@Bool.rec
(fun b ↦ H →* Bool.rec G₁ G₂ b)
(Subgroup.inclusion inf_le_left)
(Subgroup.inclusion inf_le_right)
b)
variable
(hgen : G₁ ⊔ G₂ = ⊤)
(hproper₁ : (G₁ ⊓ G₂ : Subgroup G) < G₁)
(hproper₂ : (G₁ ⊓ G₂ : Subgroup G) < G₂)
(hnot_indexTwo :
¬ (((G₁ ⊓ G₂ : Subgroup G)).relIndex G₁ = 2 ∧
((G₁ ⊓ G₂ : Subgroup G)).relIndex G₂ = 2))
(Ω₁ Ω₂ : Set Ω)
(hΩ₁ : Ω₁.Nonempty)
(hΩ₂ : Ω₂.Nonempty)
(hdisj : Disjoint Ω₁ Ω₂)
(h₁₂ : ∀ g : G₁, (g : G) ∉ (G₁ ⊓ G₂ : Subgroup G) → (g : G) • Ω₁ ⊆ Ω₂)
(h₂₁ : ∀ g : G₂, (g : G) ∉ (G₁ ⊓ G₂ : Subgroup G) → (g : G) • Ω₂ ⊆ Ω₁)
(hH₁ : ∀ h : (G₁ ⊓ G₂ : Subgroup G), (h : G) • Ω₁ ⊆ Ω₁)
(hH₂ : ∀ h : (G₁ ⊓ G₂ : Subgroup G), (h : G) • Ω₂ ⊆ Ω₂)
-- Proof sketch: use the relative-index hypothesis to make one of the ping-pong transitions
-- strict, so that every nontrivial alternating reduced word moves one of the two distinguished
-- subsets away from itself. This gives injectivity of the canonical map
-- `comparisonMap G₁ G₂`; surjectivity follows from the generation hypothesis
-- `G₁ ⊔ G₂ = ⊤`.
include hgen hproper₁ hproper₂ hnot_indexTwo Ω₁ Ω₂ hΩ₁ hΩ₂ hdisj h₁₂ h₂₁ hH₁ hH₂
noncomputable def amalgamatedFreeProductEquivOfTwoSubsetPingPong
: Subgroup.amalgamatedProduct G₁ G₂ ≃* G :=
MulEquiv.ofBijective
(Subgroup.amalgamatedProductComparison G₁ G₂)
(comparisonMap_bijective_of_twoSubsetPingPong
G₁ G₂ hgen hproper₁ hproper₂ hnot_indexTwo Ω₁ Ω₂ hΩ₁ hΩ₂ hdisj h₁₂ h₂₁ hH₁ hH₂)Proposition 3.12.6
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-12-6: under the ping-pong hypotheses on the partition Ω = Ωneg ⊔ Ωzero ⊔ Ωpos, the group G is canonically the HNN extension of G₀ with associated subgroups Hplus, Hminus, and stable letter f implementing φ by conjugation.
universe u v
open scoped Pointwise
open HNNExtension
variable {G : Type u} {Ω : Type v} [Group G] [MulAction G Ω]
variable (G₀ : Subgroup G) (Hplus Hminus : Subgroup G₀) (φ : Hplus ≃* Hminus)
variable (f : G)
variable (Ωneg Ωzero Ωpos : Set Ω)
variable (hconj : ∀ a : Hplus, (φ a : G) = f * (a : G) * f⁻¹)
-- The canonical comparison map from the HNN extension onto `G`.
noncomputable def group_hnn_extension_equiv
(hgen : Subgroup.closure ((G₀ : Set G) ∪ {f}) = ⊤)
(hcover : Set.univ = Ωneg ∪ Ωzero ∪ Ωpos)
(hdisj_neg_zero : Disjoint Ωneg Ωzero)
(hdisj_neg_pos : Disjoint Ωneg Ωpos)
(hdisj_zero_pos : Disjoint Ωzero Ωpos)
(hΩneg_nonempty : Ωneg.Nonempty)
(hΩzero_nonempty : Ωzero.Nonempty)
(hΩpos_nonempty : Ωpos.Nonempty)
(hf_pos : f • (Ωzero ∪ Ωpos) ⊆ Ωpos)
(hf_neg : f⁻¹ • (Ωzero ∪ Ωneg) ⊆ Ωneg)
(hmove_pos : ∀ g : G₀, g ∉ Hplus → (g : G) • Ωpos ⊆ Ωzero)
(hmove_neg : ∀ g : G₀, g ∉ Hminus → (g : G) • Ωneg ⊆ Ωzero) :
HNNExtension G₀ Hplus Hminus φ ≃* G3.13 — Behr Graphs
Proposition 3.13.1
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-13-1: if d is an integer-valued distance whose balls S_l(v) are finite for l ≥ 1, if d agrees with the ambient metric on V, and if the bounded descending-path condition (II) holds, then any transitive isometric action of G on V has finitely presented acting group whenever one vertex stabilizer is finitely presented.
universe u v
open MulAction
variable {V : Type u}
open scoped BehrDistance
-- Proof sketch: unfold `integerClosedBall`; its membership predicate is exactly the defining
-- inequality `d v w ≤ l`.
variable {G : Type v} [Group G] [MulAction G V] [PseudoMetricSpace V] [IsIsometricSMul G V]
-- Proof sketch: choose a base vertex `v0` and the finite generating set obtained from the finite
-- ball of radius `k` around `v0`; then follow Behr's rewriting argument using the bounded
-- descending-path hypothesis to control relators and deduce a finite presentation of `G` from a
-- finite presentation of the stabilizer `stabilizer G v0`.
theorem isFinitelyPresented_of_finitelyPresented_stabilizer_of_behr_distance_action
(d : V → V → ℕ)
(hdist : ∀ v w : V, dist v w = d v w)
(hfinite : ∀ v : V, ∀ l : ℕ, 1 ≤ l → (S[d](v, l)).Finite)
(hdesc : SatisfiesBehrConditionII d)
(v0 : V)
(htrans : MulAction.IsPretransitive G V)
(hstab : Group.IsFinitelyPresented (stabilizer G v0)) :
Group.IsFinitelyPresented GProposition 3.13.2
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-13-2: if a locally finite locally convex graph Γ admits a vertex-transitive action of G by graph automorphisms, then finite presentability of one vertex stabilizer implies finite presentability of G. The action is given through the canonical owner G →* (Γ ≃g Γ) of graph automorphisms.
universe u v
open MulAction
open scoped BehrDistance
variable {G : Type u} {V : Type v} [Group G]
theorem isFinitelyPresented_of_finitelyPresented_stabilizer_of_locallyFinite_locallyConvex_graph
(Γ : SimpleGraph V)
[Γ.LocallyFinite]
(hconvex : Γ.IsLocallyConvex)
(ρ : G →* (Γ ≃g Γ))
(v0 : V)
(htrans : ∀ p q : V, ∃ g : G, (ρ g) p = q)
(hstab : letI : MulAction G V := MulAction.compHom V ρ
Group.IsFinitelyPresented (stabilizer G v0)) :
Group.IsFinitelyPresented GLemma 3.13.3
Lean contributors (project-level attribution): Zichen Wang.
Lemma 3-13-3: if X₀ generates the stabilizer of the basepoint o, every k-short orbit step out of o is represented modulo the stabilizer by some element of X₁, and every orbit point g • o is reached from o by a finite product of such k-short steps, then X = X₀ ∪ X₁ generates G.
universe u v
open MulAction
variable {G : Type u} {Ω : Type v} [Group G] [PseudoMetricSpace Ω] [MulAction G Ω]
variable (o : Ω) (X₀ X₁ : Set G) (k : ℝ)
-- Proof sketch: first show that any short step `g` with `dist o (g • o) ≤ k` lies in
-- `Subgroup.closure (X₀ ∪ X₁)` because `g • o` is also `x • o` for some `x ∈ X₁`, so
-- `x⁻¹ * g ∈ stabilizer G o`, hence the stabilizer hypothesis puts `g` into the closure. For an
-- arbitrary `g : G`, use the bounded-step hypothesis to choose a product of short steps having the
-- same effect on `o` as `g`; the remaining difference again lies in the stabilizer, so `g`
-- belongs to the same closure.
theorem closure_union_eq_top_of_stabilizer_and_short_orbit_steps
(hX₀ : Subgroup.closure X₀ = stabilizer G o)
(hX₁ : ∀ g : G, dist o (g • o) ≤ k → ∃ x ∈ X₁, x • o = g • o)
(hsteps : ∀ g : G, ∃ l : List G, (∀ a ∈ l, dist o (a • o) ≤ k) ∧ l.prod • o = g • o) :
Subgroup.closure (X₀ ∪ X₁) = ⊤Lemma 3.13.4
Lean contributors (project-level attribution): Zichen Wang.
Lemma 3-13-4: for an isometric scalar action on a pseudometric space, the displacement of a point under a finite successive translate is at most the sum of the individual displacements.
universe u v
variable {G : Type u} {V : Type v} [PseudoMetricSpace V] [SMul G V]
variable [IsIsometricSMul G V]
theorem dist_foldl_smul_le_sum_dist_smul (v : V) (gs : List G) :
dist v (gs.foldl (fun x g ↦ g • x) v) ≤ (gs.map fun g ↦ dist v (g • v)).sumLemma 3.13.5
Lean contributors (project-level attribution): Zichen Wang.
Lemma 3-13-5: assume Behr's bounded descending-path condition in the ball about o, together with bounded generator realizations of short metric steps and bounded distinguished word representatives for stabilizer loops. Then whenever u is obtained from v by the positive word g, there is a correction word whose total product cancels g, whose tail correction.drop (|g| * k) lies in X₀, and whose prefixes keep the intermediate translates of u inside the radius max {d(o, v), d(o, u)}.
universe u v w
open scoped BehrDistance
variable {G : Type u} {V : Type v} {X : Type w}
variable [Group G] [MulAction G V]
variable (generators : X → G) (X₀ : Set X) (k : ℕ) (o : V) (d : V → V → ℕ)
theorem exists_correction_word_with_bounded_prefix_distance
(hdesc : ∀ l : ℕ, HasBoundedDescendingPathsInBall d k o l)
(hstep : HasBoundedStepWordRealization generators d k)
(hstab : HasBoundedDistinguishedStabilizerWords generators X₀ o d)
(g : List X) (v u : V) (hu : u = (g.map generators).prod • v) :
∃ correction : List X,
((g ++ correction).map generators).prod = 1 ∧
(∀ x ∈ correction.drop (g.length * k), x ∈ X₀) ∧
∀ i,
d o (((correction.take i).map generators).prod • u) ≤
max (d o v) (d o u)Corollary 3.13.6
Lean contributors (project-level attribution): Zichen Wang.
Corollary 3-13-6: for a positive generator word of length at most 3, the correction word from Lemma 3-13-5 may be chosen with the same bounded-prefix-distance control, and every letter in the tail correction.drop (3 * k) lies in the distinguished subset X₀.
universe u v w
open scoped BehrDistance
variable {G : Type u} {V : Type v} {X : Type w}
variable [Group G] [MulAction G V]
variable (generators : X → G) (X₀ : Set X) (k : ℕ) (o : V) (d : V → V → ℕ)
variable
(hdesc :
∀ l : ℕ,
∀ ⦃p q : V⦄,
p ∈ S[d](o, l) →
q ∈ S[d](o, l) →
HasBoundedDescendingPathInBall d k o l p q)
(hstep : HasBoundedStepWordRealization generators d k)
(hstab : HasBoundedDistinguishedStabilizerWords generators X₀ o d)
include hdesc hstep hstab
theorem exists_correction_word_with_bounded_prefix_distance_of_length_le_three
(g : List X) (v u : V) (hg : g.length ≤ 3) (hu : u = (g.map generators).prod • v) :
∃ correction : List X,
((g ++ correction).map generators).prod = 1 ∧
(∀ x ∈ correction.drop (3 * k), x ∈ X₀) ∧
∀ i,
d o (((correction.take i).map generators).prod • u) ≤
max (d o v) (d o u)Proposition 3.13.7
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-13-7: the canonical comparison map from the source-facing pushout of the two adjacent copies of SL(2, ℤ) in SL(2, ℤ[1/p]) onto SL(2, ℤ[1/p]) is bijective. The source-facing subgroup gamma0Subgroup p coming from Γ₀(p) is the common edge stabilizer, identified with the intersection used by the chapter owner API via gamma0Subgroup_eq_inf p.
open scoped MatrixGroups
open CongruenceSubgroup
open ConjAct
theorem specialLinearGroup_away_prime_is_amalgamatedProduct_of_Gamma0
(p : ℕ) (hp : p.Prime) :
Function.Bijective
(Subgroup.amalgamatedProductComparison
(integralSpecialLinearSubgroup p)
(adjacentSpecialLinearSubgroup p))Proposition 3.13.8
Lean contributors (project-level attribution): Zichen Wang.
Proposition 3-13-8: the canonical comparison map from the amalgamated free product of the constant copy of GL(2, F) and the upper triangular subgroup T(F[t]), with the corresponding subgroup T(F) identified, onto GL(2, F[t]) is bijective.
open scoped MatrixGroups
universe u
variable (F : Type u) [Field F]
theorem glPolynomial_amalgamatedProductComparison_bijective :
Function.Bijective
(Subgroup.amalgamatedProductComparison
(constantLinearSubgroup F)
(upperTriangularSubgroup : Subgroup (GL (Fin 2) (Polynomial F))))