# values of a polynomial

• Aug 12th 2010, 02:17 AM
Sam1992
values of a polynomial
I have a polynomial with only natural numbers as coefficients. Now I search for all such polynomials with the following additional property:

When I plug every natural number in it there is an infinite set of natural numbers not being derived.

I think the answer should be all polynomials of degrees greater or equal 2 and all linear polynomials except for x,x+1,x+2,x+3,...

But I don't know whether this is right and I can't prove it.
• Aug 12th 2010, 03:41 AM
Vlasev
I think you are right and you are on the right track. Lets look at degree two polynomials and above. Let $P(x)$ be a polynomial of degree $n\ge 2$. Let the smallest positive real root be $a$ and the largest positive real root be $b$. In the range $[a,b]$ you get a lot of swerving around and it'll be difficult to find the distribution of natural numbers that it hits in that area.

Now lets focus our attention on the values of the polynomial beyond the biggest root. Since the coefficients are natural numbers we must have that the polynomial will be positive after that last root. From here on lets examine the interval $[c, c+1]$ where $c > b$. We need that the polynomial misses infinitely many natural numbers. So if $P(c+1) \ge P(c) +2$, then we the polynomial misses one number in that range. Since the range was arbitrary with $c > b$, we must have that for every such range we are missing at least one natural number. Since there are infinitely many of these intervals, we are missing infinitely many numbers.

The key step will be to show that $P(c+1) \ge P(c) + 2$ (or $P(c+1) > P(c) + 1$ if yo u prefer a tighter bound). You can either do it directly or you can represent the polynomial in a clever way to make it easier for yourself.

Now if $P(x) = const.$, we surely get that the polynomial misses infinitely many natural numbers. The only posibility left is to consider a polynomial $P(x) = a x +b$ for natural numbers a and b and see when it misses inf. many points and when it does not. It should be pretty straightforward.
• Aug 15th 2010, 12:16 AM
Sam1992
ok,first of all thanks for the reply,

I (finally) solved the cases constant and linear.

But i do not understand your explanations on degrees greater or equal 2.
If the coefficients are all positive the whole polynomial should be positive everywhere, right?

I also tried factorizing the polynomial but this did not work out.
• Aug 15th 2010, 01:11 AM
Vlasev
You are absolutely right! That is, it'll be positive for all positive numbers x. For the actual polynomial

$P(x) = a_0+a_1x+a_2x^2+\cdots+a_nx^n$

This you can factor out like this

$P(x) = a_0+a_1x+x^2(a_2+a_3x+a_4x^2+\cdots+a_nx^{n-2}) = a_0+a_1x+x^2Q(x)$

Where $Q(x)$ is the part in the brackets. Now, since $n \ge 2$, we have that $Q(x)$ has degree $\ge 0$. This means that it is at least as big as the constant $a_2$. So in any case we have that $Q(x+1) \ge Q(x)$

Then you have the following. $P(x+1)$ is equal to:

$\displaystyle = a_0+a_1(x+1)+(x+1)^2Q(x+1)[/tex] (line 1)

[LaTeX ERROR: Convert failed] (line 2)

[LaTeX ERROR: Convert failed] (line 3)
[tex]\displaystyle = (a_0+a_1x+x^2Q(x))+(a_1+(1+2x)Q(x))" alt="\displaystyle = a_0+a_1(x+1)+(x+1)^2Q(x+1)[/tex] (line 1)

[LaTeX ERROR: Convert failed] (line 2)

[LaTeX ERROR: Convert failed] (line 3)
[tex]\displaystyle = (a_0+a_1x+x^2Q(x))+(a_1+(1+2x)Q(x))" /> (line 4)

[LaTeX ERROR: Convert failed] (line 5)

Now you have that $Q(x) \ge a_2 \ge 1$ since the coefficients are natural numbers. Also $x>0$ and $a_1 \ge 1$ So the last bit is

[LaTeX ERROR: Convert failed]

[LaTeX ERROR: Convert failed] (line 6)

Thus [tex]\displaystyle P(x+1) \ge P(x)+2[/tex] and thus every such polynomial skips at least one natural number.
• Aug 15th 2010, 01:25 AM
Sam1992
Great, thanks!

It does not look like I would have figured it out by myself, but reading this I think I understand it.
• Aug 15th 2010, 01:33 AM
Vlasev
No problem. Do you have questions about any of the steps?
• Aug 15th 2010, 01:43 AM
Sam1992
if we have f(x)=x^2 then it is 0,1,4,9,....
4,9,....no problem, but 0,1 does not skip a natural number, although your proof claims to be valid for every natural number.

So I guess, we have to consider some special cases?

edit: wait, got it, x>0

I thought 0 is a natural number, but it does not matter anyway since there infinity skips

edit2: when 0 is a natural number, I have to modify the proof a little bit (at the few last lines) and it still works out
• Aug 15th 2010, 01:53 AM
Vlasev
Quote:

Originally Posted by Sam1992

I thought 0 is a natural number, but it does not matter anyway since there infinity skips

Yea, you got it. After I wrote my proof, I realized that i could have chosen x>1 to avoid confusion. It will probably be a really good exercise to see if the property follows for polynomials with integer coefficients. Well, it does hold, but you have to make some restrictions on the degree and one or more of the coefficients.