Return to Answer

Here is a proof sketch along the lines suggested in the linked SE answer.

I will work on $S^1=[0,1]$ (identifying $0$ and $1$) and denote $e(x)=e^{2\pi ix}$. I will also denote $S_N=\{0,\frac 1N,\ldots,\frac{N-1}N\}\subset S^1$ and assume for convenience that $N$ is odd. Let $f\in C^{2}(S^1)$. Set $f_N(x)=\sum_{n=-(N-1)/2}^{(N-1)/2}\widehat {f_N}(n)e(nx)$, where $\widehat{f_N}(n)=\frac 1N\sum_{x\in S_N}f(x)e(-nx)$. Then $f_N$ coincides with $f$ on $S_N$ by the Discrete Fourier Transform.

A calculation using Abel's summation formula twice and that $f\in C^2$ shows $\widehat{f_N}(n)=O(\frac 1{n^2})$ for $-\frac{N-1}2\le n\le\frac{N-1}2$, uniformly in $N$. This is the discrete version of the (hopefully "intuitive") fact that the Fourier coefficients of a smooth function decay fast, however the actual calculation involves expressions quite similar to Dirichlet and Fejer kernels, evaluated at a discrete set of points.

From this one obtains $\sup_{S^1}|f_N'|=O(\log N)$ and since $f=f_N$ on $S_N$ and the gaps between the points of $S_N$ are $1/N$ we have that $\sup_{S^1}|f-f_N|=O(\log N/N)$ and we are done.

Here is a proof sketch along the lines suggested in the linked SE answer.

I will work on $S^1=[0,1]$ (identifying $0$ and $1$) and denote $e(x)=e^{2\pi ix}$. I will also denote $S_N=\{0,\frac 1N,\ldots,\frac{N-1}N\}\subset S^1$ and assume for convenience that $N$ is odd. Let $f\in C^{2}(S^1)$. Set $f_N(x)=\sum_{n=-(N-1)/2}^{(N-1)/2}\widehat {f_N}(n)e(nx)$, where $\widehat{f_N}(n)=\frac 1N\sum_{x\in S_N}f(x)e(-nx)$. Then $f_N$ coincides with $f$ on $S_N$ by the Discrete Fourier Transform.

A calculation using Abel's summation formula twice and that $f\in C^2$ shows $\widehat{f_N}(n)=O(\frac 1{n^2})$ for $-\frac{N-1}2\le n\le\frac{N-1}2$, uniformly in $N$. This is the discrete version of the (hopefully "intuitive") fact that the Fourier coefficients of a smooth function decay fast. The actual calculation with this approach involves expressions quite similar to Dirichlet and Fejer kernels, evaluated at a discrete set of points. An alternative, more elegant approach is to use the identity $\widehat{\Delta g}(n)=(e(\frac nN)-1)\hat g(n)$ for discrete Fourier transforms, where $\Delta$ is the difference operator $\Delta g(\frac kN)=g(\frac{k+1}N)-g(\frac kN)$.

From this one obtains $\sup_{S^1}|f_N'|=O(\log N)$ and since $f=f_N$ on $S_N$ and the gaps between the points of $S_N$ are $1/N$ we have that $\sup_{S^1}|f-f_N|=O(\log N/N)$ and we are done.

Here is a proof sketch along the lines suggested in the linked SE answer.

I will work on $S^1=[0,1]$ (identifying $0$ and $1$) and denote $e(x)=e^{2\pi ix}$. I will also denote $S_N=\{0,\frac 1N,\ldots,\frac{N-1}N\}\subset S^1$ and assume for convenience that $N$ is odd. Let $f\in C^{\infty}(S^1)$. Set $f_N(x)=\sum_{n=-(N-1)/2}^{(N-1)/2}\widehat {f_N}(n)e(nx)$, where $\widehat{f_N}(n)=\frac 1N\sum_{x\in S_N}f(x)e(-nx)$. Then $f_N$ coincides with $f$ on $S_N$ by the Discrete Fourier Transform.

