Friday, June 17, 2022
HomeMathNotes on inverse theorem entropy

# Notes on inverse theorem entropy

Let ${G}$ be a finite set of order ${N}$; in purposes ${G}$ shall be sometimes one thing like a finite abelian group, such because the cyclic group ${{bf Z}/N{bf Z}}$. Allow us to outline a ${1}$-bounded perform to be a perform ${f: G rightarrow {bf C}}$ such that $leq 1$ for all ${n in G}$. There are a lot of seminorms  of curiosity that one locations on features ${f: G rightarrow {bf C}}$ which can be bounded by ${1}$ on ${1}$-bounded features, such because the Gowers uniformity seminorms $_k$ for ${k geq 1}$ (that are real norms for ${k geq 2}$). 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 ${eta, varepsilon>0}$, and a few class ${{mathcal F}}$ of ${1}$-bounded features:

Theorem 1 (Inverse theorem template) If ${f}$ is a ${1}$-bounded perform with $f$, then there exists ${F in {mathcal F}}$ such that $langle f, F rangle$, the place ${langle,rangle}$ denotes the same old internal product

$displaystyle langle f, F rangle := {bf E}_{n in G} f(n) overline{F(n)}.$

Informally, one ought to consider ${eta}$ as being considerably small however fastened independently of ${N}$, ${varepsilon}$ as being considerably smaller however relying solely on ${eta}$ (and on the seminorm), and ${{mathcal F}}$ as representing the “structured features” for these decisions of parameters. There may be some flexibility in precisely how to decide on the category ${{mathcal F}}$ 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 ${(eta,varepsilon)}$-entropy of the seminorm  to be the least cardinality of ${{mathcal F}}$ 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 ${| f|_{L^p} := ({bf E}_{n in G} |f(n)|^p)^{1/p}}$ for ${1 < p < infty}$ have exponentially giant entropy (and so inverse theorems are usually not anticipated to be helpful on this case):

Proposition 2 (${L^p}$ norm has exponentially giant inverse entropy) Let ${1 < p < infty}$ and ${0 < eta < 1}$. Then the ${(eta,eta^p/4)}$-entropy of ${| |_{L^p}}$ is at most ${(1+8/eta^p)^N}$. Conversely, for any ${varepsilon>0}$, the ${(eta,varepsilon)}$-entropy of ${| |_{L^p}}$ is at the least ${exp( c varepsilon^2 N)}$ for some absolute fixed ${c>0}$.

Proof: If ${f}$ is ${1}$-bounded with ${|f|_{L^p} geq eta}$, then we now have

$displaystyle |langle f, |f|^{p-2} f rangle| geq eta^p$

and therefore by the triangle inequality we now have

$displaystyle |langle f, F rangle| geq eta^p/2$

the place ${F}$ is both the actual or imaginary a part of ${|f|^{p-2} f}$, which takes values in ${[-1,1]}$. If we let ${tilde F}$ be ${F}$ rounded to the closest a number of of ${eta^p/4}$, then by the triangle inequality once more we now have

$displaystyle |langle f, tilde F rangle| geq eta^p/4.$

There are solely at most ${1+8/eta^p}$ attainable values for every worth ${tilde F(n)}$ of ${tilde F}$, and therefore at most ${(1+8/eta^p)^N}$ choices for ${tilde F}$. This provides the primary declare.

Now suppose that there’s an ${(eta,varepsilon)}$-inverse theorem for some ${{mathcal F}}$ of cardinality ${M}$. If we let ${f}$ be a random signal perform (so the ${f(n)}$ are impartial random variables taking values in ${-1,+1}$ with equal likelihood), then there’s a random ${F in {mathcal F}}$ such that

$displaystyle |langle f, F rangle| geq varepsilon$

and therefore by the pigeonhole precept there’s a deterministic ${F in {mathcal F}}$ such that

$displaystyle {bf P}( |langle f, F rangle| geq varepsilon ) leq 1/M.$

Alternatively, from the Hoeffding inequality one has

