AFTD Auto-Formalizing Theoretical Domains

nus_min_card_ge_one_add_clog

theoremverifiedformalization

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
Used by 1

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

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

    lines 3–4

    uses le_csInf

      unfold nus_min_card
      apply le_csInf
  2. 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.

    line 5

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

    lines 6–8

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

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

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