SYLVESTER’S QUESTION: THE PROBABILITY

THAT n POINTS ARE IN CONVEX POSITION

Imre Bárány Mathematical Institute of the Hungarian Academy of Sciences, POB 127, Budapest, 1364 Hungary

barany@math-inst.hu

and Department of Mathematics, University College London, Gower Street, London WC1E 6BT, UK

Summary. For a convex body K in the plane let p(n, K) denote the probability that n random, independent, and uniform points from K are in convex position, i.e., none of them lies in the convex hull of the others. Here we determine the asymptotic behavior of p(n, K) by showing that, as n goes to infinity, n^{2} \sqrt[n]{p(n, K)} tends to a finite and positive limit.

Key words and phrases: convex sets, affine perimeter, random sample, random points in convex position, limit shape

AMS 1991 subject classification: primary 60D05, secondary 52A22 1. Introduction

Partially supported by Hungarian Science Foundation Grant T 016391 and by Research Grant of the Academy 96-31/61.

Assume K ⊂ R^{2} is a convex compact set with nonempty interior. In what follows we determine, asymptotically, the probability that n random, independent, and uniform points from K are in convex position, i.e., none of them is in the convex hull of the others. Write p(n, K) for the probability in question.

Work on p(n, K) started a long time ago. In the Educational Times in 1864 Sylvester asked [Sy] what the value of p(4, K) was without specifying K. Several answers came in. Most of them were different. The question was changed. For what K is p(4, K) minimal and maximal. Solution came from Blaschke [Bl]. For every convex body K ⊂ R^{2}

p(4, triangle) ≤ p(4, K) ≤ p(4, disk).

Valtr [V1] showed that

p(n, triangle) = \frac{2^{n}(3n − 3)!}{(n − 1)!^{3}(2n)!},

a surprisingly exact result. But since K can be sandwiched between two triangles and since p(n, triangle) is, asymptotically, (13.5e^{2}n^{−2})^{n}, we get that

c_{1} ≤ n^{2} \sqrt[n]{p(n, K)} ≤ c_{2}

with universal constants 0 < c_{1} < c_{2} < ∞. Our main result is

Theorem 1. For every convex set K ⊂ R^{2} with Area K = 1

lim n^{2} \sqrt[n]{p(n, K)}

exists and equals \frac{1}{4}e^{2}A^{3}(K) where A(K) is the supremum of the affine perimeter of all convex sets S ⊂ K.

Write AP (K) for the affine perimeter of K. (The definition is in section 4). As p(n, K) is invariant under nondegenerate affine transformations, the limit in the theorem equals \frac{1}{4}e^{2}A^{3}(K)/ Area K in general.

Theorem 1 of [B2] says that there is a unique convex compact K_{0} ⊂ K with AP (K_{0}) = A(K). The proof of Theorem 1 above gives more than just the asymptotic behaviour of p(n, K). Namely, if the random points x_{1}, …, x_{n} from K are in convex position, then their convex hull is, with high probability, very close to K_{0}. For the formulation of this “limit shape” result we use δ(A, B) to denote the Haussdorf distance of A, B ⊂ R^{2}. Write, further, C for the collection of convex compact sets K ⊂ R^{2} with nonempty interior and X or X_{n} for the random sample x_{1}, …, x_{n}. In formulae we abbreviate the statement “X_{n} is in convex position” to “X_{n} convex”.

Theorem 2. For every K ∈ C and every ε > 0,

lim_{n→∞} ℙ[δ(conv X_{n}, K_{0}) > ε}|X_{n} ⊂ K, X_{n} convex] = 0.

This theorem is a law of large numbers in the following sense. For C ∈ C and a unit vector u let C(u) ∈ C denote the point where the linear function ux reaches its maximum on C (assuming this point is unique). Writing C_{n} = conv X_{n}, we have from the proof of Theorem 1 that for every unit vector u, the expectation of C_{n}(u), conditional to X_{n} being in convex position, equals K_{0}(u), and Theorem 2 says that C_{n}(u) is concentrated around its expectation. (One can prove Theorem 2 along these lines; we choose, however, another approach to be used when proving Theorems 3 and 4.) In the case when K is the square we could even prove [BRSZ] a central limit theorem for the random variable C_{n}(u), a result which is similar to that of Sinai [Si] for the case of convex lattice polygons lying in a large square. Recent progress in this direction is due to Vershik and Zeitouni [VZ].

2. Further results

Let X = X_{n} be again a random sample of n uniform, independent points from K ∈ C. Define Q(X) as the random collection of all convex polygons spanned by the points of X, i.e., P ∈ Q(X) if and only if P = conv{x_{i_{1}}, …, x_{i_{k}}} for some k–tuple x_{i_{1}}, …, x_{i_{k}} ⊂ X that is in convex position (k ≥ 3). Without a doubt, the most frequently studied (see [RS], [Schn], [WW]) polygon in Q(X) is its largest element which is just conv X. Write |Q| for the number of elements in a set Q. Next we determine the expectation of |Q(X_{n})|:

Theorem 3. For each K ∈ C with Area K = 1,

(2.1)  lim_{n→∞} n^{−1/3} log E|Q(X_{n})| = 3 · 2^{−2/3}A(K).

Again, there is a limit shape to the elements of Q(X). One way of formulating this is

Theorem 4. For each K ∈ C and for each ε > 0,

(2.2)  lim_{n→∞} \frac{E|\{P ∈ Q(X_{n}) : δ(P, K_{0}) > ε\}|}{E|Q(X_{n})|} = 0.

