Let $\mathcal{P}$ be a convex polytope in $\mathbb{R}^n$ given in the form $\mathcal{P} = \{ x \in \mathbb{R}^n\colon A x\leq b \}$. Suppose that the entries of $A$ and $b$ are integers. Then it is well-known that $\mathcal{P}$ is a rational polytope, i.e., its vertices have rational (but not necessarily integral) coordinates. We might be interested in how far $\mathcal{P}$ is from being a lattice polytope. So let $\kappa$ be the biggest denominator appearing in any coordinate of a vertex of $\mathcal{P}$.

Finally, suppose further that the entries of $A$ and $b$ are bounded in absolute value by some $m$. Since there are only finitely many possible $A$ and $b$ in this case, we must be able to bound $\kappa$ in terms of $n$ and $m$. But I have no clue how $\kappa$ behaves. Which leads to my question.

Question: In this situation, what is an upper bound for $\kappa$ in terms of $n$ and $m$?


1 Answer 1


Let $x$ be a vertex of $\mathcal{P}$. By Cramer's rule, there is an $n \times n$ matrix $C$ such that each coordinate of $x$ is an integer multiple of $\frac{1}{|\det(C)|}$, and the absolute value of each entry of $C$ is bounded by $m$. Therefore, by Hadamard's inequality, $$\kappa \leq m^n n^{n/2}.$$

The proof actually shows that $\kappa$ does not depend on $b$. Of course, the largest numerators appearing in $x$ will depend on $b$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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