Proof of `The commutativity problem` (3rd statement)

groundedproofs/Lax619925Proofs/Commutativity.lean · lax-619925

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The characterisation of commutativity (paper §3, lemma commutativitycommutativity): a series is commutative if and only if it satisfies the swap and the rotate equations. The forward direction is immediate — the swap and rotate equations are exactly the commutative equivalence of words differing by a transposition or a rotation. The backward direction uses that swaps and rotations connect any two words with the same multiset of letters, so satisfying the two finite families of equations forces the series to be constant on commutatively equivalent words.