Category Archives: Appendix- Algebra and Number Theory

Periodic Solution Recurrence Relation

Probably the last post of the year- enjoy the holidays, everyone!

The problem: Periodic Solution Recurrence Relation.  This is problem AN12 in the appendix.

The description: Given a set of m ordered pairs (c_1,b_1) through (c_m, b_m with each b_i >0, can we find a sequence a_0 though a_{n-1} of integers, such that if we build the infinite sequence a_i = \sum^m_{j-1} c_j*a_{i-b_j} is periodic: that is, a_i \equiv a_{i mod n} for all i?

Example: Here’s a super simple example: m=2 and the pairs are (1,1) and (2,2).  This gives us the recurrence a_i = a_{i-1}  + 2a_{i-2}.  If we start with 1,1, this gives the sequence 1,1,3,5,11,21,43,…  which is periodic mod 10 (the last digit always repeats 1,1,3,5)

Reduction: This shows up in Plaisted’s 1984 paper.  He mentions it as a corollary to his Theorem 5.1 which showed that Non-Trivial Greatest Common Divisor and Root of Modulus 1 were NP-Complete.  Similar to the Root of Modulus 1 problem, we build a polynomial from a set of clauses that has 0’s on the unit circle.  The polynomial also has a leading coefficient of 1.  This means, apparently, that the recurrence relation corresponding to the polynomial has a periodic solution if and only if the polynomial has a root on the complex unit circle, which only happens if the original 3SAT formula was satisfiable.

Difficulty: 8.

Number of Roots for a Product Polynomial

The problem: Number of Roots for a Product Polynomial.  This is problem AN11 in the appendix.

The description: Given a set of sequences A1 through Am , each Ai containing a sequence of k pairs (a_i[1],b_i[1]) through (a_i[k],b_i[k]) , and an integer K.  If we build a polynomial for each Ai by \sum_{j=1}^k a_i[j]*z^{b_i[j]}, and then multiply all of those polynomials together, does the resulting product polynomial have less than K complex roots?

Example:  Suppose A1 was <(1,2), (2,1), (1,0)>, A2 was <(3,3), (2,2), (1,1), (0,0)>, and A3 was <(5,1), (7,0)>.  These represent the polynomials x2+2x+1, 3x3 + 2x2 + x, and 5x+7.  (I’m pretty sure it’s ok for the sequences to be of different length, because we could always add (0,0) pairs to shorter sequences).  This multiplies out to 15 x6 + 61 x5 + 96 x4+ 81 x3 +  50 x2 + 26x +7, which has 4 distint complex roots, according to Mathematica.

Reduction: This is another one that uses Plaisted’s 1977 paper.  (It’s problem P4).  He builds the polynomials PC and QC in the same way that he did in the reduction for Non-Divisibility of a Product Polynomial.  One of the statements that he says is “easy to verify” is that The product of the Q polynomials for each clause has N (for us, K) zeroes in the complex plane if and only if the original 3SAT formula was inconsistent.

Difficulty: I’m giving all of these problems based on the polynomials that come from a formula an 8.

Exponential Expression Divisibility

AN4 is Comparative Divisibility.

This next problem is related to one we’ve done before, but I think it merits its own entry.

The problem: Exponential Expression Divisibility.  This is problem AN5 in the appendix.

The description: Given two sequences A = a1..an and B=b1..bof positive integers, and an integer q. Does \prod_{i=1}^{n} (q^{a_{i}}-1) divide \prod_{i=1}^{m} (q^{b_{i}}-1)?

Let A={2,3} and B={1,4,5}.  If q=4, then the first product comes to 15×63=945 and the second product comes to 3x255x1023 = 782,595.  These two numbers don’t divide.

Reduction: Plaisted’s paper calls this a “refinement” of Polynomial Non-Divisibility.

The reduction for that built a polynomial called “Poly(Cj)”  and showed xN-1 is a factor of \prod_{j=1}^{k}Poly(~Cj)(x) if and only if S is inconsistent.  As I said in that post, there was a lot I don’t understand about it, because he doesn’t give clear proofs or explanations.  He uses some more manipulations to say that the SAT formula is inconsistent iff 2mn-1 divides \prod_{j=1}^{k} \frac{(2^{mn}-1) * Denom(C_j)(2^m)}{Num (C_j)(2*m)} .  (“Num” and “Den” were used in the creation of “Poly”).  This gives us a restatement of the Exponential Expression Divisibility problem where q =2.  Since there was nothing special about the 2, it could work for any integer and thus the reduction works in general.

Difficulty: 9.  Just like the Polynomial Non-Divisibility problem, I have a very hard time following what he’s doing here.  I wish I could find some better explanations

Simultaneous Divisibility of Linear Polynomials

Sorry for missing last week- my grading backlog is getting out of hand.

The problem: Simultaneous Divisibility of Linear Polynomials.  This is problem AN3 in the appendix.

The description: Given two sets A and B, each containing n vectors, each vector having m+1 integer entries (so for example, vector ai has values ai[0] through ai[m]) , can we find m positive integers x1 through xm such that for each pair of vectors ai and bi,

(ai[0] + ai[1]*x1 + ai[2]*x2+…+ai[m]*xm) divides (bi[0] + bi[1]*x1 + bi[2]*x2+…+bi[m]*xm)

Example: Suppose a1 was (1,2,3), b1 was (2,4,6), a2 was (4,2,4), and b2 was (7,9,10).  Then if I pick x1 = 3, x2 = 2, a1‘s equation evaluates to 13 and b1‘s evaluates to 26.   a2‘s equation evaluates to 18, and b2‘s equation evaluates to 54.  Since both a values divide their corresponding b values, we have found an x1 and x2 that work.

Reduction: The paper I found by Lipschitz that has the reduction reduces from Quadratic Congruences.  He starts by assuming that m ≤ 2n because at most 2n of the ai and bi are independent (and so the extra variables can be made equivalent to the first 2n variables by transformation).    He also uses a variation of Quadratic Congruences that states the problem is still NP-Complete if c ≤ b/2.  Then given a,b, and c, we build our divisibility problem with 5 formulas over the variables x, y, u, and v:

  • x+u | c+1
  • 4y + v | b2-1
  • x+b | y-b2
  • x+b+1 | y-(b+1)2
  • b | y-a

It turns out that if we can find an x such that x2 ≡ a mod b if and only if we can find x,y,u, and v to satisfy those divisibility problems.

If we can solve the quadratic congruence, then setting y=x2, u = c-x+1 and v = b2 – 4x2 + 1 satisfies all of the divisibility equations.

In the other direction, if we have found x,y,u, and v that works, we know:

  • x ≤ c (which is ≤ b/2) from the first equation
  • y ≤ b2/4 from the second equation
  • y = x2 + k(x+b)*(x+b+1) for some k ≥ 0 from the 3rd and 4th equations

Suppose k is not 0, and thus y is not equal to x2.  Then y has to be > b2, which violates the second fact above.  So k is really 0 and y=x2.  Then the last equation is a restatement of the quadratic congruence problem, and y (=x2 ) is congruent to a mod b.

Difficulty: 7.  I think the way this all works out is very slick, and I like how the equations give you the answer, but I have no idea how you’d come up with these equations on your own.

Simultaneous Incongruences

Back to the problems we’ve skipped over, starting with a cool take on the classic “Chinese Remainder Theorem”.

The problem: Simultaneous Incongruences.  This is problem AN2 in the appendix.

The description: Given n pairs of positive integers (a1, b1)…(an, bn), can we find an integer x such that x \not\equiv ai mod bi?

(G&J also add the rule that  ai ≤ bi for all i, but we can easily make that happen by doing division)

Example: I think it’s easier to see this as the actual congruences:

Can we find an x such that:

  • x \not\equiv 1 mod 2
  • x \not\equiv 2 mod 3, and
  • x \not\equiv 3 mod 4?

If we chose x as 4, we’ll see that it works.  For a simple example of a case that fails, we can do:

  • x \not\equiv 1 mod 3
  • x \not\equiv 2 mod 3, and
  • x \not\equiv 3 mod 3

Reduction: I found this reduction in the Algorithmic Number Theory book by Bach and Shallit.  Their Theorem 5.5.7 calls this the “Anti-Chinese Remainder theorem”.  They reduce from 3SAT.

Our formula will have t variables and each clause in our formula is made up of 3 literals, which we’ll represent as Ci = (zai∨zbi∨zci).  For each ai find pai, the aith prime number, and find pbi and pci similarly.  Define ai‘ to be 0 if zai is a positive literal, and 1 if it’s a negative literal, and define bi‘ and ci‘ similarly.   Now for each clause, use the regular Chinese Remainder theorem to find a value xi where:

  • xi \equiv ai‘ mod pai
  • xi \equiv bi‘ mod pbi
  • xi \equiv ci‘ mod pci

Our system of incongruences will be:

  • x \not\equiv 2 (mod 3)
  • x \not\equiv 2,3 (mod 5)
  • x \not\equiv 2,3,4,…pt (mod pi)   (pt is the tth prime number)

The above incongruences are there to force x to be 0 or 1 mod each pi. I think these correspond to true-false values to the variables in the SAT instance (x being 0 mod pi means setting that variable false, making it 1 mod pi means setting that variable true)

  • x \not\equiv xi (mod pai*pbi*pci) for each i

This turns out to be O(n+t3) incongruences by the Prime Number Theorem.

Each clause in the SAT instance is satisfiable unless all 3 literals are false.  By the way we’ve created our ai‘  (and b and c), this means that the variables can’t be set to be equal to all of ai‘, bi‘ and ci‘.  Because of how our xi was chosen, this means that x is not congruent to xi (mod pai*pbi*pci).

Difficulty: 7.  This is a cool short reduction, but the way the x value works is something you don’t usually see.

Quadratic Diophantine Equations

Since this problem’s reduction is basically the same as last week’s, let’s skip ahead to it now.

The problem: Quadratic Diophantine Equations.  This is problem AN8 in the appendix.

The description: Given positive integers a,b, and c, can we find positive integers x and y such that ax2 + by = c?

Example: Let a=1, b = 2, and c=5.  Then we’re asking if positive integers x and y exists to solve x2 + 2y = 5.  This is true when x=1 and y = 2.  If we change b to 3, then there are no positive integers x and y where x2 + 3y = 5.  (y has to be positive, so the only y that has a chance of working is y=1, which would require x to be √2)

Reduction: This is in the same paper by Manders and Adleman that had the reduction for Quadratic Congruences.  In fact, the reduction is almost exactly the same.  We go through the same process of creating the Subset Sum problem, and build the same H and K at the end.  The only difference is the instance: We build the quadratic (K+1)3*2*8m+1*(H2-x2) + K(x2-r2)-2K*8m+1y = 0.  We can multiply out the vales to get a,b, and c.

The rest of the reduction uses similar crazy algebra to the last problem.

Difficulty: 9, for the same reasons last week’s problem was.

Quadratic Congruences

On to the next section!  The “Algebra and Number Theory” section should take us through the end of the year.

The problem: Quadratic Congruences.  This is problem AN1 in the appendix.

The description: Given positive integers a,b, and c, can we find a positive integer x < c such that x2 ≡ a (mod b)?

Example: Let a = 3, b = 7, c = 13. It turns out that for every x < c, x2≡ either 0,1,2 or 4 mod b.   So this isn’t solvable.  But if we change a to 2, then the first c that works is 3.

One thing I learned in doing this problem is that the squares of mod b will always form a cycle with period b.  The proof is a pretty cool algebra problem if you set it up right.

Reduction: The paper by Manders and Adleman uses 3SAT.  Starting from the list of variables, they define a set Σ that holds all 3-element clauses of 3 different literals from that list of variables.  We won’t actually build this set (that’s exponential), but we can list out a number j for each of those clauses.  Then define τΦ to be -1* the sum of 8j for each of the j numbers that correspond to the clauses in our actual formula.

For each variable i, we define fi+ to be the sum of 8j for each j number in ∑ that has that variable positively, and fi to be -1* the sum of 8j for each number in Σ that has the variable negatively.

Let m be|Σ|, and set n=2m +The number of variables, and define a set C wit values c0 through cn:

  • c0 = 1
  • If j is odd(=2k-1) and ≤ 2m, cj = -8k/2
  • If j is even (=2k) and ≤ 2m, cj = -8k
  • If j is > 2m (= 2m+i), then cj = (fi++fi)/2

Set τ = τΦ + The sum of all of the ci‘s + The sum of all of the fi‘s.

This actually turns into a Subset Sum problem: Let C be our set, and count each value positively if we take it, and negatively if we don’t take it.

But we still need to prove this is SOS problem is solvable exactly when the original problem is.

Create a set p0 .. pn of consecutive prime numbers where the first one (p0) is 13.  Then define a set of θj values as the smallest number satisfying:

  • θj≡ ci (mod 8m+1)
  • θj ≡ 0 (mod The product of each (pi)n+1, except for j.)
  • θj is NOT ≡ 0 (mod pj)

Set H = The sum of all of the θj‘s.  Set L=the product of all of the (pi)n+1.  We are finally ready to create our Quadric Congruence instance:

b = 2*8m+1*K.

Let d = The inverse of (2*8m+1+K), mod b.

Then a = d*(K*τ2+2*8m+1 * H2)

c = H.

From here, it’s a bunch of algebra to show that an x exists if and only if the original formula was satisfiable.

Difficulty: 9.  Maybe it should be 10.  I don’t know enough number theory to be convinced that the θ’s exist, and be computed in polynomial time.  The algebra I’m glossing over is pretty complicated as well.