4.4 Gowers uniformity norms

Gowers uniformity norms are powerful tools in additive combinatorics. They measure how random-like a function is, helping us understand the structure of sets and functions on finite groups. This connects to arithmetic progressions by quantifying correlations with polynomial phases.

These norms play a crucial role in proving Szemerédi's theorem on arithmetic progressions. They allow us to find structured subsets in dense sets, leading to the existence of long arithmetic progressions. This technique has far-reaching applications in number theory and combinatorics.

Gowers Uniformity Norms

Definition and Properties

• Gowers uniformity norms, denoted as $U^k(f)$, are a family of norms defined on functions $f: G \to \mathbb{C}$, where $G$ is a finite Abelian group and $k$ is a positive integer
• The $U^1$ norm represents the absolute value of the average of $f$ over $G$, while the $U^2$ norm is the $L^4$ norm of $f$ minus the square of the $L^2$ norm
• Higher Gowers uniformity norms $U^k(f)$ are defined recursively using the $U^{k-1}$ norm and a convolution operation
• Gowers uniformity norms measure the correlation of $f$ with polynomial phases of degree less than $k$ (linear, quadratic, cubic, etc.)
• The $U^k$ norm is always bounded between 0 and 1, with $U^k(f) = 0$ if and only if $f$ is a polynomial phase of degree less than $k$

Invariance and Inequalities

• Gowers uniformity norms are invariant under translation and multiplication by a constant
  • If $g(x) = f(x+a)$ for some $a \in G$, then $U^k(g) = U^k(f)$
  • If $h(x) = cf(x)$ for some constant $c$, then $U^k(h) = |c|U^k(f)$
• The $U^k$ norm satisfies the Cauchy-Schwarz-Gowers inequality, which generalizes the Cauchy-Schwarz inequality
  • For functions $f_1, f_2, \ldots, f_{2^k}: G \to \mathbb{C}$, we have: $\left|\mathbb{E}_{x,h_1,\ldots,h_k \in G}\prod_{\omega \in \{0,1\}^k}f_\omega(x+\omega \cdot h)\right| \leq \prod_{\omega \in \{0,1\}^k}U^k(f_\omega)$

Calculating Gowers Uniformity Norms

Examples of Gowers Uniformity Norms

• For a constant function $f(x) = c$, the Gowers uniformity norms are $U^k(f) = |c|$ for all $k$
• For a linear function $f(x) = ax + b$ on $\mathbb{Z}_N$, the Gowers uniformity norms are $U^1(f) = |a/N + b|$ and $U^k(f) = 0$ for $k \geq 2$
  • This is because linear functions are polynomial phases of degree 1
• For the Möbius function $\mu(n)$, it is conjectured that the Gowers uniformity norms $U^k(\mu)$ tend to zero as $k \to \infty$
  • This is related to the randomness of the Möbius function and its correlation with polynomial phases

Computing and Estimating Gowers Uniformity Norms

• For the von Mangoldt function $\Lambda(n)$, the Gowers uniformity norms $U^k(\Lambda)$ are related to the distribution of primes in arithmetic progressions
  • The von Mangoldt function is defined as $\Lambda(n) = \log p$ if $n$ is a power of a prime $p$, and $\Lambda(n) = 0$ otherwise
• Computing Gowers uniformity norms for general functions can be done using the recursive definition and convolution operation
  • For example, to compute $U^3(f)$, one needs to calculate $\mathbb{E}_{x,h_1,h_2,h_3}f(x)\overline{f(x+h_1)f(x+h_2)f(x+h_3)}f(x+h_1+h_2)\overline{f(x+h_1+h_3)f(x+h_2+h_3)}f(x+h_1+h_2+h_3)$
