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 \displaystyle \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.

Protected: Non-Divisibility of a Product Polynomial

This content is password protected. To view it please enter your password below:

Protected: Non-Trivial Greatest Common Divisor

This content is password protected. To view it please enter your password below: