pm_one_rows_differ_in_half_exists_solution
Let k ≥ 1 and let A : ι → Fin (2k) → ℝ be a finite family of rows with entries ±1. If any two distinct rows differ in exactly k coordinates, then some x : Fin (2k) → ℝ has ∑_j A i j * x j = 1 for every i.
Statement
theorem pm_one_rows_differ_in_half_exists_solution {k : ℕ} (hk : 1 ≤ k) {ι : Type*} [Finite ι] (A : ι → Fin (2 * k) → ℝ) (hA : ∀ i j, A i j = 1 ∨ A i j = -1) (hrows : ∀ i i', A i ≠ A i' → (Finset.univ.filter fun j => A i j ≠ A i' j).card = k) : ∃ x : Fin (2 * k) → ℝ, ∀ i, ∑ j, A i j * x j = 1
- Source
- arXiv:2611.00468 (The symbolic pfaffian method I), Lemma 2.1, the linear-algebra step (the proof differs from the paper's: an explicit solution instead of a rank argument)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- orientation_tuple_is_pfaffian_of_rows_differ_in_halfLet k ≥ 1, let G be a simple graph on Fin n and let D : Fin (2k) → Digraph (Fin n) be a 2k-tuple of orientations of G…
The proof, explained
The proof constructs the explicit solution vector x = (1 / 2k) ∑_{a ∈ S} a, where S ⊆ ℝ^(2k) is the finite set of distinct row vectors of A. Because all entries are ±1, the inner product of row A(i) with an identical row is 2k, while its inner product with any distinct row is 0 because the two rows agree on k coordinates and disagree on k coordinates. Swapping the order of summation in the dot product ∑_j A(i)_j x_j causes every term with a ≠ A(i) to vanish, leaving only (1 / 2k) * 2k = 1 for each row i.
It suffices to show that the candidate vector x = (1 / 2k) ∑_{a ∈ S} a satisfies ∑_j A(i)_j x_j = 1 for an arbitrary row index i, where S = {A(i') : i' ∈ ι} is the finite set of distinct row vectors.
Using Fintype.ofFinite, we turn the finiteness assumption on ι into a Fintype instance and collect the distinct row vectors into a finite set S = A(ι). We propose the witness x ∈ ℝ^(2k) whose j-th coordinate is x_j = (1 / 2k) ∑_{a ∈ S} a_j. The goal then reduces to fixing an arbitrary row index i and verifying that ∑_j A(i)_j x_j = 1.
uses
Fintype.ofFiniteclassical have : Fintype ι := Fintype.ofFinite ι set S : Finset (Fin (2 * k) → ℝ) := Finset.univ.image A with hS refine ⟨fun j => (1 / (2 * k : ℝ)) * ∑ a ∈ S, a j, fun i => ?_⟩
The dimension 2k is strictly positive, and for any row index i' and coordinate j, the product A(i)_j A(i')_j equals 1 if the two entries agree and -1 if they differ.
Since k ≥ 1, 2k > 0 by positivity. Because every entry of A is 1 or -1, the product A(i)_j A(i')_j is 1 when both entries are 1 or both are -1, and -1 when one is 1 and the other is -1. This matches the conditional expression checking whether A(i)_j = A(i')_j.
have hk' : (0 : ℝ) < 2 * k := by positivity -- inner products of rows have hprod : ∀ i' j, A i j * A i' j = if A i j = A i' j then 1 else -1 := by intro i' j rcases hA i j with h | h <;> rcases hA i' j with h' | h' <;> rw [h, h'] <;> norm_num
For any row vector a ∈ S, the inner product ∑_j A(i)_j a_j equals 2k if a = A(i) and 0 if a ≠ A(i).
Every a ∈ S is the row A(i') for some index i' by Finset.mem_image.mp. Rewriting the product A(i)_j a_j using our agreement formula, the inner product becomes the sum over all j of 1 (where the rows agree) and -1 (where they differ). If A(i') = A(i) (using if_pos), all 2k coordinates agree, so the sum evaluates to 2k • 1 = 2k via Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, and mul_one. If A(i') ≠ A(i) (using if_neg), the two rows differ on exactly k coordinates by assumption (Ne.symm, ne_eq). Splitting the sum into agreements and disagreements with Finset.sum_ite, and using Finset.card_filter_add_card_filter_not to partition the 2k total coordinates, linear arithmetic (omega) determines that the rows must agree on exactly 2k - k = k coordinates. The inner product is therefore k • 1 + k • (-1) = 0.
uses
Finset.mem_image.mp,if_pos,if_true,Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul,mul_one,if_neg,Ne.symm,Finset.sum_ite,Finset.card_filter_add_card_filter_not,ne_eqhave hinner : ∀ a ∈ S, ∑ j, A i j * a j = if a = A i then (2 * k : ℝ) else 0 := by intro a ha obtain ⟨i', -, rfl⟩ := Finset.mem_image.mp ha simp only [hprod] by_cases he : A i' = A i · rw [if_pos he] simp only [he, if_true, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, mul_one] push_cast; ring · rw [if_neg he] have hc := hrows i i' (Ne.symm he) rw [Finset.sum_ite, Finset.sum_const, Finset.sum_const, nsmul_eq_mul, nsmul_eq_mul] have hsplit := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin (2 * k)))) (fun j => A i j = A i' j) rw [Finset.card_univ, Fintype.card_fin] at hsplit have hc' : (Finset.univ.filter fun j => ¬ A i j = A i' j).card = k := by simpa only [ne_eq] using hc rw [hc'] at hsplit ⊢ have : (Finset.univ.filter fun j => A i j = A i' j).card = k := by omega rw [this]; ring
The candidate vector x satisfies ∑_j A(i)_j x_j = 1.
Distributing A(i)_j into the sum defining x_j and swapping the order of summation over coordinates j and rows a ∈ S (using Finset.mul_sum, Finset.sum_comm, and Finset.sum_congr), we express ∑_j A(i)_j x_j as (1 / 2k) ∑_{a ∈ S} (∑_j A(i)_j a_j). Applying our inner product formula, the inner sum equals 2k when a = A(i) and 0 otherwise. Because A(i) ∈ S (by Finset.mem_image_of_mem and Finset.mem_univ), this sum over S collapses via Finset.sum_ite_eq' and if_pos to the single nonzero term 2k. Finally, field simplification evaluates (1 / 2k) * 2k to 1.
uses
Finset.mul_sum,Finset.sum_comm,Finset.sum_congr,Finset.sum_ite_eq',if_pos,Finset.mem_image_of_mem,Finset.mem_univcalc ∑ j, A i j * ((1 / (2 * k : ℝ)) * ∑ a ∈ S, a j) = (1 / (2 * k : ℝ)) * ∑ a ∈ S, ∑ j, A i j * a j := by simp only [Finset.mul_sum] conv_lhs => rw [Finset.sum_comm] exact Finset.sum_congr rfl fun a _ => Finset.sum_congr rfl fun j _ => by ring _ = (1 / (2 * k : ℝ)) * ∑ a ∈ S, (if a = A i then (2 * k : ℝ) else 0) := by rw [Finset.sum_congr rfl hinner] _ = 1 := by rw [Finset.sum_ite_eq' S (A i), if_pos (Finset.mem_image_of_mem A (Finset.mem_univ i))] field_simp
Fintype.ofFinite- Any type with a Finite instance can be endowed with a Fintype structure, providing an explicit finite set of all its elements.
Finset.mem_image.mp- If an element belongs to the image f(s), then it equals f(a) for some a ∈ s.
if_pos- If a condition c holds, the conditional expression if c then t else e evaluates to t.
if_true- A conditional with condition True reduces to its first branch.
Finset.sum_const- The sum of a constant value b over a finite set s equals |s| • b.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin- The finite type Fin n has cardinality n.
nsmul_eq_mul- Natural-number scalar multiplication n • a in a semiring equals the product of the coerced real number n with a.
mul_one- Multiplying any element by 1 yields the element itself.
if_neg- If a condition c does not hold, the conditional expression if c then t else e evaluates to e.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.sum_ite- The sum of a conditional expression over a finite set splits into the sum of the true branch over elements satisfying the condition plus the sum of the false branch over elements satisfying its negation.
Finset.card_filter_add_card_filter_not- The number of elements in a finite set satisfying a predicate plus the number not satisfying it equals the total size of the set.
ne_eq- The relation a ≠ b is definitionally the negation ¬(a = b).
Finset.mul_sum- A scalar factor distributes over a finite sum.
Finset.sum_comm- The order of two finite summations can be swapped.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element.
Finset.sum_ite_eq'- A sum over a finite set s of an indicator function that takes value b(x) when x = a and 0 otherwise evaluates to b(a) if a ∈ s and 0 otherwise.
Finset.mem_image_of_mem- If an element a belongs to s, then f(a) belongs to the image of s under f.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
- The candidate solution x is defined by summing over the set of distinct rows S = A(ι) rather than the index set ι itself, preventing duplicate rows from being overcounted.
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 pm_one_rows_differ_in_half_exists_solution {k : ℕ} (hk : 1 ≤ k) {ι : Type*} [Finite ι] (A : ι → Fin (2 * k) → ℝ) (hA : ∀ i j, A i j = 1 ∨ A i j = -1) (hrows : ∀ i i', A i ≠ A i' → (Finset.univ.filter fun j => A i j ≠ A i' j).card = k) : ∃ x : Fin (2 * k) → ℝ, ∀ i, ∑ j, A i j * x j = 1 := by classical have : Fintype ι := Fintype.ofFinite ι set S : Finset (Fin (2 * k) → ℝ) := Finset.univ.image A with hS refine ⟨fun j => (1 / (2 * k : ℝ)) * ∑ a ∈ S, a j, fun i => ?_⟩ have hk' : (0 : ℝ) < 2 * k := by positivity -- inner products of rows have hprod : ∀ i' j, A i j * A i' j = if A i j = A i' j then 1 else -1 := by intro i' j rcases hA i j with h | h <;> rcases hA i' j with h' | h' <;> rw [h, h'] <;> norm_num have hinner : ∀ a ∈ S, ∑ j, A i j * a j = if a = A i then (2 * k : ℝ) else 0 := by intro a ha obtain ⟨i', -, rfl⟩ := Finset.mem_image.mp ha simp only [hprod] by_cases he : A i' = A i · rw [if_pos he] simp only [he, if_true, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, mul_one] push_cast; ring · rw [if_neg he] have hc := hrows i i' (Ne.symm he) rw [Finset.sum_ite, Finset.sum_const, Finset.sum_const, nsmul_eq_mul, nsmul_eq_mul] have hsplit := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin (2 * k)))) (fun j => A i j = A i' j) rw [Finset.card_univ, Fintype.card_fin] at hsplit have hc' : (Finset.univ.filter fun j => ¬ A i j = A i' j).card = k := by simpa only [ne_eq] using hc rw [hc'] at hsplit ⊢ have : (Finset.univ.filter fun j => A i j = A i' j).card = k := by omega rw [this]; ring calc ∑ j, A i j * ((1 / (2 * k : ℝ)) * ∑ a ∈ S, a j) = (1 / (2 * k : ℝ)) * ∑ a ∈ S, ∑ j, A i j * a j := by simp only [Finset.mul_sum] conv_lhs => rw [Finset.sum_comm] exact Finset.sum_congr rfl fun a _ => Finset.sum_congr rfl fun j _ => by ring _ = (1 / (2 * k : ℝ)) * ∑ a ∈ S, (if a = A i then (2 * k : ℝ) else 0) := by rw [Finset.sum_congr rfl hinner] _ = 1 := by rw [Finset.sum_ite_eq' S (A i), if_pos (Finset.mem_image_of_mem A (Finset.mem_univ i))] field_simp