AFTD Auto-Formalizing Theoretical Domains

high_rep_disjoint_translate

theoremverified

Let G be a finite abelian group, A a finite subset of G, and g an element of G. If g does not belong to the 3-fold restricted sumset of A (the set of sums of 3 distinct elements of A), then the set of elements with more than 2 ordered restricted representations as sums of two distinct elements of A is disjoint from g - A.

Statement

theorem high_rep_disjoint_translate {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
    (A : Finset G) (g : G)
    (hg : g ∉ (A.powersetCard 3).image (fun s => ∑ x ∈ s, x)) :
    Disjoint
      (Finset.univ.filter (fun x => 2 < ((A ×ˢ A).filter (fun p => p.1 ≠ p.2 ∧ p.1 + p.2 = x)).card))
      (A.image (fun a => g - a))
Source
arXiv:2610.14496 Proposition 3.1 proof -- When Do Restricted Sumsets Cover a Finite Abelian Group?
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any finite additive commutative group $G$ with decidable equality, any finite subset $A$ of $G$, and any element $g \in G$, if $g$ is not the sum of any 3-element subset of $A$ (that is, $g \notin \{ \sum_{x \in s} x \mid s \subseteq A, |s| = 3 \}$), then the set of elements $x \in G$ for which there are strictly more than 2 pairs $(p_1, p_2) \in A \times A$ with $p_1 \neq p_2$ and $p_1 + p_2 = x$ is disjoint from the translate $\{ g - a \mid a \in A \}$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by contradiction: suppose an element x lies in both the high-representation set and the translate g - A. Then x = g - a for some a ∈ A, and x has more than two ordered representations as a sum of two distinct elements of A. Since at most two such representations can involve the element a (namely (a, g - 2a) and (g - 2a, a)), there must exist a representation p₁ + p₂ = g - a with p₁, p₂ ∈ A distinct from each other and from a. Then {p₁, p₂, a} is a 3-element subset of A summing to (g - a) + a = g, which contradicts the hypothesis that g does not belong to the 3-fold restricted sumset of A.

  1. Assuming the two sets intersect, there is a common element x = g - a with a ∈ A whose set P of ordered restricted representations has cardinality |P| > 2.

    Disjointness is established by contradiction: suppose an element x belongs to both sets. As an element of the translate g - A, x must be of the form g - a for some a ∈ A. Since x also belongs to the high-representation set, the set P of ordered pairs (p₁, p₂) ∈ A × A such that p₁ ≠ p₂ and p₁ + p₂ = g - a has cardinality strictly greater than 2, and every p ∈ P satisfies p₁ + p₂ = g - a.

    lines 8–19

    uses Finset.disjoint_left, Finset.mem_filter, Finset.mem_image

      rw [Finset.disjoint_left]
      intro x hx hx_image
      rw [Finset.mem_filter] at hx
      obtain ⟨-, hx⟩ := hx
      rw [Finset.mem_image] at hx_image
      obtain ⟨a, ha, rfl⟩ := hx_image
      let P := (A ×ˢ A).filter (fun p => p.1 ≠ p.2 ∧ p.1 + p.2 = g - a)
      have hP_card : 2 < P.card := hx
      have hP_sum : ∀ p ∈ P, p.1 + p.2 = g - a := by
        intro p hp
        rw [Finset.mem_filter] at hp
        exact hp.2.2
  2. There exists a representation p ∈ P such that neither coordinate equals a (that is, p₁ ≠ a and p₂ ≠ a). automation

    Suppose for contradiction that every representation p ∈ P has p₁ = a or p₂ = a. Because every pair in P must satisfy p₁ + p₂ = g - a, setting p₁ = a uniquely forces p₂ = (g - a) - a, and setting p₂ = a uniquely forces p₁ = (g - a) - a. Hence P ⊆ {(a, (g - a) - a), ((g - a) - a, a)}, which implies |P| ≤ 2. But this contradicts |P| > 2.

    lines 20–42

    uses Or.inl, Or.inr, Finset.mem_insert, Finset.mem_singleton, add_sub_cancel_left, add_sub_cancel_right, Finset.card_le_card, Finset.card_le_two

      have hex : ∃ p ∈ P, p.1 ≠ a ∧ p.2 ≠ a := by
        by_contra hc
        have h : ∀ p ∈ P, p.1 = a ∨ p.2 = a := by
          intro p hp
          by_cases h1 : p.1 = a
          · exact Or.inl h1
          · refine Or.inr (by_contra fun h2 => hc ⟨p, hp, h1, h2⟩)
        have hsub : P ⊆ {(a, (g - a) - a), ((g - a) - a, a)} := by
          intro p hp
          have hor := h p hp
          have hsum := hP_sum p hp
          simp only [Finset.mem_insert, Finset.mem_singleton]
          rcases hor with h1 | h2
          · left
            ext
            · exact h1
            · rw [← add_sub_cancel_left p.1 p.2, hsum, h1]
          · right
            ext
            · rw [← add_sub_cancel_right p.1 p.2, hsum, h2]
            · exact h2
        have : P.card ≤ 2 := (Finset.card_le_card hsub).trans Finset.card_le_two
        omega
  3. There exist elements p₁, p₂ ∈ A with p₁ ≠ p₂, p₁ ≠ a, p₂ ≠ a, and p₁ + p₂ = g - a.

    Fixing the witness p ∈ P from the previous step and unfolding the definitions of the Cartesian product and filter yields two distinct elements p₁, p₂ ∈ A that are both different from a and sum to g - a.

    lines 43–50

    uses Finset.mem_filter, Finset.mem_product

      obtain ⟨p, hp, hp1a, hp2a⟩ := hex
      rw [Finset.mem_filter] at hp
      have hpA : p ∈ A ×ˢ A := hp.1
      rw [Finset.mem_product] at hpA
      have huA : p.1 ∈ A := hpA.1
      have hvA : p.2 ∈ A := hpA.2
      have huv : p.1 ≠ p.2 := hp.2.1
      have hsum : p.1 + p.2 = g - a := hp.2.2
  4. The set s = {p₁, p₂, a} has cardinality 3.

    Because p₁ ≠ p₂ and p₁ ≠ a, p₁ is not in {p₂, a}. Similarly, because p₂ ≠ a, p₂ is not in {a}. Inserting elements one at a time into the singleton {a} shows that {p₁, p₂, a} has cardinality 1 + 1 + 1 = 3.

    lines 51–61

    uses Finset.mem_insert, Finset.mem_singleton, Finset.notMem_singleton.mpr, Finset.card_insert_of_notMem, Finset.card_singleton

      let s : Finset G := {p.1, p.2, a}
      have h1 : p.1 ∉ ({p.2, a} : Finset G) := by
        intro h
        rw [Finset.mem_insert, Finset.mem_singleton] at h
        rcases h with h | h
        · exact huv h
        · exact hp1a h
      have h2 : p.2 ∉ ({a} : Finset G) := Finset.notMem_singleton.mpr hp2a
      have hs_card : s.card = 3 := by
        dsimp [s]
        rw [Finset.card_insert_of_notMem h1, Finset.card_insert_of_notMem h2, Finset.card_singleton]
  5. The set s is a 3-element subset of A (an element of the powerset of size 3).

    Every element of s is either p₁, p₂, or a, each of which belongs to A. Since s ⊆ A and |s| = 3, s is an element of the collection of 3-element subsets of A.

    lines 62–72

    uses Finset.mem_insert, Finset.mem_singleton, Finset.mem_powersetCard

      have hs_sub : s ⊆ A := by
        intro y hy
        dsimp [s] at hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hy
        rcases hy with rfl | rfl | rfl
        · exact huA
        · exact hvA
        · exact ha
      have hs_mem : s ∈ A.powersetCard 3 := by
        rw [Finset.mem_powersetCard]
        exact ⟨hs_sub, hs_card⟩
  6. The sum of the elements in s is equal to g.

    Summing the elements of s = {p₁, p₂, a} yields (p₁ + p₂) + a. Substituting the relation p₁ + p₂ = g - a gives (g - a) + a = g.

    lines 73–76

    uses Finset.sum_insert, Finset.sum_singleton, add_assoc, sub_add_cancel

      have hs_sum : ∑ y ∈ s, y = g := by
        dsimp [s]
        rw [Finset.sum_insert h1, Finset.sum_insert h2, Finset.sum_singleton]
        rw [← add_assoc, hsum, sub_add_cancel]
  7. This contradicts the hypothesis that g is not in the 3-fold restricted sumset of A.

    We have constructed a 3-element subset s ⊆ A whose sum is g. Therefore, g is in the image of the 3-element subsets under summation, contradicting the initial assumption hg.

    lines 77–79

    uses Finset.mem_image

      apply hg
      rw [Finset.mem_image]
      exact ⟨s, hs_mem, hs_sum⟩
Finset.disjoint_left
Two finite sets are disjoint if and only if no element in the first set belongs to the second set.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.mem_image
An element belongs to the image of a set under a function if and only if it is the image of some element in the set.
Or.inl
If a proposition A holds, then the disjunction A ∨ B holds.
Or.inr
If a proposition B holds, then the disjunction A ∨ B holds.
Finset.mem_insert
An element belongs to the set obtained by inserting an element b into a set s if and only if it equals b or already belongs to s.
Finset.mem_singleton
An element belongs to a singleton set {a} if and only if it equals a.
add_sub_cancel_left
In an additive abelian group, adding and then subtracting an element on the left yields the second summand: (a + b) - a = b.
add_sub_cancel_right
In an additive group, adding and then subtracting an element on the right yields the first summand: (a + b) - b = a.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to that of the larger set.
Finset.card_le_two
A finite set containing at most two elements has cardinality at most 2.
Finset.mem_product
An ordered pair belongs to the Cartesian product of two sets if and only if its first coordinate belongs to the first set and its second coordinate belongs to the second set.
Finset.notMem_singleton.mpr
If two elements are distinct, the first does not belong to the singleton set containing the second.
Finset.card_insert_of_notMem
Inserting an element not present in a finite set increases its cardinality by 1.
Finset.card_singleton
The cardinality of a singleton set is 1.
Finset.mem_powersetCard
A set belongs to the collection of n-element subsets of A if and only if it is a subset of A and has cardinality n.
Finset.sum_insert
The sum of a function over an inserted element not in the set equals the function value at that element plus the sum over the original set.
Finset.sum_singleton
The sum of a function over a singleton set {a} equals the value of the function at a.
add_assoc
Addition is associative: (a + b) + c = a + (b + c).
sub_add_cancel
Subtracting and then adding the same element recovers the original element: (a - b) + b = 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 an element is missing from the 3-fold restricted sumset, its high-representation set is disjoint from a translate of the subset. -/theorem high_rep_disjoint_translate {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]    (A : Finset G) (g : G)    (hg : g ∉ (A.powersetCard 3).image (fun s => ∑ x ∈ s, x)) :    Disjoint      (Finset.univ.filter (fun x => 2 < ((A ×ˢ A).filter (fun p => p.1 ≠ p.2 ∧ p.1 + p.2 = x)).card))      (A.image (fun a => g - a)) := by  rw [Finset.disjoint_left]  intro x hx hx_image  rw [Finset.mem_filter] at hx  obtain ⟨-, hx⟩ := hx  rw [Finset.mem_image] at hx_image  obtain ⟨a, ha, rfl⟩ := hx_image  let P := (A ×ˢ A).filter (fun p => p.1 ≠ p.2 ∧ p.1 + p.2 = g - a)  have hP_card : 2 < P.card := hx  have hP_sum : ∀ p ∈ P, p.1 + p.2 = g - a := by    intro p hp    rw [Finset.mem_filter] at hp    exact hp.2.2  have hex : ∃ p ∈ P, p.1 ≠ a ∧ p.2 ≠ a := by    by_contra hc    have h : ∀ p ∈ P, p.1 = a ∨ p.2 = a := by      intro p hp      by_cases h1 : p.1 = a      · exact Or.inl h1      · refine Or.inr (by_contra fun h2 => hc ⟨p, hp, h1, h2⟩)    have hsub : P ⊆ {(a, (g - a) - a), ((g - a) - a, a)} := by      intro p hp      have hor := h p hp      have hsum := hP_sum p hp      simp only [Finset.mem_insert, Finset.mem_singleton]      rcases hor with h1 | h2      · left        ext        · exact h1        · rw [← add_sub_cancel_left p.1 p.2, hsum, h1]      · right        ext        · rw [← add_sub_cancel_right p.1 p.2, hsum, h2]        · exact h2    have : P.card ≤ 2 := (Finset.card_le_card hsub).trans Finset.card_le_two    omega  obtain ⟨p, hp, hp1a, hp2a⟩ := hex  rw [Finset.mem_filter] at hp  have hpA : p ∈ A ×ˢ A := hp.1  rw [Finset.mem_product] at hpA  have huA : p.1 ∈ A := hpA.1  have hvA : p.2 ∈ A := hpA.2  have huv : p.1 ≠ p.2 := hp.2.1  have hsum : p.1 + p.2 = g - a := hp.2.2  let s : Finset G := {p.1, p.2, a}  have h1 : p.1 ∉ ({p.2, a} : Finset G) := by    intro h    rw [Finset.mem_insert, Finset.mem_singleton] at h    rcases h with h | h    · exact huv h    · exact hp1a h  have h2 : p.2 ∉ ({a} : Finset G) := Finset.notMem_singleton.mpr hp2a  have hs_card : s.card = 3 := by    dsimp [s]    rw [Finset.card_insert_of_notMem h1, Finset.card_insert_of_notMem h2, Finset.card_singleton]  have hs_sub : s ⊆ A := by    intro y hy    dsimp [s] at hy    simp only [Finset.mem_insert, Finset.mem_singleton] at hy    rcases hy with rfl | rfl | rfl    · exact huA    · exact hvA    · exact ha  have hs_mem : s ∈ A.powersetCard 3 := by    rw [Finset.mem_powersetCard]    exact ⟨hs_sub, hs_card⟩  have hs_sum : ∑ y ∈ s, y = g := by    dsimp [s]    rw [Finset.sum_insert h1, Finset.sum_insert h2, Finset.sum_singleton]    rw [← add_assoc, hsum, sub_add_cancel]  apply hg  rw [Finset.mem_image]  exact ⟨s, hs_mem, hs_sum⟩
See it in the graphDiscuss this resultChallenge it