Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
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!
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