This paper is closely related to the results of [B2] which is about the limit shape of convex lattice polygons contained in K. The lattice is \frac{1}{n}Z^{2} and the main result is that, as n goes to infinity, the overwhelming majority of the convex lattice polygons contained in K are very close to K_{0}. Formally, writing P_{n}(K) for the convex \frac{1}{n}Z^{2}– lattice polygons contained in K ∈ C, for every ε > 0

(2.3)  lim_{n→∞} \frac{|\{P ∈ P_{n}(K) : δ(P, K_{0}) > ε\}|}{|P_{n}(K)|} = 0.

This is completely parallel to Theorem 4 above. Results of this type were first proved by the author [B1] and Vershik [Ve] for the case when K is the square, later Sinai [Si] found stronger forms of the limit shape theorem. The analogue of Theorem 3 is the following result from [B2]: Under the assumptions of Theorem 3

(2.4)  lim_{n→∞} n^{−2/3} log |P_{n}(K)| = 3\sqrt[3]{\frac{ζ(3)}{4ζ(2)}}A(K)

where ζ(s) is Riemann’s zeta function.

In (2.1) and (2.4) n appears with different exponents. The reason is that in (2.1) the number of random points in K is n while in (2.4) the number of lattice points is n^{2}. It has been my conviction that random points and lattice points, in relation to convex bodies, behave essentially the same way. The analogy between (2.1) and (2.4) is another confirmation and so is the one between (2.2) and (2.3). In fact, this paper and [B2] establish analogous statements for random points and for lattice points in K.

The next section is about higher dimensions. Then we define the affine perimeter and recall several of its properties, mainly from Blaschke’s book [Bl] and from [B2]. We also need the special positioning of K, and the existence of a small circle rolling freely within K_{0}. In section 5 we give the proof of Theorem 1. Theorem 2 is proved in section 6. The final sections contain proofs (or sketches of proofs) of Theorems 3 and 4.

3. Higher dimensions

The probability p(n, K) can be defined for convex bodies K ⊂ R^{d} with d > 2 as well. Most of the known results are about the case when K = B^{d}, the Euclidean unit ball: Hostinsky [Ho] determined p(5, B^{3}), later Kingman [Ki] calculated p(d+2, B^{d}). Miles [Mi] showed lim_{d→∞} p(d+3, B^{d}) = 1. He conjectured and Buchta [Bu] showed lim_{d→∞} p(d + m, B^{d}) = 1 for every fixed m > 3. Bárány and Füredi [BF] proved that p(n, B^{d}) is close to one as long as n < d^{−1}2^{d/2} and close to zero for n > d2^{d/2}.

The results of this paper must have higher dimensional analogues. But the proofs given here do not go through. It is not only the unicity of the convex subset of K ⊂ R^{d} with maximal affine surface area that is missing. For comments on this see Remark 1 in [B2]. (Actually, the unicity of K_{0} is not needed for the proof of Theorem 1.) It is not clear what could replace the multiplicative formula (5.2). Nevertheless I think that for a convex K ⊂ R^{d} of volume 1 (with obvious extensions of the definitions)

(3.1)  n^{\frac{2}{d−1}} \sqrt[n]{p(n, K)} = const(d)A(K)^{\frac{d+1}{d−1}} (1 + o(1)).

There is a similar statement in the theory of best approximation of convex bodies by polytopes. Namely, let S be a convex body with smooth, say C^{2}, boundary (and Vol S = 1) and P_{n} be a convex polytope with n vertices. When approximation of S by P_{n} is measured by the volume of their symmetric difference, there is a best approximating polytope P_{n}^{∗} with n vertices. It is known [Gr] that

(3.2)  n^{\frac{2}{d−1}} Vol(S△P_{n}^{∗}) = const(d)AP (S)^{\frac{d+1}{d−1}} (1 + o(1)).

Moreover, there are indications [Gr] that the vertices of P_{n}^{∗} are distributed “uniformly” in a small neighbourhood U_{n} of ∂S. The width of U_{n} at z ∈ ∂S is n^{− \frac{2}{d−1}} κ^{\frac{1}{d+1}} (z) where κ is the product curvature. This speculation and (3.1) suggest that the random sample X_{n} is in convex position and conv X_{n} is very close to a fixed smooth convex S ⊂ K with probability (Vol U_{n})^{n}. This quantity is the largest when S = K_{0}. Thus X_{n} is most likely to be close to K_{0} when the sample is in convex position. Perhaps this can be used to attack (3.1) or the high dimensional variant of Theorem 3, or its lattice–polytope analogue. Of the latter, it is known that for K ∈ C with Vol K = 1,

0 < c_{1} < n^{−d \frac{d−1}{d+1}} log |P_{n}(K)| < c_{2}

where P_{n}(K) is the set of convex \frac{1}{n}Z^{d}–lattice polytopes contained in K, (cf. (2.4)). This follows from the results of [BV].

Returning to the planar case, it is very likely that Blaschke’s inequality (1.1) extends to

p(n, triangle) ≤ p(n, K) ≤ p(n, disk).

4. Affine perimeter

We are going to use the results of [B2] on affine perimeter extensively. Given S ∈ C choose a subdivision x_{1}, …, x_{m}, x_{m+1} = x_{1} of the boundary ∂S and lines L_{i} supporting S at x_{i} for all i ∈ [m] where [m] = {1, …, m}. Write y_{i} for the intersection of L_{i} and L_{i+1} (if L_{i} = L_{i+1}, then y_{i} can be any point between x_{i} and x_{i+1}). Let T_{i} denote the triangle with vertices x_{i}, y_{i}, x_{i+1} and also its area. The affine perimeter of S is defined as

