AFTD Auto-Formalizing Theoretical Domains

critical_three_canonical_diagonal_coverage

theoremverified

For each pair of listed four-bit masks with sorted two-bit signatures in each of the designated chore groups, one of seven explicitly listed pairs of diagonal triples contains at most one high chore per agent.

Statement

theorem critical_three_canonical_diagonal_coverage :
    let bit : ℕ → ℕ → ℕ := fun x j => x / 2^j % 2
    let pop : ℕ → ℕ := fun x => bit x 0 + bit x 1 + bit x 2 + bit x 3 + bit x 4 + bit x 5 + bit x 6
    let masks : Fin 35 → ℕ := ![15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120]
    let sig : ℕ → ℕ → ℕ → ℕ := fun a b j => bit a j + 2 * bit b j
    let one : ℕ → ℕ → ℕ → ℕ → Prop := fun a x y z => bit a x + bit a y + bit a z ≤ 1
    ∀ a b : Fin 35,
      (pop (masks a) = 4 ∧ pop (masks b) = 4 ∧
       sig (masks a) (masks b) 0 ≤ sig (masks a) (masks b) 1 ∧
       sig (masks a) (masks b) 1 ≤ sig (masks a) (masks b) 2 ∧
       sig (masks a) (masks b) 2 ≤ sig (masks a) (masks b) 3 ∧
       sig (masks a) (masks b) 4 ≤ sig (masks a) (masks b) 5 ∧
       sig (masks a) (masks b) 5 ≤ sig (masks a) (masks b) 6) →
      ((one (masks a) 0 1 4 ∧ one (masks b) 0 2 3) ∨
       (one (masks a) 0 4 5 ∧ one (masks b) 0 2 5) ∨
       (one (masks a) 0 2 5 ∧ one (masks b) 1 4 5) ∨
       (one (masks a) 1 4 5 ∧ one (masks b) 1 4 5) ∨
       (one (masks a) 1 2 5 ∧ one (masks b) 0 3 5) ∨
       (one (masks a) 0 2 4 ∧ one (masks b) 0 1 4) ∨
       (one (masks a) 0 2 6 ∧ one (masks b) 0 4 6))
Source
Explicit finite certificate for OP-1112, experiment 26817.
Verified
14 Nov 2026
Axioms
propext
Used by 1

The proof, explained

The theorem asserts that among all pairs of 4-element subsets of a 7-element chore set (encoded as 7-bit integers of Hamming weight 4) whose joint chore signatures are sorted within groups {0, 1, 2, 3} and {4, 5, 6}, at least one of seven specified pairs of chore triples allocates at most one chore to each agent. The proof proceeds by finite exhaustive verification: after unfolding the definitions of bits, weights, signatures, and triple occupancy, Lean's `decide` tactic checks all 35 × 35 = 1,225 mask pairs by direct computation.

  1. Every pair of masks satisfying the sorted signature and weight conditions satisfies at least one of the seven diagonal triple coverage conditions. automation

    The local definitions (`bit`, `pop`, `masks`, `sig`, and `one`) are unfolded into the goal by `dsimp only`. Because the universal quantification ranges over the finite type `Fin 35 × Fin 35` (a total of 35 × 35 = 1,225 pairs) and each condition is an arithmetic check on small natural numbers, the entire proposition is decidable. The `decide` tactic verifies the claim by exhaustive kernel evaluation over all 1,225 pairs.

    lines 24–25

      dsimp only
      decide

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

set_option maxRecDepth 100000set_option maxHeartbeats 10000000theorem critical_three_canonical_diagonal_coverage :    let bit : ℕ → ℕ → ℕ := fun x j => x / 2^j % 2    let pop : ℕ → ℕ := fun x => bit x 0 + bit x 1 + bit x 2 + bit x 3 + bit x 4 + bit x 5 + bit x 6    let masks : Fin 35 → ℕ := ![15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120]    let sig : ℕ → ℕ → ℕ → ℕ := fun a b j => bit a j + 2 * bit b j    let one : ℕ → ℕ → ℕ → ℕ → Prop := fun a x y z => bit a x + bit a y + bit a z ≤ 1    ∀ a b : Fin 35,      (pop (masks a) = 4 ∧ pop (masks b) = 4 ∧       sig (masks a) (masks b) 0 ≤ sig (masks a) (masks b) 1 ∧       sig (masks a) (masks b) 1 ≤ sig (masks a) (masks b) 2 ∧       sig (masks a) (masks b) 2 ≤ sig (masks a) (masks b) 3 ∧       sig (masks a) (masks b) 4 ≤ sig (masks a) (masks b) 5 ∧       sig (masks a) (masks b) 5 ≤ sig (masks a) (masks b) 6) →      ((one (masks a) 0 1 4 ∧ one (masks b) 0 2 3) ∨       (one (masks a) 0 4 5 ∧ one (masks b) 0 2 5) ∨       (one (masks a) 0 2 5 ∧ one (masks b) 1 4 5) ∨       (one (masks a) 1 4 5 ∧ one (masks b) 1 4 5) ∨       (one (masks a) 1 2 5 ∧ one (masks b) 0 3 5) ∨       (one (masks a) 0 2 4 ∧ one (masks b) 0 1 4) ∨       (one (masks a) 0 2 6 ∧ one (masks b) 0 4 6)) := by  dsimp only  decide
See it in the graphDiscuss this resultChallenge it