boolean_top_form_eq_zero_of_not_injective
For any natural number d, module V over ZMod 2, function p : V → ZMod 2, and tuple h : Fin d → V that is not injective (¬ Function.Injective h), booleanTopForm d p h = 0.
Statement
theorem boolean_top_form_eq_zero_of_not_injective {d : ℕ} {V : Type*} [AddCommGroup V] [Module (ZMod 2) V] (p : V → ZMod 2) (h : Fin d → V) (hinj : ¬ Function.Injective h) : booleanTopForm d p h = 0
- Formalizes
- arXiv:2611.03452 Lemma 2.7 (iii) -- Parity Decision Trees of Depth O(4^d log ||f_hat||_1) for Boolean Functions f of F_2-Degree d
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- booleanTopFormGiven a type V with an additive commutative group structure [AddCommGroup V], a natural number d, a function p : V → ZMod 2, and a tuple h…
Read back from the Lean
For any natural number $d$, any type $V$ equipped with an additive commutative group structure and a $\mathbb{Z}/2\mathbb{Z}$-module structure, any function $p : V \to \mathbb{Z}/2\mathbb{Z}$, and any function $h : \text{Fin } d \to V$: if $h$ is not injective, then $\text{booleanTopForm } d\ p\ h = 0$ 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.
The proof, explained
The boolean top form evaluates a function p at the partial sums ∑_{k ∈ S} h(k) for all subsets S ⊆ Fin d, summing the results in ZMod 2. When h is not injective, there exist distinct indices i ≠ j with h(i) = h(j). We partition the subsets into disjoint pairs via the fixed-point-free involution S ↦ S ∆ {i, j}; because h(i) = h(j) and 2 = 0 in the module, the vector sum is invariant under toggling {i, j}, so the two terms in each pair are equal and cancel out in ZMod 2.
In any module over ZMod 2, every element is self-inverse: x + x = 0.
Since 2 = 0 in ZMod 2 by direct computation, we rewrite x + x as 2 • x using `two_nsmul`, translate the natural-number scalar multiplication to the module action via `Nat.cast_smul_eq_nsmul`, and conclude that 0 • x = 0 using `zero_smul`.
uses
two_nsmul,Nat.cast_smul_eq_nsmul,zero_smulhave h : ((2 : ℕ) : ZMod 2) = 0 := by decide rw [← two_nsmul, ← Nat.cast_smul_eq_nsmul (R := ZMod 2) 2 x, h, zero_smul]
When a ∈ T, toggling a in T via symmetric difference changes the sum of v by adding v a.
If a ∈ T, the symmetric difference T ∆ {a} is the set T with a removed (`T.erase a`). Removing a subtracts v a from the sum over T; because v a is self-inverse (v a + v a = 0), -v a = v a, so subtracting v a is the same as adding v a.
uses
Finset.mem_symmDiff,Finset.mem_singleton,Finset.mem_erase,Finset.sum_erase_eq_sub,sub_eq_add_neg,neg_eq_of_add_eq_zero_rightby_cases ha : a ∈ T · have hset : T ∆ ({a} : Finset (Fin d)) = T.erase a := by ext x simp only [Finset.mem_symmDiff, Finset.mem_singleton, Finset.mem_erase] by_cases hx : x = a · subst hx; simp [ha] · simp [hx] rw [hset, Finset.sum_erase_eq_sub ha, sub_eq_add_neg, neg_eq_of_add_eq_zero_right (hv a)]
When a ∉ T, toggling a in T via symmetric difference changes the sum of v by adding v a.
If a ∉ T, T ∆ {a} is the set obtained by inserting a into T (`insert a T`). The sum over the enlarged set equals v a plus the sum over T, which is the sum over T plus v a by commutativity of addition.
uses
Finset.mem_symmDiff,Finset.mem_singleton,Finset.mem_insert,Finset.sum_insert,add_comm· have hset : T ∆ ({a} : Finset (Fin d)) = insert a T := by ext x simp only [Finset.mem_symmDiff, Finset.mem_singleton, Finset.mem_insert] by_cases hx : x = a · subst hx; simp [ha] · simp [hx] rw [hset, Finset.sum_insert ha, add_comm]
If v i = v j for distinct i ≠ j and all values are self-inverse, summing over S ∆ {i, j} equals summing over S.
We decompose the double toggle S ∆ {i, j} into two successive single toggles (S ∆ {i}) ∆ {j}. Applying the single-element lemma twice adds v i + v j to the sum over S. Since v i = v j and v i is self-inverse, v i + v j = v i + v i = 0, leaving the original sum unchanged.
uses
Finset.mem_symmDiff,Finset.mem_singleton,Finset.mem_insert,boolean_top_form_eq_zero_of_not_injective_symmDiff_singleton,add_assoc,add_zerohave hset : S ∆ ({i, j} : Finset (Fin d)) = (S ∆ ({i} : Finset (Fin d))) ∆ {j} := by ext x simp only [Finset.mem_symmDiff, Finset.mem_singleton, Finset.mem_insert] by_cases hxi : x = i <;> by_cases hxj : x = j <;> simp_all rw [hset, boolean_top_form_eq_zero_of_not_injective_symmDiff_singleton v hv j, boolean_top_form_eq_zero_of_not_injective_symmDiff_singleton v hv i, add_assoc] have hzero : v i + v j = 0 := by rw [← hveq] exact hv i rw [hzero, add_zero]
Set up the pairing on subsets of Fin d via an involution exchanging indices i and j.
Because h is not injective, there exist distinct indices i ≠ j such that h i = h j (`Function.not_injective_iff.mp`). Unfolding the definition of `booleanTopForm`, we express the sum over all subsets of Fin d and apply `Finset.sum_involution` with the involution g(S) = S ∆ {i, j}.
uses
Function.not_injective_iff.mp,Finset.sum_involutionobtain ⟨i, j, hveq, hij⟩ := Function.not_injective_iff.mp hinj unfold booleanTopForm refine Finset.sum_involution (s := Finset.univ) (f := fun S => p (∑ k ∈ S, h k)) (g := fun S _ => S ∆ ({i, j} : Finset (Fin d))) ?_ ?_ ?_ ?_
Paired terms in the sum cancel: p(∑_{k ∈ S} h k) + p(∑_{k ∈ S ∆ {i, j}} h k) = 0.
By the pair-toggling lemma, the vector sum over S ∆ {i, j} equals the vector sum over S. Therefore, the two evaluated terms in ZMod 2 are identical, and any element in ZMod 2 added to itself is zero by `boolean_top_form_eq_zero_of_not_injective_add_self`.
uses
boolean_top_form_eq_zero_of_not_injective_symmDiff_pair,boolean_top_form_eq_zero_of_not_injective_add_self· intro S _ rw [boolean_top_form_eq_zero_of_not_injective_symmDiff_pair h (fun k => boolean_top_form_eq_zero_of_not_injective_add_self (h k)) hij hveq S] exact boolean_top_form_eq_zero_of_not_injective_add_self _
The involution has no fixed points: S ∆ {i, j} ≠ S for every subset S.
Membership in the symmetric difference satisfies i ∈ S ∆ {i, j} ↔ i ∉ S because i is in {i, j}. If S ∆ {i, j} were equal to S, substituting this equality would yield i ∈ S ↔ i ∉ S, which is a propositional contradiction (`tauto`).
uses
Finset.mem_symmDiff· intro S _ _ have key : (i ∈ (S ∆ ({i, j} : Finset (Fin d)))) ↔ ¬ (i ∈ S) := by simp [Finset.mem_symmDiff] intro hEq rw [hEq] at key tauto
The operation g(S) = S ∆ {i, j} maps Finset.univ to itself and is an involution.
Any subset of Fin d trivially belongs to the universe of subsets (`Finset.mem_univ`), and toggling {i, j} twice returns the original set S because symmetric difference with the same set cancels out (`symmDiff_symmDiff_cancel_right`). Hence `Finset.sum_involution` closes the goal.
uses
Finset.mem_univ,symmDiff_symmDiff_cancel_right· intro S _ exact Finset.mem_univ _ · intro S _ exact symmDiff_symmDiff_cancel_right ({i, j} : Finset (Fin d)) S
two_nsmul- In an additive monoid, multiplying an element by the natural number 2 equals adding it to itself: 2 • a = a + a.
Nat.cast_smul_eq_nsmul- In a module over a semiring R, scalar multiplication by the canonical image of n : ℕ in R agrees with the standard n-fold addition.
zero_smul- Scalar multiplication of any vector by the zero scalar gives the zero vector: 0 • m = 0.
Finset.mem_symmDiff- An element belongs to the symmetric difference s ∆ t if and only if it belongs to s but not t, or to t but not s.
Finset.mem_singleton- An element b belongs to the singleton {a} if and only if b = a.
Finset.mem_erase- An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
Finset.sum_erase_eq_sub- Summing a function over a finite set with element a removed equals the total sum minus the value at a.
sub_eq_add_neg- Subtraction in an additive group equals addition of the additive inverse: a - b = a + (-b).
neg_eq_of_add_eq_zero_right- If a + b = 0 in an additive group, then -a = b; when an element is self-inverse (a + a = 0), its negative is itself.
Finset.mem_insert- An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.sum_insert- If a ∉ s, the sum of a function over insert a s equals the value at a plus the sum over s.
add_comm- Addition in an additive commutative magma is commutative: a + b = b + a.
boolean_top_form_eq_zero_of_not_injective_symmDiff_singleton- If each vector v(k) is self-inverse, summing v over the symmetric difference T ∆ {a} equals summing over T plus v(a).
add_assoc- Addition in an additive semigroup is associative: (a + b) + c = a + (b + c).
add_zero- Adding zero to an element leaves it unchanged: a + 0 = a.
Function.not_injective_iff.mp- If a function is not injective, there exist two distinct arguments on which it takes the same value.
Finset.sum_involution- A finite sum vanishes if there is an involution g on the index set such that paired terms sum to zero, g has no fixed points on nonzero terms, and g maps the index set into itself.
boolean_top_form_eq_zero_of_not_injective_symmDiff_pair- If v(i) = v(j) with i ≠ j and all values are self-inverse, summing v over S ∆ {i, j} yields the same sum as summing over S.
boolean_top_form_eq_zero_of_not_injective_add_self- In any module over ZMod 2, every element is self-inverse: x + x = 0.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
symmDiff_symmDiff_cancel_right- Taking symmetric difference with the same set twice is the identity: (b ∆ a) ∆ a = b.
- The set-theoretic identities expressing symmetric difference with singletons or pairs in terms of element insertion, deletion, or successive single-element symmetric differences are verified formally via pointwise membership extensionality and automated boolean case analysis (`ext`, `simp only`, `by_cases`).
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 scoped BigOperators symmDiff/-- In a module over `ZMod 2`, every element is its own negative. -/private lemma boolean_top_form_eq_zero_of_not_injective_add_self {V : Type*} [AddCommGroup V] [Module (ZMod 2) V] (x : V) : x + x = 0 := by have h : ((2 : ℕ) : ZMod 2) = 0 := by decide rw [← two_nsmul, ← Nat.cast_smul_eq_nsmul (R := ZMod 2) 2 x, h, zero_smul]/-- Toggling a single element `a` changes the sum of `v` over a finset by `v a`. -/private lemma boolean_top_form_eq_zero_of_not_injective_symmDiff_singleton {d : ℕ} {V : Type*} [AddCommGroup V] (v : Fin d → V) (hv : ∀ k, v k + v k = 0) (a : Fin d) (T : Finset (Fin d)) : ∑ k ∈ T ∆ ({a} : Finset (Fin d)), v k = ∑ k ∈ T, v k + v a := by by_cases ha : a ∈ T · have hset : T ∆ ({a} : Finset (Fin d)) = T.erase a := by ext x simp only [Finset.mem_symmDiff, Finset.mem_singleton, Finset.mem_erase] by_cases hx : x = a · subst hx; simp [ha] · simp [hx] rw [hset, Finset.sum_erase_eq_sub ha, sub_eq_add_neg, neg_eq_of_add_eq_zero_right (hv a)] · have hset : T ∆ ({a} : Finset (Fin d)) = insert a T := by ext x simp only [Finset.mem_symmDiff, Finset.mem_singleton, Finset.mem_insert] by_cases hx : x = a · subst hx; simp [ha] · simp [hx] rw [hset, Finset.sum_insert ha, add_comm]/-- If `v i = v j` with `i ≠ j` and all values are self-inverse, then summing over `S ∆ {i,j}`gives the same result as summing over `S`. -/private lemma boolean_top_form_eq_zero_of_not_injective_symmDiff_pair {d : ℕ} {V : Type*} [AddCommGroup V] (v : Fin d → V) (hv : ∀ k, v k + v k = 0) {i j : Fin d} (hij : i ≠ j) (hveq : v i = v j) (S : Finset (Fin d)) : ∑ k ∈ S ∆ ({i, j} : Finset (Fin d)), v k = ∑ k ∈ S, v k := by have hset : S ∆ ({i, j} : Finset (Fin d)) = (S ∆ ({i} : Finset (Fin d))) ∆ {j} := by ext x simp only [Finset.mem_symmDiff, Finset.mem_singleton, Finset.mem_insert] by_cases hxi : x = i <;> by_cases hxj : x = j <;> simp_all rw [hset, boolean_top_form_eq_zero_of_not_injective_symmDiff_singleton v hv j, boolean_top_form_eq_zero_of_not_injective_symmDiff_singleton v hv i, add_assoc] have hzero : v i + v j = 0 := by rw [← hveq] exact hv i rw [hzero, add_zero]/-- The top form vanishes on any tuple with repeated vectors. -/theorem boolean_top_form_eq_zero_of_not_injective {d : ℕ} {V : Type*} [AddCommGroup V] [Module (ZMod 2) V] (p : V → ZMod 2) (h : Fin d → V) (hinj : ¬ Function.Injective h) : booleanTopForm d p h = 0 := by obtain ⟨i, j, hveq, hij⟩ := Function.not_injective_iff.mp hinj unfold booleanTopForm refine Finset.sum_involution (s := Finset.univ) (f := fun S => p (∑ k ∈ S, h k)) (g := fun S _ => S ∆ ({i, j} : Finset (Fin d))) ?_ ?_ ?_ ?_ · intro S _ rw [boolean_top_form_eq_zero_of_not_injective_symmDiff_pair h (fun k => boolean_top_form_eq_zero_of_not_injective_add_self (h k)) hij hveq S] exact boolean_top_form_eq_zero_of_not_injective_add_self _ · intro S _ _ have key : (i ∈ (S ∆ ({i, j} : Finset (Fin d)))) ↔ ¬ (i ∈ S) := by simp [Finset.mem_symmDiff] intro hEq rw [hEq] at key tauto · intro S _ exact Finset.mem_univ _ · intro S _ exact symmDiff_symmDiff_cancel_right ({i, j} : Finset (Fin d)) S