boolean_derivative_has_degree_le_pred
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.
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.
uses
if_pos,one_mul,if_neg,zero_mulby_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]
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}.
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_commhave 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]
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'.
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
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.
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
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.
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]
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}.
uses
Finset.sum_congr,boolean_derivative_has_degree_le_pred_prod_add_cancelhave 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]
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`.
uses
Finset.sum_congr,Finset.univ_inter,Finset.sum_ite_mem,zero_mul,Finset.sum_commhave 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]
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).
uses
Finset.sum_congr,Finset.sum_mulhave 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]
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.
uses
Finset.sum_congr,boolean_derivative_has_degree_le_pred_zmod2_mul_eq_ite,Finset.sum_filterhave 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.
- Linear integer arithmetic in `omega` handles the cardinality inequalities, while `decide` handles finite case exhaustion over ℤ/2ℤ.
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.
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