AFTD Auto-Formalizing Theoretical Domains

opposed_latin_blocking_sum_eq

theoremverifiedformalization

Let n >= 2 and let L be an n x n Latin square with symbols 0,...,n-1 (every row and every column of L is a permutation). In the opposed Latin marriage market of L (man i ranks woman j at position L(i,j)+1, woman j ranks man i at position n-L(i,j), smaller rank preferred), let B(mu) be the number of blocking pairs of a complete matching mu. Then the sum of B(mu) over all n! complete matchings mu is n! * n(n-2)/6; that is, the expected number of blocking pairs of a uniformly random complete matching is exactly n(n-2)/6.

Statement

theorem opposed_latin_blocking_sum_eq (n : ℕ) (hn : 2 ≤ n) (L : Fin n → Fin n → Fin n)
    (hL : latin_square_is L) :
    6 * ∑ μ : Equiv.Perm (Fin n),
        {p : Fin n × Fin n | is_blocking_pair (opposed_latin_market L) μ p.1 p.2}.ncard =
      n.factorial * (n * (n - 2))
Formalizes
arXiv:2609.17418 (A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem), eq. (2), Lemma 2.1 and Remark 3.3: E[B] = (1/(n(n-1))) sum_ij A_ij B_ij, computed there for the cyclic market C_n; here for every opposed Latin market, where A_ij = n-1-L(i,j) and B_ij = L(i,j). Stated as a sum over matchings in natural numbers.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • opposed_latin_marketThe strict opposed Latin marriage market associated with an n × n Latin square L: man i ranks woman j at position L(i,j)+1, and woman j…
  • is_blocking_pairIn a marriage market with agent types M and W and a matching μ : M ≃ W, a man m and a woman w form a blocking pair when m strictly prefers…
  • latin_square_isA Latin square of order n: an n × n array with entries in {1, ..., n} whose rows and columns are permutations of {1, ..., n}.

Read back from the Lean

For any natural number $n \ge 2$ and any function $L : \mathrm{Fin}(n) \to \mathrm{Fin}(n) \to \mathrm{Fin}(n)$ that is a Latin square (meaning each row $L(i, \cdot)$ is injective and each column $L(\cdot, j)$ is injective): 6 times the sum over all permutations $\mu \in \mathrm{Perm}(\mathrm{Fin}(n))$ of the number of blocking pairs $(m, w) \in \mathrm{Fin}(n) \times \mathrm{Fin}(n)$ for the matching $\mu$ in the opposed Latin market defined by $L$ is equal to $n! \cdot n(n - 2)$. Here, in the opposed Latin market associated with $L$: - A man $m$ strictly prefers woman $w$ over woman $w'$ if $L(m, w) < L(m, w')$. - A woman $w$ strictly prefers man $m$ over man $m'$ if $n - L(m, w) < n - L(m', w)$ (which, since entries are strictly less than $n$, is equivalent to $L(m, w) > L(m', w)$). - A pair $(m, w)$ is a blocking pair for $\mu$ if $m$ strictly prefers $w$ to his partner $\mu(m)$ and $w$ strictly prefers $m$ to her partner $\mu^{-1}(w)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof calculates the total number of blocking pairs over all n! matchings by representing the blocking condition as an indicator function and exchanging the order of summation. Using the 2-transitivity of the symmetric group S_n, the expectation of any pair indicator over all permutations is uniform across all distinct pairs of indices, reducing the sum over matchings to a sum over all pairs of distinct entries. Because every row and column of the Latin square is a permutation of {0, ..., n-1}, the number of entries above and below a given symbol is determined solely by that symbol's value, causing the sum to factor row by row into a polynomial sum over {0, ..., n-1}. Finally, evaluating this polynomial sum by induction yields exactly n! * n(n-2)/6 blocking pairs in total.

  1. Each row and each column of the Latin square L is an injection on Fin n.

    By definition of a Latin square (`latin_square_is`), each row map L(i, -) and column map L(-, j) is injective. Classical reasoning is enabled for set cardinality calculations.

    lines 6–7

      classical
      obtain ⟨hrow, hcol⟩ := hL
  2. For any function G on pairs and distinct indices i ≠ k, the sum over all permutations ∑_μ G(μ(i'), μ(k')) is independent of the chosen distinct pair (i', k').

    Because the symmetric group S_n acts 2-transitively on Fin n, any distinct pair (i, k) can be mapped to any other distinct pair (i', k') by a permutation ρ, constructed explicitly by composing transpositions. Since right-multiplication by ρ is a bijection on S_n, re-indexing the sum over μ by μ ∘ ρ preserves the total sum while evaluating at (i', k') instead of (i, k).

    lines 8–29

    uses Equiv.swap, Equiv.swap_apply_left, Equiv.swap_apply_of_ne_of_ne, Equiv.Perm.mul_apply, Ne.symm, Equiv.mulRight, Equiv.sum_comp

      have key : ∀ (G : Fin n → Fin n → ℕ) (i k : Fin n), i ≠ k →
          n * (n - 1) * ∑ μ : Equiv.Perm (Fin n), G (μ i) (μ k) =
            n.factorial * ∑ a : Fin n, ∑ b : Fin n, if a = b then 0 else G a b := by
        intro G i k hik
        classical
        have inv : ∀ i' k' : Fin n, i' ≠ k' →
            ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k') = ∑ μ : Equiv.Perm (Fin n), G (μ i) (μ k) := by
          intro i' k' hik'
          obtain ⟨ρ, h1, h2⟩ : ∃ ρ : Equiv.Perm (Fin n), ρ i = i' ∧ ρ k = k' := by
            set σ := Equiv.swap i i' with hσ
            have hm : σ k ≠ i' := by
              intro h
              apply hik
              apply σ.injective
              rw [h, hσ, Equiv.swap_apply_left]
            refine ⟨Equiv.swap (σ k) k' * σ, ?_, ?_⟩
            · rw [Equiv.Perm.mul_apply, hσ, Equiv.swap_apply_left]
              exact Equiv.swap_apply_of_ne_of_ne (Ne.symm hm) hik'
            · rw [Equiv.Perm.mul_apply, Equiv.swap_apply_left]
          symm
          rw [← Equiv.sum_comp (Equiv.mulRight ρ)]
          simp [Equiv.Perm.mul_apply, h1, h2]
  3. Summing over all n(n-1) pairs of distinct indices (i', k') scales the single-pair sum by n(n-1).

    For each fixed i', exactly n - 1 indices k' are distinct from i', so there are n(n-1) distinct pairs (i', k'). Because the permutation sum is invariant across all distinct pairs by the previous step, summing over all i' ≠ k' simply multiplies the single-pair sum by n(n-1).

    lines 30–46

    uses Finset.sum_ite, Finset.filter_ne, Finset.card_erase_of_mem, Finset.card_univ, Fintype.card_fin

        have hcard : ∀ i' : Fin n, (∑ k' : Fin n, if i' = k' then 0 else 1) = n - 1 := by
          intro i'
          rw [Finset.sum_ite, Finset.sum_const_zero, zero_add, Finset.sum_const, smul_eq_mul, mul_one,
            Finset.filter_ne, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ,
            Fintype.card_fin]
        have hsum : ∑ i' : Fin n, ∑ k' : Fin n,
            (if i' = k' then 0 else ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k')) =
              n * (n - 1) * ∑ μ : Equiv.Perm (Fin n), G (μ i) (μ k) := by
          have : ∀ i' k' : Fin n, (if i' = k' then 0 else ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k')) =
              (if i' = k' then 0 else 1) * ∑ μ : Equiv.Perm (Fin n), G (μ i) (μ k) := by
            intro i' k'
            split_ifs with h
            · simp
            · rw [one_mul, inv i' k' h]
          simp only [this, ← Finset.sum_mul, hcard, Finset.sum_const, Finset.card_univ,
            Fintype.card_fin, smul_eq_mul]
        rw [← hsum]
  4. The key averaging lemma holds: n(n-1) ∑_μ G(μ(i), μ(k)) = n! ∑_{a ≠ b} G(a, b) for any distinct indices i ≠ k.

    Exchanging the order of summation between the index pairs (i', k') and the permutation μ brings the sum over μ to the outside. For each fixed permutation μ, the map (i', k') ↦ (μ(i'), μ(k')) is a bijection on the set of pairs of distinct elements, so the inner sum is always equal to ∑_{a ≠ b} G(a, b). Summing this constant across all |S_n| = n! permutations completes the proof of `key`.

    lines 47–69

    uses Equiv.sum_comp, Finset.sum_congr, Finset.sum_comm, Fintype.card_perm, Fintype.card_fin

        have hswap : ∀ μ : Equiv.Perm (Fin n),
            (∑ i' : Fin n, ∑ k' : Fin n, if i' = k' then 0 else G (μ i') (μ k')) =
              ∑ a : Fin n, ∑ b : Fin n, if a = b then 0 else G a b := by
          intro μ
          rw [← Equiv.sum_comp μ (fun a => ∑ b : Fin n, if a = b then 0 else G a b)]
          refine Finset.sum_congr rfl fun a _ => ?_
          rw [← Equiv.sum_comp μ (fun b => if μ a = b then 0 else G (μ a) b)]
          refine Finset.sum_congr rfl fun b _ => ?_
          simp [μ.injective.eq_iff]
        have hcomm : (∑ i' : Fin n, ∑ k' : Fin n,
            (if i' = k' then 0 else ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k'))) =
            ∑ μ : Equiv.Perm (Fin n), ∑ i' : Fin n, ∑ k' : Fin n,
              if i' = k' then 0 else G (μ i') (μ k') := by
          have hpush : ∀ i' k' : Fin n,
              (if i' = k' then 0 else ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k')) =
                ∑ μ : Equiv.Perm (Fin n), if i' = k' then 0 else G (μ i') (μ k') := by
            intro i' k'
            split_ifs <;> simp
          simp_rw [hpush]
          rw [Finset.sum_congr rfl fun i' _ => Finset.sum_comm]
          exact Finset.sum_comm
        rw [hcomm, Finset.sum_congr rfl fun μ _ => hswap μ, Finset.sum_const, Finset.card_univ,
          Fintype.card_perm, Fintype.card_fin, smul_eq_mul]
  5. For every natural number m, 6 * ∑_{y=0}^{m-1} (m - 1 - y) * y = m * (m - 1) * (m - 2).

    This integer identity is proved by induction on m. The base cases m = 0, 1, 2 vanish trivially. For the inductive step, splitting off the last term from the sum and expanding (m - y)y = (m - 1 - y)y + y expresses the sum for m + 1 as the sum for m plus the triangular sum ∑_{y < m} y. Applying the induction hypothesis and the triangular number formula 2 * ∑_{y < m} y = m(m-1), the algebraic identity simplifies directly.

    lines 70–96

    uses Finset.sum_range_succ, Finset.sum_range_id_mul_two, Nat.add_sub_cancel

      have hf : ∀ m : ℕ, 6 * ∑ y ∈ Finset.range m, (m - 1 - y) * y = m * (m - 1) * (m - 2) := by
        intro n
        induction n with
        | zero => simp
        | succ n ih =>
          have h : ∑ y ∈ Finset.range (n + 1), (n + 1 - 1 - y) * y =
              ∑ y ∈ Finset.range n, (n - 1 - y) * y + ∑ y ∈ Finset.range n, y := by
            rw [Finset.sum_range_succ, ← Finset.sum_add_distrib]
            simp only [Nat.add_sub_cancel, Nat.sub_self, zero_mul, add_zero]
            refine Finset.sum_congr rfl fun y hy => ?_
            have := Finset.mem_range.mp hy
            obtain ⟨d, rfl⟩ : ∃ d, n = y + 1 + d := ⟨n - y - 1, by omega⟩
            rw [show y + 1 + d - y = d + 1 by omega, show y + 1 + d - 1 - y = d by omega]
            ring
          have g := Finset.sum_range_id_mul_two n
          rw [h, mul_add, ih]
          rcases n with _ | _ | n
          · simp
          · simp
          · have e1 : n + 1 + 1 + 1 - 2 = n + 1 := by omega
            have e2 : n + 1 + 1 - 2 = n := by omega
            have : 6 * ∑ i ∈ Finset.range (n + 1 + 1), i = 3 * ((n + 1 + 1) * (n + 1)) := by
              rw [show (n + 1 + 1) * (n + 1) = (∑ i ∈ Finset.range (n + 1 + 1), i) * 2 by
                rw [g]; rfl]; ring
            rw [this]
            simp only [Nat.add_sub_cancel, e1, e2]
            ring
  6. The number of blocking pairs for a matching μ is given by the double sum ∑_i ∑_k G(i, k, μ(i), μ(k)), where G(i, k, a, b) indicates that L(i, b) < L(i, a) and L(k, b) < L(i, b).

    A pair (i, j) blocks μ if man i prefers woman j to his match μ(i) (so L(i, j) < L(i, μ(i))) and woman j prefers man i to her match μ⁻¹(j) (which in the opposed market means n - L(i, j) < n - L(μ⁻¹(j), j), or equivalently L(μ⁻¹(j), j) < L(i, j)). Re-indexing woman j by the man k = μ⁻¹(j) she is matched with, so that j = μ(k), this blocking condition is precisely G(i, k, μ(i), μ(k)) = 1. Summing the indicator over all (i, k) counts all blocking pairs.

    lines 97–117

    uses is_blocking_pair, opposed_latin_market, Set.ncard_coe_finset, Finset.card_filter, Fintype.sum_prod_type, Equiv.sum_comp

      set G : Fin n → Fin n → Fin n → Fin n → ℕ := fun i k a b =>
        if (L i b : ℕ) < L i a ∧ (L k b : ℕ) < L i b then 1 else 0 with hG
      have hB : ∀ μ : Equiv.Perm (Fin n),
          {p : Fin n × Fin n | is_blocking_pair (opposed_latin_market L) μ p.1 p.2}.ncard =
            ∑ i : Fin n, ∑ k : Fin n, G i k (μ i) (μ k) := by
        intro μ
        have hset : {p : Fin n × Fin n | is_blocking_pair (opposed_latin_market L) μ p.1 p.2} =
            ↑(Finset.univ.filter fun p : Fin n × Fin n =>
              (L p.1 p.2 : ℕ) < L p.1 (μ p.1) ∧ (L (μ.symm p.2) p.2 : ℕ) < L p.1 p.2) := by
          ext p
          simp only [is_blocking_pair, opposed_latin_market, Set.mem_ofPred_eq, Finset.coe_filter,
            Finset.mem_univ, true_and]
          have := (L p.1 p.2).isLt
          have := (L (μ.symm p.2) p.2).isLt
          constructor <;> rintro ⟨h1, h2⟩ <;> exact ⟨h1, by omega⟩
        rw [hset, Set.ncard_coe_finset, Finset.card_filter, Fintype.sum_prod_type]
        refine Finset.sum_congr rfl fun i _ => ?_
        rw [← Equiv.sum_comp μ (fun j => if (L i j : ℕ) < L i (μ i) ∧ (L (μ.symm j) j : ℕ) < L i j
          then 1 else 0)]
        refine Finset.sum_congr rfl fun k _ => ?_
        simp [hG]
  7. The scaled total blocking sum n(n-1) * ∑_μ ∑_i ∑_k G(i, k, μ(i), μ(k)) equals n! * ∑_i ∑_k ∑_{a ≠ b} G(i, k, a, b).

    When i = k, the definition of G requires L(i, b) < L(i, b), which is impossible, so the diagonal terms G(i, i, a, b) are zero. For each of the remaining pairs of distinct indices i ≠ k, applying the key averaging lemma (`key`) to G(i, k, -, -) replaces the sum over μ by n! * ∑_{a ≠ b} G(i, k, a, b). Summing over all i and k gives the result.

    lines 118–131

    uses Finset.sum_comm, Finset.mul_sum, Finset.sum_congr

      have hdiag : ∀ i a b : Fin n, G i i a b = 0 := by
        intro i a b; simp only [hG]; split_ifs with h <;> omega
      have hstep : n * (n - 1) * ∑ μ : Equiv.Perm (Fin n), ∑ i : Fin n, ∑ k : Fin n,
          G i k (μ i) (μ k) =
            n.factorial * ∑ i : Fin n, ∑ k : Fin n, ∑ a : Fin n, ∑ b : Fin n,
              (if a = b then 0 else G i k a b) := by
        rw [Finset.sum_comm, Finset.mul_sum, Finset.mul_sum]
        refine Finset.sum_congr rfl fun i _ => ?_
        rw [Finset.sum_comm, Finset.mul_sum, Finset.mul_sum]
        refine Finset.sum_congr rfl fun k _ => ?_
        by_cases hik : i = k
        · subst hik
          simp [hdiag]
        · exact key (G i k) i k hik
  8. In any row i, the number of entries strictly greater than x is n - 1 - x.

    Because row i of the Latin square is an injective map from Fin n to Fin n, it is a bijection by finiteness. Re-indexing the sum by this bijection, the condition x < L(i, a) simply counts the number of values in {0, ..., n-1} strictly greater than x, which is the cardinality of the open interval (x, n), namely n - 1 - x.

    lines 132–140

    uses Equiv.sum_comp, Equiv.ofBijective, Fin.sum_univ_eq_sum_range, Finset.sum_boole, Nat.card_Ioo

      have hrowsum : ∀ (i : Fin n) (x : ℕ),
          (∑ a : Fin n, if x < (L i a : ℕ) then 1 else 0) = n - 1 - x := by
        intro i x
        rw [← Equiv.sum_comp (Equiv.ofBijective _ (hrow i).bijective_of_finite).symm]
        simp only [Equiv.ofBijective_apply_symm_apply]
        rw [Fin.sum_univ_eq_sum_range (fun y => if x < y then 1 else 0) n, Finset.sum_boole,
          Nat.cast_id, show (Finset.range n).filter (fun y => x < y) = Finset.Ioo x n by
            ext y; simp [Finset.mem_Ioo]; omega, Nat.card_Ioo]
        omega
  9. In any column b, the number of entries strictly less than x (for x ≤ n) is x.

    Because column b of the Latin square is an injective map from Fin n to Fin n, it is a bijection. Re-indexing by this bijection, the condition L(k, b) < x counts the number of values in {0, ..., n-1} strictly less than x, which is the cardinality of the range {0, ..., x-1}, namely x.

    lines 141–150

    uses Equiv.sum_comp, Equiv.ofBijective, Fin.sum_univ_eq_sum_range, Finset.sum_boole, Finset.card_range

      have hcolsum : ∀ (b : Fin n) (x : ℕ), x ≤ n →
          (∑ k : Fin n, if (L k b : ℕ) < x then 1 else 0) = x := by
        intro b x hx
        rw [← Equiv.sum_comp (Equiv.ofBijective (fun i => L i b) (hcol b).bijective_of_finite).symm]
        have h := fun y => Equiv.ofBijective_apply_symm_apply (fun i => L i b)
          (hcol b).bijective_of_finite y
        simp only [h]
        rw [Fin.sum_univ_eq_sum_range (fun y => if y < x then 1 else 0) n, Finset.sum_boole,
          Nat.cast_id, show (Finset.range n).filter (fun y => y < x) = Finset.range x by
            ext y; simp; omega, Finset.card_range]
  10. The 4-fold sum ∑_i ∑_k ∑_{a ≠ b} G(i, k, a, b) equals n * ∑_{y=0}^{n-1} (n - 1 - y) * y.

    For a fixed row i and column b, the condition (a ≠ b) ∧ G(i, k, a, b) factors into independent requirements on a and k: L(i, b) < L(i, a) and L(k, b) < L(i, b). Summing over a yields n - 1 - L(i, b) by the row-sum identity, and summing over k yields L(i, b) by the column-sum identity. Summing their product (n - 1 - L(i, b)) * L(i, b) over b re-indexes over all values y in {0, ..., n-1} because row i is a bijection. Finally, summing the identical result across all n rows i multiplies by an outer factor of n.

    lines 151–179

    uses if_neg, Finset.sum_comm, Finset.sum_mul_sum, Fin.sum_univ_eq_sum_range, Equiv.sum_comp, Equiv.ofBijective, le_of_lt

      have hT : ∑ i : Fin n, ∑ k : Fin n, ∑ a : Fin n, ∑ b : Fin n,
          (if a = b then 0 else G i k a b) = n * ∑ y ∈ Finset.range n, (n - 1 - y) * y := by
        have hrow' : ∀ i : Fin n, (∑ k : Fin n, ∑ a : Fin n, ∑ b : Fin n,
            (if a = b then 0 else G i k a b)) = ∑ y ∈ Finset.range n, (n - 1 - y) * y := by
          intro i
          have e1 : ∀ k a b : Fin n, (if a = b then 0 else G i k a b) =
              (if (L i b : ℕ) < L i a then 1 else 0) * (if (L k b : ℕ) < L i b then 1 else 0) := by
            intro k a b
            simp only [hG]
            by_cases hab : a = b
            · subst hab; simp
            · rw [if_neg hab]
              by_cases h1 : (L i b : ℕ) < L i a <;> by_cases h2 : (L k b : ℕ) < L i b <;> simp [h1, h2]
          simp_rw [e1]
          have e2 : (∑ k : Fin n, ∑ a : Fin n, ∑ b : Fin n,
              (if (L i b : ℕ) < L i a then 1 else 0) * (if (L k b : ℕ) < L i b then 1 else 0)) =
              ∑ b : Fin n, (∑ a : Fin n, if (L i b : ℕ) < L i a then 1 else 0) *
                (∑ k : Fin n, if (L k b : ℕ) < L i b then 1 else 0) := by
            rw [Finset.sum_congr rfl fun k _ => Finset.sum_comm, Finset.sum_comm]
            refine Finset.sum_congr rfl fun b _ => ?_
            rw [Finset.sum_mul_sum]
            exact Finset.sum_comm
          rw [e2]
          simp_rw [hrowsum, fun b => hcolsum b _ (le_of_lt (L i b).isLt)]
          rw [← Fin.sum_univ_eq_sum_range (fun y => (n - 1 - y) * y) n]
          exact Equiv.sum_comp (Equiv.ofBijective _ (hrow i).bijective_of_finite)
            (fun y : Fin n => (n - 1 - (y : ℕ)) * y)
        rw [Finset.sum_congr rfl fun i _ => hrow' i]
        simp
  11. Multiplying the sum of blocking pairs by 6 gives n! * n(n-2), concluding the theorem.

    Since n ≥ 2, the multiplier n(n-1) is strictly positive. Multiplying the expression by n(n-1) allows substitution of the previous identities to express n(n-1) * (6 * ∑_μ B(μ)) as n! * n * (6 * ∑_{y=0}^{n-1} (n - 1 - y) * y). By the polynomial summation lemma hf, the parenthesized sum is n(n-1)(n-2), making the right-hand side n(n-1) * (n! * n(n-2)). Canceling the positive factor n(n-1) from both sides completes the proof.

    lines 180–188

    uses Nat.mul_pos, Nat.eq_of_mul_eq_mul_left, Finset.sum_congr

      have hpos : 0 < n * (n - 1) := Nat.mul_pos (by omega) (by omega)
      apply Nat.eq_of_mul_eq_mul_left hpos
      rw [Finset.sum_congr rfl fun μ _ => hB μ]
      calc n * (n - 1) * (6 * ∑ μ : Equiv.Perm (Fin n), ∑ i : Fin n, ∑ k : Fin n, G i k (μ i) (μ k))
          = 6 * (n * (n - 1) * ∑ μ : Equiv.Perm (Fin n), ∑ i : Fin n, ∑ k : Fin n,
              G i k (μ i) (μ k)) := by ring
        _ = n.factorial * n * (6 * ∑ y ∈ Finset.range n, (n - 1 - y) * y) := by
              rw [hstep, hT]; ring
        _ = n * (n - 1) * (n.factorial * (n * (n - 2))) := by rw [hf]; ring
Equiv.swap
The transposition that swaps elements a and b and leaves all other elements fixed.
Equiv.swap_apply_left
The transposition swap(a, b) maps a to b.
Equiv.swap_apply_of_ne_of_ne
The transposition swap(a, b) fixes any element x distinct from both a and b.
Equiv.Perm.mul_apply
Permutation multiplication is function composition: (f * g)(x) = f(g(x)).
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Equiv.mulRight
In a group, right-multiplication by a fixed element is a permutation of the group.
Equiv.sum_comp
Re-indexing a finite sum by a bijection (equivalence) preserves the sum: ∑ i, g(e(i)) = ∑ i, g(i).
Finset.sum_ite
A sum of an if-then-else splits into the sum over elements satisfying the condition plus the sum over those that do not.
Finset.filter_ne
Filtering a finite set for elements not equal to b is equivalent to erasing b from the set.
Finset.card_erase_of_mem
Removing an element that belongs to a finite set decreases its cardinality by 1.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
Finset.sum_congr
If two finite index sets are equal and the summands agree on each element, the sums are equal.
Finset.sum_comm
Fubini's theorem for finite sums: the order of summation in a double sum can be swapped.
Fintype.card_perm
The cardinality of the permutation group on a finite set of size k is k!.
Finset.sum_range_succ
Splitting off the last term from a range sum: ∑_{x < n+1} f(x) = (∑_{x < n} f(x)) + f(n).
Finset.sum_range_id_mul_two
Twice the sum of the first n natural numbers equals n(n-1): 2 * ∑_{i < n} i = n * (n - 1).
Nat.add_sub_cancel
For natural numbers, (n + m) - m = n.
is_blocking_pair
A pair (m, w) blocks matching μ if m prefers w to μ(m) and w prefers m to μ⁻¹(w).
opposed_latin_market
The marriage market defined by Latin square L where man i prefers woman j over j' when L(i,j) < L(i,j'), and woman j prefers man i over i' when n - L(i,j) < n - L(i',j).
Set.ncard_coe_finset
The set cardinality (.ncard) of a coerced finite set equals its finset cardinality (.card).
Finset.card_filter
The cardinality of a filtered subset equals the sum over the parent set of the indicator of the condition.
Fintype.sum_prod_type
A sum over a Cartesian product type α₁ × α₂ is equal to the iterated sum over α₁ and α₂.
Finset.mul_sum
A constant factor distributes over a finite sum: a * ∑ f(i) = ∑ a * f(i).
Equiv.ofBijective
A bijective function between types can be promoted to an equivalence (a bijection).
Fin.sum_univ_eq_sum_range
Summing a function over Fin n is equivalent to summing over the range {0, ..., n-1} in ℕ.
Finset.sum_boole
The sum of the boolean indicator of a condition over a set equals the cardinality of the subset satisfying the condition.
Nat.card_Ioo
The number of natural numbers strictly between a and b is b - a - 1 (for a < b).
Finset.card_range
The cardinality of the range set {0, ..., n-1} is n.
if_neg
An if-then-else expression reduces to the else branch when the condition is false.
Finset.sum_mul_sum
The product of two finite sums equals the double sum of the pairwise products of their terms.
le_of_lt
Strict inequality of numbers implies non-strict inequality: a < b implies a ≤ b.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
Nat.eq_of_mul_eq_mul_left
Left cancellation for multiplication of natural numbers: if n > 0 and n * m = n * k, then m = k.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem opposed_latin_blocking_sum_eq (n : ℕ) (hn : 2 ≤ n) (L : Fin n → Fin n → Fin n)    (hL : latin_square_is L) :    6 * ∑ μ : Equiv.Perm (Fin n),        {p : Fin n × Fin n | is_blocking_pair (opposed_latin_market L) μ p.1 p.2}.ncard =      n.factorial * (n * (n - 2)) := by  classical  obtain ⟨hrow, hcol⟩ := hL  have key : ∀ (G : Fin n → Fin n → ℕ) (i k : Fin n), i ≠ k →      n * (n - 1) * ∑ μ : Equiv.Perm (Fin n), G (μ i) (μ k) =        n.factorial * ∑ a : Fin n, ∑ b : Fin n, if a = b then 0 else G a b := by    intro G i k hik    classical    have inv : ∀ i' k' : Fin n, i' ≠ k' →        ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k') = ∑ μ : Equiv.Perm (Fin n), G (μ i) (μ k) := by      intro i' k' hik'      obtain ⟨ρ, h1, h2⟩ : ∃ ρ : Equiv.Perm (Fin n), ρ i = i' ∧ ρ k = k' := by        set σ := Equiv.swap i i' with hσ        have hm : σ k ≠ i' := by          intro h          apply hik          apply σ.injective          rw [h, hσ, Equiv.swap_apply_left]        refine ⟨Equiv.swap (σ k) k' * σ, ?_, ?_⟩        · rw [Equiv.Perm.mul_apply, hσ, Equiv.swap_apply_left]          exact Equiv.swap_apply_of_ne_of_ne (Ne.symm hm) hik'        · rw [Equiv.Perm.mul_apply, Equiv.swap_apply_left]      symm      rw [← Equiv.sum_comp (Equiv.mulRight ρ)]      simp [Equiv.Perm.mul_apply, h1, h2]    have hcard : ∀ i' : Fin n, (∑ k' : Fin n, if i' = k' then 0 else 1) = n - 1 := by      intro i'      rw [Finset.sum_ite, Finset.sum_const_zero, zero_add, Finset.sum_const, smul_eq_mul, mul_one,        Finset.filter_ne, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ,        Fintype.card_fin]    have hsum : ∑ i' : Fin n, ∑ k' : Fin n,        (if i' = k' then 0 else ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k')) =          n * (n - 1) * ∑ μ : Equiv.Perm (Fin n), G (μ i) (μ k) := by      have : ∀ i' k' : Fin n, (if i' = k' then 0 else ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k')) =          (if i' = k' then 0 else 1) * ∑ μ : Equiv.Perm (Fin n), G (μ i) (μ k) := by        intro i' k'        split_ifs with h        · simp        · rw [one_mul, inv i' k' h]      simp only [this, ← Finset.sum_mul, hcard, Finset.sum_const, Finset.card_univ,        Fintype.card_fin, smul_eq_mul]    rw [← hsum]    have hswap : ∀ μ : Equiv.Perm (Fin n),        (∑ i' : Fin n, ∑ k' : Fin n, if i' = k' then 0 else G (μ i') (μ k')) =          ∑ a : Fin n, ∑ b : Fin n, if a = b then 0 else G a b := by      intro μ      rw [← Equiv.sum_comp μ (fun a => ∑ b : Fin n, if a = b then 0 else G a b)]      refine Finset.sum_congr rfl fun a _ => ?_      rw [← Equiv.sum_comp μ (fun b => if μ a = b then 0 else G (μ a) b)]      refine Finset.sum_congr rfl fun b _ => ?_      simp [μ.injective.eq_iff]    have hcomm : (∑ i' : Fin n, ∑ k' : Fin n,        (if i' = k' then 0 else ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k'))) =        ∑ μ : Equiv.Perm (Fin n), ∑ i' : Fin n, ∑ k' : Fin n,          if i' = k' then 0 else G (μ i') (μ k') := by      have hpush : ∀ i' k' : Fin n,          (if i' = k' then 0 else ∑ μ : Equiv.Perm (Fin n), G (μ i') (μ k')) =            ∑ μ : Equiv.Perm (Fin n), if i' = k' then 0 else G (μ i') (μ k') := by        intro i' k'        split_ifs <;> simp      simp_rw [hpush]      rw [Finset.sum_congr rfl fun i' _ => Finset.sum_comm]      exact Finset.sum_comm    rw [hcomm, Finset.sum_congr rfl fun μ _ => hswap μ, Finset.sum_const, Finset.card_univ,      Fintype.card_perm, Fintype.card_fin, smul_eq_mul]  have hf : ∀ m : ℕ, 6 * ∑ y ∈ Finset.range m, (m - 1 - y) * y = m * (m - 1) * (m - 2) := by    intro n    induction n with    | zero => simp    | succ n ih =>      have h : ∑ y ∈ Finset.range (n + 1), (n + 1 - 1 - y) * y =          ∑ y ∈ Finset.range n, (n - 1 - y) * y + ∑ y ∈ Finset.range n, y := by        rw [Finset.sum_range_succ, ← Finset.sum_add_distrib]        simp only [Nat.add_sub_cancel, Nat.sub_self, zero_mul, add_zero]        refine Finset.sum_congr rfl fun y hy => ?_        have := Finset.mem_range.mp hy        obtain ⟨d, rfl⟩ : ∃ d, n = y + 1 + d := ⟨n - y - 1, by omega⟩        rw [show y + 1 + d - y = d + 1 by omega, show y + 1 + d - 1 - y = d by omega]        ring      have g := Finset.sum_range_id_mul_two n      rw [h, mul_add, ih]      rcases n with _ | _ | n      · simp      · simp      · have e1 : n + 1 + 1 + 1 - 2 = n + 1 := by omega        have e2 : n + 1 + 1 - 2 = n := by omega        have : 6 * ∑ i ∈ Finset.range (n + 1 + 1), i = 3 * ((n + 1 + 1) * (n + 1)) := by          rw [show (n + 1 + 1) * (n + 1) = (∑ i ∈ Finset.range (n + 1 + 1), i) * 2 by            rw [g]; rfl]; ring        rw [this]        simp only [Nat.add_sub_cancel, e1, e2]        ring  set G : Fin n → Fin n → Fin n → Fin n → ℕ := fun i k a b =>    if (L i b : ℕ) < L i a ∧ (L k b : ℕ) < L i b then 1 else 0 with hG  have hB : ∀ μ : Equiv.Perm (Fin n),      {p : Fin n × Fin n | is_blocking_pair (opposed_latin_market L) μ p.1 p.2}.ncard =        ∑ i : Fin n, ∑ k : Fin n, G i k (μ i) (μ k) := by    intro μ    have hset : {p : Fin n × Fin n | is_blocking_pair (opposed_latin_market L) μ p.1 p.2} =        ↑(Finset.univ.filter fun p : Fin n × Fin n =>          (L p.1 p.2 : ℕ) < L p.1 (μ p.1) ∧ (L (μ.symm p.2) p.2 : ℕ) < L p.1 p.2) := by      ext p      simp only [is_blocking_pair, opposed_latin_market, Set.mem_ofPred_eq, Finset.coe_filter,        Finset.mem_univ, true_and]      have := (L p.1 p.2).isLt      have := (L (μ.symm p.2) p.2).isLt      constructor <;> rintro ⟨h1, h2⟩ <;> exact ⟨h1, by omega⟩    rw [hset, Set.ncard_coe_finset, Finset.card_filter, Fintype.sum_prod_type]    refine Finset.sum_congr rfl fun i _ => ?_    rw [← Equiv.sum_comp μ (fun j => if (L i j : ℕ) < L i (μ i) ∧ (L (μ.symm j) j : ℕ) < L i j      then 1 else 0)]    refine Finset.sum_congr rfl fun k _ => ?_    simp [hG]  have hdiag : ∀ i a b : Fin n, G i i a b = 0 := by    intro i a b; simp only [hG]; split_ifs with h <;> omega  have hstep : n * (n - 1) * ∑ μ : Equiv.Perm (Fin n), ∑ i : Fin n, ∑ k : Fin n,      G i k (μ i) (μ k) =        n.factorial * ∑ i : Fin n, ∑ k : Fin n, ∑ a : Fin n, ∑ b : Fin n,          (if a = b then 0 else G i k a b) := by    rw [Finset.sum_comm, Finset.mul_sum, Finset.mul_sum]    refine Finset.sum_congr rfl fun i _ => ?_    rw [Finset.sum_comm, Finset.mul_sum, Finset.mul_sum]    refine Finset.sum_congr rfl fun k _ => ?_    by_cases hik : i = k    · subst hik      simp [hdiag]    · exact key (G i k) i k hik  have hrowsum : ∀ (i : Fin n) (x : ℕ),      (∑ a : Fin n, if x < (L i a : ℕ) then 1 else 0) = n - 1 - x := by    intro i x    rw [← Equiv.sum_comp (Equiv.ofBijective _ (hrow i).bijective_of_finite).symm]    simp only [Equiv.ofBijective_apply_symm_apply]    rw [Fin.sum_univ_eq_sum_range (fun y => if x < y then 1 else 0) n, Finset.sum_boole,      Nat.cast_id, show (Finset.range n).filter (fun y => x < y) = Finset.Ioo x n by        ext y; simp [Finset.mem_Ioo]; omega, Nat.card_Ioo]    omega  have hcolsum : ∀ (b : Fin n) (x : ℕ), x ≤ n →      (∑ k : Fin n, if (L k b : ℕ) < x then 1 else 0) = x := by    intro b x hx    rw [← Equiv.sum_comp (Equiv.ofBijective (fun i => L i b) (hcol b).bijective_of_finite).symm]    have h := fun y => Equiv.ofBijective_apply_symm_apply (fun i => L i b)      (hcol b).bijective_of_finite y    simp only [h]    rw [Fin.sum_univ_eq_sum_range (fun y => if y < x then 1 else 0) n, Finset.sum_boole,      Nat.cast_id, show (Finset.range n).filter (fun y => y < x) = Finset.range x by        ext y; simp; omega, Finset.card_range]  have hT : ∑ i : Fin n, ∑ k : Fin n, ∑ a : Fin n, ∑ b : Fin n,      (if a = b then 0 else G i k a b) = n * ∑ y ∈ Finset.range n, (n - 1 - y) * y := by    have hrow' : ∀ i : Fin n, (∑ k : Fin n, ∑ a : Fin n, ∑ b : Fin n,        (if a = b then 0 else G i k a b)) = ∑ y ∈ Finset.range n, (n - 1 - y) * y := by      intro i      have e1 : ∀ k a b : Fin n, (if a = b then 0 else G i k a b) =          (if (L i b : ℕ) < L i a then 1 else 0) * (if (L k b : ℕ) < L i b then 1 else 0) := by        intro k a b        simp only [hG]        by_cases hab : a = b        · subst hab; simp        · rw [if_neg hab]          by_cases h1 : (L i b : ℕ) < L i a <;> by_cases h2 : (L k b : ℕ) < L i b <;> simp [h1, h2]      simp_rw [e1]      have e2 : (∑ k : Fin n, ∑ a : Fin n, ∑ b : Fin n,          (if (L i b : ℕ) < L i a then 1 else 0) * (if (L k b : ℕ) < L i b then 1 else 0)) =          ∑ b : Fin n, (∑ a : Fin n, if (L i b : ℕ) < L i a then 1 else 0) *            (∑ k : Fin n, if (L k b : ℕ) < L i b then 1 else 0) := by        rw [Finset.sum_congr rfl fun k _ => Finset.sum_comm, Finset.sum_comm]        refine Finset.sum_congr rfl fun b _ => ?_        rw [Finset.sum_mul_sum]        exact Finset.sum_comm      rw [e2]      simp_rw [hrowsum, fun b => hcolsum b _ (le_of_lt (L i b).isLt)]      rw [← Fin.sum_univ_eq_sum_range (fun y => (n - 1 - y) * y) n]      exact Equiv.sum_comp (Equiv.ofBijective _ (hrow i).bijective_of_finite)        (fun y : Fin n => (n - 1 - (y : ℕ)) * y)    rw [Finset.sum_congr rfl fun i _ => hrow' i]    simp  have hpos : 0 < n * (n - 1) := Nat.mul_pos (by omega) (by omega)  apply Nat.eq_of_mul_eq_mul_left hpos  rw [Finset.sum_congr rfl fun μ _ => hB μ]  calc n * (n - 1) * (6 * ∑ μ : Equiv.Perm (Fin n), ∑ i : Fin n, ∑ k : Fin n, G i k (μ i) (μ k))      = 6 * (n * (n - 1) * ∑ μ : Equiv.Perm (Fin n), ∑ i : Fin n, ∑ k : Fin n,          G i k (μ i) (μ k)) := by ring    _ = n.factorial * n * (6 * ∑ y ∈ Finset.range n, (n - 1 - y) * y) := by          rw [hstep, hT]; ring    _ = n * (n - 1) * (n.factorial * (n * (n - 2))) := by rw [hf]; ring
See it in the graphDiscuss this resultChallenge it