Polynomials that pass through a lot of primes

Whenever I mention a polynomial $p(x)$ passes through $n$, I mean there is an integer $z$ so that $p(z)=n$, also any polynomial I talk about is assumed to have integer coefficients.

It's a well known open to question to find a polynomial of degree 2 or more that passes through an infinite amount of primes.

Do we know of general polynomials of degree n that pass through at least f(n) primes where f isn't constant (so f could be like log(n) or 1.5*n)?

Additionally, do we know if the number of primes a quadratic pass through is unbounded (and similarly for other degrees)? Meaning if we look at $s(p(x))$ : the number of primes $p(x)$ passes through, where $p(x)$ is a quadratic, is $s(p(x))$ bounded?

Solution 1:

Your last question is answered by a classical and beautiful theorem of Sierpinski:

For any integer $m \ge 1$, there exists a constant $k$ such that the quadratic $n^2 + k$ passes through at least $m$ primes.

Thus $s(p(x))$ is unbounded even when $p(x)$ is restricted to the simplest possible family of quadratic polynomials.

Solution 2:

Getting an integer polynomial of degree $n$ where $p(0),p(1),\dots,p(n)$ are all prime is a little work, but relatively simple with a shout-out to Dirichlet's theorem on primes in arithmetic progressions.

Given a fixed $n$, we will find a sequence $p_k(z)$ of polynomials for $k=0,1,\dots,n$ such that $p_k$ is of degree at most $k$ and $p_k(i)$ is prime and bigger than $n$ for $0\leq i\leq k$.

For $k=0$, we find a prime $q>n$, and define $p_0(z)=q$.

Then, given a $p_k(z)$ with $k<n$, we define $p_{k+1}(z)=p_k(z)+a_{k+1} z(z-1)\dots(z-k)$. We need to find $a_{k+1}$ so that $p_k(k+1)+a_{k+1} (k+1)!$ is a prime bigger than $n$.

Claim: $p_k(k+1)$ is relatively prime to $(k+1)!$.

Proof: If $1\leq d\leq k+1$, then $$p_k(k+1)\equiv p_k(k+1-d)\pmod {d}.$$ Since $p_k(k+1-d)$ is a prime bigger than $n$, and hence bigger than $k$, then $p_k(k+1)$ is relatively prime to $d$.

So, by Dirichlet, we can pick an integer $a_k$ so that $p_k(k+1)+a_{k+1} (k+1)!$ is a prime.

Then $p_{k+1}(z)=p_k(z)+a_k z(z-1)(z-2)\dots(z-k)$ is of degree $k+1$ and has the property that $p_{k+1}(i)$ is prime for $i=0,1,2,\dots,k$.