high_rep_disjoint_translate
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.
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.
uses
Finset.disjoint_left,Finset.mem_filter,Finset.mem_imagerw [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
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.
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_twohave 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
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.
uses
Finset.mem_filter,Finset.mem_productobtain ⟨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
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.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.notMem_singleton.mpr,Finset.card_insert_of_notMem,Finset.card_singletonlet 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]
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.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.mem_powersetCardhave 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⟩
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.
uses
Finset.sum_insert,Finset.sum_singleton,add_assoc,sub_add_cancelhave 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]
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.
uses
Finset.mem_imageapply 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.
- On line 42, the contradiction between $|P| \le 2$ and $|P| > 2$ is resolved by the `omega` decision procedure for Presburger arithmetic.
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.
/-- 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⟩