On the number of lattice convex chains

On the number of lattice convex chains, Discrete Analysis 2016:19, 15pp.

A lattice convex polygon is a convex polygon whose vertices have integer coordinates. This simple definition leads quickly to some very interesting questions that have been studied by several authors. For example, one can ask for an asymptotic formula for the number of lattice convex polygons with vertices in the set \(\{1,2,\dots,n\}^2\) when \(n\) is large. One can also ask what the typical shape of such a polygon is: in particular, is there a limiting shape that a random lattice convex polygon in an \(n\times n\) box approaches with high probability?

The answer to this last question was shown to be yes by Barany, Vershik, and Sinai (independently): a typical lattice convex polygon in an \(n\times n\) box is (approximately) made out of four parabolic arcs, each one tangent to two adjacent sides of the box at their midpoints.

Given the form of this answer, it is not surprising that what really matters for this analysis is the shape of a piecewise linear convex function \(f:[0,n]\to [0,n]\) such that \(f(0)=0\), \(f(n)=n\), and the only points at which the gradient changes have integer coordinates. Equivalently, one is interested in sequences \((x_0,y_0), (x_1,y_1),\dots,(x_n,y_n)\) of points in \(\{0,1,\dots,n\}^2\) with \((x_0,y_0)=(0,0)\), \((x_n,y_n)=(n,n)\), and \((y_i-y_{i-1})/(x_i-x_{i-1})\) strictly increasing with \(i\). These are called lattice convex chains. Barany, Vershik and Sinai proved that the number of lattice convex chains is \(\exp(3\kappa^{1/3}n^{2/3}(1+o(1)))\), where \(\kappa=\zeta(3)/\zeta(2)\). Here \(\zeta\) is the Riemann zeta function.

This paper obtains a much more precise version of the above formula, which is too complicated to give here, which gives the correct result up to a factor \(1+o(1)\). (This is of course much stronger than having the \(1+o(1)\) inside the exponential.) The authors achieve this by using a statistical-mechanical model developed by Sinai and analysing its partition function with the help of an integral representation that they have discovered.

However, their formula involves a sum over zeros of the zeta function, and it is not easy to estimate its magnitude. Assuming the Riemann hypothesis, the rough order of this term can be given. The authors also show the converse: that is, a suitable estimate for the magnitude of this term would imply the Riemann hypothesis.