rearrangement_operator_comp_apply
For any array $A$ of order $m$, index $i \in \mathrm{Fin}\,m$, and permutations $P, Q \in \mathrm{Equiv.Perm}(\mathrm{Fin}\,m)$, applying the composition of rearrangement operators $(\widehat{P} \circ \widehat{Q})(A)$ at index $i$ yields $\widehat{Q \circ P}(A)[i] = A(Q(P(i)))$.
Statement
theorem rearrangement_operator_comp_apply {m : ℕ} (P Q : Equiv.Perm (Fin m)) (A : Arr m) (i : Fin m) :
(rearrangement_operator P ∘ rearrangement_operator Q) A i = rearrangement_operator (Q * P) A i- Source
- 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_applyUnder the source-index convention, the entry at index $i$ of the rearranged array $\widehat{P}(A)$ equals $A(P(i))$ for any permutation…
- Used by 1
- rearrangement_operator_anti_homomorphismUnder the source-index convention where the rearrangement operator $\widehat{P}$ acts on an array…
Read back from the Lean
For any natural number $m$, any permutations $P, Q \in \text{Equiv.Perm}(\text{Fin } m)$, any function $A : \text{Fin } m \to \text{Fin } m$, and any index $i \in \text{Fin } m$, the composition of the rearrangement operator for $P$ with the rearrangement operator for $Q$, applied to $A$ and evaluated at $i$, equals the rearrangement operator for the permutation product $Q * P$ applied to $A$ and evaluated at $i$.
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
By definition, the rearrangement operator $\widehat{P}$ acts on an array $A$ by precomposition, sending $A$ to $A \circ P$. Evaluating the left-hand side at an index $i$ gives $A(Q(P(i)))$, while the right-hand side evaluates to $A((Q * P)(i)) = A(Q(P(i)))$ because the permutation group operation is function composition. Since both expressions are definitionally equal, the proof is completed in one step by reflexivity.
$(\widehat{P} \circ \widehat{Q})(A)[i] = \widehat{Q \circ P}(A)[i]$ holds definitionally for all indices $i$.
By definition, the rearrangement operator acts by precomposition, $\widehat{P}(A) = A \circ P$. Thus, the left-hand side evaluates at index $i$ to $((A \circ Q) \circ P)(i) = A(Q(P(i)))$. For permutations, multiplication is function composition, $(Q * P)(i) = Q(P(i))$, so the right-hand side is $(A \circ (Q * P))(i) = A(Q(P(i)))$. Because both sides expand definitionally to the exact same expression, the goal is closed by reflexivity.
rfl
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.
/-- Pointwise composition of rearrangement operators: $(\widehat{P} \circ \widehat{Q})(A)[i] = \widehat{Q \circ P}(A)[i]$. -/theorem rearrangement_operator_comp_apply {m : ℕ} (P Q : Equiv.Perm (Fin m)) (A : Arr m) (i : Fin m) : (rearrangement_operator P ∘ rearrangement_operator Q) A i = rearrangement_operator (Q * P) A i := by rfl