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.

  • $\begingroup$ Whose lemma would that be? $\endgroup$ – Will Jagy Jun 26 '14 at 2:19
  • $\begingroup$ Please clarify: (1) does the polytope include its boundary? (2) is the polytope required to be full-dimensional in the space in which the integer points are being counted? (i.e. must it have nonempty interior in that space?) $\endgroup$ – Don Hatch May 17 '16 at 4:13

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

  1. The coefficient of linear constraints must be rational. Otherwise, your lemma will not be true (e.g. consider $\sqrt{2}x_1-\sqrt{3}x_2=0$).
  2. Since your polyhedron $P \subset \mathbb{R}^n$ is unbounded 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 infinitely many values of $\lambda$.
  • $\begingroup$ @ChristianRemling, Thanks for your comments, I edit my comments. $\endgroup$ – Mahdi Jun 26 '14 at 18:30
  • $\begingroup$ The Lemma also works fine with arbitrary constraints if $P$ has non-empty interior (see my answer). $\endgroup$ – Christian Remling Jun 26 '14 at 21:15
  • $\begingroup$ What's your counterexample with non-rational coefficients? $\endgroup$ – Don Hatch May 17 '16 at 4:16
  • $\begingroup$ @DonHatch: I added a counterexample with non-rational coefficients. $\endgroup$ – Mahdi May 4 '18 at 19:51

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.

  • $\begingroup$ 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. $\endgroup$ – heinz Jun 26 '14 at 7:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Christian Remling Jun 26 '14 at 17:27
  • $\begingroup$ 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. $\endgroup$ – Christian Remling Jun 26 '14 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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