13

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?

  • 6
    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 '16 at 20:07
  • 1
    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 '16 at 20:08
  • Related: it's impossibile for a polynomial to only take prime values (that is, for all integers $n$, the number $p(n)$ is prime) –  Feb 17 '16 at 20:23
  • 2
    @vrugtehagel You forgot a word: nonconstant ;) – Daniel Fischer Feb 17 '16 at 21:02
  • 1
    @GregoryGrant note the coefficients need to be integers, not rationals, so I don't think it's so immediate. –  Feb 17 '16 at 21:55
  • @user336-iactuallychosethis Every polynomial with rational coefficients can be turned into one with integer coefficients by simply clearing denominators. Nowhere does he say the polynomial has to be monic. – Gregory Grant Feb 17 '16 at 22:01
  • 2
    @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. –  Feb 17 '16 at 22:26
  • A little bit of pedantry, but is there a specific reason you want polynomials with integer coefficients rather than integer-valued polynomials? None of the known answers change on either side, but there are polynomials that are integers at all integer values but don't have integer coefficients - $p(n)=\frac12n^2+\frac12n$ is a classic example. – Steven Stadnicki Feb 17 '16 at 22:28
  • @StevenStadnicki No I just didn't think of those when posting the question. –  Feb 17 '16 at 22:29
  • @user336-iactuallychosethis By clearing the denominator you don't change the value of any of the roots of the polynomial. For example $x-\frac12=0$ has the same roots as $2x-1=0$. – Gregory Grant Feb 17 '16 at 22:31
  • 2
    @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 $cp(n) = cq$ which isn't. –  Feb 17 '16 at 22:35

3 Answers3

17

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.

Erick Wong
  • 25,198
  • 3
  • 37
  • 91
  • 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. –  Feb 17 '16 at 21:51
  • 1
    @user336-iactuallychosethis I found a very simple proof here that uses basic facts about sums of two squares and Dirichlet's theorem: http://math.nsc.ru/LBRT/k5/Ageev/Sierpinski.ps. You may also be interested in this article which proves a wide generalization: http://www.jstor.org/stable/2324063 – Erick Wong Feb 17 '16 at 22:01
  • 1
    @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 '16 at 22:04
  • So beautiful! Thanks! We even get k is a square right? Is there a similar result for higher degrees? –  Feb 17 '16 at 22:22
  • 1
    @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 '16 at 22:25
  • 1
    Oh sorry I was so excited I forgot to check the other link, thanks for being patient with me haha. –  Feb 17 '16 at 22:27
10

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

Zach Teitler
  • 3,020
Thomas Andrews
  • 177,126
  • 1
    Neat argument! I wonder if there is an argument which doesn't use Dirichlet's theorem... – Wojowu Feb 17 '16 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. –  Feb 17 '16 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 '16 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 –  Feb 17 '16 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 '16 at 23:26
  • @Wojowu I think Dirichlet's theorem can probably be eliminated from the argument. The inductive requirement is that each prime is congruent to the previous one mod $k!$, so it should suffice (for a fixed $k$) to choose all primes to be in the same congruence class mod $k!$. By the pigeonhole principle, some congruence class admits infinitely many primes... but this can also be attributed to Dirichlet, haha! – Erick Wong Feb 18 '16 at 01:14
  • No, that is not the requirement. $p_k(k+1)$ is not the previous prime. $p_k(k)$ is the previous prime. @ErickWong – Thomas Andrews Feb 18 '16 at 02:14
  • @ThomasAndrews Ah, you're right, my mistake – Erick Wong Feb 18 '16 at 02:36
3

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.

Piquito
  • 29,594
  • Of course Buniakowski's conjecture is hard, but it's worth noting that Garrison's result was further generalized by Forman: http://jstor.org/stable/2324063 – Erick Wong Feb 17 '16 at 22:28
  • 1
    Don't forget A. A. Ageev nor U. Abel and H. Siebert in working together, after Forman. – Piquito Feb 18 '16 at 00:03