jump to navigation

Additive Combinatorics July 22, 2009

Posted by lhstephens in Uncategorized.

My project at RSI is in additive combinatorics, which is a field of math, which extends the notions of set over operations. Here is a brief introduction to some of the terminology and theorems in the field.

Additive combinatorics studies subsets of abelian groups. To study these sets, additive combinatorics uses theorems and notation from both graph theory and set theory. An additive set {A} with respect to an abelian group {Z} is a set {A \subset Z}. The group Z is referred to as an ambient group. Normally, the group {Z} is the integers over addition or {\mathbb{Z} , +}.

The size of an additive set {A} is the number of unique elements of {A} and is denoted by {|A|}. For example, if { A=\{1,2,3,4\}} then {|A| = 4}. For two additive sets {A,B} in an abelian group {Z}, the sumset of {A} and {B} is defined to be { A + B = \{a+b: a\in A, b\in B\}}. For example, let { A= \{1,2,3\}} and let {B= \{2,5,6\} } then {A +B = \{3,4,5,6,7,8,9\}}. Similarly the difference set, {A-B}, is defined as { A-B = \{a-b:a \in A, b\in B\}}.

The dilate of a set {A} by {x}, where {x \in \mathbb{Z}} is {x\cdot A = \{xa: a \in A\}}. This is different than {xA} which takes the form {xA=\{a_{1} +a_{2}+a_{3}+\cdots +a_{x}:a_{1} ,a_{2},a_{3},\cdots ,a_{x} \in A\}} and is equivalent to {A+A+A+\cdots +A} with {x} copies of {A}. For example, if {A = \{1,2,3\}}, then {2\cdot A = \{2,4,6\}} while {2A = \{2,3,4,5,6\}}. In particular, Bukh investigated sumsets of the form {x_1 \cdot A+ x_2 \cdot A + \cdots + x_k \cdot A}. Bukh proved that for any finite set {A \subset \mathbb{Z}}, {|A+3 \cdot A| \geq 4 \cdot |A| - O(1)}, where {O(1)} is a sharp error term. Then, Bukh proved that if either {|A+A| \leq K \cdot |A|} or {|A-A| \leq K\cdot|A|} then {|x_1\cdot A + \cdots + x_k\cdot A| \leq K^p \cdot |A|} for {p = 7 +12 \sum_{i=1}^{k} \log_2 (1+|x_i|)}.

The doubling constant of an additive set {A} is defined as {\sigma (A) = \frac{|A+A|} {|A|} } and is a measure of the number of pairs in {A} with equal sums. The difference constant of an additive set {A} is similarly defined as {\delta (A) = \frac{|A-A|}{|A|} }, and is a measure of the number of pairs with equal difference. Both the doubling constant and the difference constant are measures of the structure, or non-randomness, of an additive set {A}.

Additive combinatorics also uses Graph theory and Fourier analysis to  prove some of the more powerful theorems, for a more detailed look at the subject, see Terrence Tao’s and Van H. Vu’s book, Additive Combinatorics.



1. Michael Lugo - July 22, 2009

For a briefer answer to the question of “what is additive combinatorics?” that’s still longer than this post, but shorter than the book of Tao and Vu, one might take a look at Ben Green’s review of that book, in the July 2009 issue of the Bulletin of the American Mathematical Society.

2. charav - August 11, 2009

The Tao and Vu’s book is for an introduction to the subject or is for an advanced level?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: