An observation that has been made many times is that the internet is a perfect place to disseminate mathematical knowledge that is worth disseminating but that is not conventionally publishable. Another observation that has been made many times is that either of the following features can render a piece of mathematics unpublishable, even if it could be useful to other mathematicians.
1. It is not original.
2. It does not lead anywhere conclusive.
A piece of unoriginal mathematical writing can be useful if it explains a known piece of mathematics in a new way (and “new” here does not mean radically original — just a slightly different slant that can potentially appeal to a different audience), or if it explains something that “all the experts know” but nobody has bothered to write down. And an inconclusive observation such as “This proof attempt looks promising at first, but the following construction suggests that it won’t work, though unfortunately I cannot actually prove a rigorous result along those lines,” can be very helpful to somebody else who is thinking about a problem.
I’m mentioning all this because I have recently spent a couple of weeks thinking about the cap-set problem, getting excited about an approach, realizing that it can’t work, and finally connecting these observations with conversations I have had in the past (in particular with Ben Green and Tom Sanders) in order to see that these thoughts are ones that are almost certainly familiar to several people. They ought to have been familiar to me too, but the fact is that they weren’t, so I’m writing this as a kind of time-saving device for anyone who wants to try their hand at the cap-set problem and who isn’t one of the handful of experts who will find everything that I write obvious.
Added a little later: this post has taken far longer to write than I expected, because I went on to realize that the realization that the approach couldn’t work was itself problematic. It is possible that some of what I write below is new after all, though that is not my main concern. (It seems to me that mathematicians sometimes pay too much attention to who was the first to make a relatively simple observation that is made with high probability by anybody sensible who thinks seriously about a given problem. The observations here are of that kind, though if any of them led to a proof then I suppose they might look better with hindsight.) The post has ended up as a general discussion of the problem with several loose ends. I hope that others may see how to tie some of them up and be prepared to share their thoughts. This may sound like the beginning of a Polymath project. I’m not sure whether it is, but discuss the possibility at the end of the post.
Statement of problem.
First, a quick reminder of what the cap-set problem is. A cap-set is a subset of \(\mathbb{F}_3^n\) that contains no line, or equivalently no three distinct points \(x,y,z\) such that \(x+y+z=0,\) or equivalently no non-trivial arithmetic progression \(a,a+d,a+2d.\) (Why it has this name I don’t know.) The problem is the obvious one: how large can a cap-set be? The best-known bound is obtained by a straightforward adaptation of Roth’s proof of his theorem about arithmetic progressions of length 3, as was observed by Meshulam. (In fact, the argument in \(\mathbb{F}_3^n\) is significantly simpler than the argument in \(\mathbb{N},\) which is part of the reason it is hard to improve.) The bound turns out to be \(C3^n/n.\) That is, the density you need, \(C/n,\) is logarithmic in the cardinality of \(\mathbb{F}_3^n.\) This is why many people are interested in the problem of improving the bound for the cap-set problem: if one could, then there are standard techniques that often work for modifying the proof to obtain a bound for Roth’s theorem, and that bound would probably be better than \(1/\log n\) (at least if the improvement in the cap-set problem was reasonably substantial). And that would solve the first non-trivial case of Erdős’s conjecture that if \(\sum_{n\in X}n^{-1}=\infty\) then \(X\) contains arithmetic progressions of all lengths.
If you Google “cap set problem” you will find other blog posts about it, including Terence Tao’s first (I think) blog post and various posts by Gil Kalai, of which this is a good introductory one.
Sketch of proof.
Next, here is a brief sketch of the Roth/Meshulam argument. I am giving it not so much for the benefit of people who have never seen it before, but because I shall need to refer to it. Recall that the Fourier transform of a function \(f:\mathbb{F}_3^n\to\mathbb{C}\) is defined by the formula
\(\hat{f}(r)=\mathbb{E}f(x)\omega^{r.x},\)
where \(\mathbb{E}\) is short for \(3^{-n}\sum,\) \(\omega\) stands for \(\exp(2\pi i/3)\) and \(r.x\) is short for \(\sum_ir_ix_i.\) Now
\(\mathbb{E}_{x+y+z=0}f(x)f(y)f(z)=f*f*f(0).\)
(Here \(\mathbb{E}\) stands for \(3^{-2n}\sum,\) since there are \(3^{2n}\) solutions of \(x+y+z=0.\)) By the convolution identity and the inversion formula, this is equal to \(\sum_r\hat{f}(r)^3.\)
Now let \(f\) be the characteristic function of a subset \(A\subset\mathbb{F}_3^n\) of density \(\delta.\) Then \(\hat{f}(0)=\delta.\) Therefore, if \(A\) contains no solutions of \(x+y+z=0\) (apart from degenerate ones — I’ll ignore that slight qualification for the purposes of this sketch as it makes the argument slightly less neat without affecting its substance) we may deduce that
\(\sum_{r\ne 0}|\hat{f}(r)|^3\geq\delta^3.\)
Now Parseval’s identity tells us that
\(\sum_r|\hat{f}(r)|^2=\mathbb{E}_x|f(x)|^2=\delta,\)
from which it follows that \(\max_{r\ne 0}|\hat{f}(r)|\geq\delta^2.\)
Recall that \(\hat{f}(r)=\mathbb{E}_xf(x)\omega^{r.x}.\) The function \(x\mapsto\omega^{r.x}\) is constant on each of the three hyperplanes \(r.x=b\) (here I interpret \(r.x\) as an element of \(\mathbb{F}_3\)). From this it is easy to show that there is a hyperplane \(H\) such that \(\mathbb{E}_{x\in H}f(x)\geq\delta+c\delta^2\) for some absolute constant \(c.\) (If you can’t be bothered to do the calculation, the basic point to take away is that if \(\hat{f}(r)\geq\alpha\) then there is a hyperplane perpendicular to \(r\) on which \(A\) has density at least \(\delta+c\alpha,\) where \(c\) is an absolute constant. The converse holds too, though you recover the original bound for the Fourier coefficient only up to an absolute constant, so non-trivial Fourier coefficients and density increases on hyperplanes are essentially the same thing in this context.)
Thus, if \(A\) contains no arithmetic progression of length 3, there is a hyperplane inside which the density of \(A\) is at least \(\delta+c\delta^2.\) If we iterate this argument \(1/c\delta\) times, then we can double the (relative) density of \(A.\) If we iterate it another \(1/2c\delta\) times, we can double it again, and so on. The number of iterations is at most \(2/c\delta,\) so by that time there must be an arithmetic progression of length 3. This tells us that we need lose only \(2/c\delta\) dimensions, so for the argument to work we need \(n\geq 2/c\delta,\) or equivalently \(\delta\geq C/n.\)
Can we do better at the first iteration?
There is a very obvious first question to ask if one is trying to improve this argument: is the first iteration best possible? That is, is a density increase from \(\delta\) to \(\delta+c\delta^2\) the best we can do if we are allowed to restrict to a hyperplane?
There is an annoying difficulty with this question, which is that the answer is trivially no if there do not exist sets of density \(\delta\) that contain no arithmetic progressions. So initially it isn’t clear how we would prove that \(\delta+c\delta^2\) is the best increase we can hope for.
There are two potential ways round this difficulty. One, which I shall adopt here, is to observe that all we actually used in the proof was the fact that \(\sum_{r\ne 0}|\hat{f}(r)|^3\geq c\delta^3.\) So we can ask whether there are sets of density \(\delta\) that satisfy this condition and also the condition that \(\max_{r\ne 0}|\hat{f}(r)|\leq C\delta^2.\) The other is to observe that a similar density increase can be obtained even if we look for solutions to \(x+y+z=0\) with \(x\in A,\) \(y\in B\) and \(z\in C\), where \(A, B\) and \(C\) are not assumed to be the same set. Now it becomes easy to avoid such solutions and keep the sets dense. If we do so, can we obtain a bigger density increase than the argument above (appropriately modified) gives? This again has become a question that makes sense.
The following simple example disposes of the first question. Let \(k=\log_3(1/\delta^3),\) let \(B\) be a random subset of \(\mathbb{F}_3^{k}\) of density \(\delta,\) and let \(A\) be the set of all \(x\in\mathbb{F}_3^n\) such that their first \(k\) coordinates form a vector in \(B.\) Then \(A\) has density \(\delta.\)
Let \(f\) be the characteristic function of \(A.\) Then it is not hard to prove that \(\hat{f}(r)=0\) unless \(r\) is supported in the first \(k\) coordinates. If this is the case, then as long as \(r\ne 0,\) the typical value of \(|\hat{f}(r)|\) is around \(\delta^{1/2}3^{-k/2},\) or around \(\delta^2.\) It follows (despite the sloppiness of my argument) that \(\sum_{r\ne 0}|\hat{f}(r)|^3\) is around \(\delta^{-3}\delta^6=\delta^3.\)
If we could say that the typical value of \(|\hat{f}(r)|\) was roughly its maximum value, then we would be done. This is true up to logarithmic factors, so this example is pretty close to what we want. If one wishes for more, then one can choose a set that is “better than random” in the sense that its Fourier coefficients are all as small as they can be. A set that will do the job is \(\{x:x_1^2+\dots+x_k^2=0\}.\) (That sum is of course mod 3.) Again, the details are not too important. What matters is that there are sets with the “wrong number” of arithmetic progressions, such that we cannot increase their density by all that much by passing to a codimension-1 affine subspace of \(\mathbb{F}_3^n.\)
Taking a bigger bite.
This is the point where I had one of those bursts of excitement that seems a bit embarrassing in retrospect when one realizes not only that it doesn’t work but also that other people would be surprised that you hadn’t realized that it didn’t work. But I’ve had enough of that kind of embarrassment not to mind a bit more. The little thought I had was that in the example above, even though there are no big density increases on codimension-1 subspaces, there is a huge density increase on a subspace of codimension \(3\log_3(1/\delta).\) Indeed, the density increases all the way to 1.
I quickly saw that that was too much to hope for in general. A different example that does something similar is to take a random subset \(B\) of \(\mathbb{F}_3^k,\) (that is, with each element chosen with probability \(1/2\)), to take \(C\) to be the set of \(x\) with first \(k\) coordinates forming a vector in \(B,\) and to let \(A\) be a random subset of \(C\) of density \(\delta\) (in \(\mathbb{F}_3^n,\) so each element of \(C\) is put into \(A\) with probability \(2\delta\)). This set turns out to have a fairly similar size distribution for the squares and cubes of its Fourier coefficients, but now we cannot hope for a density increase to more than \(2\delta\) even if we pass to a subspace of codimension \(\log(1/\delta).\)
But that would be pretty good! We could iterate this process \(\log(1/\delta)\) times and get to a density of 1, losing \(\log(1/\delta)\) dimensions each time. That would require \(n=(\log(1/\delta))^2,\) which would correspond to the best known lower bound for Roth’s theorem.
I won’t bore you with too much detail about the plans I started to devise for proving something like this. The rough idea was this: for each codimension-\(k\) subspace \(V,\) define \(P_V\) to be the averaging projection that takes \(f\) to \(g,\) where \(g(x)=\mathbb{E}_{y\in V}f(x+y).\) (The characteristic measure \(\mu_V\) of \(V\) is defined to be the unique function that is constant on \(V\) and zero outside \(V,\) and that averages 1. The projection \(P_V\) takes \(f\) to \(f*\mu_V.\)) Then I was trying expanding \(f\) in terms of its projections \(P_Vf.\) It turns out that one can obtain expressions for the number of arithmetic progressions, and also a variant of Parseval’s identity. What I hoped to do was find a way to show that if we take \(k=C\log(1/\delta),\) we can prove that there is some \(V\) such that \(\|\delta\mathbf{1}-P_Vf\|_2^2\) has order of magnitude \(\delta^2,\) from which it follows straightforwardly that there is a density increase of order of magnitude \(\delta\) on some coset of \(V.\)
But how would such a result be proved? I had a few ideas about this, some of which I was getting pretty fond of, and as I thought about it I found myself being drawn inexorably towards an inequality of Chang.
Chang’s inequality.
It is noticeable that in the example that provoked this proof attempt, the large Fourier coefficients \(\hat{f}(r)\) all occurred inside a low-dimensional subspace. Conversely, if that is the case, it is not too hard to prove that there is a nice large density increase on a small-codimensional subspace.
This suggests a line of attack: try to show that the only way that lots of Fourier coefficients can be large is if they all crowd together into a single subspace. A good enough result like that would enable one to drop down by more than one dimension, but not too many dimensions, and make a greater gain in density than is possible if one repeatedly drops down by one dimension and uses the best codimension-1 result at each step.
There is good news and bad news here. The good news is that there is a result of precisely this type due to Mei-Chu Chang: she shows that the large spectrum (that is, the set of \(r\) such that \(\hat{f}(r)\) is large) cannot contain too large an independent set. (Actually, her result concerns so-called dissociated sets, but in the \(\mathbb{F}_3^n\) context that means linearly independent.) The bad news is that the bound that comes out of her result does not yield any improvement to the bound for the cap-set problem: up to logarithmic factors, the number of linearly independent \(r\) for which \(\hat{f}(r)\) can have size \(\delta^2\) is around \(\delta^{-2}\), and even if we could somehow use that information to deduce that \(A\) has density 1 in a codimension-\(\delta^{-2}\) subspace, we would end up proving a bound of \(n^{-1/2}\) for the density needed to guarantee an arithmetic progression, which is considerably worse than one obtains from the much simpler Roth/Meshulam argument.
Let me briefly state (a slight simplification of) Chang’s inequality in the \(\mathbb{F}_3^n\) context. If \(A\) is a set of density \(\delta\) with characteristic function \(f,\) then for any \(\rho\) the largest possible independent set of \(r\) such that \(|\hat{f}(r)|\geq\rho\delta\) has size at most \(\rho^{-2}\log(\delta^{-1}).\)
For comparison, note that Parseval’s identity tells us that the number of \(r\) with \(|\hat{f}(r)|\geq\rho\delta\) cannot be more than \(k,\) where \(k\rho^2\delta^2=\delta\), which gives us a bound of \(\rho^{-2}\delta^{-1}\) without the linear independence assumption.
Later we’ll think a little bit about the proof of Chang’s inequality, but first let us get a sense of how close or otherwise it comes to allowing us to improve on the bounds for the cap-set problem.
How might the structure of the large spectrum help us?
In this short section I will make a couple of very simple observations.
First of all, suppose that \(A\) is a set of density \(\delta\) that contains no non-trivial arithmetic progression of length 3. Let \(f\) be the characteristic function of \(A.\) Then as we have seen, \(\sum_{r\ne 0}|\hat{f}(r)|^3\geq\delta^3.\) (That isn’t quite accurate, but it almost is, and it’s fine if we replace the bound by \(\delta^3/2,\) say, which would not affect the arguments I am about to give.)
Now let us do a dyadic decomposition. For each positive integer \(k,\) let \(E_k\) be the set of all non-zero \(r\) such that \(2^{-k}\delta<|\hat{f}(r)|<2^{-(k-1)}\delta.\) Then there are a few easy facts we can write down. First of all, by Parseval’s identity, \(|A_k|2^{-2k}\delta^2\leq\delta,\) from which it follows that \(|A_k|\leq 2^{2k}\delta^{-1}.\) Secondly, the contribution to the sum \(\sum_r|\hat{f}(r)|^3\) from \(r\) such that \(|\hat{f}(r)|\leq \delta^2/4\) is, by Parseval again, at most \((\delta^2/4)\delta=\delta^3/4.\) Thirdly, by the bound on the sum of the cubes of the Fourier coefficients, we have that
\(\delta^3/2\leq 8\sum_k|A_k|2^{-3k}\delta^3.\)
From this and the previous observation it follows that there exists \(k\) such that \(|A_k|\geq c2^{3k}/\log(1/\delta)\) for some absolute constant \(c.\)
Thus, up to log factors (in \(1/\delta\)), there exists \(\rho\geq\delta\) such that the number of \(r\) with \(|\hat{f}(r)|\geq\rho\delta\) is \(\rho^{-3}.\) This is a strengthening of the statement used by Roth/Meshulam, which is merely that there exists some \(r\) with \(|\hat{f}(r)|\geq\delta^2.\)
In combination with Chang’s theorem, and again being cavalier about log factors, this tells us that we have around \(\rho^{-3}\) values of \(r\) such that \(|\hat{f}(r)|\geq\rho\delta,\) and they all have to live in a subspace of dimension at most \(\rho^{-2}.\) So the obvious question now is this: can we somehow exploit the fact that the large spectrum lies inside some lowish-dimensional subspace?
A quick point to make here is that if all we want is some improvement to the Roth/Meshulam bound, then we can basically assume that \(\rho=\delta,\) since any larger value of \(\rho\) would allow us to drop a dimension in return for a larger density increase than the Roth/Meshulam argument obtains. However, let me stick with a general \(\rho\) for now.
If there are \(\rho^{-3}\) values of \(r,\) all living in a \(\rho^{-2}\)-dimensional subspace \(V,\) such that \(|\hat{f}(r)|\geq\rho\delta\) for each one, then \(\sum_{s\in V}|\hat{f}(s)|^2\geq\rho^{-3}\rho^2\delta^2=\rho^{-1}\delta^2.\) Therefore, the pointwise product of \(\hat{f}\) with the characteristic function of \(V\) has \(\ell_2\)-norm squared equal to \(\rho^{-1}\delta^2.\) It follows that the convolution of \(f-\delta\) with the characteristic measure of \(V\), which is the function you get by replacing \(f\) by the averaging projection \(g\) of \(f\) defined earlier in this post, has \(L_2\)-norm squared equal to \(\rho^{-1}\delta^2.\)
Now \(f-\delta\) never takes values less than \(-\delta,\) so the \(L_2\)-norm squared of the negative part of the projection of \(f-\delta\) is at most \(\delta^2.\) Therefore, there must be some coset on which \(f-\delta\) averages at least \(\rho^{-1/2}\delta\) or so.
Thus, we can lose \(\rho^{-2}\) dimensions for a density gain of \(\rho^{-1/2}\delta.\) Is that good? For comparison, if we lose just one dimension we gain \(\rho\delta,\) so losing \(\rho^{-2}\) dimensions should gain us \(\rho^{-1}\delta.\) Thus, the more complicated argument using the structure of the Fourier coefficients does worse than the much simpler Roth/Meshulam argument where you lose a dimension at a time.
When \(\rho=\delta,\) it is even easier to see just how unhelpful this approach is: to use it to make a density gain of \(\delta^{1/2},\) we have to lose \(\delta^{-2}\) dimensions, whereas the Roth/Meshulam argument loses \(\delta^{-1}\) dimensions in total.
Can Chang’s inequality be improved?
The next part of this post is a good example of how useful it can be to the research mathematician to remember slogans, even if those slogans are only half understood. For instance, as a result of discussions with Ben Green, I had the following two not wholly precise thoughts stored in my brain.
1. Chang’s inequality is best possible.
2. The analogue for finite fields of Ruzsa’s niveau sets is sets based on the sum (in \(\mathbb{Z}\)) of the coordinates.
The relevance of the second sentence to this discussion isn’t immediately clear, but the point is that Ben proved the first statement (suitably made precise) in this paper, and to do so he modified a remarkable construction of Ruzsa (which provides some very surprising counterexamples) of sets called niveau sets. So in order to come up with a set that has lots of large Fourier coefficients in linearly independent places, facts 1 and 2 suggest looking at sets built out of layers — that is, sets of the form \(\{x\in\{0,1,2\}^n:\sum_ix_i=r\},\) where the sum is the sum in \(\mathbb{N}\) and not the sum in \(\mathbb{F}_3.\) Incidentally, to the best of my knowledge, “fact” 2 is an insight due to Ben himself — no less valuable for not being a precise statement — though it is likely that others such as Ruzsa had thought of it too.
Let me switch to \(\mathbb{F}_2^n\) because it is slightly easier technically and I’m almost certain that whatever I say will carry over to \(\mathbb{F}_3^n.\) Let \(A\subset\mathbb{F}_2^n\) be the set of all \(x\) such that \(\sum_ix_i=r,\) where \(r\) is an integer around \(n/2-\sqrt{n}.\) The density of this layer is about \(cn^{-1/2}\) for a positive absolute constant \(c.\) Now let us think about its Fourier coefficients at the points \(e_1,\dots,e_n\) of the standard basis. By symmetry these will all be the same, so let us look just at the Fourier coefficient at \(e_1.\) If we write \(A_i\) for the set of points \(x\in A\) such that \(x_1=i,\) then this is equal to the density of \(A_0\) minus the density of \(A_1.\)
The density of \(A_0\) is half the density in \(\mathbb{F}_2^{n-1}\) of the layer of points with coordinate sum \(r,\) whereas the density of \(A_1\) is half the density in \(\mathbb{F}_2^{n-1}\) of the layer with coordinate sum \(r-1.\) So basically we need to know the difference in density of two consecutive layers of the cube when both layers are close to \(n/2-\sqrt{n}.\)
The ratio of the binomial coefficients \(\binom n{r-1}\) and \(\binom nr\) is approximately \(r/(n-r),\) or in our case around \(1+2n^{-1/2}.\) Since the two densities are around \(n^{-1/2},\) the difference is around \(n^{-1}.\)
Thus, if we choose \(n\) to be around \(\delta^{-2},\) we have a set of density around \(\delta\) with around \(\delta^{-2}\) Fourier coefficients of size around \(\delta^2.\) Apart from the log factor, this is the Chang bound. (If we want a similar bound for a larger value of \(n,\) then all we have to do is take a product of this example with \(\mathbb{F}_3^m\) for some \(m.\))
Is this kind of approach completely dead?
Chang’s theorem doesn’t give a strong enough bound to improve the Roth/Meshulam bound. And Chang’s theorem itself cannot be hugely improved, as the above example shows. (With a bit of messing about, one can modify the example to provide examples for different values of \(\rho\).) So there is no hope of using this kind of approach to improve the bounds for the cap-set problem.
Or is that conclusion too hasty? Here are two considerations that should give us pause.
1. The example above that showed that Chang’s theorem is best possible does not have the kind of spectrum that a set with no arithmetic progressions would have. In particular, there does not exist \(\rho\) such that, up to log factors, \(\rho^{-3}\) Fourier coefficients have size at least \(\rho\delta.\) (If we take \(\rho=\delta,\) then we get only \(\rho^{-2}\) such coefficients.)
2. There are other ways one might imagine improving Chang’s theorem. For instance, suppose we are given \(\delta^{-3}\) Fourier coefficients of size \(\delta^2.\) We know that they must all live in a \(\delta^{-2}\)-dimensional subspace, but it is far from clear that they can be an arbitrary set of points in a \(\delta^{-2}\)-dimensional subspace. (All the time I’m ignoring log factors.)
Let me discuss each of these two considerations in turn.
Is there an example that completely kills the density-increment approach?
Just to be clear, the density-increment approach to the theorem is to show that if a set \(A\) of density \(\delta\) does not contain an arithmetic progression of length 3, then there is some subspace \(V\) of small codimension such that the density of \(A\cap V\) in \(V\) is at least \(\delta+c(\delta).\) The Roth/Meshulam argument allows us to take \(c(\delta)=\delta^2\) with a codimension of 1. If we could take \(c(\delta)\) to be substantially more than \(k\delta^2\) on a subspace of codimension \(k,\) then we would be in excellent shape. Conversely, if we could find an example where this is not possible, then we would place significant limitations on what the proof of an improved bound could look like.
Again we face the problem of deciding what “an example” means, since we are not trying to construct dense sets with no arithmetic progressions. I find that I keep coming back to the following precise question.
Question 1. Let \(A, B\) and \(C\) be three subsets of \(\mathbb{F}_3^n,\) each of density \(\delta.\) Suppose that there are no solutions to the equation \(a+b+c=0\) with \(a\in A,\) \(b\in B\) and \(c\in C.\) For what values of \(k\) and \(\eta\) can we say that there must be an affine subspace \(V\) of codimension \(k\) such that the density of \(A\cap V\) in \(V\) is at least \(\delta+\eta\)?
The Roth/Meshulam argument implies that we can take \(k=1\) and \(\eta=\delta^2.\) The following example shows that we can’t do much better than \(\eta=\delta^{3/2}\) when \(k=1\) (I don’t claim that it is hard to improve on this example, but I can’t do so after five minutes of thinking about it). Pick \(n\) such that \(\delta=3^{-n/2}.\) (Again, one can obtain a larger \(n\) by taking a product.) Let \(A=B\) be a random subset of \(\mathbb{F}_3^n\) of density \(\delta.\) Then \(A+A\) has size bounded above by approximately \(|A|^2/2,\) which means that it must miss around half of \(\mathbb{F}_3^n,\) so we can find \(C\) of the same density such that \(0\notin A+B+C.\)
Since \(A\) is random, its non-trivial Fourier coefficients will be around \(3^{-n}|A|^{1/2}=3^{-n}3^{n/4}=\delta^{3/2}.\) (Again, I am ignoring a log factor that is due to the fact that a few Fourier coefficients will be unexpectedly large. Again, quadratic examples can take care of this.)
Now note that in the above example we took \(n\) to be proportional to \(\log(1/\delta).\) That means that if we are prepared to lose only \(\log(1/\delta)\) dimensions, we can get the density up to 1. So the obvious next case to think about is how big a density increase we can hope for if we are prepared to drop that many dimensions.
We certainly can’t hope to jump all the way to 1. A simple example that shows this is to let \(A=B\) be a random subset of \(\{x:x_1=0\}\) of density \(\delta\) in \(\mathbb{F}_3^n,\) and to let \(C\) be a subset of \(\{x:x_1=1\}.\) Then the relative density of \(A\) in an affine subspace \(V\) will be \(0,\) approximately \(\delta\) or approximately \(3\delta\) according to whether \(V\) is disjoint from \(x_1=0,\) neither disjoint from nor contained in it, or contained in it — unless, that is, we are prepared to drop down to a very low dimension indeed, where the codimension depends on \(n.\) Thus, the best density increase it is reasonable to aim for is one that is proportional to the existing density.
Putting these thoughts together, it is tempting to ask the following question, which is a more specific version of Question 1.
Question 2. Let \(A,B\) and \(C\) be above. Can we take \(k\) proportional to \(\log(1/\delta)\) and \(\eta\) proportional to \(\delta\)?
If the answer to this question is yes, then it implies a bound for the problem of \(\delta=\exp(-c\sqrt{n}),\) a huge improvement on the Roth/Meshulam bound of \(\delta=cn^{-1}.\) Writing \(N\) for \(3^n,\) we can rewrite this bound as \(\delta=\exp(-c\sqrt{\log N}),\) which is of the same form as the Behrend bound in \(\mathbb{Z}_N.\) This is suggestive, but so weakly suggestive that I’m not sure it should be taken seriously.
I should stress that a counterexample to this rather optimistic conjecture would be very interesting. But it is far from clear to me where a counterexample is going to come from, since the examples that show that Chang’s theorem is best possible do not appear to have enough large Fourier coefficients to have no arithmetic progressions.
[Added later: Ben Green makes an observation about Questions 1 and 2 in a comment below, which demands to be mentioned here since it places them in a context about which plenty is known, including exciting recent progress due to Tom Sanders. Suppose that Question 2 has a positive answer, say. Let \(A\) be a set of density \(\delta.\) Then either \(A+A+A=\mathbb{F}_3^n\) or there exists \(x\) such that \(A+A+(A-x)\) does not contain 0. In the latter case, we can set \(A\) and \(B\) equal to \(A\) and \(C\) equal to \(A-x\) and Question 2 tells us that there must be a codimension-\(k\) subspace (where \(k=c\log(1/\delta)\)) inside which \(A\) has density \(\delta(1+c).\) We cannot iterate this argument more than \(C\log(1/\delta)\) times before reaching a density of 1, so \(A+A+A\) must contain a subspace of codimension at most \(C(\log(1/\delta))^2,\) which is stronger than the best known result in this direction, due to Sanders.
However, Sanders’s result is in the same territory: he shows that \(2A-2A\) contains a subspace of codimension at most a fixed power of \((\log(1/\delta))\) in this paper. Usually what you can do for four sets you can do for three — I haven’t checked that that is true here, but maybe somebody else has (Tom, if you are reading this, perhaps you could confirm it). Thus, even if it looks a bit optimistic to prove a positive answer to Question 2, one can still hope for a positive answer with the bound slightly weakened, to say \(k\leq(\log(1/\delta))^5\) or something like that. Furthermore, the fact that Sanders has proved what he has proved suggests that there could be techniques out there, such as the Croot-Sisask lemma, that would be extremely helpful. (However, it is clear that Sanders, Croot and Sisask have thought pretty hard about what they can get out of these techniques, so a cheap application of them seems unlikely to be possible.)]
What can the large spectrum look like?
The following argument is excerpted from the proof of Chang’s theorem. Let \(A\) be a set of density \(\delta,\) and let \(f\) be the characteristic function of \(A.\) Let \(K\) be a subset of \(\mathbb{F}_3^n\) such that \(\rho\delta\leq|\hat{f}(r)|\leq 2\rho\delta\) for every \(r\in K.\) Let \(g\) be the function \(g(x)=\sum_{r\in K}\hat{f}(r)\omega^{r.x},\) and recall that \(f(x)=\sum_r\hat{f}(r)\omega^{r.x},\) by the inversion formula.
Then
\(\langle f,g\rangle=\sum_{r\in K}|\hat{f}(r)|^2\geq|K|\rho^2\delta^2.\)
Also, for any \(p\in [1,\infty],\) and \(q\) such that \(1/p+1/q=1,\) Hölder’s inequality tells us that
\(\langle f,g\rangle\leq\|f\|_q\|g\|_p.\)
Now \(\|f\|_q=\delta^{1/q}=\delta\delta^{-1/p},\) which is close to \(\delta\) when \(p\) is large, and within a constant of \(\delta\) when \(p\) reaches \(\log(1/\delta)\).
In order to think about \(\|g\|_p,\) let us make the simplifying (and, it turns out, not remotely problematic) assumption that \(p\) is an even integer \(2t.\) Then a standard calculation (or easy use of the convolution identity) shows that
\(\|g\|_p^p=\sum_{r_1+\dots+r_t=s_1+\dots+s_t}\hat{f}(r_1)\dots\hat{f}(r_t)\overline{\hat{f}(s_1)}\dots\overline{\hat{f}(s_t)}.\)
We therefore know that
\(\delta^{p-1}\sum_{r_1+\dots+r_t=s_1+\dots+s_t}\hat{f}(r_1)\dots\hat{f}(r_t)\overline{\hat{f}(s_1)}\dots\overline{\hat{f}(s_t)}\)
is at least \(|K|^p\rho^{2p}\delta^{2p}.\)
To get a feel for what this is telling us, let us bound the left-hand side by replacing each Fourier coefficient by \(2\rho\delta.\) That tells us that \(\delta^{p-1}(2\rho\delta)^{2t}\) times the number of \(2t\)-tuples \((r_1,\dots,r_t,s_1,\dots,s_t)\in K^{2t}\) such that \(r_1+\dots+r_t=s_1+\dots+s_t\) is at least \(|K|^{p}\rho^{2p}\delta^{2p}.\) Therefore, the number of these \(2t\)-tuples is at least \((\rho/2)^{2t}\delta|K|^{2t}.\)
Now a trivial lower bound for the number of the \(2t\)-tuples is \(|K|^t.\) If the number is roughly equal to this lower bound, then we obtain something like the inequality
\(|K|^t\geq(\rho/2)^{2t}\delta|K|^{2t},\)
which implies that
\(|K|\leq(2/\rho)^2\delta^{-1/t}.\)
For example, if \(t=2\) and \(\rho=\delta,\) then this tells us that we cannot have a subset \(K\) of the large spectrum of size \(C\delta^{-5/2}\) without having on the order of \(|K|^2\) non-trivial quadruples \(r_1+r_2=s_1+s_2.\)
Even this example (which is not the \(t\) that Chang considers — she takes \(t\) to be around \(\log(1/\delta)\)) raises an interesting question. Let us write \(m\) for \(\delta^{-3}.\) Then if we cannot improve on the Roth/Meshulam bound, we must have (up to log factors) a set \(K\) of size \(m\) such that amongst any \(m^{5/6}\) of its elements there are at least as many non-trivial additive quadruples \(r_1+r_2=s_1+s_2\) as there are trivial ones: that is, at least \(m^{5/3}\) such quadruples.
Sets with very weak additive structure.
What does this imply about the set \(K\)? The short answer is that I don’t know, but let me give a longer answer.
First of all, the hypothesis (that every subset of size \(m^{5/6}\) spans some non-trivial additive quadruples) is very much in the same ball park as the hypotheses for Freiman’s theorem and the Balog-Szemerédi theorem, in particular the latter. However, the number of additive quadruples assumed to exist is so small that we cannot even begin to touch this question using the known proofs of those theorems.
Should we therefore say that this problem is way beyond the reach of current techniques? It’s possible that we should, but there are a couple of reasons that I think one shouldn’t jump to this conclusion too hastily.
To explain the first reason, let me consider a weakening of the hypothesis of the problem: instead of assuming that every set of size \(m^{5/6}\) spans at least \(m^{5/3}\) non-trivial additive quadruples, let’s just see how many additive quadruples that tells us there must be and assume only that we have that number.
This we can do with a standard double-counting argument. If we choose a random set of size \(m^{5/6},\) our hypothesis tells us it will contain at least \(m^{5/3}\) non-trivial additive quadruples. But the probability that any given non-trivial additive quadruple \((r_1,r_2,s_1,s_2)\in K^4\) belongs to the set is \(m^{-2/3},\) so if the total number of non-trivial additive quadruples is \(h,\) then \(m^{-2/3}h\) must be at least \(m^{5/3}\) (counting the expected number of additive quadruples in a random set in two different ways). That is, \(h\) must be at least \(m^{7/3}.\) This is to be contrasted with the trivial lower and upper bounds of \(m^2\) and \(m^3.\)
Here are two natural ways of constructing a set with that many additive quadruples. The first is simply to choose a set \(m\) randomly from a subspace of cardinality \(M.\) The typical number of additive quadruples if \(m=\alpha M\) is \(\alpha^4M^3=\alpha m^3,\) so we want to take \(\alpha=m^{-2/3}\) and thus to take \(M=m^{5/3}.\) The dimension of this subspace is therefore logarithmic in \(m,\) which means that the entire large spectrum is contained in a log-dimensional subspace, which gives us a huge density increase for only a small cost in dimensions.
The second is at the opposite extreme: we take a union of \(s\) subspaces of cardinality \(t,\) for some \(st=m.\) The number of non-trivial additive quadruples is approximately \(st^3,\) so for this to equal \(m^{7/3}\) we need \(t\) to be \(m^{2/3}\) and \(s\) to be \(m^{1/3}.\) Note that here again we are cramming a large portion of the large spectrum into a log-dimensional subspace.
So far this is quite encouraging, but we should remind ourselves (i) that there could be some much more interesting examples than these ones (as I write it occurs to me that finite-fields niveau sets are probably worth thinking about, for instance) and (ii) that even if the most optimistic conjectures are true, they seem to be very hard to prove with this level of weakness of hypothesis.
A quick remark about the second example. If we choose \(m^{1/2}\) points at random from each of the \(m^{1/3}\) subspaces of size \(m^{2/3},\) then those points will span around \(m^{2-2/3}=m^{4/3}\) additive quadruples, so in total we will get around \(m^{5/3}\) additive quadruples. This is how to minimize the number of additive quadruples in a set of size \(m^{5/6},\) so in the second case (as well as the first) we also have the stronger property that every subset of size \(m^{5/6}\) contains at least \(m^{5/3}\) non-trivial additive quadruples.
Going back to the point that we are assuming a very weak condition, the main reason that that doesn’t quite demonstrate that this approach is hopelessly difficult is that we can get by with a very weak conclusion as well. Given the very weak hypotheses, one can either say, “Well, it looks as though A ought to be true, but I have no idea how to prove it,” or one can say, “Let’s see if we can prove anything non-trivial about sets with this property.” As far as I know, not too much thought has been given to the second question. (If I’m wrong about that then I’d be very interested to know.)
I’ve basically given the argument already, but let me just spell out again what conclusion would be sufficient for some kind of improvement to the current bound. For the purposes of this discussion I’ll be delighted with a bound that gives a density of \(n^{-11/10}\) (since that would be below the magic \(1/\log(3^n)\) barrier and would thus raise hopes for beating that barrier in Roth’s theorem too).
As ever, I’ll take \(\rho\) to equal \(\delta,\) so that we have around \(\delta^{-3}\) Fourier coefficients of size around \(\delta^2.\) If \(t\) of these are contained in a \(k\)-dimensional subspace \(V,\) then the sum of squares of all the Fourier coefficients in \(V\) is at least \(t\delta^4,\) which gives us a coset of \(V\) in which the density is increased by \(\delta^2\sqrt{t}.\) This is an improvement on the Roth/Meshulam argument provided only that \(\sqrt{t}\) is significantly bigger than \(k,\) or in other words \(t\) is significantly bigger than \(k^2.\)
So here is a question, a positive answer to which would give a weakish, but definitely very interesting, improvement to the Roth/Meshulam bound. I’ve chosen some arbitrary numbers to stick in rather than asking the question in a more general but less transparent form. But if you would prefer the latter, then it’s easy to modify the formulation below.
Question 3. Let \(K\) be a subset of \(\mathbb{F}_3^n\) of size \(m\) that contains at least \(m^{7/3}\) quadruples \(r_1+r_2=s_1+s_2.\) Does it follow that there is a subspace of \(\mathbb{F}_3^n\) of dimension at most \(m^{1/100}\) that contains at least \(m^{3/100}\) elements of \(K\)?
I talked about very weak conclusions above. The justification for that description is that we are asking for the number of points of \(K\) in the subspace to be around the cube of the dimension, whereas the cardinality of the subspace is exponential in the dimension. So we are asking for only a tiny fraction of the subspace to be filled up. This is much much weaker than anything that comes out of Freiman’s theorem.
To give an idea of the sort of argument that it makes available to us that is not available when one wishes to prove Freiman’s theorem, let us suppose we have a set \(K\) of size \(m\) such that no subspace of dimension \(m^{1/100}\) contains more than \(m^{3/100}\) points, and let us choose from \(K\) a random subset \(L,\) picking each element with probability \(m^{-1/20}.\)
Given any subspace of dimension \(m^{1/100},\) the expected number of points we pick in that subspace is at most \(m^{3/100}m^{-1/20}=m^{-1/50},\) and the probability that we pick at least \(t\) points is at most around \(m^{-t/50}/t!.\) The number of subspace of dimension \(m^{1/100}\) that contain at least \(m^{1/100}\) points of \(K\) is at most \(\binom m{m^{1/100}},\) which is at most \(m^{m^{1/100}}.\) If we take \(t\) to be \(50m^{1/100},\) then the expected number of these subspaces that contain at least \(t\) points is less than 1.
On the other hand, if the number of additive quadruples in \(K\) was at least \(m^{7/3},\) then the expected number in our random subset is at least \(m^{7/3-4/20}=m^{32/15}\) while the size of that subset is around \(m^{19/20}.\)
The precise numbers here are not too important. The point is that this random subset is a set \(L\) of size \(h\) that contains \(h^\alpha\) additive quadruples for some \(\alpha>2,\) such that no subspace of dimension \(h^\beta\) contains more than \(Ch^\beta\) points of \(L.\) And we have a certain amount of flexibility in the values of \(\alpha\) and \(\beta.\) Thus, to improve on the bounds for the cap-set problem it is enough to show that having \(h^\alpha\) additive quadruples implies the existence of a subspace of dimension \(h^\beta\) for some small \(\beta\) (or even smaller dimension if one is satisfied with a yet more modest improvement to the Roth/Meshulam bound) that contains a superlinear number (in the dimension of the subspace) of points of \(L.\)
This is promising, partly because it potentially allows us to use the stronger hypothesis that we were actually given about \(K.\) Recall that the \(m^{7/3}\) bound for the number of additive quadruples was actually derived from the fact that every subset of \(K\) of size \(m^{5/6}\) contains at least \(m^{5/3}\) non-trivial additive quadruples. So one thing we might try to do is assume that we have a set \(L\) of size \(h\) such that no subspace of dimension \(h^\beta\) contains more than \(Ch^\beta\) points of \(L,\) and try to use that to build inside \(L\) a largish subset (of size \(h^{7/8},\) say) that has very few additive quadruples.
Let me end this section with a reminder that we have by no means explored all the possibilities that arise out of Chang’s argument. I have concentrated on the case \(p=4\) (and thus \(t=2\)) because it is easy to describe and because it relates rather closely to existing results in additive combinatorics. But if it is possible to use these ideas to obtain a big improvement to the Roth/Meshulam bound, then I’m pretty sure that to do so one needs to take \(p\) to be something closer to \(\log(1/\delta),\) as Chang does in her theorem. The arguments I have been sketching have their counterparts in this range too. In short, there seems to be a lot of territory round here, and I suspect that not all of it has been thoroughly explored.
Is there a simple and direct way of answering Question 2?
Let me begin with a reminder of what Question 2 was. Let \(A, B\) and \(C\) be three subsets of \(\mathbb{F}_3^n,\) each of density \(\delta.\) Suppose that there are no solutions to the equation \(a+b+c=0\) with \(a\in A,\) \(b\in B\) and \(c\in C.\) Then Question 2 asks whether there is an affine subspace \(V\) of codimension \(C\log(1/\delta)\) such that the density of \(A\cap V\) inside \(V\) is at least \((1+c)\delta.\)
The Roth/Meshulam argument gives us a density of \(\delta+c\delta^2\) in a codimension-1 subspace, and it does so by expanding and applying simple identities and inequalities such as Parseval and Cauchy-Schwarz to the Fourier coefficients. Now Fourier coefficients are very closely related to averaging projections onto cosets of 1-codimensional subspaces (a remark I’ll make more precise in a moment). Can we somehow generalize the Roth/Meshulam argument and look at an expansion in terms of averaging projections to cosets of \(k\)-codimensional subspaces, with \(k=C\log(1/\delta)\)? Is there a very simple argument here that everybody has overlooked? Probably not, but if there isn’t then it at least seems worth understanding where the difficulties are, especially as quite a lot of the Roth/Meshulam argument does generalize rather nicely.
Expanding in terms of projections.
[Added later: While looking for something else, I stumbled on a paper of Lev, which basically contains all the observations in this section.]
For the purposes of this section it will be convenient to work not with the characteristic functions of \(A, B\) and \(C\) but with their balanced functions, which I shall call \(f,g\) and \(h.\) The balanced function of a set \(A\) of density \(\delta\) is the characteristic function minus \(\delta.\) That is, if \(x\in A\) then \(f(x)=1-\delta\) and otherwise \(f(x)=-\delta.\) The main properties we shall need of the balanced function are that it averages zero and that if it averages \(\eta\) in some subset of \(\mathbb{F}_3^n\) then \(A\) has density \(\delta+\eta\) inside that subset.
Here is another simple (and very standard) lemma about balanced functions. Suppose we pick a random triple \((x,y,z)\) of elements of \(\mathbb{F}_3^n\) such that \(x+y+z=0.\) Then the probability that it lies in \(A\times B\times C\) is
\(\mathbb{E}_{x+y+z=0}(\delta+f(x))(\delta+g(y))(\delta+h(z)).\)
This sum splits into a sum of eight sums, one for each way of choosing either the first or the second term from each bracket. But since \(f,g\) and \(h\) all average zero, all but two of these terms disappear. For example, \(\mathbb{E}_{x+y+z=0}\delta g(y)h(z)\) is zero since it equals \(\delta\mathbb{E}_{y,z}g(y)h(z)\) which in turn equals \(\delta(\mathbb{E}_yg(y))(\mathbb{E}_zh(z)).\) Thus, the probability in question is
\(\delta^3+\mathbb{E}_{x+y+z=0}f(x)g(y)h(z).\)
In particular, if it is zero, then \(\mathbb{E}_{x+y+z=0}f(x)g(y)h(z)=-\delta^3.\)
Let \(V\) be a linear subspace of \(\mathbb{F}_3^n\) of codimension 1. Then \(V\) is of the form \(\{x:r.x=0\}\) for some \(r\in\mathbb{F}_3^n\) (which is unique up to a scalar multiple), where \(r.x\) stands for the sum \(\sum_i r_ix_i\) in \(\mathbb{F}_3.\) Let us write \(P_Vf\) for the function \(g\) defined by setting \(g(x)\) to be the average of \(f(x+v)\) over all \(v\in V.\) Thus, \(P_V\) is the averaging projection that maps a function to the nearest function that is constant on cosets of \(V.\) Let us now relate this to the Fourier expansion of \(f.\) I shall do it by a direct calculation, but it can be understood conceptually: if we restrict the Fourier transform to a subspace, then we convolve the original function by the annihilator of that subspace.
By the inversion formula, we have that
\(f(x)=\sum_r\hat{f}(r)\omega^{r.x},\)
where \(\omega=\exp(2\pi i/3).\) Now let us pick a non-zero \(r\) and consider the sum
\(\hat{f}(0)+\hat{f}(r)\omega^{r.x}+\hat{f}(-r)\omega^{-r.x}.\)
Note that we are adding up over all Fourier coefficients at multiples of \(r.\) Expanding the Fourier coefficients, we obtain the sum
\(\mathbb{E}_z f(z)(1+\omega^{r.(x-z)}+\omega^{-r.(x-z)}).\)
The term in brackets is 3 when \(r.x=r.z\) and 0 otherwise. If \(V\) is the subspace \(\{x:r.x=0\},\) then this says that the term in brackets is 3 if \(x\) and \(z\) lie in the same coset of \(V\) and 0 otherwise. Since the probability that they lie in the same coset is 1/3, this tells us that the sum is nothing other than \(P_Vf(x).\)
An additional observation, and our reason for using balanced functions, is that if \(f\) averages zero, then \(\hat{f}(0)=0.\) Therefore, in this case we have the identity
\(P_Vf(x)=\hat{f}(r)\omega^{r.x}+\hat{f}(-r)\omega^{-r.x}\)
and also (by the inversion formula and the fact that the pairs \(\{r,-r\}\) partition the non-zero elements of \(\mathbb{F}_3^n\)) the identity
\(f=\sum_VP_Vf,\)
where the sum is over all subspaces \(V\) of codimension 1.
Since the functions \(\omega^{r.x}\) form an orthonormal basis, we can also translate Parseval’s identity into the form
\(\|f\|_2^2=\sum_V\|P_Vf\|_2^2\)
and more generally
\(\langle f,g\rangle=\sum_V\langle P_Vf,P_Vg\rangle.\)
What about counting arithmetic progressions of length 3? Well, \(\mathbb{E}_{x+y+z=0}f(x)g(y)h(z)\) expands as
\(\mathbb{E}_{x+y+z=0}\sum_{U,V,W}P_Uf(x)P_Vg(y)P_Wh(z).\)
Interchanging summation we obtain
\(\sum_{U,V,W}\mathbb{E}_{x+y+z=0}P_Uf(x)P_Vg(y)P_Wh(z).\)
Now the three functions \(P_Uf,\) \(P_Vg\) and \(P_Wh\) all average zero, and they are constant on cosets of \(U,V\) and \(W,\) respectively. If \(U,V\) and \(W\) are not all equal, then the inner expectation must be zero. To see this, let \(r,\) \(s\) and \(t\) be vectors “perpendicular” to \(U,V\) and \(W,\) respectively. Then \(U+V+W\ne\mathbb{F}_3^n\) if and only if there exists \(x\) that cannot be written as \(a+b+c\) with \(r.a=s.b=t.c=0.\) That is the case if and only if there is a multiple \(u\) of each of \(r,s\) and \(t\) such that \(x.u\ne 0.\) (Why? Well if there is such a multiple then it is obvious. Conversely, if \(x\) is not in \(U+V+W\) then there must be a linear functional \(u\) that vanishes on \(U+V+W\) but not at \(x.\) If that linear functional is \(u,\) then \(u\) must be a multiple of each of \(r,s\) and \(t.\)) Such \(u,x\) exist if and only if \(r,s\) and \(t\) are all multiples of each other, which happens if and only if \(U,V\) and \(W\) are all equal.
Therefore, the AP count can be rewritten as
\(\sum_U\mathbb{E}_{x+y+z=0}P_Uf(x)P_Ug(y)P_Uh(z).\)
In words, the AP count is obtained by summing the AP counts over all codimension-1 averaging projections.
Now the size of that last expression is bounded above by
\(\max_U\|P_Uf\|_\infty\sum_U\langle P_Ug,P_Uh\rangle.\)
By the projections version of Parseval’s identity, the sum of those inner products is \(\langle g,h\rangle,\) so the assumption that there are no APs in \(A\times B\times C\) implies that
\(\max_U\|P_Uf\|_\infty\|g\|_2\|h\|_2\geq\delta^3.\)
Since \(\|g\|_2\) and \(\|h\|_2\) are at most \(\delta^{1/2},\) we find that \(\max_U\|P_Uf\|_\infty\geq\delta^2,\) which implies that there is a coset of some \(U\) in which \(f\) averages at least \(\delta^2/2.\) (The factor 1/2 comes from the fact that \(f_U\) might have its \(L_\infty\) norm by virtue of \(f\) averaging \(-\delta^2\) on a coset. But since \(f_U\) averages zero, we then get at least \(\delta^2/2\) on one of the other two cosets.)
What I have just done is recast the Roth/Meshulam argument in terms of averaging projections rather than Fourier coefficients — but it is basically the same argument. What was the point of doing that? My motivation was that the projections version gives me something I can generalize to subspaces of higher codimension.
Expanding in terms of higher-codimension averaging projections.
A lot of what I said in the last section carries over easily to the more general situation where we sum over higher-codimension averaging projections. Let us fix a \(k\) and interpret all sums over subspaces as being over the set of all subspaces of codimension \(k.\) Our first identity in the case \(k=1\) was
\(f=\sum_V P_Vf.\)
What happens for general \(k\)? Well,
\(\sum_VP_Vf(x)=\sum_V\mathbb{E}_{y\in V}f(x+y)\)
\(=3^{k-n}\sum_yf(x+y)\sum_{V\ni y}1.\)
Let us write \(S(n,k)\) for the number of codimension-\(k\) subspaces of \(\mathbb{F}_3^n.\) Then the number of codimension-\(k\) subspaces that contain \(y\) is \(S(n,k)\) if \(y=0\) and \(T(n,k)=(3^{n-k}-1)S(n,k)/(3^n-1)\) otherwise (since the probability that a random codimension-\(k\) subspace contains \(y\) is equal to the number of non-zero points in such a subspace divided by the total number of non-zero points in \(\mathbb{F}_3^n\)). Therefore, the sum above works out as
\(3^{k-n}((S(n,k)-T(n,k))f(x)+T(n,k)\sum_yf(x+y)).\)
The contribution from the second term is zero, since \(f\) averages zero, so we get \(3^{k-n}(S(n,k)-T(n,k))f(x).\)
Thus, \(\sum_VP_Vf\) is proportional to \(f,\) with a constant of proportionality that is not too hard to estimate.
Next, let us prove a version of Parseval’s identity.
\(\sum_V\|P_Vf\|_2^2=\sum_V\mathbb{E}_x\mathbb{E}_{y,z\in V}f(x+y)f(x+z)\)
\(=\mathbb{E}_x3^{2(k-n)}\sum_{y,z}f(x+y)f(x+z)\sum_{V\ni y,z}1.\)
Now the number of subspaces containing \(\{y,z\}\) depends on the dimension of the space spanned by \(y\) and \(z.\) However, if we sum \(\sum_xf(x+y)f(x+z)\) over all pairs \((y,z)\) then we get zero (since \(f\) averages zero). If we sum over all pairs of the form \((u,-u)\) for some \(u,\) then we get zero, since every pair \((w,z)\) can be written in \(3^n\) ways as \((x+u,x-u).\) The same applies to pairs of the form \((u,0)\) and pairs of the form \((0,u).\) Finally, if we sum over pairs of the form \((u,u)\) we get a multiple of \(\|f\|_2^2,\) with a larger multiple (by a factor of roughly \(3^k\)) if \(u=0.\)
Putting this together, we find that \(\sum_V\|P_Vf\|_2^2\) is proportional to \(\|f\|_2^2,\) again with a constant of proportionality that, with a bit of effort, one can estimate fairly accurately. Once again, this implies (by polarization or by generalizing the proof) that \(\langle f,g\rangle\) is proportional to \(\sum_V\langle P_Vf,P_Vg\rangle.\)
Finally, let us prove that the AP count of \(f,g,h\) is proportional to the sum of the AP counts of the projections. We have
\(\sum_V\mathbb{E}_{x+y+z=0}P_Vf(x)P_Vg(y)P_Vh(z)\)
\(=\sum_V\mathbb{E}_{x+y+z=0}\mathbb{E}_{u,v,w\in V}f(x+u)g(y+v)h(z+w)\)
\(=3^{3(k-n)}\mathbb{E}_{x+y+z=0}\sum_{u,v,w}f(x+u)g(y+v)h(z+w)\sum_{V\ni u,v,w}1.\)
The value of \(\sum_{V\ni u,v,w}1\) depends only on the dimension of the subspace spanned by \(u,v,w.\) The sum of \(\mathbb{E}_{x+y+z=0}f(x+u)g(y+v)h(z+w)\) over all \((u,v,w)\) is zero. The sum over all \((u,v,w)\) that satisfy a non-trivial linear relation \(au+bv+cw=0\) is zero unless \(a=b=c\) (because unless that is the case we can express any triple in the form \((x+u,y+v,z+w)\) with \(x+y+z=0\) and \(au+bv+cw=0\) and the result is proportional to \(\mathbb{E}_{x,y,z}f(x)g(y)h(z)=0\)). The sum over all \((u,v,w)\) such that \(u+v+w=0\) is proportional to \(\mathbb{E}_{x+y+z=0}f(x)g(y)h(z).\) Putting all this together tells us that
\(\sum_V\mathbb{E}_{x+y+z=0}P_Vf(x)P_Vg(y)P_Vh(z)\)
is proportional to \(\mathbb{E}_{x+y+z=0}f(x)g(y)h(w),\) as claimed. What is potentially significant about this is that if we can use it to show that there is some \(V\) of low codimension such that the AP count of \(P_Vf, P_Vg, P_Vh\) is reasonably large, then there must be some coset of \(V\) on which \(P_Vf\) has reasonably large average.
At this point, honesty compels me to mention that the above facts can be proved much more simply on the Fourier side — so much so that it casts serious doubt on whether one could get anything out of this “codimension-\(k\) expansion” that one couldn’t get out of the normal Fourier expansion. All we have to do is point out that the Fourier expansion of \(P_Vf\) is the restriction of \(\hat{f}\) to \(V,\) and that if \(f\) sums to zero then \(\hat{f}(0)=0.\) From this it follows easily that the Fourier transform of \(\sum_V\widehat{P_Vf}\) is proportional to \(\hat{f},\) that \(\sum_V\|\widehat{P_Vf}\|_2^2\) is proportional to \(\|\hat{f}\|_2^2,\) and that \(\sum_V\sum_r\widehat{P_Vf(r)}^3\) is proportional to \(\sum_r\hat{f}(r)^3.\) From those facts, the results above follow easily.
Thus, all we are doing by splitting up into the functions \(P_Vf\) is splitting up the Fourier transform of \(f\) as a suitable average of its restrictions to the subspaces \(V\) (and using the fact that \(\hat{f}(0)=0\) — all non-zero points will be in the same number of subspaces \(V\)). How can that possibly tell us anything that we can’t learn from examining the Fourier transform directly?
The only answer I can think of to this question is that it might conceivably be possible to prove something by looking at some function of the projections \(P_Vf\) that does not translate easily over to the Fourier side. I have various thoughts about this, but nothing that is worth posting just yet.
So what was the point of this section? It’s here more to ask a question than propose an answer to anything. The question is this. If it really is the case that for every AP-free set (or AP-free triple of sets \(A,B,C\)) there must be a fairly low-codimensional subspace \(V\) such that variations in density show up even after one applies the averaging projection \(P_V,\) then it seems highly plausible that some kind of expression in terms of these expansions should be useful for proving it. For instance, we might be interested in the quantity \(\max_V\|P_Vf\|_2,\) where \(f\) is the balanced function of \(A.\) And perhaps we might try to analyse that by looking instead at \(\sum_V\|P_Vf\|_2^p\) for some suitably chosen large integer \(p\) (to get a handle on the maximum but also to give us something we can expand and think about). The question is, can anything like this work? I don’t rule out a convincing negative answer. One possibility would be to show that it cannot give you anything that straightforward Fourier analysis doesn’t give you. A more extreme possibility is that the rather optimistic conjecture about getting a large density increment on a low-codimensional subspace is false. The latter would be very interesting to me as it would rule out a lot of approaches to the problem.
Conclusion.
I don’t really feel that I’ve come to the end of what I want to say, but I also feel as though I am never going to reach that happy state, so I am going to cut myself off artificially at this point. Let me end by briefly discussing a question I mentioned at the beginning of this post: is this the beginning of a Polymath project?
It isn’t meant to be, partly because I haven’t done any kind of consultation to see whether a Polymath project on this problem would be welcome. For now, I see it as very much in the same spirit as Gil Kalai’s “open discussion”. What I hope is that some of my remarks will provoke others to share some of their thoughts — especially if they have tried things I suggest above and can elaborate on why they are difficult, or known not to work. If at some point in the future it becomes clear that there is an appetite for collectively pursuing one particular approach to the problem, then at that point we could perhaps think about a Polymath project.
Should there be ground rules associated with an open discussion of a mathematical problem? Perhaps there should, but I’m not sure what they should be. I suppose if you use a genuine idea that somebody has put forward in the discussion then it is only polite to credit them: in any case, the discussion will be in the public domain so if you have an idea and share it then it will be date-stamped. If anyone has any further suggestions about where trouble might arise and how to avoid it then I’ll be interested to hear them.
This entry was posted on January 11, 2011 at 3:10 pm and is filed under Straight maths. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.