Given an interval $[a,b]$ what is the minimum degree of univariate polynomials in $\mathbb Q[x]$ that passes through all primes between $a$ and $b$ (denoted by $\mathbb P[a,b]$ with total number of primes in $[a,b]$ given by $\pi(b-a)=|\mathbb P[a,b]|$)?


$\forall x,y\in\{1,\dots,\pi(b-a)\},f(x),f(y)\in\mathbb P[a,b]$ and $f(x)<f(y)\iff x<y$.


It is at most $O(\pi(b-a))$ and is there a reason to believe it cannot be $o(\pi(b-a))$?



Polynomials of minimum degree that interpolate primes in intervals
Equivalently, you want to interpolate the points $(i, p\_i)$, $i = m \ldots n$ where $p\_i$ is the $i$'th prime.


The prime $k$-tuples conjecture implies that for each integer $k > 2$ and each $d$ from $1$ to $k-1$, there are infinitely many $m$ such that with $n=m+k$ the minimum degree of the interpolating polynomial is $d$.


The conjecture says that $(p\_{m+1}-p\_m, p\_{m+2}-p\_m, \ldots, p\_{m+k} - p\_m)$ is, for infinitely many $m$, any increasing $k$-tuple of even integers such that there is no prime $q$ for which this covers all residues mod $q$. In particular this implies that for a given
$k>2$, if $A$ is the product of all primes $\le k$ and $d \ge 1$ there are infinitely many $m$ such that
$p\_j = p\_m + A (j-m)^d$ for $m \le j \le m+k$. Thus in such a case, if $d \le k-1$ the minimum degree is $d$.


EDIT: see also [OEIS sequence A335435](https://oeis.org/draft/A335435).


