Source author record

Terence Tao

Terence Tao appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO math.NT math.PR math.DS math.CA math.GR math.AP math.AG math.MG math-ph math.MP math.OA math.CV math.FA math.RA math.RT hep-ph hep-th math.AT math.CT math.SP

Catalog footprint

What is connected

113works

21topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

A Host--Kra ${\mathbf F}_2^ω$-system of order $5$ that is not Abramov of order $5$, and non-measurability of the inverse theorem for the $U^6({\mathbf F}_2^n)$ norm

It was conjectured by Bergelson, Tao, and Ziegler \cite{btz} that every Host--Kra $\F_p^ω$-system of order $k$ is an Abramov system of order $k$. This conjecture has been verified for $k \leq p+1$. In this paper we show that the conjecture fails when $k=5, p=2$. We in fact establish a stronger (combinatorial) statement, in that we produce a bounded function $f: \F_2^n \to \C$ of large Gowers norm $\|f\|_{U^6(\F_2^n)}$ which (as per the inverse theorem for that norm) correlates with a non-classical quintic phase polynomial $e(P)$, but with the property that all such phase polynomials $e(P)$ are ``non-measurable'' in the sense that they cannot be well approximated by functions of a bounded number of random translates of $f$. A simpler version of our construction can also be used to answer a question of Candela, González-Sánchez, and Szegedy \cite{CGSS}.

preprint2026arXiv

Polynomial towers and inverse Gowers theory for bounded-exponent groups

In this paper we develop Host--Kra and inverse Gowers theory for abelian groups of bounded exponent. We show that the Host--Kra factors $Z^{\leq k}(\mathrm{X})$ associated with actions of such groups admit extensions with the structure of \emph{polynomial towers}. This new notion is a system obtained as a finite iteration of abelian extensions of the trivial system by polynomial cocycles; crucially, the intermediate extensions in this system are not required to agree with the Host--Kra factors. We prove that all such extensions are Abramov (generalizing a recent result of Candela, González-Sánchez, and Szegedy), but not necessarily Weyl, and have the structure of k-step translational systems. Combining this structure theorem with a correspondence principle due to the first and third authors, we derive an inverse theorem for the Gowers norms on finite abelian groups of bounded exponent: large $U^{k+1}$-norm implies large correlation with a polynomial of degree $\le k$ (on the same group), even when the exponent is not square-free or is divisible by small primes. This resolves a conjecture of the first and third authors for such groups, and also answers a question of Candela, González-Sánchez, and Szegedy.

preprint2024arXiv

New bounds for Szemeredi's theorem, II: A new bound for $r_4(N)$

Define $r_4(N)$ to be the largest cardinality of a set $A$ in $\{1,\dots,N\}$ which does not contain four elements in arithmetic progression. In 1998 Gowers proved that $r_4(N) \ll N(\log \log N)^{-c}$ for some absolute constant $c> 0$. In this paper (part II of a series) we improve this to $r_4(N) \ll N e^{-c\sqrt{\log \log N}}$. In part III of the series we will use a more elaborate argument to improve this to $r_4(N) \ll N(\log N)^{-c}$.

preprint2022arXiv

Almost all orbits of the Collatz map attain almost bounded values

Define the \emph{Collatz map} $\mathrm{Col} : \mathbb{N}+1 \to \mathbb{N}+1$ on the positive integers $\mathbb{N}+1 = \{1,2,3,\dots\}$ by setting $\mathrm{Col}(N)$ equal to $3N+1$ when $N$ is odd and $N/2$ when $N$ is even, and let $\mathrm{Col}_{\min}(N) := \inf_{n \in \mathbb{N}} \mathrm{Col}^n(N)$ denote the minimal element of the Collatz orbit $N, \mathrm{Col}(N), \mathrm{Col}^2(N), \dots$. The infamous \emph{Collatz conjecture} asserts that $\mathrm{Col}_{\min}(N)=1$ for all $N \in \mathbb{N}+1$. Previously, it was shown by Korec that for any $θ> \frac{\log 3}{\log 4} \approx 0.7924$, one has $\mathrm{Col}_{\min}(N) \leq N^θ$ for almost all $N \in \mathbb{N}+1$ (in the sense of natural density). In this paper we show that for \emph{any} function $f : \mathbb{N}+1 \to \mathbb{R}$ with $\lim_{N \to \infty} f(N)=+\infty$, one has $\mathrm{Col}_{\min}(N) \leq f(N)$ for almost all $N \in \mathbb{N}+1$ (in the sense of logarithmic density). Our proof proceeds by establishing an approximate transport property for a certain first passage random variable associated with the Collatz iteration (or more precisely, the closely related Syracuse iteration), which in turn follows from estimation of the characteristic function of a certain skew random walk on a $3$-adic cyclic group at high frequencies. This estimation is achieved by studying how a certain two-dimensional renewal process interacts with a union of triangles associated to a given frequency.

preprint2022arXiv

An averaged form of Chowla's conjecture

Let $λ$ denote the Liouville function. A well known conjecture of Chowla asserts that for any distinct natural numbers $h_1,\dots,h_k$, one has $\sum_{1 \leq n \leq X} λ(n+h_1) \dotsm λ(n+h_k) = o(X)$ as $X \to \infty$. This conjecture remains unproven for any $h_1,\dots,h_k$ with $k \geq 2$. In this paper, using the recent results of the first two authors on mean values of multiplicative functions in short intervals, combined with an argument of Katai and Bourgain-Sarnak-Ziegler, we establish an averaged version of this conjecture, namely $$\sum_{h_1,\dots,h_k \leq H} \left|\sum_{1 \leq n \leq X} λ(n+h_1) \dotsm λ(n+h_k)\right| = o(H^kX)$$ as $X \to \infty$ whenever $H = H(X) \leq X$ goes to infinity as $X \to \infty$, and $k$ is fixed. Related to this, we give the exponential sum estimate $$ \int_0^X \left|\sum_{x \leq n \leq x+H} λ(n) e(αn)\right| dx = o( HX )$$ as $X \to \infty$ uniformly for all $α\in \mathbb{R}$, with $H$ as before. Our arguments in fact give quantitative bounds on the decay rate (roughly on the order of $\frac{\log\log H}{\log H}$), and extend to more general bounded multiplicative functions than the Liouville function, yielding an averaged form of a (corrected) conjecture of Elliott.

preprint2022arXiv

An uncountable Mackey-Zimmer theorem

The Mackey-Zimmer theorem classifies ergodic group extensions $X$ of a measure-preserving system $Y$ by a compact group $K$, by showing that such extensions are isomorphic to a group skew-product $X \equiv Y \rtimes_ρH$ for some closed subgroup $H$ of $K$. An analogous theorem is also available for ergodic homogeneous extensions $X$ of $Y$, namely that they are isomorphic to a homogeneous skew-product $Y \rtimes_ρH/M$. These theorems have many uses in ergodic theory, for instance playing a key role in the Host-Kra structural theory of characteristic factors of measure-preserving systems. The existing proofs of the Mackey-Zimmer theorem require various "countability", "separability", or "metrizability" hypotheses on the group $Γ$ that acts on the system, the base space $Y$, and the group $K$ used to perform the extension. In this paper we generalize the Mackey-Zimmer theorem to "uncountable" settings in which these hypotheses are omitted, at the cost of making the notion of a measure-preserving system and a group extension more abstract. However, this abstraction is partially counteracted by the use of a "canonical model" for abstract measure-preserving systems developed in a companion paper. In subsequent work we will apply this theorem to also obtain uncountable versions of the Host-Kra structural theory.

preprint2022arXiv

An uncountable Moore-Schmidt theorem

We prove an extension of the Moore-Schmidt theorem on the triviality of the first cohomology class of cocycles for the action of an arbitrary discrete group on an arbitrary measure space and for cocycles with values in an arbitrary compact Hausdorff abelian group. The proof relies on a "conditional" Pontryagin duality for spaces of abstract measurable maps.

preprint2022arXiv

Foundational aspects of uncountable measure theory: Gelfand duality, Riesz representation, canonical models, and canonical disintegration

We collect several foundational results regarding the interaction between locally compact spaces, probability spaces and probability algebras, and commutative $C^*$-algebras and von Neumann algebras equipped with traces, in the "uncountable" setting in which no separability, metrizability, or standard Borel hypotheses are placed on these spaces and algebras. In particular, we review the Gelfand dualities and Riesz representation theorems available in this setting. We also present a canonical model that represents probability algebras as compact Hausdorff probability spaces in a completely functorial fashion, and apply this model to obtain a canonical disintegration theorem and to readily construct various product measures. These tools are useful in applications to "uncountable" ergodic theory (as demonstrated by the authors and others).

