low_mul3_target2_not_mem_degree_two
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.
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₄.
uses
low_mul3_target2_L_linsimp [low_mul3_target2_L_lin]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`).
decideThe 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`.
uses
Submodule.span_induction,low_mul3_target2_L_lin_apply,low_mul3_target2_L_monomial_eq_zerorefine 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
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.
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]
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`.
uses
low_mul3_target2_L_lin_applyrw [low_mul3_target2_L_lin_apply] decide
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.
uses
low_mul3_target2_L_lin_zero_of_mem_degreeSpace,low_mul3_target2_L_lin_target2intro 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
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ℤ.
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.
- The subcube summation functional corresponds to the 4th-order Boolean derivative in the directions of S₄ = {0, 1, 3, 4}, which extracts the coefficient of the quartic monomial x₀x₁x₃x₄ in the algebraic normal form.
- The tactic `decide` is used to verify finite combinatorial evaluations over 𝔽₂ by exhaustive evaluation: checking that all monomials of degree at most 2 vanish on the subcube sum, computing the sum of the target function to obtain 1, and deriving False from 0 = 1.
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.
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