A Sharp Fourier Inequality
and the Epanechnikov Kernel

Sean Richardson Sean Richardson, Department of Mathematics, University of Washington, Seattle, WA [email protected]

Abstract.

We consider functions $f:\mathbb{Z}\to\mathbb{R}$ and kernels $u:\{-n,\cdots,n\}\to\mathbb{R}$ normalized by $\sum_{\ell=-n}^{n}u(\ell)=1$ , making the convolution $u\ast f$ a “smoother” local average of $f$ . We identify which choice of $u$ most effectively smooths the second derivative in the following sense. For each $u$ , basic Fourier analysis implies there is a constant $C(u)$ so $\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}\leq C(u)\|f\|_{\ell^{2}(\mathbb{Z})}$ for all $f:\mathbb{Z}\to\mathbb{R}$ . By compactness, there is some $u$ that minimizes $C(u)$ and in this paper, we find explicit expressions for both this minimal $C(u)$ and the minimizing kernel $u$ for every $n$ . The minimizing kernel is remarkably close to the Epanechnikov kernel in Statistics. This solves a problem of Kravitz-Steinerberger and an extremal problem for polynomials is solved as a byproduct.

1. Introduction

We are interested in the study of functions $f:\mathbb{Z}\rightarrow\mathbb{R}$ . These functions appear naturally in many applications (for example as “time series”) and a natural problem that arises frequently is to take local averages at a fixed, given scale. A popular way is to fix a kernel $u:\{-n,-n+1,\cdots,n-1,n\}\to\mathbb{R}$ and consider the convolution

(u\ast f)(k)=\sum_{\ell=-n}^{n}u(\ell)f(k-\ell).

A natural question is now which kernel $u:\{-n,\cdots,n\}\to\mathbb{R}$ one should pick. We will always assume that the kernel is normalized $\sum_{\ell=-n}^{n}u(\ell)=1$ so that the convolution $u\ast f$ is indeed a local average. There is no “right choice” of a kernel $u$ as different choices of weights are optimal in different ways. For example, in image processing theory [16] one is interested in kernels $u$ so that for any $f$ , the convolution $u\ast f$ has fewer local extrema than $f$ ; this property together with the other “scale-space axioms” uniquely characterizes the Gaussian kernel [1, 12, 23]. In kernel density estimation, one is interested in a kernel that minimizes least-squared error, which uniquely characterizes the Epanechnikov kernel [7]. In this paper, we build on the work of Kravitz and Steinerberger [15] and take the approach of asking that the convolution $u\ast f$ be as smooth as possible, which we show uniquely characterizes yet another kernel in the second derivative case.

To make this precise, first define the discrete derivative $Df:\mathbb{Z}\rightarrow\mathbb{R}$ by $Df(k)=f(k+1)-f(k)$ and define higher-order derivatives inductively by $D^{m}f=D(D^{m-1}f)$ . Then it follows from basic Fourier analysis (see Section 3.3) that for every kernel $u:\{-n,\cdots,n\}\to\mathbb{R}$ and every $m\in\mathbb{N}$ , there exists a constant $C_{m}(u)<\infty$ so that

\forall~{}f\in\ell^{2}(\mathbb{Z}),\qquad\|D^{m}(u\ast f)\|_{\ell^{2}(\mathbb{Z})}\leq C_{m}(u)\|f\|_{\ell^{2}(\mathbb{Z})}.

We can now ask a natural question.

Question. Given a positive integer $m$ , how small can $C_{m}(u)$ be and which convolution kernels $u$ attain the optimal constant?

Such a kernel would then be the “canonical” kernel producing the smallest $m$ th derivatives and is a natural candidate for use in practice. The problem has been solved by Kravitz and Steinerberger when $m=1$ .

Theorem (Kravitz-Steinerberger [15]).

For any normalized $u:\{-n,\cdots,n\}\to\mathbb{R}$ ,

C_{1}(u)\geq\frac{2}{2n+1}

with equality if and only if $u(k)=1/(2n+1)$ is the constant kernel.

That is, averaging by convolving with the characteristic function of an interval best minimizes the first derivative. Kravitz and Steinerberger also studied the $m=2$ case under the assumption $u$ has non-negative Fourier transform.

Theorem (Kravitz-Steinerberger [15]).

For any normalized $u:\{-n,\cdots,n\}\to\mathbb{R}$ with nonnegative Fourier transform,

C_{2}(u)\geq\frac{4}{(n+1)^{2}}

with equality if and only if $u$ is the triangle function $u(k)=(n+1-|k|)/(n+1)^{2}.$

The main result of this paper resolves the $m=2$ case without additional assumptions on the kernel, providing the optimal constant and optimal kernel for all $n$ .

Theorem (Main Result).

For any normalized $u:\{-n,\cdots,n\}\to\mathbb{R},$

C_{2}(u)\geq\frac{4}{n+1}\frac{\sin(\frac{\pi}{2n+2})}{1+\cos(\frac{\pi}{2n+2})}

with equality if and only if $u$ is given by the kernel in (3).

A quick computation shows the optimal kernels $u_{n}:\{-n,\cdots,n\}\to\mathbb{R}$ satisfy, as $n\to\infty$ , the following asymptotic equivalence; notice the asymptotic improvement from $4$ to $\pi$ when removing the nonnegative Fourier transform restriction:

(1)

C_{2}(u_{n})\sim\frac{\pi}{(n+1)^{2}}.

The optimal kernel $u_{n}$ for each $n$ is given as an integral expression by (3) in the following section, and Figure 1 pictures the optimal kernels $u_{10}$ and $u_{1000}$ . Figure 2 depicts a time series function $f:\mathbb{Z}\to\mathbb{R}$ encoding the water level of Lake Chelan over a two week period as well as the smoothed data $u_{10}\ast f$ . Notice this smoothing reduces noise and clarifies long-term trends.

As seen in Figure 1, the optimal kernel resembles a parabola, but it turns out the points do not quite lie on any parabola. However, choosing weights by sampling from a parabola results in the discrete Epanechnikov kernel $E_{n}$ for each $n$ , which is a simple and effective approximation of the optimal kernel. Indeed, we show the parabolic Epanechnikov kernel has constant $C_{2}(E_{n})$ within $2\%$ of the optimal constant $C_{2}(u_{n})$ for large $n$ , providing a new reason to use the Epanechnikov kernel.

2. Results

2.1. A Sharp Fourier Inequality

We can rewrite the main result discussed in the Introduction as the following Fourier inequality. As usual, we only consider kernels $u:\{-n,-n+1,\cdots,n-1,n\}\to\mathbb{R}$ normalized so that $\sum_{\ell=-n}^{n}u(\ell)=1$ .

Theorem 1 (Main Result, restated).

For any normalized $u:\left\{-n,\dots,n\right\}\rightarrow\mathbb{R}$ ,

(2)

\sup_{0\neq f\in\ell^{2}(\mathbb{Z})}\frac{\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}\geq\frac{4}{n+1}\cdot\frac{\sin\left(\frac{\pi}{2n+2}\right)}{1+\cos\left(\frac{\pi}{2n+2}\right)}.

With equality if and only if $u(k)$ is as in (3).

Note the discrete Laplacian $(\Delta f)(k)\coloneqq f(k+2)-2f(k+1)+f(k)$ is precisely the discrete second derivative $(D^{2}f)(k)$ defined in the Introduction. The optimal $u_{n}:\{-n,\cdots,n\}\to\mathbb{R}$ that yields equality in Theorem 1 for any $n$ can be written explicitly by defining $u_{n}$ to be symmetric $u_{n}(k)=u_{n}(-k)$ , then for $k\geq 0$ setting