preprint2022arXiv

Perfectly packing a square by squares of nearly harmonic sidelength

A well known open problem of Meir and Moser asks if the squares of sidelength $1/n$ for $n \geq 2$ can be packed perfectly into a square of area $\sum_{n=2}^\infty \frac{1}{n^2} = \frac{π^2}{6}-1$. In this paper we show that for any $1/2 < t < 1$, and any $n_0$ that is sufficiently large depending on $t$, the squares of sidelength $n^{-t}$ for $n \geq n_0$ can be packed perfectly into a square of area $\sum_{n=n_0}^\infty \frac{1}{n^{2t}}$. This was previously known (if one packs a rectangle instead of a square) for $1/2 < t \leq 2/3$ (in which case one can take $n_0=1$).

preprint2022arXiv

Pointwise ergodic theorems for non-conventional bilinear polynomial averages

We establish convergence in norm and pointwise almost everywhere for the non-conventional (in the sense of Furstenberg) bilinear polynomial ergodic averages \[ A_N(f,g)(x) := \frac{1}{N} \sum_{n =1}^N f(T^nx) g(T^{P(n)}x)\] as $N \to \infty$, where $T \colon X \to X$ is a measure-preserving transformation of a $σ$-finite measure space $(X,μ)$, $P(\mathrm{n}) \in \mathbb Z[\mathrm{n}]$ is a polynomial of degree $d \geq 2$, and $f \in L^{p_1}(X), \ g \in L^{p_2}(X)$ for some $p_1,p_2 > 1$ with $\frac{1}{p_1} + \frac{1}{p_2} \leq 1$. We also establish an $r$-variational inequality for these averages (at lacunary scales) in the optimal range $r > 2$. We are also able to "break duality" by handling some ranges of exponents $p_1,p_2$ with $\frac{1}{p_1}+\frac{1}{p_2} > 1$, at the cost of increasing $r$ slightly. This gives an affirmative answer to Problem 11 from Frantzikinakis' open problems survey for the Furstenberg--Weiss averages (with $P(\mathrm{n})=\mathrm{n}^2$), which is a bilinear variant of Question 9 considered by Bergelson in his survey on Ergodic Ramsey Theory from 1996. This also gives a contribution to the Furstenberg-Bergelson-Leibman conjecture. Our methods combine techniques from harmonic analysis with the recent inverse theorems of Peluse and Prendiville in additive combinatorics. At large scales, the harmonic analysis of the adelic integers $\mathbb A_{\mathbb Z}$ also plays a role.

preprint2022arXiv

Sendov's conjecture for sufficiently high degree polynomials

Sendov's conjecture asserts that if a complex polynomial $f$ of degree $n \geq 2$ has all of its zeroes in closed unit disk $\{ z: |z| \leq 1 \}$, then for each such zero $λ_0$ there is a zero of the derivative $f'$ in the closed unit disk $\{ z: |z-λ_0| \leq 1 \}$. This conjecture is known for $n < 9$, but only partial results are available for higher $n$. We show that there exists a constant $n_0$ such that Sendov's conjecture holds for $n \geq n_0$. For $λ_0$ away from the origin and the unit circle we can appeal to the prior work of Dégot and Chalebgwa; for $λ_0$ near the unit circle we refine a previous argument of Miller (and also invoke results of Chijiwa when $λ_0$ is extremely close to the unit circle); and for $λ_0$ near the origin we introduce a new argument using compactness methods, balayage, and the argument principle.

preprint2022arXiv

The Hardy--Littlewood--Chowla conjecture in the presence of a Siegel zero

Assuming that Siegel zeros exist, we prove a hybrid version of the Chowla and Hardy--Littlewood prime tuples conjectures. Thus, for an infinite sequence of natural numbers $x$, and any distinct integers $h_1,\dots,h_k,h'_1,\dots,h'_\ell$, we establish an asymptotic formula for $$\sum_{n\leq x}Λ(n+h_1)\cdots Λ(n+h_k)λ(n+h_{1}')\cdots λ(n+h_{\ell}')$$ for any $0\leq k\leq 2$ and $\ell \geq 0$. Specializing to either $\ell=0$ or $k=0$, we deduce the previously known results on the Hardy--Littlewood (or twin primes) conjecture and the Chowla conjecture under the existence of Siegel zeros, due to Heath-Brown and Chinis, respectively. The range of validity of our asymptotic formula is wider than in these previous results.

preprint2021arXiv

Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra

If $A$ is an $n \times n$ Hermitian matrix with eigenvalues $λ_1(A),\dots,λ_n(A)$ and $i,j = 1,\dots,n$, then the $j^{\mathrm{th}}$ component $v_{i,j}$ of a unit eigenvector $v_i$ associated to the eigenvalue $λ_i(A)$ is related to the eigenvalues $λ_1(M_j),\dots,λ_{n-1}(M_j)$ of the minor $M_j$ of $A$ formed by removing the $j^{\mathrm{th}}$ row and column by the formula $$ |v_{i,j}|^2\prod_{k=1;k\neq i}^{n}\left(λ_i(A)-λ_k(A)\right)=\prod_{k=1}^{n-1}\left(λ_i(A)-λ_k(M_j)\right)\,.$$ We refer to this identity as the \emph{eigenvector-eigenvalue identity} and show how this identity can also be used to extract the relative phases between the components of any given eigenvector. Despite the simple nature of this identity and the extremely mature state of development of linear algebra, this identity was not widely known until very recently. In this survey we describe the many times that this identity, or variants thereof, have been discovered and rediscovered in the literature (with the earliest precursor we know of appearing in 1834). We also provide a number of proofs and generalizations of the identity.

preprint2021arXiv

Singmaster's conjecture in the interior of Pascal's triangle

