Non-Divisibility of a Product Polynomial

Now back to the problem we skipped over last week.

The problem: Non-Divisibility of a Product Polynomial.  This is problem AN6 in the appendix.

The description: Just like Non-Trivial Greatest Common Divisor, we’re given a set of m sequences of pairs of  integers (so sequence Ai is <(ai[1],bi[1]) …(ai[k],bi[k])>), where each b element is ≥ 0.  We’re also given an integer N.

Just like Non-Trivial Greatest Common Divisor, we build the polynomials \sum_{j=1}^k a_i[j]*z^{b_i[j]}, for each i from 1 to m.  But now we want to multiply them all together.  If we do, is the product not divisible by zN-1?

Example: Suppose A1 was <(1,3), (2,2), (-1,1), (-2,0)> and A2 was <(5,4), (3,2), (7,0)>.  Then A1‘s polynomial is z3 + 2z2-z-2, and A2‘s polynomial is 5z4+3z2+7.  The product of these is: 5z7+10z6 -2z5 – 4z4 + 4z3 + 8z2-7z-14.  If N=2, then it turns out that z2-1 is a factor (it’s actualy a factor of A1), so the decision problem would say “No”.

Reduction: The reduction for this is again by Plaisted, using his polynomials that come from logical statements. For each clause C of a 3SAT formula, you build the polynomial PC for that clause, and from that QC = (xN-1)/PC  He mentions in his paper that it is “easy to verify” (but doesn’t actually prove it) that The product of all of these QC‘s / (xN-1) is analytic iff S is inconsistent.  I think the reason is that QC represents in his polynomial the ways to assign variables to make a formula false. So if all assignments make it false, the product is equal to all assignments.  I still don’t quite see how the divisibility follows.

Difficulty: 8.  It’s about as hard as the last one.

Leave a Reply

Your email address will not be published. Required fields are marked *