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, 6 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears 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

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, 6 months ago

Log in to reply

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, 6 months ago

Log in to reply

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, 6 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, 6 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, 6 months ago

Log in to reply

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, 6 months ago

Log in to reply

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, 6 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, 6 months ago

Log in to reply

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, 6 months ago

Log in to reply

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, 6 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, 6 months ago

Log in to reply

@Sambit Senapati Can someone help me out here?

Vikram Waradpande - 4 years, 6 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, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...