# The Sylvester question in $R^d$: convex sets with a flat floor

Ludovic Morin, Jean-François Marckert

<figure><img src="image_1.png" /></figure>

## To cite this version:

Ludovic Morin, Jean-François Marckert. The Sylvester question in $R^d$: convex sets with a flat floor. 2024. hal-04779758

HAL Id: hal-04779758

https://hal.science/hal-04779758v1

Preprint submitted on 13 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Sylvester question in $\mathbb{R}^d$: convex sets with a flat floor.

Jean-François Marckert & Ludovic Morin

Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France

## Abstract

Pick $n$ independent and uniform random points $U_1, \dots, U_n$ in a compact convex set $K$ of $\mathbb{R}^d$ with volume 1, and let $P_K^{(d)}(n)$ be the probability that these points are in convex position. The Sylvester conjecture in $\mathbb{R}^d$ is that $\min_K P_K^{(d)}(d+2)$ is achieved by the $d$-dimensional simplices $K$ (only).

In this paper, we focus on a companion model, already studied in the 2d case, which we define in any dimension $d$: we say that $K$ has $F$ as a flat floor, if $F$ is a subset of $K$, contained in a hyperplan $P$, such that $K$ lies in one of the half-spaces defined by $P$.

We define $Q_K^F(n)$ as the probability that $U_1, \dots, U_n$ together with $F$ are in convex position (i.e., the $U_i$ are on the boundary of the convex hull $CH(\{U_1, \dots, U_n\} \cup F)$). We prove that, for all fixed $F$, $K \to Q_K^F(2)$ reaches its minimum on the "mountains" with floor $F$ (mountains are convex hull of $F$ union an additional vertex), while the maximum is not reached, but $K \to Q_K^F(2)$ has values arbitrary close to 1. If the optimisation is done on the set of $K$ contained in $F \times [0, d]$ (the "subprism case"), then the minimum is also reached by the mountains, and the maximum by the "prism" $F \times [0, 1]$. Since again, $Q_K^F(2)$ relies on the expected volume (of $CH(\{V_1, V_2\} \cup F)$), this result can be seen as a proof of the Sylvester problem in the floor case.

In 2d, where $F$ can essentially be the segment $[0, 1]$, we give a general decomposition formula for $Q_K^F(n)$ so to compute several formulas and bounds for different $K$. In 3D, we give some bounds for $Q_K^F(n)$ for various floors $F$ and special cases of $K$.

# 1 Introduction and main results

Let $d \ge 2$ be a fixed integer. Throughout the paper, the space $\mathbb{R}^d$ is equipped with an orthonormal basis $e_1, \dots, e_d$, and its associated coordinate system.

For $n \ge 1$, we say that an $n$-tuple of points $u[n] = (u_1, \dots, u_n) \in (\mathbb{R}^d)^n$ is in convex position if $\{u_1, \dots, u_n\}$ forms the vertex set of a convex polytope. For any compact convex domain $K$ in $\mathbb{R}^d$ with non-empty interior and for any $n \in \mathbb{N}$, we let $\cup_K$ be the uniform distribution on $K$, and let $\cup_K(n)$ be the product measure (of $n$ iid random variables $U[n] = (U_1, \dots, U_n)$ with common distribution $\cup_K$).

Finally, we let $P_K^{(d)}(n)$ be the probability that an $n$-tuple of points $U[n]$ with distribution $\cup_K(n)$ is in convex position.

The very first problem in the study of $P_K^{(d)}(n)$ was posed by Sylvester [26] in 1864 (see Pfiefer [22] for a history of this problem) and consisted in determining the probability that 4 random points in the plan, are in convex position. This problem evolved over time into computing the convex domains $K$ that minimize or maximize the probability $P_K^{(2)}(4)$. Blaschke [5] provided the answer to this question in 1917, by proving that the lower bound is reached when $K = \Delta$ is a triangle, and the upper bound when $K = \bigcirc$ is a disk, namely

$$ \frac{2}{3} = P_{\Delta}^{(2)}(4) \le P_{K}^{(2)}(4) \le P_{\bigcirc}^{(2)}(4) = 1 - \frac{35}{12\pi^2}. $$
In larger dimensions, an analogous problem exists. Since $d+1$ random points are in convex position with probability 1, the question is whether we may optimize the quantity $P_K^{(d)}(d+2)$? As a generalization of Blaschke's proof, the upper bound $P_K^{(d)}(d+2) \le P_{\bigcirc^d}^{(d)}(d+2)$ is true whereas the following $d$-Sylvester's question

$$P_{\Delta^d}^{(d)}(d+2) \le P_K^{(d)}(d+2) \le P_{\bigcirc^d}^{(d)}(d+2),$$

($\Delta^d$ and $\bigcirc^d$ denote respectively a simplex and an ellipsoid of volume 1) remains a conjecture due to the lower bound. In general, the quantity $P_K^{(d)}(d+2)$ satisfies

$$P_K^{(d)}(d+2) = 1 - (d+2)\mathbb{E}(\mathrm{Vol}_d(\mathrm{Simplex}(U_1, \dots, U_{d+1}))), \quad (1.1)$$

and this formula may be understood as the fact that $U_1, \dots, U_{d+2}$ are not in convex position if and only if one of the $U_i$ is in the convex hull of the others. Hence, the problem of optimizing $K \mapsto P_K^{(d)}(d+2)$ is equivalent to the problem of optimizing $K \mapsto -\mathbb{E}(\mathrm{Vol}_d(\mathrm{Simplex}(U_1, \dots, U_{d+1})))$.

This problem seems to be out of reach for the moment, and then, we will turn our attention to another problem, which has a common flavour for many reasons, which should become clear gradually.

**Definition 1.1.** Let $K$ be a compact convex set of $\mathbb{R}^d$, for some $d \ge 2$, and $F$ be a subset of $\mathbb{R}^{d-1}$. We say that $F$ is the floor of $K$ if $K$ is contained in the half space $\{x_d \ge 0\}$, and if its intersection with the hyperplane $x_d = 0$ is $F \times \{0\}$.

Hence, the floor of $K$ exists if $K$ intersects the hyperplane $\mathbb{R}^{d-1} \times \{0\}$ and lies above it. By definition, a floor $F$ is always a compact convex set of $\mathbb{R}^{d-1}$. For the sequel, we will need to distinguish **two families of convex sets** (see Fig. 1):

**Definition 1.2.** ■ We say that a convex set $K$ with floor $F$ is a **sub-prism** if $K$ is a subset of $F \times [0, H]$ for some $H \ge 0$.

■ We denote by SubPrism($F$) the set of convex sets $K$, that are sub-prisms with floor $F$, and such that $\mathrm{Vol}_d(K) = 1$.

In the following, we will say that $\mathrm{Floor}(K) \times [0, H]$ is a **prism**.

In geometry, the word "prism" is often used in 3D to identify a polyhedron that is equal to the convex hull of two (non-coplanar) polygons, image of each other by a translation. In this case, each face other than $F$ is still a polygon. It will not be the case here, since we do not necessarily assume that $F$ is a polytope (it can be smooth, for example).

The second family we introduce is:

**Definition 1.3.** We denote by CCSF($F$) the set of Compact Convex Set $K$ with Floor $F$, and such that $\mathrm{Vol}_d(K) = 1$.

**Convention:** Throughout the paper, $F$ will be a compact convex set of $\mathbb{R}^{d-1}$ such that

$$\mathrm{Vol}_{d-1}(F) = 1. \qquad (1.2)$$

Since affine maps preserve both convexity and the uniform distribution, this is not a real restriction.
<figure><img src="image_3.png" /><figcaption>Figure 1: Two compact convex sets of $\mathbb{R}^3$ with the same floor $F$; the second one is a mountain. Both of them are subprisms. The third one is not a subprism, it is an element of $\text{CCSF}(F)$.</figcaption></figure>

**A modified Sylvester question in the fixed floor case.** Let us fix a floor $F$, which will always be assumed to be a compact convex set (of volume 1) in $\mathbb{R}^{d-1}$. For any $K \in \text{CCSF}(F)$, denote by $Q_K(2)$ the probability that the convex hull of the set formed by the floor of $K$ (that is, the domain $F$), and two random points taken independently and uniformly in $K$ contains these two points on its boundary.

We will motivate this question further in Section 1.3, but for the moment, observe that the problem of optimizing $K \mapsto Q_K(2)$ has the same flavour as that of $K \mapsto P_K^{(2)}(4)$ due to an analogue of the Efron formula [10]; indeed, by the same reasoning as for (1.1) we have:

$$Q_K(2) = 1 - 2\mathbb{E}(\text{Vol}_d(\text{CH}(\{U\} \cup F))), \qquad (1.3)$$

where $U$ is uniform in $K$. The two quantities $P_K^{(d)}(d+2)$ and $Q_K(2)$ are the first "non trivial quantities" in both cases.

We then introduce a geometrical object:

**Definition 1.4.** For a point $z$ with positive last coordinate $z_d \ge 0$, we call mountains with apex $z$, the compact convex set

$$\text{Mountain}_F(z) = \text{CH}(\{z\} \cup F).$$

Of course, $\text{Mountain}_F(z)$ has floor $F$, and since $\text{Vol}_{d-1}(F) = 1$,

$$\text{Vol}_d(\text{Mountain}_F(z)) = z_d/d. \qquad (1.4)$$

One of the main contributions of this paper are the two following theorems:

**Theorem 1.5.** [*Optimisation in the set SubPrism($F$).*] Let $d \ge 2$, $F$ be a compact convex set in $\mathbb{R}^{d-1}$ such that $\text{Vol}_{d-1}(F) = 1$. For all sub-prism $K \in \text{SubPrism}(F)$,

$$Q_{\text{UnitMountain}}(2) \le Q_K(2) \le Q_{\text{UnitPrism}}(2),$$

where the UnitPrism is the prism $F \times [0, 1]$ and a UnitMountain identifies any mountain with floor $F$ with volume 1.

Moreover,

$$Q_{\text{UnitMountain}}(2) = 1 - 2/(d+1) \qquad (1.5)$$

$$Q_{\text{UnitPrism}}(2) = 1 - 1/d, \qquad (1.6)$$

both of which do not depend on $F$.
Again, since invertible affine maps preserve convexity and the uniform measure, this result applies to "non vertical prism".

**Remark 1.6.** The bound $Q_K(2) \le Q_{\text{UnitPrism}}(2)$ holds even if $K$ is not convex. The proof we will give entails that if $K$ can be written as $\cup_{z \in F\{z\}} \times [0, G(z)]$ where $G(z)$ is the height at $z$, then under the only hypothesis that $G$ is measurable and satisfies $\int_F G(z) dz = 1$, then in this case $Q_K(2) \le Q_{\text{UnitPrism}}(2)$.

**Theorem 1.7.** [Optimization in the set CCSF($F$)]. Let $d \ge 2$, $F$ be a compact convex set in $\mathbb{R}^{d-1}$ such that $\text{Vol}_{d-1}(F) = 1$. For all $K \in \text{CCSF}(F)$,

$$Q_{\text{UnitMountain}}(2) \le Q_K(2) < 1,$$

and there exists an element of CCSF($F$) such that $Q_K(2) \ge 1 - \alpha$, for all $\alpha > 0$, and none such that $Q_K(2) = 1$.

## 1.1 Related results in 2D

