AFTD Auto-Formalizing Theoretical Domains

nus_min_card_le_sq_of_midpoint_balanced

theoremverified

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

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

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

    line 3

    uses finset_has_no_unique_sums_sumset_of_balanced

      have h_nus := finset_has_no_unique_sums_sumset_of_balanced B hB
  2. m(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`.

    line 4

    uses nus_min_card_le_of_has_no_unique_sums

      have h_le := nus_min_card_le_of_has_no_unique_sums ((B ×ˢ B).image (fun x => x.1 + x.2)) h_nus
  3. |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|².

    lines 5–8

    uses Finset.card_image_le, Finset.card_product, sq

      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]
  4. m(p) ≤ |B|²

    Linear arithmetic (`omega`) combines the bounds m(p) ≤ |B + B| and |B + B| ≤ |B|² by transitivity of ≤ on natural numbers.

    line 9

      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

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