Friday, June 30, 2006

Yidali wan sui!

After Italy scored the overtime goal against Australia on Monday, CCTV commentator Huang Jianxiang went beserk, shouting 马尔蒂尼今天生日快乐, happy birthday Maldini, 意大利万岁 long live (literally, "live 10,000 years") Italy, and so on. We share the sentiment. He later had to apologize.



At YouTube there is an extended transcript (in English).

By the way, is it Go West by the Pet Shop Boys playing at the end in the background?

Update: as the commenters correctly point out, Go West is by the Village People, and the Pet Shop Boys version is a later cover. Shame on me. To atone, here is the Village People video:

Tuesday, June 27, 2006

Not one of those girlie blogs

Microsoft Research has developed a tool to measure how butch is a web site. (Via Doug Tygar.) In Theory scores 54% male. It must be all those manly posts about math. (Although I have to agree with the first comment here.)

Monday, June 26, 2006

Point and counterpoint

When traveling in East Asia, it is easy to make fun of the mistranslated signs and the oddly named stores. (There is, in fact, a whole website devoted to just that: see a few examples here, here and here, out of several hundreds.)

Anyways, when we use Chinese characters in the West, the joke is on us.

Property testing and Szemeredi's Theorem

After discussing Szemeredi's Theorem and the analytical approaches of Roth and Gowers, let's see some ideas and open problems in the combinatorial approach.

The following result is a good starting point.
Triangle Removal Lemma. For every d>0 there is a constant eps(d)>0 such that if G is an n-vertex graph with at most eps(d)n3 triangles, then it is possible to make G triangle-free by removing at most dn2 edges.

This result follows easily from the Szemeredi Regularity Lemma, and it is a prototype of several results in the field of property testing.

Indeed, consider the problem of distinguishing triangle-free graphs from graphs that are not even close to being triangle-free. For the purpose of this example, we think of a graph as "close to being triangle-free" if it can be made triangle-free by removing at most dn2 edges, for some small constant d. Then the Lemma tells us that in a not-even-close graph we have at least eps(d)n3 triangles, and so a sample of O(1/eps(d)) vertices is likely to contain a triangle. So here is an algorithm for the problem: pick at random O(1/eps(d)) vertices and see if they induce a triangle. We note that:

  • The algorithm satisfies our requirement;

  • The running time is a constant independent of n and dependent only on d;

  • this all makes sense only if 1/eps(d) grows moderatly as a function of 1/d.

Let us now see that the Triangle Removal Lemma proves Szemeredi's Theorem for sequences of length 3. As we discussed earlier, it is enough to prove the Theorem in groups of the type ZN, with N prime; we will do better and prove the Theorem in any abelian group. So let G be an abelian group of size N, an let A be a subset of G of size dN. Construct a tri-partite graph (X,Y,Z,E) where X,Y,Z are sets of vertices, each of size N, and each a copy of the group G. The set of edges is defined as follows:

  1. for x in X and y in Y, (x,y) is an edge if there is a a in A such that x+a=y
  2. for x in X and z in Z, (x,z) is an edge if there is a b in A such that x+b+b=z
  3. for y in Y and z in Z, (y,z) is an edge if there is a c in A such that y+c=z

Now we notice that if x,y,z is a triangle, then there are a,b,c in A such that (after some cancelations) a+c = b+b, which means that a,b,c is an arithmetic progression of length 3 in the group G. In fact, we see that the number of triangles in the graph is precisely N times the number of triples (a,b,c) in arithmetic progression in A.

Consider now the N*|A| = dN2 triangles corresponding to the "trivial" progressions of the form a,a,a. (These are the triangles x,x+a,x+a+a.) We can see that these triangles are edge-disjoint, and so in order just to remove such triangles we have to remove from the graph at least dN2 edges. So the Triangle Removal Lemma implies that there are at least eps(d)N3 triangles in the graph, and so at least eps(d)N2 triples in arithmetic progression in A. If N > d/eps(d), then some of those arithmetic progressions must be non-trivial, and we have the length-3 case of Szemeredi's theorem.

