finset_has_no_unique_sums_univ_zmod
For an odd prime p, the whole of Z/pZ has no unique sums.
Statement
theorem finset_has_no_unique_sums_univ_zmod {p : ℕ} [Fact p.Prime] (hp : p ≠ 2) :
finset_has_no_unique_sums (Finset.univ : Finset (ZMod p))- Formalizes
- arXiv:2610.09349 (A near-quadratic lower bound for sets with no unique sums), Sec. 1 (F_p itself is NUS: each s has (p+1)/2 ≥ 2 unordered representations).
- Verified
- 09 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- finset_has_no_unique_sumsA has no unique sums (is NUS): |A| ≥ 2 and every sum a + b with a, b ∈ A has at least two representations as an unordered pair from A.
- finset_unordered_sum_rep_countr_{A,2}(s): the number of unordered pairs {a, b} (a = b allowed) of elements of A with a + b = s.
- Used by 4
- nus_min_card_ge_near_quadratic_of_rank_hadamard_boundIf every NUS set A ⊆ Z/pZ satisfies log p ≤ K(√|A| + |A|/log p)·log|A| with K ≥ 1, then m(p) ≥ (1/(32K²))(log p/log log p)² for every…
- nus_min_card_five_eq_fourThe minimal size of a set with no unique sums in Z/5Z is exactly 4 (witness {0,1,2,3}; no set of size ≤ 3 works).
- nus_min_card_seven_eq_fiveThe minimal size of a set with no unique sums in Z/7Z is exactly 5 (witness {0,1,2,3,4}; every set of size ≤ 4 fails).
- nus_min_card_ge_one_add_clogFor an odd prime p, m(p) ≥ 1 + ⌈log₂ p⌉: every subset of Z/pZ with no unique sums has at least 1 + ⌈log₂ p⌉ elements.
The proof, explained
For an odd prime p, the entire group ℤ/pℤ has no unique sums, meaning that |ℤ/pℤ| ≥ 2 and every sum s = a + b has at least two representations as an unordered pair sum. Since p is an odd prime, the cardinality |ℤ/pℤ| = p is at least 3, which is ≥ 2. To find two distinct representations for any sum s, the proof branches on whether s = 1: if s = 1, the pairs {0, 1} and {2, -1} both sum to 1 and are distinct because p ≠ 2 and 1 ≠ 0; if s ≠ 1, the pairs {0, s} and {1, s - 1} both sum to s and are distinct because s ≠ 1 and 1 ≠ 0.
The universe ℤ/pℤ has cardinality at least 2.
By definition, a finset has no unique sums if its cardinality is at least 2 and every pair sum has at least two representations. Splitting the goal with `constructor`, the first requirement asks that |univ| ≥ 2. Rewriting using `Finset.card_univ` and `ZMod.card` transforms this into 2 ≤ p. Since p is prime, 2 ≤ p, and since p ≠ 2, we have 2 < p via `Nat.lt_of_le_of_ne`, which implies 2 ≤ p by `le_of_lt`.
uses
Finset.card_univ,ZMod.card,Nat.lt_of_le_of_ne,Fact.out,Ne.symm,le_of_ltconstructor · rw [Finset.card_univ, ZMod.card p] have : 2 < p := Nat.lt_of_le_of_ne (Fact.out : p.Prime).two_le (Ne.symm hp) exact le_of_lt this
To show every sum s = a + b in ℤ/pℤ has at least two representations, it suffices to consider separately the cases s = 1 and s ≠ 1.
Fixing arbitrary elements a, b ∈ ℤ/pℤ, we unfold `finset_unordered_sum_rep_count` to reveal that we must show the set of unordered pairs in (ℤ/pℤ)⁽²⁾ summing to s = a + b has cardinality at least 2. We then split into two cases: s = 1 and s ≠ 1.
· intros a _ b _ unfold finset_unordered_sum_rep_count set s : ZMod p := a + b by_cases hs : s = 1
When s = 1, it suffices to show that the unordered pairs {0, 1} and {2, -1} both sum to 1 and are distinct.
To show the fiber has cardinality at least 2, we rewrite 2 ≤ |S| as 1 < |S| using `Nat.add_one_le_iff`. By `Finset.one_lt_card.2`, it suffices to exhibit two distinct elements in the fiber. We candidate the unordered pairs s(0, 1) and s(2, -1).
uses
Nat.add_one_le_iff,Finset.one_lt_card.2· rw [Nat.add_one_le_iff] apply Finset.one_lt_card.2 refine ⟨s(0, 1), ?_, s(2, -1), ?_, ?_⟩
Both {0, 1} and {2, -1} belong to the fiber of sums equal to s = 1.
Unfolding membership in the filtered finset via `Finset.mem_filter`, membership in the universe holds trivially. We then check the sum conditions: 0 + 1 = 1 = s holds by `zero_add` and the hypothesis s = 1, while 2 + (-1) = 1 = s holds by ring arithmetic and s = 1.
uses
Finset.mem_filter,zero_add· rw [Finset.mem_filter] refine ⟨by simp, ?_⟩ show (0 : ZMod p) + 1 = s rw [hs, zero_add] · rw [Finset.mem_filter] refine ⟨by simp, ?_⟩ show (2 : ZMod p) + (-1) = s rw [hs] ring
Assuming {0, 1} = {2, -1}, the equality branch 0 = 2 is impossible because p ≠ 2.
By `Sym2.eq_iff`, equality of the unordered pairs {0, 1} = {2, -1} implies either (0 = 2 ∧ 1 = -1) or (0 = -1 ∧ 1 = 2). In the first branch, 0 = 2 in ℤ/pℤ implies p ∣ 2 by `CharP.cast_eq_zero_iff`. Since 2 > 0, this yields p ≤ 2 by `Nat.le_of_dvd`. Combined with 2 ≤ p for primes, antisymmetry gives p = 2, which contradicts the hypothesis p ≠ 2.
uses
Sym2.eq_iff,CharP.cast_eq_zero_iff,Nat.le_of_dvd,Fact.out,Nat.le_antisymm· intro h rw [Sym2.eq_iff] at h rcases h with ⟨h02, -⟩ | ⟨h0neg, -⟩ · have hp2 : p ∣ 2 := (CharP.cast_eq_zero_iff (ZMod p) p 2).mp h02.symm have hle := Nat.le_of_dvd (by decide) hp2 have hge : 2 ≤ p := (Fact.out : p.Prime).two_le exact hp (Nat.le_antisymm hle hge)
Assuming {0, 1} = {2, -1}, the equality branch 0 = -1 is impossible because 1 ≠ 0.
In the second branch where 0 = -1 in ℤ/pℤ, negating both sides gives 1 = -(-1) = -0 = 0. But 1 ≠ 0 by `one_ne_zero`, yielding a contradiction.
uses
one_ne_zero· have : (1 : ZMod p) = 0 := by calc (1 : ZMod p) = - (-1) := by ring _ = - 0 := by rw [← h0neg] _ = 0 := by ring exact one_ne_zero this
When s ≠ 1, it suffices to show that {0, s} and {1, s - 1} both sum to s and are distinct.
Rewriting 2 ≤ |S| as 1 < |S| via `Nat.add_one_le_iff` and applying `Finset.one_lt_card.2`, it suffices to exhibit two distinct elements in the fiber. We candidate the unordered pairs s(0, s) and s(1, s - 1).
uses
Nat.add_one_le_iff,Finset.one_lt_card.2· rw [Nat.add_one_le_iff] apply Finset.one_lt_card.2 refine ⟨s(0, s), ?_, s(1, s - 1), ?_, ?_⟩
Both {0, s} and {1, s - 1} belong to the fiber of sums equal to s.
Using `Finset.mem_filter`, membership in the universe is trivial. The sum condition 0 + s = s holds by `zero_add`, and 1 + (s - 1) = s holds by ring arithmetic.
uses
Finset.mem_filter,zero_add· rw [Finset.mem_filter] refine ⟨by simp, ?_⟩ show (0 : ZMod p) + s = s exact zero_add s · rw [Finset.mem_filter] refine ⟨by simp, ?_⟩ show (1 : ZMod p) + (s - 1) = s ring
The unordered pairs {0, s} and {1, s - 1} are distinct when s ≠ 1.
Assuming equality of the unordered pairs, `Sym2.eq_iff` implies either (0 = 1 ∧ s = s - 1) or (0 = s - 1 ∧ s = 1). The first case is refuted by 1 ≠ 0 via `one_ne_zero`. The second case gives s = 1, directly contradicting the assumption s ≠ 1.
uses
Sym2.eq_iff,one_ne_zero· intro h rw [Sym2.eq_iff] at h rcases h with ⟨h01, -⟩ | ⟨-, hs1⟩ · exact one_ne_zero h01.symm · exact hs hs1
CharP.cast_eq_zero_iff- In a ring of characteristic p, the cast of a natural number x is zero if and only if p divides x.
Finset.card_univ- The cardinality of the universal finset `Finset.univ` on a finite type equals the cardinality of the type.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.one_lt_card.2- If a finite set contains at least two distinct elements, its cardinality is strictly greater than 1.
Fact.out- Extracts the underlying proposition asserted by a `Fact` typeclass instance.
Nat.add_one_le_iff- For natural numbers, n + 1 ≤ m if and only if n < m.
Nat.le_antisymm- If n ≤ m and m ≤ n for natural numbers, then n = m.
Nat.le_of_dvd- If a natural number divides a strictly positive natural number, it is less than or equal to it.
Nat.lt_of_le_of_ne- A natural number less than or equal to another and not equal to it is strictly less than it.
Ne.symm- Disequality is symmetric: if a ≠ b, then b ≠ a.
Sym2.eq_iff- Two unordered pairs {x, y} and {z, w} are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
ZMod.card- The cardinality of the ring ℤ/nℤ is n.
le_of_lt- A strict inequality implies the corresponding non-strict inequality.
one_ne_zero- In a nontrivial ring, 1 is not equal to 0.
zero_add- Zero is an additive identity on the left: 0 + a = a.
- `Sym2` denotes the symmetric square of a type, representing unordered pairs, with notation `s(x, y)`.
- `Finset.one_lt_card.2` uses projection notation for the right-to-left direction (`mpr`) of `Finset.one_lt_card`.
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 finset_has_no_unique_sums_univ_zmod {p : ℕ} [Fact p.Prime] (hp : p ≠ 2) : finset_has_no_unique_sums (Finset.univ : Finset (ZMod p)) := by constructor · rw [Finset.card_univ, ZMod.card p] have : 2 < p := Nat.lt_of_le_of_ne (Fact.out : p.Prime).two_le (Ne.symm hp) exact le_of_lt this · intros a _ b _ unfold finset_unordered_sum_rep_count set s : ZMod p := a + b by_cases hs : s = 1 · rw [Nat.add_one_le_iff] apply Finset.one_lt_card.2 refine ⟨s(0, 1), ?_, s(2, -1), ?_, ?_⟩ · rw [Finset.mem_filter] refine ⟨by simp, ?_⟩ show (0 : ZMod p) + 1 = s rw [hs, zero_add] · rw [Finset.mem_filter] refine ⟨by simp, ?_⟩ show (2 : ZMod p) + (-1) = s rw [hs] ring · intro h rw [Sym2.eq_iff] at h rcases h with ⟨h02, -⟩ | ⟨h0neg, -⟩ · have hp2 : p ∣ 2 := (CharP.cast_eq_zero_iff (ZMod p) p 2).mp h02.symm have hle := Nat.le_of_dvd (by decide) hp2 have hge : 2 ≤ p := (Fact.out : p.Prime).two_le exact hp (Nat.le_antisymm hle hge) · have : (1 : ZMod p) = 0 := by calc (1 : ZMod p) = - (-1) := by ring _ = - 0 := by rw [← h0neg] _ = 0 := by ring exact one_ne_zero this · rw [Nat.add_one_le_iff] apply Finset.one_lt_card.2 refine ⟨s(0, s), ?_, s(1, s - 1), ?_, ?_⟩ · rw [Finset.mem_filter] refine ⟨by simp, ?_⟩ show (0 : ZMod p) + s = s exact zero_add s · rw [Finset.mem_filter] refine ⟨by simp, ?_⟩ show (1 : ZMod p) + (s - 1) = s ring · intro h rw [Sym2.eq_iff] at h rcases h with ⟨h01, -⟩ | ⟨-, hs1⟩ · exact one_ne_zero h01.symm · exact hs hs1