Results 1 to 8 of 8

Math Help - values of a polynomial

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2010
    Posts
    5
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    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:

    [LaTeX ERROR: Convert failed] (line 2)

    [LaTeX ERROR: Convert failed] (line 3)
    [Math]\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)[/Math] (line 1)

    [LaTeX ERROR: Convert failed] (line 2)

    [LaTeX ERROR: Convert failed] (line 3)
    [Math]\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 [Math]\displaystyle P(x+1) \ge P(x)+2[/tex] and thus every such polynomial skips at least one natural number.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2010
    Posts
    5
    Great, thanks!

    It does not look like I would have figured it out by myself, but reading this I think I understand it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    No problem. Do you have questions about any of the steps?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2010
    Posts
    5
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    Quote Originally Posted by Sam1992 View Post

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 3rd 2012, 11:45 PM
  2. Predicting maximum values from minimum values
    Posted in the Statistics Forum
    Replies: 0
    Last Post: October 4th 2011, 08:42 AM
  3. Replies: 1
    Last Post: June 1st 2011, 02:47 AM
  4. Replies: 2
    Last Post: January 28th 2010, 02:39 AM
  5. Replies: 1
    Last Post: May 24th 2009, 06:16 AM

Search Tags


/mathhelpforum @mathhelpforum