Thompson's group on the circle, and the presented group
DefinitionCannonFloydParry_TCannon–Floyd–Parry §5 (pp. 233–239): Thompson's group and the presented group .
The circle. p. 233: “Consider as the interval with the endpoints identified.” is UnitAddCircle, the reals modulo , which is that circle; is the image of (the source uses , as on p. 235, without defining it).
IsThompsonCircle, T. pp. 233–234: “Then is the group of piecewise linear homeomorphisms from to itself that map images of dyadic rational numbers to images of dyadic rational numbers and that are differentiable except at finitely many images of dyadic rational numbers and on intervals of differentiability the derivatives are powers of .” A permutation of satisfies IsThompsonCircle f when it has a lift : an order isomorphism of with and for all , which maps dyadic rationals to dyadic rationals and, for some finite set of dyadic rationals, is affine with slope an integer power of on every closed interval whose interior meets no point (, ). T is the subgroup of permutations of generated by these maps; it is the group of this sentence.
toCircle, mapC, symT. p. 234 (Example 5.1): “The elements and of induce elements of , which will still be denoted by and .” toCircle g, for an order isomorphism of , is the permutation of (; fixes ). p. 234: “A third element of is the function defined (on ) by ” mapC is this , with half-open pieces: on , on , on . symT sends the formal symbols , , to toCircle mapA, toCircle mapB and mapC, where mapA, mapB are 's generators from the imported bundle.
T1. p. 236: “Let ” T1 is the presented group on the three symbols of FormalABC with these six relators, the commutators written out as , as p. 225 (§3) defines them: “Given elements , in a group, .”
XT1, CT1, IsPositiveT1. p. 236: “Define the elements , , of by and for .” XT1 n is . p. 236: “Define the elements , , of by . For convenience we define .” CT1 n is . p. 239: “Following the terminology for , an element of which is a product of nonnegative powers of the ’s will be called positive and an inverse of a positive element will be called negative.” IsPositiveT1 takes an element to be positive when it lies in the submonoid generated by the .
Formalization Note. Products of permutations compose right to left, , the convention under which the source's computations hold (it makes the translation by , as on p. 236). T is defined as a generated subgroup so that the definition carries no proof obligation; that the maps satisfying IsThompsonCircle already form a group is a milestone of this mission, as for .
import Definitions.Def_CannonFloydParry
import Mathlib
/-!
# Cannon–Floyd–Parry §5: Thompson's group `T`
Cannon, Floyd, Parry, *Introductory notes on Richard Thompson's groups*, L'Enseignement Math.
(2) 42 (1996), §5, pp. 233–239. The circle `S¹` is `UnitAddCircle`, the reals modulo `1`,
which is `[0,1]` with its endpoints identified. `T` is a group of permutations of it; the
presented group `T₁` and its elements `Xₙ`, `Cₙ` are the objects of the section's algebra.
-/
namespace CannonFloydParry
/-! ### The group `T` of the circle (pp. 233–234) -/
/-- The condition, on a permutation `f` of the circle `ℝ/ℤ`, that defines Thompson's group `T`
(p. 233), stated through a lift of `f` to the line: an order isomorphism `L` of `ℝ` that
commutes with translation by `1` and covers `f`, maps dyadic rationals to dyadic rationals, and
is affine with slope an integer power of `2` on every closed interval whose interior avoids the
integer translates of a finite set `B` of dyadic breakpoints. -/
def IsThompsonCircle (f : Equiv.Perm UnitAddCircle) : Prop :=
∃ L : ℝ ≃o ℝ, (∀ x, L (x + 1) = L x + 1) ∧
(∀ x : ℝ, f (x : UnitAddCircle) = ((L x : ℝ) : UnitAddCircle)) ∧
(∀ x, IsDyadic x → IsDyadic (L x)) ∧
∃ B : Finset ℝ, (∀ b ∈ B, IsDyadic b) ∧
∀ x y : ℝ, x < y → (∀ t ∈ Set.Ioo x y, ∀ b ∈ B, ∀ k : ℤ, t ≠ b + k) →
∃ (n : ℤ) (c : ℝ), ∀ z ∈ Set.Icc x y, L z = 2 ^ n * z + c
/-- Thompson's group `T`: the subgroup of permutations of the circle generated by the maps
satisfying `IsThompsonCircle`. -/
def T : Subgroup (Equiv.Perm UnitAddCircle) := Subgroup.closure {f | IsThompsonCircle f}
lemma orderIso_one (f : UI ≃o UI) : f ⟨1, one_mem_UI⟩ = ⟨1, one_mem_UI⟩ := by
apply le_antisymm
· exact Subtype.coe_le_coe.mp (f ⟨1, one_mem_UI⟩).2.2
· obtain ⟨z, hz⟩ := f.surjective ⟨1, one_mem_UI⟩
have := f.monotone (show z ≤ ⟨1, one_mem_UI⟩ from Subtype.coe_le_coe.mp z.2.2)
rwa [hz] at this
lemma orderIso_lt_one_iff (f : UI ≃o UI) (x : UI) : (f x : ℝ) < 1 ↔ (x : ℝ) < 1 := by
have h := @OrderIso.lt_iff_lt _ _ _ _ f x ⟨1, one_mem_UI⟩
rw [orderIso_one] at h
exact h
/-- An order isomorphism of `[0,1]` fixes `1`, so it restricts to a permutation of `[0,1)`. -/
noncomputable def icoPerm (f : UI ≃o UI) : Equiv.Perm (Set.Ico (0 : ℝ) (0 + 1)) where
toFun x := ⟨f ⟨x, x.2.1, by linarith [x.2.2]⟩, (f _).2.1, by
have := (orderIso_lt_one_iff f ⟨x, x.2.1, by linarith [x.2.2]⟩).2 (by linarith [x.2.2])
linarith⟩
invFun x := ⟨f.symm ⟨x, x.2.1, by linarith [x.2.2]⟩, (f.symm _).2.1, by
have := (orderIso_lt_one_iff f.symm ⟨x, x.2.1, by linarith [x.2.2]⟩).2 (by linarith [x.2.2])
linarith⟩
left_inv x := by
apply Subtype.ext
change ((f.symm (f ⟨x, x.2.1, by linarith [x.2.2]⟩) : UI) : ℝ) = x
rw [OrderIso.symm_apply_apply]
right_inv x := by
apply Subtype.ext
change ((f (f.symm ⟨x, x.2.1, by linarith [x.2.2]⟩) : UI) : ℝ) = x
rw [OrderIso.apply_symm_apply]
/-- The permutation of the circle induced by an order isomorphism of `[0,1]` (p. 234, "The
elements `A` and `B` of `F` induce elements of `T`"). -/
noncomputable def toCircle (f : UI ≃o UI) : Equiv.Perm UnitAddCircle :=
(AddCircle.equivIco (1 : ℝ) 0).trans ((icoPerm f).trans (AddCircle.equivIco (1 : ℝ) 0).symm)
/-- The function `C` of Example 5.1 (p. 234) on `[0,1)`: `x/2 + 3/4` on `[0,1/2)`, `2x - 1` on
`[1/2,3/4)` and `x - 1/4` on `[3/4,1)`. -/
noncomputable def cFun (x : ℝ) : ℝ :=
if x < 1 / 2 then x / 2 + 3 / 4 else if x < 3 / 4 then 2 * x - 1 else x - 1 / 4
/-- The inverse of `cFun` on `[0,1)`. -/
noncomputable def cInv (y : ℝ) : ℝ :=
if y < 1 / 2 then (y + 1) / 2 else if y < 3 / 4 then y + 1 / 4 else 2 * y - 3 / 2
lemma cFun_mem {x : ℝ} (hx : x ∈ Set.Ico (0 : ℝ) (0 + 1)) : cFun x ∈ Set.Ico (0 : ℝ) (0 + 1) := by
obtain ⟨h0, h1⟩ := hx
unfold cFun; split_ifs <;> constructor <;> linarith
lemma cInv_mem {x : ℝ} (hx : x ∈ Set.Ico (0 : ℝ) (0 + 1)) : cInv x ∈ Set.Ico (0 : ℝ) (0 + 1) := by
obtain ⟨h0, h1⟩ := hx
unfold cInv; split_ifs <;> constructor <;> linarith
lemma cInv_cFun {x : ℝ} (hx : x ∈ Set.Ico (0 : ℝ) (0 + 1)) : cInv (cFun x) = x := by
obtain ⟨h0, h1⟩ := hx
unfold cFun cInv
split_ifs <;> first | (exfalso; linarith) | ring
lemma cFun_cInv {x : ℝ} (hx : x ∈ Set.Ico (0 : ℝ) (0 + 1)) : cFun (cInv x) = x := by
obtain ⟨h0, h1⟩ := hx
unfold cFun cInv
split_ifs <;> first | (exfalso; linarith) | ring
/-- `cFun` as a permutation of `[0,1)`. -/
noncomputable def cIco : Equiv.Perm (Set.Ico (0 : ℝ) (0 + 1)) where
toFun x := ⟨cFun x, cFun_mem x.2⟩
invFun x := ⟨cInv x, cInv_mem x.2⟩
left_inv x := Subtype.ext (cInv_cFun x.2)
right_inv x := Subtype.ext (cFun_cInv x.2)
/-- The element `C` of `T` (Example 5.1, p. 234), as a permutation of the circle. -/
noncomputable def mapC : Equiv.Perm UnitAddCircle :=
(AddCircle.equivIco (1 : ℝ) 0).trans (cIco.trans (AddCircle.equivIco (1 : ℝ) 0).symm)
/-! ### The presented group `T₁` (p. 236) -/
/-- The three formal symbols `A`, `B`, `C` of the presentation of `T₁`. -/
inductive FormalABC
| A
| B
| C
deriving DecidableEq
/-- The relators of `T₁` (p. 236), with `[x, y] = x y x⁻¹ y⁻¹`:
`[AB⁻¹, A⁻¹BA]`, `[AB⁻¹, A⁻²BA²]`, `C⁻¹B(A⁻¹CB)`, `((A⁻¹CB)(A⁻¹BA))⁻¹B(A⁻²CB²)`,
`(CA)⁻¹(A⁻¹CB)²` and `C³`. -/
def relsT1 : Set (FreeGroup FormalABC) :=
let a := FreeGroup.of FormalABC.A
let b := FreeGroup.of FormalABC.B
let c := FreeGroup.of FormalABC.C
{ (a * b⁻¹) * (a⁻¹ * b * a) * (a * b⁻¹)⁻¹ * (a⁻¹ * b * a)⁻¹,
(a * b⁻¹) * (a⁻¹ ^ 2 * b * a ^ 2) * (a * b⁻¹)⁻¹ * (a⁻¹ ^ 2 * b * a ^ 2)⁻¹,
c⁻¹ * b * (a⁻¹ * c * b),
((a⁻¹ * c * b) * (a⁻¹ * b * a))⁻¹ * b * (a⁻¹ ^ 2 * c * b ^ 2),
(c * a)⁻¹ * (a⁻¹ * c * b) ^ 2,
c ^ 3 }
/-- `T₁ = ⟨A, B, C : relsT1⟩` (p. 236). -/
abbrev T1 := PresentedGroup relsT1
/-- The intended images of the formal symbols among the maps of the circle: `A` and `B` are
the maps of `F` carried to the circle, and `C` is `mapC`. -/
noncomputable def symT : FormalABC → Equiv.Perm UnitAddCircle
| FormalABC.A => toCircle mapA
| FormalABC.B => toCircle mapB
| FormalABC.C => mapC
/-- The elements `X₀ = A` and `Xₙ = A^{-(n-1)} B A^{n-1}` (`n ≥ 1`) of `T₁` (p. 236). -/
def XT1 : ℕ → T1
| 0 => PresentedGroup.of FormalABC.A
| n + 1 => (PresentedGroup.of FormalABC.A ^ n)⁻¹ * PresentedGroup.of FormalABC.B
* PresentedGroup.of FormalABC.A ^ n
/-- The elements `C₀ = 1` and `Cₙ = A^{-(n-1)} C B^{n-1}` (`n ≥ 1`) of `T₁` (p. 236). -/
def CT1 : ℕ → T1
| 0 => 1
| n + 1 => (PresentedGroup.of FormalABC.A ^ n)⁻¹ * PresentedGroup.of FormalABC.C
* PresentedGroup.of FormalABC.B ^ n
/-- The **positive** elements of `T₁` (p. 239): products of nonnegative powers of the `Xᵢ`. -/
def IsPositiveT1 (g : T1) : Prop := g ∈ Submonoid.closure (Set.range XT1)
end CannonFloydParry
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back
This item is a bundle of definitions (with a few small auxiliary facts proved along the way). They share the following vocabulary.
Shared vocabulary
The circle. is the additive quotient of by the subgroup of integer multiples of . For , denotes its class. Every point of has exactly one representative in the half-open interval ; the "representative map" sends a class to that representative, and its inverse is .
Permutations of the circle. is the group of all bijections — no continuity or order condition is built in. The product is composition with the right factor applied first: .
Dyadic rationals. A real number is dyadic if there are an integer and a natural number with
( is allowed, so every integer is dyadic.)
The unit interval. (closed), with its usual order. An order isomorphism of is an order-preserving bijection whose inverse is also order-preserving.
Powers of 2. Wherever appears with an integer, it is the real number with possibly negative (so ).
1. Circle maps of "Thompson type"
A bijection is of Thompson type if there exists an order isomorphism (an order-preserving bijection with order-preserving inverse) satisfying all four of the following:
-
Periodicity: for every real .
-
lifts : for every real .
-
preserves dyadics: for every real , if is dyadic then is dyadic. (Only this direction is required.)
-
Piecewise dyadic-affine with finitely many dyadic breakpoints mod 1: there exists a finite set , all of whose elements are dyadic, such that for all reals :
if the open interval contains no point of the form with and , then there exist an integer and a real number such that
Remarks on the fine print:
- In (4) the hypothesis is only about the open interval ; the endpoints may themselves be of the form , and the affine formula is then asserted on the closed interval .
- The set is any finite set of dyadic reals; it is not required to lie in , and it may be empty. If is empty, the hypothesis of (4) holds for every .
- The integer and the real may depend on and . The constant is not itself required to be dyadic.
- Nothing is said about the inverse of or of beyond being an order isomorphism.
2. The group
is the subgroup of generated by all bijections of Thompson type (Section 1), i.e. the smallest subgroup of containing every such bijection. Its elements are exactly the finite products of Thompson-type bijections and their inverses (the empty product being the identity).
3. Two auxiliary facts about order isomorphisms of (proved, not assumed)
- For every order isomorphism of : .
- For every order isomorphism of and every : if and only if .
4. From interval maps to circle maps
Restriction to . Given an order isomorphism of , define the bijection of the half-open interval by . (It lands in by the second fact of Section 3; its inverse is .)
Transport to the circle. For an order isomorphism of , is the bijection
In words: take the representative in , apply , and take the class again.
5. The map on the circle
Define by
and by
Only their values on matter below. Proved auxiliary facts: and each map into , and on they are inverse to each other ( and for ).
Concretely on : sends to by ; to by ; and to by .
is the resulting bijection of (inverse ), and
6. The interval maps and (from the imported vocabulary)
is the order isomorphism of given by
and is the order isomorphism of given by
(The formulas agree at the shared breakpoints. Each is the restriction to of an order isomorphism of that is the identity outside .)
7. The generator assignment
A three-letter alphabet is introduced (three distinct symbols). The function from this alphabet to is
So and for . This is only a function on the three letters; no group homomorphism out of any group is defined or claimed here.
8. The presented group
Write for the free generators of the free group on the three letters. The relator set consists of the following six elements of (products read left to right; means ):
is the group : the quotient of by the normal subgroup generated by the six relators (so each relator becomes the identity). Below, also denote their images in .
9. The elements and of
For :
So , , , and so on. Note the index shift: conjugates by , not .
So , , , and so on. (The right-hand factor is a power of , not of .)
In this notation relators 1–6 read: , (commutator ), , , , .
10. Positive elements of
An element is positive if it lies in the submonoid of generated by — that is, is a finite product with and each (no inverses; the empty product gives , so the identity is positive). Note is among the generators. Positivity is a property of the group element, not of a chosen word: is positive if some such product equals in .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.