high_rep_card_le_of_missing
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 number of elements with more than 2 ordered restricted representations as sums of two distinct elements of A is at most |G| - |A|.
Statement
theorem high_rep_card_le_of_missing {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G] (A : Finset G) (g : G) (hg : g ∉ (A.powersetCard 3).image (fun s => ∑ x ∈ s, x)) : (Finset.univ.filter (fun x => 2 < ((A ×ˢ A).filter (fun p => p.1 ≠ p.2 ∧ p.1 + p.2 = x)).card)).card ≤ Fintype.card G - A.card
- Source
- arXiv:2610.14496 Proposition 3.1 equation (3) -- When Do Restricted Sumsets Cover a Finite Abelian Group?
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
Let $G$ be a finite additive abelian group (with decidable equality), let $A$ be a finite subset of $G$, and let $g \in G$. Assume that $g$ is not the sum of any three distinct elements of $A$ (that is, $g$ is not in the image under summation of the subsets of $A$ of cardinality 3). Then the number of elements $x \in G$ that have strictly more than 2 representations as $x = a + b$ with $a, b \in A$ and $a \neq b$ (counted as ordered pairs $(a, b) \in A \times A$) is at most $|G| - |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
We show that the set X of elements with more than 2 restricted representations as sums of two distinct elements of A is disjoint from the shift B = {g - a : a ∈ A}. If any element x ∈ X could be written as g - a for a ∈ A, then every representation p₁ + p₂ = g - a with p₁ ≠ p₂ in A must have {p₁, p₂} ∩ {a} ≠ ∅, because otherwise {p₁, p₂, a} would be a 3-element subset of A summing to g, contradicting that g is missing from the 3-fold restricted sumset. Consequently, g - a can have at most two representations, namely (a, g - 2a) and (g - 2a, a), so X and B cannot intersect. Since |B| = |A| by injectivity of translation, the disjoint union X ∪ B ⊆ G gives |X| + |A| ≤ |G|, which implies |X| ≤ |G| - |A|.
To bound the number of pairs (p₁, p₂) ∈ A × A of distinct elements summing to g - a, it suffices to show they belong to T = {(a, g - 2a), (g - 2a, a)}.
We let S be the set of pairs p = (p₁, p₂) ∈ A × A with p₁ ≠ p₂ and p₁ + p₂ = g - a, and let T = {(a, g - a - a), (g - a - a, a)}. To prove |S| ≤ 2, we introduce an arbitrary pair p ∈ S and unpack its defining properties: p₁ ∈ A, p₂ ∈ A, p₁ ≠ p₂, and p₁ + p₂ = g - a.
uses
Finset.mem_filter,Finset.mem_product,Finset.mem_insert,Finset.mem_singletonlet S := (A ×ˢ A).filter (fun p : G × G => p.1 ≠ p.2 ∧ p.1 + p.2 = g - a) let T : Finset (G × G) := {(a, g - a - a), (g - a - a, a)} have hST : S ⊆ T := by intro p hp rw [Finset.mem_filter, Finset.mem_product] at hp rcases hp with ⟨⟨hp1A, hp2A⟩, hpne, hpsum⟩ rw [Finset.mem_insert, Finset.mem_singleton]
If p₁ = a, then p = (a, g - 2a) ∈ T.
When p₁ = a, substituting this into p₁ + p₂ = g - a gives a + p₂ = g - a, which implies p₂ = g - a - a. Therefore, p = (a, g - a - a), which is the first element of T.
uses
eq_sub_of_add_eq'by_cases h1 : a = p.1 · left ext · exact h1.symm · dsimp rw [← h1] at hpsum exact eq_sub_of_add_eq' hpsum
If p₂ = a, then p = (g - 2a, a) ∈ T.
When p₁ ≠ a but p₂ = a, substituting into p₁ + p₂ = g - a gives p₁ + a = g - a, which implies p₁ = g - a - a. Therefore, p = (g - a - a, a), which is the second element of T.
uses
eq_sub_of_add_eq· by_cases h2 : a = p.2 · right ext · dsimp rw [← h2] at hpsum exact eq_sub_of_add_eq hpsum · exact h2.symm
It is impossible that neither p₁ nor p₂ equals a.
If p₁ ≠ a and p₂ ≠ a, then since p₁ ≠ p₂, the three elements p₁, p₂, a are pairwise distinct and all belong to A. Thus {p₁, p₂, a} is a 3-element subset of A. Its sum is (p₁ + p₂) + a = (g - a) + a = g, meaning that g is a sum of three distinct elements of A. This contradicts the hypothesis that g is not in the 3-fold restricted sumset of A.
uses
Finset.mem_image,Finset.mem_powersetCard,Finset.mem_insert,Finset.mem_singleton,Finset.card_insert_of_notMem,Finset.card_singleton,Ne.symm,not_or,Finset.sum_insert,Finset.sum_singleton,add_assoc,sub_add_cancel· exfalso apply hg rw [Finset.mem_image] refine ⟨{p.1, p.2, a}, ?_, ?_⟩ · rw [Finset.mem_powersetCard] refine ⟨?_, ?_⟩ · intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl <;> assumption · rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp only [Finset.mem_singleton] exact Ne.symm h2 · simp only [Finset.mem_insert, Finset.mem_singleton, not_or] exact ⟨hpne, Ne.symm h1⟩ · have h_not1 : p.1 ∉ ({p.2, a} : Finset G) := by simp [hpne, Ne.symm h1] have h_not2 : p.2 ∉ ({a} : Finset G) := by simp [Ne.symm h2] rw [Finset.sum_insert h_not1, Finset.sum_insert h_not2, Finset.sum_singleton, ← add_assoc, hpsum, sub_add_cancel]
The number of representations of g - a as a sum of two distinct elements of A is at most 2.
Since S ⊆ T and the set T = {(a, g - 2a), (g - 2a, a)} has at most 2 elements, |S| ≤ |T| ≤ 2 by transitivity of inequality.
uses
le_trans,Finset.card_le_card,Finset.card_le_twoexact le_trans (Finset.card_le_card hST) Finset.card_le_twoThe shifted set B = g - A has the same cardinality as A.
We define X to be the set of elements of G having strictly more than 2 representations as sums of two distinct elements of A, and define B = {g - a : a ∈ A}. Since the translation map a ↦ g - a is injective on G, the image B has cardinality |B| = |A|.
uses
Finset.card_image_of_injective,sub_right_inj.mplet X := Finset.univ.filter (fun x => 2 < ((A ×ˢ A).filter (fun p => p.1 ≠ p.2 ∧ p.1 + p.2 = x)).card) let B := A.image (fun a => g - a) have hB_card : B.card = A.card := by apply Finset.card_image_of_injective intro x y h exact sub_right_inj.mp h
The high-representation set X and the shifted set B are disjoint.
If an element x were in both X and B, then x = g - a for some a ∈ A. By the helper lemma, g - a has at most 2 representations as a sum of two distinct elements of A. But membership in X requires strictly more than 2 such representations, a contradiction.
uses
Finset.disjoint_right,Finset.mem_image,Finset.mem_filter,high_rep_card_le_of_missing_helper,not_lt_of_gehave h_disj : Disjoint X B := by rw [Finset.disjoint_right] intro x hxB hxX rw [Finset.mem_image] at hxB rcases hxB with ⟨a, ha, rfl⟩ rw [Finset.mem_filter] at hxX have h_le := high_rep_card_le_of_missing_helper A g hg a ha exact not_lt_of_ge h_le hxX.2
The cardinality of X is at most |G| - |A|.
Since X and B are disjoint subsets of the finite group G, the cardinality of their union is |X ∪ B| = |X| + |B| = |X| + |A|. Because X ∪ B ⊆ G, this sum is at most |G|, which gives |X| ≤ |G| - |A|.
uses
Finset.subset_univ,Finset.card_le_card,Finset.card_union_of_disjoint,Finset.card_univ,Nat.le_sub_of_add_lehave h_union : X ∪ B ⊆ Finset.univ := Finset.subset_univ _ have h_card := Finset.card_le_card h_union rw [Finset.card_union_of_disjoint h_disj, hB_card, Finset.card_univ] at h_card exact Nat.le_sub_of_add_le h_card
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_product- A pair belongs to the Cartesian product of two finsets if and only if the first component is in the first finset and the second is in the second.
Finset.mem_insert- An element belongs to the insertion of b into s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
eq_sub_of_add_eq'- In an additive commutative group, if c + a = b, then a = b - c.
eq_sub_of_add_eq- In an additive group, if a + c = b, then a = b - c.
Finset.mem_image- An element is in the image of a finset under a function if and only if it is the image of some element in the finset.
Finset.mem_powersetCard- A finset belongs to the collection of n-element subsets of t if and only if it is a subset of t and has cardinality n.
Finset.card_insert_of_notMem- Inserting an element not already in a finset increases its cardinality by 1.
Finset.card_singleton- A singleton finset has cardinality 1.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
not_or- De Morgan's law: the negation of a disjunction is the conjunction of the negations.
Finset.sum_insert- The sum of a function over insert a s (where a ∉ s) equals f(a) plus the sum over s.
Finset.sum_singleton- The sum of a function over a singleton {a} is f(a).
add_assoc- Addition in an additive semigroup is associative.
sub_add_cancel- Subtracting b and then adding b yields the original element: (a - b) + b = a.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.card_le_card- If one finset is a subset of another, its cardinality is at most the other's.
Finset.card_le_two- A doubleton finset {a, b} has cardinality at most 2.
Finset.card_image_of_injective- The image of a finset under an injective map has the same cardinality as the finset.
sub_right_inj.mp- Subtracting from the same element on the left is injective: if g - x = g - y, then x = y.
Finset.disjoint_right- Two finsets are disjoint if and only if no element of the second finset belongs to the first.
high_rep_card_le_of_missing_helper- If g is not a sum of three distinct elements of A, then for any a ∈ A, at most two pairs of distinct elements of A sum to g - a.
not_lt_of_ge- If a ≤ b, then b is not strictly less than a.
Finset.subset_univ- Every finset in a finite type is a subset of the universal finset.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Nat.le_sub_of_add_le- For natural numbers, if a + b ≤ c, then a ≤ c - b.
- In lines 31–46 of the helper lemma, Lean carries out several formal checks that on paper are immediate: verifying by case analysis that the elements {p.1, p.2, a} are in A, that the set has cardinality exactly 3 via repeated insertion of non-members, and that the sum over the finset evaluates to g via sum_insert.
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 high_rep_card_le_of_missing_helper {G : Type*} [AddCommGroup G] [DecidableEq G] (A : Finset G) (g : G) (hg : g ∉ (A.powersetCard 3).image (fun s => ∑ x ∈ s, x)) (a : G) (ha : a ∈ A) : ((A ×ˢ A).filter (fun p : G × G => p.1 ≠ p.2 ∧ p.1 + p.2 = g - a)).card ≤ 2 := by let S := (A ×ˢ A).filter (fun p : G × G => p.1 ≠ p.2 ∧ p.1 + p.2 = g - a) let T : Finset (G × G) := {(a, g - a - a), (g - a - a, a)} have hST : S ⊆ T := by intro p hp rw [Finset.mem_filter, Finset.mem_product] at hp rcases hp with ⟨⟨hp1A, hp2A⟩, hpne, hpsum⟩ rw [Finset.mem_insert, Finset.mem_singleton] by_cases h1 : a = p.1 · left ext · exact h1.symm · dsimp rw [← h1] at hpsum exact eq_sub_of_add_eq' hpsum · by_cases h2 : a = p.2 · right ext · dsimp rw [← h2] at hpsum exact eq_sub_of_add_eq hpsum · exact h2.symm · exfalso apply hg rw [Finset.mem_image] refine ⟨{p.1, p.2, a}, ?_, ?_⟩ · rw [Finset.mem_powersetCard] refine ⟨?_, ?_⟩ · intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl <;> assumption · rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp only [Finset.mem_singleton] exact Ne.symm h2 · simp only [Finset.mem_insert, Finset.mem_singleton, not_or] exact ⟨hpne, Ne.symm h1⟩ · have h_not1 : p.1 ∉ ({p.2, a} : Finset G) := by simp [hpne, Ne.symm h1] have h_not2 : p.2 ∉ ({a} : Finset G) := by simp [Ne.symm h2] rw [Finset.sum_insert h_not1, Finset.sum_insert h_not2, Finset.sum_singleton, ← add_assoc, hpsum, sub_add_cancel] exact le_trans (Finset.card_le_card hST) Finset.card_le_two/-- If an element is missing from the 3-fold restricted sumset, the high-representation set has cardinality at most |G| - |A|. -/theorem high_rep_card_le_of_missing {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G] (A : Finset G) (g : G) (hg : g ∉ (A.powersetCard 3).image (fun s => ∑ x ∈ s, x)) : (Finset.univ.filter (fun x => 2 < ((A ×ˢ A).filter (fun p => p.1 ≠ p.2 ∧ p.1 + p.2 = x)).card)).card ≤ Fintype.card G - A.card := by let X := Finset.univ.filter (fun x => 2 < ((A ×ˢ A).filter (fun p => p.1 ≠ p.2 ∧ p.1 + p.2 = x)).card) let B := A.image (fun a => g - a) have hB_card : B.card = A.card := by apply Finset.card_image_of_injective intro x y h exact sub_right_inj.mp h have h_disj : Disjoint X B := by rw [Finset.disjoint_right] intro x hxB hxX rw [Finset.mem_image] at hxB rcases hxB with ⟨a, ha, rfl⟩ rw [Finset.mem_filter] at hxX have h_le := high_rep_card_le_of_missing_helper A g hg a ha exact not_lt_of_ge h_le hxX.2 have h_union : X ∪ B ⊆ Finset.univ := Finset.subset_univ _ have h_card := Finset.card_le_card h_union rw [Finset.card_union_of_disjoint h_disj, hB_card, Finset.card_univ] at h_card exact Nat.le_sub_of_add_le h_card