3
$\begingroup$

Let $E_n = \{ (i,j) : 0 \leq i,j \leq n-1 \}$. We say that a polytope $P$ is an integer polytope in $E_n$ if all vertices of $P$ belongs to $E_n$.

My question is how many different integer polytopes there are in $E_n$?

In other words, how many different subsets $S \subset E_n$ have property that every element of $S$ is a vertex of the convex hull of S?

$\endgroup$
6
  • 1
    $\begingroup$ Hm. I am strongly against closing this question. $\endgroup$ Commented Jan 7, 2016 at 13:32
  • $\begingroup$ @Fedor, thanks for the answer. I need some time to understand your arguments, and I'm against closing the question at this point, as well. $\endgroup$
    – Victor
    Commented Jan 7, 2016 at 15:19
  • $\begingroup$ The word "polytope" is for something more than 2-dimensional, is not it? By the way, asymptotical result is similar to that in dimension 2, done by Bárány – Vershik, renyi.hu/~barany/cikkek/52.pdf but it is not proved that limit constant exists $\endgroup$ Commented Jan 7, 2016 at 15:57
  • $\begingroup$ Sure, in general, we may consider higher dimensions, but first I would like clearly understand basic case. $\endgroup$
    – Victor
    Commented Jan 7, 2016 at 16:40
  • $\begingroup$ @FedorPetrov thanks for the reference to the paper by Bárány and Vershik you mentioned. If I understood well, their result doesn't directly imply something about the question. This is because not every polytope of 'proper' volume can be packed into $E_n$. For example if your try to apply their results to count the number of polytopes of volume $2n$, then some of these polytopes may be placed in $E_n$, but some may not (consider for example rectangle with sides 1 and $2n$). $\endgroup$
    – Victor
    Commented Jan 7, 2016 at 16:49

2 Answers 2

3
$\begingroup$

This is known, let me briefly explain in some details how to deal with such problems.

Convex polygon is uniquely (up to translation) determined by vectors of edges, which are vectors from $\mathbb{Z}^2$, not two have the same direction, and sum up to 0. Each integer vector $x\ne 0$ has unique representation $x=ny$ for positive integer $n$ and primitive vector $y$ ('primitive' means 'with coprime coordinates'.) That is, a convex polygon corresponds to a partition of zero vector onto primitive vectors. After this point we reduce counting convex integer polygons to the theory of partitions, where machinery of generating functions applies. As far as I know, this approach was suggested by Vershik in early 1990's.

Let us start from a slightly different question than counting convex polygons inside a square box. Let's count convex chains from the point $O=(0,0)$ to $A=(n,m)$, which lie, say, below line $OA$. As we have already observed, this is the number of partitions of the vector $(n,m)$ onto primitive non-negative vectors, i.e., $$ p(n,m):=[t^ns^m] \prod (1+t^as^b+t^{2a}s^{2b}+\dots)=[t^ns^m] \prod \frac1{1-t^as^b}, $$ where the product is taken over all primitive non-negative vectors $(a,b)$. Denote $t=e^{-\tau}$, $s=e^{-\xi}$ for some positive $\tau,\xi$ and use obvious inequality $[t^ns^m] F(t,s)\leqslant t^{-n}s^{-m} F(t,s)$ for any series $F(t,s)$ with non-negative coefficients. We get $$ \log p(n,m)\leqslant n\tau+m\xi+\sum -\log(1-e^{-a\tau-b\xi}). $$ What we know about primitive vectors is that they are uniformly distributed with density $1/\zeta(2)$. In other words, the probability that two positive integers are coprime is $1/\zeta(2)$ (quick 'proof': denote this probability by $p$, then by scaling argument probability that greatest common divisor of two positive integers equals $N$ is $p/N^2$, sum up by all $N=1,2,\dots$ to get $1=\sum_{N} p/N^2=p\cdot \zeta(2)$). It means that $\sum f(\varepsilon_1 a,\varepsilon_2 b)$ behaves as $\zeta(2)^{-1}\varepsilon_1^{-1} \varepsilon_2^{-1} \int_0^\infty\int_0^\infty f$ for small $\varepsilon_1,\varepsilon_2$ and any reasonable function $f$. We think about $\tau,\xi$ close to 0, this corresponds to large and not too much different $n,m$. To be more precise, we need $n+m=o(\min(n,m)^2)$. I do not justify here why this is enough.

