AFTD Auto-Formalizing Theoretical Domains

rearrangement_operator_comp_apply

theoremverified

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

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.

  1. $(\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.

    line 4

      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

/-- 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
See it in the graphDiscuss this resultChallenge it