Singmaster's conjecture asserts that every natural number greater than one occurs at most a bounded number of times in Pascal's triangle; that is, for any natural number $t \geq 2$, the number of solutions to the equation $\binom{n}{m} = t$ for natural numbers $1 \leq m < n$ is bounded. In this paper we establish this result in the interior region $\exp(\log^{2/3+\varepsilon} n) \leq m \leq n-\exp(\log^{2/3 + \varepsilon} n)$ for any fixed $\varepsilon > 0$. Indeed, when $t$ is sufficiently large depending on $\varepsilon$, we show that there are at most four solutions (or at most two in either half of Pascal's triangle) in this region. We also establish analogous results for the equation $(n)_m = t$, where $(n)_m := n(n-1)\ldots(n-m+1)$ denotes the falling factorial.

preprint2020arXiv

Correlations of the von Mangoldt and higher divisor functions II. Divisor correlations in short ranges

We study the problem of obtaining asymptotic formulas for the sums $\sum_{X < n \leq 2X} d_k(n) d_l(n+h)$ and $\sum_{X < n \leq 2X} Λ(n) d_k(n+h)$, where $Λ$ is the von Mangoldt function, $d_k$ is the $k^{\operatorname{th}}$ divisor function, $X$ is large and $k \geq l \geq 2$ are real numbers. We show that for almost all $h \in [-H, H]$ with $H = (\log X)^{10000 k \log k}$, the expected asymptotic estimate holds. In our previous paper we were able to deal also with the case of $Λ(n) Λ(n + h)$ and we obtained better estimates for the error terms at the price of having to take $H = X^{8/33 + \varepsilon}$.

preprint2020arXiv

Exploring the toolkit of Jean Bourgain

Gian-Carlo Rota once asserted that "every mathematician only has a few tricks". The sheer breadth and ingenuity in the work of Jean Bourgain may at first glance appear to be a counterexample to this maxim. However, as we hope to illustrate in this article, even Bourgain relied frequently on a core set of tools, which formed the base from which problems in many disparate mathematical fields could then be attacked. We discuss a selected number of these tools here, and then perform a case study of how an argument in one of Bourgain's papers can be interpreted as a sequential application of several of these tools.

preprint2020arXiv

Homogenization of iterated singular integrals with applications to random quasiconformal maps

We study homogenization of iterated randomized singular integrals and homeomorphic solutions to the Beltrami differential equation with a random Beltrami coefficient. More precisely, let $(F_j)_{j \geq 1}$ be a sequence of normalized homeomorphic solutions to the planar Beltrami equation $\overline{\partial} F_j (z)=μ_j(z,ω) \partial F_j(z),$ where the random dilatation satisfies $|μ_j|\leq k<1$ and has locally periodic statistics, for example of the type $$μ_j (z,ω)=ϕ(z)\sum_{n\in \mathbf{Z}^2}g(2^j z-n,X_{n}(ω)), $$ where $g(z,ω)$ decays rapidly in $z$, the random variables $X_{n}$ are i.i.d., and $ϕ\in C^\infty_0$. We establish the almost sure and local uniform convergence as $j\to\infty$ of the maps $F_j$ to a deterministic quasiconformal limit $F_\infty$. This result is obtained as an application of our main theorem, which deals with homogenization of iterated randomized singular integrals. As a special case of our theorem, let $T_1,\ldots , T_{m}$ be translation and dilation invariant singular integrals on ${\bf R}^d, $ and consider a $d$-dimensional version of $μ_j$, e.g., as defined above or within a more general setting. We then prove that there is a deterministic function $f$ such that almost surely as $j\to\infty$, $$ μ_j T_{m}μ_j\ldots T_1μ_j\to f \quad \textrm{weakly in } L^p,\quad 1 < p < \infty\ . $$

preprint2020arXiv

On the universality of potential well dynamics

Given a smooth potential function $V : \mathbf{R}^m \to \mathbf{R}$, one can consider the ODE $\partial_t^2 u = -(\nabla V)(u)$ describing the trajectory of a particle $t \mapsto u(t)$ in the potential well $V$. We consider the question of whether the dynamics of this family of ODE are \emph{universal} in the sense that they contain (as embedded copies) any first-order ODE $\partial_t u = X(u)$ arising from a smooth vector field $X$ on a manifold $M$. Assuming that $X$ is nonsingular and $M$ is compact, we show (using the Nash embedding theorem) that this is possible precisely when the flow $(M,X)$ supports a geometric structure which we call a \emph{strongly adapted $1$-form}; many smooth flows do have such a $1$-form, but we give an example (due to Bryant) of a flow which does not, and hence cannot be modeled by the dynamics of a potential well. As one consequence of this embeddability criterion, we construct an example of a (coercive) potential well system which is \emph{Turing complete} in the sense that the halting of any Turing machine with a given input is equivalent to a certain bounded trajectory in this system entering a certain open set. In particular, this system contains trajectories for which it is undecidable whether that trajectory enters such a set. Remarkably, the above results also hold if one works instead with the nonlinear wave equation $\partial_t^2 u - Δu = -(\nabla V)(u)$ on a torus instead of a particle in a potential well, or if one replaces the target domain $\mathbf{R}^m$ by a more general Riemannian manifold.

preprint2020arXiv

Quantitative bounds for critically bounded solutions to the Navier-Stokes equations

We revisit the regularity theory of Escauriaza, Seregin, and Šverák for solutions to the three-dimensional Navier-Stokes equations which are uniformly bounded in the critical $L^3_x(\mathbf{R}^3)$ norm. By replacing all invocations of compactness methods in these arguments with quantitative substitutes, and similarly replacing unique continuation and backwards uniqueness estimates by their corresponding Carleman inequalities, we obtain quantitative bounds for higher regularity norms of these solutions in terms of the critical $L^3_x$ bound (with a dependence that is triple exponential in nature). In particular, we show that as one approaches a finite blowup time $T_*$, the critical $L^3_x$ norm must blow up at a rate $(\log\log\log \frac{1}{T_*-t})^c$ or faster for an infinite sequence of times approaching $T_*$ and some absolute constant $c>0$.

preprint2020arXiv

Sharp bounds for multilinear curved Kakeya, restriction and oscillatory integral estimates away from the endpoint

We revisit the multilinear Kakeya, curved Kakeya, restriction, and oscillatory integral estimates that were obtained in paper of Bennett, Carbery, and the author using a heat flow monotonicity method applied to a fractional Cartesian product, together with induction on scales arguments. Many of these estimates contained losses of the form $R^\varepsilon$ (or $\log^{O(1)} R$) for some scale factor $R$. By further developing the heat flow method, and applying it directly for the first time to the multilinear curved Kakeya and restriction settings, we are able to eliminate these losses, as long as the exponent $p$ stays away from the endpoint. In particular, we establish global multilinear restriction estimates away from the endpoint, without any curvature hypotheses on the hypersurfaces.

preprint2020arXiv

Sumset and inverse sumset theorems for Shannon entropy

Let $G = (G,+)$ be an additive group. The sumset theory of Plünnecke and Ruzsa gives several relations between the size of sumsets $A+B$ of finite sets $A, B$, and related objects such as iterated sumsets $kA$ and difference sets $A-B$, while the inverse sumset theory of Freiman, Ruzsa, and others characterises those finite sets $A$ for which $A+A$ is small. In this paper we establish analogous results in which the finite set $A \subset G$ is replaced by a discrete random variable $X$ taking values in $G$, and the cardinality $|A|$ is replaced by the Shannon entropy $\mathrm{Ent}(X)$. In particular, we classify the random variable $X$ which have small doubling in the sense that $\mathrm{Ent}(X_1+X_2) = \mathrm{Ent}(X)+O(1)$ when $X_1,X_2$ are independent copies of $X$, by showing that they factorise as $X = U+Z$ where $U$ is uniformly distributed on a coset progression of bounded rank, and $\mathrm{Ent}(Z) = O(1)$. When $G$ is torsion-free, we also establish the sharp lower bound $\mathrm{Ent}(X+X) \geq \mathrm{Ent}(X) + {1/2} \log 2 - o(1)$, where $o(1)$ goes to zero as $\mathrm{Ent}(X) \to \infty$.

preprint2016arXiv

Equivalence of the logarithmically averaged Chowla and Sarnak conjectures

Let $λ$ denote the Liouville function. The Chowla conjecture asserts that $$ \sum_{n \leq X} λ(a_1 n + b_1) λ(a_2 n+b_2) \dots λ(a_k n + b_k) = o_{X \to \infty}(X) $$ for any fixed natural numbers $a_1,a_2,\dots,a_k$ and non-negative integer $b_1,b_2,\dots,b_k$ with $a_ib_j-a_jb_i \neq 0$ for all $1 \leq i < j \leq k$, and any $X \geq 1$. This conjecture is open for $k \geq 2$. As is well known, this conjecture implies the conjecture of Sarnak that $$ \sum_{n \leq X} λ(n) f(n) = o_{X \to \infty}(X)$$ whenever $f : {\bf N} \to {\bf C}$ is a fixed deterministic sequence and $X \geq 1$. In this paper, we consider the weaker logarithmically averaged versions of these conjectures, namely that $$ \sum_{X/ω\leq n \leq X} \frac{λ(a_1 n + b_1) λ(a_2 n+b_2) \dots λ(a_k n + b_k)}{n} = o_{ω\to \infty}(\log ω) $$ and $$ \sum_{X/ω\leq n \leq X} \frac{λ(n) f(n)}{n} = o_{ω\to \infty}(\log ω)$$ under the same hypotheses on $a_1,\dots,a_k,b_1,\dots,b_k$ and $f$, and for any $2 \leq ω\leq X$. Our main result is that these latter two conjectures are logically equivalent to each other, as well as to the "local Gowers uniformity" of the Liouville function. The main tools used here are the entropy decrement argument of the author used recently to establish the $k=2$ case of the logarithmically averaged Chowla conjecture, as well as the inverse conjecture for the Gowers norms, obtained by Green, Ziegler, and the author.

preprint2016arXiv

Finite time blowup for high dimensional nonlinear wave systems with bounded smooth nonlinearity

We consider the global regularity problem for nonlinear wave systems $$ \Box u = f(u) $$ on Minkowski spacetime ${\bf R}^{1+d}$ with d'Alambertian $\Box := -\partial_t^2 + \sum_{i=1}^d \partial_{x_i}^2$, where the field $u \colon {\bf R}^{1+d} \to {\bf R}^m$ is vector-valued, and the nonlinearity $f \colon {\bf R}^m \to {\bf R}^m$ is a smooth function with $f(0)=0$ and all derivatives bounded; the higher-dimensional sine-Gordon equation $\Box u = \sin u$ is a model example of this class of nonlinear wave system. For dimensions $d \leq 9$, it follows from the work of Heinz, Pecher, Brenner, and von Wahl that one has smooth solutions to this equation for any smooth choice of initial data. Perhaps surprisingly, we show that this result is almost sharp, in the sense that for any $d \geq 11$, there exists an $m$ (in fact we can take $m=2$) and a nonlinearity $f \colon {\bf R}^m \to {\bf R}^m$ with all derivatives bounded, for which the above equation admits solutions that blow up in finite time. The intermediate case $d=10$ remains open.

preprint2016arXiv

Finite time blowup for Lagrangian modifications of the three-dimensional Euler equation

In the language of differential geometry, the incompressible inviscid Euler equations can be written in vorticity-vector potential form as \begin{align*} \partial_t ω+ {\mathcal L}_u ω&= 0\\ u &= δ\tilde η^{-1} Δ^{-1} ω\end{align*} where $ω$ is the vorticity $2$-form, ${\mathcal L}_u$ denotes the Lie derivative with respect to the velocity field $u$, $Δ$ is the Hodge Laplacian, $δ$ is the codifferential (the negative of the divergence operator), and $\tilde η^{-1}$ is the canonical map from $2$-forms to $2$-vector fields induced by the Euclidean metric $η$. In this paper we consider a generalisation of these Euler equations in three spatial dimensions, in which the vector potential operator $\tilde η^{-1} Δ^{-1}$ is replaced by a more general operator $A$ of order $-2$; this retains the Lagrangian structure of the Euler equations, as well as most of its conservation laws and local existence theory. Despite this, we give three different constructions of such an operator $A$ which admits smooth solutions that blow up in finite time, including an example on ${\bf R}^3$ which is self-adjoint and positive definite. This indicates a barrier to establishing global regularity for the three-dimensional Euler equations, in that any such method must use some property of those equations that is not shared by the generalised Euler equations considered here.

preprint2016arXiv

Polynomial patterns in the primes

Let $P_1,\dots,P_k \colon {\bf Z} \to {\bf Z}$ be polynomials of degree at most $d$ for some $d \geq 1$, with the degree $d$ coefficients all distinct, and admissible in the sense that for every prime $p$, there exists integers $n,m$ such that $n+P_1(m),\dots,n+P_k(m)$ are all not divisible by $p$. We show that there exist infinitely many natural numbers $n,m$ such that $n+P_1(m),\dots,n+P_k(m)$ are simultaneously prime, generalizing a previous result of the authors, which was restricted to the special case $P_1(0)=\dots=P_k(0)=0$ (though it allowed for the top degree coefficients to coincide). Furthermore, we obtain an asymptotic for the number of such prime pairs $n,m$ with $n \leq N$ and $m \leq M$ with $M$ slightly less than $N^{1/d}$. Our arguments rely on four ingredients. The first is a (slightly modified) generalized von Neumann theorem of the authors, reducing matters to controlling certain averaged local Gowers norms of (suitable normalizations of) the von Mangoldt function. The second is a more recent concatenation theorem of the authors, controlling these averaged local Gowers norms by global Gowers norms. The third ingredient is the work of Green and the authors on linear equations in primes, allowing one to compute these global Gowers norms for the normalized von Mangoldt functions. Finally, we use the Conlon-Fox-Zhao densification approach to the transference principle to combine the preceding three ingredients together. In the special case $P_1(0)=\dots=P_k(0)=0$, our methods also give infinitely many $n,m$ with $n+P_1(m),\dots,n+P_k(m)$ in a specified set primes of positive relative density $δ$, with $m$ bounded by $\log^L n$ for some $L$ independent of the density $δ$. This improves slightly on a result from our previous paper, in which $L$ was allowed to depend on $δ$.

preprint2016arXiv

Sumfree sets in groups: a survey

We discuss several questions concerning sum-free sets in groups, raised by Erdős in his survey "Extremal problems in number theory" (Proceedings of the Symp. Pure Math. VIII AMS) published in 1965. Among other things, we give a characterization for large sets $A$ in an abelian group $G$ which do not contain a subset $B$ of fixed size $k$ such that the sum of any two different elements of $B$ do not belong to $A$ (in other words, $B$ is sum-free with respect to $A$). Erdős, in the above mentioned survey, conjectured that if $|A|$ is sufficiently large compared to $k$, then $A$ contains two elements that add up to zero. This is known to be true for $k \leq 3$. We give counterexamples for all $k \ge 4$. On the other hand, using the new characterization result, we are able to prove a positive result in the case when $|G|$ is not divisible by small primes.

preprint2016arXiv

The logarithmically averaged Chowla and Elliott conjectures for two-point correlations

Let $λ$ denote the Liouville function. The Chowla conjecture, in the two-point correlation case, asserts that $$ \sum_{n \leq x} λ(a_1 n + b_1) λ(a_2 n+b_2) = o(x) $$ as $x \to \infty$, for any fixed natural numbers $a_1,a_2,b_1,b_2$ with $a_1b_2-a_2b_1 \neq 0$. In this paper we establish the logarithmically averaged version $$ \sum_{x/ω(x) < n \leq x} \frac{λ(a_1 n + b_1) λ(a_2 n+b_2)}{n} = o(\log ω(x)) $$ of the Chowla conjecture as $x \to \infty$, where $1 \leq ω(x) \leq x$ is an arbitrary function of $x$ that goes to infinity as $x \to \infty$, thus breaking the "parity barrier" for this problem. Our main tools are the multiplicativity of the Liouville function at small primes, a recent result of Matomäki, Radziwiłł, and the author on the averages of modulated multiplicative functions in short intervals, concentration of measure inequalities, the Hardy-Littlewood circle method combined with a restriction theorem for the primes, and a novel "entropy decrement argument". Most of these ingredients are also available (in principle, at least) for the higher order correlations, with the main missing ingredient being the need to control short sums of multiplicative functions modulated by local nilsequences. Our arguments also extend to more general bounded multiplicative functions than the Liouville function $λ$, leading to a logarithmically averaged version of the Elliott conjecture in the two-point case. In a subsequent paper we will use this version of the Elliott conjecture to affirmatively settle the Erdős discrepancy problem.

preprint2015arXiv

Cancellation for the multilinear Hilbert transform

For any natural number $k$, consider the $k$-linear Hilbert transform $$ H_k( f_1,\dots,f_k )(x) := \operatorname{p.v.} \int_{\bf R} f_1(x+t) \dots f_k(x+kt)\ \frac{dt}{t}$$ for test functions $f_1,\dots,f_k: {\bf R} \to {\bf C}$. It is conjectured that $H_k$ maps $L^{p_1}({\bf R}) \times \dots \times L^{p_k}({\bf R}) \to L^p({\bf R})$ whenever $1 < p_1,\dots,p_k,p < \infty$ and $\frac{1}{p} = \frac{1}{p_1} + \dots + \frac{1}{p_k}$. This is proven for $k=1,2$, but remains open for larger $k$. In this paper, we consider the truncated operators $$ H_{k,r,R}( f_1,\dots,f_k )(x) := \int_{r \leq |t| \leq R} f_1(x+t) \dots f_k(x+kt)\ \frac{dt}{t}$$ for $R > r > 0$. The above conjecture is equivalent to the uniform boundedness of $\| H_{k,r,R} \|_{L^{p_1}({\bf R}) \times \dots \times L^{p_k}({\bf R}) \to L^p({\bf R})}$ in $r,R$, whereas the Minkowski and Hölder inequalities give the trivial upper bound of $2 \log \frac{R}{r}$ for this quantity. By using the arithmetic regularity and counting lemmas of Green and the author, we improve the trivial upper bound on $\| H_{k,r,R} \|_{L^{p_1}({\bf R}) \times \dots \times L^{p_k}({\bf R}) \to L^p({\bf R})}$ slightly to $o( \log \frac{R}{r} )$ in the limit $\frac{R}{r} \to \infty$ for any admissible choice of $k$ and $p_1,\dots,p_k,p$. This establishes some cancellation in the $k$-linear Hilbert transform $H_k$, but not enough to establish its boundedness in $L^p$ spaces.

preprint2015arXiv

Counting the number of solutions to the Erdos-Straus equation on unit fractions

For any positive integer $n$, let $f(n)$ denote the number of solutions to the Diophantine equation $\frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}$ with $x,y,z$ positive integers. The \emph{Erdős-Straus conjecture} asserts that $f(n) > 0$ for every $n \geq 2$. To solve this conjecture, it suffices without loss of generality to consider the case when $n$ is a prime $p$. In this paper we consider the question of bounding the sum $\sum_{p<N} f(p)$ asymptotically as $N \to \infty$, where $p$ ranges over primes. Our main result establishes the asymptotic upper and lower bounds $$ N \log^2 N \ll \sum_{p \leq N} f(p) \ll N \log^2 N \log \log N.$$ In particular, from this bound and the prime number theorem we have $f(p) = O(\log^3 p \log \log p)$ for a subset of primes of density arbitrarily close to 1; thus a typical prime has a relatively small number of solutions to the Erdős-Straus Diophantine equation. We also establish some related results on $f$ and related quantities, for instance establishing the bound $f(p) \ll p^{3/5} + O(\frac{1}{\log\log p})}$ for all primes $p$.

