2.2 Uniformity Norms and True Complexity
Definition 2.2. Let G be a finite Abelian group. For any positive integer k ≥2 and any function f :G→C, define the Uk-norm by the formula
kfk2Ukk :=Ex,h1,...,hk∈G
Y
ω∈{0,1}k
C|ω|f(x+ω·h),
where ω·his shorthand for P
iωihi, and C|ω|f =f ifP
iωi is even and f otherwise.
These norms were first defined in [Gow01] (in the case where Gis the groupZN). Of particular interest in this chapter will be the U2-norm and theU3-norm. The former can be described in many different ways. The definition above expresses it as the fourth root of the average of
f(x)f(x+h)f(x+h0)f(x+h+h0)
over all triples (x, h, h0). It is not hard to show that this average is equal tokf∗fk22, and also tokfkb 44. (These identities depend on appropriate normalizations—we follow the most commonly used convention of taking averages in physical space and sums in frequency space.)
We shall call a function f c-uniform if kfkU2 ≤ c and c-quadratically uniform if kfkU3 ≤ c. We shall often speak more loosely and describe a function as uniform if it is c-uniform for some small c, and similarly for higher-degree uniformity. We remark here that if j ≤ k then kfkUj ≤ kfkUk, so c-uniformity of degree k implies c-uniformity of all lower degrees.
If A is a subset of an Abelian group G and the density of A is α, then we say that A is uniform of degree k if it is close in the Uk-norm to the constant function α.
More precisely, we define the balanced function f(x) = A(x)−α and say that A is c-uniform of degree k if kfkUk ≤c.
The following theorem is essentially Theorem 3.2 in [Gow01]. (More precisely, in that paper the theorem was proved for the group ZN, but the proof is the same.)
Theorem 2.3. Let k ≥2 and let G be a finite Abelian group such that there are no non-trivial solutions to the equation jx = 0 for any 1 ≤ j < k. Let c > 0 and let f1, f2, . . . , fk be functions from G to C such that kfik∞≤1 for every i. Then
Ex,y∈Gf1(x)f2(x+y). . . fk(x+ (k−1)y)
≤ kfkkUk−1.
It follows easily from this result that if A is a set of density α and A is c-uniform for sufficiently smallc, thenAcontains approximatelyαk|G|2 arithmetic progressions
2.2 Uniformity Norms and True Complexity
of length k. Very briefly, the reason for this is that we are trying to show that the average
Ex,yA(x)A(x+y). . . A(x+ (k−1)y) is close to αk. Now this average is equal to
Ex,yA(x)A(x+y). . . f(x+ (k−1)y) +αEx,yA(x)A(x+y). . . A(x+ (k−2)y).
The first of these terms is at most c, by Theorem 2.3, and the second can be handled inductively. The bound we obtain in this way is c(1 +α+· · ·+αk−1)≤kc.
We can now state formally Green and Tao’s generalization in terms of CS-complexity in the case where G is the groupZN, which is implicit in [GT06a].
Theorem 2.4. Let N be a prime, letf1, . . . , fm be functions fromZN to[−1,1], and let L be a linear system of CS-complexity k consisting of m forms in d variables.
Then, provided N ≥k,
Ex1,...,xd∈ZN
m
Y
i=1
f(Li(x1, ..., xd))
≤min
i kfikUk+1.
Just as in the case of arithmetic progressions, it follows easily that if A is a subset of G of density α, then the probability, given a random element (x1, ..., xd) ∈ Gd, that all the m images Li(x1, ..., xd) lie in A is approximately αm. (The inductive argument depends on the obvious fact that if L has complexity at most k then so does any subsystem of L.)
Green and Tao proved the above theorem because they were investigating which linear configurations can be found in the primes. For that purpose, they in fact needed a more sophisticated “relative” version of the statement. Since the proof of the version we need here is simpler (partly because we are discussing systems of complexity at most 2, but much more because we do not need a relative version), we give it for the convenience of the reader. This is another result where the proof is essentially the same for all Abelian groups, give or take questions of small torsion. Since we need it in the case G=Fnp, we shall just prove it for this group. The reader should bear in mind that for this group, one should understand linear independence of a system of forms as independence over Fp when one is defining complexity (and also square-independence).
The first step of Green and Tao’s proof was to put an arbitrary linear system into a convenient form for proofs. Given a linear form L in d variables x1, . . . , xd, let us define the support of L to be the set of j such that L depends on xj. That is,
2.2 Uniformity Norms and True Complexity
if L(x1, . . . , xd) = λ1x1 +· · ·+λdxd then the support of L is {i : λi 6= 0}. Let L = (L1, . . . , Lm) be a system of linear forms and let the support ofLi beσi for each i. Then L is said to be in s-normal form if it is possible to find subsets τi ⊂ σi for each i with the following two properties.
(i) Each τi has cardinality at mosts+ 1.
(ii) If i6=j then τi is not a subset of σj.
If a linear system L is in s-normal form, then it has complexity at most s. Indeed, if τi has r elements {i1, . . . , ir}, then one can partition the remaining forms into r sets L1, . . . ,Lr in such a way that no form in Lh uses the variable xih. SinceLi does use the variable xih it is not in the linear span of Lh.
The converse of this statement is false, but Green and Tao prove that every linear system of complexitys can be “extended” to one that is ins-normal form. This part of the proof is the same in both contexts, so we do not reproduce it. All we need to know here is that if we prove Theorem 2.4 for systems in normal form then we have it for general systems.
Just to illustrate this, consider the obvious system associated with arithmetic pro-gressions of length 4, namely (x, x+y, x+ 2y, x+ 3y). This is not in 2-normal form, because the support of the first form is contained in the supports of the other three.
However, the system (−3x−2y−z,−2x−y+w,−x+z + 2w, y+ 2z + 3w) is in 2-normal form (since the supports have size 3 and are distinct) and its images are also uniformly distributed over all arithmetic progressions of length 4 (if we include degenerate ones).
Now let us prove Theorem 2.4 whenk = 2. Without loss of generality we may assume that L is in 2-normal form at 1, and that it is the only form using all three variables x1 = x, x2 = y and x3 = z. We use the shorthand h(x, y, z) = f(L1(x1, x2, ..., xd)), and denote by b(x, y) any general bounded function in two variables x and y. It is then possible to rewrite
Ex1,...,xd∈Fnp
m
Y
i=1
f(Li(x1, ..., xd)) as
Ex4,x5,...,xdEx,y,zh(x, y, z)b(x, y)b(y, z)b(x, z).
Here, the functionshandb depend on the variablesx4, . . . , xdbut we are suppressing this dependence in the notation.
2.2 Uniformity Norms and True Complexity
Estimating the expectation over (x, y, z) is a well-known argument from the theory of quasirandom hypergraphs. (See for instance Theorem 4.1 in [Gow06a].) First, we apply Cauchy-Schwarz and use the boundedness of b to obtain an upper bound of
(Ex,y(Ezh(x, y, z)b(x, z)b(y, z))2)1/2. Expanding out the square and rearranging yields
(Ey,z,z0b(y, z)b(y, z0)Exh(x, y, z)h(x, y, z0)b(x, z)b(x, z0))1/2,
and by a second application of Cauchy-Schwarz we obtain an upper bound of (Ey,z,z0(Exh(x, y, z)h(x, y, z0)b(x, z)b(x, z0))2)1/4.
A second round of interchanging summation followed by a third application of Cauchy-Schwarz gives us an upper bound of
(Ex,x0,z,z0(Eyh(x, y, z)h(x, y, z0)h(x0, y, z)h(x0, y, z0))2)1/8.
This expression equals the “octahedral norm” of the functionh(x, y, z)—a hypergraph analogue of the U3-norm. Because for fixed x4, . . . , xd, h depends only on the linear expression L1(x, y, z), a simple change of variables can be used to show that it is in fact equal to kfkU3.
Now all that remains is to take the expectation over the remaining variables and the proof is complete. It is also not hard to generalize to arbitrary k, but this we leave as an exercise to the reader.
Now, as we stated earlier, Theorem 2.4 does not settle the question of which systems are controlled by which degrees of uniformity. Accordingly, we make the following definition.
Definition 2.5. Let L be a system of m distinct linear forms L1, L2, . . . , Lm in d variables. The true complexity of L is the smallest k with the following property.
For every > 0 there exists δ > 0 such that if G is any finite Abelian group and f :G→C is any function with kfk∞≤1 and kfkUk+1 ≤δ, then
Ex1,...,xd∈G m
Y
i=1
f(Li(x1, ..., xd)) ≤.
The main conjecture of this chapter is now simple to state precisely.