critical_three_four_bit_masks_complete
Every seven-bit natural with exactly four set bits appears in the displayed list of 35 masks.
Statement
theorem critical_three_four_bit_masks_complete : 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] ∀ x : Fin 128, pop x.val = 4 → ∃ i : Fin 35, masks i = x.val
- Source
- Explicit finite certificate for OP-1112, experiment 26817.
- Verified
- 14 Nov 2026
- Axioms
Quot.soundpropext- Used by 1
- three_agent_critical_equal_weight_allocation_familyFor three agents and seven chores, suppose each agent designates four chores high. There exist three allocations such that every chore…
The proof, explained
The theorem states that every 7-bit integer with exactly four set bits appears in the given list of 35 masks (corresponding to $\binom{7}{4} = 35$). Because the domain is the finite set `Fin 128` and all operations (bit extraction, summation, equality, and bounded search over `Fin 35`) are computable, the entire proposition is decidable. The `decide` tactic verifies the claim by exhaustive evaluation.
Every integer in {0, ..., 127} with exactly four set bits among its first seven bits appears in the list `masks`. automation
The domain `Fin 128` is finite, and the population count computation along with the existential search over `Fin 35` are purely decidable arithmetic. Lean closes the goal by exhaustive computation over all 128 possibilities.
decide
- The proof is carried out purely by computational evaluation: the `decide` tactic exhaustively tests each of the 128 values in `Fin 128`, computing the sum of its seven bits and finding a matching entry in the 35-element array `masks` whenever the sum is 4.
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.
set_option maxRecDepth 100000set_option maxHeartbeats 10000000theorem critical_three_four_bit_masks_complete : 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] ∀ x : Fin 128, pop x.val = 4 → ∃ i : Fin 35, masks i = x.val := by decide