zero_sum_constant_s_star_lower_bound_witness
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.
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.
uses
Multiset.le_iff_exists_add,Multiset.card_add,Multiset.card_eq_zero,add_zerotheorem 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]
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`).
uses
Multiset.induction_on,Multiset.map_cons,Multiset.card_cons,Multiset.replicate_succ,Multiset.mem_cons_self,Multiset.mem_cons_of_memtheorem 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)
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.
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
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.
uses
Multiset.card_add,Multiset.card_replicate,Multiset.card_singleton,Nat.sub_add_cancelhave 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, ?_, ?_⟩
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.
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
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).
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 -h1The 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.
uses
Multiset.mem_add,Multiset.eq_of_mem_replicate,Multiset.mem_singleton,ZMod.natCast_eq_zero_iff,Nat.le_of_dvdhave 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
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.
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_addlet 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 _
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.
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_selfhave 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
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.
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_zerohave 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
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.
uses
Multiset.card_eq_zero,zero_add,multiset_eq_of_le_card_eq,add_zero,ZMod.val_zero,Nat.zero_modrcases 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.
- The file includes two preliminary helper lemmas: `multiset_eq_of_le_card_eq` (a sub-multiset of equal cardinality equals the original multiset) and `map_const_of_forall_mem` (mapping a constant function over a multiset produces copies of that constant). These are proved in lines 1-20 and invoked in the main proof.
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.
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