AFTD Auto-Formalizing Theoretical Domains

hamming_norm_sum_two_degree_six_monomials

theoremverifiedformalization

Let 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 + monomial J on (Fin 12 → ZMod 2) to ZMod 2 is equal to 128 - 2 ^ ((I ∩ J).card + 1).

Statement

theorem hamming_norm_sum_two_degree_six_monomials
    (I J : Finset (Fin 12)) (hI : I.card = 6) (hJ : J.card = 6) :
    hammingNorm (monomial I + monomial J) = 128 - 2 ^ ((I ∩ J).card + 1)
Formalizes
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 4
  • 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…
  • monomial_mulFor any natural number s and any two finite subsets I and J of Fin s, the pointwise product of the coordinate monomials monomial I and…
  • hamming_norm_monomialFor 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…
  • hamming_norm_add_eqFor any finite type α and any two Boolean functions f, g : α → ZMod 2, the Hamming norm of their pointwise sum f + g equals hammingNorm f…
Used by 1

Read back from the Lean

For any two subsets $I, J \subseteq \text{Fin } 12$ such that the cardinality of $I$ is $6$ and the cardinality of $J$ is $6$, the Hamming norm of the function $(\text{monomial } I + \text{monomial } J) : (\text{Fin } 12 \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/2\mathbb{Z}$ equals $128 - 2^{|I \cap J| + 1}$.

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 proof computes the Hamming norm of the sum of two degree-6 coordinate monomials using the general identity |f + g| = |f| + |g| - 2|f * g| for ZMod 2-valued functions. The norms of the individual monomials and their product (the monomial indexed by I ∪ J) are expressed as powers of 2. The principle of inclusion-exclusion relates the cardinality of the union |I ∪ J| to the intersection |I ∩ J|, reducing the expression by elementary arithmetic to 128 - 2 ^ (|I ∩ J| + 1).

  1. The Hamming norm of the sum is expanded into powers of 2 in terms of |I|, |J|, and |I ∪ J|, reducing the equation to 2 ^ (12 - 6) + 2 ^ (12 - 6) - 2 * 2 ^ (12 - (I ∪ J).card) = 128 - 2 ^ ((I ∩ J).card + 1).

    By `hamming_norm_add_eq`, the Hamming norm of the sum of two functions to ZMod 2 is |f + g| = |f| + |g| - 2|f * g|. The weight of each monomial is evaluated using `hamming_norm_monomial`, which gives 2 ^ (12 - |T|). The product of the two monomials is rewritten as the monomial of their union I ∪ J using `monomial_mul`. Finally, the known cardinalities |I| = 6 and |J| = 6 are substituted.

    lines 5–9

    uses hamming_norm_add_eq, hamming_norm_monomial, monomial_mul

      rw [hamming_norm_add_eq]
      rw [hamming_norm_monomial, hamming_norm_monomial]
      rw [hI, hJ]
      rw [monomial_mul]
      rw [hamming_norm_monomial]
  2. The exponent 12 - |I ∪ J| is replaced by |I ∩ J|, giving 2 ^ (12 - 6) + 2 ^ (12 - 6) - 2 * 2 ^ (I ∩ J).card = 128 - 2 ^ ((I ∩ J).card + 1).

    By inclusion-exclusion (`Finset.card_union_add_card_inter`), |I ∪ J| + |I ∩ J| = |I| + |J|. Because |I| = 6 and |J| = 6, linear arithmetic (`omega`) yields 12 - |I ∪ J| = |I ∩ J|. Rewriting with this equality replaces the exponent in the goal.

    lines 10–13

    uses Finset.card_union_add_card_inter

      have h_card : 12 - (I ∪ J).card = (I ∩ J).card := by
        have h_union := Finset.card_union_add_card_inter I J
        omega
      rw [h_card]
  3. Both sides simplify to 128 - 2 ^ ((I ∩ J).card + 1), completing the proof.

    The identity 2 * 2 ^ |I ∩ J| = 2 ^ (|I ∩ J| + 1) is established by ring arithmetic (`ring`) and rewritten into the goal. Since 2 ^ (12 - 6) + 2 ^ (12 - 6) = 64 + 64 = 128, both sides are definitionally identical and the goal is closed by reflexivity (`rfl`).

    lines 14–17

      have h_pow : 2 * 2 ^ (I ∩ J).card = 2 ^ ((I ∩ J).card + 1) := by
        ring
      rw [h_pow]
      rfl
Finset.card_union_add_card_inter
For any two finite sets, the size of their union plus the size of their intersection equals the sum of their sizes.
hamming_norm_add_eq
The Hamming norm of the sum of two functions to ZMod 2 equals the sum of their Hamming norms minus twice the Hamming norm of their pointwise product.
hamming_norm_monomial
The Hamming norm of a coordinate monomial on s variables indexed by a subset T is 2 ^ (s - |T|).
monomial_mul
The pointwise product of two coordinate monomials indexed by I and J is the coordinate monomial indexed by their union I ∪ J.

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

/-- Hamming weight of the sum of two degree-6 coordinate monomials in 12 variables. -/theorem hamming_norm_sum_two_degree_six_monomials    (I J : Finset (Fin 12)) (hI : I.card = 6) (hJ : J.card = 6) :    hammingNorm (monomial I + monomial J) = 128 - 2 ^ ((I ∩ J).card + 1) := by  rw [hamming_norm_add_eq]  rw [hamming_norm_monomial, hamming_norm_monomial]  rw [hI, hJ]  rw [monomial_mul]  rw [hamming_norm_monomial]  have h_card : 12 - (I ∪ J).card = (I ∩ J).card := by    have h_union := Finset.card_union_add_card_inter I J    omega  rw [h_card]  have h_pow : 2 * 2 ^ (I ∩ J).card = 2 ^ ((I ∩ J).card + 1) := by    ring  rw [h_pow]  rfl
See it in the graphDiscuss this resultChallenge it