# Interpolation Operator Bounded in Sobolev Norm

Let $m\in \mathbb{N}$, $p\in [1,\infty]$, $W^{m,p}([0,1])$ the space of all functions $[0,1]\rightarrow \mathbb{R}$ which are $m$ times weakly differentiable and weak derivatives in $L^p$, $$|u|_{W^{m,p}([0,1])}:=\|u^{(m)}\|_{L^p([0,1])}$$ for all $u\in W^{m,p}$ the Sobolev seminorm where $u^{(m)}$ is the $m$-th derivative of $u$, $[n]=\{0,\dots,n\}$, $\ell([n],\mathbb{R})$ the set of all functions $[n]\rightarrow \mathbb{R}$, $\nabla \colon \ell([n],\mathbb{R})\rightarrow \ell([n-1],\mathbb{R})$ defined by $$(\nabla x)_i:=x_{i+1}-x_i,$$ $$\|f\|_{\ell^p}:=\left(\frac{1}{n}\sum_{i\in [n]} |f_i|^p\right)^{\frac{1}{p}}$$ the discrete $p$-norm and $$|f|_{\ell^{m,p}}:=\|n^m\nabla^mf\|_{\ell^p}$$ the discrete Sobolev norm. I want to find a linear operator $E\colon \ell([n],\mathbb{R})\rightarrow W^{m,p}([0,1])$ which is interpolatory, i.e. $Ef(k/n)=f_k$ for all $k\in [n]$, and satisfies $$C_1|f|_{\ell^{m,p}}\leq |Ef|_{W^{m,p}([0,1]}\leq C_2|f|_{\ell^{m,p}}$$for some $C_1,C_2$ independent of $n$ and $f$. I tried spline-interpolation of degree $m$. However I don't know how to prove the statement. Such a theorem would be very useful for me and maybe others to get some high-order approximation estimates.

I prove here that the upper bound for your inequality is true for $m=1$. However, this approach should help you prove what you want in general. (EDIT: This is true in general after checking with Charles Fefferman--see edit at bottom.)
What you're trying to do is similar to recent work by Charles Fefferman, Arie Israel, and Garving Luli. Using your notation, define $X_m \,\colon= W^{m,p}(\mathbb{R})$ equipped with the homogeneous seminorm $|F|_{X_m} := ||F^{(m)}||_{L^p(\mathbb{R})}$, and define $X_m([n])\, \colon= \ell([n],\mathbb{R})$ equipped with the seminorm $|f|_{X_m([n])} \,\colon= \inf\{|F|_{X_m} \, \colon\, F \in X_m,\, F=f \, \text{on}\, [n]\}$. Let $p \in (1,\infty)$. In Sobolev Extension by Linear Operators, one of the theorems Fefferman, Israel, and Luli prove is that there exists a linear map $T \colon X_m([n]) \rightarrow X_m$ such that $Tf = f$ on $[n]$ and $|Tf|_{X_m} \leq C|f|_{X_m([n])}$, where $C$ depends only on $m,n,p$. Note that we also have the trivial fact $|f|_{X_m([n])} \leq |Tf|_{X_m}$. Their result is in fact true for extensions of any subset in $\mathbb{R}^n$ with $p \in (n,\infty)$, not just finite subsets of $\mathbb{R}$ (the restriction on $p$ comes from the Sobolev Embedding Theorem). Recently, they proved in Fitting a Sobolev function to data, that when the subset is finite, $T$ additionally has the important but technical condition of "$\Omega$-assisted bounded depth," where $\Omega$ is a certain set of linear functionals on $X_m([n])$.
Applying this to your problem, define $Y_m\,\colon= W^{m,p}([0,n])$ with $|F|_{Y_m} := ||F^{(m)}||_{L^p(\mathbb{[0,n]})}$, and define $Y_m([n])\, \colon= \ell([n],\mathbb{R})$ equipped with seminorm $|f|_{Y_m([n])} \, \colon= \inf\{|F|_{Y_m} \, \colon\, F \in Y_m,\, F=f \, \text{on}\, [n]\}$. Note that $|f|_{Y_m([n])} = |f|_{X_m([n])}$. Suppose we have that $|f|_{Y_m([n])} = \big(\sum\limits_{i \in [n-m]} |\nabla^m f|^p\big)^{\frac{1}{p}}$. Then, $$\big(\sum\limits_{i \in [n-m]} |\nabla^m f|^p\big)^{\frac{1}{p}} = |f|_{Y_m([n])} \leq |Tf|_{Y_m} \leq |Tf|_{X_m} \leq C|f|_{X_m([n])} = C\big(\sum\limits_{i \in [n-m]} |\nabla^m f|^p\big)^{\frac{1}{p}}$$ Multiplying in by $n^{m -\frac{1}{p}}$, this implies your desired inequality, using that $$n^{m -\frac{1}{p}}\big(\int\limits_{0}^n |u^{(m)}(x)|^p \,dx\big)^{\frac{1}{p}} = \big(\int\limits_{0}^1 |u^{(m)}(nx)|^p \,dx\big)^{\frac{1}{p}}$$ for $u \in Y_m$ by scaling and the chain rule.
So, your problem comes down to comparing $|f|_{Y_m([n])}$ and $\big(\sum_{i \in [n-m]} |\nabla^m f|^p\big)^{\frac{1}{p}}$. It is easy to see that $|f|_{Y_1([n])} \leq \big(\sum_{i \in [n-1]} |\nabla f|^p\big)^{\frac{1}{p}}$, which gives the upper bound in your desired inequality for $m=1$. Let $f \in \ell([n],\mathbb{R})$, and let $G_1 \colon [0,n] \rightarrow \mathbb{R}$ be the function whose graph consists of the straight lines connecting $f(i)$ to $f(i+1)$ for $i=0,\dots,n-1$. Then, $G_1 \in Y_1$ and for $z \in (i,i+1)$, $\frac{dG_1}{dx}(z) = (\nabla f)_i$. Then, $|f|_{Y_1([n])} \leq ||G_1^{(1)}||_{L^p(\mathbb{R})} = \big(\sum_{i \in [n-1]} |\nabla f|^p\big)^{\frac{1}{p}}$.
EDIT: I asked Charles Fefferman today, just to make sure the direction I'm going is correct, if your discrete Sobolev norm and the norm induced on $[n]$ by restrictions of extensions are equivalent, and he said that they certainly are. The lower bound follows from considering a polynomial extension, and the upper bound should follow from an argument where you prove it for small subsets and use a partitions of unity to prove it for all of $[n]$. Since the norms on $[n]$ are equivalent, this means that using my little argument above, your problem is true, since it is equivalent to a specific case of Fefferman, Israel, and Luli's result.