AFTD Auto-Formalizing Theoretical Domains

boolean_derivative_has_degree_le_pred

theoremverified

The directional derivative of any Boolean function of algebraic degree at most d + 1 along any vector v has algebraic degree at most d.

Statement

theorem boolean_derivative_has_degree_le_pred {n : ℕ} (f : (Fin n → ZMod 2) → ZMod 2) (v : Fin n → ZMod 2) {d : ℕ} (hf : has_degree_le f (d + 1)) : has_degree_le (boolean_derivative v f) d
Source
step towards boolean_derivative_bent_dim_eight_degree_le
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • boolean_derivativeThe directional derivative of a Boolean function f on (Fin n → ZMod 2) along a vector v is the function x ↦ f(x) + f(x + v).
  • has_degree_leA Boolean function f has algebraic degree at most d if it can be represented as a sum of monomials of degree at most d over ZMod 2.

The proof, explained

The proof decomposes a Boolean function f into its algebraic normal form as a sum of monomials of degree at most d + 1. For each monomial, the directional derivative along v expands via `Finset.prod_add`, and the top-degree term cancels in characteristic 2, leaving only proper sub-monomials of degree at most d. Exchanging the order of summation groups the resulting terms into a new polynomial whose non-zero coefficients correspond to subsets of size at most d, proving that the directional derivative has algebraic degree at most d.

  1. For any c, m ∈ ℤ/2ℤ, the product c * m equals m if c = 1, and 0 otherwise.

    We perform a case analysis on whether c = 1. If c = 1, the product reduces to 1 * m = m. If c ≠ 1, since the only elements of ℤ/2ℤ are 0 and 1, c must be 0, so the product simplifies to 0 * m = 0.

    lines 3–9

    uses if_pos, one_mul, if_neg, zero_mul

      by_cases h : c = 1
      · rw [h, if_pos rfl, one_mul]
      · rw [if_neg h]
        have : c = 0 := by
          revert c h
          decide
        rw [this, zero_mul]
  2. For any subset S and vectors x, v, the sum ∏_{i ∈ S} x i + ∏_{i ∈ S} (x i + v i) equals the sum of (∏_{i ∈ S \\ T} v i) * (∏_{i ∈ T} x i) over all proper subsets T ⊊ S.

    Expanding ∏_{i ∈ S} (x i + v i) via `Finset.prod_add` gives a sum over all subsets T ⊆ S. Separating out the top term T = S yields ∏_{i ∈ S} x i. In characteristic 2, adding ∏_{i ∈ S} x i cancels this top term (as a + a = 0), leaving only the terms for proper subsets T ∈ powerset(S) \\ {S}.

    lines 14–23

    uses Finset.prod_add, Finset.mem_powerset_self, Finset.add_sum_erase, Finset.sdiff_self, Finset.prod_empty, mul_one, add_assoc, CharTwo.add_self_eq_zero, zero_add, Finset.sum_congr, mul_comm

      have hp := Finset.prod_add x v S
      rw [hp]
      have hmem : S ∈ S.powerset := Finset.mem_powerset_self S
      rw [← Finset.add_sum_erase S.powerset _ hmem]
      have hS : (∏ i ∈ S, x i) * ∏ i ∈ S \ S, v i = ∏ i ∈ S, x i := by
        rw [Finset.sdiff_self, Finset.prod_empty, mul_one]
      rw [hS, ← add_assoc, CharTwo.add_self_eq_zero, zero_add]
      apply Finset.sum_congr rfl
      intro T _
      rw [mul_comm]
  3. To bound the algebraic degree of the directional derivative, it suffices to construct a family c' of subsets of size at most d whose sum of monomials represents the derivative.

    Unpacking the hypothesis that f has degree at most d + 1 yields a representation of f as a sum of monomials over a family c of subsets of size at most d + 1. For every subset T, we define coeff(T) as the sum over S ∈ c containing T properly of ∏_{i ∈ S \\ T} v i. We let c' be the set of T with coeff(T) = 1, and reduce the goal to showing |T| ≤ d for all T ∈ c' and that the derivative equals the sum of monomials over c'.

    lines 27–33

      rcases hf with ⟨c, hc_card, hc_sum⟩
      let coeff : Finset (Fin n) → ZMod 2 := fun T =>
        ∑ S ∈ c, if T ∈ S.powerset.erase S then (∏ i ∈ S \ T, v i) else 0
      let c' : Finset (Finset (Fin n)) :=
        (Finset.univ : Finset (Finset (Fin n))).filter (fun T => coeff T = 1)
      use c'
      constructor
  4. Every monomial T ∈ c' has cardinality at most d.

    For T ∈ c', coeff(T) = 1 ≠ 0. If for contradiction |T| > d, then for any S ∈ c, since |S| ≤ d + 1, any proper subset T ⊊ S would force |T| < |S| ≤ d + 1, hence |T| ≤ d, a contradiction. Thus T is never a proper subset of any S ∈ c. Consequently, all terms in the sum defining coeff(T) vanish, giving coeff(T) = 0, which contradicts coeff(T) ≠ 0.

    lines 34–55

    uses Finset.mem_filter, Finset.mem_erase, Finset.mem_powerset, Finset.ssubset_iff_subset_ne, Finset.card_lt_card, Finset.sum_eq_zero, if_neg

      · intro T hT
        rw [Finset.mem_filter] at hT
        have hT_coeff : coeff T = 1 := hT.2
        have hT_ne_zero : coeff T ≠ 0 := by
          rw [hT_coeff]
          decide
        by_contra h_not
        have h_not_in : ∀ S ∈ c, T ∉ S.powerset.erase S := by
          intro S hS h_in
          have h_card_S := hc_card S hS
          rw [Finset.mem_erase, Finset.mem_powerset] at h_in
          have h_ssubset : T ⊂ S := by
            rw [Finset.ssubset_iff_subset_ne]
            exact ⟨h_in.2, h_in.1⟩
          have h_card_lt := Finset.card_lt_card h_ssubset
          omega
        have h_zero : coeff T = 0 := by
          dsimp [coeff]
          apply Finset.sum_eq_zero
          intro S hS
          rw [if_neg (h_not_in S hS)]
        exact hT_ne_zero h_zero
  5. The directional derivative D_v f(x) can be rewritten as the sum over S ∈ c of the monomial differences ∏_{i ∈ S} x i + ∏_{i ∈ S} (x i + v i).

    By definition, D_v f(x) = f(x) + f(x + v). Substituting the monomial expansion of f at x and x + v and combining the two summations over S ∈ c into a single sum yields the claim.

    lines 56–63

    uses Finset.sum_add_distrib.symm

      · intro x
        dsimp [boolean_derivative]
        rw [hc_sum x, hc_sum (x + v)]
        have h_sum_add : (∑ S ∈ c, ∏ i ∈ S, x i) + (∑ S ∈ c, ∏ i ∈ S, (x + v) i) =
            ∑ S ∈ c, ((∏ i ∈ S, x i) + ∏ i ∈ S, (x i + v i)) := by
          change (∑ S ∈ c, ∏ i ∈ S, x i) + (∑ S ∈ c, ∏ i ∈ S, (x i + v i)) = _
          rw [Finset.sum_add_distrib.symm]
        rw [h_sum_add]
  6. The directional derivative D_v f(x) expands into a double sum over S ∈ c and proper subsets T ⊊ S.

    We apply the cancellation lemma `boolean_derivative_has_degree_le_pred_prod_add_cancel` to each summand indexed by S ∈ c, replacing each monomial derivative by the sum over proper subsets T ∈ powerset(S) \\ {S}.

    lines 64–69

    uses Finset.sum_congr, boolean_derivative_has_degree_le_pred_prod_add_cancel

        have h_step1 : (∑ S ∈ c, ((∏ i ∈ S, x i) + ∏ i ∈ S, (x i + v i))) =
            ∑ S ∈ c, ∑ T ∈ S.powerset.erase S, (∏ i ∈ S \ T, v i) * (∏ i ∈ T, x i) := by
          apply Finset.sum_congr rfl
          intro S _
          exact boolean_derivative_has_degree_le_pred_prod_add_cancel S x v
        rw [h_step1]
  7. The inner summation can be extended to all subsets T in the universe with an indicator function, and the order of summation can be swapped.

    We rewrite the inner sum over T ∈ powerset(S) \\ {S} as a sum over all T in the universe by inserting an if-then-else indicator for membership. We then exchange the two sums using `Finset.sum_comm`.

    lines 70–87

    uses Finset.sum_congr, Finset.univ_inter, Finset.sum_ite_mem, zero_mul, Finset.sum_comm

        have h_step2 : (∑ S ∈ c, ∑ T ∈ S.powerset.erase S, (∏ i ∈ S \ T, v i) * (∏ i ∈ T, x i)) =
            ∑ S ∈ c, ∑ T ∈ (Finset.univ : Finset (Finset (Fin n))),
              (if T ∈ S.powerset.erase S then (∏ i ∈ S \ T, v i) else 0) * (∏ i ∈ T, x i) := by
          apply Finset.sum_congr rfl
          intro S _
          have h_univ : (∑ T ∈ S.powerset.erase S, (∏ i ∈ S \ T, v i) * (∏ i ∈ T, x i)) =
              ∑ T ∈ (Finset.univ : Finset (Finset (Fin n))),
                if T ∈ S.powerset.erase S then (∏ i ∈ S \ T, v i) * (∏ i ∈ T, x i) else 0 := by
            conv_lhs => rw [← Finset.univ_inter (S.powerset.erase S)]
            exact (Finset.sum_ite_mem Finset.univ (S.powerset.erase S) _).symm
          rw [h_univ]
          apply Finset.sum_congr rfl
          intro T _
          split_ifs with h
          · rfl
          · rw [zero_mul]
        rw [h_step2]
        rw [Finset.sum_comm]
  8. The monomial term ∏_{i ∈ T} x i factors out of the inner sum over S, yielding coeff(T) * ∏_{i ∈ T} x i for each T.

    For each fixed T, the factor ∏_{i ∈ T} x i does not depend on S, so it factors out of the sum over S ∈ c by right-distributivity, leaving the coefficient coeff(T).

    lines 88–95

    uses Finset.sum_congr, Finset.sum_mul

        have h_step3 : (∑ T ∈ (Finset.univ : Finset (Finset (Fin n))),
              ∑ S ∈ c, (if T ∈ S.powerset.erase S then (∏ i ∈ S \ T, v i) else 0) * (∏ i ∈ T, x i)) =
            ∑ T ∈ (Finset.univ : Finset (Finset (Fin n))), coeff T * (∏ i ∈ T, x i) := by
          apply Finset.sum_congr rfl
          intro T _
          dsimp [coeff]
          rw [← Finset.sum_mul]
        rw [h_step3]
  9. Replacing the coefficient by an indicator and filtering to c' proves that D_v f(x) = ∑_{T ∈ c'} ∏_{i ∈ T} x i.

    Using the helper lemma on multiplication in ℤ/2ℤ, coeff(T) * ∏_{i ∈ T} x i equals ∏_{i ∈ T} x i when coeff(T) = 1 and 0 otherwise. Summing this indicator over all subsets T is equivalent to summing over the filtered set c' = {T | coeff(T) = 1}, concluding the proof.

    lines 96–102

    uses Finset.sum_congr, boolean_derivative_has_degree_le_pred_zmod2_mul_eq_ite, Finset.sum_filter

        have h_step4 : (∑ T ∈ (Finset.univ : Finset (Finset (Fin n))), coeff T * (∏ i ∈ T, x i)) =
            ∑ T ∈ (Finset.univ : Finset (Finset (Fin n))), if coeff T = 1 then (∏ i ∈ T, x i) else 0 := by
          apply Finset.sum_congr rfl
          intro T _
          exact boolean_derivative_has_degree_le_pred_zmod2_mul_eq_ite (coeff T) (∏ i ∈ T, x i)
        rw [h_step4]
        exact (Finset.sum_filter (fun T => coeff T = 1) (fun T => ∏ i ∈ T, x i)).symm
