AFTD Auto-Formalizing Theoretical Domains

hamming_norm_monomial

theoremverified

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
  • monomialFor a natural number s and a finite subset T of Fin s, the monomial associated with T is the function from (Fin s → ZMod 2) to ZMod 2…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Used by 1

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

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

    lines 1–5

    uses Finset.prod_ne_zero_iff

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

    lines 7–17

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

    lines 18–22

      right_inv := by
        intro g
        ext ⟨j, hj⟩
        dsimp
        simp [hj]
  4. 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.

    line 27

      change (Finset.filter (fun x => monomial T x ≠ 0) Finset.univ).card = 2 ^ (s - T.card)
  5. 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.

    lines 28–32

    uses Finset.mem_filter, Finset.mem_univ, true_and, hamming_norm_monomial_ne_zero_iff

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

    lines 33–36

    uses Fintype.card_subtype, Fintype.card_congr, hamming_norm_monomial_equiv, Fintype.card_fun

      rw [h_filt]
      rw [← Fintype.card_subtype]
      rw [Fintype.card_congr (hamming_norm_monomial_equiv T)]
      rw [Fintype.card_fun]
  7. The cardinality of ZMod 2 is 2. automation

    The finite field ZMod 2 has exactly two elements, 0 and 1.

    line 37

      have h1 : Fintype.card (ZMod 2) = 2 := by simp
  8. 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.

    lines 38–43

    uses Fintype.card_subtype, Finset.card_sdiff_of_subset, Finset.subset_univ, Finset.card_univ, Fintype.card_fin

      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]
  9. The Hamming norm is 2^(s - |T|).

    Substituting |ZMod 2| = 2 and |{j // j ∉ T}| = s - |T| into 2^(s - |T|) completes the proof.

    line 44

      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.

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