nus_min_card_three_eq_three
The minimal cardinality of a set with no unique sums in Z/3Z is exactly 3.
Statement
theorem nus_min_card_three_eq_three : nus_min_card 3 = 3- Source
- step towards nus_min_card_ge_c_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- nus_min_cardm(p): the least size of a subset of Z/pZ with no unique sums.
- 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.
- finset_has_no_unique_sums_univ_zmod_threeThe whole of Z/3Z has no unique sums.
- nus_min_card_le_of_has_no_unique_sumsIf A is a subset of Z/pZ with no unique sums, then m(p) ≤ |A|.
The proof, explained
The theorem is proved by sandwiching the minimal cardinality between matching lower and upper bounds. The lower bound $\mathrm{nus\_min\_card}(3) \ge 1 + \lceil \log_2 3 \rceil = 3$ is supplied by the general bound for odd primes. The upper bound $\mathrm{nus\_min\_card}(3) \le 3$ is witnessed by the universal set $\mathbb{Z}/3\mathbb{Z}$ itself, which is known to have no unique sums and contains 3 elements.
$\mathrm{nus\_min\_card}(3) \ge 1 + \lceil \log_2 3 \rceil$
We invoke the general lower bound `nus_min_card_ge_one_add_clog`, which holds for any odd prime $p$. The primality of $3$ is resolved by typeclass inference, and the requirement $3 \neq 2$ is verified by computational reflection (`decide`).
uses
nus_min_card_ge_one_add_cloghave h1 : 1 + Nat.clog 2 3 ≤ nus_min_card 3 := by apply nus_min_card_ge_one_add_clog decide
$\mathrm{nus\_min\_card}(3) \le 3$
By `nus_min_card_le_of_has_no_unique_sums`, any subset with no unique sums bounds the minimal cardinality from above. The universal set $\mathbb{Z}/3\mathbb{Z}$ satisfies this property by `finset_has_no_unique_sums_univ_zmod_three`. Rewriting its cardinality using `Finset.card_univ` and `ZMod.card` shows $|\mathbb{Z}/3\mathbb{Z}| = 3$, giving the upper bound $\mathrm{nus\_min\_card}(3) \le 3$.
uses
nus_min_card_le_of_has_no_unique_sums,finset_has_no_unique_sums_univ_zmod_three,Finset.card_univ,ZMod.cardhave h2 : nus_min_card 3 ≤ (Finset.univ : Finset (ZMod 3)).card := by apply nus_min_card_le_of_has_no_unique_sums exact finset_has_no_unique_sums_univ_zmod_three rw [Finset.card_univ, ZMod.card 3] at h2
The lower and upper bounds sandwich $\mathrm{nus\_min\_card}(3)$ to equal $3$.
Evaluating the ceiling logarithm yields $\lceil \log_2 3 \rceil = 2$ by definitional equality (`rfl`), turning the lower bound into $1 + 2 = 3 \le \mathrm{nus\_min\_card}(3)$. Together with the upper bound $\mathrm{nus\_min\_card}(3) \le 3$, linear integer arithmetic (`omega`) closes the goal.
have hc : Nat.clog 2 3 = 2 := rfl omega
nus_min_card_ge_one_add_clog- For an odd prime $p$, the minimal cardinality of a set with no unique sums in $\mathbb{Z}/p\mathbb{Z}$ is at least $1 + \lceil \log_2 p \rceil$.
nus_min_card_le_of_has_no_unique_sums- If a finite subset $A \subseteq \mathbb{Z}/p\mathbb{Z}$ has no unique sums, then the minimal cardinality of such a set is at most $|A|$.
finset_has_no_unique_sums_univ_zmod_three- The entire group $\mathbb{Z}/3\mathbb{Z}$, viewed as a finite set, has no unique sums.
Finset.card_univ- The cardinality of the universal finset of a finite type is the cardinality of the type itself.
ZMod.card- The cardinality of the type $\mathbb{Z}/n\mathbb{Z}$ is $n$.
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.
/-- The minimal cardinality of a set with no unique sums in Z/3Z is exactly 3. -/theorem nus_min_card_three_eq_three : nus_min_card 3 = 3 := by have h1 : 1 + Nat.clog 2 3 ≤ nus_min_card 3 := by apply nus_min_card_ge_one_add_clog decide have h2 : nus_min_card 3 ≤ (Finset.univ : Finset (ZMod 3)).card := by apply nus_min_card_le_of_has_no_unique_sums exact finset_has_no_unique_sums_univ_zmod_three rw [Finset.card_univ, ZMod.card 3] at h2 have hc : Nat.clog 2 3 = 2 := rfl omega