finset_is_midpoint_balanced_of_has_no_unique_sums
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.
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.
uses
Finset.card_pos.1classical have hcard := hA.1 refine ⟨Finset.card_pos.1 (by omega), fun b hb => ?_⟩
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).
uses
Finset.exists_mem_ne,lt_of_lt_of_le,one_lt_two,Finset.mem_filterhave 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
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.
uses
Sym2.ind,Finset.mk_mem_sym2_iff,Sym2.lift_mkinduction z using Sym2.ind with | h u v => rw [Finset.mk_mem_sym2_iff, Sym2.lift_mk] at hz obtain ⟨⟨hu, hv⟩, huv⟩ := hz
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.
uses
ZMod.natCast_eq_zero_iff,Nat.prime_dvd_prime_iff_eq,Fact.out,Nat.prime_twohave 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')
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.
refine ⟨u, hu, v, hv, ?_, ?_, ?_, huv.symm⟩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).
uses
add_left_cancel· intro h rw [h] at huv have hvb := add_left_cancel huv exact hzb (by rw [h, hvb])
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).
uses
add_right_cancel· intro h rw [h] at huv have hub := add_right_cancel huv exact hzb (by rw [h, hub])
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).
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.
- The non-emptiness of A from 2 ≤ |A| on line 5 is discharged automatically by the linear integer arithmetic tactic `omega`.
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.
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])