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

is there a simple proof for the following lemma:

An unbounded convex polytope (defined by linear constraints) has either zero integer points or infinite many integer points.

share|improve this question
    
Whose lemma would that be? –  Will Jagy Jun 26 at 2:19

2 Answers 2

Edit: the following argument is true when the polytope $P$ is the intersection of finite many linear constraints: $a_1 x_1 + \ldots + a_n x_n \leq b$.

  1. The cofficient of linear constraints must be rational. Otherwise, your lemma will not be true.
  2. Since your polytope $P \subset \mathbb{R}^n$ is unbouded and defined by rational linear constraints, it has a rational recession direction, i.e. there exists $ 0 \neq d \in \mathbb{Q}^n$ such that $x+\lambda d \in P $, for all $x \in P$ and $ \lambda \geq 0 $. Therefore, if $x_0\in P \cap \mathbb{Z}^n $ then $x_0 +\lambda d \in P \cap \mathbb{Z}^n $ for infinite many values of $\lambda$.
share|improve this answer
    
@ChristianRemling, Thanks for your comments, I edit my comments. –  Mahdi Jun 26 at 18:30
    
The Lemma also works fine with arbitrary constraints if $P$ has non-empty interior (see my answer). –  Christian Remling Jun 26 at 21:15

Edit: Let me emphasize that I make the (obviously necessary) extra assumption that $P$ has non-empty interior. I am not assuming, however, that the bounding hyperplanes have rational normal directions.

This will (essentially) follow from this sublemma:

If $x$ is in the interior of $P$, then $P$ contains a $\delta$ neighborhood of a ray $x+te$, $t\ge 0$, for some direction $e\in S$.

To see this, consider $x+te$ for fixed $e$ and observe that if this intersects a bounding hyperplane $H$ for some $t_0>0$, then suitable points $x+t(e')e'$ will also be on $H$, with $t(e')\approx t_0$, for all $e'\approx e$ (that could only fail if $n_H\cdot e=0$ for the normal direction of $H$, but then we would have $x\in H$ already). So if every ray $x+te$, $e\in S$ intersected the boundary, then $P$ would be bounded after all by compactness of the unit sphere. Since there are only finitely many bounding hyperplanes, there is a fixed positive distance to all of them from my ray.

If we now have an $x\in \mathbb Z^n$ in the interior of $P$, then this tube $y+te$, $t\ge 0$, $|y-x|<\delta$ will contain infinitely many other integer points because $x+te$ at least gets arbitrarily close to $\mathbb Z^n$ (the details depend on the rational relations among the $e_j$).

If $x$ was on the boundary, a modified version of this still works.

share|improve this answer
    
i don't understand some of your arguments what i came up with say the polytope is over Q^n (this reduces the proof). Say x is a feasible integer point. Then your ray for each e intersects either a bounding hyperplane or is for all t inside the polytope. Since the problem is convex and the polytope is unbounded there exists a e from Q so that the ray is inside. If it is inside for all t you can choose t as the common denominator of all entries in e and the point is integer again. This you can do again till infinity. The only tricky point is to show that the e is from Q. –  heinz Jun 26 at 7:52
    
You will not be able to show that $e\in\mathbb Q^n$ because $e$ could easily be unique. But fortunately, I don't need anything on the components $e_j$. Either $e_j n \mod 1$ is periodic ($\iff e_j\in\mathbb Q$), or $e_j kn\mod 1$, $n\ge 0$ is dense in the torus, for all $k\ge 1$ ($\iff e_j\notin\mathbb Q$). Generically, the components will in fact be rationally independent, so I will not hit another integer point. That's why I need the tube instead of the ray. –  Christian Remling Jun 26 at 17:27
    
In general, you can have some rational relations $\sum q_j^{(k)} e_j =$, but no matter what the details of the situation are, $te$ always comes at least arbitrarily close to $\mathbb Z^n$ arbitrarily often. –  Christian Remling Jun 26 at 17:38

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.