Publications
'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 entropyincrement arguments can replace or even outperform more traditional energyincrement strategies or alternative approximation arguments based on the HahnBanach theorem. 
Status: 
Submitted. 
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 2colouring 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 2colouring 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 2colourings 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 graphtheoretic problem.

Status: 
Quarterly Journal of Mathematics, first published online 9th May, 2016. 
Links: 
journal  pdf  mathscinet 
'Finite field models in arithmetic combinatoricsten 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 highdimensional 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, 233274, 2015. 
Links: 
journal  pdf  mathscinet 
'Samplingbased proofs of almostperiodicity results and applications' with E. BenSasson, N. RonZewi and M. Tulsiani
Abstract: 
We give new combinatorial proofs of known almostperiodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask, whose almostperiodicity lemma has had farreaching implications in additive combinatorics. We provide an alternative (and L^pnorm free) point of view, which allows for proofs to easily be converted to probabilistic algorithms that decide membership in almostperiodic sumsets of dense subsets of F_2^n.
As an application, we give a new algorithmic version of the quasipolynomial BogolyubovRuzsa lemma recently proved by Sanders. Together with the results by the last two authors, this implies an algorithmic version of the quadratic GoldreichLevin 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 normfree) 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, 955966, 2014. 
Links: 
journal  ECCC  mathscinet 
'Polynomial configurations in the primes' with Th. H. Lê
Abstract: 
The BergelsonLeibman 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 BergelsonLeibman 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 TaoZiegler theorem can be restricted to the set of primes minus 1.

Status: 
Int. Math. Res. Not., first published online August 2013. 
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: 389427, 2013. 
Links: 
journal  pdf  mathscinet 
'Quadratic GoldreichLevin 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 GoldreichLevin 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'', higherdegree 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 selfcorrection procedure for ReedMuller codes of order 2
(over F_2^n) for a function at distance 1/2epsilon from a codeword. Given a function f: F_2^n to {1,1} at fractional Hamming distance 1/2epsilon from a quadratic phase (which is a codeword of ReedMuller
code of order 2), we give an algorithm that runs in time polynomial in n and finds a
codeword at distance at most 1/2eta 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 listdecoding 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), 619628, 2011.
Long version in SIAM J. Comput., Vol. 43, No. 2, 730766, 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 nontrivial case of the main conjecture
from [GW07].

Status: 
J. Anal. Math. 115: 121186, 2011. 
Links: 
journal  arXiv  mathscinet 
'Linear forms and higherdegree uniformity for functions on F_p^n' with W.T. Gowers
Abstract: 
In [GW09a] we conjectured that uniformity of degree k1 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): 3669, 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 HahnBanach 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): 215237, 2012. 
Links: 
journal  arXiv  mathscinet 
'Subsets of F_q^n containing no kterm 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(k1)}+q^{k1}1 which contains no k points on a line, and hence no kterm 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): 13981403, 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 3term 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 4term progressions'
Abstract: 
We improve the lower bound given by Cameron, Cilleruelo and Serra [CSS05] for the minimum number of monochromatic 4term progressions contained in any 2colouring of Z_p with p a prime. We also exhibit a colouring with significantly fewer than the random number of monochromatic 4term 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 2colouring of K_n by Giraud [Gir79], and briefly discuss the analogy between the upperbound graph constructions of Thomason [Tho89] and ours for subsets of Z_p.

Status: 
J. Comb. 1(1): 5368, 2010. 
Links: 
journal  pdf  mathscinet 
'The true complexity of a system of linear equations' with W.T. Gowers
Abstract: 
It is wellknown 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 socalled 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: 155176, 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 socalled 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 multidimensional torus and Esseen's Inequality.

Status: 
Israel J. Math., 179(1): 253278, 2010. 
Links: 
journal  pdf  mathscinet  note by T. Sanders at arXiv:0807.5106 
Theses
'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 sousensembles 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é ParisSud (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 stateoftheart technique due to Pintz, Steiger and Szemeréedi which yields the best known upper bound on the density of sets whose difference set is squarefree. Inspired by the wellknown 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 socalled ``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 4term progressions in any twocolouring 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 wellknown 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 socalled '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 
