Papers and Preprints

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

F_2^n. Following closely the original argument of Samorodnitsky [S07] and adding some ingredients from Green and Tao [GT08], we prove that if a function f: F_2^n -> [-1,1] has U^3 norm at least delta, then there exists a subspace V of codimension polynomial in delta^{-1} such that, on average, f correlates polynomially with the same quadratic phase on every translate of V. For vector spaces over finite fields with characteristic strictly greater than 2, this result was established in [GT08] and exploited in the forthcoming paper [GW09].

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.

and Gowers and the author [GW07]. Both papers independently describe two manifestations of the same phenomenon, the former in the context of ergodic theory and the latter in arithmetic combinatorics. In their respective settings, they address the question after the degree of the minimal characteristic factor of a multiple ergodic average along a system of linear forms, or the minimal degree of uniformity needed to accurately count solutions to the corresponding system of linear equations. The present article is aimed at readers with a combinatorics background and limited prior exposure to ergodic theory.

to [Ru84], and was recently rediscovered and improved by Beigel and Gasarch [Bei08]. The main purpose of this short note is to show that Ruzsa's construction achieves its limit in the function field setting, thereby complementing a recent upper bound on the size of a square-difference free set in this context by [LeThai08] In the final section we investigate related coloring problems in both the integers and the cyclic group modulo p.

whose difference set contains no squares which was first derived by Pintz, Steiger and Szemerédi in [PSS88]. We show how this method can be brought in line with the modern view of the energy increment strategy employed in problems such as Szemerédi's Theorem on arithmetic progressions, and explore the extent to which the particularities of the method are specific to the set of squares.

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.