AFTD Auto-Formalizing Theoretical Domains

high_rep_card_le_of_missing

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

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

    lines 6–12

    uses Finset.mem_filter, Finset.mem_product, Finset.mem_insert, Finset.mem_singleton

      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]
  2. 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.

    lines 13–19

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

    lines 20–26

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

    lines 27–46

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

    line 47

    uses le_trans, Finset.card_le_card, Finset.card_le_two

      exact le_trans (Finset.card_le_card hST) Finset.card_le_two
  6. The 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|.

    lines 55–60

    uses Finset.card_image_of_injective, sub_right_inj.mp

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

    lines 61–68

    uses Finset.disjoint_right, Finset.mem_image, Finset.mem_filter, high_rep_card_le_of_missing_helper, not_lt_of_ge

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

    lines 69–72

    uses Finset.subset_univ, Finset.card_le_card, Finset.card_union_of_disjoint, Finset.card_univ, Nat.le_sub_of_add_le

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

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 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
See it in the graphDiscuss this resultChallenge it