On Tightness of the Figiel-Lindenstrauss-Milman Inequality

Tomer Milo · 2025

Read On Tightness of the Figiel-Lindenstrauss-Milman Inequality by Tomer Milo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13571.txt.

Introduction

Tomer Milo gives a short and elementary proof of the Figiel-Lindenstrauss-Milman inequality, a key result in the combinatorial theory of polytopes. In the classic route, it comes as a corollary of a version of Dvoretzky theorem due to Milman. Milo derives more general versions of the result and discusses its tightness, an aspect where much remains unknown.

Catalog record

CREATORTomer Milo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE11 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-13571

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Tightness of the Figiel-Lindenstrauss-Milman Inequality Tomer Milo Abstract This note aims to explore the tightness of the classical Figiel-Lindenstrauss-Milman inequality, which states that there exists some constant c > 0 c>0 such that for any dimension n n and any symmetric polytope P ⊂ ℝ n P\subset\mathbb{R}^{n} : log ⁡ | V | ⋅ log ⁡ | ℱ | ≥ c ​ n \log|V|\cdot\log|\mathcal{F}|\geq cn , where V V and ℱ \mathcal{F} denote the sets of vertices and facets of P P , respectively. We show that this inequality is asymptotically tight in almost all possible cases, except for a special case which was previously studied by Barvinok. The Figiel-Lindenstrauss-Milman (FLM) inequality, originally proved in [ 2 ] (see also [ 4 ] for a short and elementary proof), states the following: Theorem 1 . There exists an absolute constant c>0 such that for every n\in\mathbb{N} and for every convex polytope P\subset\mathbb{R}^{n} which is symmetric about the origin (that is, P=-P ) we have: \log|V|\cdot\log|\mathcal{F}|\geq cn Where V and \mathcal{F} are the sets of vertices ( 0 -dimensional) and facets ( (n-1) -dimensional facets) of P , respectively. Moreover, the same estimate holds for a general polytope P satisfying B_{2}^{n}\subset P\subset\sqrt{n}B_{2}^{n} , where B_{2}^{n} is the Euclidean unit ball in \mathbb{R}^{n} . The aim of this note is to explore how tight this inequality is. As a starting point, we observe that for the cube P=B_{\infty}^{n}:=[-1,1]^{n} we have |V|=2^{n} and |\mathcal{F}|=2n and so \log|V|\cdot\log|\mathcal{F}|\sim n\log n (here and throughout, \sim means ‘equivalent up to absolute constants’). The paper is organized as follows: first, we show that in some dimensions we can construct polytopes P_{n}\subset\mathbb{R}^{n} such that \log|V_{n}|\sim\log|\mathcal{F}_{n}|\sim\sqrt{n} and in particular \log|V_{n}|\cdot\log|\mathcal{F}_{n}|\sim n . Here V_{n} and \mathcal{F}_{n} denote the sets of vertices and facets of P_{n} , respectively. We then use this construction to produce other constructions which show that Theorem 1 is tight for almost all possible choices of the sizes of |V_{n}| and |\mathcal{F}_{n}| , complementing a result of Barvinok (see Theorem 3 below) which shows that there are certain cases in which Theorem 1 is in fact not tight. 1 Preliminaries and notations We call a subset P\subset\mathbb{R}^{n} a polytope if it is the convex hull of finitely many points and has a non-empty interior. We denote by V_{P} and \mathcal{F}_{P} the sets of vertices ( 0 -dimensional faces) and facets ( (n-1) -dimensional faces) respectively, and often just write V and \mathcal{F} when the polytope which we refer to is clear from the context. When we have a sequence of polytopes P_{n}\subset\mathbb{R}^{n} we will also often write V_{n} instead of V_{P_{n}} , etc. For two quantities A and B , which may depend on the dimension, a polytope, and other parameters, we say that A\lesssim B if there exists some absolute constant c>0 so that A<cB . We write A\sim B if A\lesssim B and B\lesssim A . For a polytope P\subset\mathbb{R}^{n} , we denote by P^{\circ}:=\{x\in\mathbb{R}^{n}:\max_{y\in P}\langle x,y\rangle\leq 1\} the dual polytope of P (this is indeed a polytope whenever 0\in{\rm int}(P) ). It is easy to verify that the dual operation switches between the numbers of vertices and facets of a polytope; that is, |V_{P^{\circ}}|=|\mathcal{F}_{P}| and |\mathcal{F}_{P^{\circ}}|=|V_{P}| , and that duality is an involution: P^{\circ\circ}=P . We will often use the following elementary facts: given an orthogonal decomposition \mathbb{R}^{n+k}=\mathbb{R}^{n}\bigoplus\mathbb{R}^{k} and polytopes P\subset\mathbb{R}^{n} and Q\subset\mathbb{R}^{k} , then for the polytope P\times Q\subset\mathbb{R}^{n+k}=\mathbb{R}^{n}\bigoplus\mathbb{R}^{k} , we have |V_{P\times Q}|=|V_{P}||V_{Q}| and |\mathcal{F}_{P\times Q}|=|\mathcal{F}_{P}|+|\mathcal{F}_{Q}| . Finally, it is elementary to verify that (P\times Q)^{\circ}={\rm conv}(P^{\circ},Q^{\circ}) , where the duals P^{\circ} and Q^{\circ} are computed in the respective subspaces \mathbb{R}^{n} and \mathbb{R}^{k} of \mathbb{R}^{n+k} . All logarithms are to base 2 . 2 The constructions We begin by constructing symmetric polytopes P_{n}\subset\mathbb{R}^{2^{n}} such that \log|V_{n}|\cdot\log|\mathcal{F}_{n}|\sim 2^{n} . Actually, we will have \log|V_{n}|\sim\log|\mathcal{F}_{n}|\sim 2^{\frac{n}{2}} . This will show that Theorem 1 is generally asymptotically tight (up to a constant). Proposition 2 . For any dimension n\in\mathbb{N} there exists a polytope P_{n}\subset\mathbb{R}^{2^{n}} such that \log|V_{n}|\sim\log|\mathcal{F}_{n}|\sim 2^{\frac{n}{2}} . So, writing N=2^{n} , we have: P_{n}\subset\mathbb{R}^{N} and \log|V_{n}|\cdot\log|\mathcal{F}_{n}|\sim N . Proof. We take Cartesian products and convex hulls iteratively to obtain a certain Hanner polytope P_{n} , starting with P_{0}=[-1,1]\subset\mathbb{R} , as follows: Assuming P_{n}\subset\mathbb{R}^{2^{n}} is defined, we define P_{n+1}\subset\mathbb{R}^{2^{n+1}}=\mathbb{R}^{2^{n}}\bigoplus\mathbb{R}^{2^{n}} as P_{n+1}=\begin{cases}{\rm conv}(P_{n},P_{n}),\>n\>even\\ P_{n}\times P_{n},\>n\>odd\\ \end{cases} Clearly P_{n} is centrally symmetric for all n , and |V_{n+1}|=\begin{cases}2|V_{n}|,\>n\>even\\ |V_{n}|^{2},\>n\>odd\\ \end{cases} and by duality, |\mathcal{F}_{n+1}|=\begin{cases}2|\mathcal{F}_{n}|,\>n\>odd\\ |\mathcal{F}_{n}|^{2},\>n\>even\\ \end{cases} It is now obvious that we have the following asymptotics for P_{n} : \log|V_{n}|\sim\log|\mathcal{F}_{n}|\sim 2^{\frac{n}{2}}. which is what we wanted to prove. ∎ Remark. One can use the above construction to construct, for any dimension N , a polytope P_{N}\subset\mathbb{R}^{N} such that \log|V_{N}|\sim\log|\mathcal{F}_{N}|\sim\sqrt{N} . This shows that Theorem 1 can’t even be strengthened for some special sequence of dimensions. Indeed, we may write N as N=\sum_{i\in I}2^{r_{i}} for some index set I\subset[n] and some natural numbers r_{1}>..>r_{|I|} , where r_{1}=n=\lfloor\log N\rfloor . Letting P_{N}=P_{1}\times...\times P_{|I|}\subset\mathbb{R}^{N}, we have \log|V_{N}|=\sum_{i\in I}2^{\frac{r_{i}}{2}}\sim 2^{\frac{\log N}{2}}=\sqrt{N} , and similarly, \log|\mathcal{F}_{N}|\sim\sqrt{N} as well. Our next goal is to check whether there are special cases for which Theorem 1 is actually not tight. In [ 3 ] , Barvinok provided an answer in the case where the number of facets is linear in n : Theorem 3 . For any \alpha>0 there exists \gamma>0 such that the following holds: for any dimension n and any centrally symmetric polytope P\subset\mathbb{R}^{n} , if \mathcal{|}{\mathcal{F}|}\leq\alpha n then |V|\geq e^{\gamma n} . The same result holds when one assumes that B_{2}^{n}\subset P\subset\sqrt{n}B_{2}^{n} instead of the central-symmetry assumption. In words: linearly many facets implies exponentially many vertices, in the dimension n , and vice versa by duality, which means that Theorem 1 is not always tight. We now prove that other than this particular case, Theorem 1 is (almost) always tight: Proposition 4 . Let f(n)\to_{n\to\infty}\infty be some arbitrary sequence of integers such that f(n)<\sqrt{n} . There exists polytopes P_{N}\subset\mathbb{R}^{N} where N=N(n)\to_{n\to\infty}\infty is another sequence such that: |V_{N}|\sim 2^{\frac{cN}{f(N)}}\>\>and\>\>|\mathcal{F}_{N}|\sim N\frac{2^{c^{\prime}f(N)}}{f(N)^{2}} Where c,c^{\prime}>0 are absolute constants. In particular, \log|V_{N}|\cdot\log|\mathcal{F}_{N}|\sim N\left(1+\frac{\log N}{f(N)}\right). (1) Remark. Choosing f(N)=\log N gives polytopes P_{N}\subset\mathbb{R}^{N} with \log|\mathcal{F}_{N}|\sim\log N and \log|V_{N}|\sim\frac{N}{\log N} , showing that Barvinok’s theorem 3 cannot be extended to the polynomial case. In fact, we now see that Theorem 1 is tight, up to a constant, for almost all possible choices of sizes of |V_{N}| and |\mathcal{F}_{N}| , in the following sense: whenever f(N) has at least a logarithmic type growth (that is, there exists some {\varepsilon}>0 such that f(N)>{\varepsilon}\log N ), we have \log|V_{N}|\cdot\log|\mathcal{F}_{N}|\sim N in (1). Noting that f(N)={\varepsilon}\log N corresponds to |\mathcal{F}_{N}|\sim\frac{N^{1+c^{\prime}{\varepsilon}}}{{\varepsilon}^{2}\log^{2}N} , we can conclude that whenever a sequence a_{n} has a type of growth of at least n^{1+{\varepsilon}} for some {\varepsilon}>0 (and also \log(a_{n})<\sqrt{n} ) one can generate polytopes P_{N}\subset\mathbb{R}^{N} for which \log|\mathcal{F}_{N}|\sim\log a_{N} and \log|V_{N}|\sim\frac{N}{\log a_{N}} , by writing a_{N}=N\frac{2^{f(N)}}{cf(N)^{2}} and inverting the relation to find the appropriate f to apply Proposition 4 to (note that f(n)\sim\log a_{n} ). This settles the question of tightness of Theorem 1 , except for the regime of ‘between linear and polynomial’ - see section 3 for a discussion. Proof of Proposition 4 . Let P_{n}\subset\mathbb{R}^{2^{n}} be the polytopes constructed in Proposition 2 . Let N be given by n=2\lfloor\log f(N)\rfloor (here we

Read the complete text