rearrangement_operator_apply
Under the source-index convention, the entry at index $i$ of the rearranged array $\widehat{P}(A)$ equals $A(P(i))$ for any permutation $P$, array $A$, and index $i$.
Statement
theorem rearrangement_operator_apply {m : ℕ} (P : Equiv.Perm (Fin m)) (A : Arr m) (i : Fin m) :
rearrangement_operator P A i = A (P i)- Source
- arXiv:2611.05397, Section 2.2, Definition 2: Ranking and Unranking Permutations in Heap's Order
- Verified
- 09 Nov 2026
- Axioms
Quot.sound- Built on 2
- 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…
- Used by 1
- 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 any natural number $m$, any permutation $P$ of $\mathrm{Fin}(m)$, any array (function) $A : \mathrm{Fin}(m) \to \mathrm{Fin}(m)$, and any index $i \in \mathrm{Fin}(m)$, the result of applying the rearrangement operator with permutation $P$ to array $A$ at index $i$ equals $A(P(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
The rearrangement operator $\\widehat{P}(A)$ is defined directly as the function composition $A \\circ P$. Evaluating this composite function at an index $i$ yields $(A \\circ P)(i) = A(P(i))$ by definition, so the statement holds by reflexivity.
$(\\widehat{P}(A))(i) = A(P(i))$
By definition, the rearrangement operator $\\widehat{P}(A)$ is the composite function $A \\circ P$. Evaluating $(A \\circ P)$ at index $i$ gives $A(P(i))$. Because both sides of the equality are definitionally identical, the goal is closed immediately by reflexivity (`rfl`).
rearrangement_operator P A i = A (P i) := by 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 evaluation of the rearrangement operator under the source-index convention. -/theorem rearrangement_operator_apply {m : ℕ} (P : Equiv.Perm (Fin m)) (A : Arr m) (i : Fin m) : rearrangement_operator P A i = A (P i) := by rfl