Paperlane

no. 11 · Monday 9 November 2026

Braid Groups in Lean : Formalizing Dehornoy's Subword Reversing Algorithm

Hannah Fechtner

math.GR · □ lean

Abstract

We formalize the group-theoretic definition of infinite and finite Artin braid groups in Lean. We implement a polynomial-time procedure for determining equivalence in the braid group known as Dehornoy's subword reversing algorithm. Termination and correctness of this algorithm are shown using rectangular grids, which are a specific form of van Kampen diagram. The literature only hints at a proof linking rectangular grids to braid equivalence. We present a novel, three-stage proof of this result, introducing partial grids and associated size metrics.

fields
Group Theory
pdf ↗ page arXiv:2611.09787 ↗