'Stable arithmetic regularity lemma in the finite-field model' with C. Terry

Abstract: The arithmetic regularity lemma for F_p^n, proved by Green in 2005, states
that given a subset A of F_p^n, there exists a subspace H in F_p^n of bounded codimension such that A is Fourier-uniform with respect to almost all cosets of H. It is known that in general, the growth of the codimension of H is required to be of tower type depending on the degree of uniformity, and that one must allow for a small number of non-uniform cosets.
Our main result is that, under a natural model-theoretic assumption of stability, the tower-type bound and non-uniform cosets in the arithmetic regularity lemma are not necessary. Specifically, we prove an arithmetic regularity lemma for k-stable subsets A of F_p^n in which the bound on the codimension of the subspace is a polynomial (depending on k) in the degree of uniformity, and in which there are no non-uniform cosets. This result is an arithmetic analogue of the stable graph regularity lemma proved by Malliaris and Shelah.
Status: Preprint.
Links: journal  | arXiv | mathscinet

'Szemerédi's theorem in the primes' with L. Rimanic

Abstract: Green and Tao famously proved in 2005 that any subset of the primes of
fixed positive density contains arbitrarily long arithmetic progressions. Green had previously shown that in fact any subset of the primes of relative density tending to zero sufficiently slowly contains a 3-term term progression. This was followed by work of Helfgott and de Roton, and Naslund, who improved the bounds on the relative density in the case of 3-term progressions. The aim of this note is to present an analogous result for longer progressions by combining a quantified version of the relative Szemerédi theorem given by Conlon, Fox and Zhao with Henriot's estimates of the enveloping sieve weights.
Status: Submitted.
Links: journal  | arXiv | mathscinet

'Some applications of relative entropy in additive combinatorics'

Abstract: This survey looks at some recent applications of relative entropy in additive
combinatorics. Specifically, we examine to what extent entropy-increment arguments can replace or even outperform more traditional energy-increment strategies or alternative approximation arguments based on the Hahn-Banach theorem.
Status: Surveys in Combinatorics 2017, London Mathematical Society Lecture Note Series, 409--442, CUP.
Links: journal  | pdf | mathscinet

'Ramsey multiplicity of linear patterns in certain finite abelian groups' with A. Saad

Abstract: It is well known (and a result of Goodman) that a random 2-colouring of the
edges of a large complete graph K_n contains asymptotically (in n ) the minimum number of monochromatic triangles (K_3s). Erdős conjectured that a random 2-colouring also minimises the number of monochromatic K_4s, but his conjecture was disproved by Thomason in 1989. The question of determining for which small graphs Goodman's result holds true remains wide open.
In this article we explore an arithmetic analogue: what can be said about the number of monochromatic additive configurations in 2-colourings of finite abelian groups? While we are able to answer several instances of this question using techniques from additive combinatorics and quadratic Fourier analysis, the main purpose of this paper is to advertise this sphere of problems and to put forward a number of concrete conjectures. We also note that, perhaps surprisingly, some of our results in the arithmetic setting have implications for the original graph-theoretic problem.
Status: Quarterly Journal of Mathematics, 68 (1): 125--140, 2017.
Links: journal  | pdf | mathscinet

'Finite field models in arithmetic combinatorics--ten years on'

Abstract: It has been close to ten years since the publication of Green's influential
survey 'Finite field models in additive combinatorics', in which the author championed the use of high-dimensional vector spaces over finite fields as a toy model for tackling additive problems concerning the integers. The path laid out by Green has proven to be a very successful one to follow. In the present article we survey the highlights of the past decade and outline the challenges for the years to come.
Status: Finite Fields and Their Applications, Vol. 32, 233--274, 2015.
Links: journal  | pdf | mathscinet

'Sampling-based proofs of almost-periodicity results and applications' with E. Ben-Sasson, N. Ron-Zewi and M. Tulsiani

Abstract: We give new combinatorial proofs of known almost-periodicity results for
sumsets of sets with small doubling in the spirit of Croot and Sisask, whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and L^p-norm free) point of view, which allows for proofs to easily be converted to probabilistic algorithms that decide membership in almost-periodic sumsets of dense subsets of F_2^n.
As an application, we give a new algorithmic version of the quasipolynomial Bogolyubov-Ruzsa lemma recently proved by Sanders. Together with the results by the last two authors, this implies an algorithmic version of the quadratic Goldreich-Levin theorem in which the number of terms in the quadratic Fourier decomposition of a given function is quasipolynomial in the error parameter, compared with an exponential dependence previously proved by the authors. It also improves the running time of the algorithm to have quasipolynomial dependence instead of an exponential one.
We also give an application to the problem of finding large subspaces in sumsets of dense sets. Green showed that the sumset of a dense subset of F_2^n contains a large subspace. Using Fourier analytic methods, Sanders proved that such a subspace must have dimension bounded below by a constant times the density time n. We provide an alternative (and L^p norm-free) proof of a comparable bound, which is analogous to a recent result of Croot, Laba and Sisask in the integers.
Status: Proceedings of 41st International Colloquium on Automata, Languages and Programming (ICALP), Part I, 955--966, 2014.
Links: journal  | ECCC |  mathscinet