(4.1)  AP (S) = 2 lim ∑_{1}^{m} \sqrt[3]{T_{i}}

where the limit is taken over a sequence of subdivisions with max_{1,...,m} |x_{i} −x_{i+1}| → 0. The existence of the limit, and its independence of the sequence chosen, follow from the fact that ∑_{1}^{m} \sqrt[3]{T_{i}} decreases as the subdivision is refined. Consequently

(4.2)  AP (S) = 2 inf ∑_{1}^{m} \sqrt[3]{T_{i}}.

We record further properties of the map AP : C → R:

(4.3)  AP (λS) = λ^{2/3}AP (S), when λ > 0,
(4.4)  AP (LS) = (det L)^{1/3}AP (S), when L : R^{2} → R^{2} is linear,
(4.5)  AP (S) = ∫_{∂S} κ^{1/3}ds = ∫_{0}^{2π} r^{2/3}dϕ,

where κ is the curvature and r = r(ϕ) = κ^{−1} is the radius of curvature at the boundary point with outer normal u(ϕ) = (cos ϕ, sin ϕ). In (4.5), of course, ∂S has to be sufficiently smooth.

The affine length of a convex curve is defined analogously. We will need the following fact. Given a triangle T = conv{a, b, c}, let M be the unique parabola which is tangent to ac at a and to bc at b.

(4.6) Among all convex curves connecting a and b within T the arc of the parabola M is the unique one with maximal affine length, and AP (M) = 2\sqrt[3]{T}.

We defined A(K) = sup{AP (S) : S ∈ C(K)}, where C(K) = {S ∈ C: S ⊂ K} and cited Theorem 1 of [B2] about the existence and unicity of K_{0} ∈ C, K_{0} ⊂ K with AP (K_{0}) = A(K).

As p(n, K) is invariant under (non–degenerate) affine transformations we want to choose a “good position” for K. We assume first that Area K = 1. Let E be the maximum area ellipse contained in K. It is well known that Area E ≥ \frac{π}{3\sqrt{3}}. Clearly AP (K_{0}) = A(K) ≥ AP (E). The affine isoperimetric inequality implies Area K_{0} ≥ Area E ≥ \frac{π}{3\sqrt{3}} and so the maximum area ellipse E_{0} in K_{0} has area at least \frac{π^{2}}{27} .

We say that K is in special position if Area K = 1 and E_{0} coincides with a circle of radius r_{0} centered at the origin. Clearly, r_{0} ≥ \sqrt{π/27} > 1/3 which implies, in turn, that diam K < 3. So we have

(4.7) Every K ∈ C can be brought to special position by a suitable affine transformation. In special position r_{0}B ⊂ K_{0} and K ⊂ 3B (where B is the unit circle centered at the origin).

We will write C_{s} for the collection of K ∈ C that are in special position. We will need several properties of K_{0}.

Evidently ∂K_{0} ∩ ∂K ≠ ∅ as otherwise a slightly enlarged copy of K_{0} would be contained in K and would have larger affine perimeter than A(K). Thus ∂K_{0} \ ∂K consists of (countably many) convex arcs A_{1}, A_{2}, …, to be called free arcs. The second property we need is

(4.8) Each free arc A is an arc of a parabola whose tangents at the endpoints are tangent to K_{0} as well.

It is proved in [B2] that ∂K_{0} contains no line segment on its boundary. This implies that the point z(ϕ) ∈ ∂K_{0} where the outer normal to K_{0} is u(ϕ) = (cos ϕ, sin ϕ) is uniquely determined for every ϕ ∈ [0, 2π). One can prove more: when K ∈ C_{s}, the radius of curvature to K_{0} exists and is bounded away from 0 and ∞ at every z(ϕ). Of this we only need (and prove)

(4.9) The circle of radius ρ = \frac{1}{240} rolls freely within K_{0} (provided K ∈ C_{s}),

i.e., for every z ∈ K_{0} there is a circle B_{z} of radius ρ such that z ∈ B_{z} ⊂ K_{0}. We prove (4.9) at the end of this section.

U_{m} = {u_{1}, …, u_{m}} is an ordered set of unit vectors with u_{i} = (cos ϕ_{i}, sin ϕ_{i}) for i ∈ [m] (where [m] is a shorthand for {1, …, m}) if 0 ≤ ϕ_{1} < ϕ_{2} < ⋯ < ϕ_{m} < 2π. U_{m} is dense if every arc of the unit circle whose length is \frac{5π}{m} contains at least one of the u_{i}. We say that the points x_{1}, …, x_{m} are in convex position with respect to u_{1}, …, u_{m}, (or in u–convex position, for short,) if, for every i ∈ [m],

max{u_{i}x_{j} : j ∈ [m]} = u_{i}x_{i}.

Note that x_{i} = x_{i+1} is possible. Write T_{i} for the triangle bounded by the segment [x_{i}, x_{i+1}] and lines u_{i}(x − x_{i}) = 0 and u_{i+1}(x − x_{i+1}) = 0. We denote the area of this triangle with the same letter T_{i}. Finally, if X = {x_{1}, …, x_{m}} is in u–convex position, we define

T (X) = T (X, U_{m}) = 2 ∑_{1}^{m} \sqrt[3]{T_{i}}.

