hamming_norm_monomial
For any natural number s and any finite subset T of Fin s, the Hamming norm of the coordinate monomial monomial T as a function from (Fin s → ZMod 2) to ZMod 2 is equal to 2 ^ (s - T.card).
Statement
theorem hamming_norm_monomial {s : ℕ} (T : Finset (Fin s)) :
hammingNorm (monomial T : (Fin s → ZMod 2) → ZMod 2) = 2 ^ (s - T.card)- 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- Built on 2
- 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 natural number s and any subset T : Finset (Fin s), the Hamming norm of the function monomial T : (Fin s → ZMod 2) → ZMod 2 is equal to 2 ^ (s - T.card).
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 is the number of inputs where it evaluates to a non-zero value. For the coordinate monomial indexed by T, the product over T is non-zero in ZMod 2 if and only if each coordinate in T is equal to 1. Fixing these |T| coordinates leaves the remaining s - |T| coordinates unconstrained, yielding an equivalence with the space of functions from the complement of T into ZMod 2, whose cardinality is 2 ^ (s - |T|).
The coordinate monomial indexed by T evaluates to a non-zero value at x if and only if x i = 1 for all i ∈ T.
Unfolding monomial as a product over T, Finset.prod_ne_zero_iff asserts that the product is non-zero if and only if every factor x i is non-zero. In ZMod 2, the only non-zero element is 1, so each condition x i ≠ 0 is equivalent to x i = 1.
uses
Finset.prod_ne_zero_ifflemma hamming_norm_monomial_ne_zero_iff {s : ℕ} (T : Finset (Fin s)) (x : Fin s → ZMod 2) : monomial T x ≠ 0 ↔ ∀ i ∈ T, x i = 1 := by change (∏ i ∈ T, x i) ≠ 0 ↔ ∀ i ∈ T, x i = 1 rw [Finset.prod_ne_zero_iff] simp_rw [show ∀ y : ZMod 2, y ≠ 0 ↔ y = 1 from fun y => by revert y; decide]
Restricting a vector to coordinates outside T has a well-defined inverse that sets coordinates in T to 1, which acts as a left inverse.
We define the forward map by restricting x to {j // j ∉ T}. The inverse map extends a function g on the complement by setting coordinate i to 1 when i ∈ T and g ⟨i, h⟩ otherwise; this extension satisfies the condition that all coordinates in T are 1. For any vector x that is 1 on T, extending its restriction gives 1 on T (which equals x i) and x i outside T, recovering x.
def hamming_norm_monomial_equiv {s : ℕ} (T : Finset (Fin s)) : {x : Fin s → ZMod 2 // ∀ i ∈ T, x i = 1} ≃ ({j : Fin s // j ∉ T} → ZMod 2) where toFun x j := x.1 j.1 invFun g := ⟨fun i => if h : i ∈ T then 1 else g ⟨i, h⟩, fun i hi => by simp [hi]⟩ left_inv := by intro ⟨x, hx⟩ ext i dsimp split_ifs with hi · exact (hx i hi).symm · rfl
The extension map is also a right inverse, establishing the equivalence hamming_norm_monomial_equiv.
For any function g on coordinates outside T and any j ∉ T, the extension evaluated at j falls into the else branch, returning g ⟨j, hj⟩. Thus restricting the extension recovers g.
right_inv := by intro g ext ⟨j, hj⟩ dsimp simp [hj]
The Hamming norm of monomial T is the cardinality of the finset of inputs x where monomial T x ≠ 0.
By definition, the Hamming norm of a function is the number of inputs at which it takes a non-zero value, which is the cardinality of the finset of such inputs filtered from the universal finset.
change (Finset.filter (fun x => monomial T x ≠ 0) Finset.univ).card = 2 ^ (s - T.card)
The inputs where monomial T x ≠ 0 are precisely those where x i = 1 for all i ∈ T.
By extensionality on finsets, x belongs to the filtered finset if and only if monomial T x ≠ 0, which by hamming_norm_monomial_ne_zero_iff holds if and only if x i = 1 for all i ∈ T.
uses
Finset.mem_filter,Finset.mem_univ,true_and,hamming_norm_monomial_ne_zero_iffhave h_filt : (Finset.filter (fun x => monomial T x ≠ 0) Finset.univ) = Finset.filter (fun x => ∀ i ∈ T, x i = 1) Finset.univ := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hamming_norm_monomial_ne_zero_iff T x
The number of such inputs equals the cardinality of functions from the complement of T to ZMod 2.
Rewriting with the simplified filter, we convert the finset cardinality to the cardinality of the subtype of vectors that are 1 on T via Fintype.card_subtype. Applying the bijection hamming_norm_monomial_equiv T and Fintype.card_congr transfers this to the cardinality of functions from {j // j ∉ T} to ZMod 2. Finally, Fintype.card_fun expresses this as |ZMod 2|^|{j // j ∉ T}|.
uses
Fintype.card_subtype,Fintype.card_congr,hamming_norm_monomial_equiv,Fintype.card_funrw [h_filt] rw [← Fintype.card_subtype] rw [Fintype.card_congr (hamming_norm_monomial_equiv T)] rw [Fintype.card_fun]
The cardinality of ZMod 2 is 2. automation
The finite field ZMod 2 has exactly two elements, 0 and 1.
have h1 : Fintype.card (ZMod 2) = 2 := by simp
The number of coordinates outside T is s - |T|.
We convert the subtype cardinality to the cardinality of the filtered finset of elements not in T. This set is the difference Finset.univ \ T. Since T is a subset of univ, its cardinality is |univ| - |T| = s - |T| by Finset.card_sdiff_of_subset, Finset.card_univ, and Fintype.card_fin.
uses
Fintype.card_subtype,Finset.card_sdiff_of_subset,Finset.subset_univ,Finset.card_univ,Fintype.card_finhave h2 : Fintype.card {j : Fin s // j ∉ T} = s - T.card := by rw [Fintype.card_subtype] have : (Finset.filter (fun j => j ∉ T) Finset.univ) = Finset.univ \ T := by ext x simp rw [this, Finset.card_sdiff_of_subset (Finset.subset_univ T), Finset.card_univ, Fintype.card_fin]
The Hamming norm is 2^(s - |T|).
Substituting |ZMod 2| = 2 and |{j // j ∉ T}| = s - |T| into 2^(s - |T|) completes the proof.
rw [h1, h2]
Finset.prod_ne_zero_iff- A finite product of elements in a commutative monoid with zero and no zero divisors is non-zero if and only if each factor is non-zero.
hamming_norm_monomial_ne_zero_iff- The coordinate monomial on T is nonzero at x if and only if x i = 1 for all i in T.
hamming_norm_monomial_equiv- The type of vectors that are 1 on T is equivalent to the type of functions from the complement of T into ZMod 2.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_univ- Every element belongs to the universal finset.
true_and- The conjunction True ∧ p is equivalent to p.
Fintype.card_subtype- The cardinality of a subtype {x // p x} equals the cardinality of the filtered finset of elements satisfying p.
Fintype.card_congr- A bijection between two finite types implies they have the same cardinality.
Fintype.card_fun- The cardinality of the function type α → β is |β|^|α|.
Finset.card_sdiff_of_subset- For a subset s of t, the cardinality of t \ s is |t| - |s|.
Finset.subset_univ- Every finset is a subset of the universal finset.
Finset.card_univ- The universal finset of α has cardinality equal to the Fintype cardinality of α.
Fintype.card_fin- The cardinality of Fin n is n.
- The lemma hamming_norm_monomial_ne_zero_iff uses decide to exhaustively verify that y ≠ 0 ↔ y = 1 for the two elements of ZMod 2.
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_monomial_ne_zero_iff {s : ℕ} (T : Finset (Fin s)) (x : Fin s → ZMod 2) : monomial T x ≠ 0 ↔ ∀ i ∈ T, x i = 1 := by change (∏ i ∈ T, x i) ≠ 0 ↔ ∀ i ∈ T, x i = 1 rw [Finset.prod_ne_zero_iff] simp_rw [show ∀ y : ZMod 2, y ≠ 0 ↔ y = 1 from fun y => by revert y; decide]def hamming_norm_monomial_equiv {s : ℕ} (T : Finset (Fin s)) : {x : Fin s → ZMod 2 // ∀ i ∈ T, x i = 1} ≃ ({j : Fin s // j ∉ T} → ZMod 2) where toFun x j := x.1 j.1 invFun g := ⟨fun i => if h : i ∈ T then 1 else g ⟨i, h⟩, fun i hi => by simp [hi]⟩ left_inv := by intro ⟨x, hx⟩ ext i dsimp split_ifs with hi · exact (hx i hi).symm · rfl right_inv := by intro g ext ⟨j, hj⟩ dsimp simp [hj]/-- The Hamming norm of a coordinate monomial indexed by T in s variables is 2^(s - |T|). -/theorem hamming_norm_monomial {s : ℕ} (T : Finset (Fin s)) : hammingNorm (monomial T : (Fin s → ZMod 2) → ZMod 2) = 2 ^ (s - T.card) := by change (Finset.filter (fun x => monomial T x ≠ 0) Finset.univ).card = 2 ^ (s - T.card) have h_filt : (Finset.filter (fun x => monomial T x ≠ 0) Finset.univ) = Finset.filter (fun x => ∀ i ∈ T, x i = 1) Finset.univ := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hamming_norm_monomial_ne_zero_iff T x rw [h_filt] rw [← Fintype.card_subtype] rw [Fintype.card_congr (hamming_norm_monomial_equiv T)] rw [Fintype.card_fun] have h1 : Fintype.card (ZMod 2) = 2 := by simp have h2 : Fintype.card {j : Fin s // j ∉ T} = s - T.card := by rw [Fintype.card_subtype] have : (Finset.filter (fun j => j ∉ T) Finset.univ) = Finset.univ \ T := by ext x simp rw [this, Finset.card_sdiff_of_subset (Finset.subset_univ T), Finset.card_univ, Fintype.card_fin] rw [h1, h2]