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 square. Their number turns out to be
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 and define as the family of all convex -lattice polygons lying in the unit square . The polygons in have a limit shape (as ) if there is a convex set such that the overwhelming majority of the polygons in are very close to . In other words, for every the number of polygons in that are farther than from (in Hausdorff distance, say) is a minute part of , that is, as . To put it differently, the average of the characteristic functions of tends to a zero-one function:
The limit shape theorem
The limit shape theorem says that such a exists, its boundary consists of four parabola arcs each touching consecutive sides of 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 (in this order on its boundary) is uniquely determined by the edge-vectors . Using this one can write down the generating function of the number of convex lattice paths from to lying in the triangle whose vertices are and . And this number can be estimated by saddle point methods (from complex variables). This is also how formula (1) for can be established.
A beautiful geometric result
On the geometry part one needs a beautiful (and almost elementary) result saying that, in a triangle with vertices and with subtriangles and (see the figure)
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 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 , (and ), the stronger inequality says that
which was probably not known to Blaschke.
It is important to point out that is the unique convex subset of whose affine perimeter is the largest among all convex subsets of . 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) in the plane and the family of all convex -lattice polygons contained in , and ask whether a similar limit shape exists in this case. The answer is yes. The limit shape, , is the unique convex subset of whose affine perimeter is maximal among all convex subsets of . The affine perimeter is upper semicontinuous, implying the existence of convex subset of with maximal affine perimeter. The proof of its uniqueness requires extra effort. In the case when is the unit square , the limit shape is equal to . Note that for every convex body with , .
Random points vs. lattice points
What happens if, instead of the -lattice points in , we take a random sample of points from , chosen independently and uniformly? Let be the set of all polygons whose vertices belong to . This is again a finite set and one can show that
where is equal to the affine perimeter, , of . This confirms the philosophy (or my intuition) that random points and lattice points in convex bodies behave similarly. Note that is of order while is of order which is fine as number of -lattice points in is approximately .
Even more interestingly, the limit shape of the polygons in is , in the sense that, in expectation, the overwhelming majority of polygons in is very close to . More precisely, for every
where 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 be a triangle with two specified vertices and say, and let be a random independent sample of uniform points from . Then is called a convex chain (from to ) if the convex hull of is a convex polygon with exactly vertices. Then
a surprisingly precise result (due to Pavel Valtr).
For the second theorem let denote the probability that the random sample (independent and uniform again) lands in convex position, that is, their convex hull is a convex -gon. For this is Sylvester’s famous four point problem from 1864 (although he did not specify the underlying convex body ). Then
with the same as before. The proof of this theorem uses the previous result of Valtr about convex chains in triangles and the properties of , the largest affine area convex subset of . The set appears again: it is the limit shape of under the condition that landed in convex position.
The map is affinely equivariant and has interesting properties. turns out to be the limit shape in some further cases as well. For instance, the maximal number of vertices of the polygons in equals
as . This is of course the same as the maximal number of points in that are in convex position. Although the convex -lattice polygon with maximal number of vertices is not necessary unique, they have a limit shape which is again . The same happens in as well. In this case, however, the expectation of the maximal number of vertices is equal to constant times but the value of this (positive) constant is not known. The reason is the following. In the triangle with specified vertices and , and random sample we define as the maximal number of points from that form a convex chain in from to . The random variable is concentrated around its expectation, which is equal to some non-negative constant times as 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 . This question about the random variable 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 denote the unit cube in 3-space, and let denote the set of all convex -lattice polygons contained in . It is known that is between and with , but nothing more precise. Probably there is a limit shape here as well, and it might be the convex subset of 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 in the plane, choose points on it, take the tangent lines at these points and form the triangles as in the figure. By definition, the affine perimeter is the infimum of the sum as the subdivision gets finer and finer. The affine perimeter of the unit circle is which explains the constant in front of . The exponent 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 where is the curvature and the radius of curvature and means integration with arc length. The affine perimeter is an affine invariant or rather equivariant meaning that for a non-degenerate affine transformation . Quite often the affine perimeter (and the affine surface area) appears in connection with affine equivariant properties of the convex set . One example is best approximation by inscribed polygons on vertices. When approximation is measured by then the best approximating polygon satisfies the estimate
The set , the convex subset of 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 , then this piece is a parabola arc. It has positive curvature everywhere. It is of course affinely equivariant meaning that . According to (3) has the worst approximation properties among all convex subsets of . 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)
Dear Imre,
Thanks for the interesting post. It may not make a difference but I wonder how you think of “creating” triangles T1 and T2? If you are given the a and b of the diagram then they determine the line 46 and one can choose point 5 on the line to produced triangles T1 and T2. But you could pick point 5 in the interior of the triangle, and some line through it which generates T1 and T2 and gives rise to a and b.
Best,
Joe
Nice post! Where can I find a (modern English) proof of (2) and its strengthening involving ?
To Joseph Malkevitch: dear Joe, point 5 is on the segment 46. This is part of the condition for inequality (2) but I did not state it explicitly (perhaps I should have..).
best, Imre
Dear Matt, you can find a proof of the stronger inequality in my paper Longest Convex chains, for instance on my homepage https://www.renyi.hu/~barany/cikkek/. Figure 2 in that paper gives a simple proof of inequality (2) from the post because
Area T_1= abc Area T and Area T_2=(1-a)(1-b)(1-c)Area T
and the inequality between the geometric and arithmetic means finishes the proof.
Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more