Abstract
We study the ‘no-dimension’ analogue of Carathéodory’s theorem in Banach spaces. We prove such a result together with its colorful version for uniformly smooth Banach spaces. It follows that uniform smoothness leads to a greedy de-randomization of Maurey’s classical lemma Pisier (in: Séminaire Analyse fonctionnelle (dit “Maurey-Schwartz”), 1980), which is itself a ‘no-dimension’ analogue of Carathéodory’s theorem with a probabilistic proof. We find the asymptotically tight upper bound on the deviation of the convex hull from the k-convex hull of a bounded set in \(L_p\) with \(1 < p \le 2\) and get asymptotically the same bound as in Maurey’s lemma for \(L_p\) with \(1< p < \infty \).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Carathéodory’s theorem [4] is a classical result in Convex Geometry. It states that every point in the convex hull \({\mathrm{conv}}\, S\) of a set \(S \subset {\mathbb {R}}^d\) is a convex combination of at most \(d+1\) points of S. There are many different generalizations of this theorem. Recently, several authors studied so-called approximate versions of Carathéodory’s theorem, where the distance between a point of the convex hull \({\mathrm{conv}}\,S \) of a bounded set S and the k-convex hull \({\mathrm{conv}}_k S\) were investigated. The latter, the k-convex hull of S, is the set of all convex combinations of at most k points of S. For example, [1, Thm. 2.2] the following optimal result in the Euclidean case was proven:
The distance between any point p in the convex hull of a bounded set S of a Euclidean space and the k-convex hull \({\mathrm{conv}}_k S\) is at most \(\frac{{\mathrm{diam}}\, S}{\sqrt{2k}}\).
However, not only the Euclidean case was studied. Probably, the most significant result in the area is Maurey’s lemma [16], in which an approximate version of Carathéodory’s theorem is proven for spaces that have (Rademacher) type \(p > 1\). We explain the definitions and formulate Maurey’s lemma and explain its relation to our results in the next section. We note here that Maurey’s lemma is a more general statement than our results. However, Maurey’s proof uses Khintchine’s inequality and it is probabilistic.
We think that a simple geometric property of Banach spaces hides behind such a sophisticated technique. In this paper, we prove the approximate Carathéodory’s theorem for uniformly smooth Banach spaces, and bound the distance between a point of the convex hull of a bounded set and its k-convex hull in terms of the modulus of smoothness of a Banach space. In fact, we provide a greedy algorithm for the approximation of a point of the convex hull of a bounded set in a uniformly smooth Banach space. We note here that an \(L_p\) space for \(1< p < \infty \) is uniformly smooth and its modulus of smoothness is well known. We give all the required definitions in Sect. 2 and briefly discuss there some properties of Banach spaces that are connected to the uniform smoothness of Banach spaces. The following statement is the main result of the paper.
Theorem 1.1
Let S be a bounded set in a uniformly smooth Banach space X, \(a \in {\mathrm{conv}}\,S\). Then there exists a sequence \(\{x_i\}_{i=1}^\infty \subset S\) such that for vectors \(a_k = \frac{1}{k} \sum _{i \in [k]} x_i\) the following inequality holds:
where \(\rho _{X}\,\left( \cdot \right) \) is the modulus of smoothness of X.
In the proof we provide a greedy algorithm for constructing such a sequence, which directly implies the colorful version of approximate Carathéodory’s theorem.
Corollary 1.2
Let \(\{S_i\}_{i=1}^\infty \) be a family of sets of a Banach space X such that \(a \in \bigcap _{i=_1}^{\infty } {\mathrm{conv}}\, S_i\) and \(D = \sup _i {\mathrm{diam}}\, S_i < \infty \) Then there exists a transversal sequence \(\{x_i\}_{i=1}^\infty \) (that is, \(x_i \in S_i\)) such that for vectors \(a_k = \frac{1}{k} \sum _{i \in [k]} x_i\) the following inequality holds:
where \(\rho _{X}\,\left( \cdot \right) \) is the modulus of smoothness of X.
At the end of the next section, we show that the bound in inequality (1.1) is tight for all \(L_p\) spaces with \( 1 \le p \le 2\) and coincides with the bound obtained in [2] for \(2 \le p < \infty \) up to a reasonable constant factor.
There are some other “measures of non-convexity” of the k-convex hull. We refer the reader to the survey [8]. However, they were mostly studied in the Euclidean case.
2 Modulus of Smoothness and Its Properties
In this section, we give definitions from the Banach space theory and provide a certain reformulation of the main result using this language.
The modulus of smoothness (or Lindenstrauss’ modulus) of a Banach space X is the function \(\rho _X:[0, \infty ] \rightarrow [0, \infty ]\) given by
A Banach space X is called uniformly smooth if \(\rho _{X}\,\left( t \right) = o(t)\) as \(t \rightarrow 0\). It is known that uniform smoothness is equivalent to the uniform differentiability of the norm. As a good reference with simple geometric explanations of different properties of the modulus of smoothness and uniformly smooth spaces we refer to Chapter 2 of [6].
It is known that the modulus of smoothness \(\rho _{X}\,\left( \cdot \right) \) of a Banach space X is a convex strictly increasing function that satisfies the following inequality of Day–Nordlander type [13] for all positive \(\tau \):
where \(\rho _{H}\left( \tau \right) \) is the modulus of smoothness of Hilbert space. The latter inequality implies the following technical observations, which we use in the sequel:
and
Clearly, uniform smoothness of the norm is not stable under small perturbations of the norm. However, equivalent renormalization of a space just adds a constant factor to inequalities (1.1), (1.2). That is, we can approximate a point of the convex hull by a point of the k-convex hull of a bounded set in every Banach space, which admits an equivalent uniformly smooth norm. Such spaces are well-studied; moreover, due to Enflo [7] and Pisier [15], we know that these spaces are exactly the so-called super-reflexive Banach spaces. Summarizing their results, the following assertions are equivalent
-
a Banach space X admits an equivalent uniformly smooth norm;
-
a Banach space X admits an equivalent uniformly smooth norm with modulus of smoothness of power type p;
-
a Banach space X is a super-reflexive space.
It is said that a uniformly smooth Banach space X has modulus of smoothness of power type p if, for some \(0< C < \infty \), \(\rho _{X}\,\left( \tau \right) \le C \tau ^p\). Now we can reformulate our results in a norm renormalization invariant way. We use \(\mathrm{dist}\left( a, B \right) \) to denote the distance between a point a and a set B. We define the deviation of a set A from a set B as follows:
We say that a Banach space X has Carathéodory’s approximation property if there is a function \(f:\mathbb {N} \rightarrow [0, \infty )\) with \(\lim _{k \rightarrow \infty } f(k) = 0\) such that \(h^{+} ({\mathrm{conv}}\, S, {\mathrm{conv}}_k S) \le f(k)\) for an arbitrary subset S of the unit ball of X. Theorem 1.1 and the discussion above imply the following.
Corollary 2.1
A super-reflexive Banach space X has Carathéodory’s approximation property: that is, there exists \(p \in (1,2]\) and constant C such that
for all \(\varepsilon > 0\) and \(k \ge C \bigl (\frac{{\mathrm{diam}}\, S}{\varepsilon }\bigr )^{{p}/({p-1})}\).
A Banach space X is said to be of type p for some \(1 < p \leqslant 2\), if there exists a constant \(T_p(X) < \infty \) such that, for every finite set of vectors \(\{x_{j}\}_{j=1}^{n}\) in X, we have
where \(\left\{ r_{j}\right\} _{j=1}^{\infty }\) denotes the sequence of the Rademacher functions.
We can formulate Maurey’s lemma as follows (see also [3, Lem. D]).
Let S be a bounded set in a Banach space X which is of type p, \(a \in {\mathrm{conv}}\, S\). Set \(q = {p}/({p -1})\). Then there exists a sequence \(\{x_i\}_{i=1}^\infty \subset S\) such that for vectors \(a_k = \frac{1}{k} \sum _{i \in [k]} x_i\) the following inequality holds:
Since a Banach space with modulus of smoothness of power type p implies type p, then Theorem 1.1 follows from Maurey’s lemma (up to a constant term in the inequalities). The converse is not true in general (see [12, 17]). However, type p with some additional not very restrictive property (see table on p. 101 in [14]) implies modulus of smoothness of power type p. It is known [13] that \(L_p\), \(1< p < \infty \), is of type \(q = \max \{p, 2\}\) and has modulus of smoothness of power \(\max \{p, 2\}\). More precisely,
Since p in Corollary 2.1 can be chosen to be the order of the modulus of smoothness, we see that \(k = O \bigl (\frac{{\mathrm{diam}}^2 S}{\varepsilon ^2} \bigr )\) in \(L_p\), \(2 \le p < \infty \), which coincides with the rate of convergence in Maurey’s lemma. Moreover, as was shown in Barman’s paper [2, Thm. 3.2], the constants in both inequalities are close enough to one another in this case.
In case of an \(L_p\) space with \(1 \le p \le 2\), the bound in inequality (1.1) is the best possible up to a constant: when \(n = 2k\), \(S=\{e_1, \dots , e_{2n}\}\) and \(a = \{1/n, \dots , 1/n\}\), then \(\mathrm{dist}\left( a, {\mathrm{conv}}_k S \right) \ge \frac{1}{4}\, k^{1/p - 1}\). Moreover, this implies that \(L_1\) and \(L_\infty \) have no Carathéodory’s approximation property.
3 Geometrical Idea Behind the Proof
We begin with a sketch of the proof of the following folklore analogue of the main theorem in a Euclidean space (see [5, 18]).
Let S be a subset of the unit ball of a Euclidean space such that \(0 \in {\mathrm{conv}}\, S\). Then there exists a sequence \(\{x_i\}_{i=1}^\infty \subset S\) such that
for all \(k \in {\mathbb {N}}\).
We apply induction on k. Assume that we have chosen \(x_1, \dots , x_n\) that satisfy the inequality for all \(k \in [n]\). Since \(0 \in {\mathrm{conv}}\, S\), there exists \(x_{n+1}\) such that \(\bigl \langle x_{n+1},\sum _{i=1}^n x_i\bigr \rangle \le 0\). Then, by the law of cosines,
The statement is proven.
In fact, the law of cosines can be reformulated in terms of the deviation of the unit sphere from its supporting hyperplane as follows.
We use \(u^*\) to denote a unit functional that attains its norm on a non-zero vector u of a Banach space X, i.e., \(\langle u^*,u\rangle = \left\| u \right\| \left\| u^* \right\| = \left\| u \right\| \). Clearly, a set \(\{x \in X \,|\, \langle u^*,x\rangle = 1 \}\) is a supporting hyperplane to the unit ball of X at \(u/\left\| u \right\| \). For simplicity, we assume that \(u^*= 0\) for \(u =0\). Let H be a supporting hyperplane at a unit vector u of the unit ball in a Euclidean space E and x be such that \(\left\langle u^*,x\right\rangle \le 0\). Then the norm of \(\left\| u+x \right\| \) is at most \( \sqrt{1 +\left\| x \right\| ^2}\) (\(\approx 1 + \rho _{E}\left( \left\| x \right\| \right) \) for sufficiently small \(\left\| x \right\| \)) with equality only for x parallel to H. That is, we see that vectors from the supporting hyperplane spoil the sum most badly and we measure the deviation of the unit sphere from a supporting hyperplane to bound the norm of the sum on each step. Similar statements can be proven in a uniformly smooth Banach space. However, it is not necessarily true that for an arbitrary unit vector u of a Banach space the maximum of norm \(\left\| u + v \right\| \), where \(\left\| v \right\| \) is fixed and \(\left\langle u^*,v\right\rangle \le 0\), is attained on the supporting hyperplane to the unit ball at u. But one can measure this deviation using the modulus of smoothness, which we do in the following simple lemma.
Lemma 3.1
Let u be a unit vector of Banach space X and \(x \in X\) such that \(\left\langle u^*,x\right\rangle \le 0\). Then
Proof
Since \(\left\langle u^*,x\right\rangle \le 0\) and \(H_u = \{q \in X \,|\, \langle u^*,q\rangle = 1\}\) is a supporting hyperplane for the unit ball of X, we have that \(\left\| u - x \right\| \ge 1\). Therefore, by the definition of the modulus of smoothness, we obtain
or, equivalently,
\(\square \)
Our proof follows the same line as in the above-mentioned Euclidean analogue with the use of Lemma 3.1 instead of the law of cosines.
Remark 3.2
The deviation of the unit sphere from the supporting hyperplane in a Banach space was studied by the author in [9]. In particular, it was shown that the inequality from Lemma 3.1 is asymptotically tight as \(\left\| x \right\| \) tends to zero. On the other hand, it was proven in [11] that for any \(\tau \) in an arbitrary Banach space, there is a unit vector u and a vector x parallel to a supporting hyperplane to the unit ball at u such that \(\left\| u + x \right\| = \sqrt{1 + \left\| x \right\| ^2} = \sqrt{1 + \tau ^2}\). That is, the smallest upper bound is attained in the Euclidean case.
4 Proof of the Main Result
By setting \(S_i = S\) for all \(i \in \mathbb {N}\), we see that Corollary 1.2 implies Theorem 1.1. We give the proof of the corollary, which coincides with the proof of the theorem up to above-mentioned renaming of sets.
Proof
To simplify the proof, we translate \(S_i\) to \(S_i - a\) and then scale them in such a way that \(D = \sup _i{\mathrm{diam}}\, S_i = 1\). Then inequality (1.2) transforms into
Let us construct a sequence \(\{x_i\}_{i=1}^\infty \), where \(x_i \in S_i\), that satisfies the latter inequality. We use the following algorithm:
-
(1)
\(x_1\) is an arbitrary point from \(S_1\); \(x_2\) is an arbitrary point from \(S_2\).
-
(2)
For the constructed sequence \(\{x_1, \dots , x_{k}\}\), \(k \ge 2\), we choose \(x_{k+1} \in S_{k+1}\) such that \(\left\langle x_{k+1},a_k^*\right\rangle \le 0\) (that is, \(x_{k+1}\) is an arbitrary point of \(S_{k+1}\) if \(a_k = 0\)).
Firstly, the sequence \(\{x_i\}_{i=1}^\infty \) is well defined. Indeed, there exists \(q \in S_{k+1}\) such that \(\left\langle q,p\right\rangle \le 0\) for an arbitrary functional \(p \in X^*\), since \(0 \in {\mathrm{conv}}\, S_{k+1}\). In the algorithm we choose a functional \(p = a_k^*\) such that \(\left\| a_k^* \right\| = 1\) and for \(a_k = \frac{1}{k}\sum _{i \in [k]} x_i, a_k \ne 0\), the equality \(\left\langle a_k^*,a_k\right\rangle = \left\| a_k \right\| \) is valid.
Secondly, let us show that \(\{x_i\}_{i=1}^\infty \) satisfies inequality (4.1). Fix k. By inequality (2.1), we assume that \(k \ge 3\). By definition put \(\eta _k = 1 /\rho ^{-1}_{X}\,\left( 1/k \right) \) and \(u_k = k a_k\). If inequality \(\left\| u_k \right\| \le \eta _k\) holds, it implies the required inequality. Assume that \(\left\| u_k \right\| > \eta _k\). Then let \(m-1\) be the biggest number in \([k-1]\) such that \(\left\| u_{m-1} \right\| \le \eta _k\) and \(\left\| u_m \right\| > \eta _k\). Such m exists since, by inequality (2.2), we have that \(\left\| u_1 \right\| = \left\| x_1 \right\| \le \eta _k\). Since \(\eta _k \ge 1\) for \(k \ge 3\), we have
By the choice of m, we have that \(\left\| u_{m+\ell -1} \right\| > \eta _k \ge 1\) for all \(\ell \in [k-m]\). Hence, by the definition of \(\eta _k\) and the construction of \(\{x_i\}_{i=1}^\infty \), we get
Combining these inequalities for all \(\ell \in [k-m]\) and inequality (4.2), we obtain
Therefore, \(a_k = u_k/k\) satisfies inequality (4.1). The theorem is proven. \(\square \)
We note here that the authors used a similar idea in [10] to prove the convexity of a special type limit object in a uniformly smooth Banach space.
References
Adiprasito, K., Bárány, I., Mustafa, N.H.: Theorems of Carathéodory, Helly, and Tverberg without dimension. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2350–2360. SIAM, Philadelphia (2019)
Barman, S.: Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory’s theorem. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pp. 361–369. ACM, New York (2015)
Bourgain, J., Pajor, A., Szarek, S.J., Tomczak-Jaegermann, N.: On the duality problem for entropy numbers of operators. In: Lindenstrauss, J., Milman, V.D. (eds.) Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 1376, pp. 50–63. Springer, Berlin (1989)
Carathéodory, C.: Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen. Math. Ann. 64(1), 95–115 (1907)
Cassels, J.W.S.: Measures of the non-convexity of sets and the Shapley–Folkman–Starr theorem. Math. Proc. Cambridge Philos. Soc. 78(3), 433–436 (1975)
Diestel, J.: Geometry of Banach Spaces—Selected Topics. Lecture Notes in Mathematics, vol. 485. Springer, Berlin (1975)
Enflo, P.: Banach spaces which can be given an equivalent uniformly convex norm. Israel J. Math. 13(3–4), 281–288 (1972)
Fradelizi, M., Madiman, M., Marsiglietti, A., Zvavitch, A.: The convexification effect of Minkowski summation (2017). arXiv:1704.05486
Ivanov, G.M.: Modulus of supporting convexity and supporting smoothness. Eurasian Math. J. 6(1), 26–40 (2015)
Ivanov, G.M., Polovinkin, E.S.: A generalization of the set averaging theorem. Math. Notes 92(3–4), 369–374 (2012)
Ivanov, G., Martini, H.: New moduli for Banach spaces. Ann. Funct. Anal. 8(3), 350–365 (2017)
James, R.C.: Nonreflexive spaces of type 2. Israel J. Math. 30(1–2), 1–13 (1978)
Lindenstrauss, J.: On the modulus of smoothness and divergent series in Banach spaces. Michigan Math. J. 10(3), 241–252 (1963)
Lindenstrauss, J., Tzafriri, L.: Classical Banach Spaces II: Function Spaces. Ergebnisse der Mathematik und ihrer Grenzgebiet, vol. 97. Springer, Berlin (2013)
Pisier, G.: Martingales with values in uniformly convex spaces. Israel J. Math. 20(3–4), 326–350 (1975)
Pisier, G.: Remarques sur un résultat non publié de B. Maurey. In: Séminaire Analyse fonctionnelle (dit “Maurey-Schwartz”), vol. 5, pp. 1–12 (1980)
Pisier, G., Xu, Q.H.: Random series in the real interpolation spaces between the spaces \(v_p\). In: Lindenstrauss, J., Milman, V.D. (eds.) Geometrical Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 1267, pp. 185–209. Springer, Berlin (1987)
Starr, R.M.: Quasi-equilibria in markets with non-convex preferences. Econometrica 37(1), 25–38 (1969)
Acknowledgements
I wish to thank Imre Bárány for bringing the problem to my attention.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supported by the Swiss National Science Foundation Grant 200021_179133. Supported by the Russian Foundation for Basic Research, Project 18-01-00036 A.
Rights and permissions
About this article
Cite this article
Ivanov, G. Approximate Carathéodory’s Theorem in Uniformly Smooth Banach Spaces. Discrete Comput Geom 66, 273–280 (2021). https://doi.org/10.1007/s00454-019-00130-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-019-00130-w