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.

  • $\begingroup$ counting integer points in $mP+nQ$ is quite famous question, related to mixed volumes. Perhaps you can use it to get $|S|$... $\endgroup$ – Dima Pasechnik May 19 '15 at 12:31
  • $\begingroup$ do we know anything about P and Q?, because otherwise the question is a bit vague. $\endgroup$ – JMP May 24 '15 at 10:39
  • $\begingroup$ Suppose $P=conv((0,3,0),(5,0,0),(0,0,11),(4,2,7))$ and $Q=conv((0,9,0),(7,0,0),(0,0,4),(3,8,2)).$ Then what is the cardinality of S? $\endgroup$ – Cusp May 24 '15 at 11:18
  • $\begingroup$ small question - is there a reason in your definition of S you have used $(\mathbb{N}\cup\{0\})$ again when you have already defined it as $\mathbb{Z_+}$? $\endgroup$ – JMP May 26 '15 at 6:20
  • $\begingroup$ Those are same. $\endgroup$ – Cusp May 26 '15 at 14:28

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.


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:



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.

  • $\begingroup$ What do you mean by local minimums of P. I am new in this area (convex geometry). Can you please explain more elaborately. $\endgroup$ – Cusp May 27 '15 at 15:14
  • $\begingroup$ I think cardinality of the set (Z_+)^n\P+Q+(Q_+)^n is less than the cardinality of S. $\endgroup$ – Cusp May 28 '15 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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