AFTD Auto-Formalizing Theoretical Domains

zero_sum_constant_s_star_lower_bound_witness

theoremverified

For every odd prime $p$, there exists a multiset $W$ of size $2p$ of units in $\mathbb{Z}/p^2\mathbb{Z}$ that has no sub-multiset $T \le W$ of cardinality $p$ with (T.sum : ZMod (p^2)).val % p = 0 and (T.sum : ZMod (p^2)).val % p^2 ≠ 0.

Statement

theorem zero_sum_constant_s_star_lower_bound_witness (p : ℕ) (hp : p.Prime) (hp_odd : p ≠ 2) :
    ∃ W : Multiset (ZMod (p ^ 2)), W.card = 2 * p ∧ (∀ x ∈ W, IsUnit x) ∧
      ¬ ∃ T ≤ W, T.card = p ∧ T.sum.val % p = 0 ∧ T.sum.val % p ^ 2 ≠ 0
Source
scout/2611-14248-the-zero-sum-constant-mathsf-s-p-and-inverse-problem.md:2441
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For every prime natural number $p$ with $p \neq 2$ (i.e., every odd prime $p$), there exists a multiset $W$ of elements in $\mathbb{Z}/p^2\mathbb{Z}$ (ZMod (p ^ 2)) such that: 1. The cardinality of $W$ is $2p$; 2. Every element $x \in W$ is a unit (invertible in the ring $\mathbb{Z}/p^2\mathbb{Z}$); 3. There does not exist a submultiset $T \le W$ of cardinality $p$ such that the canonical integer representative of the sum of $T$ (T.sum.val) is divisible by $p$ (T.sum.val % p = 0) and not divisible by $p^2$ (T.sum.val % p ^ 2 ≠ 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

To show the lower bound s_p^* ≥ 2p + 1, we construct a multiset W = A + B of 2p units in ZMod (p^2), where A consists of p - 1 copies of 1 together with 1 - p, and B consists of p - 1 copies of -1 together with p - 1. Both A and B sum to 0 in ZMod (p^2), and the canonical reduction homomorphism f : ZMod (p^2) → ZMod p sends all elements of A to 1 and all elements of B to -1. For any sub-multiset T ≤ W of size p, the condition that its sum is divisible by p forces the number of elements coming from A to satisfy 2|T_A| ≡ 0 (mod p), which for an odd prime p implies |T_A| = 0 or |T_A| = p. Consequently, T must equal either B or A, both of which sum to 0 in ZMod (p^2), contradicting the existence of a sub-multiset with sum divisible by p but non-zero modulo p^2.

  1. A sub-multiset of the same cardinality as the ambient multiset is equal to it (`multiset_eq_of_le_card_eq`).

    If s ≤ t, there is a multiset u such that t = s + u (`Multiset.le_iff_exists_add`). Taking cardinalities (`Multiset.card_add`), |t| = |s| + |u|. Since |s| = |t|, linear arithmetic over ℕ (`omega`) forces |u| = 0, so u is empty (`Multiset.card_eq_zero`), establishing s = t.

    lines 1–6

    uses Multiset.le_iff_exists_add, Multiset.card_add, Multiset.card_eq_zero, add_zero

    theorem multiset_eq_of_le_card_eq {α : Type*} (s t : Multiset α) (hle : s ≤ t) (hcard : s.card = t.card) : s = t := by
      obtain ⟨u, rfl⟩ := Multiset.le_iff_exists_add.mp hle
      rw [Multiset.card_add] at hcard
      have : u.card = 0 := by omega
      rw [Multiset.card_eq_zero.mp this, add_zero]
    
  2. Applying a function that is identically c on a multiset s produces c replicated |s| times (`map_const_of_forall_mem`).

    We proceed by multiset induction on s using `Multiset.induction_on`. The base case of the empty multiset simplifies immediately. For the inductive step a :: s, we evaluate g(a) = c via membership of a (`Multiset.mem_cons_self`), simplify constructors (`Multiset.map_cons`, `Multiset.card_cons`, `Multiset.replicate_succ`), and apply the induction hypothesis to s since every element of s belongs to a :: s (`Multiset.mem_cons_of_mem`).

    lines 7–20

    uses Multiset.induction_on, Multiset.map_cons, Multiset.card_cons, Multiset.replicate_succ, Multiset.mem_cons_self, Multiset.mem_cons_of_mem

    theorem map_const_of_forall_mem {α β : Type*} (s : Multiset α) (c : β) (g : α → β)
        (h : ∀ x ∈ s, g x = c) :
        s.map g = Multiset.replicate s.card c := by
      induction s using Multiset.induction_on with
      | empty => simp
      | cons a s ih =>
        simp only [Multiset.map_cons, Multiset.card_cons, Multiset.replicate_succ]
        have ha : g a = c := h a (Multiset.mem_cons_self a s)
        rw [ha]
        congr 1
        apply ih
        intro x hx
        exact h x (Multiset.mem_cons_of_mem hx)
    
  3. Define the candidate multiset W = A + B in ZMod (p^2) as the witness.

    Since p ∣ p^2 via `dvd_pow_self`, we obtain the canonical reduction homomorphism f : ZMod (p^2) →+* ZMod p via `ZMod.castHom`. We define A as p - 1 copies of 1 plus the singleton {1 - p}, and B as p - 1 copies of -1 plus the singleton {p - 1}. We set W = A + B and provide W as the existential witness.

    lines 21–30

    uses dvd_pow_self, ZMod.castHom, Multiset.replicate

    /-- Existence of an exceptional sequence of length 2p of units in ZMod (p^2), witnessing the lower bound s_p^* >= 2p + 1. -/
    theorem zero_sum_constant_s_star_lower_bound_witness (p : ℕ) (hp : p.Prime) (hp_odd : p ≠ 2) :
        ∃ W : Multiset (ZMod (p ^ 2)), W.card = 2 * p ∧ (∀ x ∈ W, IsUnit x) ∧
          ¬ ∃ T ≤ W, T.card = p ∧ T.sum.val % p = 0 ∧ T.sum.val % p ^ 2 ≠ 0 := by
      let h_dvd : p ∣ p ^ 2 := dvd_pow_self p (by decide)
      let f : ZMod (p ^ 2) →+* ZMod p := ZMod.castHom h_dvd (ZMod p)
      let A : Multiset (ZMod (p ^ 2)) := Multiset.replicate (p - 1) 1 + {1 - (p : ZMod (p ^ 2))}
      let B : Multiset (ZMod (p ^ 2)) := Multiset.replicate (p - 1) (-1) + {(p : ZMod (p ^ 2)) - 1}
      let W := A + B
      use W
  4. The cardinalities satisfy |A| = p, |B| = p, and |W| = 2p.

    By expanding definitions, |A| = (p - 1) + 1 = p and |B| = (p - 1) + 1 = p using `Nat.sub_add_cancel` since p is prime (hence p > 0). Consequently, |W| = |A| + |B| = p + p = 2p by multiset cardinality addition and ring arithmetic.

    lines 31–43

    uses Multiset.card_add, Multiset.card_replicate, Multiset.card_singleton, Nat.sub_add_cancel

      have hA_card : A.card = p := by
        dsimp [A]
        simp only [Multiset.card_add, Multiset.card_replicate, Multiset.card_singleton]
        exact Nat.sub_add_cancel hp.pos
      have hB_card : B.card = p := by
        dsimp [B]
        simp only [Multiset.card_add, Multiset.card_replicate, Multiset.card_singleton]
        exact Nat.sub_add_cancel hp.pos
      have hW_card : W.card = 2 * p := by
        dsimp [W]
        rw [Multiset.card_add, hA_card, hB_card]
        ring
      refine ⟨hW_card, ?_, ?_⟩
  5. Every element of W is a unit in ZMod (p^2).

    The element 1 is a unit (`isUnit_one`), and -1 is a unit as its negation. For 1 - p, we compute (1 - p)(1 + p) = 1 - p^2 = 1 in ZMod (p^2) because p^2 = 0 (`ZMod.natCast_self`), so 1 - p divides 1 and is a unit (`isUnit_of_dvd_one`). The element p - 1 = -(1 - p) is also a unit as the negation of a unit. Any element x ∈ W must belong to A or B, so x is one of 1, 1 - p, -1, or p - 1, each of which is a unit.

    lines 44–67

    uses isUnit_one, Nat.cast_pow, ZMod.natCast_self, isUnit_of_dvd_one, Multiset.mem_add, Multiset.eq_of_mem_replicate, Multiset.mem_singleton

      · intro x hx
        have h_unit_one : IsUnit (1 : ZMod (p ^ 2)) := isUnit_one
        have h_unit_neg_one : IsUnit (-1 : ZMod (p ^ 2)) := isUnit_one.neg
        have h_inv : (1 - (p : ZMod (p ^ 2))) * (1 + (p : ZMod (p ^ 2))) = 1 := by
          have : (p : ZMod (p ^ 2)) ^ 2 = 0 := by
            rw [← Nat.cast_pow, ZMod.natCast_self]
          linear_combination -this
        have h_unit_1_sub_p : IsUnit (1 - (p : ZMod (p ^ 2))) :=
          isUnit_of_dvd_one ⟨1 + (p : ZMod (p ^ 2)), h_inv.symm⟩
        have h_unit_p_sub_1 : IsUnit ((p : ZMod (p ^ 2)) - 1) := by
          have : (p : ZMod (p ^ 2)) - 1 = - (1 - (p : ZMod (p ^ 2))) := by ring
          rw [this]
          exact h_unit_1_sub_p.neg
        dsimp [W, A, B] at hx
        rw [Multiset.mem_add] at hx
        rcases hx with hx | hx
        · rw [Multiset.mem_add] at hx
          rcases hx with hx | hx
          · rw [Multiset.eq_of_mem_replicate hx]; exact h_unit_one
          · rw [Multiset.mem_singleton.mp hx]; exact h_unit_1_sub_p
        · rw [Multiset.mem_add] at hx
          rcases hx with hx | hx
          · rw [Multiset.eq_of_mem_replicate hx]; exact h_unit_neg_one
          · rw [Multiset.mem_singleton.mp hx]; exact h_unit_p_sub_1
  6. Assuming an exceptional sub-multiset T exists, the sums of A and B in ZMod (p^2) are both 0.

    Suppose for contradiction there is T ≤ W with |T| = p, (T.sum).val % p = 0, and (T.sum).val % p^2 ≠ 0. The sum of A is (p - 1) * 1 + (1 - p) = (p - 1) + 1 - p = 0 in ZMod (p^2) using `Nat.sub_add_cancel`. Similarly, the sum of B is (p - 1) * (-1) + (p - 1) = -(p - 1) + (p - 1) = 0 in ZMod (p^2).

    lines 68–82

    uses Multiset.sum_add, Multiset.sum_replicate, Multiset.sum_singleton, nsmul_eq_mul, mul_one, Nat.cast_add_one, Nat.sub_add_cancel, mul_neg

      · rintro ⟨T, hTW, hT_card, hT_p, hT_p2⟩
        have hA_sum : A.sum = 0 := by
          dsimp [A]
          rw [Multiset.sum_add, Multiset.sum_replicate, Multiset.sum_singleton]
          simp only [nsmul_eq_mul, mul_one]
          have h1 : ((p - 1 : ℕ) : ZMod (p ^ 2)) + 1 = (p : ZMod (p ^ 2)) := by
            rw [← Nat.cast_add_one, Nat.sub_add_cancel hp.pos]
          linear_combination h1
        have hB_sum : B.sum = 0 := by
          dsimp [B]
          rw [Multiset.sum_add, Multiset.sum_replicate, Multiset.sum_singleton]
          simp only [nsmul_eq_mul, mul_neg, mul_one]
          have h1 : ((p - 1 : ℕ) : ZMod (p ^ 2)) + 1 = (p : ZMod (p ^ 2)) := by
            rw [← Nat.cast_add_one, Nat.sub_add_cancel hp.pos]
          linear_combination -h1
  7. The reduction homomorphism f sends all elements of A to 1, all elements of B to -1, and -1 ≠ 1 in ZMod p.

    Under f, f(1) = 1 and f(1 - p) = 1 - 0 = 1, so f(x) = 1 for all x ∈ A. Under f, f(-1) = -1 and f(p - 1) = 0 - 1 = -1, so f(x) = -1 for all x ∈ B. Since p is an odd prime, p ≠ 2 and p ≥ 2, which implies 2 ≠ 0 in ZMod p (`ZMod.natCast_eq_zero_iff`, `Nat.le_of_dvd`), and therefore -1 ≠ 1 in ZMod p.

    lines 83–111

    uses Multiset.mem_add, Multiset.eq_of_mem_replicate, Multiset.mem_singleton, ZMod.natCast_eq_zero_iff, Nat.le_of_dvd

        have hfA : ∀ x ∈ A, f x = 1 := by
          intro x hx
          have h1 : f 1 = 1 := by simp [f]
          have h2 : f (1 - (p : ZMod (p ^ 2))) = 1 := by simp [f]
          dsimp [A] at hx
          rw [Multiset.mem_add] at hx
          rcases hx with hx | hx
          · rw [Multiset.eq_of_mem_replicate hx]; exact h1
          · rw [Multiset.mem_singleton.mp hx]; exact h2
        have hfB : ∀ x ∈ B, f x = -1 := by
          intro x hx
          have h3 : f (-1) = -1 := by simp [f]
          have h4 : f ((p : ZMod (p ^ 2)) - 1) = -1 := by simp [f]
          dsimp [B] at hx
          rw [Multiset.mem_add] at hx
          rcases hx with hx | hx
          · rw [Multiset.eq_of_mem_replicate hx]; exact h3
          · rw [Multiset.mem_singleton.mp hx]; exact h4
        have h2_ne_0 : (2 : ZMod p) ≠ 0 := by
          intro h
          have : (2 : ZMod p) = ((2 : ℕ) : ZMod p) := rfl
          rw [this, ZMod.natCast_eq_zero_iff] at h
          have : p ≤ 2 := Nat.le_of_dvd (by decide) h
          have : p ≥ 2 := hp.two_le
          omega
        have hneg1_ne_1 : (-1 : ZMod p) ≠ 1 := by
          intro h
          have : (2 : ZMod p) = 0 := by linear_combination -h
          exact h2_ne_0 this
  8. Filtering T by f partitions T into sub-multisets TA ≤ A and TB ≤ B.

    Let TA be the sub-multiset of T where f(x) = 1, and TB where f(x) ≠ 1. For TA, every element has f(x) = 1, so it cannot belong to B (since f is -1 on B and -1 ≠ 1). Thus the count of x in B is 0. Since T ≤ W = A + B, the multiplicity of x in TA is at most its multiplicity in A, proving TA ≤ A via `Multiset.le_iff_count`. Symmetrically, TB ≤ B.

    lines 112–145

    uses Multiset.le_iff_count, Multiset.mem_filter, Multiset.count_eq_zero, Multiset.count_le_of_le, Multiset.filter_le, Multiset.count_add, add_zero, Nat.zero_le, zero_add

        let TA := T.filter (fun x => f x = 1)
        let TB := T.filter (fun x => f x ≠ 1)
        have hTA_le : TA ≤ A := by
          rw [Multiset.le_iff_count]
          intro x
          by_cases hx : x ∈ TA
          · have hfx : f x = 1 := (Multiset.mem_filter.mp hx).2
            have hxB : x ∉ B := by
              intro h
              have := hfB x h
              rw [this] at hfx
              exact hneg1_ne_1 hfx
            have hxB_count : B.count x = 0 := Multiset.count_eq_zero.mpr hxB
            have hle := Multiset.count_le_of_le x (Multiset.filter_le (fun x => f x = 1) T)
            have hle2 := Multiset.count_le_of_le x hTW
            rw [Multiset.count_add, hxB_count, add_zero] at hle2
            exact hle.trans hle2
          · rw [Multiset.count_eq_zero.mpr hx]
            exact Nat.zero_le _
        have hTB_le : TB ≤ B := by
          rw [Multiset.le_iff_count]
          intro x
          by_cases hx : x ∈ TB
          · have hfx : f x ≠ 1 := (Multiset.mem_filter.mp hx).2
            have hxA : x ∉ A := by
              intro h
              exact hfx (hfA x h)
            have hxA_count : A.count x = 0 := Multiset.count_eq_zero.mpr hxA
            have hle := Multiset.count_le_of_le x (Multiset.filter_le (fun x => f x ≠ 1) T)
            have hle2 := Multiset.count_le_of_le x hTW
            rw [Multiset.count_add, hxA_count, zero_add] at hle2
            exact hle.trans hle2
          · rw [Multiset.count_eq_zero.mpr hx]
            exact Nat.zero_le _
  9. The sum of f over T equals |TA| - |TB| in ZMod p, and |TB| ≡ -|TA| (mod p).

    Since T = TA + TB (`Multiset.filter_add_not`), |TA| + |TB| = |T| = p. Mapping f over TA yields |TA| copies of 1 by `map_const_of_forall_mem`, and over TB yields |TB| copies of -1. Summing the map gives (T.map f).sum = |TA| - |TB| in ZMod p. Modulo p, |TA| + |TB| = p ≡ 0, so |TB| = -|TA| in ZMod p.

    lines 146–162

    uses Multiset.filter_add_not, Multiset.card_add, map_const_of_forall_mem, Multiset.mem_filter, Multiset.mem_of_le, Multiset.map_add, Multiset.sum_add, Multiset.sum_replicate, nsmul_eq_mul, mul_one, mul_neg, ZMod.natCast_self

        have hT_decomp : T = TA + TB := by
          exact (Multiset.filter_add_not (fun x => f x = 1) T).symm
        have h_cards : TA.card + TB.card = p := by
          rw [← Multiset.card_add, ← hT_decomp, hT_card]
        have hTA_map : TA.map f = Multiset.replicate TA.card 1 :=
          map_const_of_forall_mem TA 1 f (fun x hx => (Multiset.mem_filter.mp hx).2)
        have hTB_map : TB.map f = Multiset.replicate TB.card (-1) :=
          map_const_of_forall_mem TB (-1) f (fun x hx => hfB x (Multiset.mem_of_le hTB_le hx))
        have hT_map_sum : (T.map f).sum = (TA.card : ZMod p) - (TB.card : ZMod p) := by
          rw [hT_decomp, Multiset.map_add, Multiset.sum_add, hTA_map, hTB_map]
          simp only [Multiset.sum_replicate, nsmul_eq_mul, mul_one, mul_neg]
          ring
        have h_TB_card : (TB.card : ZMod p) = - (TA.card : ZMod p) := by
          have : ((TA.card + TB.card : ℕ) : ZMod p) = (p : ZMod p) := by rw [h_cards]
          push_cast at this
          rw [ZMod.natCast_self] at this
          linear_combination this
  10. The cardinality |TA| must be either 0 or p.

    Because (T.sum).val % p = 0, the homomorphism gives f(T.sum) = 0 in ZMod p (`ZMod.castHom_apply`, `ZMod.cast_eq_val`). Since f commutes with sums (`map_multiset_sum`), (T.map f).sum = 0. Substituting |TB| = -|TA| yields 2 * |TA| = 0 in ZMod p. Since p is prime and 2 ≠ 0, this forces |TA| ≡ 0 (mod p). But 0 ≤ |TA| ≤ |A| = p, so |TA| must be 0 or p.

    lines 163–189

    uses ZMod.castHom_apply, pow_ne_zero, ZMod.cast_eq_val, ZMod.natCast_eq_zero_iff, Nat.dvd_iff_mod_eq_zero, map_multiset_sum, mul_eq_zero, False.elim, Multiset.card_le_card, Nat.eq_zero_or_pos, Nat.le_of_dvd, Nat.dvd_of_mod_eq_zero

        have hT_sum_zero : f T.sum = 0 := by
          have : f T.sum = (T.sum.val : ZMod p) := by
            rw [ZMod.castHom_apply]
            have : NeZero (p ^ 2) := ⟨pow_ne_zero 2 hp.ne_zero⟩
            exact ZMod.cast_eq_val T.sum
          rw [this, ZMod.natCast_eq_zero_iff, Nat.dvd_iff_mod_eq_zero]
          exact hT_p
        have h_2TA : 2 * (TA.card : ZMod p) = 0 := by
          have h1 : (T.map f).sum = 0 := (map_multiset_sum f T).symm.trans hT_sum_zero
          calc 2 * (TA.card : ZMod p) = (TA.card : ZMod p) - (- (TA.card : ZMod p)) := by ring
          _ = (TA.card : ZMod p) - (TB.card : ZMod p) := by rw [← h_TB_card]
          _ = (T.map f).sum := hT_map_sum.symm
          _ = 0 := h1
        have hTA_zero : (TA.card : ZMod p) = 0 := by
          have : Fact p.Prime := ⟨hp⟩
          cases mul_eq_zero.mp h_2TA with
          | inl h => exact False.elim (h2_ne_0 h)
          | inr h => exact h
        rw [ZMod.natCast_eq_zero_iff, Nat.dvd_iff_mod_eq_zero] at hTA_zero
        have hTA_le_p : TA.card ≤ p := (Multiset.card_le_card hTA_le).trans_eq hA_card
        have hTA_cases : TA.card = 0 ∨ TA.card = p := by
          rcases Nat.eq_zero_or_pos TA.card with h | h
          · left; exact h
          · right
            have := Nat.le_of_dvd h (Nat.dvd_of_mod_eq_zero hTA_zero)
            omega
        have hT_sum_eq_zero : T.sum = 0 := by
  11. In either case T.sum = 0 in ZMod (p^2), contradicting (T.sum).val % p^2 ≠ 0.

    If |TA| = 0, then TA is empty, so T = TB ≤ B. Since |TB| = p = |B|, `multiset_eq_of_le_card_eq` gives T = B, so T.sum = B.sum = 0. If |TA| = p, then |TB| = 0, so T = TA ≤ A. Since |TA| = p = |A|, `multiset_eq_of_le_card_eq` gives T = A, so T.sum = A.sum = 0. In either case, T.sum = 0 in ZMod (p^2), so (T.sum).val % p^2 = 0 (`ZMod.val_zero`, `Nat.zero_mod`), which directly contradicts the assumption that (T.sum).val % p^2 ≠ 0.

    lines 190–204

    uses Multiset.card_eq_zero, zero_add, multiset_eq_of_le_card_eq, add_zero, ZMod.val_zero, Nat.zero_mod

          rcases hTA_cases with h0 | hp_eq
          · have hTA_empty : TA = 0 := Multiset.card_eq_zero.mp h0
            rw [hTA_empty, zero_add] at hT_decomp
            have hTB_eq : TB = B := multiset_eq_of_le_card_eq TB B hTB_le (by omega)
            rw [hTB_eq] at hT_decomp
            rw [hT_decomp, hB_sum]
          · have hTB_zero : TB.card = 0 := by omega
            have hTB_empty : TB = 0 := Multiset.card_eq_zero.mp hTB_zero
            rw [hTB_empty, add_zero] at hT_decomp
            have hTA_eq : TA = A := multiset_eq_of_le_card_eq TA A hTA_le (by omega)
            rw [hTA_eq] at hT_decomp
            rw [hT_decomp, hA_sum]
        have : T.sum.val % p ^ 2 = 0 := by
          rw [hT_sum_eq_zero, ZMod.val_zero, Nat.zero_mod]
        exact hT_p2 this
Multiset.le_iff_exists_add
For multisets s and t, s ≤ t if and only if there exists a multiset u such that t = s + u.
Multiset.card_add
The cardinality of the sum of two multisets is the sum of their cardinalities: |s + t| = |s| + |t|.
Multiset.card_eq_zero
A multiset has cardinality 0 if and only if it is the empty multiset.
add_zero
Adding zero leaves an element unchanged: a + 0 = a.
Multiset.induction_on
Principle of induction on multisets: a property holds for all multisets if it holds for 0 and is preserved under consing an element.
Multiset.map_cons
Mapping a function over a consed multiset satisfies map g (a :: s) = g a :: map g s.
Multiset.card_cons
Consing an element increases the cardinality of a multiset by 1.
Multiset.replicate_succ
Replicating an element n + 1 times is equal to consing the element to n replications.
Multiset.mem_cons_self
An element a is a member of the multiset a :: s.
Multiset.mem_cons_of_mem
If an element a is in s, it is in b :: s.
dvd_pow_self
Any element divides its positive powers: a ∣ a^n for n ≠ 0.
ZMod.castHom
Canonical projection ring homomorphism from ZMod n to a ring of characteristic m when m ∣ n.
Multiset.replicate
Constructs a multiset by repeating an element a given number of times.
Multiset.card_replicate
The cardinality of replicating an element n times is n.
Multiset.card_singleton
The cardinality of a singleton multiset {a} is 1.
Nat.sub_add_cancel
For natural numbers with m ≤ n, (n - m) + m = n.
isUnit_one
The identity element 1 is a unit in any monoid.
Nat.cast_pow
Natural number casting preserves powers: ↑(m ^ n) = (↑m) ^ n.
ZMod.natCast_self
In ZMod n, the element n is zero: ↑n = 0.
isUnit_of_dvd_one
In a commutative monoid, any divisor of 1 is a unit.
Multiset.mem_add
An element is in s + t if and only if it is in s or in t.
Multiset.eq_of_mem_replicate
If b is in the replication of a, then b = a.
Multiset.mem_singleton
An element is in the singleton {a} if and only if it equals a.
Multiset.sum_add
The sum of elements in s + t is the sum of s plus the sum of t.
Multiset.sum_replicate
The sum of n copies of an element a is n • a.
Multiset.sum_singleton
The sum of a singleton multiset {a} is a.
nsmul_eq_mul
Natural scalar multiplication in a semiring equals multiplication by the cast: n • a = ↑n * a.
mul_one
Multiplying by 1 on the right is the identity: a * 1 = a.
Nat.cast_add_one
Casting to an add monoid with one distributes over adding one: ↑(n + 1) = ↑n + 1.
mul_neg
Multiplication distributes over negation: a * (-b) = -(a * b).
ZMod.natCast_eq_zero_iff
In ZMod b, the natural cast ↑a equals 0 if and only if b ∣ a.
Nat.le_of_dvd
If m ∣ n and n > 0, then m ≤ n.
Multiset.le_iff_count
Multiset inclusion s ≤ t is equivalent to the multiplicity of every element in s being at most that in t.
Multiset.mem_filter
An element x is in filter p s if and only if x ∈ s and p x holds.
Multiset.count_eq_zero
The multiplicity of an element in a multiset is 0 if and only if it is not in the multiset.
Multiset.count_le_of_le
If s ≤ t, then the multiplicity of any element in s is at most its multiplicity in t.
Multiset.filter_le
The sub-multiset obtained by filtering is a sub-multiset: filter p s ≤ s.
Multiset.count_add
The multiplicity of an element in s + t is the sum of its multiplicities in s and in t.
Nat.zero_le
Every natural number is greater than or equal to 0.
zero_add
Adding zero on the left leaves an element unchanged: 0 + a = a.
Multiset.filter_add_not
Filtering a multiset by a predicate and by its negation partitions the multiset: filter p s + filter (¬p) s = s.
map_const_of_forall_mem
If a function takes a constant value c on all elements of s, mapping it over s yields |s| copies of c.
Multiset.mem_of_le
If s ≤ t and a ∈ s, then a ∈ t.
Multiset.map_add
Mapping a function distributes over multiset addition: map f (s + t) = map f s + map f t.
ZMod.castHom_apply
Evaluating castHom on an element yields its canonical cast.
pow_ne_zero
A power of a non-zero element in a reduced monoid with zero is non-zero.
ZMod.cast_eq_val
In ZMod n with n ≠ 0, the cast of an element to another ring equals the cast of its canonical representative in ℕ.
Nat.dvd_iff_mod_eq_zero
A natural number m divides n if and only if n % m = 0.
map_multiset_sum
An additive monoid homomorphism commutes with multiset sums: f (s.sum) = (s.map f).sum.
mul_eq_zero
In an integral domain, a * b = 0 implies a = 0 or b = 0.
False.elim
From False, any proposition follows.
Multiset.card_le_card
If s ≤ t, then the cardinality of s is at most that of t.
Nat.eq_zero_or_pos
Every natural number is either 0 or strictly positive.
Nat.dvd_of_mod_eq_zero
If n % m = 0, then m ∣ n.
multiset_eq_of_le_card_eq
If s ≤ t and |s| = |t|, then s = t.
ZMod.val_zero
The canonical integer representative of 0 in ZMod n is 0.
Nat.zero_mod
For any natural modulus b, 0 % b = 0.

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

theorem multiset_eq_of_le_card_eq {α : Type*} (s t : Multiset α) (hle : s ≤ t) (hcard : s.card = t.card) : s = t := by  obtain ⟨u, rfl⟩ := Multiset.le_iff_exists_add.mp hle  rw [Multiset.card_add] at hcard  have : u.card = 0 := by omega  rw [Multiset.card_eq_zero.mp this, add_zero]theorem map_const_of_forall_mem {α β : Type*} (s : Multiset α) (c : β) (g : α → β)    (h : ∀ x ∈ s, g x = c) :    s.map g = Multiset.replicate s.card c := by  induction s using Multiset.induction_on with  | empty => simp  | cons a s ih =>    simp only [Multiset.map_cons, Multiset.card_cons, Multiset.replicate_succ]    have ha : g a = c := h a (Multiset.mem_cons_self a s)    rw [ha]    congr 1    apply ih    intro x hx    exact h x (Multiset.mem_cons_of_mem hx)/-- Existence of an exceptional sequence of length 2p of units in ZMod (p^2), witnessing the lower bound s_p^* >= 2p + 1. -/theorem zero_sum_constant_s_star_lower_bound_witness (p : ℕ) (hp : p.Prime) (hp_odd : p ≠ 2) :    ∃ W : Multiset (ZMod (p ^ 2)), W.card = 2 * p ∧ (∀ x ∈ W, IsUnit x) ∧      ¬ ∃ T ≤ W, T.card = p ∧ T.sum.val % p = 0 ∧ T.sum.val % p ^ 2 ≠ 0 := by  let h_dvd : p ∣ p ^ 2 := dvd_pow_self p (by decide)  let f : ZMod (p ^ 2) →+* ZMod p := ZMod.castHom h_dvd (ZMod p)  let A : Multiset (ZMod (p ^ 2)) := Multiset.replicate (p - 1) 1 + {1 - (p : ZMod (p ^ 2))}  let B : Multiset (ZMod (p ^ 2)) := Multiset.replicate (p - 1) (-1) + {(p : ZMod (p ^ 2)) - 1}  let W := A + B  use W  have hA_card : A.card = p := by    dsimp [A]    simp only [Multiset.card_add, Multiset.card_replicate, Multiset.card_singleton]    exact Nat.sub_add_cancel hp.pos  have hB_card : B.card = p := by    dsimp [B]    simp only [Multiset.card_add, Multiset.card_replicate, Multiset.card_singleton]    exact Nat.sub_add_cancel hp.pos  have hW_card : W.card = 2 * p := by    dsimp [W]    rw [Multiset.card_add, hA_card, hB_card]    ring  refine ⟨hW_card, ?_, ?_⟩  · intro x hx    have h_unit_one : IsUnit (1 : ZMod (p ^ 2)) := isUnit_one    have h_unit_neg_one : IsUnit (-1 : ZMod (p ^ 2)) := isUnit_one.neg    have h_inv : (1 - (p : ZMod (p ^ 2))) * (1 + (p : ZMod (p ^ 2))) = 1 := by      have : (p : ZMod (p ^ 2)) ^ 2 = 0 := by        rw [← Nat.cast_pow, ZMod.natCast_self]      linear_combination -this    have h_unit_1_sub_p : IsUnit (1 - (p : ZMod (p ^ 2))) :=      isUnit_of_dvd_one ⟨1 + (p : ZMod (p ^ 2)), h_inv.symm⟩    have h_unit_p_sub_1 : IsUnit ((p : ZMod (p ^ 2)) - 1) := by      have : (p : ZMod (p ^ 2)) - 1 = - (1 - (p : ZMod (p ^ 2))) := by ring      rw [this]      exact h_unit_1_sub_p.neg    dsimp [W, A, B] at hx    rw [Multiset.mem_add] at hx    rcases hx with hx | hx    · rw [Multiset.mem_add] at hx      rcases hx with hx | hx      · rw [Multiset.eq_of_mem_replicate hx]; exact h_unit_one      · rw [Multiset.mem_singleton.mp hx]; exact h_unit_1_sub_p    · rw [Multiset.mem_add] at hx      rcases hx with hx | hx      · rw [Multiset.eq_of_mem_replicate hx]; exact h_unit_neg_one      · rw [Multiset.mem_singleton.mp hx]; exact h_unit_p_sub_1  · rintro ⟨T, hTW, hT_card, hT_p, hT_p2⟩    have hA_sum : A.sum = 0 := by      dsimp [A]      rw [Multiset.sum_add, Multiset.sum_replicate, Multiset.sum_singleton]      simp only [nsmul_eq_mul, mul_one]      have h1 : ((p - 1 : ℕ) : ZMod (p ^ 2)) + 1 = (p : ZMod (p ^ 2)) := by        rw [← Nat.cast_add_one, Nat.sub_add_cancel hp.pos]      linear_combination h1    have hB_sum : B.sum = 0 := by      dsimp [B]      rw [Multiset.sum_add, Multiset.sum_replicate, Multiset.sum_singleton]      simp only [nsmul_eq_mul, mul_neg, mul_one]      have h1 : ((p - 1 : ℕ) : ZMod (p ^ 2)) + 1 = (p : ZMod (p ^ 2)) := by        rw [← Nat.cast_add_one, Nat.sub_add_cancel hp.pos]      linear_combination -h1    have hfA : ∀ x ∈ A, f x = 1 := by      intro x hx      have h1 : f 1 = 1 := by simp [f]      have h2 : f (1 - (p : ZMod (p ^ 2))) = 1 := by simp [f]      dsimp [A] at hx      rw [Multiset.mem_add] at hx      rcases hx with hx | hx      · rw [Multiset.eq_of_mem_replicate hx]; exact h1      · rw [Multiset.mem_singleton.mp hx]; exact h2    have hfB : ∀ x ∈ B, f x = -1 := by      intro x hx      have h3 : f (-1) = -1 := by simp [f]      have h4 : f ((p : ZMod (p ^ 2)) - 1) = -1 := by simp [f]      dsimp [B] at hx      rw [Multiset.mem_add] at hx      rcases hx with hx | hx      · rw [Multiset.eq_of_mem_replicate hx]; exact h3      · rw [Multiset.mem_singleton.mp hx]; exact h4    have h2_ne_0 : (2 : ZMod p) ≠ 0 := by      intro h      have : (2 : ZMod p) = ((2 : ℕ) : ZMod p) := rfl      rw [this, ZMod.natCast_eq_zero_iff] at h      have : p ≤ 2 := Nat.le_of_dvd (by decide) h      have : p ≥ 2 := hp.two_le      omega    have hneg1_ne_1 : (-1 : ZMod p) ≠ 1 := by      intro h      have : (2 : ZMod p) = 0 := by linear_combination -h      exact h2_ne_0 this    let TA := T.filter (fun x => f x = 1)    let TB := T.filter (fun x => f x ≠ 1)    have hTA_le : TA ≤ A := by      rw [Multiset.le_iff_count]      intro x      by_cases hx : x ∈ TA      · have hfx : f x = 1 := (Multiset.mem_filter.mp hx).2        have hxB : x ∉ B := by          intro h          have := hfB x h          rw [this] at hfx          exact hneg1_ne_1 hfx        have hxB_count : B.count x = 0 := Multiset.count_eq_zero.mpr hxB        have hle := Multiset.count_le_of_le x (Multiset.filter_le (fun x => f x = 1) T)        have hle2 := Multiset.count_le_of_le x hTW        rw [Multiset.count_add, hxB_count, add_zero] at hle2        exact hle.trans hle2      · rw [Multiset.count_eq_zero.mpr hx]        exact Nat.zero_le _    have hTB_le : TB ≤ B := by      rw [Multiset.le_iff_count]      intro x      by_cases hx : x ∈ TB      · have hfx : f x ≠ 1 := (Multiset.mem_filter.mp hx).2        have hxA : x ∉ A := by          intro h          exact hfx (hfA x h)        have hxA_count : A.count x = 0 := Multiset.count_eq_zero.mpr hxA        have hle := Multiset.count_le_of_le x (Multiset.filter_le (fun x => f x ≠ 1) T)        have hle2 := Multiset.count_le_of_le x hTW        rw [Multiset.count_add, hxA_count, zero_add] at hle2        exact hle.trans hle2      · rw [Multiset.count_eq_zero.mpr hx]        exact Nat.zero_le _    have hT_decomp : T = TA + TB := by      exact (Multiset.filter_add_not (fun x => f x = 1) T).symm    have h_cards : TA.card + TB.card = p := by      rw [← Multiset.card_add, ← hT_decomp, hT_card]    have hTA_map : TA.map f = Multiset.replicate TA.card 1 :=      map_const_of_forall_mem TA 1 f (fun x hx => (Multiset.mem_filter.mp hx).2)    have hTB_map : TB.map f = Multiset.replicate TB.card (-1) :=      map_const_of_forall_mem TB (-1) f (fun x hx => hfB x (Multiset.mem_of_le hTB_le hx))    have hT_map_sum : (T.map f).sum = (TA.card : ZMod p) - (TB.card : ZMod p) := by      rw [hT_decomp, Multiset.map_add, Multiset.sum_add, hTA_map, hTB_map]      simp only [Multiset.sum_replicate, nsmul_eq_mul, mul_one, mul_neg]      ring    have h_TB_card : (TB.card : ZMod p) = - (TA.card : ZMod p) := by      have : ((TA.card + TB.card : ℕ) : ZMod p) = (p : ZMod p) := by rw [h_cards]      push_cast at this      rw [ZMod.natCast_self] at this      linear_combination this    have hT_sum_zero : f T.sum = 0 := by      have : f T.sum = (T.sum.val : ZMod p) := by        rw [ZMod.castHom_apply]        have : NeZero (p ^ 2) := ⟨pow_ne_zero 2 hp.ne_zero⟩        exact ZMod.cast_eq_val T.sum      rw [this, ZMod.natCast_eq_zero_iff, Nat.dvd_iff_mod_eq_zero]      exact hT_p    have h_2TA : 2 * (TA.card : ZMod p) = 0 := by      have h1 : (T.map f).sum = 0 := (map_multiset_sum f T).symm.trans hT_sum_zero      calc 2 * (TA.card : ZMod p) = (TA.card : ZMod p) - (- (TA.card : ZMod p)) := by ring      _ = (TA.card : ZMod p) - (TB.card : ZMod p) := by rw [← h_TB_card]      _ = (T.map f).sum := hT_map_sum.symm      _ = 0 := h1    have hTA_zero : (TA.card : ZMod p) = 0 := by      have : Fact p.Prime := ⟨hp⟩      cases mul_eq_zero.mp h_2TA with      | inl h => exact False.elim (h2_ne_0 h)      | inr h => exact h    rw [ZMod.natCast_eq_zero_iff, Nat.dvd_iff_mod_eq_zero] at hTA_zero    have hTA_le_p : TA.card ≤ p := (Multiset.card_le_card hTA_le).trans_eq hA_card    have hTA_cases : TA.card = 0 ∨ TA.card = p := by      rcases Nat.eq_zero_or_pos TA.card with h | h      · left; exact h      · right        have := Nat.le_of_dvd h (Nat.dvd_of_mod_eq_zero hTA_zero)        omega    have hT_sum_eq_zero : T.sum = 0 := by      rcases hTA_cases with h0 | hp_eq      · have hTA_empty : TA = 0 := Multiset.card_eq_zero.mp h0        rw [hTA_empty, zero_add] at hT_decomp        have hTB_eq : TB = B := multiset_eq_of_le_card_eq TB B hTB_le (by omega)        rw [hTB_eq] at hT_decomp        rw [hT_decomp, hB_sum]      · have hTB_zero : TB.card = 0 := by omega        have hTB_empty : TB = 0 := Multiset.card_eq_zero.mp hTB_zero        rw [hTB_empty, add_zero] at hT_decomp        have hTA_eq : TA = A := multiset_eq_of_le_card_eq TA A hTA_le (by omega)        rw [hTA_eq] at hT_decomp        rw [hT_decomp, hA_sum]    have : T.sum.val % p ^ 2 = 0 := by      rw [hT_sum_eq_zero, ZMod.val_zero, Nat.zero_mod]    exact hT_p2 this
See it in the graphDiscuss this resultChallenge it