A simple calculation with Riemann sums (using the standard error term in the trapezoid rule) shows $|\hat f(n)-\widehat{f_N}(n)|=O(\frac {n^2}{N^2})$. Since $f$ is smooth, $\hat f(n)=O(\frac 1{n^2})$ and therefore $|\widehat{f_N}(n)|=O(\frac 1{n^2}+\frac {n^2}{N^2})$. It follows that $\sup_{S^1}|f-f_N|=O(

Since $f$ and $f_N$ coincide on $S_N$ and the gaps in $S_N$ have size $\frac 1N$, we obtain that $\sup_{S^1}|f-f_N|=O(\frac 1n+\frac{n^2}

Here is a proof sketch along the lines suggested in the linked SE answer.

I will work on $S^1=[0,1]$ (identifying $0$ and $1$) and denote $e(x)=e^{2\pi ix}$. I will also denote $S_N=\{0,\frac 1N,\ldots,\frac{N-1}N\}\subset S^1$ and assume for convenience that $N$ is odd. Let $f\in C^{2}(S^1)$. Set $f_N(x)=\sum_{n=-(N-1)/2}^{(N-1)/2}\widehat {f_N}(n)e(nx)$, where $\widehat{f_N}(n)=\frac 1N\sum_{x\in S_N}f(x)e(-nx)$. Then $f_N$ coincides with $f$ on $S_N$ by the Discrete Fourier Transform.

A calculation using Abel's summation formula twice and that $f\in C^2$ shows $\widehat{f_N}(n)=O(\frac 1{n^2})$ for $-\frac{N-1}2\le n\le\frac{N-1}2$, uniformly in $N$. This is the discrete version of the (hopefully "intuitive") fact that the Fourier coefficients of a smooth function decay fast, however the actual calculation involves expressions quite similar to Dirichlet and Fejer kernels, evaluated at a discrete set of points.

From this one obtains $\sup_{S^1}|f_N'|=O(\log N)$ and since $f=f_N$ on $S_N$ and the gaps between the points of $S_N$ are $1/N$ we have that $\sup_{S^1}|f-f_N|=O(\log N/N)$ and we are done.

Here is a proof sketch along the lines suggested in the linked SE answer.

I will work on $S^1=[0,1]$ (identifying $0$ and $1$) and denote $e(x)=e^{2\pi ix}$. I will also denote $S_N=\{0,\frac 1N,\ldots,\frac{N-1}N\}\subset S^1$ and assume for convenience that $N$ is odd. Let $f\in C^{\infty}(S^1)$. Set $f_N(x)=\sum_{n=-(N-1)/2}^{(N-1)/2}\widehat {f_N}(n)e(nx)$, where $\widehat{f_N}(n)=\frac 1N\sum_{x\in S_N}f(x)e(-nx)$. Then $f_N$ coincides with $f$ on $S_N$ by the Discrete Fourier Transform.

A simple calculation with Riemann sums shows $|\hat f(n)-\widehat{f_N}(n)|=O(\frac nN)$. Since $f$ is smooth, $\hat f(n)=O(\frac 1{n^2})$ and therefore $|\widehat{f_N}(n)|=O(\frac 1{n^2}+\frac nN)$.

Next we consider the truncated trigonometric sum $f_{N,m}(x)=\sum_{n=-m}^m\widehat{f_N}(n)e(nx)$.

Consequently $\sup_{S^1} |f_N'|=O(\frac 1n+\frac{n^2}N)$.

Since $f$ and $f_N$ coincide on $S_N$ and the gaps in $S_N$ have size $\frac 1N$, we obtain that $\sup_{S^1}|f-f_N|=O(\frac 1{

Here is a proof sketch along the lines suggested in the linked SE answer.

I will work on $S^1=[0,1]$ (identifying $0$ and $1$) and denote $e(x)=e^{2\pi ix}$. I will also denote $S_N=\{0,\frac 1N,\ldots,\frac{N-1}N\}\subset S^1$ and assume for convenience that $N$ is odd. Let $f\in C^{\infty}(S^1)$. Set $f_N(x)=\sum_{n=-(N-1)/2}^{(N-1)/2}\widehat {f_N}(n)e(nx)$, where $\widehat{f_N}(n)=\frac 1N\sum_{x\in S_N}f(x)e(-nx)$. Then $f_N$ coincides with $f$ on $S_N$ by the Discrete Fourier Transform.

A simple calculation with Riemann sums (using the standard error term in the trapezoid rule) shows $|\hat f(n)-\widehat{f_N}(n)|=O(\frac {n^2}{N^2})$. Since $f$ is smooth, $\hat f(n)=O(\frac 1{n^2})$ and therefore $|\widehat{f_N}(n)|=O(\frac 1{n^2}+\frac {n^2}{N^2})$. It follows that $\sup_{S^1}|f-f_N|=O(

Since $f$ and $f_N$ coincide on $S_N$ and the gaps in $S_N$ have size $\frac 1N$, we obtain that $\sup_{S^1}|f-f_N|=O(\frac 1n+\frac{n^2}