nus_min_card_ge_one_add_clog
For 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.
Statement
theorem nus_min_card_ge_one_add_clog {p : ℕ} [Fact p.Prime] (hp : p ≠ 2) :
1 + Nat.clog 2 p ≤ nus_min_card p- Formalizes
- arXiv:2610.09349 (A near-quadratic lower bound for sets with no unique sums), Appendix B (the lower bound 1 + ⌈log₂ p⌉ ≤ m(p), from Lemma B.1).
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- nus_min_cardm(p): the least size of a subset of Z/pZ with no unique sums.
- finset_has_no_unique_sums_univ_zmodFor an odd prime p, the whole of Z/pZ has no unique sums.
- finset_is_midpoint_balanced_of_has_no_unique_sumsFor an odd prime p, every subset of Z/pZ with no unique sums is balanced.
- finset_card_ge_one_add_clog_of_midpoint_balancedFor a prime p, every nonempty balanced subset B of Z/pZ has |B| ≥ 1 + ⌈log₂ p⌉.
- finset_is_midpoint_balancedA finite set B is balanced: it is nonempty and every b ∈ B satisfies 2b = u + v for two distinct elements u, v of B other than b.
- 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 1
- nus_min_card_three_eq_threeThe minimal cardinality of a set with no unique sums in Z/3Z is exactly 3.
The proof, explained
The minimum size m(p) is defined as the infimum of the cardinalities of all subsets of Z/pZ without unique sums. The proof establishes the lower bound 1 + ⌈log₂ p⌉ ≤ m(p) by observing that the full group Z/pZ witnesses nonemptiness, and that every subset without unique sums is midpoint-balanced, which in turn forces its size to be at least 1 + ⌈log₂ p⌉.
To bound nus_min_card p from below, it suffices to show that the set of sizes of subsets without unique sums is nonempty and bounded below by 1 + ⌈log₂ p⌉.
The definition of `nus_min_card p` is the infimum (`sInf`) of the cardinalities of all subsets of Z/pZ having no unique sums. Applying `le_csInf` reduces proving that 1 + ⌈log₂ p⌉ ≤ nus_min_card p to two obligations: that the set of such cardinalities is nonempty, and that 1 + ⌈log₂ p⌉ ≤ b for every element b in that set.
uses
le_csInfunfold nus_min_card apply le_csInf
The set of cardinalities of subsets without unique sums is nonempty.
For an odd prime p, the entire group Z/pZ (`Finset.univ`) has no unique sums by `finset_has_no_unique_sums_univ_zmod`. Its cardinality therefore provides an explicit element witnessing nonemptiness.
uses
finset_has_no_unique_sums_univ_zmod· refine ⟨(Finset.univ : Finset (ZMod p)).card, ⟨Finset.univ, finset_has_no_unique_sums_univ_zmod hp, rfl⟩⟩
Every subset of Z/pZ without unique sums has cardinality at least 1 + ⌈log₂ p⌉.
Given an element b of the set, it is the cardinality |A| of some subset A ⊆ Z/pZ having no unique sums. By `finset_is_midpoint_balanced_of_has_no_unique_sums`, having no unique sums implies that A is midpoint-balanced. Then `finset_card_ge_one_add_clog_of_midpoint_balanced` guarantees that any midpoint-balanced subset has size at least 1 + ⌈log₂ p⌉.
uses
finset_is_midpoint_balanced_of_has_no_unique_sums,finset_card_ge_one_add_clog_of_midpoint_balanced· rintro b ⟨A, hA, rfl⟩ have h_bal := finset_is_midpoint_balanced_of_has_no_unique_sums hp A hA exact finset_card_ge_one_add_clog_of_midpoint_balanced A h_bal
le_csInf- If a set s is nonempty and a is a lower bound for every element of s, then a ≤ sInf s.
finset_has_no_unique_sums_univ_zmod- For any odd prime p, the entire group Z/pZ has no unique sums.
finset_is_midpoint_balanced_of_has_no_unique_sums- For any odd prime p, any subset of Z/pZ with no unique sums is midpoint-balanced.
finset_card_ge_one_add_clog_of_midpoint_balanced- For any prime p, every midpoint-balanced subset B of Z/pZ satisfies |B| ≥ 1 + ⌈log₂ p⌉.
- Because `nus_min_card` is defined as an infimum (`sInf`) in a conditionally complete lattice, `le_csInf` formally requires showing the set is nonempty in addition to showing the lower bound.
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 nus_min_card_ge_one_add_clog {p : ℕ} [Fact p.Prime] (hp : p ≠ 2) : 1 + Nat.clog 2 p ≤ nus_min_card p := by unfold nus_min_card apply le_csInf · refine ⟨(Finset.univ : Finset (ZMod p)).card, ⟨Finset.univ, finset_has_no_unique_sums_univ_zmod hp, rfl⟩⟩ · rintro b ⟨A, hA, rfl⟩ have h_bal := finset_is_midpoint_balanced_of_has_no_unique_sums hp A hA exact finset_card_ge_one_add_clog_of_midpoint_balanced A h_bal