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$.

  • $\begingroup$ 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)? $\endgroup$ – T.... Oct 26 '14 at 8:06
  • 1
    $\begingroup$ 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). $\endgroup$ – Ilya Bogdanov Oct 26 '14 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.