AFTD Auto-Formalizing Theoretical Domains

low_half_mul3_six_and_upper_bound

theoremverifiedformalization

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

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

    line 4

      revert v k
  2. 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.

    line 5

      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

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