Monthly Archives: October 2018

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.