• Gowers uniformity norms can be estimated using sampling techniques and probabilistic methods
  • Random sampling can be used to approximate the averages in the definition of Gowers uniformity norms
  • Concentration inequalities (Chernoff bounds, Hoeffding's inequality) can be used to bound the error in the estimates

Gowers Norms and Arithmetic Progressions

Gowers Uniformity Norms and Arithmetic Progressions

• The $U^k$ norm of a function $f$ is related to the number of $k$-term arithmetic progressions in the support of $f$
  • The support of $f$ is the set of points where $f$ is non-zero
• If $f$ is the characteristic function of a set $A \subseteq G$, then $U^k(f)$ measures the density of $k$-term arithmetic progressions in $A$
  • A characteristic function $1_A(x)$ is defined as $1_A(x) = 1$ if $x \in A$, and $1_A(x) = 0$ otherwise
• The Gowers uniformity norms can be used to prove Szemerédi's theorem, which states that any subset of the integers with positive upper density contains arbitrarily long arithmetic progressions
  • The upper density of a set $A \subseteq \mathbb{N}$ is defined as $\limsup_{N \to \infty} |A \cap [1,N]|/N$

Inverse Theorem and Applications

• Gowers' proof of Szemerédi's theorem uses the $U^k$ norms to find a structured subset of $A$ that contains many arithmetic progressions
  • The structured subset is a set that correlates with a polynomial phase of degree less than $k$
• The inverse theorem for the Gowers uniformity norms states that if $U^k(f)$ is large, then $f$ correlates with a polynomial phase of degree less than $k$
  • Formally, if $U^k(f) \geq \delta$, then there exists a polynomial phase $\phi$ of degree less than $k$ such that $|\mathbb{E}_{x \in G}f(x)\overline{\phi(x)}| \geq c(\delta)$, where $c(\delta)$ is a constant depending on $\delta$
• This inverse theorem is a key ingredient in the proof of Szemerédi's theorem and its generalizations
  • It allows one to reduce the problem of finding arithmetic progressions to finding structured sets that correlate with polynomial phases

Applications of Gowers Uniformity Norms

Additive Combinatorics

• Gowers uniformity norms can be used to prove the density Hales-Jewett theorem, which is a multidimensional generalization of Szemerédi's theorem
  • The Hales-Jewett theorem states that for any fixed $k$ and $r$, any subset of $[k]^n$ with positive density contains a combinatorial line (a set of points that agree on all but one coordinate) if $n$ is sufficiently large
• The $U^3$ norm is related to the existence of parallelepipeds in subsets of Abelian groups, which has applications in additive combinatorics
  • A parallelepiped is a set of points of the form $\{x, x+d_1, x+d_2, x+d_3, x+d_1+d_2, x+d_1+d_3, x+d_2+d_3, x+d_1+d_2+d_3\}$ for some $x, d_1, d_2, d_3 \in G$
• Gowers uniformity norms can be used to prove the Green-Tao theorem, which states that the primes contain arbitrarily long arithmetic progressions
  • The proof uses a transference principle to reduce the problem to finding arithmetic progressions in a subset of the integers with positive relative density in a pseudorandom set

Ergodic Theory and Graph Theory

• In ergodic theory, Gowers uniformity norms are used to study the convergence of multiple ergodic averages and prove results about nilsystems and nilsequences
  • A nilsystem is a dynamical system that can be represented as a homogeneous space of a nilpotent Lie group, and a nilsequence is a sequence that can be approximated by a polynomial sequence on a nilsystem
• The Gowers-Host-Kra seminorms, which generalize the Gowers uniformity norms to measure the degree of uniformity of a dynamical system, have important applications in ergodic theory
  • They are used to prove the convergence of multiple ergodic averages for commuting transformations and to characterize the structure of measure-preserving systems
• Gowers uniformity norms have been used to prove results in graph theory, such as the hypergraph removal lemma and the induced removal lemma
  • The hypergraph removal lemma states that for any fixed hypergraph $H$ and $\varepsilon > 0$, any hypergraph on $n$ vertices with at most $o(n^{|V(H)|})$ copies of $H$ can be made $H$-free by removing at most $\varepsilon n^{|V(H)|}$ edges
  • The induced removal lemma is a similar result for induced subgraphs