perm_card_left_gt_le
theoremverified
For 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 with s(j) < x.
Statement
theorem perm_card_left_gt_le {n : ℕ} (σ : Equiv.Perm (Fin n)) (x : Fin n) (hx : (x : ℕ) ≤ σ x) : (Finset.univ.filter fun i : Fin n => (i : ℕ) < x ∧ (σ x : ℕ) < σ i).card ≤ (Finset.univ.filter fun j : Fin n => (x : ℕ) < j ∧ (σ j : ℕ) < x).card
- 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 1
- perm_card_val_ltFor a permutation s of {0, ..., n-1} and c in {0, ..., n-1}, exactly c elements x have s(x) < c.
- Used by 10
- WickContraction.mem_not_eq_erase_of_isSomeWickContraction.mem_not_eq_erase_of_isSome
- WickContraction.toInvolution_fromInvolutionWickContraction.toInvolution_fromInvolution
- 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…
- WickContraction.fromInvolutionThe Wick contraction formed by an involution
fofFin nby taking as the contracted sets of the contraction the orbits offof… - WickContraction.mem_erase_uncontracted_iffWickContraction.mem_erase_uncontracted_iff
- WickContraction.fromInvolution_getDual?_isSomeWickContraction.fromInvolution_getDual?_isSome
- WickContraction.fromInvolution_getDual?_eq_someWickContraction.fromInvolution_getDual?_eq_some
- WickContraction.mem_uncontracted_iff_not_contractedWickContraction.mem_uncontracted_iff_not_contracted
- WickContraction.mem_not_eq_erase_of_isNoneWickContraction.mem_not_eq_erase_of_isNone
- WickContraction.eraseGiven a Wick contraction
WickContraction n.succand ai : Fin n.succthe Wick contraction associated withnobtained by removing…
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_card_left_gt_le {n : ℕ} (σ : Equiv.Perm (Fin n)) (x : Fin n) (hx : (x : ℕ) ≤ σ x) : (Finset.univ.filter fun i : Fin n => (i : ℕ) < x ∧ (σ x : ℕ) < σ i).card ≤ (Finset.univ.filter fun j : Fin n => (x : ℕ) < j ∧ (σ j : ℕ) < x).card := by have hA := perm_card_val_lt σ x have hB : (Finset.univ.filter fun i : Fin n => (i : ℕ) < x).card = x := by have := perm_card_val_lt (Equiv.refl (Fin n)) x simpa using this have key : (Finset.univ.filter fun i : Fin n => (i : ℕ) < x ∧ (x : ℕ) ≤ σ i).card + (Finset.univ.filter fun i : Fin n => (σ i : ℕ) < x).card = (Finset.univ.filter fun j : Fin n => (x : ℕ) ≤ j ∧ (σ j : ℕ) < x).card + (Finset.univ.filter fun i : Fin n => (i : ℕ) < x).card := by rw [Finset.card_filter, Finset.card_filter, Finset.card_filter, Finset.card_filter, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun i _ => ?_ split_ifs <;> omega rw [hA, hB] at key have e : (Finset.univ.filter fun i : Fin n => (i : ℕ) < x ∧ (x : ℕ) ≤ σ i).card = (Finset.univ.filter fun j : Fin n => (x : ℕ) ≤ j ∧ (σ j : ℕ) < x).card := by omega calc (Finset.univ.filter fun i : Fin n => (i : ℕ) < x ∧ (σ x : ℕ) < σ i).card ≤ (Finset.univ.filter fun i : Fin n => (i : ℕ) < x ∧ (x : ℕ) ≤ σ i).card := by apply Finset.card_le_card intro i simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro h omega _ = (Finset.univ.filter fun j : Fin n => (x : ℕ) ≤ j ∧ (σ j : ℕ) < x).card := e _ ≤ (Finset.univ.filter fun j : Fin n => (x : ℕ) < j ∧ (σ j : ℕ) < x).card := by apply Finset.card_le_card intro j simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro h refine ⟨?_, h.2⟩ rcases Nat.lt_or_eq_of_le h.1 with h' | h' · exact h' · exfalso have : j = x := Fin.val_inj.mp h'.symm subst this omega