Non-Trivial Greatest Common Divisor

We’ll do this next one out of order because I think this order is better explained by the paper.

The problem: Non-Trivial Greatest Common Divisor.  This is problem AN7 in the appendix.

The description: 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.  I’m pretty sure k can be different in each sequence.  If we build the polynomials \sum_{j=1}^k a_i[j]*z^{b_i[j]}, for each i from 1 to m, does the greatest common divisor of those polynomials have degree greater than 0?

Example: I think the hardest part of this description is picturing the polynomials, so here’s a simple example showing how that works.  Suppose m=2, and A1 was <(20,3),(4,2),(30,1)> and A2 was <(2,4),(8,1)>

(As an aside, I wish G&J didn’t use A for both the name of a sequence and lowercase a for the name of one of the entries of each pair.  They’re not related.)

The polynomial corresponding to A1 is 20x3 + 4x2+30x, and the polynomial corresponding to A2 is 2x4 +8x.  The polynomial 2x is a divisor of both, and I think it’s the GCD.  (If not, the GCD is larger, and so also has degree >0).  So, this problem instance would have the answer “yes”.

Reduction:

This reduction is also by Plaisted, who did last week’s reduction, but is in his 1984 paper.  His reduction is from 3SAT.  In the paper, he gives an algorithm that turns a logical formula into a polynomial.  The polynomial p that gets created has the property that p(z) = 0 if and only if z is an M-th root of unity (a solution to zM=1).  This leads to a way of setting the truth values of the logical formula: if ω is the root of unity, set variable Pj to true if ω^{M/q_j}=1, where qj is the jth prime number.  It turns out if you do that, you make the entire logical formula true.

So, for our problem, we’re handed a 3SAT instance with n variables.  Let M be the product of the first n primes.  The formula is satisfiable iff we can make all clauses true, which happens iff there is an Mth root of unity ω such that the polynomial on each clause is 0 (so we make a polynomial for each clause in the SAT formula). He states an “easy” identity (without proof) that the polynomial of A∧B is the gcd of the polynomials of A and B.  So therefore if ω exists for all polynomials, the gcd has degree greater than 0.

Difficulty: 8.  This is a little easier to follow because he states the properties of his polynomial up front.  I’d like to see more proofs of his “easy” properties and to be honest, I’m not sure how the last step happens (how having ω exist means that the gcd has degree > 0).  I also don’t know how you’d ask students to come up with these polynomials on their own.

Leave a Reply

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