We see that both for the "property testing" application and for the Szemeredi Theorem application it is important to have good quantitative bounds on eps(d). We know that, in Szemeredi's theorem, N must be super-polynomial in 1/d, and so, in the Triangle Removal Lemma, 1/eps(d) must be super-polynomial in 1/d.

The known bounds, however, are quite unreasonable: we only know how to bound 1/eps(d) by a tower of exponentials whose height is poly(1/d). Unfortunately, such unreasonable bounds are unavoidable in any proof of the Triangle Removal Lemma based on Szemeredi's Regularity Lemma. This is because, as proved by Gowers, such tower-of-exponentials bounds are necessary in the Regularity Lemma.

Can we find a different proof of the Triangle Removal Lemma that has only a singly- or doubly-exponential eps(d)? That would be wonderful, both for property testing (because the proof would probably apply to other sub-graph homomorphism problems) and for additive combinatorics. Over the last year, I have found at least three such proofs. Unfortunately they were all fatally flawed.

Or, is there a more-than-exponential lower bound for the Triangle Removal Lemma? This would also be a major result: it would show that several results in property testing for dense graphs have no hope of being practical, and that there is a "separation" between the quantitative version of Szemeredi's Theorem provable with analytical methods versus what can be proved with the above reduction. Besides, it's not often that we have super-exponential lower bounds for natural problems, with Gowers's result being a rare exception.

By the way, what about Szemeredi's Theorem for longer sequences? For sequences of length k one needs a "k-clique removal lemma" for (k-1)-uniform hypergraphs, which in turn can be derived from the proper generalization of the Regularity Lemma to hypergraphs. This turns out to be quite complicated, and it has been accomplished only very recently in independent work by Nagle, Rödl and Schacht; and by Gowers. An alternative proof has been given by Tao. The interested reader can find more in expository paper by Gowers and Tao.

What about Szemeredi's own proof? It does use the Regularity Lemma, which was conceived and proved specifically for this application, and it involves a reduction to a graph-theoretic problem. I have to admit that I don't know much else.

Wednesday, June 21, 2006

More on the Poincare conjecture

The Strings 2006 conference is under way in Beijing, and yesterday Field Medalist Yau Shing-Tung gave a popular talk on the Poincare conjecture. Yau's talk was preceded by taped remarks by Richard Hamilton. A transcript of Hamilton's remarks is here, the People's Daily article is here and a first-hand account is here.

Friday, June 16, 2006

The True North strong and free

The 30th Frameline film festival is under way. It can exist, and be such a big production, thanks to the contributions of the Frameline members and to the major sponsors. In addition, each screening has its own sponsor. The movie I saw today was sponsored by ... Canada!

No kidding.

This is not an isolated act of kindness. The Frameline programmer who introduced the movie said that, over time, the Canadian government has contributed more than the US federal government to the festival.

I have two things to say: (1) foreign aid to needy countries is very noble; (2) I blame the electoral college.

Thursday, June 15, 2006

In Theory: non-judgemental for five more years

Found today in a fortune cookie:
At 20 years of age the will reigns; at 30 the wit; at 40 the judgement.

My gut is better than yours

Scott complains that "art snobs" want to have it both ways: to assert that the beauty of art is an aesthetic experience, a gut feeling, and, at the same time, that certain tastes are more valid than others. What is this, do they think that their guts are better than ours? That's certainly not how we do things in complexity theory. Or is it?

When we talk about the "beauty" of a theorem or of a proof, we rarely refer to the literal statement of the theorem, much less to the fact that the proof is correct.

The beauty of a theorem is typically found in the way it fits into the bigger fabric of a theory, how it is explained by, and how it explains, other results. The statement of a theorem can feel comforting, surprising, or even unsettling, or worrisome. In a proof, we appreciate economy, a way of getting to the point in what feels like the "right" way, an unexpected use of techniques, a quick turn and a surprising ending.

If we think of, say, Reingold's proof that L=SL, we (meaning, I and some other people) appreciate the statement for being a major milestone in the program of derandomization, and we appreciate the proof for the simplicity of its structure and for the cleverness of the way its technical tools are used.