preprint2015arXiv

Failure of the $L^1$ pointwise and maximal ergodic theorems for the free group

Let $F_2$ denote the free group on two generators $a,b$. For any measure-preserving system $(X, {\mathcal X}, μ, (T_g)_{g \in F_2})$ on a finite measure space $X = (X,{\mathcal X},μ)$, any $f \in L^1(X)$, and any $n \geq 1$, define the averaging operators $${\mathcal A}_n f(x) := \frac{1}{4 \times 3^{n-1}} \sum_{g \in F_2: |g| = n} f( T_g^{-1} x ),$$ where $|g|$ denotes the word length of $g$. We give an example of a measure-preserving system $X$ and an $f \in L^1(X)$ such that the sequence ${\mathcal A}_n f(x)$ is unbounded in $n$ for almost every $x$, thus showing that the pointwise and maximal ergodic theorems do not hold in $L^1$ for actions of $F_2$. This is despite the results of Nevo-Stein and Bufetov, who establish pointwise and maximal ergodic theorems in $L^p$ for $p>1$ and for $L \log L$ respectively, as well as an estimate of Naor and the author establishing a weak-type $(1,1)$ maximal inequality for the action on $\ell^1(F_2)$. Our construction is a variant of a counterexample of Ornstein concerning iterates of a Markov operator.

