AFTD Auto-Formalizing Theoretical Domains

hamming_norm_add_eq

theoremverified

For any finite type α and any two Boolean functions f, g : α → ZMod 2, the Hamming norm of their pointwise sum f + g equals hammingNorm f + hammingNorm g - 2 * hammingNorm (f * g).

Statement

theorem hamming_norm_add_eq {α : Type*} [Fintype α]
    (f g : α → ZMod 2) :
    hammingNorm (f + g) = hammingNorm f + hammingNorm g - 2 * hammingNorm (f * g)
Source
arXiv:2610.29807, Lemma 3.2: Some Results on the Weight Spectrum of Binary Reed-Muller Codes RM(m-7,m)
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any finite type α and any functions f, g : α → ZMod 2, the Hamming norm of their pointwise sum f + g is equal to the Hamming norm of f plus the Hamming norm of g minus twice the Hamming norm of their pointwise product f * g, where the operations on the Hamming norms are in ℕ (with truncated natural subtraction). (Note: The definition g from the knowledge base is shadowed by the bound variable g : α → ZMod 2 and is not used in this theorem.)

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 Hamming norm of a function to `ZMod 2` is the cardinality of its support. For Boolean functions $f$ and $g$, the support of their pointwise sum $f + g$ is the symmetric difference of their supports, because addition in `ZMod 2` is non-zero if and only if exactly one summand is non-zero. Similarly, the support of their pointwise product $f \cdot g$ is the intersection of their supports. The Hamming norm relation then reduces to the standard inclusion-exclusion identity for the size of a symmetric difference, $|s \mathbin{\Delta} t| = |s| + |t| - 2|s \cap t|$.

  1. In `ZMod 2`, a sum is non-zero if and only if exactly one term is non-zero. automation

    The helper lemma `hamming_norm_add_eq_zmod2_add` is proved by finite exhaustion using `decide`, checking all four pairs of values in `ZMod 2`.

    lines 1–4

    lemma hamming_norm_add_eq_zmod2_add (x y : ZMod 2) :
        (x + y ≠ 0) ↔ (x ≠ 0 ∧ y = 0) ∨ (x = 0 ∧ y ≠ 0) := by
      revert x y
      decide
  2. In `ZMod 2`, a product is non-zero if and only if both factors are non-zero. automation

    The helper lemma `hamming_norm_add_eq_zmod2_mul` is likewise proved by `decide`, exhaustively verifying all four pairs in `ZMod 2`.

    lines 6–9

    lemma hamming_norm_add_eq_zmod2_mul (x y : ZMod 2) :
        (x * y ≠ 0) ↔ (x ≠ 0 ∧ y ≠ 0) := by
      revert x y
      decide
  3. Let $s$ and $t$ be the supports of $f$ and $g$.

    Assuming classical logic, we define $s$ as the finset of indices $i \in \alpha$ where $f(i) \neq 0$, and $t$ as the finset where $g(i) \neq 0$, each obtained by filtering `Finset.univ`.

    lines 15–17

      classical
      let s : Finset α := Finset.univ.filter (fun i => f i ≠ 0)
      let t : Finset α := Finset.univ.filter (fun i => g i ≠ 0)
  4. The support of the pointwise sum $f + g$ is the symmetric difference $s \mathbin{\Delta} t$.

    By extensionality on $i \in \alpha$, $(f + g)(i) \neq 0$ unfolds to $f(i) + g(i) \neq 0$. By `hamming_norm_add_eq_zmod2_add`, this is equivalent to $(f(i) \neq 0 \wedge g(i) = 0) \vee (f(i) = 0 \wedge g(i) \neq 0)$, which simplifies via propositional logic (`tauto`) and double negation elimination to membership in the symmetric difference `symmDiff s t`.

    lines 18–22

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_symmDiff, Pi.add_apply, hamming_norm_add_eq_zmod2_add, not_not

      have h_add_set : Finset.univ.filter (fun i => (f + g) i ≠ 0) = symmDiff s t := by
        ext i
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_symmDiff,
          Pi.add_apply, hamming_norm_add_eq_zmod2_add, s, t, not_not]
        tauto
  5. The support of the pointwise product $f \cdot g$ is the intersection $s \cap t$.

    By extensionality, an index $i$ belongs to the support of $f \cdot g$ if and only if $(f \cdot g)(i) \neq 0$. Unfolding pointwise multiplication and rewriting with `hamming_norm_add_eq_zmod2_mul`, this is equivalent to $f(i) \neq 0 \wedge g(i) \neq 0$, which matches the definition of $i \in s \cap t$.

    lines 23–26

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_inter, Pi.mul_apply, hamming_norm_add_eq_zmod2_mul

      have h_mul_set : Finset.univ.filter (fun i => (f * g) i ≠ 0) = s ∩ t := by
        ext i
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_inter,
          Pi.mul_apply, hamming_norm_add_eq_zmod2_mul, s, t]
  6. The cardinality of the symmetric difference satisfies $|s \mathbin{\Delta} t| = |s| + |t| - 2|s \cap t|$.

    Since $s \mathbin{\Delta} t = (s \setminus t) \cup (t \setminus s)$ and the two parts are disjoint (`disjoint_sdiff_sdiff`), its cardinality is $|s \setminus t| + |t \setminus s|$. Decomposing $|s| = |s \setminus t| + |s \cap t|$ and $|t| = |t \setminus s| + |t \cap s|$ via `Finset.card_sdiff_add_card_inter`, and noting that $t \cap s = s \cap t$, the linear arithmetic solver `omega` proves the identity $|s \mathbin{\Delta} t| = |s| + |t| - 2|s \cap t|$.

    lines 27–33

    uses Finset.symmDiff_def, Finset.card_union_of_disjoint, disjoint_sdiff_sdiff, Finset.card_sdiff_add_card_inter, Finset.inter_comm

      have h_card : (symmDiff s t).card = s.card + t.card - 2 * (s ∩ t).card := by
        have h1 : (symmDiff s t).card = (s \ t).card + (t \ s).card := by
          rw [Finset.symmDiff_def, Finset.card_union_of_disjoint disjoint_sdiff_sdiff]
        have h2 := Finset.card_sdiff_add_card_inter s t
        have h3 := Finset.card_sdiff_add_card_inter t s
        rw [Finset.inter_comm t s] at h3
        omega
  7. The Hamming norm identity $\text{hammingNorm}(f + g) = \text{hammingNorm}(f) + \text{hammingNorm}(g) - 2 \cdot \text{hammingNorm}(f \cdot g)$ holds.

    The Hamming norm is by definition the cardinality of the support set. Rewriting the support of $f + g$ to $s \mathbin{\Delta} t$ and the support of $f \cdot g$ to $s \cap t$ turns the goal into $(s \mathbin{\Delta} t).\text{card} = s.\text{card} + t.\text{card} - 2 * (s \cap t).\text{card}$, which is precisely the cardinality identity established above.

    lines 34–37

      change (Finset.univ.filter (fun i => (f + g) i ≠ 0)).card =
        s.card + t.card - 2 * (Finset.univ.filter (fun i => (f * g) i ≠ 0)).card
      rw [h_add_set, h_mul_set]
      exact h_card