(4.10) For every ε > 0 and every K ∈ C_{s} there is m_{0} such that for all m > m_{0}, for all dense ordered set U_{m} of unit vectors, and for all X = {x_{1}, …, x_{m}} ⊂ K in u–convex position, T (X, U_{m}) ≤ A(K) + ε.

Proof. Note first that T (X) is the affine perimeter of a convex body M(X): M(X) is bounded by parabola–arcs touching edges [y_{i}, v_{i}] and [v_{i}, y_{i+1}] of T_{i} at y_{i} and y_{i+1} (where v_{i} is the third vertex of T_{i}). Assume (4.10) is false. Then there is a sequence of Us and Xs with larger and larger ms so that T (X) ≥ A(K_{0}) + ε. Choose a convergent subsequence of the M(X)s. Clearly, the limit M is a convex subset of K. Since the affine perimeter is upper semicontinuous (this was proved in more general form by Lutwak [Lu]), AP (M) ≥ AP (K_{0}) + ε, a contradiction.

Proof of (4.9). Fix an x, y coordinate system and consider the parabola M_{t} whose equation is

y = g_{t}(x) = 118(x − t)^{2}

with t ∈ [−1/6, 1/6]. As K ∈ C_{s}, ∂K_{0} ∩ {(x, y) : x ∈ [−1/3, 1/3]} is the graph of two functions; let f(x) be the smaller. f is evidently convex and f(x) < g_{t}(x) for all x ∈ [−1/3, 1/3]. Set m_{t} = min{g_{t}(x) − f(x) : x ∈ [−1/3, 1/3]}.

The set C_{t} = {x ∈ [−1/3, 1/3] : m_{t} = g_{t}(x) − f(x)} is nonempty and closed. Further, there is a unique tangent to f at x ∈ C_{t} and it is parallel to the tangent of g_{t} at x. We claim C_{t} is connected. Assume not, then there is an open interval (x_{1}, x_{2}) disjoint from C_{t} but with x_{1}, x_{2} ∈ C_{t}. But then replacing the piece of ∂K_{0} between (x_{1}, f(x_{1})) and (x_{2}, f(x_{2})) with the arc of the parabola g_{t}(x) − m_{t} would produce, by (4.6), a larger affine perimeter contradicting the maximality of K_{0}.

Thus C_{t} is either a point or an interval. Increasing the coefficient 118 to 120 in the definition of M_{t} ensures that C_{t} is a single point for every t ∈ [−1/6, 1/6]. Assume the coefficient is 120 and keep the notation the same. Then t ↦ C_{t} is a point–to–point map. We claim it is continuous.

Assume t_{j} is a sequence with limit t_{0}. Then C_{t_{j}} has a convergent subsequence with limit x_{0}, say. It is easy to see that x_{0} ∈ C_{t_{0}} holds. But then C_{t_{j}} cannot have two distinct accumulation points showing that the map in question is, indeed, continuous.

A simple inspection, using the special position of K, shows that C_{−1/6} < −1/120 and C_{1/6} > 1/120. Thus the parabola g_{t}(x) − m_{t} slides freely on ∂K_{0} between x = −1/120 and 1/120. The circle of radius 1/240 rolls freely within the parabola M_{t}, so it also rolls freely on ∂K_{0} on the interval [−1/120, 1/120]. Since we can fix the coordinate system arbitrarily but the origin we get that the same circle rolls freely within K_{0}. □

5. Proof of Theorem 1

Fix K in special position and let X_{n} = {x_{1}, …, x_{n}} be an n–sample of random, independent, uniform points from K. Let m be large (it will depend on ε > 0 to be given later) and U_{m} be an ordered, dense set of unit vectors. Define i(j) by u_{j}x_{i(j)} = max{u_{j}x_{i} : i ∈ [n]}. Clearly, i(j) is well–defined with probability one and the points x_{i(1)}, …, x_{i(m)} are in convex position with respect to u_{1}, …, u_{m}. Repetitions may, however, occur but only in contiguous intervals. So let y_{1}, …, y_{k} be the collection of the distinct x_{i(j)}s in their original order. To fix the notation assume y_{h} is maximal for u_{i_{h−1}+1}, u_{i_{h−1}+2}, …, u_{i_{h}} while h ∈ [k]. Write Y = {y_{1}, …, y_{k}}. We also say, with a slight but convenient abuse of language, that Y is in u–convex position. Now p(n, K) can be computed as

p(n, K) = ℙ[X convex] = ∫ ⋯ ∫_{X convex} dx_{1} … dx_{n}

(5.1) = ∑_{k=3}^{m} ∑ \binom{n}{k} ∫ ⋯ ∫_{Y u–convex} ℙ[X convex, Y ⊂ X]dy_{1} … dy_{k},

where the second sum is taken over all possible choices of 1 ≤ i_{1} < ⋯ < i_{k} ≤ m and the probability under the integral is understood with Y fixed and X \Y varying so that X is in convex position.

The points of X\Y have to lie in the triangles T_{h} with h ∈ [k] where T_{h} is bounded by the segment [y_{h}, y_{h+1}] and by the lines u_{i_{h}}(x − y_{h}) = 0 and u_{i_{h+1}}(x − y_{h+1}) = 0.

Writing p_{h} for the number of points of X \ Y lying in T_{h} we have

ℙ[X convex, Y ⊂ X]

= ∑^{∗} \binom{n − k}{p_{1}, …, p_{k}} ∏_{1}^{k}(T_{h} ∩ K)^{p_{h}} ℙ[p_{h} points form a convex chain in T_{h} ∩ K], (5.2)

