Integer points in polyhedra

104 Views Asked by At

I kindly ask your expertise on the following point:

Let $P$ be an unbounded polyhedron of $R^d$ defined by linear inequalities as

$$P = \{x\in R^d : \ell_1 (x)< \alpha_1,\ \ \ell_2 (x)\leq \alpha_2, \ \ \ldots, \ell_t (x)\leq \alpha_t, \}$$

where only the first inequality is strict and the others are weaker.

My question is: Does there exists some $\varepsilon >0$ such that the closed polyhedron $P_\varepsilon$

$$P_\varepsilon = \{x\in R^d : \ell_1 (x)\leq \alpha_1 - \varepsilon,\ \ \ell_2 (x)\leq \alpha_2, \ \ \ldots, \ell_t (x)\leq \alpha_t, \}$$

contains the same integer points of $P$, i.e.

$$P_\varepsilon \cap Z^d = P \cap Z^d$$

For $d=1$ and for polytopes, this is true.

Thank you in advance for your help.

1

There are 1 best solutions below

8
On

For a bounded polyhedron, the answer would be "yes"; for an unbounded one, not necessarily so.

Indeed, for any $\varepsilon>0$ there are integer points $(n,m)$ that satisfy $n-\sqrt2m>0$, but not $n-\sqrt2m\geqslant\varepsilon$. Ditto for any other irrational slope.

To make the answer always "yes", you need a stricter condition, like rational coefficients in $\ell_1 (x)$ or the boundedness of the polyhedron's face corresponding to it.

So it goes.