Under the quantity $P_K^{(d)}(n)$ lie many other questions. Can we compute $P_K^{(d)}(n)$ for some specific domains $K$? Can we optimize $P_K^{(d)}(n)$ on $K$ for other values of $n$? How does an $n$-tuple of points $U[n]$ with distribution $\cup_K(n)$ behaves when conditioned to be in convex position?

To date, the overwhelming majority of answers to these problems have been given when $d = 2$.

<figure><img src="image_4.png" /><figcaption>Figure 2: A subprism convex domain with floor $[0, 1] \times \{0\}$; in the first picture the 3 points are in convex position, but they are not in convex position together with $F$, since, as shown in the second picture, the convex hull of the union of $F$ and of the three points does not contain all these objects on its border. In the third picture, they are in convex position together with $F$. In the 2D-case, instead of $F$, one can require equivalently that the two extremities of the segments (instead of $F$), together with the other points, forms the vertex set of a convex polygon. In a general dimension, one can replace $F$ by its extremal points.</figcaption></figure>

For example, a natural generalization of Sylvester's problem when $d = 2$ would be

$$P_{\Delta}^{(2)}(n) \le P_{K}^{(2)}(n) \le P_{\bigcirc}^{(2)}(n),$$

for any compact convex set $K$ of $\mathbb{R}^2$. The case $n = 5$ was proved by Marckert and Rahmani [18], but $n \ge 6$ is still a conjecture (but one finds in [18] an explicit formula to compute $P_K^{(2)}(n)$).

As for the computation of $P_K^{(2)}(n)$, several results are known. If $K$ is a parallelogram or a triangle, Valtr [27, 28] computed two exact formulas for all $n \ge 3$:

$$P_{\square}^{(2)}(n) = \frac{1}{(n!)^2} \binom{2n-2}{n-1}^2 \quad \text{and} \quad P_{\Delta}^{(2)}(n) = \frac{2^n(3n-3)!}{(2n)!!((n-1)!)^3}.$$
<figure><img src="image_5.png" /><figcaption>Figure 3: Buchta's method to compute the probability that the $n$ points $U_1, \cdots, U_n$ are in convex position in a parallelogram. Push the sides of the initial parallelogram inside, and stop them when they hit a point. In the end, each of the four sides contains a point (the 4 points are not necessarily different). This forms 2, 3 or 4 triangles, all of which have 2 marked points at their boundaries. The $U_i$ are in convex position, if all the other points belong to a triangle, and if all the points inside a triangle, together with the two marked points are in convex position.</figcaption></figure>

In dimension $d=2$, a fixed floor $F$ can only be a nonzero segment. Thus, $Q_K(n)$ is the probability that $n$ points in $K$ are in convex position, together with both extremities of $F$. In fact, an important tool for these results relates to the $2d$-floor case. Indeed, a classical method to compute $P_K(n)$ consists "in shrinking $K$", e.g., by pushing the boundaries inwards (as in [7], Marckert [17], Morin [21, 20], see also Fig. 3), until some points among the $U_i$ are "hit". This defines several regions, which either must not contain any points, or must bound a compact convex domain containing a subset of the $U_i$ that must be in convex position together with the two extremities of a segment (these extremities being some $U_i$ discovered when pushing the boundaries). Up to an affine map, this latter domain is a compact convex set with a floor. In [7] and [21, 20], the zones are triangles, while in [17] they are the interior of some arcs of disk parameterized by an angle $\theta$.

Some important asymptotic results also involve this type of tool, such as Bárany's formula [2], who proved that for any compact convex domain $K \subset \mathbb{R}^2$,

$$ \lim_{n \to +\infty} n^2 \left( P_K^{(2)}(n) \right)^{\frac{1}{n}} = \frac{1}{4} e^2 \mathrm{AP}^*(K)^3, $$

where $\mathrm{AP}^*(K)$ is the supremum of the affine perimeters of all convex sets $S \subset K$. In the case where $K$ is a polygon, this logarithmic equivalent was refined into a true equivalent by Morin [21, 20]. Both authors used the well-known case when $K$ is a triangle, due to Bárany, Rote, Steiger and Zhang [4]:

$$ t_n := Q_{\Delta}(n) = \frac{2^n}{n!(n+1)!}. \qquad (1.7) $$

Again, the notation "Q" refers to the floor case when $P$ refers to the classical one.

Other questions then arise. Do we know other values of $Q_K(n)$? Can we optimize $Q_K(n)$ for values of $n \ge 3$? In this paper, we give a recursive formula for $Q_K(n)$ in the $2d$-case which allows to recover the triangle case (Theorem 3.3), to compute exact values in the case where $K$ is a square (denoted by $q_n$, see Proposition 3.4) or a parabola (Theorem 3.5) above the segment $F$ (denoted by $p_n$), namely

$$ p_n = \frac{12^{n+1}}{6(2n+2)!} \quad \text{and} \quad q_n = \frac{1}{n!(n+1)!} \binom{2n}{n}. $$
Of course, a rewording of Theorem 1.5 in the 2d-case gives immediately that

$$t_2 = \frac{1}{3} \le Q_K(2) \le q_2 = \frac{1}{2}.$$

However, two additional independent elementary proofs will be given in Section 3.4. More generally, we believe that,

**Conjecture 1.8.** For all $n \ge 3$, and all $K \in \text{CCSF}([0, 1])$,

$$t_n \le Q_K(n) \le q_n.$$

## 1.2 Bounds and universal bounds in dimension 3

When $d > 2$, exact results for the computation of $Q_K(n)$ or $P_K^{(d)}(n)$ are rare. Most of the known results were obtained when $K = \mathcal{O}^d$, the Euclidean unit ball in dimension $d$. The value of $P_{\mathcal{O}^3}^{(3)}(5)$ (that is, 5 points in the 3d-ball) was computed by Hostinsky [14], before a general formula for $P_{\mathcal{O}^d}^{(d)}(d+2)$ was found by Kingman [15]. Miles [19] proved that $\lim_{d \to \infty} P_{\mathcal{O}^d}^{(d)}(d+3) = 1$, and later conjectured that for all $m > 4$, $\lim_{d \to \infty} P_{\mathcal{O}^d}^{(d)}(d+m) = 1$, a conjecture proved by Buchta [6].

Even in dimension 3, very little is known. The most classical and simplest results in dimension 2 have no analog in dimension 3 (however, Buchta & Reitzner [8] computed the expected volume of the convex hull of $n$ iid uniform points taken in the tetrahedron).

The last section of this paper tries to remedy this problem by providing bounds in the floor case. In Theorem 4.1, we will prove that for any floor $F$ the unit mountains $M$ with floor $F$, we have

$$Q_M(n) \ge \frac{2^n}{n!} \prod_{j=1}^{n} \frac{1}{3j-1}.$$

When $F$ is a triangle, such a mountain is a tetrahedron $T$. In this case, we also obtained an upper bound (and an improved lower bound) in Theorem 4.7 and Theorem 4.8, and so we give two explicit sequences $(u_n)$ and $(\ell_n)$ such that

$$\ell_n \le Q_T^{(3)}(n) \le u_n, \text{ for } n \ge 0. \qquad (1.8)$$

## 1.3 Motivation

In fact, there are several motivations for studying these "floor case questions".

■ In 2d, an important tool in the study of points in convex position are convex chains in a triangle (with two vertices of the triangle being elements of this chain). They appear in under some forms in most of papers devoted to points in convex position: Bárány & al. [4]e Valtr [27, 28], Buchta [7], Morin [20, 21]. These objects correspond to "2D floor cases" (actually, 2D mountains) in the present paper (and in Marckert [17], the decomposition is also based on bi-pointed segments, that correspond to some compact convex sets with a floor as well). The reason, is that, as already explained, it is natural in most situations to cut the random convex chain under stud between well-chosen points; this allows workinf in a simpler form (a triangular shape, in general), and the "floor" is another way to understand how we fix two boundary points. We can infer the global behavior of these global chains, from these simpler chains in triangles (see e.g. [2] for the limit shape theorem, and Morin [20] for asymptotics, and Gaussian
fluctuations around the limit shape). Of course, these triangles we discuss here are the same object as our 2d mountains, and in [17] the author works in domains decomposed as segments surrounded by an "arc of circle".

The computation of $P_K^{(d)}(d+2)$ becomes much more difficult as soon as $d \ge 3$, and most likely due to the fact that there is no convenient decomposition suitable for a combinatorial approach. For example, if one draws $n$ iid uniform points $U_1, \dots, U_n$ in the 3D cube, and if one pushes the faces of the cube inward until they hit a point in $U[n]$, then one gets a parallelepiped with marked points, and this structure does not seem to be helpful for further decomposition of the problem! (For example, if each of the 6 faces contains a distinct point, then, the complement of the convex hull of these points is still connected, and it seems difficult to make any progress from there).

However, because of the success and simplicity of the study of the "floor case in 2D", it is natural to try to understand the floor case in 3D, and in the following dimensions.

■ Take a compact convex set $K$ of dimension $d$, and let $d+2$ iid uniform points $U_1, \dots, U_{d+2}$ into $K$. Let $S_m$ be the convex hull of $U_1, \dots, U_m$, and $H_m$ be the affine space of dimension $m-1$ containing $S_m$. We have

$$ P_K^{(d)}(d+2) = 1 - (d+2)\mathbb{E}(\mathrm{Vol}_d(\mathrm{CH}(S_{d+1}))) \\ = 1 - \frac{d+2}{d} \mathbb{E}(\mathrm{Vol}_{d-1}(\mathrm{CH}(S_d)) \times D(U_{d+1}, H_d)) $$

where $D(U_{d+1}, H_d)$ is the Euclidean distance of $U_{d+1}$ from the hyperplan $H_d$ (for more information, see e.g. Kingman [15], who computed $P_K^{(d)}(d+2)$, where $K$ is the unit Euclidean ball in $\mathbb{R}^d$).

To solve the Sylvester problem, it is natural to try to understand the typical (joint) behavior of the two random variables $\mathrm{Vol}_{d-1}(\mathrm{CH}(S_d))$ and $D(U_{d+1}, H_d)$. If we draw a small picture, we see that $H_d$ cuts $K$ into two parts $P_1$ and $P_2$, and $U_{d+1}$ will fall into one of these parts, proportional to its $d$-volume. Up to an affine map, $H_d$ plays the role of a floor, and conditional on $H_d$ (and of the part $P_j$ in which $U_{d+1}$ arrived) $D(U_{d+1}, H_d)$ has the same distribution "as the height of a random point in $P_j$", which we will see throughout the rest of the paper, up to a constant, is the probability that two points in $P_j$, are in convex position in the floor problem in $P_j$.

Trying to understand what kind of part maximizes the height expectation – and we proved that they are mountains – can be seen as a step towards solving the Sylvester problem.

## 1.4 Related results about the convex hull of random points

In this paper, we focus on the probability of points being in convex position. An important number of results instead concern the behavior of the convex hull of random points. The two topics are related by many ways. Let $C_n^{(d)}(K)$ be the convex hull of $n$ iid uniform points chosen in $K$, where $d$ is the dimension of the ambient space.

In this matter, we can cite Rényi & Sulanke [24] for the computation of the expectation on the number of vertices of $C_n^{(2)}(K)$ (observing a $\log n$ behavior when $K$ is a polygon, and an $n^{1/3}$ behavior, when $K$ is smooth). Groeneboom [11] for a central limit theorem for the number of vertices of $C_n^{(2)}(K)$ when $K$ is a polygon, or a disk (variance expansion and Berry-Esseen bound when $K$ is a polygon can be found in Gusakova & al. [12], for large deviations in general 2D compact convex sets, see Vu [29], Calka and Schreiber [9]).
In higher dimensions, precise results concerning the number of vertices, and number of facets have also been obtained (see e.g. Reitzner [23], Bárány and Reitzner [3]). See Majumdar & al. [16] for a survey written in 2010.

