On special type polynomial inequalities over integers - MathOverflow

On special type polynomial inequalities over integers

2010-09-03T23:04:04Z

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?

Answer by David Speyer for On special type polynomial inequalities over integers

2010-09-03T23:10:28Z

ADDED: As Mark Sapir and other are pointing out, if you only have $\neq$'s, no $=$'s, $<$ 's or $>$ '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 $<$ 's and $>$ 's:

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.

So special equations are no simpler than ordinary equations and, as I imagine you know, there is no algorithm to solve Diophantine equations.

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 < f(x,y,z) < 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.

Answer by Mark Sapir for On special type polynomial inequalities over integers

2010-09-04T03:54:20Z

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.

Answer by fbou for On special type polynomial inequalities over integers

2010-09-04T08:16:21Z

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?

The argument given by David Speyer does not seem to solve the problem for this other question.