• No results found

in order to satisfy both conditions in (1.7). We can then check that the remaining conditions are satisfied. It was necessary to have

αX1−1/3, α Xm

pK/L and α Xm

K1/3 6/5

to ensure that we could neglect the contributions from the fairly major and the minor arcs, and m ≤ Q/X14m to force the intervals I(a/q, m/Q) to be disjoint. We have made no attempts to optimize the constants involved here.

1.6 Remarks

The method which we have discussed was extended to cover the case ofkth powers in [BPPS94]. Only minor modifications to the argument are necessary, and these occur almost exclusively through the Hardy-Littlewood type estimates in the appendix.

It should also be clear that similar progress can be made for polynomial differences such asx2−1. Very recently, Lucier [Luc07] applied the method to the shifted primes to obtain a bound of

(log3N)4 log logN

log5N

on the density of the set which avoids the set of all p = 1, p a prime. However, it should be noted that the currently best-known bound for this problem obtained in [RS07] is of the form

exp(−cp4 logN)

and does not use this technique. Indeed, at least assuming GRH it is relatively straightforward to obtain a density increment of size a constant times α in the case of primes, which cannot be improved by the technique described in this chapter. (For comparison, the straightforward density increase in the case of squares is of size α2, and can be improved to α using combinatorics of rationals.)

Given the fact that the application to the primes is slightly bogus, it would be very interesting to find a genuinely new and useful application of this method.

Acknowledgements. The author would like to thank Endre Szemer´edi for helpful comments and discussions.

Chapter 2

The True Complexity of a Linear System

2.1 Introduction

This chapter includes joint work with Tim Gowers. Section 2.3 has been submitted as [GW07b]. Section 4.1 is a precursor to the forthcoming paper [GW07a].

In this chapter we look for conditions that are sufficient to guarantee that a subsetA of a finite Abelian groupGcontains the “expected” number of linear configurations of a given type. The simplest non-trivial result of this kind is the well-known fact that if G has odd order, A has density α and all Fourier coefficients of the characteristic function of A are significantly smaller than α (except the one at zero, which equals α), thenAcontains approximatelyα3|G|2 triples of the form (a, a+d, a+ 2d). This is

“expected” in the sense that a random set A of density α has approximately α3|G|2 such triples with very high probability.

More generally, it was shown in [Gow01] (in the case G= ZN for N prime, but the proof generalizes) that a setA of density αhas about αk|G|2 arithmetic progressions of length k if the characteristic function ofA is almost as small as it can be, given its density, in a norm that is now called the Uk−1-norm. Green and Tao [GT06a] have found the most general statement that follows from the technique used to prove this result, introducing a notion that they call thecomplexity of a system of linear forms.

They prove that ifAhas almost minimalUk+1-norm then it has the expected number of linear configurations of a given type, provided that the associated complexity is at most k. The main result of this chapter is that the converse is not true: in particular there are certain systems of complexity 2 that are controlled by theU2-norm, whereas the result of Green and Tao requires the stronger hypothesis of U3-control.

2.1 Introduction

We say that a system ofm linear formsL1, . . . , Lm indvariables hastrue complexity k if k is the smallest positive integer such that, for any setAof density αand almost minimal Uk+1-norm, the number of d-tuples (x1, . . . , xd) such thatLi(x1, . . . , xd)∈A for every i is approximately αm|G|d. We conjecture that the true complexity k is the smallest positive integer s for which the functions Ls+11 , . . . , Ls+1m are linearly independent.

Using the “quadratic Fourier analysis” of Green and Tao we prove this conjecture in Section 2.3 in the case where the complexity of the system (in Green and Tao’s sense) is 2, s = 1 and G is the group Fnp for some fixed odd prime p. Section 4.1 is devoted to obtaining improved bounds for this problem. Finally, a closely related result in ergodic theory was recently proved independently by Leibman [Lei07]. We discuss the connections between his result and ours in Section 2.5.

Let us now turn to a more detailed description of the problem. SupposeAis a subset of a finite Abelian group G and let α =|A|/|G| be the density of A. We say that A isuniform if it has one of several equivalent properties, each of which says in its own way thatA“behaves like a random set”. For example, writingAfor the characteristic function of the set A, we can define the convolution A∗A by the formula

