Imre Bárány: Limit shape

Combinatorics and more 2019-08-20

Limit shapes are fascinating objects in the interface between probability and geometry and between the discrete and the continuous. This post is kindly contributed by Imre Bárány.

What is a limit shape?

There are finitely many convex lattice polygons contained in the ${[0,n]^2}$ square. Their number turns out to be

$\displaystyle \exp\{3\sqrt[3]{\zeta(3)/\zeta(2)}n^{2/3}(1+o(1))\}. \ \ \ \ \ (1)$

This is a large number. How does a typical element of this large set look? Is there a limit shape of these convex lattice polygons?

To answer this question it is convenient to consider the lattice ${{\mathbb{Z}}_n=\frac 1n {\mathbb{Z}}^2}$ and define ${\mathcal{F}^n}$ as the family of all convex ${{\mathbb{Z}}_n}$ -lattice polygons lying in the unit square ${Q}$ . The polygons in ${\mathcal{F}^n}$ have a limit shape (as ${n\rightarrow \infty}$ ) if there is a convex set ${K\subset Q}$ such that the overwhelming majority of the polygons in ${\mathcal{F}^n}$ are very close to ${K}$ . In other words, for every ${\epsilon>0}$ the number of polygons in ${\mathcal{F}^n}$ that are farther than ${\epsilon}$ from ${K}$ (in Hausdorff distance, say) is a minute part of ${\mathcal{F}^n}$ , that is, ${o(|\mathcal{F}^n|)}$ as ${n \rightarrow \infty}$ . To put it differently, the average of the characteristic functions ${\chi_P(.)}$ of ${P\in \mathcal{F}^n}$ tends to a zero-one function:

$\lim {\rm Ave}_{P\in \mathcal{F}^n}\chi_P(x)=\begin{cases} 1& \mbox{ if } x \in K,\\ 0& \mbox{ if } x \notin K. \end{cases}$

The limit shape theorem

The limit shape theorem says that such a $K$ exists, its boundary consists of four parabola arcs each touching consecutive sides of $Q$ at their midpoints, see the figure.

Generating functions and saddle point methods

The proof is based on the fact that a convex (lattice or non-lattice) polygon with vertices $v_1,\ldots,v_n$ (in this order on its boundary) is uniquely determined by the edge-vectors $v_2-v_1,\ldots,v_n-v_{n-1}, v_1-v_n$ . Using this one can write down the generating function of the number of convex lattice paths from $(0,0)$ to $(a,b)\in \mathbb{Z}^2$ lying in the triangle whose vertices are $(0,0),(a,0)$ and $(a,b)$ . And this number can be estimated by saddle point methods (from complex variables). This is also how formula (1) for $|\mathcal{F}^n|$ can be established.

A beautiful geometric result

On the geometry part one needs a beautiful (and almost elementary) result saying that, in a triangle $T$ with vertices $1,2,3$ and with subtriangles $T_1$ and $T_2$ (see the figure)

$\displaystyle \sqrt[3]{\textrm{Area} \; T}\ge \sqrt[3]{\textrm{Area} \; T_1}+\sqrt[3]{\textrm{Area} \; T_2}, \ \ \ \ \ (2)$

with equality iff the line segment 46 is touches the special parabola arc at point 5. The special parabola arc is the one that touches sides 12 and 13 of ${T}$ at points 2 and 3. I was very proud of inequality (2) but it turned out that it had been known for long (cf Blaschke: Vorlesungen Über Differentialgeometrie II, (1923) page 38).

In the proof one needs a slightly stronger version of (2). Assuming point 4 (resp. 6) divides segment 12 (and 13) in ratio ${1-a:a}$ , (and ${b:1-b}$ ), the stronger inequality says that

$\displaystyle \sqrt[3]{\textrm{Area} \; T}\left(1-\frac13 (a-b)^2\right)\ge \sqrt[3]{\textrm{Area} \; T_1}+\sqrt[3]{\textrm{Area} \; T_2},$

which was probably not known to Blaschke.

It is important to point out that ${K}$ is the unique convex subset of ${Q}$ whose affine perimeter is the largest among all convex subsets of ${Q}$ . I’ll return to the affine perimeter later.

Yakov Sinai came up with a different, elegant, and more powerful proof using canonical ensembles from statistical physics. His method was developed further by Vershik and Zeitouni, by Bureaux and Enriquez, by Bogachev and Zarbaliev.

Limit shapes for polygons in convex bodies

