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?
1
-
$\begingroup$ This is a subcase of Hilbert's tenth problem, so I'm inclined to say "probably not" and would be very surprised if this were true. $\endgroup$– dvitekSep 3, 2010 at 23:10
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
8
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.
answered Sep 3, 2010 at 23:10
-
$\begingroup$ To complete the proof, it is at least as hard to solve Diophantine inequalities as Diophantine equations. This is because the Diophantine equation f(x_1, ...) = 0 is equivalent to the Diophantine inequality f(x_1, ...)^2 \le 0. $\endgroup$ Sep 3, 2010 at 23:14
-
$\begingroup$ I think that Bakh wanted in-equations, i.e. formulas like $u\ne 0$. Right? So given a polynomial equation $f=0$, what is the system of in-equations that it is equivalent to? $\endgroup$– user6976Sep 3, 2010 at 23:40
-
-
$\begingroup$ $-1<f<1$ means $f=0$. I am asking about $f\ne 0$. $\endgroup$– user6976Sep 4, 2010 at 2:42
-
$\begingroup$ Mark, $f\ne0$ is the same as $f^2>0$. Although maybe doing $f^2$ means we don't have "special" in-equations any more. $\endgroup$ Sep 4, 2010 at 6:39
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ As I said, in-equations ($u≠0$) always have integer solutions, provided u is not 0. I am sure that if u is "special", then the algorithm to solve the equation $u=0$ exists: induction on the number of variables, it should reduce the problem to linear Diophantine equations. $\endgroup$– user6976Sep 4, 2010 at 9:23