A remark on two duality relations

DOI10.1007/S00020-006-1479-4MaRDI QIDQ2464699zbMATH OpenOpenAlexFDO

Publication date 17 December 2007

Published in Integral Equations and Operator Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0603461

convex bodies covering numbers entropy entropy numbers Pietsch's duality conjecture Sudakov's minoration

Local theory of Banach spaces (46B07) Riesz operators; eigenvalue distributions; approximation numbers, (s)-numbers, Kolmogorov numbers, entropy numbers, etc. of operators (47B06) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21)

Abstract: We remark that an easy combination of two known results yields a positive answer, up to log(n) terms, to a duality conjecture that goes back to Pietsch. In particular, we show that for any two symmetric convex bodies K,T in R^n, denoting by N(K,T) the minimal number of translates of T needed to cover K, one has: N(K,T) <= N(T*,(C log(n))^{-1} K*)^{C log(n) loglog(n)}, where K*,T* are the polar bodies to K,T, respectively, and C > 1 is a universal constant. As a corollary, we observe a new duality result (up to log(n) terms) for Talagrand's gamma_p functionals.

Review text

Let \(K,T\) be two centrally symmetric convex bodies in \({\mathbb R}^n\), and let \(N (K, T)\) be the covering number of \(K\) by \(T\), i.e., the minimal number of translates of \(T\) needed to cover \(K\). Pietsch's duality conjecture, formulated in 1972, asks whether this covering number is of the same order as the covering number \(N (T^\circ, K^\circ)\) of the polar body \(T^\circ\) of \(T\) by the polar body \(K^\circ\) of \(K\); more precisely: do there exist two numerical constants \(a, b \geq 1\) such that, for any \(n \geq 1\), one has, for any two symmetric convex bodies \(K, T \subseteq {\mathbb R}^n\): \[ b^{-1} \log N (T^\circ, a K^\circ) \leq \log (K, T) \leq b \log N (T^\circ, a^{-1} K^\circ) ? \] The answer is positive for a wide class of bodies, as it is well detailed in this paper, but the problem is still open in full generality (and it seems to the author that the answer might be negative in general, leading him to formulate a `weak duality conjecture for covering numbers'). In this paper, that he modestly entitled ``A remark\dots, the author was able to derive that Pietsch's conjecture has, up to a \(\log n\) factor, a positive answer. Though his result follows directly from two previous results: Theorem~6 in [\textit{J.\,Bourgain, A.\,Pajor, S.\,J.\thinspace Szarek} and \textit{N.\,Tomczak--Jaegermann}, Lect.\ Notes Math.\ 1376, 50--63 (1989; Zbl 0678.47015)] and the reduction lemma of \textit{S.\,Artstein, V.\,D.\thinspace Milman} and \textit{S.\,J.\thinspace Szarek} [Ann.\ Math.\ (2) 159, No.\,3, 1313--1328 (2004; Zbl 1072.52001)], which allows to assume that \(K \subseteq 4T\) or \(T \subseteq 4K\), it generalizes and unifies all previously known results. It states that, for any symmetric convex bodies \(K, T\) in \({\mathbb R}^n\), one has: \[ \log N (K, T) \leq (V \log V) \log N (T^\circ, V^{-1} K^\circ), \tag{1} \] where \(V= \min \big( V(K), V (T) \big)\). The parameter \(V(L)\), \(L\) a symmetric convex body, is defined as the infimum, over all the convex bodies \(B\) of \({\mathbb R}^n\), of some function depending on the Banach--Mazur distance between \(L\) and \(B\), and, implicitly, on the \(K\)-convexity constant of the Banach space whose unit ball is \(B\). Actually: \[ V = C_1 \inf\{ \log (C_2 t) \big( 10 T_p (X_B) \big)^q;\; \;K \subseteq tB, \;B \subseteq 4T, \;t \geq 1\}, \] where the infimum is taken over all symmetric convex bodies \(B\) of \({\mathbb R}^n\), \(X_B\) is the Banach space whose unit ball is \(B\), \(T_p(X_B)\) is its type \(p\) constant, and \(q = p/ (p - 1)\). However, the expression with the \(K\)-convexity constant allows to use duality to get the reverse inequality in (1). Using John's theorem, the author gets, as a corollary, that, for a universal constant \(C > 0\): \[ \log N (K, T) \leq C\,\log (n + 1) \log\log (n + 2)\, \log N \big(T^\circ, (C \log (n + 1))^{-1} K^\circ \big). \tag{2} \] The best previous known estimate was \(\log N (K, T) \leq C \log N (T^\circ, (Cn)^{-1/2} K^\circ )\). The second ``remark of this paper concerns Talagrand's functional \(\gamma_p\), \(p > 0\). It is defined, for every metric space \((M,d)\), by \(\gamma_p (M,d)= \inf \sup_{x \in M} \sum_{j \geq 0} 2^{j/p} d (x, M_j)\), where the infimum runs over all the subsets \(M_j\) of \(M\) such that \(|M_j| = 2^{2^j}\). For two symmetric convex bodies \(K,T\) in \({\mathbb R}^n\), \(\gamma_p (K,T)\) is \(\gamma_p (K, d_T)\), where \(d_T\) is the distance associated to the norm induced by \(T\). This functional was first introduced (when \(T= D\) is an ellipsoid) by Talagrand, in order to study the boundedness of Gaussian processes. The author uses his result (2) to prove the following duality result: \[ \gamma_p (K, T) \leq C_p\, \log (n + 1)^{2 + 1/p} \log\log (n + 2)^{1/p}\, \gamma_p (T^\circ, K^\circ), \tag{3} \] for any two symmetric convex bodies \(K, T\) in \({\mathbb R}^n\). Though the author says that this follows directly from \((2)\) and elementary observations, he had to prove the following inequalities (Proposition 3.3): \[ 2^{-1/p} \sup_{k \geq 1} k^{1/p} e_k \leq \gamma_p \leq C_p \sum_{k\geq 1} k^{{1\over p} - 1} e_k \leq \log (n + 1)\, C'_p\, \sup_{k \geq 1} k^{1/p} e_k, \tag{4} \] where \(\gamma_p = \gamma_p (K,T)\), and \(e_k = e_k (K,T) = \inf \{ \varepsilon > 0\); \(N (K, \varepsilon T) \leq 2^k\}\) is the \(k\)th entropy number of \(K\) with respect to \(T\). The first inequality in \((4)\) is an analogue of Sudakov's minoration (since Talagrand's theorem asserts that \(\gamma_2 (K, D) \approx {\mathbb E}\,\sup_{x \in K} \langle x, G \rangle\), for any Gaussian variable \(G\), where \(D\) is the ellipsoid associated to the covariance of \(G\)). The second one is Dudley's entropy majoration, and \((3)\) says that they are equivalent, up to a \(\log n\) term.

Recommendations

Cited in

(10)

This page was built for publication: A remark on two duality relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2464699)