7.2 The uncertainty principle and its applications
4 min read•july 30, 2024
The uncertainty principle in finite abelian groups reveals a fundamental trade-off between a set's size and its . 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 , 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