# 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?

-
It's relatively elementary to find an integer polynomial of degree $n$ so that $p(0),p(1),\dots,p(n)$ are primes. – Thomas Andrews Feb 17 at 20:07
You can fit a polynomial to any number of points so yes take $f(n)=n$ and fit a polynomial of degree $n$ to those $n$ points. – Gregory Grant Feb 17 at 20:08
@vrugtehagel You forgot a word: nonconstant ;) – Daniel Fischer Feb 17 at 21:02
@GregoryGrant I probably misunderstand you, if you clear denominators you're multiplying the values of the polynomial by the value as well making them not prime. – user336- i actually chose this Feb 17 at 22:26
@GregoryGrant I'm really not following you sorry, we want to find a polynomial with integer coefficients that passes through some primes, if the coefficients are rational, you have to multiply the polynomial by a constant $c$, then if before $p(n) = q$ where q is prime, we now have $c*p(n) = c*q$ which isn't. – user336- i actually chose this Feb 17 at 22:35

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-1))$ is of degree $k$ and has the property that $p_{k+1}(i)$ is prime for $i=0,1,2,\dots,k$.

-
Neat argument! I wonder if there is an argument which doesn't use Dirichlet's theorem... – Wojowu Feb 17 at 20:33
Nice! I think you can simplify the last part, $p_k(k))$ is relatively prime to $k!$ because $p_k(k))$ is a prime larger than n which is larger or equal to k. – user336- i actually chose this Feb 17 at 21:49
Whoops, I have an off-by-one error in my proof. Will fix when home - question should be about $p_k(k+1)$, not $p_k(k)$ – Thomas Andrews Feb 17 at 22:17
Wow and I was stupid enough not to notice it, sorry. I actually watched the indexes so well that I was sure all was well :P – user336- i actually chose this Feb 17 at 22:23
Self abuse does you no good. @user336-iactuallychosethis I would't have noticed your error without your comment. – Thomas Andrews Feb 17 at 23:26

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.

-
Awesome, do you have a link for a proof? I can't find the theorem on google. By the way I accepted the other answer but yours was just good, I chose randomly. – user336- i actually chose this Feb 17 at 21:51
@user336-iactuallychosethis I found a very simple proof here that uses basic facts about sums of two squares and Dirichlet's theorem: math.nsc.ru/LBRT/k5/Ageev/Sierpinski.ps. You may also be interested in this article which proves a wide generalization: jstor.org/stable/2324063 – Erick Wong Feb 17 at 22:01
@user336-iactuallychosethis The basic idea is that if every value of $k$ only gave a bounded number of primes then there would be very few primes of the form $n^2 + k^2$. But in fact we know there are lots of such primes. – Erick Wong Feb 17 at 22:04
@user336-iactuallychosethis Yup, you do get a square value of $k$ from that particular argument, but it isn't the only one. There is a lot of freedom even in the non-square case because there is not that much multiplicity of representation of a prime as $n^2 + k$. The second link I posted in my comment proves this for all integer-valued functions which grow polynomially (or even a little bit faster than polynomial). – Erick Wong Feb 17 at 22:25
Oh sorry I was so excited I forgot to check the other link, thanks for being patient with me haha. – user336- i actually chose this Feb 17 at 22:27

THEOREM. Let $k\ge 2$ be an integer and let $M$ an arbitrarily large number. Then there exist positive integers $c,d$ such that $x^k+c$, likewise $x^k-d$ is prime for more than $M$ positive integers $x$
The famous conjecture of Buniakowski (1854) say that for any irreducible polynomial $f(x)\in \mathbb Z [x]$ such that the set of values f (n) has no common divisor larger than $1$ ($f(x)=x^3+x+2$ is irreducible but $f(n)$ is always even) there are infinitely many primes $f(n)$. This conjecture is still one of the major unsolved problems in number theory when the degree of $f$ is greater than one. For degree 1 one has Dirichlet’s theorem on primes in arithmetic progressions (obviously $ax+b; (a,b)=1$, is irreducible); in other words, Buniakowski’s conjecture wants to generalize this celebrated theorem.