hamming_norm_add_eq_zmod2_add
In `ZMod 2`, a sum $x + y$ is non-zero if and only if exactly one of $x$ or $y$ is non-zero.
hamming_norm_add_eq_zmod2_mul
In `ZMod 2`, a product $x \cdot y$ is non-zero if and only if both $x \neq 0$ and $y \neq 0$.
Finset.mem_filter
An element $a$ belongs to `Finset.filter p s` if and only if $a \in s$ and $p(a)$ holds.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and
A conjunction `True ∧ p` is logically equivalent to `p`.
Finset.mem_symmDiff
An element belongs to the symmetric difference `symmDiff s t` if and only if it belongs to $s$ but not $t$, or to $t$ but not $s$.
Pi.add_apply
Function addition is defined pointwise: $(f + g)(i) = f(i) + g(i)$.
not_not
Double negation elimination: $\neg\neg a \leftrightarrow a$.
Finset.mem_inter
An element belongs to the intersection $s_1 \cap s_2$ if and only if it belongs to both $s_1$ and $s_2$.
Pi.mul_apply
Function multiplication is defined pointwise: $(f \cdot g)(i) = f(i) \cdot g(i)$.
Finset.symmDiff_def
The symmetric difference of two finsets is the union of their differences: $s \mathbin{\Delta} t = (s \setminus t) \cup (t \setminus s)$.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
disjoint_sdiff_sdiff
For any sets $x$ and $y$, the differences $x \setminus y$ and $y \setminus x$ are disjoint.
Finset.card_sdiff_add_card_inter
For any finsets $s$ and $t$, the size of their difference plus the size of their intersection equals the size of $s$: $|s \setminus t| + |s \cap t| = |s|$.
Finset.inter_comm
Finset intersection is commutative: $s_1 \cap s_2 = s_2 \cap s_1$.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma hamming_norm_add_eq_zmod2_add (x y : ZMod 2) :    (x + y ≠ 0) ↔ (x ≠ 0 ∧ y = 0) ∨ (x = 0 ∧ y ≠ 0) := by  revert x y  decidelemma hamming_norm_add_eq_zmod2_mul (x y : ZMod 2) :    (x * y ≠ 0) ↔ (x ≠ 0 ∧ y ≠ 0) := by  revert x y  decide/-- Inclusion-exclusion for the Hamming norm of the sum of two Boolean functions. -/theorem hamming_norm_add_eq {α : Type*} [Fintype α]    (f g : α → ZMod 2) :    hammingNorm (f + g) = hammingNorm f + hammingNorm g - 2 * hammingNorm (f * g) := by  classical  let s : Finset α := Finset.univ.filter (fun i => f i ≠ 0)  let t : Finset α := Finset.univ.filter (fun i => g i ≠ 0)  have h_add_set : Finset.univ.filter (fun i => (f + g) i ≠ 0) = symmDiff s t := by    ext i    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_symmDiff,      Pi.add_apply, hamming_norm_add_eq_zmod2_add, s, t, not_not]    tauto  have h_mul_set : Finset.univ.filter (fun i => (f * g) i ≠ 0) = s ∩ t := by    ext i    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_inter,      Pi.mul_apply, hamming_norm_add_eq_zmod2_mul, s, t]  have h_card : (symmDiff s t).card = s.card + t.card - 2 * (s ∩ t).card := by    have h1 : (symmDiff s t).card = (s \ t).card + (t \ s).card := by      rw [Finset.symmDiff_def, Finset.card_union_of_disjoint disjoint_sdiff_sdiff]    have h2 := Finset.card_sdiff_add_card_inter s t    have h3 := Finset.card_sdiff_add_card_inter t s    rw [Finset.inter_comm t s] at h3    omega  change (Finset.univ.filter (fun i => (f + g) i ≠ 0)).card =    s.card + t.card - 2 * (Finset.univ.filter (fun i => (f * g) i ≠ 0)).card  rw [h_add_set, h_mul_set]  exact h_card
See it in the graphDiscuss this resultChallenge it