bent_sum_counterexample_not_has_degree_lt
For any m ≥ 4 and any k < m, bent_sum_counterexample_func m hm does not have algebraic degree at most k.
Statement
theorem bent_sum_counterexample_not_has_degree_lt (m : ℕ) (hm : 4 ≤ m) :
∀ k < m, ¬ has_degree_le (bent_sum_counterexample_func m hm) k- Source
- step towards bent_sum_counterexample_not_sum_of_two_bent
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
- bent_sum_counterexample_funcFor any integer m ≥ 4, the Boolean function on (Fin (2 * m) → ZMod 2) defined by multiplying the first m - 2 coordinates and the sum of…
The proof, explained
The proof proceeds by contradiction, assuming that the Boolean function has algebraic degree at most k < m. A polynomial of degree at most k must sum to 0 over the m-dimensional subcube indexed by the first m coordinates T = {0, ..., m-1}, because every monomial in its representation has fewer than m variables and thus evaluates to 1 on an even number (2^(m - |S|)) of points. On the other hand, direct evaluation shows that all variable pairs outside T vanish on this subcube, leaving only the full product over T, which evaluates to 1 only at A = T and yields a sum of 1. This produces 0 = 1 in ZMod 2, a contradiction.
For any assignment x, the coordinate product over T = {0, ..., m-1} factors into the product over the first m-2 coordinates times x_{m-2} * x_{m-1}.
The set S0 consists of the first m-2 indices. Since a = m-2 and b = m-1 have values exceeding m-3, neither belongs to S0, and a ≠ b. Applying Finset.prod_image rewrites the product over S0, and Finset.prod_insert extracts a and b from T = insert a (insert b S0). Ring arithmetic rearranges the factors into the desired form.
uses
Finset.prod_image,Finset.prod_insertlemma bent_sum_counterexample_not_has_degree_lt_prod_T (m : ℕ) (hm : 4 ≤ m) (x : Fin (2 * m) → ZMod 2) : let S0 : Finset (Fin (2 * m)) := Finset.univ.image (fun (i : Fin (m - 2)) => ⟨i.val, by omega⟩) let a : Fin (2 * m) := ⟨m - 2, by omega⟩ let b : Fin (2 * m) := ⟨m - 1, by omega⟩ let T : Finset (Fin (2 * m)) := insert a (insert b S0) (∏ i ∈ T, x i) = (∏ i : Fin (m - 2), x ⟨i.val, by omega⟩) * (x a * x b) := by intro S0 a b T have hS0_mem : ∀ v ∈ S0, (v : Fin (2 * m)).val < m - 2 := by intro v hv simp only [S0, Finset.mem_image, Finset.mem_univ, true_and] at hv rcases hv with ⟨i, hi⟩ have hi_val : (v : ℕ) = i.val := congrArg Fin.val hi.symm have := i.isLt; omega have hb_notin_S0 : b ∉ S0 := by intro h; have := hS0_mem b h; dsimp [b] at this; omega have ha_notin_S0 : a ∉ S0 := by intro h; have := hS0_mem a h; dsimp [a] at this; omega have hab : a ≠ b := by intro h; apply_fun Fin.val at h; dsimp [a, b] at h; omega have ha_notin : a ∉ insert b S0 := by simp [hab, ha_notin_S0] have hprod_S0 : (∏ i ∈ S0, x i) = ∏ i : Fin (m - 2), x ⟨i.val, by omega⟩ := by dsimp [S0] rw [Finset.prod_image] intro u _ v _ huv ext have := congrArg Fin.val huv exact this dsimp [T] rw [Finset.prod_insert ha_notin, Finset.prod_insert hb_notin_S0, hprod_S0] ring
Assuming the counterexample function has degree at most k < m, we construct an index set T of size m such that k < |T|.
We assume for contradiction that the algebraic degree is at most k with k < m. We define T by adjoining a = m-2 and b = m-1 to S0 = {0, ..., m-3}. Since the embedding of Fin (m-2) into Fin (2*m) is injective, |S0| = m - 2 by Finset.card_image_of_injective and Fintype.card_fin. As a and b are distinct and not in S0, applying Finset.card_insert_of_notMem twice shows |T| = m, which implies k < |T|.
uses
Finset.card_image_of_injective,Fintype.card_fin,Finset.card_insert_of_notMem/-- The counterexample Boolean function f_n on (Fin (2*m) → ZMod 2) does not have algebraic degree strictly less than m. -/ theorem bent_sum_counterexample_not_has_degree_lt (m : ℕ) (hm : 4 ≤ m) : ∀ k < m, ¬ has_degree_le (bent_sum_counterexample_func m hm) k := by intro k hk hdeg let S0 : Finset (Fin (2 * m)) := Finset.univ.image (fun (i : Fin (m - 2)) => ⟨i.val, by omega⟩) let a : Fin (2 * m) := ⟨m - 2, by omega⟩ let b : Fin (2 * m) := ⟨m - 1, by omega⟩ let T : Finset (Fin (2 * m)) := insert a (insert b S0) have hS0_card : S0.card = m - 2 := by dsimp [S0] rw [Finset.card_image_of_injective] · exact Fintype.card_fin (m - 2) · intro x y hxy ext have : (⟨x.val, by omega⟩ : Fin (2 * m)).val = (⟨y.val, by omega⟩ : Fin (2 * m)).val := congrArg Fin.val hxy exact this have hS0_mem : ∀ v ∈ S0, (v : Fin (2 * m)).val < m - 2 := by intro v hv simp only [S0, Finset.mem_image, Finset.mem_univ, true_and] at hv rcases hv with ⟨i, hi⟩ have hi_val : (v : ℕ) = i.val := congrArg Fin.val hi.symm have := i.isLt; omega have hb_notin_S0 : b ∉ S0 := by intro h; have := hS0_mem b h; dsimp [b] at this; omega have ha_notin_S0 : a ∉ S0 := by intro h; have := hS0_mem a h; dsimp [a] at this; omega have hab : a ≠ b := by intro h; apply_fun Fin.val at h; dsimp [a, b] at h; omega have ha_notin : a ∉ insert b S0 := by simp [hab, ha_notin_S0] have hT_card : T.card = m := by dsimp [T] rw [Finset.card_insert_of_notMem ha_notin, Finset.card_insert_of_notMem hb_notin_S0, hS0_card] omega have hkT : k < T.card := by rw [hT_card]; exact hk
The sum of the function over all indicator vectors 1_A for subsets A ⊆ T equals 0.
By the degree assumption, the function is a sum of monomials with degree at most k. Swapping the sums using Finset.sum_comm, it suffices to show that each monomial S with |S| ≤ k < |T| sums to 0 over A ⊆ T. A monomial evaluates to 1 on 1_A if and only if S ⊆ A. If S is not a subset of T, no such A exists and the sum is 0 by Finset.filter_eq_empty_iff. If S ⊆ T, the family of subsets A ⊆ T containing S is the interval [S, T], which has size 2^(|T| - |S|) by Finset.card_Icc_finset. Because |S| < |T|, Nat.sub_pos_of_lt ensures |T| - |S| ≥ 1, so the cardinality is a positive power of 2 and therefore vanishes modulo 2 by mul_zero.
uses
Finset.sum_comm,Finset.filter_eq_empty_iff,Finset.card_Icc_finset,Nat.sub_pos_of_lt,mul_zerohave h_zero : (∑ A ∈ T.powerset, bent_sum_counterexample_func m hm (fun i => if i ∈ A then 1 else 0)) = 0 := by rcases hdeg with ⟨c, hc_card, hc_eval⟩ have h1 : (∑ A ∈ T.powerset, bent_sum_counterexample_func m hm (fun i => if i ∈ A then 1 else 0)) = ∑ A ∈ T.powerset, ∑ S ∈ c, ∏ i ∈ S, (if i ∈ A then (1 : ZMod 2) else 0) := by apply Finset.sum_congr rfl intro A hA exact hc_eval _ rw [h1, Finset.sum_comm] have h2 : ∀ S ∈ c, (∑ A ∈ T.powerset, ∏ i ∈ S, (if i ∈ A then (1 : ZMod 2) else 0)) = 0 := by intro S hS have hprod : ∀ A, (∏ i ∈ S, (if i ∈ A then (1 : ZMod 2) else 0)) = if S ⊆ A then 1 else 0 := by intro A split_ifs with h · have : ∀ i ∈ S, (if i ∈ A then (1 : ZMod 2) else 0) = 1 := by intro i hi; simp [h hi] rw [Finset.prod_congr rfl this, Finset.prod_const_one] · rw [Finset.not_subset] at h rcases h with ⟨x, hxS, hxA⟩ have : (if x ∈ A then (1 : ZMod 2) else 0) = 0 := by simp [hxA] exact Finset.prod_eq_zero hxS this simp_rw [hprod] have hScard : S.card < T.card := lt_of_le_of_lt (hc_card S hS) hkT rw [Finset.sum_ite, Finset.sum_const_zero, add_zero, Finset.sum_const, nsmul_eq_mul, mul_one] by_cases h : S ⊆ T · rw [← Finset.Icc_eq_filter_powerset, Finset.card_Icc_finset h] rcases Nat.exists_eq_succ_of_ne_zero (ne_of_gt (Nat.sub_pos_of_lt hScard)) with ⟨r, hr⟩ rw [hr, pow_succ] push_cast have : (2 : ZMod 2) = 0 := rfl rw [this, mul_zero] · have : Finset.filter (fun u => S ⊆ u) T.powerset = ∅ := by rw [Finset.filter_eq_empty_iff] intro u hu hsu rw [Finset.mem_powerset] at hu exact h (hsu.trans hu) rw [this, Finset.card_empty, Nat.cast_zero] rw [Finset.sum_congr rfl h2, Finset.sum_const_zero]
Direct evaluation of the function shows that its sum over all subsets A ⊆ T equals 1.
All elements in T have index at most m - 1, so the variables c1 = m and e = m + 2 never belong to any A ⊆ T. Therefore x_A(c1) = 0 and x_A(e) = 0, causing the second and third quadratic terms in the definition of the function to vanish. By bent_sum_counterexample_not_has_degree_lt_prod_T, the remaining term is the product over all coordinates in T, which equals 1 if and only if T ⊆ A. Since A ⊆ T, this holds uniquely when A = T. Summing over all subsets A in the powerset of T, Finset.sum_ite_eq' and Finset.mem_powerset_self evaluate the sum to 1.
uses
bent_sum_counterexample_not_has_degree_lt_prod_T,Finset.sum_ite_eq',Finset.mem_powerset_selfhave h_one : (∑ A ∈ T.powerset, bent_sum_counterexample_func m hm (fun i => if i ∈ A then 1 else 0)) = 1 := by let c1 : Fin (2 * m) := ⟨m, by omega⟩ let d1 : Fin (2 * m) := ⟨m + 1, by omega⟩ let e : Fin (2 * m) := ⟨m + 2, by omega⟩ let f1 : Fin (2 * m) := ⟨m + 3, by omega⟩ have hT_mem : ∀ v ∈ T, (v : Fin (2 * m)).val ≤ m - 1 := by intro v hv simp only [T, Finset.mem_insert] at hv rcases hv with rfl | rfl | hv · dsimp [a]; omega · dsimp [b]; omega · have := hS0_mem v hv; omega have hA_mem : ∀ A ∈ T.powerset, ∀ v ∈ A, (v : Fin (2 * m)).val ≤ m - 1 := by intro A hA v hv rw [Finset.mem_powerset] at hA exact hT_mem v (hA hv) have hc1_notin : ∀ A ∈ T.powerset, c1 ∉ A := by intro A hA h; have := hA_mem A hA c1 h; dsimp [c1] at this; omega have he_notin : ∀ A ∈ T.powerset, e ∉ A := by intro A hA h; have := hA_mem A hA e h; dsimp [e] at this; omega have h_term : ∀ A ∈ T.powerset, bent_sum_counterexample_func m hm (fun i => if i ∈ A then 1 else 0) = if A = T then 1 else 0 := by intro A hA let xA : Fin (2 * m) → ZMod 2 := fun i => if i ∈ A then 1 else 0 have hxA_c1 : xA c1 = 0 := by dsimp [xA]; simp [hc1_notin A hA] have hxA_e : xA e = 0 := by dsimp [xA]; simp [he_notin A hA] have hf_def : bent_sum_counterexample_func m hm xA = (∏ i : Fin (m - 2), xA ⟨i.val, by omega⟩) * (xA a * xA b + xA c1 * xA d1 + xA e * xA f1) := rfl rw [hf_def, hxA_c1, hxA_e, zero_mul, zero_mul, add_zero, add_zero] have hpair := bent_sum_counterexample_not_has_degree_lt_prod_T m hm xA dsimp only [S0, a, b, T] at hpair rw [← hpair] have hprod : (∏ i ∈ T, xA i) = if T ⊆ A then 1 else 0 := by dsimp [xA] split_ifs with h · have : ∀ i ∈ T, (if i ∈ A then (1 : ZMod 2) else 0) = 1 := by intro i hi; simp [h hi] rw [Finset.prod_congr rfl this, Finset.prod_const_one] · rw [Finset.not_subset] at h rcases h with ⟨v, hvT, hvA⟩ have : (if v ∈ A then (1 : ZMod 2) else 0) = 0 := by simp [hvA] exact Finset.prod_eq_zero hvT this rw [hprod] rw [Finset.mem_powerset] at hA have : (T ⊆ A) ↔ (A = T) := by constructor · intro h; exact Finset.Subset.antisymm hA h · rintro rfl; exact Finset.Subset.refl T rw [if_congr this rfl rfl] rw [Finset.sum_congr rfl h_term] rw [Finset.sum_ite_eq' T.powerset T (fun _ => (1 : ZMod 2))] have hT_in : T ∈ T.powerset := Finset.mem_powerset_self T simp [hT_in]
A contradiction is reached, proving that the function cannot have degree at most k.
Equating the results of the two summations yields 0 = 1 in ZMod 2, which contradicts zero_ne_one.
uses
zero_ne_onerw [h_zero] at h_one exact zero_ne_one h_one
Finset.prod_image- The product of a function over the image of a finite set under an injective map equals the product of the composed function over the original domain.
Finset.prod_insert- Inserting an element not already present in a finite set multiplies the product over the set by the function value at that element.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
Fintype.card_fin- The standard finite set Fin n has cardinality n.
Finset.card_insert_of_notMem- Inserting an element into a finite set that does not already contain it increases its cardinality by 1.
Finset.sum_comm- The order of summation in a finite double sum can be swapped.
Finset.card_Icc_finset- For finite sets s ⊆ t, the number of subsets u satisfying s ⊆ u ⊆ t is 2^(|t| - |s|).
Nat.sub_pos_of_lt- If m < n for natural numbers, then n - m > 0.
mul_zero- Multiplication by zero equals zero in any commutative semiring.
Finset.filter_eq_empty_iff- The filter of elements satisfying a predicate in a finite set is empty if and only if no element of the set satisfies the predicate.
bent_sum_counterexample_not_has_degree_lt_prod_T- On the index set T = {0, ..., m-1}, the product of coordinates factors into the product over the first m-2 coordinates times x_{m-2} * x_{m-1}.
Finset.sum_ite_eq'- Summing an indicator term that is non-zero only when the variable equals a given element evaluates to that term if the element belongs to the set, and 0 otherwise.
Finset.mem_powerset_self- Every finite set is an element of its own powerset.
zero_ne_one- Zero is not equal to one in ZMod 2.
- Linear integer arithmetic via the omega tactic is used throughout to verify index inequalities and establish disjointness of index sets.
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 bent_sum_counterexample_not_has_degree_lt_prod_T (m : ℕ) (hm : 4 ≤ m) (x : Fin (2 * m) → ZMod 2) : let S0 : Finset (Fin (2 * m)) := Finset.univ.image (fun (i : Fin (m - 2)) => ⟨i.val, by omega⟩) let a : Fin (2 * m) := ⟨m - 2, by omega⟩ let b : Fin (2 * m) := ⟨m - 1, by omega⟩ let T : Finset (Fin (2 * m)) := insert a (insert b S0) (∏ i ∈ T, x i) = (∏ i : Fin (m - 2), x ⟨i.val, by omega⟩) * (x a * x b) := by intro S0 a b T have hS0_mem : ∀ v ∈ S0, (v : Fin (2 * m)).val < m - 2 := by intro v hv simp only [S0, Finset.mem_image, Finset.mem_univ, true_and] at hv rcases hv with ⟨i, hi⟩ have hi_val : (v : ℕ) = i.val := congrArg Fin.val hi.symm have := i.isLt; omega have hb_notin_S0 : b ∉ S0 := by intro h; have := hS0_mem b h; dsimp [b] at this; omega have ha_notin_S0 : a ∉ S0 := by intro h; have := hS0_mem a h; dsimp [a] at this; omega have hab : a ≠ b := by intro h; apply_fun Fin.val at h; dsimp [a, b] at h; omega have ha_notin : a ∉ insert b S0 := by simp [hab, ha_notin_S0] have hprod_S0 : (∏ i ∈ S0, x i) = ∏ i : Fin (m - 2), x ⟨i.val, by omega⟩ := by dsimp [S0] rw [Finset.prod_image] intro u _ v _ huv ext have := congrArg Fin.val huv exact this dsimp [T] rw [Finset.prod_insert ha_notin, Finset.prod_insert hb_notin_S0, hprod_S0] ring/-- The counterexample Boolean function f_n on (Fin (2*m) → ZMod 2) does not have algebraic degree strictly less than m. -/theorem bent_sum_counterexample_not_has_degree_lt (m : ℕ) (hm : 4 ≤ m) : ∀ k < m, ¬ has_degree_le (bent_sum_counterexample_func m hm) k := by intro k hk hdeg let S0 : Finset (Fin (2 * m)) := Finset.univ.image (fun (i : Fin (m - 2)) => ⟨i.val, by omega⟩) let a : Fin (2 * m) := ⟨m - 2, by omega⟩ let b : Fin (2 * m) := ⟨m - 1, by omega⟩ let T : Finset (Fin (2 * m)) := insert a (insert b S0) have hS0_card : S0.card = m - 2 := by dsimp [S0] rw [Finset.card_image_of_injective] · exact Fintype.card_fin (m - 2) · intro x y hxy ext have : (⟨x.val, by omega⟩ : Fin (2 * m)).val = (⟨y.val, by omega⟩ : Fin (2 * m)).val := congrArg Fin.val hxy exact this have hS0_mem : ∀ v ∈ S0, (v : Fin (2 * m)).val < m - 2 := by intro v hv simp only [S0, Finset.mem_image, Finset.mem_univ, true_and] at hv rcases hv with ⟨i, hi⟩ have hi_val : (v : ℕ) = i.val := congrArg Fin.val hi.symm have := i.isLt; omega have hb_notin_S0 : b ∉ S0 := by intro h; have := hS0_mem b h; dsimp [b] at this; omega have ha_notin_S0 : a ∉ S0 := by intro h; have := hS0_mem a h; dsimp [a] at this; omega have hab : a ≠ b := by intro h; apply_fun Fin.val at h; dsimp [a, b] at h; omega have ha_notin : a ∉ insert b S0 := by simp [hab, ha_notin_S0] have hT_card : T.card = m := by dsimp [T] rw [Finset.card_insert_of_notMem ha_notin, Finset.card_insert_of_notMem hb_notin_S0, hS0_card] omega have hkT : k < T.card := by rw [hT_card]; exact hk have h_zero : (∑ A ∈ T.powerset, bent_sum_counterexample_func m hm (fun i => if i ∈ A then 1 else 0)) = 0 := by rcases hdeg with ⟨c, hc_card, hc_eval⟩ have h1 : (∑ A ∈ T.powerset, bent_sum_counterexample_func m hm (fun i => if i ∈ A then 1 else 0)) = ∑ A ∈ T.powerset, ∑ S ∈ c, ∏ i ∈ S, (if i ∈ A then (1 : ZMod 2) else 0) := by apply Finset.sum_congr rfl intro A hA exact hc_eval _ rw [h1, Finset.sum_comm] have h2 : ∀ S ∈ c, (∑ A ∈ T.powerset, ∏ i ∈ S, (if i ∈ A then (1 : ZMod 2) else 0)) = 0 := by intro S hS have hprod : ∀ A, (∏ i ∈ S, (if i ∈ A then (1 : ZMod 2) else 0)) = if S ⊆ A then 1 else 0 := by intro A split_ifs with h · have : ∀ i ∈ S, (if i ∈ A then (1 : ZMod 2) else 0) = 1 := by intro i hi; simp [h hi] rw [Finset.prod_congr rfl this, Finset.prod_const_one] · rw [Finset.not_subset] at h rcases h with ⟨x, hxS, hxA⟩ have : (if x ∈ A then (1 : ZMod 2) else 0) = 0 := by simp [hxA] exact Finset.prod_eq_zero hxS this simp_rw [hprod] have hScard : S.card < T.card := lt_of_le_of_lt (hc_card S hS) hkT rw [Finset.sum_ite, Finset.sum_const_zero, add_zero, Finset.sum_const, nsmul_eq_mul, mul_one] by_cases h : S ⊆ T · rw [← Finset.Icc_eq_filter_powerset, Finset.card_Icc_finset h] rcases Nat.exists_eq_succ_of_ne_zero (ne_of_gt (Nat.sub_pos_of_lt hScard)) with ⟨r, hr⟩ rw [hr, pow_succ] push_cast have : (2 : ZMod 2) = 0 := rfl rw [this, mul_zero] · have : Finset.filter (fun u => S ⊆ u) T.powerset = ∅ := by rw [Finset.filter_eq_empty_iff] intro u hu hsu rw [Finset.mem_powerset] at hu exact h (hsu.trans hu) rw [this, Finset.card_empty, Nat.cast_zero] rw [Finset.sum_congr rfl h2, Finset.sum_const_zero] have h_one : (∑ A ∈ T.powerset, bent_sum_counterexample_func m hm (fun i => if i ∈ A then 1 else 0)) = 1 := by let c1 : Fin (2 * m) := ⟨m, by omega⟩ let d1 : Fin (2 * m) := ⟨m + 1, by omega⟩ let e : Fin (2 * m) := ⟨m + 2, by omega⟩ let f1 : Fin (2 * m) := ⟨m + 3, by omega⟩ have hT_mem : ∀ v ∈ T, (v : Fin (2 * m)).val ≤ m - 1 := by intro v hv simp only [T, Finset.mem_insert] at hv rcases hv with rfl | rfl | hv · dsimp [a]; omega · dsimp [b]; omega · have := hS0_mem v hv; omega have hA_mem : ∀ A ∈ T.powerset, ∀ v ∈ A, (v : Fin (2 * m)).val ≤ m - 1 := by intro A hA v hv rw [Finset.mem_powerset] at hA exact hT_mem v (hA hv) have hc1_notin : ∀ A ∈ T.powerset, c1 ∉ A := by intro A hA h; have := hA_mem A hA c1 h; dsimp [c1] at this; omega have he_notin : ∀ A ∈ T.powerset, e ∉ A := by intro A hA h; have := hA_mem A hA e h; dsimp [e] at this; omega have h_term : ∀ A ∈ T.powerset, bent_sum_counterexample_func m hm (fun i => if i ∈ A then 1 else 0) = if A = T then 1 else 0 := by intro A hA let xA : Fin (2 * m) → ZMod 2 := fun i => if i ∈ A then 1 else 0 have hxA_c1 : xA c1 = 0 := by dsimp [xA]; simp [hc1_notin A hA] have hxA_e : xA e = 0 := by dsimp [xA]; simp [he_notin A hA] have hf_def : bent_sum_counterexample_func m hm xA = (∏ i : Fin (m - 2), xA ⟨i.val, by omega⟩) * (xA a * xA b + xA c1 * xA d1 + xA e * xA f1) := rfl rw [hf_def, hxA_c1, hxA_e, zero_mul, zero_mul, add_zero, add_zero] have hpair := bent_sum_counterexample_not_has_degree_lt_prod_T m hm xA dsimp only [S0, a, b, T] at hpair rw [← hpair] have hprod : (∏ i ∈ T, xA i) = if T ⊆ A then 1 else 0 := by dsimp [xA] split_ifs with h · have : ∀ i ∈ T, (if i ∈ A then (1 : ZMod 2) else 0) = 1 := by intro i hi; simp [h hi] rw [Finset.prod_congr rfl this, Finset.prod_const_one] · rw [Finset.not_subset] at h rcases h with ⟨v, hvT, hvA⟩ have : (if v ∈ A then (1 : ZMod 2) else 0) = 0 := by simp [hvA] exact Finset.prod_eq_zero hvT this rw [hprod] rw [Finset.mem_powerset] at hA have : (T ⊆ A) ↔ (A = T) := by constructor · intro h; exact Finset.Subset.antisymm hA h · rintro rfl; exact Finset.Subset.refl T rw [if_congr this rfl rfl] rw [Finset.sum_congr rfl h_term] rw [Finset.sum_ite_eq' T.powerset T (fun _ => (1 : ZMod 2))] have hT_in : T ∈ T.powerset := Finset.mem_powerset_self T simp [hT_in] rw [h_zero] at h_one exact zero_ne_one h_one