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
| CREATOR | Tomer Milo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 11 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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