Additive Combinatorics

Additive Combinatorics July 22, 2009

Posted by lhstephens in Uncategorized.
trackback

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.

About these ads

Comments»

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.

Reply
2. charav - August 11, 2009: The Tao and Vu’s book is for an introduction to the subject or is for an advanced level?

Reply

	malmsteenkoushik on Divisibility theorems for grou…
	tinyurl.com on The tubular neighborhood …
	Advanced Analysis, N… on The Hahn-Banach theorem and tw…
	Gary K on The tubular neighborhood …
	Gary K on The tubular neighborhood …

Delta Epsilons

Additive Combinatorics July 22, 2009

Like this:

Comments»

Leave a Reply Cancel reply

About

Mathematical websites

Categories

Recent Posts

Recent Comments

Previous Posts

Tags

Feeds

Follow “Delta Epsilons”