AFTD Auto-Formalizing Theoretical Domains

f2_subset_le_four_universal_spectrum

theoremverifiedformalization

For every natural number d and every subset T of Fin d → ZMod 2 with cardinality 1, 2, or 4, there exists a subset B of Fin d → ZMod 2 such that |B| * |T| = 2^d and for all distinct b, b' ∈ B, the character sum ∑ t ∈ T, (-1 : ℤ) ^ (dotProduct (b + b') t).val is nonzero.

Statement

open scoped Matrix in
theorem f2_subset_le_four_universal_spectrum (d : ℕ)
    (T : Finset (Fin d → ZMod 2)) (hT : T.card = 1 ∨ T.card = 2 ∨ T.card = 4) :
    ∃ B : Finset (Fin d → ZMod 2), B.card * T.card = 2 ^ d ∧
      ∀ b ∈ B, ∀ b' ∈ B, b ≠ b' → ∑ t ∈ T, (-1 : ℤ) ^ (dotProduct (b + b') t).val ≠ 0
Formalizes
arXiv:2610.24022, Lemma 3.3
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For every natural number $d$ and every finite subset $T \subseteq (\mathbb{Z}/2\mathbb{Z})^d$ (represented as Finset (Fin d → ZMod 2)) whose cardinality is 1, 2, or 4, there exists a finite subset $B \subseteq (\mathbb{Z}/2\mathbb{Z})^d$ such that: 1. $|B| \cdot |T| = 2^d$, and 2. for all $b, b' \in B$ with $b \neq b'$, the sum $$\sum_{t \in T} (-1)^{((b + b') \cdot t).\mathrm{val}} \neq 0$$ in $\mathbb{Z}$, where $(b + b') \cdot t = \sum_{i \in \mathrm{Fin}\, d} (b(i) + b'(i)) t(i) \in \mathbb{Z}/2\mathbb{Z}$ is the standard dot product, and .val takes the value in $\{0, 1\} \subseteq \mathbb{N}$.

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 theorem constructs a dual subset B in (ZMod 2)^d such that |B| * |T| = 2^d and the character sum ∑_{t ∈ T} (-1)^((b + b') ⬝ᵥ t) is nonzero for all distinct b, b' ∈ B, whenever |T| ∈ {1, 2, 4}. For |T| = 1, B is chosen to be the entire space (ZMod 2)^d, where the sum has 1 term (±1 ≠ 0). For |T| = 2, B is the orthogonal hyperplane to the difference t₁ + t₂, which makes both dot products equal and yields a sum of 2 * (±1) ≠ 0. For |T| = 4, B is the codimension-2 subspace orthogonal to both t₁ + t₀ and t₂ + t₀; this forces three of the four characters to agree, producing a sum of the form 3(±1) ± 1 ∈ {±2, ±4}, which is always nonzero.

  1. Every element c of ZMod 2 is either 0 or 1.

    The canonical representative c.val is strictly less than 2, so by interval cases c.val must be 0 or 1, which reduces c to 0 or 1 respectively.

    lines 5–9

    uses ZMod.val_lt, ZMod.natCast_zmod_val

      have h : c.val < 2 := ZMod.val_lt c
      have hc : ((c.val : ℕ) : ZMod 2) = c := ZMod.natCast_zmod_val c
      interval_cases c.val
      · left; rw [← hc]; norm_num
      · right; rw [← hc]; norm_num
  2. For any a, b in ZMod 2, a + b = 0 if and only if a = b.

    Since ZMod 2 has characteristic 2, the additive inverse of any element is itself (-b = b). Thus a + b = 0 implies a = -b = b, and conversely a = b implies a + b = b + b = 0.

    lines 13–17

    uses neg_eq_of_add_eq_zero_left, CharTwo.neg_eq, CharTwo.add_self_eq_zero

      constructor
      · intro h
        rw [← neg_eq_of_add_eq_zero_left h]
        exact CharTwo.neg_eq b
      · intro h; rw [h]; exact CharTwo.add_self_eq_zero b
  3. In the vector space (ZMod 2)^d, every vector is its own additive inverse (z + z = 0 and -z = z), and a + b = 0 if and only if a = b.

    Pointwise addition and negation on functions into ZMod 2 inherit the characteristic-2 properties of the ground ring. It follows that a + b = 0 implies a = -b = b, and conversely a = b implies a + b = 0.

    lines 21–35

    uses Pi.add_apply, Pi.zero_apply, CharTwo.add_self_eq_zero, Pi.neg_apply, CharTwo.neg_eq, neg_eq_of_add_eq_zero_left, f2_subset_le_four_universal_spectrum_neg_eq_self_fun, f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun

      funext j; simp only [Pi.add_apply, Pi.zero_apply]; exact CharTwo.add_self_eq_zero (z j)
    
    lemma f2_subset_le_four_universal_spectrum_neg_eq_self_fun (d : ℕ) (z : Fin d → ZMod 2) :
        -z = z := by
      funext j; simp only [Pi.neg_apply]; exact CharTwo.neg_eq (z j)
    
    lemma f2_subset_le_four_universal_spectrum_add_eq_zero_iff (d : ℕ)
        (a b : Fin d → ZMod 2) : a + b = 0 ↔ a = b := by
      constructor
      · intro h
        rw [← neg_eq_of_add_eq_zero_left h]
        exact f2_subset_le_four_universal_spectrum_neg_eq_self_fun d b
      · intro h
        rw [h]
        exact f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d b
  4. For any z in ZMod 2, the sign (-1)^z.val is nonzero and belongs to {1, -1}.

    Since z.val < 2, testing the cases z.val = 0 and z.val = 1 gives (-1)^0 = 1 and (-1)^1 = -1, both of which are nonzero.

    lines 39–47

    uses ZMod.val_lt

      have h : z.val < 2 := ZMod.val_lt z
      interval_cases z.val <;> simp
    
    lemma f2_subset_le_four_universal_spectrum_chi_pm_one (z : ZMod 2) :
        (-1 : ℤ) ^ z.val = 1 ∨ (-1 : ℤ) ^ z.val = -1 := by
      have h : z.val < 2 := ZMod.val_lt z
      interval_cases z.val
      · left; simp
      · right; simp
  5. For any nonzero vector v in (ZMod 2)^d, the orthogonal hyperplane {x | x ⬝ᵥ v = 0} has cardinality 2^(d-1), so twice its size is 2^d.

    Since v ≠ 0, some coordinate v i is 1. The standard basis vector e = Pi.single i 1 satisfies e ⬝ᵥ v = 1 and e + e = 0. Translation by e is an involution and establishes a bijection between {x | x ⬝ᵥ v = 0} and its complement {x | x ⬝ᵥ v = 1}. These two subsets partition the full space (ZMod 2)^d of size 2^d into two equal-sized halves. Linear arithmetic concludes the claim.

    lines 52–89

    uses f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one, single_dotProduct, f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun, Finset.card_bij, add_dotProduct, add_right_cancel, add_assoc, add_zero, Finset.filter_congr, Finset.card_filter_add_card_filter_not, Finset.card_univ, Fintype.card_fun, ZMod.card, Fintype.card_fin

      obtain ⟨i, hi⟩ : ∃ i, v i ≠ 0 := by
        by_contra h
        simp only [not_exists, not_not] at h
        exact hv (funext h)
      have hi1 : v i = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (v i)).resolve_left hi
      set e : Fin d → ZMod 2 := Pi.single i 1 with he
      have hev : e ⬝ᵥ v = 1 := by rw [he, single_dotProduct]; simp [hi1]
      have hee : e + e = 0 := f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d e
      have hbij : (Finset.univ.filter (fun x => x ⬝ᵥ v = 0)).card
          = (Finset.univ.filter (fun x => x ⬝ᵥ v = 1)).card := by
        apply Finset.card_bij (fun x _ => x + e)
        · intro x hx
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢
          rw [add_dotProduct, hx, hev]; decide
        · intro x1 _ x2 _ h
          exact add_right_cancel h
        · intro y hy
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hy
          refine ⟨y + e, ?_, ?_⟩
          · simp only [Finset.mem_filter, Finset.mem_univ, true_and]
            rw [add_dotProduct, hy, hev]; decide
          · show y + e + e = y
            rw [add_assoc, hee, add_zero]
      have hnot : (Finset.univ.filter (fun x => ¬ (x ⬝ᵥ v = 0)))
          = (Finset.univ.filter (fun x => x ⬝ᵥ v = 1)) := by
        apply Finset.filter_congr
        intro x _
        constructor
        · intro h; exact (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (x ⬝ᵥ v)).resolve_left h
        · intro h h0; rw [h0] at h; exact absurd h (by decide)
      have hpart : (Finset.univ.filter (fun x => x ⬝ᵥ v = 0)).card
          + (Finset.univ.filter (fun x => ¬ (x ⬝ᵥ v = 0))).card
          = Fintype.card (Fin d → ZMod 2) := by
        rw [Finset.card_filter_add_card_filter_not, Finset.card_univ]
      have hV : Fintype.card (Fin d → ZMod 2) = 2^d := by
        rw [Fintype.card_fun, ZMod.card, Fintype.card_fin]
      rw [hV, hnot, ← hbij] at hpart
      omega
  6. For any distinct nonzero vectors a, b in (ZMod 2)^d, there exists a vector x such that x ⬝ᵥ a = 0 and x ⬝ᵥ b = 1.

    If there is a coordinate j where b j = 1 and a j = 0, the basis vector e_j directly witnesses the claim. Otherwise, the support of b is strictly contained in the support of a. Since a ≠ b, there is an index i with a i = 1 and b i = 0, and since b ≠ 0, there is an index j ≠ i with b j = 1 and a j = 1. Then x = e_i + e_j satisfies x ⬝ᵥ a = 1 + 1 = 0 and x ⬝ᵥ b = 0 + 1 = 1.

    lines 94–122

    uses single_dotProduct, f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one, one_ne_zero, add_dotProduct

      by_cases h : ∃ j, b j ≠ 0 ∧ a j = 0
      · obtain ⟨j, hbj, haj⟩ := h
        refine ⟨Pi.single j 1, ?_, ?_⟩
        · rw [single_dotProduct, haj, mul_zero]
        · rw [single_dotProduct, one_mul]
          exact (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (b j)).resolve_left hbj
      · have h' : ∀ j, b j ≠ 0 → a j ≠ 0 := by
          intro j hbj haj; exact h ⟨j, hbj, haj⟩
        obtain ⟨j, hbj⟩ : ∃ j, b j ≠ 0 := by
          by_contra hh; simp only [not_exists, not_not] at hh; exact hb (funext hh)
        obtain ⟨i, hi⟩ : ∃ i, a i ≠ b i := by
          by_contra hh; simp only [not_exists, not_not] at hh; exact hab (funext hh)
        have hbi : b i = 0 := by
          rcases f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (b i) with h0 | h1
          · exact h0
          · exfalso
            have hai : a i ≠ 0 := h' i (by rw [h1]; exact one_ne_zero)
            have hai1 : a i = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (a i)).resolve_left hai
            exact hi (by rw [hai1, h1])
        have hai : a i = 1 := by
          rcases f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (a i) with h0 | h1
          · exact absurd (by rw [h0, hbi] : a i = b i) hi
          · exact h1
        have haj : a j = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (a j)).resolve_left (h' j hbj)
        have hbj1 : b j = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (b j)).resolve_left hbj
        have hij : i ≠ j := by intro hij; rw [hij] at hbi; exact hbj hbi
        refine ⟨Pi.single i 1 + Pi.single j 1, ?_, ?_⟩
        · rw [add_dotProduct, single_dotProduct, single_dotProduct, hai, haj]; decide
        · rw [add_dotProduct, single_dotProduct, single_dotProduct, hbi, hbj1]; decide
  7. For distinct nonzero vectors a, b in (ZMod 2)^d, four times the size of {x | x ⬝ᵥ a = 0 ∧ x ⬝ᵥ b = 0} equals 2^d.

    Let S be the hyperplane {x | x ⬝ᵥ a = 0}, which has size 2^(d-1). By the preceding lemma, choose x₀ with x₀ ⬝ᵥ a = 0 and x₀ ⬝ᵥ b = 1. Translation by x₀ preserves S and toggles the dot product with b, giving a bijection between {x ∈ S | x ⬝ᵥ b = 0} and {x ∈ S | x ⬝ᵥ b = 1}. These two sets partition S into two equal halves of size 2^(d-2), so four times the size is 2^d.

    lines 127–160

    uses f2_subset_le_four_universal_spectrum_exists_dotProduct_pair, f2_subset_le_four_universal_spectrum_card_hyperplane, f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun, Finset.card_bij, add_dotProduct, add_right_cancel, f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one, add_assoc, add_zero, Finset.card_filter_add_card_filter_not, Finset.filter_filter

      obtain ⟨x0, hx0a, hx0b⟩ := f2_subset_le_four_universal_spectrum_exists_dotProduct_pair d a b ha hb hab
      set s := Finset.univ.filter (fun x => x ⬝ᵥ a = 0) with hs
      have hcard_s : 2 * s.card = 2^d := f2_subset_le_four_universal_spectrum_card_hyperplane d a ha
      have hx00 : x0 + x0 = 0 := f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d x0
      have hbij : (s.filter (fun x => x ⬝ᵥ b = 0)).card = (s.filter (fun x => ¬ (x ⬝ᵥ b = 0))).card := by
        apply Finset.card_bij (fun x _ => x + x0)
        · intro x hx
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, hs] at hx ⊢
          obtain ⟨hxa, hxb⟩ := hx
          refine ⟨?_, ?_⟩
          · rw [add_dotProduct, hxa, hx0a]; decide
          · rw [add_dotProduct, hxb, hx0b]; decide
        · intro x1 _ x2 _ h; exact add_right_cancel h
        · intro y hy
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, hs] at hy
          obtain ⟨hya, hyb⟩ := hy
          have hyb1 : y ⬝ᵥ b = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (y ⬝ᵥ b)).resolve_left hyb
          refine ⟨y + x0, ?_, ?_⟩
          · simp only [Finset.mem_filter, Finset.mem_univ, true_and, hs]
            refine ⟨?_, ?_⟩
            · rw [add_dotProduct, hya, hx0a]; decide
            · rw [add_dotProduct, hyb1, hx0b]; decide
          · show y + x0 + x0 = y
            rw [add_assoc, hx00, add_zero]
      have hpartition : (s.filter (fun x => x ⬝ᵥ b = 0)).card
          + (s.filter (fun x => ¬ (x ⬝ᵥ b = 0))).card = s.card := by
        rw [Finset.card_filter_add_card_filter_not]
      rw [hbij] at hpartition
      have hp0 : 2 * (s.filter (fun x => x ⬝ᵥ b = 0)).card = s.card := by omega
      have hEq : (s.filter (fun x => x ⬝ᵥ b = 0))
          = (Finset.univ.filter (fun x => x ⬝ᵥ a = 0 ∧ x ⬝ᵥ b = 0)) := by
        rw [hs, Finset.filter_filter]
      rw [hEq] at hp0
      omega
  8. When |T| = 1, taking B to be the universe (ZMod 2)^d satisfies |B| * |T| = 2^d and all character sums for distinct pairs in B are nonzero.

    When T = {t}, the universe has size 2^d, so |B| * |T| = 2^d * 1 = 2^d. For distinct b, b' ∈ B, the character sum reduces to the single term (-1)^((b + b') ⬝ᵥ t).val, which is ±1 and therefore nonzero.

    lines 166–171

    uses Finset.card_singleton, mul_one, Finset.card_univ, Fintype.card_fun, ZMod.card, Fintype.card_fin, Finset.sum_singleton, f2_subset_le_four_universal_spectrum_chi_ne_zero

      obtain ⟨t, rfl⟩ := Finset.card_eq_one.mp hT
      refine ⟨Finset.univ, ?_, ?_⟩
      · rw [Finset.card_singleton, mul_one, Finset.card_univ, Fintype.card_fun, ZMod.card, Fintype.card_fin]
      · intro b _ b' _ _
        rw [Finset.sum_singleton]
        exact f2_subset_le_four_universal_spectrum_chi_ne_zero _
  9. When |T| = 2, taking B to be the hyperplane orthogonal to t₁ + t₂ satisfies |B| * |T| = 2^d and all character sums for distinct pairs in B are nonzero.

    Write T = {t₁, t₂} with t₁ ≠ t₂, so t₁ + t₂ ≠ 0. The orthogonal hyperplane B to t₁ + t₂ has cardinality 2^(d-1), so |B| * |T| = 2^d. For any distinct b, b' ∈ B, their sum b + b' is also orthogonal to t₁ + t₂, meaning (b + b') ⬝ᵥ t₁ = (b + b') ⬝ᵥ t₂. Hence the two terms in the character sum are identical, summing to 2 * (±1) = ±2 ≠ 0.

    lines 177–197

    uses f2_subset_le_four_universal_spectrum_add_eq_zero_iff, f2_subset_le_four_universal_spectrum_card_hyperplane, Finset.card_pair, add_dotProduct, add_zero, dotProduct_add, f2_subset_le_four_universal_spectrum_zmod2_add_eq_zero_iff, Finset.sum_pair, f2_subset_le_four_universal_spectrum_chi_ne_zero, mul_ne_zero

      obtain ⟨t1, t2, ht12, rfl⟩ := Finset.card_eq_two.mp hT
      have hv : t1 + t2 ≠ 0 := by
        intro h
        exact ht12 ((f2_subset_le_four_universal_spectrum_add_eq_zero_iff d t1 t2).mp h)
      refine ⟨Finset.univ.filter (fun x => x ⬝ᵥ (t1 + t2) = 0), ?_, ?_⟩
      · have hcard := f2_subset_le_four_universal_spectrum_card_hyperplane d (t1 + t2) hv
        rw [Finset.card_pair ht12]
        omega
      · intro b hb b' hb' hne
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb hb'
        have hx : (b + b') ⬝ᵥ (t1 + t2) = 0 := by rw [add_dotProduct, hb, hb', add_zero]
        have hsum0 : (b + b') ⬝ᵥ t1 + (b + b') ⬝ᵥ t2 = 0 := by
          rw [← dotProduct_add]; exact hx
        have heq : (b + b') ⬝ᵥ t1 = (b + b') ⬝ᵥ t2 :=
          (f2_subset_le_four_universal_spectrum_zmod2_add_eq_zero_iff ((b + b') ⬝ᵥ t1) ((b + b') ⬝ᵥ t2)).mp hsum0
        rw [Finset.sum_pair ht12, heq]
        have hchi := f2_subset_le_four_universal_spectrum_chi_ne_zero ((b + b') ⬝ᵥ t2)
        have hdbl : (-1:ℤ)^((b+b')⬝ᵥt2).val + (-1:ℤ)^((b+b')⬝ᵥt2).val
            = 2 * (-1:ℤ)^((b+b')⬝ᵥt2).val := by ring
        rw [hdbl]
        exact mul_ne_zero (by norm_num) hchi
  10. When |T| = 4, taking B to be the codimension-2 subspace orthogonal to t₁ + t₀ and t₂ + t₀ satisfies |B| * |T| = 2^d and all character sums for distinct pairs in B are nonzero.

    Write T = {t₀, t₁, t₂, t₃} with distinct elements. The vectors t₁ + t₀ and t₂ + t₀ are distinct and nonzero, so their joint orthogonal subspace B has cardinality 2^(d-2), giving |B| * |T| = 2^d. For any b, b' ∈ B, their sum is orthogonal to both vectors, so (b + b') ⬝ᵥ t₁ = (b + b') ⬝ᵥ t₂ = (b + b') ⬝ᵥ t₀. Thus three terms in the character sum are equal to some sign ±1, while the fourth term is ±1. The sum is 3(±1) ± 1 ∈ {±2, ±4}, which is never zero.

    lines 203–237

    uses f2_subset_le_four_universal_spectrum_add_eq_zero_iff, add_right_cancel, f2_subset_le_four_universal_spectrum_card_hyperplane_pair, add_dotProduct, add_zero, add_assoc, f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun, dotProduct_add, zero_add, Finset.sum_insert, Finset.sum_singleton, f2_subset_le_four_universal_spectrum_chi_pm_one

      obtain ⟨t0, t1, t2, t3, h01, h02, h03, h12, h13, h23, rfl⟩ := Finset.card_eq_four.mp hT
      have ha0 : t1 + t0 ≠ 0 := by
        intro h
        exact h01 ((f2_subset_le_four_universal_spectrum_add_eq_zero_iff d t1 t0).mp h).symm
      have hb0 : t2 + t0 ≠ 0 := by
        intro h
        exact h02 ((f2_subset_le_four_universal_spectrum_add_eq_zero_iff d t2 t0).mp h).symm
      have hab : t1 + t0 ≠ t2 + t0 := by
        intro h; exact h12 (add_right_cancel h)
      refine ⟨Finset.univ.filter (fun x => x ⬝ᵥ (t1 + t0) = 0 ∧ x ⬝ᵥ (t2 + t0) = 0), ?_, ?_⟩
      · have hcard := f2_subset_le_four_universal_spectrum_card_hyperplane_pair d (t1 + t0) (t2 + t0) ha0 hb0 hab
        rw [hT]
        omega
      · intro b hb b' hb' hne
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb hb'
        obtain ⟨hba, hbb⟩ := hb
        obtain ⟨hb'a, hb'b⟩ := hb'
        have hxa : (b + b') ⬝ᵥ (t1 + t0) = 0 := by rw [add_dotProduct, hba, hb'a, add_zero]
        have hxb : (b + b') ⬝ᵥ (t2 + t0) = 0 := by rw [add_dotProduct, hbb, hb'b, add_zero]
        have ht1 : (b + b') ⬝ᵥ t1 = (b + b') ⬝ᵥ t0 := by
          have hsplit : t1 = (t1 + t0) + t0 := by
            rw [add_assoc, f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d t0, add_zero]
          rw [hsplit, dotProduct_add, hxa, zero_add]
        have ht2 : (b + b') ⬝ᵥ t2 = (b + b') ⬝ᵥ t0 := by
          have hsplit : t2 = (t2 + t0) + t0 := by
            rw [add_assoc, f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d t0, add_zero]
          rw [hsplit, dotProduct_add, hxb, zero_add]
        rw [Finset.sum_insert, Finset.sum_insert, Finset.sum_insert, Finset.sum_singleton]
        · rw [ht1, ht2]
          rcases f2_subset_le_four_universal_spectrum_chi_pm_one ((b + b') ⬝ᵥ t0) with hp | hp <;>
            rcases f2_subset_le_four_universal_spectrum_chi_pm_one ((b + b') ⬝ᵥ t3) with hq | hq <;>
            rw [hp, hq] <;> norm_num
        · simp [h23]
        · simp [h12, h13]
        · simp [h01, h02, h03]
  11. For any subset T of (ZMod 2)^d of size 1, 2, or 4, there exists B such that |B| * |T| = 2^d and all character sums for distinct pairs in B are nonzero.

    We perform a case split on the cardinality of T (whether it is 1, 2, or 4) and dispatch to the corresponding case lemmas proven above.

    lines 245–248

    uses f2_subset_le_four_universal_spectrum_case_one, f2_subset_le_four_universal_spectrum_case_two, f2_subset_le_four_universal_spectrum_case_four

      rcases hT with h1 | h2 | h4
      · exact f2_subset_le_four_universal_spectrum_case_one d T h1
      · exact f2_subset_le_four_universal_spectrum_case_two d T h2
      · exact f2_subset_le_four_universal_spectrum_case_four d T h4
CharTwo.neg_eq
In any ring of characteristic 2, every element is its own negative: -x = x.
CharTwo.add_self_eq_zero
In any semiring of characteristic 2, adding any element to itself gives zero: x + x = 0.
Fintype.card_fin
The cardinality of Fin n is n.
Fintype.card_fun
The number of functions from α to β is |β|^|α|.
Finset.card_pair
The cardinality of a pair {a, b} of distinct elements is 2.
Finset.card_singleton
The cardinality of a singleton {a} is 1.
Finset.card_univ
The cardinality of the universal finset is the cardinality of the underlying finite type.
Finset.card_filter_add_card_filter_not
For any predicate p on a finset s, the size of s is the sum of the sizes of the elements satisfying p and those not satisfying p.
Finset.card_bij
Two finsets s and t have the same cardinality if there is a bijection between them.
Finset.filter_filter
Filtering twice by predicates p and q is the same as filtering once by their conjunction p ∧ q.
Finset.filter_congr
Two filtered finsets are equal if the predicates are equivalent on the base set.
Finset.sum_singleton
The sum of a function over a singleton {a} is f(a).
Finset.sum_pair
The sum of a function over a two-element set {a, b} with a ≠ b is f(a) + f(b).
Finset.sum_insert
The sum over insert a s (where a ∉ s) is f(a) plus the sum over s.
Pi.add_apply
Pointwise addition of functions evaluated at an argument: (f + g)(i) = f(i) + g(i).
Pi.neg_apply
Pointwise negation of a function: (-f)(i) = -f(i).
Pi.zero_apply
The zero function evaluated at any argument gives zero: 0(i) = 0.
single_dotProduct
The standard basis vector at i dot-producted with v equals x * v(i).
add_dotProduct
Dot product distributes over addition on the left: (u + v) ⬝ᵥ w = u ⬝ᵥ w + v ⬝ᵥ w.
dotProduct_add
Dot product distributes over addition on the right: u ⬝ᵥ (v + w) = u ⬝ᵥ v + u ⬝ᵥ w.
add_right_cancel
In any additive group, a + b = c + b implies a = c.
add_assoc
Associativity of addition: a + b + c = a + (b + c).
add_zero
Adding zero on the right is the identity: a + 0 = a.
zero_add
Adding zero on the left is the identity: 0 + a = a.
mul_one
Multiplying any element by 1 on the right is the identity: a * 1 = a.
mul_ne_zero
The product of two nonzero elements in a domain is nonzero.
one_ne_zero
1 is not equal to 0.
neg_eq_of_add_eq_zero_left
If a + b = 0 in an additive group, then -b = a.
ZMod.card
The cardinality of ZMod n is n.
ZMod.val_lt
The integer value representative of an element in ZMod n is strictly less than n.
ZMod.natCast_zmod_val
The natural cast of the integer representative of a in ZMod n equals a.
f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one
Every element in ZMod 2 is either 0 or 1.
f2_subset_le_four_universal_spectrum_zmod2_add_eq_zero_iff
In ZMod 2, a + b = 0 if and only if a = b.
f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun
In (ZMod 2)^d, every vector satisfies z + z = 0.
f2_subset_le_four_universal_spectrum_neg_eq_self_fun
In (ZMod 2)^d, every vector satisfies -z = z.
f2_subset_le_four_universal_spectrum_add_eq_zero_iff
In (ZMod 2)^d, a + b = 0 if and only if a = b.
f2_subset_le_four_universal_spectrum_chi_ne_zero
For any z ∈ ZMod 2, (-1)^z.val is nonzero (being 1 or -1).
f2_subset_le_four_universal_spectrum_chi_pm_one
For any z ∈ ZMod 2, (-1)^z.val is either 1 or -1.
f2_subset_le_four_universal_spectrum_card_hyperplane
For any nonzero vector v ∈ (ZMod 2)^d, the hyperplane {x | x ⬝ᵥ v = 0} has size 2^(d-1), so twice its size is 2^d.
f2_subset_le_four_universal_spectrum_exists_dotProduct_pair
For any distinct nonzero vectors a, b ∈ (ZMod 2)^d, there exists a vector x with x ⬝ᵥ a = 0 and x ⬝ᵥ b = 1.
f2_subset_le_four_universal_spectrum_card_hyperplane_pair
For distinct nonzero vectors a, b ∈ (ZMod 2)^d, the intersection of their orthogonal hyperplanes has size 2^(d-2), so 4 times its size is 2^d.
f2_subset_le_four_universal_spectrum_case_one
When |T| = 1, taking B to be the entire space (ZMod 2)^d satisfies |B| * |T| = 2^d with nonzero character sums.
f2_subset_le_four_universal_spectrum_case_two
When |T| = 2, taking B to be the orthogonal hyperplane to the sum of the two elements satisfies |B| * |T| = 2^d with nonzero character sums.
f2_subset_le_four_universal_spectrum_case_four
When |T| = 4, taking B to be the codimension-2 subspace orthogonal to t₁ + t₀ and t₂ + t₀ satisfies |B| * |T| = 2^d with nonzero character sums.

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 Matrixlemma f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (c : ZMod 2) :    c = 0 ∨ c = 1 := by  have h : c.val < 2 := ZMod.val_lt c  have hc : ((c.val : ℕ) : ZMod 2) = c := ZMod.natCast_zmod_val c  interval_cases c.val  · left; rw [← hc]; norm_num  · right; rw [← hc]; norm_numlemma f2_subset_le_four_universal_spectrum_zmod2_add_eq_zero_iff (a b : ZMod 2) :    a + b = 0 ↔ a = b := by  constructor  · intro h    rw [← neg_eq_of_add_eq_zero_left h]    exact CharTwo.neg_eq b  · intro h; rw [h]; exact CharTwo.add_self_eq_zero blemma f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun (d : ℕ) (z : Fin d → ZMod 2) :    z + z = 0 := by  funext j; simp only [Pi.add_apply, Pi.zero_apply]; exact CharTwo.add_self_eq_zero (z j)lemma f2_subset_le_four_universal_spectrum_neg_eq_self_fun (d : ℕ) (z : Fin d → ZMod 2) :    -z = z := by  funext j; simp only [Pi.neg_apply]; exact CharTwo.neg_eq (z j)lemma f2_subset_le_four_universal_spectrum_add_eq_zero_iff (d : ℕ)    (a b : Fin d → ZMod 2) : a + b = 0 ↔ a = b := by  constructor  · intro h    rw [← neg_eq_of_add_eq_zero_left h]    exact f2_subset_le_four_universal_spectrum_neg_eq_self_fun d b  · intro h    rw [h]    exact f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d blemma f2_subset_le_four_universal_spectrum_chi_ne_zero (z : ZMod 2) :    (-1 : ℤ) ^ z.val ≠ 0 := by  have h : z.val < 2 := ZMod.val_lt z  interval_cases z.val <;> simplemma f2_subset_le_four_universal_spectrum_chi_pm_one (z : ZMod 2) :    (-1 : ℤ) ^ z.val = 1 ∨ (-1 : ℤ) ^ z.val = -1 := by  have h : z.val < 2 := ZMod.val_lt z  interval_cases z.val  · left; simp  · right; simplemma f2_subset_le_four_universal_spectrum_card_hyperplane (d : ℕ) (v : Fin d → ZMod 2)    (hv : v ≠ 0) :    2 * (Finset.univ.filter (fun x => x ⬝ᵥ v = 0)).card = 2^d := by  obtain ⟨i, hi⟩ : ∃ i, v i ≠ 0 := by    by_contra h    simp only [not_exists, not_not] at h    exact hv (funext h)  have hi1 : v i = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (v i)).resolve_left hi  set e : Fin d → ZMod 2 := Pi.single i 1 with he  have hev : e ⬝ᵥ v = 1 := by rw [he, single_dotProduct]; simp [hi1]  have hee : e + e = 0 := f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d e  have hbij : (Finset.univ.filter (fun x => x ⬝ᵥ v = 0)).card      = (Finset.univ.filter (fun x => x ⬝ᵥ v = 1)).card := by    apply Finset.card_bij (fun x _ => x + e)    · intro x hx      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢      rw [add_dotProduct, hx, hev]; decide    · intro x1 _ x2 _ h      exact add_right_cancel h    · intro y hy      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hy      refine ⟨y + e, ?_, ?_⟩      · simp only [Finset.mem_filter, Finset.mem_univ, true_and]        rw [add_dotProduct, hy, hev]; decide      · show y + e + e = y        rw [add_assoc, hee, add_zero]  have hnot : (Finset.univ.filter (fun x => ¬ (x ⬝ᵥ v = 0)))      = (Finset.univ.filter (fun x => x ⬝ᵥ v = 1)) := by    apply Finset.filter_congr    intro x _    constructor    · intro h; exact (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (x ⬝ᵥ v)).resolve_left h    · intro h h0; rw [h0] at h; exact absurd h (by decide)  have hpart : (Finset.univ.filter (fun x => x ⬝ᵥ v = 0)).card      + (Finset.univ.filter (fun x => ¬ (x ⬝ᵥ v = 0))).card      = Fintype.card (Fin d → ZMod 2) := by    rw [Finset.card_filter_add_card_filter_not, Finset.card_univ]  have hV : Fintype.card (Fin d → ZMod 2) = 2^d := by    rw [Fintype.card_fun, ZMod.card, Fintype.card_fin]  rw [hV, hnot, ← hbij] at hpart  omegalemma f2_subset_le_four_universal_spectrum_exists_dotProduct_pair (d : ℕ)    (a b : Fin d → ZMod 2) (_ha : a ≠ 0) (hb : b ≠ 0) (hab : a ≠ b) :    ∃ x, x ⬝ᵥ a = 0 ∧ x ⬝ᵥ b = 1 := by  by_cases h : ∃ j, b j ≠ 0 ∧ a j = 0  · obtain ⟨j, hbj, haj⟩ := h    refine ⟨Pi.single j 1, ?_, ?_⟩    · rw [single_dotProduct, haj, mul_zero]    · rw [single_dotProduct, one_mul]      exact (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (b j)).resolve_left hbj  · have h' : ∀ j, b j ≠ 0 → a j ≠ 0 := by      intro j hbj haj; exact h ⟨j, hbj, haj⟩    obtain ⟨j, hbj⟩ : ∃ j, b j ≠ 0 := by      by_contra hh; simp only [not_exists, not_not] at hh; exact hb (funext hh)    obtain ⟨i, hi⟩ : ∃ i, a i ≠ b i := by      by_contra hh; simp only [not_exists, not_not] at hh; exact hab (funext hh)    have hbi : b i = 0 := by      rcases f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (b i) with h0 | h1      · exact h0      · exfalso        have hai : a i ≠ 0 := h' i (by rw [h1]; exact one_ne_zero)        have hai1 : a i = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (a i)).resolve_left hai        exact hi (by rw [hai1, h1])    have hai : a i = 1 := by      rcases f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (a i) with h0 | h1      · exact absurd (by rw [h0, hbi] : a i = b i) hi      · exact h1    have haj : a j = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (a j)).resolve_left (h' j hbj)    have hbj1 : b j = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (b j)).resolve_left hbj    have hij : i ≠ j := by intro hij; rw [hij] at hbi; exact hbj hbi    refine ⟨Pi.single i 1 + Pi.single j 1, ?_, ?_⟩    · rw [add_dotProduct, single_dotProduct, single_dotProduct, hai, haj]; decide    · rw [add_dotProduct, single_dotProduct, single_dotProduct, hbi, hbj1]; decidelemma f2_subset_le_four_universal_spectrum_card_hyperplane_pair (d : ℕ)    (a b : Fin d → ZMod 2) (ha : a ≠ 0) (hb : b ≠ 0) (hab : a ≠ b) :    4 * (Finset.univ.filter (fun x => x ⬝ᵥ a = 0 ∧ x ⬝ᵥ b = 0)).card = 2^d := by  obtain ⟨x0, hx0a, hx0b⟩ := f2_subset_le_four_universal_spectrum_exists_dotProduct_pair d a b ha hb hab  set s := Finset.univ.filter (fun x => x ⬝ᵥ a = 0) with hs  have hcard_s : 2 * s.card = 2^d := f2_subset_le_four_universal_spectrum_card_hyperplane d a ha  have hx00 : x0 + x0 = 0 := f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d x0  have hbij : (s.filter (fun x => x ⬝ᵥ b = 0)).card = (s.filter (fun x => ¬ (x ⬝ᵥ b = 0))).card := by    apply Finset.card_bij (fun x _ => x + x0)    · intro x hx      simp only [Finset.mem_filter, Finset.mem_univ, true_and, hs] at hx ⊢      obtain ⟨hxa, hxb⟩ := hx      refine ⟨?_, ?_⟩      · rw [add_dotProduct, hxa, hx0a]; decide      · rw [add_dotProduct, hxb, hx0b]; decide    · intro x1 _ x2 _ h; exact add_right_cancel h    · intro y hy      simp only [Finset.mem_filter, Finset.mem_univ, true_and, hs] at hy      obtain ⟨hya, hyb⟩ := hy      have hyb1 : y ⬝ᵥ b = 1 := (f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one (y ⬝ᵥ b)).resolve_left hyb      refine ⟨y + x0, ?_, ?_⟩      · simp only [Finset.mem_filter, Finset.mem_univ, true_and, hs]        refine ⟨?_, ?_⟩        · rw [add_dotProduct, hya, hx0a]; decide        · rw [add_dotProduct, hyb1, hx0b]; decide      · show y + x0 + x0 = y        rw [add_assoc, hx00, add_zero]  have hpartition : (s.filter (fun x => x ⬝ᵥ b = 0)).card      + (s.filter (fun x => ¬ (x ⬝ᵥ b = 0))).card = s.card := by    rw [Finset.card_filter_add_card_filter_not]  rw [hbij] at hpartition  have hp0 : 2 * (s.filter (fun x => x ⬝ᵥ b = 0)).card = s.card := by omega  have hEq : (s.filter (fun x => x ⬝ᵥ b = 0))      = (Finset.univ.filter (fun x => x ⬝ᵥ a = 0 ∧ x ⬝ᵥ b = 0)) := by    rw [hs, Finset.filter_filter]  rw [hEq] at hp0  omegalemma f2_subset_le_four_universal_spectrum_case_one (d : ℕ) (T : Finset (Fin d → ZMod 2))    (hT : T.card = 1) :    ∃ B : Finset (Fin d → ZMod 2), B.card * T.card = 2^d ∧      ∀ b ∈ B, ∀ b' ∈ B, b ≠ b' → ∑ t ∈ T, (-1:ℤ)^(dotProduct (b+b') t).val ≠ 0 := by  obtain ⟨t, rfl⟩ := Finset.card_eq_one.mp hT  refine ⟨Finset.univ, ?_, ?_⟩  · rw [Finset.card_singleton, mul_one, Finset.card_univ, Fintype.card_fun, ZMod.card, Fintype.card_fin]  · intro b _ b' _ _    rw [Finset.sum_singleton]    exact f2_subset_le_four_universal_spectrum_chi_ne_zero _lemma f2_subset_le_four_universal_spectrum_case_two (d : ℕ) (T : Finset (Fin d → ZMod 2))    (hT : T.card = 2) :    ∃ B : Finset (Fin d → ZMod 2), B.card * T.card = 2^d ∧      ∀ b ∈ B, ∀ b' ∈ B, b ≠ b' → ∑ t ∈ T, (-1:ℤ)^(dotProduct (b+b') t).val ≠ 0 := by  obtain ⟨t1, t2, ht12, rfl⟩ := Finset.card_eq_two.mp hT  have hv : t1 + t2 ≠ 0 := by    intro h    exact ht12 ((f2_subset_le_four_universal_spectrum_add_eq_zero_iff d t1 t2).mp h)  refine ⟨Finset.univ.filter (fun x => x ⬝ᵥ (t1 + t2) = 0), ?_, ?_⟩  · have hcard := f2_subset_le_four_universal_spectrum_card_hyperplane d (t1 + t2) hv    rw [Finset.card_pair ht12]    omega  · intro b hb b' hb' hne    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb hb'    have hx : (b + b') ⬝ᵥ (t1 + t2) = 0 := by rw [add_dotProduct, hb, hb', add_zero]    have hsum0 : (b + b') ⬝ᵥ t1 + (b + b') ⬝ᵥ t2 = 0 := by      rw [← dotProduct_add]; exact hx    have heq : (b + b') ⬝ᵥ t1 = (b + b') ⬝ᵥ t2 :=      (f2_subset_le_four_universal_spectrum_zmod2_add_eq_zero_iff ((b + b') ⬝ᵥ t1) ((b + b') ⬝ᵥ t2)).mp hsum0    rw [Finset.sum_pair ht12, heq]    have hchi := f2_subset_le_four_universal_spectrum_chi_ne_zero ((b + b') ⬝ᵥ t2)    have hdbl : (-1:ℤ)^((b+b')⬝ᵥt2).val + (-1:ℤ)^((b+b')⬝ᵥt2).val        = 2 * (-1:ℤ)^((b+b')⬝ᵥt2).val := by ring    rw [hdbl]    exact mul_ne_zero (by norm_num) hchilemma f2_subset_le_four_universal_spectrum_case_four (d : ℕ) (T : Finset (Fin d → ZMod 2))    (hT : T.card = 4) :    ∃ B : Finset (Fin d → ZMod 2), B.card * T.card = 2^d ∧      ∀ b ∈ B, ∀ b' ∈ B, b ≠ b' → ∑ t ∈ T, (-1:ℤ)^(dotProduct (b+b') t).val ≠ 0 := by  obtain ⟨t0, t1, t2, t3, h01, h02, h03, h12, h13, h23, rfl⟩ := Finset.card_eq_four.mp hT  have ha0 : t1 + t0 ≠ 0 := by    intro h    exact h01 ((f2_subset_le_four_universal_spectrum_add_eq_zero_iff d t1 t0).mp h).symm  have hb0 : t2 + t0 ≠ 0 := by    intro h    exact h02 ((f2_subset_le_four_universal_spectrum_add_eq_zero_iff d t2 t0).mp h).symm  have hab : t1 + t0 ≠ t2 + t0 := by    intro h; exact h12 (add_right_cancel h)  refine ⟨Finset.univ.filter (fun x => x ⬝ᵥ (t1 + t0) = 0 ∧ x ⬝ᵥ (t2 + t0) = 0), ?_, ?_⟩  · have hcard := f2_subset_le_four_universal_spectrum_card_hyperplane_pair d (t1 + t0) (t2 + t0) ha0 hb0 hab    rw [hT]    omega  · intro b hb b' hb' hne    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb hb'    obtain ⟨hba, hbb⟩ := hb    obtain ⟨hb'a, hb'b⟩ := hb'    have hxa : (b + b') ⬝ᵥ (t1 + t0) = 0 := by rw [add_dotProduct, hba, hb'a, add_zero]    have hxb : (b + b') ⬝ᵥ (t2 + t0) = 0 := by rw [add_dotProduct, hbb, hb'b, add_zero]    have ht1 : (b + b') ⬝ᵥ t1 = (b + b') ⬝ᵥ t0 := by      have hsplit : t1 = (t1 + t0) + t0 := by        rw [add_assoc, f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d t0, add_zero]      rw [hsplit, dotProduct_add, hxa, zero_add]    have ht2 : (b + b') ⬝ᵥ t2 = (b + b') ⬝ᵥ t0 := by      have hsplit : t2 = (t2 + t0) + t0 := by        rw [add_assoc, f2_subset_le_four_universal_spectrum_add_self_eq_zero_fun d t0, add_zero]      rw [hsplit, dotProduct_add, hxb, zero_add]    rw [Finset.sum_insert, Finset.sum_insert, Finset.sum_insert, Finset.sum_singleton]    · rw [ht1, ht2]      rcases f2_subset_le_four_universal_spectrum_chi_pm_one ((b + b') ⬝ᵥ t0) with hp | hp <;>        rcases f2_subset_le_four_universal_spectrum_chi_pm_one ((b + b') ⬝ᵥ t3) with hq | hq <;>        rw [hp, hq] <;> norm_num    · simp [h23]    · simp [h12, h13]    · simp [h01, h02, h03]open scoped Matrix in/-- Existence of a dual spectrum avoiding character zeros for subsets of size 1, 2, or 4 in (ZMod 2)^d. -/theorem f2_subset_le_four_universal_spectrum (d : ℕ)    (T : Finset (Fin d → ZMod 2)) (hT : T.card = 1 ∨ T.card = 2 ∨ T.card = 4) :    ∃ B : Finset (Fin d → ZMod 2), B.card * T.card = 2 ^ d ∧      ∀ b ∈ B, ∀ b' ∈ B, b ≠ b' → ∑ t ∈ T, (-1 : ℤ) ^ (dotProduct (b + b') t).val ≠ 0 := by  rcases hT with h1 | h2 | h4  · exact f2_subset_le_four_universal_spectrum_case_one d T h1  · exact f2_subset_le_four_universal_spectrum_case_two d T h2  · exact f2_subset_le_four_universal_spectrum_case_four d T h4
See it in the graphDiscuss this resultChallenge it