preprint2015arXiv

Finite time blowup for an averaged three-dimensional Navier-Stokes equation

The Navier-Stokes equation on the Euclidean space $\mathbf{R}^3$ can be expressed in the form $\partial_t u = Δu + B(u,u)$, where $B$ is a certain bilinear operator on divergence-free vector fields $u$ obeying the cancellation property $\langle B(u,u), u\rangle=0$ (which is equivalent to the energy identity for the Navier-Stokes equation). In this paper, we consider a modification $\partial_t u = Δu + \tilde B(u,u)$ of this equation, where $\tilde B$ is an averaged version of the bilinear operator $B$ (where the average involves rotations and Fourier multipliers of order zero), and which also obeys the cancellation condition $\langle \tilde B(u,u), u \rangle = 0$ (so that it obeys the usual energy identity). By analysing a system of ODE related to (but more complicated than) a dyadic Navier-Stokes model of Katz and Pavlovic, we construct an example of a smooth solution to such a averaged Navier-Stokes equation which blows up in finite time. This demonstrates that any attempt to positively resolve the Navier-Stokes global regularity problem in three dimensions has to use finer structure on the nonlinear portion $B(u,u)$ of the equation than is provided by harmonic analysis estimates and the energy identity. We also propose a program for adapting these blowup results to the true Navier-Stokes equations.

preprint2015arXiv

Inverse theorems for sets and measures of polynomial growth

We give a structural description of the finite subsets $A$ of an arbitrary group $G$ which obey the polynomial growth condition $|A^n| \leq n^d |A|$ for some bounded $d$ and sufficiently large $n$, showing that such sets are controlled by (a bounded number of translates of) a coset nilprogression in a certain precise sense. This description recovers some previous results of Breuillard-Green-Tao and Breuillard-Tointon concerning sets of polynomial growth; we are also able to describe the subsequent growth of $|A^m|$ fairly explicitly for $m \geq n$, at least when $A$ is a symmetric neighbourhood of the identity. We also obtain an analogous description of symmetric probability measures $μ$ whose $n$-fold convolutions $μ^{*n}$ obey the condition $\| μ^{*n} \|_{\ell^2}^{-2} \leq n^d \|μ\|_{\ell^2}^{-2}$. In the abelian case, this description recovers the inverse Littlewood-Offord theorem of Nguyen-Vu, and gives a variant of a recent nonabelian inverse Littlewood-Offord theorem of Tiep-Vu. Our main tool to establish these results is the inverse theorem of Breuillard, Green, and the author that describes the structure of approximate groups.

preprint2015arXiv

Large gaps between consecutive prime numbers

Let $G(X)$ denote the size of the largest gap between consecutive primes below $X$. Answering a question of Erdos, we show that $$G(X) \geq f(X) \frac{\log X \log \log X \log \log \log \log X}{(\log \log \log X)^2},$$ where $f(X)$ is a function tending to infinity with $X$. Our proof combines existing arguments with a random construction covering a set of primes by arithmetic progressions. As such, we rely on recent work on the existence and distribution of long arithmetic progressions consisting entirely of primes.

preprint2015arXiv

On the quantitative distribution of polynomial nilsequences - erratum

This is an erratum to 'On the quantitative distribution of polynomial nilsequences' [GT]. The proof of Theorem 8.6 of that paper, which claims a distribution result for multiparameter polynomial sequences on nilmanifolds, was incorrect. We provide two fixes for this issue here. First, we deduce the "equal sides" case $N_1 = \dots = N_t = N$ of [GT, Theorem 8.6] from the 1-parameter results in [GT]. This is the same basic mode of argument we attempted in the original paper, though the details are different. The equal sides case is the only one required in applications such as the proof of the inverse conjectures for the Gowers norms due to the authors and Ziegler. Second, we sketch a proof that [GT, Theorem 8.6] does in fact hold in its originally stated form, that is to say without the equal sides condition. To obtain this statement the entire argument of [GT] must be run in the context of multiparameter polynomial sequences $g : \mathbb{Z}^t \rightarrow G$ rather than 1-parameter sequences $g : \mathbb{Z} \rightarrow G$ as is currently done.

preprint2015arXiv

Random matrices: tail bounds for gaps between eigenvalues

Gaps (or spacings) between consecutive eigenvalues are a central topic in random matrix theory. The goal of this paper is to study the tail distribution of these gaps in various random matrix models. We give the first repulsion bound for random matrices with discrete entries and the first super-polynomial bound on the probability that a random graph has simple spectrum, along with several applications.

preprint2015arXiv

Sign patterns of the Liouville and Möbius functions

Let $λ$ and $μ$ denote the Liouville and Möbius functions respectively. Hildebrand showed that all eight possible sign patterns for $(λ(n), λ(n+1), λ(n+2))$ occur infinitely often. By using the recent result of the first two authors on mean values of multiplicative functions in short intervals, we strengthen Hildebrand's result by proving that each of these eight sign patterns occur with positive lower natural density. We also obtain an analogous result for the nine possible sign patterns for $(μ(n), μ(n+1))$. A new feature in the latter argument is the need to demonstrate that a certain random graph is almost surely connected.

preprint2015arXiv

The Elliott-Halberstam conjecture implies the Vinogradov least quadratic nonresidue conjecture

For each prime $p$, let $n(p)$ denote the least quadratic nonresidue modulo $p$. Vinogradov conjectured that $n(p) = O(p^\eps)$ for every fixed $\eps>0$. This conjecture follows from the generalised Riemann hypothesis, and is known to hold for almost all primes $p$ but remains open in general. In this paper we show that Vinogradov's conjecture also follows from the Elliott-Halberstam conjecture on the distribution of primes in arithmetic progressions, thus providing a potential "non-multiplicative" route to the Vinogradov conjecture. We also give a variant of this argument that obtains bounds on short centred character sums from "Type II" estimates of the type introduced recently by Zhang and improved upon by the Polymath project, or from bounds on the level of distribution on variants of the higher order divisor function. In particular, we can obtain an improvement over the Burgess bound would be obtained if one had Type II estimates with level of distribution above $2/3$ (when the conductor is not cube-free) or $3/4$ (if the conductor is cube-free); morally, one would also obtain such a gain if one had distributional estimates on the third or fourth divisor functions $τ_3, τ_4$ at level above $2/3$ or $3/4$ respectively. Some applications to the least primitive root are also given.

preprint2015arXiv

The quantitative behaviour of polynomial orbits on nilmanifolds

