nus_min_card_le_of_has_no_unique_sums
If A is a subset of Z/pZ with no unique sums, then m(p) ≤ |A|.
Statement
theorem nus_min_card_le_of_has_no_unique_sums {p : ℕ} (A : Finset (ZMod p)) (hA : finset_has_no_unique_sums A) : nus_min_card p ≤ A.card- Source
- step towards nus_min_card_ge_c_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- nus_min_cardm(p): the least size of a subset of Z/pZ with no unique sums.
- 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.
- Used by 4
- 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_three_eq_threeThe minimal cardinality of a set with no unique sums in Z/3Z is exactly 3.
- nus_min_card_le_sq_of_midpoint_balancedIf B is a midpoint-balanced subset of Z/pZ, then m(p) ≤ |B|².
The proof, explained
By definition, $m(p)$ (`nus_min_card p`) is the infimum of the cardinalities of all subsets of $\mathbb{Z}/p\mathbb{Z}$ that have no unique sums. Since $A$ is assumed to have no unique sums, its cardinality $|A|$ belongs to this collection of sizes. The inequality $m(p) \le |A|$ then follows directly from the fact that the infimum of a set of natural numbers is at most any of its elements (`Nat.sInf_le`).
It suffices to show that $|A|$ belongs to the set of cardinalities of subsets of $\mathbb{Z}/p\mathbb{Z}$ with no unique sums.
Unfolding the definition of $m(p)$ (`nus_min_card p`), it is the infimum of all cardinalities $k$ for which there exists a subset of $\mathbb{Z}/p\mathbb{Z}$ without unique sums of size $k$. By `Nat.sInf_le`, the infimum of a set of natural numbers is bounded above by any element of the set, reducing the goal to showing that $|A|$ is in this set.
uses
Nat.sInf_leunfold nus_min_card apply Nat.sInf_le
$|A| \in \{k \mid \exists A', \text{finset\_has\_no\_unique\_sums } A' \land |A'| = k\}$
The subset $A$ itself witnesses membership in the set: it satisfies `finset_has_no_unique_sums` by the hypothesis $hA$, and its cardinality is $|A|$.
exact ⟨A, hA, rfl⟩
Nat.sInf_le- For any set of natural numbers $s$ and any element $m \in s$, the infimum $\inf s$ satisfies $\inf s \le m$.
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.
/-- If A is a subset of Z/pZ with no unique sums, then m(p) ≤ |A|. -/theorem nus_min_card_le_of_has_no_unique_sums {p : ℕ} (A : Finset (ZMod p)) (hA : finset_has_no_unique_sums A) : nus_min_card p ≤ A.card := by unfold nus_min_card apply Nat.sInf_le exact ⟨A, hA, rfl⟩