/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ /- Original Mathlib author: Hang Lu Su. -/ module public import Mathlib.Analysis.Normed.Group.Defs public import FormalConjecturesForMathlib.Geometry.Group.WordProd

The word metric

The word length of an element is the length of a shortest representing word, over a generating family given by Group.Generators. The word length defines a norm on G inducing the word metric dist g h = ‖g⁻¹ * h‖.

This file is copied from Mathlib.Geometry.Group.WordMetric (leanprover-community/mathlib4#43118). It is in Mathlib from v4.34.0.

TODO: delete this file when this repository moves to Mathlib v4.34.0.

Main definitions

    Group.Generators.wordLength: the word length of an element of G with respect to a generating family P.

    Group.Generators.IsGeodesic: a word is geodesic if it is of minimal length among the words representing the same group element.

    Group.Generators.groupNorm: the word length as a norm on G.

    Group.Generators.normedGroup: the normed group structure on G induced by groupNorm. This gives rise to a word metric on G.

Main results

    Group.Generators.exists_isGeodesic: every element of G is represented by some geodesic word.

@[expose] public sectionnamespace Group.Generatorsvariable {G ι : Type*} [Group G]variable (P : Group.Generators G ι) (g h : G) (l : List (ι × Bool))

Definition of word length

The word length of g with respect to the generating family P.

@[`@[no_expose]` has no effect outside a `module` fileno_expose] noncomputable def wordLength : ℕ := sInf {n | ∃ l, P.wordProd l = g ∧ l.length = n}

Geodesic words

A word l is geodesic if its length is exactly the word length of the group element it represents.

def IsGeodesic : Prop := P.wordLength (P.wordProd l) = l.lengthlemma IsGeodesic.eq {l : List (ι × Bool)} (hl : P.IsGeodesic l) : P.wordLength (P.wordProd l) = l.length := hl

Every group element has a geodesic word representative.

theorem exists_isGeodesic : ∃ l, P.IsGeodesic l ∧ P.wordProd l = g := G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:G⊢ ∃ l, P.IsGeodesic l ∧ P.wordProd l = g G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιl:List (ι × Bool)hlen:l.length = sInf (List.length '' fun x ↦ P.wordProd x = P.wordProd l)⊢ ∃ l_1, P.IsGeodesic l_1 ∧ P.wordProd l_1 = P.wordProd l All goals completed! 🐙

Word length

lemma wordLength_wordProd_le : P.wordLength (P.wordProd l) ≤ l.length := Nat.sInf_le ⟨l, rfl, rfl⟩

The characterisation of word length: the word length of a group element is less or equal to n if and only if there exists a word l of length at most n which evaluates to g.

theorem wordLength_le_iff {n : ℕ} : P.wordLength g ≤ n ↔ ∃ l, l.length ≤ n ∧ P.wordProd l = g := G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gn:ℕ⊢ P.wordLength g ≤ n ↔ ∃ l, l.length ≤ n ∧ P.wordProd l = g G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gn:ℕ⊢ P.wordLength g ≤ n → ∃ l, l.length ≤ n ∧ P.wordProd l = gG:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gn:ℕ⊢ (∃ l, l.length ≤ n ∧ P.wordProd l = g) → P.wordLength g ≤ n G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gn:ℕ⊢ P.wordLength g ≤ n → ∃ l, l.length ≤ n ∧ P.wordProd l = g G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gn:ℕh:P.wordLength g ≤ n⊢ ∃ l, l.length ≤ n ∧ P.wordProd l = g G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιn:ℕl:List (ι × Bool)hl:P.IsGeodesic lh:P.wordLength (P.wordProd l) ≤ n⊢ ∃ l_1, l_1.length ≤ n ∧ P.wordProd l_1 = P.wordProd l All goals completed! 🐙 G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gn:ℕ⊢ (∃ l, l.length ≤ n ∧ P.wordProd l = g) → P.wordLength g ≤ n G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιn:ℕl:List (ι × Bool)hl:l.length ≤ n⊢ P.wordLength (P.wordProd l) ≤ n All goals completed! 🐙G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:G⊢ (∃ l, l.length ≤ 0 ∧ P.wordProd l = g) ↔ g = 1 All goals completed! 🐙All goals completed! 🐙-- This is superseded by `wordLength_inv`. private lemma wordLength_inv_le : P.wordLength g⁻¹ ≤ P.wordLength g := G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:G⊢ P.wordLength g⁻¹ ≤ P.wordLength g G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιl:List (ι × Bool)hl:P.IsGeodesic l⊢ P.wordLength (P.wordProd l)⁻¹ ≤ P.wordLength (P.wordProd l) All goals completed! 🐙@[simp] lemma wordLength_inv : P.wordLength g⁻¹ = P.wordLength g := G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:G⊢ P.wordLength g⁻¹ = P.wordLength g G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:G⊢ P.wordLength g⁻¹ ≤ P.wordLength gG:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:G⊢ P.wordLength g ≤ P.wordLength g⁻¹ G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:G⊢ P.wordLength g⁻¹ ≤ P.wordLength g All goals completed! 🐙 G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:G⊢ P.wordLength g ≤ P.wordLength g⁻¹ All goals completed! 🐙lemma wordLength_mul_le : P.wordLength (g * h) ≤ P.wordLength g + P.wordLength h := G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gh:G⊢ P.wordLength (g * h) ≤ P.wordLength g + P.wordLength h G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιh:Gl₁:List (ι × Bool)hl₁:P.IsGeodesic l₁⊢ P.wordLength (P.wordProd l₁ * h) ≤ P.wordLength (P.wordProd l₁) + P.wordLength h G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιl₁:List (ι × Bool)hl₁:P.IsGeodesic l₁l₂:List (ι × Bool)hl₂:P.IsGeodesic l₂⊢ P.wordLength (P.wordProd l₁ * P.wordProd l₂) ≤ P.wordLength (P.wordProd l₁) + P.wordLength (P.wordProd l₂) All goals completed! 🐙

The wordLength with respect to a generating family P defines a norm on G.

noncomputable def groupNorm : GroupNorm G where toFun g := P.wordLength g map_one' := G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gh:Gl:List (ι × Bool)⊢ ↑(P.wordLength 1) = 0 All goals completed! 🐙 mul_le' := mod_cast P.wordLength_mul_le inv' := G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gh:Gl:List (ι × Bool)⊢ ∀ (x : G), ↑(P.wordLength x⁻¹) = ↑(P.wordLength x) All goals completed! 🐙 eq_one_of_map_eq_zero' := G:Type u_1ι:Type u_2inst✝:Group GP:Generators G ιg:Gh:Gl:List (ι × Bool)⊢ ∀ (x : G), ↑(P.wordLength x) = 0 → x = 1 All goals completed! 🐙

Word metric

G as a metric space NormedGroup G with respect to a generating family P. The metric is given by dist g h = ‖g⁻¹ * h‖, where the norm is given by groupNorm.

@[instance_reducible] noncomputable def normedGroup : NormedGroup G := P.groupNorm.toNormedGroupend Group.Generators