$displaystyle {bf P}( |langle f, F rangle| geq varepsilon ) ll exp( - c varepsilon^2 N )$

for some absolute fixed ${c}$, therefore

$displaystyle M geq exp( c varepsilon^2 N )$

as claimed. $Box$

Most seminorms of curiosity in additive combinatorics, such because the Gowers uniformity norms, are bounded by some finite ${L^p}$ 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 ${G}$ have at most exponential inverse theorem entropy. However we are able to do considerably higher than this:

• For the ${U^1}$ seminorm ${|f|_{U^1(G)} := |{bf E}_{n in G} f(n)|}$, one can merely take ${{mathcal F} = {1}}$ to include the fixed perform ${1}$, and the ${(eta,eta)}$-entropy is clearly equal to ${1}$ for any ${0 < eta < 1}$.
• For the ${U^2}$ norm, the usual Fourier-analytic inverse theorem asserts that if ${|f|_{U^2(G)} geq eta}$ then $langle f, e(xi cdot) rangle$ for some Fourier character ${xi in hat G}$. Thus the ${(eta,eta^2)}$-entropy is at most ${N}$.
• For the ${U^k({bf Z}/N{bf Z})}$ norm on cyclic teams for ${k > 2}$, the inverse theorem proved by Inexperienced, Ziegler, and myself offers an ${(eta,varepsilon)}$-inverse theorem for some ${varepsilon gg_{k,eta} 1}$ and ${{mathcal F}}$ consisting of nilsequences ${n mapsto F(g(n) Gamma)}$ for some filtered nilmanifold ${G/Gamma}$ of diploma ${k-1}$ in a finite assortment of cardinality ${O_{eta,k}(1)}$, some polynomial sequence ${g: {bf Z} rightarrow G}$ (which was subsequently noticed by Candela-Sisask (see additionally Manners) that one can select to be ${N}$-periodic), and a few Lipschitz perform ${F: G/Gamma rightarrow {bf C}}$ of Lipschitz norm ${O_{eta,k}(1)}$. By the Arzela-Ascoli theorem, the variety of attainable ${F}$ (as much as uniform errors of measurement at most ${varepsilon/2}$, say) is ${O_{eta,k}(1)}$. By customary arguments one may be sure that the coefficients of the polynomial ${g}$ are ${O_{eta,k}(1)}$, after which by periodicity there are solely ${O(N^{O_{eta,k}(1)}}$ such polynomials. As a consequence, the ${(eta,varepsilon)}$-entropy is of polynomial measurement ${O_{eta,k}( N^{O_{eta,k}(1)} )}$ (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 ${eta,k}$ 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 ${varepsilon = eta^{O_k(1)}}$ to be polynomial in ${eta}$ and the entropy to be of the order ${O_k( N^{exp(exp(eta^{-O_k(1)}))} )}$, or alternatively one can scale back the entropy to ${O_k( exp(exp(eta^{-O_k(1)})) N^{eta^{-O_k(1)}})}$ at the price of degrading ${varepsilon}$ to ${1/expexp( O(eta^{-O(1)}))}$.
• If one replaces the cyclic group ${{bf Z}/N{bf Z}}$ by a vector house ${{bf F}_p^n}$ over some fastened finite discipline ${{bf F}_p}$ of prime order (in order that ${N=p^n}$), then the inverse theorem of Ziegler and myself (accessible in each excessive and low attribute) permits one to acquire an ${(eta,varepsilon)}$-inverse theorem for some ${varepsilon gg_{k,eta} 1}$ and ${{mathcal F}}$ the gathering of non-classical diploma ${k-1}$ polynomial phases from ${{bf F}_p^n}$ to ${S^1}$, which one can normalize to equal ${1}$ on the origin, after which by the classification of such polynomials one can calculate that the ${(eta,varepsilon)}$ entropy is of quasipolynomial measurement ${exp( O_{p,k}(n^{k-1}) ) = exp( O_{p,k}( log^{k-1} N ) )}$ in ${N}$. By utilizing the latest work of Gowers and Milicevic, one could make the dependence on ${p,k}$ right here extra exact, however we won’t carry out these calcualtions right here.
• For the ${U^3(G)}$ 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 ${O( q^{O(n^2)} N^{exp(eta^{-O(1)})})}$ on the ${(eta,varepsilon)}$-entropy for some ${varepsilon gg eta^{O(1)}}$, which one can enhance barely to ${O( q^{O(n^2)} N^{eta^{-O(1)}})}$ if one degrades ${varepsilon}$ to ${1/exp(eta^{-O(1)})}$, the place ${q}$ is the maximal order of a component of ${G}$, and ${n}$ is the rank (the variety of components wanted to generate ${G}$). This certain is polynomial in ${N}$ within the cyclic group case and quasipolynomial typically.

For normal finite abelian teams ${G}$, 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:

Proposition 3 (Low-cost subexponential certain) Let ${k geq 2}$ and ${0 < eta < 1/2}$, and suppose that ${G}$ is a finite abelian group of order ${N geq eta^{-C_k}}$ for some sufficiently giant ${C_k}$. Then the ${(eta,c_k eta^{O_k(1)})}$-complexity of ${| |_{U^k(G)}}$ is at most ${O( exp( eta^{-O_k(1)} N^{1 - frac{k+1}{2^k-1}} ))}$.

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 ${N geq eta^{-C_k}}$ for some sufficiently giant ${C_k>0}$, since in any other case the declare follows from Proposition 2.

Let ${A}$ be a random subset of ${{bf Z}/N{bf Z}}$ with the occasions ${n in A}$ being iid with likelihood ${0 < p < 1}$ to be chosen later, conditioned to the occasion $leq 2pN$. Let ${f}$ be a ${1}$-bounded perform. By a typical second second calculation, we see that with likelihood at the least ${1/2}$, we now have

$displaystyle |f|_{U^k(G)}^{2^k} = {bf E}_{n, h_1,dots,h_k in G} f(n) prod_{omega in {0,1}^k backslash {0}} {mathcal C}^omega frac{1}{p} 1_A f(n + omega cdot h)$

$displaystyle + O((frac{1}{N^{k+1} p^{2^k-1}})^{1/2}).$

Thus, by the triangle inequality, if we select ${p := C eta^{-2^{k+1}/(2^k-1)} / N^{frac{k+1}{2^k-1}}}$ for some sufficiently giant ${C = C_k > 0}$, then for any ${1}$-bounded ${f}$ with ${|f|_{U^k(G)} geq eta/2}$, one has with likelihood at the least ${1/2}$ that

$displaystyle |{bf E}_{n, h_1,dots,h_k i2^n G} f(n) prod_{omega in {0,1}^k backslash {0}} {mathcal C}^omega frac{1}{p} 1_A f(n + omega cdot h)|$

$displaystyle geq eta^{2^k}/2^{2^k+1}.$

We are able to write the left-hand facet as $langle f, F rangle$ the place ${F}$ is the randomly sampled twin perform

$displaystyle F(n) := {bf E}_{n, h_1,dots,h_k in G} f(n) prod_{omega in {0,1}^k backslash {0}} {mathcal C}^+1 frac{1}{p} 1_A f(n + omega cdot h).$

Sadly, ${F}$ isn’t ${1}$-bounded typically, however we now have

$displaystyle |F|_{L^2(G)}^2 leq {bf E}_{n, h_1,dots,h_k ,h'_1,dots,h'_k in G}$

$displaystyle prod_{omega in {0,1}^k backslash {0}} frac{1}{p} 1_A(n + omega cdot h) frac{1}{p} 1_A(n + omega cdot h')$

and the right-hand facet will be proven to be ${1+o(1)}$ on the common, so we are able to situation on the occasion that the right-hand facet is ${O(1)}$ with out vital loss in falure likelihood.

If we then let ${tilde f_A}$ be ${1_A f}$ rounded to the closest Gaussian integer a number of of ${eta^{2^k}/2^{2^{10k}}}$ within the unit disk, one has from the triangle inequality that

$displaystyle |langle f, tilde F rangle| geq eta^{2^k}/2^{2^k+2}$

the place ${tilde F}$ is the discretised randomly sampled twin perform

$displaystyle tilde F(n) := {bf E}_{n, h_1,dots,h_k in G} f(n) prod_{omega in {0,1}^k backslash {0}} {mathcal C}^+1 frac{1}{p} tilde f_A(n + omega cdot h).$

For any given ${A}$, there are at most ${2np}$ locations ${n}$ the place ${tilde f_A(n)}$ will be non-zero, and in these locations there are ${O_k( eta^{-2^{k}})}$ attainable values for ${tilde f_A(n)}$. Thus, if we let ${{mathcal F}_A}$ be the gathering of all attainable ${tilde f_A}$ related to a given ${A}$, the cardinality of this set is ${O( exp( eta^{-O_k(1)} N^{1 - frac{k+1}{2^k-1}} ) )}$, and for any ${f}$ with ${|f|_{U^k(G)} geq eta/2}$, we now have

$displaystyle sup_{tilde F in {mathcal F}_A} |langle f, tilde F rangle| geq eta^{2^k}/2^{k+2}$

with likelihood at the least ${1/2}$.

Now we take away the failure likelihood by impartial resampling. By rounding to the closest Gaussian integer a number of of ${c_k eta^{2^k}}$ within the unit disk for a small enough ${c_k>0}$, one can discover a household ${{mathcal G}}$ of cardinality ${O( eta^{-O_k(N)})}$ consisting of ${1}$-bounded features ${tilde f}$ of ${U^k(G)}$ norm at the least ${eta/2}$ such that for each ${1}$-bounded ${f}$ with ${|f|_{U^k(G)} geq eta}$ there exists ${tilde f in {mathcal G}}$ such that

$displaystyle |f-tilde f|_{L^infty(G)} leq eta^{2^k}/2^{k+3}.$

Now, let ${A_1,dots,A_M}$ be impartial samples of ${A}$ for some ${M}$ to be chosen later. By the previous dialogue, we see that with likelihood at the least ${1 - 2^{-M}}$, we now have

$displaystyle sup_{tilde F in bigcup_{j=1}^M {mathcal F}_{A_j}} |langle tilde f, tilde F rangle| geq eta^{2^k}/2^{k+2}$

for any given ${tilde f in {mathcal G}}$, so by the union certain, if we select ${M = lfloor C N log frac{1}{eta} rfloor}$ for a big sufficient ${C = C_k}$, we are able to discover ${A_1,dots,A_M}$ such that

$displaystyle sup_{tilde F in bigcup_{j=1}^M {mathcal F}_{A_j}} |langle tilde f, tilde F rangle| geq eta^{2^k}/2^{k+2}$

for all ${tilde f in {mathcal G}}$, and therefore y the triangle inequality

$displaystyle sup_{tilde F in bigcup_{j=1}^M {mathcal F}_{A_j}} |langle f, tilde F rangle| geq eta^{2^k}/2^{k+3}.$

Taking ${{mathcal F}}$ to be the union of the ${{mathcal F}_{A_j}}$ (making use of some truncation and rescaling to those ${L^2}$-bounded features to make them ${L^infty}$-bounded, after which ${1}$-bounded), we receive the declare. $Box$

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 ${0 < varepsilon leq eta < 1}$, and suppose that one has a set ${f_1,dots,f_M}$ of ${1}$-bounded features such that for all ${i=1,dots,M}$, $f_i$ one has $langle f_i, f_j rangle$ for all however at most ${L}$ decisions of ${j in {1,dots,M}}$ for all distinct ${i,j in {1,dots,M}}$. Then the ${(eta, varepsilon)}$-entropy of  is at the least ${varepsilon^2 M / 2L}$.

Proof: Suppose we now have an ${(eta,varepsilon)}$-inverse theorem with some household ${{mathcal F}}$. Then for every ${i=1,dots,M}$ there may be ${F_i in {mathcal F}}$ such that $geq varepsilon$. By the pigeonhole precept, there may be thus ${F in {mathcal F}}$ such that $geq varepsilon$ for all ${i}$ in a subset ${I}$ of ${{1,dots,M}}$ of cardinality at the least ${M/|{mathcal F}|}$:

$displaystyle |I| geq M / |{mathcal F}|.$

We are able to sum this to acquire

$displaystyle |sum_{i in I} c_i langle f_i, F rangle| geq |I| varepsilon$

for some complicated numbers ${c_i}$ of unit magnitude. By Cauchy-Schwarz, this means

$displaystyle | sum_{i in I} c_i f_i |_{L^2(G)}^2 geq |I|^2 varepsilon^2$

and therefore by the triangle inequality

$displaystyle sum_{i,j in I} |langle f_i, f_j rangle| geq |I|^2 varepsilon^2.$

Alternatively, by speculation we are able to certain the left-hand facet by $I$. Rearranging, we conclude that

$displaystyle |I| leq 2 L / varepsilon^2$

and therefore

$displaystyle |{mathcal F}| geq varepsilon^2 M / 2L$

giving the declare. $Box$

Thus as an example:

• For the ${U^2(G)}$ norm, one can take ${f_1,dots,f_M}$ to be the household of linear exponential phases ${n mapsto e(xi cdot n)}$ with ${M = N}$ and ${L=1}$, and procure a linear decrease certain of ${varepsilon^2 N/2}$ for the ${(eta,varepsilon)}$-entropy, thus matching the higher certain of ${N}$ as much as constants when ${varepsilon}$ is fastened.
• For the ${U^k({bf Z}/N{bf Z})}$ norm, an identical calculation utilizing polynomial phases of diploma ${k-1}$, mixed with the Weyl sum estimates, offers a decrease certain of ${gg_{k,varepsilon} N^{k-1}}$ for the ${(eta,varepsilon)}$-entropy for any fastened ${eta,varepsilon}$; by contemplating nilsequences as effectively, along with nilsequence equidistribution idea, one can substitute the exponent ${k-1}$ right here by some amount that goes to infinity as ${eta rightarrow 0}$, although I’ve not tried to calculate the precise price.
• For the ${U^k({bf F}_p^n)}$ norm, one other comparable calculation utilizing polynomial phases of diploma ${k-1}$ ought to give a decrease certain of ${gg_{p,k,eta,varepsilon} exp( c_{p,k,eta,varepsilon} n^{k-1} )}$ for the ${(eta,varepsilon)}$-entropy, although I’ve not totally carried out the calculation.

We shut with one last instance. Suppose ${G}$ is a product ${G = A times B}$ of two units ${A,B}$ of cardinality ${asymp sqrt{N}}$, and we contemplate the Gowers field norm

$displaystyle |f|_{Box^2(G)}^4 := {bf E}_{a,a' in A; b,b' in B} f(a,b) overline{f}(a,b') overline{f}(a',b) f(a,b).$

One attainable selection of sophistication ${{mathcal F}}$ listed below are the symptoms ${1_{U times V}}$ of “rectangles” ${U times V}$ with ${U subset A}$, ${V subset B}$ (cf. this earlier weblog submit on reduce norms). By customary calculations, one can use this class to point out that the ${(eta, eta^4/10)}$-entropy of ${| |_{Box^2(G)}}$ is ${O( exp( O(sqrt{N}) )}$, and a variant of the proof of the second a part of Proposition 2 exhibits that that is the proper order of development in ${N}$. In distinction, a modification of Proposition 3 solely offers an higher certain of the shape ${O( exp( O( N^{2/3} ) ) )}$ (the bottleneck is guaranteeing that the randomly sampled twin features keep bounded in ${L^2}$), 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).

RELATED ARTICLES