AFTD Auto-Formalizing Theoretical Domains

perm_cross_inv_sum

theoremverified

For 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 and s(a) < s(b), plus the sum of s(a) over a in A, equals the sum of a over a in A.

Statement

theorem perm_cross_inv_sum {n : ℕ} (σ : Equiv.Perm (Fin n)) :
    (∑ a : Fin n, ∑ b : Fin n,
        if (σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ (b : ℕ) < a ∧ (σ a : ℕ) < σ b then 1 else 0) +
      ∑ a : Fin n, (if (σ a : ℕ) < a then (σ a : ℕ) else 0) =
      ∑ a : Fin n, (if (σ a : ℕ) < a then (a : ℕ) 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 1
  • perm_inv_left_addFor 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…
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

theorem perm_cross_inv_sum {n : ℕ} (σ : Equiv.Perm (Fin n)) :    (∑ a : Fin n, ∑ b : Fin n,        if (σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ (b : ℕ) < a ∧ (σ a : ℕ) < σ b then 1 else 0) +      ∑ a : Fin n, (if (σ a : ℕ) < a then (σ a : ℕ) else 0) =      ∑ a : Fin n, (if (σ a : ℕ) < a then (a : ℕ) else 0) := by  -- I a b: both in A, an inversion with a on the right  have hpt : ∀ a : Fin n,      (∑ b : Fin n,          if (σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ (b : ℕ) < a ∧ (σ a : ℕ) < σ b then 1 else 0) +        (∑ b : Fin n,          if (σ a : ℕ) < a ∧ (σ b : ℕ) < b ∧ (b : ℕ) < a ∧ (σ a : ℕ) < σ b then 1 else 0) +        (if (σ a : ℕ) < a then (σ a : ℕ) else 0) =      (∑ b : Fin n,          if (σ b : ℕ) < b ∧ (σ a : ℕ) < a ∧ (a : ℕ) < b ∧ (σ b : ℕ) < σ a then 1 else 0) +        (if (σ a : ℕ) < a then (a : ℕ) else 0) := by    intro a    by_cases ha : (σ a : ℕ) < a    · have h1 := perm_inv_left_add σ a      rw [Finset.card_filter, Finset.card_filter] at h1      rw [if_pos ha, if_pos ha, ← Finset.sum_add_distrib]      have e1 : ∀ b : Fin n,          ((if (σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ (b : ℕ) < a ∧ (σ a : ℕ) < σ b then 1 else 0) +            (if (σ a : ℕ) < a ∧ (σ b : ℕ) < b ∧ (b : ℕ) < a ∧ (σ a : ℕ) < σ b then 1 else 0) : ℕ) =          if (b : ℕ) < a ∧ (σ a : ℕ) < σ b then 1 else 0 := by        intro b; split_ifs <;> omega      have e2 : ∀ b : Fin n,          (if (σ b : ℕ) < b ∧ (σ a : ℕ) < a ∧ (a : ℕ) < b ∧ (σ b : ℕ) < σ a then 1 else 0 : ℕ) =          if (a : ℕ) < b ∧ (σ b : ℕ) < σ a then 1 else 0 := by        intro b; split_ifs <;> omega      rw [Finset.sum_congr rfl fun b _ => e1 b, Finset.sum_congr rfl fun b _ => e2 b]      exact h1    · rw [if_neg ha, if_neg ha]      have z : ∀ b : Fin n, (if (σ a : ℕ) < a ∧ (b : ℕ) ≤ σ b ∧ (b : ℕ) < a ∧          (σ a : ℕ) < σ b then 1 else 0 : ℕ) = 0 := fun b => if_neg (by omega)      have z2 : ∀ b : Fin n, (if (σ a : ℕ) < a ∧ (σ b : ℕ) < b ∧ (b : ℕ) < a ∧          (σ a : ℕ) < σ b then 1 else 0 : ℕ) = 0 := fun b => if_neg (by omega)      have z3 : ∀ b : Fin n, (if (σ b : ℕ) < b ∧ (σ a : ℕ) < a ∧ (a : ℕ) < b ∧          (σ b : ℕ) < σ a then 1 else 0 : ℕ) = 0 := fun b => if_neg (by omega)      simp only [z, z2, z3, Finset.sum_const_zero]      rfl  have hsum := Finset.sum_congr rfl fun a (_ : a ∈ Finset.univ) => hpt a  rw [Finset.sum_add_distrib, Finset.sum_add_distrib, Finset.sum_add_distrib] at hsum  have hswap : (∑ a : Fin n, ∑ b : Fin n,      if (σ b : ℕ) < b ∧ (σ a : ℕ) < a ∧ (a : ℕ) < b ∧ (σ b : ℕ) < σ a then 1 else 0) =      ∑ a : Fin n, ∑ b : Fin n,        if (σ a : ℕ) < a ∧ (σ b : ℕ) < b ∧ (b : ℕ) < a ∧ (σ a : ℕ) < σ b then 1 else 0 :=    Finset.sum_comm  rw [hswap] at hsum  omega
See it in the graphDiscuss this resultChallenge it