AFTD Auto-Formalizing Theoretical Domains

tile_walsh_mul_eq_zero

theoremverifiedformalization

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

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.

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

    lines 5–6

      revert a b
      decide
  2. Every 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.

    lines 9–10

      revert a ha
      decide
  3. There 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.

    lines 14–21

    uses tile_walsh_mul_eq_zero_zmod2_eq_one_of_ne_zero, Equiv.addRight

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

    lines 22–31

    uses Equiv.sum_comp, dotProduct_add, dotProduct_single, mul_one, tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add

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

    lines 32–34

    uses Fintype.sum_congr, Finset.sum_neg_distrib

      rw [Fintype.sum_congr _ _ hterm] at hsum
      rw [Finset.sum_neg_distrib] at hsum
      linarith
  6. 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.

    lines 38–40

    uses Finset.mem_image, Finset.mem_product, Finset.mem_add, Prod.exists

      ext x
      simp only [Finset.mem_image, Finset.mem_product, Finset.mem_add, Prod.exists]
      tauto
  7. 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.

    lines 48–54

    uses Finset.sum_mul_sum, Finset.sum_product', Finset.sum_congr, dotProduct_add, tile_walsh_mul_eq_zero_zmod2_neg_one_pow_add

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

    lines 55–60

    uses tile_walsh_mul_eq_zero_image_add_eq, Finset.card_product, Finset.card_image_iff

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

    lines 61–64

    uses Finset.sum_image, tile_walsh_mul_eq_zero_sum_univ

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

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