rearrangement_operator_anti_homomorphism
Under the source-index convention where the rearrangement operator $\widehat{P}$ acts on an array $A : \mathrm{Fin}\,m \to \mathrm{Fin}\,m$ by $\widehat{P}(A) = A \circ P$, the composition of rearrangement operators satisfies the anti-homomorphism property $\widehat{P} \circ \widehat{Q} = \widehat{Q \circ P}$ for all permutations $P, Q \in \mathrm{Equiv.Perm}(\mathrm{Fin}\,m)$.
Statement
theorem rearrangement_operator_anti_homomorphism (m : ℕ) (P Q : Equiv.Perm (Fin m)) :
rearrangement_operator P ∘ rearrangement_operator Q = rearrangement_operator (Q * P)- Formalizes
- arXiv:2611.05397, Section 2.2, Lemma 1: Ranking and Unranking Permutations in Heap's Order
- Verified
- 09 Nov 2026
- Axioms
Quot.sound- Built on 3
- ArrThe set of arrangement arrays of order $m$ is represented as the type of functions from $\mathrm{Fin}\,m$ to $\mathrm{Fin}\,m$.
- rearrangement_operatorFor a permutation $P \in \mathrm{Equiv.Perm}(\mathrm{Fin}\,m)$, the rearrangement operator $\widehat{P}$ acts on an array…
- rearrangement_operator_comp_applyFor any array $A$ of order $m$, index $i \in \mathrm{Fin}\,m$, and permutations $P, Q \in \mathrm{Equiv.Perm}(\mathrm{Fin}\,m)$, applying…
Read back from the Lean
For every natural number $m$ and all permutations $P, Q$ of $\text{Fin}(m)$, the composition of the rearrangement operator for $P$ with the rearrangement operator for $Q$ equals the rearrangement operator for $Q * P$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes the anti-homomorphism property $\widehat{P} \circ \widehat{Q} = \widehat{Q * P}$ for rearrangement operators acting by precomposition on arrays. By function extensionality, it suffices to show that both sides agree on any array $A$, where the left side gives $(A \circ Q) \circ P$ and the right side gives $A \circ (Q \circ P)$ by the definition of permutation multiplication. The automated proof search tactic `aesop` closes the goal directly using function extensionality and associativity of function composition.
$\widehat{P} \circ \widehat{Q} = \widehat{Q * P}$ automation
The automated tactic `aesop` proves the equality of operators via function extensionality. For any array $A : \mathrm{Fin}\,m \to \mathrm{Fin}\,m$, the left-hand side evaluates to $\widehat{P}(\widehat{Q}(A)) = (A \circ Q) \circ P$. In $\mathrm{Equiv.Perm}$, the group operation $Q * P$ corresponds to composition $Q \circ P$ on elements, so the right-hand side evaluates to $A \circ (Q \circ P)$. By associativity of function composition, $(A \circ Q) \circ P = A \circ (Q \circ P)$, making both sides definitionally equal for every $A$.
rearrangement_operator P ∘ rearrangement_operator Q = rearrangement_operator (Q * P) := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)
- The proof attempts a series of standard automated tactics in a `first | ...` chain (`simp_all`, `omega`, `decide`, `linarith`, `positivity`). All fail until `aesop`, which completes the proof automatically.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Operator anti-homomorphism under the source-index convention: $\widehat{P} \circ \widehat{Q} = \widehat{Q \circ P}$. -/theorem rearrangement_operator_anti_homomorphism (m : ℕ) (P Q : Equiv.Perm (Fin m)) : rearrangement_operator P ∘ rearrangement_operator Q = rearrangement_operator (Q * P) := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)