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.


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!

If this is already known, then let me know please.

Can also ask for polys in Q[x], R[x], C[x]. For Q[x] and R[x] same theorem is true- no poly can produce all primes. I suspect also true for C[x] but I haven't seen it stated anywhere. (ADDED LATER- Proof for C[x] is easy. First proof
for Q[x] and then by Lagrange interpoloation if a poly has inf many times
where f(integer)=integer, poly is in Q[x].)

You can also NOT include negative primes and see how that changes things.

No comments:

Post a Comment