Skip to main content
2 of 3
added 55 characters in body
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

This is known, but let me 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}). $$

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459