You are currently browsing the tag archive for the ‘random sampling’ tag.

Let ${G}$ be a finite set of order ${N}$; in applications ${G}$ will be typically something like a finite abelian group, such as the cyclic group ${{\bf Z}/N{\bf Z}}$. Let us define a ${1}$-bounded function to be a function ${f: G \rightarrow {\bf C}}$ such that ${|f(n)| \leq 1}$ for all ${n \in G}$. There are many seminorms ${\| \|}$ of interest that one places on functions ${f: G \rightarrow {\bf C}}$ that are bounded by ${1}$ on ${1}$-bounded functions, such as the Gowers uniformity seminorms ${\| \|_k}$ for ${k \geq 1}$ (which are genuine norms for ${k \geq 2}$). All seminorms in this post will be implicitly assumed to obey this property.

In additive combinatorics, a significant role is played by inverse theorems, which abstractly take the following form for certain choices of seminorm ${\| \|}$, some parameters ${\eta, \varepsilon>0}$, and some class ${{\mathcal F}}$ of ${1}$-bounded functions:

Theorem 1 (Inverse theorem template) If ${f}$ is a ${1}$-bounded function with ${\|f\| \geq \eta}$, then there exists ${F \in {\mathcal F}}$ such that ${|\langle f, F \rangle| \geq \varepsilon}$, where ${\langle,\rangle}$ denotes the usual inner product

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

Informally, one should think of ${\eta}$ as being somewhat small but fixed independently of ${N}$, ${\varepsilon}$ as being somewhat smaller but depending only on ${\eta}$ (and on the seminorm), and ${{\mathcal F}}$ as representing the “structured functions” for these choices of parameters. There is some flexibility in exactly how to choose the class ${{\mathcal F}}$ of structured functions, but intuitively an inverse theorem should become more powerful when this class is small. Accordingly, let us define 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 can be expected to be a useful tool. This concept arose in some discussions I had with Ben Green many years ago, but never appeared in print, so I decided to record some observations we had on this concept here on this blog.

Lebesgue norms ${\| f\|_{L^p} := ({\bf E}_{n \in G} |f(n)|^p)^{1/p}}$ for ${1 < p < \infty}$ have exponentially large entropy (and so inverse theorems are not expected to be useful in this case):

