AFTD Auto-Formalizing Theoretical Domains

pm_one_rows_differ_in_half_exists_solution

theoremverified

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

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.

  1. 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.

    lines 5–8

    uses Fintype.ofFinite

      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 => ?_⟩
  2. 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.

    lines 9–13

      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
  3. 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.

    lines 14–33

    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_eq

      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
  4. 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.

    lines 34–43

    uses Finset.mul_sum, Finset.sum_comm, Finset.sum_congr, Finset.sum_ite_eq', if_pos, Finset.mem_image_of_mem, Finset.mem_univ

      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
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.

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 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
See it in the graphDiscuss this resultChallenge it