Abstract
Let K be a centrally symmetric spherical and simplicial polytope, whose vertices form a \((4n)^{-1}\)-net in the unit sphere in \({\mathbb R}^n\). We prove a uniform lower bound on the norms of all hyperplane projections \(P:X\rightarrow X\), where X is the n-dimensional normed space with the unit ball K. The estimate is given in terms of the determinant function of vertices and faces of K. In particular, if \(N\ge n^{4n}\) and \(K={{\,\textrm{conv}\,}}{\{\pm x_1,\pm x_2,\dots ,\pm x_N\}}\), where \(x_1,x_2,\dots ,x_N\) are independent random points distributed uniformly in the unit sphere, then every hyperplane projection \(P:X \rightarrow X\) satisfies an inequality \(\Vert P\Vert _X\ge 1+c_nN^{-(2n^2+4n+6)}\) (for some explicit constant \(c_n\)), with the probability at least \(1-3/N\).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let X be a real normed space of dimension at least 2. A linear and continuous mapping \(P:X \rightarrow X\) is called a projection, if it satisfies the equation \(P^2=P\). By a hyperplane projection we shall mean a projection with the image of codimension 1.
Projection is a very old concept in mathematics and a basic notion of the approximation theory, as it provides an approximation of the identity operator on a subspace, by a linear operator defined on the whole space. For this reason, one often seeks for a projection with the smallest possible operator norm, as the smaller norm yields a better approximation. Such a projection P is called a norm-minimal projection from X onto the image of P.
Norm-minimal projection were studied by a lot of different authors in a great variety of contexts (see for example [1,2,3, 8,9,10, 15, 16, 19,20,21]). The so-called projection constants were studied most extensively. Projection constants play a profound role in the functional analysis and the local theory of Banach spaces, as they are deeply connected with some other important numerical invariants of Banach spaces. We refer to Chapter 8 in a monograph [26] for a broader picture on the theory of the projection constants. In terms of the norm, the best possible situation happens, when there exists a projection of norm 1 onto a given subspace. In this case, we say that a subspace is 1-complemented in the given space.
By the Hahn–Banach theorem, every 1-dimensional subspace is 1-complemented. For this reason, we shall call a projection non-trivial, if its image has dimension at least 2, and it is different from the whole space. In a Hilbert space, every subspace is 1-complemented by means of the orthogonal projection. Conversely, it is well known that if every subspace of a given Banach space X, satisfying \(\dim X\ge 3\), is 1-complemented, then X is isometric to a Hilbert space (see for example [17]). Still, most of the classical spaces posses some 1-complemented subspace of dimension at least 2, even if they are not necessarily Hilbert. For example, in the classical \(\ell _p^n\) space, a hyperplane Y is 1-complemented if and only if Y is the kernel of a functional, which represented as a vector in \({\mathbb R}^n\), has at most two coordinates that are different from zero (see [1]). Study of 1-complemented subspaces of Banach spaces has a long history and there is a large volume of published research on this topic (see [24]).
Bosznay and Garay proved in [6] that, in the context of a normed spaces of given dimension \(n\ge 3\), this is, in fact, a very rare instance, to posses some non-trivial projection with the norm 1. It turns out, that the set of n-dimensional normed spaces, for which every non-trivial projection \(P:X \rightarrow X\) has norm strictly larger than 1, is open and dense in the set of all n-dimensional normed spaces. This somewhat reminds of the well-known fact, that the set of continuous and nowhere differentiable functions forms an open and dense subset of the set of continuous functions. Moreover, this naturally raises a question of establishing some explicit, uniform lower bound on the norms of projections of a given space, which is strictly greater than 1. Thinking more globally, it is natural to define the constant \(\rho _n\) as the largest positive number, for which there exists an n-dimensional normed space X, such that every non-trivial projection \(P:X\rightarrow X\) satisfies \(\Vert P\Vert _X\ge 1+\rho _n\). The fact, that \(\rho _n\) is positive, follows immediately from the result of Bosznay and Garay and a standard compactness argument. By a result of [9], on every two-dimensional subspace there is always a projection with the norm at most 4/3, so obviously we have \(\rho _n\le 1/3\) for every \(n\ge 3\).
It seems that no positive lower bounds on \(\rho _n\) are known. This may be related to the fact, that lower bounds for the norms of projections were studied mostly in the case of specific subspaces, rather than uniformly. Nevertheless, some remarkable results related to the uniform lower bounds were obtained. Gluskin in [12] and Szarek in [25] used norms generated by random polytopes to establish such lower bounds, but only for projections with the rank in a specific range. Later, a similar construction was provided also in [22]. All of these results give estimates of the following type: there exists an n-dimensional normed space X, such that for every projection \(P:X \rightarrow X\) with the rank m in an interval of the form \([\alpha n,\beta n]\) (where \(0<\alpha<\beta <1\) are constants), we have \(\Vert P\Vert _X\ge C\sqrt{m}\) (for some constant C depending on \(\alpha \) and \(\beta \)). Asymptotically speaking, this is best possible up to a constant, as the famous result of Kadec and Snobar (see [16]) yields the inequality \(\Vert P\Vert _X<\sqrt{m}\).
A deeply profound role, that random polytopes play in the modern high-dimensional geometry, has been started with a pioneering previous work of Gluskin in [13], who used them to prove that the asymptotic order of the diameter of the Banach–Mazur compactum is linear. After that, many different important applications of the random objects in the high-dimensional geometry have been established, including the examples above.
It does not seem possible to apply those methods directly to projections with the rank not in the interval of the form \([\alpha n,\beta n]\). In this case, the examples are generally lacking. However, some results were obtained in [18] for the case of hyperplane projections. For each \(n\ge 3\) let us define a constant \(\rho _n^H\) as the largest positive number, for which there exists an n-dimensional normed space X, such that every hyperplane projection \(P:X \rightarrow X\) satisfies \(\Vert P\Vert _X\ge 1+\rho ^H_n\). Obviously, we have \(\rho _n^H\ge \rho _n\) for every \(n\ge 3\). Moreover, by a result of Bohnenblust (see [4]), every hyperplane admits a projection of norm at most \(2-2/n\), and therefore \(\rho ^H_n\le 1-1/n\) for every \(n\ge 3\). In [18] a uniform lower bound on the norms of the hyperplane projections was provided in the case of the space X being a rather general subspace of the \(\ell _{2p}^m\) space (where \(p\ge 2\) is an integer). In consequence, we have
for every \(n\ge 4\). This implies an asymptotic lower bound on \(\rho _n^H\) of the form
for some absolute constant \(C>0\).
The aim of this paper, is to study uniform lower bounds for the norms of hyperplane projections in the setting of the spherical polytopes (by which we mean the convex hulls of points lying on the unit sphere). Our main result gives such an explicit, uniform lower bound for a broad class of normed spaces, with the unit ball being a symmetric spherical, simplicial polytope whose vertices form a \((4n)^{-1}\)-net in the unit sphere. If \(K\subseteq {\mathbb R}^n\) is a convex polytope, then by a term face we shall mean only \((n-1)\)-dimensional face (facet) of K. We will say that face F of K is given by a vector \(f\in {\mathbb S}_n\) (or corresponds to f), if f is a unit vector perpendicular to the affine hyperplane containing F. We recall that a convex polytope is called simplicial, if every face is an \((n-1)\)-dimensional simplex. By \(\Vert \,{\cdot }\,\Vert \) we shall always mean the Euclidean norm in \({\mathbb R}^n\). By \({\mathbb S}_n=\{x\in {\mathbb R}^n:\Vert x\Vert =1\}\) we denote the Euclidean unit sphere in \({\mathbb R}^n\) (not to be confused with the unit sphere in \({\mathbb R}^{n+1}\)). For an n-dimensional normed space X, the norm of X will be denoted by \(\Vert \,{\cdot }\,\Vert _X\) and the same symbol will be used for the operator norm of a projection \(P:X\rightarrow X\). Two faces of K are called non-neighbouring if their intersection is empty. For a given \(\varepsilon >0\), a set \(X\subseteq {\mathbb S}_n\) is called an \(\varepsilon \)-net if for every point \(p\in {\mathbb S}_n\), there exists \(x\in X\) such that \(\Vert x-p\Vert \le \varepsilon \). Throughout the paper, we always assume that \(n\ge 3\) is an integer. Our main result goes as follows.
Theorem 1.1
(general lower bound for the spherical polytopes) Let N be a positive integer and \(\alpha , \beta \) positive real numbers. Suppose that points \(x_1,x_2,\dots ,x_N\in {\mathbb S}_n\) satisfy the following conditions:
-
(i)
Vertices of a convex polytope \(K={{\,\textrm{conv}\,}}{\{\pm x_1,\pm x_2,\dots ,\pm x_N\}}\) form a \((4n)^{-1}\)-net in \({\mathbb S}_n\).
-
(ii)
K is a simplicial polytope.
-
(iii)
For any \(1\le i_1<i_2<\ldots <i_n\le N\) we have \(|{\det {(x_{i_1},x_{i_2},\dots ,x_{i_n})}}|\ge \alpha \).
-
(iv)
For any n pairwise non-neighbouring faces of K, given by the vectors \(f_1,f_2,\dots ,f_n\in {\mathbb S}_n\), we have \(|{\det (f_1,f_2,\dots ,f_n)}|\ge \beta \).
Let X be the n-dimensional real normed space with the unit ball K. Then, every hyperplane projection \(P:X \rightarrow X\) satisfies
where
Informally speaking, the determinant function that appears in the estimate above, could be considered as some kind of a measure of the linear independency of the vertices and facets of K. The probability that a random symmetric polytope, with vertices drawn uniformly and independently in \({\mathbb S}_n\), is simplicial and the determinant function does not vanish on any subset of vertices or pairwise non-neighbouring faces is equal to 1. Thus, if we pick appropriately large number of points at random from the unit sphere, the resulting normed space, has all hyperplane projections with the norm greater than 1 with a high probability. This is clearly expected by the previously mentioned result of Bosznay and Garay. The question of estimating this probability for some explicit, uniform lower bound on the norms of hyperplane projection arises naturally. Points \(x_1,x_2,\dots ,x_N\in {\mathbb S}_n\) will be called random points, if they are distributed independently and uniformly in \({\mathbb S}_n\). In the next result, we provide a uniform lower bound for the norms of hyperplane projections, which holds with a large probability for a random spherical polytope. The result states, that for the symmetric convex hull of \(N\ge n^{4n}\) random points in \({\mathbb S}^n\), the corresponding normed space has all hyperplane projections with norm greater than \(1+c_nN^{-(2n^2+4n+6)}\) (for some specific constant \(c_n\)), with the probability at least \(1-3/N\).
Theorem 1.2
(lower bound for random spherical polytopes) Let \(N\ge n^{4n}\) be a positive integer. Let \(x_1,x_2,\dots ,x_N\in {\mathbb S}_n\) be random points and let \(X=(\mathbb {R}^n,\Vert \,{\cdot }\,\Vert _X)\) be the n-dimensional normed space with the unit ball \(B_X={{\,\textrm{conv}\,}}{\{\pm x_1,\pm x_2,\dots ,\pm x_N\}}\). Then, the probability that every hyperplane projection \(P{:}\,X \rightarrow ~X\) satisfies
where
is at least \(1-3/N\).
We can say that the result above quantifies the original result of Bosznay and Garay (in the hyperplane setting) in two different ways. It gives a uniform lower bound on the norms of projections, but it also estimates the measure of the spherical polytopes with given number of vertices, which satisfy it. In the three-dimensional case, this gives an estimate of \(1+cN^{-36}\) for some explicit constant \(c>0\)—see Remark 4.1. We note that, even if we work with random polytopes, our methods are different than those from previously mentioned papers [12, 22, 25]. This may stem from the fact that the hyperplane case seems to be rather dissimilar to the case of projections with the rank depending linearly on n. In particular, we do not rely on some more advanced variants of the concentration of measure, but we use only basic probabilistic tools, such as Markov’s inequality. Let us also remark, that we took some care, to keep all constants appearing in our estimates as explicit as possible, but in some instances they were estimated rather crudely, in order to keep the results clearer.
Since we consider polytopes approximating the unit sphere very well, the corresponding norm is close to the Euclidean norm and we are working rather locally around it. Therefore, as the orthogonal projection has norm 1, it is not reasonable to expect that our results will yield an optimal lower bound on the constant \(\rho _n^H\). By taking \(N=n^{4n}\) in Theorem 1.2 we get a lower bound
which is worse than the lower bound (2) obtained in [18]. We also note that the estimate (1) from [18] works only for\(n\ge 4\). Thus, our result gives a first non-trivial bound for the three-dimensional constant \(\rho _3^H=\rho _3\). See Remark 4.2 for some numerical estimate on \(\rho _3\) that can be deduced with our approach. It should be emphasized, that main goal of the paper is to study uniform bounds on the norms of projections in the setting of the spherical polytopes with large number of vertices. The general discussion on \(\rho _n\) and \(\rho _n^H\) was presented for the sake of motivating this line of research. We consider the derived bounds on \(\rho _n^H\), which are likely far from being optimal, only as an interesting by-product of our investigation.
The paper is organized as follows. In Sect. 2 we prove Theorem 1.1. In Sect. 3 we establish Theorem 1.2 by applying Theorem 1.1 in combination with several auxiliary results concerning random polytopes. The paper is concluded in Sect. 4, where some further remarks related to our results, are provided.
2 Proof of the General Lower Bound for the Spherical Polytopes
In this section we prove Theorem 1.1. We start with some simple auxiliary results.
Lemma 2.1
Let N be a positive integer and suppose that a set \(\{x_1,x_2,\dots ,x_N\}\subseteq {\mathbb S}_n\) is an \(\varepsilon \)-net for some \(0<\varepsilon <1\). Then, every face of a convex polytope \(K={{\,\textrm{conv}\,}}{\{x_1,x_2,\dots ,x_N\}}\) has diameter not greater than \(2\varepsilon \) and an inclusion \((1-\varepsilon ){\mathbb S}_n\subseteq K\) holds.
Proof
Let F be any face of K and let x be the center of the spherical cap determined by F. Clearly, x is equidistant to the vertices of F. Let us denote this distance by d. We have \(d\le \varepsilon \). By the triangle inequality, the distance between any two vertices of F is at most \(2d\le 2\varepsilon \), which shows the first claim. For the second claim, let h be the distance between x and the hyperplane containing F. Clearly \(h\le d\le \varepsilon \). Moreover, the hyperplane tangent in x to S is parallel to the hyperplane containing F. Since \((1-h)^{-1}\le (1-\varepsilon )^{-1}\), it is clear that \(S\subseteq (1-\varepsilon )^{-1}K\) and the proof is complete.
\(\square \)
Lemma 2.2
Let \(x_1,x_2,\dots ,x_n\in \mathbb {S}_n\) be such that \(|{\det (x_1,x_2,\dots ,x_n)}|\ge \alpha \) for some \(\alpha >0\). Then, for any \(v\in {\mathbb S}_n\) we have \(\max _{1\le i\le n}|\langle x_i,v\rangle |\ge \alpha /n\).
Proof
Assume on the contrary, that for for some \(v\in {\mathbb S}_n\) and for each \(1\le i\le n\) we have that \(\langle x_i,v\rangle =r_i\in (-\alpha /n,\alpha /n)\). Let \(r=(r_1,r_2,\dots ,r_n)\in {\mathbb R}^n\). Then \(\Vert r\Vert <\sqrt{{n\alpha ^2}/n^2}=\alpha /{\sqrt{n}}\). Hence, from Cramer’s rule and the Hadamard inequality it follows that
In the same way we prove that \(|v_i|<1/{\sqrt{n}}\) for \(2\le i\le n\). Hence
which gives the desired contradiction. \(\square \)
Now we are ready to prove Theorem 1.1.
Proof of Theorem 1.1
We denote by \(\Vert \,{\cdot }\,\Vert _X\) the norm of X and by \(\Vert \,{\cdot }\,\Vert _{X^*}\) the dual norm. By the second assumption and Lemma 2.1, every face of K is an \((n-1)\)-dimensional simplex of a diameter not greater than \(d=(2n)^{-1}\). Moreover, the inclusion \({\mathbb S}_n\subseteq (4n/(4n-1))K\) holds. Let \(Y\subseteq X\) be an arbitrary \((n-1)\)-dimensional subspace. Suppose that \(P:X \rightarrow X\) is a projection with the image Y, that satisfies the inequality \(\Vert P\Vert _X<1+C_n\alpha ^2\beta \). Let us take \(w\in \ker P\) with \(\Vert w\Vert =1\) and suppose that \(Y=\{x\in {\mathbb R}^n:\langle x,v\rangle =0\}\) with \(\Vert v\Vert =1\). Assume that Y has non-empty intersection with the faces \(F_1,\dots ,F_k,-F_1,\dots ,-F_k\) of K, given by the vectors \(f_1,\dots ,f_k,-f_1,\dots ,-f_k\in {\mathbb S}_n\). Let us call a face \(F_i\) a bad face, if there does not exist a vector \(z\in Y\cap F_i\) such that \({{\,\textrm{dist}\,}}(z,{{\,\textrm{bd}\,}}F_i)\ge s\) (the boundary \({{\,\textrm{bd}\,}}F_i\) is considered in the affine hyperplane containing \(F_i\)), where
Otherwise, a face \(F_i\) is called a good face. We shall prove the following claim.
Claim 2.3
If F is a bad face, then there exists a vertex a of F such that \(|\langle a,v\rangle |<\alpha /n\).
Indeed, let \(F={{\,\textrm{conv}\,}}{\{a_1,a_2,\dots ,a_n\}}\) be a bad face. A region
is a simplex, positively homothetic to F (soon, we shall see that \(F'\) is non-empty). As the hyperplane Y does not intersect \(F'\), the simplex \(F'\) lies in one of the open half-spaces determined by Y. Without loss of generality, let us assume that a vertex \(a_1\) of F lies in the opposite (closed) half-space—as Y has a non-empty intersection with F, there are vertices in both closed half-spaces. Let \(f_1\) be the face of F not containing \(a_1\) (thus \(f_1\) has dimension \(n-2\)). Then, it is clear that Y intersects the parallelotope
Let \(a_1'\) be a vertex of \(F'\) corresponding to \(a_1\). Then \(a_1'\in P_1\) and \(\Vert a_1-x\Vert \le \Vert a_1-a_1'\Vert \) for some \(x\in P_1\cap Y\). We shall now prove an upper estimate on the distance \(\Vert a_1-a_1'\Vert \). Let \(0<k<1\) be the homothety ratio of F and \(F'\) and let r be the inradius of F. The homothety center c is the incenter of both F and \(F'\). In particular, \(kr+s=r\), which gives us an equality \(k=(r-s)/r\). Furthermore,
which yields
We shall now establish a lower bound on the inradius r. Let us observe that
but on the other hand,
where h denotes the distance of the hyperplane determined by F to the origin, and \(S_i\) for \(1\le i\le n\) denote the \((n-2)\)-dimensional volumes of the faces of F. Each face of F is an \((n-2)\)-dimensional simplex with the edge length not greater than d. Thus, it is well known that under these constraints, for each \(1\le i\le n\), volume \(S_i\) is not greater than that of an \((n-2)\)-dimensional regular simplex of edge length d, which is equal to
Combining the two previous estimates with an obvious inequality \(h<1\), we get a lower bound
Let us note here, that this shows in particular, that the region \(F'\) is non-empty, as by the above inequality we clearly have \(s<r\). Now, coming back to (3) we obtain
Hence
which proves Claim 2.3. Now, we shall establish a similar claim for the good faces.
Claim 2.4
If F is a good face, given by the vector \(f\in {\mathbb S}_n\), then \(|\langle w,f\rangle |<\beta /n\).
Since F is a good face, there exists a vector \(z\in Y\cap F\), such that \({{\,\textrm{dist}\,}}(z,{{\,\textrm{bd}\,}}F)\ge s\). This means, that a ball B(z, s) with the center z and radius s, intersected with the boundary of K, is an \((n-1)\)-dimensional Euclidean ball contained in F. Let us take any real number \(\lambda \) satisfying \(|\lambda |\le s/5\). Then, we have
Moreover,
By combining two previous estimates we obtain
where the last inequality follows easily from the inequality \(|\lambda |\le s/5\). Finally, we have that
This shows that for \(|\lambda |\le s/5\), the vector \((z+\lambda w)/\Vert z+\lambda w\Vert _X\) belongs to the intersection of a ball B(z, s) with the boundary of K and therefore to the face F. In consequence, we have
where \(\tilde{f}=f/\Vert f\Vert _{X^*}\). Thus
Hence,
By taking \(\lambda =\pm s/5\) and using the fact that \(\Vert \tilde{f}\Vert \ge \Vert f\Vert \), we get
by the definitions of s and \(C_n\). This proves Claim 2.4.
Now, with both claims at our disposal, we can finish the proof of Theorem 1.1. We take any point \(x\in Y\) with \(\Vert x\Vert _X=1\) and any two-dimensional subspace \(V\subseteq Y\) such that \(x\in V\). Let us consider a two-dimensional curve (a broken path), lying in \(V\cap {{\,\textrm{bd}\,}}K\), which connects x and \(-x\). Clearly, its Euclidean length is greater than \(2\Vert x\Vert \ge (4n-1)\Vert x\Vert _X/(2n)=(4n-1)/(2n)\). This means, that we can find points \(p_1,p_2,\dots ,p_{2n-1}\) on this curve such that, for \(i\ne j\) we have
Every point \(p_i\) lies in the boundary of K, and thus in some face of K. Let \(F_i\) be any face of K such that \(p_i\in F_i\). Note for \(i\ne j\), faces \(F_i\) and \(F_j\) are non-neighbouring. Indeed, if \(u\in F_i\cap F_j\), then
which is a contradiction. It is clear, that in the set \(\{F_1,F_2,\dots ,F_{2n-1}\}\) there are at least n bad faces or at least n good faces. If there are n good faces, then by Claim 2.3, we get existence of n vertices \(a_1,a_2,\dots ,a_n\) of K, such that \(|\langle a_i,v\rangle |<\alpha /n\) for any \(1\le i\le n\). This is an immediate contradiction with Lemma 2.2 and the third condition of the theorem. Similarly, if there exist n good faces among \(F_1,F_2,\dots ,F_{2n-1}\), then there are n pairwise non-neighbouring faces of K, given by the vectors \(f_1,f_2,\dots ,f_n\in {\mathbb S}_n\), such that \(|\langle w,f\rangle |<\beta /n\). Again, this contradicts Lemma 2.2 combined with the fourth condition of the theorem. This completes the proof. \(\square \)
3 Random Spherical Polytopes
In this section we derive Theorem 1.2 from Theorem 1.1. In order to do this, we need to establish several probabilistic lemmas. These results are strongly based on the ideas developed by different authors. We shall rephrase or modify them, according to our needs. We start with a straightforward reformulation of the lower bound on the probabilistic measure of the spherical cap, that was given in [5].
Lemma 3.1
Let \(x\in {\mathbb S}_n\) and \(0<r<1\). Then, the probabilistic measure of the spherical cap
is at least
Proof
If \(0<\varphi \le \pi /2\) is such that
then by the first part of [5, Cor. 3.2], it follows that the measure of C(x, r) is at least
However
and hence the claim follows. \(\square \)
In [7] there is an outline of the proof, that for any fixed \(\varepsilon >0\), the probability, that N random points on the unit sphere in \({\mathbb R}^n\) form a \(N^{-1/(n-1)+\varepsilon }\)-net, tends to 1, as \(N\rightarrow \infty \) (see the proof of (1.27) in Appendix A there). In order to obtain more explicit estimate, we give a minor modification of this argument in the following lemma.
Lemma 3.2
Let \(N\ge n^{4n}\) be a positive integer. If \(x_1,x_2,\dots ,x_N\in {\mathbb S}_n\) are random points, then the probability, that these random points do not form a \((4n)^{-1}\)-net in the unit sphere, is less than 1/N.
Proof
It is well known that for any \(\varepsilon >0\), there exists a \(\varepsilon \)-net in the unit sphere of cardinality at least \((1+2/\varepsilon )^n\). In particular, there exists a \((8n)^{-1}\)-net of the cardinality \((16n+1)^n\le (17n)^n\). Hence, let \(z_1,z_2,\dots ,z_{(17n)^n}\) be some fixed \((8n)^{-1}\)-net in the unit sphere. For a fixed \(1\le j\le (17n)^n\), the probability that each point \(x_1,x_2,\dots ,x_N\) is outside the cap \(C(z_j,(8n)^{-1})\), is by Lemma 3.1 at most
Therefore, the probability that at least one of the caps \(C(z_j,(8n)^{-1})\) is empty, is at most
where \(a=8n\sqrt{2}\). Since \(N\ge n^{4n}\) and \(n\ge 3\) we have that
It is easy to check that for \(N\ge n^{4n}\) and \(n\ge 3\) the inequality
is true. Hence, the probability that at least one of the caps \(C(z_j,(8n)^{-1})\) is empty is less than 1/N. It remains to observe, that if each of these caps is non-empty, then the points \(x_i\) form a \((4n)^{-1}\)-net in the unit sphere. This concludes the proof. \(\square \)
The last piece of information, that we need to apply Theorem 1.1, in order to prove Theorem 1.2, is the expected value of the determinant of n random points in \({\mathbb S}_n\). More precisely, we estimate the \((-1/2)\)-moment of the absolute value of the determinant. We use the fact, that the distribution of the random variable \(|{\det (x_1,x_2,\dots ,x_n)}|\), where \(x_i\in {\mathbb S}_n\) are random points, is well known. We will also refer to the following well-known inequalities on the ratio of Gamma functions:
The lower bound appeared in this form in [11] and upper bound in [27].
Lemma 3.3
Let \(M_n\) be the expected value of \(|{\det (x_1,x_2,\dots ,x_n)}|^{-1/2}\), where \(x_i\in {\mathbb S}_n\) for \(1\le i\le n\) are random points. Then, we have \(M_n<e^{n/4}(n-1)\).
Proof
Let us recall that a random variable has a Beta distribution with parameters \(\alpha _1,\alpha _2>0\), if its density is given by
for \(t\in (0,1)\). It turns out that the random variable \(\det (x_1,x_2,\dots ,x_n)^2\) has the distribution \(\prod _{i=1}^{n-1}\beta _{i/2,(n-i)/2}\), where \(\beta _{\alpha _1,\alpha _2}\) has a Beta distribution with parameters \(\alpha _1,\alpha _2\) and the variables in the product are independent (see [14, 23]). The \((-1/4)\)-moment of the Beta variable with parameters \(\alpha _1>1/4\), \(\alpha _2>0\) is equal to
Therefore,
From the inequality (4) we have
Similarly,
for \(2\le i\le n-1\). For \(i=1\), we can check by a direct calculation that
Thus,
Hence, we conclude that
by Stirling’s approximation formula. This finishes the proof. \(\square \)
Finally, we are ready to move to the proof of Theorem 1.2. We will use the following simple upper bound on the binomial coefficient: \(\left( {\begin{array}{c}N\\ n\end{array}}\right) \le (Ne/n)^n\) for \(N\ge n\).
Proof of Theorem 1.2
Let us consider the following probability events:
-
(i)
Points \(x_1,x_2,\dots ,x_N\) do not form a \((4n)^{-1}\)-net in \({\mathbb S}_n\).
-
(ii)
$$\begin{aligned} |{\det (x_{i_1},x_{i_2},\dots ,x_{i_n})}|\le \biggl (\frac{e^{{5n}/2}}{n^{2n-2}}N^{2n+2}\biggr )^{\!-1}\end{aligned}$$
for some indices \(1\le i_1<i_2<\ldots <i_n\le N\).
-
(iii)
There exist pairwise non-neighbouring faces \(F_1,F_2,\dots ,F_n\) of \(B_X\), perpendicular to vectors \(f_i\in {\mathbb S}_n\) (where \(1\le i\le n\)), such that
$$\begin{aligned}|{\det (f_1,f_2,\dots ,f_n)}|\le \biggl ( \frac{e^{2n^2+5n/2}}{n^{2n^2+2n-2}}N^{2n^2+2}\biggr )^{\!-1}.\end{aligned}$$
We shall prove that each of these three events has probability at most 1/N. We can also assume that \(B_X\) is a simplicial polytope, as this happens with the probability 1.
(i) Our claim follows directly from Lemma 3.2.
(ii) We use Lemma 3.3 and Markov’s inequality applied to the random variable \(|{\det (y_1,y_2,\dots ,y_n)}|^{-1/2}\), where \(y_1,y_2,\dots ,y_n\in {\mathbb S}_n\) are random points. For any \(a>0\) we have
which is equivalent to
Using this inequality for \(a=N\left( {\begin{array}{c}N\\ n\end{array}}\right) \), with the union bound for all possible choices of n points from \(x_1,x_2,\dots ,x_N\), along with an estimate \(\left( {\begin{array}{c}N\\ n\end{array}}\right) \le (Ne/n)^n\), we get the desired upper bound of 1/N.
(iii) If \(A\subseteq \{1,2,\dots ,N\}\) is an n-element set, then by \(x_A^{\perp }\in {\mathbb S}_n\) we denote a unit vector perpendicular to the affine hyperplane containing the points \(x_i\) for \(i\in A\) (this hyperplane is determined uniquely with the probability 1). To be more precise, we can define \(x^{\perp }_A\) as the exterior product of \(x_i\) for \(i\in A\). A set of vectors \(\{f_1,f_2,\dots ,f_n\}\subseteq {\mathbb S}_n\), corresponding to a set of n pairwise non-neighbouring faces of \(B_X\), can be represented as \(\{x_{A_1}^{\perp },x_{A_2}^{\perp },\dots ,x_{A_n}^{\perp }\}\) for a certain n-element family \(\{A_1,A_2,\dots ,A_n\}\) of n-element disjoint subsets of the set \(\{1,2,\dots ,N\}\). Let us denote by \(\mathcal {F}\) the collection of all such families. Then, for a given \(c>0\), the probability that there exist pairwise non-neighbouring faces of \(B_X\), given by vectors \(f_1,f_2,\dots ,f_n\in {\mathbb S}_n\), that satisfy \(|{\det (f_1,f_2,\dots ,f_n)}|\le c\) is, by the union bound, at most
where \(\{B_1,B_2,\dots ,B_n\}\in \mathcal F\) is any fixed family (this probability is clearly the same for any family in \(\mathcal F\)). Since the points \(x_i\) are chosen uniformly and independently and the sets \(B_i\) are disjoint, it easily follows that \(\{x_{B_1}^{\perp },x_{B_2}^{\perp },\dots ,x_{B_n}^{\perp }\}\) is a set of n independent random points in \({\mathbb S}_n\), with respect to the uniform distribution. Thus, we can use Markov’s inequality as in (5) for \(a=\#\mathcal F\cdot N\) to get
Using the bound \(\left( {\begin{array}{c}N\\ n\end{array}}\right) \le (Ne/n)^n\) and Stirling’s approximation formula, we can estimate the cardinality of \(\mathcal F\) as follows:
Hence
and in consequence, the probability that there exist pairwise non-neighbouring faces of \(B_X\), \(\{f_1,f_2,\dots ,f_n\}\subseteq {\mathbb S}_n\), satisfying
is at most 1/N.
The result follows now from Theorem 1.1 and easy computation, where
\(\square \)
4 Concluding Remarks
In the following section we present some remarks related to previous results. We start with the three-dimensional setting.
Remark 4.1
In the three-dimensional case, the uniform estimate given in Theorem 1.2 gives us
where \(c=(9/e^3)^{14}\). By taking \(N=3^{12}\) we get a first non-trivial lower bound on \(\rho _3=\rho ^H_3\). Better numerical bound on \(\rho _3\) will be given in the next remark.
Remark 4.2
It is not hard to prove, that in the three-dimensional case, the condition (i) in Theorem 1.1 can be replaced with an assumption, that the volume of K is greater than 4 (here we mean the standard volume in \({\mathbb R}^3\)) and length of every edge of K is less than 1/4. With a help of a computer program, a spherical polytope K, satisfying these conditions was found. Number of vertices of K is equal to 434 and \(\alpha =5.303\cdot 10^{-7}\), \(\beta =1.244\cdot 10^{-7}\). This gives us a better numerical estimate than in Remark 4.1:
It is rather hard to believe, that this estimate could be close to the true value of \(\rho _3\). Still, in the class of spherical polytopes with 434 vertices, it is not necessarily so weak.
It turns out that if the dimension is fixed, the polynomial bound, given in terms of N, can be improved.
Remark 4.3
For the asymptotics with n fixed and \(N\rightarrow \infty \), the estimate given in Theorem 1.2 can be strengthened to \(1+c_{n,\varepsilon }N^{-(n^2+3n+3+\varepsilon )}\) for any \(\varepsilon >0\) and some constant \(c_{n,\varepsilon }\), depending on n and \(\varepsilon \). Indeed, the expected value of a random variable \(|{\det (x_1,x_2,\dots ,x_n)}|^{-1+\varepsilon }\) is finite for every \(\varepsilon >0\). This can be easily deduced from the distribution of a random variable \(\det (x_1,x_2,\dots ,x_n)^2\), given in Lemma 3.3. Thus, we can replace the exponent of \(-2\), in the right hand sides of the inequalities given in the properties (ii) and (iii) in the proof of Theorem 1.2, to the exponent of \(-1-\varepsilon \), albeit with some different constant depending on n and \(\varepsilon \).
Remark 4.4
In Theorem 1.1 it seems to be essential that the vertices of K form a good approximation of the unit sphere (the first condition). Let us consider a convex polytope \(K={{\,\textrm{conv}\,}}{\{\pm e_1,\pm e_2,\dots ,\pm e_n\}}\), where \(e_i\) is the i-th vector from the canonical unit basis of \({\mathbb R}^n\). Thus, the convex polytope K is the unit ball of the \(\ell _1\) norm in \({\mathbb R}^n\). In this case we have:
-
K is a simplicial polytope, that is, the second condition of Theorem 1.1 is satisfied.
-
The third condition is satisfied with \(\alpha =1\).
-
The fourth condition is satisfied with any positive \(\beta \), since it is not possible to choose any n pairwise non-neighbouring faces of K.
Yet, in the \(\ell _1\) norm there are hyperplane projections of norm 1—for example any projection \(P:{\mathbb R}^n\rightarrow {\mathbb R}^n\) of the form
where \(1\le i\le n\). This shows that without the first condition of Theorem 1.1 (or some substitute of it), it is not possible to give a uniform lower bound on the norms of the hyperplane projections in terms of the minimum of the determinant function of vertices and faces.
This also explains, why is it necessary to assume that the number of random points is large enough in Theorem 1.2, that is \(N\ge n^{4n}\). By a standard volume argument, yielding a lower bound on the cardinality of an \(\varepsilon \)-net in the unit sphere, it is not possible to significantly improve the estimate given in Lemma 3.2. Therefore, the presented approach works only for spherical polytopes with a sufficiently large number of vertices.
Remark 4.5
We were interested only in lower bounds on the norms of the hyperplane projections. In the context of random symmetric spherical polytopes with 2N vertices, establishing some good upper bounds on the projection constants of hyperplanes, also seems to be an interesting and non-trivial problem. Here we briefly explain, how to get a simple uniform upper bound that goes to 1 and that holds with probability tending to 1, as \(N\rightarrow \infty \). Indeed, by a result of [7], we know that N random points in \(\mathbb {S}^n\), form an \(N^{-1/(2(n-1))}\)-net with the probability tending to 1, as \(N\rightarrow \infty \) (see the comment before Lemma 3.2). If this condition is satisfied, then from Lemma 2.1 it follows that \((1-N^{-1/(2(n-1))}){\mathbb S}_n\subseteq K\), where \(K={{\,\textrm{conv}\,}}{\{\pm x_1,\dots ,\pm x_N\}}\). Hence, if we denote by \(X=({\mathbb R}^n,\Vert \,{\cdot }\,\Vert _X)\) the normed space, for which \(B_X=K\), then
Now, let \(Y \subseteq X\) be an arbitrary hyperplane. If \(P:{\mathbb R}^n\rightarrow Y\) is an orthogonal projection, then \(\Vert P\Vert _2=1\) and from the estimates above it easily follows that \(\Vert P\Vert _X\le 1+2N^{-1/(2(n-1))}\). Thus, combining this with Theorem 1.2 we get, that for \(N\rightarrow \infty \), the projection constant of an arbitrary hyperplane in X lies in the interval
with the probability tending to 1. We do not know, to what extent this range is best possible, but it is likely that it could be improved (restricted) significantly.
We must note that the asymptotic lower bound (2) on \(\rho _n^H\) does not seem to be optimal. The same is true for the estimate \(\rho _3>175\cdot 10^{-16}\) on the three-dimensional constant. Moreover, we do not have any non-trivial bound on the constant \(\rho _n\) for \(n\ge 4\).
Providing some different example of a class of normed spaces, for which all non-trivial projections/hyperplane projections satisfy some explicit uniform lower bound on the norm, is of its own interest, even if it does not lead to improvement in the global estimates. We do not know if our results for the random spherical polytopes are optimal. Studying this example in more depth, certainly seems to be interesting. Considering the importance of random constructions in modern functional analysis, it is reasonable to believe, that random polytopes could possibly yield much better bounds on the constants \(\rho _n\) and \(\rho _n^H\). It is likely, that our methods could be extended to all non-trivial projections, providing some bound on \(\rho _n\). However, to obtain a better bound on \(\rho _n^H\), it would be probably necessary to use random polytopes with the number of vertices of a smaller order than \(n^{4n}\). Even in the hyperplane setting, this would possibly require some completely new ideas.
References
Baronti, M., Papini, P.L.: Norm-one projections onto subspaces of \(l_p\). Ann. Mat. Pura Appl. 152, 53–61 (1988)
Basso, G.: Computation of maximal projection constants. J. Funct. Anal. 277(10), 3560–3585 (2019)
Blatter, J., Cheney, E.W.: Minimal projections on hyperplanes in sequence spaces. Ann. Mat. Pura Appl. 101, 215–227 (1974)
Bohnenblust, F.: Subspaces of \(l_{p, n}\) spaces. Am. J. Math. 63, 64–72 (1941)
Böröczky, K. Jr., Wintsche, G.: Covering the sphere by equal spherical balls. In: Discrete and Computational Geometry. Algorithms Combin., vol. 25, pp. 235–251. Springer, Berlin (2003)
Bosznay, Á.P., Garay, B.M.: On norms of projections. Acta Sci. Math. (Szeged) 50(1–2), 87–92 (1986)
Bourgain, J., Sarnak, P., Rudnick, Z.: Local statistics of lattice points on the sphere. In: Modern Trends in Constructive Function Theory. Contemp. Math., vol. 661, pp. 269–282. American Mathematical Society, Providence (2016)
Chalmers, B.L., Lewicki, G.: Three-dimensional subspace of \(l^{(5)}_\infty \) with maximal projection constant. J. Funct. Anal. 257(2), 553–592 (2009)
Chalmers, B.L., Lewicki, G.: A proof of the Grünbaum conjecture. Studia Math. 200(2), 103–129 (2010)
Foucart, S., Skrzypek, L.: On maximal relative projection constants. J. Math. Anal. Appl. 447(1), 309–328 (2017)
Gautschi, W.: Some elementary inequalities relating to the gamma and incomplete gamma function. J. Math. Phys. 38, 77–81 (1959)
Gluskin, E.D.: Finite-dimensional analogues of spaces without a basis. Dokl. Akad. Nauk SSSR 261(5), 1046–1050 (1981). (in Russian)
Gluskin, E.D.: The diameter of the Minkowski compactum is roughly equal to \(n\). Funktsional. Anal. i Prilozhen. 15(1), 72–73 (1981). (in Russian)
Grote, J., Kabluchko, Z., Thäle, Ch.: Limit theorems for random simplices in high dimensions. ALEA Lat. Am. J. Probab. Math. Stat. 16(1), 141–177 (2019)
Grünbaum, B.: Projection constants. Trans. Am. Math. Soc. 95, 451–465 (1960)
Kadec, M.I., Snobar, M.G.: On certain functionals on the Minkowski compactum. Mat. Zametki 10(4), 453–457 (1971). (in Russian)
Kakutani, S.: Some characterizations of Euclidean space. Jpn. J. Math. 16, 93–97 (1939)
Kobos, T.: A uniform estimate of the relative projection constant. J. Approx. Theory 225, 58–75 (2018)
König, H.: Spaces with large projection constants. Isr. J. Math. 50(3), 181–188 (1985)
König, H., Lewis, D.R., Lin, P.K.: Finite-dimensional projection constants. Studia Math. 75(3), 341–358 (1983)
König, H., Tomczak-Jaegermann, N.: Norms of minimal projections. J. Funct. Anal. 119(2), 253–280 (1994)
Latala, R., Mankiewicz, P., Oleszkiewicz, K., Tomczak-Jaegermann, N.: Banach–Mazur distances and projections on random subgaussian polytopes. Discrete Comput. Geom. 38(1), 29–50 (2007)
Mathai A.M.: Distributions of random volumes without using integral geometry techniques. In: Probability and Statistical Models with Applications, # 19. Chapman & Hall/CRC, Boca Raton (2001)
Randrianantoanina, B.: Norm-one projections in Banach spaces. Taiwan. J. Math. 5(1), 35–95 (2001)
Szarek, S.J.: The finite-dimensional basis problem with an appendix on nets of Grassmann manifolds. Acta Math. 151(3–4), 153–179 (1983)
Tomczak-Jaegermann, N.: Banach–Mazur Distances and Finite-Dimensional Operator Ideals. Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 38. Longman Scientific & Technical, Harlow (1989)
Wendel, J.G.: Note on the gamma function. Am. Math. Monthly 55(9), 563–564 (1948)
Acknowledgements
We are grateful to Zakhar Kabluchko for an extensive discussion concerning the probabilistic part of the paper and to Simon Foucart for useful suggestions. We also thank Marin Varivoda for a help with a computer assisted computation, that resulted in a numerical bound presented in Remark 4.2.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: Kenneth Clarkson
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Kobos, T. A Uniform Lower Bound on the Norms of Hyperplane Projections of Spherical Polytopes. Discrete Comput Geom 70, 279–296 (2023). https://doi.org/10.1007/s00454-023-00506-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-023-00506-z