AFTD Auto-Formalizing Theoretical Domains

not_rigid_sequence_product_zero_sum_free

theoremverifiedoriginal

The statement rigid_sequence_product_zero_sum_free is false: The statement is false for a = 1, m = 3, n = 6, t = 1, r(0) = 1 over G = Fin 1 → ZMod 6. Let h : Fin 1 → ZMod 6 := fun _ => 1, and l : Fin 1 → ZMod 6 := fun _ => 4. Let S(0) = replicate 5 h + replicate 1 l. 1. S(0) satisfies is_rigid_sequence 6 3 (S 0): - S(0) has cardinality 6 and sum 5 * 1 + 1 * 4 = 9 = 3 ≠ 0 in ZMod 6. Since card S(0) = 6, its only submultiset of size 6 is itself, which has non-zero sum. Thus S(0) has no 6-term zero-sum subsequence. - The counts in S(0) are count(h) = 5 = 6 - 1 (heavy) and count(l) = 1 with 0 < 1 ≤ 3 - 1 = 2 (light). - Any 6-term multiset supported on supp(S(0)) = {h, l} has the form h^k l^(6-k). Its sum is k * 1 + (6 - k) * 4 = 24 - 3k = -3k mod 6. For this to be 0 mod 6, k must be even: * k = 0: W = l^6 (form x^n) * k = 6: W = h^6 (form x^n) * k = 2: W = h^2 l^4 (form h^k l^(n-k) with 0 < 2 < 6) * k = 4: W = h^4 l^2 (form h^k l^(n-k) with 0 < 4 < 6). Thus every 6-term zero-sum supported on S(0) satisfies the rigid sequence condition. 2. In rigid_sequence_tensor_product 6 3 S: - For x_h := fun _ => h, coordinate 0 is heavy, so it has 0 light coordinates and multiplicity n - 1 = 5. - For x_l := fun _ => l, coordinate 0 is light, so it has 1 light coordinate and multiplicity m - 1 = 2. 3. Consider W = replicate 4 x_h + replicate 2 x_l: - W ≤ rigid_sequence_tensor_product 6 3 S because count(x_h, W) = 4 ≤ 5 and count(x_l, W) = 2 ≤ 2. - W.card = 4 + 2 = 6 = n. - W.sum = 4 • x_h + 2 • x_l = fun _ => fun _ => (4 * 1 + 2 * 4) = fun _ => fun _ => 12 = 0. Thus W is a 6-term zero-sum subsequence of rigid_sequence_tensor_product 6 3 S, contradicting the theorem statement.

Statement

theorem not_rigid_sequence_product_zero_sum_free : ¬ (∀ {a : ℕ} (ha : 1 ≤ a) {m : ℕ} (hm : Odd m) (hm3 : 3 ≤ m) {n : ℕ} (hn : n = 2 ^ a * m)
    {t : ℕ} (ht : 1 ≤ t) (r : Fin t → ℕ)
    (S : (i : Fin t) → Multiset (Fin (r i) → ZMod n))
    (hS : ∀ i, is_rigid_sequence n m (S i)), ¬ ∃ W : Multiset ((i : Fin t) → Fin (r i) → ZMod n),
      W ≤ rigid_sequence_tensor_product n m S ∧ W.card = n ∧ W.sum = 0)
Related work
refutes `rigid_sequence_product_zero_sum_free`
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • rigid_sequence_tensor_productGiven natural numbers n and m, a natural number t, a family of types G(i) with decidable equality for each i in Fin t, and a sequence S(i)…

Lean source view module on GitHub

private def not_rigid_sequence_product_zero_sum_free_h : Fin 1 → ZMod 6 := fun _ => 1

private def not_rigid_sequence_product_zero_sum_free_l : Fin 1 → ZMod 6 := fun _ => 4

private def not_rigid_sequence_product_zero_sum_free_S : Multiset (Fin 1 → ZMod 6) :=
  Multiset.replicate 5 not_rigid_sequence_product_zero_sum_free_h +
    Multiset.replicate 1 not_rigid_sequence_product_zero_sum_free_l

private def not_rigid_sequence_product_zero_sum_free_W : Multiset ((_ : Fin 1) → Fin 1 → ZMod 6) :=
  Multiset.replicate 4 (fun _ : Fin 1 => not_rigid_sequence_product_zero_sum_free_h) +
    Multiset.replicate 2 (fun _ : Fin 1 => not_rigid_sequence_product_zero_sum_free_l)

private lemma not_rigid_sequence_product_zero_sum_free_mem_iff (x : Fin 1 → ZMod 6) :
    x ∈ not_rigid_sequence_product_zero_sum_free_S ↔
      x = not_rigid_sequence_product_zero_sum_free_h ∨
        x = not_rigid_sequence_product_zero_sum_free_l := by
  simp only [not_rigid_sequence_product_zero_sum_free_S, Multiset.mem_add, Multiset.mem_replicate]
  constructor
  · rintro (⟨-, h⟩ | ⟨-, h⟩)
    · exact Or.inl h
    · exact Or.inr h
  · rintro (rfl | rfl)
    · exact Or.inl ⟨by decide, rfl⟩
    · exact Or.inr ⟨by decide, rfl⟩

private lemma not_rigid_sequence_product_zero_sum_free_decomp
    (W : Multiset (Fin 1 → ZMod 6))
    (hW : ∀ x ∈ W, x = not_rigid_sequence_product_zero_sum_free_h ∨
      x = not_rigid_sequence_product_zero_sum_free_l) :
    W = Multiset.replicate (Multiset.count not_rigid_sequence_product_zero_sum_free_h W)
          not_rigid_sequence_product_zero_sum_free_h +
        Multiset.replicate (Multiset.count not_rigid_sequence_product_zero_sum_free_l W)
          not_rigid_sequence_product_zero_sum_free_l := by
  induction W using Multiset.induction_on with
  | empty => simp
  | cons a s ih =>
    have ha : a = not_rigid_sequence_product_zero_sum_free_h ∨
        a = not_rigid_sequence_product_zero_sum_free_l := hW a (Multiset.mem_cons_self a s)
    have hs : ∀ x ∈ s, x = not_rigid_sequence_product_zero_sum_free_h ∨
        x = not_rigid_sequence_product_zero_sum_free_l :=
      fun x hx => hW x (Multiset.mem_cons_of_mem hx)
    have hih := ih hs
    rcases ha with rfl | rfl
    · simp only [Multiset.count_cons]
      simp only [if_neg (by decide : ¬ not_rigid_sequence_product_zero_sum_free_l =
        not_rigid_sequence_product_zero_sum_free_h), Nat.add_zero]
      conv_lhs => rw [hih]
      simp [Multiset.replicate_succ]
    · simp only [Multiset.count_cons]
      simp only [if_neg (by decide : ¬ not_rigid_sequence_product_zero_sum_free_h =
        not_rigid_sequence_product_zero_sum_free_l), Nat.add_zero]
      conv_lhs => rw [hih]
      simp [Multiset.replicate_succ]