## 2 Optimization of $Q_K(2)$ in the multidimensional case

Consider an element $K$ taken in CCSF($F$) or in SubPrism($F$), and take $U$ a uniform random point inside $K$. Set $H = U_d$, the last coordinate of $U$, seen as a height, and let $Z = (U_1, \cdots, U_{d-1})$ the $d-1$ first coordinates. If $K$ is in SubPrism($F$), then $Z \in F$ almost certainly, while this may not be the case for $K \in \text{CCSF}(F)$.

Consider the "layer of $K$ at level $t$", defined by

$$ \text{Layer}_K(t) = K \cap (\mathbb{R}^{d-1} \times \{t\}), $$

and consider its volume

$$ L_K(t) := \text{Vol}_{d-1}(\text{Layer}_K(t)). $$

It is clear that $L_K$ is null outside the compact set $[0, m_K]$ where $m_K = \max\{z_d : z \in K\}$ is "its maximal height". By standard calculus

$$ \text{Vol}_d(K) = \int_0^{m_K} L_K(t) dt = 1, $$

and in fact, $L_K$ is the density of the random variable $H$.

**Lemma 2.1.** Let $K \in \text{CCSF}(F)$ (which includes SubPrism($F$)), then

$$ Q_K(2) = 1 - 2 \int_0^{+\infty} L_K(t) \frac{t}{d} dt. \qquad (2.9) $$

*Proof.* By (1.3),

$$ Q_K(2) = 1 - 2\mathbb{E}(\text{Vol}_d(\text{Mountain}_F(Z, H))) = 1 - 2\mathbb{E}(H/d) = 1 - 2 \int_0^{+\infty} L_K(t) \frac{t}{d} dt. \qquad (2.10) $$

□

Hence, in the case of unitary mountains,

$$ L_{\text{UnitMountain}}(t) = (1 - t/d)^{d-1} \mathbb{1}_{[0,d]}(t), \qquad (2.11) $$

and then $Q_{\text{UnitMountain}}(2) = 1 - 2 \int_0^d (1 - t/d)^{d-1} \frac{t}{d} dt = 1 - \frac{2}{d+1}$, as announced. In the case of UnitPrism, $L_{\text{UnitPrism}}(t) = \mathbb{1}_{[0,1]}(t)$, so that $Q_{\text{UnitPrism}}(2) = 1 - 2 \int_0^1 \frac{t}{d} dt = 1 - 1/d$ as announced.

We will first establish Theorem 1.5, and then Theorem 1.7.

### 2.1 SubPrism case: proof of Theorem 1.5

#### 2.1.1 Proofs of Theorem 1.5: upperbound

Each element $K \in \text{SubPrism}(F)$ is characterized by its top function $G_K$ defined by

$$ \begin{array}{rcl} G_K: & F & \rightarrow [0, +\infty) \\ & z = (z_1, \cdots, z_{d-1}) & \mapsto G_K(z) := \sup\{y \in \mathbb{R}, (z_1, \cdots, z_{d-1}, y) \in K\} \end{array} \qquad (2.12) $$
since

$$K = \bigcup_{z \in F} \left[ (z_0, \dots, z_{d-1}, 0), (z_0, \dots, z_{d-1}, G_K(z)) \right]. \qquad (2.13)$$

Thus, if $K \in \text{SubPrism}(F)$, both $G_K$ and $K$ characterize each other. Moreover, a function $G: F \to \mathbb{R}$ is the top function of a compact convex set $K$ in SubPrism($F$) iff it is nonnegative, concave, and satisfies $\int_F G(z) dz = 1$.

Recall that for $U = (Z, H)$ uniform in $K$, and by (2.10), $Q_K(2) = 1 - 2\mathbb{E}(H/d)$. The density of $Z$ is $G_K$ on $F$ while, given $Z, H$ is uniform on $[0, G_K(z)]$, so that $\mathbb{E}(H | Z = z) = G_K(z)/2$. Hence

$$Q_K(2) = 1 - 2 \int_F G_K(z) \frac{G_K(z)}{2d} dz = 1 - \int_F \frac{G_K^2(z)}{d} dz. \qquad (2.14)$$

From here the proof of the upper bound is quasi-immediate:

$$Q_{\text{UnitPrism}}(2) - Q_K(2) = \int_F \frac{G_K^2(z) - 1}{d} dz = \int_F \frac{(G_K(z) - 1)^2}{d} dz + \underbrace{\int_F \frac{(2G_K(z) - 2)}{d} dz}_{=0} \ge 0.$$

### 2.1.2 Proof of Theorem 1.5 and of Theorem 1.7 lowerbound

The proof we give is valid in CCSF($F$), and since the lower bound is reached for unitary mountains (for any two unitary mountains $M_1$ and $M_2$, $Q_{M_1}(2) = Q_{M_2}(2)$), some of which are in SubPrism($F$), the proof that follows is valid in SubPrism($F$) too.

In the following, $K$ is an element of CCSF($F$), and $M$ is a unitary mountain in CCSF($F$). Using (2.9), it suffices to prove that

$$\mathbb{E}(H_K) \le \mathbb{E}(H_M) \qquad (2.15)$$

where $H_K$ and $H_M$ denote the respective random variable heights of a point $U_K$ and $U_M$ taken uniformly in $K$ and $M$. For any non-negative random variable $X$, we have $\mathbb{E}(X) = \int_t \mathbb{P}(X \ge t) dt$. Since

$$\mathbb{P}(H_K \ge t) = \int_t^\infty L_K(s) ds = 1 - \int_0^t L_K(s) ds,$$

we have

$$\mathbb{E}(H_M) - \mathbb{E}(H_K) = \int_0^{+\infty} \left( \int_0^t L_K(s) - L_M(s) ds \right) dt. \qquad (2.16)$$

To prove (2.15), it suffices to show that

**Lemma 2.2. We have**

$$B_K(t) \ge B_M(t) \quad \text{for all } t \qquad (2.17)$$

where

$$B_K(t) = \int_0^t L_K(s) ds, \quad B_M(t) = \int_0^t L_M(s) ds$$

are the volume of $K$ and of $M$ below level $t$.
**Lemma 2.3.** Let $K$ be an element of CCSF($F$), and $m_K$ its maximal height. For every $(t_1, s, t_2)$ such that $0 \le t_1 \le s \le t_2 \le m_K$, we have

$$L_K(s)^{\frac{1}{d-1}} \geq \frac{t_2-s}{t_2-t_1} L_K(t_1)^{\frac{1}{d-1}} + \frac{s-t_1}{t_2-t_1} L_K(t_2)^{\frac{1}{d-1}}, \quad (2.18)$$

which is equivalent to say that $s \mapsto L_K(s)^{\frac{1}{d-1}}$ is concave. For a unitary mountain $M$ (with maximal height $d$) for $t \in [0, d]$,

$$L_M(t) = \left(1 - \frac{t}{d}\right)^{d-1}, \quad B_M(t) = 1 - \left(1 - \frac{t}{d}\right)^d$$

and then

$$L_M(s)^{\frac{1}{d-1}} = \frac{t_2-s}{t_2-t_1} L_M(t_1)^{\frac{1}{d-1}} + \frac{s-t_1}{t_2-t_1} L_M(t_2)^{\frac{1}{d-1}}, \quad (2.19)$$

and hence, $t \mapsto L_M(s)^{\frac{1}{d-1}}$ is linear.

*Proof.* Fix three heights $t_1, s, t_2$ such that $0 \le t_1 \le s \le t_2 \le m_K$. Since $K$ is convex, any line intersecting both $\text{Layer}_K(t_1)$ and $\text{Layer}_K(t_2)$ intersects also $\text{Layer}_K(s)$, and then

$$\text{Layer}_K(s) \supset \frac{t_2-s}{t_2-t_1}\text{Layer}_K(t_1) + \frac{s-t_1}{t_2-t_1}\text{Layer}_K(t_2), \quad (2.20)$$

(since each element $z \in \text{Layer}_K(s)$ can be written as $\frac{t_2-s}{t_2-t_1}z_1 + \frac{s-t_1}{t_2-t_1}z_2$ for some $z_1 \in \text{Layer}_K(t_1)$ and $z_2 \in \text{Layer}_K(t_2)$). By the Brunn-Minkowski inequality (see e.g. Schneider [25, Section 6.1]) applied to the $d-1$ dimensional layers, we get

$$\mathrm{Vol}_{d-1}(\mathrm{Layer}_K(s)) \geq \mathrm{Vol}_{d-1}\left(\frac{t_2-s}{t_2-t_1}\mathrm{Layer}_K(t_1)\right) + \mathrm{Vol}_{d-1}\left(\frac{s-t_1}{t_2-t_1}\mathrm{Layer}_K(t_2)\right) \quad (2.21)$$

and since $\mathrm{Vol}_{d-1}(c\text{Layer}_K(\tau)) = c^{d-1}\mathrm{Vol}_{d-1}(\text{Layer}_K(\tau))$, we get (2.18). The other statements are just exercises.

□

To complete the proofs of the lower bound parts of Theorem 1.5 and of Theorem 1.7, it remains to prove Lemma 2.2.

*Proof of Lemma 2.2.* There is nothing to prove if $K$ is a unit mountain: we will assume that $K$ is not a unit mountain, so that its maximum height satisfies $m_K < d$.

Consider the map $\Psi: \mathbb{R}^+ \to \mathbb{R}$

$$\Psi(t) := L_K(t)^{\frac{1}{d-1}} - L_M(t)^{\frac{1}{d-1}}.$$

We claim that there exists $t^* \in (0, m_K)$ such that $\Psi(t)$ is non-negative on $[0, t^*]$, non-positive on $(t^*, m_K)$.

The main argument will be the concavity of $t \mapsto L_K(t)^{\frac{1}{d-1}}$ and of $t \mapsto -L_M(t)^{\frac{1}{d-1}}$ (notice the sign): there is only a tiny complication that comes from the fact that the first one is concave on $[0, m_K]$ (and null thereafter), while the second is concave on the larger interval $[0, d]$ (and null thereafter).

To prove the claim we need three facts:

* By (2.18) and (2.19), $\Psi$ is concave on $[0, m_K]$ (and negative on $(m_K, d)$, and null thereafter),

* We have $\int_0^{m_K} L_K(t)dt = 1 > \int_0^{m_K} L_M(t)dt$, so that there must exist some $t$ such that $L_K(t) > L_M(t)$ in $(0, m_K)$, so that $\Psi$ must be positive somewhere on $(0, m_K)$
• In the extremities, we have $\Psi(0) = 0$ and $\Psi(m_K)$ can be:

- either positive, and since $\Psi(t) < 0$ on $(m_K, d)$ the claim holds for $t^* = m_K$,

- or $\Psi(m_K) < 0$, in which case, by concavity, there is a single cancellation time $t^*$ on $(0, m_K)$, and $\Psi(t)$ is non-positive on $(t^*, d]$.

This proves the claim.

Since the map $x \mapsto x^{1/(d-1)}$ is non-decreasing (on $\mathbb{R}^+$), the claim is also valid for the map $\Phi(t) := L_K(t) - L_M(t)$.

