## Monday, September 07, 2015

### An Open(?) question about prime-producing-polynomials

Known Theorem: If f(x)∈ Z[x] is  prime for all nat number inputs then  f(x) is a constant.

NOTE- Recall that if p is a prime then so is -p.

Known Proof: Assume f(x) has degree d. f(1) IS prime.  Let f(1)=p. Look at

f(1+p), f(1+2p),...,f(1+(2d+1)p).

One can easily show that p divides all of these. Hence if they are all primes then they must all be p or -p. Since there are 2d+1 of them, at least d+1 of them are the same, say p. Hence f is the constant p.

END of known proof.

Note that the proof gives the following theorem:

Let f(x)∈ Z[x] of degree d. We assume f(1)≥ 0. Least a st f(a) is NOT prime is  ≤ 1+(2d+1)p.

(This can prob be improved a bit with some cases, but its good enough for now.)

Recall Euler's poly x2-x+41 produces primes for x=0,...,40. But at 41 you get a composite. This is much smaller than the upper bound 1+(2d+1)p = 1+5*41=206.

Wolfram MathWorld has a  page of other polys in Z[x]  that produces lots of primes initially, but NONE come close to the bound.

QUESTIONS:

Proof a better upper bound.

Proof a better lower bound (Fix d and produce and infinite seq of polys of degree d...)

Close the gap!