opposed_latin_blocking_sum_eq
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.
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.
classical obtain ⟨hrow, hcol⟩ := hLFor 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).
uses
Equiv.swap,Equiv.swap_apply_left,Equiv.swap_apply_of_ne_of_ne,Equiv.Perm.mul_apply,Ne.symm,Equiv.mulRight,Equiv.sum_comphave 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]
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).
uses
Finset.sum_ite,Finset.filter_ne,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_finhave 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]
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`.
uses
Equiv.sum_comp,Finset.sum_congr,Finset.sum_comm,Fintype.card_perm,Fintype.card_finhave 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]
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.
uses
Finset.sum_range_succ,Finset.sum_range_id_mul_two,Nat.add_sub_cancelhave 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
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.
uses
is_blocking_pair,opposed_latin_market,Set.ncard_coe_finset,Finset.card_filter,Fintype.sum_prod_type,Equiv.sum_compset 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]
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.
uses
Finset.sum_comm,Finset.mul_sum,Finset.sum_congrhave 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
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.
uses
Equiv.sum_comp,Equiv.ofBijective,Fin.sum_univ_eq_sum_range,Finset.sum_boole,Nat.card_Ioohave 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
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.
uses
Equiv.sum_comp,Equiv.ofBijective,Fin.sum_univ_eq_sum_range,Finset.sum_boole,Finset.card_rangehave 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]
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.
uses
if_neg,Finset.sum_comm,Finset.sum_mul_sum,Fin.sum_univ_eq_sum_range,Equiv.sum_comp,Equiv.ofBijective,le_of_lthave 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
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.
uses
Nat.mul_pos,Nat.eq_of_mul_eq_mul_left,Finset.sum_congrhave 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.
- The entire proof is carried out within the natural numbers (ℕ), multiplying both sides by 6 and n(n-1) > 0 and canceling at the end with Nat.eq_of_mul_eq_mul_left to avoid fractions and rational division.
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
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 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