tile_walsh_mul_eq_zero
Let E and T be subsets of Fin d → ZMod 2 such that E + T is the universal set and |E| * |T| = 2^d. For every nonzero vector u : Fin d → ZMod 2, the product of the character sums (∑ e ∈ E, (-1 : ℤ) ^ (dotProduct u e).val) and (∑ t ∈ T, (-1 : ℤ) ^ (dotProduct u t).val) is equal to 0.
Statement
open scoped Pointwise Matrix in theorem tile_walsh_mul_eq_zero {d : ℕ} (E T : Finset (Fin d → ZMod 2)) (hET : E + T = Finset.univ) (hcard : E.card * T.card = 2 ^ d) (u : Fin d → ZMod 2) (hu : u ≠ 0) : (∑ e ∈ E, (-1 : ℤ) ^ (dotProduct u e).val) * (∑ t ∈ T, (-1 : ℤ) ^ (dotProduct u t).val) = 0
- Formalizes
- arXiv:2610.24022, equation (2.2)
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
Read back from the Lean
For any natural number $d$, and any two finite subsets $E, T \subseteq (\mathrm{Fin}\ d \to \mathbb{Z}/2\mathbb{Z})$, if the Minkowski sum $E + T$ equals the universal set $(\mathrm{Fin}\ d \to \mathbb{Z}/2\mathbb{Z})$ and the product of their cardinalities is $|E| \cdot |T| = 2^d$, then for every non-zero vector $u : \mathrm{Fin}\ d \to \mathbb{Z}/2\mathbb{Z}$, the product of the Walsh-Hadamard sums of $E$ and $T$ at $u$ vanishes: $$\left( \sum_{e \in E} (-1)^{(u \cdot e)\mathrm{.val}} \right) \cdot \left( \sum_{t \in T} (-1)^{(u \cdot t)\mathrm{.val}} \right) = 0,$$ where $u \cdot x = \sum_{i \in \mathrm{Fin}\ d} u(i)x(i) \in \mathbb{Z}/2\mathbb{Z}$ is the standard dot product, and $\mathrm{.val}$ takes the representative in $\{0, 1\} \subset \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 product of character sums over E and T expands into a sum of (-1)^(u ⬝ᵥ (e + t)) over the Cartesian product E ×ˢ T. Since E + T tiles (ZMod 2)^d and |E| * |T| = 2^d, the addition map (e, t) ↦ e + t is a bijection from E ×ˢ T onto the universal set. Re-indexing along this bijection transforms the sum into the full character sum over all of (ZMod 2)^d. Translating along a coordinate where u is nonzero negates every term of this full sum, proving that it equals 0.
The map x ↦ (-1)^x.val on ZMod 2 is a multiplicative character, turning addition into multiplication.
The identity is verified by exhaustive check over all pairs (a, b) ∈ (ZMod 2) × (ZMod 2).
revert a b decideEvery nonzero element in ZMod 2 is 1.
Since ZMod 2 contains only 0 and 1, any element not equal to 0 is 1, verified by decision procedure.
revert a ha decideThere is a coordinate j where u j = 1, giving a translation vector c = Pi.single j 1 and a permutation e(x) = x + c.
By contradiction, if all components of u were 0, then u would be the zero vector, contradicting hu. Thus some component u j is nonzero, and by tile_walsh_mul_eq_zero_zmod2_eq_one_of_ne_zero it equals 1. Defining c to be the standard basis vector at j and e to be translation by c (Equiv.addRight) gives a permutation of the space.
uses
tile_walsh_mul_eq_zero_zmod2_eq_one_of_ne_zero,Equiv.addRighthave ⟨j, hj⟩ : ∃ j, u j ≠ 0 := by by_contra! h apply hu ext j exact h j have huj : u j = 1 := tile_walsh_mul_eq_zero_zmod2_eq_one_of_ne_zero (u j) hj let c : Fin d → ZMod 2 := Pi.single j 1 let e := Equiv.addRight c
Translating by c preserves the sum over the space while negating every term.
Re-indexing the sum by the equivalence e preserves the total sum by Equiv.sum_comp. Expanding the dot product using dotProduct_add and dotProduct_single, the dot product u ⬝ᵥ (x + c) evaluates to u ⬝ᵥ x + u j * 1 = u ⬝ᵥ x + 1 via mul_one. By tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add, (-1)^(u ⬝ᵥ x + 1).val factors as (-1)^(u ⬝ᵥ x).val * (-1)^1, which simplifies to -(-1)^(u ⬝ᵥ x).val.
uses
Equiv.sum_comp,dotProduct_add,dotProduct_single,mul_one,tile_walsh_mul_eq_zero_zmod2_neg_one_pow_addhave hsum : ∑ x, (-1 : ℤ) ^ (dotProduct u x).val = ∑ x, (-1 : ℤ) ^ (dotProduct u (e x)).val := (Equiv.sum_comp e _).symm have hterm (x : Fin d → ZMod 2) : (-1 : ℤ) ^ (dotProduct u (e x)).val = - (-1 : ℤ) ^ (dotProduct u x).val := by dsimp [e, c] rw [dotProduct_add, dotProduct_single, huj, mul_one] rw [tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add] have : (1 : ZMod 2).val = 1 := rfl rw [this] ring
The Walsh character sum over the universal set vanishes for any nonzero vector u.
Congruence of sums (Fintype.sum_congr) and distributing the negation (Finset.sum_neg_distrib) shows that the sum S satisfies S = -S. Linear arithmetic (linarith) yields S = 0.
uses
Fintype.sum_congr,Finset.sum_neg_distribrw [Fintype.sum_congr _ _ hterm] at hsum rw [Finset.sum_neg_distrib] at hsum linarith
The image of E ×ˢ T under vector addition is the sumset E + T.
Extensionality on finsets reduces the claim to an element-level equivalence. Unfolding the definitions of finset image, product, and sumset (Finset.mem_image, Finset.mem_product, Finset.mem_add, Prod.exists) leaves an equivalence established by propositional logic.
uses
Finset.mem_image,Finset.mem_product,Finset.mem_add,Prod.existsext x simp only [Finset.mem_image, Finset.mem_product, Finset.mem_add, Prod.exists] tauto
The product of the character sums over E and T equals the sum of (-1)^(u ⬝ᵥ (p.1 + p.2)).val over p ∈ E ×ˢ T.
Expanding the product of sums via Finset.sum_mul_sum and Finset.sum_product' converts the product into a sum of (-1)^(u ⬝ᵥ p.1).val * (-1)^(u ⬝ᵥ p.2).val over p ∈ E ×ˢ T. Applying dotProduct_add and tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add inside the sum (Finset.sum_congr) combines the product into a single term (-1)^(u ⬝ᵥ (p.1 + p.2)).val.
uses
Finset.sum_mul_sum,Finset.sum_product',Finset.sum_congr,dotProduct_add,tile_walsh_mul_eq_zero_zmod2_neg_one_pow_addrw [Finset.sum_mul_sum, ← Finset.sum_product'] have hsum : ∑ p ∈ E ×ˢ T, (-1 : ℤ) ^ (dotProduct u p.1).val * (-1 : ℤ) ^ (dotProduct u p.2).val = ∑ p ∈ E ×ˢ T, (-1 : ℤ) ^ (dotProduct u (p.1 + p.2)).val := by apply Finset.sum_congr rfl intro p _ rw [dotProduct_add, tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add] rw [hsum]
The addition map f(p) = p.1 + p.2 maps E ×ˢ T onto the universal set and is injective on E ×ˢ T.
By tile_walsh_mul_eq_zero_image_add_eq and the tiling hypothesis E + T = Finset.univ, the image of E ×ˢ T under f is the entire space, which has cardinality 2^d. Since the cardinality of E ×ˢ T is also |E| * |T| = 2^d (by Finset.card_product and hcard), the image has the same cardinality as the domain, so f is injective on E ×ˢ T by Finset.card_image_iff.
uses
tile_walsh_mul_eq_zero_image_add_eq,Finset.card_product,Finset.card_image_ifflet f : (Fin d → ZMod 2) × (Fin d → ZMod 2) → (Fin d → ZMod 2) := fun p => p.1 + p.2 have himage : (E ×ˢ T).image f = Finset.univ := by rw [tile_walsh_mul_eq_zero_image_add_eq, hET] have hcard_univ : (Finset.univ : Finset (Fin d → ZMod 2)).card = 2 ^ d := by simp have hinj : Set.InjOn f ↑(E ×ˢ T) := by rw [← Finset.card_image_iff, himage, hcard_univ, Finset.card_product, hcard]
The character product is 0.
Because f is injective on E ×ˢ T, Finset.sum_image re-indexes the sum over E ×ˢ T into the full character sum over its image, the universal set. Since u ≠ 0, this sum is 0 by tile_walsh_mul_eq_zero_sum_univ.
uses
Finset.sum_image,tile_walsh_mul_eq_zero_sum_univhave hsum_univ := @Finset.sum_image _ _ ℤ _ (fun x => (-1 : ℤ) ^ (dotProduct u x).val) _ (E ×ˢ T) f hinj rw [himage] at hsum_univ rw [← hsum_univ] exact tile_walsh_mul_eq_zero_sum_univ u hu
tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add- The character map x ↦ (-1)^x.val on ZMod 2 sends addition to integer multiplication: (-1)^(a+b).val = (-1)^a.val * (-1)^b.val.
tile_walsh_mul_eq_zero_zmod2_eq_one_of_ne_zero- The only nonzero element in ZMod 2 is 1.
tile_walsh_mul_eq_zero_sum_univ- For any nonzero vector u in (ZMod 2)^d, the character sum ∑ x, (-1)^(u ⬝ᵥ x).val over the entire space equals 0.
tile_walsh_mul_eq_zero_image_add_eq- The image of the Cartesian product E ×ˢ T under the addition map (e, t) ↦ e + t is the sumset E + T.
Equiv.addRight- Right addition by an element in an additive group is an equivalence (permutation) of the group.
Equiv.sum_comp- Summing over a finite domain is invariant under precomposition with an equivalence.
dotProduct_add- The dot product distributes over addition: u ⬝ᵥ (v + w) = u ⬝ᵥ v + u ⬝ᵥ w.
dotProduct_single- The dot product of a vector v with the coordinate vector Pi.single i x equals v i * x.
mul_one- Multiplying by 1 on the right is the identity: a * 1 = a.
Fintype.sum_congr- Two sums over the same finite type are equal if their terms are pointwise equal.
Finset.sum_neg_distrib- Summation distributes over negation: ∑ x ∈ s, -f x = -∑ x ∈ s, f x.
Finset.mem_image- An element b is in the image of a finset s under f if and only if b = f a for some a ∈ s.
Finset.mem_product- A pair p is in the Cartesian product s ×ˢ t if and only if p.1 ∈ s and p.2 ∈ t.
Finset.mem_add- An element x is in the sumset s + t if and only if x = y + z for some y ∈ s and z ∈ t.
Prod.exists- An existential statement over pairs is equivalent to an existential statement over each component.
Finset.sum_mul_sum- The product of two sums equals the sum of the products of each pair of terms.
Finset.sum_product'- A double sum over two finsets is equal to the sum over their Cartesian product.
Finset.sum_congr- Two finset sums are equal if their index sets are equal and their summands agree on that set.
Finset.card_product- The cardinality of a Cartesian product of finsets is the product of their cardinalities.
Finset.card_image_iff- The image of a finset under a map has the same cardinality as the finset if and only if the map is injective on the finset.
Finset.sum_image- If g is injective on a finset s, the sum of f over the image of s under g equals the sum of f ∘ g over s.
- In Lean, characters with values in {±1} are formalized using integer powers of -1, specifically (-1 : ℤ) ^ x.val for x : ZMod 2, which requires explicit lemmas connecting addition in ZMod 2 to multiplication in ℤ.
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 Pointwise Matrixlemma tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add (a b : ZMod 2) : (-1 : ℤ) ^ (a + b).val = (-1 : ℤ) ^ a.val * (-1 : ℤ) ^ b.val := by revert a b decidelemma tile_walsh_mul_eq_zero_zmod2_eq_one_of_ne_zero (a : ZMod 2) (ha : a ≠ 0) : a = 1 := by revert a ha decidelemma tile_walsh_mul_eq_zero_sum_univ {d : ℕ} (u : Fin d → ZMod 2) (hu : u ≠ 0) : ∑ x : Fin d → ZMod 2, (-1 : ℤ) ^ (dotProduct u x).val = 0 := by have ⟨j, hj⟩ : ∃ j, u j ≠ 0 := by by_contra! h apply hu ext j exact h j have huj : u j = 1 := tile_walsh_mul_eq_zero_zmod2_eq_one_of_ne_zero (u j) hj let c : Fin d → ZMod 2 := Pi.single j 1 let e := Equiv.addRight c have hsum : ∑ x, (-1 : ℤ) ^ (dotProduct u x).val = ∑ x, (-1 : ℤ) ^ (dotProduct u (e x)).val := (Equiv.sum_comp e _).symm have hterm (x : Fin d → ZMod 2) : (-1 : ℤ) ^ (dotProduct u (e x)).val = - (-1 : ℤ) ^ (dotProduct u x).val := by dsimp [e, c] rw [dotProduct_add, dotProduct_single, huj, mul_one] rw [tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add] have : (1 : ZMod 2).val = 1 := rfl rw [this] ring rw [Fintype.sum_congr _ _ hterm] at hsum rw [Finset.sum_neg_distrib] at hsum linarithlemma tile_walsh_mul_eq_zero_image_add_eq {d : ℕ} (E T : Finset (Fin d → ZMod 2)) : (E ×ˢ T).image (fun p => p.1 + p.2) = E + T := by ext x simp only [Finset.mem_image, Finset.mem_product, Finset.mem_add, Prod.exists] tautoopen scoped Pointwise Matrix in/-- Convolution orthogonality of character sums for translational tiling pairs in (ZMod 2)^d. -/theorem tile_walsh_mul_eq_zero {d : ℕ} (E T : Finset (Fin d → ZMod 2)) (hET : E + T = Finset.univ) (hcard : E.card * T.card = 2 ^ d) (u : Fin d → ZMod 2) (hu : u ≠ 0) : (∑ e ∈ E, (-1 : ℤ) ^ (dotProduct u e).val) * (∑ t ∈ T, (-1 : ℤ) ^ (dotProduct u t).val) = 0 := by rw [Finset.sum_mul_sum, ← Finset.sum_product'] have hsum : ∑ p ∈ E ×ˢ T, (-1 : ℤ) ^ (dotProduct u p.1).val * (-1 : ℤ) ^ (dotProduct u p.2).val = ∑ p ∈ E ×ˢ T, (-1 : ℤ) ^ (dotProduct u (p.1 + p.2)).val := by apply Finset.sum_congr rfl intro p _ rw [dotProduct_add, tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add] rw [hsum] let f : (Fin d → ZMod 2) × (Fin d → ZMod 2) → (Fin d → ZMod 2) := fun p => p.1 + p.2 have himage : (E ×ˢ T).image f = Finset.univ := by rw [tile_walsh_mul_eq_zero_image_add_eq, hET] have hcard_univ : (Finset.univ : Finset (Fin d → ZMod 2)).card = 2 ^ d := by simp have hinj : Set.InjOn f ↑(E ×ˢ T) := by rw [← Finset.card_image_iff, himage, hcard_univ, Finset.card_product, hcard] have hsum_univ := @Finset.sum_image _ _ ℤ _ (fun x => (-1 : ℤ) ^ (dotProduct u x).val) _ (E ×ˢ T) f hinj rw [himage] at hsum_univ rw [← hsum_univ] exact tile_walsh_mul_eq_zero_sum_univ u hu