You are currently browsing the tag archive for the ‘linear patterns’ tag.

In the previous lecture notes, we used (linear) Fourier analysis to control the number of three-term arithmetic progressions ${a, a+r, a+2r}$ in a given set ${A}$. The power of the Fourier transform for this problem ultimately stemmed from the identity

$\displaystyle \mathop{\bf E}_{n,r \in {\bf Z}/N'{\bf Z}} 1_A(n) 1_A(n+r) 1_A(n+2r)$

$\displaystyle = \sum_{\alpha \in \frac{1}{N'}{\bf Z} / {\bf Z}} \hat 1_A(\alpha) \hat 1_A(-2\alpha) \hat 1_A(\alpha) \ \ \ \ \ (1)$

for any cyclic group ${{\bf Z}/N'{\bf Z}}$ and any subset ${A}$ of that group (analogues of this identity also exist for other finite abelian groups, and to a lesser extent to non-abelian groups also, although that is not the focus of my current discussion). As it turns out, linear Fourier analysis is not able to discern higher order patterns, such as arithmetic progressions of length four; we give some demonstrations of this below the fold, taking advantage of the polynomial recurrence theory from Notes 1.

The main objective of this course is to introduce the (still nascent) theory of higher order Fourier analysis, which is capable of studying higher order patterns. The full theory is still rather complicated (at least, at our present level of understanding). However, one aspect of the theory is relatively simple, namely that we can largely reduce the study of arbitrary additive patterns to the study of a single type of additive pattern, namely the parallelopipeds

$\displaystyle ( x + \omega_1 h_1 + \ldots + \omega_d h_d )_{\omega_1,\ldots,\omega_d \in \{0,1\}}. \ \ \ \ \ (2)$

Thus for instance, for ${d=1}$ one has the line segments

$\displaystyle x, x+h_1 \ \ \ \ \ (3)$

for ${d=2}$ one has the parallelograms

$\displaystyle x, x+h_1, x+h_2, x+h_1+h_2, \ \ \ \ \ (4)$

for ${d=3}$ one has the parallelopipeds

$\displaystyle x, x+h_1, x+h_2, x+h_3, x+h_1+h_2, x+h_1+h_3, x+h_2+h_3, x+h_1+h_2+h_3. \ \ \ \ \ (5)$

These patterns are particularly pleasant to handle, thanks to the large number of symmetries available on the discrete cube ${\{0,1\}^d}$. For instance, whereas establishing the presence of arbitrarily long arithmetic progressions in dense sets is quite difficult (Szemerédi’s theorem), establishing arbitrarily high-dimensional parallelopipeds is much easier:

Exercise 1 Let ${A \subset [N]}$ be such that ${|A| > \delta N}$ for some ${0 < \delta \leq 1}$. If ${N}$ is sufficiently large depending on ${\delta}$, show that there exists an integer ${1 \leq h \ll 1/\delta}$ such that ${|A \cap (A+h)| \gg \delta^2 N}$. (Hint: obtain upper and lower bounds on the set ${\{ (x,y) \in A \times A: x < y \leq x + 10/\delta \}}$.)

Exercise 2 (Hilbert cube lemma) Let ${A \subset [N]}$ be such that ${|A| > \delta N}$ for some ${0 < \delta \leq 1}$, and let ${d \geq 1}$ be an integer. Show that if ${N}$ is sufficiently large depending on ${\delta,d}$, then ${A}$ contains a parallelopiped of the form (2), with ${1 \leq h_1,\ldots,h_d \ll_\delta 1}$ positive integers. (Hint: use the previous exercise and induction.) Conclude that if ${A \subset {\bf Z}}$ has positive upper density, then it contains infinitely many such parallelopipeds for each ${d}$.

Exercise 3 Show that if ${q \geq 1}$ is an integer, and ${d}$ is sufficiently large depending on ${q}$, then for any parallelopiped (2) in the integers ${{\bf Z}}$, there exists ${\omega_1,\ldots,\omega_d \in \{0,1\}}$, not all zero, such that ${x + h_1 \omega_1 + \ldots + h_d \omega_d = x \hbox{ mod } q}$. (Hint: pigeonhole the ${h_i}$ in the residue classes modulo ${q}$.) Use this to conclude that if ${A}$ is the set of all integers ${n}$ such that ${|n-km!| \geq m}$ for all integers ${k, m \geq 1}$, then ${A}$ is a set of positive upper density (and also positive lower density) which does not contain any infinite parallelopipeds (thus one cannot take ${d=\infty}$ in the Hilbert cube lemma).

The standard way to control the parallelogram patterns (and thus, all other (finite complexity) linear patterns) are the Gowers uniformity norms

$\displaystyle \| f\|_{U^d(G)} := {\bf E}_{x,h_1,\ldots,h_d \in G} \prod_{\omega_1,\ldots,\omega_d \in \{0,1\}^d} {\mathcal C}^{\omega_1+\ldots+\omega_d} f(x+\omega_1 h_1 + \ldots + \omega_d h_d) \ \ \ \ \ (6)$

with ${f: G \rightarrow {\bf C}}$ a function on a finite abelian group ${G}$, and ${{\mathcal C}: z \mapsto \overline{z}}$ is the complex conjugation operator; analogues of this norm also exist for group-like objects such as the progression ${[N]}$, and also for measure-preserving systems (where they are known as the Gowers-Host-Kra uniformity seminorms, see this paper of Host-Kra for more discussion). In this set of notes we will focus on the basic properties of these norms; the deepest fact about them, known as the inverse conjecture for these norms, will be discussed in later notes.