AFTD Auto-Formalizing Theoretical Domains

lowMul3Target2

def

The target function z_2 : (Fin 6 → Bool) → ZMod 2 of the 3-bit low-half multiplier, given by z_2(x) = x(0)*x(5) + x(1)*x(4) + x(2)*x(3) + x(0)*x(1)*x(3)*x(4).

Statement

def lowMul3Target2 : (Fin 6 → Bool) → ZMod 2
Defined in
arXiv:2611.15992 Section 2 (Targets)
Verified
16 Nov 2026
Axioms
none listed
Used by 2
  • lowMul3TargetsThe set of target bits {z_0, z_1, z_2} of the three-bit low-half multiplier.
  • low_mul3_target2_not_mem_degree_twoThe target function z_2 of the three-bit low-half multiplier does not lie in the space of functions of degree at most 2 over ZMod 2.

Read back from the Lean

The definition lowMul3Target2 is a function mapping a 6-element boolean vector $x : \text{Fin } 6 \to \text{Bool}$ to $\mathbb{Z}/2\mathbb{Z}$. It evaluates the polynomial in $\mathbb{Z}/2\mathbb{Z}$: $$ (x_0 \cdot x_5) + (x_1 \cdot x_4) + (x_2 \cdot x_3) + (x_0 \cdot x_1 \cdot x_3 \cdot x_4) $$ where $x_i$ denotes $1 \in \mathbb{Z}/2\mathbb{Z}$ if $x(i) = \text{true}$ and $0 \in \mathbb{Z}/2\mathbb{Z}$ if $x(i) = \text{false}$, and all operations are addition and multiplication in $\mathbb{Z}/2\mathbb{Z}$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The third output bit z_2 = q_2 + a_0 * a_1 * b_0 * b_1 of the three-bit low-half multiplier. -/
def lowMul3Target2 : (Fin 6 → Bool) → ZMod 2 := (fun x => if x 0 then (1 : ZMod 2) else 0) * (fun x => if x 5 then 1 else 0) +
   (fun x => if x 1 then 1 else 0) * (fun x => if x 4 then 1 else 0) +
   (fun x => if x 2 then 1 else 0) * (fun x => if x 3 then 1 else 0) +
   (fun x => if x 0 then 1 else 0) * (fun x => if x 1 then 1 else 0) *
     (fun x => if x 3 then 1 else 0) * (fun x => if x 4 then 1 else 0)
See it in the graphDiscuss this resultChallenge it