'Polynomial configurations in the primes' with Th. H. Lê

Abstract: The Bergelson-Leibman theorem states that if P_1, . . ., P_k are in Z[x], then
any subset of the integers of positive upper density contains a polynomial configuration x+P_1(m), . . ., x+P_k(m), where x,m are integers. Various generalizations of this theorem are known. Wooley and Ziegler showed that the variable m can in fact be taken to be a prime minus 1, and Tao and Ziegler showed that the Bergelson-Leibman theorem holds for subsets of the primes of positive relative upper. Here we prove a hybrid of the latter two results, namely that the step m in the Tao-Ziegler theorem can be restricted to the set of primes minus 1.
Status: Int. Math. Res. Not. (23): 6448-6473, 2014.
Links: journal  | arXiv | mathscinet

'Arithmetic and polynomial progressions in the primes, d'après Gowers, Green, Tao and Ziegler'

Abstract: In a celebrated theorem from 2004, Green and Tao showed that there exist
arbitrarily long arithmetic progressions in the primes. A few years later Tao and Ziegler extended this result to establish the existence of arbitrary polynomial progressions in the primes: given polynomials
P_1, . . . , P_k in Z[m] such that P_1(0)= . . . =P_k(0)=0, there exist infinitely many integers x,m such that x+P_1(m), . . . , x+P_k(m) are simultaneously prime.
In this talk we outline the general strategy of proof that allows one to make structural statements about dense subsets of the integers and the primes, and detail the specific ingredients that are necessary to deal with polynomial configurations.
Status: Séminaire Bourbaki, 64ème année, Exposé no.1054, Astérisque No. 352: 389--427, 2013.
Links: journal  | pdf | mathscinet

'Quadratic Goldreich-Levin theorems' with M. Tulsiani

Abstract: Decomposition theorems in classical Fourier analysis enable us to express a
bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases.
The Goldreich-Levin algorithm can be viewed as an algorithmic analogue of such a decomposition as it gives a way to efficiently find the linear phases associated with large Fourier coefficients.
In the study of "quadratic Fourier analysis'', higher-degree analogues of such decompositions have been developed in which the pseudorandomness property is stronger but the structured part correspondingly weaker. For example, it has previously been shown that it is possible to express a bounded function as a sum of a few quadratic phases plus a part that is small in the U^3 norm, defined by Gowers for the purpose of counting arithmetic progressions of length 4. We give a polynomial time algorithm for computing such a decomposition.
A key part of the algorithm is a local self-correction procedure for Reed-Muller codes of order 2 (over F_2^n) for a function at distance 1/2-epsilon from a codeword. Given a function f: F_2^n to {-1,1} at fractional Hamming distance 1/2-epsilon from a quadratic phase (which is a codeword of Reed-Muller code of order 2), we give an algorithm that runs in time polynomial in n and finds a codeword at distance at most 1/2-eta for eta = eta(epsilon).
This is an algorithmic analogue of Samorodnitsky's result, which gave a tester for the above problem. To our knowledge, it represents the first instance of a correction procedure for any class of codes, beyond the list-decoding radius.
In the process, we give algorithmic versions of results from additive combinatorics used in Samorodnitsky's proof and a refined version of the inverse theorem for the Gowers U^3 norm over F_2^n.
Status: Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), 619--628, 2011.
Long version in SIAM J. Comput., Vol. 43, No. 2, 730--766, 2014.
Links: proceedings |  journal  | arXiv | mathscinet

'Linear forms and quadratic uniformity for functions on Z_N' with W.T. Gowers

