Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  drvitek Sep 3 '10 at 23:10

3 Answers 3

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.

share|improve this answer
    
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. –  Qiaochu Yuan Sep 3 '10 at 23:14
    
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? –  Mark Sapir Sep 3 '10 at 23:40
    
Just what David said: $-1 < f < 1$. –  drvitek Sep 3 '10 at 23:57
    
$-1<f<1$ means $f=0$. I am asking about $f\ne 0$. –  Mark Sapir Sep 4 '10 at 2:42
    
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. –  Gerry Myerson Sep 4 '10 at 6:39

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.

share|improve this answer

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.

share|improve this answer
1  
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. –  Mark Sapir Sep 4 '10 at 9:23

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.