Therefore the map $t \mapsto B_K(t) - B_M(t)$, whose derivative is $\Phi(t)$, is non-decreasing on $[0, t^*)$ and non-increasing on $[t^*, d]$. Since $B_K(0) - B_M(0) = B_K(d) - B_M(d) = 0$, these variations properties imply that $t \mapsto B_K(t) - B_M(t)$ is non-negative on $[0, d]$ (and null after that). $\square$

### 2.1.3 Proof of Theorem 1.7 upper bound

The main idea is to construct a wide trapezoid $T_h$ with a very small height, so that random points inside have small heights. The first base of the trapezoid is $B_1 := F \times \{0\}$ and the second one is $B_2 := (c_h F) \times \{h\}$ for $h > 0$, and $c_h$ a real number (depending on $h$), and the trapezoid $T_h$ is the convex hull of the two bases (and has floor $F$). Since $\mathrm{Vol}_{d-1}(B_2) = c_h^{d-1}$, and since we want $\mathrm{Vol}_d(T_h) = 1$, we set $c_h = (2/h - 1)^{1/(d-1)}$. When $h$ goes to zero, $c_h$ goes to $+\infty$. Take $\alpha > 0$. For $U = (Z, H)$ uniformly taken in $T_h$, $\mathbb{E}(H) \le h$ and then $Q_{T_h}(2) = 1 - 2\mathbb{E}(H)/d \ge 1 - 2h/d \ge 1 - \alpha$, for $h > 0$ small enough.

It remains to show that $Q_K(2) = 1$ is impossible: since $K$ has a non-empty interior, for $U = (Z, H)$ uniform in $K$, $H$ is almost surely positive, and then $\mathbb{E}(H) > 0$.

## 3 2D - considerations.

In the 2D case, we will make a great use of top functions, which are simple concave functions. We focus on convex domains having floor $F := [0, 1] \times \{0\}$, belonging to SubPrism($F$), which prosaically means that they are contained in the rectangle

$$ \mathrm{Rect} := [0, 1] \times [0, 2]. $$

