Loading ...
Sorry, an error occurred while loading the content.

Factoring a particular class of polynomials

Expand Messages
  • Kermit Rose
    The polynomial with all non-negative coeficients p(x) = 1 + v1 x + v2 x^2 + v3 x^3 + . . . v_k x^k where v1
    Message 1 of 1 , Dec 29, 2006
    • 0 Attachment
      The polynomial with all non-negative coeficients
      p(x) = 1 + v1 x + v2 x^2 + v3 x^3 + . . . v_k x^k

      where
      v1 < 3
      v2 < 4
      v3 < 5
      . . .
      v_k < (k+1)

      and

      v_k < 2
      v_(k-1) < 3
      v_(k-2) < 4
      v_(k-3) < 5
      . . .
      v2 < k
      v1 < (k+1)

      Thus for each j, j = 1,2,3 . . .,k

      it is required that

      v_j < min(j+2, k-j-1)


      These conditions ensure that if p(x) is reducible into two factors a(x)
      * b(x),
      each with all non-negative coefficients,
      then the coefficients of a(x) and b(x) are in [0,1].



      p(x) is a product of two polynomials each with all non-negative
      coefficients,

      if and only if

      the elements in the multi-set

      [ [0,1], [1,v1], [2,v2] . . . ]

      can be arranged into a rectangular addition table.

      [j,v_j] means j, repeated v_j times.

      Examples.

      x3 + x2 + x + 1
      is

      [ [0,1],[1,1],[2,1],[3,1] ]

      which yields the addition table

      0 1
      2 3

      producing factors from top row and left column

      of (x + 1) * (x^2 + 1)


      x^2 + 2 x + 1

      is [ [0,1], [1,2], [2,1] ]

      which yields the addition table

      0 1
      1 2

      producing factors from top row and left column

      of (x + 1) * (x + 1)

      x^3 + 2 x^2 + 2 x + 1
      is
      [ [0,1], [1,2],[2,2],[3,1] ]

      which yields

      0 1 2
      1 2 3

      producing factors from top row and left column
      (x^2 + x + 1) * (x + 1)


      x^7 + x^6 + 2 x^5 + 3 x^4 + 3 x^3 + 2 x^2 + 2 x + 1

      is

      [ [0,1],[1,2],[2,2],[3,3],[4,3],[5,2],[6,1],[7,1] ]

      which easily yields the addition table

      0 1 2 3 4
      1 2 3 4 5
      3 4 5 6 7


      producing factors from top row and left column


      (x^4 + x^3 + x^2 + x + 1) * ( x^3 + x + 1)


      I think it's possible to extend this theory to cases where the the v's
      are permitted to be negative.

      but to do so may require me to figure out an interpretation of
      multi-sets with elements of negative multiplicity.


      I also expect that it could be extended to cases where the v's are not
      constrained by upper or lower bounds,
      but it's not yet clear to me how that would effect the corresponding
      multi-sets.

      I have a vague notion that the upper and lower bound constraints would
      be replaced by constraint
      equations relating the v's to each other.


      Kermit < kermit@... >
    Your message has been successfully submitted and would be delivered to recipients shortly.