3.1 Basic properties of sumsets

Sumsets are a fundamental concept in additive combinatorics. They're all about combining elements from different sets through addition. Understanding sumsets helps us explore how numbers interact and grow when we add them together.

Sumsets have some cool properties that make them useful in math. They're commutative, associative, and follow a distributive rule. These properties help us analyze patterns in number theory and solve problems in other areas of math.

Sumsets and their notation

Definition and representation

Top images from around the web for Definition and representation

• 

  Additive combinatorics - Wikipedia View original

  Is this image relevant?

• 

  co.combinatorics - Important formulas in Combinatorics - MathOverflow View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

• 

  Additive combinatorics - Wikipedia View original

  Is this image relevant?

• 

  co.combinatorics - Important formulas in Combinatorics - MathOverflow View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and representation

• 

  Additive combinatorics - Wikipedia View original

  Is this image relevant?

• 

  co.combinatorics - Important formulas in Combinatorics - MathOverflow View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

• 

  Additive combinatorics - Wikipedia View original

  Is this image relevant?

• 

  co.combinatorics - Important formulas in Combinatorics - MathOverflow View original

  Is this image relevant?

1 of 3

• A sumset, denoted $A + B$, is the set of all possible pairwise sums of elements from two sets $A$ and $B$
  • Formally, $A + B = \{a + b : a \in A, b \in B\}$
• The notation $A + B$ represents the sumset of sets $A$ and $B$, where each element in $A$ is added to each element in $B$
  • Example: If $A = \{1, 2\}$ and $B = \{3, 4\}$, then $A + B = \{4, 5, 5, 6\}$

Extensions and cardinality

• Sumsets can be defined for any number of sets, such as $A + B + C$, which represents the set of all possible sums of elements from three sets $A$, $B$, and $C$
  • Example: If $A = \{1\}$, $B = \{2\}$, and $C = \{3\}$, then $A + B + C = \{6\}$
• The number of elements in a sumset $A + B$ is denoted by $|A + B|$, where $|A|$ and $|B|$ represent the number of elements in sets $A$ and $B$, respectively
  • Example: If $A = \{1, 2, 3\}$ and $B = \{4, 5\}$, then $|A + B| = 6$ since $A + B = \{5, 6, 6, 7, 7, 8\}$

Properties of sumsets

Commutativity and associativity

• Commutativity: For any sets $A$ and $B$, $A + B = B + A$
  • This property states that the order of the sets in a sumset does not affect the resulting set
  • Example: $\{1, 2\} + \{3, 4\} = \{3, 4\} + \{1, 2\}$
• Associativity: For any sets $A$, $B$, and $C$, $(A + B) + C = A + (B + C)$
  • This property allows for the grouping of sets in a sumset without changing the result
  • Example: $(\{1\} + \{2\}) + \{3\} = \{1\} + (\{2\} + \{3\})$

Identity element and distributive property

• Identity element: For any set $A$, $A + \{0\} = A$
  • The set containing only the element $0$ acts as an identity element for sumsets, as adding it to any set $A$ does not change the resulting sumset
  • Example: $\{1, 2, 3\} + \{0\} = \{1, 2, 3\}$
• Distributive property: For any sets $A$, $B$, and $C$, $A + (B \cup C) = (A + B) \cup (A + C)$
  • This property demonstrates the distributive nature of sumsets over unions of sets
  • Example: $\{1\} + (\{2\} \cup \{3\}) = (\{1\} + \{2\}) \cup (\{1\} + \{3\})$

Sumset calculations and analysis

Computing sumsets for integer sets

• Calculate sumsets for sets of integers, such as $A = \{1, 2, 3\}$ and $B = \{0, 1, 2\}$, and determine the resulting set $A + B$
  • Example: If $A = \{1, 2, 3\}$ and $B = \{0, 1, 2\}$, then $A + B = \{1, 2, 3, 3, 4, 4, 5\}$
• Analyze the structure of sumsets, including the number of elements, the range of values, and any patterns or symmetries that emerge
  • Example: The sumset $\{1, 2, 3\} + \{0, 1, 2\}$ has $7$ elements, ranging from $1$ to $5$, with some repeated values

Relationship between original set structure and sumset structure

• Investigate the relationship between the structure of the original sets and the structure of their sumset
  • Example: If the original sets are arithmetic progressions, the sumset will also be an arithmetic progression
• Explore the behavior of sumsets when one or both of the original sets are infinite
  • Example: The sumset of the set of natural numbers with itself, $\mathbb{N} + \mathbb{N}$, is equal to the set of natural numbers, $\mathbb{N}$

Sumset size vs Original set size

Bounds on sumset size

• Investigate the bounds on the size of a sumset $A + B$ in relation to the sizes of the original sets $A$ and $B$
  • Trivial bounds: $|A| \leq |A + B| \leq |A| \cdot |B|$
  • Example: If $|A| = 3$ and $|B| = 2$, then $3 \leq |A + B| \leq 6$
• Analyze the conditions under which the size of a sumset reaches its maximum or minimum value
  • Example: The sumset reaches its maximum size when the original sets have no common elements

Doubling constant and Plünnecke-Ruzsa inequality

• Explore the concept of the doubling constant for a set $A$, defined as $|A + A| / |A|$, and its implications for the structure and growth of sumsets
  • Example: If $A = \{0, 1, 2\}$, then $A + A = \{0, 1, 2, 2, 3, 4\}$, and the doubling constant is $6/3 = 2$
• Study the Plünnecke-Ruzsa inequality, which relates the size of iterated sumsets, such as $|A + A + A|$, to the size of the original set $A$ and its doubling constant
  • Example: If $A = \{0, 1, 2\}$, then $A + A + A = \{0, 1, 2, 3, 3, 4, 4, 5, 6\}$, and the Plünnecke-Ruzsa inequality provides bounds on $|A + A + A|$ in terms of $|A|$ and the doubling constant