AFTD Auto-Formalizing Theoretical Domains

perm_inv_left_add

theoremverified

For a permutation s of {0, ..., n-1} and a position g, the number of x < g with s(x) > s(g), plus s(g), equals the number of x > g with s(x) < s(g), plus g.

Statement

theorem perm_inv_left_add {n : ℕ} (σ : Equiv.Perm (Fin n)) (g : Fin n) :
    (Finset.univ.filter fun x : Fin n => (x : ℕ) < g ∧ (σ g : ℕ) < σ x).card + (σ g : ℕ) =
      (Finset.univ.filter fun x : Fin n => (g : ℕ) < x ∧ (σ x : ℕ) < σ g).card + (g : ℕ)
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 1
  • 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…

Lean source view module on GitHub

theorem perm_inv_left_add {n : ℕ} (σ : Equiv.Perm (Fin n)) (g : Fin n) :    (Finset.univ.filter fun x : Fin n => (x : ℕ) < g ∧ (σ g : ℕ) < σ x).card + (σ g : ℕ) =      (Finset.univ.filter fun x : Fin n => (g : ℕ) < x ∧ (σ x : ℕ) < σ g).card + (g : ℕ) := by  have hA := perm_card_val_lt σ (σ g)  have key : (Finset.univ.filter fun x : Fin n => (x : ℕ) < g ∧ (σ g : ℕ) < σ x).card +      (Finset.univ.filter fun x : Fin n => (σ x : ℕ) < σ g).card =      (Finset.univ.filter fun x : Fin n => (g : ℕ) < x ∧ (σ x : ℕ) < σ g).card +      (Finset.univ.filter fun x : Fin n => (x : ℕ) < g).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 x _ => ?_    have h1 : (x : ℕ) = g → (σ x : ℕ) = σ g := fun h => by rw [Fin.val_inj.mp h]    have h2 : (σ x : ℕ) = σ g → (x : ℕ) = g := fun h => by      rw [σ.injective (Fin.val_inj.mp h)]    split_ifs <;> omega  have hB : (Finset.univ.filter fun x : Fin n => (x : ℕ) < g).card = g := by    have := perm_card_val_lt (Equiv.refl (Fin n)) g    simpa using this  rw [hA, hB] at key  exact key
See it in the graphDiscuss this resultChallenge it