Does set remain bounded if these integer constraints are removed?

Question

Question:

Let $P$ be a nonempty polyhedron in $\mathbb{R}^n$, and let $l_i, u_i \in \mathbb{R}$ for all $i \in I$, where $I \subseteq \{1,\dots,n\}$.

I'm looking at a problem where the feasible region $$ F := P \cap \{x \in \mathbb{R}^n \mid l_i \leq x_i \leq u_i,\; x_i \in \mathbb{Z} \quad \forall i \in I\} $$ is nonempty and bounded.

Does it follow that $M := P \cap \{x \in \mathbb{R}^n \mid l_i \leq x_i \leq u_i\; \forall i \in I \}$ is also bounded?

---

Thoughts:

It seems like this should be the case. It works with the claim in my attempt below. But I haven't shown this claim to be true yet.

Attempt:

Set $M := P \cap \{x \in \mathbb R^n \mid l_i \leq x_i \leq u_i \; \forall i \in I\}$ and $Z := \{x \in \mathbb R^n \mid x_i \in \mathbb Z \; \forall i \in I\}$.

Want to show: If $M \cap Z$ is bounded, then $M$ is bounded.

Claim: If $F = M \cap Z$ is bounded, then $\textrm{dist}\big(\textrm{conv}(M \cap Z),\; M \setminus \textrm{conv}(M \cap Z) \big) \leq 1$ with respect to the $\|\cdot\|_\infty$ norm.

Proof: Haven't been able to show this yet.

Define $B := B_{\leq}(0,1)$ to be the closed unit ball with respect to the $\|\cdot\|_\infty$ norm. Hence $$ W := \textrm{conv}(M \cap Z) + B \supseteq M $$ Note that $\textrm{conv}(M \cap Z)$ is bounded, since convex hulls of bounded sets are bounded. Therefore $W$ is bounded as the sum of two bounded sets. The boundedness of $M$ follows from the boundedness of $W$.

Answer 1

If your polyhedron is closed (i.e. it is the intersection of closed half-spaces), then the following is a counterexample:

Let $n = 3$ and $I = \emptyset$. Let $\lambda \in \mathbb{R} \setminus \mathbb{Q}$ and consider the set $$P = \{(t + x, t, \lambda t + z) \mid t \in \mathbb{R}\text{, } x,z \in [0,1/4] \text{ and } |z| \leq x\}$$

If $(t + x, t, \lambda t + z)$ is a lattice point then one of the following must be the case:

1. If $t = 0$ then $x = z = 0$ and so $(0,0,0)$ is a lattice point, hence $F \neq \emptyset$.
2. If $t \neq 0$ and $x = 0$ then it must be the case that $t \in \mathbb{Z}$. But then $|z| \leq x$ implies that $z = 0$, and $\lambda \in \mathbb{R} \setminus \mathbb{Q}$, so $\lambda t \not\in \mathbb{Z}$.
3. If $t \neq 0$ and $x > 0$ then $t + x$ and $t$ differ by an amount between $0$ and $1$, hence they cannot both be integers.

Thus $(0,0,0)$ is the only lattice point in $P$. $\square$

On the other hand, if $P$ is assumed to be open, or $P$ is assumed to have a lattice point in its interior, the claim is true:

Claim: Let $U \subset \mathbb{R}^{n}$ be an open convex set. Suppose that $U \cap \mathbb{Z}^{n} \neq \emptyset$. The $U \cap \mathbb{Z}^{n}$ is finite if an only if $U$ is bounded.

Sketch: If $U \cap \mathbb{Z}^{n}$ is infinite then $U$ is trivially unbounded.

Now, suppose that $U$ is unbounded. First, consider the special case where $U$ is the $\epsilon$-neighbourhoon of the ray $\{t \underline{\lambda} \mid t \in \mathbb{R}_{\geq 0}\}$, where $\underline{\lambda} \in \mathbb{R}^{n} \setminus \{0\}$.

