• No results found

2.3 True Complexity for Vector Spaces over Finite Fields

2.3.4 Remarks

2.3 True Complexity for Vector Spaces over Finite Fields

Corollary 2.20. For every > 0 there exists c > 0 with the following property.

Let A be a c-uniform subset of Fnp of density α. Let L = (L1, . . . , Lm) be a square-independent system of linear forms in d variables, with Cauchy-Schwarz complexity at most 2. Let x = (x1, . . . , xd) be a random element of (Fnp)d. Then the probability that Li(x)∈A for every i differs from αm by at most .

Proof. We shall choose as our c the c that is given by the previous theorem when is replaced by /2m. Our assumption is then that we can write A = α+f for a c-uniform functionf. The probability we are interested in is

Ex∈(Fnp)d m

Y

i=1

A(Li(x)),

which we can split into 2m parts, obtained by replacing each occurrence of A either by α or by f.

For each part that involves at least one occurrence of f, we have a power of α multiplied by a product over some subsystem of L. This subsystem will also be square-independent and have CS-complexity at most 2. Moreover, the number of linear forms will have decreased. Therefore, the previous theorem and our choice of c tell us that the contribution it makes is at most /2m. Therefore, the contribution from all such parts is at most . The only remaining part is the one where every A(Li(x)) has been replaced by α, and that gives us the main termαm.

2.3 True Complexity for Vector Spaces over Finite Fields

on an affine subspace. The resulting argument is almost identical to the well-known argument for 3-term progressions [Mes95]. Translation invariance is needed because the subspace on which we find a density increment may be an affine and not a strictly linear one. (It is not hard to show that the result is false if the system is not translation invariant.)

There are several ways in which the results of Section 3 might be generalized. An obvious one is to prove comparable results for the groupZN. As we mentioned earlier, we have a different proof forFnp and this can be transferred toZN by “semi-standard”

methods. (That is, the general approach is clear, but the details can be complicated and sometimes require more than merely technical thought.) The alternative proof for Fnp gives a doubly exponential bound for the main result rather than the tower-type bound obtained here.

Possibly even more obvious is to try to extend the main result of this paper to a proof of Conjecture 2.6. This involves a generalization in two directions: to systems of CS-complexity greater than 2, and to systems with true complexity greater than 1.

All further cases will require polynomial Fourier analysis for a degree that is greater than 2: the simplest is likely to be to show that a square-independent system with CS-complexity 3 has true complexity 1. In this case, we would use a decomposition into a structured part (a projection onto a cubic factor) and a uniform part (which would be small inU4 and therefore negligible) and then, as before, concentrate on the structured part. Square-independence (which implies cube-indepence) would ensure that we could reduce to the linear part of the factor as before.

This state of affairs leaves us very confident that Conjecture 2.6 is true. Although cubic and higher-degree Fourier analysis have not yet been worked out, they do at least exist in local form forZN: they were developed in [Gow01] to prove the general case of Szemer´edi’s theorem. It is therefore almost certain that global forms will eventually become available, both for ZN and for Fnp. And then, given a statement analogous to Theorem 2.11, it is easy to see how to generalize the main steps of our proof. In particular, the Gauss-sum estimates on which we depend so heavily have higher-degree generalizations.

A completely different direction in which one might consider generalizing the above re-sults is to hypergraphs. For example, very similar proofs to those of Theorems 2.3 and 2.4 can be used to prove so-called “counting lemmas” for quasirandom hypergraphs—

lemmas that assume that a certain norm is small and deduce that the hypergraph contains approximately the expected number of small configurations of a given kind.

One can now ask whether, as with sets, weaker quasirandomness assumptions about a

2.3 True Complexity for Vector Spaces over Finite Fields

hypergraph suffice to guarantee the right number of certain configurations, and if so, which ones. It turns out to be possible to give a complete answer to a fairly natural formulation of this question. Unfortunately, however, the proof is rather too easy to be interesting, so here we content ourselves with somewhat informal statements of results concerning the special case of 3-uniform hypergraphs. The proofs we leave as exercises for any reader who might be interested.

Recall that ifX, Y andZ are finite sets andf :X×Y ×Z →R, then theoctahedral norm of f is the eighth root of

Ex(0),x(1)∈XEy(0),y(1)∈YEz(0),z(1)∈Z

Y

∈{0,1}3

f(x(1), y(2), z(3)).

It is easy to verify that ifX =Y =Z =Gfor some Abelian groupGandf(x, y, z) = g(x+y+z) for some function g, then the octahedral norm of f is the same as the U3-norm of g. Therefore, it is natural to consider the octahedral norm of functions defined on X×Y ×Z as the correct analogue of the U3-norm of functions defined on Abelian groups.

An important fact about the octahedral norm is that f has small octahedral norm if and only if it has a small correlation with any function of the formu(x, y)v(y, z)w(x, z).

Another important fact, the so-called “counting lemma” for quasirandom hyper-graphs, states the following. Let X be a finite set and let H be a 3-uniform hy-pergraph with vertex set X and density α. Suppose that H is quasirandom in the sense that the functionH(x, y, z)−αhas small octahedral norm (whereH(x, y, z) = 1 if{x, y, z} ∈Hand 0 otherwise). ThenHhas about the expected number of copies of any fixed small hypergraph. For instance, if you choose x,y, z and wrandomly from X, then the probability that all of {x, y, z},{x, y, w},{x, z, w} and {y, z, w} belong to H is approximately α4.

Now let us suppose that g is uniform but not necessarily quadratically uniform, and that we again define f(x, y, z) to beg(x+y+z). What can we say about f? It is not necessarily the case that f has small octahedral norm, or that it has low correlation with functions of the form u(x, y)v(y, z)w(x, z). However, it is not hard to show that it has low correlation with any function of the forma(x)b(y)c(z), a property that was referred to as vertex uniformity in [Gow06a].

One might therefore ask whether vertex uniformity was sufficient to guarantee the right number of copies of some small hypergraphs. However, well-known and easy examples shows that it does so only for hypergraphs such that no pair {x, y} is contained in more than one hyperedge. For instance, let u be a random symmetric