AFTD Auto-Formalizing Theoretical Domains

possible_weights_sum_two_degree_six_monomials

theoremverifiedformalization

The set of Hamming norms of all sums monomial I + monomial J of two coordinate monomials corresponding to 6-element subsets I, J of Fin 12 on (Fin 12 → ZMod 2) to ZMod 2 is {0, 64, 96, 112, 120, 124, 126}.

Statement

theorem possible_weights_sum_two_degree_six_monomials :
    {w : ℕ | ∃ (I J : Finset (Fin 12)), I.card = 6 ∧ J.card = 6 ∧
      hammingNorm (monomial I + monomial J) = w} =
    {0, 64, 96, 112, 120, 124, 126}
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 2
  • 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 +…
  • 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…

Read back from the Lean

The set of natural numbers $w$ such that there exist subsets $I, J \subseteq \text{Fin } 12$ each of cardinality 6 with the Hamming norm of the Boolean function $(\text{monomial } I + \text{monomial } J)$ equal to $w$ is exactly the set $\{0, 64, 96, 112, 120, 124, 126\}$.

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 establishes the set equality by showing both inclusions. An established formula states that the Hamming weight of the sum of two degree-6 coordinate monomials in 12 variables is given by 128 - 2^(|I ∩ J| + 1). Because the intersection size of two 6-element subsets must be an integer between 0 and 6, the only possible weights are 128 - 2^(k+1) for k ∈ {0, ..., 6}, which evaluates to {0, 64, 96, 112, 120, 124, 126}. Conversely, pairing a fixed 6-element set with explicit subsets of intersection sizes 6 down to 0 witnesses that every one of these seven weights is achieved.

  1. The problem reduces to showing that an arbitrary integer w is the Hamming weight of the sum of two degree-6 monomials if and only if w ∈ {0, 64, 96, 112, 120, 124, 126}.

    We define a reference subset I = {0, 1, 2, 3, 4, 5} for later use in witnessing values. By extensionality (`ext w`), the two sets are equal if they have the same members. Rewriting with `Set.mem_insert_iff` and `Set.mem_singleton_iff` turns membership in {0, 64, 96, 112, 120, 124, 126} into a seven-way disjunction, and `constructor` splits the equivalence into the forward and backward inclusions.

    lines 6–9

    uses Set.mem_insert_iff, Set.mem_singleton_iff

      let I : Finset (Fin 12) := {0, 1, 2, 3, 4, 5}
      ext w
      simp only [Set.mem_insert_iff, Set.mem_singleton_iff]
      constructor
  2. Every weight of a sum of two degree-6 monomials belongs to {0, 64, 96, 112, 120, 124, 126}.

    Given 6-element subsets I' and J' such that w is the Hamming norm of monomial I' + monomial J', the theorem `hamming_norm_sum_two_degree_six_monomials` expresses w as 128 - 2^(|I' ∩ J'| + 1). Since I' ∩ J' ⊆ I' by `Finset.inter_subset_left`, their intersection size satisfies |I' ∩ J'| ≤ |I'| = 6 by `Finset.card_le_card`. Case analysis (`interval_cases`) across the possible values 0 ≤ |I' ∩ J'| ≤ 6 evaluates the formula to 126, 124, 120, 112, 96, 64, and 0 respectively, which confirms w is in the target set.

    lines 10–15

    uses hamming_norm_sum_two_degree_six_monomials, Finset.card_le_card, Finset.inter_subset_left

      · rintro ⟨I', J', hI, hJ, rfl⟩
        rw [hamming_norm_sum_two_degree_six_monomials I' J' hI hJ]
        have h_le : (I' ∩ J').card ≤ 6 := by
          have := @Finset.card_le_card _ (I' ∩ J') I' Finset.inter_subset_left
          omega
        interval_cases (I' ∩ J').card <;> simp
  3. Each of the seven values in {0, 64, 96, 112, 120, 124, 126} is achieved as the Hamming norm of a sum of two degree-6 monomials.

    For each target value w in the disjunction, we exhibit the reference set I = {0, 1, 2, 3, 4, 5} and an explicit 6-element subset J with |I ∩ J| = k for each k ∈ {6, 5, 4, 3, 2, 1, 0}: - w = 0: J = {0, 1, 2, 3, 4, 5}, with |I ∩ J| = 6, yielding 128 - 2^7 = 0; - w = 64: J = {0, 1, 2, 3, 4, 6}, with |I ∩ J| = 5, yielding 128 - 2^6 = 64; - w = 96: J = {0, 1, 2, 3, 6, 7}, with |I ∩ J| = 4, yielding 128 - 2^5 = 96; - w = 112: J = {0, 1, 2, 6, 7, 8}, with |I ∩ J| = 3, yielding 128 - 2^4 = 112; - w = 120: J = {0, 1, 6, 7, 8, 9}, with |I ∩ J| = 2, yielding 128 - 2^3 = 120; - w = 124: J = {0, 6, 7, 8, 9, 10}, with |I ∩ J| = 1, yielding 128 - 2^2 = 124; - w = 126: J = {6, 7, 8, 9, 10, 11}, with |I ∩ J| = 0, yielding 128 - 2^1 = 126. In each case, the cardinalities and intersections are evaluated computationally, and `hamming_norm_sum_two_degree_six_monomials` confirms the resulting Hamming norm is w.

    lines 16–44

    uses hamming_norm_sum_two_degree_six_monomials

      · rintro (rfl | rfl | rfl | rfl | rfl | rfl | rfl)
        · refine ⟨I, {0, 1, 2, 3, 4, 5}, by decide, by decide, ?_⟩
          rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 4, 5} (by decide) (by decide)]
          have : (I ∩ {0, 1, 2, 3, 4, 5}).card = 6 := by decide
          rw [this]; rfl
        · refine ⟨I, {0, 1, 2, 3, 4, 6}, by decide, by decide, ?_⟩
          rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 4, 6} (by decide) (by decide)]
          have : (I ∩ {0, 1, 2, 3, 4, 6}).card = 5 := by decide
          rw [this]; rfl
        · refine ⟨I, {0, 1, 2, 3, 6, 7}, by decide, by decide, ?_⟩
          rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 6, 7} (by decide) (by decide)]
          have : (I ∩ {0, 1, 2, 3, 6, 7}).card = 4 := by decide
          rw [this]; rfl
        · refine ⟨I, {0, 1, 2, 6, 7, 8}, by decide, by decide, ?_⟩
          rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 6, 7, 8} (by decide) (by decide)]
          have : (I ∩ {0, 1, 2, 6, 7, 8}).card = 3 := by decide
          rw [this]; rfl
        · refine ⟨I, {0, 1, 6, 7, 8, 9}, by decide, by decide, ?_⟩
          rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 6, 7, 8, 9} (by decide) (by decide)]
          have : (I ∩ {0, 1, 6, 7, 8, 9}).card = 2 := by decide
          rw [this]; rfl
        · refine ⟨I, {0, 6, 7, 8, 9, 10}, by decide, by decide, ?_⟩
          rw [hamming_norm_sum_two_degree_six_monomials I {0, 6, 7, 8, 9, 10} (by decide) (by decide)]
          have : (I ∩ {0, 6, 7, 8, 9, 10}).card = 1 := by decide
          rw [this]; rfl
        · refine ⟨I, {6, 7, 8, 9, 10, 11}, by decide, by decide, ?_⟩
          rw [hamming_norm_sum_two_degree_six_monomials I {6, 7, 8, 9, 10, 11} (by decide) (by decide)]
          have : (I ∩ {6, 7, 8, 9, 10, 11}).card = 0 := by decide
          rw [this]; rfl
