AFTD Auto-Formalizing Theoretical Domains

cross_pair_orientation_capacity

theoremverified

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.

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

    lines 2–3

      classical
      let total : ℕ := (Finset.univ.filter (fun p : Fin 2 × Fin (2 * s - 1) => P p.1 p.2 = true)).card
  2. 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}.

    lines 4–12

    uses Finset.card_filter, Finset.sum_product, Finset.sum_congr

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

    lines 13–23

    uses Finset.card_filter, Finset.sum_product, Finset.sum_comm, Finset.sum_congr

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

    lines 24–31

    uses Finset.sum_le_sum

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

    lines 32–35

    uses Finset.card_sdiff

      have hout_card : s ≤ (Finset.univ \ T).card := by
        rw [Finset.card_sdiff]
        simp
        omega
  6. 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.

    lines 36–44

    uses Finset.card_filter_add_card_filter_not, Fintype.card_fin

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

    lines 45–51

    uses Finset.card_nsmul_le_sum

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

    lines 52–54

    uses Finset.sum_le_sum_of_subset

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

    lines 55–57

    uses le_trans

      have htotal_ge : s ≤ total := by
        rw [htotal_col]
        exact le_trans hout_card (le_trans hsum_out_ge hsum_le_col)
  10. 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.

    line 58

      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

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