if_pos
An if-then-else expression evaluates to its 'then' branch when the condition is true.
one_mul
Multiplying by 1 on the left leaves an element unchanged.
if_neg
An if-then-else expression evaluates to its 'else' branch when the condition is false.
zero_mul
Multiplying by 0 on the left yields 0.
Finset.prod_add
The product over a finite set of a sum of two terms expands into the sum over all subsets of products of the respective terms.
Finset.mem_powerset_self
Every finite set is an element of its own powerset.
Finset.add_sum_erase
A sum over a finite set equals the term at an element plus the sum over the set with that element removed.
Finset.sdiff_self
The set difference of any set with itself is the empty set.
Finset.prod_empty
The product over the empty set is 1.
mul_one
Multiplying by 1 on the right leaves an element unchanged.
add_assoc
Addition is associative.
CharTwo.add_self_eq_zero
In characteristic 2, adding any element to itself gives 0.
zero_add
Adding 0 on the left leaves an element unchanged.
Finset.sum_congr
Two sums are equal if their index sets are equal and their summands agree on all elements of the index set.
mul_comm
Multiplication is commutative.
Finset.mem_filter
An element belongs to the filtered subset if and only if it belongs to the ambient set and satisfies the predicate.
Finset.mem_erase
An element belongs to a set with an element removed if and only if it is in the set and distinct from the removed element.
Finset.mem_powerset
A set is in the powerset of another if and only if it is a subset.
Finset.ssubset_iff_subset_ne
A set is a strict subset of another if and only if it is a subset and not equal to it.
Finset.card_lt_card
A strict subset of a finite set has strictly smaller cardinality.
Finset.sum_eq_zero
A sum over a finite set is 0 if every summand is 0.
Finset.sum_add_distrib.symm
The sum of two sums over the same finite set equals the sum of their pointwise additions.
boolean_derivative_has_degree_le_pred_prod_add_cancel
The directional derivative of a single monomial cancels the top-degree term, leaving a sum over strictly smaller subsets.
Finset.univ_inter
Intersecting any set with the universal set of a finite type yields the set itself.
Finset.sum_ite_mem
Summing a function guarded by set membership over an ambient set equals the sum over the intersection.
Finset.sum_comm
The order of two finite summations can be exchanged.
Finset.sum_mul
Multiplication distributes over finite summation on the right.
boolean_derivative_has_degree_le_pred_zmod2_mul_eq_ite
Multiplication by an element of ℤ/2ℤ equals the other factor if the element is 1, and 0 otherwise.
Finset.sum_filter
Summing over a filtered subset equals summing an if-then-else indicator over the ambient set.

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

