The polymath blog

February 5, 2011

Polymath6: improving the bounds for Roth’s theorem

Filed under: polymath proposals — gowers @ 12:03 pm

For the time being this is an almost empty post, the main purpose of which is to provide a space for mathematical comments connected with the project of assessing whether it is possible to use the recent ideas of Sanders and of Bateman and Katz to break the 1/\log N barrier in Roth’s theorem. (In a few hours’ time I plan to write a brief explanation of what one of the main difficulties seems to be.)

Added later. Tom Sanders made the following remarks as a comment. It seems to me to make more sense to have them as a post, since they are a good starting point for a discussion. So I have taken the liberty of upgrading the comment. Thus, the remainder of this post is written by Tom.


This will hopefully be an informal post on one aspect of what we might need to do to translate the Bateman-Katz work into the \mathbb{Z}/N\mathbb{Z} setting.

One of the first steps in the Bateman-Katz argument is to note that if A \subset \mathbb{F}_3^n is a cap-set (meaning it is free of three-term progressions) of density \alpha then we can assume that there are no large Fourier coefficients, meaning

\sup_{0_{\widehat{G}}\neq\gamma \in \widehat{\mathbb{F}_3^n}}{|\widehat{1_A}(\gamma)|} \leq C\alpha/n.

They use this to develop structural information about the large spectrum, \rm{Spec}_{\Omega(\alpha)}(1_A), which consequently has size between \Omega(C^{-3}n^3) and O(\alpha^{-3}). This structural information is then carefully analysed in the `beef’ of the paper.

To make the assumption there are no large Fourier coefficients they proceed via the usual Meshulam argument: if there is a large coefficient then we get a density increment of the form \alpha \mapsto \alpha(1+\Omega(Cn)) on a subspace of co-dimension 1 and this can be iterated until they have all been removed. In the \mathbb{Z}/N\mathbb{Z} setting this has to be `Bourgainised’.

