MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Finite interpolation by nondecreasing indefinitely differentiable functions in a finite-dimensional space

Some time ago, I asked about inite interpolation by a nondecreasing polynomial here at http://mathoverflow.net/questions/16673/finite-interpolation-by-a-nondecreasing-polynomial. This turned out to be an already solved problem; it also turned out that the degree of the solution could not be bounded in terms of the number of interpolation points alone.

My new question is: if we are willing to replace polynomials by another vector space V of indefinitely differentiable functions, then we can we achieve something better than with polynomials, in the sense that V is finite-dimensional?

Formally, fix $x_1 \lt x_2 \lt \ldots \lt x_n$ and let $y_1 \leq y_2\leq \ldots \leq y_n$ vary. We consider the system $(S)$ made of the $n$ interpolation constraints $f(x_i)=y_i$ for $i$ between $1$ and $n$. Is there a finite-dimensional subspace $V$ of ${\cal C}^{\infty}([x_1,x_n],{\mathbb R})$ such that for any $y_1 \leq y_2\leq \ldots \leq y_n$, there is a solution to $(S)$ which is nondecreasing and also in $V$?

-
 The most obvious answer is the space of all continuous functions which are affine on each interval of the subdivision (or other similar variations on these lines). Is this what you want? – Pietro Majer Nov 16 2010 at 17:22 Sorry, I misstated my problem. I've corrected it just now – Ewan Delanoy Nov 16 2010 at 17:29 A modification of Pietro Majer's answer still works, right? You just need to smooth everything out in a neighborhood of each x_i. – Qiaochu Yuan Nov 16 2010 at 17:36 @ Qiaochu : I think not. The more "smoothings" you need to do, the bigger V becomes (in terms of dimensionality). Subproblem : what is the minimal dimensionality of V, if we replace indefinitely derivable functions by functions derivable k times? – Ewan Delanoy Nov 16 2010 at 18:22

This is to expand Qiaochu Yuan's comment. For $1\le i < n$ let $b_i:=(x_{i+1}+x_i)/2$ be the mid-point of the $i$-th interval, and let $0 < \epsilon \leq \min_{1\le i < n} (x_{i+1}+x_i)/2\ .$ Start with the linear space $V_0$ of all continuous functions on $\mathbb{R}$ that are affine on each component interval of $\mathbb{R}\setminus \{b _i\ : \ 1\leq i < n \}$ and take $V$ to be the image of $V_0$ via the (linear) convolution operator $u\mapsto u*\phi$, with a symmetric kernel $\phi\ge0$, $C^\infty_c(\ ]-\epsilon,+\epsilon[\ )\$ and $\int_\mathbb{R} \phi = 1 .$ The convolution with $\phi$ preserve monotonicity and the values at the nodes $x_i$, so that the interpolation function in $V$ is just the mollification of the interpolation function on $V_0.$

-
 I don't understand why the values at the nodes $x_i$ are preserved. – Ewan Delanoy Nov 16 2010 at 20:50 For any $u\in V_0$ we have $(u*\phi)(x_i)=u(x_i)$ just because $\phi$ is symmetric with support in $[-\epsilon,\epsilon]$ and $u$ is affine on $[x_i-\epsilon,x_i+\epsilon]$. – Pietro Majer Nov 16 2010 at 22:17

From a more pedestrian point of view: If what you want is possible at all (and it is) then in particular there is some non-decresing $f_3 \in {\cal C}^{\infty}([x_1,x_n],{\mathbb R})$ with $f_3(x_1)=f_3(x_2)=0$ and$f_3(x_3)=f_3(x_4)=\cdots=f_3(x_n)=1$. i.e. a ${\cal C}^{\infty}$ function on $\mathbb R$ which is $0$ up to $x_2$ then increases to $1$ and then is $1$ from $x_3$ on. If so, then one can have $n$ similar functions $f_k$ with $f_k(x_j)=$ $0$ or $1$ according as $j < k$ or $k \le j$. They span a degree $n$ space $V$ and the non-negative linear combinations of the $f_k$ do what you want.

It remains only to show how to build the $f_k$. Here's one way, maybe not the most elegant: First consider ${\cal C}^{\infty}$ function $g_3$ which is $0$ except on the open interval $(x_2,x_3)$ where it is $$e^{-1/(x-x_2)^2}e^{-1/(x-x_3)^2}$$ Then let $f_3(x)=c\int_{-\infty}^{x}g_3(t)\ dt$ where the constant $c>0$ is chosen to make $f_3(x)=1$ for $x \ge x_3$.

-
 Thanks Aaron. Your solution is more "pedestrian" indeed, but it helped me understand better Qiaochu's and Pietro's "magical" solution. – Ewan Delanoy Nov 17 2010 at 12:19