Cardinality of non-integer points in the translation of the Minkowski sum of convex hull.

Question

Let $\operatorname{conv}(a_1,\ldots,a_m)$ denote the convex hull of $\{a_1,\ldots,a_m\}$. Let $\mathbb{Z}_+=\mathbb{N}\cup\{0\}$ and $\mathbb{Q}_+$ denotes the positive (inluding 0) rational numbers. Let $P = \operatorname{conv}(a_1,\ldots,a_p)$ and $Q = \operatorname{conv}(b_1,\ldots,b_q)$ be two convex sets in $\mathbb R^n$ such that $a_i,b_j\in\mathbb{Z}^n_+$. Given two positive integers $m$ and $n$, suppose the cardinality of $S=(\mathbb{N}\cup\{0\})^n\setminus(mP+nQ+\mathbb{Q}^n_+)$ is finite where $+$ denotes the Minkowski sum.

Q) Is there any method to find the cardinality of $S$?

Any reference of any kind will be helpful. Thanks in advance.

Answer 1

As Dima Pasechnik suggests, your questions is related to mixed volume. But in this case, for mixed volume of co-convex bodies. You may find details in A. Khovanskii, V. Timorin paper "On the theory of coconvex bodies", available on arxiv. Of course, they consider arbitrary number of bodies (not just two). They also study number of integer points and Ehrhart polynomial.

Answer 2

The key point here is the omission of $\mathbb{Q}^n_+$ from $S$. The two convex hulls $P$ and $Q$ provide a twist to the argument, and to begin just consider $S_p=\mathbb{Z}^n_+\setminus(mP+\mathbb{Q}^n_+)$.

$\mathbb{Q}^n_+$ can be $\{0,\dots,0\}$ and other variations, and so integer points of $P$ create infinite cubes from $P+\mathbb{Q}^n_+$. We can call the collection of infinite cubes the shadow of $P$. As $|S|$ is finite, $P$ must contain a point on each axis. We can also see that $mP$ in this case is contained in the shadow of $P$, and so we need only need to consider $\mathbb{Z}^n_+\setminus(P+Q+\mathbb{Q}^n_+)$

Adding $Q$ back into the definition of $S$ means we need to consider the minimal integer coordinates of $P$ and $Q$. Each integer point in $P$ and/or $Q$ gives rise to a shadow, and these points are eliminated from $S$. The number of integer points in the remaining non-shadowed space (a sort of jig-jagged 'cube') gives $|S|$.

If we work through your example:

$P=conv((5,0,0),(0,3,0),(0,0,11),(4,2,7))$

$Q=conv((7,0,0),(0,9,0),(0,0,4),(3,8,2))$

then the following lines bound $S$.

• $x=5$
• $y=3$
• $z=4$

In this case we then have $|S|\le4.2.3=24$

These come from the minimum value for each axis e.g. for the x-axis $(7,0,0)$ is in the shadow of $(5,0,0)$.

We then need to count integer points inside the convex hulls in the shadow of other given coordinates and that those inside or on the convex hull, and subtract these to get a final value for $|S|$, which needs explicit examples.