cross_pair_orientation_sum_capacity
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$.
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$.
uses
Finset.sum_le_sumclassical 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
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|$.
uses
Finset.sum_le_sum,Finset.sum_add_distribhave 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
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)$.
uses
Finset.sum_comm,Finset.sum_add_distrib,Finset.sum_congrhave 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
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$.
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
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 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