(3)

u_{n}(k)=\frac{1}{\pi}\int_{-1}^{1}S_{n}(x)T_{k}(x)\frac{dx}{\sqrt{1-x^{2}}}

where $T_{k}(x)$ is the $k$ th Chebyshev polynomial (as defined in Section 3.1), and

(4)

S_{n-1}(x)=\frac{1}{x-1}\cdot\frac{2\sin\left(\frac{\pi}{2n}\right)}{n\left(1+\cos\left(\frac{\pi}{2n}\right)\right)}\cdot T_{n}\left(\frac{1+\cos\left(\frac{\pi}{2n}\right)}{2}(x+1)-1\right).

This result extends the work of Kravitz and Steinerberger [15] and adds to the recent research activity on sharp Fourier inequalities. For example, there is current research on sharp Fourier restriction and extension inequalities [5, 4, 17, 19, 20], on sharp Strichartz inequalities [8, 11], on sharp Hausdorff-Young inequalities [13, 14], and other Fourier inequalities [2, 3, 6, 9]

2.2. The Epanechnikov Kernel

The optimal kernel $u_{n}$ has a complicated expression as given in (3). However, as seen in Figure 1, this optimal $u_{n}$ resembles a parabola, and conversely we find that choosing weights by sampling from a parabola does extraordinarily well in smoothing the Laplacian of a given function. This choice of weights yields the discrete normalized Epanechnikov kernel $E_{n}:\{-n,\cdots,n\}\to\mathbb{R}$ defined by

(5)

E_{n}(k)=\frac{3}{n(4n^{2}-1)}\left(n^{2}-k^{2}\right).

The Epanechnikov kernel is widely used [10, 18, 22] in both theory and applications. This popularity stems from its computational efficiency and from Epanechnikov’s proof [7] that it is the optimal kernel to use in kernel density estimation (KDE) in terms of minimizing expected mean integrated square error. The following theorem reveals the Epanechnikov kernel is less than 2% worse than optimal in smoothing the Laplacian, providing another reason to use the Epanechnikov kernel in practice.

Theorem 2.

Let $\mu$ be as in (6). Then as $n\to\infty$ we get the asymptotic equivalence

