Monthly Archives: November 2018

Root of Modulus 1

After taking a week off for Thanksgiving, we move on to another equation problem.

The problem: Root of Modulus 1.  This is problem AN10 in the appendix.

The description: Given a set of ordered pairs (a_1,b_1) through (a_n, b_n) of integers, each b_i is non-negative.  Can we find a complex number q where \mid q \mid= 1 such that \sum_{i=1}^n a_i * q^{b_i} =0?

Example: It was hard for me to come up with an interesting example (where q is not just 1 or i), so thanks to this StackOverflow post for giving me something I could use.

Let our ordered pairs be (5,2), (-6,1), and (5,0).  This gives us the polynomial 5x2-6x+5.  Plugging these into the quadratic formula get us the roots \frac{3}{5} \pm  \frac{4}{5} i, which is on the complex unit circle.

Reduction: This one is again from Plaisted’s 1984 paper.  It again uses his polynomial that we’ve seen in some other problems (most recently Non-Divisibility of a Product Polynomial).  So again, we start with a 3SAT instance and build the polynomial.  He starts by showing that if you have a polynomial with real coefficients p(z), then p(z)*p(1/z) is a real, non-negative polynomial on the complex unit circle, and it has zeros on the unit circle exactly where p(z) does.

Then, we can do this for the sum of the polynomials made out of each clause, which means that this new polynomial has 0’s on the unit circle exactly where the original one did.  Which means it has a 0 on the complex unit circle if and only if the formula was consistent.

Difficulty: 8.  I’m starting to appreciate the coolness of turning a formula into a polynomial, and how it makes a lot of problems easier.  I just wish it was clearer to see how it all works.

 

Algebraic Equations over GF[2]

AN8 is Quadratic Diophantine Equations.

The problem: Algebraic Equations over GF[2].  This is problem AN9 in the appendix.

The description: Given a set P of m polynomials over n variables (x1 through xn) where each polynomial is the sum of terms that is either 1 or the product of distinct xi, can we find a value ui for each xi in the range {0,1} that make each polynomial 0, if we define 1+1=0, and 1*1 = 1?

Example: It helps to think of GF[2] as a boolean logic world, where + is XOR and * is AND.  So, suppose we have three variables, and the polynomials:

  • P1 = 1 + x1x2 + x2x3
  • P2 = x1 + x1x2x3

..Then setting x1=0, x2=1, x3=1 makes both polynomials 0.

Reduction: G&J say that Fraenkel and Yesha use X3C, but the paper I found uses 3SAT.  We’re given an equation that has n variables and m clauses.  The variables of our polynomials will be the same variables in the 3SAT instance.  For each clause, we build a polynomial by:

  • Replacing a negated literal (~x) with the equation 1 + x.  (Remember, + means XOR in this system)
  • Replacing an OR clause (A ∨ B) with the equation A+ B +A*B
  • Xoring the whole above thing with 1.

Notice that the first replacement makes ~x have the opposite truth value of x, the second replacement rule is logically equivalent to A∨B, and the third part makes the polynomial 0 if and only if the clause evaluated to 1.  So the polynomial is 0 if and only if the clause is satisfiable.  So all polynomials are 0 if and only if the all clauses are satisfiable.

Difficulty: 5.  This is easy to follow.  It’s a little tricky to make students come up with the equivalence rules above, but I think if you can explain it right, it’s not that bad.

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.

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.