The Connes–Kreimer–Foissy Hopf algebra of planar rooted trees #
The carrier is H k = MonoidAlgebra k (FreeMonoid RTree): the free k-module on planar forests,
with forest concatenation as product. The combinatorial coproduct of
Formalizations.RingTheory.HopfAlgebra.ConnesKreimer.Coproduct is lifted to a linear map, and
H k becomes a Mathlib Coalgebra, Bialgebra and HopfAlgebra.
Main results #
ConnesKreimer.coassoc_map:(Δ ⊗ id) ∘ Δ = (id ⊗ Δ) ∘ Δas linear maps.ConnesKreimer.instCKCoalg:Coalgebra k (H k).ConnesKreimer.Δ_mul,ConnesKreimer.Δ_one,ConnesKreimer.instCKBialg:Bialgebra k (H k).ConnesKreimer.antipodeF: the antipode by the connected-graded recursionS(f) = −Σ_{(p,r), r ≠ ∅} S(p)·r.ConnesKreimer.leftAntipode_eq,ConnesKreimer.rightAntipode'_eq,ConnesKreimer.antipode_eq_antipode': both antipode axioms.ConnesKreimer.instCKHopf:HopfAlgebra k (H k).
Implementation notes #
Ported from Lean v4.30.0-rc2. In current Mathlib MonoidAlgebra is a structure over its
coefficient Finsupp, no longer the Finsupp itself; linear maps out of H k are defined
through MonoidAlgebra.coeffLinearEquiv and tested on the basis by ConnesKreimer.lhom_ext. These
adaptations follow the port of the same development in
LeanPool/lean-pool (LeanPool/ConnesKreimer/Core.lean).
References #
- A. Connes, D. Kreimer, Hopf algebras, renormalization and noncommutative geometry, Comm. Math. Phys. 199 (1998) 203–242.
- L. Foissy, Les algèbres de Hopf des arbres enracinés décorés, I, Bull. Sci. Math. 126 (2002) 193–239.
- C. Marín, How a Tree Remembers Its Cuts: the Connes–Kreimer–Foissy Hopf Algebra of Rooted Trees,
Machine-Checked in Lean 4 (2026), doi:10.5281/zenodo.20762280. Ported from
ConnesKreimer.leanof karlesmarin/connes-kreimer-lean (Lean v4.30.0-rc2).
Carrier: forests with k-coefficients (product = forest concatenation).
Equations
Instances For
Extensionality for linear maps out of H k, tested on the forest basis. A Forest-indexed
repackaging of MonoidAlgebra.lhom_ext' (Forest and FreeMonoid RTree are definitionally
but not reducibly equal, and rw needs the former).
Pure 2-tensor of a cut (p, r).
Equations
- ConnesKreimer.e2 k pr = MonoidAlgebra.single pr.1 1 ⊗ₜ[k] MonoidAlgebra.single pr.2 1
Instances For
Pure 3-tensor of an iterated cut (a, b, c), associated to the right.
Equations
- ConnesKreimer.e3 k t = MonoidAlgebra.single t.1 1 ⊗ₜ[k] (MonoidAlgebra.single t.2.1 1 ⊗ₜ[k] MonoidAlgebra.single t.2.2 1)
Instances For
Δ on a basis forest.
Equations
- ConnesKreimer.Δ₀ k f = (List.map (ConnesKreimer.e2 k) (ConnesKreimer.coprodForest f)).sum
Instances For
E3 of a triple-tensor list.
Equations
- ConnesKreimer.E3 k l = (List.map (ConnesKreimer.e3 k) l).sum
Instances For
Comultiplication.
Equations
Instances For
A linear map commutes with a List.sum of mapped terms.
LHS structural map on Δ₀ f.
RHS structural map on Δ₀ f.
The combinatorial coassoc, transported to E3.
Coassociativity as an equality of linear maps.
Counit. #
Counit monoid hom: every generator ↦ 0, so a word ↦ 0 ^ len = indicator of empty.
Equations
- ConnesKreimer.εmon k = FreeMonoid.lift fun (x : ConnesKreimer.RTree) => 0
Instances For
Counit as an algebra hom, then linear.
Equations
Instances For
The Connes-Kreimer counit as a linear map.
Equations
Instances For
The left-counit collapse: ε on the left leg selects the unique ([], f) cut.
The right-counit collapse: ε on the right leg selects the unique (f, []) cut.
(ε ⊗ id) ∘ Δ on a basis forest gives 1 ⊗ single f 1.
(id ⊗ ε) ∘ Δ on a basis forest gives single f 1 ⊗ 1.
Equations
- ConnesKreimer.instCoalgebraStructH k = { comul := ConnesKreimer.Δ k, counit := ConnesKreimer.ε k }
Equations
- ConnesKreimer.instCKCoalg k = { toCoalgebraStruct := ConnesKreimer.instCoalgebraStructH k, coassoc := ⋯, rTensor_counit_comp_comul := ⋯, lTensor_counit_comp_comul := ⋯ }
single of a concatenation is the product (algebra structure of H).
Product of two List.sums is the double sum.
Equations
- ConnesKreimer.instCKBialg k = Bialgebra.mk' k (ConnesKreimer.H k) ⋯ ⋯ ⋯ ⋯
Toward HopfAlgebra: node count (grading) and its conservation under cuts. #
Conservation `|p| + |r| = |f|` makes the antipode recursion well-founded
(`r ≠ [] ⟹ |p| < |f|`).
Number of nodes in a rooted tree.
Equations
Instances For
Number of nodes in a rooted forest.
Equations
- ConnesKreimer.sizeF [] = 0
- ConnesKreimer.sizeF (t :: ts) = ConnesKreimer.sizeT t + ConnesKreimer.sizeF ts
Instances For
A forest as an H-basis element, with the index forced to FreeMonoid RTree
via ofList (so it is always typed H k, even on the empty forest).
Equations
Instances For
The antipode on the forest basis, by well-founded recursion on node count.
S(∅) = 1; S(f) = -Σ_{(p,r) cut, r ≠ ∅} S(p)·r. Recursion decreases since
|p| < |f|.
Equations
- One or more equations did not get rendered due to their size.
- ConnesKreimer.antipodeF k [] = 1
Instances For
The antipode linear map obtained by extending antipodeF from the forest basis.
Equations
Instances For
r ++ b is nonempty when r is.
Filtering cuts by "empty right leg" factorizes over tmul.
The unique empty-right cut of a tree t is ([t], []).
Filtering cuts by "empty left leg" factorizes over tmul.
The unique empty-left cut of a tree t is ([], [t]).
The right antipode by well-founded recursion on node count.
S'(∅) = 1; S'(f) = -Σ_{(p,r) cut, p ≠ ∅} p·S'(r). Decreases since |r| < |f|.
Equations
- One or more equations did not get rendered due to their size.
- ConnesKreimer.antipodeF' k [] = 1
Instances For
The mirrored antipode candidate used to prove the right convolution identity.
Equations
Instances For
Left antipode identity as a linear-map equality (the Hopf left axiom).
Right antipode identity for S' as a linear-map equality.
Equations
- ConnesKreimer.instHopfAlgebraStructH k = { toBialgebra := ConnesKreimer.instCKBialg k, antipode := ConnesKreimer.antipode k }
Equations
- ConnesKreimer.instCKHopf k = { toHopfAlgebraStruct := ConnesKreimer.instHopfAlgebraStructH k, mul_antipode_rTensor_comul := ⋯, mul_antipode_lTensor_comul := ⋯ }