lemma boolean_derivative_has_degree_le_pred_zmod2_mul_eq_ite (c : ZMod 2) (m : ZMod 2) :    c * m = if c = 1 then m else 0 := by  by_cases h : c = 1  · rw [h, if_pos rfl, one_mul]  · rw [if_neg h]    have : c = 0 := by      revert c h      decide    rw [this, zero_mul]lemma boolean_derivative_has_degree_le_pred_prod_add_cancel {n : ℕ} (S : Finset (Fin n)) (x v : Fin n → ZMod 2) :    (∏ i ∈ S, x i) + (∏ i ∈ S, (x i + v i)) =    ∑ T ∈ S.powerset.erase S, (∏ i ∈ S \ T, v i) * (∏ i ∈ T, x i) := by  have hp := Finset.prod_add x v S  rw [hp]  have hmem : S ∈ S.powerset := Finset.mem_powerset_self S  rw [← Finset.add_sum_erase S.powerset _ hmem]  have hS : (∏ i ∈ S, x i) * ∏ i ∈ S \ S, v i = ∏ i ∈ S, x i := by    rw [Finset.sdiff_self, Finset.prod_empty, mul_one]  rw [hS, ← add_assoc, CharTwo.add_self_eq_zero, zero_add]  apply Finset.sum_congr rfl  intro T _  rw [mul_comm]/-- The directional derivative of any Boolean function of algebraic degree at most d + 1 along any vector has algebraic degree at most d. -/theorem boolean_derivative_has_degree_le_pred {n : ℕ} (f : (Fin n → ZMod 2) → ZMod 2) (v : Fin n → ZMod 2) {d : ℕ} (hf : has_degree_le f (d + 1)) : has_degree_le (boolean_derivative v f) d := by  rcases hf with ⟨c, hc_card, hc_sum⟩  let coeff : Finset (Fin n) → ZMod 2 := fun T =>    ∑ S ∈ c, if T ∈ S.powerset.erase S then (∏ i ∈ S \ T, v i) else 0  let c' : Finset (Finset (Fin n)) :=    (Finset.univ : Finset (Finset (Fin n))).filter (fun T => coeff T = 1)  use c'  constructor  · intro T hT    rw [Finset.mem_filter] at hT    have hT_coeff : coeff T = 1 := hT.2    have hT_ne_zero : coeff T ≠ 0 := by      rw [hT_coeff]      decide    by_contra h_not    have h_not_in : ∀ S ∈ c, T ∉ S.powerset.erase S := by      intro S hS h_in      have h_card_S := hc_card S hS      rw [Finset.mem_erase, Finset.mem_powerset] at h_in      have h_ssubset : T ⊂ S := by        rw [Finset.ssubset_iff_subset_ne]        exact ⟨h_in.2, h_in.1⟩      have h_card_lt := Finset.card_lt_card h_ssubset      omega    have h_zero : coeff T = 0 := by      dsimp [coeff]      apply Finset.sum_eq_zero      intro S hS      rw [if_neg (h_not_in S hS)]    exact hT_ne_zero h_zero  · intro x    dsimp [boolean_derivative]    rw [hc_sum x, hc_sum (x + v)]    have h_sum_add : (∑ S ∈ c, ∏ i ∈ S, x i) + (∑ S ∈ c, ∏ i ∈ S, (x + v) i) =        ∑ S ∈ c, ((∏ i ∈ S, x i) + ∏ i ∈ S, (x i + v i)) := by      change (∑ S ∈ c, ∏ i ∈ S, x i) + (∑ S ∈ c, ∏ i ∈ S, (x i + v i)) = _      rw [Finset.sum_add_distrib.symm]    rw [h_sum_add]    have h_step1 : (∑ S ∈ c, ((∏ i ∈ S, x i) + ∏ i ∈ S, (x i + v i))) =        ∑ S ∈ c, ∑ T ∈ S.powerset.erase S, (∏ i ∈ S \ T, v i) * (∏ i ∈ T, x i) := by      apply Finset.sum_congr rfl      intro S _      exact boolean_derivative_has_degree_le_pred_prod_add_cancel S x v    rw [h_step1]    have h_step2 : (∑ S ∈ c, ∑ T ∈ S.powerset.erase S, (∏ i ∈ S \ T, v i) * (∏ i ∈ T, x i)) =        ∑ S ∈ c, ∑ T ∈ (Finset.univ : Finset (Finset (Fin n))),          (if T ∈ S.powerset.erase S then (∏ i ∈ S \ T, v i) else 0) * (∏ i ∈ T, x i) := by      apply Finset.sum_congr rfl      intro S _      have h_univ : (∑ T ∈ S.powerset.erase S, (∏ i ∈ S \ T, v i) * (∏ i ∈ T, x i)) =          ∑ T ∈ (Finset.univ : Finset (Finset (Fin n))),            if T ∈ S.powerset.erase S then (∏ i ∈ S \ T, v i) * (∏ i ∈ T, x i) else 0 := by        conv_lhs => rw [← Finset.univ_inter (S.powerset.erase S)]        exact (Finset.sum_ite_mem Finset.univ (S.powerset.erase S) _).symm      rw [h_univ]      apply Finset.sum_congr rfl      intro T _      split_ifs with h      · rfl      · rw [zero_mul]    rw [h_step2]    rw [Finset.sum_comm]    have h_step3 : (∑ T ∈ (Finset.univ : Finset (Finset (Fin n))),          ∑ S ∈ c, (if T ∈ S.powerset.erase S then (∏ i ∈ S \ T, v i) else 0) * (∏ i ∈ T, x i)) =        ∑ T ∈ (Finset.univ : Finset (Finset (Fin n))), coeff T * (∏ i ∈ T, x i) := by      apply Finset.sum_congr rfl      intro T _      dsimp [coeff]      rw [← Finset.sum_mul]    rw [h_step3]    have h_step4 : (∑ T ∈ (Finset.univ : Finset (Finset (Fin n))), coeff T * (∏ i ∈ T, x i)) =        ∑ T ∈ (Finset.univ : Finset (Finset (Fin n))), if coeff T = 1 then (∏ i ∈ T, x i) else 0 := by      apply Finset.sum_congr rfl      intro T _      exact boolean_derivative_has_degree_le_pred_zmod2_mul_eq_ite (coeff T) (∏ i ∈ T, x i)    rw [h_step4]    exact (Finset.sum_filter (fun T => coeff T = 1) (fun T => ∏ i ∈ T, x i)).symm
See it in the graphDiscuss this resultChallenge it