More generally, one can consider a convex body (compact convex set with non-empty interior) ${C}$ in the plane and the family ${\mathcal{F}^n(C)}$ of all convex ${{\mathbb{Z}}_n}$ -lattice polygons contained in ${C}$ , and ask whether a similar limit shape exists in this case. The answer is yes. The limit shape, ${C_0}$ , is the unique convex subset of ${C}$ whose affine perimeter is maximal among all convex subsets of ${C}$ . The affine perimeter is upper semicontinuous, implying the existence of convex subset of ${C}$ with maximal affine perimeter. The proof of its uniqueness requires extra effort. In the case when ${C}$ is the unit square ${Q}$ , the limit shape ${K}$ is equal to ${Q_0}$ . Note that for every convex body ${C}$ with ${Q_0\subset C \subset Q}$ , ${C_0=Q_0}$ .

Random points vs. lattice points

What happens if, instead of the ${{\mathbb{Z}}_n}$ -lattice points in ${C}$ , we take a random sample ${X_n=\{x_1,\ldots,x_n\}}$ of points from ${C}$ , chosen independently and uniformly? Let ${\mathcal{G}(X_n)}$ be the set of all polygons whose vertices belong to ${X_n}$ . This is again a finite set and one can show that $\displaystyle \lim_{n\rightarrow \infty} n^{-1/3}\log \mathop{\mathbb E}( |\mathcal{G}(X_n)|)=3\cdot2^{-2/3}\frac{A^*(C)}{\sqrt[3]{\textrm{Area} \; C}},$

where ${A^*(C)}$ is equal to the affine perimeter, ${AP(C_0)}$ , of ${C_0}$ . This confirms the philosophy (or my intuition) that random points and lattice points in convex bodies behave similarly. Note that ${\mathop{\mathbb E}|\mathcal{G}(X_n)|}$ is of order ${\exp\{c_1n^{1/3}\}}$ while ${|\mathcal{F}^n(C)|}$ is of order ${\exp\{c_2n^{2/3}\}}$ which is fine as number of ${{\mathbb{Z}}_n}$ -lattice points in ${C}$ is approximately ${n^2 \textrm{Area} \; C}$ .

Even more interestingly, the limit shape of the polygons in ${\mathcal{G}(X_n)}$ is ${C_0}$ , in the sense that, in expectation, the overwhelming majority of polygons in ${\mathcal{G}(X_n)}$ is very close to ${C_0}$ . More precisely, for every ${\epsilon>0}$ $\displaystyle \lim_{n \rightarrow \infty} \frac{\mathop{\mathbb E}|\{P\in \mathcal{G}(X_n):\delta(P,C_0)>\epsilon\}|}{\mathop{\mathbb E}(|\mathcal{G}(X_n)|)}=0,$

where ${\delta}$ stands for the Hausdorf distance.

The proof of the lattice case does not work here. The edge vectors determine the convex polygon, still, but the edge vectors can’t be used, there is no generating function, etc. Instead the proof is based on the following two theorems. For the first let ${\Delta}$ be a triangle with two specified vertices ${a}$ and ${b}$ say, and let ${X_k}$ be a random independent sample of ${k}$ uniform points from ${\Delta}$ . Then ${X_k}$ is called a convex chain (from ${a}$ to ${b}$ ) if the convex hull of ${\{a,b\}\bigcup X_k}$ is a convex polygon with exactly ${k+2}$ vertices. Then $\displaystyle \Pr[X_k \mbox{ is a convex chain}]=\frac {2^k}{k!(k+1)!},$

a surprisingly precise result (due to Pavel Valtr).

For the second theorem let ${p(n,C)}$ denote the probability that the random sample ${X_n}$ (independent and uniform again) lands in convex position, that is, their convex hull is a convex ${n}$ -gon. For ${n=4}$ this is Sylvester’s famous four point problem from 1864 (although he did not specify the underlying convex body ${C}$ ). Then $\displaystyle \lim_{n\rightarrow \infty} n^2\sqrt[n]{p(n,C)}=\frac {e^2}4\frac{A^*(C)}{\sqrt[3]{\textrm{Area} \; C}},$

with the same ${A^*(C)}$ as before. The proof of this theorem uses the previous result of Valtr about convex chains in triangles and the properties of ${C_0}$ , the largest affine area convex subset of ${C}$ . The set ${C_0}$ appears again: it is the limit shape of ${\textrm{conv}X_n}$ under the condition that ${X_n}$ landed in convex position.

The map ${C \rightarrow C_0}$ is affinely equivariant and has interesting properties. ${C_0}$ turns out to be the limit shape in some further cases as well. For instance, the maximal number of vertices of the polygons in ${\mathcal{F}^n(C)}$ equals

$\displaystyle \frac {3n^{2/3}}{(2\pi)^{2/3}}A^*(C)(1+o(1)),$

