7.2 The uncertainty principle and its applications

The uncertainty principle in finite abelian groups reveals a fundamental trade-off between a set's size and its Fourier transform. This powerful tool helps us understand the structure of sets with special additive properties, like small doubling.

Applications of the uncertainty principle are far-reaching in additive combinatorics. It's used to derive bounds on sum and difference sets, prove the existence of large Fourier coefficients, and plays a key role in important results like the Bogolyubov-Ruzsa lemma.

Uncertainty Principle for Finite Abelian Groups

Statement and Proof

• State the uncertainty principle for finite abelian groups
  • For any non-empty subset A of a finite abelian group G, the product of the size of A and the size of its Fourier transform is at least the size of G
• Prove the uncertainty principle using the following tools:
  • Orthogonality relations for characters of finite abelian groups
  • Cauchy-Schwarz inequality
• Interpret the uncertainty principle as a quantitative version of the fact that a function and its Fourier transform cannot both be simultaneously localized

Fundamental Result and Applications

• Recognize the uncertainty principle as a fundamental result in additive combinatorics
• Apply the uncertainty principle to numerous problems in additive combinatorics, such as:
  • Studying sum sets, difference sets, and related problems
  • Deriving bounds on the size of sum sets and difference sets (see next section for more details)
  • Establishing the existence of large Fourier coefficients for sets with small doubling (see later section for more details)

Uncertainty Principle Applications

Bounds on Sum Sets and Difference Sets

• Use the uncertainty principle to derive lower bounds on the size of:
  • Sum sets A+B (where A+B = {a+b : a ∈ A, b ∈ B})
  • Difference sets A-B (where A-B = {a-b : a ∈ A, b ∈ B}) for subsets A and B of a finite abelian group G
• Show that if A is a subset of G with small doubling (i.e., |A+A| ≤ K|A| for some constant K), then the size of the difference set A-A must be large
  • More precisely, if |A+A| ≤ K|A|, then the uncertainty principle implies that |A-A| ≥ |G|/K
• Obtain similar bounds for the size of the sum set A+B in terms of the sizes of A, B, and their Fourier transforms
• Combine these bounds with other tools, such as the Plünnecke-Ruzsa inequalities, to study the structure of sets with small doubling or related additive properties

Applications in Additive Combinatorics Proofs

• Use the bounds derived from the uncertainty principle in conjunction with other tools to prove important results in additive combinatorics, such as:
  • Freiman's theorem on sets with small doubling
  • Bogolyubov-Ruzsa lemma (see later section for more details)
  • Results on arithmetic progressions in sumsets

Large Fourier Coefficients

Existence of Large Fourier Coefficients

• Use the uncertainty principle to show that sets with small doubling must have large Fourier coefficients
  • Specifically, if A is a subset of a finite abelian group G with |A+A| ≤ K|A| for some constant K, then there exists a non-trivial character χ of G such that the Fourier coefficient |Â(χ)| is at least |A|/√(K|G|)
• Prove this result using:
  • The uncertainty principle
  • The fact that the Fourier transform of the convolution 1A * 1A is equal to |Â|^2 (where 1A is the indicator function of A)

Applications in Additive Combinatorics Proofs

• Use the existence of large Fourier coefficients for sets with small doubling as a key ingredient in several proofs in additive combinatorics, such as:
  • Freiman's theorem on sets with small doubling
  • Bogolyubov-Ruzsa lemma (see next section for more details)
• Apply this result to study the structure of sets with small doubling and related additive properties

Uncertainty Principle vs Bogolyubov-Ruzsa Lemma

Statement of the Bogolyubov-Ruzsa Lemma

• State the Bogolyubov-Ruzsa lemma
  • If A is a subset of a finite abelian group G with |A+A| ≤ K|A| for some constant K, then the 2k-fold sumset 2kA (where 2kA = A+A+...+A, k times) contains a non-trivial subgroup of G of size at least |G|/K^(O(k))

Proof of the Bogolyubov-Ruzsa Lemma

• Understand the role of the uncertainty principle in the proof of the Bogolyubov-Ruzsa lemma
  • Use the uncertainty principle to find a non-trivial character χ with large Fourier coefficient |Â(χ)|
  • Use this character to construct a dense subset of 2kA that is highly structured (i.e., a coset of a subgroup)
• Recognize the importance of the existence of large Fourier coefficients for sets with small doubling in the proof of the Bogolyubov-Ruzsa lemma

Applications of the Bogolyubov-Ruzsa Lemma

• Use the Bogolyubov-Ruzsa lemma as a powerful tool for studying the structure of sets with small doubling
• Apply the Bogolyubov-Ruzsa lemma to numerous problems in additive combinatorics, such as:
  • Proving Freiman's theorem on sets with small doubling
  • Studying arithmetic progressions in sumsets
  • Investigating the structure of sets with related additive properties