A∗A(x) = Ey+z=xA(y)A(z),

where the expectation is with respect to the uniform distribution over all pairs (y, z)∈ G2 such that y+z =x; one of the properties in question is that the variance ofA∗A should be small. As we have already remarked above, if this is the case and G has odd order, then it is easy to show thatAcontains approximatelyα3|G|2 triples of the form (x, x+d, x+ 2d). Indeed, these triples are the solutions (x, y, z) of the equation x+z = 2y, and

Ex+z=2yA(x)A(y)A(z) =EyA∗A(2y)A(y).

The mean of the function A∗A isα2, so if the variance is sufficiently small, then the right-hand side is approximatelyα2EyA(y) =α3. This is a probabilistic way of saying that the number of solutions of x+z = 2y inside A is approximately α3|G|2, which is what we would expect if A was a random set with elements chosen independently with probability α.

An easy generalization of the above argument shows that, given any linear equation in Gof the form

c1x1+c2x2+· · ·+cmxm = 0,

for suitable fixed coefficients c1, c2, ..., cm, the number of solutions in A is

approxi-2.1 Introduction

mately αm|G|m−1. Roughly speaking, you can choose x3, . . . , xm in A however you like, and if A is sufficiently uniform then the number of ways of choosing x1 and x2

to lie in A and satisfy the equation will almost always be roughly α2|G|. By “suit-able” we mean that there are certain divisibility problems that must be avoided. For example, if Gis the group Fn2,x+z = 2yand xbelongs toA, thenz belongs toA for the trivial reason that it equals x. Throughout this chapter we shall consider groups of the formFnp for some primep and assume thatpis large enough for such problems not to arise.

When k ≥ 4, uniformity of a set A does not guarantee that A contains approxi-mately αk|G|2 arithmetic progressions of length k. For instance, there are examples of uniform subsets of ZN that contain significantly more, or even significantly fewer than, the expected number of four-term progressions [Gow06b]. It was established in [Gow98] that the appropriate measure for dealing with progressions of length 4 is a property known as quadratic uniformity: sets which are sufficiently quadratically uniform contain roughly the correct number of four-term progressions. We shall give precise definitions of higher-degree uniformity in the next section, but for now let us simply state the result, proved in [Gow01] in the caseG=ZN, that ifA is uniform of degreek−2, thenAcontains approximatelyαk|G|2 arithmetic progressions of length k. Moreover, if A is uniform of degree j for some j < k−2, then it does not follow that A must contain approximately αk|G|2 arithmetic progressions of length k.

The discrepancy betweenk and k−2 seems slightly unnatural until one reformulates the statement in terms of solutions of equations. We can define an arithmetic pro-gression of length k either as a k-tuple of the form (x, x+d, . . . , x+ (k−1)d) or as a solution (x1, x2, . . . , xk) to the system of k −2 equations xi −2xi+1 +xi+2 = 0, i= 1,2, . . . , k−2. In all the examples we have so far discussed, we need uniformity of degree precisely k in order to guarantee approximately the expected number of solutions of a system of k equations. It is tempting to ask whether this is true in general.

However, a moment’s reflection shows that it is not. For example, the system of equations x1 −2x2 +x3 = 0, x4 −2x5 +x6 = 0 has about α6|G|4 solutions in a uniform set, since the two equations are completely independent. This shows that a sensible conjecture must take account of how the equations interact with each other.

A more interesting example is the system that consists of the m3

equationsxij+xjk = xik in the m2

unknownsxij, 1≤i < j ≤m. These equations are not all independent, but one can of course choose an independent subsystem of them. It is not hard to see that there is a bijection between solutions of this system of equations where every

2.1 Introduction

xij belongs to A and m-tuples (x1, . . . , xm) such that xj −xi ∈ A whenever i < j. Now one can form a bipartite graph with two vertex sets equal to G by joining x to y if and only if y −x ∈ A. It is well-known that if A is uniform, then this bipartite graph is quasirandom. The statement that every xj−xi belongs to A can be reformulated to say that (x1, . . . , xm) form a clique in an m-partite graph that is built out of quasirandom pieces derived from A. A “counting lemma” from the theory of quasirandom graphs then implies easily that the number of such cliques is approximately α(m2)|G|m. So uniformity of degree 1 is sufficient to guarantee that there are about the expected number of solutions to this fairly complicated system of equations.