where ∑^{∗} is taken over all p_{1}, …, p_{k} that sum to n − k. We have to explain what stands after ℙ: We say that points z_{1}, …, z_{p} form a convex chain in T ∩ K where T is a triangle with distinguished vertices z_{0}, z_{p+1} ∈ K if all the z_{i} are in T ∩ K and conv{z_{0}, z_{1}, …, z_{p}, z_{p+1}} has p + 2 vertices. In our case the distinguished vertices are, of course, y_{h} and y_{h+1}. Now ℙ[p points form a convex chain in T ∩K] is meant with p random, independent points drawn uniformly from T ∩ K. This probability is known when T ⊂ K: it is proved in [BRSZ] (see also Valtr [V2] for a related statement) that

(5.3)  ℙ[p points form a convex chain in T] = \frac{2^{p}}{p!(p + 1)!}.

Here is a quick sketch of the proof. First assume that z_{1}, …, z_{p} are drawn from the unit square and seek the probability that they, together with (0, 0) and (1, 1) form a convex chain in the triangle conv{(0, 0), (1, 0), (1, 1)}. The vertical and horizontal lines through the z_{j} have p^{2} intersection points, arranged in a matrix. Every one of the p! diagonals (i.e., one point from every vertical and every horizontal line) of this matrix are equally likely but only one of them is an increasing chain from (0, 0) to (1, 1). So z_{1}, …, z_{p} is an increasing chain with probability 1/p!. Now an increasing chain is just an ordered set of (p + 1) positive vectors. It turns out that all of their permutations are equally likely. Clearly all of them are increasing but only one is convex. This gives (p!(p + 1)!)^{−1} for the probability in the square. The case of the triangle follows now readily.

We are going to estimate p(n, K) first from above and then from below. We use (5.1) and (5.2). Assume a small positive ε is given, and choose m_{0} according to (4.10) and let m > m_{0}.

For the upper estimate we assume first that K is a convex polygon (in special position). Let U_{m} be an ordered, dense set of unit vectors with the extra condition that the outer unit normals to the edges of K are all contained in U_{m}. This implies T_{h} ∩ K = T_{h} and so we can apply (5.3). (This is the only point where K has to be a polygon.) We continue (5.2) using (5.3):

(5.4)  ℙ[X convex, Y ⊂ X] ≤ (n − k)! ∑^{∗} ∏_{1}^{k} \frac{(2T_{h})^{p_{h}}}{p_{h}!^{2}(p_{h} + 1)!}

with the previous remark about ∑^{∗}. Here (2T_{h})^{p_{h}}(p_{h}!^{2}(p_{h} +1)!)^{−1} ≤ (2e^{3}T_{h}p_{h}^{−3})^{p_{h}} and it is easy to show that the product, over h = 1, …, k, of the last expression is maximal, subject to the condition ∑ p_{h} = n − k, when

p_{h} = \begin{matrix}^{3} & \sqrt{T_{h}} \\ ∑ & {k \atop j=1} & \sqrt[3]{T_{j}} \end{matrix} (n − k).

(To see this consider p_{h} a positive real variable, and determine the conditional maximum of the logarithm of the product, the condition being ∑ p_{h} = n − k.) We have then

∏_{1}^{k} \frac{(2T_{h})^{p_{h}}}{p_{h}!^{2}(p_{h} + 1)!} ≤ ∏_{1}^{k}(2e^{3}T_{h}p_{h}^{−3})^{p_{h}} ≤ (\frac{2e^{3}(∑_{1}^{k} \sqrt[3]{T_{h}})^{3}}{(n − k)^{3}} )^{n−k} ≤ (\frac{e^{3}T (Y)^{3}}{4(n − k)^{3}} )^{n−k}

where T (Y) is to be understood as 2 ∑ \sqrt[3]{T_{h}}, or as T (x_{i(1)}, …, x_{i(m)}) possibly with repeated elements. We continue (5.4) by observing that the number of terms in the sum is \binom{n−1}{k−1}:

ℙ[X convex, Y ⊂ X]
(5.5) ≤ (n − k)!\binom{n − 1}{k − 1} (\frac{e^{3}T (Y)^{3}}{4(n − k)^{3}} )^{n−k} ≤ n\binom{n − 1}{k − 1} (\frac{e^{2}T (Y)^{3}}{4(n − k)^{2}} )^{n−k} .

According to (4.10) and the choice of m, T (Y) ≤ A(K) + ε. Returning now to (5.1) we see that each integral is bounded by the right hand side of the last formula with T (Y) replaced by A(K) + ε. The number of terms of the second sum in (5.1) is equal to the number of ways to partition [m] into k contiguous intervals, i.e., \binom{m}{k}. So we infer

ℙ[X convex] ≤ ∑_{k=3}^{m} \binom{m}{k}\binom{n}{k}n\binom{n − 1}{k − 1} (\frac{e^{2}(A(K) + ε)^{3}}{4(n − k)^{2}} )^{n−k}

≤ 2^{m}n^{2m} (\frac{e^{2}(A(K) + ε)^{3}}{4(n − m)^{2}} )^{n−m} .

Here m is fixed and depends only on ε, so for large enough n we have

n^{2} \sqrt[n]{p(n, K)} ≤ \frac{e^{2}}{4} (A(K) + 2ε)^{3}.

Now let K ∈ C be arbitrary. Choose a convex polygon P containing K so that A(P) ≤ A(K) + ε. Writing Z_{n} for a random n–tuple of points from P we have

