# About the maximum degree of multivariate polynomial interpolation

It is well known that in the univariate case, to interpolate $k$ points in $\mathbb{R}$, we need to use a polynomial of degree $k-1$.

My question is about multivariate polynomial interpolation in higher dimension. We are given $k$ points $x_1,\ldots,x_k$ in $\mathbb{R}^d$. Define the max-deg of a multivariate polynomial to be the maximum exponent of any variable. For example, the max-deg of the linear function $x_1+x_2+x_3$ is 1 and the max-deg $x_1^2+x_2$ is 2. My question is: given $x_1,\ldots,x_n$, what is the minimum $d$ such that for any $y_1,\ldots, y_d$, there is a polynomial $P$ of max-deg $d$ such that $P(x_i)=y_i\forall i$. The answer should really depend on the configuration of $x_1 ,\ldots,x_k$. For example, if $x_1 ,\ldots,x_k$ are linearly independent, we only need max-deg to be 1 (i.e., we can use a linear function to intepolate it).

Has the same problem (or some thing similar) been studied before?

• Same as before, $d=k-1$. You can't improve on this because the points could be on a coordinate axis. Conversely, you can interpolate with polynomials of this max-deg. – Christian Remling Oct 11 '14 at 4:25
• I am not looking for the worse case scenorios. The answer should really depend on the configuration of $x_1,\ldots,x_k$. For example, if $x_1,\ldots,x_k$ are linearly independent, we only need max-deg to be 1. – jian Oct 11 '14 at 11:07
• Then you get the max-deg's between $0$ and $k-1$, since you can deliberately put some or all of your points on the graph of a given polynomial. – Christian Remling Oct 11 '14 at 16:56
• Maybe I did not make myself clear. My question was "given $x_1,\ldots, x_n$, what the max-deg should be". We do not get to choose where $x_1,\ldots,x_n$ are, but $y_1,\ldots, y_n$ can be arbitrary. – jian Oct 12 '14 at 3:23

One would hope to be able to interpolate data sites $X = \{x_1,\dots, x_Q \}$ with a polynomial from $\pi_m(\mathbb{R}^d)$ when $Q=\dim \pi_m(\mathbb{R}^d)={m+d\choose d}$. Here $m$ is your "max-deg".