Waste less time on Facebook — follow Brilliant.
×

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.

Note by Vikram Waradpande
4 years, 3 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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 · 4 years, 3 months ago

Log in to reply

@Gabriel Wong 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 · 4 years, 3 months ago

Log in to reply

@Calvin Lin 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 · 4 years, 3 months ago

Log in to reply

Can such an infinite polynomial exist? How to approach such a problem? What are the properties of an infinite polynomial?

Please express your thoughts on the above question, guys. Sambit Senapati · 4 years, 3 months ago

Log in to reply

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. Sambit Senapati · 4 years, 3 months ago

Log in to reply

@Sambit Senapati You need to be careful with your proofs. Make sure you write down everything that's in your head, as the rest of us are not mind-readers.

Your proof is currently incomplete: 1. I believe that you are missing the sentence "If \(a\) is composite, then \(f(0)\) is not prime".
2 You also need to justify why \(f(a) = a \). Why can't we have \(f(a) = -a \) ? Calvin Lin Staff · 4 years, 3 months ago

Log in to reply

@Calvin Lin I thought that primes should be considered positive, unless otherwise stated. http://en.wikipedia.org/wiki/Prime_number and http://mathworld.wolfram.com/PrimeNumber.html define primes over positive integers. Sambit Senapati · 4 years, 3 months ago

Log in to reply

I found a much simpler proof. Here it goes: \[\] Consider \(p(x)=a_n x^n+a_{n-1}x^{n-1}...a_1 x^1 + a_0 = m.\) Now consider \(p(x+m)\). By expanding, we get that \(m\) divides \(p(x+m). \) So, such a polynomial doesn't exist. Vikram Waradpande · 4 years, 3 months ago

Log in to reply

@Vikram Waradpande How does only showing that m|p(x+m) prove that such a polynomial doesn't exist? m can be a prime and p(x+m) can be m. In my opinion, a little more explanation is required. Sambit Senapati · 4 years, 3 months ago

Log in to reply

@Sambit Senapati I think this proof is alright. We claim that such a prime polynomial exists. But then we show that for \(p(x+m)\) , it can be divided by \(m\). Then no matter what \(m\) is, a prime or composite. And \(p(x+m)\) cannot be \(m\). I guess the proof is complete. Vikram Waradpande · 4 years, 3 months ago

Log in to reply

@Vikram Waradpande But you didn't prove why p(x+m) can't be m. Sambit Senapati · 4 years, 3 months ago

Log in to reply

@Sambit Senapati Can someone help me out here? Vikram Waradpande · 4 years, 3 months ago

Log in to reply

@Vikram Waradpande Hint: Set \(m = p(0)\), which is prime by assumption. What does this tell us about the possible values of \(p(n)\) where \(n\) is an integer?

Hint: Any finite degree polynomial which takes on a value infinitely often is the constant polynomial. Calvin Lin Staff · 4 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...