conjecture_subsequence_sums_cover_n_two
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.
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.
uses
Multiset.nodup_iff_le,Multiset.mem_toFinset,Multiset.mem_map,Multiset.mem_powersetCard,CharTwo.add_self_eq_zerohave _ := 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]
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.
uses
Finset.card_eq_iff_eq_univ,Multiset.toFinset_card_of_nodup,Multiset.mem_toFinset,Finset.mem_univhave 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
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.
uses
Finset.mem_sdiff,Finset.mem_univ,Finset.mem_singleton,true_andext g simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_singleton, true_and] constructor
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.
· intro hg rintro rfl exact hS_zs hg
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.
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.
- The hypothesis `hr : 1 ≤ r` is brought into scope on line 7 but is not needed in the subsequent reasoning, as the cardinality argument holds for any rank r.
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.
/-- 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