# Conditions for Linear Diophantine Equations to always have a solution

Given a set of $n$ linear equations in $v$ integer variables, where $v > n$, we can say that this system of equations will always have an integer solution.

Over $\mathbb N$, is there any such constraint that guarantees that a solution always exists? Or, if not, can it be tested in polynomial time?

• In the first paragraph, are you using the Smith normal form? Jun 15 '17 at 19:07

Short answer: No. Most likely, no useful constraint exists; and it can't be tested in polynomial time.

Detailed answer, with justification: It cannot be tested in polynomial time, unless P = NP. In particular, if you could test for existence of a non-negative integer solution to such a system, you could solve integer linear programming (ILP). Here's how the reduction works:

Suppose we have an ILP instance with variables $x_1,\dots,x_k$. We'll modify it by introducing variables $x_1^+,\dots,x_k^+$ and $x_1^-,\dots,x_k^-$. Then we'll replace each inequality

$$c_0 + c_1 x_1 + \dots + c_k x_k \ge 0$$

with the equality

$$c_0 + c_1 x_1^+ - c_1 x_1^- + \dots + c_k x_k^+ - c_k x_k^- = y_j$$

and the inequality $y_j \ge 0$, where $y_j$ is a fresh new variable. Thus if the original ILP instance has $k$ variables and $m$ inequalities, the new instance will have $2k+m$ variables, $m$ equalities, and $2k+m$ inequalities $x_i^+ \ge 0$, $x_i^- \ge 0$, $y_j \ge 0$.

This now has the form of your problem, i.e., integer linear diophantine equations where we are looking for non-negative solutions, with $n=m$ linear equations and $v=2k+m$ variables. Note in particular that we are guaranteed to have $v>n$, since we must have $k>0$. Moreover, any solution to the original integer linear programming instance leads to a solution to this diophantine problem (take $x_i^+ = \max(0,x_i)$ and $x_i^- = \max(0,-x_i)$), and conversely, any solution to this diophantine problem leads to a solution to the original ILP instance (take $x_i = x_i^+-x_i^-$). Therefore the derived diophantine problem is equivalent to the original ILP instance.

This reduces ILP to testing existence of a solution to a diophantine problem. Since ILP is NP-hard, it follows that testing existence of solutions to this kind of diophantine problem is NP-hard, too. That means there is not likely to be any polynomial-time algorithm to it (assuming you believe it is unlikely that P = NP).

For similar reasons, you should not expect a useful condition that is necessary and sufficient to ensure that a solution always exists: any such condition must be infeasible to check in the worst case, unless P = NP. You can pick two out of any three: necessary; sufficient; efficiently checkable -- but you can't have all three, assuming P != NP (as many expect).

• Thank you for such a detailed answer. Assuming we are limiting the number of unique pure constants (i.e. one involving no variables eg. $c_0$ above in the eqn) in the system to a finite limit (say number of pure constants = 2 or perhaps =1 in any system) would this restricted problem still remain NP Complete? Jun 16 '17 at 6:19
• @J.Doe, I don't really understand what you are asking (you are saying the number of unique values of $c_0$, across all inequalities, is limited? Or that's true for all coefficients too?) -- but either way, I don't know the answer. I suspect it's still NP-hard, but it sounds like something to ask as a new question. You might start by asking a new question about whether ILP with a limited number of unique constants is NP-hard.
– D.W.
Jun 16 '17 at 7:10
• Thank you. I meant the number of unique values of $c_0$ across all inequalities is limited. I will ask it as a new Question as a follow up to this one. Jun 16 '17 at 7:32
• @D.W. What about the case when there is an additional constraint that in ILP $v - n < C$ where $C$ is a positive integer constant ? Jun 16 '17 at 8:20