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))$?

  • $\begingroup$ What do you mean by saying a polynomial "passes through" a prime? What points are you interpolating? $\endgroup$ – Robert Israel Jul 1 at 16:14

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.

| cite | improve this answer | |

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.