perm_gap_sum
theoremverified
For a permutation s of {0, ..., n-1}, the number of pairs (a, b) with s(b) < a < b, plus the number of positions b with s(b) < b, plus the sum of s(b) over those b, equals the sum of b over those b.
Statement
theorem perm_gap_sum {n : ℕ} (σ : Equiv.Perm (Fin n)) : (∑ a : Fin n, ∑ b : Fin n, if (σ b : ℕ) < a ∧ (a : ℕ) < b then 1 else 0) + (∑ b : Fin n, if (σ b : ℕ) < b then 1 else 0) + ∑ b : Fin n, (if (σ b : ℕ) < b then (σ b : ℕ) else 0) = ∑ b : Fin n, (if (σ b : ℕ) < b then (b : ℕ) else 0)
- Source
- step towards hollow_shell_blocking_pairs_ncard_le (Shield-Core upper bound, A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem (2026), arXiv:2609.17418, Sec. 7.1)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- perm_nesting_boundFor a permutation s of {0, ..., n-1} with k positions a such that s(a) < a: the number of pairs (a, b) with a < b and s(b) < s(a) and a, b…
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.
theorem perm_gap_sum {n : ℕ} (σ : Equiv.Perm (Fin n)) : (∑ a : Fin n, ∑ b : Fin n, if (σ b : ℕ) < a ∧ (a : ℕ) < b then 1 else 0) + (∑ b : Fin n, if (σ b : ℕ) < b then 1 else 0) + ∑ b : Fin n, (if (σ b : ℕ) < b then (σ b : ℕ) else 0) = ∑ b : Fin n, (if (σ b : ℕ) < b then (b : ℕ) else 0) := by rw [Finset.sum_comm, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun b _ => ?_ have hc : (∑ a : Fin n, if (σ b : ℕ) < a ∧ (a : ℕ) < b then 1 else 0) = (b : ℕ) - σ b - 1 := by rw [← Finset.card_filter] have : (Finset.univ.filter fun a : Fin n => (σ b : ℕ) < a ∧ (a : ℕ) < b) = Finset.Ioo (σ b) b := by ext a simp rw [this, Fin.card_Ioo] rw [hc] split_ifs <;> omega