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.
2
-
$\begingroup$ Whose lemma would that be? $\endgroup$– Will JagyJun 26, 2014 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 HatchMay 17, 2016 at 4:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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$.
- 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$).
- 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$– MahdiJun 26, 2014 at 18:30
-
$\begingroup$ The Lemma also works fine with arbitrary constraints if $P$ has non-empty interior (see my answer). $\endgroup$ Jun 26, 2014 at 21:15
-
$\begingroup$ What's your counterexample with non-rational coefficients? $\endgroup$ May 17, 2016 at 4:16
-
$\begingroup$ @DonHatch: I added a counterexample with non-rational coefficients. $\endgroup$– MahdiMay 4, 2018 at 19:51
$\begingroup$
$\endgroup$
3
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.
answered Jun 26, 2014 at 2:53
-
$\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$– heinzJun 26, 2014 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$ Jun 26, 2014 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$ Jun 26, 2014 at 17:38