f2_subset_le_four_universal_spectrum
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.
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.
uses
ZMod.val_lt,ZMod.natCast_zmod_valhave 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
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.
uses
neg_eq_of_add_eq_zero_left,CharTwo.neg_eq,CharTwo.add_self_eq_zeroconstructor · 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
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.
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_funfunext 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
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.
uses
ZMod.val_lthave 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
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.
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_finobtain ⟨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
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.
uses
single_dotProduct,f2_subset_le_four_universal_spectrum_zmod2_eq_zero_or_one,one_ne_zero,add_dotProductby_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
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.
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_filterobtain ⟨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
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.
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_zeroobtain ⟨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 _
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.
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_zeroobtain ⟨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
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.
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_oneobtain ⟨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]
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.
uses
f2_subset_le_four_universal_spectrum_case_one,f2_subset_le_four_universal_spectrum_case_two,f2_subset_le_four_universal_spectrum_case_fourrcases 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
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.
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