AFTD Auto-Formalizing Theoretical Domains

bent_sum_counterexample_not_has_degree_lt

theoremverified

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.

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

    lines 1–32

    uses Finset.prod_image, Finset.prod_insert

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

    lines 33–70

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

    lines 71–108

    uses Finset.sum_comm, Finset.filter_eq_empty_iff, Finset.card_Icc_finset, Nat.sub_pos_of_lt, mul_zero

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

    lines 109–163

    uses bent_sum_counterexample_not_has_degree_lt_prod_T, Finset.sum_ite_eq', Finset.mem_powerset_self

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

    lines 164–165

    uses zero_ne_one

      rw [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.

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