Abstract: A very useful fact in additive combinatorics is that analytic expressions that
can be used to count the number of structures of various kinds in subsets of Abelian groups are robust under quasirandom perturbations, and moreover that quasirandomness can often be measured by means of certain easily described norms, known as uniformity norms. However, determining which uniformity norms work for which structures turns out to be a surprisingly hard question. In [GW09a] and [GW09b, GW09c] we gave a complete answer to this question for groups of the form G=F_p^n, provided p is not too small. In Z_N, substantial extra difficulties arise, of which the most important is that an "inverse theorem'' even for the uniformity norm ||.||_{U^3} requires a more sophisticated (local) formulation. When N is prime, Z_N is not rich in subgroups, so one must use regular Bohr neighbourhoods instead. In this paper, we prove the first non-trivial case of the main conjecture from [GW07].
Status: J. Anal. Math. 115: 121--186, 2011.
Links: journal  | arXiv | mathscinet

'Linear forms and higher-degree uniformity for functions on F_p^n' with W.T. Gowers

Abstract: In [GW09a] we conjectured that uniformity of degree k-1 is sufficient to
control an average over a family of linear forms if and only if the kth powers of these linear forms are linearly independent. In this paper we prove this conjecture in F_p^n, provided only that p is sufficiently large. This result represents one of the first applications of the recent inverse theorem for the U^k norm over F_p^n by Bergelson, Tao and Ziegler [BTZ09,TZ08]. We combine this result with some abstract arguments in order to prove that a bounded function can be expressed as a sum of polynomial phases and a part that is small in the appropriate uniformity norm. The precise form of this decomposition theorem is critical to our proof, and the theorem itself may be of independent interest.
Status: Geom. Funct. Anal. 21 (1): 36--69, 2011.
Links: journal  | arXiv | mathscinet

'Linear forms and quadratic uniformity for functions on F_p^n' with W.T. Gowers

Abstract: We give improved bounds for our theorem in [GW09], which shows that a
system of linear forms on F_p^n with squares that are linearly independent has the expected number of solutions in any linearly uniform subset of F_p^n. While in [GW09] the dependence between the uniformity of the set and the resulting error in the average over the linear system was of tower type, we now obtain a doubly exponential relation between the two parameters. Instead of the structure theorem for bounded functions due to Green and Tao [GrT08], we use the Hahn-Banach theorem to decompose the function into a quadratically structured plus a quadratically uniform part. This new decomposition makes more efficient use of the U^3 inverse theorem [GrT08].
Status: Mathematika 57 (2): 215--237, 2012.
Links: journal  | arXiv | mathscinet

'Subsets of F_q^n containing no k-term progressions' with Y. Lin

Abstract: In this note we prove that for any fixed integer k and any prime power q>k,
there exists a subset of F_q^{2k} of size q^{2(k-1)}+q^{k-1}-1 which contains no k points on a line, and hence no k-term arithmetic progressions. As a corollary we obtain an asymptotic lower bound as n tends to infinity for r_k(F_q^n) when q>k, which can be interpreted as the finite field analogue of Behrend's construction for longer progressions [Ra62], [LL01].
Status: European J. Combin., 31(5): 1398--1403, 2010.
Links: journal | pdf | mathscinet

'A note on Elkin's improvement of Behrend's construction' with B.J. Green

Abstract: We provide a short proof of a recent result of Elkin [E08] in which large
subsets of {1, 2, ..., N} free of 3-term progressions are constructed.
Status: Additive Number Theory: Festschrift In Honor Of The Sixtieth Birthday Of Melvyn B. Nathanson, Springer, 2010.
Links: journal | arXiv | mathscinet

'The minimal number of monochromatic 4-term progressions'

Abstract: We improve the lower bound given by Cameron, Cilleruelo and Serra
[CSS05] for the minimum number of monochromatic 4-term progressions contained in any 2-colouring of Z_p with p a prime. We also exhibit a colouring with significantly fewer than the random number of monochromatic 4-term progressions, which is based on an a recent example in additive combinatorics by Gowers [Gow07]. In the second half of this paper, we discuss the corresponding problem in graphs, which has received a great deal more attention to date. We give a simplified proof of the best known lower bound on the minimum number of monochromatic K_4s contained in any 2-colouring of K_n by Giraud [Gir79], and briefly discuss the analogy between the upper-bound graph constructions of Thomason [Tho89] and ours for subsets of Z_p.
Status: J. Comb. 1(1): 53--68, 2010.
Links: journal | pdf | mathscinet

'The true complexity of a system of linear equations' with W.T. Gowers

Abstract: It is well-known that if a subset A of a finite Abelian group G satisfies a
quasirandomness property called uniformity of degree k, then it contains roughly the expected number of arithmetic progressions of length k+2, that is, the number of progressions one would expect in a random subset of G of the same density as A. One is naturally led to ask which degree of uniformity is required of A in order to control the number of solutions to a general system of linear equations. Using so-called quadratic Fourier analysis, we show that certain linear systems that were previously thought to require quadratic uniformity are in fact governed by linear uniformity. More generally, we conjecture a necessary and sufficient condition on a linear system L which guarantees that any subset A of F_p^n which is uniform of degree k contains the expected number of solutions to L.
Status: Proc. London Math. Soc. (3), 100: 155--176, 2010.
Links: journal | arXiv | mathscinet

