AFTD Auto-Formalizing Theoretical Domains

finset_is_midpoint_balanced_of_has_no_unique_sums

theoremverifiedformalization

For an odd prime p, every subset of Z/pZ with no unique sums is balanced.

Statement

theorem finset_is_midpoint_balanced_of_has_no_unique_sums {p : ℕ} [Fact p.Prime] (hp : p ≠ 2)
    (A : Finset (ZMod p)) (hA : finset_has_no_unique_sums A) : finset_is_midpoint_balanced A
Formalizes
arXiv:2610.09349 (A near-quadratic lower bound for sets with no unique sums), Lemma B.1 (first statement: every NUS set in odd characteristic is balanced).
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • 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_unordered_sum_rep_countr_{A,2}(s): the number of unordered pairs {a, b} (a = b allowed) of elements of A with a + b = s.
Used by 1
  • nus_min_card_ge_one_add_clogFor 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.

The proof, explained

To show that a subset A ⊆ Z/pZ with no unique sums is midpoint-balanced, we show that A is non-empty and that every b ∈ A is the midpoint of two distinct elements u, v ∈ A ∖ {b}. Non-emptiness is immediate since |A| ≥ 2. For any b ∈ A, the sum b + b has at least two unordered sum representations from A, so there exists a non-trivial representation {u, v} ≠ {b, b} with u + v = b + b. Setting u = b or v = b immediately forces the other element to equal b by additive cancellation, while setting u = v gives 2u = 2b, which forces u = v = b because p ≠ 2 implies 2 is non-zero (and hence invertible) in Z/pZ.

  1. The set A is non-empty, and it suffices to find distinct witnesses u, v ∈ A ∖ {b} with b + b = u + v for each b ∈ A.

    By assumption, 2 ≤ |A|, so |A| > 0, which implies A is non-empty via Finset.card_pos.1. By definition of midpoint-balanced, it then suffices to fix an arbitrary b ∈ A and show the existence of u, v ∈ A distinct from each other and from b such that b + b = u + v.

    lines 3–5

    uses Finset.card_pos.1

      classical
      have hcard := hA.1
      refine ⟨Finset.card_pos.1 (by omega), fun b hb => ?_⟩
  2. There exists an unordered pair z in A.sym2 distinct from s(b, b) whose sum is b + b.

    Because A has no unique sums, the sum b + b has at least two unordered sum representations from A. Since 1 < 2 ≤ |{z ∈ A.sym2 | sum(z) = b + b}|, Finset.exists_mem_ne provides an unordered pair z in this filtered set that is not equal to the trivial pair s(b, b).

    lines 6–9

    uses Finset.exists_mem_ne, lt_of_lt_of_le, one_lt_two, Finset.mem_filter

      have h2 := hA.2 b hb b hb
      unfold finset_unordered_sum_rep_count at h2
      obtain ⟨z, hz, hzb⟩ := Finset.exists_mem_ne (lt_of_lt_of_le one_lt_two h2) s(b, b)
      rw [Finset.mem_filter] at hz
  3. The pair z has the form s(u, v) with u, v ∈ A, u + v = b + b, and s(u, v) ≠ s(b, b).

    By Sym2.ind, every element of the symmetric square can be written as s(u, v). Unfolding membership in A.sym2 gives u, v ∈ A, and evaluating the lifted sum yields u + v = b + b.

    lines 10–13

    uses Sym2.ind, Finset.mk_mem_sym2_iff, Sym2.lift_mk

      induction z using Sym2.ind with
      | h u v =>
        rw [Finset.mk_mem_sym2_iff, Sym2.lift_mk] at hz
        obtain ⟨⟨hu, hv⟩, huv⟩ := hz
  4. 2 ≠ 0 in ZMod p.

    If 2 = 0 in ZMod p, then p divides 2 by ZMod.natCast_eq_zero_iff. Since both p and 2 are prime, this would force p = 2 by Nat.prime_dvd_prime_iff_eq, which contradicts the hypothesis p ≠ 2.

    lines 14–18

    uses ZMod.natCast_eq_zero_iff, Nat.prime_dvd_prime_iff_eq, Fact.out, Nat.prime_two

        have two_ne : (2 : ZMod p) ≠ 0 := by
          intro h
          have h' : ((2 : ℕ) : ZMod p) = 0 := by exact_mod_cast h
          rw [ZMod.natCast_eq_zero_iff] at h'
          exact hp ((Nat.prime_dvd_prime_iff_eq Fact.out Nat.prime_two).1 h')
  5. Choosing u and v as the candidates, it remains to verify u ≠ b, v ≠ b, and u ≠ v.

    Since u, v ∈ A and u + v = b + b (hence b + b = u + v), the elements u and v satisfy the midpoint condition once they are shown to be distinct from b and each other.

    line 19

        refine ⟨u, hu, v, hv, ?_, ?_, ?_, huv.symm⟩
  6. u ≠ b.

    Assuming u = b, substituting into u + v = b + b gives b + v = b + b. Left additive cancellation forces v = b, which implies s(u, v) = s(b, b), contradicting s(u, v) ≠ s(b, b).

    lines 20–23

    uses add_left_cancel

        · intro h
          rw [h] at huv
          have hvb := add_left_cancel huv
          exact hzb (by rw [h, hvb])
  7. v ≠ b.

    Assuming v = b, substituting into u + v = b + b gives u + b = b + b. Right additive cancellation forces u = b, which implies s(u, v) = s(b, b), again contradicting s(u, v) ≠ s(b, b).

    lines 24–27

    uses add_right_cancel

        · intro h
          rw [h] at huv
          have hub := add_right_cancel huv
          exact hzb (by rw [h, hub])
  8. u ≠ v.

    Assuming u = v, we have v + v = b + b, which rewrites as 2 * v = 2 * b via two_mul. Since 2 ≠ 0 in ZMod p, we can cancel 2 using mul_left_cancel₀ to conclude v = b, and hence u = b, which once more contradicts s(u, v) ≠ s(b, b).

    lines 28–31

    uses mul_left_cancel₀, two_mul

        · intro h
          rw [h] at huv
          have hvb : v = b := mul_left_cancel₀ two_ne (by rw [two_mul, two_mul]; exact huv)
          exact hzb (by rw [h, hvb])
Finset.card_pos.1
A finite set is non-empty if and only if its cardinality is strictly positive.
Finset.exists_mem_ne
In any finite set with cardinality greater than 1, there exists an element distinct from any specified element.
lt_of_lt_of_le
Strict inequality combined with non-strict inequality is strictly transitive: if a < b and b ≤ c, then a < c.
one_lt_two
The number 1 is strictly less than 2.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the filter predicate.
Sym2.ind
Induction principle for the symmetric square: any property of unordered pairs holds if it holds for all pairs s(x, y).
Finset.mk_mem_sym2_iff
An unordered pair s(a, b) belongs to the symmetric square of s if and only if both a and b belong to s.
Sym2.lift_mk
Lifting a symmetric binary function to the symmetric square evaluates on s(a, b) as the function applied to a and b.
ZMod.natCast_eq_zero_iff
The canonical image of a natural number a in ZMod b is zero if and only if b divides a.
Nat.prime_dvd_prime_iff_eq
For prime numbers p and q, p divides q if and only if p = q.
Fact.out
Extracts the underlying fact from a Fact typeclass instance.
Nat.prime_two
The natural number 2 is prime.
add_left_cancel
Left cancellation in an additive structure: if a + b = a + c, then b = c.
add_right_cancel
Right cancellation in an additive structure: if a + b = c + b, then a = c.
mul_left_cancel₀
Left cancellation of multiplication by a non-zero element in a domain: if a ≠ 0 and a * b = a * c, then b = c.
two_mul
Multiplication by 2 in a semiring satisfies 2 * n = n + 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

theorem finset_is_midpoint_balanced_of_has_no_unique_sums {p : ℕ} [Fact p.Prime] (hp : p ≠ 2)    (A : Finset (ZMod p)) (hA : finset_has_no_unique_sums A) : finset_is_midpoint_balanced A := by  classical  have hcard := hA.1  refine ⟨Finset.card_pos.1 (by omega), fun b hb => ?_⟩  have h2 := hA.2 b hb b hb  unfold finset_unordered_sum_rep_count at h2  obtain ⟨z, hz, hzb⟩ := Finset.exists_mem_ne (lt_of_lt_of_le one_lt_two h2) s(b, b)  rw [Finset.mem_filter] at hz  induction z using Sym2.ind with  | h u v =>    rw [Finset.mk_mem_sym2_iff, Sym2.lift_mk] at hz    obtain ⟨⟨hu, hv⟩, huv⟩ := hz    have two_ne : (2 : ZMod p) ≠ 0 := by      intro h      have h' : ((2 : ℕ) : ZMod p) = 0 := by exact_mod_cast h      rw [ZMod.natCast_eq_zero_iff] at h'      exact hp ((Nat.prime_dvd_prime_iff_eq Fact.out Nat.prime_two).1 h')    refine ⟨u, hu, v, hv, ?_, ?_, ?_, huv.symm⟩    · intro h      rw [h] at huv      have hvb := add_left_cancel huv      exact hzb (by rw [h, hvb])    · intro h      rw [h] at huv      have hub := add_right_cancel huv      exact hzb (by rw [h, hub])    · intro h      rw [h] at huv      have hvb : v = b := mul_left_cancel₀ two_ne (by rw [two_mul, two_mul]; exact huv)      exact hzb (by rw [h, hvb])
See it in the graphDiscuss this resultChallenge it