We denote by Conca the set of concave functions $G : [0, 1] \to \mathbb{R}^+$ such that $\int_0^1 G(x) dx = 1$. The set Conca and SubPrism($F$) can be identified by associating with each $K$ its top function (and reciprocally, to a function $G \in$ Conca, the domain below its graph

$$ D_G := \{(x, y) : y \le x\} \cap \mathrm{Rect} $$

(see if needed the beginning of Section 2.1.1). Since it is more convenient to work with functions in the sequel, we will use the notation

$$ Q_n^G := Q_{D_G}(n). $$

### 3.1 General decomposition formula for $Q_K(n)$

The main message of this section is that there exists a formula that allows to compute $Q_n^G$: the formula is recursive and uses some elements $Q_n^H$ where $H$ are defined using a part of the graph of $G$. Let us introduce the material devoted to the expression of this decomposition.
First, take $t \in [0, 1]$ and consider the two segments $S_1 := [(0,0), (t, G(t))]$ and $S_2 := [(t, G(t)), (1,0)]$. Consider $L(t)$, the points that are in $D_G$ and above the segment $S_1$; similarly, let $R(t)$ those that are in $D_G$ and above $S_2$. Formally,

$$L(t) = \{(x, y) : 0 \le x \le t, y \ge \frac{x}{t}G(t)\} \cap D_G, \qquad (3.22)$$

$$R(t) = \{(x, y) : t \le x \le 1, y \ge G(t) + \frac{x-t}{1-t}(G(1) - G(t))\} \cap D_G. \qquad (3.23)$$

In what follows, we will sometimes write $L^G(t)$ and $R^G(t)$ to clarify the dependence of these sets on $G$. For any $E \subset \mathbb{R}^2$, we will also use the notation $|E|$ standing for the Lebesgue measure of the set $E$; hence

$$|L(t)| + |R(t)| = 1 - G(t)/2.$$

In the sequel, we perform a decomposition at any $t \in [0, 1]$ along $L(t)$ and $R(t)$ and deal with the uniform

<figure><img src="image_6.png" /><figcaption>Figure 4: Introduction of the domain $L(t)$ and $R(t)$</figcaption></figure>

distribution in these domains which have respective floors $S_1$ and $S_2$.

We would rather work with the fixed floor $F = [0,1] \times \{0\}$ and functions in Conca, therefore we map these domains at a suitable position using affine maps (that preserve both convexity and the uniform distribution). Note that for $t \in (0, 1)$ one can find:

* a unique affine map $\Phi^{L,t}$ with positive determinant, that sends $S_1$ on $F$ and $L(t)$ inside Rect, preserves vertical lines, and such that $|\Phi^{L,t}(L(t))| = 1$; let $N(L(t))$ be the top function of $\Phi^{L,t}(L(t))$ (the prefix "N" stands for normalized)

* a unique affine map $\Phi^{R,t}$ with positive determinant, sending $S_2$ on $F$ and $R(t)$ in Rect, preserving vertical lines, and such that $|\Phi^{R,t}(R(t))| = 1$. Let $N(R(t))$ be the top function of $\Phi^{R,t}(R(t))$.

The sequence $(Q_n^G, n \ge 0)$ obeys the following decomposition

**Theorem 3.1.** For any function $G \in \text{Conca}$, any $n \ge 0$,

$$Q_n^G = \sum_{m=0}^{n-1} \binom{n-1}{m} \int_0^1 G(t) Q_m^{NL(t)} Q_{n-1-m}^{NR(t)} |L(t)|^m |R(t)|^{n-1-m} dt. \qquad (3.24)$$

**Remark 3.2.** Theorem 3.1 allows to express $Q^G(n)$ in terms of $Q^{NR(t)}(m)$ and $Q^{NL(t)}(n-1-m)$ where $NR(t)$ and $NL(t)$ are relatively simple functions of the initial function $G$. In order to derive a close formula for $Q^G(n)$, it is morally necessary that the class of domains $NL(t)$ and $NR(t)$ appearing in the decomposition remains under control. This is the case if the class of functions is stable by composition by affine functions (as constant, linear, quadratic functions are).
*Proof.* The proof is inspired by the comb formula in [18].

Consider the family of maps $G_\lambda : x \mapsto (1-\lambda)G(x)$. For $\lambda = 0$ the graph of $G_\lambda$ is the same as that of $G$. As $\lambda$ moves from 0 to 1, the family of domains $D^{G_\lambda}$ decreases for the inclusion partial order, and eventually, at time $\lambda = 1$, becomes flat. Let $U_1, \dots, U_n$ be iid uniform in $D^G$. Let $\lambda^* = \sup\{\lambda > 0 : U_1, \dots, U_n \in D^{G_\lambda}\}$.

<figure><img src="image_7.png" /><figcaption>Figure 5: Families of map $G^\lambda$ (decreasing as $\lambda$ grows). Representation of the images $NL(t)$ and $NR(t)$ of $L(t)$ and $R(t)$ by the affine maps that transport the "floor segments" of both domains onto $F$, that send vertical lines onto vertical lines, and that vertically rescale the domain so that $|NR(t)| = |NL(t)| = 1$.</figcaption></figure>

Almost surely $\lambda^* \in (0, 1)$, and for $\lambda^* = \lambda$ there is a single (uniform index) $i^* \in [1, n]$ such that $U_{i^*} \in \partial D^{G_\lambda}$. Now, the set of points $U_1, \dots, U_n$ together with $(0,0)$ and $(1,0)$ are in convex position if and only if none of them lies in the interior of the triangle with vertices $(0,0)$, $(1,0)$, $U_{i^*}$, and if the points of $[1, n] \setminus \{i^*\}$ can be partitioned in two parts $P_1, P_2$ such that all the points with indices in $P_1$ lie in $L^{G_\lambda}(t)$ and are in convex position together with the extremities of $S_1$ (computed in $D^{G_\lambda}$), and all those of $P_2$ lie in $R^{G_\lambda}(t)$ and are in convex position together with the extremities of $S_2$ (computed in $D^{G_\lambda}$).

We claim that, for $U_i = (X_i, Y_i)$

$$Q_n^G = \sum_{k=1}^n \sum_{m=0}^{n-1} \int_0^1 \int_0^1 \binom{n-1}{m} |L(t)|^m |R(t)|^{n-m-1} Q_m^{NL(t)} Q_{n-m-1}^{NR(t)} \mathbb{P}(i^* = k, X_{i^*} \in dt) d\mathbb{P}_{\lambda^*}(\lambda) \quad (3.25)$$

where $\mathbb{P}_{\lambda^*}$ stands for the law of $\lambda^*$. This formula is valid because:

- when one finds $U_{i^*}$ in $\partial G_{\lambda^*}$, the other points are uniformly distributed in $D^{G_{\lambda^*}}$. We search for the probability that these points are in convex position (together with $\lambda$) and avoid the triangle $(0,0), (1,0), U_{i^*}$. By applying the affine map $(x, y) \to (x, 1/\lambda)$ that sends $D^{G_\lambda}$ over $D^G$, we are back to the original problem with $n-1$ points that must fall partly in $L(t)$, and partly in $R(t)$: this is why even if we have contracted $D^G$ into $D^{G_\lambda}$, the initial function $G$ still plays a role in the definition of the left and right domains $L(t)$ and $R(t)$.

Now, we claim that

$$\mathbb{P}(i^* = k, X_{i^*} \in dt) = (1/n)G(t)dt. \quad (3.26)$$

Indeed, in order to sample $U_i = (X_i, Y_i)$ uniformly at random in $D^G$, one can proceed as follows: sample $X_i$ according to $G$ and then set $Y_i = G(X_i)V_i$ where $V_i$ is uniform on $[0, 1]$ (all the $V_i$ are independent, and
independent of the $X_i$). In this representation, $i^*$ is the index $i$ of the largest $V_i$, and the remaining $X_i$ are still independent and have distribution $G$. Injecting (3.26) in Formula (3.25), allows to see that the sum over $k$ can be simplified, and the integral over $\lambda$ can be factorized, and gives 1. $\square$

## 3.2 Exact computation for some particular shapes

### 3.2.1 The bi-pointed triangular case

Consider the triangle $\Delta$ defined by the concave map of area 1, $G(t) = 2t$ (on $[0, 1]$), with floor $F = [0, 1] \times \{0\}$. Let

$$t_n = Q_{\Delta}(n)$$

be the corresponding bi-pointed probability. Let us recover the following theorem due to Bárány, Rote, Steiger and Zhang [4] (see also Gusakova and Thäle [13] for recent results on the number of points on the convex hull of $\{U_1, \dots, U_n\} \cup \{(0, 1), (0, 0)\}$ where the $U_i$ are iid uniform random points $n$ in the triangle).

**Theorem 3.3.** For all $n \ge 1$, we have

$$t_n = \frac{2^n}{n!(n+1)!} \qquad (3.27)$$

The eight first terms of this sequence (starting with $t_0$) are

$$1, 1, \frac{1}{3}, \frac{1}{18}, \frac{1}{180}, \frac{1}{2700}, \frac{1}{56700}, \frac{1}{1587600}, \frac{1}{57153600} \qquad (3.28)$$

Recall that for all $a, b > 0$,

$$\beta(a, b) := \int_{0}^{1} t^{a-1}(1-t)^{b-1} dt = \Gamma(a)\Gamma(b)/\Gamma(a+b). \qquad (3.29)$$

*Proof.* For each $t$, $L(t)$ is flat and $R(t)$ is triangular and has area $|R(t)| = 1-t$. We then have

$$t_n = \int_0^1 (2t)(1-t)^{n-1} t_{n-1} \binom{n-1}{n-1} dt = 2\beta(2, n) t_{n-1}$$

and using (3.29), we conclude (since $\beta(2, n) = 1/(n(n+1)))$. $\square$

### 3.2.2 The bi-pointed square case

In a square $S = [0, 1]^2$ with floor $F = [0, 1] \times \{0\}$, set $q_n = Q_S(n)$.

**Proposition 3.4.** For all $n \ge 0$ we have

$$q_n = \frac{1}{n!(n+1)!} \binom{2n}{n}. \qquad (3.30)$$

The eight first terms are

$$1, 1, \frac{1}{2}, \frac{5}{36}, \frac{7}{288}, \frac{7}{2400}, \frac{11}{43200}, \frac{143}{8467200}, \frac{143}{162570240}$$
*Proof.* We have $G(t) = 1$ for all $t \in [0, 1]$, $R(t)$ is a triangle with area $t/2$, $L(t)$ a triangle with area $(1-t)/2$. Still using (3.29), we have:

$$q_n = \sum_{k=0}^{n-1} \binom{n-1}{k} t_k t_{n-1-k} \int_0^1 (t/2)^k ((1-t)/2)^{(n-k-1)} dt \quad (3.31)$$

$$= \sum_{k=0}^{n-1} \binom{n-1}{k} \frac{1}{(k+1)!(n-k)!} \frac{1}{n!} = \frac{1}{n!(n+1)!} \sum_{k=0}^{n-1} \binom{n-1}{k} \binom{n+1}{n-k}; \quad (3.32)$$

to conclude, observe that this last sum is $\binom{2n}{n}$ because one can partition the set of subsets of size $n$ of $\{1, \dots, 2n\}$, with respect to their numbers $k$ of elements belonging to $\{0, \dots, n-1\}$ (and then, $k$ ranges from 0 to $n-1$). $\square$

### 3.2.3 The bi-pointed parabola case

Consider the parabolic function $G: x \mapsto 6x(1-x)$; its area is 1, and of course, $G$ is in Conca. Let $p_n = Q_n^G$ be the probability that $n$ iid point taken uniformly in $D$, together with (0,0) and (1,0) are in convex position.

**Theorem 3.5.** For all $n \ge 0$ we have

$$p_n = \frac{12^{n+1}}{6(2n+2)!} \quad (3.33)$$

*Proof.* In this case,

$$|L(t)| = t^3 \text{ and } |R(t)| = (1-t)^3.$$

Moreover, $L(t)$ (resp. $R(t)$) can be sent on $D^G$ using an invertible affine map, so that $NL(t) = NR(t) = G$. We then have by Theorem 3.1, $p_0 = 1$, and for $n \ge 1$,

$$p_n = \sum_{k=0}^{n-1} \binom{n-1}{k} p_k p_{n-1-k} \int_0^1 G(t) t^{3k} (1-t)^{3(n-k-1)} dt. \quad (3.34)$$

Replacing $G(t)$ by $6t(1-t)$ (inside this integral) and using (3.29), we get

$$p_n = \sum_{k=0}^{n-1} \binom{n-1}{k} p_k p_{n-1-k} \times 6 \frac{(1+3k)!(1+3(n-k-1))!}{(3n)!} \quad (3.35)$$

To prove that the sequence $(p_n)$ given in (3.33) satisfies this formula, it suffices to assume that it does so for all $k < n$ (for some $n \ge 1$), and to prove that it does so for $n$ as well. To do this, replace in the rhs $p_k$ by $12^{k+1}/(6(2k+2)!)$ and a quick inspection shows that this is sufficient to establish that

$$\left(\frac{3n+1}{n-1}\right) \frac{4}{(3n+1)} = \sum_{k=0}^{n-1} \binom{2+3k}{k} \frac{2}{3k+2} \binom{2+3(n-k-1)}{(n-k-1)} \frac{2}{2+3(n-k-1)} \quad (3.36)$$

(we have slightly modified the formula to highlight the expressions that we discuss now). Now, we claim that this formula is just a consequence of the fact that the number of paths with step +2 or -1, of length $3N+k$, that hits $-k$ (with $k > 0$) for the first time at time $3N+k$ is counted by $\binom{3N+k}{N} \frac{k}{3N+k}$ so that the rhs of (3.36) counts the number of paths hitting position -4 for the first time at time $3n+1$ while the rhs decomposes the convolution of pairs of paths, each of them hitting -2 at their ends, and having a cumulative number of steps equal to $3n+1$. Hence, the formula is valid for $n$, and by induction, for all $n$. $\square$
### 3.3 Barany's analogues in the 2d-floor case

It is a well-known result, due to Bárany[1], that in any convex set $K$ with non-empty interior, the convex hull of $n$ iid uniform points taken in $K$, conditioned to be in convex position, converges for the Hausdorff distance $d_H$ in probability to a (unique) deterministic convex domain $\text{Dom}(K)$ inside $K$. The domain $\text{Dom}(K)$ can be characterized both as the aforementioned limit, or as the only domain among all convex subsets of $K$ realizing the maximum of a quantity called the affine perimeter $AP$. This maximum will be denoted by $AP^*(K)$. However, fixing a floor $[0, 1]$ to $K$ does not affect this property! In fact, we have the following proposition:

**Proposition 3.6.** Consider a convex domain $K \in \text{CCSF}([0, 1])$, and let $U_1, \dots, U_n$ be an $n$-tuple of points with distribution $\cup_K(n)$, conditioned to be in convex position together with $(0, 0), (1, 0)$. There exists a unique set $S \subset K$, with $S \in \text{CCSF}([0, 1])$, such that

$$d_H(\text{CH}({U_1}, \dots, {U_n} \cup [0, 1]), S) \xrightarrow[n]{(\text{proba.})} 0. \qquad (3.37)$$

*Proof.* A segment has an affine perimeter of zero, i.e. for any $K \in \text{CCSF}([0, 1])$, the affine perimeter of $K$ is actually the affine perimeter of its "convex" boundary above $[0, 1]$. Hence, with this property and Bárany's result [1], it is clear that there exists a unique set $S \subset K$, with $S \in \text{CCSF}([0, 1])$, which realizes $AP^*(K) = AP(S)$ and, once more by Bárany's, the convex hull of an $n$-tuple of points with distribution $\cup_K(n)$, conditioned to be in convex position together with $(0, 0), (1, 0)$, converges in probability for the Hausdorff distance to the "convex" boundary of $S$ above $[0, 1]$. □

If $K$ is a polygon, the boundary of $\text{Dom}(K)$ is composed of finitely many parabola arcs. In the fixed floor case, if $\Delta$ is the triangle of vertices $(0, 0), (1, 0), (1/2, 2)$, for $n$ iid uniform points taken in $\Delta$ and conditioned to be in convex position together with $(0, 0), (1, 0)$, the convex hull of these points converges for the Hausdorff distance to the convex set whose boundary is composed of the parabola of equation $t \mapsto -4t^2 + 4t$ and the segment $[0, 1]$. We denote by LS this convex set (standing for "Limit Shape"). This parabola is the only one contained in $\Delta$ whose extremities are tangent to $\Delta$ at $(0, 0)$ and $(0, 1)$. Hence, an immediate corollary of Theorem 3.5 is:

**Corollary 3.7.** Let $U[n]$ be $n$ points with distribution $\cup_{\Delta}(n)$ conditioned to be in convex position together with $(0, 0), (1, 0)$. We denote by $s_n$ the probability that $U[n]$ are in convex position under their limit shape LS. We have

$$s_n = \left(\frac{2}{3}\right)^n \frac{p_n}{t_n} = \frac{2 \cdot 4^n}{n+1} \frac{1}{\binom{2n+2}{n+1}} \xrightarrow{n \to \infty} \frac{\sqrt{\pi}}{2} \frac{1}{\sqrt{n+1}}.$$

*Proof.* It is standard computation combined with $\text{Area}(\text{LS}) = 2/3$. □

Let us give another example: among all convex subsets of LS, LS has the largest affine perimeter, so that the convex hull of an $n$-tuple of points with distribution $\cup_{\text{LS}}(n)$, conditioned to be in convex position together with $(0, 0), (1, 0)$, converges to the boundary of LS.

The domain $\text{Dom}(K)$, and its affine perimeter $AP(\text{Dom}(K)) = AP^*(K)$ appear in another famous result of Bárany[2], which states that

$$n^2 (P_K^{(2)}(n))^{1/n} \xrightarrow{n \to \infty} \frac{e^2}{4} \left( \frac{AP^*(K)}{\text{Area}(K)} \right)^3. \qquad (3.38)$$

But as a direct consequence of this latter formula, this other result still holds in the 2d-floor case!
**Proposition 3.8.** Consider a convex domain $K \in \text{CCSF}([0, 1])$. We have

$$n^2(Q_K(n))^{1/n} \underset{n \to \infty}{\longrightarrow} \frac{e^2}{4} \left( \frac{\text{AP}(\text{Dom}(K))}{\text{Area}(K)} \right)^3. \qquad (3.39)$$

## 3.4 Optimisation of $Q_K(2)$ in 2D: a second simple proof

In 2D, for all $K \in \text{SubPrism}(F)$ for $F = [0, 1] \times \{0\}$, by Theorem 1.5, we have

$$t_2 \le Q_K(2) \le q_2. \qquad (3.40)$$

In this section we give an independent proof of the lower bound (we have no simpler proof than the general upper bound given in Section 2.1.1). Again, we will use the set Conca to parameterize the elements in SubPrism($F$). We want to prove that $Q_2^G \ge t_2$, and since $t_2$ corresponds to $Q_2^H$ with $H: t \mapsto 2t$, it suffices to prove that

$$Q_2^G = \int_0^1 G(t)(1-G(t)/2)dt \ge \int_0^1 2t(1-2t/2)dt = t_2 \quad \text{for } G \in \text{Conca}$$

which is then equivalent to

$$\int_0^1 G^2(t)dt \le \int_0^1 (2t)^2dt, \quad \text{for } G \in \text{Conca}. \qquad (3.41)$$

We may (and we will) assume that $G$ is different from the map $t \mapsto 2t$.

First, we claim that (3.41) holds if $G$ is in Conca$^\dagger$, the subset of Conca constituted by non-decreasing functions. Indeed, in this case, there exists a unique $t^* \in (0, 1)$ solution to $G(t^*) = 2t^*$. Since both $G$ and $t \mapsto 2t$ integrate to 1 on $[0, 1]$

$$\int_0^{t^*} (G(x)-2x)dx = \int_{t^*}^1 (2x-G(x))dx.$$

Now since $t \mapsto G(t) + 2t$ is non-decreasing, and $G(t) - 2t$ is non-negative on $[0, t^*]$, negative on $[t^*, 1]$, by setting $v^* = G(t^*) + 2t^*$, we get

$$\int_0^1 G^2(t) - (2t)^2 dt = \int_0^{t^*} (G(t)-2t)(G(t)+2t)dt + \int_{t^*}^1 (G(t)-2t)(G(t)+2t)dt \qquad (3.42)$$

$$\le v^* \int_0^{t^*} (G(t)-2t)dt + v^* \int_{t^*}^1 (G(t)-2t)dt = 0. \qquad (3.43)$$

Which implies the claim.

Since (3.41) holds in Conca$^\dagger$, by symmetry it holds also for non-increasing concave functions. A concave function reaches its maximum on an interval $[t_\star, t^*]$. On $[0, t_\star]$, the map $G$ is non-decreasing and on $[t^*, 1]$, non-increasing. At least one of this intervals is not reduced to a point. Now, write

$$\int_0^1 G(t)^2 dt = \int_0^{t^*} G^2(t) dt + \int_{t^*}^1 G^2(t) dt.$$

By a change of variable, $\int_0^{t^*} G(t)^2 dt = t^* \int_0^1 G(t^*u)^2 du$ and $\int_{t^*}^1 G^2(t) dt = (1-t^*) \int_0^1 G^2(t^* + (1-t^*)u)$. Since both $u \to G(t^*u)^2$ and $u \to G^2(t^* + (1-t^*)u)$ are monotonous elements of Conca, by the claim,

$$\int_0^1 G(t)^2 dt \ge t^* \int_0^1 (2t)^2 dt + (1-t^*) \int_0^1 (2t)^2 dt = \int_0^1 (2t)^2 dt,$$

and this ends the proof.
### 3.5 Optimisation of $Q_K(2)$ in 2D: a third simple proof

We present here a completely different argument, which we tried to extend to any dimension, but failed to do so. The idea is first to prove that every function $G \in \text{Conca}$ can be written as a weighted sums of mountains. More exactly, if $G$ is piecewise linear (and accounts for a polygon whose boundary contains the segment $[0, 1]$), it can be written as

$$G = \sum_{i \in I} \lambda_{s_i} M_{s_i} \qquad (3.44)$$

where $I$ is a finite set, $M_{s_i}$ is the unit mountains with appex $(s_i, 2)$, and $\sum_{i \in I} \lambda_{s_i} = 1$. In general

$$G = \int_{0}^{1} \lambda_{s} M_{s} d\mu(s) \qquad (3.45)$$

where $\mu$ is a positive Borelian measure with total mass 1 on $[0, 1]$: a probability distribution. With this result in hand, since $x \to x^2$ is convex, and since $\int_{0}^{1} M_{s}^{2}(x) dx = \int_{0}^{1} (2t)^{2} dt$ (because $Q_M(2)$ does not depend on the position of the apex of the mountains), by convexity of the map $G \to \int_{0}^{1} G(x)^{2} dx$,

$$\int_{0}^{1} G^{2}(x) dx \leq \int_{0}^{1} \lambda_{s} \mu(ds) \int_{0}^{1} (2t)^{2} dt = \int_{0}^{1} (2t)^{2} dt.$$

The simplest way to get (3.45) is to prove (3.44) and conclude by density. The simplest conceptual proof is as follows: set $G := \sum_{i \in I} \lambda_{s_i} M_{s_i}$ for some positive ($\lambda_i$) and distinct ($s_i$). It is easy to see that, for all $a \in (0, 1)$, $G'(a^+) - G'(a^-)$ is zero except at $a \in \{s_i, i \in I\}$, and for an element $s$ of this set,

$$G'(s^+) - G'(s^-) = \lambda_s(M_{s^+}' - M_{s^-}') = \lambda_s(-2/(1-s) - 2/s), \qquad (3.46)$$

so that the slope difference at $s$ in $G$ and the weight of the mountains $M_s$ characterize each other. If there is a vertex $s = 1$ (the case $s = 0$ is treated similarly), then $M_1(t) = 2t$, so that finally, $G(1) = 2\lambda_1$, and again the value of $G$ at 1 (resp. 0) and $\lambda_1$ (resp. $\lambda_0$) characterizes each other. These considerations allow to see that any piecewise linear element $G$ of Conca can be written as a sum of weighted mountains, and the $\lambda_{s_i}$ are positive (which is visible in (3.46), because a single mountain explains the negative jump of the derivative of $G$ at $s$).

This very last point is the core of what makes this argument difficult to generalize to higher dimensions. Indeed, adding multidimensional mountains can generate additional extreme points that are difficult to handle, and there is nothing as simple as this "difference of slope" that characterizes the "weights" of mountains in a polygon.

## 4 Convex sets in 3D with a floor: new results

In 3D, even for the seemingly simplest case as the cube, the tetrahedron with a 2 dimensional floor, we have no formula for $Q_K(n)$ (but $Q_K(2)$ can be computed in these cases). To get an idea on the behavior of $Q_K(n)$, we give here some bounds on this quantity.

### 4.1 A universal lower bound of $Q_K(n)$ for mountains in 3D

**Theorem 4.1.** Let $d = 3$. Take any floor $F$ (compact convex subset of $\mathbb{R}^2 \times \{0\}$ with area 1), any unit mountain $M$ with floor $F$. For all $n \geq 0$,

$$Q_M(n) \geq Y_n := \frac{2^n}{n!} \prod_{j=1}^{n} \frac{1}{3j-1}.$$
The first terms of the sequence $(Y_n)$, for $n \ge 0$, are the following:

$$1, 1, \frac{1}{5}, \frac{1}{60}, \frac{1}{1320}, \frac{1}{46200}, \frac{1}{2356200}, \frac{1}{164934000}, \frac{1}{15173928000}$$

We will assume all along the proof that the center of mass of $F$ is at $(0,0,0)$.

The idea is as follows: put $U_1, \dots, U_n$ in $M$, and consider the height of the layers containing these points $h_1, \dots, h_n$. The Layer$_h$ is a copy of Layer$_0$, rescaled, and placed at level $h$. We have

$$\text{Layer}_M(h) = (1 - h/3)F + (0, 0, h)$$

$$\text{Layer}_P(h) = F + (0, 0, h).$$

The layers are copies of $F$. If a point $z$ (random or not) falls in a layer, we may associate a factor $a(z)$, that we will call $F$-radius, which measures the smallest copy of $F$ (still with center of mass 0) which would contain it: for $z \in \text{Layer}(h)$:

$$a(z) = \min\{a : a \ge 0, z \in (aF) + (0, 0, h)\}.$$

The knowledge of $(a(z), h)$ is not sufficient to recover $z$, since given these numbers, we only know that $z$ belongs to the boundary of $(a(z)F) + (0, 0, h)$.

<figure><img src="image_8.png" /><figcaption>Figure 6: An illustration of Lemma 4.2: on the left, the points $(U_i)$ are in convex position above the polyg- onal floor. Each horizontal slice of the mountain containing a point is a dilatation $F'$ of $F$ (with center of mass above that of $F$), and itself contains a second dilatation $F''$ of $F$ (with center of mass above that of $F$) having this point on its boundary (these are the represented by gray lines). The scale factor needed to go from $F$ to $F''$ is $a$. On the right figure are represented the 2D points $(h_i, a_i)$ of the successive heights and factors of the points, from the bottom to the top. If the 2D points $(h_i, a_i)$ are in convex position (together with $(0, 1)$), then the $(U_i)$, together with the floor, are in convex position.</figcaption></figure>

**Lemma 4.2.** For some valid floor $F$, consider a sequence of points such $z_1, \dots, z_n$ in $F \times [0,3]$ such that $0 \le \pi_3(z_1) \le \dots \le \pi_3(z_n)$ (their third coordinates are non-decreasing). If the points

$$(1,0), (a(z_1), \pi_3(z_1)), \dots, (a(z_n), \pi_3(z_n))$$
are in convex position in the 2D-rectangle $[0, 1] \times [0, 3]$, then the $z_i$ together with the floor $F$, are in convex position in $\mathbb{R}^3$.

*Proof.* The point $(1, 0)$ somehow encodes the same information as $(a(z_0), \pi_3(z_0))$ for $z_0$ a point in $\partial F$. This is just a consequence of the fact that under the hypothesis, the points in $(\partial a(z_i)F + (0, 0, \pi_i(z_i)))$ are not in the convex hull of the other partial layers $a(z_j)F + (0, 0, \pi_3(z_j))$. □

Pick $U_1, \dots, U_n$ iid and uniform in $M$ or in $P$, and let us get to (4.1)

**Comparison with "2D-problems".** Consider the densities

$$g_1(x, y) = 2x \quad \text{on } [0, 1] \times [0, 1], \qquad (4.47)$$

$$g_2(x, y) = 2x \mathbb{1}_{x \le (1-y/3)} \quad \text{on } [0, 1] \times [0, 3]. \qquad (4.48)$$

■ Denote by $\beta_1(n)$ the probability that $(1, 0), (X_1, Y_1), \dots, (X_n, Y_n)$ are in convex position in $[0, 1] \times [0, 1]$, where the $(X_i, Y_i)$ are iid and have density $g_1$.

■ And similarly let $\beta_2(n)$ be the probability that $(1, 0), (X_1, Y_1), \dots, (X_n, Y_n)$ are in convex position in $[0, 1] \times [0, 1]$, where the $(X_i, Y_i)$ are iid and have density $g_2$.

**Lemma 4.3.** For all $n \ge 0$,

$$Q_P(n) \ge \beta_1(n),$$

$$Q_M(n) \ge \beta_2(n).$$

**Remark 4.4.** It is likely that this lower bound is not so good for small values of $n$, but better for large ones. As $n \to \infty$, if there exists a limit shape for the $(U_i)$ conditioned to be in convex position, then one can expect that the points $(a(U_j), \pi_3(U_j))$ would be close to being in convex position in 2D.

**Remark 4.5.** Similar lower bounds can be computed in higher dimensions (just replace $\mathbb{P}(a(U) \le a) = a^{d-1}$ in dimension $d$).

In dimension 3, if $K$ is neither a pyramid, nor an prism, but satisfies $\text{Layer}_K(t) = s(t) \cdot F$ (with vertically aligned center of gravity), and $t \mapsto s(t)$ is convex, then again, a comparison with a 2D problem can be designed (in this case, $\pi_3$ has density proportional to $s^2$, and $a(U)$, conditionally on $\pi_3(U) = h$, has density $2x/s(h)^2$ on $[0, s(h)]$).

*Proof of Lemma 4.3.* Taking into account Lemma 4.2, it suffices to describe the joint laws of $(a(U_i), \pi_3(U_i))$ for uniform point $U_i$, in the two cases of interest.

■ In the prism case, $\pi_3(U_i)$ is uniform on $[0, 1]$ and independent of $a(U_i)$. Now, conditional on $U \in \text{Layer}_P(h)$, $U$ is uniform on this layer, which is isomorphic to $F$. To compute the law of $a(U)$, we may work directly on $F$: for $a \in [0, 1]$, $\mathbb{P}(a(U) \le a) = \mathbb{P}(U \in aF) = a^2$, and then the density of $(a(U), \pi_3(U))$ is indeed $g_1$.

■ In the mountain case, $\pi_3(U_i)$ has density $(1 - y/3)^2$ on $[0, 3]$, since this is the height density, already discussed several times before. Now, given that $U$ is in $\text{Layer}_M(t)$, it is again uniform in this layer, which is isomorphic to $(1 - y/3)F$, which has $F$-radius $(1 - y/3)$, and then $a(U)$ will be smaller than this value. We have $\mathbb{P}(a(U) \le a | U \in \text{Layer}_M(t)) = a^2/((1 - y/3)^2) \mathbb{1}_{a \le 1 - y/3}$ so that finally, $\mathbb{P}((a(U), U) \in (dx, dy)) = \frac{2a}{(1 - y/3)^2} (1 - y/3)^2 \mathbb{1}_{x \le 1 - y/3} dx dy = g_2(x, y) dx dy$ as announced. □
<figure><img src="image_9.png" /><figcaption>Figure 7: On this representation, one sees that when the point $(a, h)$ with the smallest height $h$ is found, the other points, to be in convex position, must be in the colored zone. The density of the points would require a third dimension to be drawn, but the probability of finding a given point $U_j$ at $(a, h)$ is $2a da dh$.</figcaption></figure>

*Proof of Theorem 4.1.* We will use Lemma 4.3 and establish that $\beta_2(n)$ satisfies the formula announced for $(Y_n)$.

Let $n$ points $U_1, \cdots, U_n$ with distribution $g_2$ in the triangle $\triangle$ with vertices $(0,0), (1,0), (0,3)$ as represented on Fig. 7. Consider $V = (X, H)$ the $U_i$ with the smallest height. The points $(U_i)$ together with $(1,0)$ are in convex position iff all the $U_i$ (except $V$) are in the colored zone represented in Fig. 7, and, with $V$, are in convex position. The weight of the colored zone for $g_2$ is

$$W(a, h) = \int_{h}^{\frac{h}{1-a}} \int_{0}^{1-\frac{(1-a)}{h}} 2x dx dy = \frac{a^3 h}{3(1-a)}.$$

We claim then that

$$\beta_n = \int_0^3 \int_0^{1-h/3} 2anW(a,h)^{n-1}\beta_{n-1}dadh \quad (4.49)$$

$$= \beta_{n-1} \frac{2}{n(3n-1)} = \frac{2^n}{n!} \prod_{j=1}^{n} \frac{1}{3j-1}. \quad (4.50)$$

To finish the proof, we need to explain the following facts: the factor $n$ comes from the fact that any point can be at position $(a, h)$, the factor $W(a, h)^{n-1}$ accounts for the presence probability of all other points in the colored zone, and $\beta_{n-1}$ accounts for the probability that these points together with $V$ are in convex position. In order to prove that this last quantity is $\beta_{n-1}$, we need to remark the following: let us rescale the colored region by applying the linear map

$$\Phi : (x, y) \rightarrow \left( \frac{x}{a}, 3 \frac{1-a}{ah} (y-h) \right)$$

which bijectively maps the colored region onto the initial $\triangle$, and maps vertical lines onto vertical lines. If $U$ is taken under the density $g_2$, and conditioned to be in the colored region, then $\Phi(U)$ has density $g_2$ on $\triangle$ (since this is the only density null on the axis $x = 0$, and linear over $\triangle$, no computation is needed to make this deduction). $\square$

**Remark 4.6.** In order to obtain a similar lower bound as Theorem 4.1 for $Q_P(n)$ the Prism $P = F \times [0, 1]$ case (in the 3D case), we would need to compute $(\beta_1(n), n \ge 0)$, but we were not able to succeed to do so.
## 4.2 Bound in the tetrahedron case

Consider a tetrahedron T with vertices

$$A = (0, 0, 0), B = (1, 0, 0), C = (0, 1, 0), D = (0, 0, 6),$$

and floor $F = CH(A, B, C)$. The value of $Q_T(n)$ does not depend on the side lengths of the tetrahedron (as long as T is taken non trivial), but note that here the floor area is 1/2: the simplicity of the floor will help to get a tractable formula in the sequel. Note that for this reason, "the apex" of T, seen as a mountain, is D and has a height of 6.

The aim of this section is to prove the two following theorems 4.7 and 4.8, that gives two (non trivial) sequences ($\ell_n$) and ($u_n$) such that

$$\ell_n \le Q_T(n) \le u_n, \text{ for } n \ge 0. \qquad (4.51)$$

### 4.2.1 Computation of a upper-bound.

**Theorem 4.7.** For any $n$, we have $Q_T(n) \le u_n$, where ($u_n$) satisfies the following recursion: $u_0 = 1$, and for $n \ge 1$,

$$u_n = \frac{6}{(n+2)(n+1)n} \sum_{k=0}^{n-1} u_k u_{n-1-k}, \qquad (4.52)$$

(so that, in particular $u_1 = Q_T(1) = 1$, $u_2 = Q_T(2) = 1/2$). The first terms from $u_0$ to $u_9$ are:

$$\left[ 1, 1, \frac{1}{2}, \frac{1}{5}, \frac{7}{100}, \frac{79}{3500}, \frac{337}{49000}, \frac{2069}{1029000}, \frac{7033}{12348000} \right]$$

*Proof.* Let us call top of T, the triangle BCD. We define a floor to top projection, $\pi_t: ABC \to BCD$ parallel to the normal to the floor. Hence, for $q = (x, y, 0)$,

$$\pi_t(q) := \pi_t(x, y, 0) = (x, y, h(x, y)),$$

where $h(x, y) = 6(1 - (x + y))$ is the height of the top, above $q$.

Consider now $T_q$ the tetrahedron with vertices $A, C, D, \pi_t(q)$.

The vertical plane incident to $A, D, q, \pi_t(q)$ intersects the segment $(B, C)$ at the point

$$p = \left( \frac{x}{x+y}, \frac{y}{x+y}, 0 \right),$$

and this plane cuts the initial tetrahedron in two parts. In one of the two half space, one finds the tetrahedron $T_1(q) = A, \pi_t(q), B, D$, and in the other side $T_2(q) = A, \pi_t(q), C, D$. We have

$$\mathrm{Vol}_2(ABC) = \frac{1}{2}, \quad \mathrm{Vol}_2(ABp) = \frac{y}{2(x+y)}, \quad \mathrm{Vol}_2(ACq) = \frac{x}{2(x+y)}.$$

Hence

$$\mathrm{Vol}_3(ADBp) = \frac{y}{x+y}, \quad \mathrm{Vol}_3(ADCp) = \frac{x}{x+y},$$

and then

$$\mathrm{Vol}_3(ABp\pi_t(q)) = yh(x, y)/(6(x+y)), \quad \mathrm{Vol}_3(ABp\pi_t(q)) = xh(x, y)/(6(x+y)).$$
<figure><img src="image_10.png" /><figcaption>Figure 8: Representation of $q$, and $\pi_t(q)$. The plane incident to $A, D, q, \pi_t(q)$ cuts the initial tetrahedron in two parts.</figcaption></figure>

Finally set

$$V_1(x, y) := \mathrm{Vol}_3(T_1(q)) = \mathrm{Vol}_3(ADBp) - \mathrm{Vol}_3(ABp\pi_t(q)) = \frac{y}{x+y} - y\frac{(1-(x+y))}{x+y} = y$$

$$V_2(x, y) := \mathrm{Vol}_3(T_2(q)) = \mathrm{Vol}_3(ADCp) - \mathrm{Vol}_3(ABp\pi_t(q)) = \frac{x}{x+y} - x\frac{(1-(x+y))}{x+y} = x$$

The way of reasoning from here is very similar to that which led to "the comb formulas" in [18]. Now, consider the coordinates of the $U_i = (X_i, Y_i, Z_i)$ for the independent uniform random points taken in $T$. Conditional on $(X_i, Y_i)$, $Z_i$ being uniform on $[0, h(X_i, Y_i)]$ can be written as $Z_i = V_i h(X_i, Y_i)$ with $V_i$ uniform on $[0, 1]$, independent of $X_i, Y_i$. Now, consider $i^*$ the index $i$ of the maximal $V_i$. Conditional on $(i^*, V_{i^*})$, the other $V_i$ are uniform on $[0, V_{i^*}]$ (and independent). In other words, the other variables $U_i$ are iid uniform below the plane $(x, y, h(x, y)V_{i^*})$ while $U_{i^*}$ is on that plane.

From here we can deduce that

$$Q_T(n) := Q'_T(1, n-1) = \mathbb{P}(\{U_0, \dots, U_{n-1}\} \subset \partial\mathrm{CH}(F \cup \{U_0, \dots, U_{n-1}\}))$$

where in this new question, a point $U_0$ is placed at position $(X, Y, h(X, Y))$ on the surface of the top triangle, where the density of the variable $(X, Y)$ being $h(x, y)$ (the reason is that the position $((X_i, Y_i), 1 \le i \le n)$ are independent of the $V_i$ and then, can even be sampled after them (the notation $(1, n-1)$ is here to help to remember that there are indeed $n-1$ uniform points plus one additional special point on the top triangle). Hence, to compute $Q'_T(1, n-1)$ we place $U_0$ as said, and $U_1, \dots, U_{n-1}$ inside $T$ uniformly at random, independently from $U_0$. Conditionally on $U_0 = (x, y, h(x, y))$ (which is $\pi_t(q)$ in the previous discussion), consider the subsets of the indices $J_1$ and $J_2$ of the $U_i$ belonging to $T_1(q)$ and $T_2(q)$. If the points $U_0, U_1, \dots, U_{n-1} \in \partial\mathrm{CH}(F \cup \{U_0, \dots, U_{n-1}\})$, then $J_1$ and $J_2$ must form a partition of $\{1, \dots, n-1\}$. In particular, we must have

$$\{U_i, i \in J_1\} \in \partial\mathrm{CH}(\{U_i, i \in J_1\} \cup \{A, B, \pi_t(q)\}), \quad (4.53)$$

$$\{U_i, i \in J_2\} \in \partial\mathrm{CH}(\{U_i, i \in J_2\} \cup \{A, C, \pi_t(q)\}) \quad (4.54)$$

so that, we are back in the initial floor problem settings. We then deduce that

$$Q_T(n) = Q'_T(1, n-1) \le \int_{(x,y) \in ABC} \sum_{k=0}^{n-1} \binom{n-1}{k} h(x, y) \mathrm{Vol}(T_1)^k \mathrm{Vol}(T_2)^{n-k-1} Q_T(k) Q_T(n-k-1) dx dy.$$
The sign "≤" comes from the fact that the union over $(J_1, J_2)$ of the events (4.53) contains positions of points that are not globally in convex position. Observe that

$$
\begin{align*}
\alpha(n, k) &= \binom{n-1}{k} \int_{(x,y) \in ABC} V_1(x, y)^k V_2(x, y)^{n-1-k} h(x, y) \,dx\,dy \\
&= \binom{n-1}{k} \int_{\substack{x+y \le 1 \\ x,y \ge 0}} y^k x^{n-1-k} 6(1-(x+y)) \,dx\,dy
\end{align*}
$$

Using again (3.29),

$$
D[k, j] := \int_{x=0}^{1} x^{k} \int_{y=0}^{1-x} y^{j} dy dx = \int_{x=0}^{1} x^{k} (1-x)^{j+1} / (j+1) dx = \frac{k! j!}{(k+j+2)!}
$$

and then

$$
\alpha[n, k] = 6 \binom{n-1}{k} (D[k, n-1-k] - D[k, n-k] - D[k+1, n-1-k]) = 6 \frac{(n-1)!}{(n+2)!}
$$

In fine, putting all together, $Q_T(n) \le \sum_{k=0}^{n-1} \frac{6(n-1)!}{(n+2)!} Q_T(k)Q_T(n-k)$ from what the result follows. $\square$

4.2.2 Lower bound

**Theorem 4.8.** Let ($\ell_n, n \ge 0$) be the sequence defined by $\ell_0 = 1$, for

$$
\ell_n = 6 \frac{(n-1)! n!}{(2n+1)!} \sum_{k=0}^{n-1} \ell_k \ell_{n-1-k}, \quad \text{for } n \ge 1, \qquad (4.55)
$$

then $P_n \ge \ell_n$ for all $n$.

The first terms of the sequence ($\ell_n$), for $n$ from 0 to 6 are

$$
\left[ 1, 1, \frac{1}{5}, \frac{1}{50}, \frac{11}{10500}, \frac{431}{12127500}, \frac{2371}{2801452500} \right].
$$

This bound is better than the general bound given in Theorem 4.1.

*Proof.* We proceed in the beginning as in the proof of Theorem 4.7 until the addition of the point $U_0$, and again use that $Q_T(n) = Q'_T(1, n-1)$.

Consider $B'C'$ the segment obtained as the intersection of the top triangle $BCD$ with the line parallel
to $BC$ containing $\pi_t(q)$, oriented as in Figure 8.

Now, take the indices $J_1$ and $J_2$ of the $U_i$ (with $1 \le i \le n-1$), such that $i \in J_1 \iff U_i \in T'_1 := AB\pi_t(q)B'$
and $i \in J_2 \iff U_i \in T'_2 := AC\pi_t(q)C'$.

We claim that if $J_1$ and $J_2$ forms a partition of $\{1, \cdots, n-1\}$ and if

$$
\{U_i, i \in J_1\} \subset \mathrm{CH}(\{U_i, i \in J_1\} \cup AB\pi_t(q))
$$

$$
\{U_i, i \in J_2\} \subset \mathrm{CH}(\{U_i, i \in J_2\} \cup AC\pi_t(q))
$$

then, the points $U_0, \dots, U_{n-1} \in \mathrm{CH}(\{U_0, \dots, U_{n-1}\} \cup \mathrm{ABC})$. The reason is that the plane $AB'C'$ is therefore a
supporting plane of the $\mathrm{CH}(\{U_0, \dots, U_{n-1}\} \cup \{A, B, C\})$ and indeed, allows to separate in two independent
parts as claimed, the convexity verification.
Conditional on $U_0 = \pi_t(q) = (x, y, h(x, y))$, $B' = (x, 0, h(x, y))$ and $C' = (0, y, h(x, y))$ we get (using the determinant formula for the computation of the volume),

$$V_1'(x, y) := \mathrm{Vol}(T_1') = y(1 - (x + y)), \qquad (4.56)$$

$$V_2'(x, y) := \mathrm{Vol}(T_2') = x(1 - (x + y)). \qquad (4.57)$$

