Analytical approaches to Szemeredi's Theorem: general case
After having discussed the notion of Gowers uniformity, the statement of Szemeredi's theorem, and the proof for progressions of length 3, let me try to say something about the case of progressions of length 4 or more, and the several related open questions.
As already discussed, Gowers's proof is based on an "algorithm" that, given a subset A of ZN of size dN, does one of the following two things:
As in the proof for the case of progressions of length 3, once we have such an algorithm we are able to find a progression of length k in A, provided that, initially, N is at least exp(exp(poly(1/d))).
How does the "algorithm" work? Let us, again, identify the set A with its characteristic function A: ZN -> {0,1}, and consider the expression
It is possible to show that (*) equals dk (which is what we would expect if A were a "pseudorandom" set) plus or minus an error term that depends on Uk-1(A-d), where Uk-1 is the dimension-(k-1) Gowers uniformity as defined earlier. A result of this kind (relating Gowers uniformity and number of arithmetic progressions) is called a "generalized Von Neumann theorem" in the literature, for reasons that I unfortunately ignore. The proof is not difficult at all, it is just a series of applications of Cauchy-Schwartz. The genius is in the choice of the right definition. (And the technical difficulties are in what comes next.)
This means that if the dimension-(k-1) Gowers uniformity of the function f(x):=A(x)-d is small, then A contains a lot of length-k arithmetic progressions, and we are in case (1)
What remains to prove is that if the set A is such that f(x):=A(x)-d has noticeably large dimension-(k-1) Gowers uniformity then we can find a set A' in ZN' as in case (2) above. Gowers's paper is approximately 130 pages long, and about 100 pages are devoted to proving just that.
Obviously, I have no idea what goes on in those 100 pages, but (based on later work by Green and Tao) I can guess how it would be if we were trying to prove Szemeredi's theorem not in ZN but in Fnp with p prime and larger than k. Translated to such a setting (I think), Gowers's argument would proceed by showing that if Uk(A-d) is at least eps, then there is an affince subspace V of Fnp of dimension n/O(1) such that A restricted to V has density at least d+poly(eps). This, in turn, would be proved by showing
Let's make things simple by restricting ourselves to Boolean function (even though this p=2 case has no direct application to results about arithmetic progressions).
Then, part (1) is saying that if f:{0,1}n->{-1,1} has noticeably large dimension-k Gowers uniformity, then there is a polynomial p() of degree (k-1) over Z2, and an affine subspace V of dimesion n/O(1), such that f(x) and (-1)p(x) agree on noticeably more than 1/2 of the inputs x. Part (2) is saying that if f:{0,1}n->{-1,1} and (-1)p(x) agree on noticeably more than 1/2 of the inputs, where p is a low-degree polynomial, then there is an affine subspace V of dimension n/O(1) such that, restricted to V, f has agreement with a linear function on noticeably more than 1/2 of the inputs.
The two results together imply that if f has noticeably large Gowers uniformity then there is a large sub-space in which f is correlated with a linear function. (To reach the conclusion, you need to apply part (1), then do a change of variables so that now the V of part (1) looks like {0,1}n/O(1), and then apply part(2).)
Actually, what I just wrote may be an open question, but it should be provable along the lines of Gowers's proof, and it should be much easier to prove.
For the case of progressions of length 4 in Fnp, for small prime p>4, Green and Tao prove that if f is a bounded function of noticeably large dimension-3 Gowers uniformity, then f is correlated to a degree-2 polynomial over all of Fnp, and the correlation is especially good on a subspace of dimension n-O(1). (As opposed to n/O(1).) This improvement, and several additional ideas, lead to an improved quantitative version of Szemeredi's theorem for progressions of length 4 in Fnp, and they also announced a similar improved result for progression of length 4 over the integers.
Their proof relies on the analysis of a certain "linearity test in the highly noisy case," which is also used (and, I think, proved for the first time) in Gowers's paper. In the, simpler, Boolean, case, the result is
(Update: as Alex explains in his comment below, the above sentence is quite misleading. Gowers proves quite a different statement in ZN, a setting in which an analogous "highly noise linearity test" statement is provably false, and where it is difficult to even get the statement of the right analog. The Boolean statement above is proved for the first time in Alex's paper, with a proof whose outline is similar to Gowers's; Green and Tao prove the highly noise linearity test result in other prime fields, also following Gowers's argument.)
In the known proof, which uses difficult results from additive combinatorics, eps' is exponentially small in eps. Here two major open questions are: (i) find a simple proof and (ii) find a proof where eps'=poly(eps)
More ambitiously, there could be a simple proof that (say, in the Boolean case) if f has noticeable Gowers uniformity, then f is noticeably correlated with a linear function when restricted to a large subspace. The experts in the area would probably be able to turn a proof in the Boolean case to a proof that applies to the setting where we have ZN instead of {0,1}n, Bohr sets instead of subspaces, and things I do not understand instead of polynomials. Even so, if the proof in Boolean setting were simple enough, the whole thing could be significantly simpler than Gowers's proof, and there could be room for quantitative improvements.
As already discussed, Gowers's proof is based on an "algorithm" that, given a subset A of ZN of size dN, does one of the following two things:
- It immediately finds a progression of length k in A; or
- it constructs a subset A' of ZN' such that: (i) if there is a progression of length k in A', then there is also such a progression in A; (ii) A' has size at least (d+poly(d))*N'; N' is at least a constant root of N.
As in the proof for the case of progressions of length 3, once we have such an algorithm we are able to find a progression of length k in A, provided that, initially, N is at least exp(exp(poly(1/d))).
How does the "algorithm" work? Let us, again, identify the set A with its characteristic function A: ZN -> {0,1}, and consider the expression
(*) Ex,y A(x)*A(x+y)*A(x+2y)*...*A(x+(k-1)*y)
It is possible to show that (*) equals dk (which is what we would expect if A were a "pseudorandom" set) plus or minus an error term that depends on Uk-1(A-d), where Uk-1 is the dimension-(k-1) Gowers uniformity as defined earlier. A result of this kind (relating Gowers uniformity and number of arithmetic progressions) is called a "generalized Von Neumann theorem" in the literature, for reasons that I unfortunately ignore. The proof is not difficult at all, it is just a series of applications of Cauchy-Schwartz. The genius is in the choice of the right definition. (And the technical difficulties are in what comes next.)
This means that if the dimension-(k-1) Gowers uniformity of the function f(x):=A(x)-d is small, then A contains a lot of length-k arithmetic progressions, and we are in case (1)
What remains to prove is that if the set A is such that f(x):=A(x)-d has noticeably large dimension-(k-1) Gowers uniformity then we can find a set A' in ZN' as in case (2) above. Gowers's paper is approximately 130 pages long, and about 100 pages are devoted to proving just that.
Obviously, I have no idea what goes on in those 100 pages, but (based on later work by Green and Tao) I can guess how it would be if we were trying to prove Szemeredi's theorem not in ZN but in Fnp with p prime and larger than k. Translated to such a setting (I think), Gowers's argument would proceed by showing that if Uk(A-d) is at least eps, then there is an affince subspace V of Fnp of dimension n/O(1) such that A restricted to V has density at least d+poly(eps). This, in turn, would be proved by showing
- If f has noticeably large dimension-(k-1) Gowers uniformity, then there is an affine subspace V of dimension n/O(1) and a polynomial phase function g of degree (k-2) such that, restricted to V, f and g are noticeably correlated
- If f is a function that has noticeable correlation with a low degree polynomial phase function, then there is a subspace of dimension n/O(1) such that f is correlated to a linear function when restricted to that subspace.
Let's make things simple by restricting ourselves to Boolean function (even though this p=2 case has no direct application to results about arithmetic progressions).
Then, part (1) is saying that if f:{0,1}n->{-1,1} has noticeably large dimension-k Gowers uniformity, then there is a polynomial p() of degree (k-1) over Z2, and an affine subspace V of dimesion n/O(1), such that f(x) and (-1)p(x) agree on noticeably more than 1/2 of the inputs x. Part (2) is saying that if f:{0,1}n->{-1,1} and (-1)p(x) agree on noticeably more than 1/2 of the inputs, where p is a low-degree polynomial, then there is an affine subspace V of dimension n/O(1) such that, restricted to V, f has agreement with a linear function on noticeably more than 1/2 of the inputs.
The two results together imply that if f has noticeably large Gowers uniformity then there is a large sub-space in which f is correlated with a linear function. (To reach the conclusion, you need to apply part (1), then do a change of variables so that now the V of part (1) looks like {0,1}n/O(1), and then apply part(2).)
Actually, what I just wrote may be an open question, but it should be provable along the lines of Gowers's proof, and it should be much easier to prove.
For the case of progressions of length 4 in Fnp, for small prime p>4, Green and Tao prove that if f is a bounded function of noticeably large dimension-3 Gowers uniformity, then f is correlated to a degree-2 polynomial over all of Fnp, and the correlation is especially good on a subspace of dimension n-O(1). (As opposed to n/O(1).) This improvement, and several additional ideas, lead to an improved quantitative version of Szemeredi's theorem for progressions of length 4 in Fnp, and they also announced a similar improved result for progression of length 4 over the integers.
Their proof relies on the analysis of a certain "linearity test in the highly noisy case," which is also used (and, I think, proved for the first time) in Gowers's paper. In the, simpler, Boolean, case, the result is
Let F:{0,1}n -> {0,1}m, and suppose that
Prx,y[F(x)+F(y) = F(x+y)] > eps
where all operations are bitwise mod 2. Then there is an eps' (depending only on eps, but independent of n,m) and a matrix M such that the functions x->F(x) and x->Mx have agreement at least eps'
(Update: as Alex explains in his comment below, the above sentence is quite misleading. Gowers proves quite a different statement in ZN, a setting in which an analogous "highly noise linearity test" statement is provably false, and where it is difficult to even get the statement of the right analog. The Boolean statement above is proved for the first time in Alex's paper, with a proof whose outline is similar to Gowers's; Green and Tao prove the highly noise linearity test result in other prime fields, also following Gowers's argument.)
In the known proof, which uses difficult results from additive combinatorics, eps' is exponentially small in eps. Here two major open questions are: (i) find a simple proof and (ii) find a proof where eps'=poly(eps)
More ambitiously, there could be a simple proof that (say, in the Boolean case) if f has noticeable Gowers uniformity, then f is noticeably correlated with a linear function when restricted to a large subspace. The experts in the area would probably be able to turn a proof in the Boolean case to a proof that applies to the setting where we have ZN instead of {0,1}n, Bohr sets instead of subspaces, and things I do not understand instead of polynomials. Even so, if the proof in Boolean setting were simple enough, the whole thing could be significantly simpler than Gowers's proof, and there could be room for quantitative improvements.
posted by Luca at 9:30 PM
5 Comments:
6/13/2006 06:18:00 PM
Let F:{0,1}n -> {0,1}m, and suppose that
Prx,y[F(x)+F(y) = F(x+y)] > eps
where all operations are bitwise mod 2. Then there is an eps' (depending only on eps, but independent of n,m) and a matrix M such that the functions x->F(x) and x->Mx have agreement at least eps'.
In the known proof, which uses difficult results from additive combinatorics, eps' is exponentially small in eps. Here two major open questions are: (i) find a simple proof and (ii) find a proof where eps'=poly(eps)
Luca,
Isn't Theorem 4.1 of Samorodnitsky's paper on ECCC claiming eps' as a polynomial function of eps for this case? For general homomorphism this claim states a bound which is polynomial in eps and 1/r where r is the "order" of the group, which I think here is meant to denote the largest order of an element of the group (as opposed to the size of the group). He also says after the theorem that for case when bpoth groups are powers of Z_2, eps' depends only on eps (and possibly only polynomially reading off from the Theorem, or am I misreading some statements?)
--Venkat
6/13/2006 06:21:00 PM
To follow-up: Or is it the case that the "absolute" constant depends on eps and is independent only of the groups G,H? Now that I read the theorem statement again, this is probably what is meant, and from your post I take it that "absolute" constant is like 1/eps or something?
6/13/2006 07:12:00 PM
Hi Venkat, I think that, in Theorem 4.1 of Alex's paper, the "absolute" should be read as relative to the size of the group, but not relative to eps.
Indeed, tracing the proof back, the constants c,c' and c'' in Theorems 6.8 and 6.9 depend exponentially on the constant hidden in the \Omega() notation at the bottom of page 16. In the setting of Theorem 4.1, the constant in the Omega notation is eps of the statement of Theorem 4.1.
6/15/2006 05:14:00 AM
This comment has been removed by a blog administrator.
6/22/2006 09:10:00 AM
This is a corrected version of a somewhat incorrect comment I posted before, and which was deleted by Luca, following my request.
As to Theorem 4.1 in the ECCC paper mentioned by Venkat, the statement in the Theorem is misleading, and should be corrected. The "absolute" constant in the exponent of r is the constant in Ruzsa's theorem, cited as Theorem 6.9 in the paper. It depends (polynomially, I think) on the constant in Gowers's theorem, cited as theorem 6.8, and this last constant depends polynomially on 1/eps.
It would, in fact, be very nice to prove polynomial dependence of eps' on eps here, because it might (not too sure about this), using lots of Green, Gowers, and Tao's technology, lead to better bounds for arithmetic progressions of legth four in subsets of integers.
Also, this would indicate that a famous conjecture of Rusza is true. The conjecture says that if
F:{0,1}^n -> {0,1}^n such that
the cardinality of a multiset
{ F(x) + F(y) + F(x+y) } is K, thinking about K as small, then
F = L + R, where L is linear and the cardinality of the image of R is bounded by a polynomial in K.
If this conjecture is true, then it would imply, in particular, polynomial dependence of eps' on eps in homomorphism testing.
One additional remark on the preceding discussion. Gowers was interested in highly noisy homomorphism tests for the group Z_N. In this case the claim that there exists eps' depending only on eps and independent of the group size is incorrect (because the maximal order of an element is large). Gowers in fact calls such a putative statement an 'attractive conjecture' (or something like this) and gives a counterexample. This counterexample is actually very similar to one given by Benor and Coppersmith 10 years before this, in the context of homomorphism testing.
In his paper Gowers goes around this problem, by proving a weaker, but sufficient for his needs, statement for Z_N. On the way he develops tools which essentially solve the problem for other groups.
The analysis of the homomorphism problem for Z^n_p was, to the best of my knowledge, given independently by Green and Tao in "An inverse theorem for the Gowers U^3 norm", and in the ECCC paper discussed here. The proofs follow Gowers's approach very closely. One basically needs only to replace a theorem of Freiman on the structure of subsets of integers with small subsets ( |A + A| is not much larger than |A|) with a theorem of Ruzsa which deals with subsets of general abelian groups.
Alex
Post a Comment
<< Home