'The structure of popular difference sets'

Abstract: We show that the set of popular differences of a large subset of Z_N does
not always contain the complete difference set of another large set. For this purpose we construct a so-called niveau set, which was first introduced by Ruzsa in [Ru87] and later used in [Ru91] to show that there exists a large subset of Z_N whose sumset does not contain any long arithmetic progressions. In this paper we make substantial use of measure concentration results on the multi-dimensional torus and Esseen's Inequality.
Status: Israel J. Math., 179(1): 253--278, 2010.
Links: journal | pdf | mathscinet | note by T. Sanders at arXiv:0807.5106


'L'analyse harmonique d'ordre supérieur, et applications'

Abstract: Mes travaux se situent dans le domaine de la combinatoire arithmétique, à
l'interface entre la théorie des nombres analytique, l'analyse harmonique et la combinatoire. En particulier, je travaille sur des questions fondamentales concernant ce qu'on appelle l'analyse harmonique d'ordre supérieur, dont les applications les plus célèbres sont le théorème de Szemerédi et le théorème de Green et Tao sur les progressions arithmétiques dans l'ensemble des nombres premiers. Je m'intéresse aussi aux interactions avec la théorie ergodique ainsi qu'aux nombreuses applications en informatique théorique.
Mes contributions et ambitions dans ce domaine sont les suivantes :
- le développement des notions fondamentales et d'outils fortement quantitatifs en analyse harmonique discrète, quadratique et d'ordre supérieur;
- les applications aux questions concernant les structures additives et polynomiales dans des sous-ensembles d'entiers et dans l'ensemble des nombres premiers;
- l'analyse combinatoire des ensembles qui ne contiennent pas de telles structures;
- le renforcement des liens entre la combinatoire arithmétique et la théorie ergodique, la théorie des graphes et l'informatique théorique.
Status: Mémoire de habilitation, Université Paris-Sud (Orsay), novembre 2012.
Links: pdf

'Arithmetic structures in sets of integers', under the supervision of W.T. Gowers.

Abstract: This dissertation deals with four problems concerning arithmetic structures
in dense sets of integers. In Chapter 1 we give an exposition of the state-of-the-art technique due to Pintz, Steiger and Szemeréedi which yields the best known upper bound on the density of sets whose difference set is square-free. Inspired by the well-known fact that Fourier analysis is not sufficient to detect progressions of length 4 or more, we determine in Chapter 2 a necessary and sufficient condition on a system of linear equations which guarantees the correct number of solutions in any uniform subset of F_p^n. This joint work with Tim Gowers constitutes the core of this thesis and relies heavily on recent progress in so-called ``quadratic Fourier analysis" pioneered by Gowers, Green and Tao. In particular, we use a structure theorem for bounded functions which provides a decomposition into a quadratically structured and a quadratically uniform part. We also present an alternative decomposition leading to improved bounds for the main result, and discuss the connections with recent results in ergodic theory. Chapter 3 deals with improved upper and lower bounds on the minimum number of monochromatic 4-term progressions in any two-colouring of Z_N. Finally, in Chapter 4 we investigate the structure of the set of popular differences of a subset of Z_N. More precisely, we establish that, given a subset of size linear in N, the set of its popular differences does not always contain the complete difference set of another large set.
Status: Ph.D. thesis, University of Cambridge, submitted December 2007.
Links: pdf

'Arithmetic structures in difference sets', under the supervision of B.J. Green.

Abstract: A well-known theorem of Sarközy states that provided a subset of the set
{1,...,N} is dense enough, it contains two elements whose difference is a perfect square. Recently an elegant proof (involving elementary Fourier analysis) was given by Green, and it is on this result that most of the essay is based. In fact, we give a new combinatorial proof of an (already established) extension of Sarközy's result to cover the case where 'perfect square' is replaced by any quadratic polynomial with an integer root. We make heavy use of the so-called 'circle method' developed by Hardy and Littlewood, which we describe in some detail. As an application we also discuss the asymptotic solution to Waring's problem. The opening chapter includes a survey of some classical results on exponential sums such as Weyl's inequality and Hua's lemma.
Status: Part III essay, University of Cambridge, submitted May 2003.
Links: pdf

This page was last updated 5th October 2017.