On special type polynomial inequalities over integers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T22:11:20Z http://mathoverflow.net/feeds/question/37673 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37673/on-special-type-polynomial-inequalities-over-integers On special type polynomial inequalities over integers Bakh 2010-09-03T23:04:04Z 2010-09-04T14:17:36Z <p>A special monomial is a monomial of the form $C\cdot x_{i_1} \cdot \ldots \cdot x_{i_n}$, where C is an integer and no variable is repeated more than once in the monomial. For instance, $x\cdot y\cdot z\cdot u\cdot w$ is special while $x\cdot y\cdot z\cdot u\cdot w\cdot z$ is not since z is repeated. A special polynomial is a sum of special monomials. The question is the following. Is there an algorithm, that given a system of finite set of in-equations with special polynomials, decides if the system has integer solution?</p> http://mathoverflow.net/questions/37673/on-special-type-polynomial-inequalities-over-integers/37674#37674 Answer by David Speyer for On special type polynomial inequalities over integers David Speyer 2010-09-03T23:10:28Z 2010-09-04T14:17:36Z <p><strong>ADDED:</strong> As Mark Sapir and other are pointing out, if you only have $\neq$'s, no $=$'s, <code>$&lt;$</code>'s or <code>$&gt;$</code>'s, then there is always a solution. That is to say, if $u_1$, $u_2$, ..., $u_N$ are nonzero polynomials, then there is always a lattice point where all the $u_i$ are nonzero. I assume you are asking the nontrivial question and allowing <code>$&lt;$</code>'s and <code>$&gt;$</code>'s:</p> <hr> <p>No. Any set of equations can be turned into a set of special equations. For example, if you have the equation $x^3 y^2 z + x^2 = 7$, just introduce new variables $x_1$, $x_2$, $x_3$, $y_1$, $y_2$ and $z_1$, and write down the special equations $x_1=x_2$, $x_2=x_3$, $y_1=y_2$ and $x_1 x_2 x_3 y_1 y_2 z + x_1 x_2 =7$. This is often called the polarization trick.</p> <p>So special equations are no simpler than ordinary equations and, as I imagine you know, there is no algorithm to solve Diophantine equations.</p> <p>I just noticed that you said "inequalities" not equalities. But any Diophantine equation can be rewritten as an inequality: $f(x,y,z)=0$ is the same as $-1 &lt; f(x,y,z) &lt; 1$, and any inequality as an equality: $z \geq 0$ is equivalent to $\exists (p,q,r,s) : z=p^2+q^2+r^2+s^2$. So this doesn't gain or lose you any generality.</p> http://mathoverflow.net/questions/37673/on-special-type-polynomial-inequalities-over-integers/37688#37688 Answer by Mark Sapir for On special type polynomial inequalities over integers Mark Sapir 2010-09-04T03:54:20Z 2010-09-04T03:54:20Z <p>In fact any systems of inequations $u\ne 0$ where $u$ is a non-zero polynomial with integer coefficients has an integer solution. So the problem about inequations is obviously decidable. </p> http://mathoverflow.net/questions/37673/on-special-type-polynomial-inequalities-over-integers/37702#37702 Answer by fbou for On special type polynomial inequalities over integers fbou 2010-09-04T08:16:21Z 2010-09-04T08:16:21Z <p>By the way, does anybody have an intuition on the following refinement of the question: Is there an algorithm, that given one equation (and the same question for in-equation) with special polynomials, decides if this equation has integer solution?</p> <p>The argument given by David Speyer does not seem to solve the problem for this other question.</p>