nus_min_card_le_sq_of_midpoint_balanced
If B is a midpoint-balanced subset of Z/pZ, then m(p) ≤ |B|².
Statement
theorem nus_min_card_le_sq_of_midpoint_balanced {p : ℕ} (B : Finset (ZMod p)) (hB : finset_is_midpoint_balanced B) : nus_min_card p ≤ B.card ^ 2- Source
- step towards nus_min_card_ge_c_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- nus_min_cardm(p): the least size of a subset of Z/pZ with no unique sums.
- 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_sums_sumset_of_balancedIf B is a nonempty balanced finite subset of an abelian group, then its sumset B + B 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|.
- 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.
The proof, explained
To bound the minimum size m(p) of a subset with no unique sums, the proof considers the sumset B + B. Since B is midpoint-balanced, B + B has no unique sums, which immediately implies m(p) ≤ |B + B|. The size of the sumset is then bounded by |B × B| = |B|², yielding m(p) ≤ |B|².
The sumset B + B has no unique sums.
Applying `finset_has_no_unique_sums_sumset_of_balanced` to B and the hypothesis that B is midpoint-balanced establishes that the sumset (B ×ˢ B).image (+) has no unique sums.
uses
finset_has_no_unique_sums_sumset_of_balancedhave h_nus := finset_has_no_unique_sums_sumset_of_balanced B hBm(p) ≤ |B + B|
Because the sumset B + B has no unique sums, the minimum cardinality m(p) of such a subset in Z/pZ is bounded above by the size of B + B via `nus_min_card_le_of_has_no_unique_sums`.
uses
nus_min_card_le_of_has_no_unique_sumshave h_le := nus_min_card_le_of_has_no_unique_sums ((B ×ˢ B).image (fun x => x.1 + x.2)) h_nus
|B + B| ≤ |B|²
The cardinality of the sumset (the image of B ×ˢ B under addition) is at most |B ×ˢ B| by `Finset.card_image_le`. By `Finset.card_product` and the definition of squaring (`sq`), |B ×ˢ B| = |B| * |B| = |B|².
uses
Finset.card_image_le,Finset.card_product,sqhave h_card : ((B ×ˢ B).image (fun x => x.1 + x.2)).card ≤ B.card ^ 2 := by calc ((B ×ˢ B).image (fun x => x.1 + x.2)).card ≤ (B ×ˢ B).card := Finset.card_image_le _ = B.card ^ 2 := by rw [Finset.card_product, sq]
m(p) ≤ |B|²
Linear arithmetic (`omega`) combines the bounds m(p) ≤ |B + B| and |B + B| ≤ |B|² by transitivity of ≤ on natural numbers.
omega
finset_has_no_unique_sums_sumset_of_balanced- If a finite subset B of an abelian group is midpoint-balanced, then its sumset B + B has no unique sums.
nus_min_card_le_of_has_no_unique_sums- The minimum size m(p) of a subset of Z/pZ with no unique sums is bounded above by the size of any subset that has no unique sums.
Finset.card_image_le- The cardinality of the image of a finite set under a function is at most the cardinality of the domain.
Finset.card_product- The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
sq- The square a² of an element is equal to a * a.
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.
/-- If B is a midpoint-balanced subset of Z/pZ, then m(p) ≤ |B|². -/theorem nus_min_card_le_sq_of_midpoint_balanced {p : ℕ} (B : Finset (ZMod p)) (hB : finset_is_midpoint_balanced B) : nus_min_card p ≤ B.card ^ 2 := by have h_nus := finset_has_no_unique_sums_sumset_of_balanced B hB have h_le := nus_min_card_le_of_has_no_unique_sums ((B ×ˢ B).image (fun x => x.1 + x.2)) h_nus have h_card : ((B ×ˢ B).image (fun x => x.1 + x.2)).card ≤ B.card ^ 2 := by calc ((B ×ˢ B).image (fun x => x.1 + x.2)).card ≤ (B ×ˢ B).card := Finset.card_image_le _ = B.card ^ 2 := by rw [Finset.card_product, sq] omega