imported>Morinator: link mathematics at beginning

2025-04-06T00:56:48Z

link mathematics at beginning

New page

{{short description|Area of combinatorics in mathematics}}
'''Additive combinatorics''' is an area of [[combinatorics]] in [[mathematics]]. One major area of study in additive combinatorics are ''inverse problems'': given the size of the [[sumset]] {{Math|''A'' + ''B''}} is small, what can we say about the structures of {{Mvar|A}} and {{Mvar|B}}? In the case of the integers, the classical [[Freiman's theorem]] provides a partial answer to this question in terms of [[multi-dimensional arithmetic progression]]s.

Another typical problem is to find a lower bound for {{Math|{{abs|''A'' + ''B''}}}} in terms of {{Math|{{abs|''A''}}}} and {{Math|{{abs|''B''}}}}. This can be viewed as an inverse problem with the given information that {{Math|{{abs|''A'' + ''B''}}}} is sufficiently small and the structural conclusion is then of the form that either {{Mvar|A}} or {{Mvar|B}} is the empty set; however, in literature, such problems are sometimes considered to be direct problems as well. Examples of this type include the [[Erdős–Heilbronn conjecture|Erdős–Heilbronn Conjecture]] (for a [[restricted sumset]]) and the [[Cauchy–Davenport theorem|Cauchy–Davenport Theorem]]. The methods used for tackling such questions often come from many different fields of mathematics, including [[combinatorics]], [[ergodic theory]], [[analysis]], [[graph theory]], [[group theory]], and [[linear algebra|linear-algebra]]ic and polynomial methods.

== History of additive combinatorics ==
Although additive combinatorics is a fairly new branch of combinatorics (the term ''additive combinatorics'' was coined by [[Terence Tao]] and [[Van H. Vu]] in their 2006 book of the same name), a much older problem, the [[Cauchy–Davenport theorem]], is one of the most fundamental results in this field.

=== Cauchy–Davenport theorem ===
Suppose that ''{{Mvar|A}}'' and ''{{Mvar|B}}'' are finite subsets of the [[cyclic group]] {{Math|&integers;/''p''&integers;}} for a prime {{Mvar|p}}, then the following inequality holds.
:<math> |A+B| \ge \min(|A|+|B|-1,p) </math>

=== Vosper's theorem ===
Now we have the inequality for the cardinality of the sum set {{Math|''A'' + ''B''}}, it is natural to ask the inverse problem, namely under what conditions on {{Mvar|A}} and {{Mvar|B}} does the equality hold? Vosper's theorem answers this question. Suppose that {{Math|{{abs|''A''}},{{abs|''B''}} ≥ 2}} (that is, barring edge cases) and
:<math> |A+B| \le |A|+|B|-1 \le p-2, </math>

then {{Mvar|A}} and {{Mvar|B}} are arithmetic progressions with the same difference. This illustrates the structures that are often studied in additive combinatorics: the combinatorial structure of {{Math|''A'' + ''B''}} as compared to the algebraic structure of arithmetic progressions.

=== Plünnecke–Ruzsa inequality ===
A useful theorem in additive combinatorics is [[Plünnecke–Ruzsa inequality]]. This theorem gives an upper bound on the cardinality of {{Math|{{abs|''nA'' − ''mA''}}}} in terms of the doubling constant of {{Mvar|A}}. For instance using Plünnecke–Ruzsa inequality, we are able to prove a version of Freiman's Theorem in finite fields.

== Basic notions ==
=== Operations on sets ===
Let ''{{Mvar|A}}'' and ''{{Mvar|B}}'' be finite subsets of an abelian group; then the sum set is defined to be
:<math> A+B = \{a+b : a \in A, b \in B\}. </math>
For example, we can write {{Math|1={{mset|1,2,3,4}} + {{mset|1,2,3}} = {{mset|2,3,4,5,6,7}}}}. Similarly, we can define the difference set of ''{{Mvar|A}}'' and ''{{Mvar|B}}'' to be
:<math> A-B = \{a-b : a \in A, b \in B\}. </math>
The {{Mvar|k}}-fold sumset of the set {{Mvar|A}} with itself is denoted by
:<math>kA = \underbrace{A+A+\cdots+A}_{k\text{ terms }} = \{a_1+\cdots+a_k : a_1 \in A, \dots, a_k \in A\},</math>

which must not be confused with
:<math> k \cdot A = \{ka : a \in A\}. </math>

=== Doubling constant ===
Let ''{{Mvar|A}}'' be a subset of an abelian group. The doubling constant measures how big the sum set <math> |A+A|</math> is compared to its original size {{Math|{{abs|''A''}}}}. We define the doubling constant of {{Mvar|A}} to be
:<math> K = \dfrac{|A+A|}{|A|}.</math>

== Ruzsa distance ==
Let ''{{Mvar|A}}'' and ''{{Mvar|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|}}. </math>

The [[Ruzsa triangle inequality]] asserts that the Ruzsa distance obeys the triangle inequality:
:<math>d(B,C) \le d(A,B) + d(A,C).</math>

However, since {{Math|''d''(''A'',''A'')}} cannot be zero, the Ruzsa distance is not actually a [[Metric space|metric]].

== See also ==

* [[Arithmetic combinatorics]]
* [[Additive number theory]]

==References==
===Citations===

* Tao, T., & Vu, V. (2006). ''Additive combinatorics''. Cambridge: Cambridge University Press.
* Green, B. (2009, January 15). Additive Combinatorics Book Review. Retrieved from <nowiki>https://www.ams.org/journals/bull/2009-46-03/S0273-0979-09-01231-2/S0273-0979-09-01231-2.pdf</nowiki>.
{{reflist|20em}}

[[Category:Additive combinatorics| ]]
[[Category:Mathematical theorems]]
[[Category:Combinatorial algorithms]]

Additive combinatorics - Revision history

imported>Morinator: link mathematics at beginning