\sup_{0\neq f\in\ell^{2}(\mathbb{Z})}\frac{\|\Delta(E_{n}\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}\sim\frac{3\mu}{\pi}\cdot\frac{\pi}{n^{2}}.

The constant $3\mu/\pi$ in the above theorem is a universal constant defined by

(6)

\frac{3\mu}{\pi}\coloneqq\frac{3}{\pi}\max_{\alpha\in[0,16]}\left|\frac{\sin\alpha}{\alpha}-\cos{\alpha}\right|\approx 1.015.

Comparing Theorem 1, whose asymptotics are given by (1), and the statement of Theorem 2 reveals the asymptotics of $C_{2}(u_{n})$ and $C_{2}(E_{n})$ differ only by a factor of $3\mu/\pi\approx 1.015$ as $n\to\infty$ . Hence the Epanechnikov kernel performs less than $2\%$ worse than optimal asymptotically.

2.3. A Sharp Polynomial Inequality

After taking a Fourier transform (see Section 3.3), Theorem 1 reduces to the following claim about polynomials, which is interesting in its own right.

Theorem 3.

Let $p(x)$ be a polynomial of degree at most $n-1$ with $p(1)=1$ . Then

\max_{x\in[-1,1]}|(1-x)p(x)|\geq\frac{2\sin\left(\frac{\pi}{2n}\right)}{n\left(1+\cos\left(\frac{\pi}{2n}\right)\right)}

with equality if and only if $p(x)=S_{n-1}(x)$ where $S_{n-1}(x)$ is given in (4).

3. Proofs

3.1. A Sharp Polynomial Inequality

This section proves Theorem 3, which is the key to the proof of Theorem 1 and the formula for the optimal kernel given in (3). This proof makes heavy use Chebyshev polynomials, so we first recall some facts about Chebyshev polynomials for the convenience of the reader.

Chebyshev polynomials are a family $\{T_{n}(x)\}$ of polynomials defined by declaring $T_{0}(x)=1$ and $T_{1}(x)=x$ , then defining the rest with the recurrence

T_{n+1}(x)=2xT_{n}(x)-T_{n-1}(x).

A quick induction argument reveals Chebyshev polynomials also satisfy

(7)

T_{n}(\cos\theta)=\cos(n\theta).

The above relation is responsible for many nice properties of Chebyshev polynomials and so we typically consider Chebyshev polynomials $T_{n}(x)$ over the domain $[-1,1]$ where this formula can apply. This relation also reveals the zeroes of the Chebyshev polynomial $T_{n}(x)$ are located at $\cos\left(\frac{\pi}{n}(k+\frac{1}{2})\right)$ for $k\in\mathbb{Z}$ . By taking the derivative of both sides of (7), we find that the derivative $T_{n}^{\prime}(x)$ of Chebyshev polynomials over $[-1,1]$ can be written $T_{n}^{\prime}(x)=nU_{n-1}(x)$ for some polynomial $U_{n-1}(x)$ that satisfies $U_{n-1}(\cos(\theta))\sin\theta=\sin(n\theta)$ . These polynomials $\{U_{n}(x)\}$ are called Chebyshev polynomials of the second kind. Finally, due to (7), each Chebyshev polynomial $T_{n}(x)$ satisfies the equioscillation property, meaning there exists $n+1$ extrema $1=x_{0}>x_{1}>\cdots>x_{n}=-1$ so that $T_{n}(x_{i})=(-1)^{i}$ .

We are now equipped to prove Theorem 3. The equation defining the optimal polynomial $S_{n-1}(x)$ is long, but the idea behind its construction is a simple modification of Chebyshev polynomials. To construct a degree $n$ function $(1-x)p(x)$ that stays minimal over $[-1,1]$ , we slightly stretch the Chebyshev polynomial $T_{n}(x)$ to the function $q_{n}(x)$ so that $q_{n}(1)=0$ and $q_{n}^{\prime}(1)=-1$ . Then defining $S_{n}(x)=q_{n}(x)/(1-x)$ provides the minimal degree $n-1$ polynomial that satisfies the necessary conditions.

Proof of Theorem 3.

We start by verifying the claimed optimal polynomial $S_{n-1}(x)$ fulfills the restrictions and satisfies the claimed inequality for any positive integer $n$ . We denote $(1-x)S_{n-1}(x)$ by $q_{n}(x)$ and observe $q_{n}(x)=-\alpha T_{n}(L(x))$ is a scaled and stretched Chebyshev polynomial for carefully chosen constant $\alpha$ and linear change of variables $L(x)$ :

\displaystyle\alpha=\frac{2\sin\left(\frac{\pi}{2n}\right)}{n\left(1+\cos\left(\frac{\pi}{2n}\right)\right)}\quad\text{and}\quad L(x)=\frac{1+\cos\left(\frac{\pi}{2n}\right)}{2}(x+1)-1.

Writing $q_{n}(x)=-\alpha T_{n}(L(x))$ immediately reveals $q_{n}(x)$ is a polynomial of order $n$ . The change of variables $L(x)$ is designed so we have

q_{n}(1)=-\alpha T_{n}(L(1))=-\alpha T_{n}\left(\cos\left(\frac{\pi}{2n}\right)\right)=0,

using that $\cos\left(\frac{\pi}{2n}\right)$ is a zero of the Chebyshev polynomial $T_{n}(x)$ . Thus we have $S_{n-1}(x)=q_{n}(x)/(1-x)$ is a well-defined polynomial of order $n-1$ as claimed. Next we show $S_{n-1}(1)=1$ . First observe $S_{n-1}(1)=-q_{n}^{\prime}(1)$ and now compute

	$\displaystyle S_{n-1}(1)$	$\displaystyle=-q_{n}^{\prime}(1)=-\left.\frac{d}{dx}\right\|_{x=1}(-\alpha T_{n}(L(x)))$
		$\displaystyle=\alpha L^{\prime}(1)T_{n}^{\prime}(L(1))=\alpha\frac{n}{2}\left(1+\cos\left(\frac{\pi}{2n}\right)\right)U_{n-1}\left(\cos\left(\frac{\pi}{2n}\right)\right)$

where we used $T_{n}^{\prime}(x)=nU_{n-1}(x)$ for $U_{n-1}(x)$ the Chebyshev polynomial of the second kind with order $n-1$ . Recall $U_{n-1}(\cos\theta)=\sin(n\theta)/\sin(\theta)$ and therefore, continuing our computation, we see the constant $\alpha$ is chosen so that we get

\displaystyle S_{n-1}(1)=\alpha\cdot\frac{n}{2}\cdot\frac{1+\cos\left(\frac{\pi}{2n}\right)}{\sin\left(\frac{\pi}{2n}\right)}=\alpha\cdot\alpha^{-1}=1.

Therefore $S_{n-1}(x)$ fulfills the necessary conditions. To verify $S_{n-1}(x)$ satisfies the equality, use $L([-1,1])\subset[-1,1]$ and that $|T_{n}(y)|\leq 1$ on $[-1,1]$ to see

	$\displaystyle\max_{x\in[-1,1]}\|(1-x)S_{n-1}(x)\|$	$\displaystyle=\max_{x\in[-1,1]}\|q_{n}(x)\|$
		$\displaystyle=\max_{x\in[-1,1]}\|\alpha T_{n}(L(x))\|\leq\alpha\max_{y\in[-1,1]}\|T_{n}(y)\|\leq\alpha.$

This is indeed an equality because

\displaystyle\max_{x\in[-1,1]}|(1-x)S_{n-1}(x)|\geq|\alpha T_{n}(L(-1))|=\alpha\cdot|T_{n}(-1)|=\alpha.

We now show $S_{n-1}(x)$ is the unique polynomial of degree at most $n-1$ that achieves this equality by deriving an equioscillation property for $q_{n}(x)$ and modifying the standard argument for the minimizing property of Chebyshev polynomials. Recall the Chebyshev polynomial $T_{n}(x)$ has $n+1$ extrema $1=x_{0}>x_{1}>\cdots>x_{n}=-1$ so that the equioscillation property $T_{n}(x_{i})=(-1)^{i}$ is satisfied. To see $q_{n}(x)$ has a similar equioscillation property, define inputs $y_{i}=L^{-1}(x_{i})$ for $0\leq i\leq n$ , and observe $y_{0}\geq\cdots\geq y_{n}$ by $L^{-1}(x)$ strictly increasing. Next, note the second extrema of Chebyshev polynomials is given by $x_{1}=\cos\left(\frac{\pi}{n}\right)$ and so $x_{1}<\cos\left(\frac{\pi}{2n}\right)$ ; thus by $L^{-1}(x)$ strictly increasing, $y_{1}=L^{-1}(x_{1})<L^{-1}(\cos\left(\frac{\pi}{2n}\right))=1$ . Now compute $L(-1)=-1$ , which implies $L^{-1}(-1)=-1$ . Therefore we find the inputs $y_{i}$ satisfy $1>y_{1}\geq\cdots\geq y_{n}=-1$ , and $q_{n}(y_{i})=-\alpha T_{n}(L(y_{i}))=-\alpha T_{n}(x_{i})=-\alpha(-1)^{i}$ . That is, $q_{n}(x)$ has $n$ maxima satisfying the equioscillation property in $[-1,1]$ . Next suppose $p(x)$ is any polynomial of degree $n-1$ so that $p(1)=0$ and

\max_{x\in[-1,1]}|(1-x)p(x)|\leq\alpha.

We argue $p(x)=S_{n-1}(x)$ by using our equioscillation property to show the polynomials must intersect sufficiently many times. Formally, we count the zeros of the polynomial $z(x)=q_{n}(x)-(1-x)p(x)$ . By our equioscillation property $q_{n}(y_{i})=-\alpha(-1)^{i}$ and the assumption $|(1-x)p(x)|\leq\alpha$ over $[-1,1]$ , we require $z(y_{i})\geq 0$ for $i$ odd and $z(y_{i})\leq 0$ for $i$ even. Therefore $z(x)$ must have a zero in each interval $[y_{i},y_{i+1}]$ by the intermediate value theorem. That is, the $n-1$ intervals $[y_{1},y_{2}],\cdots,[y_{n-1},y_{n}]$ all contain a zero. Furthermore if any two intervals $[y_{i-1},y_{i}]$ and $[y_{i},y_{i+1}]$ share a zero at $y_{i}$ , then we can show $z(x)$ will have a zero of multiplicity at least two at $y_{i}$ and therefore $z(x)$ still has at least $n-1$ zeros counted with multiplicity on $[y_{0},y_{n-1}]$ as follows. By $q_{n}(y_{i})=\pm\alpha$ at $y_{i}$ , we know $q_{n}(x)$ has a minimum or maximum at $y_{i}$ , implying $q_{n}^{\prime}(y_{i})=0$ . Similarly, if $z(y_{i})=0$ , then $(1-y_{i})p(y_{i})=\pm\alpha$ and so we also find that $(1-x)p(x)$ has a minimum or maximum at $y_{i}$ , so $\left.\frac{d}{dx}\right|_{y_{i}}(1-x)p(x)=0$ . Therefore $z^{\prime}(y_{i})=q_{n}^{\prime}(y_{i})-\left.\frac{d}{dx}\right|_{y_{i}}(1-x)p(x)=0$ and so $z(x)$ indeed has a zero of multiplicity at least two at $y_{i}$ and so $z$ has $n-1$ zeros on $[-1,1)$ .

Now note $z(1)=q_{n}(1)-(1-1)p(1)=0-0=0$ and so $z(x)/(1-x)$ is a polynomial of degree $n-1$ with the same roots on $[-1,1)$ . Additionally observe

\frac{z(x)}{1-x}=\frac{q_{n}(x)-(1-x)p(x)}{1-x}=S_{n-1}(x)-p(x)

and therefore, evaluating $z(x)/(1-x)$ at $1$ reduces to $S(1)-p(1)=1-1=0$ and so $z(x)/(1-x)$ has $n$ roots. However because $z(x)/(1-x)$ is of degree $n-1$ this implies $z(x)/(1-x)$ is the zero polynomial. That is, $p(x)=S_{n-1}(x)$ . ∎

3.2. Reduction to symmetric kernels

Our Fourier analysis argument for Theorem 1 given in Section 3.3 only holds for symmetric kernels, satisfying $u(k)=u(-k)$ . Luckily, the following lemma demonstrates that it is sufficient to only prove Theorem 1 for the class of symmetric normalized kernels.

Lemma 4.

Suppose for all symmetric and normalized kernels $u:\{-n,\cdots,n\}\to\mathbb{R}$ ,

(8)

\sup_{f\neq 0}\frac{\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}\geq\beta_{n}

for some $\beta_{n}>0$ . Then (8) holds for all normalized kernels $u:\{-n,\cdots,n\}\to\mathbb{R}$ .

Proof.

Let $u:\{-n,\cdots,n\}\to\mathbb{R}$ be any kernel normalized by $\sum_{k=-n}^{n}u(k)=1$ . For any function $g(k)$ , define its reflection $g^{-}(k)=g(-k)$ . Next consider the symmetrization kernel $\widetilde{u}(k)=\frac{1}{2}(u(k)+u^{-}(k))$ , which will also satisfy $\sum_{k=-n}^{n}\widetilde{u}(k)=1$ . Now take any $f\in\ell^{2}(\mathbb{Z})$ and compute

	$\displaystyle\frac{\\|\Delta(\widetilde{u}\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}$	$\displaystyle=\frac{\\|\Delta(\frac{1}{2}(u+u^{-})\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}$
		$\displaystyle\leq\frac{1}{2}\left(\frac{\\|\Delta(u\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}+\frac{\\|\Delta(u^{-}\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}\right)$
		$\displaystyle=\frac{1}{2}\left(\frac{\\|\Delta(u\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}+\frac{\\|\Delta(u\ast f^{-})\\|_{\ell^{2}(\mathbb{Z})}}{\\|f^{-}\\|_{\ell^{2}(\mathbb{Z})}}\right).$

Therefore we find that for all $f\in\ell^{2}(\mathbb{Z})$ , either

\frac{\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}\geq\frac{\|\Delta(\widetilde{u}\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}\quad\text{or}\quad\frac{\|\Delta(u\ast f^{-})\|_{\ell^{2}(\mathbb{Z})}}{\|f^{-}\|_{\ell^{2}(\mathbb{Z})}}\geq\frac{\|\Delta(\widetilde{u}\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}.

Hence we can conclude

\displaystyle\sup_{f\neq 0}\frac{\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}\geq\sup_{f\neq 0}\frac{\|\Delta(\widetilde{u}\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}\geq\beta_{n}.

∎

3.3. From discrete kernels to polynomial extremizers

Lemma 5 (Kravitz and Steinerberger [15]).

Given a symmetric and normalized kernel $u:\{-n,\cdots,n\}\to\mathbb{R}$ , define the polynomial

\displaystyle p_{u}(x)=u(0)+\sum_{k=1}^{n}2u(k)T_{k}(x)

where $T_{k}(x)$ is the $k$ th Chebyshev polynomial. Then,

\displaystyle\sup_{0\neq f\in\ell^{2}(\mathbb{Z})}\frac{\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}=2\max_{-1\leq x\leq 1}|(1-x)p_{u}(x)|.

For the proof of Lemma 5 we follow the argument given by Kravitz and Steinerberger [15], which uses the Fourier transform and Plancherel’s theorem. Before the proof, first recall that a function $f:\mathbb{Z}\to\mathbb{R}$ on the integers has a continuous Fourier transform $\widehat{f}:\mathbb{T}\to\mathbb{C}$ defined on the 1-torus given by

\displaystyle\widehat{f}(\xi)=\sum_{k\in\mathbb{Z}}f(k)e^{-i\xi k}.

This is called the discrete-time Fourier transform, which we will also denote by $\mathcal{F}(f)(\xi)=\widehat{f}(\xi)$ . This Fourier transform takes convolution to multiplication by

\displaystyle\widehat{f\ast g}=\widehat{f}\cdot\widehat{g}.

Another useful property is the Plancherel identity, which relates the inner product of functions with that of their Fourier transform by

\displaystyle\sum_{k\in\mathbb{Z}}f(k)\overline{g(k)}=\frac{1}{2\pi}\int_{\mathbb{T}}\widehat{f}(\xi)\overline{\widehat{g}(\xi)}d\xi.

Note we can express the Fourier transform of a shifted function $f(\cdot-m)$ by

	$\displaystyle\widehat{f(\cdot-m)}(\xi)$	$\displaystyle=\sum_{k\in\mathbb{Z}}f(k-m)e^{-i\xi k}=\sum_{k\in\mathbb{Z}}f(k)e^{-i\xi(k+m)}$
		$\displaystyle=e^{-i\xi m}\sum_{k\in\mathbb{Z}}f(k)e^{-i\xi k}=e^{-i\xi m}\widehat{f}(\xi).$

Using the above, we can compute the Fourier transform of the discrete Laplacian.

	$\displaystyle\mathcal{F}(\Delta f)(\xi)$	$\displaystyle=\mathcal{F}(f(k+2)-2f(k+1)+f(k))(\xi)$
		$\displaystyle=(e^{-2i\xi}\widehat{f}(\xi)-2e^{-i\xi}\widehat{f}(\xi)+\widehat{f}(\xi)=(e^{-i\xi}-1)^{2}\widehat{f}(\xi).$

We are equipped to prove Lemma 5, but first we follow up with a claim made in the Introduction. Indeed, observe that by the first computation in the following proof, which does not yet use the symmetry of $u$ , we can conclude quickly that $\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}\leq C_{2}(u)\|f\|_{\ell^{2}(\mathbb{Z})}$ for some constant $C_{2}(u)$ depending continuously on $u$ . Furthermore, because the space of normalized kernels ${u:\{-n,\cdots,n\}\to\mathbb{R}}$ is compact, we conclude that there exists some optimal kernel $u_{n}$ that minimizes $C_{2}(u)$ . This argument can be easily generalized to higher derivatives.

Proof of Lemma 5.

Let $u$ be a fixed symmetric, normalized kernel and let $f:\mathbb{Z}\to\mathbb{R}$ be any function in $\ell^{2}(\mathbb{Z})$ . Plancherel’s identity allows us to equate $\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}$ to an easier expression in terms of the Fourier transform by computing

	$\displaystyle\sum_{k\in\mathbb{Z}}\|(\Delta(u\ast f))(k)\|^{2}$	$\displaystyle=\frac{1}{2\pi}\int_{\mathbb{T}}\|e^{-i\xi}-1\|^{4}\|\widehat{u}(\xi)\|^{2}\|\widehat{f}(\xi)\|^{2}d\xi$
(9)			$\displaystyle\leq\\|(e^{-i\xi}-1)^{4}\widehat{u}(\xi)^{2}\\|_{L^{\infty}(\mathbb{T})}\cdot\frac{1}{2\pi}\int_{\mathbb{T}}\|\widehat{f}(\xi)\|^{2}d\xi$
		$\displaystyle=\\|(e^{-i\xi}-1)^{4}\widehat{u}(\xi)^{2}\\|_{L^{\infty}(\mathbb{T})}\cdot\sum_{k\in\mathbb{Z}}\|f(k)\|^{2}.$

After taking a square root we get

\displaystyle\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}\leq\|(e^{-i\xi}-1)^{2}\widehat{u}(\xi)\|_{L^{\infty}(\mathbb{T})}\cdot\|f\|_{\ell^{2}(\mathbb{Z})}

Note that the only inequality in the derivation of the above is in (9). Furthermore, by choosing $f(k)$ so that $\widehat{f}(\xi)$ has $L^{2}$ mass concentrated at the $\xi$ in which the function $|e^{-i\xi}-1|^{4}|\widehat{u}(\xi)|^{2}$ achieves it’s maximum, we can make the above inequality arbitrary close to an equality. Thus we have shown our expression measuring the smoothing of the second derivative is equivalent to the following simpler expression:

\displaystyle\sup_{0\neq f\in\ell^{2}(\mathbb{Z})}\frac{\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}=\|(e^{-i\xi}-1)^{2}\widehat{u}(\xi)\|_{L^{\infty}(\mathbb{T})}.

Denote this simpler expression by

\displaystyle L(u)\coloneqq\|(e^{i\xi}-1)^{2}\widehat{u}(\xi)\|_{L^{\infty}(\mathbb{T})}=\max_{\xi\in[0,2\pi)}|e^{i\xi}-1|^{2}|\widehat{u}(\xi)|.

Because $u(k)$ is symmetric, real-valued, and only supported on $\{-n,\cdots,n\}$ , we can rewrite $\widehat{u}(\xi)$ by

\displaystyle\widehat{u}(\xi)=\sum_{k\in\mathbb{Z}}u(k)e^{-i\xi k}=u(0)+2\sum_{k=1}^{n}u(k)\cos(\xi k).

Therefore we find

\displaystyle L(u)=\max_{\xi\in[0,2\pi)}|e^{i\xi}-1|^{2}|\widehat{u}(\xi)|=2\max_{\xi\in[0,2\pi)}\left|(1-\cos(\xi))\left(u(0)+2\sum_{k=1}^{n}u(k)\cos(\xi k)\right)\right|.

The substitution $x=\cos(\xi)$ gives rise to

\displaystyle L(u)=2\max_{-1\leq x\leq 1}\left|(1-x)\left(u(0)+2\sum_{k=1}^{n}u(k)T_{k}(x)\right)\right|

where $T_{k}(x)$ denotes the Chebyshev polynomial of degree $k$ . Therefore, defining the polynomial $p_{u}(x)$ by

\displaystyle p_{u}(x)=u(0)+\sum_{k=1}^{n}2u(k)T_{k}(x),

we have our desired equality

\displaystyle\sup_{0\neq f\in\ell^{2}(\mathbb{Z})}\frac{\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}=L(u)=2\max_{-1\leq x\leq 1}|(1-x)p_{u}(x)|.

∎

3.4. The Sharp Fourier Inequality and Optimal Kernel

Proof of Theorem 1.

For any symmetric and normalized $u:\{-n,\cdots,n\}\to\mathbb{R}$ , define the degree $n$ polynomial

\displaystyle p_{u}(x)=u(0)+\sum_{k=1}^{n}2u(k)T_{k}(x)

as given in Lemma 5. Then note $p_{u}(1)=u(0)+\sum_{k=1}^{n}2u(k)T_{k}(1)=1$ by the normalization of $u$ . Therefore combining Lemma 5 and Theorem 3 yields

\displaystyle\sup_{0\neq f\in\ell^{2}(\mathbb{Z})}\frac{\|\Delta(u\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}=2\max_{-1\leq x\leq 1}|(1-x)p_{u}(x)|\geq\frac{4\sin\left(\frac{\pi}{2n+2}\right)}{(n+1)\left(1+\cos\left(\frac{\pi}{2n+2}\right)\right)}.

Because the above inequality holds for symmetric normalized kernels, Lemma 4 implies this in fact holds for all normalized kernels. To see this inequality is sharp, let $S_{n}(x)$ be the optimal degree $n$ polynomial as given in Theorem 3. Because the Chebyshev polynomials $\{T_{0}(x),\dots,T_{n}(x)\}$ form a basis for the space of all degree $n$ polynomials, there exists unique coefficients $\alpha_{k}$ so that

\displaystyle S_{n}(x)=\alpha_{0}T_{0}(x)+\sum_{k=1}^{n}2\alpha_{k}T_{k}(x).

These coefficients define a corresponding kernel $u_{n}:\{-n,\cdots,n\}\to\mathbb{R}$ by setting $u_{n}(k)=u_{n}(-k)=\alpha_{k}$ for $k\geq 0$ . Using $T_{k}(1)=1$ , we find this kernel is properly normalized by computing

\displaystyle\sum_{k=-n}^{n}u_{n}(k)=\alpha_{0}+2\sum_{k=1}^{n}\alpha_{k}=\alpha_{0}T_{0}(1)+\sum_{k=1}^{n}2\alpha_{k}T_{k}(1)=S(1)=1.

Noting $T_{0}(x)\equiv 1$ , we can rewrite write $S_{n}(x)$ as

\displaystyle S_{n}(x)=u_{n}(0)+\sum_{k=1}^{n}2u_{n}(k)T_{k}(x).

Using the equality condition in Theorem 3, we find $u_{n}(k)$ indeed satisfies

\displaystyle\sup_{0\neq f\in\ell^{2}(\mathbb{Z})}\frac{\|\Delta(u_{n}\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}=2\max_{-1\leq x\leq 1}|(1-x)S_{n}(x)|=\frac{4\sin\left(\frac{\pi}{2n+2}\right)}{(n+1)\left(1+\cos\left(\frac{\pi}{2n+2}\right)\right)}.

To find an explicit expression for the minimizing kernel $u_{n}(k)$ , recall that Chebyshev polynomials are orthogonal and in particular

\displaystyle\int_{-1}^{1}T_{i}(x)T_{j}(x)\frac{dx}{\sqrt{1-x^{2}}}=\begin{cases}0\quad\text{if}\quad i\neq j,\\ \pi\quad\text{if}\quad i=j=0,\\ \frac{\pi}{2}\quad\text{if}\quad i=j\neq 0.\\ \end{cases}

Therefore for any $j$ we have

\displaystyle\int_{-1}^{1}S_{n}(x)T_{j}(x)\frac{dx}{\sqrt{1-x^{2}}}=\int_{-1}^{1}\left(u_{n}(0)+\sum_{k=1}^{n}2u_{n}(k)T_{k}(x)\right)\frac{T_{j}(x)dx}{\sqrt{1-x^{2}}}=\pi\cdot u_{n}(j).

Thus we can write $u_{n}(k)$ as

\displaystyle u_{n}(k)=\frac{1}{\pi}\int_{-1}^{1}S_{n}(x)T_{k}(x)\frac{dx}{\sqrt{1-x^{2}}}

where $T_{k}(x)$ is the $k$ th Chebyshev polynomial, and

\displaystyle S_{n}(x)=\frac{1}{x-1}\frac{2\sin\left(\frac{\pi}{2n+2}\right)}{(n+1)\left(1+\cos\left(\frac{\pi}{2n+2}\right)\right)}T_{n+1}\left(\frac{1+\cos\left(\frac{\pi}{2n+2}\right)}{2}(x+1)-1\right).

∎

3.5. The Epanechnikov Kernel

This section is dedicated to proving Theorem 2, which offers a kernel that is nearly optimal and easy to implement in practice. First we verify the Epanechnikov kernel $E_{n}:\{-n,\cdots,n\}\to\mathbb{R}$ satisfies the normalization requirement. Indeed, an induction argument gives the relation

\displaystyle\sum_{k=-n}^{n}k^{2}=\frac{1}{3}n(n+1)(2n+1).

Therefore we can compute

	$\displaystyle\sum_{k=-n}^{n}E_{n}(k)$	$\displaystyle=\sum_{k=-n}^{n}\frac{3}{n(4n^{2}-1)}\left(n^{2}-k^{2}\right)$
		$\displaystyle=\frac{3}{n(4n^{2}-1)}\left(n^{2}(2n+1)-\frac{1}{3}n(n+1)(2n+1)\right)=1.$

Next, note Lemma 5 allows us to reduce the asymptotic relation of Theorem 2 to a claim about the polynomials

\displaystyle p_{n}(x)=E_{n}(0)+2\sum_{k=1}^{n}E_{n}(k)T_{k}(x).

In particular, Lemma 5 promises the equivalence

\displaystyle\sup_{0\neq f\in\ell^{2}(\mathbb{Z})}\frac{\|\Delta(E_{n}\ast f)\|_{\ell^{2}(\mathbb{Z})}}{\|f\|_{\ell^{2}(\mathbb{Z})}}=2\max_{-1\leq x\leq 1}|(1-x)p_{n}(x)|.

Therefore it suffices to show that as $n\to\infty$ we have the asymptotic equivalence

\displaystyle\max_{-1\leq x\leq 1}(1-x)p_{n}(x)\sim\frac{3\mu}{2n^{2}}.

For simplicity, we remove the normalizing coefficients of $p_{n}(x)$ and instead consider

\displaystyle\widetilde{p}_{n}(x)=\frac{n(4n^{2}-1)}{3}p_{n}(x)=n^{2}+2\sum_{k=1}^{n-1}\left(n^{2}-k^{2}\right)T_{k}(x).

Therefore it suffices to show the following asymptotic equivalence as $n\to\infty$ :

(10)

\displaystyle\max_{-1\leq x\leq 1}(1-x)\widetilde{p}_{n}(x)\sim 2\mu n.

The first step in proving this asymptotic relation is to rewrite $(1-x)\widetilde{p}(x)$ as follows.

Lemma 6.

Define the polynomial

\widetilde{p}_{n}(x)=n^{2}+2\sum_{k=1}^{n-1}\left(n^{2}-k^{2}\right)T_{k}(x).

Then,

(11)

(1-x)\widetilde{p}_{n}(x)=\frac{T_{n}(x)-T_{n-1}(x)}{x-1}+(1-2n)T_{n}(x).

Proof.

We first show the equality

(12)

(1-x)\left(1+2\sum_{k=1}^{n-1}T_{k}(x)\right)=T_{n-1}(x)-T_{n}(x).

This follows quickly by induction and the recurrence $T_{n+1}(x)=2xT_{n}(x)-T_{n-1}(x)$ . Indeed, for $n=1$ we find $(1-x)(1+2\cdot 0)=1-x=T_{0}(x)-T_{1}(x).$ Furthermore, if (12) holds for $n$ , then we find

	$\displaystyle(1-x)\left(1+2\sum_{k=1}^{n}T_{k}(x)\right)$	$\displaystyle=(T_{n-1}(x)-T_{n}(x))+2(1-x)T_{n}(x)$
		$\displaystyle=T_{n}(x)+(T_{n-1}(x)-2xT_{n}(x))$
		$\displaystyle=T_{n}(x)-T_{n+1}(x).$

Due to (12), the claim follows so long as we can prove

(13)

(1-x)\widetilde{p}_{n}(x)=\left(1+2\sum_{k=1}^{n-1}T_{k}(x)\right)+(1-2n)T_{n}(x).

We prove (13) by induction. Indeed, for $n=1$ we can immediately compute the necessary relation $(1-x)\widetilde{p}_{1}=1-x=1+(1-2\cdot 1)T_{1}(x).$ Now suppose (13) holds for $n$ . First derive the following recurrence for $\widetilde{p}_{n}$ .

	$\displaystyle\widetilde{p}_{n+1}(x)$	$\displaystyle=(n+1)^{2}+2\sum_{k=1}^{n}((n+1)^{2}-k^{2})T_{k}(x)$
		$\displaystyle=\left(n^{2}+2\sum_{k=1}^{n-1}(n^{2}-k^{2})T_{k}(x)\right)+\left((2n+1)+2\sum_{k=1}^{n}((n+1)^{2}-n^{2})T_{k}(x)\right)$
		$\displaystyle=\widetilde{p}_{n}(x)+(2n+1)\left(1+2\sum_{k=1}^{n}T_{k}(x)\right).$

Therefore we find (13) also holds for $n+1$ by the following computation, which uses our hypothesis and (12).

	$\displaystyle(1-x)\widetilde{p}_{n+1}(x)$	$\displaystyle=(1-x)\left(\widetilde{p}_{n}(x)+(2n+1)\left(1+\sum_{k=1}^{n}T_{k}(x)\right)\right)$
		$\displaystyle=\left(1+2\sum_{k=1}^{n-1}T_{k}(x)+(1-2n)T_{n}(x)\right)+(2n+1)(T_{n}(x)-T_{n+1}(x))$
		$\displaystyle=1+2\sum_{k=1}^{n}T_{k}(x)+(1-2(n+1))T_{n+1}(x)$

∎

With this new form for $(1-x)\widetilde{p}_{n}(x)$ in hand, we turn back to our objective of showing (10). For each $n$ , we will bound the intervals $[-1,\cos\left(\frac{16}{n}\right)]$ and $[\cos\left(\frac{16}{n}\right),1]$ separately. Notice (11) is useful for bounding $[-1,\cos\left(\frac{16}{n}\right)]$ because the polynomial $(T_{n}(x)-T_{n-1}(x))/(x-1)$ stays fairly small away from $1$ , which the following claim quantifies.

Lemma 7.

Over $[-1,1)$ we have

\displaystyle\left|\frac{T_{n}(x)-T_{n-1}(x)}{x-1}\right|\leq\frac{\sqrt{2}}{\sqrt{1-x}}.

Proof.

Write $T_{n}(x)-T_{n-1}(x)=\cos(n\theta)-\cos((n-1)\theta)$ by making the substitution $x=\cos\theta$ . Then apply trigonometric identities to get the bound

	$\displaystyle\|\cos(n\theta)-\cos((n-1)\theta)\|$	$\displaystyle=\left\|2\sin\left(\frac{2n-1}{2}\theta\right)\sin\left(\frac{\theta}{2}\right)\right\|$
		$\displaystyle\leq 2\left\|\sin\left(\frac{\theta}{2}\right)\right\|=\sqrt{2}\cdot\sqrt{1-\cos\theta}.$

Therefore, substituting back to $x=\cos(\theta)$ we find

\displaystyle\left|\frac{T_{n}(x)-T_{n-1}(x)}{x-1}\right|\leq\frac{\sqrt{2}\sqrt{1-x}}{1-x}=\frac{\sqrt{2}}{\sqrt{1-x}}.

∎

Now let $x\in[-1,\cos\left(\frac{16}{n}\right)]$ and use (11) to bound

(14)		$\displaystyle\|(1-x)\widetilde{p}_{n}(x)\|$	$\displaystyle\leq(2n-1)\|T_{n}(x)\|+\left\|\frac{T_{n}(x)-T_{n-1}(x)}{x-1}\right\|$
		$\displaystyle\leq(2n-1)+\frac{\sqrt{2}}{\sqrt{1-x}}\leq(2n-1)+\frac{\sqrt{2}}{\sqrt{1-\cos\left(\frac{16}{n}\right)}}.$

We can simplify this further by taking the Taylor expansion of cosine about $0$ and computing the following limit.

\displaystyle\lim_{n\to\infty}(2n-1)\frac{\sqrt{1-\cos\left(\frac{16}{n}\right)}}{\sqrt{2}}=\lim_{n\to\infty}\sqrt{\frac{(2n-1)^{2}}{2}\left(\frac{1}{2}\left(\frac{16}{n}\right)^{2}+O\left(\frac{1}{n^{4}}\right)\right)}=16.

Therefore, returning to the inequality chain (14), we have for $x\in[-1,\cos\left(\frac{16}{n}\right)]$ the following asymptotic equivalence as $n\to\infty$ :

\displaystyle|(1-x)\widetilde{p}_{n}(x)|\sim(2n-1)\left(1+\frac{1}{16}\right)\leq 2\mu n.

Where the last inequality follows from $1+\frac{1}{16}\leq\mu\approx 1.063$ by (6). We have shown

\limsup_{n\to\infty}\max_{-1\leq x\leq\cos\left(\frac{16}{n}\right)}\frac{1}{2n}(1-x)\widetilde{p}_{n}(x)\leq\mu.

Therefore if only we can show the asymptotic equivalence

(15)

\max_{\cos\left(\frac{16}{n}\right)\leq x\leq 1}(1-x)\widetilde{p}_{n}(x)\sim 2\mu n

as $n\to\infty$ , then (10) and hence Theorem 2 follows. Substitute $x=\cos\left(\frac{\alpha}{n}\right)$ and we claim uniform convergence

\frac{1}{2n}\left(1-\cos\left(\frac{\alpha}{n}\right)\right)\cdot\widetilde{p}_{n}\left(\cos\left(\frac{\alpha}{n}\right)\right)\to\frac{\sin(\alpha)}{\alpha}-\cos(\alpha).

If this is true, the result follows immediately because uniform convergence allows the following interchange of maximum and limit.

	$\displaystyle\lim_{n\to\infty}\frac{1}{2n}\max_{\cos\left(\frac{16}{n}\right)\leq x\leq 1}\|(1-x)\widetilde{p}_{n}(x)\|$	$\displaystyle=\lim_{n\to\infty}\max_{\alpha\in[0,16]}\frac{1}{2n}\left\|\left(1-\cos\left(\frac{\alpha}{n}\right)\right)\widetilde{p}_{n}\left(\cos\left(\frac{\alpha}{n}\right)\right)\right\|$
		$\displaystyle=\max_{\alpha\in[0,16]}\lim_{n\to\infty}\frac{1}{2n}\left\|\left(1-\cos\left(\frac{\alpha}{n}\right)\right)\widetilde{p}_{n}\left(\cos\left(\frac{\alpha}{n}\right)\right)\right\|$
		$\displaystyle=\max_{\alpha\in[0,16]}\left\|\frac{\sin(\alpha)}{\alpha}-\cos(\alpha)\right\|=\mu.$

Thus the following claim is the only remaining barrier to the proof of Theorem 2.

Lemma 8.

We have uniform convergence

\frac{1}{2n}\left(1-\cos\left(\frac{\alpha}{n}\right)\right)\widetilde{p}_{n}\left(\cos\left(\frac{\alpha}{n}\right)\right)\to\frac{\sin(\alpha)}{\alpha}-\cos(\alpha)

as $n\to\infty$ over $\alpha\in[0,16]$ .

Proof.

Use (11) and trigonometric identities to rewrite the sequence of functions as

	$\displaystyle\frac{1}{2n}\left(1-\cos\left(\frac{\alpha}{n}\right)\right)\widetilde{p}_{n}\left(\cos\left(\frac{\alpha}{n}\right)\right)$	$\displaystyle=\frac{1}{2n}\frac{\cos(\alpha)-\cos\left(\frac{n-1}{n}\alpha\right)}{\cos(\frac{\alpha}{n})-1}+\frac{1-2n}{2n}\cos(\alpha)$
		$\displaystyle=\frac{1}{n}\frac{\sin\left(\frac{2n-1}{2n}\alpha\right)\sin\left(\frac{\alpha}{2n}\right)}{1-\cos\left(\frac{\alpha}{n}\right)}-\frac{2n-1}{2n}\cos(\alpha)$
		$\displaystyle=\frac{1}{n}\frac{\sin\left(\frac{2n-1}{2n}\alpha\right)}{2\sin\left(\frac{\alpha}{2n}\right)}-\frac{2n-1}{2n}\cos(\alpha)$

Because $\frac{2n-1}{2n}\cos(\alpha)\to\cos(\alpha)$ uniformly, we only must show that

\displaystyle\frac{1}{n}\frac{\sin\left(\frac{2n-1}{2n}\alpha\right)}{2\sin\left(\frac{\alpha}{2n}\right)}\to\frac{\sin(\alpha)}{\alpha}

uniformly. We break this into two parts, first using that sine is Lipschitz with constant $1$ to compute

\displaystyle\left|\frac{\sin\left(\frac{2n-1}{2n}\alpha\right)}{\alpha}-\frac{\sin(\alpha)}{\alpha}\right|\leq\left|\frac{\frac{2n-1}{2n}\alpha-\alpha}{\alpha}\right|=\left|\frac{2n-1}{2n}-1\right|.

Notice the right hand side of the above inequality converges uniformly to $0$ as $n\to\infty$ , giving the uniform convergence $\frac{1}{\alpha}\sin(\frac{2n-1}{2n}\alpha)\to\frac{1}{\alpha}\sin(\alpha)$ . Secondly, use Taylor’s theorem to get the following uniform convergence over $\alpha\in[0,16]$ :

\displaystyle\frac{\alpha}{2n\sin\left(\frac{\alpha}{2n}\right)}=\frac{\alpha}{\alpha+O((\frac{\alpha}{n})^{3})}=\frac{1}{1+O(\frac{\alpha^{2}}{n^{3}})}\to 1.

Because $1$ and $\frac{1}{\alpha}\sin(\alpha)$ are bounded over $[0,16]$ , the product of the sequences converges uniformly to the product of the limits and so we get uniform convergence

\displaystyle\frac{1}{n}\frac{\sin\left(\frac{2n-1}{2n}\alpha\right)}{2\sin\left(\frac{\alpha}{2n}\right)}=\frac{\sin\left(\frac{2n-1}{2n}\alpha\right)}{\alpha}\cdot\frac{\alpha}{2n\sin\left(\frac{\alpha}{2n}\right)}\to\frac{\sin\alpha}{\alpha}.

∎

Acknowledgements

This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-2140004. Additional thanks to Stefan Steinerberger for bringing this problem to the author’s attention and for helpful conversations.

References

[1] Jean Babaud, Andrew P. Witkin, Michel Baudin, and Richard O. Duda. Uniqueness of the Gaussian kernel for scale-space filtering. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-8(1):26–33, 1986.
[2] William Beckner. Inequalities in Fourier Analysis. Annals of Mathematics, 102(1):159–182, 1975.
[3] William Beckner. Pitt’s inequality and the uncertainty principle. Proceedings of the American Mathematical Society, 123(6):1897–1905, 1995.
[4] Emanuel Carneiro, Damiano Foschi, Diogo Oliveira e Silva, and Christoph Thiele. A sharp trilinear inequality related to Fourier restriction on the circle. Revista Matematica Iberoamericana, 33(4):1463–1486, 2017.
[5] Emanuel Carneiro, Diogo Oliveira e Silva, and Mateus Sousa. Extremizers for Fourier restriction on hyperboloids. Annales de l’Institut Henri Poincaré C, Analyse non linéaire, 36(2):389–415, 2019.
[6] Michael G. Cowling and John F. Price. Bandwidth versus time concentration: The Heisenberg–Pauli–Weyl inequality. SIAM Journal on Mathematical Analysis, 15(1):151–165, 1984.
[7] V. A. Epanechnikov. Non-parametric estimation of a multivariate probability density. Theory of Probability & Its Applications, 14(1):153–158, 1969.
[8] Damiano Foschi. Maximizers for the Strichartz inequality. Journal of the European Mathematical Society, 9(4):739–774, 2007.
[9] Felipe Gonçalves, Diogo Oliveira e Silva, and Stefan Steinerberger. Hermite polynomials, linear flows on the torus, and an uncertainty principle for roots. Journal of Mathematical Analysis and Applications, 451(2):678–711, 2017.
[10] Peter Hall, Michael C. Minnotte, and Chunming Zhang. Bump hunting with non-Gaussian kernels. The Annals of Statistics, 32(5):2124 – 2141, 2004.
[11] Dirk Hundertmark and Vadim Zharnitsky. On sharp Strichartz inequalities in low dimensions. International Mathematics Research Notices, 2006:34080, 2006.
[12] Jan J Koenderink. The structure of images. Biological Cybernetics, 50(5):363–370, 1984.
[13] Vjekoslav Kovač, Diogo Oliveira e Silva, and Jelena Rupčić. A sharp nonlinear Hausdorff–Young inequality for small potentials. Proceedings of the American Mathematical Society, 147(1):239–253, 2019.
[14] Vjekoslav Kovač, Diogo Oliveira E Silva, and Jelena Rupčić. Asymptotically sharp discrete nonlinear Hausdorff–Young inequalities for the $\operatorname{SU}(1,1)$ -valued Fourier products. The Quarterly Journal of Mathematics, 73(3):1179–1188, 2022.
[15] Noah Kravitz and Stefan Steinerberger. The smoothest average: Dirichlet, Fejér and Chebyshev. Bulletin of the London Mathematical Society, 53(6):1801–1815, 2021.
[16] Tony Lindeberg. Scale-space for discrete signals. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(3):234–254, 1990.
[17] Diogo Oliveira e Silva, Christoph Thiele, and Pavel Zorin-Kranich. Band-limited maximizers for a Fourier extension inequality on the circle. Experimental Mathematics, 31(1):192–198, 2022.
[18] M Samiuddin and GM El-Sayyad. On nonparametric kernel density estimates. Biometrika, 77(4):865–874, 1990.
[19] Betsy Stovall. Uniform estimates for Fourier restriction to polynomial curves in $\mathbb{R}^{d}$ . American Journal of Mathematics, 138(2):449–471, 2016.
[20] Betsy Stovall. Extremizability of Fourier restriction to the paraboloid. Advances in Mathematics, 360:106898, 2020.
[21] United States Geological Survey. Lake Chelan elevation of resevoir water surface. https://waterdata.usgs.gov/monitoring-location/12452000. Data from 2011-07-16 to 2011-07-30. Accessed 2023-05-24.
[22] Ryoya Yamasaki and Toshiyuki Tanaka. Kernel selection for modal linear regression: Optimal kernel and irls algorithm. In 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA), pages 595–601. IEEE, 2019.
[23] Alan L. Yuille and Tomaso A. Poggio. Scaling theorems for zero crossings. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-8(1):15–25, 1986.

	$\displaystyle\frac{\\|\Delta(\widetilde{u}\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}$	$\displaystyle=\frac{\\|\Delta(\frac{1}{2}(u+u^{-})\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}$
		$\displaystyle\leq\frac{1}{2}\left(\frac{\\|\Delta(u\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}+\frac{\\|\Delta(u^{-}\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}\right)$
		$\displaystyle=\frac{1}{2}\left(\frac{\\|\Delta(u\ast f)\\|_{\ell^{2}(\mathbb{Z})}}{\\|f\\|_{\ell^{2}(\mathbb{Z})}}+\frac{\\|\Delta(u\ast f^{-})\\|_{\ell^{2}(\mathbb{Z})}}{\\|f^{-}\\|_{\ell^{2}(\mathbb{Z})}}\right).$

	$\displaystyle\sum_{k\in\mathbb{Z}}\|(\Delta(u\ast f))(k)\|^{2}$	$\displaystyle=\frac{1}{2\pi}\int_{\mathbb{T}}\|e^{-i\xi}-1\|^{4}\|\widehat{u}(\xi)\|^{2}\|\widehat{f}(\xi)\|^{2}d\xi$
(9)			$\displaystyle\leq\\|(e^{-i\xi}-1)^{4}\widehat{u}(\xi)^{2}\\|_{L^{\infty}(\mathbb{T})}\cdot\frac{1}{2\pi}\int_{\mathbb{T}}\|\widehat{f}(\xi)\|^{2}d\xi$
		$\displaystyle=\\|(e^{-i\xi}-1)^{4}\widehat{u}(\xi)^{2}\\|_{L^{\infty}(\mathbb{T})}\cdot\sum_{k\in\mathbb{Z}}\|f(k)\|^{2}.$

	$\displaystyle\lim_{n\to\infty}\frac{1}{2n}\max_{\cos\left(\frac{16}{n}\right)\leq x\leq 1}\|(1-x)\widetilde{p}_{n}(x)\|$	$\displaystyle=\lim_{n\to\infty}\max_{\alpha\in[0,16]}\frac{1}{2n}\left\|\left(1-\cos\left(\frac{\alpha}{n}\right)\right)\widetilde{p}_{n}\left(\cos\left(\frac{\alpha}{n}\right)\right)\right\|$
		$\displaystyle=\max_{\alpha\in[0,16]}\lim_{n\to\infty}\frac{1}{2n}\left\|\left(1-\cos\left(\frac{\alpha}{n}\right)\right)\widetilde{p}_{n}\left(\cos\left(\frac{\alpha}{n}\right)\right)\right\|$
		$\displaystyle=\max_{\alpha\in[0,16]}\left\|\frac{\sin(\alpha)}{\alpha}-\cos(\alpha)\right\|=\mu.$

A Sharp Fourier Inequality and the Epanechnikov Kernel

Abstract.

1. Introduction

Theorem (Kravitz-Steinerberger [15]).

Theorem (Kravitz-Steinerberger [15]).

Theorem (Main Result).

2. Results

2.1. A Sharp Fourier Inequality

Theorem 1 (Main Result, restated).

2.2. The Epanechnikov Kernel

Theorem 2.

2.3. A Sharp Polynomial Inequality

Theorem 3.

3. Proofs

3.1. A Sharp Polynomial Inequality

Proof of Theorem 3.

3.2. Reduction to symmetric kernels

Lemma 4.

Proof.

3.3. From discrete kernels to polynomial extremizers

Lemma 5 (Kravitz and Steinerberger [15]).

Proof of Lemma 5.

3.4. The Sharp Fourier Inequality and Optimal Kernel

Proof of Theorem 1.

3.5. The Epanechnikov Kernel

Lemma 6.

Proof.

Lemma 7.

Proof.

Lemma 8.

Proof.

Acknowledgements

References

A Sharp Fourier Inequality
and the Epanechnikov Kernel