AFTD Auto-Formalizing Theoretical Domains

cyclic_latin_rank_matching_rank_sum

theoremverified

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$.

  1. 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.

    line 3

    uses cyclic_latin_rank_sum, cyclic_latin_rank_matching, hash_probe_tail_prob_zero

        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)
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.

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

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