Results 1 to 2 of 2

Math Help - Integer roots of integer polynomials

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    130

    Integer roots of integer polynomials

    Let L be the language which recognizes polynomials in Z[x] (polynomials with integer coefficients) which have an integer solution. We need to show that L is in NP.

    I am trying to come with up a witness with polynomial size but I can't. Checking every integer 0, 1, -1, 2, -2.... wouldn't work.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765
    If you check 0, 1, -1, 2, -2..., then you are not using any certificate. An obvious idea is to use the root of the polynomial as a certificate.

    Now we need to show that the maximal root has polynomial size compared to the polynomial. One way to do this is to use the following necessary condition for a number to be a root. If a_nx^n+\dots+a_1x+a_0 ( a_i\in\mathbb{Z}) has an integer root, then this root divides a_0. It is easy to show this. (In fact, there is a more general fact about rational roots; the first place I found it is in this PDF file, p. 4.)

    As an unrelated aside, note that if we consider polynomials with arbitrary number of variables and integer coefficients, then the problem of finding out whether a given polynomial has an integer root is undecidable (Hilbert's tenth problem).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 13
    Last Post: August 3rd 2010, 03:16 AM
  2. Find the integer roots of two polynomials.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 1st 2010, 07:17 PM
  3. Integer roots over Z_p
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 1st 2009, 02:39 AM
  4. Integer factoring with polynomials
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: August 23rd 2009, 10:07 PM
  5. Polynomials in integer rings
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 4th 2008, 10:47 AM

Search Tags


/mathhelpforum @mathhelpforum