AFTD Auto-Formalizing Theoretical Domains

cross_pair_orientation_sum_capacity

theoremverified

A two-row, 2s−1-column orientation table cannot satisfy the displayed row and column capacity bounds when s is at least three.

Statement

theorem cross_pair_orientation_sum_capacity (s : ℕ) (hs : 3 ≤ s)
    (P : Fin 2 → Fin (2*s-1) → Prop) [∀ i j, Decidable (P i j)]
    (T : Finset (Fin (2*s-1))) (hT : T.card ≤ s-1)
    (hrow : ∀ i, (∑ j, if P i j then 1 else 0) ≤ 1)
    (hcol : ∀ j, (∑ i, if P i j then 0 else 1) ≤ 1 + if j ∈ T then 1 else 0) : False
Source
Auxiliary-graph transfer and counting steps for the OP-110 campaign.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof uses double counting on the $2 \times (2s-1)$ table. Summing the row bounds shows that the total number of true entries is at most 2, while summing the column bounds shows that the total number of false entries is at most $(2s-1) + |T| \le 3s - 2$. Because every cell is either true or false, the sum of the two counts must equal the total number of cells, $2(2s-1) = 4s-2$. Combining these inequalities yields $4s - 2 \le 3s$, which forces $s \le 2$, contradicting $s \ge 3$.

  1. The total number of true entries across all rows is at most 2.

    Summing the row hypothesis `hrow i` (each row contains at most one true entry) over both rows $i \in \text{Fin } 2$ using `Finset.sum_le_sum` gives a total of at most $1 + 1 = 2$.

    lines 6–9

    uses Finset.sum_le_sum

      classical
      have hrows : (∑ i, ∑ j, if P i j then 1 else 0) ≤ 2 := by
        have h := Finset.sum_le_sum (s := Finset.univ) (fun i _ => hrow i)
        simpa using h
  2. The total number of false entries across all columns is at most $(2s - 1) + |T|$.

    Summing the column hypothesis `hcol j` over all $2s - 1$ columns using `Finset.sum_le_sum` and distributing the sum with `Finset.sum_add_distrib` bounds the total count of false entries by $\sum_j 1 + \sum_j [j \in T] = (2s - 1) + |T|$.

    lines 10–12

    uses Finset.sum_le_sum, Finset.sum_add_distrib

      have hcols : (∑ j, ∑ i, if P i j then 0 else 1) ≤ 2*s-1 + T.card := by
        have h := Finset.sum_le_sum (s := Finset.univ) (fun j _ => hcol j)
        simpa [Finset.sum_add_distrib] using h
  3. The sum of the total number of true entries and the total number of false entries equals $2(2s - 1)$, the total number of cells in the table.

    Swapping the summation order of the false entries with `Finset.sum_comm` and combining the two double sums termwise with `Finset.sum_add_distrib` yields the sum over all $(i, j)$ of $([P(i, j)] + [\neg P(i, j)])$. Since every cell is either true or false, each summand is identically 1. Congruence of sums (`Finset.sum_congr`) reduces this to summing 1 over all $2 \times (2s - 1)$ cells, which evaluates to $2(2s - 1)$.

    lines 13–26

    uses Finset.sum_comm, Finset.sum_add_distrib, Finset.sum_congr

      have htotal : (∑ i, ∑ j, if P i j then 1 else 0) +
          (∑ j, ∑ i, if P i j then 0 else 1) = 2 * (2*s-1) := by
        rw [Finset.sum_comm (s := Finset.univ) (t := Finset.univ) (f := fun j i => if P i j then 0 else 1)]
        calc
          _ = ∑ i : Fin 2, ∑ j : Fin (2*s-1),
              ((if P i j then 1 else 0) + (if P i j then 0 else 1)) := by
                simp only [Finset.sum_add_distrib]
          _ = ∑ _i : Fin 2, ∑ _j : Fin (2*s-1), (1 : ℕ) := by
                apply Finset.sum_congr rfl
                intro i hi
                apply Finset.sum_congr rfl
                intro j hj
                split_ifs <;> omega
          _ = 2 * (2*s-1) := by simp
  4. False (a contradiction is reached).

    Linear arithmetic (`omega`) deduces a contradiction from the established relations: the total number of cells is bounded by the true entries plus the false entries, giving $2(2s - 1) \le 2 + (2s - 1) + |T|$. Since $|T| \le s - 1$, this implies $4s - 2 \le 3s$, so $s \le 2$, contradicting the assumption $s \ge 3$.

    line 27

      omega
Finset.sum_le_sum
If $f(x) \le g(x)$ for all $x$ in a finite set $s$, then $\sum_{x \in s} f(x) \le \sum_{x \in s} g(x)$.
Finset.sum_add_distrib
The sum of a sum over a finite set distributes as the sum of the two parts: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
Finset.sum_comm
The order of summation in a finite double sum can be swapped: $\sum_{x \in s} \sum_{y \in t} f(x, y) = \sum_{y \in t} \sum_{x \in s} f(x, y)$.
Finset.sum_congr
If two finite index sets are equal and their summands agree on every element, then their sums are equal.

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 cross_pair_orientation_sum_capacity (s : ℕ) (hs : 3 ≤ s)    (P : Fin 2 → Fin (2*s-1) → Prop) [∀ i j, Decidable (P i j)]    (T : Finset (Fin (2*s-1))) (hT : T.card ≤ s-1)    (hrow : ∀ i, (∑ j, if P i j then 1 else 0) ≤ 1)    (hcol : ∀ j, (∑ i, if P i j then 0 else 1) ≤ 1 + if j ∈ T then 1 else 0) : False := by  classical  have hrows : (∑ i, ∑ j, if P i j then 1 else 0) ≤ 2 := by    have h := Finset.sum_le_sum (s := Finset.univ) (fun i _ => hrow i)    simpa using h  have hcols : (∑ j, ∑ i, if P i j then 0 else 1) ≤ 2*s-1 + T.card := by    have h := Finset.sum_le_sum (s := Finset.univ) (fun j _ => hcol j)    simpa [Finset.sum_add_distrib] using h  have htotal : (∑ i, ∑ j, if P i j then 1 else 0) +      (∑ j, ∑ i, if P i j then 0 else 1) = 2 * (2*s-1) := by    rw [Finset.sum_comm (s := Finset.univ) (t := Finset.univ) (f := fun j i => if P i j then 0 else 1)]    calc      _ = ∑ i : Fin 2, ∑ j : Fin (2*s-1),          ((if P i j then 1 else 0) + (if P i j then 0 else 1)) := by            simp only [Finset.sum_add_distrib]      _ = ∑ _i : Fin 2, ∑ _j : Fin (2*s-1), (1 : ℕ) := by            apply Finset.sum_congr rfl            intro i hi            apply Finset.sum_congr rfl            intro j hj            split_ifs <;> omega      _ = 2 * (2*s-1) := by simp  omega
See it in the graphDiscuss this resultChallenge it