Set.mem_insert_iff
An element belongs to the insertion of a into a set s if and only if it equals a or belongs to s.
Set.mem_singleton_iff
An element belongs to the singleton set {b} if and only if it equals b.
hamming_norm_sum_two_degree_six_monomials
For any two 6-element subsets I and J of Fin 12, the Hamming norm of monomial I + monomial J is 128 - 2^(|I ∩ J| + 1).
Finset.card_le_card
If a finite set s is a subset of t, then the cardinality of s is at most that of t.
Finset.inter_subset_left
The intersection of two finite sets s₁ ∩ s₂ is a subset of s₁.

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

/-- The set of possible Hamming weights of sums of two degree-6 coordinate monomials in 12 variables is {0, 64, 96, 112, 120, 124, 126}. -/theorem possible_weights_sum_two_degree_six_monomials :    {w : ℕ | ∃ (I J : Finset (Fin 12)), I.card = 6 ∧ J.card = 6 ∧      hammingNorm (monomial I + monomial J) = w} =    {0, 64, 96, 112, 120, 124, 126} := by  let I : Finset (Fin 12) := {0, 1, 2, 3, 4, 5}  ext w  simp only [Set.mem_insert_iff, Set.mem_singleton_iff]  constructor  · rintro ⟨I', J', hI, hJ, rfl⟩    rw [hamming_norm_sum_two_degree_six_monomials I' J' hI hJ]    have h_le : (I' ∩ J').card ≤ 6 := by      have := @Finset.card_le_card _ (I' ∩ J') I' Finset.inter_subset_left      omega    interval_cases (I' ∩ J').card <;> simp  · rintro (rfl | rfl | rfl | rfl | rfl | rfl | rfl)    · refine ⟨I, {0, 1, 2, 3, 4, 5}, by decide, by decide, ?_⟩      rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 4, 5} (by decide) (by decide)]      have : (I ∩ {0, 1, 2, 3, 4, 5}).card = 6 := by decide      rw [this]; rfl    · refine ⟨I, {0, 1, 2, 3, 4, 6}, by decide, by decide, ?_⟩      rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 4, 6} (by decide) (by decide)]      have : (I ∩ {0, 1, 2, 3, 4, 6}).card = 5 := by decide      rw [this]; rfl    · refine ⟨I, {0, 1, 2, 3, 6, 7}, by decide, by decide, ?_⟩      rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 3, 6, 7} (by decide) (by decide)]      have : (I ∩ {0, 1, 2, 3, 6, 7}).card = 4 := by decide      rw [this]; rfl    · refine ⟨I, {0, 1, 2, 6, 7, 8}, by decide, by decide, ?_⟩      rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 2, 6, 7, 8} (by decide) (by decide)]      have : (I ∩ {0, 1, 2, 6, 7, 8}).card = 3 := by decide      rw [this]; rfl    · refine ⟨I, {0, 1, 6, 7, 8, 9}, by decide, by decide, ?_⟩      rw [hamming_norm_sum_two_degree_six_monomials I {0, 1, 6, 7, 8, 9} (by decide) (by decide)]      have : (I ∩ {0, 1, 6, 7, 8, 9}).card = 2 := by decide      rw [this]; rfl    · refine ⟨I, {0, 6, 7, 8, 9, 10}, by decide, by decide, ?_⟩      rw [hamming_norm_sum_two_degree_six_monomials I {0, 6, 7, 8, 9, 10} (by decide) (by decide)]      have : (I ∩ {0, 6, 7, 8, 9, 10}).card = 1 := by decide      rw [this]; rfl    · refine ⟨I, {6, 7, 8, 9, 10, 11}, by decide, by decide, ?_⟩      rw [hamming_norm_sum_two_degree_six_monomials I {6, 7, 8, 9, 10, 11} (by decide) (by decide)]      have : (I ∩ {6, 7, 8, 9, 10, 11}).card = 0 := by decide      rw [this]; rfl
See it in the graphDiscuss this resultChallenge it