Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Arturo Magidin Jan 24 '11 at 22:16
    
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) –  Mike B. Jan 24 '11 at 22:31
1  
They objects are usually called "polynomials" in English, and not "polynoms". –  Arturo Magidin Jan 25 '11 at 1:29
    
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. –  Esteban Crespi Jan 25 '11 at 11:21

1 Answer 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.

share|improve this answer
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$) –  Mike B. Jan 24 '11 at 23:36
    
@Mike: whoops. Very good point. –  Qiaochu Yuan Jan 24 '11 at 23:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.