Prime Polynomial

This question has been troubling me from a couple of days: Does there exist a non-constant polynomial with integer coefficients that takes only prime values? Why, Why not?

I feel that there exists no such polynomial, but I am unable to prove it. Somebody please help me out.

#MathProblem

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Let the highest coefficient of the polynomial be Ax^N. Observe that the polynomial must always take on prime values (I assume for all positive integers x, p(x) is prime) and must thus be positive. Thus A is positive. Also let the sum of the (positive) coefficients in the polynomial be B.

From Prime number theorem, the number of primes from 1 to M is less than 2 log M

The number of primes in (1,2,...M) is less than 2 log M. However, the number of values from 1 to M that are mapped to by the polynomial is at least (M/B)^(1/N), for large enough M. Observe that this value grows much faster than log M, thus for sufficiently large M at least one value mapped to by the polynomial will not be prime.

In other words: density of primes < density of numbers mapped to by polynomial.

Gabriel Wong - 8 years, 1 month ago

Note that $-2$ is a prime, so you need to be careful. If such a polynomial existed, you could multiply it by $-1$ , and so $A$ could be negative.

Density is a good way of looking at it. You have not provided any justification for your bound, how you obtained it. A slightly simpler argument is to say that $\{ f(n) \} _{i=1} ^M$ has at least $\frac{M}{N}$ distinct values by the Fundamental Theorem of Algebra.

Calvin Lin Staff - 8 years, 1 month ago

If we allow negative numbers as primes (e.g. -2), here is a revised proof:

We only need to show p(x) cannot take prime values for all positive integers x. Let p(x) take the form of (cn)(x^n) + (c(n-1))(x^(n-1)) ... + c_0

WLOG we can assume c_n is positive; otherwise, multiply the polynomial by -1.

Let abs(c0) + abs(c1) + ..+ abs(c_(n-1)) = C

Observe that abs ((c(n-1))(x^(n-1)) + (c(n-2))(x^(n-2))... + c_0) <= C (x^(n-1)) for sufficiently large x

As long as x is sufficiently large, (c_n)(x^n) > C (x^(n-1). It is then clear that p(x) only takes positive values.

Consider p(D+1), p(D+2) .... p(ED), which must all be prime, for sufficiently large integers D, E. Let the sum of all c_i be F.

It is clear that p takes a maximum value of F(ED^n). Thus, all values that p takes from D+1 to ED are contained in the region (1,F(ED^n)).

Number of primes in this region < 2log(F(ED^n)) = 2log F + 2n log(E) + 2n log (D)

Number of values p takes in this region >= (E-1)D

As F and n are constant, it is then clear due to the growth rates of the functions, that as long as E and D are sufficiently large, the number of values p takes in the region is much larger than the number of primes, completing the proof.

Gabriel Wong - 8 years, 1 month ago

Let the constant term of the polynomial be a. If a=0 then f(0) is not prime. Suppose $a\neq0$ . Then f(a)=a (a must be a prime subject to given conditions) since f(a) is divisible by a . Also f(ka)=a $\forall k \in I$ . Consider the polynomial f(x)-a. It is a polynomial of finite degree having infinitely many roots. This not possible unless f(x) is identically equal to 0. But according to our assumption a is not 0. Hence, proved.