low_half_mul3_six_and_upper_bound
For every input vector v : Fin 6 → ZMod 2 and index k : Fin 3, the k-th output of the explicit six-AND circuit low_half_mul3_six_and_circuit v k equals the k-th bit low_half_mul3_bit k v of the three-bit low-half multiplier modulo 8.
Statement
theorem low_half_mul3_six_and_upper_bound (v : Fin 6 → ZMod 2) (k : Fin 3) :
low_half_mul3_six_and_circuit v k = low_half_mul3_bit k v- Formalizes
- arXiv:2611.15992 Section 3
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- low_half_mul3_bitThe function taking index k : Fin 3 and vector v : Fin 6 → ZMod 2 and returning the element of ZMod 2 obtained by computing the product (a…
- low_half_mul3_six_and_circuitThe function taking vector v : Fin 6 → ZMod 2 and index k : Fin 3 and returning an element of ZMod 2 computed from six AND gates over ZMod…
- low_half_mul3_gate5_expansionExpansion of the sixth AND gate g_5 over GF(2): (g_1 + a_1)(g_2 + b_1) equals a_0 a_1 b_0 b_1 + g_1 + g_2 + a_1 b_1.
Read back from the Lean
For every 6-bit vector v : Fin 6 → ZMod 2 and every index k : Fin 3, the value computed by low_half_mul3_six_and_circuit v k equals low_half_mul3_bit k v. In other words, the circuit correctly computes each of the three least significant bits (indexed by k ∈ {0, 1, 2}) of the product modulo 8 of the two 3-bit integers whose binary representations are given by the first three and last three bits of v.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem states that an explicit circuit using six AND gates correctly computes the lower three bits of the product of two 3-bit integers. Because the input space and index set are small and finite (consisting of 2⁶ × 3 = 192 total cases), the proof moves the hypotheses back into a universal quantifier and verifies the identity by exhaustive computation via `decide`.
The goal is restated as a universal claim over all input vectors v and bit indices k.
Reverting `v` and `k` transforms the goal into `∀ (v : Fin 6 → ZMod 2) (k : Fin 3), low_half_mul3_six_and_circuit v k = low_half_mul3_bit k v`, framing it as a closed decidable proposition over finite types.
revert v k
The six-AND circuit output matches the three-bit low-half multiplier bit for all inputs and indices. automation
Since the function type `Fin 6 → ZMod 2` has only 2⁶ = 64 possible inputs and `Fin 3` has 3 elements, there are only 192 test cases in total. The `decide` tactic evaluates and verifies the equality by exhaustive finite computation.
decide
- The proof relies entirely on exhaustive finite verification via `decide` over all 192 cases (2⁶ = 64 input vectors times 3 output bit indices), with no intermediate algebraic lemmas.
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.
/-- Six-AND upper bound for the 3-bit low-half multiplier (PR-1225). -/theorem low_half_mul3_six_and_upper_bound (v : Fin 6 → ZMod 2) (k : Fin 3) : low_half_mul3_six_and_circuit v k = low_half_mul3_bit k v := by revert v k decide