Additive combinatorics

Additive combinatorics studies how the sizes and representation functions of sumsets reveal algebraic structure in subsets of abelian groups.

Table of contents

Sumset ( $A + B$ )

A, B

of an additive group, their sumset is

A + B = {a + b : a \in A, b \in B}

.

Difference set ( $A - B$ )

A, B

of an additive group, their difference set is

A - B = {a - b : a \in A, b \in B}

.

Doubling constant ( $∣ A + A ∣/∣ A ∣$ )

The doubling constant of a nonempty finite set

A

is

∣ A + A ∣/∣ A ∣

. A small doubling constant indicates that

A

behaves approximately like a coset of a subgroup.

Plünnecke-Ruzsa inequality

If finite sets satisfy

∣ A + B ∣ \leq K ∣ A ∣

, then the Plünnecke-Ruzsa inequality bounds iterated sumsets and difference sets by

∣ ℓ B - m B ∣ \leq K^{ℓ + m} ∣ A ∣.

Freiman-Ruzsa theorem over a finite field

If

A \subseteq F_{p}^{n}

and

∣ A + A ∣ \leq K ∣ A ∣

, then

A

is contained in a vector subspace

H

satisfying

∣ H ∣ \leq K^{2} p^{K^{4}} ∣ A ∣.

Additive energy ( $E (A)$ )

The additive energy of a finite set

A

is the number of additive quadruples in

A^{4}

, often normalized by

∣ A ∣^{3}

.

Additive quadruple

An additive quadruple is a tuple

(a, b, c, d)

satisfying

a + b = c + d

.

Balog-Szemerédi-Gowers theorem

If a finite set

A

has at least

η ∣ A ∣^{3}

additive quadruples, then it contains

A^{'}

with

∣ A^{'} ∣ \geq η^{C} ∣ A ∣

and

∣ A^{'} + A^{'} ∣ \leq η^{- C} ∣ A^{'} ∣

for an absolute constant

C

.

Bogolyubov lemma

If

A

has positive density in a finite abelian group, then

A + A - A - A

contains a structured neighbourhood of zero. In a finite-dimensional vector space this neighbourhood can be taken to be a large vector subspace; in a cyclic group it can be taken to be a Bohr set.

Bohr set ( $B (Γ, ρ)$ )

For a finite abelian group

G

Γ \subseteq G

, and

ρ > 0

, the Bohr set is

B (Γ, ρ) = {x \in G : ∣ γ (x) - 1∣ \leq ρ for every γ \in Γ} .

Its rank is

∣Γ∣

and its width is

ρ

.

Lower bound for the size of a Bohr set

A Bohr set of rank

d

and width

ρ

satisfies

∣ B (Γ, ρ) ∣ \geq (\frac{ρ}{8})^{d} ∣ G ∣.

The proof partitions each circle coordinate into arcs and applies translation averaging and the pigeonhole principle.

Arithmetic progression in a cyclic Bohr set

When

N

is prime, simultaneous approximation of the frequencies shows that

B (Γ, ρ) \subseteq Z / N Z

contains a centered arithmetic progression of length at least

\frac{1}{8} ρ N^{1/∣Γ∣} .

Almost period of a function

An almost period of a function

F

in a normed space is a shift

t

for which

∥ τ_{t} F - F ∥

is small.

Croot-Sisask almost-periodicity theorem

A, S

in a group satisfy

∣ A + S ∣ \leq K ∣ A ∣

, then for

q \geq 2

and

0 < ϵ < 1

there is

T \subseteq S

with

∣ T ∣ \geq (2 K)^{- O (q / ϵ^{2})} ∣ S ∣

such that every

t \in T - T

is an

L^{q}

almost period of

1_{A} * f

:

∥ τ_{t} (1_{A} * f) - 1_{A} * f ∥_{q} \leq ϵ ∥ 1_{A} ∥_{1} ∥ f ∥_{q} .

Finite-field character approximation

Sampling the normalized Fourier expansion of

f : F_{p}^{n} \to C

gives an average of

O (q / ϵ^{2})

phase-adjusted characters whose

L^{q}

error is at most

ϵ ∥ f ∥_{1}

. The common kernel of those characters is therefore a low-codimension subspace of almost periods of

f

.

Gowers uniformity norm ( $U^{k}$ norm)

The Gowers uniformity norm measures the average multiplicative derivative of a function around affine cubes. The

U^{k}

norm detects polynomial phases of degree below

k

.

Gowers inner product ( $⟨(f_{ϵ}) ⟩_{U^{k}}$ )

For functions indexed by

ϵ \in {0, 1}^{k}

, the Gowers inner product is

⟨ (f_{ϵ}) ⟩_{U^{k}} = E_{x, h_{1}, \dots, h_{k}} \prod_{ϵ \in {0, 1}^{k}} C^{∣ ϵ ∣} f_{ϵ} (x + ϵ \cdot h),

where

C

denotes complex conjugation.

Gowers-Cauchy-Schwarz inequality

Repeated Cauchy-Schwarz inequality gives

∣ ⟨ (f_{ϵ}) ⟩_{U^{k}} ∣ \leq \prod_{ϵ \in {0, 1}^{k}} ∥ f_{ϵ} ∥_{U^{k}} .

Quadratic phase

A quadratic phase on

F_{p}^{n}

x \mapsto e_{p} (q (x))

, where

q

is a quadratic form and

e_{p} (t) = e^{2 πi t / p}

. Its third multiplicative derivative is one, so its

U^{3}

norm is one.

Inverse theorem for the Gowers U3 norm over a finite field ( $U^{3}$ inverse theorem)

For fixed prime

p

, a one-bounded function on

F_{p}^{n}

with

U^{3}

norm at least

δ

has correlation bounded below in terms of

p

and

δ

with a quadratic phase, with the usual nonclassical formulation in small characteristic.

Freiman homomorphism

A Freiman homomorphism preserves additive quadruples: whenever

x_{1} + x_{2} = x_{3} + x_{4}

in its domain, its values satisfy

ϕ (x_{1}) + ϕ (x_{2}) = ϕ (x_{3}) + ϕ (x_{4})

.

 Ancestors (4)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Additive combinatorics by

Wikipedia Bot  1

Additive combinatorics is a branch of mathematics that studies combinatorial properties of integers, particularly focusing on additive structures within sets of numbers. It explores how subsets of integers can be analyzed using tools from both combinatorics and number theory, often involving questions about sums, differences, and other additive operations. Key topics in additive combinatorics include: 1. **Sumsets**: The study of sets formed by the sums of elements from given sets.

 Read the full article

  See all articles in the same topic Create my own version