cyclic_latin_rank_matching_rank_sum
For the rotation matching μ_r(i) = a r - i, the aggregate proposer rank is constant equal to r, hence its total is n * r.
Statement
theorem cyclic_latin_rank_matching_rank_sum (n : ℕ) [NeZero n] (a : Fin n ≃ ZMod n) (r : Fin n) :
cyclic_latin_rank_sum n a (cyclic_latin_rank_matching n a r) = n * (r : ℕ)- Source
- step towards cyclic_latin_stable_rank_polynomial_gcd_sequence_invariance
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- cyclic_latin_rank_sumGiven an order n with [NeZero n], a bijection a : Fin n ≃ ZMod n, and a matching permutation π : Equiv.Perm (ZMod n), the aggregate…
- cyclic_latin_rank_matchingGiven a natural number n, an ordering bijection a : Fin n ≃ ZMod n, and an index r : Fin n, cyclic_latin_rank_matching n a r is the…
- hash_probe_tail_prob_zeroFor any table size n with [NeZero n], offset sequence r : Fin n → ZMod n, and number of inserted keys t, the 0-th tail probability of…
The proof, explained
The aggregate proposer rank for the rotation matching $\mu_r(i) = a(r) - i$ is defined as the sum over all $i \in \mathbb{Z}/n\mathbb{Z}$ of $a^{-1}(i + \mu_r(i))$. Since $i + \mu_r(i) = i + (a(r) - i) = a(r)$, the rank paid at every element is the constant $a^{-1}(a(r)) = r$. Summing this constant rank over all $n$ elements of $\mathbb{Z}/n\mathbb{Z}$ immediately yields $n \cdot r$.
The aggregate proposer rank of the rotation matching $\mu_r$ is $n \cdot r$. automation
Unfolding the definitions of `cyclic_latin_rank_sum` and `cyclic_latin_rank_matching`, the aggregate rank is expressed as the sum $\sum_{i \in \mathbb{Z}/n\mathbb{Z}} a^{-1}(i + (a(r) - i))$. For each index $i$, the sum simplifies via $i + (a(r) - i) = a(r)$ to $a^{-1}(a(r)) = r$, so every term is identically $r$. The tactic `simpa` simplifies the summand to $r$ and sums this constant value over the $n$ elements of $\mathbb{Z}/n\mathbb{Z}$, resulting in $n \cdot r$ and closing the goal.
uses
cyclic_latin_rank_sum,cyclic_latin_rank_matching,hash_probe_tail_prob_zerocyclic_latin_rank_sum n a (cyclic_latin_rank_matching n a r) = n * (r : ℕ) := by first | exact hash_probe_tail_prob_zero | (apply hash_probe_tail_prob_zero <;> assumption) | (apply hash_probe_tail_prob_zero <;> simp_all) | simpa using hash_probe_tail_prob_zero | (simp only [cyclic_latin_rank_sum, cyclic_latin_rank_matching] at *; first | exact hash_probe_tail_prob_zero | (apply hash_probe_tail_prob_zero <;> assumption) | (apply hash_probe_tail_prob_zero <;> simp_all) | simpa using hash_probe_tail_prob_zero)
cyclic_latin_rank_sum- The total proposer rank of a permutation $\pi$ on $\mathbb{Z}/n\mathbb{Z}$, defined as $\sum_{i \in \mathbb{Z}/n\mathbb{Z}} a^{-1}(i + \pi(i))$.
cyclic_latin_rank_matching- The rotation matching $\mu_r$ on $\mathbb{Z}/n\mathbb{Z}$ mapping each $i$ to $a(r) - i$.
hash_probe_tail_prob_zero- The probability of probing at least 0 times in the hash probe model is 1.
- The tactic script is an automated search cascade produced by proof synthesis. The lemma `hash_probe_tail_prob_zero` passed to `simpa` is an unused artifact of this automation; `simpa` closes the goal during its simplification prepass by evaluating the algebraic identity and the constant sum over the finite ring, without relying on `hash_probe_tail_prob_zero`.
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.
/-- Each rotation matching pays rank r at every man, so its total proposer rank is n*r; this is the gcd-independent diagonal contribution to every rank polynomial. -/theorem cyclic_latin_rank_matching_rank_sum (n : ℕ) [NeZero n] (a : Fin n ≃ ZMod n) (r : Fin n) : cyclic_latin_rank_sum n a (cyclic_latin_rank_matching n a r) = n * (r : ℕ) := by first | exact hash_probe_tail_prob_zero | (apply hash_probe_tail_prob_zero <;> assumption) | (apply hash_probe_tail_prob_zero <;> simp_all) | simpa using hash_probe_tail_prob_zero | (simp only [cyclic_latin_rank_sum, cyclic_latin_rank_matching] at *; first | exact hash_probe_tail_prob_zero | (apply hash_probe_tail_prob_zero <;> assumption) | (apply hash_probe_tail_prob_zero <;> simp_all) | simpa using hash_probe_tail_prob_zero)