as ${n \rightarrow \infty}$ . This is of course the same as the maximal number of points in ${{\mathbb{Z}}_n\cap C}$ that are in convex position. Although the convex ${{\mathbb{Z}}_n}$ -lattice polygon ${\mathcal{F}^n(C)}$ with maximal number of vertices is not necessary unique, they have a limit shape which is again ${C_0}$ . The same happens in ${\mathcal{G}_n(C)}$ as well. In this case, however, the expectation of the maximal number of vertices is equal to constant times ${A^*(C)n^{1/3}}$ but the value of this (positive) constant is not known. The reason is the following. In the triangle ${\Delta}$ with specified vertices ${a}$ and ${b}$ , and random sample ${X_k}$ we define ${L_k}$ as the maximal number of points from ${X_k}$ that form a convex chain in ${\Delta}$ from ${a}$ to ${b}$ . The random variable ${L_k}$ is concentrated around its expectation, which is equal to some non-negative constant times ${k^{1/3}(1+o(1))}$ as ${k \rightarrow \infty}$ but this constant is not known. Experiments suggest that it is equal to 3 but there is no proof in sight. Not surprisingly, the limit shape of these maximal convex chains is again the special parabola arc in ${\Delta}$ . This question about the random variable ${L_k}$ is similar to the longest increasing subsequence problem but much less is known about it.

Open Problem: high dimensions

What remains of the limit shape phenomenon in higher dimensions? Well, hardly anything has been proved. In the simplest case, let ${Q}$ denote the unit cube in 3-space, and let ${\mathcal{F}^n(Q)}$ denote the set of all convex ${\frac 1n {\mathbb{Z}}^3}$ -lattice polygons contained in ${Q}$ . It is known that ${\log |\mathcal{F}^n(Q)|}$ is between ${c_1n^{1/2}}$ and ${c_2 n^{1/2}}$ with ${0<c_1<c_2}$ , but nothing more precise. Probably there is a limit shape here as well, and it might be the convex subset of ${Q}$ that has the largest affine surface area. The existence of such a set follows the same way as above but its uniqueness is not known.

The affine perimeter

Finally a few words about the affine perimeter. Given a convex curve ${\Gamma}$ in the plane, choose points ${x_0,\ldots, x_n}$ on it, take the tangent lines at these points and form the triangles ${T_1,\ldots,T_n}$ as in the figure. By definition, the affine perimeter ${AP(\Gamma)}$ is the infimum of the sum ${2\sum_1^n(\textrm{Area} \; T_i)^{1/3}}$ as the subdivision ${x_0,\ldots,x_n}$ gets finer and finer. The affine perimeter of the unit circle is ${2\pi}$ which explains the constant ${2}$ in front of ${\sum_1^n(\textrm{Area} \; T_i)^{1/3}}$ . The exponent ${1/3}$ is the right choice here: for larger exponent the sum is zero, and for smaller it is infinity (for the circle for instance). Inequality (2) shows that infimum in the definition can be replaced by limit. The affine perimeter of a convex polygon is zero.

For a twice differentiable curve ${AP(\Gamma) = \int_{\Gamma}\kappa^{1/3}ds=\int_{\Gamma}r^{-1/3}ds}$ where ${\kappa}$ is the curvature and ${r}$ the radius of curvature and ${ds}$ means integration with arc length. The affine perimeter is an affine invariant or rather equivariant meaning that ${AP(S(\Gamma))=\sqrt[3]{|\det S|} AP(\Gamma)}$ for a non-degenerate affine transformation ${S}$ . Quite often the affine perimeter (and the affine surface area) appears in connection with affine equivariant properties of the convex set ${C}$ . One example is best approximation by inscribed polygons ${P_n}$ on ${n}$ vertices. When approximation is measured by ${\textrm{Area}\;(C\backslash P_n)}$ then the best approximating polygon ${P_n}$ satisfies the estimate $\displaystyle \textrm{Area} \; (C\backslash P_n)= \frac 1{4\sqrt 3} \frac {AP(C)^3}{n^2}(1+o(1)). \ \ \ \ \ (3)$

The set ${C_0}$ , the convex subset of ${C}$ with maximal affine perimeter has interesting properties. For instance its boundary contains no line segment, and if some piece of its boundary lies in the interior of ${C}$ , then this piece is a parabola arc. It has positive curvature everywhere. It is of course affinely equivariant meaning that ${S(C_0)= S(C)_0}$ . According to (3) ${C_0}$ has the worst approximation properties among all convex subsets of ${C}$ . This might explain why it comes up as the limit shape so often. Actually, the high dimensional analogue of (3) suggests that the limit shape in higher dimensions is again connected to the maximal affine surface area subset of the underlying convex body.

More reading: Imre Bárány, Random points and lattice points in convex bodies, Bull AMS (2008)