Proposition 2 (${L^p}$ norm has exponentially large 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 least ${\exp( c \varepsilon^2 N)}$ for some absolute constant ${c>0}$.

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

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

and hence by the triangle inequality we have

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

where ${F}$ is either the real or imaginary part of ${|f|^{p-2} f}$, which takes values in ${[-1,1]}$. If we let ${\tilde F}$ be ${F}$ rounded to the nearest multiple of ${\eta^p/4}$, then by the triangle inequality again we have

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

There are only at most ${1+8/\eta^p}$ possible values for each value ${\tilde F(n)}$ of ${\tilde F}$, and hence at most ${(1+8/\eta^p)^N}$ possible choices for ${\tilde F}$. This gives the first claim.

Now suppose that there is an ${(\eta,\varepsilon)}$-inverse theorem for some ${{\mathcal F}}$ of cardinality ${M}$. If we let ${f}$ be a random sign function (so the ${f(n)}$ are independent random variables taking values in ${-1,+1}$ with equal probability), then there is a random ${F \in {\mathcal F}}$ such that

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

and hence by the pigeonhole principle there is a deterministic ${F \in {\mathcal F}}$ such that

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

On the other hand, from the Hoeffding inequality one has

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

for some absolute constant ${c}$, hence

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

as claimed. $\Box$

Most seminorms of interest in additive combinatorics, such as the Gowers uniformity norms, are bounded by some finite ${L^p}$ norm thanks to Hölder’s inequality, so from the above proposition and the obvious monotonicity properties of entropy, we conclude that all Gowers norms on finite abelian groups ${G}$ have at most exponential inverse theorem entropy. But we can do significantly better than this:

• For the ${U^1}$ seminorm ${\|f\|_{U^1(G)} := |{\bf E}_{n \in G} f(n)|}$, one can simply take ${{\mathcal F} = \{1\}}$ to consist of the constant function ${1}$, and the ${(\eta,\eta)}$-entropy is clearly equal to ${1}$ for any ${0 < \eta < 1}$.
• For the ${U^2}$ norm, the standard Fourier-analytic inverse theorem asserts that if ${\|f\|_{U^2(G)} \geq \eta}$ then ${|\langle f, e(\xi \cdot) \rangle| \geq \eta^2}$ 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 groups for ${k > 2}$, the inverse theorem proved by Green, Ziegler, and myself gives 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 degree ${k-1}$ in a finite collection of cardinality ${O_{\eta,k}(1)}$, some polynomial sequence ${g: {\bf Z} \rightarrow G}$ (which was subsequently observed by Candela-Sisask (see also Manners) that one can choose to be ${N}$-periodic), and some Lipschitz function ${F: G/\Gamma \rightarrow {\bf C}}$ of Lipschitz norm ${O_{\eta,k}(1)}$. By the Arzela-Ascoli theorem, the number of possible ${F}$ (up to uniform errors of size at most ${\varepsilon/2}$, say) is ${O_{\eta,k}(1)}$. By standard arguments one can also ensure that the coefficients of the polynomial ${g}$ are ${O_{\eta,k}(1)}$, and then by periodicity there are only ${O(N^{O_{\eta,k}(1)}}$ such polynomials. As a consequence, the ${(\eta,\varepsilon)}$-entropy is of polynomial size ${O_{\eta,k}( N^{O_{\eta,k}(1)} )}$ (a fact that seems to have first been implicitly observed in Lemma 6.2 of this paper of Frantzikinakis; thanks to Ben Green for this reference). One can obtain more precise dependence on ${\eta,k}$ using the quantitative version of this inverse theorem due to Manners; back of the envelope calculations using Section 5 of that paper suggest 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 reduce the entropy to ${O_k( \exp(\exp(\eta^{-O_k(1)})) N^{\eta^{-O_k(1)}})}$ at the cost of degrading ${\varepsilon}$ to ${1/\exp\exp( O(\eta^{-O(1)}))}$.
• If one replaces the cyclic group ${{\bf Z}/N{\bf Z}}$ by a vector space ${{\bf F}_p^n}$ over some fixed finite field ${{\bf F}_p}$ of prime order (so that ${N=p^n}$), then the inverse theorem of Ziegler and myself (available in both high and low characteristic) allows one to obtain an ${(\eta,\varepsilon)}$-inverse theorem for some ${\varepsilon \gg_{k,\eta} 1}$ and ${{\mathcal F}}$ the collection of non-classical degree ${k-1}$ polynomial phases from ${{\bf F}_p^n}$ to ${S^1}$, which one can normalize to equal ${1}$ at the origin, and then by the classification of such polynomials one can calculate that the ${(\eta,\varepsilon)}$ entropy is of quasipolynomial size ${\exp( O_{p,k}(n^{k-1}) ) = \exp( O_{p,k}( \log^{k-1} N ) )}$ in ${N}$. By using the recent work of Gowers and Milicevic, one can make the dependence on ${p,k}$ here more precise, but we will not perform these calcualtions here.
• For the ${U^3(G)}$ norm on an arbitrary finite abelian group, the recent inverse theorem of Jamneshan and myself gives (after some calculations) a bound of the polynomial form ${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 improve slightly to ${O( q^{O(n^2)} N^{\eta^{-O(1)}})}$ if one degrades ${\varepsilon}$ to ${1/\exp(\eta^{-O(1)})}$, where ${q}$ is the maximal order of an element of ${G}$, and ${n}$ is the rank (the number of elements needed to generate ${G}$). This bound is polynomial in ${N}$ in the cyclic group case and quasipolynomial in general.

For general finite abelian groups ${G}$, we do not yet have an inverse theorem of comparable power to the ones mentioned above that give polynomial or quasipolynomial upper bounds on the entropy. However, there is a cheap argument that at least gives some subexponential bounds:

Proposition 3 (Cheap subexponential bound) 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 large ${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 standard random sampling argument, of the type used for instance by Croot-Sisask or Briet-Gopi (thanks to Ben Green for this latter reference). We can assume that ${N \geq \eta^{-C_k}}$ for some sufficiently large ${C_k>0}$, since otherwise the claim follows from Proposition 2.

Let ${A}$ be a random subset of ${{\bf Z}/N{\bf Z}}$ with the events ${n \in A}$ being iid with probability ${0 < p < 1}$ to be chosen later, conditioned to the event ${|A| \leq 2pN}$. Let ${f}$ be a ${1}$-bounded function. By a standard second moment calculation, we see that with probability at least ${1/2}$, we 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 choose ${p := C \eta^{-2^{k+1}/(2^k-1)} / N^{\frac{k+1}{2^k-1}}}$ for some sufficiently large ${C = C_k > 0}$, then for any ${1}$-bounded ${f}$ with ${\|f\|_{U^k(G)} \geq \eta/2}$, one has with probability at 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 can write the left-hand side as ${|\langle f, F \rangle|}$ where ${F}$ is the randomly sampled dual function

$\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}^{|\omega|+1} \frac{1}{p} 1_A f(n + \omega \cdot h).$

Unfortunately, ${F}$ is not ${1}$-bounded in general, but we 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 side can be shown to be ${1+o(1)}$ on the average, so we can condition on the event that the right-hand side is ${O(1)}$ without significant loss in falure probability.

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

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

where ${\tilde F}$ is the discretised randomly sampled dual function

$\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}^{|\omega|+1} \frac{1}{p} \tilde f_A(n + \omega \cdot h).$

For any given ${A}$, there are at most ${2np}$ places ${n}$ where ${\tilde f_A(n)}$ can be non-zero, and in those places there are ${O_k( \eta^{-2^{k}})}$ possible values for ${\tilde f_A(n)}$. Thus, if we let ${{\mathcal F}_A}$ be the collection of all possible ${\tilde f_A}$ associated 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 have

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

with probability at least ${1/2}$.

Now we remove the failure probability by independent resampling. By rounding to the nearest Gaussian integer multiple of ${c_k \eta^{2^k}}$ in the unit disk for a sufficiently small ${c_k>0}$, one can find a family ${{\mathcal G}}$ of cardinality ${O( \eta^{-O_k(N)})}$ consisting of ${1}$-bounded functions ${\tilde f}$ of ${U^k(G)}$ norm at least ${\eta/2}$ such that for every ${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 independent samples of ${A}$ for some ${M}$ to be chosen later. By the preceding discussion, we see that with probability at least ${1 - 2^{-M}}$, we 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 bound, if we choose ${M = \lfloor C N \log \frac{1}{\eta} \rfloor}$ for a large enough ${C = C_k}$, we can find ${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 hence 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}}$ (applying some truncation and rescaling to these ${L^2}$-bounded functions to make them ${L^\infty}$-bounded, and then ${1}$-bounded), we obtain the claim. $\Box$

One way to obtain lower bounds on the inverse theorem entropy is to produce a collection of almost orthogonal functions with large norm. More precisely:

Proposition 4 Let ${\| \|}$ be a seminorm, let ${0 < \varepsilon \leq \eta < 1}$, and suppose that one has a collection ${f_1,\dots,f_M}$ of ${1}$-bounded functions such that for all ${i=1,\dots,M}$, ${\|f_i\| \geq \eta}$ one has ${|\langle f_i, f_j \rangle| \leq \varepsilon^2/2}$ for all but at most ${L}$ choices of ${j \in \{1,\dots,M\}}$ for all distinct ${i,j \in \{1,\dots,M\}}$. Then the ${(\eta, \varepsilon)}$-entropy of ${\| \|}$ is at least ${\varepsilon^2 M / 2L}$.

Proof: Suppose we have an ${(\eta,\varepsilon)}$-inverse theorem with some family ${{\mathcal F}}$. Then for each ${i=1,\dots,M}$ there is ${F_i \in {\mathcal F}}$ such that ${|\langle f_i, F_i \rangle| \geq \varepsilon}$. By the pigeonhole principle, there is thus ${F \in {\mathcal F}}$ such that ${|\langle f_i, F \rangle| \geq \varepsilon}$ for all ${i}$ in a subset ${I}$ of ${\{1,\dots,M\}}$ of cardinality at least ${M/|{\mathcal F}|}$:

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

We can sum this to obtain

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

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

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

and hence by the triangle inequality

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

On the other hand, by hypothesis we can bound the left-hand side by ${|I| (L + \varepsilon^2 |I|/2)}$. Rearranging, we conclude that

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

and hence

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

giving the claim. $\Box$

Thus for instance:

• For the ${U^2(G)}$ norm, one can take ${f_1,\dots,f_M}$ to be the family of linear exponential phases ${n \mapsto e(\xi \cdot n)}$ with ${M = N}$ and ${L=1}$, and obtain a linear lower bound of ${\varepsilon^2 N/2}$ for the ${(\eta,\varepsilon)}$-entropy, thus matching the upper bound of ${N}$ up to constants when ${\varepsilon}$ is fixed.
• For the ${U^k({\bf Z}/N{\bf Z})}$ norm, a similar calculation using polynomial phases of degree ${k-1}$, combined with the Weyl sum estimates, gives a lower bound of ${\gg_{k,\varepsilon} N^{k-1}}$ for the ${(\eta,\varepsilon)}$-entropy for any fixed ${\eta,\varepsilon}$; by considering nilsequences as well, together with nilsequence equidistribution theory, one can replace the exponent ${k-1}$ here by some quantity that goes to infinity as ${\eta \rightarrow 0}$, though I have not attempted to calculate the exact rate.
• For the ${U^k({\bf F}_p^n)}$ norm, another similar calculation using polynomial phases of degree ${k-1}$ should give a lower bound of ${\gg_{p,k,\eta,\varepsilon} \exp( c_{p,k,\eta,\varepsilon} n^{k-1} )}$ for the ${(\eta,\varepsilon)}$-entropy, though I have not fully performed the calculation.

We close with one final example. Suppose ${G}$ is a product ${G = A \times B}$ of two sets ${A,B}$ of cardinality ${\asymp \sqrt{N}}$, and we consider the Gowers box 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 possible choice of class ${{\mathcal F}}$ here are the indicators ${1_{U \times V}}$ of “rectangles” ${U \times V}$ with ${U \subset A}$, ${V \subset B}$ (cf. this previous blog post on cut norms). By standard calculations, one can use this class to show 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 part of Proposition 2 shows that this is the correct order of growth in ${N}$. In contrast, a modification of Proposition 3 only gives an upper bound of the form ${O( \exp( O( N^{2/3} ) ) )}$ (the bottleneck is ensuring that the randomly sampled dual functions stay bounded in ${L^2}$), which shows that while this cheap bound is not optimal, it can still broadly give the correct “type” of bound (specifically, intermediate growth between polynomial and exponential).