Cover $n$-torus $\mathbb{R}^{n}/\mathbb{Z}^{n} = \mathbb{T}_{n}$ in balls of radius $\epsilon/2$.

Consider the map $f: \mathbb{Z}_{\geq 0} \rightarrow \mathbb{T}_{n}$ given by $$f: k \mapsto k \underline{\lambda} + \mathbb{Z}^{n} \in \mathbb{T}_{n}\text{.}$$

By the pigeon hole principle, there exists an $\epsilon/2$-ball $B$ such that such that $K = \{k \mid k \underline{\lambda} \in C\}$ is infinite. Let $k_{0}$ be the lowest such $k$.

Then for all $k \in K$, $d( (k-k_{0})\underline{\lambda} + \mathbb{Z}^{n}, \mathbb{Z}^{n}) = d(k \underline{\lambda} + \mathbb{Z}^{n}, k_{0} \underline{\lambda} + \mathbb{Z}^{n}) \leq \epsilon$. Hence $K_{0} = \{ k \in \mathbb{Z}_{\geq 0} \mid d( k \underline{\lambda}, \mathbb{Z}^{n}) < \epsilon\}$ is infinite.

In particular, $K_{0}$ is unbounded, and so the set $$\{\underline{n} \in \mathbb{Z}^{n} \mid d(k \underline{\lambda}, \underline{n}) < \epsilon \text{ for some }k \in K_{0}\}$$ is infinite. This set is contained in the $\epsilon$-neighbourhood of the ray, proving this special case.

In the general case, let $x \in U$ be a lattice point and let $\epsilon > 0$ so that $B_{\epsilon}(x)$, the ball centred on $x$ of radius $\epsilon$, is contained in $U$. Let $x_{1}, x_{2},\ldots$ be and unbounded sequence in $U$. Let $y_{i}$ be the projection of $x_{i}$ onto the unit sphere centred at $x$.

Since the sphere is compact, the $y_{i}$'s have an accumulation point $y$. Let $R$ be the ray based at $x_{0}$ passing through $y$. Then $R$ is contained in the closure $\overline{U}$ of $U$, which is also convex.

Further, suppose $x' \in R$ and $y' \in B_{\epsilon}(x')$. Then there exist points $z \in B_{\epsilon}(x)$ and $z' \in R$ such that $y'$ lies on the line between $z$ and $z'$ and so $y' \in \overline{U}$ by convexity$.

Hence the $\epsilon$-neighbourhood of $R$ is contained in $\overline{U}$, hence $U$. By the special case, this neighbourhood contains an infinite number of lattice points and thus so does $U$. $\square$

If $I = \emptyset$ this directly solves the problem. If $I \neq \emptyset$ then there are two cases:

1. $M$ has an interior lattice point. then
2. $M$ has a lattice point on its boundary.

In the first case, we can apply the above claim to the interior of $M$.

In the second case, let $M_{\epsilon} = P \cap \{\underline{x} \in \mathbb{R}^{n} \mid l_{i} - \epsilon < x < u_{i} + \epsilon\}$. Then $M_{\epsilon}$ is open and convex for all $\epsilon >0$, and $M \subset M_{\epsilon}$. Thus $M_{\epsilon}$ contains one, hence infinitely many lattice points.

On the other hand, there exist integers $n^{l}_{i}$ and $n^{u}_{i}$ such that $n^{l}_{i} \geq l_{i} - \epsilon > n^{l}_{i} - 1$ and $n^{u}_{i} \leq u_{i} + \epsilon < n^{u}_{i} + 1$ for all $\epsilon > 0$ small enough. Thus, if $\epsilon$ is small enough, $\underline{x}$ is a lattice point in $M_{\epsilon}$ if and only if it is a lattice point in $M$. Since $M_{\epsilon}$ contains infinitely many lattice points, so does $M$.