finset_has_no_unique_sums_sumset_of_balanced
If B is a nonempty balanced finite subset of an abelian group, then its sumset B + B has no unique sums.
Statement
theorem finset_has_no_unique_sums_sumset_of_balanced {G : Type*} [AddCommGroup G] [DecidableEq G] (B : Finset G) (hB : finset_is_midpoint_balanced B) : finset_has_no_unique_sums ((B ×ˢ B).image (fun x => x.1 + x.2))
- Formalizes
- arXiv:2610.09349 (A near-quadratic lower bound for sets with no unique sums), Lemma A.2. Stated in any abelian group (the paper: F_p); B + B is written as the image of B × B under addition.
- 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_le_sq_of_midpoint_balancedIf B is a midpoint-balanced subset of Z/pZ, then m(p) ≤ |B|².
The proof, explained
To show that the sumset $A = B + B$ of a midpoint-balanced finite set $B$ has no unique sums, we verify that $|A| \ge 2$ and that every sum of elements of $A$ has at least two unordered sum representations. The size condition $|A| \ge 2$ follows because any element $b \in B$ has distinct balance witnesses $u, v \in B$, yielding distinct sums $b + u, b + v \in A$. For any $p = a + b$ and $q = c + d$ in $A$, regrouping $(a + b) + (c + d)$ as $(a + c) + (b + d)$ or $(a + d) + (b + c)$ provides a second representation whenever these pairs are distinct from $\{p, q\}$. When both regroupings collapse, cancellation forces $\{p, q\}$ to be of the degenerate form $\{2x, x + y\}$ for some $x, y \in B$. In this degenerate case, the midpoint balance condition $2x = u + v$ supplies an alternative representation by splitting the total as $(u + y) + (v + x)$ or $(v + y) + (u + x)$.
The sumset $A = B + B$ is defined, and any sum $a + b$ with $a, b \in B$ belongs to $A$.
We define $A$ as the image of the Cartesian product $B \times B$ under addition and establish the helper lemma `memA`: for all $a, b \in B$, the sum $a + b$ lies in $A$.
uses
Finset.mem_image.2,Finset.mem_product.2classical set A := (B ×ˢ B).image (fun x : G × G => x.1 + x.2) with hA have memA : ∀ a ∈ B, ∀ b ∈ B, a + b ∈ A := fun a ha b hb => Finset.mem_image.2 ⟨(a, b), Finset.mem_product.2 ⟨ha, hb⟩, rfl⟩
If $p, q, r, t \in A$ satisfy $p + q = r + t$ with $r \ne p$ and $r \ne q$, then $p + q$ has at least two unordered sum representations in $A$.
By definition, the representation count of $p + q$ is the cardinality of the fiber of addition on the symmetric square $A.sym2$. By `Nat.succ_le_iff` and `Finset.one_lt_card`, it suffices to exhibit two distinct elements in this fiber. We show $s(p, q)$ and $s(r, t)$ both belong to the fiber, and they are distinct because $r \ne p$ and $r \ne q$ prevent $r$ from belonging to $\{p, q\}$.
uses
Nat.succ_le_iff,Finset.one_lt_card,Finset.mem_filter,Finset.mk_mem_sym2_iff,Sym2.mem_mk_left,Sym2.mem_iff.1-- two different unordered pairs with the same total give two representations have two : ∀ p q r t : G, p ∈ A → q ∈ A → r ∈ A → t ∈ A → p + q = r + t → r ≠ p → r ≠ q → 2 ≤ finset_unordered_sum_rep_count A (p + q) := by intro p q r t hp hq hr ht hsum hrp hrq unfold finset_unordered_sum_rep_count rw [Nat.succ_le_iff, Finset.one_lt_card] refine ⟨s(p, q), ?_, s(r, t), ?_, ?_⟩ · simp [Finset.mem_filter, Finset.mk_mem_sym2_iff, hp, hq] · simp [Finset.mem_filter, Finset.mk_mem_sym2_iff, hr, ht, hsum] · intro h have : r ∈ s(p, q) := h ▸ Sym2.mem_mk_left r t rcases Sym2.mem_iff.1 this with h' | h' · exact hrp h' · exact hrq h'
For any $x, y \in B$, there exist $r, t \in A$ with $r + t = 2x + (x + y)$ such that $r \ne 2x$ and $r \ne x + y$.
Because $B$ is midpoint-balanced, $x$ has distinct balance witnesses $u, v \in B \setminus \{x\}$ with $2x = u + v$. The candidates $u + y$ and $v + x$ in $A$ sum to $(u + v) + (x + y) = 2x + (x + y)$. If $u + y \ne 2x$, this pair works, since $u + y = x + y$ would imply $u = x$ by cancellation, a contradiction. If instead $u + y = 2x$, we take $v + y$ and $u + x$; then $v + y \ne 2x$ (which would force $v = u$) and $v + y \ne x + y$ (which would force $v = x$).
uses
add_right_cancel-- the repair of a pair `{x + x, x + y}`, from the balance of `x` have key : ∀ x ∈ B, ∀ y ∈ B, ∃ r ∈ A, ∃ t ∈ A, r + t = (x + x) + (x + y) ∧ r ≠ x + x ∧ r ≠ x + y := by intro x hx y hy obtain ⟨u, hu, v, hv, hux, hvx, huv, hxuv⟩ := hB.2 x hx by_cases hu' : u + y = x + x · refine ⟨v + y, memA v hv y hy, u + x, memA u hu x hx, ?_, ?_, ?_⟩ · rw [hxuv]; abel · intro h; exact huv (add_right_cancel (hu'.trans h.symm)) · intro h; exact hvx (add_right_cancel h) · refine ⟨u + y, memA u hu y hy, v + x, memA v hv x hx, ?_, hu', ?_⟩ · rw [hxuv]; abel · intro h; exact hux (add_right_cancel h)
Any sum of elements in $A$ forming an unordered pair $\{2x, x + y\}$ for $x, y \in B$ has representation count at least 2 in $A$.
Applying the repair lemma `key` provides an alternative pair of summands $r, t \in A$ that total $2x + (x + y)$ and differ from $\{2x, x + y\}$. The criterion `two` then immediately guarantees at least two unordered representations.
have fin : ∀ x ∈ B, ∀ y ∈ B, ∀ p q : G, p ∈ A → q ∈ A → ((p = x + x ∧ q = x + y) ∨ (p = x + y ∧ q = x + x)) → 2 ≤ finset_unordered_sum_rep_count A (p + q) := by intro x hx y hy p q hp hq hpq obtain ⟨r, hr, t, ht, hs, hr1, hr2⟩ := key x hx y hy rcases hpq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact two _ _ r t hp hq hr ht hs.symm hr1 hr2 · exact two _ _ r t hp hq hr ht (by rw [hs]; abel) hr2 hr1
The sumset $A$ contains at least two distinct elements, so $|A| \ge 2$.
To verify the first clause of `finset_has_no_unique_sums`, we choose an element $b \in B$ (nonempty by balance) and distinct balance witnesses $u, v \in B$. The sums $b + u$ and $b + v$ belong to $A$ and are distinct by additive cancellation of $b$, so $A$ has cardinality at least 2 by `Finset.one_lt_card`.
uses
Nat.succ_le_iff,Finset.one_lt_card,add_left_cancelrefine ⟨?_, ?_⟩ · obtain ⟨b, hb⟩ := hB.1 obtain ⟨u, hu, v, hv, -, -, huv, -⟩ := hB.2 b hb rw [Nat.succ_le_iff, Finset.one_lt_card] exact ⟨b + u, memA b hb u hu, b + v, memA b hb v hv, fun h => huv (add_left_cancel h)⟩
For $p = a + b$ and $q = c + d$ in $A$, if either generic regrouping $(a + c) + (b + d)$ or $(a + d) + (b + c)$ avoids $\{p, q\}$, then $p + q$ has representation count at least 2.
Any elements $p, q \in A$ can be written as $a + b$ and $c + d$ with $a, b, c, d \in B$. Their sum can be rearranged as $(a + c) + (b + d)$ or $(a + d) + (b + c)$, each a sum of two elements of $A$. If $a + c$ differs from both $a + b$ and $c + d$, the first regrouping yields a second representation by lemma `two`. Otherwise, if $a + d$ differs from both, the second regrouping yields a second representation by lemma `two`.
uses
Finset.mem_image.1,Finset.mem_product.1· intro p hp q hq obtain ⟨⟨a, b⟩, hab, rfl⟩ := Finset.mem_image.1 hp obtain ⟨⟨c, d⟩, hcd, rfl⟩ := Finset.mem_image.1 hq obtain ⟨ha, hb⟩ := Finset.mem_product.1 hab obtain ⟨hc, hd⟩ := Finset.mem_product.1 hcd dsimp only at hp hq ⊢ by_cases h1 : a + c ≠ a + b ∧ a + c ≠ c + d · exact two _ _ (a + c) (b + d) hp hq (memA a ha c hc) (memA b hb d hd) (by abel) h1.1 h1.2 by_cases h2 : a + d ≠ a + b ∧ a + d ≠ c + d · exact two _ _ (a + d) (b + c) hp hq (memA a ha d hd) (memA b hb c hc) (by abel) h2.1 h2.2
If both generic regroupings collide with $\{p, q\}$, then $(c = b \lor a = d)$ and $(d = b \lor a = c)$.
Failure of the first regrouping means $a + c = a + b$ or $a + c = c + d$, which cancels to $c = b$ or $a = d$. Similarly, failure of the second regrouping means $a + d = a + b$ or $a + d = c + d$, which cancels to $d = b$ or $a = c$.
uses
add_left_cancel,add_right_cancel,add_commhave hcb : c = b ∨ a = d := by by_contra hne push_neg at hne exact h1 ⟨fun h => hne.1 (add_left_cancel h), fun h => hne.2 (add_right_cancel (h.trans (add_comm c d)))⟩ have hdb : d = b ∨ a = c := by by_contra hne push_neg at hne exact h2 ⟨fun h => hne.1 (add_left_cancel h), fun h => hne.2 (add_right_cancel h)⟩
In all cases where both regroupings collide, the representation count of $p + q$ is at least 2.
We analyze the four combinations of $c = b \lor a = d$ and $d = b \lor a = c$: if $c = b$ and $d = b$, then $\{p, q\} = \{b + a, 2b\}$; if $c = b$ and $a = c$, then $a = b$ and $\{p, q\} = \{2b, b + d\}$; if $a = d$ and $d = b$, then $a = b$ and $\{p, q\} = \{2b, b + c\}$; if $a = d$ and $a = c$, then $c = d$ and $\{p, q\} = \{a + b, 2a\}$. In every subcase, $\{p, q\}$ matches the form $\{2x, x + y\}$, so lemma `fin` applies and completes the proof.
uses
add_comm,Or.inr,Or.inlrcases hcb with hcb | had <;> rcases hdb with hdb | hac · exact fin b hb a ha _ _ hp hq (Or.inr ⟨add_comm a b, by rw [hcb, hdb]⟩) · have hab' : a = b := hac.trans hcb exact fin b hb d hd _ _ hp hq (Or.inl ⟨by rw [hab'], by rw [hcb]⟩) · have hab' : a = b := had.trans hdb exact fin b hb c hc _ _ hp hq (Or.inl ⟨by rw [hab'], by rw [hdb, add_comm]⟩) · exact fin a ha b hb _ _ hp hq (Or.inr ⟨rfl, by rw [← hac, ← had]⟩)
add_comm- In an abelian group, addition is commutative: $a + b = b + a$.
add_left_cancel- In an additive group, left cancellation holds: $c + a = c + b$ implies $a = b$.
add_right_cancel- In an additive group, right cancellation holds: $a + c = b + c$ implies $a = b$.
Finset.mem_image.1- An element $y$ belongs to the image $f(s)$ if and only if there is some $x \in s$ with $f(x) = y$; here used in the forward direction.
Finset.mem_image.2- An element $y$ belongs to the image $f(s)$ if there is some $x \in s$ with $f(x) = y$; here used in the reverse direction to construct membership.
Finset.mem_filter- An element belongs to the filtered finset $\{x \in s \mid P(x)\}$ if and only if it belongs to $s$ and satisfies $P$.
Finset.mem_product.1- A pair $(x, y)$ belongs to the Cartesian product $s \times t$ implies $x \in s$ and $y \in t$.
Finset.mem_product.2- If $x \in s$ and $y \in t$, then $(x, y) \in s \times t$.
Finset.mk_mem_sym2_iff- An unordered pair $s(a, b)$ belongs to the symmetric square $s.sym2$ if and only if both $a \in s$ and $b \in s$.
Finset.one_lt_card- A finite set has cardinality strictly greater than 1 if and only if it contains at least two distinct elements.
Nat.succ_le_iff- For natural numbers, $m + 1 \le n$ if and only if $m < n$.
Or.inl- If $A$ holds, then the disjunction $A \lor B$ holds.
Or.inr- If $B$ holds, then the disjunction $A \lor B$ holds.
Sym2.mem_iff.1- If an element belongs to an unordered pair $s(x, y)$, it equals either $x$ or $y$.
Sym2.mem_mk_left- The element $x$ is always a member of the unordered pair $s(x, y)$.
- Lean formalizes unordered pairs of elements using the symmetric square type `Sym2 G`, with notation `s(x, y)`, and evaluates the number of unordered representations by filtering the symmetric square `A.sym2`.
- The proof opens with `classical` to allow classical case analysis on equality of elements.
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_has_no_unique_sums_sumset_of_balanced {G : Type*} [AddCommGroup G] [DecidableEq G] (B : Finset G) (hB : finset_is_midpoint_balanced B) : finset_has_no_unique_sums ((B ×ˢ B).image (fun x => x.1 + x.2)) := by classical set A := (B ×ˢ B).image (fun x : G × G => x.1 + x.2) with hA have memA : ∀ a ∈ B, ∀ b ∈ B, a + b ∈ A := fun a ha b hb => Finset.mem_image.2 ⟨(a, b), Finset.mem_product.2 ⟨ha, hb⟩, rfl⟩ -- two different unordered pairs with the same total give two representations have two : ∀ p q r t : G, p ∈ A → q ∈ A → r ∈ A → t ∈ A → p + q = r + t → r ≠ p → r ≠ q → 2 ≤ finset_unordered_sum_rep_count A (p + q) := by intro p q r t hp hq hr ht hsum hrp hrq unfold finset_unordered_sum_rep_count rw [Nat.succ_le_iff, Finset.one_lt_card] refine ⟨s(p, q), ?_, s(r, t), ?_, ?_⟩ · simp [Finset.mem_filter, Finset.mk_mem_sym2_iff, hp, hq] · simp [Finset.mem_filter, Finset.mk_mem_sym2_iff, hr, ht, hsum] · intro h have : r ∈ s(p, q) := h ▸ Sym2.mem_mk_left r t rcases Sym2.mem_iff.1 this with h' | h' · exact hrp h' · exact hrq h' -- the repair of a pair `{x + x, x + y}`, from the balance of `x` have key : ∀ x ∈ B, ∀ y ∈ B, ∃ r ∈ A, ∃ t ∈ A, r + t = (x + x) + (x + y) ∧ r ≠ x + x ∧ r ≠ x + y := by intro x hx y hy obtain ⟨u, hu, v, hv, hux, hvx, huv, hxuv⟩ := hB.2 x hx by_cases hu' : u + y = x + x · refine ⟨v + y, memA v hv y hy, u + x, memA u hu x hx, ?_, ?_, ?_⟩ · rw [hxuv]; abel · intro h; exact huv (add_right_cancel (hu'.trans h.symm)) · intro h; exact hvx (add_right_cancel h) · refine ⟨u + y, memA u hu y hy, v + x, memA v hv x hx, ?_, hu', ?_⟩ · rw [hxuv]; abel · intro h; exact hux (add_right_cancel h) have fin : ∀ x ∈ B, ∀ y ∈ B, ∀ p q : G, p ∈ A → q ∈ A → ((p = x + x ∧ q = x + y) ∨ (p = x + y ∧ q = x + x)) → 2 ≤ finset_unordered_sum_rep_count A (p + q) := by intro x hx y hy p q hp hq hpq obtain ⟨r, hr, t, ht, hs, hr1, hr2⟩ := key x hx y hy rcases hpq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact two _ _ r t hp hq hr ht hs.symm hr1 hr2 · exact two _ _ r t hp hq hr ht (by rw [hs]; abel) hr2 hr1 refine ⟨?_, ?_⟩ · obtain ⟨b, hb⟩ := hB.1 obtain ⟨u, hu, v, hv, -, -, huv, -⟩ := hB.2 b hb rw [Nat.succ_le_iff, Finset.one_lt_card] exact ⟨b + u, memA b hb u hu, b + v, memA b hb v hv, fun h => huv (add_left_cancel h)⟩ · intro p hp q hq obtain ⟨⟨a, b⟩, hab, rfl⟩ := Finset.mem_image.1 hp obtain ⟨⟨c, d⟩, hcd, rfl⟩ := Finset.mem_image.1 hq obtain ⟨ha, hb⟩ := Finset.mem_product.1 hab obtain ⟨hc, hd⟩ := Finset.mem_product.1 hcd dsimp only at hp hq ⊢ by_cases h1 : a + c ≠ a + b ∧ a + c ≠ c + d · exact two _ _ (a + c) (b + d) hp hq (memA a ha c hc) (memA b hb d hd) (by abel) h1.1 h1.2 by_cases h2 : a + d ≠ a + b ∧ a + d ≠ c + d · exact two _ _ (a + d) (b + c) hp hq (memA a ha d hd) (memA b hb c hc) (by abel) h2.1 h2.2 have hcb : c = b ∨ a = d := by by_contra hne push_neg at hne exact h1 ⟨fun h => hne.1 (add_left_cancel h), fun h => hne.2 (add_right_cancel (h.trans (add_comm c d)))⟩ have hdb : d = b ∨ a = c := by by_contra hne push_neg at hne exact h2 ⟨fun h => hne.1 (add_left_cancel h), fun h => hne.2 (add_right_cancel h)⟩ rcases hcb with hcb | had <;> rcases hdb with hdb | hac · exact fin b hb a ha _ _ hp hq (Or.inr ⟨add_comm a b, by rw [hcb, hdb]⟩) · have hab' : a = b := hac.trans hcb exact fin b hb d hd _ _ hp hq (Or.inl ⟨by rw [hab'], by rw [hcb]⟩) · have hab' : a = b := had.trans hdb exact fin b hb c hc _ _ hp hq (Or.inl ⟨by rw [hab'], by rw [hdb, add_comm]⟩) · exact fin a ha b hb _ _ hp hq (Or.inr ⟨rfl, by rw [← hac, ← had]⟩)