This is all said to explain why we may change $\sum -\log(1-e^{-a\tau-b\xi})$ to $$ \frac1{\zeta(2)\tau\xi}\int_0^\infty \int_0^\infty -\log(1-e^{-x-y})dxdy= \frac{\zeta(3)}{\zeta(2)\tau\xi}, $$ the integral is calculated by expanding $-\log(1-e^{-x-y})=\sum_k \frac1k e^{-kx-ky}$. After all, we get approximate estimate $$ \log p(n,m)\leqslant n\tau+m\xi+\frac{\zeta(3)+o(1)}{\zeta(2)\tau\xi}, $$ and we may choose $\tau$ and $\xi$ as we want. Optimizing this sum is not a big deal: product of three summands is fixed, hence minimal value of the sum is attained when they are all equal to their geometric mean. So, $$ \log p(n,m)\leqslant 3\sqrt[3]{\frac{\zeta(3)}{\zeta(2)}nm}+o(\sqrt[3]{nm}). $$ It appears to be sharp enough, as such estimates usually do. As for the initial problem, it reduces to four convex chains (between the leftmost, rightmost, lowest and highest points of a polygon.) It is easy to believe and not hard to prove that the maximal number of polygons is obtained when they are in the midpoints of the sides of the square, in other words, the logarithm of the number of polygons in $[0,n]^2$ is close to $$4\log p(n/2,n/2)=6\sqrt[3]{\frac{2\zeta(3)}{\zeta(2)}}\cdot n^{2/3}+o(n^{2/3}). $$

$\endgroup$
1
$\begingroup$

You can obtain upper and lower bounds on the numbers of convex polytopes whose vertices are lattice points in a square from estimates on the maximum number of vertices. See Žunić, "Limit shape of convex lattice polygons having the minimal L∞ diameter w.r.t. the number of their vertices." Discrete Mathematics Volume 187, Issues 1–3, 6 June 1998, Pages 245–254.

You can construct a convex polygon with $c n^{2/3}$ vertices. (Sort primitive vectors inside the region $|x|+|y| \le c n^{1/3}$.) Any subset of at least $3$ vertices gives a distinct integer polytope, so there are at least $(1-o(1))2^{cn^{2/3}}$ different integer polytopes.

To get an upper bound, there are at most $\sum_{k=3}^{c n^{2/3}} {n^2 \choose k} = (1+o(1)) {n^2 \choose cn^{2/3} } = (1+o(1)) 2^{c'n^{2/3} \log n}$ sets of vertices of lattice polytopes.

From one perspective, these bounds are far apart. They differ by far more than a constant. Their logs differ by more than a constant. However, if $f(n)$ is the count, $\log\log f(n) \sim \frac{2}{3} \log n$.

$\endgroup$
4
  • $\begingroup$ Probably it doesn't effect the main terms, but strictly speaking the question wants the chosen points to be vertices, not just on the convex hull. Eg, three points are only ok if they aren't collinear. $\endgroup$ Commented Jan 7, 2016 at 8:47
  • $\begingroup$ OK, I was misreading. Sorry. $\endgroup$ Commented Jan 7, 2016 at 9:40
  • $\begingroup$ @Douglas Zare, thanks for the answer. Does asymptotic of $\log f(n)$ seems to you an open question? $\endgroup$
    – Victor
    Commented Jan 7, 2016 at 10:42
  • 2
    $\begingroup$ @Victor: It's something that I don't know, but I have higher standards than that for calling something an open problem. I would want to do a literature search first to verify that other people have considered the problem and have not found the answer before calling it an open problem. $\endgroup$ Commented Jan 7, 2016 at 10:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .