Papers and Preprints

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.

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].

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.

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].

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.

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].

of 3-term progressions are constructed.

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.

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.

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.

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.