## Factoring a particular class of polynomials

Expand Messages
• 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] ]

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] ]

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.