We then have that a lower bound is given by

$$\ell_n = \sum_{k=0}^{n-1} \ell_k \ell_{n-k} g(n, k)$$

with

$$g(n, k) := \binom{n-1}{k} \int_{ABC} V_1'^k(x, y) V_2'^{n-1-k}(x, y) h(x, y) dxdy \\ = 6 \binom{n-1}{k} \int_{ABC} y^k x^{n-1-k} (1 - (x + y))^n dxdy$$

Set $t = x + y$, and since $x + y \le 1$ we get by expanding $y^k = \sum_{k_1=0}^k \binom{k}{k_1} t^{k_1} (-x)^{k-k_1}$

$$g(n, k) := 6 \binom{n-1}{k} \iint_{0 \le x \le t \le 1} \sum_{k_1=0}^{k} \binom{k}{k_1} (-1)^{k-k_1} t^{k_1} x^{n-1-k_1} (1-t)^n dx dt \\ = 6 \binom{n-1}{k} \int_{0 \le t \le 1} \sum_{k_1=0}^{k} \binom{k}{k_1} (-1)^{k-k_1} \frac{1}{n-k_1} t^n (1-t)^n dt \\ = 6 \binom{n-1}{k} \frac{(n!)^2}{(2n+1)!} \underbrace{\sum_{k_1=0}^{k} \binom{k}{k_1} (-1)^{k-k_1} \frac{1}{n-k_1}}_{S_n}$$

