perm_nesting_bound
theoremverified
For 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 on the same side (both s(x) < x or both not), plus the number of pairs with s(a) < a, s(b) >= b and not (b < a and s(a) < s(b)), plus k, is at most k(n - k).
Statement
theorem perm_nesting_bound {n : ℕ} (σ : Equiv.Perm (Fin n)) : (∑ a : Fin n, ∑ b : Fin n, if ((a : ℕ) < b ∧ (σ b : ℕ) < σ a ∧ ((σ a : ℕ) < a ↔ (σ b : ℕ) < b)) ∨ ((σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ ¬((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 1 else 0) * (n - ∑ b : Fin n, if (σ b : ℕ) < b then 1 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- Built on 3
- perm_card_left_gt_leFor a permutation s of {0, ..., n-1} and a position x with x <= s(x), the number of i < x with s(i) > s(x) is at most the number of j > x…
- perm_gap_sumFor 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…
- perm_cross_inv_sumFor a permutation s of {0, ..., n-1}, let A be the positions a with s(a) < a. The number of pairs (a, b) with a in A, b not in A, b < a…
- Used by 1
- hollow_shell_blocking_pairs_ncard_leThe upper half of the Shield-Core conjecture (arXiv:2609.17418, open): in the cyclic Hollow-Shell market C_n, every complete matching has…
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_nesting_bound {n : ℕ} (σ : Equiv.Perm (Fin n)) : (∑ a : Fin n, ∑ b : Fin n, if ((a : ℕ) < b ∧ (σ b : ℕ) < σ a ∧ ((σ a : ℕ) < a ↔ (σ b : ℕ) < b)) ∨ ((σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ ¬((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 1 else 0) * (n - ∑ b : Fin n, if (σ b : ℕ) < b then 1 else 0) := by set k := ∑ b : Fin n, if (σ b : ℕ) < b then 1 else 0 with hk -- the three pieces have hpt : ∀ a b : Fin n, (if ((a : ℕ) < b ∧ (σ b : ℕ) < σ a ∧ ((σ a : ℕ) < a ↔ (σ b : ℕ) < b)) ∨ ((σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ ¬((b : ℕ) < a ∧ (σ a : ℕ) < σ b)) then 1 else 0 : ℕ) ≤ (if (σ a : ℕ) < a ∧ (σ b : ℕ) < a ∧ (a : ℕ) < b then 1 else 0) + (if (a : ℕ) < b ∧ (σ b : ℕ) < σ a ∧ (a : ℕ) ≤ σ a ∧ (b : ℕ) ≤ σ b then 1 else 0) + (if (σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ ¬((b : ℕ) < a ∧ (σ a : ℕ) < σ b) then 1 else 0) := by intro a b by_cases h1 : (σ a : ℕ) < a <;> by_cases h2 : (σ b : ℕ) < b <;> split_ifs <;> omega have hS2 : (∑ a : Fin n, ∑ b : Fin n, if (a : ℕ) < b ∧ (σ b : ℕ) < σ a ∧ (a : ℕ) ≤ σ a ∧ (b : ℕ) ≤ σ b then 1 else 0) ≤ ∑ a : Fin n, ∑ b : Fin n, if (a : ℕ) ≤ σ a ∧ (σ b : ℕ) < a ∧ (a : ℕ) < b then 1 else 0 := by rw [Finset.sum_comm] apply Finset.sum_le_sum intro b _ by_cases hb : (b : ℕ) ≤ σ b · have hc := perm_card_left_gt_le σ b hb rw [Finset.card_filter, Finset.card_filter] at hc calc (∑ a : Fin n, if (a : ℕ) < b ∧ (σ b : ℕ) < σ a ∧ (a : ℕ) ≤ σ a ∧ (b : ℕ) ≤ σ b then 1 else 0) ≤ ∑ a : Fin n, if (a : ℕ) < b ∧ (σ b : ℕ) < σ a then 1 else 0 := by apply Finset.sum_le_sum; intro a _; split_ifs <;> omega _ ≤ ∑ j : Fin n, if (b : ℕ) < j ∧ (σ j : ℕ) < b then 1 else 0 := hc _ = ∑ j : Fin n, if (b : ℕ) ≤ σ b ∧ (σ j : ℕ) < b ∧ (b : ℕ) < j then 1 else 0 := by apply Finset.sum_congr rfl; intro j _; split_ifs <;> omega · have z : ∀ a : Fin n, (if (a : ℕ) < b ∧ (σ b : ℕ) < σ a ∧ (a : ℕ) ≤ σ a ∧ (b : ℕ) ≤ σ b then 1 else 0 : ℕ) = 0 := fun a => if_neg (by omega) simp only [z, Finset.sum_const_zero] exact Nat.zero_le _ -- Q and C have hQ := perm_gap_sum σ have hX := perm_cross_inv_sum σ have hCX : (∑ a : Fin n, ∑ b : Fin n, if (σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ ¬((b : ℕ) < a ∧ (σ a : ℕ) < σ b) then 1 else 0) + (∑ a : Fin n, ∑ b : Fin n, if (σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ (b : ℕ) < a ∧ (σ a : ℕ) < σ b then 1 else 0) = k * (n - k) := by have hn : (∑ b : Fin n, if (σ b : ℕ) < b then 1 else 0) + (∑ b : Fin n, if (b : ℕ) ≤ σ b then 1 else 0) = n := by rw [← Finset.sum_add_distrib] have : ∀ b : Fin n, ((if (σ b : ℕ) < b then 1 else 0) + (if (b : ℕ) ≤ σ b then 1 else 0) : ℕ) = 1 := by intro b; split_ifs <;> omega simp only [this, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul, mul_one] have hnk : (∑ b : Fin n, if (b : ℕ) ≤ σ b then 1 else 0) = n - k := by omega rw [← hnk, Finset.sum_mul_sum, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl; intro a _ rw [← Finset.sum_add_distrib] apply Finset.sum_congr rfl; intro b _ split_ifs <;> omega have hsplit : (∑ a : Fin n, ∑ b : Fin n, if ((a : ℕ) < b ∧ (σ b : ℕ) < σ a ∧ ((σ a : ℕ) < a ↔ (σ b : ℕ) < b)) ∨ ((σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ ¬((b : ℕ) < a ∧ (σ a : ℕ) < σ b)) then 1 else 0) ≤ (∑ a : Fin n, ∑ b : Fin n, if (σ a : ℕ) < a ∧ (σ b : ℕ) < a ∧ (a : ℕ) < b then 1 else 0) + (∑ a : Fin n, ∑ b : Fin n, if (a : ℕ) < b ∧ (σ b : ℕ) < σ a ∧ (a : ℕ) ≤ σ a ∧ (b : ℕ) ≤ σ b then 1 else 0) + (∑ a : Fin n, ∑ b : Fin n, if (σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ ¬((b : ℕ) < a ∧ (σ a : ℕ) < σ b) then 1 else 0) := by rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib] apply Finset.sum_le_sum; intro a _ rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib] apply Finset.sum_le_sum; intro b _ exact hpt a b have hQsplit : (∑ a : Fin n, ∑ b : Fin n, if (σ a : ℕ) < a ∧ (σ b : ℕ) < a ∧ (a : ℕ) < b then 1 else 0) + (∑ a : Fin n, ∑ b : Fin n, if (a : ℕ) ≤ σ a ∧ (σ b : ℕ) < a ∧ (a : ℕ) < b then 1 else 0) = ∑ a : Fin n, ∑ b : Fin n, if (σ b : ℕ) < a ∧ (a : ℕ) < b then 1 else 0 := by rw [← Finset.sum_add_distrib] apply Finset.sum_congr rfl; intro a _ rw [← Finset.sum_add_distrib] apply Finset.sum_congr rfl; intro b _ split_ifs <;> omega omega