In their recent work on configurations in the primes, Green and Tao [GT06a] analysed the arguments used to prove the above results, which are fairly simple and based on repeated use of the Cauchy-Schwarz inequality. They isolated the property that a system of equations, or equivalently a system of linear forms, must have in order for degree-k uniformity to be sufficient for these arguments to work, and called this property complexity. Since in this chapter we shall have more than one notion of complexity, we shall sometimes call their notion Cauchy-Schwarz complexity, or CS-complexity for short.

Definition 2.1. Let L = (L1, ..., Lm) be a system of m linear forms in d variables.

For 1 ≤ i ≤ m and s ≥ 0, we say that L is s-complex at i if one can partition the m−1 forms {Lj :j 6=i}into s+ 1classes such that Li does not lie in the linear span of any of these classes. The Cauchy-Schwarz complexity (or CS-complexity) of L is defined to be the least s for which the system is s-complex at i for all 1≤i ≤m, or

∞ if no such s exists.

To get a feel for this definition, let us calculate the complexity of the system L of k linear forms x, x+y, . . . , x+ (k−1)y. Any two distinct forms x+iy and x+jy in L contain xand y in their linear span. Therefore, whichever formLwe take fromL, if we wish to partition the others into classes that do not contain L in their linear span, then we must take these classes to be singletons. Since we are partitioningk−1 forms, this tells us that the minimal s is k−2. So L has complexity k−2.

Next, let us briefly look at the system L of m2

forms xi−xj (1≤i < j ≤m) that we discussed above. IfL is the formxi−xj then no other formL0 ∈ L involves both xi andxj, so we can partitionL \ {L}into the forms that involve xi (which therefore do not involve xj) and the forms that do not involvexi. Since neither class includes L in its linear span, the complexity of L is at most 1. When m ≥ 3 it can also be shown to be at least 1.

2.1 Introduction

It follows from Green and Tao’s result that if A is sufficiently uniform and L = (L1, ..., Lm) has complexity at most 1, then A contains approximately the expected number ofm-tuples of the form (L1(x1, . . . , xd), . . . , Lm(x1, . . . xd)). (If the forms are defined over Zd, then this number is αm|G|d.)

Notice that this statement adequately explains all the cases we have so far looked at in which uniformity implies the correct number of solutions. It is thus quite natural to conjecture that Green and Tao’s result is tight. That is, one might guess that if the complexity L is greater than 1 then there exist sets A that do not have the correct number of images of L.

But is this correct? Let us look at what is known in the other direction, by discussing briefly the simplest example that shows that uniform sets inZN do not have to contain the correct number of arithmetic progressions of length 4. (Here we are taking N to be some large prime.) Roughly speaking, one takes A to be the set of allxsuch that x2 mod N is small. Then one makes use of the identity

x2−3(x+d)2+ 3(x+ 2d)2−(x+ 3d)2 = 0

to prove that ifx,x+dand x+ 2d all lie in A, then x+ 3dis rather likely to lie inA as well, because (x+ 3d)2 is a small linear combination of small elements ofZN. This means that A has “too many” progressions of length 4. (Later, we shall generalize this example and make it more precise.)

The above argument uses the fact that the squares of the linear formsx,x+d, x+ 2d and x+ 3d are linearly dependent. Later, we shall show that if L is any system of linear forms whose squares are linearly dependent, then essentially the same example works for L. This gives us a sort of “upper bound” for the set of systems L that have approximately the right number of images in any uniform set: because of the above example, we know that the squares of the forms in any such system L must be linearly independent.

And now we arrive at the observation that motivated this project: the “upper bound”

just described does not coincide with the “lower bound” of Green and Tao. That is, there are systems of linear forms of complexity greater than 1 with squares that are linearly independent. One of the simplest examples is the system (x, y, z, x+y+z, x+

2y−z, x+ 2z−y). Another, which is translation-invariant (in the sense that if you add a constant to everything in the configuration, you obtain another configuration of the same type), is (x, x+y, x+z, x+y+z, x+y−z, x+z−y). Both these examples have complexity 2, but it is not hard to produce examples with arbitrarily high complexity.