Additive combinatorics

Additive combinatorics is principally devoted to consideration of inverse problems, often over more general groups than just the integers, that is, given some information about the sumset A+B, the aim is find information about the structure of the individual sets A and B. (A more recent name sometimes associated to this sub-division is additive combinatorics.) Unlike problems related to classical bases, as described above, this sub-area often deals with finite subsets rather than infinite ones. A typical question is what is the structure of a pair of subsets whose sumset has small cardinality (in relation to |A| and |B|). In the case of the integers, the classical Freiman's theorem provides a potent partial answer to this question in terms of multi-dimensional arithmetic progressions. Another typical problem is simply to find a lower bound for |A+B| in terms of |A| and |B| (this can be viewed as an inverse problem with the given information for A+B being that |A+B| is sufficiently small and the structural conclusion then being that either A or B is the empty set; such problems are often considered direct problems as well). Examples of this type include the Erdős–Heilbronn Conjecture (for a restricted sumset) and the Cauchy–Davenport Theorem. The methods used for tackling such questions draw from across the spectrum of mathematics, including combinatorics, ergodic theory, analysis, graph theory, group theory, and linear algebraic and polynomial methods.

History of additive combinatorics

Additive combinatorics is a branch of combinatorics primarily concerned with the study of additive structures. The term ``additive combinatorics was coined by Terence Tao and Van H. Vu in their book.

One of the oldest results in additive combinatorics is Cauchy–Davenport theorem. The inverse problem is one of the major studeis in additive combinatorics, asking what we can say about the additive structures of A and B given that the sum set <math>|A+B|${\displaystyle }$ is small.

Doubling constant

Let A be a subset of an abelian group. We define the doubling constant of A to be

<math> K = \dfrac{|A+A|}{|A|}.${\displaystyle }$

Ruzsa distance

Let A and B be two subsets of an abelian group. We define the Ruzsa distance between these two sets to be the quantity

<math> d(A,B) = \log{\dfrac{|A-B|}{\sqrt{|A||B|}}}. ${\displaystyle }$

Note that since <math>d(A,A)${\displaystyle }$ cannot be zero, the Ruzsa distance is not a metric.

Ruzsa triangle inequality

Let A B and C be subsets of an abelian group, then we have the inequality

<math>|A||B-C|\le|A-B||A-C|.${\displaystyle }$

Ruzsa triangle inequality is equivalent to that the Ruzsa distance obeys the trianagle inequality, namely

<math>d(B,C) \le d(A,B) + d(A,C).${\displaystyle }$