Let be a finite set of order ; in purposes shall be sometimes one thing like a finite abelian group, such because the cyclic group . Allow us to outline a -bounded perform to be a perform such that for all . There are a lot of seminorms of curiosity that one locations on features which can be bounded by on -bounded features, such because the Gowers uniformity seminorms for (that are real norms for ). All seminorms on this submit shall be implicitly assumed to obey this property.
In additive combinatorics, a major function is performed by inverse theorems, which abstractly take the next type for sure decisions of seminorm , some parameters , and a few class of -bounded features:
Theorem 1 (Inverse theorem template) If is a -bounded perform with , then there exists such that , the place denotes the same old internal product
Informally, one ought to consider as being considerably small however fastened independently of , as being considerably smaller however relying solely on (and on the seminorm), and as representing the “structured features” for these decisions of parameters. There may be some flexibility in precisely how to decide on the category of structured features, however intuitively an inverse theorem ought to turn out to be extra highly effective when this class is small. Accordingly, allow us to outline the -entropy of the seminorm to be the least cardinality of for which such an inverse theorem holds. Seminorms with low entropy are ones for which inverse theorems will be anticipated to be a great tool. This idea arose in some discussions I had with Ben Inexperienced a few years in the past, however by no means appeared in print, so I made a decision to file some observations we had on this idea right here on this weblog.
Lebesgue norms for have exponentially giant entropy (and so inverse theorems are usually not anticipated to be helpful on this case):
Proof: If is -bounded with , then we now have
and therefore by the triangle inequality we now have
the place is both the actual or imaginary a part of , which takes values in . If we let be rounded to the closest a number of of , then by the triangle inequality once more we now have
There are solely at most attainable values for every worth of , and therefore at most choices for . This provides the primary declare.
Now suppose that there’s an -inverse theorem for some of cardinality . If we let be a random signal perform (so the are impartial random variables taking values in with equal likelihood), then there’s a random such that
and therefore by the pigeonhole precept there’s a deterministic such that
Alternatively, from the Hoeffding inequality one has
for some absolute fixed , therefore
Most seminorms of curiosity in additive combinatorics, such because the Gowers uniformity norms, are bounded by some finite norm due to Hölder’s inequality, so from the above proposition and the apparent monotonicity properties of entropy, we conclude that each one Gowers norms on finite abelian teams have at most exponential inverse theorem entropy. However we are able to do considerably higher than this:
- For the seminorm , one can merely take to include the fixed perform , and the -entropy is clearly equal to for any .
- For the norm, the usual Fourier-analytic inverse theorem asserts that if then for some Fourier character . Thus the -entropy is at most .
- For the norm on cyclic teams for , the inverse theorem proved by Inexperienced, Ziegler, and myself offers an -inverse theorem for some and consisting of nilsequences for some filtered nilmanifold of diploma in a finite assortment of cardinality , some polynomial sequence (which was subsequently noticed by Candela-Sisask (see additionally Manners) that one can select to be -periodic), and a few Lipschitz perform of Lipschitz norm . By the Arzela-Ascoli theorem, the variety of attainable (as much as uniform errors of measurement at most , say) is . By customary arguments one may be sure that the coefficients of the polynomial are , after which by periodicity there are solely such polynomials. As a consequence, the -entropy is of polynomial measurement (a undeniable fact that appears to have first been implicitly noticed in Lemma 6.2 of this paper of Frantzikinakis; due to Ben Inexperienced for this reference). One can receive extra exact dependence on utilizing the quantitative model of this inverse theorem because of Manners; again of the envelope calculations utilizing Part 5 of that paper counsel to me that one can take to be polynomial in and the entropy to be of the order , or alternatively one can scale back the entropy to at the price of degrading to .
- If one replaces the cyclic group by a vector house over some fastened finite discipline of prime order (in order that ), then the inverse theorem of Ziegler and myself (accessible in each excessive and low attribute) permits one to acquire an -inverse theorem for some and the gathering of non-classical diploma polynomial phases from to , which one can normalize to equal on the origin, after which by the classification of such polynomials one can calculate that the entropy is of quasipolynomial measurement in . By utilizing the latest work of Gowers and Milicevic, one could make the dependence on right here extra exact, however we won’t carry out these calcualtions right here.
- For the norm on an arbitrary finite abelian group, the latest inverse theorem of Jamneshan and myself offers (after some calculations) a certain of the polynomial type on the -entropy for some , which one can enhance barely to if one degrades to , the place is the maximal order of a component of , and is the rank (the variety of components wanted to generate ). This certain is polynomial in within the cyclic group case and quasipolynomial typically.
For normal finite abelian teams , we don’t but have an inverse theorem of comparable energy to those talked about above that give polynomial or quasipolynomial higher bounds on the entropy. Nonetheless, there’s a low cost argument that at the least offers some subexponential bounds:
Proof: (Sketch) We use a typical random sampling argument, of the kind used as an example by Croot-Sisask or Briet-Gopi (due to Ben Inexperienced for this latter reference). We are able to assume that for some sufficiently giant , since in any other case the declare follows from Proposition 2.
Let be a random subset of with the occasions being iid with likelihood to be chosen later, conditioned to the occasion . Let be a -bounded perform. By a typical second second calculation, we see that with likelihood at the least , we now have
Thus, by the triangle inequality, if we select for some sufficiently giant , then for any -bounded with , one has with likelihood at the least that
We are able to write the left-hand facet as the place is the randomly sampled twin perform
Sadly, isn’t -bounded typically, however we now have
and the right-hand facet will be proven to be on the common, so we are able to situation on the occasion that the right-hand facet is with out vital loss in falure likelihood.
If we then let be rounded to the closest Gaussian integer a number of of within the unit disk, one has from the triangle inequality that
the place is the discretised randomly sampled twin perform
For any given , there are at most locations the place will be non-zero, and in these locations there are attainable values for . Thus, if we let be the gathering of all attainable related to a given , the cardinality of this set is , and for any with , we now have
with likelihood at the least .
Now we take away the failure likelihood by impartial resampling. By rounding to the closest Gaussian integer a number of of within the unit disk for a small enough , one can discover a household of cardinality consisting of -bounded features of norm at the least such that for each -bounded with there exists such that
Now, let be impartial samples of for some to be chosen later. By the previous dialogue, we see that with likelihood at the least , we now have
for any given , so by the union certain, if we select for a big sufficient , we are able to discover such that
for all , and therefore y the triangle inequality
Taking to be the union of the (making use of some truncation and rescaling to those -bounded features to make them -bounded, after which -bounded), we receive the declare.
One approach to receive decrease bounds on the inverse theorem entropy is to provide a set of virtually orthogonal features with giant norm. Extra exactly:
Proposition 4 Let be a seminorm, let , and suppose that one has a set of -bounded features such that for all , one has for all however at most decisions of for all distinct . Then the -entropy of is at the least .
Proof: Suppose we now have an -inverse theorem with some household . Then for every there may be such that . By the pigeonhole precept, there may be thus such that for all in a subset of of cardinality at the least :
We are able to sum this to acquire
for some complicated numbers of unit magnitude. By Cauchy-Schwarz, this means
and therefore by the triangle inequality
Alternatively, by speculation we are able to certain the left-hand facet by . Rearranging, we conclude that
giving the declare.
Thus as an example:
- For the norm, one can take to be the household of linear exponential phases with and , and procure a linear decrease certain of for the -entropy, thus matching the higher certain of as much as constants when is fastened.
- For the norm, an identical calculation utilizing polynomial phases of diploma , mixed with the Weyl sum estimates, offers a decrease certain of for the -entropy for any fastened ; by contemplating nilsequences as effectively, along with nilsequence equidistribution idea, one can substitute the exponent right here by some amount that goes to infinity as , although I’ve not tried to calculate the precise price.
- For the norm, one other comparable calculation utilizing polynomial phases of diploma ought to give a decrease certain of for the -entropy, although I’ve not totally carried out the calculation.
We shut with one last instance. Suppose is a product of two units of cardinality , and we contemplate the Gowers field norm
One attainable selection of sophistication listed below are the symptoms of “rectangles” with , (cf. this earlier weblog submit on reduce norms). By customary calculations, one can use this class to point out that the -entropy of is , and a variant of the proof of the second a part of Proposition 2 exhibits that that is the proper order of development in . In distinction, a modification of Proposition 3 solely offers an higher certain of the shape (the bottleneck is guaranteeing that the randomly sampled twin features keep bounded in ), which exhibits that whereas this low cost certain isn’t optimum, it could possibly nonetheless broadly give the proper “kind” of certain (particularly, intermediate development between polynomial and exponential).