AFTD Auto-Formalizing Theoretical Domains

nus_min_card_three_eq_three

theoremverified

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

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.

  1. $\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`).

    lines 3–5

    uses nus_min_card_ge_one_add_clog

      have h1 : 1 + Nat.clog 2 3 ≤ nus_min_card 3 := by
        apply nus_min_card_ge_one_add_clog
        decide
  2. $\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$.

    lines 6–9

    uses nus_min_card_le_of_has_no_unique_sums, finset_has_no_unique_sums_univ_zmod_three, Finset.card_univ, ZMod.card

      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
  3. 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.

    lines 10–11

      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

/-- 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
See it in the graphDiscuss this resultChallenge it