private lemma not_rigid_sequence_product_zero_sum_free_rigid :
    is_rigid_sequence 6 3 not_rigid_sequence_product_zero_sum_free_S := by
  refine ⟨?_, ?_, ?_⟩
  · rintro ⟨W, hle, hcard, hsum⟩
    have hc : W = not_rigid_sequence_product_zero_sum_free_S :=
      Multiset.eq_of_le_of_card_le hle (by rw [hcard]; decide)
    rw [hc] at hsum
    exact absurd hsum (by decide)
  · intro x hx
    rcases (not_rigid_sequence_product_zero_sum_free_mem_iff x).1 hx with rfl | rfl
    · left; decide
    · right; decide
  · intro W hcard hsum hsupp
    have hall : ∀ x ∈ W, x = not_rigid_sequence_product_zero_sum_free_h ∨
        x = not_rigid_sequence_product_zero_sum_free_l :=
      fun x hx => (not_rigid_sequence_product_zero_sum_free_mem_iff x).1 (hsupp x hx)
    have hdec := not_rigid_sequence_product_zero_sum_free_decomp W hall
    have hcard' : Multiset.count not_rigid_sequence_product_zero_sum_free_h W +
        Multiset.count not_rigid_sequence_product_zero_sum_free_l W = 6 := by
      have h : (Multiset.replicate (Multiset.count not_rigid_sequence_product_zero_sum_free_h W)
            not_rigid_sequence_product_zero_sum_free_h +
          Multiset.replicate (Multiset.count not_rigid_sequence_product_zero_sum_free_l W)
            not_rigid_sequence_product_zero_sum_free_l).card = 6 := by
        rw [← hdec]; exact hcard
      simpa using h
    rcases Nat.eq_zero_or_pos (Multiset.count not_rigid_sequence_product_zero_sum_free_h W)
      with ha0 | hapos
    · left
      refine ⟨not_rigid_sequence_product_zero_sum_free_l,
        (not_rigid_sequence_product_zero_sum_free_mem_iff _).2 (Or.inr rfl), ?_⟩
      have hb : Multiset.count not_rigid_sequence_product_zero_sum_free_l W = 6 := by omega
      conv_lhs => rw [hdec, ha0, hb]
      simp
    · rcases Nat.lt_or_ge (Multiset.count not_rigid_sequence_product_zero_sum_free_h W) 6
        with hlt | hge
      · right
        refine ⟨not_rigid_sequence_product_zero_sum_free_h,
          not_rigid_sequence_product_zero_sum_free_l,
          Multiset.count not_rigid_sequence_product_zero_sum_free_h W,
          by decide, by decide, hapos, hlt, ?_⟩
        have hb : Multiset.count not_rigid_sequence_product_zero_sum_free_l W =
            6 - Multiset.count not_rigid_sequence_product_zero_sum_free_h W := by omega
        conv_lhs => rw [hdec, hb]
      · left
        refine ⟨not_rigid_sequence_product_zero_sum_free_h,
          (not_rigid_sequence_product_zero_sum_free_mem_iff _).2 (Or.inl rfl), ?_⟩
        have ha : Multiset.count not_rigid_sequence_product_zero_sum_free_h W = 6 := by omega
        have hb0 : Multiset.count not_rigid_sequence_product_zero_sum_free_l W = 0 := by omega
        conv_lhs => rw [hdec, ha, hb0]
        simp

theorem not_rigid_sequence_product_zero_sum_free : ¬ (∀ {a : ℕ} (ha : 1 ≤ a) {m : ℕ} (hm : Odd m) (hm3 : 3 ≤ m) {n : ℕ} (hn : n = 2 ^ a * m)
    {t : ℕ} (ht : 1 ≤ t) (r : Fin t → ℕ)
    (S : (i : Fin t) → Multiset (Fin (r i) → ZMod n))
    (hS : ∀ i, is_rigid_sequence n m (S i)), ¬ ∃ W : Multiset ((i : Fin t) → Fin (r i) → ZMod n),
      W ≤ rigid_sequence_tensor_product n m S ∧ W.card = n ∧ W.sum = 0) := by
  intro H
  refine H (a := 1) (ha := by norm_num) (m := 3) (hm := ⟨1, by norm_num⟩) (hm3 := by norm_num)
    (n := 6) (hn := by norm_num) (t := 1) (ht := by norm_num) (r := fun _ => 1)
    (S := fun _ => not_rigid_sequence_product_zero_sum_free_S)
    (hS := fun _ => not_rigid_sequence_product_zero_sum_free_rigid)
    ⟨not_rigid_sequence_product_zero_sum_free_W, ?_, ?_, ?_⟩
  · decide
  · decide
  · decide
See it in the graphDiscuss this resultChallenge it