The following situation is very common in modern harmonic analysis: one has a large scale parameter (sometimes written as in the literature for some small scale parameter , or as for some large radius ), which ranges over some unbounded subset of (e.g. all sufficiently large real numbers , or all powers of two), and one has some positive quantity depending on that is known to be of polynomial size in the sense that
for all in the range and some constant , and one wishes to obtain a subpolynomial upper bound for , by which we mean an upper bound of the form
for all and all in the range, where can depend on but is independent of . In many applications, this bound is nearly tight in the sense that one can easily establish a matching lower bound
in which case the property of having a subpolynomial upper bound is equivalent to that of being subpolynomial size in the sense that
for all and all in the range. It would naturally be of interest to tighten these bounds further, for instance to show that is polylogarithmic or even bounded in size, but a subpolynomial bound is already sufficient for many applications.
Let us give some illustrative examples of this type of problem:
Example 1 (Kakeya conjecture) Here ranges over all of . Let be a fixed dimension. For each , we pick a maximal -separated set of directions . We let be the smallest constant for which one has the Kakeya inequality
where is a -tube oriented in the direction . The Kakeya maximal function conjecture is then equivalent to the assertion that has a subpolynomial upper bound (or equivalently, is of subpolynomial size). Currently this is only known in dimension .
Example 2 (Restriction conjecture for the sphere) Here ranges over all of . Let be a fixed dimension. We let be the smallest constant for which one has the restriction inequality
for all bounded measurable functions on the unit sphere equipped with surface measure , where is the ball of radius centred at the origin. The restriction conjecture of Stein for the sphere is then equivalent to the assertion that has a subpolynomial upper bound (or equivalently, is of subpolynomial size). Currently this is only known in dimension .
Example 3 (Multilinear Kakeya inequality) Again ranges over all of . Let be a fixed dimension, and let be compact subsets of the sphere which are transverse in the sense that there is a uniform lower bound for the wedge product of directions for (equivalently, there is no hyperplane through the origin that intersects all of the ). For each , we let be the smallest constant for which one has the multilinear Kakeya inequality
where for each , is a collection of infinite tubes in of radius oriented in a direction in , which are separated in the sense that for any two tubes in , either the directions of differ by an angle of at least , or are disjoint; and is our notation for the geometric mean
The multilinear Kakeya inequality of Bennett, Carbery, and myself establishes that is of subpolynomial size; a later argument of Guth improves this further by showing that is bounded (and in fact comparable to ).
Example 4 (Multilinear restriction theorem) Once again ranges over all of . Let be a fixed dimension, and let be compact subsets of the sphere which are transverse as in the previous example. For each , we let be the smallest constant for which one has the multilinear restriction inequality
for all bounded measurable functions on for . Then the multilinear restriction theorem of Bennett, Carbery, and myself establishes that is of subpolynomial size; it is known to be bounded for (as can be easily verified from Plancherel’s theorem), but it remains open whether it is bounded for any .
Example 5 (Decoupling for the paraboloid) now ranges over the square numbers. Let , and subdivide the unit cube into cubes of sidelength . For any , define the extension operators
and
for and . We also introduce the weight function
For any , let be the smallest constant for which one has the decoupling inequality
The decoupling theorem of Bourgain and Demeter asserts that is of subpolynomial size for all in the optimal range .
Example 6 (Decoupling for the moment curve) now ranges over the natural numbers. Let , and subdivide into intervals of length . For any , define the extension operators
and more generally
for . For any , let be the smallest constant for which one has the decoupling inequality
It was shown by Bourgain, Demeter, and Guth that is of subpolynomial size for all in the optimal range , which among other things implies the Vinogradov main conjecture (as discussed in this previous post).
It is convenient to use asymptotic notation to express these estimates. We write , , or to denote the inequality for some constant independent of the scale parameter , and write for . We write to denote a bound of the form where as along the given range of . We then write for , and for . Then the statement that is of polynomial size can be written as
while the statement that has a subpolynomial upper bound can be written as
and similarly the statement that is of subpolynomial size is simply
Many modern approaches to bounding quantities like in harmonic analysis rely on some sort of induction on scales approach in which is bounded using quantities such as for some exponents . For instance, suppose one is somehow able to establish the inequality
for all , and suppose that is also known to be of polynomial size. Then this implies that has a subpolynomial upper bound. Indeed, one can iterate this inequality to show that
for any fixed ; using the polynomial size hypothesis one thus has
for some constant independent of . As can be arbitrarily large, we conclude that for any , and hence is of subpolynomial size. (This sort of iteration is used for instance in my paper with Bennett and Carbery to derive the multilinear restriction theorem from the multilinear Kakeya theorem.)
Exercise 7 If is of polynomial size, and obeys the inequality
for any fixed , where the implied constant in the notation is independent of , show that has a subpolynomial upper bound. This type of inequality is used to equate various linear estimates in harmonic analysis with their multilinear counterparts; see for instance this paper of myself, Vargas, and Vega for an early example of this method.
In more recent years, more sophisticated induction on scales arguments have emerged in which one or more auxiliary quantities besides also come into play. Here is one example, this time being an abstraction of a short proof of the multilinear Kakeya inequality due to Guth. Let be the quantity in Example 3. We define similarly to for any , except that we now also require that the diameter of each set is at most . One can then observe the following estimates:
- (Triangle inequality) For any , we have
- (Multiplicativity) For any , one has
- (Loomis-Whitney inequality) We have
These inequalities now imply that has a subpolynomial upper bound, as we now demonstrate. Let be a large natural number (independent of ) to be chosen later. From many iterations of (6) we have
and hence by (7) (with replaced by ) and (5)
where the implied constant in the exponent does not depend on . As can be arbitrarily large, the claim follows. We remark that a nearly identical scheme lets one deduce decoupling estimates for the three-dimensional cone from that of the two-dimensional paraboloid; see the final section of this paper of Bourgain and Demeter.
Now we give a slightly more sophisticated example, abstracted from the proof of decoupling of the paraboloid by Bourgain and Demeter, as described in this study guide after specialising the dimension to and the exponent to the endpoint (the argument is also more or less summarised in this previous post). (In the cited papers, the argument was phrased only for the non-endpoint case , but it has been observed independently by many experts that the argument extends with only minor modifications to the endpoint .) Here we have a quantity that we wish to show is of subpolynomial size. For any and , one can define an auxiliary quantity . The precise definitions of and are given in the study guide (where they are called and respectively, setting and ) but will not be of importance to us for this discussion. Suffice to say that the following estimates are known:
- (Crude upper bound for ) is of polynomial size: .
- (Bilinear reduction, using parabolic rescaling) For any , one has
- (Crude upper bound for ) For any one has
- (Application of multilinear Kakeya and decoupling) If are sufficiently small (e.g. both less than ), then
In all of these bounds the implied constant exponents such as or are independent of and , although the implied constants in the notation can depend on both and . Here we gloss over an annoying technicality in that quantities such as , , or might not be an integer (and might not divide evenly into ), which is needed for the application to decoupling theorems; this can be resolved by restricting the scales involved to powers of two and restricting the values of to certain rational values, which introduces some complications to the later arguments below which we shall simply ignore as they do not significantly affect the numerology.
It turns out that these estimates imply that is of subpolynomial size. We give the argument as follows. As is known to be of polynomial size, we have some for which we have the bound
for all . We can pick to be the minimal exponent for which this bound is attained: thus
We will call this the upper exponent of . We need to show that . We assume for contradiction that . Let be a sufficiently small quantity depending on to be chosen later. From (10) we then have
for any sufficiently small . A routine iteration then gives
for any that is independent of , if is sufficiently small depending on . A key point here is that the implied constant in the exponent is uniform in (the constant comes from summing a convergent geometric series). We now use the crude bound (9) followed by (11) and conclude that
Applying (8) we then have
If we choose sufficiently large depending on (which was assumed to be positive), then the negative term will dominate the term. If we then pick sufficiently small depending on , then finally sufficiently small depending on all previous quantities, we will obtain for some strictly less than , contradicting the definition of . Thus cannot be positive, and hence has a subpolynomial upper bound as required.
Exercise 8 Show that one still obtains a subpolynomial upper bound if the estimate (10) is replaced with
for some constant , so long as we also improve (9) to
(This variant of the argument lets one handle the non-endpoint cases of the decoupling theorem for the paraboloid.)
To establish decoupling estimates for the moment curve, restricting to the endpoint case for sake of discussion, an even more sophisticated induction on scales argument was deployed by Bourgain, Demeter, and Guth. The proof is discussed in this previous blog post, but let us just describe an abstract version of the induction on scales argument. To bound the quantity , some auxiliary quantities are introduced for various exponents and and , with the following bounds:
- (Crude upper bound for ) is of polynomial size: .
- (Multilinear reduction, using non-isotropic rescaling) For any and , one has
- (Crude upper bound for ) For any and one has
- (Hölder) For and one has and also whenever , where .
- (Rescaled decoupling hypothesis) For , one has
- (Lower dimensional decoupling) If and , then
- (Multilinear Kakeya) If and , then
It is now substantially less obvious that these estimates can be combined to demonstrate that is of subpolynomial size; nevertheless this can be done. A somewhat complicated arrangement of the argument (involving some rather unmotivated choices of expressions to induct over) appears in my previous blog post; I give an alternate proof later in this post.
These examples indicate a general strategy to establish that some quantity is of subpolynomial size, by
- (i) Introducing some family of related auxiliary quantities, often parameterised by several further parameters;
- (ii) establishing as many bounds between these quantities and the original quantity as possible; and then
- (iii) appealing to some sort of “induction on scales” to conclude.
The first two steps (i), (ii) depend very much on the harmonic analysis nature of the quantities and the related auxiliary quantities, and the estimates in (ii) will typically be proven from various harmonic analysis inputs such as Hölder’s inequality, rescaling arguments, decoupling estimates, or Kakeya type estimates. The final step (iii) requires no knowledge of where these quantities come from in harmonic analysis, but the iterations involved can become extremely complicated.
In this post I would like to observe that one can clean up and made more systematic this final step (iii) by passing to upper exponents (12) to eliminate the role of the parameter (and also “tropicalising” all the estimates), and then taking similar limit superiors to eliminate some other less important parameters, until one is left with a simple linear programming problem (which, among other things, could be amenable to computer-assisted proving techniques). This method is analogous to that of passing to a simpler asymptotic limit object in many other areas of mathematics (for instance using the Furstenberg correspondence principle to pass from a combinatorial problem to an ergodic theory problem, as discussed in this previous post). We use the limit superior exclusively in this post, but many of the arguments here would also apply with one of the other generalised limit functionals discussed in this previous post, such as ultrafilter limits.
For instance, if is the upper exponent of a quantity of polynomial size obeying (4), then a comparison of the upper exponent of both sides of (4) one arrives at the scalar inequality
from which it is immediate that , giving the required subpolynomial upper bound. Notice how the passage to upper exponents converts the estimate to a simpler inequality .
Exercise 9 Repeat Exercise 7 using this method.
Similarly, given the quantities obeying the axioms (5), (6), (7), and assuming that is of polynomial size (which is easily verified for the application at hand), we see that for any real numbers , the quantity is also of polynomial size and hence has some upper exponent ; meanwhile itself has some upper exponent . By reparameterising we have the homogeneity
for any . Also, comparing the upper exponents of both sides of the axioms (5), (6), (7) we arrive at the inequalities
For any natural number , the third inequality combined with homogeneity gives , which when combined with the second inequality gives , which on combination with the first estimate gives . Sending to infinity we obtain as required.
Now suppose that , obey the axioms (8), (9), (10). For any fixed , the quantity is of polynomial size (thanks to (9) and the polynomial size of ), and hence has some upper exponent ; similarly has some upper exponent . (Actually, strictly speaking our axioms only give an upper bound on so we have to temporarily admit the possibility that , though this will soon be eliminated anyway.) Taking upper exponents of all the axioms we then conclude that
for all and .
Assume for contradiction that , then , and so the statement (20) simplifies to
At this point we can eliminate the role of and simplify the system by taking a second limit superior. If we write
then on taking limit superiors of the previous inequalities we conclude that
for all ; in particular . We take advantage of this by taking a further limit superior (or “upper derivative”) in the limit to eliminate the role of and simplify the system further. If we define
so that is the best constant for which as , then is finite, and by inserting this “Taylor expansion” into the right-hand side of (21) and conclude that
This leads to a contradiction when , and hence as desired.
Exercise 10 Redo Exercise 8 using this method.
The same strategy now clarifies how to proceed with the more complicated system of quantities obeying the axioms (13)–(19) with of polynomial size. Let be the exponent of . From (14) we see that for fixed , each is also of polynomial size (at least in upper bound) and so has some exponent (which for now we can permit to be ). Taking upper exponents of all the various axioms we can now eliminate and arrive at the simpler axioms
for all , , and , with the lower dimensional decoupling inequality
for and , and the multilinear Kakeya inequality
for and .
As before, if we assume for sake of contradiction that then the first inequality simplifies to
We can then again eliminate the role of by taking a second limit superior as , introducing
and thus getting the simplified axiom system
and also
for and , and
for and .
In view of the latter two estimates it is natural to restrict attention to the quantities for . By the axioms (22), these quantities are of the form . We can then eliminate the role of by taking another limit superior
The axioms now simplify to
for .
It turns out that the inequality (27) is strongest when , thus
for .
From the last two inequalities (28), (29) we see that a special role is likely to be played by the exponents
for and
for . From the convexity (25) and a brief calculation we have
for , hence from (28) we have
Similarly, from (25) and a brief calculation we have
for ; the same bound holds for if we drop the term with the factor, thanks to (24). Thus from (29) we have
for , again with the understanding that we omit the first term on the right-hand side when . Finally, (26) gives
Let us write out the system of equations we have obtained in full:
We can then eliminate the variables one by one. Inserting (33) into (32) we obtain
which simplifies to
Inserting this into (34) gives
which when combined with (35) gives
which simplifies to
Iterating this we get
for all and
for all . In particular
which on insertion into (36), (37) gives
which is absurd if . Thus and so must be of subpolynomial growth.
Remark 11 (This observation is essentially due to Heath-Brown.) If we let denote the column vector with entries (arranged in whatever order one pleases), then the above system of inequalities (32)–(36) (using (37) to handle the appearance of in (36)) reads
for some explicit square matrix with non-negative coefficients, where the inequality denotes pointwise domination, and is an explicit vector with non-positive coefficients that reflects the effect of (37). It is possible to show (using (24), (26)) that all the coefficients of are negative (assuming the counterfactual situation of course). Then we can iterate this to obtain
for any natural number . This would lead to an immediate contradiction if the Perron-Frobenius eigenvalue of exceeds because would now grow exponentially; this is typically the situation for “non-endpoint” applications such as proving decoupling inequalities away from the endpoint. In the endpoint situation discussed above, the Perron-Frobenius eigenvalue is , with having a non-trivial projection to this eigenspace, so the sum now grows at least linearly, which still gives the required contradiction for any . So it is important to gather “enough” inequalities so that the relevant matrix has a Perron-Frobenius eigenvalue greater than or equal to (and in the latter case one needs non-trivial injection of an induction hypothesis into an eigenspace corresponding to an eigenvalue ). More specifically, if is the spectral radius of and is a left Perron-Frobenius eigenvector, that is to say a non-negative vector, not identically zero, such that , then by taking inner products of (38) with we obtain
If this leads to a contradiction since is negative and is non-positive. When one still gets a contradiction as long as is strictly negative.
Remark 12 (This calculation is essentially due to Guo and Zorin-Kranich.) Here is a concrete application of the Perron-Frobenius strategy outlined above to the system of inequalities (32)–(37). Consider the weighted sum
I had secretly calculated the weights , as coming from the left Perron-Frobenius eigenvector of the matrix described in the previous remark, but for this calculation the precise provenance of the weights is not relevant. Applying the inequalities (31), (30) we see that is bounded by
(with the convention that the term is absent); this simplifies after some calculation to the bound
and this and (37) then leads to the required contradiction.
Exercise 13
- (i) Extend the above analysis to also cover the non-endpoint case . (One will need to establish the claim for .)
- (ii) Modify the argument to deal with the remaining cases by dropping some of the steps.
11 comments
Comments feed for this article
14 June, 2019 at 9:32 pm
domotorp
The matching lower bound inequality (2.5) is in the wrong way.
[Corrected, thanks – T.]
14 June, 2019 at 11:17 pm
None
The inequality in (7) seems a bit confusing to me, is the implicit constant a eps power of M instead of N?
[Reworded – T.]
15 June, 2019 at 3:32 am
George Shakan
This reminds me of section 4 of Heath brown’s exposition of Wooley’s proof of the cubic case of efficient congruencing in Vinogradov’s mean value theorem
Click to access 1512.03272.pdf
15 June, 2019 at 7:56 am
Terence Tao
Thanks for pointing this out! In particular Heath-Brown’s observation clarifies exactly when the iteration is “strong enough” to get subpolynomial bounds – one needs the coefficient matrix of the bounds to have an eigenvalue that either exceeds one in magnitude (in which case the iteration grows exponentially), or equals one but has a nontrivial additive component coming from the induction hypothesis (in which case the iteration grows polynomially). I’ve added a remark to this effect.
15 June, 2019 at 1:52 pm
Pavel Zorin-Kranich
For the Bourgain-Demeter-Guth iteration we computed the (right) Perron-Frobenius eigenvector of the matrix of bounds in a paper with Shaoming Guo, see Theorem 3.22 in
https://arxiv.org/abs/1811.02207v1
We also found that making this calculation explicit shortens the argument substantially.
16 June, 2019 at 7:31 am
Terence Tao
Thanks for this! I have added a version of your calculation as an additional remark to the post.
18 June, 2019 at 11:58 pm
Trevor Wooley
This observation that the eigen value should be at least 1 in order to establish the necessary exponential or logarithmic growth required to prove diagonal behaviour in Vinogradov’s mean value theorem also occurs in my own work establishing the cubic case of the main conjecture (arxiv:1401.3150, so January 2014) — this was the paper that Heath-Brown sought to simplify in his own exposition of December 2015. The observation is also critical to my slightly early paper (arxiv:1401.2932) “almost” proving the main conjecture in Vinogradov’s mean value theorem for all degrees, and also in the proof of the main conjecture via nested efficient congruencing. These are all p-adic methods using induction on scales of course, as opposed to real methods (corresponding to p equals infinity).
Incidentally, the first use of different real scales in this subject is due to Vinogradov himself in 1935 in his early work on his mean value theorem, though I suppose this can be traced even to work a decade earlier of Hardy and Littlewood on Waring’s problem.
15 June, 2019 at 6:00 am
Anonymous
Dear Pro.Tao,
Within the 100 years, no mathematician in the world has been expected and inspired like you. You are liked a light of the antique oil lighter, if the light is out, the spirit of math community will be down. We hope you have many progress in attacking problems which have not been solved in many decades yet. In sum, we have some words that sent to you:” Time is gold” . You will understand our idea, because you are very smart.
16 June, 2019 at 6:31 pm
George
really enjoy your article and books
24 June, 2019 at 12:03 pm
Andy
You are still smart. While I am unemployed for a long long time, and I fell I’m getting more and more stupid.
24 June, 2019 at 3:48 pm
Anonymous
C’mon, mate! Cheer up! And please find something to laugh or smile about. And best wishes to you. :-)