AFTD Auto-Formalizing Theoretical Domains

conjecture_subsequence_sums_cover_n_two

theoremverifiedformalization

For n = 2 and any rank r ≥ 1, every sequence of length 2^r over (ZMod 2)^r containing no 2-term zero-sum has the property that its 2-term subsequence sums cover all 2^r - 1 nonzero elements.

Statement

theorem conjecture_subsequence_sums_cover_n_two
    (r : ℕ) (hr : 1 ≤ r) (S : Multiset (Fin r → ZMod 2))
    (hS_card : S.card = 2^r)
    (hS_zs : 0 ∉ ((S.powersetCard 2).map Multiset.sum).toFinset) :
    ((S.powersetCard 2).map Multiset.sum).toFinset = Finset.univ \ {0}
Formalizes
arXiv:2610.35819 Corollary 8.3
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For every natural number $r \ge 1$ and every multiset $S$ of vectors in $(\mathbb{Z}/2\mathbb{Z})^r$ (represented as Fin r → ZMod 2), if the cardinality of $S$ is $2^r$ and $0$ is not the sum of any submultiset of $S$ of cardinality $2$, then the set of all sums of 2-element submultisets of $S$ is precisely the set of all non-zero vectors in $(\mathbb{Z}/2\mathbb{Z})^r$ (that is, Finset.univ \ {0}).

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

Since the vectors lie in characteristic 2, any vector satisfies a + a = 0; thus, the absence of 2-term zero-sums forces the multiset S to have no repeated elements. Since |S| = 2^r matches the total cardinality of (ZMod 2)^r, S must contain every element of the space, in particular 0. Finally, no 2-term sum can be 0 by assumption, and any nonzero vector g is realized as the 2-term sum 0 + g of the distinct elements 0, g ∈ S.

  1. The multiset S contains no duplicate elements.

    Over a field of characteristic 2, every element satisfies a + a = 0. If S contained any element a with multiplicity at least 2, the submultiset {a, a} would have size 2 and sum to 0, which contradicts the hypothesis that S contains no 2-term zero-sum.

    lines 7–17

    uses Multiset.nodup_iff_le, Multiset.mem_toFinset, Multiset.mem_map, Multiset.mem_powersetCard, CharTwo.add_self_eq_zero

      have _ := hr
      have hS_nodup : S.Nodup := by
        rw [Multiset.nodup_iff_le]
        intro a hle
        apply hS_zs
        rw [Multiset.mem_toFinset, Multiset.mem_map]
        refine ⟨a ::ₘ a ::ₘ 0, ?_, ?_⟩
        · rw [Multiset.mem_powersetCard]
          exact ⟨hle, rfl⟩
        · ext i
          simp [CharTwo.add_self_eq_zero]
  2. Every element of (Fin r → ZMod 2) belongs to S.

    Because S has no duplicate elements, its underlying finset has cardinality equal to |S| = 2^r. Since the total number of elements in the vector space (Fin r → ZMod 2) is also 2^r, the set of elements in S equals the entire universe.

    lines 18–26

    uses Finset.card_eq_iff_eq_univ, Multiset.toFinset_card_of_nodup, Multiset.mem_toFinset, Finset.mem_univ

      have hS_all : ∀ x : Fin r → ZMod 2, x ∈ S := by
        have hu : S.toFinset = Finset.univ := by
          rw [← Finset.card_eq_iff_eq_univ]
          rw [Multiset.toFinset_card_of_nodup hS_nodup]
          rw [hS_card]
          simp
        intro x
        rw [← Multiset.mem_toFinset, hu]
        exact Finset.mem_univ x
  3. To show the two sets are equal, it suffices to show that an element g is a 2-term sum of S if and only if g ≠ 0.

    By set extensionality, two sets are identical if they have the same elements. Simplifying the membership condition for Finset.univ \\ {0} reduces the target to showing that g is attained as a 2-term sum if and only if g ≠ 0.

    lines 27–29

    uses Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and

      ext g
      simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and]
      constructor
  4. If g is a 2-term sum of S, then g ≠ 0.

    If g were 0, this would directly contradict the hypothesis that 0 is not a 2-term sum of S.

    lines 30–32

      · intro hg
        rintro rfl
        exact hS_zs hg
  5. Every nonzero element g ≠ 0 is a 2-term sum of S.

    Since S contains all elements of the space, both 0 and g belong to S. Because g ≠ 0, 0 and g are distinct elements, so the multiset {0, g} is a valid submultiset of S of cardinality 2. Its sum is 0 + g = g, witnessing that g is a 2-term sum.

    lines 33–42

    uses Multiset.mem_toFinset, Multiset.mem_map, Multiset.mem_powersetCard, Ne.symm, Multiset.cons_le_of_notMem, Multiset.singleton_le.mpr

      · intro hg
        rw [Multiset.mem_toFinset, Multiset.mem_map]
        refine ⟨0 ::ₘ g ::ₘ 0, ?_, ?_⟩
        · rw [Multiset.mem_powersetCard]
          refine ⟨?_, rfl⟩
          have h_not : (0 : Fin r → ZMod 2) ∉ (g ::ₘ 0 : Multiset (Fin r → ZMod 2)) := by
            simp [Ne.symm hg]
          rw [Multiset.cons_le_of_notMem h_not]
          exact ⟨hS_all 0, Multiset.singleton_le.mpr (hS_all g)⟩
        · simp
