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 through ai[m]) , can we find m positive integers x1 through xm such that for each pair of vectors ai and bi,
(ai + ai*x1 + ai*x2+…+ai[m]*xm) divides (bi + bi*x1 + bi*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.