AFTD Auto-Formalizing Theoretical Domains

critical_three_four_bit_masks_complete

theoremverified

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

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.

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

    line 9

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