9
$\begingroup$

Let $f(n)=a_3n^3+a_2n^2+a_1n+a_0$, with $a_i\in\mathbb{Z}$, $a_3>0, a_0\neq 0$ such that $f(n)>0$ for all positive integers $n$.

Given a prime $p$, when is $f(p)$ again prime?

For example, let $f(n)=7n^3-50n+30$. Then, $$f(7)=2081\quad {\rm (prime)},$$ $$f(11)=19\cdot463,$$ $$f(13)=14759\quad {\rm (prime)}.$$

Are there conditions on the $a_i$'s that guarantee that $f(p)$ is prime for all primes $p$?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ It is not known for any polynomial $f$ of degree greater than 1 whether $f(n)$ is prime for infinitely many values of $n$, prime or otherwise. This is the Buniakowsky conjecture (when $f$ satisfies the obvious necessary condition). $\endgroup$
    – Qiaochu Yuan
    Commented May 5, 2011 at 2:23
  • 6
    $\begingroup$ Qiaochu: the "obvious" necessary conditions are not all obvious. On first glance most people would agree that the obvious necessary conditions are that f(x) is irreducible, its leading coeff. is positive, and its coefficients as a polynomial have no common factors. But that last condition is not adequate and the substitute for it, I would say, is somewhat subtle (albeit elementary). $\endgroup$
    – KConrad
    Commented May 5, 2011 at 4:35
  • $\begingroup$ Jeff, You can use Bateman-Horn heuristics to estimate $\left|\{f(p): p \leq x, f(p) \mbox{ is prime}\}\right|$. Use Bateman-Horn for two polynomials, set $f_1(n)=n$ and $f_2(n)=f(n)$, the cubic polynomial you want. Bateman-Horn will count the inputs $n \leq x$ for which both are prime. $\endgroup$
    – Timothy Foo
    Commented Oct 22, 2011 at 4:31

2 Answers 2

Reset to default
18
$\begingroup$

There is no non-constant polynomial sending primes to primes, aside from $f(x)=x$. Indeed, it suffices to consider the case where $f$ is irreducible, as if $f(x)$ factors as $g(x)h(x)$, $f(p)$ is clearly composite for large $p$.

Now if $f(x)\not=x$, choose some large prime $p$ such that $f$ has a non-zero root $a$ in $\mathbb{F}_p$. By Dirichlet's theorem on primes in arithmetic progressions, there exist infinitely many primes $q_i$ with $q_i\equiv a\bmod p$. But for such $q_i$, $f(q_i)$ is divisible by $p$, and thus taking $q_i$ large, we have that $f(q_i)$ is composite.

I've been a bit glib about why one can choose $p$ as claimed; just look for primes which split in the splitting field of $f$ over $\mathbb{Q}$.

EDIT: More simply, use Lemma 1 here to pick $p$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ (I guess this is an answer to your last question, about what conditions on $f$ guarantee $f(p)$ prime for all primes $p$. The other, as Qiaochu points out, is wildly open, but the condition is conjectured to be the irreducibility of $f$.) $\endgroup$
    – Daniel Litt
    Commented May 5, 2011 at 2:42
  • $\begingroup$ Also I guess I'm using Chebotarev to pick a prime that splits. $\endgroup$
    – Daniel Litt
    Commented May 5, 2011 at 2:54
  • 4
    $\begingroup$ Daniel: irreducibility is not enough, e.g., x^2 - x + 2 is irreducible but has a hard time taking prime values. Also, while Chebotarev is a simple way to think about why there are lots of primes that split completely in a number field, that particular corollary of Chebotarev can be proved in about one page by a very elementary argument along the lines of Euclid's proof that there are infinitely many primes. See a paper by Cassels which I refer to in a common to Bjorn's answer at mathoverflow.net/questions/15220/… $\endgroup$
    – KConrad
    Commented May 5, 2011 at 4:50
  • $\begingroup$ +1: You're right of course. Bjorn's proof is very nice as well. $\endgroup$
    – Daniel Litt
    Commented May 5, 2011 at 5:32
  • $\begingroup$ (The added condition should be--the gcd of the integer values of $f$ must be $1$; e.g. $f$ must not vanish identically mod any prime. The example KConrad gives vanishes mod $2$.) $\endgroup$
    – Daniel Litt
    Commented May 5, 2011 at 5:36
0
$\begingroup$

It is, I think, better to investigate the last coefficient a0. It is easy to show that a0 cannot have more than 3 distinct prime factors. because, suppose that p is a prime factor of a0. then, if f(p) is prime, it must be = p, since p divides f(p). similar are the cases for other prime factors of a0. in short, if t is a prime factor of a0, then f(t)= t. but f being a cubic, it can't have more than three zeroes. this leads to my 1st statement. obviously irreducibility and all that are necessary conditions. i think a little more effort can solve your last problem.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .