Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 9 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer
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: You may also be interested in this article which proves a wide generalization: – 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

Your question is very difficult to answer in full.

For the quadratic case there are partial answers. I have kept, among others and for some time now, an article of Betty Garrison (San Diego State University. A.M.M. 97 (1990) p. 316-17) in which there is the following improvement of Sierpinski's result:

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.

share|cite|improve this answer
Of course Buniakowski's conjecture is hard, but it's worth noting that Garrison's result was further generalized by Forman: – Erick Wong Feb 17 at 22:28
Don't forget A. A. Ageev nor U. Abel and H. Siebert in working together, after Forman. – Piquito Feb 18 at 0:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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