hamming_norm_add_eq
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
- hamming_norm_sum_two_degree_six_monomialsLet I and J be two 6-element subsets of Fin 12. Then the Hamming norm of the sum of the corresponding coordinate monomials monomial I +…
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|$.
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`.
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
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`.
lemma hamming_norm_add_eq_zmod2_mul (x y : ZMod 2) : (x * y ≠ 0) ↔ (x ≠ 0 ∧ y ≠ 0) := by revert x y decide
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`.
classical let s : Finset α := Finset.univ.filter (fun i => f i ≠ 0) let t : Finset α := Finset.univ.filter (fun i => g i ≠ 0)
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`.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_symmDiff,Pi.add_apply,hamming_norm_add_eq_zmod2_add,not_nothave 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
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$.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_inter,Pi.mul_apply,hamming_norm_add_eq_zmod2_mulhave 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]
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|$.
uses
Finset.symmDiff_def,Finset.card_union_of_disjoint,disjoint_sdiff_sdiff,Finset.card_sdiff_add_card_inter,Finset.inter_commhave 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
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.
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$.
- The definitions of `hamming_norm_add_eq_zmod2_add` and `hamming_norm_add_eq_zmod2_mul` are proved by finite exhaustive case-checking (`decide`) over `ZMod 2`.
- In step 6, `omega` automatically discharges the linear integer/natural arithmetic step that derives $|s \mathbin{\Delta} t| = |s| + |t| - 2|s \cap t|$ from $|s| = |s \setminus t| + |s \cap t|$ and $|t| = |t \setminus s| + |s \cap t|$.
- `hammingNorm` is defined in Mathlib directly as the cardinality of the support set `{i | f i ≠ 0}`, which enables the theorem to reduce immediately to an inclusion-exclusion formula on finite sets.
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.
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