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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Arturo Magidin
    Commented Jan 24, 2011 at 22:16
  • $\begingroup$ 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) $\endgroup$
    – Mike B.
    Commented Jan 24, 2011 at 22:31
  • 1
    $\begingroup$ They objects are usually called "polynomials" in English, and not "polynoms". $\endgroup$
    – Arturo Magidin
    Commented Jan 25, 2011 at 1:29
  • $\begingroup$ 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 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. $\endgroup$
    – Esteban Crespi
    Commented Jan 25, 2011 at 11:21

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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$) $\endgroup$
    – Mike B.
    Commented Jan 24, 2011 at 23:36
  • $\begingroup$ @Mike: whoops. Very good point. $\endgroup$
    – Qiaochu Yuan
    Commented Jan 24, 2011 at 23:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .