AFTD Auto-Formalizing Theoretical Domains

finset_has_no_unique_sums_sumset_of_balanced

theoremverifiedformalization

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

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)$.

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

    lines 4–7

    uses Finset.mem_image.2, Finset.mem_product.2

      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⟩
  2. 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\}$.

    lines 8–21

    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'
  3. 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$).

    lines 22–34

    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)
  4. 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.

    lines 35–42

      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
  5. 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`.

    lines 43–47

    uses Nat.succ_le_iff, Finset.one_lt_card, add_left_cancel

      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)⟩
  6. 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`.

    lines 48–57

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

    lines 58–66

    uses add_left_cancel, add_right_cancel, add_comm

        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)⟩
  8. 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.

    lines 67–73

    uses add_comm, Or.inr, Or.inl

        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]⟩)
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)$.

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_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]⟩)
See it in the graphDiscuss this resultChallenge it