July 11, 2026
We prove an optimal extrapolation theorem for \(k\)-sparse Fourier sums over arbitrary real frequencies, without any separation assumption, bounding how large such a sum can be just outside an interval on which its energy is observed. For every \(g(t)=\sum_{j=1}^k v_j e^{i\lambda_jt}\) with \(\lambda_j\in\mathbb{R}\) and every \(x\ge1\), \[|g(x)|\le k^{O(1)}\exp(O(k\operatorname{arcosh}x))\|g\|_{L^2[-1,1]} .\] In the endpoint regime, this refines to the explicit bound \[|g(1+\delta)|\le O(k)\exp(O(k\sqrt\delta))\|g\|_{L^2[-1,1]}, \qquad 0\le\delta\le1 .\] This improves on the \(\exp(O(k^2\log k\cdot\delta))\) growth estimate of Chen and Price (ICALP 2019), and the exponential scaling is optimal up to constants and polynomial factors in \(k\).
As an algorithmic consequence, we improve the cluster-center resolution of Chen–Price’s clustered-frequency recovery algorithm by a factor of \(k\), while preserving its sample complexity up to logarithmic factors. We also obtain exterior leverage-score and transfer bounds for sparse Fourier feature spaces, converting in-domain active-regression guarantees into essentially sharp prediction guarantees just outside the sampling interval.
A signal with only \(k\) significant spectral components admits a concise representation as a superposition of \(k\) complex exponentials, and exploiting this structure is a central theme in sparse Fourier algorithms. In the discrete setting, Fourier sparsity enables sublinear-time algorithms for identifying and estimating the dominant Fourier coefficients [1]–[7]. In the continuous, off-grid setting, where the frequencies may be arbitrary real numbers, it underlies sparse Fourier recovery and interpolation algorithms [8]–[11]; closely related super-resolution problems ask to recover sparse point sources from bandlimited measurements [12]–[18].
A central difficulty in the continuous setting is the absence of a frequency gap. When several frequencies are closer than the inverse length of the observation window, the corresponding exponential atoms become nearly linearly dependent: the associated Fourier–Vandermonde systems become ill-conditioned, and the individual frequencies may no longer be stably identifiable. In the limiting case of a \(k\)-fold frequency collision, suitably rescaled finite differences of the exponential atoms converge to \(\{1,t,\ldots,t^{k-1}\}\), so the clustered Fourier model approaches the space of algebraic polynomials of degree at most \(k-1\). In this regime, the natural algorithmic goal is not to recover the individual frequencies but to reconstruct the entire signal with \(L^2\)-error guarantees [9], [11], [19], or to estimate the location of the frequency cluster [10].
In this paper, we study a deterministic extrapolation problem that underlies this clustered regime. Let \[g(t)=\sum_{j=1}^k v_j e^{i\lambda_jt}, \qquad \lambda_j\in\mathbb{R},\] be a \(k\)-Fourier-sparse signal whose \(L^2\)-energy is known on \([-1,1]\). Consider the following natural question:
How large can \(g\) become at a point \(x>1\) outside the observation interval?
Chen and Price [10] introduced an outside-window growth estimate as a key ingredient in their algorithm for locating the center of a clustered Fourier signal. In the edge regime \(x=1+\delta\), their Lemma 8.5 gives, in our notation, \[\label{eq:cp19} |g(1+\delta)| \le \operatorname{poly}(k) \exp\!\left(O(k^2\log k\cdot\delta)\right) \|g\|_{L^2[-1,1]} .\tag{1}\] Their proof first derives a linear recurrence involving \(d=O(k^2\log k)\) shifted values of the signal. It then propagates the estimate across steps of length \(\Theta(1/d)\), paying a constant multiplicative loss at each step. Reaching distance \(\delta\) therefore requires \(O(d\delta)\) propagation steps, which produces the exponent in 1 .
The same frequency-collision picture, however, suggests that this exponent is not tight. As the frequencies coalesce, \(k\)-term exponential sums approach degree-\((k-1)\) polynomials, and among such polynomials the classical extremal example for growth outside \([-1,1]\) is the Chebyshev polynomial: \[T_{k-1}(1+\delta) = \cosh\!\left( (k-1)\operatorname{arcosh}(1+\delta) \right).\] Since \[\operatorname{arcosh}(1+\delta)=\Theta\big(\sqrt{\delta}\big), \qquad 0\leq\delta\leq1\,,\] this example exhibits outside-growth on the scale \[\exp\!\left(\Theta(k\sqrt{\delta})\right)\,,\] that is, an edge exponent of \(k\sqrt{\delta}\) in place of \(k^2\log k \cdot \delta\). Chen and Price highlighted this discrepancy in [10], leaving open whether arbitrary \(k\)-term Fourier sums obey the same Chebyshev-scale bound.
We answer this question affirmatively by proving a sharp extrapolation bound for arbitrary real frequencies, with no separation, bounded-bandwidth, or cluster-structure assumption.
Theorem 1 (Chebyshev-scale extrapolation inequality). For every \[g(t)=\sum_{j=1}^k v_j e^{i\lambda_jt},\qquad \lambda_j\in\mathbb{R},\] and every \(x\ge1\), \[\label{eq:main-global} |g(x)|\lesssim k^2\exp\left(3\sqrt2\,k\operatorname{arcosh}x\right)\|g\|_{L^2[-1,1]}\,.\qquad{(1)}\] Moreover, for \(0\le\delta\le1\), \[\label{eq:main-edge} |g(1+\delta)|\lesssim k\exp\left(3\sqrt2\,k\sqrt\delta\right)\|g\|_{L^2[-1,1]}\,.\qquad{(2)}\] The exponential dependence is optimal up to absolute constants and polynomial factors in \(k\).
The main algorithmic consequence is a new filtering primitive for clustered Fourier signals. Chen and Price encode outside-window growth by a power-law parameter \(S\) and design a filter whose decay compensates for that power law [10]. For sparse Fourier sums, Theorem 1 shows that the intrinsic growth profile is instead \[\exp\!\left(O\!\left(k\operatorname{arcosh}\frac{|t|}{T}\right)\right)\,,\] with the endpoint form \(\exp\left(O(k\sqrt\delta)\right)\) at \(|t|=T(1+\delta)\). In Section 8.1, we construct a bandlimited window directly against this Chebyshev envelope: \[\operatorname{supp}\widehat H_{k,T} \subseteq[-O_\eta(k^2/T),O_\eta(k^2/T)]\] and \[\int_{-T}^{T}|1-H_{k,T}|^2|g|^2 +\int_{\mathbb{R}\setminus[-T,T]}|H_{k,T}|^2|g|^2 \le \eta\int_{-T}^{T}|g|^2 \qquad(g\in\mathcal{T}_k)\,.\] Thus the power-law parameter \(S\) is unnecessary for the sparse-Fourier class. Substituting this filter into the nonuniform-sampling algorithm in [10] improves the additive cluster-center resolution from \[\Delta+\widetilde{O}(k^3/T) \qquad\text{to}\qquad \Delta+O(k^2/T),\] while preserving its sample complexity up to the logarithmic factors already present in their theorem. The second application concerns extrapolative active regression. Labels are acquired on the training interval \([-1,1]\), while the learned sparse Fourier model is evaluated on the adjacent exterior region \[\mathcal{X}_\Delta := [1,1+\Delta]\cup[-1-\Delta,-1].\] This is a structured covariate-shift problem: the test points lie outside the support of the training distribution, but the regression function remains in the same sparse Fourier model class. In Section 8.2, we reinterpret Theorem 1 as a frequency-uniform exterior bound on the statistical leverage scores of Fourier feature spaces. We then distinguish the integral of these pointwise leverage scores from the actual worst-case \(L^2\) transfer constant from \([-1,1]\) to \(\mathcal{X}_\Delta\), and bound both quantities. In the nontrivial regime \(k^{-2}\lesssim\Delta\leq1\), the true transfer constant has exponential scale \[\exp\!\left(\Theta(k\sqrt{\Delta})\right)\] up to polynomial factors. Consequently, any in-domain active-regression error guarantee transfers directly to an \(L^2\)-prediction guarantee on \(\mathcal{X}_\Delta\), with polynomial overhead when \(k\sqrt{\Delta}=O(\log k)\). A single confluent Chebyshev construction gives the matching lower bound, showing that this extrapolation range is essentially sharp for any black-box implication based only on the in-domain \(L^2\) error.
We first discuss two straightforward approaches (local propagation argument and Remez/Turán inequalities) and explain why they fail. Then, we introduce our techniques and the outline of our proof for the main result.
A basic endpoint Nikolskii inequality says that a \(k\)-term exponential sum on an interval cannot put more than an \(O(k^2)\) fraction of its \(L^2\)-energy at a single endpoint. In the normalization used later, one such form is \[|g(1)|^2\le O(k^2)\int_{-1}^{1}|g(t)|^2dt .\] This inequality is classical in the theory of exponential sums; we use the Denisov–Erdelyi form (Lemma 2), and related peak-to-average estimates go back to Turan-type and Nikolskii-type inequalities for exponential sums [20]–[23]. It immediately yields a local propagation argument. Let \[E(s)=\int_{-1+s}^{1+s}|g(t)|^2dt .\] Then \(E'(s)=|g(1+s)|^2-|g(-1+s)|^2\le |g(1+s)|^2\), and the endpoint inequality applied on the shifted interval gives \(E'(s)\le O(k^2)E(s)\). Gronwall’s inequality gives \(E(\delta)\le e^{O(k^2\delta)}E(0)\), and hence \(e^{O(k^2\delta)}\) pointwise growth. This improves the logarithmic local-propagation loss in earlier sparse-Fourier analyses, but it still misses the Chebyshev edge scale \(e^{O(k\sqrt\delta)}\) when \(k^{-2}\ll\delta\ll1\).
A Remez-type inequality is a propagation-of-smallness statement: if a low-complexity function is small on a measurable subset \(E\) of an interval \(I\), how large can it be on the rest of \(I\)? For real algebraic polynomials of degree at most \(k-1\), the sharp answer is given by the classical Remez inequality \[\label{eq:poly-remez-overview} \|p\|_{L^\infty(I)} \le T_{k-1}\!\left(\frac{2|I|}{|E|}-1\right) \|p\|_{L^\infty(E)}\,,\tag{2}\] where \(|\cdot|\) denotes Lebesgue measure and \(T_{k-1}\) is the Chebyshev polynomial of the first kind; see, e.g., [24]. In our endpoint geometry, \[E=[-1,1], \qquad I=[-1,1+\delta]\,,\] so 2 becomes \[\|p\|_{L^\infty[-1,1+\delta]} \le T_{k-1}(1+\delta) \|p\|_{L^\infty[-1,1]}\,.\] Thus the sharp polynomial Remez inequality already exhibits the desired Chebyshev behavior: \[T_{k-1}(1+\delta) = \cosh\!\left((k-1)\operatorname{arcosh}(1+\delta)\right)\,,\] whose exponential scale near the endpoint is \(\exp\left(\Theta(k\sqrt{\delta})\right)\).
For a \(k\)-Fourier sparse signal \[g(t)=\sum_{j=1}^{k}v_j e^{i\lambda_jt}\,,\] the standard measurable Turán–Nazarov inequality gives the more generic bound \[\label{eq:TN-overview} \|g\|_{L^\infty(I)} \le \left(A\frac{|I|}{|E|}\right)^{k-1} \|g\|_{L^\infty(E)}\,,\tag{3}\] where \(A>1\) is an absolute constant [24], [25]. Applying 3 to the same intervals and then using the endpoint Nikolskii inequality above yields only \[\begin{align} |g(1+\delta)| \le &~ O(k) \left(A\left(1+\frac{\delta}{2}\right)\right)^{k-1} \|g\|_{L^2[-1,1]} \\ = &~ k^{O(1)} \exp\!\left((k-1)\log A+O(k\delta)\right) \|g\|_{L^2[-1,1]} \,. \end{align}\] In the outer regime when \(x\geq 2\), the fixed factor \(A^{k-1}=\exp\left(\Theta(k)\right)\) is harmless because then \(k\operatorname{arcosh}x=\Omega(k)\). However, near the endpoint, \(\delta=o(1)\) and the target \[\exp\left(O\bigl(k\sqrt{\delta}\bigl)\right)\] can be subexponential in \(k\). Hence the black-box Turán–Nazarov estimate loses precisely the endpoint information that is needed here. Our proof recovers that information by exploiting the one-sided weighted geometry of the problem, rather than reducing it only to the measure ratio \(|I|/|E|\).
The key step of our proof is to convert endpoint extrapolation into a one-sided weighted problem. Let \(F(u):=g(1-u)\). Then, \(g(1+\delta)=F(-\delta)\), while the known energy on \([-1,1]\) becomes energy of \(F\) on \([0,2]\). We compare this finite interval to the weighted half-line norm: \[\int_0^\infty |F(u)|^2e^{-\alpha u}du \,.\] After absorbing the weight by writing \(H(u)=e^{-\alpha u/2}F(u)\), the relevant functions are finite sums of decaying exponentials \[H(u)=\sum_j a_j e^{-(\alpha/2-i\lambda_j)u}\,,\] where all exponents now lie on the vertical line \(\operatorname{Re}z=\alpha/2\) in the right half-plane \(\mathbb{C}_+\).
Then, we consider the Hardy space \(H^2(\mathbb{C}_+)\) realized as the image of the Laplace transform of \(L^2(0,\infty)\). In that space, the functions \(e^{-(\alpha/2-i\lambda_j)u}\) become reproducing kernels at points on a vertical line. Gram–Schmidt of such kernels is explicit: it is the Takenaka–Malmquist basis. In Lemma 4, we prove that the Laplace transform of the \(m\)-th basis vector \(\phi_m\) is \[\frac{\sqrt\alpha}{s+\zeta_m}\prod_{\ell<m}\frac{s-\overline{\zeta_\ell}}{s+\zeta_\ell}, \qquad \text{where }\zeta_j=\alpha/2-i\lambda_j ~~~\forall j\in [k].\] The factors \((s-\overline{\zeta})/(s+\zeta)\) are inner functions: on the boundary \(s=i\omega\), they have modulus one. Thus multiplying by them preserves the Hardy, equivalently \(L^2(0,\infty)\), norm. This basis gives a stable way to write the point-evaluation norm at \(-\delta\) without inverting a possibly ill-conditioned Vandermonde matrix.
We can expand \(H(u)\) in this orthonormal basis: \[\begin{align} H = \sum_{m=0}^{k-1} \langle H,\phi_m\rangle \phi_m\,. \end{align}\] To bound \(|H(u)|\) at the endpoint window, we need to evaluate the basis functions at negative points. In the time domain, multiplication by the inner factor \((s-\overline{\zeta})/(s+\zeta)\) is the Volterra operator \[(T_\zeta h)(t)=h(t)-\alpha\int_0^t e^{-\zeta(t-u)}h(u)du .\] At \(t=-r\) the sign reverses, giving \[|(T_\zeta h)(-r)|\le |h(-r)|+ \alpha\int_0^r e^{\alpha(r-s)/2}|h(-s)|ds .\] Iterating this inequality through the Takenaka–Malmquist construction yields the frequency-independent majorant (Lemma 5): \[|\phi_m(-r)|\le \sqrt\alpha\,e^{\alpha r/2}L_m(-\alpha r),\] where \(L_m\) is a Laguerre polynomial. Using the algebraic fact that \(L_m(-y)\le e^{2\sqrt{my}}\) for all \(y\geq 0\) gives the desired square-root exponent.
The remaining step is to relate the weighted half-line norm back to the observed interval \([0,2]\). Erdelyi’s infinite–finite range inequality (Lemma 3) says that for a \(k\)-Fourier sparse \(F\), \[\int_0^\infty |F(u)|^2e^{-\alpha u}du \le O(1)\int_0^{9k/\alpha}|F(u)|^2e^{-\alpha u}du \,.\] Choosing \(\alpha=9k/2\) makes \(9k/\alpha=2\), so the right-hand side is controlled by the original energy on \([0,2]\). Combining this choice with the Laguerre estimate gives \[\exp\left(O(\sqrt{k\alpha\delta})\right)=\exp\left(O(k\sqrt\delta)\right)\,.\] This proves the endpoint bound.
For \(x\ge2\), we use a separate coefficient-explicit Turán extrapolation (Proposition 9). We place \(k\) grid points inside \([-1,1]\), express \(g(x)\) as a controlled linear combination of those values, and then use the endpoint Nikolskii inequality (Lemma 2) to pass from \(L^\infty\) to \(L^2\). The resulting growth is \((x+1)^{O(k)}=e^{O(k\operatorname{arcosh}x)}\), which is sharp away from the endpoint. Optimality is shown by the confluent construction \[T_{k-1}\!\left(\frac{e^{i\varepsilon t}-1}{i\varepsilon}\right)\to T_{k-1}(t),\] which realizes Chebyshev growth as a limit of \(k\)-sparse Fourier sums.
Section 2 collects the notation and analytic preliminaries used throughout the paper. Sections 3 and 4 together establish the extrapolation bound in the endpoint window \(1\leq x\leq2\). Section 5 treats the outer regime \(x\geq2\). Section 6 combines the two regimes to prove the main theorem. Section 7 proves the matching lower bound. Section 8 discusses the two algorithmic applications.
For \(k\ge1\), let \[\label{eq:Tk-def} \mathcal{T}_k:=\Bigl\{F(t)=\sum_{j=1}^k a_j e^{i\lambda_j t}: a_j\in\mathbb{C},\;\lambda_j\in\mathbb{R}\Bigr\}\tag{4}\] denote the class of exponential sums with at most \(k\) terms. Repeated frequencies are always merged. We define the norms: \[\|h\|_{L^2(I)}:=\Bigl(\int_I|h(t)|^2dt\Bigr)^{1/2}, \qquad \|h\|_{L^\infty(I)}:=\sup_{t\in I}|h(t)|,\] and the averaged norm: \[\|h\|_{2,T}^2:=\mathbb{E}_{t\sim[-T,T]}\left[|h(t)|^2\right] :=\frac{1}{2T}\int_{-T}^{T}|h(t)|^2dt .\]
For \(x\ge1\), \[\operatorname{arcosh}x:=\log\bigl(x+\sqrt{x^2-1}\bigr).\] We shall use the following endpoint comparison.
Lemma 1 (Elementary \(\operatorname{arcosh}\) comparisons). For \(0\le\delta\le1\), \[\label{eq:arcosh-compare} \sqrt\delta\le \operatorname{arcosh}(1+\delta)\le \sqrt{2\delta}\le2\sqrt\delta .\qquad{(3)}\]
Proof. For the lower bound, \(\cosh y\le1+y^2\) for \(0\le y\le1\); setting \(y=\sqrt\delta\) gives \(\cosh\sqrt\delta\le1+\delta\), and monotonicity of \(\operatorname{arcosh}\) gives the claim. For the upper bound, \[\operatorname{arcosh}(1+\delta)=\int_1^{1+\delta}\frac{du}{\sqrt{u^2-1}} \le \int_0^\delta \frac{dv}{\sqrt v}=2\sqrt\delta,\] and the sharper \(\sqrt{2\delta}\) follows from \(\cosh y\ge1+y^2/2\) with \(y=\operatorname{arcosh}(1+\delta)\). ◻
Let \(\mathbb{C}_+=\{s\in\mathbb{C}:\operatorname{Re}s>0\}\). The Hardy space \(H^2(\mathbb{C}_+)\) is realized as the image of \(L^2(0,\infty)\) under the Laplace transform \[\mathcal{L}\left[h\right](s)=\int_0^\infty h(t)e^{-st}dt, \qquad \operatorname{Re}s>0,\] with boundary inner product \[\langle G_1,G_2\rangle_{H^2} =\frac{1}{2\pi}\int_{-\infty}^{\infty}G_1(i\omega)\overline{G_2(i\omega)}d\omega .\] We use the following standard facts.
Fact 2 (Paley–Wiener isometry [26]). The Laplace transform is an isometry from \(L^2(0,\infty)\) onto \(H^2(\mathbb{C}_+)\).
Fact 3 (Reproducing kernel of \(H^2(\mathbb{C}_+)\) [26]). For \(w\in\mathbb{C}_+\), the function \(k_w(s)=1/(s+\overline{w})\) belongs to \(H^2(\mathbb{C}_+)\) and satisfies \[\langle G,k_w\rangle_{H^2}=G(w), \qquad \|k_w\|_{H^2}^2=\frac{1}{2\operatorname{Re}w} .\]
Fact 4 (Inner multipliers [26], [27]). If \(\Theta\) is holomorphic on \(\mathbb{C}_+\), \(|\Theta|\le1\) there, and \(|\Theta(i\omega)|=1\) for a.e.\(\omega\in\mathbb{R}\), then multiplication by \(\Theta\) is an isometry of \(H^2(\mathbb{C}_+)\) into itself. Finite products of inner functions are inner.
The proof uses two inequalities of Erdelyi for pure-imaginary exponential sums. We state them in the normalizations used below.
Lemma 2 (Endpoint Nikolskii inequality [22]). For every \(F\in\mathcal{T}_k\), \[\label{eq:nik-01} \|F\|_{L^\infty[0,1]}\leq \frac{\pi k}{2}\,\|F\|_{L^2[0,1]}.\qquad{(4)}\] Consequently, for every \(g\in\mathcal{T}_k\), \[\label{eq:nik-11} \|g\|_{L^\infty[-1,1]}\leq \frac{\pi k}{2\sqrt2}\,\|g\|_{L^2[-1,1]}.\qquad{(5)}\]
Proof. Inequality ?? is the sharp Denisov form recorded by Erdelyi. For ?? , apply ?? to \(F(u)=g(2u-1)\). Then \(\|F\|_{L^\infty[0,1]}=\|g\|_{L^\infty[-1,1]}\) and \(\|F\|_{L^2[0,1]}=2^{-1/2}\|g\|_{L^2[-1,1]}\). ◻
Lemma 3 (Weighted infinite–finite range inequality [22]). For every \(F\in\mathcal{T}_k\) and every \(\alpha>0\), \[\label{eq:finite-range} \int_0^\infty |F(u)|^2e^{-\alpha u}du \le A_{\mathrm{fr}}\int_0^{9k/\alpha}|F(u)|^2e^{-\alpha u}du,\qquad{(6)}\] where one may take \(A_{\mathrm{fr}}=8191\).
Proof. For \(\alpha=1\), this is Erdelyi’s infinite–finite range inequality, stated for \(E_k^-\) and hence in particular for \(\mathcal{T}_k\), with constant \(1+8190e^{-k/10}\le8191\). For general \(\alpha\), apply the \(\alpha=1\) statement to \(H(t)=F(t/\alpha)\) and change variables. ◻
For an integer \(m\geq0\), let \(L_m\) denote the ordinary Laguerre polynomial, \[\label{eq:laguerre-def} L_m(y)=\sum_{\ell=0}^m\binom{m}{\ell}\frac{(-y)^\ell}{\ell!},\tag{5}\] so that, for \(y\geq0\), \[\label{eq:laguerre-neg} L_m(-y)=\sum_{\ell=0}^m\binom{m}{\ell}\frac{y^\ell}{\ell!}\;\geq\;1.\tag{6}\] The key endpoint estimate is the following.
Theorem 5 (Laguerre half-line comparison). Let \(F\in\mathcal{T}_k\), let \(\alpha>0\), and let \(r\geq0\). Then \(F\) extends to an entire function1, and \[\label{eq:halfline} |F(-r)|^2\leq \alpha\sum_{m=0}^{k-1}L_m(-\alpha r)^2\int_0^\infty|F(u)|^2e^{-\alpha u}\,du.\qquad{(7)}\]
We prove Theorem 5 in the rest of this section, using the Hardy-space notation and facts collected in Section 2.
Lemma 4 (Takenaka–Malmquist basis on a vertical line [28], [29]; cf.[27], [30]). Fix \(\alpha>0\) and distinct* real numbers \(\lambda_0,\ldots,\lambda_{d-1}\), and set \[\zeta_j=\frac{\alpha}{2}-i\lambda_j,\qquad 0\leq j\leq d-1.\] Then the \(d\)-dimensional subspace \[\mathcal{S}=\operatorname{span}\{e^{-\zeta_jt}:0\leq j\leq d-1\}\subset L^2(0,\infty)\] has an orthonormal basis \(\phi_0,\ldots,\phi_{d-1}\) whose Laplace transforms are \[\label{eq:TM-formula} \mathcal{L}\left[\phi_m\right](s)=\frac{\sqrt\alpha}{s+\zeta_m}\prod_{\ell=0}^{m-1}B_\ell(s), \qquad B_\ell(s):=\frac{s-\overline{\zeta_\ell}}{s+\zeta_\ell}, \qquad 0\leq m\leq d-1.\tag{7}\] Moreover each \(\phi_m\) lies in \(\operatorname{span}\{e^{-\zeta_\ell t}:0\leq\ell\leq m\}\), with a nonzero coefficient on \(e^{-\zeta_mt}\).*
Proof. First note that each \(e^{-\zeta_jt}\) lies in \(L^2(0,\infty)\) because \(\operatorname{Re}\zeta_j=\alpha/2>0\), and that exponentials with distinct exponents are linearly independent, so \(\dim\mathcal{S}=d\).
Next, we show that \(\{\phi_m\}\) form an orthonormal basis.
The Blaschke factors \(B_\ell\) are inner. Each \(B_\ell\) is a Möbius transformation whose only pole, \(-\zeta_\ell\), lies in the closed left half-plane, so \(B_\ell\) is holomorphic on \(\mathbb{C}_+\). On the boundary \(s=i\omega\), writing \(\zeta_\ell=\alpha/2-i\lambda_\ell\), \[|i\omega-\overline{\zeta_\ell}|=\Bigl|-\frac{\alpha}{2}+i(\omega-\lambda_\ell)\Bigr| =\Bigl|\frac{\alpha}{2}+i(\omega-\lambda_\ell)\Bigr|=|i\omega+\zeta_\ell|,\] so \(|B_\ell(i\omega)|=1\); by the maximum principle \(|B_\ell|\leq1\) on \(\mathbb{C}_+\). Hence \(B_\ell\), and every product of the \(B_\ell\)’s, is inner in the sense of Fact 4.
Unit norms. Apply Fact 3 with \(w=\overline{\zeta_m}\), so that \(\overline{w}=\zeta_m\) and \(2\operatorname{Re}w=\alpha\): the factor \(\sqrt\alpha/(s+\zeta_m)=\sqrt{2\operatorname{Re}w}\,k_w(s)\) is the normalized reproducing kernel at \(\overline{\zeta_m}\) and has norm \(1\). Since the prefactor \(\prod_{\ell<m}B_\ell\) is inner, Fact 4 gives \(\|\mathcal{L}\left[\phi_m\right]\|=1\). Thus, by Fact 2, \(\|\phi_m\|_{L^2(0,\infty)}=1\).
Orthogonality. Let \(m<n\) and write \[\begin{align} \mathcal{L}\left[\phi_n\right]&=\Theta\,B_m\Psi, & \mathcal{L}\left[\phi_m\right]&=\Theta\,\kappa_m,\\ \Theta&=\prod_{\ell=0}^{m-1}B_\ell, & \kappa_m(s)&=\frac{\sqrt\alpha}{s+\zeta_m}, & \Psi&=\Bigl(\prod_{\ell=m+1}^{n-1}B_\ell\Bigr)\kappa_n . \end{align}\] Here \(\Psi\in H^2(\mathbb{C}_+)\), being a bounded holomorphic multiple of \(\kappa_n\in H^2(\mathbb{C}_+)\). By Fact 4 the common inner factor \(\Theta\) cancels, and then the reproducing property (Fact 3) at \(w=\overline{\zeta_m}\) applies: \[\langle\mathcal{L}\left[\phi_n\right],\mathcal{L}\left[\phi_m\right]\rangle =\langle B_m\Psi,\kappa_m\rangle =\sqrt\alpha\,\bigl(B_m\Psi\bigr)\bigl(\overline{\zeta_m}\bigr)=0,\] because \(B_m(\overline{\zeta_m})=\dfrac{\overline{\zeta_m}-\overline{\zeta_m}} {\overline{\zeta_m}+\zeta_m}=0\). Thus, \(\{\phi_m\}_{m=0}^{d-1}\) are orthonormal in \(L^2(0,\infty)\).
Triangularity and spanning. The rational function 7 is proper (degree of denominator exceeds degree of numerator) with simple poles at the distinct points \(-\zeta_0,\ldots,-\zeta_m\). By partial-fraction expansion, we have \[\mathcal{L}\left[\phi_m\right](s)=\sqrt{\alpha}\frac{\prod_{\ell=0}^{m-1}(s-\overline{\zeta_\ell})}{\prod_{\ell=0}^{m}(s+\zeta_\ell)}=\sum_{\ell=0}^m\frac{c_{m\ell}}{s+\zeta_\ell}\,.\] Since \(\mathcal{L}\left[e^{-\zeta_\ell t}\right]=1/(s+\zeta_\ell)\), we get that \[\begin{align} \phi_m(t)=\sum_{\ell=0}^m c_{m\ell}\,e^{-\zeta_\ell t}\in \mathrm{span}\{e^{-\zeta_0t},\dots,e^{-\zeta_m t}\}\,. \end{align}\] Moreover, the coefficient \(c_{mm}\) is nonzero: \[c_{mm}=\lim_{s\to-\zeta_m}(s+\zeta_m)\mathcal{L}\left[\phi_m\right](s) =\sqrt\alpha\prod_{\ell=0}^{m-1}\frac{-\zeta_m-\overline{\zeta_\ell}}{-\zeta_m+\zeta_\ell} =\sqrt\alpha\prod_{\ell=0}^{m-1}\frac{-\alpha+i(\lambda_m-\lambda_\ell)}{i(\lambda_m-\lambda_\ell)}\ne 0\,,\] each factor being nonzero because its numerator has real part \(-\alpha\neq0\) and its denominator is nonzero by the distinctness of the \(\lambda_j\).
The lemma is then proved. ◻
The next lemma is the heart of the matter: at exterior points the basis functions grow at most like Laguerre polynomials, uniformly in the frequencies \(\lambda_0,\ldots,\lambda_{d-1}\).
Lemma 5 (Pointwise Laguerre majorant for the Takenaka–Malmquist basis). With the notation of Lemma 4, for every \(r\geq0\) and every \(0\leq m\leq d-1\), \[\label{eq:majorant} |\phi_m(-r)|\leq\sqrt\alpha\,e^{\alpha r/2}\,L_m(-\alpha r).\qquad{(8)}\]
Proof. We prove this lemma in the following steps:
Step 1: an integral operator realizing the inner factors. For \(\zeta\in\mathbb{C}\) with \(\operatorname{Re}\zeta=\alpha/2\), define, for entire \(h\), \[\label{eq:Tzeta} (T_\zeta h)(t)=h(t)-\alpha\int_0^te^{-\zeta(t-u)}h(u)\,du,\qquad t\in\mathbb{C},\tag{8}\] the integral being taken over the straight segment from \(0\) to \(t\). Then \(T_\zeta h\) is again entire, and \[\begin{align} T_\zeta h = h - \alpha \left(e^{-\zeta t}\mathbf{1}_{t\geq 0}\right) * h\,. \end{align}\] If \(h\in L^2(0,\infty)\), then \(T_\zeta h\) is also in \(L^2(0,\infty)\), and by the convolution theorem for the Laplace transform, \[\label{eq:Tzeta-symbol} \mathcal{L}\left[T_\zeta h\right](s)=\Bigl(1-\frac{\alpha}{s+\zeta}\Bigr)\mathcal{L}\left[h\right](s) =\frac{s+\zeta-\alpha}{s+\zeta}\,\mathcal{L}\left[h\right](s) =\frac{s-\overline{\zeta}}{s+\zeta}\,\mathcal{L}\left[h\right](s)\,.\tag{9}\]
Step 2: factorization of \(\phi_m\). Let \(h_m(t)=\sqrt\alpha\,e^{-\zeta_mt}\), so that \(\mathcal{L}\left[h_m\right](s)=\sqrt\alpha/(s+\zeta_m)\). Applying 9 repeatedly, the entire function \[\psi_m:=T_{\zeta_0}T_{\zeta_1}\cdots T_{\zeta_{m-1}}h_m\] restricts to a function in \(L^2(0,\infty)\) whose Laplace transform is \[\begin{align} \mathcal{L}\left[\psi_m\right](s) = &~\frac{s-\overline{\zeta_0}}{s+\zeta_0}\mathcal{L}\left[ (T_{\zeta_1}\cdots T_{\zeta_{m-1}}h_m)\right](s)=\cdots \\ = &~ \prod_{\ell=0}^{m-1}\frac{s-\overline{\zeta_\ell}}{s+\zeta_\ell}\, \mathcal{L}\left[h_m\right](s) = \frac{\sqrt\alpha}{s+\zeta_m}\prod_{\ell=0}^{m-1}B_\ell(s)=\mathcal{L}\left[\phi_m\right](s)\,, \end{align}\] where each application of 9 is legitimate because, by Step 1, every intermediate function again lies in \(L^2(0,\infty)\). By injectivity of the Laplace transform, \(\psi_m=\phi_m\) almost everywhere on \((0,\infty)\); both being entire, the identity theorem gives \(\psi_m=\phi_m\) on all of \(\mathbb{C}\). Hence, \[\label{eq:phi-factorized} \phi_m=T_{\zeta_0}T_{\zeta_1}\cdots T_{\zeta_{m-1}}h_m\tag{10}\] as entire functions.
Step 3: induction on the number of factors. Define \[\phi_{m}^{(m)}:=h_m, \qquad \phi_m^{(m-q)}:=T_{\zeta_{m-q}}\cdots T_{\zeta_{m-1}}h_m, \qquad 1\leq q\leq m .\] We claim that for all \(0\leq q\leq m\) and \(r\geq0\), \[\label{eq:induction} \left|\phi_{m}^{(m-q)}(-r)\right|\leq\sqrt\alpha\,e^{\alpha r/2}P_q(r)\,,\tag{11}\] where \[\begin{align} P_0:=1,\quad P_{q+1}(r):=P_q(r)+\alpha\int_0^rP_q(s)\,ds\,. \end{align}\] We prove by induction. For \(q=0\) this holds with equality of the moduli: \[\begin{align} |h_m(-r)|=\sqrt\alpha\,|e^{\zeta_m r}| =\sqrt\alpha\,e^{r\operatorname{Re}\zeta_m}=\sqrt\alpha\,e^{\alpha r/2}\,. \end{align}\] Assume 11 holds for \(q-1\). Evaluating 8 at \(t=-r\) and substituting \(u=-s\) gives \[\phi_{m}^{(m-q)}(-r)=(T_{\zeta_{m-q}}\phi_m^{(m-q+1)})(-r)=\phi_m^{(m-q+1)}(-r)+\alpha\int_0^re^{\zeta_{m-q}(r-s)}\phi_m^{(m-q+1)}(-s)\,ds \,.\] Since \(\operatorname{Re}\zeta_{m-q}=\alpha/2\) and \(r-s\geq0\), we have \(|e^{\zeta_{m-q}(r-s)}|=e^{\alpha(r-s)/2}\). Thus, \[\begin{align} |\phi_{m}^{(m-q)}(-r)| \leq&~ |\phi_m^{(m-q+1)}(-r)| + \alpha \int_{0}^r |e^{\zeta_{m-q}(r-s)}|\cdot |\phi_m^{(m-q+1)}(-s)|\,ds\\ \leq &~ \sqrt\alpha\,e^{\alpha r/2}P_{q-1}(r) +\alpha\int_0^re^{\alpha(r-s)/2}\cdot\sqrt\alpha\,e^{\alpha s/2}P_{q-1}(s)\,ds\\ = &~ \sqrt\alpha\,e^{\alpha r/2}\Bigl(P_{q-1}(r)+\alpha\int_0^rP_{q-1}(s)\,ds\Bigr)\\ = &~ \sqrt\alpha\,e^{\alpha r/2} P_{q}(r)\,. \end{align}\] By induction, 11 holds for all \(0\leq q\leq m\).
Step 4: identification \(P_q(r)=L_q(-\alpha r)\). We verify by induction that \[\label{eq:Pq-formula} P_q(r)=\sum_{\ell=0}^q\binom{q}{\ell}\frac{(\alpha r)^\ell}{\ell!}.\tag{12}\] For \(q=0\) both sides equal \(1\). Assuming 12 , \[\begin{align} P_{q+1}(r) = &~ \sum_{\ell=0}^q\binom{q}{\ell}\frac{(\alpha r)^\ell}{\ell!} +\alpha\sum_{\ell=0}^q\binom{q}{\ell}\frac{\alpha^\ell}{\ell!}\cdot\frac{r^{\ell+1}}{\ell+1}\\ = &~ \sum_{\ell=0}^{q+1}\biggl[\binom{q}{\ell}+\binom{q}{\ell-1}\biggr]\frac{(\alpha r)^\ell}{\ell!}\\ = &~ \sum_{\ell=0}^{q+1}\binom{q+1}{\ell}\frac{(\alpha r)^\ell}{\ell!}\,, \end{align}\] where the second step uses the convention \(\binom{q}{-1}=\binom{q}{q+1}=0\), and the third step follows from Pascal’s rule. Comparing 12 with the definition of the Laguerre polynomial in 6 gives \(P_q(r)=L_q(-\alpha r)\).
Therefore, we obtain \[\begin{align} |\phi_m(-r)|=|\phi_m^{(m-m)}(-r)|\leq \sqrt\alpha\,e^{\alpha r/2}P_m(r) = \sqrt{\alpha}\,e^{\alpha r/2}L_m(-\alpha r)\quad \forall r\geq 0\,, \end{align}\] which completes the proof of the lemma. ◻
Proof of Theorem 5. We may assume that \[\begin{align} \int_0^\infty|F(u)|^2e^{-\alpha u}\,du<\infty\,, \end{align}\] since otherwise there is nothing to prove. We may also assume that \(F(t)=\sum_{j=0}^{k-1}a_je^{i\lambda_jt}\) with distinct frequencies \(\lambda_0,\ldots,\lambda_{k-1}\): merge repeated frequencies by adding their coefficients and, if fewer than \(k\) distinct frequencies remain, pad the representation with unused distinct frequencies carrying zero coefficients. Define \[H(u):=e^{-\alpha u/2}F(u)=\sum_{j=0}^{k-1}a_je^{-(\alpha/2-i\lambda_j)u} =\sum_{j=0}^{k-1}a_je^{-\zeta_ju},\] with \(\zeta_j:=\alpha/2-i\lambda_j\) as in Lemma 4. Thus \(H\) is an entire function whose restriction to \((0,\infty)\) lies in the space \(\mathcal{S}\) of Lemma 4, and \[\label{eq:H-norm} \|H\|_{L^2(0,\infty)}^2=\int_0^\infty|F(u)|^2e^{-\alpha u}\,du\,, \qquad H(-r)=e^{\alpha r/2}F(-r)\,.\tag{13}\]
Expand \(H\) in the orthonormal basis of Lemma 4: \[H=\sum_{m=0}^{k-1}\langle H,\phi_m\rangle\,\phi_m\qquad\text{in }L^2(0,\infty).\] This identity is initially an \(L^2\)-identity, hence both sides agree only almost everywhere on \((0,\infty)\). However, both sides have canonical entire representatives: \(H\) is a finite linear combination of the exponentials \(e^{-\zeta_j t}\), and, by the triangular structure in Lemma 4, so are the \(\phi_m\). By the identity theorem, they agree on all of \(\mathbb{C}\), and the expansion may be evaluated at \(t=-r\). Then, we have \[\begin{align} |H(-r)|^2 =&~ \left|\sum_{m=0}^{k-1}\langle H,\phi_m\rangle\,\phi_m(-r)\right|^2\\ \leq &~ \left(\sum_{m=0}^{k-1}|\phi_m(-r)|^2\right)\sum_{m=0}^{k-1}|\langle H,\phi_m\rangle|^2\\ = &~ \left(\sum_{m=0}^{k-1}|\phi_m(-r)|^2\right)\|H\|_{L^2(0,\infty)}^2\\ \leq &~ \alpha\,e^{\alpha r}\left(\sum_{m=0}^{k-1}L_m(-\alpha r)^2\right)\|H\|_{L^2(0,\infty)}^2\,, \end{align}\] where the second step follows from the Cauchy–Schwarz inequality, the third step follows from the orthonormality of \(\phi_m\), and the last step follows from Lemma 5.
Therefore, by 13 , \[|F(-r)|^2=e^{-\alpha r}|H(-r)|^2 \leq\alpha\sum_{m=0}^{k-1}L_m(-\alpha r)^2\int_0^\infty|F(u)|^2e^{-\alpha u}\,du\,,\] which proves the theorem. ◻
Remark 6 (Relation to Erdélyi’s endpoint estimates). At \(r=0\) and \(\alpha=1\), Theorem 5 reads \[|F(0)|\leq\sqrt k\,\bigl\|F(u)e^{-u/2}\bigr\|_{L^2(0,\infty)}\,,\] which is the pure-imaginary specialization of the half-line endpoint estimate used in Erdélyi’s Müntz–Legendre proof of his weighted endpoint inequalities [22]; see [31] for the Müntz–Legendre background. If instead \(r=0\) and \(\alpha=9k\), then \(9k/\alpha=1\), and combining the display above (rescaled) with Lemma 3 gives \[|F(0)|^2\leq 9k\cdot k\,A_{\mathrm{fr}}\int_0^1|F(u)|^2e^{-9ku}\,du, \qquad\text{i.e.}\qquad |F(0)|\lesssim k\,\bigl\|F(u)e^{-9ku/2}\bigr\|_{L^2[0,1]},\] which is the constant scale of Erdélyi’s weighted finite-interval theorem [22].
In this section we prove the main result for \(1\leq x\leq2\) by combining Theorem 5 with the finite-range inequality of Lemma 3 and the following elementary growth estimate for Laguerre polynomials on the negative axis.
Lemma 6 (Elementary Laguerre growth [32]). For every integer \(m\geq0\) and every \(y\geq0\), \[\label{eq:lag-growth} 0\leq L_m(-y)\leq e^{2\sqrt{my}}\,.\qquad{(9)}\]
Proof. Nonnegativity is clear from 6 .
For the upper bound, we have \[\begin{align} L_m(-y)=&~ \sum_{\ell=0}^m\binom m\ell\frac{y^\ell}{\ell!} \leq\sum_{\ell=0}^\infty\frac{(my)^\ell}{(\ell!)^2}=\sum_{\ell=0}^\infty\frac{(2\sqrt{my})^{2\ell}}{4^\ell (\ell!)^2}\\ \leq &~ \sum_{\ell=0}^\infty\frac{(2\sqrt{my})^{2\ell}}{(2\ell)!} =\cosh (2\sqrt{my})\leq e^{2\sqrt{my}}\,, \end{align}\] where the first inequality follows from \(\binom m\ell\leq\frac{m^\ell}{\ell!}\), the second inequality follows from \((2\ell)!=\binom{2\ell}{\ell}(\ell!)^2\leq4^\ell(\ell!)^2\), and the third inequality follows from \(\cosh x\leq e^x\). This proves ?? . ◻
Proposition 7 (Edge extrapolation). For every \(g\in\mathcal{T}_k\) and every \(0\leq\delta\leq1\), \[\label{eq:edge-sharp} |g(1+\delta)|\leq\sqrt{\frac{9A_{\mathrm{fr}}}{2}}\;k\, \exp\{3\sqrt2\,k\sqrt\delta\}\,\|g\|_{L^2[-1,1]} .\qquad{(10)}\]
Proof. Let \(F(u):=g(1-u)\) for \(u\in\mathbb{R}\). Then \(F\in \mathcal{T}_k\), \(F(-\delta)=g(1+\delta)\), and \[\label{eq:F-energy} \int_0^2|F(u)|^2\,du=\int_{-1}^1|g(t)|^2\,dt=\|g\|_{L^2[-1,1]}^2 \, .\tag{14}\] Now apply Theorem 5 to \(F\) with \(\alpha=\frac{9k}{2}\) and \(r=\delta\): \[\label{eq:edge-chain} \begin{align} |g(1+\delta)|^2=|F(-\delta)|^2 \leq &~ \alpha\sum_{m=0}^{k-1}L_m(-\alpha\delta)^2\int_0^\infty|F(u)|^2e^{-\alpha u}\,du\\ \leq &~ A_{\mathrm{fr}}\,\alpha\sum_{m=0}^{k-1}L_m(-\alpha\delta)^2\int_0^2|F(u)|^2e^{-\alpha u}\,du\\ \leq &~ A_{\mathrm{fr}}\,\alpha\sum_{m=0}^{k-1}L_m(-\alpha\delta)^2\int_0^2|F(u)|^2\,du\,, \end{align}\tag{15}\] where the second step follows from Lemma 3 with the truncation point \(9k/\alpha=2\), and the third step follows from \(e^{-\alpha u}\leq 1\) for \(u\in [0,2]\).
By Lemma 6 with \(y=\alpha\delta=\tfrac{9k}2\delta\), we can upper bound the Laguerre polynomials: \[\label{eq:edge-laguerre} \sum_{m=0}^{k-1}L_m(-\alpha\delta)^2\leq \sum_{m=0}^{k-1} \exp\left(4\sqrt{m\alpha \delta}\right)\leq k\exp\left(4\sqrt{k\alpha\delta}\right) =k\exp\left(6\sqrt2\,k\sqrt\delta\right)\,.\tag{16}\] Combining 14 , 15 , 16 , \[|g(1+\delta)|^2\leq\frac{9A_{\mathrm{fr}}}{2}\,k^2\, \exp\left(6\sqrt2\,k\sqrt\delta\right)\,\|g\|_{L^2[-1,1]}^2 \,.\] Taking square roots gives ?? . ◻
For \(x\geq2\), a coefficient-explicit Turán-type extrapolation is already on the Chebyshev scale, because \(\operatorname{arcosh}x\asymp\log x\) there.
Lemma 7 (Turán’s first main theorem). Let \(z_1,\ldots,z_k\in\mathbb{C}\) satisfy \(|z_j|\geq1\), \(b_1,\ldots,b_k\in\mathbb{C}\), and \(s_n=\sum_{j=1}^kb_jz_j^n\) for integers \(n\geq0\). Then for every integer \(m\geq0\), \[\label{eq:turan} |s_0|\leq k2^{k-1}\binom{m+k-1}{k-1}\max_{m+1\leq n\leq m+k}|s_n| .\qquad{(11)}\] For \(m=0\), the prefactor can be replaced by \(2^k-1\).
Remark 8. Lemma 7 is classical: it is a weak form of Turán’s first main theorem, whose sharp version, due independently to Makai and to de Bruijn, has the smaller constant \(\sum_{j=0}^{k-1}\binom{m+j}{j}2^j\) in place of \(k2^{k-1}\binom{m+k-1}{k-1}\) (and agrees with the constant \(2^k-1\) at \(m=0\)); see [33] or [34]. We include the short standard proof to keep the note self-contained and the constants explicit.
Proof. Let \[a(z):=\prod_{j=1}^k\Bigl(1-\frac{z}{z_j}\Bigr)=\sum_{i=0}^ka_iz^i .\] Expanding the product, \(a_i=(-1)^ie_i(z_1^{-1},\ldots,z_k^{-1})\), where \[\begin{align} e_i(x_1,\dots,x_k)=\sum_{S\in \binom{[k]}{i}}\prod_{j\in S}x_j \end{align}\] is the \(i\)-th elementary symmetric polynomial. Since \(|z_j|\geq 1\), we have for \(0\leq i\leq k\), \[\label{eq:a-coeff} |a_i|\leq \sum_{S\in \binom{[k]}{i}}\prod_{j\in S}\left|z_j^{-1}\right|\leq \binom ki\,.\tag{17}\]
For any \(z\in \mathbb{C}\), \(|z|<1\leq\min_j|z_j|\), \(a(z)^{-1}\) has the following series expansion: \[\frac{1}{a(z)}=\prod_{j=1}^k\frac{1}{1-z/z_j} =\prod_{j=1}^k\sum_{n=0}^\infty\Bigl(\frac{z}{z_j}\Bigr)^n =\sum_{\ell=0}^\infty h_\ell\,z^\ell, \qquad h_\ell=h_\ell(z_1^{-1},\ldots,z_k^{-1})\,,\] where \[\begin{align} h_\ell(x_1,\dots,x_k)=\sum_{\substack{n_1+\cdots+n_k=\ell\\n_i\geq 0}} x_1^{n_1}\cdots x_k^{n_k} \end{align}\] is the complete homogeneous symmetric polynomial of degree \(\ell\). The number of monomials in \(h_\ell\) is \(\binom{\ell+k-1}{k-1}\), and each \(|z_j^{-1}|\leq 1\). Hence, for any \(\ell\geq 0\), \[\label{eq:h-coeff} |h_\ell|\leq\binom{\ell+k-1}{k-1}\,.\tag{18}\]
Let \(H_m(z):=\sum_{\ell=0}^mh_\ell z^\ell\) be the \(m\)-th partial sum of the series expansion of \(a(z)^{-1}\), and \[\varphi(z):=1-a(z)H_m(z)=\sum_{n}\varphi_n z^n \,.\] Since \(H_m\equiv1/a\pmod{z^{m+1}}\) (as formal power series), we get \(a\,H_m\equiv1\pmod{z^{m+1}}\), i.e. all coefficients of \(\varphi\) of degree \(\leq m\) vanish. Also \(\deg\varphi\leq\deg a+\deg H_m\leq k+m\), and \(\varphi(z_j)=1-a(z_j)H_m(z_j)=1\) because \(a(z_j)=0\). Therefore, \[\label{eq:s0-expansion} s_0=\sum_{j=1}^kb_j=\sum_{j=1}^kb_j\varphi(z_j) =\sum_{j=1}^kb_j\sum_{n=m+1}^{m+k}\varphi_n z_j^n =\sum_{n=m+1}^{m+k}\varphi_n s_n \,.\tag{19}\]
It remains to bound the coefficients of \(\varphi\). For \(n\geq m+1\), \[\varphi_n=-\sum_{\substack{i+\ell=n\\ 1\leq i\leq k,\;0\leq\ell\leq m}}a_ih_\ell\] Summing over the relevant range of \(n\) and grouping by \(i\): for fixed \(i\in\{1,\ldots,k\}\), the constraint \(0\leq\ell=n-i\leq m\) together with \(m+1\leq n\leq m+k\) forces \(n\in\{m+1,\ldots,m+i\}\), i.e.at most \(i\) values of \(n\). Using 17 , 18 , and the monotonicity \(\binom{\ell+k-1}{k-1}\leq\binom{m+k-1}{k-1}\) for \(\ell\leq m\), we obtain that \[\sum_{n=m+1}^{m+k}|\varphi_n| \leq\sum_{i=1}^k i\binom ki\cdot\binom{m+k-1}{k-1} =k2^{k-1}\binom{m+k-1}{k-1}\,.\] Combined with 19 and the triangle inequality, this proves ?? .
If \(m=0\), then \(H_0=h_0=1\) and \(\varphi=1-a\) has coefficients \(-a_1,\ldots,-a_k\), so \(\sum_{\nu=1}^k|\varphi_\nu|\leq\sum_{i=1}^k\binom ki=2^k-1\). ◻
Proposition 9 (Outer extrapolation). For every \(g\in\mathcal{T}_k\) and every \(x\geq2\), \[\label{eq:outer} |g(x)|\leq k^2\exp\left(4k\,\operatorname{arcosh}x\right)\,\|g\|_{L^2[-1,1]} \,.\qquad{(12)}\]
Proof. We prove an intermediate bound: for all \(x\geq1\) and all \(k\geq1\), \[\label{eq:outer-intermediate} |g(x)|\leq k^2\bigl(3e(x+1)\bigr)^k\,\|g\|_{L^2[-1,1]} \,.\tag{20}\] Note that for \(x\geq2\) we have \(\log\bigl(3e(x+1)\bigr)\leq4\operatorname{arcosh}x\): indeed, \(x+1\leq2x\) gives \(\log\bigl(3e(x+1)\bigr)\leq\log(6e)+\log x\); moreover \(\log x\leq\log\bigl(x+\sqrt{x^2-1}\bigr)=\operatorname{arcosh}x\), and \(\operatorname{arcosh}x\geq1\) because \(\cosh1<2\leq x\), so \(\log(6e)<2.8<3\leq3\operatorname{arcosh}x\). Substituting into 20 gives ?? .
For \(k=1\), \(g(t)=v_1e^{i\lambda_1t}\), so \(|g(x)|=|v_1|\) while \(\|g\|_{L^2[-1,1]}=\sqrt2\,|v_1|\); thus \(|g(x)|\leq\|g\|_{L^2[-1,1]}\) and 20 holds trivially.
Assume \(k\geq2\). To apply Turán’s first main theorem (Lemma 7), we construct the extrapolation nodes as follows: \[h=\frac{2}{k+1},\qquad m=\max\left(0,\left\lceil\frac{x-1}{h}\right\rceil-1\right), \qquad t_n:=x-n h\quad(n\geq0).\] We claim that the \(k\) consecutive nodes \(t_{m+1},\ldots,t_{m+k}\) lie in \([-1,1]\), and \[\label{eq:m-bound} m\leq (k+1)(x-1)/2 .\tag{21}\] We prove the claim by considering \(m\geq 1\) and \(m=0\) separately:
If \(m\geq1\), then \(m+1=\lceil(x-1)/h\rceil\), so \[\begin{align} \label{eq:m95range} (x-1)/h\leq m+1<(x-1)/h+1\,. \end{align}\tag{22}\] The first inequality in 22 gives \[\begin{align} t_{m+1}=x-(m+1)h\leq x-(x-1)=1\,. \end{align}\] And the second inequality in 22 gives \(t_{m+1}>1-h\), which implies that \[t_{m+k}=t_{m+1}-(k-1)h>1-kh=1-\frac{2k}{k+1}=\frac{1-k}{k+1}\geq-1 \,.\] We also have \[\begin{align} m\leq\lceil(x-1)/h\rceil-1<(x-1)/h=(k+1)(x-1)/2\,. \end{align}\]
If \(m=0\), then \(\lceil(x-1)/h\rceil\leq1\), i.e.\(x\leq1+h\), so \(t_1=x-h\leq1\). And since \(x\geq 1\), we have \(t_k=x-kh\geq 1-kh \geq-1\) as before. And 21 trivially holds for \(m=0\).
Let \(g(t)=\sum_{j=1}^kv_je^{i\lambda_jt}\) and set \[z_j:=e^{-i\lambda_jh},\qquad b_j:=v_je^{i\lambda_jx} .\] Then \(|z_j|=1\) and \[s_n=\sum_{j=1}^kb_jz_j^n=\sum_{j=1}^kv_je^{i\lambda_j(x-n h)}=g(t_n)\,.\] In particular, \(s_0=g(x)\), and by the claim, for \(m+1\leq n \leq m+k\), \(|s_n|\leq\|g\|_{L^\infty[-1,1]}\). Now, we can apply Lemma 7 and get that \[\label{eq:outer-raw} |g(x)|\leq k2^{k-1}\binom{m+k-1}{k-1}\,\|g\|_{L^\infty[-1,1]}\,.\tag{23}\] We bound the binomial coefficient as follows: \[\label{eq:binom-bound} \begin{align} \binom{m+k-1}{k-1} \leq &~ \left(e\frac{m+k-1}{k-1}\right)^{k-1} \leq \left(e\frac{\frac{(k+1)(x-1)}{2}+k-1}{k-1}\right)^{k-1}\\ \leq &~ \left(e\frac{\frac{3(k-1)(x-1)}{2}+k-1}{k-1}\right)^{k-1} \leq \left(\frac{3e(x+1)}{2}\right)^{k-1}\,, \end{align}\tag{24}\] where the second step follows from 21 , and the third step follows from \(k\geq 2\). Combining 23 , 24 gives \[\begin{align} |g(x)|\leq k2^{k-1} \left(\frac{3e(x+1)}{2}\right)^{k-1}\, \|g\|_{L^\infty[-1,1]} = k (3e(x+1))^{k-1} \, \|g\|_{L^\infty[-1,1]}\,. \end{align}\] Then, we apply the endpoint Nikolskii inequality (Lemma 2): \[|g(x)|\leq k (3e(x+1))^{k-1}\cdot\frac{\pi k}{2\sqrt2}\,\|g\|_{L^2[-1,1]} =k^2\,\frac{\pi}{2\sqrt2}\,\bigl(3e(x+1)\bigr)^{k-1}\,\|g\|_{L^2[-1,1]}\,.\] Since \(\frac{\pi{2\sqrt2}}{<}1.2<3e(x+1)\), this is at most \(k^2(3e(x+1))^k\|g\|_{L^2[-1,1]}\), which proves the intermediate bound 20 . ◻
Proof of Theorem 1. For \(k=1\), \(g(t)=v_1e^{i\lambda_1t}\) and \(|g(x)|=|v_1|=2^{-1/2}\|g\|_{L^2[-1,1]}\), so both estimates hold trivially. Assume \(k\geq2\) and let \(\rho=\operatorname{arcosh}x\geq0\).
If \(1\leq x\leq2\), write \(x=1+\delta\) with \(0\leq\delta\leq1\). Then, Proposition 7 gives ?? : \[\begin{align} |g(1+\delta)|\leq\sqrt{\frac{9A_{\mathrm{fr}}}{2}}\;k\, e^{3\sqrt2\,k\sqrt\delta}\,\|g\|_{L^2[-1,1]} \leq 192\,k\,e^{3\sqrt2\,k\rho}\,\|g\|_{L^2[-1,1]}\,, \end{align}\] where the second step uses \(A_{\mathrm{fr}}\leq8191\) (so that \(\sqrt{9A_{\mathrm{fr}}/2}<192\)) together with the bound \(\sqrt\delta\leq\operatorname{arcosh}(1+\delta)=\rho\) from ?? . In particular, the first inequality of this display proves ?? .
If \(x\geq2\), Proposition 9 gives \[|g(x)|\leq k^2e^{4k\rho}\,\|g\|_{L^2[-1,1]}\,.\] Thus, for \(x\geq 1\), \[\begin{align} |g(x)|\leq \max\left\{192\,k\,e^{3\sqrt2\,k\rho},k^2e^{4k\rho}\right\}\,\|g\|_{L^2[-1,1]} \leq 192\,k^2e^{3\sqrt{2}k\rho}\,\|g\|_{L^2[-1,1]}\,, \end{align}\] using \(k\leq k^2\) and \(4\leq3\sqrt2\); this proves ?? . ◻
Proposition 10 (Chebyshev lower bound; cf.). For every \(k\geq1\) and every \(x\geq1\), \[\sup_{0\neq g\in\mathcal{T}_k} \frac{|g(x)|}{\|g\|_{L^2[-1,1]}} \geq \frac{1}{2\sqrt2} \exp\!\left((k-1)\operatorname{arcosh}x\right).\] Consequently the exponent \(\Theta(k\operatorname{arcosh}x)\) in Theorem 1 is sharp up to absolute constants and polynomial factors in \(k\).
Proof. Let \(n=k-1\) and \(T_{n}\) be the Chebyshev polynomial of the first kind of degree \(n\). For \(0<\varepsilon\leq1\), define \[w_\varepsilon(t):= \frac{e^{i\varepsilon t}-1}{i\varepsilon}, \qquad P_\varepsilon(t):= T_n(w_\varepsilon(t))\,.\] Since \(T_n\) is a polynomial of degree \(n\), and since \[w_\varepsilon(t)^m = (i\varepsilon)^{-m} \sum_{\ell=0}^m \binom m\ell(-1)^{m-\ell}e^{i\ell\varepsilon t}, \qquad 0\leq m\leq n\,,\] we have \[P_\varepsilon\in \operatorname{span}\{e^{i\ell\varepsilon t}:0\leq \ell\leq n\} \subset \mathcal{T}_k \,.\]
We next show that \(P_\varepsilon\to T_n\) uniformly on \([-1,x]\). Put \(R=x\). For real \(|t|\leq R\), the elementary Taylor remainder estimate \[|e^{iu}-1-iu|\leq \frac{u^2}{2}, \qquad u\in\mathbb{R},\] gives \[|w_\varepsilon(t)-t| = \frac{|e^{i\varepsilon t}-1-i\varepsilon t|}{\varepsilon} \leq \frac{\varepsilon t^2}{2} \leq \frac{\varepsilon R^2}{2}.\] Thus, as \(\varepsilon\rightarrow 0\), \(w_\varepsilon(t)\to t\) uniformly for \(t\in[-R,R]\). Since \(T_n\) is a fixed polynomial, it follows that \[P_\varepsilon(t)=T_n(w_\varepsilon(t)) \longrightarrow T_n(t)\] uniformly for \(t\in[-R,R]\), hence in particular uniformly on \([-1,1]\) and pointwise at \(x\). Therefore \[P_\varepsilon(x)\to T_n(x), \qquad \|P_\varepsilon\|_{L^2[-1,1]} \to \|T_n\|_{L^2[-1,1]} .\] Since \(P_\varepsilon\in\mathcal{T}_k\), we get \[\sup_{0\neq g\in\mathcal{T}_k} \frac{|g(x)|}{\|g\|_{L^2[-1,1]}} \geq \lim_{\varepsilon\to0} \frac{|P_\varepsilon(x)|}{\|P_\varepsilon\|_{L^2[-1,1]}} = \frac{|T_n(x)|}{\|T_n\|_{L^2[-1,1]}} .\]
Finally, \(|T_n(t)|\leq1\) for \(-1\leq t\leq1\), so \[\|T_n\|_{L^2[-1,1]}\leq \sqrt2 .\] For \(x\geq1\), \[T_n(x) = \cosh\!\left(n\operatorname{arcosh}x\right) \geq \frac{1}{2} \exp\!\left(n\operatorname{arcosh}x\right).\] Combining the last two estimates gives \[\frac{|T_n(x)|}{\|T_n\|_{L^2[-1,1]}} \geq \frac{1}{2\sqrt2} \exp\!\left(n\operatorname{arcosh}x\right),\] and since \(n=k-1\), the proposition follows. ◻
In this section we give two algorithmic applications of Theorem 1. In Section 8.1, we apply it to the Chen–Price clustered-frequency algorithm, replacing their power-law growth surrogate by a Chebyshev-matched filter and improving the attainable resolution. In Section 8.2, we bound both exterior Fourier-feature leverage scores and the associated worst-case \(L^2\) transfer constant, obtaining sharp guarantees for extrapolative active regression.
Chen and Price [10] study the following problem. In this subsection we use their cycles-per-unit-time frequency convention, so that our angular frequency is \(\lambda=2\pi f\). An unknown signal is observed on a window \([-T,T]\) through noisy samples \[y(t)=g(t)+\zeta(t),\] where \(\operatorname{supp}(\widehat g)\subseteq[f_0-\Delta,f_0+\Delta]\), the center \(f_0\in[-F,F]\) is unknown, and \[\mathbb{E}_{t\sim[-T,T]}\left[|\zeta(t)|^2\right] \le \epsilon\,\mathbb{E}_{t\sim[-T,T]}\left[|g(t)|^2\right]\] for a sufficiently small absolute constant \(\epsilon\). The goal is to estimate \(f_0\).
Their generic theorem is stated for an admissible signal class \(\mathcal{F}\). It uses the peak-to-average parameter \[R(\mathcal{F}):=\sup_{0\ne g\in\mathcal{F}} \frac{\sup_{t\in[-T,T]}|g(t)|^2}{\mathbb{E}_{t\sim[-T,T]}[|g(t)|^2]}\] and an exponent \(S\) for which every \(g\in\mathcal{F}\) satisfies the power-law majorant \[|g(t)|^2 \le \operatorname{poly}(R)\,\left|\frac{t}{T}\right|^S \mathbb{E}_{u\sim[-T,T]}[|g(u)|^2] , \qquad |t|\ge T\,.\] When \(\mathcal{F}=\mathcal{T}_k\), Chen and Price prove \(R=O(k^3\log^2k)\) and \(S=O(k^2\log k)\). Let \[\Delta_{\mathrm{CP}}:=\Delta+\widetilde{O}(k^3/T)\] and \(\delta_{\mathrm{fail}}\in(0,1)\) denote the failure probability. Their specialized nonuniform-sampling theorem uses \[O\!\left(k\log^2k\cdot \log\frac{F}{\Delta_{\mathrm{CP}}\delta_{\mathrm{fail}}}\right)\] samples and returns \(\widehat f_0\) satisfying \(|\widehat f_0-f_0|=O(\Delta_{\mathrm{CP}})\) with probability at least \(1-\delta_{\mathrm{fail}}\).
For simplicity, define \[\|g\|_{2,T}^2:=\mathbb{E}_{t\sim[-T,T]}\left[|g(t)|^2\right] =\frac{1}{2T}\int_{-T}^{T}|g(t)|^2\,dt\,.\] Rescaling Theorem 1 gives the intrinsic outside-growth envelope \[\label{eq:scaled-cheb-envelope} |g(Tx)| \le C_0k^2\exp\!\left(3\sqrt2\,k\operatorname{arcosh}x\right)\|g\|_{2,T}, \qquad \forall x\ge1\,,\tag{25}\] and, in the endpoint regime, \[\label{eq:scaled-cheb-edge} |g(T(1+\delta))| \le C_0k\exp\!\left(3\sqrt2\,k\sqrt\delta\right)\|g\|_{2,T}, \qquad \forall 0\le\delta\le1\,,\tag{26}\] where one may take \(C_0=192\sqrt2\). The next theorem constructs the filter directly against this Chebyshev envelope, without first replacing it by a monomial majorant. The construction is a multiscale product of powers of \(\operatorname{sinc}\); single-scale versions underlie the filters of [9], [10], while compactly bandlimited kernels with \(e^{-c\sqrt{|t|}}\)-type decay go back to Ingham [35]. We use the Fourier transform convention \[\begin{align} \widehat f(\xi)=\int_{\mathbb{R}}f(t)e^{-i\xi t}\,dt\,. \end{align}\]
Theorem 11 (Chebyshev-scale truncation window). For every \(0<\eta<1\), there is a constant \(C_\eta\) such that the following holds. For every integer \(k\ge1\) and every \(T>0\), there exists a real even function \(H_{k,T}\) satisfying \[0\le H_{k,T}(t)\le1, \qquad \operatorname{supp}\widehat {H_{k,T}}\subseteq[-C_\eta k^2/T,\,C_\eta k^2/T]\,,\] and, for every \(g\in\mathcal{T}_k\), \[\label{eq:cheb-filter-energy} \int_{-T}^{T}|1-H_{k,T}(t)|^2|g(t)|^2\,dt +\int_{\mathbb{R}\setminus[-T,T]}|H_{k,T}(t)|^2|g(t)|^2\,dt \le\eta\int_{-T}^{T}|g(t)|^2\,dt\, .\qquad{(13)}\]
Proof. It suffices to prove the case \(T=1\): if \(H_{k,1}\) has been constructed, set \(H_{k,T}(t):=H_{k,1}(t/T)\), so that \(\operatorname{supp}\widehat{H_{k,T}}=T^{-1}\operatorname{supp}\widehat{H_{k,1}}\), and apply the \(T=1\) estimate to \(u\mapsto g(Tu)\in\mathcal{T}_k\); changing variables back yields ?? .
We prove the \(T=1\) case in the following seven steps.
Step 1: a multiscale sinc-product kernel. Fix \(A\ge1\) (an absolute constant chosen later). For convenience, we will use \(C_A\) to denote all constant factors that depend only on \(A\) (so that in different equations, the meaning of \(C_A\) may differ). Let \(B\ge16\). Let \[J:=\lfloor\log_4B\rfloor,\qquad \omega_j:=B4^{-j},\qquad m_j:=2\lceil A2^j\rceil\qquad~\forall0\le j\le J\,,\] and define the kernel function \[\label{eq:sinc-product-filter} \Psi_{A,B}(u):=\prod_{j=0}^J\left(\operatorname{sinc}(\omega_j u)\right)^{m_j}, \quad Z_{A,B}:=\int_\mathbb{R}\Psi_{A,B}(u)\,du, \quad K_{A,B}(u):=\frac{\Psi_{A,B}(u)}{Z_{A,B}}\,,\tag{27}\] with the convention \(\operatorname{sinc}(0)=1\). Every \(m_j\) is even, so \(\Psi_{A,B}\ge0\); the factor \(j=0\) decays like \(|u|^{-m_0}\) with \(m_0\ge2\), so \(\Psi_{A,B}\) is integrable. Moreover, \(\Psi_{A,B}(0)=1\), so \(Z_{A,B}>0\) and \(K_{A,B}\) is an even probability density.
Under our Fourier-transform convention, \[\widehat{\operatorname{sinc}(\omega\,\cdot)}(\xi) =\frac{\pi}{\omega}\,\mathbf{1}_{[-\omega,\omega]}(\xi)\] (up to irrelevant endpoint values). By the convolution theorem of the Fourier transform, up to the factor \((2\pi)^{-1}\), \(\widehat{(\operatorname{sinc}(\omega\,\cdot))^m}\) is supported in the Minkowski sum of \(m\) copies of \([-\omega,\omega]\), namely \([-m\omega,m\omega]\). Applying this once more to the product over \(j\), \[\begin{align} \label{eq:supp95hat95KAB} \operatorname{supp}\widehat {K_{A,B}}\subseteq[-\sigma,\sigma]\,, \end{align}\tag{28}\] where \[\sigma:=\sum_{j=0}^Jm_j\omega_j \le\sum_{j=0}^J(2A2^j+2)B4^{-j}\le4AB+\tfrac83B\le7AB \,.\] Dividing by the nonzero scalar \(Z_{A,B}\) only multiplies the Fourier transform by \(Z_{A,B}^{-1}\), and therefore does not change its support.
Step 2: normalization. We claim that \[\label{eq:Z-lower-filter} Z_{A,B}\ge \frac{2}{e\sqrt{8A}}\frac{1}{B}\,.\tag{29}\] Indeed, for \(|z|\le1\), \(\operatorname{sinc}(z)>0\) and \(\log(\operatorname{sinc}(z))\ge-z^2\), since \[\begin{align} \frac{\sin z}{z}\ge &~ 1-\frac{z^2}{6} \qquad \text{and}\qquad e^{-z^2}\le1-z^2+\frac{z^4}{2}\le1-\frac{z^2}{6}\,. \end{align}\] Thus, for \(|u|\le1/(\sqrt{8A}\,B)\), where every \(|\omega_ju|=|B4^{-j} u|\le Bu\le1\), we have \[-\log\left(\Psi_{A,B}(u)\right)\le\sum_{j=0}^Jm_j(\omega_ju)^2 \le B^2u^2\sum_{j=0}^J(2A2^j+2)16^{-j}\le8AB^2u^2\le1\,.\] Hence \(\Psi_{A,B}\ge e^{-1}\) on that interval. Because \(\Psi_{A,B}\ge0\) on the whole real line, we may lower-bound its total integral by integrating over this subinterval alone: \[Z_{A,B}=\int_{\mathbb{R}}\Psi_{A,B}(u)\,du \ge \int_{-1/(\sqrt{8A}B)}^{1/(\sqrt{8A}B)}\Psi_{A,B}(u)\,du \ge \frac{2}{e\sqrt{8A}}\frac{1}{B},\] which is 29 .
Step 3: tails of the kernel. Let \(P_{A,B}(r):=\int_r^\infty K_{A,B}(u)\,du\) for \(r\ge0\) be the tail of the kernel. We claim that there are an absolute constant \(c>0\) and constants \(C_A\) (depending only on \(A\)) such that the following tail bounds hold: \[\begin{align} \tag{30} P_{A,B}(r)&\le C_A\,e^{-cA\sqrt B}\,r^{-cA\sqrt B}\,,&&\forall r\ge1\,,\\ \tag{31} P_{A,B}(r)&\le C_A\bigl(1+\sqrt{Br}\bigr)e^{-cA\sqrt{Br}}\,,&&\forall 0\le r\le1 \,. \end{align}\]
Far tail (\(r\geq 1\)): Let \(J':=\lfloor\log_4(B/2)\rfloor\le J\), so that \(\omega_j=B4^{-j}\ge2\) for all \(j\le J'\). For every \(u\ge r\ge1\) and \(j\le J'\), \[\begin{align} \label{eq:bound95sinc} |\operatorname{sinc}(\omega_j u)| =\left|\frac{\sin(\omega_ju)}{\omega_ju}\right| \le \frac{1}{\omega_ju}\le \frac{1}{2u}\,. \end{align}\tag{32}\] For \(J'<j\le J\) we use the trivial bound \(|\operatorname{sinc}(\omega_j u)|\le1\). Hence, \(\Psi_{A,B}(u)\le (2u)^{-M}\), where \[M:=\sum_{j=0}^{J'}m_j \ge2A\,2^{J'}\ge\frac{A\sqrt B}{2\sqrt2}\,.\] By 29 , for \(r\ge1\), \[P_{A,B}(r) \le C_AB\,\frac{2^{-M}}{M-1}\,r^{-(M-1)}.\] By choosing \(A\) larger than an absolute constant, \(M-1\ge A\sqrt B/(4\sqrt{2})\). Also \(\log B\le\sqrt B\) for \(B\ge16\), and therefore \[C_AB\,\frac{2^{-M}}{M-1} \le C_Ae^{-c_1A\sqrt B}\] for an absolute \(c_1>0\), while \[r^{-(M-1)}\le r^{-c_2A\sqrt B}\] for \(c_2:=1/(4\sqrt{2})\). Taking \(c:=\min\{c_1,c_2\}\) proves 30 .
Near tail (\(r\in [0,1]\)): If \(Br\le4\), then 31 holds trivially after enlarging \(C_A\), since \(P_{A,B}(r)\le1\). Assume \(Br>4\). For each \(u\in[r,1]\), let \(j_*(u):=\lfloor\log_4(Bu/2)\rfloor\in[0,J]\). Then, \(\omega_ju = B4^{-j} u\ge2\) for all \(j\le j_*(u)\), and as in 32 , we have \(|\operatorname{sinc}(\omega_ju)|\le\frac{1}{2}\) for those \(j\). Thus, \(\Psi_{A,B}(u)\leq 2^{-M_u}\), where \[M_u:=\sum_{j=0}^{j_*(u)} m_j = \sum_{j=0}^{j_*(u)} 2\lceil A2^j\rceil \geq 2A2^{j_*(u)} \geq 2 A \cdot \frac{\sqrt{Bu}}{2\sqrt2}\geq cA\sqrt{Bu}\,.\] Hence, by 29 and the substitution \(y=\sqrt{Bu}\) (so \(B\,du=2y\,dy\)), we have \[\begin{align} P_{A,B}(r) &\le\frac{1}{Z_{A,B}}\int_r^1e^{-cA\sqrt{Bu}}\,du+P_{A,B}(1)\\ &\le C_A\int_{\sqrt{Br}}^\infty ye^{-cAy}\,dy+P_{A,B}(1)\\ &\le C_A(1+\sqrt{Br})e^{-cA\sqrt{Br}}. \end{align}\] where in the last step, \(P_{A,B}(1)\le C_Ae^{-cA\sqrt B}\) by 30 is absorbed because \(r\le1\).
Step 4: the window and its interior defect. Define \[\label{eq:HAB-def} H_{A,B}(t):=(\mathbf{1}_{[-1,1]}*K_{A,B})(t)=\int_{-1}^1K_{A,B}(t-s)\,ds .\tag{33}\] Then, \(H_{A,B}\) is real and even, \(0\le H_{A,B}\le1\), and \(\operatorname{supp}\widehat {H_{A,B}}\subseteq[-7AB,7AB]\), since \(\widehat{H_{A,B}}=\widehat{\mathbf{1}_{[-1,1]}}\cdot\widehat{K_{A,B}}\) and 28 . Moreover, for \(r\ge0\), \[\begin{align} \label{eq:H95AB95near95bound} H_{A,B}(1+r)=\int_r^{2+r}K_{A,B}(u)\,du\le P_{A,B}(r), \end{align}\tag{34}\] with the same bound at \(-1-r\) by symmetry. And for \(t\in[-1,1]\), we have \[1-H_{A,B}(t)=P_{A,B}(1-t)+P_{A,B}(1+t)\le2P_{A,B}(1-|t|) .\] Consequently, by 31 and the substitution \(y=\sqrt{Br}\), \[\label{eq:interior-defect-filter} \begin{align} \int_{-1}^1|1-H_{A,B}(t)|^2\,dt\le &~ 8\int_0^1P_{A,B}(r)^2\,dr\\ \leq &~ 8\int_0^1 C_A^2 \bigl(1+\sqrt{Br}\bigr)^2e^{-2cA\sqrt{Br}}\,dr\\ \le &~ \frac{C_A}{B}\int_0^\infty y(1+y)^2e^{-2cAy}\,dy\le\frac{C_A}{B}\,. \end{align}\tag{35}\] Combining with the Nikolskii bound ?? , we get that \[\label{eq:inside-loss-filter} \begin{align} \int_{-1}^1|1-H_{A,B}(t)|^2|g(t)|^2\,dt \le &~ \|g\|_{L^\infty[-1,1]}^2\int_{-1}^1|1-H_{A,B}(t)|^2\,dt\\ \leq &~ \|g\|_{L^\infty[-1,1]}^2 \cdot \frac{C_A}{B}\\ \leq &~ \frac{C_Ak^2}{B}\,\|g\|_{L^2[-1,1]}^2 \,. \end{align}\tag{36}\]
Step 5: outside leakage, near range. From now on \(B=\beta k^2\) with \(\beta\ge16\) to be chosen. For \(0\le r\le1\), Proposition 7 gives \[\begin{align} |g(1+r)|^2\le\frac{9}{2}A_{\mathrm{fr}}\,k^2e^{6\sqrt2\,k\sqrt r}\,\|g\|_{L^2[-1,1]}^2\,. \end{align}\] By 34 and 31 , \[\begin{align} \int_0^1|H_{A,B}(1+r)|^2|g(1+r)|^2\,dr\leq &~ \int_0^1|P_{A,B}(r)|^2|g(1+r)|^2\,dr\\ \leq &~ C_Ak^2\,\|g\|_{L^2[-1,1]}^2 \cdot \int_0^1|P_{A,B}(r)|^2e^{6\sqrt2\,k\sqrt r}\,dr\\ \le &~ C_Ak^2\,\|g\|_{L^2[-1,1]}^2 \int_0^1\bigl(1+\sqrt{Br}\bigr)^2\,e^{-2cA\sqrt{Br}+6\sqrt2\,k\sqrt r}\,dr \,. \end{align}\] Since \(\sqrt{Br}=\sqrt\beta\,k\sqrt r\), the exponent equals \(-(2cA-6\sqrt2/\sqrt\beta)\sqrt{Br}\). Fix \(A\) so large (absolute) that \(cA\ge1\); then for \(\beta\ge72\) we have \(6\sqrt2/\sqrt\beta\le1\le cA\), so the exponent is at most \(-cA\sqrt{Br}\). Then, with \(y=\sqrt{Br}\), we get that \[\int_0^1\bigl(1+\sqrt{Br}\bigr)^2e^{-cA\sqrt{Br}}\,dr \le\frac{2}{B}\int_0^\infty y(1+y)^2e^{-cAy}\,dy\le\frac{C_A}{B} \,.\] Thus the near right tail can be bounded by: \[\begin{align} \label{eq:H95near95tail} \int_0^1|H_{A,B}(1+r)|^2|g(1+r)|^2\,dr \leq \frac{C_A}{B}k^2\|g\|_{L^2[-1,1]}^2=\frac{C_A}{\beta}\|g\|_{L^2[-1,1]}^2\,. \end{align}\tag{37}\] And the near left tail is identical by symmetry.
Step 6: outside leakage, far range. For \(r\ge1\), note that \[\begin{align} \operatorname{arcosh}(1+r)\le\log(2(1+r))\le \log ((1+r)^2)\,. \end{align}\] By ?? squared, we have \[\begin{align} |g(1+r)|^2\leq &~ Ck^4\exp\left(6\sqrt2\,k\operatorname{arcosh}(1+r)\right)\|g\|_{L^2[-1,1]}^2\\ \leq &~ C\,k^4\,(1+r)^{17k}\,\|g\|_{L^2[-1,1]}^2\,, \end{align}\] while 34 and 30 give that \[\begin{align} |H_{A,B}(1+r)|^2\leq |P_{A,B}(r)|^2\le C_Ae^{-2cA\sqrt B}r^{-2cA\sqrt B} =C_Ae^{-2cA\sqrt{\beta}k}r^{-2cA\sqrt{\beta}k}\,. \end{align}\] Using \((1+r)^{17k}\le2^{17k}r^{17k}\) and requiring \(cA\sqrt\beta\ge18\), \[\begin{align} \int_1^\infty|H_{A,B}(1+r)|^2|g(1+r)|^2\,dr &\le C_Ak^42^{17k}e^{-2cA\sqrt\beta k} \int_1^\infty r^{17k-2cA\sqrt\beta k}\,dr\cdot \|g\|^2_{L^2[-1,1]}\\ &\le C_Ae^{16k-2cA\sqrt\beta k}\,\|g\|_{L^2[-1,1]}^2\,, \end{align}\] where the second step follows from \(k^42^{17k}\le e^{16k}\) for every \(k\ge1\) and the integral is at most \(1\). Increase \(\beta\) once more so that \((2cA-1)\sqrt\beta\ge16\); since \(cA\ge1\), it is enough to take \(\beta\ge256\). Then, we have \(2cA\sqrt\beta-16\ge\sqrt\beta\), and the far right tail can be bounded by: \[\begin{align} \label{eq:H95far95tail} \int_1^\infty|H_{A,B}(1+r)|^2|g(1+r)|^2\,dr \leq C_Ae^{-\sqrt\beta k}\|g\|_{L^2[-1,1]}^2\le C_Ae^{-\sqrt\beta}\|g\|_{L^2[-1,1]}^2\,. \end{align}\tag{38}\] The far left tail is identical by symmetry.
Step 7: wrap up. Set \(H_{k,1}:=H_{A,\beta k^2}\). Summing 36 , the two near-tail bounds 37 , and the two far-tail bounds 38 , we have \[\begin{align} &~ \int_{-1}^1|1-H_{k,1}|^2|g|^2\,dt+\int_{\mathbb{R}\setminus[-1,1]}|H_{k,1}|^2|g|^2\,dt\\ \leq &~ \frac{C_A k^2}{\beta k^2}\|g\|_{L^2[-1,1]}^2 + 2\left(\frac{C_A}{\beta}\|g\|_{L^2[-1,1]}^2 + C_Ae^{-\sqrt\beta}\|g\|_{L^2[-1,1]}^2\right)\\ \le &~ C_A\bigl(\beta^{-1}+e^{-\sqrt\beta}\bigr)\|g\|_{L^2[-1,1]}^2\,. \end{align}\] We can choose \(\beta=\beta(\eta)\) sufficiently large to make the right-hand side at most \(\eta\|g\|_{L^2[-1,1]}^2\), which is ?? for \(T=1\), with Fourier support contained in \([-7A\beta k^2,7A\beta k^2]\), i.e., \(C_\eta=7A\beta(\eta)\). Therefore, the case \(T=1\) is proved.
By the reduction at the beginning of the proof, the theorem is then proved. ◻
Remark 12 (Eliminating the power-law surrogate). [10] uses the parameter \(S\) to capture the tail behavior of an arbitrary signal class by a power law. For sparse Fourier sums, however, \(S\) is not intrinsic. The true outside-window growth profile is the Chebyshev envelope 25 , with the endpoint behavior 26 . Theorem 11 constructs the window directly against this profile, thereby removing the power-law encoding from the sparse-Fourier argument.
For comparison only, the sharp peak-to-average scale is \(R=\Theta(k^2)\), and the best power-law representation with a polynomial prefactor has \(S=\Theta(k^2/\log k)\); see Propositions 14 and 15. These parameters quantify the loss in the original surrogate, but neither is needed for the direct filtering argument.
Corollary 1 (Improved clustered-frequency estimation). In the clustered-frequency model above, for every failure probability \(\delta_{\mathrm{fail}}\in(0,1)\), there is an efficient algorithm using \[O\!\left( k\log^2k\cdot \log\frac{F}{\Delta_*\delta_{\mathrm{fail}}} \right)\] samples and returning an estimate \(\widehat f_0\) such that, with probability at least \(1-\delta_{\mathrm{fail}}\), \[|\widehat f_0-f_0|\le O(\Delta_*), \qquad \Delta_*:=\Delta+O\!\left(\frac{k^2}{T}\right).\] Thus the additive resolution improves from \(\Delta+\widetilde{O}(k^3/T)\) in [10] to \(\Delta+O(k^2/T)\), while the sample complexity is unchanged up to the logarithmic factors already present in their theorem.
Proof. Fix a sufficiently small absolute \(\eta\) and use the window from Theorem 11. Appendix 10 verifies all the conditions for the window used in [10]. As a result, we obtain an analog of [10] with \(\Delta_* = \Delta+O(k^2/T)\) and \(O(k\log^2k)\) samples per phase estimate. Applying the same multiscale frequency-search routine as in [10] gives the stated guarantee and the additional logarithmic factor. ◻
Fix a frequency set \(\Lambda=(\lambda_1,\ldots,\lambda_k)\) and write \[E_\Lambda:=\operatorname{span}\{e^{i\lambda_jt}:1\le j\le k\}.\] With Lebesgue measure on \([-1,1]\), the squared norm of the evaluation functional at \(x\) is the Christoffel function \[\begin{align} \label{eq:christoffel-formula} \mathcal{K}_\Lambda(x) =\sup_{0\ne g\in E_\Lambda}\frac{|g(x)|^2}{\|g\|_{L^2[-1,1]}^2} =\nu(x)^*G^{-1}\nu(x)\,, \end{align}\tag{39}\] where \[G_{ab}=\int_{-1}^1 e^{i(\lambda_b-\lambda_a)t}dt=2\operatorname{sinc}(\lambda_b-\lambda_a), \qquad \nu_a(x)=e^{i\lambda_ax}\,.\] Indeed, \(c^*Gc=\|\sum_jc_je^{i\lambda_jt}\|_{L^2[-1,1]}^2\) and \(\sum_jc_je^{i\lambda_jx}=\nu(x)^\mathsf T c\); Cauchy–Schwarz in the \(G\)-inner product gives 39 , with equality at the kernel vector. Thus, Theorem 1 is equivalently a uniform outside-interval bound for the Christoffel function.
If the training distribution is the uniform probability measure \(\mu(dt)=\tfrac12\mathbf{1}_{[-1,1]}(t)dt\), the corresponding statistical leverage score is \(\tau_\Lambda^\mu(x)=2\mathcal{K}_\Lambda(x)\). Leverage-score sampling is a standard primitive for subspace embeddings and active least squares, and Fourier-sparse leverage bounds have been used for continuous sparse Fourier regression and kernel approximation [19], [36], [37]. Our contribution here is a uniform bound when the prediction point lies outside the support of the training distribution.
For the nonlinear class \(\mathcal{T}_k\), define the frequency-uniform exterior leverage relative to the averaged training norm by \[\tau_k(x):=\sup_{0\ne g\in\mathcal{T}_k} \frac{|g(x)|^2}{\mathbb{E}_{t\sim\mu}[|g(t)|^2]}\,.\] Squaring the endpoint estimate ?? gives an absolute constant \(C\) such that, for \(0\leq\delta\leq1\), \[\label{eq:outside-sensitivity-app} \tau_k(1+\delta)+\tau_k(-1-\delta) \leq Ck^2e^{Ck\sqrt\delta}\,.\tag{40}\]
For \(0\leq\Delta\leq1\), let \[\mathcal{X}_\Delta:=[1,1+\Delta]\cup[-1-\Delta,-1]\] be the adjacent exterior prediction region. Two related quantities arise. The integrated pointwise leverage envelope is \[\mathfrak L_k(\Delta):=\int_{\mathcal{X}_\Delta}\tau_k(x)\,dx = \int_{\mathcal{X}_\Delta}\sup_{0\ne g\in\mathcal{T}_k} \frac{|g(x)|^2}{\mathbb{E}_{t\sim\mu}[|g(t)|^2]}\,dx\,,\] whereas the actual worst-case \(L^2\) transfer constant is \[\mathfrak T_k(\Delta) :=\sup_{0\ne g\in\mathcal{T}_k} \frac{\displaystyle\int_{\mathcal{X}_\Delta}|g(x)|^2\,dx}{\displaystyle\mathbb{E}_{t\sim\mu}\left[|g(t)|^2\right]}\,.\] Since the pointwise maximizer in \(\tau_k(x)\) may depend on \(x\), these quantities need not be equal; one always has \(\mathfrak T_k(\Delta)\leq\mathfrak L_k(\Delta)\). The next proposition bounds both and proves sharpness for the actual transfer constant using a single sparse Fourier sum.
Proposition 13 (Exterior leverage and transfer at the Chebyshev scale). There are absolute constants \(c,C>0\) such that, for every \(k\geq2\) and \(0\leq\Delta\leq1\), \[\mathfrak T_k(\Delta) \leq \mathfrak L_k(\Delta) \leq C(1+k\sqrt\Delta)e^{Ck\sqrt\Delta}\,.\] Conversely, whenever \(k^{-2}\leq\Delta\leq1\), \[\mathfrak T_k(\Delta) \geq c\Delta e^{ck\sqrt\Delta}\,.\] Thus the exponential dependence \(\exp(\Theta(k\sqrt\Delta))\) is unavoidable, up to polynomial factors, for the true worst-case transfer from the training interval to the adjacent exterior region.
Proof. The inequality \(\mathfrak T_k(\Delta)\leq\mathfrak L_k(\Delta)\) follows by applying the definition of \(\tau_k(x)\) to a fixed \(g\) and then integrating. Integrating 40 and substituting \(y=k\sqrt u\) gives \[\mathfrak L_k(\Delta) \leq Ck^2\int_0^\Delta e^{Ck\sqrt u}\,du =2C\int_0^{k\sqrt\Delta}ye^{Cy}\,dy \leq C(1+k\sqrt\Delta)e^{Ck\sqrt\Delta}\,.\]
For the lower bound, let \(n=k-1\) and use the same confluent sequence as in the proof of Proposition 10: \[P_\varepsilon(t) =T_n\!\left(\frac{e^{i\varepsilon t}-1}{i\varepsilon}\right) \in\mathcal{T}_k\,.\] That proof shows that \(P_\varepsilon\to T_n\) uniformly on every compact real interval. Applying this convergence on \([-1-\Delta,1+\Delta]\) gives \[\mathfrak T_k(\Delta) \geq \lim_{\varepsilon\to0} \frac{\displaystyle\int_{\mathcal{X}_\Delta}|P_\varepsilon(x)|^2\,dx}{\displaystyle\mathbb{E}_{t\sim\mu}[|P_\varepsilon(t)|^2]} = \frac{\displaystyle\int_{\mathcal{X}_\Delta}|T_n(x)|^2\,dx}{\displaystyle\mathbb{E}_{t\sim\mu}[|T_n(t)|^2]}\,.\] The denominator is at most \(1\), since \(|T_n(t)|\leq1\) on \([-1,1]\). For \(u\in[\Delta/2,\Delta]\), Lemma 1 gives \(\operatorname{arcosh}(1+u)\geq\sqrt u\geq\sqrt{\Delta/2}\), and therefore \[|T_n(1+u)|^2 =\cosh^2\!\left(n\operatorname{arcosh}(1+u)\right) \geq\frac{1}{4}\exp\!\left(2n\operatorname{arcosh}(1+u)\right) \geq c e^{ck\sqrt\Delta}\,.\] Integrating over \(u\in[\Delta/2,\Delta]\), an interval of length \(\Delta/2\), proves \(\mathfrak T_k(\Delta)\geq c\Delta e^{ck\sqrt\Delta}\). ◻
The transfer constant gives the precise black-box implication from an in-domain regression guarantee to exterior prediction.
Corollary 2 (Black-box transfer from active regression to exterior prediction). Fix \(|\Lambda|\leq k\), and let \(g_\star,\widehat g\in E_\Lambda\). Then \[\int_{\mathcal{X}_\Delta}|\widehat g(x)-g_\star(x)|^2\,dx \leq \mathfrak T_k(\Delta)\, \mathbb{E}_{t\sim\mu}\!\left[|\widehat g(t)-g_\star(t)|^2\right].\] If \(g_\star\) and \(\widehat g\) are each \(k\)-sparse but may use different frequency sets, the same conclusion holds with \(\mathfrak T_{2k}(\Delta)\).
Proof. The difference \(h=\widehat g-g_\star\) belongs to \(E_\Lambda\subseteq\mathcal{T}_k\); apply the definition of \(\mathfrak T_k(\Delta)\). With unrelated supports, \(h\in\mathcal{T}_{2k}\). ◻
Consequently, any active or weighted least-squares algorithm that produces an in-domain error bound \[\mathbb{E}_{t\sim\mu}[|\widehat g(t)-g_\star(t)|^2] \leq\varepsilon_{\mathrm{train}}^2\] automatically gives exterior integrated error at most \(\mathfrak T_k(\Delta)\varepsilon_{\mathrm{train}}^2\), and the upper bound in Proposition 13 makes this guarantee explicit. For example, if a regression routine has the standard parametric risk \(O(\sigma^2k/m)\) after \(m\) noisy labels, then the same estimator has exterior risk at most \[O\!\left(\frac{\sigma^2k}{m}\,\bigl(1+k\sqrt\Delta\bigl)e^{Ck\sqrt\Delta}\right).\] The overhead is polynomial in \(k\) when \(k\sqrt\Delta=O(\log k)\), and it is constant at the natural edge width \(\Delta=O(k^{-2})\). Conversely, the lower bound for \(\mathfrak T_k(\Delta)\) is witnessed by one confluent Chebyshev sequence, rather than by an \(x\)-dependent family of pointwise extremizers. It therefore proves that any black-box implication based only on an in-domain \(L^2\)-error guarantee must incur super-polynomial amplification when \(k\sqrt\Delta/\log k\to\infty\) (in the regime \(\Delta\geq k^{-2}\)).
We thank Xue Chen for helpful discussion.
We used ChatGPT Pro 5.5 and Claude Opus 4.8 to assist with proving Theorem 1. We verified the correctness and wrote the proofs with suitable modifications for clarity. The authors assume responsibility for all content.
The direct filter theorem does not require the Chen–Price power-law parameter \(S\). For completeness, this appendix states two auxiliary comparisons used in Remark 12: the sharp peak-to-average scale and the best possible power-law encoding of the Chebyshev envelope.
Proposition 14 (Sharp peak-to-average ratio; cf.). For every \(T>0\) and every \(k\ge1\), \[k^2\;\le\; R_k:=\sup_{0\neq g\in\mathcal{T}_k} \frac{\sup_{t\in[-T,T]}|g(t)|^2}{\mathbb{E}_{t\in[-T,T]}|g(t)|^2} \;\le\;\frac{\pi^2}{4}\,k^2 .\]
The upper bound is essentially known: it is the energy bound of Kós [23], and it also follows, with the explicit constant \(\pi^2/4\), from the endpoint Nikolskii inequality of Denisov–Erdélyi quoted in Lemma 2. We record the short deduction together with the matching lower bound because the clustered-frequency analysis of [10] used \(R=O(k^3\log^2k)\), and the earlier interpolation analysis of [9] used \(R=O(k^4\log^3k)\).
Proof. The ratio is invariant under the change of variables \(t=Tu\), so take \(T=1\).
Upper bound: By ?? and \(\|g\|_{L^2[-1,1]}^2=2\,\mathbb{E}_{t\sim[-1,1]}\left[|g(t)|^2\right]\), \[\sup_{t\in[-1,1]}|g(t)|^2 \le\frac{\pi^2k^2}{8}\,\|g\|_{L^2[-1,1]}^2 =\frac{\pi^2k^2}{4}\,\mathbb{E}_{t\sim[-1,1]}\left[|g(t)|^2\right]\,.\]
Lower bound: Let \(P_m\) denote the Legendre polynomials, normalized by \(P_m(1)=1\) and \(\int_{-1}^1P_m^2=\frac{2}{2m+1}\), and let \[p^*(t):=\sum_{m=0}^{k-1}\frac{2m+1}{2}\,P_m(t)\] be the reproducing kernel of the polynomial space \(\Pi_{k-1}\) at the endpoint \(1\). Then \[p^*(1)=\sum_{m=0}^{k-1}\frac{2m+1}{2}=\frac{k^2}{2}, \qquad \|p^*\|_{L^2[-1,1]}^2=\sum_{m=0}^{k-1}\Bigl(\frac{2m+1}{2}\Bigr)^2\frac{2}{2m+1}=\frac{k^2}{2}\,.\] Thus, we have \[\begin{align} \frac{|p^*(1)|^2}{\mathbb{E}_{t\sim[-1,1]}\left[|p^*(t)|^2\right]}=\frac{k^4/4}{k^2/4}=k^2\,. \end{align}\] Now substitute as in the proof of Proposition 10: with \(w_\varepsilon(t)=(e^{i\varepsilon t}-1)/(i\varepsilon)\), the functions \(p^*(w_\varepsilon(\cdot))\in\mathcal{T}_k\) converge to \(p^*\) uniformly on \([-1,1]\) as \(\varepsilon\to0\), so their peak-to-average ratios converge to that of \(p^*\), which is at least \(k^2\). Hence, \(R_k\ge k^2\).
The proposition is then proved. ◻
Proposition 15 (Optimal power-law exponent). There are absolute constants \(B_0\ge1\) and \(C_1:=3\sqrt2\) such that for every \(k\ge2\), the power-law outside growth \[\label{eq:PG-template} |g(Tx)|^2\le k^B\,x^S\;\mathbb{E}_{u\sim[-T,T]}\left[|g(u)|^2\right], \qquad x\ge1,\quad g\in\mathcal{T}_k,\qquad{(14)}\] holds with \(B=B_0\) and \(S=4C_1^2\,k^2/\log k\).
Conversely, for every fixed \(B\) there are \(c_B>0\) and \(k_0(B)\) such that if ?? holds for some \(k\ge k_0(B)\), then \(S\ge c_B\,k^2/\log k\).
Remark 16. Under \(\mathrm{poly}(k)\) prefactors, the optimal power-law exponent is \(S=\Theta(k^2/\log k)\); in particular [10], which gives \(S=O(k^2\log k)\), improves by a factor \(\log^2k\), and no further improvement of the exponent is possible.
Proof. Take \(T=1\). We use the following elementary bounds: \[\begin{align} \log\cosh\rho\ge &~ \frac{\rho^2}{4} &&\qquad\forall 0\le\rho\le1\,,\tag{41}\\ \log\cosh\rho\ge &~ \frac{\rho}{4} &&\qquad \forall \rho\ge1\,,\tag{42}\\ \log\cosh\rho\le &~ \frac{\rho^2}{2} &&\qquad \forall\rho\ge0\,.\tag{43} \end{align}\] For 41 : \(\cosh\rho\ge1+\rho^2/2\) and \(\log(1+y)\ge y-y^2/2\) give \(\log\cosh\rho\ge\frac{\rho^2}{2}-\frac{\rho^4}{8}\ge\frac{\rho^2}{4}\) for \(\rho\le1\). For 42 : \(\cosh\rho\ge e^\rho/2\) gives \(\log\cosh\rho\ge\rho-\log2\ge(1-\log2)\rho\ge\rho/4\) for \(\rho\ge1\). For 43 : comparing Taylor coefficients, \((2\ell)!\ge2^\ell\,\ell!\) yields \(\cosh\rho\le e^{\rho^2/2}\).
Upper bound. Squaring 25 with \(x=\cosh \rho\), \(\rho>0\) gives \[\begin{align} |g(\cosh\rho)|^2\le C_0^2k^4e^{2C_1k\rho}\,\mathbb{E}_{u\sim[-1,1]}\left[|g(u)|^2\right]\,, \end{align}\] and \(C_0^2k^4\le k^{B_0-1}\) for an absolute constant \(B_0\) and all \(k\ge2\). It therefore suffices to show that, with \(S=4C_1^2k^2/\log k\), \[2C_1k\rho\;\le\;\log k+S\log\cosh\rho\qquad\forall\rho\ge0\,.\] For \(0\le\rho\le1\), by 41 and the AM–GM inequality, \[\log k+S\log\cosh\rho\ge\log k+\frac{S\rho^2}{4} \ge2\sqrt{\log k\cdot\frac{S\rho^2}{4}}=\sqrt{S\log k}\;\rho=2C_1k\rho .\] For \(\rho\ge1\), by 42 , \[S\log\cosh\rho\ge\frac{S\rho}{4}=\frac{C_1^2k^2}{\log k}\,\rho\ge2C_1k\rho,\] since \(C_1k/\log k\ge2\) for \(k\ge2\).
Lower bound. By Proposition 10 and \(\|g\|_{L^2[-1,1]}^2=2\,\mathbb{E}_{t\in[-1,1]}|g(t)|^2\), for every \(\rho\ge0\), \[\sup_{0\ne g\in\mathcal{T}_k}\frac{|g(\cosh\rho)|^2}{\mathbb{E}_{t\in[-1,1]}|g(t)|^2} \ge\frac{1}{4}\,e^{2(k-1)\rho} .\] If ?? holds, then for all \(\rho\in[0,1]\), using 43 , \[2(k-1)\rho-\log4\le B\log k+\frac{S\rho^2}{2} .\] Choose \(\rho=2(B+2)\log k/k\). For \(k\ge k_0(B)\), we have \(\rho\in [0,1]\) and \(2(k-1)\rho\ge k\rho=2(B+2)\log k\). Hence, for \(k\ge\max\{k_0(B),4\}\), \[\begin{align} \frac{S2^2(B+2)^2\log^2k}{2k^2} \ge &~ 2(B+2)\log k-B\log k-\log4\\ \ge &~ (2B+4-B-1)\log k=(B+3)\log k\,. \end{align}\] Therefore, \(S\ge\dfrac{(B+3)}{2(B+2)^2}\cdot\dfrac{k^2}{\log k}\).
The proposition is then proved. ◻
This appendix verifies that the window \(H_{k,T}\) from Theorem 11 can replace the filter used in the proof of [10]. Their argument needs the filter to satisfy the following conditions:
\(H_{k,T}\) preserves a constant fraction of the in-window signal energy while suppressing exterior energy (Lemma 1.6 in [10]);
\(|H_{k,T}(x)|\leq 1.01\) for any \(x\) (item (3) of Theorem 4.2 in [10]);
\(H_{k,T}\) can be efficiently evaluated at the queried points (implicitly used by line 5 of Algorithm 2 in [10]).
We will verify these conditions in this section: (1) will be verified in Lemma 8; (2) is already proved in Theorem 11; and (3) will be verified in Lemma 9. The only parameter that changes is the effective cluster half-width \(\Delta_*:=\Delta+C_\eta\frac{k^2}{T}\).
Lemma 8 (Energy preservation and concentration). Let \(H_{k,T}\) be the window from Theorem 11. Then, for every \(g\in \mathcal{T}_k\), \[\label{eq:CP-global-energy-conclusions} \begin{align} \int_{-T}^{T}|H_{k,T}(t)g(t)|^2\,dt\geq &~ (1-\sqrt\eta)^2\int_{-T}^{T}|g(t)|^2\,dt\,,\\ \int_{-T}^{T}|H_{k,T}(t)g(t)|^2\,dt\geq &~ \frac{(1-\sqrt\eta)^2}{(1-\sqrt\eta)^2+\eta} \int_{\mathbb{R}}|H_{k,T}(t)g(t)|^2\,dt\,. \end{align}\qquad{(15)}\] In particular, for sufficiently small fixed \(\eta\) (e.g., \(\eta\leq1/400\)), these imply the two constant-factor energy properties in [10].
Proof. Theorem 11 gives \[\underbrace{\int_{-T}^{T}|(1-H_{k,T}(t))g(t)|^2\,dt}_{E_{\rm defect}} +\underbrace{\int_{\mathbb{R}\setminus[-T,T]}|H_{k,T}(t)g(t)|^2\,dt}_{E_{\rm out}} \leq\eta\underbrace{\int_{-T}^{T}|g(t)|^2\,dt}_{E_0}.\] Let \[E_{\rm in}:=\int_{-T}^{T}|H_{k,T}(t)g(t)|^2\,dt.\] The triangle inequality in \(L^2[-T,T]\) implies \[E_{\rm in}^{1/2} \geq E_0^{1/2}-E_{\rm defect}^{1/2} \geq(1-\sqrt\eta)E_0^{1/2},\] and hence \[E_{\rm in}\geq(1-\sqrt\eta)^2E_0, \qquad \frac{E_{\rm in}}{E_{\rm in}+E_{\rm out}} \geq\frac{(1-\sqrt\eta)^2}{(1-\sqrt\eta)^2+\eta}\,,\] which give ?? in the lemma. ◻
Lemma 9 (Efficient evaluation). For every fixed \(\eta\), the window \(H_{k,T}\) can be evaluated at every queried point in the algorithm in [10] to the required constant relative accuracy in \(\operatorname{poly}(k)\) arithmetic time per query.
Proof. By scaling, it is enough to take \(T=1\). In the notation of the proof of Theorem 11, \[H_{A,B}(t) =\frac{\displaystyle\int_{t-1}^{t+1}\Psi_{A,B}(u)\,du}{\displaystyle\int_{\mathbb{R}}\Psi_{A,B}(u)\,du} = \int_{t-1}^{t+1}K_{A,B}(u)\,du\,, \qquad B=\Theta_\eta(k^2)\,,\] where \(\Psi_{A,B}\) is the product of \(O(\log k)\) even powers of \(\operatorname{sinc}\) functions in 27 . The Chen–Price phase test queries the window only within \(O(1/k^2)=O(1/B)\) of \([-1,1]\), because \(|\beta|\leq\gamma/\Delta_*\) and \(\Delta_*\geq c_\eta k^2\) after normalization. Decreasing the fixed constant \(\gamma\), these points satisfy \(|t|\leq1+a/B\) for a sufficiently small constant \(a>0\).
On the query region, \(H_{A,B}\) is uniformly bounded away from zero. Indeed, \(K_{A,B}\) is a nonnegative even probability density. Thus, it suffices to consider \(0\leq t\leq1+a/B\). If \(0\leq t\leq1\), then \([0,1]\subseteq[t-1,t+1]\), and therefore \[H_{A,B}(t) \geq \int_0^1K_{A,B}(u)\,du =\int_0^\infty K_{A,B}(u)\,du - \int_1^\infty K_{A,B}(u)\,du = \frac{1}{2}-P_{A,B}(1)\,.\] If \(t=1+r\) with \(0\leq r\leq a/B\), then \[\begin{align} H_{A,B}(1+r) &= \int_r^{2+r}K_{A,B}(u)\,du\\ &= \frac{1}{2} -\int_0^rK_{A,B}(u)\,du -P_{A,B}(2+r)\\ &\geq \frac{1}{2} -\frac{a}{B}\|K_{A,B}\|_{L^\infty} -P_{A,B}(1). \end{align}\] Since \(0\leq\Psi_{A,B}\leq1\) and 29 , we have \[\|K_{A,B}\|_{L^\infty} \leq Z_{A,B}^{-1} \leq C_AB\,.\] Consequently, for any \(|t|\leq 1+\frac{a}{B}\), \[H_{A,B}(t) \geq \frac{1}{2}-C_Aa-P_{A,B}(1)\,.\] Choose \(a>0\) so that \(C_Aa\leq1/8\), and then choose the constant in \(B=\Theta_\eta(k^2)\) sufficiently large such that by 30 , \[P_{A,B}(1) \leq C_Ae^{-cA\sqrt B} \leq \frac{1}{8}\,.\] Hence, \[H_{A,B}(t)\geq\frac{1}{4}\] throughout the query region.
Furthermore, \[\left|\Psi_{A,B}'(u)\right|\leq \frac{1}{2}\sum_{j=0}^{J}m_j\omega_j\leq C_AB\] provides an explicit Lipschitz constant for the integrand. Hence, on an interval of length \(L\), a composite rectangle rule with step size \(h\) has an error of at most \(C_ABLh\). For \(Z_{A,B}\), the tail estimates 30 and 31 first reduce the integral over \(\mathbb{R}\) to an integral over a bounded interval. Choosing \(h=C_A\rho/B^2\) then approximates both the numerator and the denominator to additive-error \(C_A\rho/B\), using \(\operatorname{poly}(B,1/\rho)\) arithmetic operations. By 29 , these additive-error approximations give the desired \(O(\rho)\) relative-error approximation for \(H_{A,B}(t)\).
Finally, we note that a sufficiently small constant \(\rho\) relative-error changes all importance-weighted energies by a \(1+O(\rho)\) factor and perturbs the phase-difference signal by \(O(\rho)\|y_H\|_2\). These errors are absorbed by the constant slack in [10]. Rescaling proves the lemma for general \(T\). ◻
The extension is simply the defining formula \(\sum a_je^{i\mu_jt}\) read for \(t\in\mathbb{C}\).↩︎