We proceed relative to Bohr sets rather than subspace. The problem with Bohr sets is that they do not function exactly as subspaces and, in particular, they do not have a nice additive closure property. A good model to think of is the unit cube Q in \mathbb{R}^d. The sumset Q+Q is not roughly equal to Q; it is about 2^d times as large as Q. However, if we take some small dilate Q' of Q, say the cube of side length \delta then we do have that Q+Q' \approx Q since \mu_G(Q+Q') = \mu_G(Q)(1+O(d\delta)). This provide a sort of approximate additive closure, and the fact that it can be usefully extended to Bohr sets and used for Roth’s theorem was usefully notice by Bourgain in his paper `On triples in arithmetic progression‘.

In our situation, if B is a Bohr set of dimension d, and A \subset B has relative density \alpha then we shall try to remove all characters \gamma such that |(1_A - \alpha1_B)^\wedge(\gamma)| =\Omega(C\alpha/\log N). Given such a character we produce a new Bohr set B' defined to be the intersection of B (dilated by a factor of \alpha^{O(1)}) and the \alpha^{O(1)}-approximate level set of \gamma (meaning the set of x such that |\gamma(x)-1| \leq \alpha^{O(1)}) with

\rm{width}(B') \geq \alpha^{O(1)}\rm{width}(B) \textrm{ and } \rm{dim} B' \leq \rm{dim} B + 1

and A has density \alpha(1+\Omega(C\log N)) on a translate of B'. After running this for at most O(C^{-1}\log N) iterations we end up with a Bohr set B such that

\rm{width}(B) \geq \alpha^{O(C^{-1}\log N)} \textrm{ and } \rm{dim} B = O(C^{-1}\log N).

However, the only lower bound we have on the size of a Bohr set B in a general Abelian group is \mu_G(B) \geq \rm{width}(B)^{\rm{dim} B}, which means we have to take C=\Omega(\sqrt{(\log\alpha^{-1})(\log N)}) or else our Bohr sets will become too small. Of course, in \mathbb{F}_3^n the width plays (essentially) no role in determining the size of the Bohr set and we have \mu_G(B) \geq  3^{-\rm{dim} B} and we can take C=O(1) as desired for the Bateman-Katz analysis.

Having seen this weakness of `Bourgainisation’ one naturally wants to look for arguments which somehow involve iterating a smaller number of times: if we had been able to take many Fourier coefficients together each time we passed to a new Bohr set we would not have had to iterate, and therefore narrow, the Bohr set so many times. In fact Heath-Brown and Szemeredi in their papers `Integer sets containing no arithmetic progressions‘ and `Integer sets containing no arithmetic progressions‘ provided such.

The key idea of the Heath-Brown-Szemeredi approach in the Bohr set context is to intersect the dilate of the Bohr set B with the \alpha^{O(1)}-approximate level set of all the characters in the large spectrum \rm{Spec}_{\Omega(C/\log N)}(1_A). This set has size at most O(C^{-2}\alpha ^{-1}\log^2 N) by Parseval’s theorem and so we get a Bohr set B' with

\rm{ width}(B') \geq \alpha^{O(1)}\rm{ width}(B) \textrm{ and } \rm{dim} B' \leq \rm{dim} B + O(C^{-2}\alpha ^{-1}\log^2 N).

However, in this case we end up with a much bigger density increment. Indeed, \widehat{\beta'}(\gamma) \approx 1 for all \gamma \in \rm{Spec}_{\Omega(C/\log N)}(1_A) from which we essentially get that

\sum_{\gamma}{|\widehat{1_A}(\gamma)|^2|\widehat{\beta'}(\gamma)|^2} \geq \alpha^2(1+\Omega(1))\mu_G(B).

This translates to a density increment of \alpha \mapsto \alpha(1+\Omega(1)) and such an increment can only be iterated O(\log \alpha^{-1}) times — that is to say not very many times. Unfortunately even when combined with Chang’s theorem this does not give an improvement over Bourgain’s original argument and it wasn’t until 2008 that Bourgain produced a new argument improving our understanding in `Roth’s theorem on progressions revisited‘.

In this sequel a more careful analysis of the large spectrum is produced and this benefits from knowing whether or not \rm{Spec}_{\Omega(C/\log N)}(1_A) contains most of the Fourier mass in \rm{Spec}_{\Omega(\alpha)}(1_A) or not. The point here is that we are given by the usual Fourier arguments that \rm{Spec}_{\Omega(\alpha)}(1_A) supports a large Fourier mass. Now, if C/\log N is somewhat bigger than \alpha then it is a stronger statement to say that \rm{Spec}_{\Omega(C/\log N)}(1_A) contains most of the Fourier mass. If it does then our plan might be to run one of the known Roth arguments; if it doesn’t then \rm{Spec}_{\Omega(\alpha)}(1_A) \setminus \rm{Spec}_{\Omega(C/\log N)}(1_A) is large and we can hope to run the Bateman-Katz argument.

Hopefully I’ll talk more about Bourgain’s method which gives r_3(N) = O(N/\log^{2/3-o(1)}N) (and a slight refinement which gives r_3(N) = O(N/\log^{3/4-o(1)}N)) because these along with Bourgain’s original approach can all make use of the fact that \rm{Spec}_{\Omega(C/\log N)}(1_A) is large, rather than simply the statement that A has no non-trivial three-APs (which is stronger). One of the problems we face is that naively the proof giving r_3(N) = O(N/\log^{1-o(1)}N) cannot make use of the fact that \rm{Spec}_{\Omega(C/\log N)}(1_A) is large unless this can be converted into a meaningful physical space statement.

I did wonder if there was some slight hope that the \epsilon in the Bateman-Katz result would be sufficiently large, say bigger than 1/4, that it could be combined with the r_3(N) = O(N/\log^{3/4-o(1)}N) argument to give an improvement. This seems unlikely as I am told \epsilon is rather small.

About these ads

19 Comments

  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 http://bit.ly/h1MzzB [...]

    Pingback by Tweets that mention Polymath6: improving the bounds for Roth’s theorem « The polymath blog -- Topsy.com — 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.

    Nets

    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.

      Olof

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

      • Olof,

        Thanks. I’m not very experienced with wikis.

        Nets

        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. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 246 other followers

%d bloggers like this: