A few months ago, in the coffee room of our department, I stumbled on an older Bulletin A.M.S and, since I did not have anything pressing to do, I opened it and saw a nice survey by a Hungarian mathematician called

*. I was intrigued by the title of this beautiful survey:*

**Imre Barany***Random points and lattice points in convex bodies.*I found many marvelous questions there, questions that never came close to my mind.

One of the problems mentioned in that survey was a problem posed and solved by Renyi and Sulanke sometime in the 60s. Unfortunately, their results were written in German which for me is synonym with Verboten. I tried to find an English source for this paper, and all my Google searches were fruitless. Still, I was very curious how they did it. So, armed with Google Translate, patience and curiosity I proceeded to read the first of their 3 papers. What follows is an exposition of a small part of the first paper. For more details you can look in the first paper of Renyi-Sulanke, that is, if you know enough German to read a math paper. First the problem. $\newcommand{\bR}{\mathbb{R}}$ $\DeclareMathOperator{\area}{Area}$

Suppose that $C$ is a compact convex region in the plane with nonempty interior. Assume that

*the origin is in the interior of*$C$ and $\area(C)=1$. Choose $n$ points $P_1,\dotsc, P_n\in C$ randomly, independently and uniformly distributed. (In technical terms, we choose $n$ independent $\bR^2$-valued random variables with probability distribution $I_Cdxdy$, where $I_C$ is the characteristic function of $C$.) We denote by $\Delta_n=\Delta_n(P_1,\dotsc, P_n)$ the convex hull of this collection of points. This is a convex polygon and we denote by $V_n=V_n(P_1,\dotsc, P_n)$ its number of vertices, by $L_n=L_n(P_1,\dotsc, P_n)$ its perimeter and by $A_n=A_n(P_1,\dotsc, P_n)$ its area. These are random variables and we denote by$\newcommand{\bE}{\mathbb{E}}$ $\bE(V_n)$, $\bE(L_n)$ and respectively $\bE(A_n)$ their expectations. Reny and Sulanke asked to describe the behavior of these expectations as $n\to\infty$. $\newcommand{\bP}{\mathbb{P}}$

Surprisingly, the answer depends in a dramatic fashion on the regularity of the boundary $\newcommand{\pa}{\partial}$ $\pa C$ of $C$. Here I only want to investigate the behavior of $\bE(V_n)$, the expected number of vertices of $\Delta_n$ when $\pa C$ is

*smooth and has positive curvature at every point.*The final answer is the asymptotic relation (\ref{RSv}).

For two points $P,Q\in C$ we denote by $L(P,Q)$ the line determined by them. Denote by $\bP(P,Q)$ the probability that $(n-2)$ points chosen randomly from $C$ lie on the side of $L(P,Q)$. For $i\neq j$ we denote by $E_{ij}$ the event that all the points $P_k$, $k\neq i,j$ lie on the same side of of $L(P_i,P_j)$.

The first crucial observation, one that I missed because I am still not thinking as a probabilist, is that

\begin{equation}

V_n=\sum_{i<j} I_{E_{ij}}.

\end{equation}

In particular,

\[

\bE(V_n)=\sum_{i<j}\bE( I_{E_{ij}})= \sum_{i<j}\bP(E_{ij}).

\]

Since the points $\{P_1,\dotsc, P_n\}$ are independent and identically distributed we deduce that

\[

\bP(E_{ij})=\bP(E_{i'j'}),\;\;\forall i<j,\;\;i'<j'.

\]

We denote by $p_n$ the common probability of the events $E_{ij}$. Hence

\begin{equation}

\bE(V_n)=\binom{n}{2} p_n.

\end{equation}

To compute $p_n =\bP(E_{12})$ we observe that

\[

\bP(E_{12}) =\int_C\int_C \bP(P_1,P_2) dP_1dP_2.

\]

The line $L(P_1,P_2)$ divides the region $C$ into two regions $R_1, R_2$ with areas $a_1(P_1,P_2)$ and $a_2$. The probability that $n-2$ random independent points from $C$ lie in $R_1$ is $a_1(P_1,P_2)^{n-2}$ and the probability $n-2$ random independent points from $C$ lie in $R_2$ is $a_2(P_1,P_2)^{n-2}$. We set

\[

a(P_1,P_2):=\min\bigl\{ a_1(P_1,P_2),\;a_2(P_1,P_2)\}

\]

and we deduce that

\[

\bP(P_1,P_2)= a(P_1,P_2)^{n-2}+\bigl(\;1-a(P_1,P_2)\;\bigr)^{n-2},

\]

\begin{equation}

\bE(V_n)=\binom{n}{2}\int_C\int_C\Bigl\{ \; a(P,Q)^{n-2}+\bigl(\;1-a(P,Q)\;\bigr)^{n-2}\;\bigr\} dPdQ.

\end{equation}

Since $a(P,Q)^{n-2}\leq \frac{1}{2^{n-2}} $, we deduce that

\begin{equation}

\bE(V_n)\sim \binom{n}{2} \int_C\int_C \bigl(1-a(P,Q)\bigr)^{n-2} dPdQ\;\;\mbox{as $n\to\infty$}.

\label{4}

\end{equation}

To proceed further we need to use a formula from integral geometry. Renyi and Sulanke refer to another German source, a book of integral geometry by Blaschke. Fortunately, there is a very good English substitute to Blaschke's book that contains a myriad of exotic formulas. I am referring of course to Luis Santalo's classical monograph

*Integral Geometry and Geometric Probability*. (Santalo was Blaschke's student.)

In Chapter 4, section 1, Santalo investigates the density of pairs of points, more precisely the measure $dPdQ$ used in (\ref{4}). More precisely, he discusses a clever choice of coordinates that is particularly useful in integral geometry.

The line $L(P,Q)$ has a normal $\newcommand{\bn}{\boldsymbol{n}}$ $\bn=\bn(p,q)$

\[

\bn =(\cos \theta,\sin \theta), \;\;\theta\in [0,2\pi],

\]

and it is described by a linear equation.

\[

x\cos \theta+y\sin \theta = p,\;\;p\geq 0.

\]

Once we fix a linear isometry $ T: L(P,Q)\to \bR $, we can identify $P,Q$ with two points $t_1,t_2\in \bR$. Note that $|dt_1dt_2|$ and $|t_1-t_2|$ are independent of the choice of $T$. Santalo op. cit. shows that

\[

|dPdQ|=|t_1-t_2| |dp d\theta dt_1dt_2|.

\]

Now observe that the line $L(P,Q)$ is determined only by the two parameters $p,\theta$ so we will denote it by $L(p,\theta)$. Similarly, $a(P,Q)$ depends only on $p$ and $\theta$ and we will denote it by $a(p,\theta)$. We set

\[

p_0(\theta)=\max\{ s;\;\;s\geq 0, s\bn(\theta)\in C\,\bigr\}.

\]

We denote by $S(p,\theta)$ the segment on $L(p,\theta)$ cut-out by $C$ and by $\ell(p,\theta)$ its length.

\begin{equation}

\bE(V_n)\sim \binom{n}{2}\int_0^{2\pi}\int_0^{p_0(\theta)}\bigl(1-a(p,\theta)\;\bigr)^{n-2}\left(\int_{S(s,\theta)\times S(s,\theta)} |t_1-t_2|dt_1dt_2\right) dp d\theta.

\end{equation}

Observing that for any $\ell>0$ we have

\[

\int_{[0,\ell]\times[0,\ell]}|x-y|dxdy=\frac{ \ell^3}{3}

\]

we deduce

\begin{equation}

\bE(V_n)\sim \frac{1}{3}\binom{n}{2}\int_0^{2\pi}\int_0^{p_0(\theta)}\bigl(1-a(p,\theta)\;\bigr)^{n-2}\ell(s,\theta)^3dp d\theta.

\end{equation}

Now comes the analytical part. For each $\theta\in [0,2\pi]$ we set

\[

I_n(\theta):=\frac{1}{3}\binom{n}{2}\int_0^{p_0(\theta)}\bigl(1-a(p,\theta)\;\bigr)^{n-2}\ell(s,\theta)^3dp ,

\]

so that

\[

\bE(V_n)\sim \int_0^{2\pi} I_n(\theta) d\theta.

\]

Renyi and Sulanke find the asymptotics of $I_n(\theta)$ as $n\to \infty$ by a disguised version of the old reliable Laplace method.

Fix $\theta\in [0,2\pi]$ and set $\newcommand{\ii}{\boldsymbol{i}}$ $\newcommand{\jj}{\boldsymbol{j}}$ $\bn(\theta)=\cos \theta \ii +\sin\theta\jj\in\bR^2$. Since the curvature of $\pa C$ is strictly positive there exists a unique point $P(\theta)\in \pa C$ such that the unit outer normal to $\pa C$ at $P(\theta)$ is $\bn(\theta)$.

For simplicity we set $a(p):=a(p,\theta)$. For $p\in [0,p_0(\theta)]$ we denote by $A(p)=A(p,\theta)$ the area of the cap of $C$ determined by the line $L(p,\theta)$ and the tangent line to $\pa C$ at $P(\theta)$ $x\cos\theta+y\sin\theta=p_0(\theta)$. In Figure 1 below, this cap is the yellow region between the green and the red line.

\begin{equation}

\si_0<\inf_{\theta\in [0,2\pi]} p_0(\theta) .

\end{equation}

\begin{equation}

a(p,\theta)=A(p,\theta),\;\;\forall p\in [\si_0,p_0(\theta)].

\end{equation}

\begin{equation}

c<a(p,\theta)\leq\frac{1}{2},\;\;\forall p\in [0,s_0].

\label{low}

\end{equation}

\begin{equation}

\frac{d\ell}{dp}<0\;\;\mbox{on $[\si_0,p_0]$}.

\end{equation}

We have

\[

I_n(\theta)\sim\frac{n^2}{6}\int_0^{p_0(\theta)}\bigl(1-a(p)\,\bigr)^{n-2} \ell(p) dp

\]

\[

=\underbrace{\frac{n^2}{6}\int_0^{\si_0}\bigl(1-a(p)\,\bigr)^{n-2} \ell(p) dp}_{=:I_n^0(\theta)}+\frac{n^2}{6}\underbrace{\int_{\si_0}^{p_0(\theta)}\bigl(1-a(p)\,\bigr)^{n-2} \ell(s) dp}_{=J_n(\theta)}.

\]

The condition (\ref{low}) implies that as $n\to\infty$ we have $I_n^0(\theta)=o(1)$, uniformly in $\theta$. Thus

\begin{equation}

I_n(\theta)\sim\frac{n^2}{6} J_n(\theta),\;\;n\to\infty.

\end{equation}

We will use Laplace's method to estimate $J_n(\theta)$. We introduce a new variable $\tau=\tau(p)=p_0(\theta)-p$, $s\in [\si_0, p_0(\theta)]$ so that $\tau\in [0,\tau_0(\theta)]$, $\tau_0(\theta)=p_0(\theta)-\si_0$. Geometrically, $\tau$ denotes the distance to the tangent line $L(p_0(\theta),\theta)$.

We will denote by $L(\tau)$ the line $L(p,\theta)$. Thus, as $\tau$ increases the line $L(\tau)$ moves away from the boundary point $P(\theta)$ and towards the origin. Similarly, we set $a(\tau)=a(p)=a(p,\theta)$ etc. Hence

\[

J_n(\theta)=\int_0^{\tau_0} \bigl(1-a(\tau))^{n-2}\ell(\tau)^3 d\tau.

\]

Observe first that for along the interval $[0,\tau_0]$ we have

\[

\frac{d a}{d\tau}=\frac{dA}{d\tau}=\ell(\tau).

\]

The line $L(\tau)=L(p,\theta)$ intersects the osculating circle to $\pa C$ at $P(\theta)$ along a chord of length $\bar{\ell}(\tau)$. We set $t:=\sqrt{\tau}$. From the definition of the

**circle we deduce**

*osculating*\[

\ell(t)=\bar{\ell}(t)(1+o(1)),\;\;\frac{d\ell}{dt}=\frac{d\bar{\ell}}{dt}(1+o(1))\;\;\mbox{as $t\to 0$}.

\]

If $r=r_\theta$ denotes the radius of the osculating circle so that $\frac{1}{r_\theta}$ is the curvature of $\pa C$ at $P(\theta)$, then

\[

\bar{\ell}(\tau)= 2\sqrt{r^2-(r-\tau)^2}=2\sqrt{2r\tau-\tau^2}= 2\sqrt{\tau}\sqrt{2r-\tau}=2t\sqrt{2r-t^2}.

\]

Hence

\[

\frac{d\bar{\ell}}{dt}|_{t=0}=2\sqrt{2r}

\]

We denote the $t$-derivative by an upper dot $\dot{}$. Note that

\begin{equation}

\dot{a}=\frac{d\tau}{dt}\frac{da}{d\tau}= 2t\ell(t),\;\;\dot{\ell}(t)=\dot{\ell}(0)+O(t)=2\sqrt{2r}+O(t).

\label{dota}

\end{equation}

We deduce

\begin{equation}

J_n(\theta)=2\int_0^{t_0} \bigl( 1-a(t)\bigr)^{n-2} \ell(t)^3tdt,\;\;t_0=\sqrt{\tau_0}.

\end{equation}

Note that

\[

\ddot{a}(t)=2\ell(t)+2t\dot{\ell}(t),\;\;\frac{d^3a}{dt^3}=4\dot{\ell}(t)+2t\ddot{\ell}(t),

\]

so that

\[

a(0)=\dot{a}(0)=\ddot{a}(0)=0, \;\;\frac{d^3 a}{dt^3}|_{t=0}= 4\dot{\ell}(0)=8\sqrt{2r}.

\]

We deduce

\[

a(t)=\frac{8\sqrt{2r}}{6}t^3+O(t^4)= \underbrace{\frac{4\sqrt{2r}}{3}}_{=:C(r)}\;\;t^3+O(t^4).

\]

We set

\[

\nu:=(n-2),\;\; w_\nu(t)= \bigl( 1-a(t)\bigr)^{\nu} \ell(t)^3t,

\]

\[

\frac{u}{\nu}:=C(r)t^3\iff t=\left(\frac{u}{C(r)\nu}\right)^{\frac{1}{3}}.

\]

Note that

\[

\ell(t)^3=\bigl( 2\sqrt{2r}t+O(t^2)\;\bigr)^3=(6C(r) t)^3 + O(t^4).

\]

Hence

\[

w_\nu(t)dt = \left( 1-\frac{u}{\nu} +O\left(\frac{u}{\nu} \right)^{4/3}\;\right)^\nu \left(\frac{((6C(r))^3}{C(r)\nu} u+ O\left(\frac{u}{\nu}\right)^{4/3}\;\right) \left(\frac{u}{C(r)\nu}\right)^{1/3}\left(\frac{1}{C(r)\nu}\right)^{1/3}\frac{1}{3}u^{-2/3} du

\]

\[

=\frac{(6C(r))^3}{3C(r)^{5/3}\nu^{5/3}} \left( 1-\frac{u}{\nu} +O\left( \frac{u}{\nu} \right)^{4/3}\;\right)^\nu u^{2/3} \left( 1+ O\left(\frac{u^{1/3}}{\nu^{1/3}}\right)\;\right) du

\]

\[

=\frac{6^3C(r))^{4/3}}{3\nu^{5/3}} \left( 1-\frac{u}{\nu} +O\left( \frac{u}{\nu} \right)^{4/3}\;\right)^\nu u^{2/3} \left( 1+ O\left(\frac{u^{1/3}}{\nu^{1/3}}\right)\;\right) du

\]

Hence

\[

J_n(\theta)=\frac{6^3C(r))^{4/3}}{3\nu^{5/3}}\underbrace{\int_0^{u_\nu} \left( 1-\frac{u}{\nu} +O\left( \frac{u}{\nu} \right)^{4/3}\;\right)^\nu u^{2/3} \left( 1+ O\left(\frac{u^{1/3}}{\nu^{1/3}}\right)\;\right) du}_{=:\hat{J}_\nu},\;\; u_\nu=\nu C(r)t_0^3.

\]

Now observe that

\[

\frac{6^3C(r)^{4/3}}{3}= \underbrace{\frac{1}{3}6^3 \left(4\sqrt{2}{3}\right)^{4/3}}_{=:Z_1} r^{2/3}.

\]

and

\[

\lim_{\nu\to\infty} \hat{J}_\nu=\int_0^\infty e^{-u} u^{2/3}=\Gamma(5/3).

\]

Thus

\[

J_n(\theta) \sim Z_1\Gamma(5/3)r^{2/3}\nu^{-5/3}\sim Z_1\Gamma(5/3)r^{2/3}n^{-5/3},

\]

\[

I_n(\theta) \sim \frac{n^2}{6}J_n(\theta)\sim \frac{Z_1\Gamma(5/3)r^{2/3}}{6} n^{1/3}.

\]

Now observe that the curvature at the point $P(\theta)$ is $\kappa(\theta)=\frac{1}{r_\theta}$. hence

\[

I_n(\theta) \sim \frac{n^2}{6}J_n(\theta)\sim \frac{Z_1\Gamma(5/3)\kappa(\theta)^{-2/3}}{6} n^{1/3}

\]

If we denote by $ds$ the arclength on $\pa C$, then, by definition

\[

\frac{d\theta}{ds}=\kappa(\theta)\iff d\theta=\kappa ds.

\]

Thus

\begin{equation}

\bE(V_n)\sim \int_0^{2\pi} I_n(\theta) d\theta \sim \frac{Z_1\Gamma(5/3)}{6} n^{1/3}\int_{\pa C} \kappa^{1/3} ds.

\label{RSv}

\end{equation}

This is one of Renyi-Sulanke's result.

**Remark.**Before I close, let me mention that the asymptotics of $\bE(V_n)$ for $n$ large depends dramatically on the regulariti of the boundary of $C$. For example, if $C$ itself is a convex polygon with $r$-vertices, then Renyi-Sulanke show that

\[

\bE(V_n) \sim\frac{2r}{3}\log n.

\]

Compare this with the smooth case when the convex hull is expected to have many more vertices $\approx n^{1/3}$.

There are more to say about this story. As the title indicates, I plan to return to it in a later post.