Minimum size of a sum-dominant set

TheoremChu's theorem for arbitrary finite sets of integers#✓fully proved

Let \(A\) be a finite set of integers with \(|A| < 6\). Then \(|A + A| \le |A - A|\), where \(A + A = \{a + b : a, b \in A\}\) is the sumset and \(A - A = \{a - b : a, b \in A\}\) is the difference set of \(A\).

This is Chu's theorem without the assumption that the elements of \(A\) are nonnegative.

theorem card_add_le_card_sub_of_card_lt_six (A : Finset ℤ) (h_card : A.card < 6) :
    (A + A).card ≤ (A - A).card

Used by 1

Used byChu's theorem: sets with fewer than six elements are not sum-dominant

TheoremChu's theorem: sets with fewer than six elements are not sum-dominant#✓fully proved

Let \(A\) be a finite set of nonnegative integers with \(|A| < 6\). Then \(|A + A| \le |A - A|\), where \(A + A = \{a + b : a, b \in A\}\) is the sumset and \(A - A = \{a - b : a, b \in A\}\) is the difference set of \(A\); that is, \(A\) is not sum-dominant.

The nonnegativity assumption follows the source's normalization and is not needed: the same bound holds for every finite set of integers with fewer than six elements.

theorem no_small_sum_dominant :
    ∀ (A : Finset ℤ) (h_nonneg : ∀ x ∈ A, 0 ≤ x) (h_card : A.card < 6),
      (A + A).card ≤ (A - A).card

Sources

• Hùng Việt Chu, "When Sets Are Not Sum-Dominant," Journal of Integer Sequences 22 (2019), Article 19.3.7, Theorem, lines 126–128, https://cs.uwaterloo.ca/journals/JIS/VOL22/Chu/chu5.tex

Uses 1

Proof usesChu's theorem for arbitrary finite sets of integers

2 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.