rigid_sequence_light_count_ge_m
Let S be a rigid sequence with parameters n and m over an additive commutative group G with m < n, such that every term in S has multiplicity n - 1 or m - 1. If W is an n-term zero-sum multiset of the form h^k l^(n-k) with 0 < k < n, where h has multiplicity n - 1 and l has multiplicity at most m - 1, then m <= n - k.
Statement
lemma rigid_sequence_light_count_ge_m {n m : ℕ} {G : Type*} [AddCommGroup G] [DecidableEq G] (S : Multiset G) (hS : is_rigid_sequence n m S) (h_exact : ∀ x ∈ S, S.count x = n - 1 ∨ S.count x = m - 1) (h_elem l_elem : G) (k : ℕ) (hk0 : 0 < k) (hkn : k < n) (hh : S.count h_elem = n - 1) (hl : 0 < S.count l_elem ∧ S.count l_elem ≤ m - 1) (W : Multiset G) (hW_card : W.card = n) (hW_sum : W.sum = 0) (hW_eq : W = Multiset.replicate k h_elem + Multiset.replicate (n - k) l_elem) (hnm : m < n) : m ≤ n - k
- Source
- arXiv:2610.35819 Proof of Theorem 4.3
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_rigid_sequenceA sequence S over an abelian group G without an n-term zero-sum subsequence is called rigid with parameters n and m if every term of S has…
The proof, explained
The proof proceeds by contradiction: assuming m > n - k, the zero-sum multiset W = k · h_elem + (n - k) · l_elem contains at most n - 1 copies of h_elem (since k < n) and at most m - 1 copies of l_elem (since n - k ≤ m - 1). Because h_elem and l_elem have multiplicities n - 1 and m - 1 in S respectively, every element of W appears with multiplicity at most that in S, making W a sub-multiset of S. This directly contradicts the rigidity of S, which excludes any n-term zero-sum sub-multiset.
Assume for contradiction that n - k < m.
We proceed by contradiction, assuming ¬(m ≤ n - k). Negating the inequality yields n - k < m.
uses
not_le.mpby_contra h_not have h_lt : n - k < m := not_le.mp h_not
The elements h_elem and l_elem are distinct (h_elem ≠ l_elem).
If h_elem = l_elem, then the multiplicity of l_elem in S would be n - 1 by hypothesis hh. But hypothesis hl states that the multiplicity of l_elem is at most m - 1, and since m < n, this yields n - 1 ≤ m - 1 < n - 1, a contradiction.
have h_ne : h_elem ≠ l_elem := by intro h rw [h] at hh omega
The multiplicity of l_elem in S is exactly m - 1.
Because its count in S is strictly positive, l_elem belongs to S. The hypothesis h_exact states that every element of S has multiplicity either n - 1 or m - 1. Since the multiplicity of l_elem cannot be n - 1 (which would contradict S.count l_elem ≤ m - 1 < n - 1), it must be m - 1.
uses
Multiset.count_pos.mphave hl_count : S.count l_elem = m - 1 := by have hl_mem : l_elem ∈ S := Multiset.count_pos.mp hl.1 rcases h_exact l_elem hl_mem with h1 | h2 · omega · exact h2
The multiset W is a sub-multiset of S (W ≤ S).
By Multiset.le_iff_count, it suffices to verify that for every element x, its multiplicity in W is at most its multiplicity in S. Using W = k · h_elem + (n - k) · l_elem, we consider three cases: if x = h_elem, its multiplicity in W is k (since l_elem ≠ h_elem), and k ≤ n - 1 = S.count h_elem because k < n; if x = l_elem, its multiplicity in W is n - k, and by the contradiction assumption n - k < m, we have n - k ≤ m - 1 = S.count l_elem; and if x is neither h_elem nor l_elem, its multiplicity in W is 0, which is trivially at most S.count x.
uses
Multiset.le_iff_count,Multiset.count_add,Multiset.count_replicatehave hW_le : W ≤ S := by rw [Multiset.le_iff_count] intro x rw [hW_eq, Multiset.count_add, Multiset.count_replicate, Multiset.count_replicate] by_cases hx_h : h_elem = x · subst hx_h have : l_elem ≠ h_elem := h_ne.symm simp [this, hh] omega · by_cases hx_l : l_elem = x · subst hx_l simp [hx_h, hl_count] omega · simp [hx_h, hx_l]
A contradiction is obtained, establishing m ≤ n - k.
By the first condition in the definition of a rigid sequence (is_rigid_sequence), S contains no sub-multiset of cardinality n with sum 0. However, W is a sub-multiset of S of cardinality n and sum 0, contradicting this condition.
exact hS.1 ⟨W, hW_le, hW_card, hW_sum⟩
not_le.mp- If a natural number is not less than or equal to another, the second is strictly less than the first (i.e., ¬(a ≤ b) implies b < a).
Multiset.count_pos.mp- An element belongs to a multiset if and only if its multiplicity in the multiset is strictly positive.
Multiset.le_iff_count- A multiset s is a sub-multiset of t (s ≤ t) if and only if the multiplicity of every element in s is at most its multiplicity in t.
Multiset.count_add- The multiplicity of an element in the sum of two multisets is the sum of its multiplicities in each multiset.
Multiset.count_replicate- The multiplicity of an element a in the multiset consisting of n copies of b is n if b = a, and 0 otherwise.
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.
/-- In a rigid sequence with light terms of multiplicity m - 1, a two-term n-term zero-sum requires at least m light terms. -/lemma rigid_sequence_light_count_ge_m {n m : ℕ} {G : Type*} [AddCommGroup G] [DecidableEq G] (S : Multiset G) (hS : is_rigid_sequence n m S) (h_exact : ∀ x ∈ S, S.count x = n - 1 ∨ S.count x = m - 1) (h_elem l_elem : G) (k : ℕ) (hk0 : 0 < k) (hkn : k < n) (hh : S.count h_elem = n - 1) (hl : 0 < S.count l_elem ∧ S.count l_elem ≤ m - 1) (W : Multiset G) (hW_card : W.card = n) (hW_sum : W.sum = 0) (hW_eq : W = Multiset.replicate k h_elem + Multiset.replicate (n - k) l_elem) (hnm : m < n) : m ≤ n - k := by by_contra h_not have h_lt : n - k < m := not_le.mp h_not have h_ne : h_elem ≠ l_elem := by intro h rw [h] at hh omega have hl_count : S.count l_elem = m - 1 := by have hl_mem : l_elem ∈ S := Multiset.count_pos.mp hl.1 rcases h_exact l_elem hl_mem with h1 | h2 · omega · exact h2 have hW_le : W ≤ S := by rw [Multiset.le_iff_count] intro x rw [hW_eq, Multiset.count_add, Multiset.count_replicate, Multiset.count_replicate] by_cases hx_h : h_elem = x · subst hx_h have : l_elem ≠ h_elem := h_ne.symm simp [this, hh] omega · by_cases hx_l : l_elem = x · subst hx_l simp [hx_h, hl_count] omega · simp [hx_h, hx_l] exact hS.1 ⟨W, hW_le, hW_card, hW_sum⟩