Introduction
In this article we will study random configurations in the context of Fourier decoupling theory and will answer a question of Guth [13 ] . Heuristics coming from probability theory often play an important guiding role in Fourier analysis. The notions of square root cancellation, pseudo-randomness and probabilistic models for various Fourier-analytic and number theoretic objects can often tell us how these objects should behave. These heuristics can help us formulate conjectures and could also help us determine the types of inquiry that may yield progress on important problems. With this in mind, it can be fruitful to study random configurations in the context of Fourier analysis. For example, the work of Bourgain and Talagrand on Λ ( p ) \Lambda(p) Λ ( p ) sets [1 ] [19 ] , and the work of Mockenhaupt and Schlag [17 ] on the Hardy-Littlewood majorant problem have helped govern heuristics for the study of exponential sums and have also found applications in compressed sensing and signal processing (see [16 ] , [5 ] , [21 ] for illustrative examples). We investigate ideas along these lines in the context of Fourier decoupling. A central question in this context is: what is the typical behavior of natural Fourier analytic objects? In [18 ] the author investigated random configurations in the context of the Mizohata-Takeuchi conjecture, and showed that the Mizohata-Takeuchi conjecture is true most 1 of the time. We use some of the tools developed in [18 ] and refine them to answer questions about the typical behavior of configurations that naturally arise in the context of Fourier decoupling.
Setting of the Problem and Main Questions: We recall the setting of Fourier decoupling below. Let the set N 1 / N ( S 1 ) \mathcal{N}_{1/N}(S^1) N 1/ N ( S 1 ) be the 1 / N 1/N 1/ N neighborhood of the circle S 1 ⊂ R 2 S^1 \subset\mathbb{R}^2 S 1 ⊂ R 2 . Divide N 1 / N ( S 1 ) \mathcal{N}_{1/N}(S^1) N 1/ N ( S 1 ) into N N N approximate rectangles of dimensions 1 / N × 1 / N 2 1/N \times1/N^2 1/ N × 1/ N 2 and call this collection { θ } \{\theta\} { θ } . Let f ∈ S ( R 2 ) f \in\mathcal{S}(\mathbb{R}^2) f ∈ S ( R 2 ) (the Schwartz class on R 2 \mathbb{R}^2 R 2 ) be such that
f = ∑ θ f θ with supp ( f θ ^ ) ⊆ θ , (1) f = \sum_{\theta} f_\theta\quad\text{with} \quad\operatorname{supp}(\widehat{f_\theta}) \subseteq\theta, \tag*{(1)} f = θ ∑ f θ with supp ( f θ ) ⊆ θ , (1)
then a celebrated theorem of Bourgain and Demeter [2 ] states that
∥ f ∥ L 6 ( R 2 ) ≲ ϵ N ϵ ( ∑ θ ∥ f θ ∥ L 6 ( R 2 ) 2 ) 1 / 2 . (2) \|f\|_{L^6(\mathbb{R}^2)} \lesssim_\epsilon N^\epsilon\left(\sum_{\theta}\|f_\theta\|_{L^6(\mathbb{R}^2)}^2\right)^{1/2}. \tag*{(2)} ∥ f ∥ L 6 ( R 2 ) ≲ ϵ N ϵ ( θ ∑ ∥ f θ ∥ L 6 ( R 2 ) 2 ) 1/2 . (2)
Suppose in addition that for all θ \theta θ we also have that
∥ f θ ∥ L ∞ ( R 2 ) ≤ 1. \|f_\theta\|_{L^\infty(\mathbb{R}^2)} \leq1. ∥ f θ ∥ L ∞ ( R 2 ) ≤ 1.
A consequence of more refined work by Guth, Maldague, and Wang on the decoupling problem yields a bound for the size of the super level sets U λ U_\lambda U λ . In this setting, define U λ : = { x ∈ R 2 : ∣ f ( x ) ∣ > λ } U_\lambda:= \{x \in\mathbb{R}^2 : |f(x)| > \lambda\} U λ := { x ∈ R 2 : ∣ f ( x ) ∣ > λ } . Then if B N 2 : = { x : ∣ x ∣ ≤ N 2 } B_{N^2} := \{x : |x| \le N^2\} B N 2 := { x : ∣ x ∣ ≤ N 2 } (that is the ball of radius N 2 N^2 N 2 in R 2 \mathbb{R}^2 R 2 ), then in [15 ] it was shown that
∣ U λ ∩ B N 2 ∣ ≲ ϵ N ϵ N 7 λ 6 . (3) |U_\lambda\cap B_{N^2}| \lesssim_\epsilon N^\epsilon\frac{N^7}{\lambda^6}. \tag*{(3)} ∣ U λ ∩ B N 2 ∣ ≲ ϵ N ϵ λ 6 N 7 . (3)
In light of this bound we are led to the following natural questions:
Questions:
For different values of λ \lambda λ , what kinds of functions f f f saturate the bound (3) ?
What can we say about the structure of U λ U_\lambda U λ if the bound (3) is saturated?
One can think of these questions as asking for an ‘inverse theorem’ in the context of Fourier decoupling. Inverse theorems have played a significant role in recent developments in additive combinatorics and number theory (see this excellent talk of Gowers [8 ] for more background), and a satisfactory answer to these questions could lead to important insights about the behavior of exponential sums and related questions (see this survey [11 ] of Guth for more discussion).
When λ = N 1 / 2 \lambda= N^{1/2} λ = N 1/2 it is easy to find many examples where the bound (3) is saturated. On the other hand if N 1 / 2 < λ ≤ N N^{1/2} < \lambda\le N N 1/2 < λ ≤ N , there are very few examples of functions that saturate the bounds in (3) , and it is not clear whether this bound is sharp for all values of λ \lambda λ . We remark that the question of the sharpness of (3) was investigated in [7 ] , but in the case where S 1 S^1 S 1 was replaced by the parabola P 1 P^1 P 1 , where the authors were able to leverage techniques coming from the study of some well known exponential sums. These techniques do not carry over to the case of the circle S 1 S^1 S 1 . In [13 ] Guth asked whether the bound (3) can be saturated by a random set. In particular he asked the following:
If V V V is a union of N 7 λ − 6 N^7\lambda^{-6} N 7 λ − 6 random unit balls, and λ > N 1 / 2 \lambda> N^{1/2} λ > N 1/2 , is it typically possible (in the setting above) that ∥ f ∥ L 1 ( V ) ∼ λ ∣ V ∣ \|f\|_{L^1(V)} \sim\lambda|V| ∥ f ∥ L 1 ( V ) ∼ λ ∣ V ∣ ?
If the answer to this question was yes, then it would be that in the case when (3) was saturated, the set U λ ∩ B N 2 U_\lambda\cap B_{N^2} U λ ∩ B N 2 could look like a random set. However, we answer this question in the negative. In fact we show that on the random set V V V , f f f will be strictly smaller than what the superlevel set bound (3) guarantees. To set up our main theorem we first define the class of functions F \mathcal{F} F as follows:
F : = { f ∈ S ( R 2 ) : f = ∑ θ f θ , supp ( f θ ^ ) ⊂ θ , ∥ f θ ∥ L ∞ ( R 2 ) ≤ 1 } . (4) \mathcal{F} := \left\{ f \in\mathcal{S}(\mathbb{R}^2) : f = \sum_\theta f_\theta,\quad\operatorname{supp}(\widehat{f_\theta}) \subset\theta,\quad\|f_\theta\|_{L^\infty(\mathbb{R}^2)} \le1 \right\}. \tag*{(4)} F := { f ∈ S ( R 2 ) : f = θ ∑ f θ , supp ( f θ ) ⊂ θ , ∥ f θ ∥ L ∞ ( R 2 ) ≤ 1 } . (4)
where the collection { θ } \{\theta\} { θ } is defined as in (1). Our main theorem gives a precise asymptotic for sup f ∈ F ∫ V ∣ f ( x ) ∣ d x \sup_{f\in\mathcal{F}} \int_V |f(x)|dx sup f ∈ F ∫ V ∣ f ( x ) ∣ d x .
Theorem 1 (Corollary of Main Theorem, Informal Statement). In the setting above, let V λ V_\lambda V λ be a random collection of N 7 λ − 6 N^7\lambda^{-6} N 7 λ − 6 unit balls contained in B N 2 B_{N^2} B N 2 , then with high probability
sup f ∈ F ∥ f ∥ L 1 ( V λ ) ∼ ϵ { N 1 / 2 ∣ V ∣ when N 1 / 2 < λ ≤ N 5 / 6 , λ 3 N 2 ∣ V ∣ when N 5 / 6 ≤ λ ≤ N (5) \sup_{f\in\mathcal{F}} \|f\|_{L^1(V_\lambda)} \sim_\epsilon
\begin{cases}
N^{1/2}|V| & \text{when } N^{1/2}<\lambda\le N^{5/6},\\
\frac{\lambda^3}{N^2}|V| & \text{when } N^{5/6}\le\lambda\le N
\end{cases} \tag*{(5)} f ∈ F sup ∥ f ∥ L 1 ( V λ ) ∼ ϵ { N 1/2 ∣ V ∣ N 2 λ 3 ∣ V ∣ when N 1/2 < λ ≤ N 5/6 , when N 5/6 ≤ λ ≤ N (5)
In any case one can deduce that whenever N 1 / 2 ≤ λ < N N^{1/2} \le\lambda< N N 1/2 ≤ λ < N , that
sup f ∈ F ∥ f ∥ L 1 ( V λ ) ∼ o ( λ ) ∣ V λ ∣ . (6) \sup_{f\in\mathcal{F}}\|f\|_{L^1(V_\lambda)} \sim o(\lambda)|V_\lambda|. \tag*{(6)} f ∈ F sup ∥ f ∥ L 1 ( V λ ) ∼ o ( λ ) ∣ V λ ∣. (6)
What this shows is that a set U λ U_\lambda U λ that saturates (3) cannot look random. From here, one can deduce that examples of sets U λ ∩ B N 2 U_\lambda\cap B_{N^2} U λ ∩ B N 2 that saturate (3) must possess some kind of special structure . Finding examples of such sets and determining what kind of structure U λ ∩ B N 2 U_\lambda\cap B_{N^2} U λ ∩ B N 2 must possess remains an important challenge. See [11 ] for related discussion.
The two different regimes for the estimate (5) may appear mysterious to the reader. We clarify this by proving a more general estimate for collections of random sets of arbitrary cardinality.
Theorem 2 (Main Theorem, Informal Statement). For each N ≤ q ≤ C N 4 N \le q \le CN^4 N ≤ q ≤ C N 4 , let V V V be a random collection of q q q unit balls contained inside B N 2 B_{N^2} B N 2 , then with high probability
sup f ∈ F ∥ f ∥ L 1 ( V ) ∼ ε N ε ( N 1 / 2 q + N 3 / 2 q ) . (7) \sup_{f\in\mathcal{F}}\|f\|_{L^1(V)} \sim_\varepsilon N^\varepsilon\left(N^{1/2}q+N^{3/2}\sqrt{q}\right). \tag*{(7)} f ∈ F sup ∥ f ∥ L 1 ( V ) ∼ ε N ε ( N 1/2 q + N 3/2 q ) . (7)
when q = N 7 λ − 6 q=N^7\lambda^{-6} q = N 7 λ − 6 , one can check that the first term in (7) dominates whenever N 1 / 2 ≤ λ ≤ N 5 / 6 N^{1/2} \le\lambda\le N^{5/6} N 1/2 ≤ λ ≤ N 5/6 and then second term in (7) dominates when N 5 / 6 < λ ≤ N N^{5/6}<\lambda\le N N 5/6 < λ ≤ N . These observations yield the estimate (5) .
Setup for Theorem 2
In this section we will convert the informal statement of Theorem 2 into a formal statement. Decompose B N 2 B_{N^2} B N 2 into a finitely overlapping union of C N 4 CN^4 C N 4 unit balls { V k } k = 1 C N 4 \{V_k\}_{k=1}^{CN^4} { V k } k = 1 C N 4 for some absolute constant C C C . For each 1 ≤ k ≤ C N 4 1 \le k \le CN^4 1 ≤ k ≤ C N 4 , define the Bernoulli random variable δ k \delta_k δ k as follows:
P ( δ k = 1 ) = O ( q N 4 ) = : δ , P ( δ k = 0 ) = 1 − δ . (8) \mathbb{P}(\delta_k=1)=O\left(\frac{q}{N^4}\right)=:\delta,\qquad\mathbb{P}(\delta_k=0)=1-\delta. \tag*{(8)} P ( δ k = 1 ) = O ( N 4 q ) =: δ , P ( δ k = 0 ) = 1 − δ . (8)
Then with high probability, the random set V V V defined as
V : = { ⋃ k : δ k = 1 V k } ⊆ B N 2 , (9) V:=\left\{\bigcup_{k:\delta_k=1}V_k\right\}\subseteq B_{N^2}, \tag*{(9)} V := { k : δ k = 1 ⋃ V k } ⊆ B N 2 , (9)
is such that ∣ V ∣ ∼ q |V|\sim q ∣ V ∣ ∼ q .
Theorem 3. In the setting coming from the discussion above,
E sup f ∈ F ∥ f ∥ L 1 ( V ) = E sup f ∈ F ∑ k = 1 C N 4 δ k ∫ V k ∣ f ( x ) ∣ d x ∼ ε N ε ( N 1 / 2 q + N 3 / 2 q ) . (10) \mathbb{E}\sup_{f\in\mathcal{F}}\|f\|_{L^1(V)}
=\mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^4}\delta_k\int_{V_k}|f(x)|\,dx
\sim_\varepsilon N^\varepsilon\left(N^{1/2}q+N^{3/2}\sqrt{q}\right). \tag*{(10)} E f ∈ F sup ∥ f ∥ L 1 ( V ) = E f ∈ F sup k = 1 ∑ C N 4 δ k ∫ V k ∣ f ( x ) ∣ d x ∼ ε N ε ( N 1/2 q + N 3/2 q ) . (10)
The first equality can easily be seen to be true by chasing definitions, the second inequality is the main technical result of this article.
The lower bound in (10) comes from some probabilistic constructions involving wave packets, which we show in § 7 . The technical heart of this paper, however, is in proving the upper bound which we restate here.
Proposition 4. We have the following inequality:
E sup f ∈ F ∑ k = 1 C N 4 δ k ∫ V k ∣ f ( x ) ∣ d x ≲ ε N ε ( N 1 / 2 q + N 3 / 2 q ) (11) \mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^4}\delta_k\int_{V_k}|f(x)|\,dx
\lesssim_\varepsilon N^\varepsilon\left(N^{1/2}q+N^{3/2}\sqrt{q}\right) \tag*{(11)} E f ∈ F sup k = 1 ∑ C N 4 δ k ∫ V k ∣ f ( x ) ∣ d x ≲ ε N ε ( N 1/2 q + N 3/2 q ) (11)
Remark 5. One could ask about the case when 1 ≤ q ≤ N 1 \le q \le N 1 ≤ q ≤ N , however, this regime is not so interesting since in this case the random set V V V is quite sparse and there exist f ∈ F f \in\mathcal{F} f ∈ F for which f f f is large on all of V V V . In fact we have that when 1 ≤ q ≤ N 1 \le q \le N 1 ≤ q ≤ N
E sup f ∈ F ∥ f ∥ L 1 ( V ) ∼ q N . \mathbb{E}\sup_{f\in\mathcal{F}}\|f\|_{L^1(V)} \sim qN. E f ∈ F sup ∥ f ∥ L 1 ( V ) ∼ q N .
The upper bound is trivial since ∥ f ∥ L ∞ ≤ N \|f\|_{L^\infty} \le N ∥ f ∥ L ∞ ≤ N for all f ∈ F f \in\mathcal{F} f ∈ F . Moreover a ‘wave packet tuning’ argument of Guth [13 ] , produces a corresponding lower bound.
Suprema of Stochastic Processes
One of the key inspirations behind the proof of Proposition 4 is to use ideas from the theory of bounding the expected supremum of stochastic processes. We can reframe (11) more abstractly as a question that asks for tight bounds for the quantity
E sup t ∈ T X t , (12) \mathbb{E}\sup_{t\in T}X_t, \tag*{(12)} E t ∈ T sup X t , (12)
for some stochastic process ( X t ) t ∈ T (X_t)_{t\in T} ( X t ) t ∈ T . There is an incredibly rich and interesting theory surrounding this family of problems and we refer the reader to Talagrand’s book [20 ] and the references therein for a comprehensive introduction. The study of the expected suprema of Gaussian processes is especially comprehensive; when ( X t ) t ∈ T (X_t)_{t\in T} ( X t ) t ∈ T is a Gaussian process it is known that the quantity (12) is completely determined by the metric induced by the L 2 L^2 L 2 distance between random variables on the index set T T T , given by d ( s , t ) = ( E ( X t − X s ) 2 ) 1 / 2 d(s,t) = \left(\mathbb{E}(X_t-X_s)^2\right)^{1/2} d ( s , t ) = ( E ( X t − X s ) 2 ) 1/2 for s , t ∈ T s,t\in T s , t ∈ T . A powerful strategy to used bound the expected supremum of a Gaussian process is called the chaining method. An informal description of chaining for Gaussian processes is as follows: assuming the process is centered2 we can write
E sup t ∈ T X t = E sup t ∈ T ( X t − X t 0 ) , \mathbb{E}\sup_{t\in T}X_t=\mathbb{E}\sup_{t\in T}(X_t-X_{t_0}), E t ∈ T sup X t = E t ∈ T sup ( X t − X t 0 ) ,
and then write ( X t − X t 0 ) = ∑ k ( X π k ( t ) − X π k − 1 ( t ) ) (X_t-X_{t_0})=\sum_k(X_{\pi_k(t)}-X_{\pi_{k-1}(t)}) ( X t − X t 0 ) = ∑ k ( X π k ( t ) − X π k − 1 ( t ) ) as some telescoping sum, where the π k ( t ) \pi_k(t) π k ( t ) ’s can be thought of as successive approximations to t t t in the metric space ( T , d ) (T,d) ( T , d ) . One can then use measure concentration bounds3 to control the size of the increments X π k ( t ) − X π k − 1 ( t ) X_{\pi_k(t)}-X_{\pi_{k-1}(t)} X π k ( t ) − X π k − 1 ( t ) . A celebrated application of the chaining method is Dudley’s inequality which states in this setting that
E sup t ∈ T X t ≲ ∫ 0 ∞ log N ( T , d , ϵ ) d ϵ , \mathbb{E}\sup_{t\in T}X_t\lesssim\int_0^\infty\sqrt{\log N(T,d,\epsilon)}\,\mathrm{d}\epsilon, E t ∈ T sup X t ≲ ∫ 0 ∞ log N ( T , d , ϵ ) d ϵ ,
where N ( T , d , ϵ ) N(T,d,\epsilon) N ( T , d , ϵ ) is the ϵ \epsilon ϵ -covering number of T T T (sometimes referred to as the metric entropy of T T T ), that is, the minimum number of balls of radius ϵ \epsilon ϵ in the metric space ( T , d ) (T,d) ( T , d ) required to cover T T T . We refer the reader to the references [20 ] and [23 ] for excellent introductions to the chaining method and applications. Our method crucially relies on Dudley’s inequality, but it cannot be used directly. We need to manipulate the stochastic process we are interested in, and then compute entropy estimates in an appropriate way. We refer the reader to Appendix B for some more background on the precise statements from probability theory that we use in this paper.
Remark 6. The astute reader may have realized that the quantity
E sup t ∈ T X t \mathbb{E}\sup_{t\in T}X_t E t ∈ T sup X t
may not be well defined if T T T is uncountable (since the random variable sup t ∈ T X t \sup_{t\in T} X_t sup t ∈ T X t may not even be measurable). The fix for this is to alter the definition of the expected supremum of a stochastic process so that all the previous arguments make sense by defining
E sup t ∈ T X t : = sup F ⊆ T , f i n i t e E sup t ∈ F X t . \mathbb{E}\sup_{t\in T} X_t := \sup_{\substack{F\subseteq T,\,\mathrm{finite}}} \mathbb{E}\sup_{t\in F} X_t. E t ∈ T sup X t := F ⊆ T , finite sup E t ∈ F sup X t .
We will proceed with this convention for this paper as well.
Structure and Organization of the Paper:
In § 5.1 , we reduce the proof of Proposition 4 to another proposition, Proposition 7.
In § 6 , we prove Proposition 7, which completes the proof of the upper bound for Theorem 3.
In § 7 , we supply the proof of the lower bound for Theorem 3, using wave packets.
In § 8 , we give some further remarks on the paper and the proof strategy. This includes some suggestions for reading this paper. Once familiar with the basic setup of this problem, the reader is recommended to look at § 8 for suggestions on how to read this paper.
The appendix contains two parts. In Appendix A, we prove some technical propositions in Fourier analysis. In Appendix § 10 , we give some background on the machinery coming from tools in high dimensional probability we use in the proof.
Notation.
We will use the following notation in this paper:
A ≲ B A \lesssim B A ≲ B if there exists an absolute constant C > 0 C>0 C > 0 such that A ≤ C B A\le CB A ≤ C B .
A ∼ B A\sim B A ∼ B if there exists an absolute constant such that 1 C B ≤ A ≤ C B \frac{1}{C}B\le A\le CB C 1 B ≤ A ≤ C B .
A ≲ ε B A\lesssim_{\varepsilon} B A ≲ ε B if for every ε > 0 \varepsilon>0 ε > 0 there exists a constant C ε > 0 C_{\varepsilon}>0 C ε > 0 (possibly depending on ε \varepsilon ε ) such that A ≤ C ε B A\le C_{\varepsilon}B A ≤ C ε B for all ε > 0 \varepsilon>0 ε > 0 . For example, log R ≲ ε R ε \log R\lesssim_{\varepsilon} R^{\varepsilon} log R ≲ ε R ε for all R > 0 R>0 R > 0 .
Given any A , B ⊆ R n A,B\subseteq\mathbb{R}^{n} A , B ⊆ R n , define N ( A , B ) \mathcal{N}(A,B) N ( A , B ) to be the minimum number of translates of B B B needed to cover A A A . If ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ is a norm on R n \mathbb{R}^{n} R n , we write N ( A , ∥ ⋅ ∥ , ε ) \mathcal{N}(A,\|\cdot\|,\varepsilon) N ( A , ∥ ⋅ ∥ , ε ) to be the minimum number of ball of radius ε \varepsilon ε in ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ needed to cover A A A . Covering numbers of the form N ( A , B ) \mathcal{N}(A,B) N ( A , B ) are a basic tool in the study of suprema of stochastic processes and will be used frequently in this work.
Tool and Computational Resource Disclosure.
All ideas, theorems and technical statements in this paper are due to author, and were written by the author. Once a first draft of the paper was written, we used a large language model to review the paper. The author incorporated several suggestions from the language model, which included corrections of expository and mathematical errors, as well as minor simplifications to some arguments.
Acknowledgments:
The author would like to thank Terence Tao and Hong Wang for feedback and support. Part of this work was completed when the author was visiting the Institut Hautes Études des Scientifiques, and we thank the IHES for excellent working conditions.
Reduction to Proposition 7
The goal of this section is to reduce the statement of Proposition 4 to a similar statement, Proposition 7 which we state below.
For j ∈ N j \in\mathbb{N} j ∈ N and each multi-index α = ( i 1 , i 2 , … , i j ) \alpha= (i_1, i_2, \ldots, i_j) α = ( i 1 , i 2 , … , i j ) where each i m ∈ { 1 , 2 } i_m \in\{1,2\} i m ∈ { 1 , 2 } , define ∣ α ∣ = j |\alpha| = j ∣ α ∣ = j . For any f ∈ S ( R 2 ) f \in\mathcal{S}(\mathbb{R}^2) f ∈ S ( R 2 ) , define D ( α ) f D^{(\alpha)}f D ( α ) f as follows:
D ( α ) f : = ∂ f ∂ x i 1 ∂ x i 2 … ∂ x i j . D^{(\alpha)}f := \frac{\partial f}{\partial x_{i_1}\partial x_{i_2}\ldots\partial x_{i_j}}. D ( α ) f := ∂ x i 1 ∂ x i 2 … ∂ x i j ∂ f .
Recall from that { V k } \{V_k\} { V k } is a collection of C N 4 CN^4 C N 4 unit balls. For each k k k , decompose V k V_k V k into ∼ N ϵ \sim N^\epsilon ∼ N ϵ many finitely overlapping unit balls V k , l V_{k,l} V k , l of radius N − ϵ N^{-\epsilon} N − ϵ . Write V k , l = B ( y k l , N − ϵ ) V_{k,l} = B(y_{kl},N^{-\epsilon}) V k , l = B ( y k l , N − ϵ ) as the ball of radius N − ϵ N^{-\epsilon} N − ϵ around y k l y_{kl} y k l . For each k k k , we can label the y k l y_{kl} y k l such that 1 ≤ l ≤ c 1 N ϵ 1 \leq l \leq c_1N^\epsilon 1 ≤ l ≤ c 1 N ϵ , for some absolute constant c 1 c_1 c 1 .
Proposition 7. Fix ϵ > 0 \epsilon> 0 ϵ > 0 and let ( δ k ) (\delta_k) ( δ k ) be the collection of selector random variables defined in (8). Recall that
P ( δ k = 1 ) ∼ q N 4 . (13) \mathbb{P}(\delta_k = 1) \sim\frac{q}{N^4}. \tag*{(13)} P ( δ k = 1 ) ∼ N 4 q . (13) Then for each multi-index α \alpha α , with ∣ α ∣ ≲ 1 ϵ |\alpha| \lesssim\frac{1}{\epsilon} ∣ α ∣ ≲ ϵ 1 , and each l l l , we have that
E sup f ∈ F ∑ k = 1 C N 4 δ k ∣ D ( α ) f ( y k l ) ∣ ≲ ϵ N ϵ ( N 1 / 2 q + N 3 / 2 q ) . (14) \mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^4}\delta_k\left|D^{(\alpha)}f(y_{kl})\right| \lesssim_\epsilon N^\epsilon\left(N^{1/2}q+N^{3/2}\sqrt{q}\right). \tag*{(14)} E f ∈ F sup k = 1 ∑ C N 4 δ k D ( α ) f ( y k l ) ≲ ϵ N ϵ ( N 1/2 q + N 3/2 q ) . (14)
Proof that Proposition 7 implies Proposition 4. Assuming (14) is true, we need to show that
E sup f ∈ F ∑ k = 1 C N 4 δ k ∫ V k ∣ f ( x ) ∣ d x ≲ ϵ N ϵ ( N 1 / 2 q + N 3 / 2 q ) . (15) \mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^4}\delta_k\int_{V_k}|f(x)|\,dx \lesssim_\epsilon N^\epsilon\left(N^{1/2}q+N^{3/2}\sqrt{q}\right). \tag*{(15)} E f ∈ F sup k = 1 ∑ C N 4 δ k ∫ V k ∣ f ( x ) ∣ d x ≲ ϵ N ϵ ( N 1/2 q + N 3/2 q ) . (15)
For each k k k , decompose V k V_k V k into the finite overlapping collection of balls { V k , l } \{V_{k,l}\} { V k , l } , so that
∫ V k ∣ f ( x ) ∣ d x ≲ ∑ l ∫ V k , l ∣ f ( x ) ∣ d x . (16) \int_{V_k}|f(x)|\,dx \lesssim\sum_l\int_{V_{k,l}}|f(x)|\,dx. \tag*{(16)} ∫ V k ∣ f ( x ) ∣ d x ≲ l ∑ ∫ V k , l ∣ f ( x ) ∣ d x . (16)
For each x ∈ V k , l x \in V_{k,l} x ∈ V k , l , note that x ∈ B ( y k l , N − ϵ ) x \in B(y_{kl},N^{-\epsilon}) x ∈ B ( y k l , N − ϵ ) , for each f ∈ F f \in\mathcal{F} f ∈ F , we have by Taylor’s theorem that
∣ f ( x ) ∣ ≲ ( ∑ ∣ α ∣ ≤ M ∣ D ( α ) f ( y k l ) ∣ N − ∣ α ∣ ϵ α ! ) + sup ∣ α ∣ = M + 1 ∣ D ( α ) f ( y k l ) ∣ ⋅ O ( N − M ϵ ) , (17) |f(x)| \lesssim\left(\sum_{|\alpha|\leq M}|D^{(\alpha)}f(y_{kl})|\frac{N^{-|\alpha|\epsilon}}{\alpha!}\right)+\sup_{|\alpha|=M+1}|D^{(\alpha)}f(y_{kl})|\cdot O(N^{-M\epsilon}), \tag*{(17)} ∣ f ( x ) ∣ ≲ ∣ α ∣ ≤ M ∑ ∣ D ( α ) f ( y k l ) ∣ α ! N − ∣ α ∣ ϵ + ∣ α ∣ = M + 1 sup ∣ D ( α ) f ( y k l ) ∣ ⋅ O ( N − M ϵ ) , (17)
for some M ∈ N M \in\mathbb{N} M ∈ N (to be chosen later) The next lemma shows that we can bound the remainder uniformly for all f ∈ F f \in\mathcal{F} f ∈ F .
Lemma 8. For each f ∈ F f \in\mathcal{F} f ∈ F , we have
sup f ∈ F ∣ D ( α ) f ( y k l ) ∣ ≲ ∣ α ∣ N . (18) \sup_{f\in\mathcal{F}}|D^{(\alpha)}f(y_{kl})| \lesssim_{|\alpha|} N. \tag*{(18)} f ∈ F sup ∣ D ( α ) f ( y k l ) ∣ ≲ ∣ α ∣ N . (18)
Proof. Indeed, by Bernstein’s inequality [24 Chapter 5] , since each f ∈ F f \in\mathcal{F} f ∈ F is such that f ^ \widehat{f} f has compact support, we have
∥ D ( α ) f ∥ ∞ ≲ ∣ α ∣ ∥ f ∥ ∞ \left\|D^{(\alpha)}f\right\|_\infty\lesssim_{|\alpha|}\|f\|_\infty D ( α ) f ∞ ≲ ∣ α ∣ ∥ f ∥ ∞
Moreover for each f ∈ F f \in\mathcal{F} f ∈ F ,
∥ f ∥ ∞ = ∥ ∑ θ f θ ∥ ∞ ≤ ∑ θ ∥ f θ ∥ ∞ ≤ N , \|f\|_{\infty} = \left\|\sum_{\theta} f_{\theta}\right\|_{\infty} \le\sum_{\theta} \|f_{\theta}\|_{\infty} \le N, ∥ f ∥ ∞ = θ ∑ f θ ∞ ≤ θ ∑ ∥ f θ ∥ ∞ ≤ N ,
which proves the claim.
In light of the previous lemma, for each f ∈ F f \in\mathcal{F} f ∈ F , (17) can be rewritten as
∣ f ( x ) ∣ ≲ ∑ ∣ α ∣ ≤ M ∣ D ( α ) f ( y k l ) ∣ N − ∣ α ∣ ϵ α ! + O M ( N − M ϵ + 1 ) . (19) |f(x)| \lesssim\sum_{|\alpha|\le M} |D^{(\alpha)}f(y_{kl})| \frac{N^{-|\alpha|\epsilon}}{\alpha!} + O_M(N^{-M\epsilon+1}). \tag*{(19)} ∣ f ( x ) ∣ ≲ ∣ α ∣ ≤ M ∑ ∣ D ( α ) f ( y k l ) ∣ α ! N − ∣ α ∣ ϵ + O M ( N − M ϵ + 1 ) . (19)
Set M = ⌈ 10001 ϵ ⌉ M = \left\lceil\frac{10001}{\epsilon} \right\rceil M = ⌈ ϵ 10001 ⌉ , so that the above expression can be rewritten as
∣ f ( x ) ∣ ≲ ∑ ∣ α ∣ ≲ 1 ϵ ∣ D ( α ) f ( y k l ) ∣ N − ∣ α ∣ ϵ α ! + O ϵ ( N − 10000 ) . (20) |f(x)| \lesssim\sum_{|\alpha|\lesssim\frac{1}{\epsilon}} |D^{(\alpha)}f(y_{kl})| \frac{N^{-|\alpha|\epsilon}}{\alpha!} + O_{\epsilon}(N^{-10000}). \tag*{(20)} ∣ f ( x ) ∣ ≲ ∣ α ∣ ≲ ϵ 1 ∑ ∣ D ( α ) f ( y k l ) ∣ α ! N − ∣ α ∣ ϵ + O ϵ ( N − 10000 ) . (20)
We now prove (15) assuming (14) . First, by (16) we have that
E sup f ∈ F ∑ k = 1 C N 4 δ k ∫ V k ∣ f ( x ) ∣ d x ≲ E sup f ∈ F ∑ k = 1 C N 4 δ k ∑ l ∫ V k , l ∣ f ( x ) ∣ d x . (21) \mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^4}\delta_k\int_{V_k}|f(x)|\,dx
\lesssim\mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^4}\delta_k\sum_l\int_{V_{k,l}}|f(x)|\,dx. \tag*{(21)} E f ∈ F sup k = 1 ∑ C N 4 δ k ∫ V k ∣ f ( x ) ∣ d x ≲ E f ∈ F sup k = 1 ∑ C N 4 δ k l ∑ ∫ V k , l ∣ f ( x ) ∣ d x . (21)
Now, applying the estimate (20) yields
E sup f ∈ F ∑ k = 1 C N 4 δ k ∑ l ∫ V k , l ∣ f ( x ) ∣ d x \mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^4}\delta_k\sum_l\int_{V_{k,l}}|f(x)|\,dx E f ∈ F sup k = 1 ∑ C N 4 δ k l ∑ ∫ V k , l ∣ f ( x ) ∣ d x
≲ E sup f ∈ F ∑ k = 1 C N 4 δ k ∑ l ∫ V k , l ( ∑ ∣ α ∣ ≲ 1 ϵ ∣ D ( α ) f ( y k l ) ∣ N − ∣ α ∣ ϵ α ! + O ϵ ( N − 10000 ) ) d x . \lesssim\mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^4}\delta_k\sum_l\int_{V_{k,l}}\left(\sum_{|\alpha|\lesssim\frac{1}{\epsilon}} |D^{(\alpha)}f(y_{kl})|\frac{N^{-|\alpha|\epsilon}}{\alpha!}+O_{\epsilon}(N^{-10000})\right)\,dx. ≲ E f ∈ F sup k = 1 ∑ C N 4 δ k l ∑ ∫ V k , l ∣ α ∣ ≲ ϵ 1 ∑ ∣ D ( α ) f ( y k l ) ∣ α ! N − ∣ α ∣ ϵ + O ϵ ( N − 10000 ) d x .
≲ ∑ l ∑ ∣ α ∣ ≲ 1 ϵ E sup f ∈ F ( ∑ k = 1 C N 4 δ k N − ∣ α ∣ ϵ α ! ∫ V k , l ∣ D ( α ) f ( y k l ) ∣ d x ) + O ϵ ( N − 1000 + ϵ ) . \lesssim\sum_l\sum_{|\alpha|\lesssim\frac{1}{\epsilon}}\mathbb{E}\sup_{f\in\mathcal{F}}\left(\sum_{k=1}^{CN^4}\delta_k\frac{N^{-|\alpha|\epsilon}}{\alpha!}\int_{V_{k,l}}|D^{(\alpha)}f(y_{kl})|\,dx\right)+O_{\epsilon}(N^{-1000+\epsilon}). ≲ l ∑ ∣ α ∣ ≲ ϵ 1 ∑ E f ∈ F sup k = 1 ∑ C N 4 δ k α ! N − ∣ α ∣ ϵ ∫ V k , l ∣ D ( α ) f ( y k l ) ∣ d x + O ϵ ( N − 1000 + ϵ ) .
where in the second line, we have used the estimate (20) , and in the third line, we have interchanged sums, and pulled the sums in l l l and α \alpha α outside the supremum over f ∈ F f \in\mathcal{F} f ∈ F . Noting that for each k k k and l l l , the area of V k , l V_{k,l} V k , l is ∼ N − ϵ \sim N^{-\epsilon} ∼ N − ϵ , we get that the above expression is bounded by
≲ ∑ l ∑ ∣ α ∣ ≲ 1 ϵ E sup f ∈ F ( ∑ k = 1 C N 4 δ k N − ( ∣ α ∣ + 1 ) ϵ α ! ∣ D ( α ) f ( y k l ) ∣ ) + O ϵ ( N − 1000 + ϵ ) . \lesssim\sum_l\sum_{|\alpha|\lesssim\frac{1}{\epsilon}}\mathbb{E}\sup_{f\in\mathcal{F}}\left(\sum_{k=1}^{CN^4}\delta_k\frac{N^{-(|\alpha|+1)\epsilon}}{\alpha!}|D^{(\alpha)}f(y_{kl})|\right)+O_{\epsilon}(N^{-1000+\epsilon}). ≲ l ∑ ∣ α ∣ ≲ ϵ 1 ∑ E f ∈ F sup k = 1 ∑ C N 4 δ k α ! N − ( ∣ α ∣ + 1 ) ϵ ∣ D ( α ) f ( y k l ) ∣ + O ϵ ( N − 1000 + ϵ ) .
Now noting that the term N − ( ∣ α ∣ + 1 ) ϵ α ! \frac{N^{-(|\alpha|+1)\epsilon}}{\alpha!} α ! N − ( ∣ α ∣ + 1 ) ϵ for each α \alpha α , we see that the above expression is bounded by
≤ ∑ l = 1 c 1 N ϵ ∑ ∣ α ∣ ≲ 1 ϵ E sup f ∈ F ( ∑ k = 1 C N 4 δ k ∣ D ( α ) f ( y k l ) ∣ ) + O ϵ ( N − 1000 + ϵ ) . (22) \le\sum_{l=1}^{c_1N^{\epsilon}}\sum_{|\alpha|\lesssim\frac{1}{\epsilon}}\mathbb{E}\sup_{f\in\mathcal{F}}\left(\sum_{k=1}^{CN^4}\delta_k|D^{(\alpha)}f(y_{kl})|\right)+O_{\epsilon}(N^{-1000+\epsilon}). \tag*{(22)} ≤ l = 1 ∑ c 1 N ϵ ∣ α ∣ ≲ ϵ 1 ∑ E f ∈ F sup k = 1 ∑ C N 4 δ k ∣ D ( α ) f ( y k l ) ∣ + O ϵ ( N − 1000 + ϵ ) . (22)
Now we apply (14) , which gives us an estimate for the inner term.
E sup f ∈ F ( ∑ k = 1 C N 4 δ k ∣ D ( α ) f ( y k l ) ∣ ) ≲ ϵ N ϵ ( N 1 / 2 q + N 3 / 2 q ) \mathbb{E}\sup_{f\in\mathcal{F}}\left(\sum_{k=1}^{CN^4}\delta_k|D^{(\alpha)}f(y_{kl})|\right)\lesssim_{\epsilon} N^{\epsilon}\left(N^{1/2}q+N^{3/2}\sqrt{q}\right) E f ∈ F sup k = 1 ∑ C N 4 δ k ∣ D ( α ) f ( y k l ) ∣ ≲ ϵ N ϵ ( N 1/2 q + N 3/2 q )
Finally, noting that the number summations in (22) in ℓ \ell ℓ and ∣ α ∣ |\alpha| ∣ α ∣ combined is ≲ ϵ N ϵ \lesssim_{\epsilon} N^{\epsilon} ≲ ϵ N ϵ , this yields that the expression (22) is ≲ ϵ N ϵ ( N 1 / 2 q + N 3 / 2 q ) \lesssim_{\epsilon} N^{\epsilon}(N^{1/2}q+N^{3/2}\sqrt{q}) ≲ ϵ N ϵ ( N 1/2 q + N 3/2 q ) , so that
E sup f ∈ F ∑ k = 1 C R d δ k ∫ V k ∣ f ( x ) ∣ d x ≲ ϵ N ϵ ( N 1 / 2 q + N 3 / 2 q ) . \mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CR^{d}}\delta_k\int_{V_k}|f(x)|dx\lesssim_{\epsilon}N^{\epsilon}(N^{1/2}q+N^{3/2}\sqrt{q}). E f ∈ F sup k = 1 ∑ C R d δ k ∫ V k ∣ f ( x ) ∣ d x ≲ ϵ N ϵ ( N 1/2 q + N 3/2 q ) .
which proves the claim. □
Proof of the Upper Bound
Symmetrization and Further Reductions
The previous section shows that we need to establish the desired bound
E sup f ∈ F ∑ k = 1 C N 4 δ k ∣ D ( α ) f ( y k l ) ∣ ≲ ϵ N ϵ ( N 1 / 2 q + N 3 / 2 q ) (23) \mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^{4}}\delta_k|D^{(\alpha)}f(y_{kl})|\lesssim_{\epsilon}N^{\epsilon}(N^{1/2}q+N^{3/2}\sqrt{q}) \tag*{(23)} E f ∈ F sup k = 1 ∑ C N 4 δ k ∣ D ( α ) f ( y k l ) ∣ ≲ ϵ N ϵ ( N 1/2 q + N 3/2 q ) (23)
where
q ∈ N , and N ≤ q ≤ C N 4 , (24) q\in\mathbb{N},\quad\text{and}\quad N\leq q\leq CN^{4}, \tag*{(24)} q ∈ N , and N ≤ q ≤ C N 4 , (24)
where q q q is the number of random points chosen from { y k l } k = 1 C N 4 \{y_{kl}\}_{k=1}^{CN^{4}} { y k l } k = 1 C N 4 , in expectation. The next step is a step known as ‘symmetrization’ in the literature (see [23 Lemma 6.3.2] ). First we write
δ k = ( δ k − δ ) + δ \delta_k=(\delta_k-\delta)+\delta δ k = ( δ k − δ ) + δ
Inserting this into (23) we have
E sup f ∈ F ∑ k = 1 C N 4 δ k ∣ D ( α ) f ( y k l ) ∣ ≤ E sup f ∈ F ∣ ∑ k = 1 C N 4 ( δ k − δ ) ∣ D ( α ) f ( y k l ) ∣ ∣ + δ sup f ∈ F ∑ k = 1 C N 4 ∣ D ( α ) f ( y k l ) ∣ . \mathbb{E}\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^{4}}\delta_k|D^{(\alpha)}f(y_{kl})|\leq\mathbb{E}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^{4}}(\delta_k-\delta)|D^{(\alpha)}f(y_{kl})|\right|+\delta\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^{4}}|D^{(\alpha)}f(y_{kl})|. E f ∈ F sup k = 1 ∑ C N 4 δ k ∣ D ( α ) f ( y k l ) ∣ ≤ E f ∈ F sup k = 1 ∑ C N 4 ( δ k − δ ) ∣ D ( α ) f ( y k l ) ∣ + δ f ∈ F sup k = 1 ∑ C N 4 ∣ D ( α ) f ( y k l ) ∣.
The second term is deterministic and easy to estimate. First note that
δ ∼ q N 4 , (25) \delta\sim\frac{q}{N^{4}}, \tag*{(25)} δ ∼ N 4 q , (25)
and some basic Fourier analytic arguments give that
sup f ∈ F ∑ k = 1 C N 4 ∣ D ( α ) f ( y k l ) ∣ ≲ ∥ D ( α ) f ∥ L 1 ( B N 2 ) ≲ ∥ f ∥ L 1 ( B N 2 ) ≲ ϵ N 9 / 2 + ϵ . (26) \sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^{4}}|D^{(\alpha)}f(y_{kl})|\lesssim\|D^{(\alpha)}f\|_{L^{1}(B_{N^{2}})}\lesssim\|f\|_{L^{1}(B_{N^{2}})}\lesssim_{\epsilon}N^{9/2+\epsilon}. \tag*{(26)} f ∈ F sup k = 1 ∑ C N 4 ∣ D ( α ) f ( y k l ) ∣ ≲ ∥ D ( α ) f ∥ L 1 ( B N 2 ) ≲ ∥ f ∥ L 1 ( B N 2 ) ≲ ϵ N 9/2 + ϵ . (26)
We prove these estimates rigourously in the appendix, but we can explain the basic heuristic here. Since every f ∈ F f\in\mathcal{F} f ∈ F has Fourier transform supported in [ − 2 , 2 ] 2 [-2,2]^{2} [ − 2 , 2 ] 2 , every f ∈ F f\in\mathcal{F} f ∈ F is ‘locally constant’. Thus one can make the approximation ∑ k ∣ D ( α ) f ( y k l ) ∣ ≲ ∥ D ( α ) f ∥ L 1 ( B N 2 ) \sum_k|D^{(\alpha)}f(y_{kl})|\lesssim\|D^{(\alpha)}f\|_{L^{1}(B_{N^{2}})} ∑ k ∣ D ( α ) f ( y k l ) ∣ ≲ ∥ D ( α ) f ∥ L 1 ( B N 2 ) . The third inequality follows from Bernstein’s inequality and the final inequality comes from integrating in the superlevel set bound (3). Combining the estimates (25) and (26) we obtain
δ sup f ∈ F ∑ k = 1 C N 4 ∣ D ( α ) f ( y k l ) ∣ ≲ ϵ N 1 / 2 + ϵ q , (27) \delta\sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^{4}}|D^{(\alpha)}f(y_{kl})|\lesssim_{\epsilon}N^{1/2+\epsilon}q, \tag*{(27)} δ f ∈ F sup k = 1 ∑ C N 4 ∣ D ( α ) f ( y k l ) ∣ ≲ ϵ N 1/2 + ϵ q , (27)
which corresponds to the first term on the right hand side of (23). It remains to establish
E sup f ∈ F ∣ ∑ k = 1 C N 4 ( δ k − δ ) ∣ D ( α ) f ( y k l ) ∣ ∣ ≲ N 3 / 2 + ϵ q (28) \mathbb{E}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^{4}}(\delta_k-\delta)|D^{(\alpha)}f(y_{kl})|\right|\lesssim N^{3/2+\epsilon}\sqrt{q} \tag*{(28)} E f ∈ F sup k = 1 ∑ C N 4 ( δ k − δ ) ∣ D ( α ) f ( y k l ) ∣ ≲ N 3/2 + ϵ q (28)
Let ( δ k ′ ) (\delta'_k) ( δ k ′ ) be collection of selector random variables with mean δ \delta δ which is independent from the collection ( δ k ) (\delta_k) ( δ k ) . We can write
E sup f ∈ F ∣ ∑ k = 1 C N 4 ( δ k − δ ) ∣ D ( α ) f ( y k l ) ∣ ∣ = E δ sup f ∈ F ∣ ∑ k = 1 C N 4 ( δ k − δ k ′ ) ∣ D ( α ) f ( y k l ) ∣ ∣ ≤ E δ , δ ′ sup f ∈ F ∣ ∑ k = 1 C N 4 ( δ k − δ k ′ ) ∣ D ( α ) f ( y k l ) ∣ ∣ . \begin{aligned}
\mathbb{E}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^4}(\delta_k-\delta)\left|D^{(\alpha)}f(y_{kl})\right|\right|=\mathbb{E}_{\delta}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^4}(\delta_k-\delta'_k)\left|D^{(\alpha)}f(y_{kl})\right|\right| \\
&\leq\mathbb{E}_{\delta,\delta'}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^4}(\delta_k-\delta'_k)\left|D^{(\alpha)}f(y_{kl})\right|\right|.
\end{aligned} E f ∈ F sup k = 1 ∑ C N 4 ( δ k − δ ) D ( α ) f ( y k l ) = E δ f ∈ F sup k = 1 ∑ C N 4 ( δ k − δ k ′ ) D ( α ) f ( y k l ) ≤ E δ , δ ′ f ∈ F sup k = 1 ∑ C N 4 ( δ k − δ k ′ ) D ( α ) f ( y k l ) .
where the last inequality follows from the fact that sup t ∈ T E X t ≤ E sup t ∈ T X t \sup_{t\in T}\mathbb{E}X_t\leq\mathbb{E}\sup_{t\in T}X_t sup t ∈ T E X t ≤ E sup t ∈ T X t , and the independence of the random variables ( δ k ) k = 1 n (\delta_k)_{k=1}^n ( δ k ) k = 1 n and ( δ k ′ ) k = 1 n (\delta'_k)_{k=1}^n ( δ k ′ ) k = 1 n . Let ( ϵ k ) (\epsilon_k) ( ϵ k ) be an independent and identically distributed collection of Rademacher random variables, that is P ( ϵ k = ± 1 ) = 1 2 \mathbb{P}(\epsilon_k=\pm1)=\frac{1}{2} P ( ϵ k = ± 1 ) = 2 1 , and note that the random variables
δ k − δ k ′ and ϵ k ( δ k − δ k ′ ) \delta_k-\delta'_k \qquad\text{and}\qquad\epsilon_k(\delta_k-\delta'_k) δ k − δ k ′ and ϵ k ( δ k − δ k ′ )
have the same law. Therefore,
E δ , δ ′ sup f ∈ F ∣ ∑ k = 1 C N 4 ( δ k − δ k ′ ) ∣ D ( α ) f ( y k l ) ∣ ∣ = E δ , δ ′ , ϵ sup f ∈ F ∣ ∑ k = 1 C N 4 ϵ k ( δ k − δ k ′ ) ∣ D ( α ) f ( y k l ) ∣ ∣ . \mathbb{E}_{\delta,\delta'}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^4}(\delta_k-\delta'_k)\left|D^{(\alpha)}f(y_{kl})\right|\right|=\mathbb{E}_{\delta,\delta',\epsilon}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^4}\epsilon_k(\delta_k-\delta'_k)\left|D^{(\alpha)}f(y_{kl})\right|\right|. E δ , δ ′ f ∈ F sup k = 1 ∑ C N 4 ( δ k − δ k ′ ) D ( α ) f ( y k l ) = E δ , δ ′ , ϵ f ∈ F sup k = 1 ∑ C N 4 ϵ k ( δ k − δ k ′ ) D ( α ) f ( y k l ) .
and the previous term can be bounded as follows:
E δ , δ ′ , ϵ sup f ∈ F ∣ ∑ k = 1 C N 4 ϵ k ( δ k − δ k ′ ) ∣ D ( α ) f ( y k l ) ∣ ∣ ≤ E sup f ∈ F ∣ ∑ k = 1 C N 4 ϵ k δ k ∣ D ( α ) f ( y k l ) ∣ ∣ + E sup f ∈ F ∣ ∑ k = 1 C N 4 ϵ k δ k ′ ∣ D ( α ) f ( y k l ) ∣ ∣ \mathbb{E}_{\delta,\delta',\epsilon}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^4}\epsilon_k(\delta_k-\delta'_k)\left|D^{(\alpha)}f(y_{kl})\right|\right|\leq\mathbb{E}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^4}\epsilon_k\delta_k\left|D^{(\alpha)}f(y_{kl})\right|\right|+\mathbb{E}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^4}\epsilon_k\delta'_k\left|D^{(\alpha)}f(y_{kl})\right|\right| E δ , δ ′ , ϵ f ∈ F sup k = 1 ∑ C N 4 ϵ k ( δ k − δ k ′ ) D ( α ) f ( y k l ) ≤ E f ∈ F sup k = 1 ∑ C N 4 ϵ k δ k D ( α ) f ( y k l ) + E f ∈ F sup k = 1 ∑ C N 4 ϵ k δ k ′ D ( α ) f ( y k l )
≤ 2 E sup f ∈ F ∣ ∑ k = 1 C N 4 ϵ k δ k ∣ D ( α ) f ( y k l ) ∣ ∣ . (29) \leq2\mathbb{E}\sup_{f\in\mathcal{F}}\left|\sum_{k=1}^{CN^4}\epsilon_k\delta_k\left|D^{(\alpha)}f(y_{kl})\right|\right|. \tag*{(29)} ≤ 2 E f ∈ F sup k = 1 ∑ C N 4 ϵ k δ k D ( α ) f ( y k l ) . (29)
Let S S S be the (random) set defined as
S : = { k : δ k = 1 } . (30) S:=\{k:\delta_k=1\}. \tag*{(30)} S := { k : δ k = 1 } . (30)
The next step (which also appears several times in the literature, see for example, [23 Theorem 8.3.15] ) is to condition on the random set S S S . By Fubini’s theorem, the expression (29) can be written as
E δ E ϵ sup f ∈ F ∣ ∑ k ∈ S ϵ k ∣ D ( α ) f ( y k l ) ∣ ∣ . (31) \mathbb{E}_{\delta}\mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}}\left|\sum_{k\in S}\epsilon_k\left|D^{(\alpha)}f(y_{kl})\right|\right|. \tag*{(31)} E δ E ϵ f ∈ F sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) . (31)
The main result of the next section is the following estimate:
E ϵ sup f ∈ F ∣ ∑ k ∈ S ϵ k ∣ D ( α ) f ( y k l ) ∣ ∣ ≲ ϵ N 3 / 2 + ϵ ∣ S ∣ , (32) \mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}}\left|\sum_{k\in S}\epsilon_k\left|D^{(\alpha)}f(y_{kl})\right|\right|\lesssim_{\epsilon}N^{3/2+\epsilon}\sqrt{|S|}, \tag*{(32)} E ϵ f ∈ F sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) ≲ ϵ N 3/2 + ϵ ∣ S ∣ , (32)
where this estimate holds for any subset S ⊂ [ C N 4 ] S\subset[CN^4] S ⊂ [ C N 4 ] . Plugging this estimate into (31), we have
E δ E ϵ sup f ∈ F ∣ ∑ k ∈ S ϵ k ∣ D ( α ) f ( y k l ) ∣ ∣ ≲ ϵ E δ ( N 3 / 2 + ϵ ∣ S ∣ ) ≤ N 3 / 2 + ϵ q \mathbb{E}_{\delta}\mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}}\left|\sum_{k\in S}\epsilon_k\left|D^{(\alpha)}f(y_{kl})\right|\right|\lesssim_{\epsilon}\mathbb{E}_{\delta}(N^{3/2+\epsilon}\sqrt{|S|})\leq N^{3/2+\epsilon}\sqrt{q} E δ E ϵ f ∈ F sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) ≲ ϵ E δ ( N 3/2 + ϵ ∣ S ∣ ) ≤ N 3/2 + ϵ q
where the final inequality follows from Jensen’s inequality. This establishes the required upper bound, conditional on proving the estimate (32), which we will prove in the next section.
Bounding the Symmetrized Process
In the next two sections we establish the estimate (32), which we recall here.
Proposition 9. Fix any subset S ⊆ [ C N 4 ] S \subseteq[CN^{4}] S ⊆ [ C N 4 ] . We have the following estimate:
E ϵ sup f ∈ F ∣ ∑ k ∈ S ϵ k D ( α ) f ( y k l ) ∣ ≲ ϵ N 3 / 2 + ϵ ∣ S ∣ . \mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}}\left|\sum_{k\in S}\epsilon_k D^{(\alpha)}f(y_{kl})\right|\lesssim_{\epsilon}N^{3/2+\epsilon}\sqrt{|S|}. E ϵ f ∈ F sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) ≲ ϵ N 3/2 + ϵ ∣ S ∣ .
We begin by making a reduction, where we reduce to studying a similar problem where the sup is taken over a simpler class F θ \mathcal{F}_{\theta} F θ , defined as
F θ = { f ∈ F : supp ( f ^ ) ⊆ θ } . \mathcal{F}_{\theta}=\{f\in\mathcal{F}:\operatorname{supp}(\widehat{f})\subseteq\theta\}. F θ = { f ∈ F : supp ( f ) ⊆ θ } .
Note that each f ∈ F θ f\in\mathcal{F}_{\theta} f ∈ F θ is such that ∥ f θ ∥ L ∞ ( B 2 ) ≤ 1 \|f_{\theta}\|_{L^{\infty}(B_{2})}\leq1 ∥ f θ ∥ L ∞ ( B 2 ) ≤ 1 , and every f ∈ F f\in\mathcal{F} f ∈ F is such that f = ∑ θ f θ f=\sum_{\theta}f_{\theta} f = ∑ θ f θ , for some f θ ∈ F θ f_{\theta}\in\mathcal{F}_{\theta} f θ ∈ F θ . A corollary of the contraction principle for Rademacher processes4 (see [22 Exercise 7.4] , or Appendix § 10 ) is that
E ϵ sup f ∈ F ∣ ∑ k ∈ S ϵ k D ( α ) f ( y k l ) ∣ ≲ E ϵ sup f ∈ F ∣ ∑ k ∈ S ϵ k D ( α ) f ( y k l ) ∣ . (33) \mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}}\left|\sum_{k\in S}\epsilon_kD^{(\alpha)}f(y_{kl})\right|\lesssim\mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}}\left|\sum_{k\in S}\epsilon_kD^{(\alpha)}f(y_{kl})\right|. \tag*{(33)} E ϵ f ∈ F sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) ≲ E ϵ f ∈ F sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) . (33)
We may write5
E ϵ sup f ∈ F f = ∑ θ f θ ∣ ∑ θ ∑ k ∈ S ϵ k D ( α ) f θ ( y k l ) ∣ ≤ ∑ θ E ϵ sup f ∈ F f = ∑ θ f θ ∣ ∑ k ∈ S ϵ k D ( α ) f θ ( y k l ) ∣ ≤ ∑ θ E ϵ sup f ∈ F θ ∣ ∑ k ∈ S ϵ k D ( α ) f ( y k l ) ∣ , (34) \begin{aligned}
\mathbb{E}_{\epsilon}\sup_{\substack{f\in\mathcal{F}\\f=\sum_{\theta}f_{\theta}}}\left|\sum_{\theta}\sum_{k\in S}\epsilon_kD^{(\alpha)}f_{\theta}(y_{kl})\right|
\leq\sum_{\theta}\mathbb{E}_{\epsilon}\sup_{\substack{f\in\mathcal{F}\\f=\sum_{\theta}f_{\theta}}}\left|\sum_{k\in S}\epsilon_kD^{(\alpha)}f_{\theta}(y_{kl})\right| \\
&\leq\sum_{\theta}\mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}_{\theta}}\left|\sum_{k\in S}\epsilon_kD^{(\alpha)}f(y_{kl})\right|, \tag*{(34)}
\end{aligned} E ϵ f ∈ F f = ∑ θ f θ sup θ ∑ k ∈ S ∑ ϵ k D ( α ) f θ ( y k l ) ≤ θ ∑ E ϵ f ∈ F f = ∑ θ f θ sup k ∈ S ∑ ϵ k D ( α ) f θ ( y k l ) ≤ θ ∑ E ϵ f ∈ F θ sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) , (34)
since ∣ { θ } ∣ = N |\{\theta\}|=N ∣ { θ } ∣ = N , in light of (34), it suffices to establish the estimate
E ϵ sup f ∈ F θ ∣ ∑ k ∈ S ϵ k D ( α ) f ( y k l ) ∣ ≲ ϵ N 1 / 2 + ϵ ∣ S ∣ , (35) \mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}_{\theta}}\left|\sum_{k\in S}\epsilon_kD^{(\alpha)}f(y_{kl})\right|\lesssim_{\epsilon}N^{1/2+\epsilon}\sqrt{|S|}, \tag*{(35)} E ϵ f ∈ F θ sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) ≲ ϵ N 1/2 + ϵ ∣ S ∣ , (35)
for all θ \theta θ .
In order to establish (35), we require two ingredients. First, we require a description of elements in the class F θ \mathcal{F}_{\theta} F θ . This description will allow us to control the complexity of the set F θ \mathcal{F}_{\theta} F θ . Such a description is referred to as a wave packet decomposition. The basic idea is that if supp ( f θ ^ ) ⊆ θ \operatorname{supp}(\widehat{f_{\theta}})\subseteq\theta supp ( f θ ) ⊆ θ , and ∥ f θ ∥ L ∞ ≤ 1 \|f_{\theta}\|_{L^{\infty}}\leq1 ∥ f θ ∥ L ∞ ≤ 1 , then when f θ f_{\theta} f θ is restricted to B N 2 B_{N^{2}} B N 2 we can write
f θ ≈ ∑ k = 1 N a k 1 θ k ∗ , (36) f_{\theta}\approx\sum_{k=1}^{N}a_k\mathbf{1}_{\theta_k^*}, \tag*{(36)} f θ ≈ k = 1 ∑ N a k 1 θ k ∗ , (36)
where ∣ a k ∣ ≤ 1 |a_k|\leq1 ∣ a k ∣ ≤ 1 for all k k k and the θ k ∗ \theta_k^* θ k ∗ 's are N × N 2 N\times N^2 N × N 2 rectangles oriented in the dual direction to θ \theta θ that cover B N 2 B_{N^2} B N 2 . The wave packet decomposition plays an important role in several problems in geometric Fourier analysis, see for example, [9 ] or [6 ] for precise statements and applications. Of course, (36) is not literally true, and so we need the following precise version for our purposes, which is proved in the appendix.
Proposition 10 (Abstract Wave Packet Decomposition). Suppose f ∈ S ( R 2 ) f \in\mathcal{S}(\mathbb{R}^2) f ∈ S ( R 2 ) is such that supp ( f ^ ) ⊆ θ \operatorname{supp}(\widehat{f}) \subseteq\theta supp ( f ) ⊆ θ and ∥ f ∥ L ∞ ( R 2 ) ≲ 1 \|f\|_{L^\infty(\mathbb{R}^2)} \lesssim1 ∥ f ∥ L ∞ ( R 2 ) ≲ 1 . For every δ > 0 \delta> 0 δ > 0 , we can write
f ( x ) = ∑ k ∈ Λ δ a k ϕ k ( x ) + R f ( x ) , f(x) = \sum_{k \in\Lambda_\delta} a_k \phi_k(x) + R_f(x), f ( x ) = k ∈ Λ δ ∑ a k ϕ k ( x ) + R f ( x ) , where the ϕ k \phi_k ϕ k ’s are independent of the choice of f f f and
(1) ∣ a k ∣ ≲ 1 |a_k| \lesssim1 ∣ a k ∣ ≲ 1 for all k ∈ Λ δ k \in\Lambda_\delta k ∈ Λ δ
(2) ∣ Λ δ ∣ ≲ N 1 + δ |\Lambda_\delta| \lesssim N^{1+\delta} ∣ Λ δ ∣ ≲ N 1 + δ
(3) sup x ∈ R 2 ∑ k ∣ ϕ k ( x ) ∣ ≲ 1 \sup_{x \in\mathbb{R}^2} \sum_k |\phi_k(x)| \lesssim1 sup x ∈ R 2 ∑ k ∣ ϕ k ( x ) ∣ ≲ 1
(4) ∥ R f ( x ) ∥ L ∞ ( B N 2 ) ≲ δ N − M \|R_f(x)\|_{L^\infty(B_{N^2})} \lesssim_\delta N^{-M} ∥ R f ( x ) ∥ L ∞ ( B N 2 ) ≲ δ N − M for every M > 0 M > 0 M > 0 .
Remark 11. We call this an ‘abstract’ wave packet decomposition because for our purposes we do not need any geometric information about the ϕ k \phi_k ϕ k ’s. Our proof does not require any ideas coming from incidence geometry or the geometry of wave packets. For more commentary on this matter, refer to the Appendix A.
The second ingredient we require is a corollary of Dudley’s inequality (see Appendix § 10 for more background).
Proposition 12. Fix S ⊆ [ C N 4 ] S \subseteq[CN^4] S ⊆ [ C N 4 ] , and define the metric on the set F θ \mathcal{F}_\theta F θ given as follows
d ( f , g ) = ( ∑ k ∈ S ∣ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) ∣ 2 ) 1 / 2 . d(f,g) = \left(\sum_{k \in S} \left|D^{(\alpha)}f(y_{kl}) - D^{(\alpha)}g(y_{kl})\right|^2\right)^{1/2}. d ( f , g ) = ( k ∈ S ∑ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) 2 ) 1/2 . Let N ( F θ , d , u ) \mathcal{N}(\mathcal{F}_\theta,d,u) N ( F θ , d , u ) , be equal to the minimum number of balls of radius u u u in the metric d ( ⋅ , ⋅ ) d(\cdot,\cdot) d ( ⋅ , ⋅ ) needed to cover F θ \mathcal{F}_\theta F θ . Then,
E ϵ sup f ∈ F θ ∣ ∑ k ∈ S ϵ k ∣ D ( α ) f ( y k l ) ∣ ∣ ≲ ∫ 0 diam ( F θ , d ) log N ( F θ , d , u ) d u . (37) \mathbb{E}_{\epsilon}\sup_{f \in\mathcal{F}_\theta}\left|\sum_{k \in S}\epsilon_k\left|D^{(\alpha)}f(y_{kl})\right|\right| \lesssim\int_0^{\operatorname{diam}(\mathcal{F}_\theta,d)} \sqrt{\log\mathcal{N}(\mathcal{F}_\theta,d,u)}\,du. \tag*{(37)} E ϵ f ∈ F θ sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) ≲ ∫ 0 diam ( F θ , d ) log N ( F θ , d , u ) d u . (37)
For more background on this estimate refer to the appendix.
Entropy Estimates
In view of (60) , we need to obtain bounds on the quantity log N ( F θ , d , u ) \log\mathcal{N}(\mathcal{F}_\theta,d,u) log N ( F θ , d , u ) . We have the following proposition:
Proposition 13. For every A > 4 A > 4 A > 4 , there exist c , C > 0 c,C > 0 c , C > 0 (possibly depending on α \alpha α ) such that following estimate holds:
log N ( F θ , d , u ∣ S ∣ ) ≲ ϵ { N 1 + ϵ log ( C u ) if u ≥ c N − A , ∣ S ∣ log ( C u ) if 0 < u < c N − A . \log\mathcal{N}(\mathcal{F}_\theta,d,u\sqrt{|S|}) \lesssim_\epsilon
\begin{cases}
N^{1+\epsilon}\log\left(\frac{C}{u}\right) & \text{if } u \ge cN^{-A}, \\
|S|\log\left(\frac{C}{u}\right) & \text{if } 0 < u < cN^{-A}.
\end{cases} log N ( F θ , d , u ∣ S ∣ ) ≲ ϵ { N 1 + ϵ log ( u C ) ∣ S ∣ log ( u C ) if u ≥ c N − A , if 0 < u < c N − A .
We first show that this proposition implies (35) .
Proof of (35) assuming Proposition 13. First note by Bernstein’s inequality, for any f ∈ F θ f \in\mathcal{F}_\theta f ∈ F θ ,
∥ D ( α ) f ∥ L ∞ ≲ ∥ f ∥ L ∞ ≲ 1. (38) \|D^{(\alpha)}f\|_{L^\infty} \lesssim\|f\|_{L^\infty} \lesssim1. \tag*{(38)} ∥ D ( α ) f ∥ L ∞ ≲ ∥ f ∥ L ∞ ≲ 1. (38)
Therefore,
d ( f , g ) = ( ∑ k ∈ S ∣ D f ( α ) ( y k l ) − D g ( α ) ( y k l ) ∣ 2 ) 1 / 2 ≲ ∣ S ∣ , (39) d(f,g)=\left(\sum_{k\in S}\left|D f^{(\alpha)}(y_{kl})-D g^{(\alpha)}(y_{kl})\right|^2\right)^{1/2}\lesssim\sqrt{|S|}, \tag*{(39)} d ( f , g ) = ( k ∈ S ∑ D f ( α ) ( y k l ) − D g ( α ) ( y k l ) 2 ) 1/2 ≲ ∣ S ∣ , (39)
hence diam ( F θ , d ) ≲ ∣ S ∣ \operatorname{diam}(\mathcal{F}_{\theta},d)\lesssim\sqrt{|S|} diam ( F θ , d ) ≲ ∣ S ∣ . Now
E ϵ sup f ∈ F θ ∣ ∑ k ∈ S ϵ k ∣ D ( α ) f ( y k l ) ∣ ∣ ≲ ∫ 0 C 1 ∣ S ∣ log N ( F θ , d , u ) d u = ∣ S ∣ ∫ 0 C 1 log N ( F θ , d , u ∣ S ∣ ) d u . \begin{aligned}
\mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}_{\theta}}\left|\sum_{k\in S}\epsilon_k|D^{(\alpha)}f(y_{kl})|\right|\lesssim\int_{0}^{C_1\sqrt{|S|}}\sqrt{\log\mathcal{N}(\mathcal{F}_{\theta},d,u)}\,du \\
&=\sqrt{|S|}\int_{0}^{C_1}\sqrt{\log\mathcal{N}\left(\mathcal{F}_{\theta},d,u\sqrt{|S|}\right)}\,du.
\end{aligned} E ϵ f ∈ F θ sup k ∈ S ∑ ϵ k ∣ D ( α ) f ( y k l ) ∣ ≲ ∫ 0 C 1 ∣ S ∣ log N ( F θ , d , u ) d u = ∣ S ∣ ∫ 0 C 1 log N ( F θ , d , u ∣ S ∣ ) d u .
We estimate this integral in two parts using Proposition 13. We have
∫ 0 C 1 log N ( F θ , d , u ∣ S ∣ ) d u = ∫ 0 c N − A log N ( F θ , d , u ∣ S ∣ ) d u + ∫ c N − A C 1 log N ( F θ , d , u ∣ S ∣ ) d u . \begin{aligned}
\int_{0}^{C_1}\sqrt{\log\mathcal{N}\left(\mathcal{F}_{\theta},d,u\sqrt{|S|}\right)}\,du \\
&=\int_{0}^{cN^{-A}}\sqrt{\log\mathcal{N}\left(\mathcal{F}_{\theta},d,u\sqrt{|S|}\right)}\,du+\int_{cN^{-A}}^{C_1}\sqrt{\log\mathcal{N}\left(\mathcal{F}_{\theta},d,u\sqrt{|S|}\right)}\,du.
\end{aligned} ∫ 0 C 1 log N ( F θ , d , u ∣ S ∣ ) d u = ∫ 0 c N − A log N ( F θ , d , u ∣ S ∣ ) d u + ∫ c N − A C 1 log N ( F θ , d , u ∣ S ∣ ) d u .
To estimate the first integral, note that ∣ S ∣ ≲ N 4 |S|\lesssim N^4 ∣ S ∣ ≲ N 4 , and therefore the first integral is bounded by
∫ 0 c N − A ∣ S ∣ ⋅ log ( C u ) d u ≲ ∣ S ∣ N − A ≲ 1 \int_{0}^{cN^{-A}}\sqrt{|S|}\cdot\sqrt{\log\left(\frac{C}{u}\right)}\,du\lesssim\sqrt{|S|}N^{-A}\lesssim1 ∫ 0 c N − A ∣ S ∣ ⋅ log ( u C ) d u ≲ ∣ S ∣ N − A ≲ 1
since log ( 1 / u ) ≲ u − c \sqrt{\log(1/u)}\lesssim u^{-c} log ( 1/ u ) ≲ u − c for all 0 < c < 1 0<c<1 0 < c < 1 and 0 < u < 1 0<u<1 0 < u < 1 . Choosing c c c sufficiently small, and A > 4 A>4 A > 4 yields the claim. The second integral is bounded by
∫ 0 C 1 N 1 / 2 + ϵ log ( C / u ) d u ≲ N 1 / 2 + ϵ . \int_{0}^{C_1}N^{1/2+\epsilon}\sqrt{\log(C/u)}\,du\lesssim N^{1/2+\epsilon}. ∫ 0 C 1 N 1/2 + ϵ log ( C / u ) d u ≲ N 1/2 + ϵ .
by the integrability of log ( 1 / u ) \log(1/u) log ( 1/ u ) at 0 0 0 .
Putting everything together we see that
∫ 0 C 1 ∣ S ∣ log N ( F θ , d , u ) d u ≲ ϵ ∣ S ∣ N 1 / 2 + ϵ \int_{0}^{C_1}\sqrt{|S|}\sqrt{\log\mathcal{N}\left(\mathcal{F}_{\theta},d,u\right)}\,du\lesssim_{\epsilon}\sqrt{|S|}N^{1/2+\epsilon} ∫ 0 C 1 ∣ S ∣ log N ( F θ , d , u ) d u ≲ ϵ ∣ S ∣ N 1/2 + ϵ
which completes the proof. □
We are now ready to establish the entropy estimates in Proposition 13. We begin with an elementary lemma on how metric entropy estimates are transferred under the image of Lipschitz map.
Lemma 14 (Lipschitz Distortion of Metric Entropy). Let ( X , d X ) (X,d_X) ( X , d X ) and ( Y , d Y ) (Y,d_Y) ( Y , d Y ) be two metric spaces and let Φ : X → Y \Phi:X\to Y Φ : X → Y be a map such that d X ( x 1 , x 2 ) ≤ L d Y ( Φ ( x 1 ) , Φ ( x 2 ) ) d_X(x_1,x_2)\leq Ld_Y(\Phi(x_1),\Phi(x_2)) d X ( x 1 , x 2 ) ≤ L d Y ( Φ ( x 1 ) , Φ ( x 2 )) for all x 1 , x 2 ∈ X x_1,x_2\in X x 1 , x 2 ∈ X , then
log N ( X , d X , L u ) ≤ log N ( Φ ( X ) , d Y , u ) \log\mathcal{N}(X,d_X,Lu)\leq\log\mathcal{N}(\Phi(X),d_Y,u) log N ( X , d X , Lu ) ≤ log N ( Φ ( X ) , d Y , u ) Proof. Let { Φ ( x 1 ) , Φ ( x 2 ) , … , Φ ( x r ) } ∈ Y \{\Phi(x_1),\Phi(x_2),\ldots,\Phi(x_r)\}\in Y { Φ ( x 1 ) , Φ ( x 2 ) , … , Φ ( x r )} ∈ Y be a set of distinct elements such that for any Φ ( x ) ∈ Φ ( X ) \Phi(x)\in\Phi(X) Φ ( x ) ∈ Φ ( X ) , there is some Φ ( x i ) \Phi(x_i) Φ ( x i ) for which d Y ( Φ ( x ) , Φ ( x i ) ) ≤ u d_Y(\Phi(x),\Phi(x_i))\leq u d Y ( Φ ( x ) , Φ ( x i )) ≤ u . Then the set { x 1 , x 2 , … , x r } \{x_1,x_2,\ldots,x_r\} { x 1 , x 2 , … , x r } is such that if x ∈ X x\in X x ∈ X is arbitrary, then there is some x i x_i x i such that d X ( x i , x ) ≤ L d Y ( Φ ( x i ) , Φ ( x ) ) ≤ L u d_X(x_i,x)\leq Ld_Y(\Phi(x_i),\Phi(x))\leq Lu d X ( x i , x ) ≤ L d Y ( Φ ( x i ) , Φ ( x )) ≤ Lu . It follows that
N ( X , d X , L u ) ≤ N ( X , d Y , u ) , \mathcal{N}(X,d_X,Lu)\leq\mathcal{N}(X,d_Y,u), N ( X , d X , Lu ) ≤ N ( X , d Y , u ) , taking logarithms completes the proof. □
Proof of Proposition 13. Any f ∈ F θ f \in\mathcal{F}_{\theta} f ∈ F θ , and any δ > 0 \delta> 0 δ > 0 , by Proposition 10 we may write
D ( α ) f ( x ) = ∑ r = 1 J a r φ r ( x ) + R f ( x ) (40) D^{(\alpha)}f(x) = \sum_{r=1}^{J} a_r\varphi_r(x) + R_f(x) \tag*{(40)} D ( α ) f ( x ) = r = 1 ∑ J a r φ r ( x ) + R f ( x ) (40)
where the φ r \varphi_r φ r ’s and R ( x ) R(x) R ( x ) satisfy properties 1-4 in Proposition 10 and J ≲ N 1 + δ J \lesssim N^{1+\delta} J ≲ N 1 + δ . Proposition 10 applies because D ( α ) f D^{(\alpha)}f D ( α ) f is Fourier supported in θ \theta θ and ∥ D ( α ) f ∥ L ∞ ≲ 1 \lVert D^{(\alpha)}f\rVert_{L^\infty} \lesssim1 ∥ D ( α ) f ∥ L ∞ ≲ 1 , by (38) . Consider the map Φ : F θ → C J \Phi: \mathcal{F}_{\theta} \to\mathbb{C}^{J} Φ : F θ → C J given by
Φ ( f ) = ( a 1 , a 2 , . . , a J ) , \Phi(f) = (a_1, a_2, .., a_J), Φ ( f ) = ( a 1 , a 2 , .. , a J ) ,
where the tuple ( a 1 , a 2 , … , a J ) (a_1,a_2,\ldots,a_J) ( a 1 , a 2 , … , a J ) comes from (40) . Note that a representation of the form (40) may not be unique, but we choose the a j a_j a j ’s that come out of the construction of Proposition 10 and its proof. Since each ∣ a k ∣ ≲ 1 |a_k| \lesssim1 ∣ a k ∣ ≲ 1 , we note that
Φ ( F θ ) ⊆ B ∞ C : = { ( c i ) i = 1 J ⊆ C J : ∣ c i ∣ ≤ C , 1 ≤ i ≤ J } , \Phi(\mathcal{F}_{\theta}) \subseteq B_{\infty}^{C} := \{(c_i)_{i=1}^{J} \subseteq\mathbb{C}^{J} : |c_i| \le C,\ 1 \le i \le J\}, Φ ( F θ ) ⊆ B ∞ C := {( c i ) i = 1 J ⊆ C J : ∣ c i ∣ ≤ C , 1 ≤ i ≤ J } ,
for some absolute constant C C C . Let f , g ∈ F θ f,g \in\mathcal{F}_{\theta} f , g ∈ F θ , be arbitrary, and suppose that
Φ ( f ) = ( a 1 , a 2 , … , a J ) and Φ ( g ) = ( b 1 , b 2 , … , b J ) . \Phi(f) = (a_1,a_2,\ldots,a_J) \quad\text{and} \quad\Phi(g) = (b_1,b_2,\ldots,b_J). Φ ( f ) = ( a 1 , a 2 , … , a J ) and Φ ( g ) = ( b 1 , b 2 , … , b J ) .
We can write
d ( f , g ) = ( ∑ k ∈ S ∣ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) ∣ 2 ) 1 / 2 ≤ ∣ S ∣ max k ∈ S ∣ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) ∣ (41) d(f,g) = \left(\sum_{k\in S}|D^{(\alpha)}f(y_{kl})-D^{(\alpha)}g(y_{kl})|^2\right)^{1/2}
\le\sqrt{|S|}\max_{k\in S}|D^{(\alpha)}f(y_{kl})-D^{(\alpha)}g(y_{kl})| \tag*{(41)} d ( f , g ) = ( k ∈ S ∑ ∣ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) ∣ 2 ) 1/2 ≤ ∣ S ∣ k ∈ S max ∣ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) ∣ (41)
Using the representation (40) (for f f f and g g g ) we have
max k ∈ S ∣ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) ∣ = max k ∈ S ∣ ∑ r = 1 J ( a r − b r ) φ r ( y k l ) + R f ( y k l ) − R g ( y k l ) ∣ ≲ max k ∈ S ∣ ∑ r = 1 J ( a r − b r ) φ r ( y k l ) ∣ + N − A + 1 + δ ≲ ∥ a − b ∥ ℓ ∞ ( C J ) ⋅ max k ∈ S ( ∑ k ∈ S ∣ φ k ( y k l ) ∣ ) + N − A + 1 + δ ≲ ∥ a − b ∥ ℓ ∞ ( C J ) + N − A + 1 + δ \begin{aligned}
\max_{k\in S}|D^{(\alpha)}f(y_{kl})-D^{(\alpha)}g(y_{kl})|
&=\max_{k\in S}\left|\sum_{r=1}^{J}(a_r-b_r)\varphi_r(y_{kl})+R_f(y_{kl})-R_g(y_{kl})\right|\\
&\lesssim\max_{k\in S}\left|\sum_{r=1}^{J}(a_r-b_r)\varphi_r(y_{kl})\right|+N^{-A+1+\delta}\\
&\lesssim\lVert a-b\rVert_{\ell^\infty(\mathbb{C}^{J})}\cdot\max_{k\in S}\left(\sum_{k\in S}|\varphi_k(y_{kl})|\right)+N^{-A+1+\delta}\\
&\lesssim\lVert a-b\rVert_{\ell^\infty(\mathbb{C}^{J})}+N^{-A+1+\delta}
\end{aligned} k ∈ S max ∣ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) ∣ = k ∈ S max r = 1 ∑ J ( a r − b r ) φ r ( y k l ) + R f ( y k l ) − R g ( y k l ) ≲ k ∈ S max r = 1 ∑ J ( a r − b r ) φ r ( y k l ) + N − A + 1 + δ ≲ ∥ a − b ∥ ℓ ∞ ( C J ) ⋅ k ∈ S max ( k ∈ S ∑ ∣ φ k ( y k l ) ∣ ) + N − A + 1 + δ ≲ ∥ a − b ∥ ℓ ∞ ( C J ) + N − A + 1 + δ
where the second and third inequalities follows from properties 4 and 3 of Proposition 10 respectively. Thus when ∥ a − b ∥ ∞ ≳ N − A \lVert a-b\rVert_{\infty}\gtrsim N^{-A} ∥ a − b ∥ ∞ ≳ N − A (where A A A can be taken arbitrarily large), we have
d ( f , g ) ≲ ∣ S ∣ ∥ a − b ∥ ℓ ∞ ( C J ) . d(f,g)\lesssim\sqrt{|S|}\lVert a-b\rVert_{\ell^\infty(\mathbb{C}^{J})}. d ( f , g ) ≲ ∣ S ∣ ∥ a − b ∥ ℓ ∞ ( C J ) .
Therefore by Lemma 14 , when u ≳ N − A u\gtrsim N^{-A} u ≳ N − A ,
log ( F θ , d , u ) ≤ log N ( B ∞ C , ℓ ∞ , u ) . (42) \log(\mathcal{F}_{\theta},d,u)\le\log\mathcal{N}(B_{\infty}^{C},\ell_{\infty},u). \tag*{(42)} log ( F θ , d , u ) ≤ log N ( B ∞ C , ℓ ∞ , u ) . (42)
It turns out that estimating the term log N ( B ∞ C , ℓ ∞ , u ) \log\mathcal{N}(B_{\infty}^{C},\ell_{\infty},u) log N ( B ∞ C , ℓ ∞ , u ) is quite easy, it essentially is asking for how many copies of a small ball in the ℓ ∞ \ell_{\infty} ℓ ∞ norm are are needed to cover a large ball in the ℓ ∞ \ell_{\infty} ℓ ∞ norm. Here is a sketch of this estimate. The ℓ ∞ \ell_{\infty} ℓ ∞ ball of radius C C C in R 2 J \mathbb{R}^{2J} R 2 J , can be covered perfectly by ℓ ∞ \ell_{\infty} ℓ ∞ balls of radius u u u . Comparing the volumes of these two bodies, and computing their quotient we see that
N ( B ∞ C , ℓ ∞ , u ) ≲ ( C u ) 2 J . (43) \mathcal{N}(B_{\infty}^{C},\ell_{\infty},u)\lesssim\left(\frac{C}{u}\right)^{2J}. \tag*{(43)} N ( B ∞ C , ℓ ∞ , u ) ≲ ( u C ) 2 J . (43)
Finally, note that the complex ℓ ∞ \ell_\infty ℓ ∞ ball in C J \mathbb{C}^{J} C J is contained in the real ℓ ∞ \ell_\infty ℓ ∞ ball in R 2 J \mathbb{R}^{2J} R 2 J , which yields the desired bound
log N ( B ∞ C , ℓ ∞ , u ) ≲ N 1 + δ log ( C u ) , \log\mathcal{N}(B_{\infty}^{\mathbb{C}},\ell_\infty,u) \lesssim N^{1+\delta}\log\left(\frac{C}{u}\right), log N ( B ∞ C , ℓ ∞ , u ) ≲ N 1 + δ log ( u C ) ,
and choosing δ \delta δ sufficiently small proves first part of Proposition 13. In order to prove the second part of the proposition, we forget about the wave packet structure of elements in F θ \mathcal{F}_\theta F θ and proceed more crudely. For every f ∈ F θ f\in\mathcal{F}_\theta f ∈ F θ , consider the map Φ ′ : F θ → C ∣ S ∣ \Phi':\mathcal{F}_\theta\to\mathbb{C}^{|S|} Φ ′ : F θ → C ∣ S ∣
Φ ′ ( f ) = ( D ( α ) f ( y k l ) ) k ∈ S (44) \Phi'(f)=\left(D^{(\alpha)}f(y_{kl})\right)_{k\in S} \tag*{(44)} Φ ′ ( f ) = ( D ( α ) f ( y k l ) ) k ∈ S (44)
Since ∥ D ( α ) f ∥ L ∞ ≲ 1 \|D^{(\alpha)}f\|_{L^\infty}\lesssim1 ∥ D ( α ) f ∥ L ∞ ≲ 1 , proceeding as before we see that
d ( f , g ) ≲ ∣ S ∣ ⋅ ∥ Φ ′ ( f ) − Φ ′ ( g ) ∥ ℓ ∞ ( C ∣ S ∣ ) , d(f,g)\lesssim\sqrt{|S|}\cdot\|\Phi'(f)-\Phi'(g)\|_{\ell_\infty(\mathbb{C}^{|S|})}, d ( f , g ) ≲ ∣ S ∣ ⋅ ∥ Φ ′ ( f ) − Φ ′ ( g ) ∥ ℓ ∞ ( C ∣ S ∣ ) ,
and
Φ ′ ( F θ ) ⊆ B ∞ ′ C : = { ( c i ) i = 1 J ⊆ C ∣ S ∣ : ∣ c i ∣ ≤ C , 1 ≤ i ≤ ∣ S ∣ } . (45) \Phi'(\mathcal{F}_\theta)\subseteq B_{\infty}^{\prime\mathbb{C}}:=\left\{(c_i)_{i=1}^{J}\subseteq\mathbb{C}^{|S|}:|c_i|\leq C,\ 1\leq i\leq|S|\right\}. \tag*{(45)} Φ ′ ( F θ ) ⊆ B ∞ ′ C := { ( c i ) i = 1 J ⊆ C ∣ S ∣ : ∣ c i ∣ ≤ C , 1 ≤ i ≤ ∣ S ∣ } . (45)
With the exact same argument used to produce the estimate (43), we see that
N ( B ∞ ′ C , ℓ ∞ , u ) ≲ ( C u ) ∣ S ∣ , \mathcal{N}(B_{\infty}^{\prime\mathbb{C}},\ell_\infty,u)\lesssim\left(\frac{C}{u}\right)^{|S|}, N ( B ∞ ′ C , ℓ ∞ , u ) ≲ ( u C ) ∣ S ∣ ,
so that
log N ( B ∞ ′ C , ℓ ∞ , u ) ≲ ∣ S ∣ log ( C u ) , \log\mathcal{N}(B_{\infty}^{\prime\mathbb{C}},\ell_\infty,u)\lesssim|S|\log\left(\frac{C}{u}\right), log N ( B ∞ ′ C , ℓ ∞ , u ) ≲ ∣ S ∣ log ( u C ) ,
which completes the proof of the proposition. □
Proof of the Lower Bound
In this section, we will show that the estimate (11) is sharp by constructing a family of wave packets that saturate this bound. For a fixed cap θ \theta θ , let T θ \mathcal{T}_\theta T θ be the collection of N × N 2 N\times N^2 N × N 2 rectangles that are oriented in the dual direction to θ \theta θ that cover B N 2 B_{N^2} B N 2 .
Proposition 15. Fix θ \theta θ . There exist functions { ϕ T } T ∈ T θ \{\phi_T\}_{T\in\mathcal{T}_\theta} { ϕ T } T ∈ T θ with each ϕ T ∈ F θ \phi_T\in\mathcal{F}_\theta ϕ T ∈ F θ with following properties
supp ( ϕ T ^ ) ⊆ θ \operatorname{supp}(\widehat{\phi_T})\subseteq\theta supp ( ϕ T ) ⊆ θ
∣ ϕ T ∣ ≳ 1 |\phi_T|\gtrsim1 ∣ ϕ T ∣ ≳ 1 on 1 10 T \frac{1}{10}T 10 1 T for each T ∈ T θ T\in\mathcal{T}_\theta T ∈ T θ .
sup x ∈ B N 2 ∑ T ∈ T θ ∣ ϕ T ( x ) ∣ ≲ 1 \sup_{x\in B_{N^2}}\sum_{T\in\mathcal{T}_\theta}|\phi_T(x)|\lesssim1 sup x ∈ B N 2 ∑ T ∈ T θ ∣ ϕ T ( x ) ∣ ≲ 1 .
Such a construction is well known and we do not prove it here. We refer the interested reader to [10 Notes 3] .
Let S S S be the (random) set
S : = { k : δ k = 1 } , (46) S:=\{k:\delta_k=1\}, \tag*{(46)} S := { k : δ k = 1 } , (46)
and following (9), let V V V be the random set of balls given by
V : = { ⋃ k : δ k = 1 V k } ⊆ B N 2 . V:=\left\{\bigcup_{k:\delta_k=1}V_k\right\}\subseteq B_{N^2}. V := { k : δ k = 1 ⋃ V k } ⊆ B N 2 .
Suppose V k ⊆ V V_k\subseteq V V k ⊆ V is one of the randomly chosen balls. We say T ∈ T θ T\in\mathcal{T}_\theta T ∈ T θ intersects V k V_k V k non-trivially if ∣ V k ∩ T ∣ ≥ 1 2 ∣ V k ∣ |V_k\cap T|\geq\frac{1}{2}|V_k| ∣ V k ∩ T ∣ ≥ 2 1 ∣ V k ∣ . We record the following basic geometric observations: For any fixed V k V_k V k , and each cap θ \theta θ , there is at least one T ∈ T θ T\in\mathcal{T}_\theta T ∈ T θ that non-trivially intersects V k V_k V k . Moreover, for every T ∈ T T \in\mathbb{T} T ∈ T that non-trivially intersects V k V_k V k , there is V k ′ ⊆ V k V'_k \subseteq V_k V k ′ ⊆ V k such that ∣ V k ′ ∣ ∼ 1 100 ∣ V k ∣ |V'_k| \sim\frac{1}{100}|V_k| ∣ V k ′ ∣ ∼ 100 1 ∣ V k ∣ and ∣ V k ′ ∣ ⊆ T |V'_k| \subseteq T ∣ V k ′ ∣ ⊆ T for all such T T T . A consequence of this is that
∣ ∫ V k ′ ϕ T ( x ) d x ∣ ≳ 1 , \left|\int_{V'_k} \phi_T(x)\,dx\right| \gtrsim1, ∫ V k ′ ϕ T ( x ) d x ≳ 1 ,
for every T T T that non-trivially intersects V k V_k V k . Let T = ⋃ θ T θ \mathbb{T} = \bigcup_\theta\mathbb{T}_\theta T = ⋃ θ T θ . For each T ∈ T T \in\mathbb{T} T ∈ T , let c T c_T c T be such that ∣ c T ∣ ≤ 1 |c_T| \le1 ∣ c T ∣ ≤ 1 so that the function
f = ∑ T ∈ T c T ϕ T (47) f = \sum_{T\in\mathbb{T}} c_T\phi_T \tag*{(47)} f = T ∈ T ∑ c T ϕ T (47)
is such that f ∈ F f \in\mathcal{F} f ∈ F . By the bounded overlap of the V k V_k V k ’s we have
∫ V ∣ f ( x ) ∣ d x ≳ ∑ k ∈ S ∫ V k ∣ f ( x ) ∣ d x ≥ ∑ k ∈ S ∣ ∫ V k f ( x ) d x ∣ \int_V |f(x)|\,dx \gtrsim\sum_{k\in S}\int_{V_k}|f(x)|\,dx \geq\sum_{k\in S}\left|\int_{V_k}f(x)\,dx\right| ∫ V ∣ f ( x ) ∣ d x ≳ k ∈ S ∑ ∫ V k ∣ f ( x ) ∣ d x ≥ k ∈ S ∑ ∫ V k f ( x ) d x
We choose the c k c_k c k ’s to be independent random signs ( ϵ T ) T ∈ T (\epsilon_T)_{T\in\mathbb{T}} ( ϵ T ) T ∈ T for a particular choice of the c T c_T c T ’s and use Khintchine’s inequality. More precisely, we have
sup f ∈ F ∫ V ∣ f ( x ) ∣ d x ≳ ∑ k ∈ S ∫ V k E ϵ ∣ ∑ T ∈ T ϵ T ϕ T ( x ) ∣ d x ∼ ∑ k ∈ S ∫ V k ( ∑ T ∈ T ∣ ϕ T ( x ) ∣ 2 ) 1 / 2 d x . \sup_{f\in\mathcal{F}}\int_V |f(x)|\,dx \gtrsim\sum_{k\in S}\int_{V_k}\mathbb{E}_{\epsilon}\left|\sum_{T\in\mathbb{T}}\epsilon_T\phi_T(x)\right|\,dx \sim\sum_{k\in S}\int_{V_k}\left(\sum_{T\in\mathbb{T}}|\phi_T(x)|^2\right)^{1/2}dx. f ∈ F sup ∫ V ∣ f ( x ) ∣ d x ≳ k ∈ S ∑ ∫ V k E ϵ T ∈ T ∑ ϵ T ϕ T ( x ) d x ∼ k ∈ S ∑ ∫ V k ( T ∈ T ∑ ∣ ϕ T ( x ) ∣ 2 ) 1/2 d x .
For any fixed k k k and fixed θ \theta θ , note that there is atleast one T ∈ T θ T \in\mathbb{T}_\theta T ∈ T θ that non trivially intersects V k V_k V k . Since there are N N N caps θ \theta θ , we see that
∫ V k ( ∑ T ∈ T ∣ ϕ T ( x ) ∣ 2 ) 1 / 2 d x ≳ N 1 / 2 , \int_{V_k}\left(\sum_{T\in\mathbb{T}}|\phi_T(x)|^2\right)^{1/2}dx \gtrsim N^{1/2}, ∫ V k ( T ∈ T ∑ ∣ ϕ T ( x ) ∣ 2 ) 1/2 d x ≳ N 1/2 ,
for every k k k . Thus
E sup f ∈ F ∫ V ∣ f ( x ) ∣ d x ≳ N 1 / 2 E ∣ S ∣ = N 1 / 2 q (48) \mathbb{E}\sup_{f\in\mathcal{F}}\int_V |f(x)|\,dx \gtrsim N^{1/2}\mathbb{E}|S| = N^{1/2}q \tag*{(48)} E f ∈ F sup ∫ V ∣ f ( x ) ∣ d x ≳ N 1/2 E ∣ S ∣ = N 1/2 q (48)
which proves one part of the lower bound. To proceed with the second part of the lower bound, first note that
∫ V ∣ f ( x ) ∣ d x ≳ ∑ k ∈ S ∫ V k ′ ∣ f ( x ) ∣ d x ≥ ∑ k ∈ S ∣ ∫ V k ′ f ( x ) d x ∣ , \int_V |f(x)|\,dx \gtrsim\sum_{k\in S}\int_{V'_k}|f(x)|\,dx \geq\sum_{k\in S}\left|\int_{V'_k}f(x)\,dx\right|, ∫ V ∣ f ( x ) ∣ d x ≳ k ∈ S ∑ ∫ V k ′ ∣ f ( x ) ∣ d x ≥ k ∈ S ∑ ∫ V k ′ f ( x ) d x ,
letting f f f be chosen as in (47), we obtain
sup f ∈ F ∫ V ∣ f ( x ) ∣ d x ≳ ∣ ∑ k ∈ S ∣ ∑ T ∈ T ∫ V k ′ c T ϕ T ( x ) d x ∣ ∣ (49) \sup_{f\in\mathcal{F}}\int_V |f(x)|\,dx \gtrsim\left|\sum_{k\in S}\left|\sum_{T\in\mathbb{T}}\int_{V'_k}c_T\phi_T(x)\,dx\right|\right| \tag*{(49)} f ∈ F sup ∫ V ∣ f ( x ) ∣ d x ≳ k ∈ S ∑ T ∈ T ∑ ∫ V k ′ c T ϕ T ( x ) d x (49)
where we are free to choose the c T c_T c T ’s as long as ∣ c T ∣ ≤ 1 |c_T| \leq1 ∣ c T ∣ ≤ 1 for all T T T . Let ( ϵ k ) k ∈ S (\epsilon_k)_{k\in S} ( ϵ k ) k ∈ S be an independent and identically distributed collection of Rademacher signs. The previous inequality gives
sup f ∈ F ∫ V ∣ f ( x ) ∣ d x ≳ E ϵ ∑ k ∈ S ∣ ϵ k ∑ T ∈ T ∫ V k ′ c T ϕ T ( x ) d x ∣ ≥ E ϵ ∣ ∑ T ∈ T c T ∑ k ∈ S ϵ k ∫ V k ′ ϕ T ( x ) d x ∣ . \sup_{f\in\mathcal{F}}\int_V |f(x)|\,dx \gtrsim\mathbb{E}_{\epsilon}\sum_{k\in S}\left|\epsilon_k\sum_{T\in\mathbb{T}}\int_{V'_k}c_T\phi_T(x)\,dx\right| \geq\mathbb{E}_{\epsilon}\left|\sum_{T\in\mathbb{T}}c_T\sum_{k\in S}\epsilon_k\int_{V'_k}\phi_T(x)\,dx\right|. f ∈ F sup ∫ V ∣ f ( x ) ∣ d x ≳ E ϵ k ∈ S ∑ ϵ k T ∈ T ∑ ∫ V k ′ c T ϕ T ( x ) d x ≥ E ϵ T ∈ T ∑ c T k ∈ S ∑ ϵ k ∫ V k ′ ϕ T ( x ) d x .
Since we are free to choose the c T c_T c T ’s, for each T ∈ T T \in\mathbb{T} T ∈ T , we choose c T c_T c T so that
c T ( ∑ k ∈ S ϵ k ∫ V k ′ ϕ T ( x ) d x ) = ∣ ∑ k ∈ S ϵ k ∫ V k ′ ϕ T ( x ) d x ∣ . c_T\left(\sum_{k\in S}\epsilon_k\int_{V'_k}\phi_T(x)\,dx\right)=\left|\sum_{k\in S}\epsilon_k\int_{V'_k}\phi_T(x)\,dx\right|. c T ( k ∈ S ∑ ϵ k ∫ V k ′ ϕ T ( x ) d x ) = k ∈ S ∑ ϵ k ∫ V k ′ ϕ T ( x ) d x .
Therefore,
sup f ∈ F ∣ ∫ V f ( x ) d x ∣ ≳ ∑ T ∈ T E ϵ T ∣ ∑ k ∈ S ϵ k ∫ V k ′ ϕ T ( x ) d x ∣ ∼ ∑ T ∈ T ( ∑ k ∈ S ∣ ∫ V k ′ ϕ T ( x ) d x ∣ 2 ) 1 / 2 \sup_{f\in\mathcal{F}}\left|\int_V f(x)\,dx\right|\gtrsim\sum_{T\in\mathbb{T}}\mathbb{E}_{\epsilon_T}\left|\sum_{k\in S}\epsilon_k\int_{V'_k}\phi_T(x)\,dx\right|\sim\sum_{T\in\mathbb{T}}\left(\sum_{k\in S}\left|\int_{V'_k}\phi_T(x)\,dx\right|^2\right)^{1/2} f ∈ F sup ∫ V f ( x ) d x ≳ T ∈ T ∑ E ϵ T k ∈ S ∑ ϵ k ∫ V k ′ ϕ T ( x ) d x ∼ T ∈ T ∑ k ∈ S ∑ ∫ V k ′ ϕ T ( x ) d x 2 1/2
by Khintchine’s inequality. For any fixed T ∈ T T\in\mathbb{T} T ∈ T , note that T T T contains ∼ N 3 \sim N^3 ∼ N 3 unit balls. The probability of any unit ball V k ⊂ T V_k\subset T V k ⊂ T to be included in V V V is ∼ q N 4 \sim\frac{q}{N^4} ∼ N 4 q . Thus for any fixed T T T we observe that
∑ k ∈ S ∣ ∫ V k ′ ϕ T ( x ) d x ∣ 2 ∼ Binomial ( N 3 , q N 4 ) , \sum_{k\in S}\left|\int_{V'_k}\phi_T(x)\,dx\right|^2\sim\operatorname{Binomial}\left(N^3,\frac{q}{N^4}\right), k ∈ S ∑ ∫ V k ′ ϕ T ( x ) d x 2 ∼ Binomial ( N 3 , N 4 q ) ,
which is a random variable with mean ∼ q N \sim\frac{q}{N} ∼ N q . Finally,
E S sup f ∈ F ∣ ∫ V f ( x ) d x ∣ ≳ E S ∑ T ∈ T ( ∑ k ∈ S ∣ ∫ V k ′ ϕ T ( x ) d x ∣ 2 ) 1 / 2 ∼ N 2 ⋅ ( q N ) 1 / 2 = N 3 / 2 q , \mathbb{E}_S\sup_{f\in\mathcal{F}}\left|\int_V f(x)\,dx\right|\gtrsim\mathbb{E}_S\sum_{T\in\mathbb{T}}\left(\sum_{k\in S}\left|\int_{V'_k}\phi_T(x)\,dx\right|^2\right)^{1/2}\sim N^2\cdot\left(\frac{q}{N}\right)^{1/2}=N^{3/2}\sqrt{q}, E S f ∈ F sup ∫ V f ( x ) d x ≳ E S T ∈ T ∑ k ∈ S ∑ ∫ V k ′ ϕ T ( x ) d x 2 1/2 ∼ N 2 ⋅ ( N q ) 1/2 = N 3/2 q ,
which completes the proof of the second part of the lower bound6 .
This lower bound proof bears similarity with the ‘wave packet tuning’ strategy presented in [12 ] . I am sure this is known to experts, but I have not seen this precisely written down anywhere in the literature.
Further Remarks
Suggestions For Reading This Paper
This paper makes several technical reductions that make it possible for the Fourier analytic setup for the problem to work with probabilistic machinery. On the first reading of this paper, the reader is suggested to make the following ‘cheats’ to understand the basic strategy of the proof.
Assume that every f ∈ F f\in\mathcal{F} f ∈ F is constant on any unit ball V k ⊆ B N 2 V_k\subseteq B_{N^2} V k ⊆ B N 2 . If this is assumed, the technical reduction of Section 2 is not needed. One can replace the term D ( α ) f ( y k l ) D^{(\alpha)}f(y_{kl}) D ( α ) f ( y k l ) with f ( y k ) f(y_k) f ( y k ) .
Assume that any f ∈ F θ f\in\mathcal{F}_{\theta} f ∈ F θ can be written as
f = ∑ T ∈ T θ c T 1 T f=\sum_{T\in\mathcal{T}_{\theta}}c_T\mathbb{1}_T f = T ∈ T θ ∑ c T 1 T
where T θ \mathcal{T}_{\theta} T θ is the set of N × N 2 N\times N^2 N × N 2 rectangles that cover B N 2 B_{N^2} B N 2 . This avoids the need for technical estimates used to prove Proposition 10.
As a further simplification, it may be helpful to consider the special case where we restrict to the class of f ∈ F f\in\mathcal{F} f ∈ F , where f f f is the sum of only one wave packet in each direction. That is, consider the simplified model where each f ∈ F f\in\mathcal{F} f ∈ F can be represented as
f = ∑ θ c θ 1 T θ f=\sum_{\theta}c_{\theta}\mathbb{1}_{T_{\theta}} f = θ ∑ c θ 1 T θ
for some T θ ∈ T θ T_{\theta}\in\mathcal{T}_{\theta} T θ ∈ T θ . In this case one obtains the bound
sup f ∈ F ∥ f ∥ L 1 ( V ) ∼ N 1 / 2 q , (50) \sup_{f\in\mathcal{F}}\|f\|_{L^1(V)}\sim N^{1/2}q, \tag*{(50)} f ∈ F sup ∥ f ∥ L 1 ( V ) ∼ N 1/2 q , (50)
that is, the first term in Proposition 4 dominates.
On a personal note, when I started working on this problem, I conjectured that (50) was the truth. I was not able to prove this, but eventually managed to do so in the simplified model of case (3) mentioned above. The argument in this proof (in particular the inequality (41) ) feels quite lossy, and I was not convinced that this argument was sharp until I discovered the second part of the lower bound in § 7 .
Another important detail is why the reduction of § 5.1 is necessary. As far as I can tell, the only place where it is necessary in the sequence of inequalities culminating in (34) . In order for this sequence of inequalities to work one crucially needs that the map
f → D ( α ) f f \to D^{(\alpha)}f f → D ( α ) f
is a linear map. If we do not have the reduction of § 5.1 , then manipulating the map
f → ∫ V k ∣ f ( x ) ∣ d x f \to\int_{V_k} |f(x)|dx f → ∫ V k ∣ f ( x ) ∣ d x
is awkward, because it is non-linear and one cannot deduce the equivalent of (34) in this setting.
Appendix A: Some Results in Fourier Analysis
Wave Packet Decomposition
In this section we rigorously prove Proposition 10. The wave packet decomposition has been proved and used in various forms (see [9 ] , [6 ] , [14 ] for illustrative examples). In order to make our proof work we require L ∞ L^\infty L ∞ control of the remainder term and also need a pointwise bound for the sum of the wave packets. The wave packet decompositions proved in the existing literature do not explicitly prove these properties, so we prove this precise version for our purposes here. Moreover, in our case we do not require any geometric properties of the wave packets. Most proofs involving the wave packet decomposition need to show (precisely) that the wave packets are large on a N × N 2 N \times N^2 N × N 2 rectangle and rapidly decaying outside. Our proof does not need this feature of the wave packet decomposition.
Proposition 16 (Abstract Wave Packet Decomposition). Suppose f ∈ S ( R 2 ) f \in\mathcal{S}(\mathbb{R}^2) f ∈ S ( R 2 ) is such that supp ( f ^ ) ⊆ θ \operatorname{supp}(\widehat{f}) \subseteq\theta supp ( f ) ⊆ θ and ∥ f ∥ L ∞ ( R 2 ) ≲ 1 \|f\|_{L^\infty(\mathbb{R}^2)} \lesssim1 ∥ f ∥ L ∞ ( R 2 ) ≲ 1 . For every δ > 0 \delta> 0 δ > 0 , we can write
f ( x ) = ∑ k ∈ Λ δ a k ϕ k ( x ) + R f ( x ) , f(x) = \sum_{k\in\Lambda_\delta} a_k\phi_k(x) + R_f(x), f ( x ) = k ∈ Λ δ ∑ a k ϕ k ( x ) + R f ( x ) , where the ϕ k \phi_k ϕ k ’s are independent of the choice f f f and
(1) ∣ a k ∣ ≲ 1 |a_k| \lesssim1 ∣ a k ∣ ≲ 1 for all k ∈ Λ δ k \in\Lambda_\delta k ∈ Λ δ
(2) ∣ Λ δ ∣ ≲ N 1 + δ |\Lambda_\delta| \lesssim N^{1+\delta} ∣ Λ δ ∣ ≲ N 1 + δ
(3) sup x ∈ R 2 ∑ k ∈ Λ δ ∣ ϕ k ( x ) ∣ ≲ 1 \sup_{x\in\mathbb{R}^2} \sum_{k\in\Lambda_\delta} |\phi_k(x)| \lesssim1 sup x ∈ R 2 ∑ k ∈ Λ δ ∣ ϕ k ( x ) ∣ ≲ 1
(4) ∥ R ( x ) ∥ L ∞ ( B N 2 ) ≲ δ N − M \|R(x)\|_{L^\infty(B_{N^2})} \lesssim_\delta N^{-M} ∥ R ( x ) ∥ L ∞ ( B N 2 ) ≲ δ N − M for every M > 0 M > 0 M > 0 .
Proof. By rotating and translating f f f in Fourier space (these operations do not affect the desired properties of our abstract decomposition, as can be checked), we may without loss of generality assume that θ = [ 0 , 1 N ] × [ 0 , 1 N 2 ] \theta= [0,\frac{1}{N}] \times[0,\frac{1}{N^2}] θ = [ 0 , N 1 ] × [ 0 , N 2 1 ] . Define
h ( ξ 1 , ξ 2 ) = f ^ ( ξ 1 N , ξ 2 N 2 ) . (51) h(\xi_1,\xi_2) = \widehat{f}\left(\frac{\xi_1}{N},\frac{\xi_2}{N^2}\right). \tag*{(51)} h ( ξ 1 , ξ 2 ) = f ( N ξ 1 , N 2 ξ 2 ) . (51)
By Fourier inversion we can write
f ( x ) = ∫ θ f ^ ( ξ 1 , ξ 2 ) e 2 π i ( ξ 1 x 1 + ξ 2 ⋅ x 2 ) d ξ . (52) f(x) = \int_\theta\widehat{f}(\xi_1,\xi_2)e^{2\pi i(\xi_1x_1+\xi_2\cdot x_2)}\,d\xi. \tag*{(52)} f ( x ) = ∫ θ f ( ξ 1 , ξ 2 ) e 2 π i ( ξ 1 x 1 + ξ 2 ⋅ x 2 ) d ξ . (52)
Applying the change of variables ξ 1 → ξ 1 N \xi_1 \to\frac{\xi_1}{N} ξ 1 → N ξ 1 and ξ 2 → ξ 2 N 2 \xi_2 \to\frac{\xi_2}{N^2} ξ 2 → N 2 ξ 2 in (52) , the region θ \theta θ is transformed to the region [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 and the Jacobian factor is 1 N 3 \frac{1}{N^3} N 3 1 . Therefore we have
f ( x ) = 1 N 3 ∫ [ 0 , 1 ] 2 f ^ ( ξ 1 N , ξ 2 N 2 ) e 2 π i ( ξ 1 x 1 N + ξ 2 x 2 N 2 ) d ξ = 1 N 3 ∫ [ 0 , 1 ] 2 h ( ξ 1 , ξ 2 ) e 2 π i ( ξ 1 x 1 N + ξ 2 x 2 N 2 ) d ξ . (53) f(x) = \frac{1}{N^3}\int_{[0,1]^2}\widehat{f}\left(\frac{\xi_1}{N},\frac{\xi_2}{N^2}\right)e^{2\pi i\left(\frac{\xi_1x_1}{N}+\frac{\xi_2x_2}{N^2}\right)}\,d\xi= \frac{1}{N^3}\int_{[0,1]^2}h(\xi_1,\xi_2)e^{2\pi i\left(\frac{\xi_1x_1}{N}+\frac{\xi_2x_2}{N^2}\right)}\,d\xi. \tag*{(53)} f ( x ) = N 3 1 ∫ [ 0 , 1 ] 2 f ( N ξ 1 , N 2 ξ 2 ) e 2 π i ( N ξ 1 x 1 + N 2 ξ 2 x 2 ) d ξ = N 3 1 ∫ [ 0 , 1 ] 2 h ( ξ 1 , ξ 2 ) e 2 π i ( N ξ 1 x 1 + N 2 ξ 2 x 2 ) d ξ . (53)
Since h h h is smooth and supp ( h ) ⊆ [ − π , π ] 2 \operatorname{supp}(h) \subseteq[-\pi,\pi]^2 supp ( h ) ⊆ [ − π , π ] 2 , we can extend h h h to a 2 π 2\pi 2 π periodic function on R 2 \mathbb{R}^2 R 2 . Expanding h h h as a Fourier series on [ − π , π ] [-\pi,\pi] [ − π , π ] , we write
h ( ξ 1 , ξ 2 ) = ∑ n , m ∈ Z c n , m e i ( ξ 1 n + ξ 2 m ) , (54) h(\xi_1,\xi_2) = \sum_{n,m\in\mathbb{Z}} c_{n,m}e^{i(\xi_1n+\xi_2m)}, \tag*{(54)} h ( ξ 1 , ξ 2 ) = n , m ∈ Z ∑ c n , m e i ( ξ 1 n + ξ 2 m ) , (54)
where the above sum converges uniformly on [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 (since f ∈ S ( R 2 ) f \in\mathcal{S}(\mathbb{R}^2) f ∈ S ( R 2 ) ) and the Fourier coefficients are given by
c n , m = 1 2 π ∬ [ 0 , 1 ] 2 h ( ξ 1 , ξ 2 ) e − i ( n ξ 1 + m ξ 2 ) d ξ . c_{n,m}=\frac{1}{2\pi}\iint_{[0,1]^2}h(\xi_1,\xi_2)e^{-i(n\xi_1+m\xi_2)}\,\mathrm{d}\xi. c n , m = 2 π 1 ∬ [ 0 , 1 ] 2 h ( ξ 1 , ξ 2 ) e − i ( n ξ 1 + m ξ 2 ) d ξ .
Recalling that h ( ξ 1 , ξ 2 ) = f ( ξ 1 N , ξ 2 N 2 ) h(\xi_1,\xi_2)=f\left(\frac{\xi_1}{N},\frac{\xi_2}{N^2}\right) h ( ξ 1 , ξ 2 ) = f ( N ξ 1 , N 2 ξ 2 ) , we use the change of variables ξ 1 → ξ 1 N \xi_1\to\xi_1N ξ 1 → ξ 1 N and ξ 2 → ξ 2 N 2 \xi_2\to\xi_2N^2 ξ 2 → ξ 2 N 2 to yield
c n , m = N 3 2 π ∬ θ f ^ ( ξ 1 , ξ 2 ) e − i ( ξ 1 n N + ξ 2 m N 2 ) d ξ . c_{n,m}=\frac{N^3}{2\pi}\iint_{\theta}\widehat{f}(\xi_1,\xi_2)e^{-i(\xi_1nN+\xi_2mN^2)}\,\mathrm{d}\xi. c n , m = 2 π N 3 ∬ θ f ( ξ 1 , ξ 2 ) e − i ( ξ 1 n N + ξ 2 m N 2 ) d ξ .
Applying the Fourier inversion formula we see that
c n , m = N 3 2 π f ( − n N 2 π , − m N 2 2 π ) . c_{n,m}=\frac{N^3}{2\pi}f\left(-\frac{nN}{2\pi},-\frac{mN^2}{2\pi}\right). c n , m = 2 π N 3 f ( − 2 π n N , − 2 π m N 2 ) .
the condition that ∥ f ∥ L ∞ ≲ 1 \|f\|_{L^\infty}\lesssim1 ∥ f ∥ L ∞ ≲ 1 shows that ∣ c n , m ∣ ≲ N 3 |c_{n,m}|\lesssim N^3 ∣ c n , m ∣ ≲ N 3 . Now let η ( ξ 1 , ξ 2 ) ∈ C c ∞ ( R 2 ) \eta(\xi_1,\xi_2)\in C^\infty_c(\mathbb{R}^2) η ( ξ 1 , ξ 2 ) ∈ C c ∞ ( R 2 ) be such that η ≡ 1 \eta\equiv1 η ≡ 1 on [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 and η ≡ 0 \eta\equiv0 η ≡ 0 on R 2 ∖ [ − 2 , 2 ] 2 \mathbb{R}^2\setminus[-2,2]^2 R 2 ∖ [ − 2 , 2 ] 2 . Since supp ( h ) ⊆ [ 0 , 1 ] 2 \operatorname{supp}(h)\subseteq[0,1]^2 supp ( h ) ⊆ [ 0 , 1 ] 2 , clearly we have that
h ( ξ 1 , ξ 2 ) = η ( ξ 1 , ξ 2 ) h ( ξ 1 , ξ 2 ) , ∀ ( ξ 1 , ξ 2 ) ∈ R 2 . h(\xi_1,\xi_2)=\eta(\xi_1,\xi_2)h(\xi_1,\xi_2),\quad\forall(\xi_1,\xi_2)\in\mathbb{R}^2. h ( ξ 1 , ξ 2 ) = η ( ξ 1 , ξ 2 ) h ( ξ 1 , ξ 2 ) , ∀ ( ξ 1 , ξ 2 ) ∈ R 2 .
Combining (53) and (54), we have that
f ( x ) = 1 N 3 ∬ [ 0 , 1 ] 2 h ( ξ 1 , ξ 2 ) e 2 π i ( ξ 1 x 1 N + ξ 2 x 2 N 2 ) d ξ = 1 N 3 ∬ R 2 h ( ξ 1 , ξ 2 ) η ( ξ 1 , ξ 2 ) e 2 π i ( ξ 1 x 1 N + ξ 2 x 2 N 2 ) d ξ = ∑ n , m c n , m N 3 ∬ R 2 η ( ξ 1 , ξ 2 ) e i ( n ξ 1 + m ξ 2 ) ⋅ e 2 π i ( ξ 1 x 1 N + ξ 2 x 2 N 2 ) d ξ = ∑ n , m c n , m N 3 η ^ ( − x 1 N − n 2 π , − x 2 N 2 − m 2 π ) . \begin{aligned}
f(x)&=\frac{1}{N^3}\iint_{[0,1]^2}h(\xi_1,\xi_2)e^{2\pi i\left(\frac{\xi_1x_1}{N}+\frac{\xi_2x_2}{N^2}\right)}\,\mathrm{d}\xi\\
&=\frac{1}{N^3}\iint_{\mathbb{R}^2}h(\xi_1,\xi_2)\eta(\xi_1,\xi_2)e^{2\pi i\left(\frac{\xi_1x_1}{N}+\frac{\xi_2x_2}{N^2}\right)}\,\mathrm{d}\xi\\
&=\sum_{n,m}\frac{c_{n,m}}{N^3}\iint_{\mathbb{R}^2}\eta(\xi_1,\xi_2)e^{i(n\xi_1+m\xi_2)}\cdot e^{2\pi i\left(\frac{\xi_1x_1}{N}+\frac{\xi_2x_2}{N^2}\right)}\,\mathrm{d}\xi\\
&=\sum_{n,m}\frac{c_{n,m}}{N^3}\widehat{\eta}\left(-\frac{x_1}{N}-\frac{n}{2\pi},-\frac{x_2}{N^2}-\frac{m}{2\pi}\right).
\end{aligned} f ( x ) = N 3 1 ∬ [ 0 , 1 ] 2 h ( ξ 1 , ξ 2 ) e 2 π i ( N ξ 1 x 1 + N 2 ξ 2 x 2 ) d ξ = N 3 1 ∬ R 2 h ( ξ 1 , ξ 2 ) η ( ξ 1 , ξ 2 ) e 2 π i ( N ξ 1 x 1 + N 2 ξ 2 x 2 ) d ξ = n , m ∑ N 3 c n , m ∬ R 2 η ( ξ 1 , ξ 2 ) e i ( n ξ 1 + m ξ 2 ) ⋅ e 2 π i ( N ξ 1 x 1 + N 2 ξ 2 x 2 ) d ξ = n , m ∑ N 3 c n , m η ( − N x 1 − 2 π n , − N 2 x 2 − 2 π m ) .
We set
a n , m = c n , m N 3 . a_{n,m}=\frac{c_{n,m}}{N^3}. a n , m = N 3 c n , m .
and
ϕ n , m ( x 1 , x 2 ) = η ^ ( − x 1 N − n 2 π , − x 2 N 2 − m 2 π ) . \phi_{n,m}(x_1,x_2)=\widehat{\eta}\left(-\frac{x_1}{N}-\frac{n}{2\pi},-\frac{x_2}{N^2}-\frac{m}{2\pi}\right). ϕ n , m ( x 1 , x 2 ) = η ( − N x 1 − 2 π n , − N 2 x 2 − 2 π m ) .
It is clear that the ϕ n , m \phi_{n,m} ϕ n , m ’s are independent of f f f and ∣ a n , m ∣ ≲ 1 |a_{n,m}|\lesssim1 ∣ a n , m ∣ ≲ 1 for all n , m n,m n , m . Since η ^ \widehat{\eta} η is the Fourier transform a bump function, geometrically, the function ϕ m , n \phi_{m,n} ϕ m , n can be thought of as being largest on a N × N 2 N\times N^2 N × N 2 rectangle centered at the point ( n N 2 π , m N 2 2 π ) \left(\frac{nN}{2\pi},\frac{mN^2}{2\pi}\right) ( 2 π n N , 2 π m N 2 ) and rapidly decaying outside of this rectangle. We use this basic heuristic to set up our abstract wave packet decomposition.
Selecting the wave packets and the remainder: Fix δ > 0 \delta>0 δ > 0 , and define
Λ δ : = { ( m , n ) ∈ Z 2 : ∣ n ∣ ≤ 10 N δ , ∣ m ∣ ≤ 10 N 1 + δ } . \Lambda_\delta:=\{(m,n)\in\mathbb{Z}^2:|n|\leq10N^\delta,\ |m|\leq10N^{1+\delta}\}. Λ δ := {( m , n ) ∈ Z 2 : ∣ n ∣ ≤ 10 N δ , ∣ m ∣ ≤ 10 N 1 + δ } .
so that we have ∣ Λ δ ∣ ≲ N 1 + 2 δ |\Lambda_\delta|\lesssim N^{1+2\delta} ∣ Λ δ ∣ ≲ N 1 + 2 δ . We set
R f ( x 1 , x 2 ) : = ∑ ( n , m ) ∉ Λ δ a n , m ϕ n , m ( x 1 , x 2 ) . R_f(x_1,x_2):=\sum_{(n,m)\notin\Lambda_\delta}a_{n,m}\phi_{n,m}(x_1,x_2). R f ( x 1 , x 2 ) := ( n , m ) ∈ / Λ δ ∑ a n , m ϕ n , m ( x 1 , x 2 ) .
We can now write
f ( x ) = ∑ ( n , m ) ∈ Λ δ a n , m ϕ n , m ( x ) + R ( x ) , (55) f(x)=\sum_{(n,m)\in\Lambda_\delta}a_{n,m}\phi_{n,m}(x)+R(x), \tag*{(55)} f ( x ) = ( n , m ) ∈ Λ δ ∑ a n , m ϕ n , m ( x ) + R ( x ) , (55)
and properties 1 and 2 of the proposition have been established. It now remains to prove properties 3 and 4.
The Schwartz decay of η ^ \hat{\eta} η ^ tells us that for all large M > 0 M>0 M > 0 ,
∣ ϕ n , m ( x 1 , x 2 ) ∣ ≲ ( 1 + ∣ n 2 π + x 1 N ∣ + ∣ m 2 π + x 2 N 2 ∣ ) − M . (56) |\phi_{n,m}(x_1,x_2)| \lesssim\left(1+\left|\frac{n}{2\pi}+\frac{x_1}{N}\right|+\left|\frac{m}{2\pi}+\frac{x_2}{N^2}\right|\right)^{-M}. \tag*{(56)} ∣ ϕ n , m ( x 1 , x 2 ) ∣ ≲ ( 1 + 2 π n + N x 1 + 2 π m + N 2 x 2 ) − M . (56)
We can now show that
sup x ∈ R 2 ∑ ( n , m ) ∈ Λ δ ∣ ϕ n , m ( x ) ∣ ≲ 1 , \sup_{x\in\mathbb{R}^2}\sum_{(n,m)\in\Lambda_\delta}|\phi_{n,m}(x)|\lesssim1, x ∈ R 2 sup ( n , m ) ∈ Λ δ ∑ ∣ ϕ n , m ( x ) ∣ ≲ 1 ,
which is property 3 of our wave packet decomposition. First we note that given any ( x 1 , x 2 ) ∈ R 2 (x_1,x_2)\in\mathbb{R}^2 ( x 1 , x 2 ) ∈ R 2 , define
E j = { ( n , m ) ∈ Z 2 : j ≤ dist ℓ 1 ( ( − n 2 π , − m 2 π ) , ( x 1 N , x 2 N 2 ) ) ≤ j + 1 } , E_j=\left\{(n,m)\in\mathbb{Z}^2:j\leq\operatorname{dist}_{\ell_1}\left(\left(\frac{-n}{2\pi},\frac{-m}{2\pi}\right),\left(\frac{x_1}{N},\frac{x_2}{N^2}\right)\right)\leq j+1\right\}, E j = { ( n , m ) ∈ Z 2 : j ≤ dist ℓ 1 ( ( 2 π − n , 2 π − m ) , ( N x 1 , N 2 x 2 ) ) ≤ j + 1 } ,
a basic counting argument gives
∣ E j ∣ ≲ j . (57) |E_j|\lesssim j. \tag*{(57)} ∣ E j ∣ ≲ j . (57)
Now by (56) and (57) ,
∑ ( n , m ) ∈ Λ δ ∣ ϕ n , m ( x 1 , x 2 ) ∣ ≲ ∑ ( n , m ) ∈ Λ δ ( 1 + ∣ n 2 π + x 1 N ∣ + ∣ m 2 π + x 2 N 2 ∣ ) − M ≲ ∑ j ∑ ( n , m ) ∈ Λ δ ( 1 + ∣ n 2 π + x 1 N ∣ + ∣ m 2 π + x 2 N 2 ∣ ) − M ≲ M ∑ j j ( 1 + j ) − M ≲ 1 , \begin{aligned}
\sum_{(n,m)\in\Lambda_\delta}|\phi_{n,m}(x_1,x_2)|
&\lesssim\sum_{(n,m)\in\Lambda_\delta}\left(1+\left|\frac{n}{2\pi}+\frac{x_1}{N}\right|+\left|\frac{m}{2\pi}+\frac{x_2}{N^2}\right|\right)^{-M}\\
&\lesssim\sum_j\sum_{(n,m)\in\Lambda_\delta}\left(1+\left|\frac{n}{2\pi}+\frac{x_1}{N}\right|+\left|\frac{m}{2\pi}+\frac{x_2}{N^2}\right|\right)^{-M}\\
&\lesssim_M\sum_j j(1+j)^{-M}\\
&\lesssim1,
\end{aligned} ( n , m ) ∈ Λ δ ∑ ∣ ϕ n , m ( x 1 , x 2 ) ∣ ≲ ( n , m ) ∈ Λ δ ∑ ( 1 + 2 π n + N x 1 + 2 π m + N 2 x 2 ) − M ≲ j ∑ ( n , m ) ∈ Λ δ ∑ ( 1 + 2 π n + N x 1 + 2 π m + N 2 x 2 ) − M ≲ M j ∑ j ( 1 + j ) − M ≲ 1 ,
where the last line follows from choosing M > 3 M>3 M > 3 .
We now show that ∥ R f ( x ) ∥ L ∞ ( B N 2 ) ≲ N − A \|R_f(x)\|_{L^\infty(B_{N^2})}\lesssim N^{-A} ∥ R f ( x ) ∥ L ∞ ( B N 2 ) ≲ N − A , for all A > 0 A>0 A > 0 , which is the final property that needs to be proved. If ( n , m ) ∉ Λ δ (n,m)\notin\Lambda_\delta ( n , m ) ∈ / Λ δ then either
∣ n ∣ > 10 N δ or ∣ m ∣ > 10 N 1 + δ . |n|>10N^\delta\qquad\text{or}\qquad|m|>10N^{1+\delta}. ∣ n ∣ > 10 N δ or ∣ m ∣ > 10 N 1 + δ .
In any case, if ( x 1 , x 2 ) ∈ B N 2 (x_1,x_2)\in B_{N^2} ( x 1 , x 2 ) ∈ B N 2 , then we must necessarily have that
∣ n 2 π + x 1 N ∣ + ∣ m 2 π + x 2 N 2 ∣ ≳ dist ℓ 1 ( ( − n 2 π , − m 2 π ) , ( x 1 N , x 2 N 2 ) ) ≳ N δ . (58) \left|\frac{n}{2\pi}+\frac{x_1}{N}\right|+\left|\frac{m}{2\pi}+\frac{x_2}{N^2}\right|\gtrsim\operatorname{dist}_{\ell_1}\left(\left(\frac{-n}{2\pi},\frac{-m}{2\pi}\right),\left(\frac{x_1}{N},\frac{x_2}{N^2}\right)\right)\gtrsim N^\delta. \tag*{(58)} 2 π n + N x 1 + 2 π m + N 2 x 2 ≳ dist ℓ 1 ( ( 2 π − n , 2 π − m ) , ( N x 1 , N 2 x 2 ) ) ≳ N δ . (58)
since ∣ x 1 ∣ , ∣ x 2 ∣ ≤ N 2 |x_1|, |x_2| \le N^2 ∣ x 1 ∣ , ∣ x 2 ∣ ≤ N 2 . Finally, we can estimate the remainder: If ( x 1 , x 2 ) ∈ B N 2 (x_1,x_2) \in B_{N^2} ( x 1 , x 2 ) ∈ B N 2 we have by (56), (57), and (58) that
∣ R f ( x ) ∣ = ∣ ∑ ( n , m ) ∉ Λ δ a n , m ϕ n , m ( x 1 , x 2 ) ∣ ≲ ∑ ( n , m ) ∉ Λ δ ∣ ϕ n , m ( x 1 , x 2 ) ∣ ≲ ∑ ( n , m ) ∉ Λ δ ( 1 + ∣ n 2 π + x 1 N 2 ∣ + ∣ m 2 π + x 2 N 2 ∣ ) − M ≲ ∑ j ∑ ( n , m ) ∈ Λ δ ( n , m ) ∈ E j j ⋅ ( 1 + j ) − M ≲ ∑ j ≳ N δ j ( 1 + j ) − M ≲ δ N − A \begin{aligned}
|R_f(x)| &= \left|\sum_{(n,m)\notin\Lambda_\delta} a_{n,m}\phi_{n,m}(x_1,x_2)\right| \\
&\lesssim\sum_{(n,m)\notin\Lambda_\delta} |\phi_{n,m}(x_1,x_2)| \\
&\lesssim\sum_{(n,m)\notin\Lambda_\delta} \left(1+\left|\frac{n}{2\pi}+\frac{x_1}{N^2}\right|+\left|\frac{m}{2\pi}+\frac{x_2}{N^2}\right|\right)^{-M} \\
&\lesssim\sum_j \sum_{\substack{(n,m)\in\Lambda_\delta\\(n,m)\in E_j}} j\cdot(1+j)^{-M} \\
&\lesssim\sum_{j\gtrsim N^\delta} j(1+j)^{-M} \\
&\lesssim_\delta N^{-A}
\end{aligned} ∣ R f ( x ) ∣ = ( n , m ) ∈ / Λ δ ∑ a n , m ϕ n , m ( x 1 , x 2 ) ≲ ( n , m ) ∈ / Λ δ ∑ ∣ ϕ n , m ( x 1 , x 2 ) ∣ ≲ ( n , m ) ∈ / Λ δ ∑ ( 1 + 2 π n + N 2 x 1 + 2 π m + N 2 x 2 ) − M ≲ j ∑ ( n , m ) ∈ Λ δ ( n , m ) ∈ E j ∑ j ⋅ ( 1 + j ) − M ≲ j ≳ N δ ∑ j ( 1 + j ) − M ≲ δ N − A
where the last line holds if M M M (depending on δ \delta δ ) is chosen large enough. This shows that ∥ R ( x ) ∥ L ∞ ( B N 2 ) ≲ δ N − A \|R(x)\|_{L^\infty(B_{N^2})}\lesssim_\delta N^{-A} ∥ R ( x ) ∥ L ∞ ( B N 2 ) ≲ δ N − A as desired.
We now provide a proof of the estimate (26), as a consequence for the following two lemmas.
Proposition 17. We have the uniform bound
sup f ∈ F ∑ k = 1 C N 4 ∣ D ( α ) f ( y k l ) ∣ ≲ ϵ N 9 / 2 \sup_{f\in\mathcal{F}}\sum_{k=1}^{CN^4}|D^{(\alpha)}f(y_{kl})|\lesssim_\epsilon N^{9/2} f ∈ F sup k = 1 ∑ C N 4 ∣ D ( α ) f ( y k l ) ∣ ≲ ϵ N 9/2 For each f ∈ F f\in\mathcal{F} f ∈ F , we write D ( α ) f ( y k l ) = ∫ f ( x ) η ( α ) ( x − y k l ) d x D^{(\alpha)}f(y_{kl})=\int f(x)\eta^{(\alpha)}(x-y_{kl})\,dx D ( α ) f ( y k l ) = ∫ f ( x ) η ( α ) ( x − y k l ) d x . As a consequence, for every f ∈ F f\in\mathcal{F} f ∈ F we have that
∑ k = 1 C N 4 ∣ D ( α ) f ( y k l ) ∣ ≤ ∫ R 2 ∣ f ( x ) ∣ ⋅ ( ∑ k = 1 C N 4 ∣ η ( α ) ( x − y k l ) ∣ ) d x . \sum_{k=1}^{CN^4}|D^{(\alpha)}f(y_{kl})|\le\int_{\mathbb{R}^2}|f(x)|\cdot\left(\sum_{k=1}^{CN^4}|\eta^{(\alpha)}(x-y_{kl})|\right)dx. k = 1 ∑ C N 4 ∣ D ( α ) f ( y k l ) ∣ ≤ ∫ R 2 ∣ f ( x ) ∣ ⋅ k = 1 ∑ C N 4 ∣ η ( α ) ( x − y k l ) ∣ d x . We now estimate this integral based on the following two lemmas:
Lemma 18. The following point-wise bound holds: For each x ∈ B 2 N 2 x\in B_{2N^2} x ∈ B 2 N 2 , we have
∑ k = 1 C N 4 ∣ η ( α ) ( x − y k l ) ∣ ≲ 1. \sum_{k=1}^{CN^4}|\eta^{(\alpha)}(x-y_{kl})|\lesssim1. k = 1 ∑ C N 4 ∣ η ( α ) ( x − y k l ) ∣ ≲ 1. Proof. The Schwartz Decay of η ( α ) \eta^{(\alpha)} η ( α ) tells us that
∣ η ( α ) ( x − y k l ) ∣ ≤ C N dist ( x , y k l ) − N |\eta^{(\alpha)}(x-y_{kl})|\le C_N\operatorname{dist}(x,y_{kl})^{-N} ∣ η ( α ) ( x − y k l ) ∣ ≤ C N dist ( x , y k l ) − N for some N N N to be chosen later. Define for integers j ≥ 1 j\ge1 j ≥ 1 ,
C j = { y k l : 2 j − 1 < dist ( y k l , x ) ≤ 2 j } , C_j=\{y_{kl}:2^{j-1}<\operatorname{dist}(y_{kl},x)\le2^j\}, C j = { y k l : 2 j − 1 < dist ( y k l , x ) ≤ 2 j } , and
C 0 = { y k l : dist ( y k l , x ) ≤ 2 0 } . C_0=\{y_{kl}:\operatorname{dist}(y_{kl},x)\le2^0\}. C 0 = { y k l : dist ( y k l , x ) ≤ 2 0 } .
Since the set { y k l } \{y_{kl}\} { y k l } is a 1 1 1 -separated set, we have that ∣ C j ∣ ≲ 2 j |C_j|\lesssim2^j ∣ C j ∣ ≲ 2 j , then for any N ≥ 3 N\ge3 N ≥ 3 ,
∑ k = 1 C N 4 ∣ η ( α ) ( x − y k l ) ∣ ≲ ∑ j = 0 ∞ C N dist ( x , y k l ) − N ∣ C j ∣ \sum_{k=1}^{CN^4} \left|\eta^{(\alpha)}(x-y_{kl})\right| \lesssim\sum_{j=0}^{\infty} C_N \operatorname{dist}(x,y_{kl})^{-N}|C_j| k = 1 ∑ C N 4 η ( α ) ( x − y k l ) ≲ j = 0 ∑ ∞ C N dist ( x , y k l ) − N ∣ C j ∣
≲ ∑ j = 0 ∞ 2 j 2 − N ( j − 1 ) \lesssim\sum_{j=0}^{\infty} 2^j 2^{-N(j-1)} ≲ j = 0 ∑ ∞ 2 j 2 − N ( j − 1 )
Lemma 19. We have
sup f ∈ F ∥ f ∥ L 1 ( B N 2 ) ≲ ϵ N 9 / 2 + ϵ . \sup_{f\in\mathcal{F}}\|f\|_{L^1(B_{N^2})}\lesssim_{\epsilon} N^{9/2+\epsilon}. f ∈ F sup ∥ f ∥ L 1 ( B N 2 ) ≲ ϵ N 9/2 + ϵ . Proof. For every f ∈ F f\in\mathcal{F} f ∈ F , using the superlevel set bound (3) , we have that
∥ f ∥ L 1 ( B N 2 ) ∼ ∫ 0 N 2 ∣ { x ∈ B N 2 : ∣ f ( x ) ∣ > λ } ∣ d λ \|f\|_{L^1(B_{N^2})}\sim\int_0^{N^2}\left|\{x\in B_{N^2}:|f(x)|>\lambda\}\right|d\lambda ∥ f ∥ L 1 ( B N 2 ) ∼ ∫ 0 N 2 ∣ { x ∈ B N 2 : ∣ f ( x ) ∣ > λ } ∣ d λ ∼ ∫ 0 N 1 / 2 ∣ { x ∈ B N 2 : ∣ f ( x ) ∣ > λ } ∣ d λ + ∫ N 1 / 2 N 2 ∣ { x ∈ B N 2 : ∣ f ( x ) ∣ > λ } ∣ d λ \sim\int_0^{N^{1/2}}\left|\{x\in B_{N^2}:|f(x)|>\lambda\}\right|d\lambda+\int_{N^{1/2}}^{N^2}\left|\{x\in B_{N^2}:|f(x)|>\lambda\}\right|d\lambda ∼ ∫ 0 N 1/2 ∣ { x ∈ B N 2 : ∣ f ( x ) ∣ > λ } ∣ d λ + ∫ N 1/2 N 2 ∣ { x ∈ B N 2 : ∣ f ( x ) ∣ > λ } ∣ d λ ≲ ϵ N 1 / 2 ( N 4 ) + N ϵ ∫ N 1 / 2 N 2 N 7 λ 6 d λ \lesssim_{\epsilon} N^{1/2}(N^4)+N^{\epsilon}\int_{N^{1/2}}^{N^2}\frac{N^7}{\lambda^6}\,d\lambda ≲ ϵ N 1/2 ( N 4 ) + N ϵ ∫ N 1/2 N 2 λ 6 N 7 d λ ∼ ϵ N 9 / 2 + ϵ . \sim_{\epsilon} N^{9/2+\epsilon}. ∼ ϵ N 9/2 + ϵ .
Probability Background
We give some basic background on the theory behind estimating the suprema of Rademacher processes. These results are well known, and we provide them here for the reader who may not have much of a background in probability. For more background, we refer the reader to the excellent references [23 ] , [20 ] , and [22 ] .
Let ( ϵ i ) i = 1 n (\epsilon_i)_{i=1}^{n} ( ϵ i ) i = 1 n be an i.i.d. collection of Rademacher random variables, and suppose T ⊆ C n T \subseteq\mathbb{C}^{n} T ⊆ C n . We are interested in the quantity
E sup t ∈ T ∣ ∑ i = 1 n ϵ i t i ∣ , t = ( t 1 , t 2 , … , t n ) . (59) \mathbb{E}\sup_{t \in T}\left|\sum_{i=1}^{n}\epsilon_i t_i\right|,\qquad t=(t_1,t_2,\ldots,t_n). \tag*{(59)} E t ∈ T sup i = 1 ∑ n ϵ i t i , t = ( t 1 , t 2 , … , t n ) . (59)
A way to find an upper bound for the quantity (59) is to use Dudley’s inequality. For any s , t ∈ T s,t \in T s , t ∈ T , define the canonical distance between s s s and t t t as follows:
d ( s , t ) ≔ ( ∑ i = 1 n ∣ s i − t i ∣ 2 ) 1 / 2 . d(s,t)\coloneqq\left(\sum_{i=1}^{n}|s_i-t_i|^2\right)^{1/2}. d ( s , t ) : = ( i = 1 ∑ n ∣ s i − t i ∣ 2 ) 1/2 .
Proposition 20 (Dudley’s inequality). We have the following inequality
E sup t ∈ T ∣ ∑ i = 1 n ϵ i t i ∣ ≲ ∫ 0 ∞ log N ( T , d , ϵ ) d ϵ . (60) \mathbb{E}\sup_{t \in T}\left|\sum_{i=1}^{n}\epsilon_i t_i\right|\lesssim\int_{0}^{\infty}\sqrt{\log\mathcal{N}(T,d,\epsilon)}\,d\epsilon. \tag*{(60)} E t ∈ T sup i = 1 ∑ n ϵ i t i ≲ ∫ 0 ∞ log N ( T , d , ϵ ) d ϵ . (60)
Dudley’s inequality is proved using the chaining method and we refer the reader to [23 ] for a self contained proof.
Another tool we need is the contraction principle for Rademacher processes.
Theorem 21 (Contraction Principle). For any T ⊆ C n T \subseteq\mathbb{C}^{n} T ⊆ C n the following always holds
E sup t ∈ T ∣ ∑ i = 1 n ϵ i ∣ t i ∣ ∣ ≲ E sup t ∈ T ∣ ∑ i = 1 n ϵ i t i ∣ . \mathbb{E}\sup_{t \in T}\left|\sum_{i=1}^{n}\epsilon_i|t_i|\right|\lesssim\mathbb{E}\sup_{t \in T}\left|\sum_{i=1}^{n}\epsilon_i t_i\right|. E t ∈ T sup i = 1 ∑ n ϵ i ∣ t i ∣ ≲ E t ∈ T sup i = 1 ∑ n ϵ i t i .
The intuition behind this theorem is that if the ∣ t i ∣ |t_i| ∣ t i ∣ ’s are all positive then the left hand side of the above equation could have cancellations due to the oscillatory nature of the ϵ k \epsilon_k ϵ k ’s. The right hand side gets rid of the positivity of the ∣ t i ∣ |t_i| ∣ t i ∣ ’s and therefore is a larger quantity. For a proof see [22 Exercise 7.4] .
Proof of Proposition 12. For the process
E sup f ∈ F θ ∣ ∑ k ∈ S ϵ k D ( α ) f ( y k l ) ∣ , \mathbb{E}\sup_{f\in\mathcal{F}_{\theta}}\left|\sum_{k\in S}\epsilon_k D^{(\alpha)}f(y_{kl})\right|, E f ∈ F θ sup k ∈ S ∑ ϵ k D ( α ) f ( y k l ) ,
the canonical metric is
d ( f , g ) = ( ∑ k ∈ S ∣ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) ∣ 2 ) 1 / 2 . d(f,g)=\left(\sum_{k\in S}\left|D^{(\alpha)}f(y_{kl})-D^{(\alpha)}g(y_{kl})\right|^2\right)^{1/2}. d ( f , g ) = ( k ∈ S ∑ D ( α ) f ( y k l ) − D ( α ) g ( y k l ) 2 ) 1/2 .
An application of Dudley’s inequality (60) precisely gives the statement of Proposition 12.
Department of Mathematics, University of California, Los Angeles, USA
Email address: sidmulherkar@g.ucla.edu