AFTD Auto-Formalizing Theoretical Domains

rigid_sequence_light_count_ge_m

theoremverified

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.

  1. Assume for contradiction that n - k < m.

    We proceed by contradiction, assuming ¬(m ≤ n - k). Negating the inequality yields n - k < m.

    lines 11–12

    uses not_le.mp

      by_contra h_not
      have h_lt : n - k < m := not_le.mp h_not
  2. 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.

    lines 13–16

      have h_ne : h_elem ≠ l_elem := by
        intro h
        rw [h] at hh
        omega
  3. 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.

    lines 17–21

    uses Multiset.count_pos.mp

      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
  4. 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.

    lines 22–35

    uses Multiset.le_iff_count, Multiset.count_add, Multiset.count_replicate

      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]
  5. 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.

    line 36

      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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it