AFTD Auto-Formalizing Theoretical Domains

boolean_top_form_eq_zero_of_not_injective

theoremverifiedformalization

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.

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

    lines 6–7

    uses two_nsmul, Nat.cast_smul_eq_nsmul, zero_smul

      have h : ((2 : ℕ) : ZMod 2) = 0 := by decide
      rw [← two_nsmul, ← Nat.cast_smul_eq_nsmul (R := ZMod 2) 2 x, h, zero_smul]
  2. 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.

    lines 14–22

    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_right

      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)]
  3. 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.

    lines 23–29

    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]
  4. 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.

    lines 37–46

    uses Finset.mem_symmDiff, Finset.mem_singleton, Finset.mem_insert, boolean_top_form_eq_zero_of_not_injective_symmDiff_singleton, add_assoc, add_zero

      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]
  5. 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}.

    lines 53–56

    uses Function.not_injective_iff.mp, Finset.sum_involution

      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))) ?_ ?_ ?_ ?_
  6. 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`.

    lines 57–60

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

    lines 61–66

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

    lines 67–70

    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.

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