p(n, K) = ℙ[X_{n} convex in K] = ℙ[Z_{n} convex in P |Z_{n} ⊂ K]

= \frac{ℙ[Z_{n} convex in P and Z_{n} ⊂ K]}{ℙ[Z_{n} ⊂ K]}

≤ (\frac{Area P}{Area K} )^{n} ℙ[Z_{n} convex in P]

= (Area P)^{n}p(n, P) ≤ (Area P)^{n} (\frac{e^{2}(A(P) + 2ε)^{3}}{4n^{2} Area P} )^{n}

≤ (\frac{e^{2}(A(K) + 3ε)^{3}}{4n^{2}} )^{n} . (5.6)

To estimate from below we don’t need the auxiliary polygon. Shrink first K and K_{0} (from the origin) by a factor λ < 1 so that

AP (λK_{0}) = λ^{2/3}AP (K_{0}) > AP (K_{0}) − ε.

We will fix a large m soon. Define z_{h} as the point where u_{h}x reaches its maximum in λK_{0} where we simply define u_{h} = (cos \frac{2πh}{m}, sin \frac{2πh}{m}) for all h ∈ [k]. Let T_{h}(z) be the triangle bounded by the segment [z_{h}, z_{h+1}] and lines u_{h}(x − z_{h}) = 0 and u_{h+1}(x − z_{h+1}) = 0. Choose m so large that, for all h ∈ [m], the third vertex, v_{h}, of T_{h}(z) (the intersection of the two lines) is in K and, further, the length of the edges [z_{h}, v_{h}] and [v_{h}, z_{h+1}] is at least \frac{λ}{240} tan \frac{π}{m} > \frac{1}{80m}, since λ can be chosen as close to 1 as you wish. (The existence of such an m follows from (4.9).) Finally, let B_{h} be the circle of radius \frac{1}{100m^{3}} with z_{h} ∈ B_{h} ⊂ λK_{0}.

Since we are to estimate p(n, K) from below we concentrate on the large terms in (5.1) and (5.2): we only consider the terms with k = m, and will only integrate over y_{h} ∈ B_{h}. Then, since B_{h} is very small, y_{1}, …, y_{m} are in u–convex position. Moreover, all vertices of the triangles T_{h} = T_{h}(y) belong to K. Thus T_{h}(y) ∩ K = T_{h}(y) and (5.3) can be used, again. Further, since y_{h} is in B_{h} and the length of an edge of T_{h}(z) is at least 1/80m, a little elementary geometry reveals that

T_{h}(y) ≥ T_{h}(z)(1 − \frac{1}{7m}).

Using this in (5.2) we see that, assuming y_{h} ∈ B_{h},

ℙ[X convex, Y ⊂ X]
≥ ∑^{∗} \binom{n − m}{p_{1}, …, p_{m}} ∏_{1}^{m} T_{h}(y)^{p_{h}} ℙ[p_{h} points form a convex chain in T_{h}(y)]

≥ (n − m)! ∑^{∗} (1 − \frac{1}{7m})^{n−m} ∏_{1}^{m} \frac{(2T_{h}(z))^{p_{h}}}{p_{h}!^{2}(p_{h} + 1)!} (5.7)

The factors in the product are at least (2T_{h}(z))^{p_{h}}(p_{h} + 1)!^{−3} ≥ (2e^{3}T_{h}(z)(p_{h} + 1)^{−3})^{(p_{h}+1)}. The last expression is maximal, under the condition ∑(p_{h} + 1) = n, when

p_{h} + 1 = \begin{matrix}^{3} & \sqrt{T_{h}(z)} \\ ∑ & {m \atop j=1} & \sqrt[3]{T_{j}(z)} \end{matrix}n.

It is a simple matter to see then that the product in (5.7) at the integer part of the p_{h} giving the maximum is at least

(\frac{e^{3}(2 ∑ \sqrt[3]{T_{h}(z)})^{3}}{4n^{3}} )^{n} ≥ (\frac{e^{3}(A(K) − 2ε)^{3}}{4n^{3}} )^{n} .

Recall that only the case k = m is considered in (5.1), and only one term from the sum in (5.2). Using the last inequality in (5.7) and (5.1) yields

p(n, K) ≥ \binom{n}{m}(n − m)! (\frac{e^{3}(A(K) − 2ε)^{3}}{4n^{3}} )^{n} (1 − \frac{1}{7m})^{n−m} [π(100m^{3})^{−2}]^{m}

≥ \frac{1}{m!} (\frac{e^{2}(A(K) − 2ε)^{3}}{4n^{2}} )^{n} (1 − \frac{1}{7m})^{n−m} [π(100m^{3})^{−2}]^{m} ,

where the square bracket comes from integrating over B_{h} m times. Then, for large enough n,

n^{2} \sqrt[n]{p(n, K)} ≥ \frac{e^{2}}{4} (A(K) − 3ε)^{3},

proving the theorem. □

6. Proof of Theorem 2

We need further results from [B2]. Assume first that K is in special position, and a small ε > 0 is given. Recall the notation C(K) = {S ∈ C: S ⊂ K}. Lemma 5 from [B2] says the following.

(6.1) There are halfplanes H_{1}, …, H_{p}, each with (1 − ε/24)K_{0} ⊄ H_{i}, and points z_{1}, …, z_{q} ∈ K ∩ ∂(1 + ε/24)K_{0}, where p and q are at most const/ε, such that the following holds. For every C ∈ C(K) with δ(C, K_{0}) > ε either there is an i ∈ [p] with C ⊂ H_{i} or there is an j ∈ [q] with z_{j} ∈ C.