we claim that this last sum $S_n$ equals $(n \binom{n-1}{k})^{-1}$ so that we get $g(n, k) := 6n!(n-1)/(2n+1)!$ in the end, which is the theorem statement.

To prove the claim, set $\psi(x) := \sum_{k_1=0}^k \binom{k}{k_1} (-1)^{k-k_1} \frac{x^{n-k_1}}{n-k_1}$ and observe that

$$\psi'(x) = \sum_{k_1=0}^{k} \binom{k}{k_1} (-1)^{k-k_1} x^{(n-1)-k_1} = x^{n-1}(-1+1/x)^k = x^{n-1-k}(1-x)^k.$$

Since $\psi$ is the primitive of $\psi'$ which is null at zero, we have $S_n = \psi(1) = \int_0^1 \psi'(x) dx = \int_0^1 x^{n-1-k}(1-x)^k dx$, so that with (3.29), $S_n = (n \binom{n-1}{k})^{-1}$. $\square$

## Acknowledgements

The authors were partially supported by the ANR projects CartesEtPlus (ANR-23-CE48-0018) and 3DMaps (ANR-20-CE48-0018).
References

[1] I. Bárány. Affine perimeter and limit shape. *Journal für die reine und angewandte Mathematik*, 484:71–84, 1997. 16

