1
$\begingroup$

I have a natural number $m$, and a polynomial $p: \mathbb{Z}^n \rightarrow \mathbb{Z}$, and I need to find a set $(x_1, x_2,...,x_n)$ so that $p(x_1, x_2,...,x_n) \bmod m = 0$.

First: Does every non-constant polynomial have such a set? And more importantly: Does there exist an (efficient) procedure to determine it, in case a set exists?

  • 0
    No, a solution does not always exist. Take $p(x) = 2x+1$, and $m=2$; or $p(x)=x^2+x+1$, again with $m=2$. For a two variable example, take $p(x,y) = x^2+y^2+x+y+1$ with $m=2$; since $(x^2+x)+(y^2+y)$ is always even, $p(x,y)$ is never even.2011-01-24
  • 0
    Thank you for that quick answer. That restricts the question for the procedure to the case that such set exists. (I edited the question accordingly)2011-01-24
  • 1
    They objects are usually called "polynomials" in English, and not "polynoms".2011-01-25
  • 0
    A partial answer to the first question: If $m$ is prime and the number of variables $n$ is bigger than the degree of the polynomial $p$ then by [Chevalley's Theorem](http://mathworld.wolfram.com/ChevalleysTheorem.html) the number of zeros is divisible by $p$. This might be useful if you already know a solution as in the case when there is no constant term.2011-01-25

1 Answers 1

1

If I am not mistaken, this is not known. When $m = 2$ this problem is equivalent to Boolean satisfiability (SAT for short), which is known to be NP-complete. This is because one can represent logical operations as polynomial operations on the finite field $\mathbb{F}_2$ (with $0$ being false and $1$ being true) as follows:

$$\neg x = 1 - x, x \text{ and } y = xy, x \text{ or } y = x + y + xy.$$

It follows that any Boolean expression in $n$ Boolean variables $x_1, ... x_n$ can be written as a polynomial over $\mathbb{F}_2$, and finding solutions is equivalent to finding a non-satisfying assignment for the Boolean expression (so replacing the expression with its negation we get the usual form of SAT). So the question of whether there exists a polynomial-time algorithm for solving this problem is equivalent to P vs. NP.

I was mistaken! Well, in any case, this paper might be relevant.

  • 1
    The size of the polynom resulting from a formula in CNF is not bounded polynomially, therefore this reduction is not in $P$. (Add: The arithmetization of $x \vee y$ is $x + y - xy$)2011-01-24
  • 0
    @Mike: whoops. Very good point.2011-01-24