CharTwo.add_self_eq_zero
In any semiring of characteristic 2, x + x = 0.
Finset.card_eq_iff_eq_univ
A finite subset of a finite type is equal to the universal set if and only if its cardinality matches that of the type.
Finset.mem_sdiff
An element belongs to the difference of two sets s \\ t if and only if it belongs to s and does not belong to t.
Finset.mem_singleton
An element b belongs to the singleton {a} if and only if b = a.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Multiset.cons_le_of_notMem
If an element a does not belong to multiset s, then a :: s is a submultiset of t if and only if a ∈ t and s ≤ t.
Multiset.mem_map
An element belongs to the image of a multiset under a function f if and only if it is the image of some element in the multiset.
Multiset.mem_powersetCard
A multiset s belongs to powersetCard n t if and only if s is a submultiset of t and has cardinality n.
Multiset.mem_toFinset
An element belongs to the finset associated to a multiset if and only if it belongs to the multiset.
Multiset.nodup_iff_le
A multiset has no duplicate elements if and only if no element occurs with multiplicity two or greater.
Multiset.singleton_le.mpr
If an element belongs to a multiset, then the singleton multiset containing it is a submultiset.
Multiset.toFinset_card_of_nodup
Converting a duplicate-free multiset to a finset preserves its cardinality.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
true_and
The proposition True ∧ p simplifies to p.

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

/-- Corollary 8.3: Conjecture 8.1 holds for n = 2 in any rank r ≥ 1. -/theorem conjecture_subsequence_sums_cover_n_two    (r : ℕ) (hr : 1 ≤ r) (S : Multiset (Fin r → ZMod 2))    (hS_card : S.card = 2^r)    (hS_zs : 0 ∉ ((S.powersetCard 2).map Multiset.sum).toFinset) :    ((S.powersetCard 2).map Multiset.sum).toFinset = Finset.univ \ {0} := by  have _ := hr  have hS_nodup : S.Nodup := by    rw [Multiset.nodup_iff_le]    intro a hle    apply hS_zs    rw [Multiset.mem_toFinset, Multiset.mem_map]    refine ⟨a ::ₘ a ::ₘ 0, ?_, ?_⟩    · rw [Multiset.mem_powersetCard]      exact ⟨hle, rfl⟩    · ext i      simp [CharTwo.add_self_eq_zero]  have hS_all : ∀ x : Fin r → ZMod 2, x ∈ S := by    have hu : S.toFinset = Finset.univ := by      rw [← Finset.card_eq_iff_eq_univ]      rw [Multiset.toFinset_card_of_nodup hS_nodup]      rw [hS_card]      simp    intro x    rw [← Multiset.mem_toFinset, hu]    exact Finset.mem_univ x  ext g  simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and]  constructor  · intro hg    rintro rfl    exact hS_zs hg  · intro hg    rw [Multiset.mem_toFinset, Multiset.mem_map]    refine ⟨0 ::ₘ g ::ₘ 0, ?_, ?_⟩    · rw [Multiset.mem_powersetCard]      refine ⟨?_, rfl⟩      have h_not : (0 : Fin r → ZMod 2) ∉ (g ::ₘ 0 : Multiset (Fin r → ZMod 2)) := by        simp [Ne.symm hg]      rw [Multiset.cons_le_of_notMem h_not]      exact ⟨hS_all 0, Multiset.singleton_le.mpr (hS_all g)⟩    · simp
See it in the graphDiscuss this resultChallenge it