A theorem of Leibman asserts that a polynomial orbit $(g(1),g(2),g(3),\ldots)$ on a nilmanifold $G/Γ$ is always equidistributed in a union of closed sub-nilmanifolds of $G/Γ$. In this paper we give a quantitative version of Leibman's result, describing the uniform distribution properties of a finite polynomial orbit $(g(1),\ldots,g(N))$ in a nilmanifold. More specifically we show that there is a factorization $g = εg'γ$, where $ε(n)$ is "smooth", $γ(n)$ is periodic and "rational", and $(g'(a),g'(a+d),\ldots,g'(a + d(l-1)))$ is uniformly distributed (up to a specified error $δ$) inside some subnilmanifold $G'/Γ'$ of $G/Γ$, for all sufficiently dense arithmetic progressions $a,a+d,\ldots,a+d(l-1)$ inside $\{1,..,N\}$. Our bounds are uniform in $N$ and are polynomial in the error tolerance delta. In a subsequent paper we shall use this theorem to establish the Mobius and Nilsequences conjecture from our earlier paper "Linear equations in primes".

preprint2014arXiv

A (concentration-)compact attractor for high-dimensional non-linear Schrödinger equations

We study the asymptotic behavior of large data solutions to Schrödinger equations $i u_t + Δu = F(u)$ in $\R^d$, assuming globally bounded $H^1_x(\R^d)$ norm (i.e. no blowup in the energy space), in high dimensions $d \geq 5$ and with nonlinearity which is energy-subcritical and mass-supercritical. In the spherically symmetric case, we show that as $t \to +\infty$, these solutions split into a radiation term that evolves according to the linear Schrödinger equation, and a remainder which converges in $H^1_x(\R^d)$ to a compact attractor, which consists of the union of spherically symmetric almost periodic orbits of the NLS flow in $H^1_x(\R^d)$. This is despite the total lack of any dissipation in the equation. This statement can be viewed as weak form of the "soliton resolution conjecture". We also obtain a more complicated analogue of this result for the non-spherically-symmetric case. As a corollary we obtain the "petite conjecture" of Soffer in the high dimensional non-critical case.

preprint2014arXiv

Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory

Arithmetic combinatorics is often concerned with the problem of bounding the behaviour of arbitrary finite sets in a group or ring with respect to arithmetic operations such as addition or multiplication. Similarly, combinatorial geometry is often concerned with the problem of bounding the behaviour of arbitrary finite collections of geometric objects such as points, lines, or circles with respect to geometric operations such as incidence or distance. Given the presence of arbitrary finite sets in these problems, the methods used to attack these problems have primarily been combinatorial in nature. In recent years, however, many outstanding problems in these questions have been solved by algebraic means (and more specifically, using tools from algebraic geometry and/or algebraic topology), giving rise to an emerging set of techniques which is now known as the polynomial method. While various instances of the polynomial method have been known for decades (e.g. Stepanov's method, the combinatorial nullstellensatz, or Baker's theorem), the general theory of this method is still in the process of maturing; in particular, the limitations of the polynomial method are not well understood, and there is still considerable scope to apply deeper results from algebraic geometry or algebraic topology to strengthen the method further. In this survey we present several of the known applications of these methods, focusing on the simplest cases to illustrate the techniques. We will assume as little prior knowledge of algebraic geometry as possible.

preprint2014arXiv

Expansion in finite simple groups of Lie type

We show that random Cayley graphs of finite simple (or semisimple) groups of Lie type of fixed rank are expanders. The proofs are based on the Bourgain-Gamburd method and on the main result of our companion paper, establishing strongly dense subgroups in simple algebraic groups.

preprint2014arXiv

Local universality of zeroes of random polynomials

In this paper, we establish some local universality results concerning the correlation functions of the zeroes of random polynomials with independent coefficients. More precisely, consider two random polynomials $f =\sum_{i=1}^n c_i ξ_i z^i$ and $\tilde f =\sum_{i=1}^n c_i \tilde ξ_i z^i$, where the $ξ_i$ and $\tilde ξ_i$ are iid random variables that match moments to second order, the coefficients $c_i$ are deterministic, and the degree parameter $n$ is large. Our results show, under some light conditions on the coefficients $c_i$ and the tails of $ξ_i, \tilde ξ_i$, that the correlation functions of the zeroes of $f$ and $\tilde f$ are approximately the same. As an application, we give some answers to the classical question `"How many zeroes of a random polynomials are real?" for several classes of random polynomial models. Our analysis relies on a general replacement principle, motivated by some recent work in random matrix theory. This principle enables one to compare the correlation functions of two random functions $f$ and $\tilde f$ if their log magnitudes $\log |f|, \log|\tilde f|$ are close in distribution, and if some non-concentration bounds are obeyed.

preprint2014arXiv

Narrow progressions in the primes

In a previous paper of the authors, we showed that for any polynomials $P_1,\dots,P_k \in \Z[\mathbf{m}]$ with $P_1(0)=\dots=P_k(0)$ and any subset $A$ of the primes in $[N] = \{1,\dots,N\}$ of relative density at least $δ>0$, one can find a "polynomial progression" $a+P_1(r),\dots,a+P_k(r)$ in $A$ with $0 < |r| \leq N^{o(1)}$, if $N$ is sufficiently large depending on $k,P_1,\dots,P_k$ and $δ$. In this paper we shorten the size of this progression to $0 < |r| \leq \log^L N$, where $L$ depends on $k,P_1,\dots,P_k$ and $δ$. In the linear case $P_i = (i-1)\mathbf{m}$, we can take $L$ independent of $δ$. The main new ingredient is the use of the densification method of Conlon, Fox, and Zhao to avoid having to directly correlate the enveloping sieve with dual functions of unbounded functions.

preprint2014arXiv

Outliers in the spectrum of iid matrices with bounded rank perturbations

It is known that if one perturbs a large iid random matrix by a bounded rank error, then the majority of the eigenvalues will remain distributed according to the circular law. However, the bounded rank perturbation may also create one or more outlier eigenvalues. We show that if the perturbation is small, then the outlier eigenvalues are created next to the outlier eigenvalues of the bounded rank perturbation; but if the perturbation is large, then many more outliers can be created, and their law is governed by the zeroes of a random Laurent series with Gaussian coefficients. On the other hand, these outliers may be eliminated by enforcing a row sum condition on the final matrix.

preprint2014arXiv

Random matrices have simple spectrum

Let $M_n = (ξ_{ij})_{1 \leq i,j \leq n}$ be a real symmetric random matrix in which the upper-triangular entries $ξ_{ij}, i<j$ and diagonal entries $ξ_{ii}$ are independent. We show that with probability tending to 1, $M_n$ has no repeated eigenvalues. As a corollary, we deduce that the Erd{\H o}s-Renyi random graph has simple spectrum asymptotically almost surely, answering a question of Babai.

preprint2013arXiv

A multi-dimensional Szemerédi theorem for the primes via a correspondence principle

We establish a version of the Furstenberg-Katznelson multi-dimensional Szemerédi in the primes ${\mathcal P} := \{2,3,5,\ldots\}$, which roughly speaking asserts that any dense subset of ${\mathcal P}^d$ contains constellations of any given shape. Our arguments are based on a weighted version of the Furstenberg correspondence principle, relative to a weight which obeys an infinite number of pseudorandomness (or "linear forms") conditions, combined with the main results of a series of papers by Green and the authors which establish such an infinite number of pseudorandomness conditions for a weight associated with the primes. The same result, by a rather different method, has been simultaneously established by Cook, Magyar, and Titichetrakun.

preprint2013arXiv

Bi-parameter paraproducts

In the first part of the paper we prove a bi-parameter version of a well known multilinear theorem of Coifman and Meyer. As a consequence, we generalize the Kato-Ponce inequality in nonlinear PDE, obtaining a fractional Leibnitz rule for derivatives in the $x_1$ and $x_2$ directions simultaneously. Then, we show that the double bilinear Hilbert transform does not satisfy any $L^p$ estimates.

preprint2013arXiv

Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets

Let $P: \F \times \F \to \F$ be a polynomial of bounded degree over a finite field $\F$ of large characteristic. In this paper we establish the following dichotomy: either $P$ is a moderate asymmetric expander in the sense that $|P(A,B)| \gg |\F|$ whenever $A, B \subset \F$ are such that $|A| |B| \geq C |\F|^{2-1/8}$ for a sufficiently large $C$, or else $P$ takes the form $P(x,y) = Q(F(x)+G(y))$ or $P(x,y) = Q(F(x) G(y))$ for some polynomials $Q,F,G$. This is a reasonably satisfactory classification of polynomials of two variables that moderately expand (either symmetrically or asymmetrically). We obtain a similar classification for weak expansion (in which one has $|P(A,A)| \gg |A|^{1/2} |\F|^{1/2}$ whenever $|A| \geq C |\F|^{1-1/16}$), and a partially satisfactory classification for almost strong asymmetric expansion (in which $|P(A,B)| = (1-O(|\F|^{-c})) |\F|$ when $|A|, |B| \geq |\F|^{1-c}$ for some small absolute constant $c>0$). The main new tool used to establish these results is an algebraic regularity lemma that describes the structure of dense graphs generated by definable subsets over finite fields of large characteristic. This lemma strengthens the Szémeredi regularity lemma in the algebraic case, in that while the latter lemma decomposes a graph into a bounded number of components, most of which are $\eps$-regular for some small but fixed $ε$, the latter lemma ensures that all of the components are $O(|\F|^{-1/4})$-regular. This lemma, which may be of independent interest, relies on some basic facts about the étale fundamental group of an algebraic variety.

preprint2013arXiv

Mixing for progressions in non-abelian groups

We study the mixing properties of progressions $(x,xg,xg^2)$, $(x,xg,xg^2,xg^3)$ of length three and four in a model class of finite non-abelian groups, namely the special linear groups $SL_d(F)$ over a finite field $F$, with $d$ bounded. For length three progressions $(x,xg,xg^2)$, we establish a strong mixing property (with error term that decays polynomially in the order $|F|$ of $F$), which among other things counts the number of such progressions in any given dense subset $A$ of $SL_d(F)$, answering a question of Gowers for this class of groups. For length four progressions $(x,xg,xg^2,xg^3)$, we establish a partial result in the $d=2$ case if the shift $g$ is restricted to be diagonalisable over the field, although in this case we do not recover polynomial bounds in the error term. Our methods include the use of the Cauchy-Schwarz inequality, the abelian Fourier transform, the Lang-Weil bound for the number of points in an algebraic variety over a finite field, some algebraic geometry, and (in the case of length four progressions) the multidimensional Szemerédi theorem.

preprint2013arXiv

Multiple recurrence and convergence results associated to $\mathbb{F}_{p}^ω$-actions

Using an ergodic inverse theorem obtained in our previous paper, we obtain limit formulae for multiple ergodic averages associated with the action of $\mathbb{F}_{p}^ω$. From this we deduce multiple Khintchine-type recurrence results analogous to those for $\mathbb{Z}$-systems obtained by Bergelson, Host, and Kra, and also present some new counterexamples in this setting.

preprint2013arXiv

Multiple recurrence in quasirandom groups

We establish a new mixing theorem for quasirandom groups (finite groups with no low-dimensional unitary representations) $G$ which, informally speaking, asserts that if $g, x$ are drawn uniformly at random from $G$, then the quadruple $(g,x,gx,xg)$ behaves like a random tuple in $G^4$, subject to the obvious constraint that $gx$ and $xg$ are conjugate to each other. The proof is non-elementary, proceeding by first using an ultraproduct construction to replace the finitary claim on quasirandom groups with an infinitary analogue concerning a limiting group object that we call an \emph{ultra quasirandom group}, and then using the machinery of idempotent ultrafilters to establish the required mixing property for such groups. Some simpler recurrence theorems (involving tuples such as $(x,gx,xg)$) are also presented, as well as some further discussion of specific examples of ultra quasirandom groups.

preprint2013arXiv

On sets defining few ordinary lines

Let P be a set of n points in the plane, not all on a line. We show that if n is large then there are at least n/2 ordinary lines, that is to say lines passing through exactly two points of P. This confirms, for large n, a conjecture of Dirac and Motzkin. In fact we describe the exact extremisers for this problem, as well as all sets having fewer than n - C ordinary lines for some absolute constant C. We also solve, for large n, the "orchard-planting problem", which asks for the maximum number of lines through exactly 3 points of P. Underlying these results is a structure theorem which states that if P has at most Kn ordinary lines then all but O(K) points of P lie on a cubic curve, if n is sufficiently large depending on K.

preprint2013arXiv

Random matrices: Sharp concentration of eigenvalues

Let $W_n= \frac{1}{\sqrt n} M_n$ be a Wigner matrix whose entries have vanishing third moment, normalized so that the spectrum is concentrated in the interval $[-2,2]$. We prove a concentration bound for $N_I = N_I(W_n)$, the number of eigenvalues of $W_n$ in an interval $I$. Our result shows that $N_I$ decays exponentially with standard deviation at most $O(\log^{O(1)} n)$. This is best possible up to the constant exponent in the logarithmic term. As a corollary, the bulk eigenvalues are localized to an interval of width $O(\log^{O(1)} n/n)$; again, this is optimal up to the exponent. These results strengthen recent results of Erdos, Yau and Yin (under the extra assumption of vanishing third

preprint2013arXiv

Small doubling in groups

Let A be a subset of a group G = (G,.). We will survey the theory of sets A with the property that |A.A| <= K|A|, where A.A = {a_1 a_2 : a_1, a_2 in A}. The case G = (Z,+) is the famous Freiman--Ruzsa theorem.

preprint2013arXiv

The primes contain arbitrarily long polynomial progressions

We establish the existence of infinitely many \emph{polynomial} progressions in the primes; more precisely, given any integer-valued polynomials $P_1, >..., P_k \in \Z[\m]$ in one unknown $\m$ with $P_1(0) = ... = P_k(0) = 0$ and any $\eps > 0$, we show that there are infinitely many integers $x,m$ with $1 \leq m \leq x^\eps$ such that $x+P_1(m), ..., x+P_k(m)$ are simultaneously prime. The arguments are based on those in Green and Tao, which treated the linear case $P_i = (i-1)\m$ and $\eps=1$; the main new features are a localization of the shift parameters (and the attendant Gowers norm objects) to both coarse and fine scales, the use of PET induction to linearize the polynomial averaging, and some elementary estimates for the number of points over finite fields in certain algebraic varieties.

preprint2012arXiv

A central limit theorem for the determinant of a Wigner matrix

We establish a central limit theorem for the log-determinant $\log|\det(M_n)|$ of a Wigner matrix $M_n$, under the assumption of four matching moments with either the GUE or GOE ensemble. More specifically, we show that this log-determinant is asymptotically distributed like $N(\log \sqrt{n!} - 1/2 \log n, 1/2 \log n)_\R$ when one matches moments with GUE, and $N(\log \sqrt{n!} - 1/4 \log n, 1/4 \log n)_\R$ when one matches moments with GOE.

preprint2012arXiv

Every odd number greater than 1 is the sum of at most five primes

We prove that every odd number $N$ greater than 1 can be expressed as the sum of at most five primes, improving the result of Ramaré that every even natural number can be expressed as the sum of at most six primes. We follow the circle method of Hardy-Littlewood and Vinogradov, together with Vaughan's identity; our additional techniques, which may be of interest for other Goldbach-type problems, include the use of smoothed exponential sums and optimisation of the Vaughan identity parameters to save or reduce some logarithmic losses, the use of multiple scales following some ideas of Bourgain, and the use of Montgomery's uncertainty principle and the large sieve to improve the $L^2$ estimates on major arcs. Our argument relies on some previous numerical work, namely the verification of Richstein of the even Goldbach conjecture up to $4 \times 10^{14}$, and the verification of van de Lune and (independently) of Wedeniwski of the Riemann hypothesis up to height $3.29 \times 10^9$.

preprint2012arXiv

Localisation and compactness properties of the Navier-Stokes global regularity problem

In this paper we establish a number of implications between various qualitative and quantitative versions of the global regularity problem for the Navier-Stokes equations, in the periodic, smooth finite energy, smooth $H^1$, Schwartz, or mild $H^1$ categories, and with or without a forcing term. In particular, we show that if one has global well-posedness in $H^1$ for the periodic Navier-Stokes problem with a forcing term, then one can obtain global regularity both for periodic and for Schwartz initial data (thus yielding a positive answer to both official formulations of the problem for the Clay Millennium Prize), and can also obtain global smooth solutions from smooth $H^1$ data, and global almost smooth solutions from smooth finite energy data. Our main new tools are localised energy and enstrophy estimates to the Navier-Stokes equation that are applicable for large data or long times, and which may be of independent interest.

preprint2012arXiv

New bounds for Szemeredi's theorem, Ia: Progressions of length 4 in finite field geometries revisited

Let p > 4 be a prime. We show that the largest subset of F_p^n with no 4-term arithmetic progressions has cardinality << N(log N)^{-c}, where c = 2^{-22} and N := p^n. A result of this type was claimed in a previous paper by the authors and published in Proc. London Math. Society. Unfortunately the proof had a gap, and we issue an erratum for that paper here. Our new argument is different and significantly shorter. In fact we prove a stronger result, which can be viewed as a quantatitive version of some previous results of Bergelson-Host-Kra and the authors.

preprint2012arXiv

Noncommutative sets of small doubling

A corollary of Kneser's theorem, one sees that any finite non-empty subset $A$ of an abelian group $G = (G,+)$ with $|A + A| \leq (2-\eps) |A|$ can be covered by at most $\frac{2}{\eps}-1$ translates of a finite group $H$ of cardinality at most $(2-\eps)|A|$. Using some arguments of Hamidoune, we establish an analogue in the noncommutative setting. Namely, if $A$ is a finite non-empty subset of a nonabelian group $G = (G,\cdot)$ such that $|A \cdot A| \leq (2-\eps) |A|$, then $A$ is either contained in a right-coset of a finite group $H$ of cardinality at most $\frac{2}{\eps}|A|$, or can be covered by at most $\frac{2}{\eps}-1$ right-cosets of a finite group $H$ of cardinality at most $|A|$. We also note some connections with some recent work of Sanders and of Petridis.

preprint2012arXiv

Nonlinear Fourier Analysis

The nonlinear Fourier transform discussed in these notes is the map from the potential of a one dimensional discrete Dirac operator to the transmission and reflection coefficients thereof. Emphasis is on this being a nonlinear variant of the classical Fourier series, and on nonlinear analogues of classical analytic facts about Fourier series. These notes are a summary of a series of lectures given in 2003 at the Park City Mathematics Institute.

preprint2012arXiv

Random covariance matrices: Universality of local statistics of eigenvalues

We study the eigenvalues of the covariance matrix $\frac{1}{n}M^*M$ of a large rectangular matrix $M=M_{n,p}=(ζ_{ij})_{1\leq i\leq p;1\leq j\leq n}$ whose entries are i.i.d. random variables of mean zero, variance one, and having finite $C_0$th moment for some sufficiently large constant $C_0$. The main result of this paper is a Four Moment theorem for i.i.d. covariance matrices (analogous to the Four Moment theorem for Wigner matrices established by the authors in [Acta Math. (2011) Random matrices: Universality of local eigenvalue statistics] (see also [Comm. Math. Phys. 298 (2010) 549--572])). We can use this theorem together with existing results to establish universality of local statistics of eigenvalues under mild conditions. As a byproduct of our arguments, we also extend our previous results on random Hermitian matrices to the case in which the entries have finite $C_0$th moment rather than exponential decay.

preprint2012arXiv

Random matrices: The Universality phenomenon for Wigner ensembles

In this paper, we survey some recent progress on rigorously establishing the universality of various spectral statistics of Wigner Hermitian random matrix ensembles, focusing on the Four Moment Theorem and its refinements and applications, including the universality of the sine kernel and the Central limit theorem of several spectral parameters. We also take the opportunity here to issue some errata for some of our previous papers in this area.

preprint2012arXiv

The asymptotic distribution of a single eigenvalue gap of a Wigner matrix

We show that the distribution of (a suitable rescaling of) a single eigenvalue gap $λ_{i+1}(M_n)-λ_i(M_n)$ of a random Wigner matrix ensemble in the bulk is asymptotically given by the Gaudin-Mehta distribution, if the Wigner ensemble obeys a finite moment condition and matches moments with the GUE ensemble to fourth order. This is new even in the GUE case, as prior results establishing the Gaudin-Mehta law required either an averaging in the eigenvalue index parameter $i$, or fixing the energy level $u$ instead of the eigenvalue index. The extension from the GUE case to the Wigner case is a routine application of the Four Moment Theorem. The main difficulty is to establish the approximate independence of the eigenvalue counting function $N_{(-\infty,x)}(\tilde M_n)$ (where $\tilde M_n$ is a suitably rescaled version of $M_n$) with the event that there is no spectrum in an interval $[x,x+s]$, in the case of a GUE matrix. This will be done through some general considerations regarding determinantal processes given by a projection kernel.

Terence Tao

What is connected

Connect this record

See the researcher in context

Building this map preview

113 published item(s)

A Host--Kra ${\mathbf F}_2^ω$-system of order $5$ that is not Abramov of order $5$, and non-measurability of the inverse theorem for the $U^6({\mathbf F}_2^n)$ norm

Polynomial towers and inverse Gowers theory for bounded-exponent groups

New bounds for Szemeredi's theorem, II: A new bound for $r_4(N)$

Almost all orbits of the Collatz map attain almost bounded values

An averaged form of Chowla's conjecture

An uncountable Mackey-Zimmer theorem

An uncountable Moore-Schmidt theorem

Foundational aspects of uncountable measure theory: Gelfand duality, Riesz representation, canonical models, and canonical disintegration

Perfectly packing a square by squares of nearly harmonic sidelength

Pointwise ergodic theorems for non-conventional bilinear polynomial averages

Sendov's conjecture for sufficiently high degree polynomials

The Hardy--Littlewood--Chowla conjecture in the presence of a Siegel zero

Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra

Singmaster's conjecture in the interior of Pascal's triangle

Correlations of the von Mangoldt and higher divisor functions II. Divisor correlations in short ranges

Exploring the toolkit of Jean Bourgain

Homogenization of iterated singular integrals with applications to random quasiconformal maps

On the universality of potential well dynamics

Quantitative bounds for critically bounded solutions to the Navier-Stokes equations

Sharp bounds for multilinear curved Kakeya, restriction and oscillatory integral estimates away from the endpoint

Sumset and inverse sumset theorems for Shannon entropy

Equivalence of the logarithmically averaged Chowla and Sarnak conjectures

Finite time blowup for high dimensional nonlinear wave systems with bounded smooth nonlinearity

Finite time blowup for Lagrangian modifications of the three-dimensional Euler equation

Polynomial patterns in the primes

Sumfree sets in groups: a survey

The logarithmically averaged Chowla and Elliott conjectures for two-point correlations

Cancellation for the multilinear Hilbert transform

Counting the number of solutions to the Erdos-Straus equation on unit fractions

Failure of the $L^1$ pointwise and maximal ergodic theorems for the free group

Finite time blowup for an averaged three-dimensional Navier-Stokes equation

Inverse theorems for sets and measures of polynomial growth

Large gaps between consecutive prime numbers

On the quantitative distribution of polynomial nilsequences - erratum

Random matrices: tail bounds for gaps between eigenvalues

Sign patterns of the Liouville and Möbius functions

The Elliott-Halberstam conjecture implies the Vinogradov least quadratic nonresidue conjecture

The quantitative behaviour of polynomial orbits on nilmanifolds

A (concentration-)compact attractor for high-dimensional non-linear Schrödinger equations

Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory

Expansion in finite simple groups of Lie type

Local universality of zeroes of random polynomials

Narrow progressions in the primes

Outliers in the spectrum of iid matrices with bounded rank perturbations

Random matrices have simple spectrum

A multi-dimensional Szemerédi theorem for the primes via a correspondence principle

Bi-parameter paraproducts

Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets

Mixing for progressions in non-abelian groups

Multiple recurrence and convergence results associated to $\mathbb{F}_{p}^ω$-actions

Multiple recurrence in quasirandom groups

On sets defining few ordinary lines

Random matrices: Sharp concentration of eigenvalues

Small doubling in groups

The primes contain arbitrarily long polynomial progressions

A central limit theorem for the determinant of a Wigner matrix

Every odd number greater than 1 is the sum of at most five primes

Localisation and compactness properties of the Navier-Stokes global regularity problem

New bounds for Szemeredi's theorem, Ia: Progressions of length 4 in finite field geometries revisited

Noncommutative sets of small doubling

Nonlinear Fourier Analysis

Random covariance matrices: Universality of local statistics of eigenvalues

Random matrices: The Universality phenomenon for Wigner ensembles

The asymptotic distribution of a single eigenvalue gap of a Wigner matrix

A nilpotent Freiman dimension lemma

A note on approximate subgroups of GL_n(C) and uniformly nonamenable groups

An inverse theorem for the Gowers U^{s+1}[N]-norm (announcement)

Asymptotic decay for a one-dimensional nonlinear wave equation

Effective limiting absorption principles, and applications

Large values of the Gowers-Host-Kra seminorms

Product set estimates for non-commutative groups

Random matrices: Localization of the eigenvalues and the necessity of four moments

Random matrices: The Four Moment Theorem for Wigner ensembles

Random matrices: Universal properties of eigenvectors