8
$\begingroup$

Suppose that a linear system of inequalities $Ax \le b$, where $A\in Z^{m\times n}$ and $b\in Z^m$ have integral coefficients, has an infinite number of integral solutions $x$.

Can one conclude that there is a ray $\{x+tp\mid t\ge 0\}$ containing infinitely many integral solutions? (If one drops the integrality condition, the answer is clearly yes.)

$\endgroup$
2
  • $\begingroup$ I assume you have only finitely many inequalities. And a ray doesn't have to go through the origin? Consider $1 \le 2x_1 \le 3$. $\endgroup$ Nov 26, 2015 at 23:28
  • $\begingroup$ Presumably a ray here does not have to go through the origin... $\endgroup$ Nov 26, 2015 at 23:53

1 Answer 1

2
$\begingroup$

Let the constraints be numbered 1 to $m$. Let the $i$th constraint be $a^{(i)}\cdot x\le b$. Let $S$ be the set of solutions. Inductively refine the constraints as follows: either there are $\limsup_{x\in S, x\to\infty} a^{(1)}\cdot x=-\infty$ or not. If $\limsup_{x\in S,x\to\infty} a^{(1)}\cdot x=c^{(1)}>-\infty$, then replace the system with the stronger constraint, $a^{(1)}\cdot x=c^{(1)}$. It still has infinitely many integer solutions.

Now consider the second constraint. If the $\limsup$ is finite, replace it by an equality etc.

In the end, you have a set of equalities, and a set of inequalities. For the inequalities, the inner products tend to $-\infty$ as the solution goes to $\infty$. In particular, you can find two solutions where for each equality, then inner product is the same, but for each inequality, the inner product of the first is larger than the inner product of the second.

Call these $x$ and $y$. Now $x+n(y-x)$ is an infinite family of integer solutions satisfying all of the (stronger) constraints.

$\endgroup$
2
  • $\begingroup$ why is the first limsup still $-\infty$ when only the second limsup is finite and the inequality is replaced by an equation? $\endgroup$ Nov 27, 2015 at 17:50
  • $\begingroup$ If the first $\limsup$ is $-\infty$, then along any infinite collection of solutions, the limit is $-\infty$ - in particular if you replace the second inequality by an equality. $\endgroup$ Nov 27, 2015 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.