The polymath blog

February 5, 2011

Polymath6: improving the bounds for Roth’s theorem

Filed under: polymath proposals — gowers @ 12:03 pm
About these ads


  1. [...] This post was mentioned on Twitter by Michael Druck, S.C. Kavassalis. S.C. Kavassalis said: Polymath6: improving the bounds for Roth’s theorem [...]

    Pingback by Tweets that mention Polymath6: improving the bounds for Roth’s theorem « The polymath blog -- — February 6, 2011 @ 2:41 am

  2. I have a fairly obvious question, which I think other people are likely to have thought about in detail, though I’m also tempted to think about it myself. Tom refers to the weakness of Bourgainization above, by which he means the fact that when you argue with regular Bohr sets, you have to take a “small” Bohr set inside the regular one, and eventually you pass down to that, which means that at each iteration the width of your Bohr set decreases. In some arguments, this is not a problem, but in others, when you have to iterate several times, it starts to affect bounds in a serious way. In particular, it explains why merely having the idea of replacing subspaces by Bohr sets is not enough to give a 1/\log N bound for Roth’s theorem.

    This is one of our main difficulties, since if one could just straightforwardly do that replacement, then we would have a straightforward dictionary from the Roth/Meshulam argument to a version in \mathbb{Z}_N, which would presumably make it straightforward to add on the Bateman-Katz improvement.

    One version of the question I would ask in response to that is a rather vague one: does the “weakness of Bourgainization” reflect a genuinely important difference between \mathbb{F}_3^n and \mathbb{Z}_N or does it reflect the weakness of the arguments we have so far thought of? In the rest of this comment, I’ll try to make this question more precise, though I don’t think I’ll succeed to the extent that I would ideally like.

    First of all, there obviously is a genuine difference between \mathbb{F}_3^n and \mathbb{Z}_N, which is that \mathbb{F}_3^n has lots of subgroups/subspaces and \mathbb{Z}_N doesn’t. Since I’m perfectly well aware of that, my task is to explain what I mean by this difference being important or not.

    As a first attempt at that, let me give a sense in which the difference might seem more important than it actually is. One nice feature of subspaces of \mathbb{F}_3^n is that they allow one to define averaging projections: given a subspace V and a function f defined on \mathbb{F}_3^n we define \pi_Vf by the formula \pi_Vf(x)=\mathbb{E}_{v\in V}f(x+v), which replaces the value at x by the average over the coset x+V. If B is a Bohr set, we can’t do this: it is not in general possible to partition \mathbb{Z}_N by translates of B, and even if one could, one would have to choose some translates and not others, a choice one does not have to make with subspaces. Nevertheless, there is a useful analogue of averaging projections, which is convolving with characteristic measures. That is, we define \pi_Bf by the formula \pi_Bf(x)=f*\mu_B(x)=\mathbb{E}_{y\in B}f(x+y). (The last equality relied on the fact that B=-B.) Note that we can define the averaging projection as \pi_V=f*\mu_V, so this is a direct generalization.

    When it comes to proving Roth’s theorem in \mathbb{F}_3^n, we pass to subspaces rather than taking averaging projections, so it starts to look as though it matters more that we are dealing with Bohr sets in \mathbb{Z}_N. But I can’t help wondering whether it might be possible to do something a bit cleverer that would allow one to get away with a smaller sacrifice of width.

    At this point, my thoughts get a little hazy, which is why I am asking whether anyone else has been down this road already and had clearer thoughts — either negative or positive. The sort of picture I have in my mind is something like this. Instead of passing to one Bohr set B, where it really is the case that if you pick a random point x\in B and then a difference d, you need d to belong to a much smaller Bohr set in order to be able to say that x+d probably belongs to B as well, could one do something like passing to an ensemble of Bohr sets inside which you have an ensemble of smaller Bohr sets, but this time with widths smaller by a constant factor, so that if you spill out of one Bohr set you find yourself in a neighbouring one?

    That’s just one suggestion that I haven’t thought about at all (I’m really trying to convey the type of thing I’d like to look for rather than the actual thing I’m looking for). But I can now try to rephrase my question about genuine importance. Does the fact that Bohr sets don’t have sharp boundaries, so to speak, really have a bearing on Roth’s theorem, or is just a technical irritant that we haven’t yet fully seen how to deal with?

    One final remark is this. It may seem as though by talking about averaging projections I am advocating an energy-incrementation argument rather than a passing-to-subspaces argument. But that isn’t exactly what I’m trying to do: I’m wondering whether there could be an argument that is global enough to avoid the severe edge-effects associated with Bohr sets, but local enough to have the advantages of the passing-to-subspaces approach.

    Comment by gowers — February 6, 2011 @ 11:00 am

  3. To be slightly more specific, perhaps instead of showing that the set correlates with Bohr sets, one could show that it correlates with non-negative Bohr-continuous functions or something like that. (There are various definitions one could give for this. A natural one would be to say that f is B-continuous if f\approx f*\mu_B.)

    I don’t think this actually works though, or at least not in any straightforward way. If you normalize such a function so that it becomes a probability measure \lambda, and you then try to exploit the fact that A contains no progression of length 3, the idea would be to argue that A\lambda has a small AP count as well, and that this would give bias with respect to a new trigonometric function. And the hope would be that if \lambda\approx\lambda*\mu_B, then B could play the role of the small Bohr set in the calculations rather than the large Bohr set. And then a suitable function built out of \lambda and the trigonometric function would become the new \lambda and a Bohr set built out of B and the new frequency would become the new B. And for some reason that I cannot see without doing calculations and have no convincing reason to expect, the width of B' would not have to be substantially smaller than the width of B.

    Comment by gowers — February 6, 2011 @ 2:39 pm

  4. One small question which occurs to me from the question of the limitation of Bourganisation above is whether being in a high dimensional Bohr set helps in the construction of three-term arithmetic progression-free sets or not. Specifically, can one construct a set A \subset [N]^d, free of proper three-term progressions, with A larger than the Behrend bound. It’s not clear to me that it helps at all given that the lower bounds for r_3(\mathbb{F}_3^n) are worse than r_3(3^n) but it would be some evidence of a genuine difference between Bohr sets and subspaces.

    I suppose that there are high-dimensional progressions (rather than Bohr sets) which contain large three-term progression free sets. Indeed, \{0,1\}^n in \mathbb{F}_5^n is a d-dimensional progression containing no proper three-term progressions…

    Comment by Tom — February 6, 2011 @ 3:04 pm

  5. A somewhat related remark is this. I think the problem with the kind of proposal I suggested in comment 2 is that one has to show that the B-continuous function \lambda “ought” to contain several APs of length 3. But the only ones that it seems to have to have are “local” ones, where you have a common difference belonging to B.

    But perhaps that is where the gain is: our common difference would be in B rather than in a Bohr set of much smaller width. In the course of writing this comment I have ceased to feel that I can see either that there is a problem or that there isn’t a problem. But I agree with you Tom that once one has got to the stage of considering a Bohr set of dimension d, one is morally living in a d-dimensional lattice, so if there is some sense in which the bounds for Roth are weaker in d dimensions than they are in one dimension, then there would appear to be a genuinely important difference between \mathbb{Z}_N and \mathbb{F}_3^n.

    Comment by gowers — February 6, 2011 @ 3:18 pm

  6. WIth regard to the comments on Bohr sets above, I think it’s important to distinguish two reasons why one passes to Bohr sets of smaller “width”. In my opinion one (1) is really crucial: the fact that we want a situation that is roughly closed under addition, thus for example $B + B’ \approx B$ if $B’$ has much smaller width than $B$. This “approximate group” property is completely vital and it does not hold for the Bohr set $B$ by itself, where $B + B \sim 2^d B$. The second reason (2) for passing to smaller Bohr sets is one that Tim mentions above – Bohr sets can have nasty “edge effects”, so one needs to work with so-called “regular” Bohr sets. My feeling – one that I think Tom will back up – is that for the purposes of this discussion we should just assume that all Bohr sets are regular.

    To summarise, then: (1) is a really serious conceptual point, and (2) is a technical irritant that can always be bypassed in practice.

    Comment by Ben Green — February 6, 2011 @ 4:57 pm

  7. In our offline email exchanges I mentioned that we probably “should” be working in $[N]$ rather than in $Z/NZ$, my reasoning being that the group structure in the latter is a bit artificial (some progressions are not “real” progressions). Now I’ve thought about it a bit more, I don’t mind working in $Z/NZ$ so much. The thing is that there one can talk about “the set of large Fourier coefficients”, something that Bateman and Katz are doing all the time, rather than looking at sets of $1/100 N$-separated Fourier coefficients on the circle $R/Z$ or something like that. Of course this is all a matter of finding a good language to talk in and there is no genuine mathematical gain to be made from working in one or the other setting (so far as I know).

    OK, enough from me. I plan to try and present one or two lemmas from Bateman Katz in the way that I like to understand things. I know other people (for example Tim) are doing the same, and fully concur with him that this should be helpful despite the inevitable duplication of effort.

    Comment by Ben Green — February 6, 2011 @ 5:02 pm

  8. Responding to comment 7: I just want to clarify that the thought I was floating in comment 3 was that if we want approximate closure under addition, we don’t necessarily have to have a pair of Bohr sets B and B’ with B’ smaller than B. Instead, we could have a single Bohr set B and a probability measure \lambda about which we know nothing other than that \lambda*\mu_B\approx\lambda. Thus \lambda would be “approximately closed under B-addition”.

    I’m not claiming that that actually works, or that if it does then it gives better bounds for anything. But I do want to think about it a little unless someone can persuade me in advance that it’s not worth the bother.

    Comment by gowers — February 6, 2011 @ 5:40 pm

  9. [...] the bounds for Roth’s theorem. See this post. Also there is a page on the polymath blog here. There is also a wiki here. Also see this post and this [...]

    Pingback by Polymath6 « Euclidean Ramsey Theory — February 6, 2011 @ 9:58 pm

  10. Hi all,

    I am interested in the project of getting useful physical space information from large Fourier coefficients.
    If this can’t be done for one coefficient as in the cap-set question, perhaps can the presence of many large
    coefficients help? What would constitute a counterexample convincing us that such an approach is futile?

    One way I imagined being helpful at this stage was to write some notes helping to explain our argument. I see
    you have a wiki for this, but I don’t have the appropriate permissions to modify it. I’ve noticed that
    several of you plan on contributing to it and don’t want to step on your toes.

    However let me know if an outline of the argument in section 6 and a description of some examples that necessitate
    the difficulties might be helpful.


    Comment by Nets Katz — February 7, 2011 @ 2:53 am

    • Hi Nets,

      I created some sections on the wiki for your paper with Bateman and started to add some content based on the discussions we had last week. I don’t want this to dissuade anyone from writing different takes on whatever I have added, however. Indeed, I imagine having several different perspectives on things will be very useful. So please don’t worry about the stepping on of toes on my account.

      I think you should be able to create an account on the wiki yourself; at least there is a link towards the top right of the site that gives that impression.


      Comment by Olof Sisask — February 7, 2011 @ 6:06 am

      • Olof,

        Thanks. I’m not very experienced with wikis.


        Comment by Nets Katz — February 7, 2011 @ 6:13 am

  11. I would like to join this project. Unfortunately, I don’t know much about Bohr sets yet, which may be something of a handicap. However, I have researched the cap-set problem a little, and have come up with an idea for a computer experiment to test the finite-field heuristic by comparing \mathbb{F}_3^n against (\mathbb{Z}/3 \mathbb{Z})^n for \Lambda(1_A), which I have described in a blog post here. Obviously though, I am far from certain whether data from such an experiment would be of interest, so feedback on that would be welcome.

    Comment by Paul Delhanty — February 7, 2011 @ 6:04 pm

    • Could I ask what the difference is between \mathbb{F}_3 and \mathbb{Z}/3\mathbb{Z} in what you write?

      Comment by gowers — February 7, 2011 @ 7:06 pm

      • Regarding your very reasonable question, you are of course correct that there is no difference between {{\mathbb F}_3} and {{\mathbb Z}/3{\mathbb Z}}. I stupidly wrote {{{\mathbb Z}/3{\mathbb Z}}^n} when I was thinking of {{{\mathbb Z}/3^n{\mathbb Z}}}, and then copied the LaTeX for my mistake all over my blog post. Accordingly, I have updated to refer to {{{\mathbb Z}/3^n{\mathbb Z}}}, which is what I meant. So for clarity, I am proposing to compare {{\mathbb F}_3^n} against {{{\mathbb Z}/3^n{\mathbb Z}}}, obtaining frequency counts for possible values of {\Lambda(1_A) - P_G(A)^3} at each density level-set in the power set of {[3^n]}.

        I don’t think that I have explained very well why I find the experiment interesting. Certainly, I can update my rather rushed blog post with a clearer explanation. However, even if I explain that clearly, I am far from confident that the experimental data would be of wider interest. If the experiment is of interest, then I can move material to this blog or to the wiki. On the other hand, if the experiment is not of interest, I still feel honour bound to complete the experiment before moving on.

        Comment by Paul Delhanty — February 8, 2011 @ 5:14 am

  12. [...] Gowers very reasonably asked here “Could I ask what the difference is between and and in what you write?” The answer is [...]

    Pingback by Polymath6: thoughts on empirically testing the finite-field heuristic for very low ‘n’ « Paul Delhanty — February 8, 2011 @ 4:51 am

  13. This comment is a reply to comment 2 and the need to pass to subspaces rather than taking averaging projections when proving Roth’s theorem for {{\mathbb F}_3^n}.

    I have dug out a sketch of an alternative proof of Lemma 10.15 (Non-uniformity implies density increment) from Tao & Vu that uses the dual form of the Poisson summation formula (essentially taking averaging projections). Seeing as Lemma 10.15 is used when passing to a subspace, might it be possible to unpack my proof somehow and then replace {\pi_V f} by {\pi_B f} for the Bohr set case? The proof also improves the constant in Lemma 10.15 from 1/2 to {\sqrt 2}, which makes me quite nervous that I have made a silly mistake. However, I am going to post the proof anyway in case something can be salvaged from the idea.

    Lemma 10.15 + improved constant:

    Write Z as a shorthand for {{\mathbb F}_p^n}. Let {f: Z \rightarrow {\mathbb R}} be a function with mean zero. Then there exists a codimension 1 subspace V of Z and a point {x_0 \in Z}, such that

    \displaystyle \mathop{\mathbb E}_{y \in x_0+V} f(y) \geq \sqrt 2 ||f||_{u^2(Z)}

    Sketch of proof:

    Choose {\xi \in Z} such that {|\hat f(\xi)| = ||f||_{u^2(Z)}}.

    Let W be the dimension 1 Fourier subspace generated by {\xi} and let V be the orthogonal complement of {\xi}. Let {h := \pi_V f}.

    By the dual form of the Poisson Summation formula (Exercise 4.1.7 in Tao & Vu) {\hat h = \hat f . 1_W}.

    From the Parseval identity and the fact that {f} is real valued:

    \displaystyle \mathop{\mathbb E}_{x \in Z} |h(x)|^2 = \sum_{\zeta \in Z} |\hat h(\zeta)|^2 \geq |\hat f(\xi)|^2 + |\hat f(-\xi)|^2 = 2 ||f||_{u^2(Z)}

    The result follows from the fact that {h} is constant on codimension 1 affine subspaces and the pigeonhole principle.

    Comment by Paul Delhanty — February 9, 2011 @ 3:40 am

    • Because the required bound on {\mathop{\mathbb E}_{y \in x_0+V} f(y)} is signed, I have concluded that my proof is broken at the last point where I invoked the pigeonhole principle on {\mathop{\mathbb E}_{x \in Z} |h(x)|^2}. At that point it is necessary to choose a phase as is done in Tao &Vu. I think that the proof may be able to be salvaged, but the constant would not {\sqrt 2}. That would still leave the core idea intact though.

      Comment by Paul Delhanty — February 9, 2011 @ 6:48 am

    • The problem with using the U_2 norm (which would seem to be a very natural thing to do) is that the nonexistence of APs in a set A provides a bound on the U_2 norm of the balanced function of A that results, after the above argument, in a weaker density increment than you get if you use a Fourier expansion: the \ell_\infty norm is what you care about if you are looking for a density increment, so you lose information if you use the \ell_4 norm.

      Comment by gowers — February 9, 2011 @ 8:01 am

RSS feed for comments on this post.

The Rubric Theme. Blog at


Get every new post delivered to your Inbox.

Join 245 other followers

%d bloggers like this: