# Minimum degree rational function interpolation

Find a rational function $R(x)$ such that:

$1)$ For $i\in\{1,\dots,g\}$, $x_{i}=x_{i-1}+g$ with $x_0=0$.

$2)$ For $i\in\{0,\dots,g-1\}$ $R(x_i)=R(x_i+1)=\dots=R(x_i+g-1)=i+1$.

$3)$ $R(x_g)=g+1$.

So $R(x)$ is defined at $g^2+1$ points.

These points and the value taken by these points have an arithmetic progression structure and I know that Lagrange interpolation gives $O(g^2)$ polynomial.

However is there a degree $O(g)$ rational function $R(x)$ that takes advantages of the structure in the conditions?

The answer is no. I assume that the degree of a rational function is the maximum of degrees of its numerator and denominator (in the irreducible form).

Consider any interval $(x_i+j,x_i+j+1)$ with $0\leq i\leq g-1$ and $0\leq j\leq g-2$. If the denominator of $R(x)$ has no roots on this interval, then $R'(x)$ should have a root on it. Let $d$ be the degree of $R(x)$. Then there are at most $d$ roots of the denominator, and at most $2d-2$ roots of the numerator of $R'(x)$, since this numerator has degree at most $2d-2$. Thus $g(g-1)\leq d+(2d-2)$, so $d\geq \frac{g(g-1)+2}3$.

• Thank you. 1) why "If the denominator of R(x) has no roots on this interval, then R′(x) should have a root on it." 2) why g(g-1) a lower bound for d+(2d-2)? 3) why atmost 2d-2 roots of numerator of R'(x)? – T.... Oct 26 '14 at 8:06
• 1) By Rolle's theorem. 2) You have $g(g-1)$ intervals of the described form, each contains one of the roots. 3) As I told, the numerator of $R'$ has degree at most $2d-2$: check the formula for the derivative of the ratio (and see that the terms of degree $2d-1$ cancel). – Ilya Bogdanov Oct 26 '14 at 8:10