# convex polytope integer points

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.

-
Whose lemma would that be? –  Will Jagy Jun 26 '14 at 2:19

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$.
-
The Lemma also works fine with arbitrary constraints if $P$ has non-empty interior (see my answer). –  Christian Remling Jun 26 '14 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.

-
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 '14 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 '14 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 '14 at 17:38