cross_pair_orientation_capacity
A two-row grid with 2s−1 columns cannot orient all its entries so that each row has at most one entry of the first orientation and all but at most s−1 columns have at most one entry of the second orientation, for s at least three.
Statement
theorem cross_pair_orientation_capacity (s : ℕ) (hs : 3 ≤ s) (P : Fin 2 → Fin (2 * s - 1) → Bool) (T : Finset (Fin (2 * s - 1))) (hT : T.card ≤ s - 1) (hrow : ∀ i, (Finset.univ.filter fun j => P i j = true).card ≤ 1) (hcol : ∀ j, j ∉ T → (Finset.univ.filter fun i => P i j = false).card ≤ 1) : False
- Source
- Cross-arc counting reduction in the general minimum-counterexample route to OP-110; experiments 12590 and 12591.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof proceeds by double-counting the total number of cells assigned the first orientation (true) in the 2 × (2s - 1) grid. Summing along the two rows shows there are at most 2 such cells, as each row contains at most 1. On the other hand, each column outside the exceptional set T has at most one cell with the second orientation (false), forcing it to contain at least one cell with the first orientation; since there are at least (2s - 1) - (s - 1) = s such columns, the total number of true cells must be at least s. This gives s ≤ 2, which contradicts s ≥ 3.
Let total denote the number of cells in the 2 × (2s - 1) grid assigned the value true.
We enable classical reasoning and define total as the cardinality of the set of grid coordinates (i, j) ∈ Fin 2 × Fin (2s - 1) where P(i, j) is true.
classical let total : ℕ := (Finset.univ.filter (fun p : Fin 2 × Fin (2 * s - 1) => P p.1 p.2 = true)).card
The total number of true cells equals the sum over all rows of the number of true cells in each row.
By expressing the grid as the Cartesian product of the row and column sets, rewriting the filtered set's cardinality as a sum of indicators, using Fubini's theorem to split the product sum into an iterated sum, and rewriting each inner sum back as the cardinality of row i's true cells, we obtain total = ∑ i, #{j | P(i, j) = true}.
uses
Finset.card_filter,Finset.sum_product,Finset.sum_congrhave htotal_row : total = ∑ i : Fin 2, (Finset.univ.filter (fun j => P i j = true)).card := by dsimp [total] rw [show (Finset.univ : Finset (Fin 2 × Fin (2 * s - 1))) = (Finset.univ : Finset (Fin 2)) ×ˢ (Finset.univ : Finset (Fin (2 * s - 1))) by simp] rw [Finset.card_filter] rw [Finset.sum_product] apply Finset.sum_congr rfl intro i hi rw [← Finset.card_filter]
The total number of true cells equals the sum over all columns of the number of true cells in each column.
Similarly, rewriting the total count as a sum over the product set, swapping the order of summation using the commutativity of finite sums, and converting the inner sum back to a set cardinality yields total = ∑ j, #{i | P(i, j) = true}.
uses
Finset.card_filter,Finset.sum_product,Finset.sum_comm,Finset.sum_congrhave htotal_col : total = ∑ j : Fin (2 * s - 1), (Finset.univ.filter (fun i : Fin 2 => P i j = true)).card := by dsimp [total] rw [show (Finset.univ : Finset (Fin 2 × Fin (2 * s - 1))) = (Finset.univ : Finset (Fin 2)) ×ˢ (Finset.univ : Finset (Fin (2 * s - 1))) by simp] rw [Finset.card_filter] rw [Finset.sum_product] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro j hj rw [← Finset.card_filter]
The total number of true cells is at most 2.
By the row-sum decomposition, the total is the sum over the 2 rows of their true counts. Since each row contains at most 1 true cell by assumption, this sum is bounded by 1 + 1 = 2.
uses
Finset.sum_le_sumhave htotal_le : total ≤ 2 := by rw [htotal_row] calc (∑ i : Fin 2, (Finset.univ.filter fun j => P i j = true).card) ≤ ∑ i : Fin 2, 1 := by apply Finset.sum_le_sum intro i hi exact hrow i _ = 2 := by simp
There are at least s columns outside the exceptional set T.
The total number of columns is 2s - 1 and |T| ≤ s - 1. The size of the complement univ \\ T is (2s - 1) - |T|, which is at least (2s - 1) - (s - 1) = s by linear arithmetic.
uses
Finset.card_sdiffhave hout_card : s ≤ (Finset.univ \ T).card := by rw [Finset.card_sdiff] simp omega
Every column outside T contains at least one true cell.
In any column j, the 2 entries are partitioned into those where P(i, j) = true and those where P(i, j) = false, so their counts sum to the row size 2. When j ∉ T, the column has at most 1 false cell, which leaves at least 2 - 1 = 1 true cell.
uses
Finset.card_filter_add_card_filter_not,Fintype.card_finhave htrue_ge_one : ∀ j, j ∉ T → 1 ≤ (Finset.univ.filter fun i : Fin 2 => P i j = true).card := by intro j hj have hfalse := hcol j hj have hpart : (Finset.univ.filter (fun i : Fin 2 => P i j = true)).card + (Finset.univ.filter (fun i : Fin 2 => P i j = false)).card = 2 := by have h := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin 2))) (p := fun i => P i j = true) simpa [Fintype.card_fin] using h omega
The sum of true cell counts over columns outside T is at least |univ \\ T|.
Since each column outside T has at least 1 true cell, summing these counts over the set univ \\ T yields at least 1 · |univ \\ T| = |univ \\ T|.
uses
Finset.card_nsmul_le_sumhave hsum_out_ge : (Finset.univ \ T).card ≤ ∑ j ∈ (Finset.univ \ T), (Finset.univ.filter fun i : Fin 2 => P i j = true).card := by simpa using Finset.card_nsmul_le_sum (s := (Finset.univ \ T)) (f := fun j => (Finset.univ.filter fun i : Fin 2 => P i j = true).card) (n := 1) (by intro j hj exact htrue_ge_one j (by simpa using hj))
The sum of true cell counts over columns outside T is at most the sum over all columns.
Because univ \\ T is a subset of all columns and all summands are non-negative, the partial sum is bounded above by the full sum.
uses
Finset.sum_le_sum_of_subsethave hsum_le_col : (∑ j ∈ (Finset.univ \ T), (Finset.univ.filter fun i : Fin 2 => P i j = true).card) ≤ ∑ j : Fin (2 * s - 1), (Finset.univ.filter fun i : Fin 2 => P i j = true).card := by exact Finset.sum_le_sum_of_subset (by simp)
The total number of true cells is at least s.
By the column-sum decomposition, total equals the sum over all columns. Combining s ≤ |univ \\ T|, |univ \\ T| ≤ ∑_{j ∉ T} #{true cells in column j}, and the inclusion inequality by transitivity gives s ≤ total.
uses
le_transhave htotal_ge : s ≤ total := by rw [htotal_col] exact le_trans hout_card (le_trans hsum_out_ge hsum_le_col)
A contradiction is derived, completing the proof.
We have established both total ≤ 2 and s ≤ total, which forces s ≤ 2. This contradicts the hypothesis 3 ≤ s by linear integer arithmetic.
omega
Finset.card_filter- The cardinality of a filtered subset {x ∈ s | p x} equals the sum over s of the indicator of p (1 if p x holds, 0 otherwise).
Finset.sum_product- A double sum over the Cartesian product s ×ˢ t of two finite sets equals an iterated sum first over s and then over t.
Finset.sum_congr- Two sums over finite sets are equal if their index sets are equal and their summands agree on all elements.
Finset.sum_comm- The order of summation in a double sum over two finite sets can be exchanged.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set s, then the sum of f over s is at most the sum of g over s.
Finset.card_sdiff- The cardinality of a set difference t \\ s equals |t| - |s ∩ t|.
Finset.card_filter_add_card_filter_not- For any predicate on a finite set s, the number of elements satisfying the predicate plus the number satisfying its negation equals |s|.
Fintype.card_fin- The standard finite set Fin n has cardinality n.
Finset.card_nsmul_le_sum- If every term in a sum over a finite set s is at least n, then the sum is at least |s| · n.
Finset.sum_le_sum_of_subset- The sum of non-negative elements over a subset s ⊆ t is at most the sum over the entire set t.
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
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_capacity (s : ℕ) (hs : 3 ≤ s) (P : Fin 2 → Fin (2 * s - 1) → Bool) (T : Finset (Fin (2 * s - 1))) (hT : T.card ≤ s - 1) (hrow : ∀ i, (Finset.univ.filter fun j => P i j = true).card ≤ 1) (hcol : ∀ j, j ∉ T → (Finset.univ.filter fun i => P i j = false).card ≤ 1) : False := by classical let total : ℕ := (Finset.univ.filter (fun p : Fin 2 × Fin (2 * s - 1) => P p.1 p.2 = true)).card have htotal_row : total = ∑ i : Fin 2, (Finset.univ.filter (fun j => P i j = true)).card := by dsimp [total] rw [show (Finset.univ : Finset (Fin 2 × Fin (2 * s - 1))) = (Finset.univ : Finset (Fin 2)) ×ˢ (Finset.univ : Finset (Fin (2 * s - 1))) by simp] rw [Finset.card_filter] rw [Finset.sum_product] apply Finset.sum_congr rfl intro i hi rw [← Finset.card_filter] have htotal_col : total = ∑ j : Fin (2 * s - 1), (Finset.univ.filter (fun i : Fin 2 => P i j = true)).card := by dsimp [total] rw [show (Finset.univ : Finset (Fin 2 × Fin (2 * s - 1))) = (Finset.univ : Finset (Fin 2)) ×ˢ (Finset.univ : Finset (Fin (2 * s - 1))) by simp] rw [Finset.card_filter] rw [Finset.sum_product] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro j hj rw [← Finset.card_filter] have htotal_le : total ≤ 2 := by rw [htotal_row] calc (∑ i : Fin 2, (Finset.univ.filter fun j => P i j = true).card) ≤ ∑ i : Fin 2, 1 := by apply Finset.sum_le_sum intro i hi exact hrow i _ = 2 := by simp have hout_card : s ≤ (Finset.univ \ T).card := by rw [Finset.card_sdiff] simp omega have htrue_ge_one : ∀ j, j ∉ T → 1 ≤ (Finset.univ.filter fun i : Fin 2 => P i j = true).card := by intro j hj have hfalse := hcol j hj have hpart : (Finset.univ.filter (fun i : Fin 2 => P i j = true)).card + (Finset.univ.filter (fun i : Fin 2 => P i j = false)).card = 2 := by have h := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin 2))) (p := fun i => P i j = true) simpa [Fintype.card_fin] using h omega have hsum_out_ge : (Finset.univ \ T).card ≤ ∑ j ∈ (Finset.univ \ T), (Finset.univ.filter fun i : Fin 2 => P i j = true).card := by simpa using Finset.card_nsmul_le_sum (s := (Finset.univ \ T)) (f := fun j => (Finset.univ.filter fun i : Fin 2 => P i j = true).card) (n := 1) (by intro j hj exact htrue_ge_one j (by simpa using hj)) have hsum_le_col : (∑ j ∈ (Finset.univ \ T), (Finset.univ.filter fun i : Fin 2 => P i j = true).card) ≤ ∑ j : Fin (2 * s - 1), (Finset.univ.filter fun i : Fin 2 => P i j = true).card := by exact Finset.sum_le_sum_of_subset (by simp) have htotal_ge : s ≤ total := by rw [htotal_col] exact le_trans hout_card (le_trans hsum_out_ge hsum_le_col) omega