Actually, Lemma 5 in [B2] is stated without ε/24 (in “there exists η > 0” form) but the same proof with simple and generous computations shows the validity of (6.1). The second thing we need is a pointed version of the existence and unicity of K_{0} (Theorem 4 in [B2]):

(6.2) For every K ∈ C and every z ∈ K there is a unique K_{0}(z) ∈ C(K) containing z such that AP (K_{0}(z)) > AP (S) for every convex S ∈ C(K) with z ∈ S, different form K_{0}(z).

Assume now n is large, X_{n} is a random n–sample from K, write C_{n} = conv X_{n}. Let E_{i} and F_{j}, respectively, denote the event that X_{n} ⊂ H_{i}, and z_{j} ∈ C_{n}, and G the event that X_{n} is in convex position. We want to bound

ℙ[δ(C_{n}, K_{0}) > ε|G] = \frac{ℙ[δ(C_{n}, K_{0}) > ε and G]}{ℙ[G]}.

By (6.1), the numerator is smaller than

∑_{1}^{p} ℙ[E_{i} ∩ G] + ∑_{1}^{q} ℙ[F_{j} ∩ G].

The unicity of K_{0} and (6.2) imply the existence of η > 0 such that A(K ∩H_{i})+3η < A(K) and AP (K_{0}(z_{j})) + 4η < A(K). Now for large enough n, Theorem 1 ensures

(6.3)  ℙ[G] ≥ (\frac{e^{2}(A(K) − η)^{3}}{4n^{2}} )^{n} .

Next we estimate ℙ[E_{i} ∩ G]. Using Theorem 1 we have ℙ[E_{i} ∩ G] = ℙ[X_{n} ⊂ H_{i} and X_{n} convex]

= ℙ[X_{n} convex|X_{n} ⊂ H_{i}] ℙ[X_{n} ⊂ H_{i}] = p(n, K ∩ H_{i}) (\frac{Area(K ∩ H_{i})}{Area K})^{n}

≤ (\frac{e^{2}(A(K ∩ H_{i}) + η)^{3}}{4n^{2} Area(K ∩ H_{i})} )^{n} (\frac{Area(K ∩ H_{i})}{Area K})^{n}

(6.4) = (\frac{e^{2}}{4n^{2}} (A(K ∩ H_{i}) + η)^{3})^{n} < (\frac{e^{2}}{4n^{2}} (A(K) − 2η)^{3})^{n}

Estimating ℙ[F_{j} ∩G] is similar but one has to be more careful. We have to repeat the proof of Theorem 1, upper bound, with the extra condition z_{j} ∈ C_{n}. (For the sake of simplicity we ignore the use of the auxiliary polygon.) At the very start of the proof we defined x_{i(1)}, …, x_{i(m)} which was abbreviated as Y after getting rid of repetitions. This gives rise to the convex polygon (which clearly depends only on Y)

P (Y) = {x: u_{h}(x − x_{i(h)}) ≤ 0 for h ∈ [m]}.

Now the proof goes unchanged up to (5.5) this time with the condition z_{j} ∈ C_{n} which implies z_{j} ∈ P (Y) because C_{n} ⊂ P (Y). We claim that T (Y) − η < AP (K_{0}(z_{j})) provided m is large enough.

The proof is almost identical to that of (4.10). Assume the claim is false. Then there is a sequence of Y s with larger and larger ms so that T (Y)−η ≥ AP (K_{0}(z_{j})). Define the convex body M(Y) as in (4.10). Then M(Y) ⊂ P (Y) and AP (M(Y)) = T (Y). Choose a convergent subsequence of the M(Y)s with limit M ∈ C(K). Evidently z_{j} ∈ M. Since the affine perimeter is upper semicontinuous (see Lutwak [Lu]), AP (M) − η ≥ AP (K_{0}(z_{j})), a contradiction.

Now, with the claim just proved, the inequality T (Y) < AP (K_{0}(z_{j})) + η < A(K) − 3η can be used in (5.5). So we have, repeating the same steps

ℙ[F_{j} ∩ G] ≤ (\frac{e^{2}(A(K) − 2η)^{3}}{4n^{2}} )^{n} .

Now (6.2), (6.3), and (6.4) show

ℙ[δ(C_{n}, K_{0}) > ε|G] ≥ (p + q) (\frac{A(K) − 2η}{A(K) − η} )^{3n}

which is very small when n is large. □

7. Proof of Theorem 3

We are to estimate

E|Q(X_{n})| = ∑_{k=3}^{n} ∑_{x_{i_{1}} ,...,x_{i_{k}}} ℙ[x_{i_{1}}, …, x_{i_{k}} convex]

= ∑_{k=3}^{n} \binom{n}{k} ℙ[y_{1}, …, y_{k} convex] (7.1)

where y_{1}, …, y_{k} are random, independent, uniform points from K. Given ε > 0, choose n_{0}, by Theorem 1, so large that for m ≥ n_{0}

(7.2)  (\frac{e^{2}A(K)^{3}(1 − ε)}{4m^{2}})^{m} ≤ p(m, K) ≤ (\frac{e^{2}A(K)^{3}(1 + ε)}{4m^{2}})^{m} .

Let k = \sqrt[3]{2^{−2}A(K)^{3}(1 − ε)n} and assume k is an integer and n is so large that k > n_{0}. Then the kth term in the last line of (7.1) is at least

