AFTD Auto-Formalizing Theoretical Domains

nus_min_card_le_of_has_no_unique_sums

theoremverified

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

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`).

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

    lines 3–4

    uses Nat.sInf_le

      unfold nus_min_card
      apply Nat.sInf_le
  2. $|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|$.

    line 5

      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

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