Here we present a formulation of a lemma from Bateman-Katz‘s work on the cap-set problem, which may be of independent interest in additive combinatorics at large. The proof is also novel — Ben Green knows of no other instances of this argument — and may yet find other applications. Indeed, Thomas Bloom recently used this lemma together with other bounds to give his improvement to Roth’s theorem.
[Our main result will be ‘Corollary 3’ below, which will follow from Lemma 1 and Theorem 2. ]
For any abelian group and finite , we define the ‘2-fold additive energy’ of by
Any counted on the right-hand-side we call an ‘additive tuple’. The energy is one way of measuring the additive structure of . The main theorems of this note link data concerning the energy to data concerning another notion of additive structure, namely (in the case where is a finite vector space) dimension.
If and , with , then
Remarks on Lemma 1
- There are about diagonal solutions counted in the additive energy, and — thinking of as much smaller than — the claim is exactly saying that (up to some tame factors) these dominate when is very small, i.e. when is almost completely linearly independent. This matches our intuition.
- The claim is (worse than) trivial if is the same order as .
- We shall see that information about dimension meshes most naturally with equations in the elements of , and not additive tuples. The count for the former is roughly equivalent to Bloom’s notion of ‘restricted energy’, and we will, like him, have to undergo a messy calculation to convert information about this restricted energy into information about . The issue that cannot be calculated directly does genuinely seem to have been missed by B-K. Broadly speaking this means that their definition giving what it means for the large spectrum to be ‘additive smoothing’ is overly optimistic. I am currently trying to establish whether this has any major effect on their work; this will probably be the subject of a future blog post.
- My dependence is extremely wasteful, and no doubt one can do much better. However, don’t be too scared of extra factors; in Bloom’s argument they roughly correspond to factors in the final bound. Also remember that there are factors in the trivial lower bound, so we cannot eschew them completely.
- The reason we go to the trouble of proving these theorems for rather than the restricted energy is that has a particularly pleasant expression in terms of the Fourier transform, which allows for many useful manipulations (in particular Holder’s inequality).
Viewing Lemma 1 in the contrapositive, it is saying that sets with larger-than-trivial energy have lower-than-trivial dimension. Theorem 2 is a more refined version, namely that sets with large energy have subsets with very low dimension.
Let integers be arbitrary parameters and be independent of . Let V be finite vector space, and satisfy . Then with and
Remarks on Theorem 2
- This theorem is good in the case where is a smallish power of ; B-K have . It gives some structural information even when the 2-fold additive energy of is quite a long way below the maximum possible.
- This is the first main ‘new’ result in Bateman-Katz’s paper, and is the main topic of this post.
- is just a minor technical condition that streamlines a particular estimation step. It could certainly be removed with a little more effort, and no effort at all if one didn’t care about how the constants in Theorem 2 depended on .
- One needs Lemma 1 as an ingredient in the proof of Theorem 2, applied to a suitably chosen random subset .
- For certain choices of the parameters we can use Theorem 2 to bootstrap an improved theorem regarding , say, which would be better than applying Theorem 2 directly with .
Expanding on this last remark, we note that by Holder’s inequality we have
[This follows from the fact that and taking Holder in the form with , followed by Parseval applied to the second bracket].
Therefore we can make the conclusion of Theorem 2 provided that, for some ,
Suppose we wanted to be able to take for some fixed . Applying Theorem 2 directly would only allow us to do so when (so for example we would be forced to have to get a non-trivial result). However, equation (1) allows us to conclude whenever . Taking large enough, depending on , we win if , which is better for . We state this as a corollary:
Let , and let V be finite vector space, and . Then there exist a constant such that if then with and
Proof: Above discussion.
Proofs of Lemma 1 and Theorem 2 are below.
Proof of Lemma 1
Let be the formal vector space of dimension spanned by the elements of . Let be the set of all linear combinations of the elements of , with at most variables, which equal when evaluated in .
Now, consider the linear map from to given by evaluation in . This map is clearly surjective, so has a kernel of dimension . But every element of is in this kernel, so has a basis of at most elements of , which we can assume — recalling the linear algebra fact that every spanning set contains a basis — consists of elements from . These basis elements mention at most elements of , so all equations in combined mention at most elements of .
Regrettably does not contain all additive -tuples . There are two phenomena which are not counted in :
- We could have for one or more pairs (diagonal behaviour).
- We could have repetition of on one side of the equation that is some multiple of the characteristic of the underlying field.
To prove the claim all we do is take both of these into account. However, the reader is allowed to find this simple process rather painful. There is a similar — and equally painful — lemma in Bloom.
Indeed, a particular additive -tuple could have pairs , say. There are choices for the positions of these pairs, and choices for what the elements are. We remove these pairs from both sides to get another equation, in which no equals any .
The elements mentioned in this equation only come from that special set of size at most except those elements which appear a multiple of times on one side of the equation, where is the characteristic of the underlying field.
Let’s say that there are such elements . Then there are
ways of choosing the subsets of repeated indices (where there are instances of in the multinomial coefficient) and way of assigning elements of to these repeated blocks. [Of course this overcounts tuples where a particular element of is repeated times, but we’re only after an upper bound]. There are at most ways of filling in the remaining .
By performing a similar analysis for the we see that
which — approximating factorials by powers, forgetting about the denominator of the multinomial coefficient completely, and taking the maximum value of everything in the sum — is at most
which — as — is at most
which is at most
Remark: When we only get contribution from terms which come entirely from phenomena 1 and 2. Running the above calculation we get a bound of in this case.
Proof of Theorem 2
We prove the contrapositive statement. Suppose every with satisfies . We will show that this assumption makes a random subset of of size have small energy, and therefore that the entire set has small energy.
Indeed, let be a subset of size picked uniformly at random.
Claim: For any integer in the range , we claim that .
Proof of Claim: We can consider picking the elements of one at a time, uniformly, without replacement. For , let be the set constructed after trials, and be the next chosen element. Then
by assumption, since is certainly a subset of whose span has dimension at most .
Now, the events are not — in general — independent. Indeed, suppose that and let , for some linearly independent vectors and . Then and both have positive probabilities but . [Bloom’s paper uses a slightly different probabilistic model in which we pick with replacement, but this example still scuppers independence even in that instance].
However, it is true that . Indeed, if any of the have probability zero then the above inequality is trivial. Otherwise, if then conditioning on cannot increase hence cannot increase , i.e. . This shows the inequality for pairwise intersections. We may show similarly that whenever . Writing out as a suitable product of conditional probabilities, this proves the inequality.
[In B-K and in Bloom, it is not entirely obvious from the wording whether independence is implicitly (and incorrectly) assumed or whether this weaker statement is (correctly) assumed.]
The probability that is exactly the probability that of the events occur. By the above discussion, we have
thus proving the claim.
Claim: With the random set of size constructed earlier,
Proof of claim: We have
which, by Theorem 1 and the remark following its proof, and the previous claim, is at most
It remains just to bound this sum. The infinite sum is clearly convergent; we observe that if then . and we can bound the sum by the ratio test. If then the above certainly holds. By assumption, , hence we may split the sum as
and bound both bits as
which is certainly at most
Inputting this into the upper bound for the expected energy, and adding in the contribution, we get the bound
We are now nearly ready to finish to proof of the Theorem 2. Indeed, we can easily bound below by noting that the probability that a certain additive -tuple is entirely contained in is at least and so by linearity of expectation . Therefore, combining our upper and lower bounds, we get