Although, in the end, it is a matter of taste to see that the statement is important and that the proof is beautiful, I don't think that the taste of the expert in the area is equally valid as the taste of the non-expert who says, oh this is an algorithm for connectivity that runs in n100 time and it does not even work on directed graphs?

(I am so delighted to have a discussion where one can take the notion of mathematical beauty for granted, and then use it to argue about artistic beauty.)

This wouldn't be a non-technical In Theory post without an unnecessary personal story, so let me conclude with my experience with modern dance.

At one point, a few years ago, I was taken to see several modern dance performances. My first experience was not unlike Woody Allen's in Small Time Crooks. While the sound system was playing annoying and discordant sounds, people on stage were moving around in what looked like a random way. I was convinced that the nearly sold-out audience at Zellerbach (it's a big theater) was there simply to feel good about themeselves and nobody could really like that stuff. There was something that puzzled me, however: at one point, everybody laughed, presumably because something (intentionally) funny happened in the choreography. Everybody got it (except me, of course), so perhaps there was something going on in those random movements, after all. After a few more shows, the experience started to feel less agonizing, and I started to notice that I would like some segments better than others, and that this would agree with what others thought. Finally, one night, I laughed out when a dancer did something really funny on stage, and so did the rest of the audience. Aha, the brainwashing had succeeded! I left the theater feeling good about myself... No, wait, this is so not the point I wanted to make...

Wednesday, June 14, 2006

Snoop Dogg raps about complexity

I can't decide if this is funny or racist. (From Gizoogle.)

Monday, June 12, 2006

Polynomials and subspaces

My latest post on Szemeredi's theorem was long and rambling, mostly because I had no idea what I was talking about. There are, however, a couple of neat questions, and I am afraid they got lost in the rambling, so let me state them again.

  1. It is either known or probably derivable from known proof techniques that
    If f:{0,1}^n -> {0,1} has agreement 1/2+eps with a degree-k polynomial, then there is an affine subspace V of {0,1}n, of dimension n/c, and a linear function L, such that f and L have agreement 1/2 + eps' when restricted to V. Here c=c(k) is a constant that depends only on k and eps'=eps'(eps,k) is a constant that depends only on eps and on k.

    This is somewhat surprising, even if you look at the special case of a function f that is a polynomial (as opposed to being correlated with a polynomial).

    Is there a simple proof of this result? Is the result true if you replace "subspace" by "restriction"? (Meaning, you are only allowed to fix all but a constant fraction of the variables.) Shouldn't this be useful in complexity theory somewhere?

    [Update 7/14/06: the degree-2 case has indeed a very simple proof. A more general result is proved here, in section 7. For higher degree, the result is actually false, in the sense that it is impossible to find a subspace of dimension constant*n. Avi Wigderson and I have found a counterexample already for degree 3, and Ben Green has sharpened our lower bound. The best one can do for degree-k polynomials is to find a subspace of dimension about n(1/(k-1)).]



  2. If f has agreement 1/2+eps with a linear function L in a subspace V of dimension n-t, then there is a linear function L' such that f and L' agree on a fraction at least 1/2+eps/2t of all of {0,1}n

    This is fairly easy to see.

  3. This is a fascinating challenge: find an simple proof (or any proof that fits in fewer than, say, 20 pages) that if f:{0,1}n->{-1,1} has dimension-k Gowers uniformity at least eps, then there is a linear subspace V of dimension n/c and a linear function L, such that f and L have agreement at least 1/2+eps' on V. (Where c=c(k) and eps'=eps'(eps,k).)

    Chances are that such a proof could be turned into a simpler proof of Gowers's quantitative version of Szemeredi's theorem. (A proof of the above result for boolean functions can probably be "translated back" from Gowers's paper, and it would probably be at least 50-60 pages. As I understand it, such a proof would first argue that f is correlated with a polynomial in a large subspace, and then proceed with (1) above. I wonder: can one prove such a statement without mentioning polynomials at all?)

  4. Unfortunately the conclusion cannot be strenghtened to "... there is a linear subspace V of dimension n-o(n)...". Consider
    f(x1,...,x1):= x1*x2+...+ xn-1*xn mod 2

    Its dimension-3 Gowers uniformity is 1, but, if you could find a subspace V of dimension n-o(n) on which f agrees with a linear function on a 1/2+eps' fraction of inputs, then you could also find a linear function that agrees with f on a 1/2+eps/2o(n) fraction of inputs. But we know that no linear function agrees with f on more than a 1/2+1/2n/2 fraction of inputs.

Thursday, June 08, 2006

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:

  1. It immediately finds a progression of length k in A; or
  2. 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

  1. 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
  2. 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.

Monday, June 05, 2006

Poincare conjecture proved for real?

The Poincare conjecture is one the seven Clay millenium problems, each worth a million-dollar prize. It says something about all 3-dimensional "simply connected" manifolds being "equivalent" to the sphere in R4. A Fields medal was awarded for the proof for k-dimensional manifolds, k>4, and another Fields medal for k=4. (In those cases the "equivalence" is with the sphere in Rk+1.)

A few years ago, the Russian mathematician Grigori Perelman posted a series of papers on the arxiv. The papers outlined a proof of the "Thurston geometrization conjecture," a statement that implies the Poincare conjecture.

Ever since, the status of the Poincare conjecture has remained uncertain. Perelman's papers do not contain a full proof, but various experts have been in agreement that most likely Perelman's ideas can be successfully formalized. Meanwhile, Perelman's himself seemed to be oblivious to the matters of writing a full paper and claiming the prize.

Now comes the news (via Not Even Wrong) that two Chinese mathematicians have written a 300-page paper that formalizes Perelman's argument, and the paper is about to be published in the Asian Journal of Mathematics.

Update 6/6/06: The Guardian technology blog picks up the story.

Update 6/6/06: The Notices of the AMS have an article on the genesis of the Clay millenium prizes. The stories are very interesting. (For example Wiles's insights into mathematical politics.) I noticed one paragraph in particular. Perhaps with Perelman's case in mind, Arthur Jaffe writes
The rules for the prize resulted from a fair amount of thought. [...] One major safeguard involved the importance of publication of the solution. [...] Of course there can also be unforeseen circumstances. For example, an author of a solution may not write it down completely [...]


Update 6/7/06: An April 10 press releas from the organizers of ICM'06 suggests that there were plans to announce in Madrid that Perelman's proof has been "checked."

Update 6/8/06: see also the May 15 ICM bulletin.

Sunday, June 04, 2006

Analytical approaches to Szemeredi's Theorem: k=3

Here is the idea of Roth's proof of the k=3 case of Szemeredi's Theorem. (See yesterday's post if you have no idea what I am talking about.) We have a subset A of ZN of size dN and we want to find a length-3 arithmetic progression in A. A first observation is that if d > 2/3 then we are done, because if we pick a,b at random there is positive probability that a,a+b,a+b+b are all in A. (Use the union bound.) The proof will work by "induction" on d, showing that the truth of the theorem for a smaller value of d can be derived from the truth of the theorem for a larger value d. Of course d is a continous parameter, so it will not really be induction, but that's how we should think of it.

The main result is an "algorithm" that given A subset of ZN of size dN does one of the following two things:

  1. It immediately finds a length-3 progression in A; or

  2. it constructs a subset A' of ZN' such that (i) if A' has a length-3 progression then so does A; (ii) A' has size at least about (d+d2)*N'; and (iii) N' is about sqrt(N).

So, given A, we run the algorithm, and we either immediately find the progression, or we get A'. In the latter case, we run the algorithm on A', and we either get a progression in A' (implying a progression in A) or we get a new set A'', and so on. But how many times do we have to keep doing this? At each step, the density of the set increases, and if it ever goes above 2/3 then we are also done. So, how many times can you do the d -> d + d2 transformation until you get 2/3? Certainly no more than O(1/d2) times, but actually O(1/d) is enough. This means that we will always find a length-3 progression in A, provided that N is large enough that we can take its square root O(1/d) times. So if N is doubly exponential in 1/d we have our proof.

Gowers's proof for the general case has the same outline. Now we want to find a length-k progression in A. If the density of A is more than (k-1)/k, we are done. Gowers describes an algorithm that, given A, either finds a length-k progression or constructs a set A' in ZN' such that if A' has a length-k progression that so does A'. Furthermore, A' has density d+poly(d) and N' is a constant root of N.

How do these arguments work? Let us look at Roth's proof in the case in which A is a subset of Fnp with prime p; for concreteness, take p=3. Given A, consider its characteristic function (that we denote again A) A: Fn3 -> {0,1} and compute its Fourier transform.

Consider now the probability that, when picking a,b at random, the three points a,a+b,a+b+b are all in A. This is the same as
(*) Ea,b A(a)*A(a+b)*A(a+b+b)

which can be expressed really cleanly in terms of the Fourier coefficients of A. In particular, the expression (*) is d3, which is the number you would get if you were looking at 3 independent points, plus or minus an error term that depends on the largest Fourier coefficient of A. If all Fourier coefficients are less than, say, d2/2, then epression (*) is at least d3/2, and we have plenty of length-3 progressions in A; this is case (1) of the proof. In this case, we should think of A as a "pseudorandom set against adversaries that look for random length-3 progressions."

What happens if A has a large Fourier coefficient? This means that A is correlated with a linear function, and so there is an affine subspace V in Fn3 of dimension n-1 such that A is denser in V than in the rest of Fn3. Now, map V to Fn-13 via an invertible affine map, and let A' be the image of A under this map. If there is a length-3 progression in A', that's just 3 points on a line; but then it means that also in A we had 3 points on a line. The set A' has density about d+d2 in Fn-13, and so we have part (2) of the argument.

As a bonus, we only lost a constant fraction of our group size at each step, so d can be as large as about 1/logN, where N=3n is the size of the initial group containing A.

Note the "win-win" structure of the argument. If A has small Fourier coefficients, then it is "pseudorandom", and we get what we want from the pseudorandomness. Otherwise, A has some "linear structure," and we can take advantage of it to reduce to a simpler instance of our original problem.

This "either we get what we want or we reduce to a simpler case" proof strategy has been used in some constructions of extractors, but it seems such a good idea that it may apply more widely, and one should keep it mind.

What about lower bounds? Excellent question. There is a very simple construction due to Behrend of a subset of size N/exp(sqrt(log N)) of {1,...,N} that has no length-3 progression, so N must be super-polynomial in 1/d when we prove the theorem over the integers (or over ZN with prime N, the two cases are essentially equivalent). Note that if you try to find a large set with no length-3 progression using the probabilistic method, you will not go very far. This is a better than random explicit construction, a rarity in extremal combinatorics. By the way, Behrend's construction is very simple (here is a half-page description), it is 60 year old, and nobody has been able to improve it ever since.

What about lower bounds for Fn3? There is no known construction of a large subset avoiding length-3 progressions. The best lower bounds are of the form cn, with c<3. Is there a (3-o(1))n lower bound? This is a major open question. If there were a (2.999)n upper bound, then it would be a stunning result, because it would show that the business of translating proofs from finite fields to the integers using Bohr sets cannot be applied as a black box, but it works on some proofs and does not work on other proofs.

Xi Shuashua!

This is getting too serious, it is time for some mandarin pop.



This song, 嘻唰唰, while (intentionally) silly, is quite catchy, and it was a big hit in China. It has also been at the center of a controversy: the band has been accused of plagiarizing the song from an older Japanese pop hit. It really makes you think: to write a song like this you have to plagiarize it? It is like the story of the worst referee report ever.
The paper presents a wrong proof of a known result. The mistake, however, is not new.

Saturday, June 03, 2006

Szemeredi's theorem

Szemeredi's theorem on arithmetic progressions is one of the great triumphs of the "Hungarian approach" to mathematics: pose very difficult problems, and let deep results, connections between different areas of math, and applications, come out as byproducts of the search for a solution.

(Tim Gowers's essay The two cultures of mathematics discusses brilliantly this "problem solving" way of doing math, as distinct from the "theory building" way.)

Some of the math surrounding Szemeredi's theorem has found applications in property testing, in PCP constructions, and in extractor constructions, and more future applications are likely. Besides, it is truly beautiful (and somewhat accessible) math. It can be a lot of fun for a computer scientist to delve into this literature.

In telling the story of Szemeredi's theorem, one usually starts from Van der Waerden's 1927 theorem that, no matter how you color the integers with a finite number of colors, there are arbitrarily long monochromatic arithmetic progressions. (An aritmetic progression is a sequence of the form a,a+b,a+2b,...,a+kb,....) In a more quantitative form, the theorem says that for every constants c,k there is an N(c,k) such that for every N>N(c,k), no matter how we color the integers {1,...,N} with c colors, there will be a monochromatic arithmetic progression of length k.

In 1936, Erdos and Turan conjectured that the coloring in Van der Waerden's theorem was just a "distraction," and that the "true reason" why the theorem is true is that every dense enough set of integers (in particular, the largest color class in Van der Waerden's theorem) must contain long arithmetic progressions. Specifically, they conjectured that for every density 0 < d <1 and every integer k there is an N(d,k) such that every subset A of {1,...,N} of cardinality dN contains a length-k arithmetic progression, provided N> N(d,k).

This conjecture became one of the great unsolved problems in Ramsey theory. In 1953, Roth proved the k=3 case of the Erdos-Turan conjecture. In Roth's proof, N(d,3) is doubly exponential in 1/d. In other words, Roth proves that a subset of {1,...,N} containing at least about N/log log N elements must contain a length-3 progression. The proof is analytical, and uses Fourier analysis. (Or the "circle method" as number theorists say.)

It was only in 1974 that Szemeredi proved the Erdos-Turan conjecture in the general case, and this is the result that is now known as Szemeredi's Theorem. Szemeredi's proof is combinatorial, and works via a reduction to a graph-theoretic problem. The Szemeredi regularity Lemma, that has several applications in computer science, is part of the proof. The value of even N(d,4) is a tower of exponentials in Szemeredi's proof; one only gets that a subset of {1,...,N} of size about N/log* log* n must contain a length-4 progression.

In 1977 Furstemberg found a completely different proof. He proved a "transfer theorem" showing that results about arithmetic progressions (and other related structures) can be derived from statements about certain continous objects, and then he proved the continous statements by "standard methods" in Ergodic Theory. The transfer theorem uses a result that requires the Axiom of Choice and so, while the proof establishes that finite values of N(d,k) exist, it is impossible, even in principle, to extract any quantitative bound.

Quantitative bounds are important because of the long-standing (and recently solved) question of whether the primes contain arbitrarily long arithmetic progressions. If one could show that a subset of {1,...,N} of size about N/log N contains long arithmetic progressions, then the result for the primes follows purely from the fact that the set of primes is dense enough.

There is a simple reduction that shows that, to prove Szemeredi's theorem over the integers, it is enough to prove it for the additive group ZN, with N prime. (That is, it is enough to look for arithmetic progressions mod N in {1,...,N} .) Also, if one looks at Roth's proof, it can be seen that it gives a much stronger bound in the additive group Fn3; in that setting, the proof shows that in every subset A of size about 3n/n there are three points in arithmetic progressions (that is, three points of the form a,a+b,a+b+b). The bound is of the form N/log N, where N is the size of the group. The proof, however, uses the fact that Fn3 is a linear space, that it has subspaces, and so on. Bourgain (1999) was able to "simulate" this proof in ZN by using the notion of "Bohr" set of ZN, and showing that it can play a role analogous to that of "subspace" in Fn3. Bourgain obtains a bound that is about N/sqrt(log N).

The great quantitative breakthrough came with the work of Gowers (1998-2001), who proved bounds of the form N/loglog N (as in Roth's proof) for progressions of any length. His work introduced the notion of Gowers uniformity I discussed two days ago.

So there are now three completely different proofs, Szemeredi's proof using graph theoretic arguments, Furstemberg's proof using Ergodic Theory, and Gowers's analytical proof. Recent work by Tao, however, shows that there are deep similarities between the proofs, although a complete "understanding" of what goes on is probably still to come.

There is also a new (2004-05) fourth proof, that uses a hypergraph regularity lemma, and that is similar in spirit to (but technically very different from, and simpler than) Szemeredi's proof. It also has deep relations with the the other three proofs. (See e.g. this paper.) It is an independent achievement of Nagle, Rödl, Schacht, and Skokan; Gowers; and Tao.

The most famous result on arithmetic progressions is probably the Green-Tao proof that the primes contain arbitrarily long arithmetic progressions.

The structure of the proof is quite amazing, and perhaps it contains ideas that could also be useful in computer science. They begin by defining a notion of pseudorandomness for sets of integers (which requires two conditions: Gowers uniformity and an additional properties). Then they show:

  1. Assuming Szemeredi's theorem as a black-box, the theorem is also true for subsets of pseudorandom sets. That is, if S is a large enough and pseudorandom enough set of integers, and A is a subset of A of constant density, then A must contain long arithmetic progressions. (Roughly speaking, a "distinguisher" that looks for arithmetic progressions cannot distinguish a dense subset of a pseudorandom set from a dense subset of all the integers. This is akin to the notion of "pseudo-entropy" in HILL, but the quantification is different.)

  2. The set of "pseudoprimes" (integers having only few, large, divisors) is pseudorandom in the integers. (This uses new results of Goldston and Yildirim.)

  3. The primes have constant density in the pseudoprimes.



Coming up next: Roth's proof for k=3, the structure of Gowers's proof for general k, the Green-Tao improvement for k=4, and the constellation of wonderful open questions around the k=3 and k=4 cases in finite vector spaces. (After that, back to politics, food, movies, and China.)

Thursday, June 01, 2006

Gowers uniformity

One of the three questions that were more frequently asked to me at STOC was why I did not define Gowers uniformity in my talk on this joint work with Alex Samorodnitsky. Is it because the definition is very complicated? Not at all, it is just that the definition seems very arbitrary unless one has the time to tell some stories about it and to look at a few equivalent versions of the definition and some of its basic properties.

My favorite source is this paper by Green and Tao; the first 6-7 sections are a wonderful review of what is known. Another great source is this survey paper by Green, that presents several open questions that could be of interest to us, especially the question of how large can a subset of F3n be so that no three points are on a line. (The big question is whether the asnwer is (3-o(1))n or not.) There is also a question related to "linearity testing," and I will probably talk about it in another post. Green has also written a more recent survey paper that is more limited in scope but that has more technical details.

In this post, I will tell a story about Gowers uniformity in the computer science language of linearity testing and low degree test for Boolean functions, which may be the gentlest introduction for many readers. I will almost exclusively refer to Boolean functions, but the theory applies more generally to bounded complex-valued functions whose domain is an Abelian group. (Some definitions/results, however, are more simply stated in the special case of Boolean functions.)

Umesh often complains that, during technical talks, the suspense kills him, meaning that the speaker goes on and on with technical definitions and results, without giving any indication of where he or she is going.

To spoil all suspense: the eventual goal is to have a "higher degree" Fourier analysis that allows us to talk about correlations of a given function with low-degree polynomials. (In contrast with Fourier analysis that, in the Boolean case, talks about correlations of a given function with linear functions.) For every fixed k, we will define a "dimension-k" norm for Boolean functions; such norms are conjectured to "approximate" the correlation of the function with the closest degree-(k-1) polynomial. The conjecture is a theorem for k=2 (by Fourier analysis) and for k=3 (by a tour de force), and it is open otherwise. What is known, however, is that functions with small norm have several useful "pseudorandomness" properties, and that functions with noticable large norm have useful "structure." (Low-degree-polynomial-like structure.) Most proofs that make use of Gowers uniformity have a two-part structure: if the norm is small, we get what we want from the pseudorandomness; if the norm is large, we get what we want from the structure. In our work on PCP, for example, when we analyse the soundness, we can argue that if the PCP proof is "pseudorandom" then the verifier is about as likely to accept it as it is to accept a random proof (hence, very low probability), but a PCP proof with "structure" can be "decoded" to a valid witness (hence, this cannot happen in the soundness case).

Let's get started with the definition. If
f:{0,1}n -> {0,1}

is a Boolean function, and y is an element of {0,1}n, let us define
fy (x) := f(x) - f(x+y)

where all operations are mod 2 (or bit-wise mod 2). We think of fy as a sort of "derivative" of f. In particular, if f is a constant then fy is identically 0 for every y, and if f is a degree-d polynomial then fy is a degree-(d-1) polynomial.

We also define fy,z as (fy)z, and so on.

Now, consider the following test of "non-constancy:" pick at random x,y, and check whether fy(x)=0. If f is a constant, then the test accepts with probability 1; it is also possible to argue that the test accepts with probability that is always at least 1/2, and that it accepts with probability 1/2+eps if and only if f has agreement 1/2 + eps' with a constant function.

This may not be too exciting, but consider the next "logical" step, that is, pick x,y,z at random, and check if fy,z(x)=0. If f is a degree-1 polynomial (an affine function), then the test accepts with probability 1. Also, it can be shown that the test accepts with probability at least 1/2. The interesting thing, which is easy to prove using Fourier analysis, is that the test accepts with probability noticeably larger than 1/2 if and only if f has agreement noticeably larger than 1/2 with a degree-1 function. Indeed, the test checks whether
f(x) - f(x+y) -f(x+z) + f(x+y+z)=0

and, up to a change of variables, this is the same as checking if
f(x) + f(y) +f(z) = f(x+y+z)

a slight variant of the Blum-Luby-Rubinfeld linearity test.

So you see where this is going: pick x,x1,...,xk at random and check if fx1,...,xk(x) =0. If f is a degree-(k-1) polynomial then the test accepts with probability 1.

Alon, Kaufman, Krivelevich, Litsyn and Ron proved in Random'03 that if the test accepts with probability 1-eps then f has agreement 1-O(2k eps) with a degree-(k-1) polynomial. Samorodnitsky, in a manuscript that predates our PCP work, proves the more challenging "low-end" result that, for k=3, if the test accepts with probability 1/2 + eps then the function has agreement 1/2 + eps' with a degree-2 polynomial.

The low-end result is open for k=4! Furthermore, for k=3, eps' is exponentially small in eps. It is an open question to have a polynomial dependency.

So, what about these Gowers uniformity norms? Take the probability that the test with x1...xk accepts, subtract 1/2 from the probability, and multiply by 2, so you get a number between 0 and 1. This is the dimension-k Gowers uniformity of f; Alex and I use the notation Uk(f). The 2kth root of the number I just described is the dimension-k Gowers uniformity norm of f, denoted ||f|| with subscript Uk (sorry, HTML does not allow subscripts of subscripts).

What's with this subtracting 1/2 and multiplying by 2 business? The analytical study of Boolean functions is often cleaner if we think of them as functions
f: {0,1}n -> {-1,1}

where bit b is replaced by bit (-1)b in the output. With this notation, we can define
fy (x) := f(x) * f(x+y)

and now the dimension-k uniformity can be given the following equivalent, but much cleaner, definition:
Uk (f) := Ex,x1,...,xk fx1...xk (x)

Now the advantage is that the definition can be applied to any real-valued function (which is often useful), not just Boolean functions. The 2kth root of Uk (f) is a norm for the space of real-valued functions of domain {0,1}n. The definitions extends to functions f: G-> R where G is any Abelian group (we just need to re-interpret the + in the definition) and R are the real numbers. The definition can also be extended to complex-valued functions, with a small change to the definition of fy.

With this notation, Alex proves that, for Boolean f, U3(f) is noticeably large if and only if f has noticeable correlation with a degree-2 polynomial. Green and Tao, in their 72-page paper I referenced above, prove an analogous result for bounded functions f:G->C where G is an Abelian group of order not divisible by 2 or by 3, and C are the complex number. (If the group contains a large cyclic subgroup, then it is quite messy to even state the theorem. If G is of the form Fnq where n is large compared with q, then the statement is simply about noticeable norm versus correlation with polynomials.)

And, to summarize again the hundreds of pages of mathematical knowledge we have about these norms, if the norm is small, the function is kind of pseudorandom; if the norm is not small, then the function is kind of "structured," in a way that sort of resembles a low-degree polynomial. It is open to turn "sort of resembles" into "is correlated with." (And it cannot be done if the domain of the function is a group with a large cyclic subgroup -- in that case, there are more complicated conjectures.)