[2] I. Bárány. Sylvester's question: The probability that n points are in convex position. *The Annals of Probability*, 27(4):2020–2034, 1999. 5, 6, 16

[3] I. Bárány and M. Reitzner. On the variance of random polytopes. *Adv. Math.*, 225(4):1986–2001, 2010. 8

[4] I. Bárány, G. Rote, W. Steiger, and C.-H. Zhang. A central limit theorem for convex chains in the square. *Discrete & Computational Geometry*, 23:35–50, 01 2000. 5, 6, 14

[5] W. Blaschke. Über affine geometrie xi: Lösung des "vierpunktproblems" von sylvester aus der theorie der geometrischen wahrscheinlichkeiten. *Leipziger Berichte*, 69:436–453, 1917. 1

[6] C. Buchta. On a conjecture of r. e. miles about the convex hull of random points. *Monatshefte für Mathematik*, 102:91–102, 1986. 6

[7] C. Buchta. The exact distribution of the number of vertices of a random convex chain. *Mathematika*, 53(2):247–254, 2006. 5, 6

[8] C. Buchta and M. Reitzner. The convex hull of random points in a tetrahedron: solution of Blaschke's problem and more general results. *J. Reine Angew. Math.*, 536:1–29, 2001. 6

[9] P. Calka and T. Schreiber. Large deviation probabilities for the number of vertices of random polytopes in the ball. *Adv. in Appl. Probab.*, 38(1):47–58, 2006. 7

[10] B. Efron. The convex hull of a random set of points. *Biometrika*, 52(3/4):331–343, 1965. 3

[11] P. Groeneboom. Limit theorems for convex hulls. *Probab. Theory Related Fields*, 79(3):327–368, 1988. 7

[12] A. Gusakova, M. Reitzner, and C. Thäle. Variance expansion and Berry-Esseen bound for the number of vertices of a random polygon in a polygon. *Ann. H. Lebesgue*, 6:875–906, 2023. 7

[13] A. Gusakova and C. Thäle. On random convex chains, orthogonal polynomials, PF sequences and probabilistic limit theorems. *Mathematika*, 67(2):434–446, 2021. 14

[14] B. Hostinsky. *Sur les probabilites geometriques*. Publ. Fac. Sci. Univ. Brno., 1925. 6

[15] J. F. C. Kingman. Random secants of a convex body. *Journal of Applied Probability*, 6(3):660–672, 1969. 6, 7

[16] S. N. Majumdar, A. Comtet, and J. Randon-Furling. Random convex hulls and extreme value statistics. *J. Stat. Phys.*, 138(6):955–1009, 2010. 8

[17] J.-F. Marckert. The probability that n random points in a disk are in convex position. *Brazilian Journal of Probability and Statistics*, 31(2):320–337, 2017. 5, 6, 7
[18] J.-F. Marckert and S. Rahmani. Around Sylvester's question in the plane. *Mathematika*, 67(4):860–884, Aug. 2021. 4, 13, 23

[19] R. E. Miles. Isotropic random simplices. *Advances in Applied Probability*, 3(2):353–382, 1971. 6

[20] L. Morin. Probability that *n* points are in convex position in a general convex polygon: Asymptotic results, 2024. 5, 6

[21] L. Morin. Probability that *n* points are in convex position in a regular κ-gon: Asymptotic results, 2024. 5, 6

[22] R. E. Pfiefer. The historical development of j. j. sylvester's four point problem. *Mathematics Magazine*, 62(5):309–317, 1989. 1

[23] M. Reitzner. The combinatorial structure of random polytopes. *Adv. Math.*, 191(1):178–208, 2005. 8

[24] A. Rényi and R. Sulanke. über die konvexe Hülle von *n* zufällig gewählten Punkten. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2:75–84, 1963. 7

[25] R. Schneider. *Convex bodies: the Brunn-Minkowski theory*, volume 44 of *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, 1993. 10

[26] J. J. Sylvester. Problem 1491. *The educational Times*, 1864. 1

[27] P. Valtr. Probability that *n* random points are in convex position. *Discrete and computational geometry*, 13(3-4):637–643, 1995. 4, 6

[28] P. Valtr. The probability that *n* random points in a triangle are in convex position. *Combinatorica*, 16(4):567–573, 1996. 4, 6

[29] V. H. Vu. Sharp concentration of random polytopes. *Geom. Funct. Anal.*, 15(6):1284–1318, 2005. 7
# Contents

<table><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>Introduction and main results</td><td>1</td></tr><tr><td>1.1</td><td>Related results in 2D</td><td>4</td></tr><tr><td>1.2</td><td>Bounds and universal bounds in dimension 3</td><td>6</td></tr><tr><td>1.3</td><td>Motivation</td><td>6</td></tr><tr><td>1.4</td><td>Related results about the convex hull of random points</td><td>7</td></tr><tr><td>2</td><td>Optimization of Q<sub>K</sub>(2) in the multidimensional case</td><td>8</td></tr><tr><td>2.1</td><td>SubPrism case: proof of Theorem 1.5</td><td>8</td></tr><tr><td>2.1.1</td><td>Proofs of Theorem 1.5: upperbound</td><td>8</td></tr><tr><td>2.1.2</td><td>Proof of Theorem 1.5 and of Theorem 1.7 lowerbound</td><td>9</td></tr><tr><td>2.1.3</td><td>Proof of Theorem 1.7 upper bound</td><td>11</td></tr><tr><td>3</td><td>2D considerations.</td><td>11</td></tr><tr><td>3.1</td><td>General decomposition formula for Q<sub>K</sub>(n)</td><td>11</td></tr><tr><td>3.2</td><td>Exact computation for some particular shapes</td><td>14</td></tr><tr><td>3.2.1</td><td>The bi-pointed triangular case</td><td>14</td></tr><tr><td>3.2.2</td><td>The bi-pointed square case</td><td>14</td></tr><tr><td>3.2.3</td><td>The bi-pointed parabola case</td><td>15</td></tr><tr><td>3.3</td><td>Barany's analogues in the 2d-floor case</td><td>16</td></tr><tr><td>3.4</td><td>Optimisation of Q<sub>K</sub>(2) in 2D: a second simple proof.</td><td>17</td></tr><tr><td>3.5</td><td>Optimisation of Q<sub>K</sub>(2) in 2D: a third simple proof</td><td>18</td></tr><tr><td>4</td><td>Convex sets in 3D with a floor: new results</td><td>18</td></tr><tr><td>4.1</td><td>A universal lower bound of Q<sub>K</sub>(n) for mountains in 3D</td><td>18</td></tr><tr><td>4.2</td><td>Bound in the tetrahedron case</td><td>22</td></tr><tr><td>4.2.1</td><td>Computation of a upper-bound.</td><td>22</td></tr><tr><td>4.2.2</td><td>Lower bound</td><td>24</td></tr></tbody></table>