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 A_{i} is <(a_{i}[1],b_{i}[1]) …(a_{i}[k],b_{i}[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 , 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 z^{N}-1?

**Example: **Suppose A_{1} was <(1,3), (2,2), (-1,1), (-2,0)> and A_{2} was <(5,4), (3,2), (7,0)>. Then A_{1}‘s polynomial is z^{3} + 2z^{2}-z-2, and A_{2}‘s polynomial is 5z^{4}+3z^{2}+7. The product of these is: 5z^{7}+10z^{6} -2z^{5} – 4z^{4 }+ 4z^{3} + 8z^{2}-7z-14. If N=2, then it turns out that z^{2}-1 is a factor (it’s actualy a factor of A_{1}), 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 P_{C} for that clause, and from that Q_{C} = (x^{N}-1)/P_{C} He mentions in his paper that it is “easy to verify” (but doesn’t actually prove it) that The product of all of these Q_{C}‘s / (x^{N}-1) is analytic iff S is inconsistent. I think the reason is that Q_{C} 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.