AFTD Auto-Formalizing Theoretical Domains

low_mul3_target2_not_mem_degree_two

theoremverified

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

Statement

theorem low_mul3_target2_not_mem_degree_two :
    lowMul3Target2 ∉ degreeSpace (ZMod 2) (Fin 6) 2
Source
arXiv:2611.15992 Section 5 (Proof of Theorem 8)
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • lowMul3Target2The 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) +…
  • degreeSpaceFor a commutative ring K, a finite type ι with decidable equality, and a natural number d, degreeSpace K ι d is the K-submodule of (ι →…
  • monomialFor a natural number s and a finite subset T of Fin s, the monomial associated with T is the function from (Fin s → ZMod 2) to ZMod 2…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

Read back from the Lean

The function lowMul3Target2 : (Fin 6 → Bool) → ZMod 2 does not belong to degreeSpace (ZMod 2) (Fin 6) 2, which is the subspace of functions from Fin 6 → Bool to ZMod 2 of degree at most 2. That is, the function mapping $x$ to $x_0 x_5 + x_1 x_4 + x_2 x_3 + x_0 x_1 x_3 x_4 \pmod 2$ (with Boolean values interpreted as elements of $\mathbb{F}_2$) cannot be represented as an $\mathbb{F}_2$-linear combination of monomials $\prod_{i \in S} x_i$ with $|S| \le 2$.

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 proof defines a linear functional L that sums a Boolean function over the 4-dimensional subcube spanned by coordinates S₄ = {0, 1, 3, 4}. Over ℤ/2ℤ, summing over a 4-dimensional subcube annihilates every monomial of degree at most 2, so by submodule span induction L vanishes on the entire space of functions of degree at most 2. However, evaluating L on the multiplier target function lowMul3Target2 yields 1, because its degree-4 monomial x₀x₁x₃x₄ evaluates to 1 on the subcube while all lower-degree monomials sum to 0. This contradiction (0 = 1) proves that lowMul3Target2 cannot belong to the degree-2 space.

  1. The linear functional L evaluates on any function f as the sum of f over all 16 subcube indicator assignments spanned by S₄ = {0, 1, 3, 4}. automation

    Unfolding the definition of `low_mul3_target2_L_lin` as the sum of coordinate projection linear maps, the simplifier establishes that evaluating L on f yields the sum of f(1_T) over all subsets T ⊆ S₄.

    line 20

    uses low_mul3_target2_L_lin

      simp [low_mul3_target2_L_lin]
  2. For any monomial of degree at most 2, its sum over the subcube S₄ is 0 in ℤ/2ℤ. automation

    Since there are only finitely many subsets U ⊆ {0, …, 5} with |U| ≤ 2 and only 16 subcube indicator inputs, the identity is proved by exhaustive finite computation (`decide`).

    line 25

      decide
  3. The functional L vanishes on all generating monomials of degree at most 2.

    We set up an induction on the submodule span via `Submodule.span_induction`. For the generator case, any generator is a monomial function corresponding to an index set U with |U| ≤ 2. Rewriting with `low_mul3_target2_L_lin_apply` turns L applied to the monomial into its subcube sum, which is 0 by `low_mul3_target2_L_monomial_eq_zero`.

    lines 29–32

    uses Submodule.span_induction, low_mul3_target2_L_lin_apply, low_mul3_target2_L_monomial_eq_zero

      refine Submodule.span_induction (p := fun g _ => low_mul3_target2_L_lin g = 0) ?_ ?_ ?_ ?_ hf
      · rintro g ⟨U, hU, rfl⟩
        rw [low_mul3_target2_L_lin_apply]
        exact low_mul3_target2_L_monomial_eq_zero U hU
  4. The kernel of L is closed under zero, addition, and scalar multiplication, completing the proof that L vanishes on the entire degree-2 space.

    Because L is a linear map, L(0) = 0 by `low_mul3_target2_L_lin.map_zero`. For sums, L(x + y) = L(x) + L(y) = 0 + 0 = 0 by `low_mul3_target2_L_lin.map_add` and `add_zero`. For scalar multiples, L(a • x) = a • L(x) = a • 0 = 0 by `low_mul3_target2_L_lin.map_smul` and `smul_zero`. Hence L vanishes on all of degreeSpace 2.

    lines 33–37

    uses low_mul3_target2_L_lin.map_zero, low_mul3_target2_L_lin.map_add, add_zero, low_mul3_target2_L_lin.map_smul, smul_zero

      · exact low_mul3_target2_L_lin.map_zero
      · intro x y hx hy hx0 hy0
        rw [low_mul3_target2_L_lin.map_add, hx0, hy0, add_zero]
      · intro a x hx hx0
        rw [low_mul3_target2_L_lin.map_smul, hx0, smul_zero]
  5. The linear functional L evaluates to 1 on the target function lowMul3Target2. automation

    Rewriting with `low_mul3_target2_L_lin_apply` expresses L(lowMul3Target2) as the sum of lowMul3Target2 over all 16 subcube assignments. Evaluating this finite sum over ℤ/2ℤ gives 1, checked by `decide`.

    lines 40–41

    uses low_mul3_target2_L_lin_apply

      rw [low_mul3_target2_L_lin_apply]
      decide
  6. Assuming for contradiction that lowMul3Target2 has degree at most 2 implies 0 = 1 in ℤ/2ℤ.

    Assuming lowMul3Target2 belongs to degreeSpace 2, `low_mul3_target2_L_lin_zero_of_mem_degreeSpace` implies L(lowMul3Target2) = 0. But `low_mul3_target2_L_lin_target2` states that L(lowMul3Target2) = 1. Substituting the former into the latter produces 0 = 1.

    lines 46–49

    uses low_mul3_target2_L_lin_zero_of_mem_degreeSpace, low_mul3_target2_L_lin_target2

      intro h
      have h0 := low_mul3_target2_L_lin_zero_of_mem_degreeSpace h
      have h1 := low_mul3_target2_L_lin_target2
      rw [h0] at h1
  7. The equality 0 = 1 is false in ℤ/2ℤ, completing the contradiction. automation

    Moving the false hypothesis 0 = 1 back to the goal with `revert`, `decide` proves that 0 = 1 implies False by finite decidability in ℤ/2ℤ.

    lines 50–51

      revert h1
      decide
add_zero
Adding zero to any element leaves it unchanged: a + 0 = a.
low_mul3_target2_L_lin
The linear functional on Boolean functions from Fin 6 to ZMod 2 defined by summing coordinate projections over the power set of S₄ = {0, 1, 3, 4}.
low_mul3_target2_L_lin_apply
The evaluation of the linear functional low_mul3_target2_L_lin at a function f equals the sum of f evaluated on the indicator assignments of all subsets of S₄.
low_mul3_target2_L_lin.map_add
The linear map low_mul3_target2_L_lin preserves addition: L(x + y) = L(x) + L(y).
low_mul3_target2_L_lin.map_smul
The linear map low_mul3_target2_L_lin preserves scalar multiplication: L(c • x) = c • L(x).
low_mul3_target2_L_lin.map_zero
The linear map low_mul3_target2_L_lin sends the zero function to 0.
low_mul3_target2_L_lin_target2
The linear functional low_mul3_target2_L_lin evaluates to 1 on the target function lowMul3Target2.
low_mul3_target2_L_lin_zero_of_mem_degreeSpace
Any Boolean function lying in the space of functions of degree at most 2 evaluates to 0 under the linear functional low_mul3_target2_L_lin.
low_mul3_target2_L_monomial_eq_zero
For every subset U with at most 2 elements, the sum of the corresponding monomial function over all subsets of S₄ is 0 in ZMod 2.
smul_zero
Scalar multiplication of any scalar by zero yields zero: a • 0 = 0.
Submodule.span_induction
To prove a property holds for all elements of a submodule span, it suffices to prove it for all generators, for zero, and show it is closed under addition and scalar multiplication.

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

open BigOperators/-- The index set of the quartic monomial in `lowMul3Target2`. -/def low_mul3_target2_S4 : Finset (Fin 6) := {0, 1, 3, 4}/-- The indicator assignment of a subset `T ⊆ Fin 6`. -/def low_mul3_target2_indicator (T : Finset (Fin 6)) : Fin 6 → Bool :=  fun i => i ∈ T/-- A multilinear monomial function corresponding to subset `U ⊆ Fin 6`. -/def low_mul3_target2_monomialFn (U : Finset (Fin 6)) : (Fin 6 → Bool) → ZMod 2 :=  fun x => ∏ i ∈ U, if x i = true then 1 else 0/-- The linear functional evaluating a Boolean function on the subcube spanned by `low_mul3_target2_S4`. -/def low_mul3_target2_L_lin : ((Fin 6 → Bool) → ZMod 2) →ₗ[ZMod 2] ZMod 2 :=  ∑ T ∈ low_mul3_target2_S4.powerset, LinearMap.proj (low_mul3_target2_indicator T)theorem low_mul3_target2_L_lin_apply (f : (Fin 6 → Bool) → ZMod 2) :    low_mul3_target2_L_lin f = ∑ T ∈ low_mul3_target2_S4.powerset, f (low_mul3_target2_indicator T) := by  simp [low_mul3_target2_L_lin]theorem low_mul3_target2_L_monomial_eq_zero :    ∀ U : Finset (Fin 6), U.card ≤ 2 →      (∑ T ∈ low_mul3_target2_S4.powerset, low_mul3_target2_monomialFn U (low_mul3_target2_indicator T)) = 0 := by  decidetheorem low_mul3_target2_L_lin_zero_of_mem_degreeSpace {f : (Fin 6 → Bool) → ZMod 2}    (hf : f ∈ degreeSpace (ZMod 2) (Fin 6) 2) : low_mul3_target2_L_lin f = 0 := by  refine Submodule.span_induction (p := fun g _ => low_mul3_target2_L_lin g = 0) ?_ ?_ ?_ ?_ hf  · rintro g ⟨U, hU, rfl⟩    rw [low_mul3_target2_L_lin_apply]    exact low_mul3_target2_L_monomial_eq_zero U hU  · exact low_mul3_target2_L_lin.map_zero  · intro x y hx hy hx0 hy0    rw [low_mul3_target2_L_lin.map_add, hx0, hy0, add_zero]  · intro a x hx hx0    rw [low_mul3_target2_L_lin.map_smul, hx0, smul_zero]theorem low_mul3_target2_L_lin_target2 : low_mul3_target2_L_lin lowMul3Target2 = 1 := by  rw [low_mul3_target2_L_lin_apply]  decide/-- The target output z_2 does not belong to degreeSpace 2 because its algebraic normal form has degree 4. -/theorem low_mul3_target2_not_mem_degree_two :    lowMul3Target2 ∉ degreeSpace (ZMod 2) (Fin 6) 2 := by  intro h  have h0 := low_mul3_target2_L_lin_zero_of_mem_degreeSpace h  have h1 := low_mul3_target2_L_lin_target2  rw [h0] at h1  revert h1  decide
See it in the graphDiscuss this resultChallenge it