exp{3 · 2^{−2/3}A(K)n^{1/3}(1 − ε)},

as one can easily check.

To bound E|Q(X_{n})| from above, choose n so large that k_{0} = \sqrt[3]{2^{−2}A(K)^{3}(1 + ε)n} is much larger than n_{0}. We can estimate the sum in the last line of (7.1) as

E|Q(X_{n})| ≤ ∑_{k=3}^{n_{0}} \binom{n}{k} + ∑_{n_{0}+1}^{n} \binom{n}{k}p(k, K)

≤ n_{0}\binom{n}{n_{0}} + ∑_{n_{0}}^{n} \binom{n}{k} (\frac{e^{2}A(K)^{3}(1 + ε)}{4k^{2}})^{k}

≤ n_{0}\binom{n}{n_{0}} + ∑_{n_{0}}^{n} (\frac{en}{k})^{k} (\frac{e^{2}A(K)^{3}(1 + ε)}{4k^{2}})^{k} ,

where we used (7.2) as well. The maximal term in the second sum occurs at k = k_{0} and turns out to be smaller than exp{3 · 2^{−2/3}A(K)n^{1/3}(1 + ε)^{1/3}}, yielding

E|Q(X_{n})| ≤ n^{n_{0}} + n exp{3 · 2^{−2/3}A(K)n^{1/3}(1 + ε)^{1/3}}
≤ exp{3 · 2^{−2/3}A(K)n^{1/3}(1 + ε)}. □

8. Proof of Theorem 4

We have to estimate the expectation of the number of P ∈ Q(X_{n}) that satisfy δ(P, K_{0}) > ε. We use (6.1) and estimate the expectations of P ∈ Q(X_{n}) satisfying P ⊂ H_{i}, and z_{j} ∈ P, respectively.

The previous section contains bounds for ℙ[X_{k} ⊂ H_{i}, X_{k} convex] and also for ℙ[z_{j} ∈ X_{k}, X_{k} convex]. Using them the way we computed E|Q(X_{n})| there is no difficulty finishing the proof. □

Acknowledgement. My thanks are due to Rick Vitale who suggested that the random analogue of (2.1), that is, Theorem 4, may be true. Actually, it was his question and my conviction (that random points and lattice points behave similarly in generic convex bodies) that led to the results of this paper. I also thank Pavel Valtr for comments and suggestions, and for careful ckecking of the manuscript.

References

[B1] I. Bárány, The limit shape of convex lattice polygons, Discrete Comp. Geom., 13 (1995), 270–295.

[B2] I. Bárány, Affine perimeter and limit shape, J. Reine Ang. Math., 484 (1997), 71–84.

[BRSZ] I. Bárány, G. Rote, W. Steiger, C. Zhang, A central limit theorem for random convex chains, (1999), to appear in Discrete Comp. Geom.

[BF] I. Bárány, Z. Füredi, On the shape of the convex hull of random points, Prob. Theory Rel. Fields, 77 (1988), 231–240.

[BV] I. Bárány. A. M. Vershik, On the number of convex lattice polytopes, GAFA Journal, 2 (1992), 381–293.

[Bl] W. Blaschke, Vorlesungen über Differenzialgeometrie II. Affine Differenzialgeometrie, Berlin, Springer, (1923).

[Bu] C. Buchta, On a conjecture of R.E. Miles about the convex hull of random

points, Monatsh. Math., 102 (1986), 91–102.

[Gr] P. M. Gruber, Aspects of approximation of convex bodies, in: Handbook of convex geometry, Amsterdam, North Holland (1993), 1391–1438.

[Ho] B. Hostinsky, Sur les probabilités géométriques, Publ. Fac. Sci. Univ. Brno (1925).

[Ki] J. F. C. Kingman, Random secants of a convex body, J. Appl. Probab., 6 (1969), 660–672.

[Le] K. Leichtweiss, Zur Affinoberfläche konvexer Körper, Manuscripta Math., 56 (1986), 429–464.

[Lu] E. Lutwak, Extended affine surface area, Adv. Math., 85 (1991) 39–68.

[Mi] R. E. Miles, Isotropic random simplices, Adv. Appl. Prob., 3 (1971), 353–382.

[RS] A. Rényi, R. Sulanke, Über die konvexe Hülle von n zufällig gewählten Punkten, Z. Wahrsch. Verw. Geb., 2 (1963), 75–84.

[Sch] R. Schneider, Random approximation of convex sets, J. Microscopy , 151 (1988), 211–227.

[Sy] J. J. Sylvester, Problem 1491, The Educational Times, London, (April, 1864).

[Si] Ya. G. Sinai, Probabilistic approach to analyse the statistics of convex polygonal curves, Funk. Anal. Appl. 28 (1994), 41–48. (in Russian)

[V1] P. Valtr, The probability that n random points in a triangle are in convex position, Combinatorica, 16 (1996), 567–574.

[V2] P. Valtr, Catalan numbers via random planar point sets, Bolyai Society Math. Studies 6 “Intuitive Geometry”, (1997), 441–443.

[Ve] A. M. Vershik, The limit shape for convex lattice polygons and related topics, Funk. Anal. Appl., 28 (1994), 16–25. (in Russian)

[VZ] A. M. Vershik, O. Zeitouni, Large deviations in the geometry of convex

lattice polygons, Isreal J. Math., 109 (1999), 13–28.

[WW] W. Weil, J. A. Wieacker, Stochastic geometry, in: Handbook of convex geometry, Amsterdam, North Holland (1993), 1391–1438.