Lecture Notes in Mathematics 2131
David Alonso-Gutiérrez Jesús Bastero
Approaching the Kannan-LovászSimonovits and Variance Conjectures
Lecture Notes in Mathematics Editors J.-M. Morel, Cachan B. Teissier, Paris Advisory Board: Camillo De Lellis, Zurich Mario di Bernardo, Bristol Alessio Figalli, Austin Davar Khoshnevisan, Salt Lake City Ioannis Kontoyiannis, Athens Gabor Lugosi, Barcelona Mark Podolskij, Aarhus Sylvia Serfaty, Paris and NY Catharina Stroppel, Bonn AnnaWienhard, Heidelberg
2131
More information about this series at http://www.springer.com/series/304
David Alonso-Gutiérrez • Jesús Bastero
Approaching the Kannan-Lovász-Simonovits and Variance Conjectures
123
David Alonso-Gutiérrez Departament de MatemJatiques and IMAC Universitat Jaume I Castelló de la Plana, Spain
Jesús Bastero Departamento de Matemáticas and IUMA Universidad de Zaragoza Zaragoza, Spain
ISBN 978-3-319-13262-4 ISBN 978-3-319-13263-1 (eBook) DOI 10.1007/978-3-319-13263-1 Springer Cham Heidelberg New York Dordrecht London Lecture Notes in Mathematics ISSN print edition: 0075-8434 ISSN electronic edition: 1617-9692 Library of Congress Control Number: 2014959425 Mathematics Subject Classification (2010): 46Bxx, 52Axx, 60-XX, 28Axx © Springer International Publishing Switzerland 2015 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
Preface
Asymptotic geometric analysis is a rather new branch of research in mathematics, coming from modern functional analysis and, more specifically, from the local theory of Banach spaces when it interplays with classical convex geometry and probability which studies high dimensional phenomena. It seems to us that the starting point of the theory can be found in Milman’s approach to the proof of Dvoretzky’s theorem [9]: “Given any norm in Rn , for a random C log n-dimensional subspace of Rn (C > 0 is an absolute constant) the norm is almost Euclidean”. In a geometrical setting, “given any convex body in Rn , a random C log n-dimensional section of it is almost a Euclidean ball”. It was well known from the very beginning of the theory that many infinitedimensional Banach spaces cannot have infinite-dimensional closed subspaces isomorphic to the Hilbert space. Thus, Dvoretzky’s theorem broke down the idea that the theory of finite-dimensional normed spaces could be a good approach for the study of the infinite-dimensional ones. On the contrary, when we are working on Rn and n is increasing to infinity, new and unexpected properties appear in the spaces and that was the blowup of a new theory, asymptotic in essence. Officially, asymptotic geometric analysis was born at the end of the last century and is now growing very fast since it is connected with many other parts of mathematics and also of mathematical physics and theoretical computer sciences. Nowadays the achievements of asymptotic geometric analysis show new and unexpected phenomena for high dimensions, which occur in several domains of mathematics and other sciences when we are dealing with a huge number of variables. It also includes connections with asymptotic combinatorics, complexity of graph theory and random matrices. Furthermore, in its development asymptotic geometric analysis uses tools coming from harmonic analysis, PDEs, Riemannian geometry, information and learning theories, quantum versions of this, and some other areas in mathematics. We can find several books concerning or related to these topics. For instance, in the very origins [9–11], and more recently [2, 3, 6, 7], and some others, especially several numbers of the collection Lecture Notes in Mathematics (Springer) entitled “Geometric Aspects of Functional Analysis”, Israel Seminar, GAFA (see the references in [5], [8], and [4]). v
vi
Preface
The readers interested in an overview of the whole theory should read the very recent book by Brazatikos, Giannopoulos, Valettas, and Vritsiou entitled “Geometry of Isotropic Log-Concave Measures” [4], in which the state of the art of the theory is perfectly explained. Our lecture notes focus only on a tiny part of this new theory. They concern two main conjectures: the Kannan-Lovász-Simonovits (KLS) spectral gap and the variance conjectures. Obviously, this is a small fragment of this theory, but it has become very active in research. Possibly, many readers will miss the hyperplane conjecture or slicing problem in these lecture notes. Certainly, this third and very important conjecture also appears in the notes, although only in a tangential manner in order to show its relation with the other two conjectures. As we commented before, the monograph [4] is really the state of the art in asymptotic geometric analysis. Since the advances in the theory are already gathered there, we feel that we must explain the reader what are the differences between what he will find in these notes and what he can find in the aforementioned monograph. In [4], complete information on all the topics in the theory can be found, with detailed proofs of each result. Many of the facts appear with the original approach in the corresponding citations and some others with new proofs and improvements. Our approach is aimed by a different intention. We want to present the theory in such a way that it allows interested people, even the ones who are not experts in the field, to get a quick account on the treated topics. In order to do it, we intend to go directly to the core of these two problems, simplifying the exposition in some cases and, in some other cases, offering a presentation of the methods suitable for the professionals with not much background in analysis, geometry, or probability. We expect that both experts and the less initiated, professional researchers interested in other different subjects as well as graduate student in mathematics, can get directly into these topics in the theory without any special effort. This is our main reason to present the theory, avoiding the need of a deep knowledge of the modern theory of convex bodies. Our work goes directly to connect isoperimetric-type inequalities and functional inequalities to offer the interested reader a fast approach to the center of the Kannan-Lovász-Simonovits and variance conjectures, which we think are very natural, modern, and interesting problems. We also try to complete the information related to these conjectures appearing in the reference quoted before by adding some special examples which do not appear in it. These are some of the contents in Chap. 2. In the same spirit we include some topics in Chap. 1, Sect. 1.7.2, corresponding to the case in which the probability we are working with is not isotropic, since it is not clear at this moment, as far as we know, how to pass from the variance of a function for an isotropic measure to the corresponding one for any of its linear deformations. These lecture notes are divided into three chapters plus an appendix. Let us comment the contents in these final lines of the Preface. Chapter 1 is composed of seven sections. The first four are introductory, introduce the conjectures, and their connection with theoretical computer science. Section 1.5 is dedicated to give the theorem by E. Milman on the role of convexity
References
vii
in the isoperimetry for log-concave probabilities. The two conjectures, KLS and variance, are presented in the last two sections of this first chapter. Chapter 2, composed of four sections, is dedicated to present the main examples where one or both conjectures are known to be true. The known examples of uniform probabilities on convex bodies which verify the KLS conjecture are some revolution bodies, the simplex and the `np -balls, 1 p 1. The fourth section develops Klartag’s results for unconditional log-concave probabilities. We also study the negative square correlation property and the examples satisfying it. In Chap. 3 we present four important results in this theory. The first two, the theorems by Eldan–Klartag and Ball–Nguyen, relate the variance or the KLS conjectures, respectively, with the hyperplane conjecture. Next we offer an approach to Eldan’s work on the relation between the thin-shell width and the KLS conjecture. Eventually we present the main ideas to prove the best known estimate for the thin-shell width given by Guédon–Milman. We want to mention here that we will only sketch the proofs in this chapter, since our intention is to offer the main ideas and give the results in a compelling way. In the appendix we present some basic facts related to Prékopa–Leindler, Brunn– Minkowski, and Borell’s inequalities. A part of these notes has been explained by the second author in the “VI International Course of Mathematical Analysis in Andalucía”, held in Antequera in September 2014 [1]. We would like to finish this preface thanking Prof. Julio Bernués for many discussions that helped us improving the presentation of these notes, Prof. Darío Cordero–Erausquin for providing us his notes on “La preuve de Eldan–Klartag un peu allegée” and allowing us to reproduce them here, and the anonymous referees for many useful comments that helped us to improve the final presentation of this monograph. This work has been done with the financial support of MTM2013-42105-P and DGA E-64 projects and of Institut Universitari de Matemàtiques i Aplicacions de Castelló. Castelló de la Plana, Spain Zaragoza, Spain October 2014
David Alonso-Gutiérrez Jesús Bastero
References 1. D. Alonso-Gutiérrez, J. Bastero, Convex inequalities, isoperimetry and spectral gap, in Proceedings of CIDAMA 2014 (to appear in 2015) 2. S. Bobkov, C. Houdré, Some connections between isoperimetric and sobolev-type inequalities. Mem. Am. Math. Soc. 129(616), (1997) 3. S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities. A Non-Asymptotic Theory of Independence (Oxford Univesity Press, Oxford, 2013)
viii
Preface
4. S. Brazitikos, A. Giannopoulos, P. Valettas, B.H. Vritsiou, Geometry of Isotropic Convex Bodies, Mathematical Surveys and Monographs, vol 196 (American Mathematical Society, Providence, RI, 2014) 5. B. Klartag, S. Mendelson, V.D. Milman, Geometric Aspects of Functional Analysis. Israel Seminar 2006–2010, Springer Lecture Notes in Mathematics, vol 2050 (Springer, New Yok, 2012) 6. A. Koldobsky, Fourier Analysis in Convex Geometry, Mathematical Surveys and Monographs, vol 116 (American Mathematical Society, Providence, RI, 2005) 7. M. Ledoux, The Concentration of Measure Phenomenon, Mathematical Surveys and Monographs, vol 89 (American Mathematical Society, Providence, RI, 2001) 8. M. Ludwig, V.D. Milman, V. Pestov, N. Tomczack-Jaegermann, Asymptotic Geometric Analysis. Proceedings of the Fall 2010, Fields Institute Tematic Program, Fieds Institute Communications, vol 68 (Springer, New York, 2013) 9. V.D. Milman, G. Schechtman, Asymptotic Theory of Finite Dimensional Normed Spaces, Springer Lecture Notes in Mathematics, vol 1200 (Springer, New York 1986) 10. G. Pisier, The Volume of Convex Bodies and Banach Space Geometry, vol 94 (Cambridge University Press, Cambridge 1989) 11. N. Tomczak-Jaegermann, Banach-Mazur Distances and Finite-Dimensional Normed Spaces, Pitman Monograghs and Surveys in Pure and Applied Mathematics, vol 38 (Longman Scientific & Technical, New York, 1989)
Contents
1
The Conjectures .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.1 Introduction and Notation .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.2 The KLS Conjecture in Theoretical Computer Science . . . . . . . . . . . . . . 1.3 Cheeger-Type Isoperimetric Inequality .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.4 Poincaré’s Inequalities and Spectral Gap .. . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.4.1 Hörmander’s L2 -Method . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.4.2 The One-Dimensional Case . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.4.3 Poincaré’s Inequality and Concentration of Measure Phenomena . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.4.4 Tensorizing Poincaré’s Inequality . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.5 E. Milman’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.6 Kannan-Lovász-Simonovits Spectral Gap Conjecture .. . . . . . . . . . . . . . . 1.6.1 Kannan, Lovász and Simonovits and Bobkob Approach .. . . . 1.6.2 Concentration and Relation with Strong Paouris’s Estimate.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.7 The Variance Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.7.1 Relation with the Thin-Shell Width . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.7.2 Linear Deformations . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.7.3 Square Negative Correlation Property . . . .. . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
2 Main Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 2.1 Tensorizing Examples Verifying KLS . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 2.1.1 Revolution Bodies .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 2.1.2 The Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 2.1.3 The `np -Balls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 2.2 Examples Verifying the Square Negative Correlation Property .. . . . . 2.2.1 The `np -Balls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 2.2.2 Generalized Orlicz Balls . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
1 1 5 7 11 13 18 22 25 26 34 36 41 44 49 53 58 61 65 65 66 69 72 79 79 81
ix
x
Contents n Orthogonal Projections of B1n and B1 and the Variance Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 84 2.3.1 Hyperplane Projections of Isotropic Convex Bodies . . . . . . . . . 84 2.3.2 Hyperplane Projections of the Cube. . . . . . .. . . . . . . . . . . . . . . . . . . . 86 2.3.3 Hyperplane Projections of the Cross-Polytope . . . . . . . . . . . . . . . 90 2.4 Klartag’s Theorems for Unconditional bodies . . . .. . . . . . . . . . . . . . . . . . . . 92 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 100
2.3
3 Relating the Conjectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.1 From the Variance Conjecture to the Slicing Problem Via Eldan-Klartag’s Method .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.2 KLS Conjecture Versus Hyperplane Conjecture According to Ball and Nguyen.. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.3 From the Thin-Shell Width to the KLS Conjecture: An Approach to R. Eldan’s Method . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.3.1 How to Approach Theorem 3.5.. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.3.2 How to Approach Theorem 3.6.. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.3.3 Stochastic Construction .. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.3.4 Thin-Shell Implies Spectral Gap . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.4 Guédon and Milman’s Estimate for the Thin-Shell Width . . . . . . . . . . . 3.4.1 Main Estimate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.4.2 How to Derive the Deviation Estimates . . .. . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
103
113 115 118 120 124 125 128 132 134
A Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . A.1 Brunn–Minkowski Inequality .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . A.2 Consequences of Brunn–Minkowski Inequality . .. . . . . . . . . . . . . . . . . . . . A.3 Borell’s Inequality and Concentration of Mass . . .. . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
137 137 140 142 146
103 109
Index . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 147
Chapter 1
The Conjectures
1.1 Introduction and Notation This first section is an introduction in which we present the main notions we are interested in: Cheeger’s isoperimetric inequality, log-concave probabilities, the isotropic ones, the thin-shell width of a log-concave probability, and isotropic convex bodies. We also present the two conjectures appearing in the title of these lecture notes and the rest of the notation we will use next. The classical isoperimetric inequality in Rn states that for every bounded Borel set A Rn mC .A/ C m.A/
n1 n
;
where m is the n-dimensional Lebesgue measure in Rn , mC is the outer Minkowski content defined by mC .A/ WD lim inf "!0
m.A" / m.A/ ; "
being A" D fa C xI a 2 A; jxj < "g the "-dilation of A and the constant C D
mC .B/ m.B/
n1 n
D
mn1 .S n1 / m.B/
n1 n
(B is the Euclidean unit ball, S n1 its boundary and mn1 .S n1 / its Hausdorff measure). The outer Minkowski content mC coincides with the .n 1/-dimensional Hausdorff measure of the boundary @A for bounded Borel sets with smooth enough boundary.
© Springer International Publishing Switzerland 2015 D. Alonso-Gutiérrez, J. Bastero, Approaching the Kannan-Lovász-Simonovits and Variance Conjectures, Lecture Notes in Mathematics 2131, DOI 10.1007/978-3-319-13263-1_1
1
2
1 The Conjectures
This inequality has its counterpart in the functional framework through Sobolevtype inequalities. Indeed (see [29, 47]), it is well known that proving the inequality above with a constant C is equivalent to proving that n k jrf j k1 C kf k n1
for any compactly supported smooth function f W Rn ! R, where Z n kf k n1 D
jf .x/j
n n1
n1 n dx :
Rn
We want to consider here what is called Cheeger’s isoperimetric inequality for log-concave Borel probabilities on Rn . In the sequel we consider a centered full-dimensional log-concave Borel probability on Rn . We say that is log-concave if its density with respect to the Lebesgue measure is eV for some convex function V W Rn ! .1; 1. In particular, the uniform probability measure on a convex body in Rn is log-concave. Given a function g W Rn ! R, let us denote the expectation of g with respect to by E g and the variance of g with respect to by 2 Var g D E g E g D E g 2 .E g/2 : Definition 1.1 Let be a log-concave probability on Rn . We say that verifies Cheeger’s isoperimetric inequality with constant C if for every Borel set A Rn C .A/ C minf.A/; .Ac /g;
(1.1)
where C .A/ D lim inf "!0
.A" / .A/ : "
We denote by Is./ the best constant in (1.1), which is called the Cheeger’s constant of . In a similar way as the classical isoperimetric inequality is related to Sobolev’s inequality, Cheeger-type isoperimetric inequalities are related to some kind of Poincaré-type inequalities. For that, let F be the space of all locally Lipschitz, integrable with respect to functions f W Rn ! R. For functions f 2 F , we define the Euclidean norm of its gradient jrf j W Rn ! Œ0; 1/ by jrf .x/j D lim sup y!x
jf .y/ f .x/j : jy xj
1.1 Introduction and Notation
3
We will see in Sect. 1.3 (see Theorems 1.1 and 1.2) that inequality (1.1) is true with a constant C1 if and only if the inequality C2 kf E f k1 k jrf j k1
(1.2)
is true for every f 2 F , with 2C2 C1 C2 . Let us introduce some more notation. If is a centered log-concave probability measure in Rn , we denote by the square root of the largest eigenvalue of the covariance matrix M D E xi xj i;j : 2 D kM k`n2 !`n2 D sup E hx; i2 : 2S n1
We say that a log-concave probability is isotropic if: (i) The barycenter is the origin, i.e., E x D 0, and (ii) The covariance matrix M is the identity, i.e., E xi xj D ıi;j , 1 i; j n. One of the two conjectures we present in this notes (see Sect. 1.6) was posed by Kannan, Lovász and Simonovits (KLS) (see [37]) and it concerns the Cheeger’s constant of log-concave probabilities. It suggests that there exists an absolute constant, independent of and n, such that any log-concave probability on Rn verifies the Cheeger-type isoperimetric inequality C .A/
C .A/
(1.3)
for any Borel set A with .A/ 1=2 or, equivalently, (1.2) is true E jf E f j C E jrf j
8f 2 F
(1.4)
for some absolute constant C > 0. We will see in Sect. 1.5 that proving (1.4) is equivalent to proving E jf E f j2 C 2 E jrf j2
8f 2 F \ L2 ./
(1.5)
for some absolute constant C . From the definition of , (1.5) is true with constant C D 1, for any log-concave probability and any linear function f . The KLS conjecture originally stems from an algorithmic question about the complexity of volume computation for convex bodies, and a positive answer to it would have implications on the complexity of numerous other algorithms (see Sect. 1.2 later for a rough approach or summary to this fact).
4
1 The Conjectures
The variance conjecture for general log-concave probability measures is the particular case of (1.5) when f .x/ D jxj2 . In such case the conjecture reads Var jxj2 C 2 E jxj2 ;
(1.6)
where C > 0 is an absolute constant. In the particular case that we consider (1.6) for isotropic log-concave probability measures it takes the form Var jxj2 C n;
(1.7)
where C > 0 is an absolute constant. Even though the variance conjecture (1.7) is just a particular case of the KLS conjecture (1.5), its origin comes from a different problem. It was considered by Bobkov and Koldobsky in the context of the Central Limit Problem for isotropic convex bodies (see [16]). It was conjectured before by Anttila, Ball and Perissinaki [2] that for an isotropic log-concave probability , jxj is highly concentrated in a “thin shell”, more than the trivial bound Varjxj Ejxj2 suggested. The variance conjecture (1.7) is true for any isotropic log-concave if and only if the “thin-shell width” of any isotropic log-concave is bounded from above, i.e., q n WD sup
ˇ p ˇ2 E ˇjxj n ˇ W isotropic, log-concave C
(1.8)
and, furthermore, this would imply that the hyperplane conjecture would be true (see [4, 26]). In [27] the authors prove that bounding from above the “thin-shell” width is essentially equivalent to control the correct dependence on the dimension in the stability version of Brunn-Minkowski inequality, which is another important conjecture in the modern theory of convex bodies. In these notes we present an approach to the aforementioned conjectures and some of the results, known up to now, related to these conjectures. Only a few examples are known to satisfy the KLS conjecture [i.e., (1.3), (1.4) or (1.5)]. Some of these examples are the case of uniform measures on `np -balls, 1 p 1, the simplex and some revolution convex bodies [7, 36, 43, 55]. Besides, Klartag proved (1.5) with an extra log n factor for uniform probabilities on unconditional convex bodies (see [41]) and recently Barthe and Cordero extended this result for log-concave measures with many symmetries [6]. Fleury proved that Gaussian polytopes verify this conjecture in expectation (see [31]). We will present some of these examples in Chap. 2. Concerning the variance conjecture [i.e., (1.6), (1.7) or (1.8)], Klartag (see [40]) proved (1.6) for unconditional convex bodies. We will also present this example in Chap. 2. A general result, also in the case of isotropic log-concave probabilities, was proved by Guédon and Milman with a factor n1=3 instead of C in (1.8) and improving down to n1=4 when is 2 (see [35]). This results improved earlier
1.2 The KLS Conjecture in Theoretical Computer Science
5
estimates by Fleury [30] and by Klartag [39]. It is also easy to deduce (1.6) with an extra factor n2=3 from Guédon and Milman’s result. Very recently Eldan (see [25]) proved a relation between the variance conjecture and the KLS conjecture. As a result (1.5) is true with an extra factor n2=3 .log n/2 . We will give an idea of Guédon-Milman and Eldan’s results in Chap. 3. We finish this section introducing some more notation that we will be using. A convex body K in Rn is a convex, compact subset of Rn having the origin in its interior. Given an n-dimensional convex body K, we will denote by jKjn (or Q n D 1). simply jKj) its volume and by KQ its homothetic image of volume 1 (jKj n1 KQ D jKjn K. The volume of the n-dimensional Euclidean ball will be denoted by !n . A convex body K Rn is said to be isotropic if it has volume jKjn D 1, the barycenter of K is atRthe origin and its inertia matrix is a multiple of the identity, R i.e., K xdx D 0 and K xi xj dx D L2K ıij for some constant LK > 0. Equivalently, there exists a constant LK > 0 called the isotropic constant of K such that L2K D R 2 n1 . In this case the probability uniformly distributed K hx; i dx for every 2 S 1 on LK K is isotropic. When we write a b, for a; b > 0, it means that the quotient of a and b is bounded from above and from below by absolute constants. O.n/ and SO.n/ will always denote the orthogonal and the symmetric orthogonal group on Rn . The Haar probability on them will be denoted by . We will also denote by n1 or just the Haar probability measure on S n1 .
1.2 The KLS Conjecture in Theoretical Computer Science Even though the KLS conjecture is an interesting geometric problem in itself, the origin of this problem is not purely geometric but it comes from another problem in theoretical computer science. Theoretical computer science deals with the design of efficient algorithms, i.e., with small complexity, and is related to convex geometry since the 1970s, when geometric algorithms for convex optimization started to be developed. In this section we present the problem in computer science that led to the KLS conjecture. We refer the reader to [58] for a more thorough explanation of some of the algorithmic convex geometry problems treated in theoretical computer science. One of the problems treated in theoretical computer science is the design of an algorithm to compute the volume of an n-dimensional convex body, i.e., an algorithm that receives as an input an n-dimensional convex body K, a point x0 2 K and an error parameter " and returns as an output a real number A such that .1 "/jKj A .1 C "/jKj: The convex body is given as an oracle. Typically, this will be the membership oracle which, given a point x 2 Rn , will tell whether the point x belongs to K or not. The
6
1 The Conjectures
complexity of such an algorithm will be measured by both the number of calls to the oracle and the number of arithmetic operations. Any deterministic algorithm for computing the volume of a convex body had been proved to have an exponential complexity (see [28] and [5]). However, in 1989, Dyer, Frieze, and Kannan [24] showed that if we allow some randomness we can construct an algorithm that gives the right answer with probability 1 ı and runs in polynomial time. Namely, the complexity of the algorithm is polynomial in n; 1" , and log 1ı . The solution provided in [24] is based on a scheme for sampling nearly uniformly on K. Hence, the more efficiently we construct a sampling algorithm, the more efficiently we construct an algorithm for computing the volume. A sampling algorithm for a convex body K is an algorithm that receives as an input and n-dimensional convex body (in the form of an oracle), a point x0 2 K and an error parameter " and returns as an output a random point whose distribution is within total variation distance " from the uniform distribution on K. The way to construct a sampling algorithm is taking a random walk, i.e., a Markov chain. Starting at the point x0 , received as an input, we take a random point x1 . From x1 we take a random point x2 and so on. Under some conditions, the distribution of the random point xt converges, in total variation distance, to a unique stationary distribution. Thus, the way to construct a sampling algorithm depends on the distribution of the random point xn given xn1 . In Dyer, Frieze, and Kannan’s paper [24] the authors constructed a random walk on a grid of cubes. In order to prove that the Markov chain mixes rapidly, i.e., the distribution of the point xt in the random walk converges to the uniform distribution on K in polynomial time, the authors needed to show that for a convex body with smooth boundary KK, constructed from the convex body K which is the input of the algorithm, the uniform probability measure on its surface satisfies a Cheeger-type isoperimetric inequality. However, the authors conjectured that any convex body K satisfies a Cheeger-type isoperimetric inequality with constant a fixed polynomial in n and the diameter of K. This would simplify their proof as well as give an estimate on the mixing rate of the algorithm. In [38, 46] and [23] some lower bounds, involving the diameter of K, for the Cheeger’s constant were proved. In [37], Kannan, Lovász, and Simonovits improved these estimates and conjectured the lower bound C ( denotes the uniform probability on a convex body), which is the main conjecture treated in this monograph. Remark 1.1 If a sampling algorithm is constructed using the random walk in [24], one cannot get a mixing rate better than O.n8 /. If we construct the Markov chain using the ball walk, which from a point xi takes a random point at distance smaller than ı and jumps there if the point is in K (otherwise it stays in xi ), then the mixing rate of the random walk can be improved. If KLS conjecture were true we would obtain a mixing rate of the order O.n2 /, which matches the best possible for the ball walk, as shown by an isotropic cube. The best mixing rate up to now is of the order O.nc / for some constant c between 2 and 3.
1.3 Cheeger-Type Isoperimetric Inequality
7
Remark 1.2 If the KLS conjecture were true and we could obtain a sampling algorithm with mixing rate O.n2 / then there exists the possibility (one would still have to surmount other substantial hurdles) of getting a volume-computing algorithm of complexity O .n3 /, where the notation O suppresses error terms and logarithmic factors. Very recently, Cousins and Vempala (see [22]) managed to bypass the KLS conjecture and construct a volume-computing algorithm with complexity O .n3 /. Their improvement derives from the fact the KLS conjecture is verified by the restriction of Gaussian measures to convex bodies. Nevertheless, computing the volume of a convex body is not the only problem for which constructing a sampling algorithm is important, Some other problems in theoretical computer science, such as optimization and rounding, are solved by reduction to random sampling.
1.3 Cheeger-Type Isoperimetric Inequality This section is devoted to prove the equivalence between Cheeger’s isoperimetric inequality and a type of Poincaré’s inequality for probability measures in Rn (with exponents 1). We prove the co-area formula for this. By the work of Rothaus, Cheeger, Maz’ya and Ledoux (see [14, Theorem 1.1]) we have the following results: Theorem 1.1 Let be a Borel probability measure on Rn . The following statements are equivalent: (i) For any Borel set A Rn C .A/ C1 minf.A/; .Ac /g: (ii) For any integrable and locally Lipschitz (Lipschitz on any Euclidean ball) function f C2 kf E f k1 k jrf j k1 ; with C2 C1 2C2 . We will begin with a proof of the co-area formula for locally Lipschitz functions. Lemma 1.1 (Co-area Formula) Let f W Rn ! R be locally Lipschitz and integrable with respect to . Then Z
Z
1
C fx 2 Rn W jf .x/j > tgdt:
jrf .x/jd.x/ Rn
0
8
1 The Conjectures
Proof For every h > 0, let fh W Rn ! R be defined by fh .x/ D sup jf .y/j. The jxyj
function fh is measurable and for any x 2 Rn lim sup h!0
fh .x/ jf .x/j jf .y/j jf .x/j D lim sup jrf .x/j: h jy xj y!x
Then, using Fatou’s lemma, Z
Z jrf .x/jd.x/ Rn
fh .x/ jf .x/j d.x/ h
lim sup Rn
h!0
Z
fh .x/ jf .x/j d.x/ h
lim sup h!0
Z
Rn
lim inf h!0
D lim inf h!0
Rn
1 h
Z
fh .x/ jf .x/j d.x/ h 1
.fx 2 Rn ; fh .x/ > t g fx 2 Rn ; jf .x/j > t g/ dt:
0
For a fixed t > 0 , let us call At D fx 2 Rn W jf .x/j > tg. It is easy to see that .At /h D At C hB D fx 2 Rn W fh .x/ > tg and so, using Fatou’s lemma again, Z
Z 1 1 jrf .x/jdx lim inf ..Aht / .At //dt h!0 n h R 0 Z 1 Z 1 .Aht / .At / dt D lim inf C .At /dt: h!0 h 0 0
We can now prove Theorem 1.1 Proof (of Theorem 1.1) : (i) H) (ii) Assume that f is bounded from below. It is clear that f1 D f C K > 0, for some K > 0, f1 is integrable and locally Lipschitz, kf Ef k1 D kf1 Ef1 k1 and krf k1 D krf1 k1 . Then, by the co-area formula, Z
Z
1
C fx 2 Rn W f1 .x/ > tgdt
jrf1 .x/jdx Rn
0
Z
1
C1 0
minf.At /; .Act /gdt;
1.3 Cheeger-Type Isoperimetric Inequality
9
where At D fx 2 Rn W f1 .x/ > tg and so, Z Z 1 jrf1 .x/jdx C1 .At /.Act /dt Rn
0
C1 D 2 C1 D 2 D D
C1 2 C1 2 C1 2
C1 D 2 D
Z
1
kAt E At k1 dt Z
0
Z
1
sup 0
kgk1 D1 Rn
Z
1
Z
sup kgk1 D1 0
Z
1
.At .x/ E At /g.x/d.x/dt
Z
Rn
sup Rn
kgk1 D1 0
Z
.At .x/ E At /g.x/d.x/dt At .x/.g.x/ E g/d.x/dt
.g.x/ E g/f1 .x/d
sup kgk1 D1 Rn
Z
sup
.f1 .x/ E f1 /g.x/d.x/
kgk1 D1 Rn
C1 kf E f k1 : 2
In the general case we proceed by an approximation argument. (ii) H) (i) Let A be a Borel set in Rn . Given 0 < " < 1, we define ( ) 2 d.x; A" / f" .x/ D max 0; 1 : " "2 2
It is clear that 0 f" .x/ 1, f" .x/ D 1 in the open set A" A and vanishes if d.x; A/ > ". Moreover lim"!0 f" D A , where A denotes the closure of A. Since jf" .x/ f" .y/j
ˇ ˇ jx yj 1 2 2 ˇ ˇ ; ˇ d.x; A" / d.y; A" / ˇ ".1 "/ ".1 "/
f" is locally Lipschitz and jrf" .x/j
1 " "2 2
for every x 2 Rn . Clearly jrf" .x/j D 0 if x 2 fx 2 Rn I d.x; A/ > "g [ A" fx 2 Rn I d.x; A/ > "g [ A. Thus, Z
Z
2
.A"C" / .A/ jrf" .x/jd.x/ D jrf" .x/jd.x/ : " "2 Rn fx2Rn Id.x;A/"gnA
10
1 The Conjectures
By (ii), 2
C2 kf" E f" k1
.A"C" / .A/ ; " "2
and letting " ! 0C we obtain 2C2 .A/.Ac / C .A/ (we can restrict ourselves to the case .A/ D .A/, otherwise C .A/ D 1). Since maxf.A/; .Ac /g 12 , this gives C2 minf.A/; .Ac /g C .A/: Instead of using the expectation we can use the median of the functions and then we have that Theorem 1.2 Let be a Borel probability on Rn . The following statements are equivalent (i) For any Borel set A Rn C minf.A/; .Ac /g C .A/: (ii) For any integrable and locally Lipschitz function f C E jf m.f /j E jrf j; where m.f / is the median of f . Only minor changes are necessary to obtain this result. Let us sketch them. The co-area formula can also be expressed in the following way Z
Z
1
C fx 2 Rn W f .x/ > tgdt:
jrf .x/jd.x/ Rn
1
(First consider f bounded from below, add K such that f C K > 0 and then use an approximation procedure). Then Z
Z
m.f /
.1 fx 2 Rn W f > tg/dt
jrf .x/jd.x/ C Rn
1 Z 1
fx 2 Rn W f > tgdt
CC m.f /
D C E jf m.f /j:
1.4 Poincaré’s Inequalities and Spectral Gap
11
For the reverse implication we follow the same procedure as in Theorem 1.1 (ii)H) (i), and apply (ii) to g" D f" m.f" /, taking into account that, when " tends to 0, N < 1=2 or .A/ N 1=2, respectively. g" tends to either AN 1 or AN whenever .A/
1.4 Poincaré’s Inequalities and Spectral Gap In this section we focus in Poincaré’s inequality in Rn . We begin by presenting the proof of Poincaré’s inequality for a convex body with smooth boundary, endowed with the uniform probability measure on it, by solving the corresponding Neumann problem for the Laplacian. Next we consider the Hörmander’s L2 -method to prove that log-concave probabilities more convex than Gaussian in Rn also satisfy a Poincaré-type inequality. We will prove Bobkov’s extension of Talagrand’s inequality for one dimensional log-concave probabilities. Eventually in this section we will prove the concentration of measure phenomena expressed by the GromovMilman theorem in terms of the spectral gap. Poincaré’s inequality states that for a log-concave probability on Rn , Var f C./E jrf j2 for any f 2 F \ L2 ./. We are interested in the best value of the constant C./, whose inverse we will denote C./1 D 1 ./. 1 ./ will be called the spectral gap of . Kannan, Lovász and Simonovits [37] proved that Var f 4 inf n E jx x0 j2 E jrf j2 x0 2R
for any locally Lipschitz function f in L2 ./. If we consider isotropic log-concave probabilities, the best known estimate, depending only on n, is 2
Var f C n 3 log2 nE jrf j2 ; given by Eldan [25] using a previous estimate of the thin-shell width by Guédon and Milman [35]. A result involving the variance of jxj2 was obtained by Bobkov [12]. As a consequence, a sharper result is true for log-concave probabilities satisfying the variance conjecture: 1
Var f C 2 n 2 E jrf j2 : We begin with the classical case, the uniform probability measure on a convex body (we follow [40]). The classical Laplacian is the operator associated to this inequality: Let ˝ be a convex body in Rn with regular boundary, i.e., there exists W ˝ ! R, C 1 .˝/-smooth and convex with bounded derivatives of all orders in a
12
1 The Conjectures
neighborhood on @˝, such that jr .x/j D 1; .x/ D 0
for every x 2 @˝
and .x/ 0
for x 2 ˝:
Note that r .x/ is the outer unit normal for x 2 @˝. Denote by D.˝/ the C 1 .˝/-smooth functions u W ˝ ! R (with bounded derivatives of all orders, so the boundary values are well defined and C 1 on the boundary) which satisfy the Neumann boundary conditions hru.x/; r .x/i D 0
for x 2 @˝:
The operator , defined in D.˝/ as the opposite of the Laplacian, extends to a non-bounded closed self-adjoint operator in L2 .˝; dx/ with dense domain. Furthermore, integrating by parts and using Rademacher’s differentiation theorem we have Z Z f .x/ u.x/ dx D hrf .x/; ru.x/idx ˝
˝
(second of Green’s identities). By solving the Neumann problem in this domain
u.x/ C u.x/ D 0 if x 2 ˝ hru.x/; r .x/i D 0 if x 2 @˝;
we get that the operator has a non-bounded sequence of eigenvalues 0 D 0 < 1 2 : : : , with the corresponding sequence of eigenvectors, which form an orthonormal basis in L2 .˝/. It is clear that 0 D C and that the other eigenvectors, f n g1 nD1 , are functions in D.˝/ satisfying
n C n n D 0: For instance, if n D 1 and ˝ D Œ0; 1,pthe eigenvalues are f0; .n /2 I n 2 Ng and the corresponding eigenvectors are f1; 2 cos.n x/; n 2 Ng). By Green’s second identity we have Z 0D
. n .x/ m .x/ m .x/ n .x//dx ˝
Z
D .n m /
n .x/ m .x/dx ˝
and then n and m are orthogonal, if n ¤ m.
1.4 Poincaré’s Inequalities and Spectral Gap
13
Moreover, n ın;m D n h n ; m iL2 .˝/ D h n ; m iL2 .˝/ D hr n ; r m iL2 .˝/ : p 2 Thus, fr n = n g1 nD1 is also an orthonormal system in L .˝/. 2 Let f 2 L .˝/ be locally Lipschitz. If we denote by the uniform probability on ˝ then 1 kf E f k22
1 X
n jhf; n ij2 D
nD1
D
1 X 1 jhf; n ij2 n nD1
1 1 X X 1 1 jhrf; r n ij2 D jhrf; p r n ij2 n nD1 n nD1
krf k22 : It is important to remark here for future use that if is an eigenfunction associated to the eigenvalue 1 then E D 0 and 1 k k22 D k jr j k22 :
(1.9)
Thus, we have the following: Theorem 1.3 (Poincaré’s Inequality) Let ˝ be a convex body in Rn with smooth boundary and finite Lebesgue measure and the uniform probability measure on ˝. Then, ˇ2 Z ˇ Z Z ˇ ˇ 1 1 1 ˇ ˇ f .x/dxˇ dx 1 Var f D 1 f .x/ jrf .x/j2 dx j˝j ˝ ˇ j˝j ˝ j˝j ˝ D E jrf j2
(1.10)
for any locally Lipschitz function f 2 L2 .˝; dx/. 1 is called the spectral gap, of in the domain ˝. Furthermore, the equality is attained when f D 1 , eigenfunction corresponding to the first non-trivial eigenvalue 1 , for in this domain.
1.4.1 Hörmander’s L2 -Method We consider now the case of a log-concave probability on Rn (we follow [6, 21]). We assume that d.x/ D eW .x/ dx, for some W W Rn ! R convex in C 2 .Rn /. We introduce the associated Laplace-Beltrami operator on L2 ./ given by Lu D u hrW; rui:
14
1 The Conjectures
This operator is well defined on D D fu W Rn ! R W u 2 C 2 .Rn / compactly supportedg and extends to a non-bounded closed self-adjoint operator in L2 .Rn ; d/. It is easy to show Green’s identity for L. Indeed, let f be a locally Lipschitz function such that f and jrf j 2 L2 ./, then Z
Z f .x/Lu.x/ d.x/ D Rn
hrf .x/; ru.x/id.x/ Rn
for all u 2 D. Indeed, Z Z f .x/Lu.x/ d.x/ D Rn
Z
f .x/. u.x/ hrW .x/; ru.x/i/d.x/ Rn
f .x/eW .x/ u.x/ dx
D Rn
Z f .x/eW .x/ hrW .x/; ru.x/idx
Z
Rn
Z
Rn
Z
Rn
hru.x/; r.f eW /.x/idx
D
f .x/eW .x/ hrW .x/; ru.x/dx
hrf .x/; ru.x/id.x/:
D Rn
N According to [6], “Hörmander developed the L2 -method for solving the @equation, emphasizing the central role played by the convexity, or rather plusubharmonicity, of the domain or of the potential W . We will use only the easy part of the method, namely the a priori spectral type inequalities (which are often referred to, in the real case, as Poincaré Brascamp-Lieb inequalities)”. The following are two well-known properties on positive linear operators Lemma 1.2 Let H be the Euclidean space Rn . The following assertions are true: (i) If x; y 2 H and T 0 is an invertible linear operator in H , then 2hx; yi hTx; xi C hT 1 y; yi: (ii) If T is an operator in H such that T I , i.e., hTy; yi hy; yi for all y 2 Rn , then T is invertible and I T 1 . Proof (i) If T 0, i.e. hTy; yi 0 for all y 2 H , then T is self-adjoint, invertible by hypothesis, and 0 hT .x T 1 y/; x T 1 yi D hTx; xi C hy; T 1 yi hTx; T 1 yi hy; xi:
1.4 Poincaré’s Inequalities and Spectral Gap
15
(ii) Clearly T is invertible. Since T I is self-adjoint, the spectral theorem says P that T I D niD1 i i ˝ i , where i 0, f i gniD1 is an orthonormal basis and ˝ x D h ; xi . Then, I T 1 D
n X i D1
i
i ˝ i 1 C i
and the result holds. We will use only the easy part in Hörmander’s method to obtain Poincaré’s inequality. The following lemma was proved in [21]. Lemma 1.3 L.D/ is dense in L20 ./, the closed vector subspace of L2 ./ orthogonal to the constant functions. Proof Assume that W is a real C 2 -smooth function on Rn . Let m be the Lebesgue measure on Rn . Define U the unitary operator U W L2 ./ ! L2 .m/ given by Uf D feW =2 . Given 2 D, f 2 L2 ./ with jrf j 2 L2 ./, let g D Uf 2 L2 .m/. Then we have Z hL.U /; f iL2 .m/ D hr.U /.x/; rf .x/i eW .x/ dx Z
Rn
D
hr .x/ C Z
Rn
1 .x/rW .x/; eW .x/=2 rf .x/idx 2
1 1 .x/rW .x/; rg.x/ C g.x/rW .x/idx 2 2 Rn Z Z 1
.x/ g.x/dx C hr. g/.x/; rW .x/idx D n 2 R Rn Z 1 C g.x/ .x/jrW .x/j2 dx 4 Rn Z D . .x/ C V .x/ .x//g.x/dx; D
hr .x/ C
Rn
where V .x/ D 14 jrW .x/j2 12 W .x/. Then, by a density argument, the equality hL.U /; f iL2 ./ D h
C V ; Uf iL2 .m/
is also true for any function f 2 L2 ./ (U transforms L into a Schrödinger operator). Assume that f 2 L2 ./ is orthogonal to L.D/. It follows that g D Vg as a 2;2 distribution in D 0 , for g D Uf . Hence g belongs to the Sobolev space Wloc .Rn / and jrf j exists.
16
1 The Conjectures
Let 2 D be such that D 1 in a neighborhood of 0, define k .x/ D .x=k/ for k 1. We will prove that k jr.k f /j kL2 ./ !k!1 0; which will imply that f is constant and this will finish the proof. We have that Z Z jr.k f /.x/j2 d.x/ D jr.k geW =2 /.x/j2 eW .x/ dx Rn
Rn
D (integrating by parts) Z jr.k g/.x/j2 C .k .x/g.x//2 W .x/ dx D Rn
Z
jr.k g/j2 C k2 g g dx
D Rn
Z
Z jrk .x/j2 g 2 .x/dx C
D Rn
Rn
Z
k .x/g.x/hrk .x/; rg.x/idx
C2 Rn
Z C
Rn
Z
k2 .x/jrg.x/j2 dx
k2 .x/g.x/ g.x/dx
jrk .x/j2 g 2 .x/dx !k!1 0;
D Rn
since
Z Rn
div .k2 grg/.x/dx D 0:
Theorem 1.4 Let be a log-concave probability d.x/ D eW .x/ dx where W W Rn ! R is a C 2 smooth convex function. Assume that Hess W .x/ c I for any x 2 Rn (the function W has some strict convexity). Then, Var f
1 E jrf j2 c
for any locally Lipschitz, integrable function f 2 L2 ./. Proof If u 2 D, integrating by parts its derivatives with respect to any coordinate we have Z Z .Lu.x//2 d.x/ D hHess W .x/ru.x/; ru.x/id.x/ Rn
Rn
Z
C Rn
kHess u.x/k2HS d.x/;
1.4 Poincaré’s Inequalities and Spectral Gap
17
where Hess f is the Hessian matrix of f and k kHS is the Hilbert-Schmidt norm, i.e. X kHess u.x/k2HS D .@ij u.x//2 : i;j
In particular, Z
Z .Lu.x//2 d.x/
Rn
hHess W .x/ru.x/; ru.x/id.x/: Rn
2 2 We use that L.D/ is R dense in L0 ./. Let f be a function such that f 2 L ./, 2 jrf j 2 L ./ and Rn f .x/d.x/ D 0. We have Z .Lu.x/ f .x//2 d.x/ D 0: inf u2D
Rn
Hence, for any u 2 D, Z Z 2 Var f .f .x/ Lu.x// d.x/ D 2 hrf .x/; ru.x/i d.x/ Rn
Rn
Z
.Lu.x//2 d.x/
Rn
Z 2
hrf .x/; ru.x/id.x/
Z
hHess W .x/ru.x/; ru.x/id.x/
(by Lemma 1.2 i)) Z h.Hess W /1 .x/rf .x/; rf .x/id.x/ Rn
(by Lemma 1.2 ii)) Z 1 jrf .x/j2 d.x/: c Rn Taking the infimum in u we obtain the result. Remark 1.3 If has convex support K, i.e. d.x/ D eW .x/ dx with W of class C 2 on K, and equal to C1 outside K, then the integration by parts above incorporates a boundary term which, by the convexity of K, is always non-negative. Then we have Z Z 2 .Lu.x// d.x/ hHess W .x/ru.x/; ru.x/i d.x/ Rn
Z C Rn
kHess W u.x/k2HS d.x/;
18
1 The Conjectures
which goes in the right direction for the arguments and the results can directly be extended to this more general class of measures.
1.4.2 The One-Dimensional Case The one dimensional case was worked out by Bobkov extending Talagrand’s isoperimetric inequality (see [11, 15, 57]). Theorem 1.5 Let d.x/ D eW .x/ dx be a log-concave probability on R, where W W ˝ ! R is a convex function defined in some non-empty open interval ˝ R. Ra Let a denote the median of , i.e., the only real number for which 1 d D 1=2. Then 2 1 Is./2 : 3 Var x Var x Besides Is./ D 2m./ D 2eW .a/ . Moreover the following Poincaré-type inequality holds 1 ./Var f E jrf j2 for any locally Lipschitz, integrable function in L2 ./, where 1 1 1 ./ : 12Var x Var x Proof Let F be the distribution function of , i.e., F W R ! .0; 1/ is given by Z
x
F .x/ D
eW .t / dt:
1
F W ˝ ! .0; 1/ is a strictly increasing, onto C 1 function. Consider the random variable Y D F 1 .Y1 /, where Y1 is a uniform random variable on .0; 1/. Y is distributed in R according to d. We want to estimate Z
Z
1
Var x D Var Y D
F
1
1
2
.p/ dp
0
F
1
2 .p/dp :
0
For that, we introduce the function I W .0; 1/ ! .0; 1/ given by I .p/ D
dF 1 1 .F .p// D eW .F .p// dx
8 p 2 .0; 1/:
1.4 Poincaré’s Inequalities and Spectral Gap
19
I is concave since dI dW 1 .p/ D .F .p// dp dx and we have 1 Var Y D 2 1 D 2 1 2
D
Z
1
Z
1
Z
0
Z
1 0
0
1
2 F 1 .p/ F 1 .q/ dpdq
Z
0
0
p q
1 Z
1Z
Z
0
p q
2 dF1 .u/ du dpdq du du 2 dpdq: I .u/
Let us assume the following claim, which will be proved later: Claim Let I W .0; 1/ ! .0; 1/ be a concave function, then (i) I.p/ 2I 12 minfp; 1 pg; 0
Z
1 1 2
1
Z
0
2
1 0
Z
p q
du minfu; 1 ug
2 dpdq:
If X is a real random variable distributed according to the exponential law, d.x/ D 12 ejxj dx, it is clear that the corresponding function I is I .p/ D minfp; 1 pg
8 p 2 .0; 1/
and Var X D 2. Thus, we get Var Y 4I
1 1 2 Var X 2
2I
1 1 2 : 2
On the other hand, 1 Var Y 2
Z 0
1
Z
1 0
Z
p q
du 1 I 2 C u 12
!2 dpdq:
20
1 The Conjectures
The right hand side of this inequality is an even and symmetric with respect to 0 convex function in , so 1 Var Y 2
Z
1 0
Z
Z
1 0
p q
du 1
I
!2 dpdq
1 1 2 :
12I
2
2
Next we are going to prove that Is./ D inf
0
I .p/ : minfp; 1 pg
Consider A D f.1; x/I x 2 Rg. If A 2 A we have R xC" lim"!0 1" x eW .t / dt C .A/ Rx Rx D minf.A/; 1 .A/g minf 1 eW .t / dt; 1 1 eW .t / dtg D
eW .x/ Rx minf 1 eW .t / dt; 1 1 eW .t / dtg Rx
D .whenever x D F 1 .p// D
I .p/ : minfp; 1 pg
Hence 1 C .A/ 2I D inf 2 A2A ;.A/D 12 minf.A/; 1 .A/g inf A
C .A/ minf.A/; 1 .A/g
D . by Theorem 1.1 / inf f
E jrf j D Is./: jf E f j
On the other hand, let U W R ! R be U D F1 ı F . U is bijective and C 1 and pushes forward the probability to . Let V D U 1 . It is not difficult to check by the chain rule that for any x D F1 .p/ dV.x/ D dx
eW .x/ dF .x/ .V .x// dx
D
eW .x/ 1 V .x/ e 2
I .p/ 1 2I : D minfp; 1 pg 2
1.4 Poincaré’s Inequalities and Spectral Gap
21
Let x < y be real numbers, then Z
U.y/
y x D V .U.y// V .U.x// D
V 0 .t/dt 2I
U.x/
1 .U.y/ U.x//: 2
1 1 . We know that for any f W R ! R
Thus, U is Lipschitz with kU kLips
2I 2 Lipschitz with median m .f / D 0, Talagrand’s isoperimetric inequality for the exponential probability implies that E jf j E jrf j. Let now g W R ! R be locally Lipschitz integrable with respect to and having m .g/ D 0. Define f D g ı U . It is easy to see that m .f / D 0. Thus, E jg m .g/j D E jf m .f /j E jrf j E jrgjkU kLips D kU kLips E jrgj
1 1 E jrgj;
2I
2
which implies that 1 Is./: 2I 2 The last assertion will be proved in Sect. 1.5. Proof (of the Claim) (i) Let 0 < " < p < 1=2 I.p/
1 2 1 2
p
p" I."/ C 1 I " " 2
p" 1 1 1 I 2 2 " 2
and let " ! 0, so I.p/ 2pI 12 . A similar argument can be applied for 1=2 < p < 1. (ii) Since I is concave and positive I.p/ is under the tangent at the point .1=2; I.1=2//, i.e., 1 1 0 I.p/ I C p 0 < p < 1: 2 2 Taking p ! 0 or p ! 1 we have 1 0I 2 2 and then jj 2I. 21 /.
0I
1 C 2 2
22
1 The Conjectures
1.4.3 Poincaré’s Inequality and Concentration of Measure Phenomena Next we relate Poincaré inequality, concentration and deviation inequalities, using ideas by Gromov-Milman (see [34]) and tools appearing in [44, 50]. Given a probability measure on Rn we define the concentration function for any t > 0, ˛ , by 1 : ˛ .t/ D sup 1 .At / W A Rn Borel set ; .A/ 2 Theorem 1.6 Let be any probability on Rn . Consider the following statements: (i) For every Lipschitz function f W Rn ! R with Lipschitz constant kf kLips D 1 and median m.f / we have fx 2 Rn I jf m.f /j > tg aebt for any t > 0, (ii) ˛ .t/ cedt , for any t > 0, (iii) For every f 2 F 1 Var f E jrf j2 ; (iv) For every Lipschitz, integrable function f W Rn ! R Var f C1 kf k2Lips : Then, • • • •
q (iii) H) (ii), with c 12 and d 161 , (ii) H) (i), with a 2c and b d , (i) H) (iv), with C1 2a b , (iv) H) (iii) with 1 CC1 , where C is an absolute constant. Let us start proving the following lemma:
Lemma 1.4 Let be a probability on Rn with spectral gap 1 ./. Let A; B be two Borel subsets in Rn such that d.A; B/ " > 0. Then .B/
1 .A/ : 1 C 1 ./.A/"2
1.4 Poincaré’s Inequalities and Spectral Gap
23
Proof First of all assume that A; B are open sets in Rn such D a > 0 and that .A/ 1 1 1 1 C minf"; d.x; A/g. .B/ D b > 0. Consider the function f .x/ D a " a b This function is Lipschitz. Indeed 1 1 C jminf"; d.x; A/g minf"; d.y; A/gj a b 1 1 1 C jx yj : " a b
1 jf .x/ f .y/j D "
It is clear that rf .x/ D 0 for every x 2 A [ B. Then 1 1 ./Var f E jrf j 2 "
2
1 1 C a b
2 .1 a b/ :
Since for any ˛ 2 R Z 2
E jf ˛j
2
jf ˛j d C A
D
Z
2
jf ˛j d B
1 ˛ a
2
2 1 aC ˛ b b
1 1 1 1 C C a˛ 2 C b˛ 2 C ; a b a b
taking ˛ D E f , we obtain 1 1 ./ 2 "
1 1ab 1 C .1 a b/ ; a b ab"2
since a C b 1. This implies that b
1a : 1 C 1 ./a"2
In the general case, take > 0, define A D fx 2 Rn I d.x; A/ < g and B in a similar way. Apply the preceding argument and pass to the limit when ! 0. Proof (of Theorem 1.6) • (iii) H) (ii) 1 2
D e2 . If B is a Borel set then, as a 2 consequence of the preceding lemma applied to A D .B /c , Let > 0 be such that 1 C
.B / 1=2 H) .B / e2 .B/;
24
1 The Conjectures
since .A/ 1=2. By recurrence .B k /
1 H) .B k / e2k .B/: 2
Let A be a Borel set such that .A/ 1=2 and let " > 0. Choose k 2 N such that k " .k C 1/ (if k D 0 the result is trivial). Denote by B D .Ak /c . It is clear that B k Ac and so .B k / 1=2. Then 1 .B k / e2k .B/ D e2k ..Ak /c /: 2 Thus, .A" / 1 ..Ak /c / 1
1 1 1 " 1 kC1 1 e 2k 2e 2e 2
p
1 "p 1 1 e 16 2 and we obtain (ii). • (ii) H) (i) Assume that f W Rn ! R is a Lipschitz function with Lipschitz constant L D 1 and median m.f /. Let A D fx W f .x/ m.f /g, B D fx W f .x/ m.f /g. We have .A/; .B/ 1=2. Since At fxI f > m.f / tg and B t fxI f < m.f / C tg we deduce fjf m.f /j < tg D fm.f / t < f < m.f / C tg .At \ B t / D 1 ..At /c [ .B t /c / 1 2cedt : • (i) H) (iv) We can assume without loss of generality that kf kLips D 1. It is clear that Z
1
2
Var f E jf m.f /j D
2tfjf m.f /j > tgdt 0
Z
1
ebt dt D
2a 0
2a : b
• (i) H) (iv) This implication will be proved in Sect. 1.5.
1.4 Poincaré’s Inequalities and Spectral Gap
25
1.4.4 Tensorizing Poincaré’s Inequality We finish this section with the following facts Theorem 1.7 The following facts are true (i) In the case that K is the uniform probability on a convex body K, K D aCK D UK D K for any a 2 Rn , U 2 O.n/. Besides tK D tK for any t > 0. Is./ (ii) Poincaré’s inequality is stable under tensorization. Furthermore Is.n / p 2 6 and the same is true for Cheeger’s inequality. Proof (i) This fact is trivial (ii) The first part is consequence of the following lemma: Lemma 1.5 Let .˝i ; i /, 1 i n, n-probability spaces and let .X; P/ be the product probability space. Then VarP f
n X
EP Vari fi ;
i D1
where f is any measurable function on X and fi .xi / D f .x1 ; : : : ; xi ; : : : ; xn / with .x1 ; : : : ; xi ; : : : ; xn / 2 X . This lemma can be proved by induction. Indeed, let us prove it for n D 2: Var˝ f E˝ .Var f C Var f /: We have that Var˝ f D E˝ jf E˝ f j2 D E˝ .f E f /2 C E˝ .E f E˝ f /2 C2E˝ .f E f /.E f E˝ f /: The first summand equals E˝ .f E f /2 D E E .f E f /2 D E Var f D E˝ Var f; the second one equals E˝ .E f E˝ f /2 D E .E .f E f //2 (by Jensen’s inequality) E Var f D E˝ Var f;
26
1 The Conjectures
and the last one vanishes E˝ .f E f /.E f E˝ f / D E˝ .f E f / E˝ .f E˝ f / E˝ .E f /2 C E˝ .E f E˝ f / D E .E f /2 .E˝ f /2 E .E f /2 C.E˝ f /2 D 0: The second part was proved by Bobkov and Houdré (see [15]).
1.5 E. Milman’s Theorem This section is dedicated to give a proof of the nice theorem by E. Milman on the role of convexity, where he proved the equivalence among all Poincaré-type inequalities for all values of p. In particular Cheeger’s isoperimetric inequality, Poincaré’s inequality, the exponential concentration inequality and the first-moment concentration inequality are equivalent with the same constants, up to absolute factors. In Poincaré’s inequality we can consider different exponents, Dp;q kf E f kp k jrf j kq for functions f 2 F , whenever p q (by Jensen). Dp;q is the best constant verifying the inequality above for all the functions f 2 F . If p D q D 1 we have an inequality which is equivalent to Cheeger’s inequality according to Theorem 1.1. The case p D q D 2 is Poincaré’s inequality (1.10). The most important result is the one by E. Milman concerning the equivalence for all Poincaré-type inequalities with different values of p’s, for log-concave probabilities. In the first result we will deduce Poincaré’s inequality from Cheeger’s inequality, i.e., CD1;1 D2;2 for some absolute constant C > 0. Theorem 1.8 Let be a probability measure on Rn . Assume that the following inequality holds D1;1 E jf E f j E jrf j
1.5 E. Milman’s Theorem
27
whenever f 2 F . Then we have the following Poincaré’s inequality CD21;1 E jf E f j2 E jrf j2 for any locally Lipschitz f 2 L2 ./, where C > 0 is an absolute constant. Proof First of all we can consider m.f /, the median of f , instead of E f . Indeed, let p 1 ˇp ˇ ˇ ˇp E ˇf E f ˇ 2p inf E jf ajp 2p E ˇf m.f /ˇ a
ˇ ˇ2 (we trivially have E ˇf E f ˇ E jf m.f /j2 , for p D 2). In order to prove the reverse inequality we may assume m.f / > E f (otherwise, change f by f ). Markov’s inequality implies that 1 ff m.f /g fjf E f j m.f / E f g 2 E jf E f j : m.f / E f Then E jf m.f /jp
ˇ p ˇp 1=p ˇp ˇ E ˇf E f ˇ C .m.f / E f / 3p E ˇf E f ˇ :
Let now g 2 L2 ./ with m.g/ D 0. Consider f D jgj2 sign.g/. It is clear that f 2 L1 ./, it is locally Lipschitz, and m.f / D 0. Thus, E jg E gj2 4E jgj2 D 4E jf m.f /j 12E jf E f j
12 E jrf j D1;1
1=2 1=2 24 E jrgj2 E C jgj2 D1;1
1=2 1=2 C E jrgj2 E jg Egj2 D1;1
and so, CD21;1 D2;2 , where C is an absolute constant. Adapting the arguments, the same proof gives the following result (see [48, Proposition 2.5]): Theorem 1.9 Let 0 p p 0 1 and 0 q q 0 1, such that 1 1 1 1 D 0 0: p q p q
28
1 The Conjectures
Then, Dp;q Cp0 Dp0 ;q 0 ; where C > 0 is an absolute constant. E. Milman proved a breakthrough showing that, under convexity assumptions, for instance log-concave probabilities, we can reverse the inequalities Dp;q CD1;1 for all 1 p q 1. In order to prove this fact we will introduce the semigroup technique, previously used by Ledoux. We can assume that d D e V .x/ dx is a log-concave probability with V smooth (an approximation argument to deduce the result without any smoothness assumption can be seen in [49]). Let .Pt /t 0 be the semigroup associated to the diffusion process whose infinitesimal generator is the Laplace-Beltrami operator L D hrV; ri. It is characterized by the following system of differential equations of second order d Pt .f / D L.Pt .f //; dt
P0 .f / D f
for every bounded smooth function f . Pt is bounded on Lp ./, p 1. Furthermore • • • • •
Pt .1/ D 1, f 0 H) Pt .f / 0, E Pt .f / D E f , E jPt .f /jp E jf jp , 8p 1 (Bakry-Ledoux) 2tjrPt .f /j2 Pt .f 2 / .Pt .f //2
for all t 0 and f bounded and smooth (in Riemannians manifolds the factor 2t should be changed according to the curvature). Here, the convexity of V plays a special role. • (Consequence of preceding ones). If 2 q 1 and f bounded and smooth 1 k jrPt .f /j kLq ./ p kf kLq ./ : 2t • (Ledoux). If f bounded smooth kf Pt .f /kL1 ./
p
2tk jrf j kL1 ./ :
1.5 E. Milman’s Theorem
29
Theorem 1.10 (E. Milman, [48], Theorem 2.9) Let be a log-concave probability on Rn . Assume that D1;1 E jf E f j k jrf j k1 whenever f 2 L1 ./ and locally Lipschitz. If A is a Borel set in Rn with .A/ 1=2, then C .A/ CD1;1 .A/2 ; where C > 0 is an absolute constant. As a consequence, CD1;1 E jf E f j E jrf j whenever f 2 F . Proof Assume that A is closed. Given " > 0, let A" D fx 2 Rn W d.x; A/ < "g and A;" .x/ D maxf1 1" d.x; A/; 0g. It is clear that lim A;" .x/ D
"!0
1; if 0; if
x 2 A; x … A;
and 8 D 0; if jA;" .y/ A;" .x/j < jrA;" .x/j D lim sup D 0; if : 1 jy xj y!x " ; if
x 2 intA; d.x; A/ > "; x … intA; 0 d.x; A/ ":
Then, .A" / .A/ "
Z jrA;" .x/jd.x/ Rn
1 (by Ledoux) p E jA;" Pt .A;" /j: 2t Taking lim inf"!0 we obtain Z p C 2t .A/ E jA Pt .A /j D 2 .A/ Pt .A /.x/d.x/ A c
D 2 Œ.A/.A / E.A .A//.Pt .A / .A//
2 .A/.Ac / kA .A/k1 E jPt .A / .A/j :
30
1 The Conjectures
We use the hypothesis E jPt .A / .A/j
1 D1;1
kjrPt .A /jk1 :
Since E Pt .A / D .A/ and rPt .A .A// D rPt .A /; we have 1 kjrPt .A /jk1 p kPt A .A/k1 2t 1 p kA .A/k1 : 2t Hence, we have p 1 2t C .A/ 2 .A/.Ac / p kA .A/k21 2tD1;1 ! 1 c 2 .A/.A / p : 2tD1;1 Choose
!
p 2t D 2.D1;1 .A/.Ac //1 and we get C .A/
1 1 D1;1 ..A/.Ac //2 D1;1 minf.A/2 ; .Ac /2 g: 2 8
In order to prove the second part we use the following argument. Let I .t/ be the isoperimetric profile, defined by I .t/ WD inffC .A/ W .A/ D tg, 0 t 1=2. It is well known that I .t/ is a concave function (see [14]). Then we deduce that, if 0 t 1=2, t D .1 2t/0 C 2t1=2 and so I .t/ 2tI
1 1 2tCD1;1 CD1;1 t: 2 4
Hence C .A/ CD1;1 .A/;
whenever .A/
Thus, by Theorem 1.1, we get E jrf j CD1;1 E jf Ef j: We can summarize the results in the following way
1 : 2
1.5 E. Milman’s Theorem
31
Theorem 1.11 Let be a full dimensional, log-concave probability on Rn . The following statements are equivalent: (i) Is./ > 0, i.e. C .A/ Is./ minf.A/; .Ac /g for any Borel set A Rn , (ii) There exist 1 p q 1 such that Dp;q > 0, i.e., Dp;q kf Ef kp k jrf j kq for every f 2 F , (iii) There exists a constant D > 0 such that fx 2 Rn W jf Ef j tg 2eDt for all t > 0, and any 1-Lipschitz integrable function f . Besides the following relations hold Is./ D1;1 D
Dp;q D1;1 CD1;1 Cp0 Dp0 ;q 0
for any 1 p q 1 and 1 p 0 q 0 1. Proof The only things left to prove here are that (ii) implies (iii) and (iii) implies (ii) for p D 1 and q D 1, which are standard. Let us summarize. • (ii) H) (iii): Assume that 0 < Dp;q for some 1 p q 1. Let f be a 1-Lipschitz integrable function, then Dp;q kf Ef kp k jrf j kq k jrf j k1 D 1: Thus, Dp;q D1;1 CD1;1 ; where C > 0 is an absolute constant. Using now Theorem 1.9, D1;1 CrDr;r and E jf Ef jr
.Cr/r r D1;1
32
1 The Conjectures
for all 1 r 1 and for any > 0 t
fx 2 Rn W jf Ef j tg e E e
jf ef j
:
Since E e
jf Ef j
1 X 1 D 1C E jf E f jr r rŠ rD1
1C
1 X rD1
Cr D2 .D1;1 /r
by taking D 2C =D1;1 , the result follows. • (iii) H) (ii): If f is 1-Lipschitz and integrable we have Z 1 Z ˚ n E jf E f j D x 2 R W jf .x/ E f j t dt 2 0
1
0
eDt dt D
2 : D
Hence, for general Lipschitz integrable functions we have E jf E f j
2 kjrf jk1 : D
Thus, D=2 D1;1 . Remark 1.4 E. Milman proved this remarkable result in the context of Riemannian manifolds with smooth convexity assumptions. Let us quote the general result. We say that “convexity conditions” are fulfilled if • .M; g/ is an n-dimensional (n 2) smooth complete oriented connected Riemannian manifold or .M; g/ D .Rn ; j j/, • d D e d volM , 2 C 2 .M / and as tensor fields on M Ricg C Hessg
0
or can be approximated in total variation by measures fm g so that .M; d; m / satisfy the convexity assumptions (d denotes the induced geodesic distance on .M; g/). Theorem 1.12 (E. Milman) Under the convexity assumptions, the following statements are equivalent • • • •
Cheeger’s isoperimetric inequality (with best constant D1;1 ), Poincaré’s inequality (with best constant D2;2 ), Exponential concentration inequality (with best constant D), First-moment concentration inequality (with best constant D1;1 ),
1.5 E. Milman’s Theorem
33
with the following relation between the constants: D1;1 D2;2 D D1;1 : Remark 1.5 The hierarchy D2;2 D1;1 =2 D Is./=2 (Cheeger’s isoperimetric inequality) was proved by Maz’ya [47] and Cheeger [20]. Remark 1.6 Buser [19] and Ledoux [44] proved D1;1 cD2;2 under smooth convexity assumptions. The fact that the constant c does not depend on the dimension is very remarkable. Remark 1.7 In the proof of E. Milman’s theorem two main facts, in which the smooth convexity assumptions are crucial, play a special role: the semigroup approach coming from Ledoux [45] and Bakry-Ledoux [3] and the fact that the isoperimetric profile I is concave on .0; 1/, due to the work of several authors: Bavard-Pansu [8], Bérard-Besson-Gallot, Gallot [33], Morgan-Johnson [52], Sternberg-Zumbrun [56], Kuwert [42], Bayle-Rosales [10], Bayle [9], Morgan [51], Bobkov [11]. Remark 1.8 The first-moment concentration inequality, i.e., D1;1 > 0, is clearly a-priori much weaker than exponential concentration. The equivalence with exponential concentration extends the well-known Khinchine-Kahane type inequalities in convexity theory (consequences of Borell’s lemma) stating that linear functional have comparable moments to 1-Lipschitz functions (see, for instance, [17, Lemma 3.1] or [50, Appendix III]). Remark 1.9 Using E. Milman’s result we have an easy proof that the spectral gap for any log-concave probability in Rn is finite. Indeed, let f be any Lipschitz, integrable function in L2 ./. Then, Z
Z
2
2
E jf E f j
jf .x/ f .y/jd.y/ Rn
Rn
Z
d.x/ Z jf .x/ f .y/j2 d.y/d.x/
(by Jensen’s inequality) Z
Rn
Z
Rn
jx yj2 d.y/d.x/
krf k1 Rn
Rn
D 2krf k1 E jxj2 : Thus, p 1 D2;1 CD2;2 D C 1 ./: 0< p 2E jxj2
34
1 The Conjectures
1.6 Kannan-Lovász-Simonovits Spectral Gap Conjecture In this section we introduce the Kannan-Lovász-Simonovits spectral gap conjecture. We prove a certain type of linear invariance, which leads us to focus only on isotropic log-concave probabilities. We present Kannan-Lovász-Simonovits and Bobkov’s bound for the spectral gap and see how Kannan-Lovázs-Simonovits bound is easily deduced from E. Milman’s result quoted before. Eventually in this section we compare the estimate of the moments of the Euclidean norm given by Paouris’s strong concentration result with the one given by the spectral gap. Kannan, Lovász and Simonovits posed the following conjecture (see [37]), concerning the constant in Cheeger’s isoperimetric inequality for log-concave probabilities: Conjecture 1.1 There exists an absolute constant C > 0 such that for any logconcave probability on Rn we have C .A/
C minf.A/; .Ac /g
for every A Rn Borel set. According to the preceding results this conjecture is equivalent to prove that the spectral gap in Poincaré’s inequality, 1 ./, is equivalent to the inverse of 2 : 1 ./
1 2
up to universal constants, i.e., the conjecture can be restated as Conjecture 1.2 There exists an absolute constant C > 0 such that for any logconcave probability on Rn we have Var f C 2 E jrf j2 for any locally Lipschitz f 2 L2 ./. Notice that if we denote by M D .E xi xj /ni;j D1 the covariance matrix of , then 2 D kM k`n2 !`n2 and if f .x/ D ha; xi is a linear function, then E f D 0, jrf j2 D jaj2 , and Var f D
n X i;j D1
ai aj E xi xj D hM a; ai jaj2 kM k`n2 !`n2 D 2 jrf j2 :
1.6 Kannan-Lovász-Simonovits Spectral Gap Conjecture
35
Hence, the linear functions verify the KLS conjecture trivially. Thus, proving the conjecture is the same as proving that these functions are extremal up to an absolute constant. It is well known that every centered probability measure with full dimensional support has a unique, up to orthogonal transformations, linear image ı T which is isotropic. In this case Conjecture 1.2 for isotropic probabilities becomes Var f C E jrf j2
(1.11)
for any locally Lipschitz f 2 L2 ./. The following lemma is just the chain rule of differential calculus Lemma 1.6 Conjecture 1.2 is “linear invariant” in the following sense: Let be a centered, log-concave probability on Rn such that Var f C1 E jrf j2 for any locally Lipschitz f 2 L2 ./. Then for any T 2 GL.n/, if we denote D ı T , we have Var f C1 kT 1 k2`n !`n E jrf j2 2
2
for any locally Lipschitz f 2 L2 ./. In particular, if we prove Conjecture 1.2 for isotropic log-concave measures, then Conjecture 1.2 is true any log-concave measure. Indeed, Proposition 1.1 Let be an isotropic, log-concave probability satisfying (1.11) and let D ı T . Then kT 1 k`n2 !`n2 D 2 :
(1.12)
Proof Assume that T 1 D VU where V; U 2 O.n/ and D Œ1 ; : : : ; n (i > 0) a diagonal map. Let 2 S n1 and fei gniD1 the canonical basis in Rn . Since D
n X
h; U ei iU ei ;
i D1
it is clear that ˇ n ˇ2 n ˇX ˇ X ˇ ˇ 1 2 jT j D ˇ h; U ei iU.U ei /ˇ D h; U ei i2 2i ˇ ˇ i D1
i D1
36
1 The Conjectures
and kT 1 k2op D sup jT 1 j2 D max 2i : i
2S n1
On the other hand, 2 D sup E hx; i2 D sup E hT 1 x; i2 2S n1
2S n1
D sup E hUx; i2 D sup E 2S n1
D sup 2S n1
D sup 2S n1
D sup 2S n1
D sup 2S n1
2S n1
X
n X hx; U ei ii hU ei ; i
!2
i D1
i j hU; ei ihU; ej iE hx; U ei ihx; U ej i
i;j
X
i j hU; ei ihU; ej iE xk xl hU ei ; ek ihU ej ; el i
i;j;k;l
X
i j hU; ei ihU; ej ihU ei ; ek ihU ej ; ek i
i;j;k
X
i j hU; ei ihU; ej ihU ei ; U ej i D sup 2S n1
i;j
X
2i hU; ei i2
i
D max 2i : i
Let us remark that if is general log-concave probability and D ı T then it is not clear whether 2 kT 1 kop 2 or not.
1.6.1 Kannan, Lovász and Simonovits and Bobkob Approach Besides the exponential and Gaussian vectors only a few examples are known to satisfy Conjecture 1.2. Kannan, Lovász and Simonovits proved Conjecture with the factor .E jxj/2 , instead of 2 (see [37]), using the localization method. They proved the following: Theorem 1.13 Let be a centered log-concave, probability on Rn . Then (i) For every A Rn we have C .A/ In particular, this shows that constant.
C minf.A/; .Ac /g: E jxj p 1 E jxj C , where C > 0 is an absolute
1.6 Kannan-Lovász-Simonovits Spectral Gap Conjecture
37
(ii) Furthermore, For every A Rn we have C .A/
C minf.A/; .Ac /g: infx0 E jx x0 j
(iii) Let be the uniform probability on a convex body K. For every x 2 K, consider K .x/ the length of the maximum interval centered in x and contained in K. Then for every A Rn we have C .A/
C minf.A/; .Ac /g: E K .x/
Remark 1.10 Notice that (i) and (ii) are equivalent, since E x D 0 and E jxj 2 inf E jx x0 j 2E jxj: x0
Also (i) is weaker than the conjecture since, 2 D sup E hx; i2 j jD1
E jxj2 .by Borell’s lemma) .E jxj/2 : Remark 1.11 It is clear how to deduce (ii) (and thus (i)) from E. Milman’s theorem. Indeed, let f 2 F , and x0 2 Rn . Then E jf E f j E jf f .x0 /j C jE f f .x0 /j 2E jf f .x0 /j 2k jrf j k1 E jx x0 j: Thus, p 1 D1;1 C 1 ./: 2E jx x0 j Remark 1.12 Also, we have that K .x/ diam K. Payne and Weinberger (see [54]) proved that if is the uniform probability on K p 1 ./
diam K
for convex bodies with smooth boundary. Thus, (iii) improves this estimate p
1 ./
C C E K .x/ diam K
38
1 The Conjectures
The inequality in (iii) gives the right estimate for the Euclidean ball, but not for p 1 the simplex. In the Euclidean ball with radius jB2n j n n, 14 .x/2 C jxj2 D 2 jB2n j n . Then Z
1
jB2n j n
r
E .x/ D 2
n1
0
njB2n j
q 2 jB2n j n r 2 dr C:
Very recently Bobkov and Cordero-Erausquin in [13], extended (iii) for any logconcave probability with density f and proved that for any 0 < ı < 1 C .A/
1 1ı minf.A/; .Ac /g; 64 E f;ı .x/
where f;ı .x/ is the supremum over all h such that p f .x C h/f .x h/ > ıf .x/: p Bobkov improved the estimate in KLS conjecture to 1 ./ .Var jxj2 /1=2 Ejxj (see [12]), where is the width of the thin-shell of (see Definition 1.2). Let us show Bobkov’s method, which improves the original method by Kannan, Lovász and Simonovits. Their approach is based on a localization lemma of Kannan and Lovász, which can be extended easily to the general log-concave probabilities. Lemma 1.7 Let ˛; ˇ > 0 and assume that ui , i D 1; 2, are non-negative upper semi-continuous and ui , i D 3; 4 non-negative lower-semicontinuous functions defined on Rn , such that for any segment L Rn and any affine function ` W L ! R ˛ Z
Z u1 e
`
ˇ u2 e
L
`
˛ Z
Z
u3 e
L
`
L
ˇ u4 e
`
:
L
Then Z
˛ Z
ˇ
u1 .x/dx Rn
u2 .x/dx Rn
˛ Z
Z
ˇ
u3 .x/dx Rn
u4 .x/dx
:
Rn
(see the proof in [37] and also in [32]). We apply the lemma in the following case: Take " > 0 and let A be an open Borel set in Rn , B D .A" /c D fx 2 Rn W d.x; A/ > "g. We take ˛ D ˇ D 1, u1 D A , u2 D B , u3 D .A[B/c and u4 D g any non-negative continuous function. on Rn . If the inequality .C / .A/.B/ "
Z gd
1.6 Kannan-Lovász-Simonovits Spectral Gap Conjecture
39
holds for any one-dimensional log-concave probability measure, then it holds for any n-dimensional log-concave probability measure on Rn . Now, letting " ! 0 and noting that 1 minfa; 1 ag a.1 a/ minfa; 1 ag 2
0a1
we get Corollary 1.1 Given a non-negative continuous function g on Rn , if Z minf.A/; .Ac /g C .A/
g.x/d.x/
for any Borel set A Rn and for any one-dimensional log-concave probability measure on Rn , then Z minf.A/; .Ac /g 2C .A/ g.x/d.x/ for any n-dimensional log-concave probability measure on Rn . In particular, according to Theorem 1.5, we have Corollary 1.2 Given a non-negative continuous function g on Rn , if Z g.x/ d.x/
p 3Var x
for any one-dimensional log-concave probability measure in Rn , then Z 2
g.x/ d.x/
1 Is./
for any n-dimensional log-concave probability measure in Rn . Theorem 1.14 If is a full-dimensional log-concave probability in Rn , then C Is./ p ; Var.jX j2 / where C > 0 is an absolute constant and X is a random vector in Rn distributed according to . ˇ1 ˇ Proof Let g.x/ D C ˇjxj2 ˛ 2 ˇ 2 , with C > 0 and ˛ 2 R to be fixed later. Any one-dimensional log-concave probability on Rn may be viewed as the distribution of a random vector a C , where a; 2 Rn are orthogonal, jj D 1 and is a real random variable with a log-concave distribution. We will use several times the
40
1 The Conjectures
following fact, extension of Borell’s inequality, proved by Bourgain (see [12, 18]): if Q.x/ is a polynomial in Rn of degree d , and is a log-concave probability on Rn then
E jQjp
p1
c.d; p/kQk0 D c.d; p/eE log jQj ;
p>0
with constants c.d; p/ depending only on d and p. Thus
E g
2
ˇ ˇ1 2 D C 2 E ˇjaj2 C 2 ˛ 2 ˇ 2 ˇ2 12 C 2 ˇˇ 2 E jaj C 2 ˛ 2 ˇ c 1 C2 Var 2 2 ; c
where we use that Var f D infa E jf aj2 for any function f . Then 2 C2 2 C2 1 1
E g k E 2 k2 D
.E 2 / 2 C .E 2 / 2 2 c c 2 1 1 C
.E 2 / 2 C .E 2 / 2 0 c
2
1 C .E 2 /1=2 0 C .E 2 / 2 D 0 c
C2 1 1
3 .E 2 / 2 C .E 2 / 2 2 2 c
C2 Var : c3
Hence, by the previous corollary and choosing a corresponding constant C we have that for any full-dimensional log-concave on Rn 1 1 C2 inf E jjxj2 ˛j 2 ˛ Is./ and 1 1 C2 .Var jxj2 / 4 : Is./
1.6 Kannan-Lovász-Simonovits Spectral Gap Conjecture
41
Using the function g.x/ D jxj we could get the result by KLS, which is weaker than the one by Bobkov, since Var jxj2 Ejxj4 and by Borell’s inequality we 1 obtain .Var jxj2 / 4 C E jxj. In the case of log-concave probabilities verifying the variance conjecture we obtain Var jxj2 C1 2 E jxj2 C n4 : Then 1 1 C 2 n 4 Is./ and the corresponding Poincare’s inequality is 1
Var f C n 2 2 E jrf j2 for any locally Lipschitz integrable function.
1.6.2 Concentration and Relation with Strong Paouris’s Estimate The next result shows the relation between Poincaré-type inequalities and thin-shell width and was established by Gromov and Milman. In particular, if KLS conjecture were true the mass in isotropic log-concave probabilities would be concentrated in a thin shell of constant width and depending with n as the central limit theorem suggests. Besides the convex bodies satisfying the KLS conjecture, this fact has only been proved for the isotropic unconditional bodies by Klartag (see [40]). Theorem 1.15 (See [34], or also [44], Theorem 3.1) Let be a probability on Rn (non-necessarily log-concave) with spectral gap 1 ./, then ˇ ˇ 1 p ˇ 1 ˇ 1 2 2 2 2ˇ ˇ x 2 R W ˇjxj E jxj ˇ > t E jxj2 2 2eCt 1 ./.Ejxj /
n
for all t > 0, where C > 0 is an absolute constant. Proof We use the results of Theorem 1.6. Note that as a corollary we have that p ˇ ˇ ˚ x 2 Rn W ˇjxj E jxjˇ > tE jxj C1 eC2 t 1 ./Ejxj
for all t > 0, where C1 ; C2 > 0 are absolute constants.
42
1 The Conjectures
In order to improve this estimate, let p 1. Then, by the triangle inequality, ˇ ˇ ˇ ˇp p1 ˇ ˇp p1 1 ˇ ˇ ˇ 2 1=2 ˇ 2 2ˇ ˇ ˇ ˇ E ˇjxj E jxj E jxj E jxj C ˇE jxj E jxj ˇ ˇ ˇ ˇ ˇ ˇˇ ˇ ˇ ˇp p1 ˇ ˇjxj2 E jxj2 ˇ ˇ ˇ E ˇjxj E jxjˇ C ˇˇE 1 ˇ ˇ jxj C E jxj2 2 ˇ
1 ˇ ˇp p1 Var jxj2 2 E ˇjxj E jxjˇ C 1 E jxj2 2
ˇp 1 ˇ C E ˇjxj E jxjˇ p C p : 1 ./ We compute ˇ ˇp E ˇjxj E jxjˇ D
Z
1
ˇ ˇ ˚ ptp1 x 2 Rn W ˇjxj E jxjˇ > t dt
0
Z
1
C1
pt
p1 C2
e
p
1 t
0
C1 .p C 1/ dt D p .C2 1 /p
Cp
p 1 ./
!p :
Then ˇ 1 ˇ ˇ 1 ˇp p Cp 2 2ˇ ˇ E ˇjxj E jxj ˇ p : 1 ./ Thus, by Markov’s inequality, for any ˛ > 0, 9 8 ˇˇ ˇ 1ˇ ˇ ˇ ˇ > ˆ ˇ ˇjxj.E jxj2 / 2 ˇ = < ˇ ˇ ˇ 1 ˇ t ˛ ˇˇjxj E jxj2 2 ˇˇ > ˛t e >1 > ˆ ; : ˇ ˇ ˇjxj.E jxj2 / 12 ˇ E e
˛
0
t
ˇ 1 ˇp 1 1 E ˇˇjxj E jxj2 2 ˇˇ X B C et @1 C A p pŠ ˛ pD1
2et : p 1 Taking ˛ D pC./ and t D C 1 1 ./.E jxj2 / 2 with C a constant big enough 1 the theorem holds.
1.6 Kannan-Lovász-Simonovits Spectral Gap Conjecture
43
Remark 1.13 (Relation with Paouris’ Concentration Estimate) If is a logconcave probability measure on Rn , by Borell’s lemma we know that
E jxjp
p1
1 C p E jxj2 2
8p 1;
where C > 0 is an absolute constant. Paouris’s concentration result states that, for general log-concave probabilities, 1 E jxjp p C
1 1 E jxj2 2 C sup E jhx; ijp p
! 8p 1;
2S n1
which implies 1 1 1 E jxjp p C E jxj2 2 C Cp sup E jhx; ij2 2 0
2S n1
1 2 1 p A C E jxj2 2 @1 C 1 E jxj2 2 for any p 1. Using the spectral gap, we achieve
E jxj
p
p1
ˇ 1 ˇ ˇ 1 ˇp p 1 2 2ˇ ˇ E ˇjxj E jxj ˇ C E jxj2 2 0 1 1 1 Cp A p C E jxj2 2 E jxj2 2 @1 C p 12 2 1 ./ 1 ./ E jxj Cp
for any p 1. If were isotropic we would have: by Borell’s estimate
E jxjp
p1
p Cp n
8p 1;
by Paouris’s estimate 1 p p p p ; C n 1C p E jxj n and, by using the spectral gap, ! 1 p Cp p p E jxj : n 1C p p 1 ./ n
44
1 The Conjectures
Hence, if Conjecture 1.2 were true we would have optimal reverse Hölder inequalities for the moments and concentration of the mass around a thin shell.
1.7 The Variance Conjecture This section is devoted to the introduction of the variance conjecture. We compare it with the thin-shell width related with the central limit problem for isotropic convex bodies. Next, we consider linear deformations of an isotropic probability measure and we give a random result for the variance conjecture when some extra conditions are satisfied. We present the square negative correlation property and how it is related to the variance conjecture. In this section we consider a weaker conjecture than the KLS conjecture: the variance conjecture. Its origin comes from [2] and the work of [16], where the authors only consider isotropic log-concave probabilities. Conjecture 1.3 Let be a log-concave probability on Rn then Var jxj2 C 2 E jxj2 ; where C > 0 is an absolute constant. This conjecture is nothing else than Conjecture 1.2 for the function f .x/ D jxj2 . When is isotropic the variance conjecture takes the form Var jxj2 C n:
(1.13)
This conjecture was considered by Bobkov and Koldobsky in the context of the Central Limit Problem for isotropic convex bodies (see [16]). It was conjectured before by Anttila, Ball and Perissinaki (see [2]) that, for an isotropic log-concave measure, jxj is highly concentrated in a thin shell more than the trivial bound Var jxj E jxj2 suggested. Let us introduce Definition 1.2 Let be a centered log-concave probability on Rn with fulldimensional support. The thin-shell width of is r D
ˇ ˇ 1 ˇ2 ˇ E ˇjxj .E jxj2 / 2 ˇ :
It is well known that Var jxj 2 2Var jxj:
1.7 The Variance Conjecture
45
Indeed ˇ ˇ ˇ 1 ˇ2 1 2 D E ˇˇjxj E jxj2 2 ˇˇ D 2E jxj2 2 E jxj2 2 E jxj D2
E jxj2
2
E jxj2 .E jxj/2 E jxj2 .E jxj/2 2 D 2 E jxj 1 1 E jxj2 C E jxj2 2 E jxj E jxj2 C E jxj2 2 E jxj
D 2 Var jxj
E jxj2 : 1 E jxj2 C E jxj2 2 E jxj
Both inequalities are clear using Hölder’s inequality. Actually, it is known (it will be proved in Sect. 1.7.1) that the variance conjecture is equivalent to the thin-shell width conjecture: Conjecture 1.4 There exists an absolute constant C such that for every log-concave probability C : It is also known (see [26]) that these two equivalent conjectures are stronger than the hyperplane conjecture, which states that every convex body of volume 1 has a hyperplane section of volume greater than some absolute constant. The best known (dimension-dependent) bound for log-concave isotropic prob1 abilities in Conjecture 1.4 was proved by Guédon and Milman with a factor n 3 1 instead of C , improving down to n 4 when is 2 (see [35]). This results gives better estimates than previous ones by Klartag (see [39]) and Fleury (see [31]). Theorem 1.16 (See [35], Theorem 1.1) Let be an isotropic, log-concave probability on Rn and T 2 GL.n/. Then 1
2
3 ıT 1 C kT k`3n !`n kT kHS : 2
2
1
If we take T D In then we get the bound n 3 . Applying (1.12) in Sect. 1.6 we know that kT k`n2 !`n2 D and also kT k2HS D E jTxj2 , since is isotropic and then
E jTxj2 D
X i
0 E @
X j
12 tij xj A D
X ij
Thus, we obtain 1 1 2 3 3 ıT 1 C ıT : 1 EıT 1 jxj
tij2 :
46
1 The Conjectures
The next proposition shows that, in order to prove the variance conjecture for a general centered log-concave probability measure, it is enough to prove it for symmetric log-concave probability measures. Proposition 1.2 Let us assume that for any symmetric log-concave probability measure on Rn , Var jxj2 C 2 E jxj2 : Then, for any centered log-concave probability measure on Rn , Var jxj2 2C 2 E jxj2 : Proof Let be a centered log-concave probability measure on Rn , with density d D eV .x/ dx. Consider the probability measure d D eV .x/ eV .x/ dx, where
denotes the convolution. is symmetric and for any function f we have E f .y/ D E˝ f .x1 x2 /: Then, for any 2 S n1 we have E hy; i2 D E˝ hx1 x2 ; i2 D E hx1 ; i2 C E hx2 ; i2 D 2E hx; i2 : Thus, 2 D 22 . Besides, E jyj2 D E˝ jx1 x2 j2 D E jx1 j2 C E jx2 j2 2E˝ hx1 ; x2 i D 2E jxj2 and E jyj4 D E˝ .jx1 j2 C jx2 j2 2hx1 ; x2 i/2 D E jx1 j4 C E jx2 j4 C 4E˝ hx1 ; x2 i2 C 2E˝ jx1 j2 jx2 j2 4E˝ jx1 j2 hx1 ; x2 i 4E˝ jx2 j2 hx1 ; x2 i x1 D 2E jxj4 C 4E˝ jx1 j2 h ; x2 i2 C 2.E jxj2 /2 : jx1 j Consequently, Var jyj2 D 2Var jxj2 C 4E˝ jx1 j2 h
x1 ; x2 i2 2Var jxj2 : jx1 j
By hypothesis, since is a symmetric log-concave probability measure on Rn Var jxj2
1 C Var jyj2 2 E jyj2 D 2C 2 E jxj2 : 2 2
1.7 The Variance Conjecture
47
First of all we begin by proving the following well-known result: Proposition 1.3 Let be a symmetric full dimensional isotropic log-concave probability on Rn . Then C p ; n where C > 0 is an absolute constant. The inequality is sharp and is attained when p is the uniform probability on nB2n . Proof We assume d.x/ D eV .x/ dx, where V is a smooth, even and convex function. The convexity of V implies that V .y/ V .x/ C hrV .x/; y xi
8x; y 2 Rn :
By taking y D x we get hrV .x/; xi 0
8x 2 Rn :
Define Z q.r/ D
njB2n j
eV .r / dn1 ./
8r 0:
S n1
It is clear that Z
1
r n1 q.r/dr:
1D 0
Since dq D njB2n j dr
Z eV .r / hrV .r/; idn1 ./ 0; S n1
q is non-increasing and limr!1 q.r/ D 0. Alternative argument: For every 2 S n1 , the convexity assumption implies that V .r1 /
r2 r1 r2 C r1 V .r2 / C V .r2 / maxfV .r2 /; V .r2 /g 2r2 2r2
whenever 0 < r1 < r2 . Then V .r1 / V .r2 / if V is even or is the uniform probability in a convex set K, since in this case 0 2 K and r2 2 K implies that r1 2 K.
48
1 The Conjectures
Then we can write Z
1
q.r/ D n r
p.s/ ds; sn
1 dq 0. Moreover where p.s/ D s n n ds Z s Z 1 Z 1 p.s/ p.s/ds D n n r n1 dr ds s 0 0 0 Z 1 Z 1 p.s/ n1 D r n n ds dr s 0 r Z 1 r n1 q.r/dr D 1: D 0
Let be a probability measure with density d.s/ D p.s/ds Z E jxj˛ D
Z
1
jxj˛ d.x/ D Rn Z 1
Z
r nC˛1 q.r/dr D 0
p.s/ r n n ds dr D s 0 r Z s Z 1 Z 1 p.s/ n D n n r nC˛1 dr ds D p.s/s ˛ ds s n C ˛ 0 0 0 n ˛ D E s : nC˛ 1
nC˛1
Since is isotropic, 2 n n E s 2 .E s/2 nC2 nC1 2 ! n n n 2 Var s C .E s/ D nC2 nC2 nC1
Var jxj D E jxj2 .E jxj/2 D
.E /2
n 1 D .E jxj/2 2 .n C 2/.n C 1/ n.n C 2/
(by Borell’s lemma)
C n
and the result follows. We remark that the result is also true if is the uniform probability on a convex body with barycenter the origin, since q.r/ is clearly non increasing.
1.7 The Variance Conjecture
49
If is an even, non-necessarily isotropic, log-concave probability with D ı T 1 , isotropic and T 2 GL.n/ we get
E jxj2 C n
12
C kT kHS Dp p : n n
1.7.1 Relation with the Thin-Shell Width Next, we prove the equivalence between the variance conjecture and the thin-shell width conjecture by general log-concave probabilities. Proposition 1.4 (See, for instance, [1]) Let be an isotropic log-concave probability on Rn . Let T 2 GL.n/ be any non-singular matrix. Consider the general log-concave probability D ı T 1 . Then 2
2
kT k`n !`n Var jyj2 2 2 2 C C C 2 : 1 2 E jyj2 kT k2HS
Proof The first inequality is clear, since ˇ ˇ2 ˇ 2 12 ˇ ˇ ˇ ˇ ˇ C .E jyj / ˇjyj ˇ 1 ˇ2 1 ˇ2 ˇ ˇ 2 D E ˇjyj .E jyj2 / 2 ˇ E ˇjyj .E jyj2 / 2 ˇ E jyj2 D
Var jyj2 : E jyj2
Let us now show the second inequality. Since E g D E .g ı T /, for some B > 0 to be chosen later, we have ˇ ˇ2 ˇ ˇ2 Var jyj2 D E ˇjTxj2 E jTxj2 ˇ D E ˇjTxj2 E jTxj2 ˇ ˇ ˇ2 CE ˇjTxj2 E jTxj2 ˇ
1
jTxj>B.E jTxj2 / 2
1
jTxjB.E jTxj2 / 2
:
The first term equals ˇ ˇ ˇ ˇ 1 ˇ2 ˇ 1 ˇ2 ˇ E ˇjTxj C .E jTxj2 / 2 ˇ ˇjTxj .E jTxj2 / 2 ˇ .1 C B/2 2 E jTxj2 :
1
jTxjB.E jTxj2 / 2
50
If B
1 The Conjectures p1 , 2
the second term verifies
ˇ ˇ2 E ˇjTxj2 E jTxj2 ˇ
1
jTxj>B.E jTxj2 / 2
E jTxj4
1
jTxj>B.E jTxj2 / 2
:
By Paouris’s strong estimate for isotropic log-concave probabilities (see [53]), there exists an absolute constant C such that 1
fjTxj > Ct.E jTxj2 / 2 g e
kT kHS n `n 2 !`2
t kT k
8t 1:
o n Choosing B D max C; p1 we have that the second term is bounded from 2 above by E jTxj4
1
1
fjTxj>B.E jTxj2 / 2 g
D B 4 .E jTxj2 /2 fjTxj > B.E jTxj2 / 2 g Z
1
CB 4 .E jTxj2 /2
1
4t 3 fjTxj > Bt.E jTxj2 / 2 gdt 1 kT k
B
4
kT k4`n !`n 2 2
HS kT k4HS kT k`n !` n 2 2 e 4 kT k`n !`n 2
Z CB 4 kT k4HS
2
1
4t 3 e
kT kHS n `n 2 !`2
t kT k
dt
1
C2 kT k4`n !`n : 2
2
Hence, we achieve 4
kT k`n !`n Var jTxj2 2 2 2 .1 C B/2 C C2 2 E jTxj kT k2HS C1 2 C C2 D
C1 2
C C2
kT k4`n !`n 2
2
kT k2HS kT k2`n !`n 2
kT k2HS
2
2 :
As a consequence of this proposition we obtain that Conjectures 1.3 and 1.4 are equivalent. Combining it with the estimate of given in Theorem 1.16 we obtain the following
1.7 The Variance Conjecture
51
Corollary 1.3 There exist absolute constants C1 ; C2 such that for every isotropic log-concave probability and any linear map T 2 GL.n/, if D ı T 1 , we have H) Var jyj2 .C1 a2 C C2 /2 E jyj2
a and
1
Var jyj2 b 2 E jyj2
H) b 2 :
Moreover, we have 1
C1 n 3
2
Var jyj2 C2 n 3 2 E jyj2 :
and
Proof The two implications are a direct consequence of the previous proposition and the fact that kT k`n2 !`n2 kT kHS . By Theorem 1.16 we have that 1
2
3 C kT k`3n !`n kT kHS : 2
2
Thus, by the previous proposition, 2
kT k`n !`n Var jyj2 2 2 2 C C C 2 1 2 E jyj2 kT k2HS 0 1 4 2 3 kT k`n !`n C B kT kHS 2 2 C 2 @ C A 4 2 kT k 3 HS kT k`n !`n 2
2
4 3
C 2
kT kHS 4 3 `n2 !`n2
2
C n 3 2 ;
kT k since kT k`n2 !`n2 kT kHS
p
nkT k`n2 !`n2 .
The next proposition shows that the variance conjecture implies strong concentration. Proposition 1.5 Let be a log-concave probability verifying the variance Conjecture 1.3 for a constant C > 0. Then 1
p .E jxj2 / 4 ˇ o nˇ C 0 t p ˇ 2 12 ˇ 2 12 ; ˇjxj .E jxj / ˇ > t.E jxj / 2e 1
where C 0 D C 4 C1 , with C1 an absolute constant.
8 t > 0;
52
1 The Conjectures
Proof Bobkov proved that for some absolute constant C2 > 0 p1 p 1 C2 p E jP .x/j d ; E jP .x/j d for any P .x/ a polynomial in n variables of degree d , p 1 and a log-concave probability (see [12]). Applying this result to P .x/ D jxj2 E jxj2 we obtain ˇ ˇ p p1 ˇ ˇ1 E ˇjxj2 E jxj2 ˇ 2 C2 p E ˇjxj2 E jxj2 ˇ 2 ˇ ˇ2 14 C2 p E ˇjxj2 E jxj2 ˇ 1
1
1
C2 C 4 p 2 .E jxj2 / 4 : Hence, there exists a numerical constant C3 , such that ˇ ˇ 2 ˇjxj E jxj2 ˇ1=2 1
1=2
2 1=4 4 E e C3 C .E jxj / 2
and then, by Markov’s inequality, ˇ nˇ o 1ˇ 1 ˇ ˇjxj .E jxj2 / 2 ˇ > t.E jxj2 / 2 ˇ ˇo nˇ ˇ 1 ˇ 1ˇ D ˇjxj2 E jxj2 ˇ > t.E jxj2 / 2 ˇjxj C .E jxj2 / 2 ˇ ˇ ˚ˇ ˇjxj2 E jxj2 ˇ > tE jxj2 8 0 19 0 ˇ ˇ1 1 1 < 2 14 ˇjxj2 E jxj2 ˇ 2 2 t .E jxj / = A > exp @ A D exp @ 1 1 1 1 1 ; : C3 C 4 2 .E jxj2 / 4 C3 C 4 2 1
p .E jxj2 / 4 C 0 t p : 2e In particular, using Theorem 1.16, we have Ct ˇ o nˇ ˇ 2 12 ˇ 2 12 ˇjxj .E jxj / ˇ > t.E jxj / 2e
1=2 .E jxj
2 1=4
/
1=2 n1=6
;
8 t > 0;
1.7 The Variance Conjecture
53
which is worse than the estimate achieved in the same Theorem 1.16 by the authors (see [35]) 1
.E jxj2 / 2 ˇ min.t 3 ; t/ C o nˇ 2 ˇ 2 12 ˇ 2 12 : ˇjxj .E jxj / ˇ > t.E jxj / C1 e
1.7.2 Linear Deformations Since the variance conjecture is not linearly invariant, we study its behavior under linear transformations, i.e., given a centered log-concave probability , we study the variance conjecture for the log-concave probability measure D ı T 1 , where T 2 GL.n/ (recall that E f D E f ı T for any integrable function). We prove, in particular, that if is an isotropic log-concave probability verifying (1.13), then the non-isotropic ı .T ı U /1 verifies the variance Conjecture 1.3 for a typical U 2 O.n/. Furthermore, if we restrict T by imposing conditions on the parameter ˛.T / defined below, we can prove that ı .T ı U /1 verifies Conjecture 1.3 for a random U , i.e., with high probability (see Proposition 1.7). Proposition 1.6 (See [1]) Let be a centered log-concave probability on Rn verifying Conjecture 1.3 with constant C1 and B the spectral condition number of its covariance matrix, i.e., B2 D
max 2S n1 E hx; i2 : min 2S n1 E hx; i2
Let T 2 GL.n/ be any linear transformation. If U is a random map uniformly distributed in O.n/ (with respect to the Haar probability measure ), then E Varı.T ıU /1 jxj2 CC 1 B 4 2ı.T ıu/1 Eı.T ıu/1 jxj2 for any u 2 O.n/, where C is an absolute constant. Proof The non-singular linear map T can be expressed as T D VU1 where V; U1 2 O.n/ and D Œ1 ; : : : ; n ( i > 0) is a diagonal map. Given fei gniD1 the canonical basis in Rn , we will identify every U 2 O.n/ with the orthonormal basis f i gniD1 such that U1 U i D ei for all i . Thus, by uniqueness of the Haar measure invariant under the action of O.n/, we have that for any integrable function F E F .U / D E F . 1 ; : : : ; n / Z Z Z ::: D S n1
S n1 \ ? 1
? S n1 \ ? 1 \\ n1
F . 1 ; : : : ; n /d0 . n / : : : dn1 . 1 /;
54
1 The Conjectures
? where dni . i / is the Haar probability measure on S n1 \ ? 1 \ \ i 1 . Then, n n X X hUx; ei i2 D 2i hx; i i2 , we have that since jTUxj2 D jUxj2 D i D1
i D1
E Varı.T ıU /1 jxj2 D E Var jTUxj2 D
n X
4i E .E hx; i i4 .E hx; i i2 /2 /
i D1
C
X
2i 2j E .E hx; i i2 hx; j i2 E hx; i i2 E hx; j i2 /:
i ¤j
Since for every i Z E .E hx; i i4 .E hx; i i2 /2 / E E hx; i i4 D E jxj4
he1 ; 1 i4 dn1 . 1 / S n1
D
3 E jxj4 ; n.n C 2/
and for every i ¤ j E .E hx; i i2 hx; j i2 E hx; i i2 Ehx; j i2 / 2 Z 2 Z x x 4 ; 1 ; 2 dn2 . 2 /dn1 . 1 / D E jxj jxj S n1 jxj S n1 \ ? 1 2 Z 2 Z x y ; 1 ; 2 dn2 . 2 /dn1 . 1 / E˝ jxj2 jyj2 jyj S n1 jxj S n1 \ ? 1 Z E jxj4 1 he1 ; 1 i4 dn1 . 1 / D n1 n S n1 !! 2 2 Z jxj2 jyj2 1 x y ; 1 ; 1 dn1 . 1 / E˝ n1 n jyj S n1 jxj E jxj4 1 3 D n 1 n n.n C 2/ !! 1 2 jxj2 jyj2 1 x y 2 E˝ ; ; n1 n n.n C 2/ n.n C 2/ jxj jyj
1.7 The Variance Conjecture
55
we have that X 3 4i E jxj4 n.n C 2/ n
E Var jTUxj2
i D1
0
E jxj4 .E jxj2 /2 C@ E˝ n.n C 2/
3 E jxj4 n.n C 2/
n X i D1
4i C
2jxj2 jyj2 .n 1/n.n C 2/
x y ; 1 jxj jyj
2 !! X
1 2i 2j A
i ¤j
Var jxj2 X 2 2 i j : n.n C 2/ i ¤j
Now, since for every 2 S n1 2 B2
E hx; i2 2
and satisfies the variance conjecture with constant C1 , we have Var jxj2 C1 2 E jxj2 C1 n4 and E jxj4 D Var jxj2 C .E jxj2 /2 C1 n4 C n2 4 : Hence, for any U 2 O.n/ and using the identification with an orthonormal basis f i gniD1 mentioned in the beginning of the proof, we have 2ı.T ıU /1 D sup E hTUx; i2 D sup E hUx; i2 max 2i E hx; i i2 2S n1
1i n
2S n1
and thus E Varı.T ıU /1 jxj2 CC 1 4
n X
4i C
i D1
CC 1 B 4
n X
CC1 4 X n
2i 2j
i ¤j
4i E hx; i i4
i D1
C
CC 1 B 4 X 2 2 i j E hx; i i2 E hx; j i2 : n i ¤j
By Borell’s lemma E hx; i i4 C.E hx; i i2 /2 :
56
1 The Conjectures
Consequently, E Varı.T ıU /1 jxj2
0
1 X 1 CC 1 B 4 max 2i E hx; i i2 @ 2i E hx; i i2 C 2j E hx; j i2 A 1i n n i D1 n X
i ¤j
CC 1 B 4 2ı.T ıU /1 Eı.T ıU /1 jxj2 : As a consequence of Markov’s inequality we obtain the following Corollary 1.4 Let be an isotropic, log-concave probability measure on Rn verifying the variance conjecture with constant C1 . There exists an absolute constant C such that the measure of the set of orthogonal operators U for which the probability ı .T ı U /1 verifies the variance conjecture with constant CC1 is greater than 12 . For a non-singular linear map T we introduce the parameter Pn i D1
4i
i D1
i
˛.T / D P n
14
kT k4 D ; 1 kT kHS 2 2
where fi gn1 are the singular values of T and kT k4 is the Schatten norm kT k4 D 1 Pn 1 4 4 . It is clear that n 4 ˛.T / < 1. The next proposition will prove that, i D1 i 1 whenever n˛ ˛.T / < 1, for 0 < ˛ < 14 or, even more, ˛.T /1 D o.n 4 /, the corollary above is true with high probability. Proposition 1.7 Let be an isotropic, log-concave probability on Rn verifying the variance conjecture with constant C1 . There exists an absolute constant C such that the measure of the set of orthogonal operators U for which the probability ı .T ı U /1 verifies the variance conjecture with constant CC 1 is greater than 1 C2 eC3 n˛.T /
4
whenever ˛.T /4 n 2. Proof We use the notation in Proposition 1.6. We consider the function F .U / D Varı.T ıU /1 jxj2 and we estimate its Lipschitz constant. If U1 ; U2 are two orthogonal transformations in SO.n/ D fU 2 O.n/ W det U D 1g, let f i g, fi g be two orthonormal basis such that U ı U1 i D U ı U2 i D ei , (1 i n). Then, since is isotropic, F .U1 / D E
n X i D1
!2 2i hx; i i2
n X i D1
!2 2i
1.7 The Variance Conjecture
57
and F .U1 /F .U2 / D E
n X
hx; i i2 C hx; i i2
2i
!
i D1
n X
2i
! 2 2 hx; i i hx; i i :
i D1
Hence, n X
jF .U1 / F .U2 /j
2i 2j E hx; i i2 C hx; i i2 hx; j i2 hx; j i2
i;j D1
and, using Cauchy-Schwartz, Borell’s and Minkowski’s inequalities, we have that jF .U1 / F .U2 /j
12 2 1 E jhx; j j ij2 2 2i 2j E hx; i i2 C hx; i i2 jhx; j C j ij2
n X i;j D1
C
n X
4 14 2i 2j j j j jj j C j j E hx; i i2 C hx; i i2
i;j D1
C
n X
2j j j j j
j D1
C
n X i D1
X
2i
i
! 2i
n X
! 12 0 @
4j
i D1
n X
1 12 j j j j2 A :
j D1
Thus, the Lipschitz constant of F is
LC
n X
1 12 !0 n X 2i @ 4j A D C ˛.T /2 kT k4HS :
i D1
j D1
Now, also from Proposition 1.6, we deduce that !
3E jxj4 1 E Varı.T ıU /1 jxj D n.n C 2/ i D1 0 1 X E jxj4 2 2A @ 1 C i j n.n C 2/ 2
n X
4i
i 6Dj
58
1 The Conjectures
1 0 n X X E jxj4 @3 D 4i C 2i 2j A kT k4HS n.n C 2/ i D1 i 6Dj
D
kT k4HS
! n X E jxj4 Ejxj4 4 1 C2 : i n.n C 2/ n.n C 2/ i D1
By putting together both estimates we obtain E Varı.T ıU /1 jxj2 1 L C ˛.T /4
E jxj4 2˛.T /2 Ejxj4 1 C 0; n.n C 2/ C n.n C 2/
since the variance is also 0. By Hölder’s inequality it is clear that E jxj4 n2 . Then 4 E jxj4 1 1 n 2 2 E jxj C 1 2˛.T /2 2˛.T / 2 2 n.n C 2/ ˛.T / n.n C 2/ n C 2 ˛.T / n C 2 1 2n˛.T /2 1 nC2 ˛.T /4 n C ˛.T /2 p whenever, for instance, ˛.T /4 n 2. Next we use the concentration of measure phenomena on the group SO.n/ (see [50]) and
E F .U / C2 n 1 L U 2 SO.n/I jF .U / E F .U /j > E F .U / C1 e 2
2
and we get the result (we note that computing E F .U / in O.n/ or in SO.n/ gives the same result by symmetry).
1.7.3 Square Negative Correlation Property The square negative correlation property appeared in [2] in the context of the central limit problem for convex bodies. Definition 1.3 Let be a centered log-concave probability on Rn and f i gniD1 an orthonormal basis of Rn . We say that satisfies the square negative correlation property with respect to f i gniD1 if for every i ¤ j E hx; i i2 hx; j i2 E hx; i i2 E hx; j i2 :
1.7 The Variance Conjecture
59
In [2], the authors showed that the uniform probability on Bpn satisfies the square negative correlation property with respect to the canonical basis of Rn . The same property was proved for the uniform probability on generalized Orlicz balls in [59], where it was also shown that this property does not hold in general, even in the class of the uniform probabilities on one-symmetric convex bodies. More recently, in [1] the authors proved that the class of probabilities uniformly distributed on the .n1/-dimensional orthogonal projection of the n-dimensional unit cube satisfy the negative square correlation property, with respect to every orthonormal basis. As far as we know this is the only known case of probabilities with this strong property. We will show these results in Chap. 2. Satisfying the negative square correlation property with respect to some orthonormal basis, implies verifying variance conjecture. Indeed, Proposition 1.8 Let be a log-concave probability on Rn satisfying the square negative correlation property with respect to the orthonormal basis . i /niD1 . Then satisfies the variance conjecture. Proof Since x D
n X hx; i i i , we have that, if verifies the square negative i D1
correlation property, Var jxj2 D
n X .E hx; i i4 .E hx; i i2 /2 / i D1
C
X .E hx; i i2 hx; j i2 E hx; i i2 E hx; j i2 / i ¤j
n X
E hx; i i4 (by Borell’s inequality)
i D1
n X
C.E hx; i i2 /2 C sup E hx; i i2 E jxj2 1i n
i D1
C 2 E jxj2 ; where C > 0 is an absolute constant. Even though verifying the variance conjecture is not equivalent to satisfying a square negative correlation property, the following lemma shows that it is equivalent to satisfying a “weak averaged square negative correlation” property with respect to one and every orthonormal basis. Lemma 1.8 Let be a centered log concave random vector on Rn . The following statements are equivalent (i) verifies the variance conjecture with constant C1 Var jxj2 C1 2 Ejxj2 ;
60
1 The Conjectures
(ii) satisfies the following “weak averaged square negative correlation” property with respect to some orthonormal basis f i gniD1 with constant C2 X
.E hx; i i2 hx; j i2 E hx; i i2 E hx; j i2 / C2 2 E jxj2 ;
i ¤j
(iii) satisfies the following “weak averaged square negative correlation” property with respect to every orthonormal basis f i gniD1 with constant C3 X .E hx; i i2 hx; j i2 E hx; i i2 E hx; j i2 / C3 2 E jxj2 : i ¤j
Besides, the following relation between the constants hold C2 C1 C2 C C
C3 C1 C3 C C;
with C an absolute constant. Proof For any orthonormal basis f i gniD1 we have Var jxj2 D
n X .E hx; i i4 .E hx; i i2 /2 / i D1
C
X
.E hx; i i2 hx; j i2 E hx; i i2 E hx; j i2 /:
i ¤j
Denoting by A. / the second term we have, using Borell’s lemma, that A. / Var jxj2 C 2 Ejxj2 C A. /; since A. / Var jxj2 A. / C
n X
E hx; i i4
i D1
A. / C C
n X
2 E hx; i i2
i D1
A. / C C 2 Ejxj2 : Hence, the equivalence is clear.
References
61
Since the square negative correlation property is stronger than the weak version, it is clear that if a log-concave probability satisfies the square negative correlation property with respect to an orthonormal basis f i gniD1 , then satisfies Conjecture 1.3. Moreover, some linear perturbations ı T 1 also verify Conjecture 1.3, whenever T D VU , with U; V 2 O.n/, U i D ei for all i and D Œ1 ; : : : ; n ( i > 0) a diagonal map. This fact will be deduced from the proof of the more general following statement: Proposition 1.9 Let be a centered log-concave probability measure on Rn satisfying the square negative correlation property with respect to any orthonormal basis, then Conjecture 1.3 holds for any linear image ı T 1 , T 2 GL.n/. Proof Let T D VU , with U; V 2 O.n/ and D Œ1 ; : : : ; n ( i > 0) a diagonal map. Let f i gniD1 be the orthonormal basis defined by U i D ei for all i . By the square negative correlation property VarıT 1 jxj2 D Var jTxj2 D C
X
n X
4i .E hx; i i4 .E hx; i i2 /2 /
i D1
2i 2j .E hx; i i2 hx; j i2
E hx; i i2 E hx; j i2 /
i ¤j
n X
4i .E hx; i i4 .E hx; i i2 /2 /
i D1
Thus, VarıT 1 jxj2 C
n X
4i .E hx; i i2 /2 C 2
i D1
D
n X
2i E hx; i i2
i D1
C 2 EıT 1 jxj2 :
References 1. D. Alonso-Gutiérrez, J. Bastero, The variance conjecture on some polytopes, in Asymptotic Geometric Analysis, Proceedings of the Fall 2010, Fields Institute Thematic Program (Springer, New York, 2013), pp. 1–20 2. M. Anttila, K. Ball, I. Perissinaki, The central limit problem for convex bodies. Trans. Am. Math. Soc. 355(12), 4723–4735 (2003) 3. D. Bakry, M. Ledoux, Lévy-Gromov’s isoperimetric inequality for an infinite-dimensional diffusion generator. Invent. Math. 123(2), 259–281 (1996) 4. K. Ball, V.H. Nguyen, Entropy jumps for random vectors with log-concave density and spectral gap. Stud. Math. 213(1), 81–96 (2012) 5. I. Bárány, Z. Füredi, Computing the volume is difficult, in Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pp. 442–447 (1986)
62
1 The Conjectures
6. F. Barthe, D. Cordero-Erausquin, Invariances in variance estimates. Proc. Lond. Math. Soc. (3) 106(1), 33–64 (2013) 7. F. Barthe, P. Wolff, Remarks on non-interacting conservative spin systems: The case of gamma distributions. Stoch. Process. Appl. 119, 2711–2723 (2009) 8. C. Bavard, P. Pansu, Sur le volume minimal de R2 . Ann. Sci. Ecole Norm. Sup. 19(4), 479–490 (1986) 9. V. Bayle, Propriétés de concavité du profil isopérimétrique et applications, PhD thesis, Institut Joseph Fourier, 2004 10. V. Bayle, C. Rosales, Some isoperimetric comparison theorems for convex bodies in Riemannian manifolds. Indiana Univ. Math. J. 54(5), 1371–1394 (2005) 11. S. Bobkov, Isoperimetric and analytic inequalities for log-concave probability measures. Ann. Probab. 27(4), 1903–1921 (1999) 12. S. Bobkov, On isoperimetric constants for log-concave probability distributions, in Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 1910 (Springer, Berlin, 2007), pp. 81–88 13. S. Bobkov, D. Cordero-Erausquin, KLS-type isoperimetric bounds for log-concave probability measures. to appear in Annali di Mat. 14. S. Bobkov, C. Houdré, Some Connections Between Isoperimetric and Sobolev-Type Inequalities. Memoirs of the American Mathematical Society, vol. 129(616) (American Mathematical Society, Providence, 1997) 15. S. Bobkov, C. Houdré, Isoperimetric constants for product probability measures. Ann. Probab. 25(1), 184–205 (1997) 16. S. Bobkov, A. Koldobsky, On the central limit property of convex bodies, in Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 1807 (Springer, Berlin, 2003), pp. 44–52 17. C. Borell, Convex measures on locally convex spaces. Ark. Math. 12, 239–252 (1974) 18. J. Bourgain, On the distribution of polynomials on high dimensional convex bodies, in Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 1469 (Springer, Berlin, 1991), pp. 127–137 19. P. Buser, A note on the isoperimetric constant. Ann. Sci. Ecole Norm. Sup. (4), 15(2), 213–230 (1982) 20. J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, in Problems in Analysis (Papers dedicated to Salomon Bochner, 1969) (Princeton University Press, Princeton, 1970), pp. 195–199 21. D. Cordero-Erausquin, M. Fradelizzi, B. Maurey, The (B) conjecture for the Gaussian measure of dilates of symmetric convex sets and related problems. J. Funct. Anal. 214, 410–427 (2004) 22. B. Cousins, S. Vempala, Gaussian cooling and an O .n3 / volume algorithm, arXiv:1409.6011v1 23. M.E. Dyer, A.E. Frieze, Computing the volume of convex bodies: a case where randomness provably helps, in Probabilistic Combinatorics and Its Applications, Proceedings of Symposia in Applied Mathematics, vol. 44, ed. by B. Bollobás (American Mathematical Society, Providence, 1992), pp. 123–170 24. M.E. Dyer, A.E. Frieze, R. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies. J. Assoc. Comput. Mach. 38(1), 1–17 (1991) 25. R. Eldan, Thin shell implies spectral gap up to polylog via stochastic localization scheme. Geom. Funct. Anal. 23, 532–569 (2013) 26. R. Eldan, B. Klartag, Approximately gaussian marginals and the hyperplane conjecture. Contemp. Math. 545, 55–68 (2011) 27. R. Eldan, B. Klartag, Dimensionality and the stability of the Brunn-Minkowski inequality. to appear in Ann. Sc. Norm. Sup. Pisa. 28. G. Elekes, A geometric inequality and the complexity of computing volume. Discrete Comput. Geom. 1, 289–292 (1986) 29. H. Federer, W. Fleming, Normal integral currents. Ann. Math. 72, 458–520 (1960)
References
63
30. B. Fleury, Concentration in a thin shell for log-concave measures. J. Func. Anal. 259, 832–841 (2010) 31. B. Fleury, Poincaré inequality in mean value for Gaussian polytopes. Probab. Theory Relat. Fields 152(1–2), 141–178 (2012) 32. M. Fradelizi, O. Guédon, The extreme points of subsets of s-concave probabilities and a geometric localization theorem. Adv. Math. 204(2), 509–529 (2006) 33. S. Gallot, Inégalités isopérimétriques et analytiques sur les variétés riemanniennes. Astérisque 163–164, 5–6, 31–91 (1988); 281 (1989). On the geometry of differentiable manifolds (Rome, 1986) 34. M. Gromov, V. Milman, Generalization of the spherical isoperimetric inequality to uniformly convex Banach spaces. Compos. Math. 62, 263–287 (1987) 35. O. Guédon, E. Milman, Interpolating thin-shell and sharp large-deviation estimates for isotropic log-concave measures. Geom. Funct. Anal. 21(5), 1043–1068 (2011) 36. N. Huet, Spectral gap for some invariant log-concave probability measures. Mathematika 57(1), 51–62 (2011) 37. R. Kannan, L. Lovász, M. Simonovits, Isoperimetric problems for convex bodies and a localization lemma. Discrete Comput. Geom. 13(3–4), 541–559 (1995) 38. A. Karzanov, L.G. Khachiyan, On the conductance of order Markov chains. Order 8, 7–15 (1991) 39. B. Klartag, Power-law estimates for the central limit theorem for convex sets. J. Funct. Anal. 245(1), 284–310 (2007) 40. B. Klartag, A Berry-Esseen type inequality for convex bodies with an unconditional basis. Probab. Theory Relat. Fields 145(1–2), 1–33 (2009) 41. B. Klartag, Poincaré Inequalities and Moment Maps. Ann. Fac. Sci. Toulouse Math. 22(1), 1–41 (2013) 42. E. Kuwert, Note on the isoperimetric profile of a convex body, in Geometric Analysis and Nonlinear Partial Differential Equations (Springer, Berlin, 2003), pp. 195–200 43. R. Latala, J.O. Wojtaszczyk, On the infimum convolution inequality. Stud. Math. 189(2), 147– 187 (2008) 44. M. Ledoux, A simple analytic proof of an inequality by P. Buser. Proc. Am. Math. Soc. 121(3), 951–959 (1994) 45. M. Ledoux, The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs, vol. 89 (American Mathematical Society, Providence, 2001) 46. L. Lovász, M. Simonovits, Mixing rates of Markov chains, an isoperimetric inequality, and computing the volume, in Proc. 31st Annual Symp. on Found. of Computer Science, IEEE Computer Soc., pp. 346–55 (1990) 47. V. Maz’ja, Classes of domains and embedding theorems for function spaces. Dokl. Akad. Nauk. SSSR 133, 527–530 (1960) 48. E. Milman, On the role of convexity in isoperimetry, spectral gap and concentration. Invent. Math. 177(1), 1–43 (2009) 49. E. Milman, On the role of convexity in functional and isoperimetric inequalities. Proc. Lond. Math. Soc. 99(3), 32–66 (2009) 50. V.D. Milman, G. Schechtman, Asymptotic Theory of Finite Dimensional Normed Spaces. Springer Lecture Notes in Mathematics, vol. 1200 (Springer, Berlin, 1986) 51. F. Morgan, The Levy-Gromov isoperimetric inequality in convex manifolds with boundary. J. Geom. Anal. 18, 1053–1057 (2008) 52. F. Morgan, D.L. Johnson, Some sharp isoperimetric theorems for Riemannian manifolds, Indiana Univ. Math. J. 49(3), 1017–1041 (2000) 53. G. Paouris, Concentration of mass on convex bodies. Geom. Funct. Anal. 16, 1021–1049 (2006) 54. L.E. Payne, H.F. Weinberger, An optimal Poincaré inequality for convex domains. Arch. Rational Mech. Anal. 5, 286–292 (1960) 55. S. Sodin, An isoperimetric inequality on the `p balls. Ann. Inst. H. Poincar é Probab. Statist. 44(2), 362–373 (2008)
64
1 The Conjectures
56. P. Sternberg, K. Zumbrun, On the connectivity of boundaries of sets minimizing perimeter subject to a volume constraint. Commun. Anal. Geom. 7(1), 199–220 (1999) 57. M. Talagrand, A new isoperimetric inequality and the concentration of measure phenomenon, in Geometric Aspects of Functional Analysis. Lecture notes in Mathematics, vol. 1469 (Springer, Berlin, 1991), pp. 94–124 58. S. Vempala, Recent progress and open problems in algorithmic convex geometry, in 30th International Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 8 (Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2010), pp. 42–64 59. J.O. Wojtaszczyk, The square negative correlation property for generalized Orlicz balls, in Geometric Aspects of Functional Analysis. Israel Seminar. Lecture Notes in Mathematics, vol. 1910 (Springer, Berlin, 2007), pp. 305–313
Chapter 2
Main Examples
We present in this chapter the main classes of log-concave probabilities that are known to verify the conjectures. First we present the main examples verifying the KLS conjecture. The square negative correlation property with respect to some orthonormal basis implies the variance conjecture. However, this property is not implied by verifying the KLS conjecture. We present some examples of probabilities that satisfy this property, even though we will have already shown that they verify the variance conjecture as a consequence of verifying the KLS conjecture. Then we present some other examples verifying the variance conjecture. They will have in common that they are uniform probabilities on projections of polytopes. Some of these examples verify a stronger square negative correlation property, i.e., they verify this property with respect to any orthonormal basis. Finally, we show some results on uniform probabilities on unconditional bodies which verify the variance conjecture and, up to a log n factor in the isotropic case, the KLS conjecture.
2.1 Tensorizing Examples Verifying KLS In this section we present the three classes of convex bodies for which the uniform probability on them verifies the KLS conjecture: spherically symmetric or revolution bodies, the `np balls, and the simplex. The common method used to prove these results is to represent the corresponding log-concave probability as a product of probabilities for which the KLS conjecture is verified. After that, as a fundamental tool, E. Milman’s result is applied.
© Springer International Publishing Switzerland 2015 D. Alonso-Gutiérrez, J. Bastero, Approaching the Kannan-Lovász-Simonovits and Variance Conjectures, Lecture Notes in Mathematics 2131, DOI 10.1007/978-3-319-13263-1_2
65
66
2 Main Examples
2.1.1 Revolution Bodies Bobkov confirmed the KLS conjecture for the class of spherically symmetric logconcave probabilities (see [7]) and N. Huet extended the result for revolution bodies (see [10]). Next we present a simplified version of this result. Theorem 2.1 Let W R RC ! RC be a smooth log-concave function such that @s .t; s/ 0 for all .t; s/ 2 R RC . If d.t; x/ D .t; jxj/ dtdx is an isotropic log-concave probability on R Rn , then Var f C for any 1-Lipschitz function f 2 L2 .R Rn ; /, where C > 0 is a positive absolute constant. Therefore, by Theorem 1.10, the KLS conjecture is true for this class of log-concave probabilities. Proof Using polar coordinates and integration by parts, we can consider d as a product probability in the following way: let f W R Rn ! R be an integrable function. Then Z Z Z Z 1 n f .t; x/d.t; x/ D njB2 j r n1 f .t; r/ .t; r/drdn1 ./dt RRn
R
S n1
0
(dn1 ./ is the uniform probability measure on S n1 ) Z Z D
njB2n j
Z
1
r R
Z Z D njB2n j
S n1
Z
n1
R
D njB2n j Z
0
Z
1
Z
0
R
S n1
s
r n1 f .t; r/drdsdn1 ./dt 0
1
B2n
0
@s .t; s/dsdrdn1 ./dt r
Z
1
s n @s .t; s/ Z
RRC
S n1
1
f .t; r/
@s .t; s/ Z Z
D
Z
un1 f .t; su/dudsdn1 ./dt 0
f .t; sz/s n @s .t; s/dzdsdt:
Denote d.t; s/ D jB2n js n @s .t; s/dsdt, which is a probability on R RC , and d˛.z/ the uniform probability on B2n . Then E f .t; x/ D E˝˛ F .t; s; z/; where F W R RC B2n ! R is defined by F .t; s; z/ D f .t; sz/. We are going to prove the result by tensorizing. Let f be a fixed 1-Lipschitz function f W R Rn ! R and F defined as above. We know (see Lemma 1.5) that Var f D Var˝˛ F E˝˛ Var F C E˝˛ Var˛ F:
2.1 Tensorizing Examples Verifying KLS
67
Fix .t; s/ 2 R RC . Since f is 1-Lipschtz, by Poincaré’s inequality in B2n (with respect to d˛), we have Var˛ f .t; sz/
C Cs2 E˛ jrz f .t; sz/j2 n n
and E˝˛ Var˛ F
C nC2 E s 2 D n n2
Z jxj2 d.t; x/ C; RRn
since is isotropic. In order to bound the first summand from above, fix z 2 B2n . We have to estimate Var f .t; sz/. Let g.t; s/ D f .t; sz/ a, a to be chosen later. Consider g1 D jgj, it is clear that k jrt;s g1 j k1 D k jrt;s gj k1 D k jrf j k1 1. We have Z 2
Var f .t; sz/ D Var g E g D
E g12
D
jB2n j
RRC
s n @s .t; s/g12 .t; s/dsdt
D (integrating by parts) Z D jB2n j .t; s/ nsn1 g12 .t; s/ C s n 2g1 .t; s/hrx f .t; sz/; zi dsdt RRC
Z jB2n j
n1
RRC
ns
2s 2 g .t; s/ g1 .t; s/ C 1 .t; s/ dsdt: n
Denoting by the log-concave probability on R2 given by d .t; s/ D jB2n jnsn1 RC .s/ .t; s/dtds we have Var f .t; sz/ E g 2 C
1=2 2 1=2 2 2 E .sg1 / E g 2 C E g 2 E s : n n
It is clear that E s 2 D E jxj2 n: Since is log-concave in R2 , we can apply the KLS bound and we obtain Var g C inf E j.t; s/ bj2 E jrgj2 C Var j.t; s/j D C.Var t C Var s/: b2R2
If we choose a D E f .t; s; z/ so that E g D 0 we get E g 2 D Var g C.Var t C Var s/:
68
2 Main Examples
It is clear that Var t E t 2 D E t 2 D 1: In order to compute Var s we use the following lemma by Bobkob: Lemma 2.1 Let be a positive random variable with density q.x/ D x n1 p.x/, where p.x/ is log-concave. Then Var
C .E /2 : n
Then, consider the positive random variable distributed on RC with density Z njB2n js n1
h.s/ D
.t; s/dt: R
It satisfies the conditions of the lemma, since by Prékopa’s theorem the marginals of log-concave functions are also log-concave. Hence Var s D Var
2 C C .E s/2 D E jxj C E jxj2 D C n n
and this finishes the proof of the Theorem. Proof (of Lemma 2.1) Let 0 < x; y and let z D
xCy . 2
x nC1 y n1
It is easy to prove that z 2n n
.n C 1/nC1 .n 1/n1
so we can apply Prékopa’s inequality to the functions w.z/ D
z n n
p.z/;
u.x/ D
x nC1
nC1 p.x/;
v.y/ D
y n1 p.y/: n1
Since 1
1
u.x/ 2 v.y/ 2 w
xCy 2
x; y > 0;
we obtain Z
12 Z
1
v.x/dx
u.x/dx 0
12
1 0
Z
1
w.x/dx: 0
2.1 Tensorizing Examples Verifying KLS
69
Hence Z
Z
1
1
x nC1 p.x/dx 0
0
Z 1 2 1 2 x n1 p.x/dx 1 C x n p.x/dx n 0
and the lemma holds.
2.1.2 The Simplex In this subsection we present the method given by F. Barthe and P. Wolff [5]. Theorem 2.2 The uniform probability on the simplex verifies the KLS conjecture (Conjecture 1.2). Proof We consider the following representation for the .n1/-dimensional simplex
n1 Rn
n1 D fx 2 Rn I xi 0;
n X
xi D 1g:
i D1
Let T W .0; 1/n ! n1 be the map given by T .x1 ; : : : ; xn / D
x1
Pn
i D1 xi
xn
; : : : ; Pn
i D1
xi
;
and S.x1 ; : : : ; xn / D
n X
xi :
i D1
Let us also call d.t/ D et .0;1/ .t/dt, which is a log-concave probability on R. The product probability n is also log-concave in Rn . We define .A/ D n .T 1 .A// for each Borel set A n1 . is then the uniform probability on n1 . Indeed, Z fxITx2Ag .x/e
.A/ D .0;1/n
Pn 1
xi
dx1 : : : dxn :
70
2 Main Examples
Changing variables yi D xi , (1 i n 1) and yn D
n X
xi , we have
i D1
Z
1
.A/ D 0
eyn jB.yn /jn1 dyn1 ;
where ( B.yn / D .y1 ; : : : ; yn1 / 2
Rn1 C
W
n1 X
yi yn ; .y1 ; : : : ; yn1 ; yn
i D1
n1 X
) yi / 2 yn A
i D1
and ˇ( )ˇ n1 n1 ˇ ˇ X X ˇ ˇ jB.yn /jn1 D ynn1 ˇ .z1 ; : : : ; zn1 / 2 Rn1 W zi 1I .z1 ; : : : ; zn1 ; 1 zi / 2 A ˇ ˇ ˇ iD1
D
ynn1
iD1
n1
p n jAjn1 ;
which implies that .A/ D
jAjn1 : j jn1
P Let H be the affine hyperplane H D fx 2 Rn I niD1 xi D 1g n1 . Consider in H the Euclidean structure endowed by the one in Rn , with the origin in the barycenter of n1 . Since the gradient in Rn is invariant under orthogonal transformations, we assume that rRn D rH ˚ @N , where N D p1n ; : : : ; p1n . p n
1
n
n1 is isotropic with n1 1. Thus, j n1 jn1 and since j jn1 D .n1/Š 1 we have that n . Consequently, in order to prove Conjecture 1.2, we need to establish the following inequality:
Z
n1
ˇ Z ˇ ˇg.x/ ˇ
ˇ Z ˇ C ˇ g.x/d.x/ˇ d.x/ jrH g.x/j d.x/ n n1
n1
for any g 2 F . Since n is log-concave, we have, by Theorem 1.7, Z RnC
ˇ ˇ Z Z ˇ ˇ ˇ ˇ n f .x/d .x/ˇ dn .x/ C jrf .x/jdn .x/ ˇf .x/ n n ˇ ˇ R R C
C
2.1 Tensorizing Examples Verifying KLS
71
for any f 2 Fn . Thus, taking f .x/ D g.T .x// and denoting by JT.x/ the Jacobian matrix of T at x we have ˇ ˇ Z Z Z ˇ ˇ ˇg.x/ ˇ g.x/ˇ d.x/ C jrRn f .x/jdn .x/ ˇ
n1
n1
Z
RnC
DC Z
RnC
C Z
RnC
DC RnC
jrRn g.Tx/ JT.x/jdn .x/ jrRn g.Tx/j kJT.x/k`n2 !`n2 dn .x/ jrH g.Tx/j kJT.x/k`n2 !`n2 dn .x/ Z
C k jrgj k1
RnC
Thus, by Theorem 1.10, ˇ ˇ Z Z Z ˇ ˇ ˇg.x/ ˇ d.x/ C k jrgj k1 g.x/ ˇ ˇ
n1
RnC
n1
kJT.x/k`n2 !`n2 dn .x/:
kJT.x/k`n2 !`n2 dn .x/:
We need to estimate the second integral. JT.x/ D Pn
1
i D1 xi
.I .1; : : : ; 1/ ˝ T .x// ;
where .1; : : : ; 1/ ˝ T .x/ is the matrix associated to the linear map .1; : : : ; 1/ ˝ T .x/.y/ D
n X
yi T .x/:
i D1
Then kJT.x/k`n2 !`n2
p p 1 C n jTxj 1 C n jTxj Pn : D S.x/ i D1 xi
It is known that if X1 ; : : : ; Xn are independent random variables distributed according to , then the random vector T .X / D T .X1 ; : : : ; Xn / and the random variable S.X / D S.X1 ; : : : ; Xn / are independent [6]. Thus,
Z RnC
p 1 .1 C n jT .X /j/ S.X / p 1 .1 C n En jT .X /j/: D En S.X /
kJT.x/k`n2 !`n2 dn .x/ En
72
2 Main Examples
In order to compute En S.X /1 D Gamma distributions, En S.X /
we can proceed, by using properties of
ˇ( )ˇ n1 ˇ X eyn ˇˇ ˇ n1 D yi yn ˇ dyn ˇ y 2 RC W ˇ ˇ y n 0 i D1 n1 Z 1 1 D ynn2 eyn dyn .n 1/Š 0 Z
1
1 n1
D
1
1 .n 2/Š D : .n 1/Š n1
Besides,
En jT .X /j En jT .X /j D
2
12
D
En jT .x/j2 S.X /2 / En .S.X /2 /
12
r P 12 1 En niD1 Xi2 2 2 2n Pn : D D En . i D1 Xi /2 n.n C 1/ nC1
Consequently, Z RnC
kJT.x/k`n2 !`n2 dn .x/
C n
and we obtain the result.
2.1.3 The `pn -Balls First of all we remark that the case of the uniform probability on the `np -balls (1 p 2) was proved by A. Sodin (see [19], which is based in the previous work by Schetmann-Zinn [18]). Sodin gave sharp estimates for the isoperimetric profile of such a probabilities, which implies the best estimate for Cheeger’s inequality. The case 2 p 1 was proved by Latała–Wojtaszczyk, who established the infimum convolution inequality for these balls [14]. In the case 1 p 2, the approach here is different from the one by Sodin. We will use Barthe and Wolff’s method, who follow the same lines as in the case of the simplex, using the strong result by E. Milman, Theorem 1.10. When p > 2 we simplify the method developed by Latała–Wojtaszczyk [14], using again E. Milman’s result.
2.1 Tensorizing Examples Verifying KLS
73
Theorem 2.3 Let be uniform probability measure on the `np -ball, 1 p 1. Then satisfies the KLS conjecture (Conjecture 1.2). Proof Let X D .X1 ; : : : ; XnC1 / be a random vector in RnC1 , where Xi , 1 i n are independent random variables distributed according to the probability measure p
d1 .t/ D
ejt j dt 2 .1 C p1 /
and XnC1 is independent of X1 ; ; : : : ; Xn and is distributed according to p
d2 .t/ D ptp1 et .0;1/ .t/dt: Thus, X is distributed on Rn according to d D dn1 ˝ d2 . Let S D 1 P nC1 p p jX j and T W RnC1 n f0g ! Rn defined by i i D1 T .x/ D
.x1 ; : : : ; xn / : k.x1 ; : : : ; xnC1 /kp
The following statements are well known: (i) The random vector T .X / is uniformly distributed on Bpn . X (ii) The random variable S and the random vector are independent (see [6]). kX kp Let us denote by C1 and C2 the constants in the one-dimensional Poincaré’s inequalities for 1 and 2 . Since 1 and 2 are log-concave and one-dimensional, maxfC1 ; C2 g C , where C is an absolute constant. If g W Bpn ! R is locally Lipschitz and f D g ı T we have, by Lemma 1.5, E jg Egj2 D E jf E f j2 maxfC1 ; C2 gE jrf .X /j2 C kjrgj k21 E kJT.X /k2nC1 `2
!`n2
:
Thus, we need to estimate the last expectation. 1 JT.x/ D kxkp p1
p1
.I j0/
.x1
p1
; : : : ; xnC1 / p
kxkp
! ˝ .x1 ; : : : ; xn / ;
where xi denotes here jxi jp1 sgn xi and .I j0/ is the n .n C 1/ matrix formed by the identity and a column of zeroes and u˝v is the matrix associated to the linear
74
2 Main Examples
map u ˝ v.y/ D hu; yiv for any u; y 2 RnC1 , v 2 Rn . Thus, denoting by x p1 the p1 p1 vector .x1 ; : : : ; xnC1 /, we have jx p1 j 1C j.x ; : : : ; x /j 1 n p kxkp ! jx p1 j 1 1 C jT .x/j : D p1 kxkp kxkp
kJT.x/k`nC1 !`n 2
2
1 kxkp
If 1 p 2, this last quantity is bounded from above by 1 1 1 1 C .n C 1/ p 2 jT .x/j kxkp Consequently, if 1 p 2, E kJT.X /k2nC1 `2
1
!`n2
1
p 2 jT .X /j/2 E kX k2 p E .1 C .n C 1/
2=p E .jT .X /j2 kX k2p / 2 2E kX kpp 1 C .n C 1/ p 1 E kX k2p 0 1 p2 2 2 nE X 1 1 @1 C .n C 1/ p 1 A: D 2E kX kpp p p2 E kX kp
!
Since the variables jXi jp are distributed as a Gamma distribution with parameter 1 i n and 1 for i D n C 1, we have that kX kp is distributed as a Gamma distribution of parameter 1 C pn . Hence, 1 , p
0 1 n 1 C n2 1 C 2 p p @1 C .n C 1/ p 1 nEX12 A E kJT.X /k2`n !`n 2 2 2 1 C pn 1 C nC2 p 2
Cn p since, by Stirling’s formula, 1 C pn 2 np : 1 C n2 p
2.1 Tensorizing Examples Verifying KLS
75
If p > 2 we proceed like in [14], Sect. 5. It is easy to see that Z
1
p
er r n1 dr D 0
1 p
n : p
(2.1)
The function f W Œ0; 1/ ! Œ0; 1/ defined by p
n p
Z
s
Z
p
f .s/
er r n1 dr D
0
nrn1 dr D f .s/n 0
transports the probability on Œ0; 1/ with density
p p er r n1 dr n p
onto the proba-
bility on Œ0; 1 with density nrn1 dr. Consequently, it is clear that the map T W Rn ! Rn defined by Tx D
x f .kxkp / kxkp
transports the product probability n1 on Rn with density p 1 dn1 .x/ D n ekxkp dx 2 1 C p1
onto the uniform probability on the unit ball Bpn . In a similar way, consider the map W W Rn ! Rn defined by W .x/ D .'.x1 /; : : : ; '.xn //, where the function ' is defined by 1 2
Z
1
ejt j dt D x
1 2 1 C p1
Z
1
p
ejt j dt;
x 2 R:
(2.2)
'.x/
It is clear that W transports the exponential probability on Rn , (case p D 1), onto n1 . Hence, the map S D T ı W W Rn ! Rn transports the exponential probability on Rn onto the uniform probability on the unit ball Bpn , . Therefore, if g W Bpn ! R is a Lipschitz integrable map with respect to we have ˇ2 ˇ E jg E gj2 D E ˇg ı S E g ı S ˇ C E jr.g ı S /j2 C k jrgj k21 E kJSk2`n !`n : 2
2
76
2 Main Examples
Differentiating we obtain ıi;j ' 0 .xi / .@S /j D f .kWxkp / @xi kWxkp '.xj / @kWxkp 1 f 0 .kWxkp / C : kWxkp kWxkp @xi Since (2.1) and (2.2) imply p
f 0 .s/ D
1 s n1 es n1 1 C pn f .s/
and ' 0 .t/ D
1 j'.t /jp jt j e 1C p
respectively, we have ıi;j ' 0 .xi /f .s/ .@S /j C ˛.s/'.xj /ˇ.xi /; D @xi s where s D kWxkp ˛.s/ D
1 s pC1
.sf 0 .s/ f .s//
ˇ.t/ D j'.t/jp1 ' 0 .t/sgn'.t/: Then,
kJSk`n2 !`n2
n X f .s/ 0 max j' .xi /j C j˛.s/j ˇ 2 .xi / i s i D1
! 12 jWxj:
In order to get an estimate of this quantity we will use the following two lemmas whose proof is written below Lemma 2.2 The function ' verifies the following: (i) j' 0 .t/j 1, for all t 2 R. (ii) j'.t/jp1 j' 0 .t/j 1=p, for all t 2 R.
2.1 Tensorizing Examples Verifying KLS
77
Lemma 2.3 The function f verifies the following: (i) For any s > 0, p
e
sn
1 n n f .s/ 1: 1C p s
(ii) For any s > 0, f .s/ f .s/ f 0 .s/ minf1; 2psp =ng: s s
0< Then kJSk`n2 !`n2
o n 2psp 1 f .s/ min 1; n n 2 12 p1 f .s/ C n s s s sp p n f .s/ p1 1 C sn min ;2 D s psp n n o 1 1 f .s/ f .s/ Cn p 1 C 2sn p min p ; 1 3 s s s
and we get the result. Proof (of Lemma 2.2) We may assume t > 0, since ' is odd by definition. (i) From the definition of ' we have that Z e
t
D
e
x
x p dx '.t / e R1 p x dx 0 e
dx D
t
R1
Z
u '.t /p e du R1 u 0 e du
R1
R1
1
1
'.t /p
D R 1 0
1
u p 1 eu du 1
u p 1 eu du p
ex dx D e'.t / :
D '.t /p
Hence, '.t/p t and then 1 '.t /p t 1 ' 0 .t/ D 1 C e 1: 1C p p (ii) Denote by y D '.t/, t D ' 1 .y/. We have that Z e
t
1
D
e t
x
dx D
1C
1 p1 py 1 C p1
Z
1
Z
1 p
p
ex dx y p
1
px y
1
p1 x p
e
ey : dx D pyp1 1 C p1
78
2 Main Examples
Then p j'.t/jp1 j' 0 .t/j D '.t/p1 1 C p1 e'.t / t p1 : Proof (of Lemma 2.3) (i) Since Z
p
s
s n es n
Z
p
s
r n1 er dr
0
nrn1 dr D s n 0
we have that p
s n es
n p
n f n .s/ s n ; p
which implies (i). (ii) According to (2.1), it is clear that p
0<
Thus, 0
f .s/ s
es sf 0 .s/ sn D 1: n f .s/ 1 C pn f .s/
f 0 .s/
1 f .s/n p
f .s/ . s
Therefore,
Z s Z p 1 s pn 1 u n p D er r n1 dr D u e du: p p 0 0
By a simple differentiation argument we can check that Z
x
u
2x 1 x q e du e x 1 C q q
q1 u
0
whenever 0 x q2 . Thus, p
pes s n 1 sf 0 .s/ D p f .s/ nf .s/n pn 1 C 2 sp n whenever s p
n 2p .
Hence, when s p
n 2p ,
we also have
sf 0 .s/ f .s/ 1 f .s/ 2psp f .s/ f .s/ 0 f .s/ D : 1 1 p p s s f .s/ s 1 C 2ns s n
2.2 Examples Verifying the Square Negative Correlation Property
79
2.2 Examples Verifying the Square Negative Correlation Property In this section we show the proof given in [2] of the fact that the uniform probability measure on Bpn satisfies the square negative correlation property and the extension of this fact to the uniform probability measure on generalized Orlicz balls, shown in [20]. As discussed in Sect. 1.7.3, this property implies the variance conjecture. In the next section, we will give another example of measures verifying the square negative correlation property. Namely, the uniform probability measure on n hyperplane projections of B1 .
2.2.1 The `pn -Balls In this section we prove the following: Theorem 2.4 Let be the uniform probability measure on Bpn . Then, for any i ¤ j E hx; ei i2 hx; ej i2 E hx; ei i2 E hx; ej i2 : Proof We can assume without loss of generality that i D 1; j D 2. Since Z 1Z 1 • E hx; e1 i2 hx; e2 i2 D 4 t1 t2 fjx1 j t1 ; jx2 j t2 gdt2 dt1 , 0 0 Z 1 • E hx; e1 i2 D 2 t1 fjx1 j t1 gdt1 , and Z0 1 • E hx; e2 i2 D 2 t2 fjx2 j t2 gdt2 , 0
it is enough to show that for any t1 ; t2 0 we have fx 2 Bpn W jx1 j t1 ; jx2 j t2 g fx 2 Bpn W jx1 j t1 gfx 2 Bpn W jx2 j t2 g: Notice that for any increasing function f W Œ0; 1 ! R and any measure , we have that for every s 2 .0; 1 1 Œ0; s
Z
s 0
1 f .u/d.u/ Œ0; 1
Z
1
f .u/d.u/: 0
80
2 Main Examples
Thus, taking • f .u/ D
jfx 2 Bpn W jx1 j D 1 u; jx2 j t2 gjn1
jfx 2 Bpn W jx1 j D 1 ugjn1 jfx 2 Bpn W jx1 j D 1 ugjn1 • d.u/ D du, and jBpn jn • s D 1 t1 ,
,
we have that p
1
p
1
• f is increasing, since f .u/ D 0 for 0 u 1.1t2 / p and for 1.1t2 / p u<1 jfx 2 Bpn W
jx1 j D 1 u; jx2 j t2 gjn1 ˇn oˇ 1 ˇ ˇ D 2 ˇ y 2 .1 .1 u/p / p Bpn1 W jy2 j t2 ˇ Z D 4jBpn2 jn2
n1
1 .1.1u/p / p
.1 .1 u/p t p / t2
D 4jBpn2 jn2 .1 .1 u/p /
n1 p
Z
n2 p
1
.1 s p /
t2
1 .1.1u/p / p
p
1
and so, if 1 .1 t2 / p u < 1, Z f .u/ D
1 t2 .1.1u/p /1=p
Z
.1 s p /
n2 p
ds ;
1 p
.1 s /
n2 p
ds
0
which Z s is clearly increasing, • f .u/d.u/ D fx 2 Bpn W jx1 j t1 ; jx2 j t2 g, 0
• .Œ0; s/ D fx 2 Bpn W jx1 j t1 g, Z 1 Z 1 jfx 2 Bpn W jx1 j D 1 u; jx2 j t2 gjn1 f .u/d.u/ D du D • jBpn jn 0 0 D fx 2 Bpn W jx2 j t2 g, and • .Œ0; 1/ D 1, which completes the proof.
dt n2 p
ds
2.2 Examples Verifying the Square Negative Correlation Property
81
2.2.2 Generalized Orlicz Balls A generalized Orlicz ball is a convex body of the form ( n
KD x2R W
n X
) fi .jxi j/ 1 ;
i D1
where the functions ffi gniD1 are Young functions, i.e., fi W Œ0; 1/ ! Œ0; 1/ are increasing convex functions satisfying fi .0/ D 0. We are going to show that the uniform probability measure on an Orlicz ball satisfies the square negative correlation property with respect to the canonical basis fei gniD1 . This fact was proved by Wojtaszczyk in [20]: Theorem ˚2.5 Let P be the uniform probability measure on a generalized Orlicz ball K D x 2 Rn W niD1 fi .jxi j/ 1 . Then, for any i ¤ j E hx; ei i2 hx; ej i2 E hx; ei i2 E hx; ej i2 :
Proof We can assume without loss of generality that i D 1, j D 2. Let us consider the generalized Orlicz ball L Rn1 defined by the Young functions f˚i gin1 D1 , with ˚1 .t/ D t and ˚i .t/ D fi C1 .t/ for i D 2; : : : ; n 1. Calling, for any x 2 R, Lx D fy 2 Rn2 W .x; y/ 2 Lg we have, by Brunn–Minkowski inequality, that for any x; y 2 R and any 0 t 1 1t : jLtxC.1t /y jn2 jLx jtn2 jLy jn2
In particular, for any positive real numbers a; b; c we have that b
c
bCc bCc jLaCbCc jn2 and jLaCc jn2 jLa jn2 c
b
bCc bCc jLaCb jn2 jLa jn2 jLaCbCc jn2 :
Multiplying both inequalities we obtain jLaCc jn2 jLaCb jn2 jLa jn2 jLaCbCc jn2 :
(2.3)
82
2 Main Examples
Now, let us consider the generalized Orlicz ball K and for any .y; z/ 2 R2 let us call Ky;z D fw 2 Rn2 W .y; z; w/ 2 Kg and m.y; z/ D jKy;z jn2 . For any y > y > 0 and z > z > 0, let us take • a D f1 .y/ C f2 .z/, • b D f1 .y/ f1 .y/, and • c D f2 .z/ f2 .z/. Then La D Ky;z , LaCb D Ky;z , LaCc D Ky;z , and LaCbCc D Ky;z .
• • • •
Equation (2.3) gives that for any y > y > 0 and z > z > 0 m.y; z/m.y; z/ m.y; z/m.y; z/:
(2.4)
On the other hand, notice that for any function h of two variables a; b 2 A we can write Z Z Z 1 h.a; b/dbda D h.b; a/dbda D .h.a; b/ C h.b; a//dbda: 2 A2 A2 A2 Thus, for any functions f; g, using Fubini’s theorem Z
Z
Z
f .x1 /dx K
Z
g.x2 /dx D K
m.y; z/f .y/dydz Z
R2
Z
R4
m.y; z/g.z/d yd z R2
m.y; z/m.y; z/f .y/g.z/dydzdyd z
D D
m.y; z/m.y; z/f .y/g.z/dydzdyd z R4
D
1 2
Z m.y; z/m.y; z/.f .y/g.z/ C f .y/g.z//dydzdyd z: R4
Repeating the same trick, exchanging z and z and leaving y and y unchanged and we obtain Z Z Z 1 f .x1 /dx g.x2 /dx D .m.y; z/m.y; z/.f .y/g.z/ C f .y/g.z// 4 R4 K K Cm.y; z/m.y; z/.f .y/g.z/ C f .y/g.z///dydzdyd z:
2.2 Examples Verifying the Square Negative Correlation Property
83
We repeat the same operation and obtain Z
Z
Z
f .x1 /g.x2 /dx
dx D
K
m.y; z/m.y; z/f .y/g.z/dydzdyd z R4
K
D
1 4
Z .m.y; z/m.y; z/.f .y/g.z/ C f .y/g.z// R4
Cm.y; z/m.y; z/.f .y/g.z/ C f .y/g.z///dydzdyd z: Consequently, Z
Z
Z
f .x1 /g.x2 /dx K
1 D 4
Z
dx K
Z
f .x1 /dx
g.x2 /dx
K
K
.m.y; z/m.y; z/ m.y; z/m.y; z//.f .y/ f .y//.g.z/ g.z//dydzdyd z: R4
Notice that if we exchange y and y the integrand does not change and the same happens if we exchange z and z. Thus, Z
Z
Z
f .x1 /g.x2 /dx K
Z
dx
f .x1 /dx
K
Z
g.x2 /dx
K
K
.m.y; z/m.y; z/ m.y; z/m.y; z//
D fjyj>jyj;jzj>jzjg
.f .y/ f .y//.g.z/ g.z//dydzdyd z: Besides, if f and g are symmetric functions, since K is 1-unconditional Z
Z
Z
f .x1 /g.x2 /dx K
Z
Z
dx K
f .x1 /dx K
g.x2 /dx K
.m.y; z/m.y; z/ m.y; z/m.y; z//
D 16 fy>y>0;z>z>0g
.f .y/ f .y//.g.z/ g.z//dydzdyd z: Taking D g.x/ D x 2 , (2.4) gives that this integral is non-positive and dividing R f .x/ 2 by . K dx/ we obtain the result. Remark 2.1 The same proof (using Prékopa–Leindler’s inequality instead of Brunn–Minkowski’s) gives that any log-concave probability supported on a generalized Orlicz ball satisfies the square negative correlation property.
84
2 Main Examples
n 2.3 Orthogonal Projections of B1n and B1 and the Variance Conjecture
In this section we follow [1]. We are going to give some new examples of logconcave probability measures verifying the variance conjecture. We consider the family of the uniform probabilities on a hyperplane projection of some symmetric isotropic convex body K0 . These probabilities are not necessarily isotropic. However, as we will see in the next proposition, they are almost isotropic. i.e., the spectral condition number B of their covariance matrix verifies 1 B C , for some absolute constant C .
2.3.1 Hyperplane Projections of Isotropic Convex Bodies Proposition 2.1 Let K0 Rn be a symmetric isotropic convex body, and let H D ? be any hyperplane. Let K D PH K0 and the probability uniformly distributed on K. Then, for any 2 SH D fx 2 H I jxj D 1g we have E hx; i
Z
1
2
1C 2 jKjn n1
K
hx; i2 dx L2K0 :
Consequently, LK0 and B./ 1. 1 n1 1. Indeed, using Proof The first two expressions are equivalent, since jKjn1 Hensley’s result [9] and the best general known upper bound for the isotropy constant of an n-dimensional convex body [12], we have
1
1
n1 n1 jKjn1 jK0 \ H jn1
c LK0
1 n1
c
1 n1
c:
1
n4
On the other hand, since (see [17] for a proof) 1 jKjn1 jK0 \ H ? j1 jK0 jn D 1; n we have 1 n1 jKjn1
n 2r.K0 /
1 n1
n 2LK0
1 n1
1
.cn/ n1 c;
where we have used that r.K0 / D supfr W rBn2 K0 g cLK0 (see [11]).
n 2.3 Orthogonal Projections of B1n and B1 and the Variance Conjecture
85
Let us prove the last estimate. Let S.K0 / be the Steiner symmetrization of K0 with respect to the hyperplane H , which is the convex body 1 S.K0 / D y C t 2 PH .K0 / hi W jtj jK0 \ .y C hi/j1 2 and let S1 be its isotropic position. It is known (see [3] or [16]) that for any isotropic n-dimensional convex body L and any linear subspace E of codimension k 1 k jL \ Ejnk
LC ; LL
where C is a convex body in E ? . In particular, we have that jS1 \ H jn1
1 LS.K0 /
and jS1 \ H \ ? jn2
1 : L2S.K0 /
Since K0 is symmetric, S1 \ H is symmetric and thus centered. Then, by Hensley’s result [9] jS1 \ H j2n1 1 2 ? jS1 \ H jn1 jS1 \ H \ jn2 Z 1 hx; i2 dx; 2 1C n1 S \H 1 jS1 \ H jn1
L2S.K0 /
because jS1 \ H jn1
B
1 LS.K0 /
Z hx; i2 dx S1 \H
1 n1 and so jS1 \ H jn1 c.
E
1
n1 Q because, even But now, S1 \ H D jS1 \ H jn1 .S1 \ H / D S .K0 / \ H D K, though S.K0 / is not isotropic, S1 is obtained from S.K0 / multiplying it by some in H and by 11 in H ? . Thus, n1
Z L2S.K0 /
e
S1 \H
Z hx; i2 dx D
hx; i2 dx D KQ
and, since LS.K0 / LK0 , we obtain the result.
1 jKj
2 1C n1
Z hx; i2 dx K
86
2 Main Examples
2.3.2 Hyperplane Projections of the Cube The first examples we consider are uniform probability measures on hyperplane projections of the cube. We will see that these probability measures satisfy the negative square correlation property with respect to any orthonormal basis. Consequently, by Proposition 1.9, any linear image of these measures will verify the variance conjecture with an absolute constant. n n Theorem 2.6 Let 2 S n1 and let K D PH B1 be the projection of B1 on the ? hyperplane H D . If is the uniform probability measure on K then, for any two orthonormal vectors 1 ; 2 2 H , we have
E hx; 1 i2 hx; 2 i2 E hx; 1 i2 E hx; 2 i2 : Consequently, satisfies the square negative correlation property with respect to any orthonormal basis in H . n I yji j D sgn i g , i 2 f˙1; : : : ; ˙ng. Proof Let Fi denote the facet Fi D fy 2 B1 From Cauchy’s formula, it is clear that for any function f ˙n X jji j j E f .x/ D E.f .PH Y i //; 2kk1 i D˙1
where Y i is a random vector uniformly distributed on the facet Fi . Remark that jPH .Fi /jn1 D jh; eji j ijjFi jn1 D 2n1 jji j j for i D ˙1; : : : ; ˙n and jKjn1 D 2n1 kk1 . n For any unit vector 2 H , we have by isotropicity of the facets of B1 , ˙n ˙n n X X jji j j jji j j X 2 i 2 EhY i ; i2 D E
Y 2kk1 2kk1 j D1 j j i D˙1 i D˙1 0 1 n n ˙n X X j j j j 1 X 2 X jji j j 1 2 j i A D
EY i D
2j @ C 2 j D1 j kk1 j kk 3 kk 1 1 j D1
E hx; i2 D
i D˙1
D
n X j D1
2j
2jj j 1 C 3kk1 3
i 6Dj
2 X 2 jj j 1 C
: 3 3 j D1 j kk1 n
D
n 2.3 Orthogonal Projections of B1n and B1 and the Variance Conjecture
87
Consequently, E hx; 1 i2 E hx; 2 i2 2 X ji j 1 4 X ji1 jji2 j C . 1 .i /2 C 2 .i /2 / C
1 .i1 /2 2 .i2 /2 9 9 i D1 kk1 9 i ;i D1 kk21 n
D
n
1 2
2 1 C 9 9
n X i D1
ji j . 1 .i /2 C 2 .i /2 /: kk1
On the other hand, by symmetry, ˙n X jji j j E hx; 1 i hx; 2 i D EhY i ; 1 i2 hY i ; 2 i2 2kk1 2
2
i D˙1
D
˙n X i D˙1
jji j j 1 n1 j 2kk1 jB1 n1
Z n1 B1
.hy; Peji j 1 i C sgn.i / 1 .i //2
.hy; Peji j 2 i C sgn.i / 2 .i //2 dy Z n X ji j 1 D hy; Pe? 1 i2 hy; Pe? 2 i2 C 2 .i /2 hy; Pe? 1 i2 n1 j i i i n1 kk jB 1 n1 B 1 1 i D1 C 1 .i /2 hy; Pe? 2 i2 C 1 .i /2 2 .i /2 C 4 1 .i / 2 .i /hy; Pe? 1 ihy; Pe? 2 i dy i
n X
i
1 1
1 .i /2 jPe? 2 j2 C 2 .i /2 jPe? 1 j2 C 1 .i /2 2 .i /2 i i 3 3 i D1 Z 1 C4 1 .i / 2 .i / n1 hy; Pe? 1 ihy; Pe? 2 idy i i n1 jB1 jn1 B1 Z 1 hy; Pe? 1 i2 hy; Pe? 2 i2 dy C n1 i i n1 jB1 jn1 B1 n X ji j 1 1 1
1 .i /2 C 2 .i /2 C 1 .i /2 2 .i /2 D kk1 3 3 3 i D1 Z 1 C4 1 .i / 2 .i / n1 hy; Pe? 1 ihy; Pe? 2 idy i i n1 jB1 jn1 B1 Z 1 C n1 hy; Pe? 1 i2 hy; Pe? 2 i2 dy i i n1 jB1 jn1 B1 D
ji j kk1
i
88
2 Main Examples
Since Z
1 n1 j jB1 n1
n1 B1
n1 j jB1 n1
Z
n1 j jB1 n1
1X
D
3
0 @
i
X
@ n1 B1
1
D
i
0
Z
1
D
hy; Pe? 1 ihy; Pe? 2 idy 1 yl1 yl2 1 .l1 / 2 .l2 /A dy
l1 ;l2 ¤i
X
n1 B1
1
yl2 1 .l/ 2 .l/A dy
l¤i
1 .l/ 2 .l/
l¤i
1 .h 1 ; 2 i 1 .i / 2 .i // 3 1 D 1 .i / 2 .i /; 3 D
the previous sum equals n X i D1
1 1
1 .i /2 C 2 .i /2 1 .i /2 2 .i /2 3 3 Z 1 2 2 C hy; Pe? 1 i hy; Pe? 2 i dy : n1 j i i n1 jB1 n1 B1
ji j k k1
Now, Z
1 n1 j jB1 n1
D
D
Z
1 n1 j jB1 n1
X
2
X l1 ¤l2 .¤i /
D
1X 5
l¤i
hy; Pe? 1 i2 hy; Pe? 2 i2 dy i
0 @
n1 B1
1 .l/ 2 .l/
l¤i
C
n1 B1
i
X
1 yl1 yl2 yl3 yl4 1 .l1 / 1 .l2 / 2 .l3 / 2 .l4 /A dy
l1 ;l2 ;l3 ;l4
Z
1
2
n1 j jB1 n1
1
yl4 dy
Z
n1 j jB1 n1
1 .l/2 2 .l/2 C
n1 B1
n1 B1
1 9
yl21 yl22 dy. 1 .l1 /2 2 .l2 /2 C 1 .l1 / 1 .l2 / 2 .l1 / 2 .l2 //
X
. 1 .l1 /2 2 .l2 /2 C 1 .l1 / 1 .l2 / 2 .l1 / 2 .l2 //
l1 ¤l2 .¤i /
n 2.3 Orthogonal Projections of B1n and B1 and the Variance Conjecture
D
89
1X
1 .l/2 2 .l/2 5 l¤i
2 1 4X
1 .l/2 .1 2 .l/2 2 .i /2 / C 9 l¤i
C 1 .l/ 2 .l/.h 1 ; 2 i 1 .l/ 2 .l/ 1 .i / 2 .i // D
#
1X
1 .l/2 2 .l/2 5 l¤i
0 X 1@ C
1 .l/2 2 .l/2 2 .i /2 C 1 .i /2 2 .i /2 1 1 .i /2 9 l¤i
X
1
1 .l/2 2 .l/2 C 1 .i /2 2 .i /2 A
l¤i
D
1 2 1 X 1 1 1 .i /2 2 .i /2 C 1 .i /2 2 .i /2
1 .l/2 2 .l/2 : 9 9 9 9 45 l¤i
Consequently, 1 X ji j C 9 i D1 kk1 n
E hx; 1 i2 hx; 2 i2 D
2 2 7
1 .i /2 C 2 .i /2 1 .i /2 2 .i /2 9 9 9 1
1 X
1 .i /2 2 .l/2 A 45 l¤i
1 2 X ji j C . 1 .i /2 C 2 .i /2 /; 9 9 i D1 kk1 n
which concludes the proof. By Proposition 1.9 we obtain the following Corollary 2.1 There exists an absolute constant C such that for every hyperplane n H and any linear map T on H , if is the uniform probability distributed on PH B1 , then ı T 1 verifies the variance conjecture with constant C , i.e., VarıT 1 jxj2 C 2ıT 1 EıT 1 jxj2 :
90
2 Main Examples
2.3.3 Hyperplane Projections of the Cross-Polytope The next examples we consider are uniform measures on hyperplane projections of B1n . Even though in this case we are not able to prove that these measures satisfy a square negative correlation property, we are still able to show that they verify the variance conjecture with some absolute constant. Theorem 2.7 There exists an absolute constant C such that for every hyperplane H D ? the uniform probability measure on PH B1n , , verifies the variance conjecture with constant C , i.e., Var jxj2 C 2 E jxj2 :
Proof First of all, notice that by Proposition 2.1 we have that, for every 2 SH D S n1 \ H , 1
E hjB1n j n x; i2 L2B n 1 1
and so 2
1 n2
and
E jxj2
1 : n
C Thus, we have to prove that Var jxj2 3 . n By Cauchy’s formula, P denoting by the uniform probability measure on n1 D fy 2 Rn W yi 0; niD1 yi D 1g, P1 the probability measure on f1; 1gn given by j n1 jn1 jh"0 ; ij jh"0 ; ij D p jh"; ij 2 njPH .B1n /jn1 "2f1;1gn
P1 ."0 / D P
and, for " 2 f1; 1gn and x 2 Rn , "x D ."1 x1 ; : : : ; "n xn /; we have that Var jxj2 D E jxj4 .E jxj2 /2 D EP1 ˝ jPH ."y/j4 .EP1 ˝ jPH ."y/j2 /2 D EP1 ˝ .j"yj2 h"y; i2 /2 .EP1 ˝ .j"yj2 h"y; i2 //2 D EP1 ˝ .jyj2 hy; "i2 /2 .EP1 ˝ .jyj2 hy; "i2 //2 E jyj4 C EP1 ˝ h"y; i4 .E jyj2 EP1 ˝ h"y; i2 /2 :
n 2.3 Orthogonal Projections of B1n and B1 and the Variance Conjecture
91
Since for every a; b 2 N with a C b D 4 we have E y1a y2b D
aŠbŠ ; .n C 3/.n C 2/.n C 1/n
we obtain E jyj4 D nE y14 C n.n 1/E y12 y22 4Š 4.n 1/ C .n C 3/.n C 2/.n C 1/ .n C 3/.n C 2/.n C 1/ 4 1 D 2 CO : n n3
D
Denoting by P2 the uniform probability on f1; 1gn we have, by Khintchine inequality, j n1 jn1 EP1 ˝ h"y; i4 D p E 2 njPH .B1n /jn1
X
jh"; ijh"y; i4
"2f1;1gn
2n j n1 jn1 D p E EP2 jh"; ijh"y; i4 2 njPH .B1n /jn1 1 1 C E EP2 h"; i2 2 EP2 h"y; i8 2 !2 n X C E yi2 i2 0
i D1
D C @E y14
n X
i4 C E y12 y22
i D1
X
1 i2 j2 A
i ¤j
1 n n X X C @24 D i4 C 4 i2 j2 A .n C 3/.n C 2/.n C 1/n i D1 i;j D1 0
C ; n4
P P since niD1 i4 niD1 i2 D 1. On the other hand, since E y12 D
2 .n C 1/n
and
E y1 y2 D
1 ; .n C 1/n
92
2 Main Examples
we have E jyj2 D nE y12 D
2 nC1
and 0 1 n X X yi2 i2 C "i "j yi yj i j A EP1 ˝ h"y; i2 D EP1 ˝ @ i D1
D E y12 C
X
i ¤j
i j EP1 "i "j E y1 y2
i ¤j
D
2 1 C .EP h"; i2 1/ .n C 1/n .n C 1/n 1
D
1 1 .1 C EP1 h"; i2 / 2 ; .n C 1/n n
since, by Khintchine inequality, j n1 jn1 EP1 h"; i2 D p 2 njPH .B1n /jn1
X
jh"; ij3
"2f1;1gn
C EP2 jh"; ij3 C: Thus, .E jyj2 E h"y; i2 /2 D
4 CO n2
1 n3
and so Var jxj2
C : n3
2.4 Klartag’s Theorems for Unconditional bodies In this section we present Klartag’s work on unconditional log-concave probabilities. We will prove that the uniform probabilities on unconditional convex bodies, either or not isotropic, verify the variance conjecture. They also verify the KLS one with an extra log n factor.
2.4 Klartag’s Theorems for Unconditional bodies
93
We come back to the methods used in Sect. 1.4. We follow [4]. We recall that the natural Laplace–Beltrami operator L associated to the log-concave probability d.x/ D eW .x/ dx, (W 2 C 2 .Rn /), is Lu D u hrW; rui. The proof of the following result mimics the one of Theorem 1.4. Proposition 2.2 Let be a log-concave probability d.x/ D eW .x/ dx, where W W Rn ! R is a convex function in C 2 .Rn /. Assume that d is invariant for a group G of isometries (G O.n/). If there exists a map x ! A.x/ from Rn to the set of positive definite n n matrices such that for every u 2 D that is G-invariant we have that Z Z .Lu.x//2 d.x/ hA.x/ru.x/; ru.x/id.x/ Rn
Rn
then, for every f 2 L2 ./ locally Lipschitz that is G-invariant we have Z hA.x/1 rf .x/; rf .x/id.x/:
Var f Rn
Proof We can assume that G is closed and thus, a compact subgroup in O.n/ with the usual topology. Consider on G its bi-invariant normalized Haar probability . 1 For any f 2 L2 ./ such that E f D R 0 there exists a sequence fuk gkD1 D such 2 that Luk ! f in L ./. Let uQ k D G uk ı Rd.R/. It is clear that uk 2 D, uQ k is G-invariant and LQuk ! f in L2 ./. Then Z .f .x/ LQuk .x//2 d
Var f Rn
Z
D 2
Z .LQuk .x//2 d.x/
hrf .x/; r uQ k .x/i d.x/ Rn
Z
Z
Rn
hrf .x/; r uQ k .x/id.x/
2 Rn
Z
hA.x/r uQ k .x/; r uQ k .x/id.x/ Rn
hA1 rf .x/; rf .x/id:
(by Lemma 1.2) Rn
Taking limits when k ! 1 we obtain the result. Now, let us prove that any unconditional log-concave probability verifies the variance conjecture. The following theorem was proved by Klartag in [12]. Theorem 2.8 There exists a positive absolute constant C such that for any unconditional log-concave probability on Rn Var .jxj2 / C 2 E jxj2 :
94
2 Main Examples
Proof Let us assume that d.x/ D eW .x/ dx with W 2 C 2 .Rn / a convex function and W .x1 ; : : : ; xn / D W .jx1 j; : : : ; jxn j/. Thus, d is invariant under reflections with respect to the coordinate hyperplanes. In this case it is clear that the covariance matrix of is a diagonal matrix D .1 ; : : : ; n / with i > 0, 1 i n, and 2 D sup i D sup E xi2 : 1i n
1i n
Let u 2 D be such that u.x1 ; : : : ; xn / D u.jx1 j; : : : ; jxn j/. Denote x D .x1 ; y/ with y 2 Rn1 fixed. Let v W R ! R be defined by v.x1 / D u.x1 ; y/ and d the log-concave probability on R given by the even density eW .x1 ;y/ dx1 : W .x1 ;y/ dx 1 Re
d.x1 / D R
Since v is even, E v 0 D 0. Then, using Poincaré’s inequality in the one-dimensional case (Proposition 1.5), we obtain E .v 0 /2 C E x12 E .v 00 /2 and so, for any x 2 Rn , Z
R
x12 eW .x1 ;:::;xn / dx1 W .x1 ;:::;xn / dx 1 Re
.@1 u.x// d.x1 / C RR 2
R
Z .@11 u.x//2 d.x1 /: R
Proceeding analogously for any 1 i n and denoting by R 2 W .x ;:::;t;:::;x / 1 n dt t e gi .x/ D C RR W .x ;:::;t;:::;x / 1 n dt Re we have, since gi .x/ does not depend on xi that for any 1 i n, Z Rn
1 .@i u.x//2 d.x/ (by Fubini) gi .x/
Z .@ii u.x//2 d.x/: Rn
Since integration by parts gives the formula Z
Z .Lu.x//2 d.x/ D Rn
hHess W .x/ru.x/; ru.x/id.x/
(2.5)
Rn
Z
C
kHess u.x/kHS d.x/; Rn
(2.6)
2.4 Klartag’s Theorems for Unconditional bodies
95
where Hess f .x/ denotes the Hessian of f at x, we have Z
Z
Z
2
.Lu.x// d.x/
kHess
Rn
Rn
Z
n X Rn i D1
u.x/k2HS d.x/
n X
.@ii u.x//2 d.x/
Rn i D1
1 .@i u.x//2 d.x/: gi .x/
Applying Proposition 2.2 to the matrix A.x/ D .aij .x//ni;j D1 with aij .x/ D ıij gi 1.x/ we get that Z
n X
Var f
gi .x/.@i f .x//2 d.x/
Rn i D1
for every function f that is unconditional and locally Lipschitz. If we apply this estimate to the function f .x/ D jxj2 we obtain
Var jxj2 C
n Z X iD1
DC
R 2 W .x/ x e dxi W .x/ xi2 RR i W .x/ e dx dxi Rn Re R
n Z X iD1
x 2 eW .x/ dxi R R i W .x/ dx i Re
Rn1
!2 Z
eW .x/ dxi dx1 : : : dxi1 dxiC1 : : : dxn R
(by Hölder’s inequality) Z n Z X xi4 eW .x/ dxi dx1 : : : dxi1 dxiC1 : : : dxn C iD1
DC
iD1
C
Rn1
n Z X Rn
xi4 d.x/ (by Borell’s inequality)
n Z X iD1
R
2 Rn
xi2 d.x/
C 2
n Z X
xi2 d.x/ D C 2 E jxj2 :
iD1
If has compact support (for instance, is the uniform probability measure on a convex body) then an extra positive factor appears in the identity (2.5) and proceeding analogously in the proof of Proposition 2.2 we obtain the same result. The result is true for any log-concave unconditional probability by approximating W by smooth functions. This answers positively the variance conjecture in the case of unconditional probabilities. We will give another proof of Theorem 2.8 for uniform probabilities on unconditional bodies, due to Klartag [13]. In order to do that we introduce the following definitions.
96
2 Main Examples
p p A subset K RnC is said to be 12 -convex if f. x1 ; : : : ; xn /; x 2 Kg is convex, where x D .x1 ; : : : xn /. Every 12 -convex set is convex. A subset K RnC is said to be monotone if .x1 ; : : : ; xn / 2 K and 0 yi xi ; 8i , implies .y1 ; : : : ; yn / 2 K. Every convex monotone set is 12 -convex. Note that an unconditional set K 2 Rn verifies K \ RnC is monotone and so 12 -convex. Similarly, a function W RnC ! R [ f1g is 12 -convex if x ! .x12 ; : : : ; xn2 / is convex. Any function e with 12 -convex is said to be 12 -log concave. Clearly, for a 12 -convex K RnC , the characteristic function K is 12 -convex. Proposition 2.3 Let K RnC be a 12 -convex bounded set and the uniform probability measure on it. Then for every f 2 C 1 .K/, Z Var f 4
n X
Rn i D1
xi2
ˇ ˇ2 ˇ @f ˇ ˇ ˇ ˇ @x .x/ˇ d.x/: i
This proposition is a consequence of the following Proposition 2.4 Let be a 12 -log concave finite measure on RnC . Then for every f 2 C 1 .RnC /, Z Var f 4
n X
RnC i D1
xi2
ˇ ˇ2 ˇ @f ˇ ˇ ˇ ˇ @x .x/ˇ d.x/: i
Proof Let e be the density of with convex and denote .x/ D .x12 ; : : : ; xn2 /. n X log.2xi / and denote by the measure with density Write '.x/ D . .x// e' . ' is also convex and
i D1
Hess '.x/ Hess
n X
!
0
1 x12
B: log.2xi / D B @ :: i D1 0
:: :
1 0 :: C C : A > 0: 1 xn2
1 x12 0 C B Therefore, .Hess '/1 .x/ @ ::: : : : ::: A. 0 xn2 Write g.x/ D f . .x//. We have seen in the proof of Theorem 1.4 that 0
Z Var g
1
.Hess '.x// RnC
Z hrg.x/; rg.x/id.x/ D
n X
RnC i D1
xi2
ˇ ˇ2 ˇ @g ˇ '.x/ ˇ ˇ dx: ˇ @x .x/ˇ e i
2.4 Klartag’s Theorems for Unconditional bodies
97
Q Now, since e'.x/ D e .x/ niD1 .2xi / and the Jacobian of the map at any Q x 2 RnC is niD1 .2xi /, we have that the map transports the measure to . @f @g Therefore, Var g D Var f and, for all 1 i n, .x/ D 2xi . .x// which, @xiˇ ˇ@xi ˇ2 ˇ2 ˇ @g ˇ @f ˇ ˇ .x/ˇˇ D 4yi2 ˇˇ .yi /ˇˇ and via the change of variables y D .x/, implies xi2 ˇˇ @xi @yi the result follows. Corollary 2.2 Let be the uniform probability measure on an unconditional convex body in Rn . Then Var jxj2 C E jxj2 for some absolute constant C > 0. Proof Denote by the conditioning of to RnC . In particular is 12 -convex. By unconditionality and the use of the previous proposition for f .x/ D jxj2 with rf .x/ D 2x, we have 2
2
Var jxj D Var jxj 4E
n X i D1
yi2
ˇ ˇ2 n X ˇ @f ˇ ˇ ˇ E .yi4 /: ˇ @y .y/ˇ D 16 i i D1
p p Since y1 ; : : : yn are log-concave we use Borell’s lemma in order to bound each summand and
Therefore,
E .yi4 /
1 p p E . yi /8 2 E . yi /4 : 8Š 4Š
! ! ! 8 8 8 2 2 2 E .yi / D E .xi / and then 4 4 4 2
Var jxj
C 2
n X
E .xi2 / D C 2 E jxj2 :
i D1
Klartag proved that the uniform measure on an isotropic unconditional convex body verifies the KLS conjecture with an extra logarithmic factor. In [4] the authors remark that Klartag’s method applies for log-concave probabilities with rather general symmetries.
98
2 Main Examples
Theorem 2.9 Let K be an unconditional isotropic convex body and let be the uniform probability on L1 K K. Then there exists an absolute constant C > 0 such that 1 ./
C : log2 n
The proof is based on the following results Lemma 2.2 Let K be an unconditional convex body, the uniform probability on K and u 6D 0 an eigenfunction corresponding to the first eigenvalue 1 ./ > 0 associated to the operator . Then there exists i 2 f1; : : : ; ng such that the function v.x/ D u.x1 ; : : : ; xi ; : : : ; xn / u.x/ is also a non-zero eigenfunction associated to the same 1 ./: Proof We will assume that K is a strictly convex body in Rn with C 1 boundary, defined by a function , such that .x/ 0 for x 2 K and jr .x/j D 1 for x 2 @K. In such case Klartag proved in [12], by using Stokes theorem, that for any u 2 D.K/ Z . u/2 .x/dx D
Z X n
K
K i D1
Z jr@i u.x/j2 dx C
hHess .x/ru.x/; ru.x/idx: @K
It is clear that v es an eigenfunction for 1 . If the result were not true, then u would be unconditional, u.˙x1 ; : : : ; ˙xn / D u.x1 ; : : : ; xn / and so E @i u D 0, for all i . Then, using the properties of eigenfunctions and Poincaré’s inequality for K with smooth boundary conditions given a function , we have Z
Z K
1 X 1 ./ i D1 n
u2 .x/d.x/ D
1 ./
jru.x/j2 d.x/ K
Z jr@i u.x/j2 d.x/
n Z 1 X jr@i u.x/j2 d.x/ 1 ./ i D1 Z 1 C hHess .x/ru.x/; ru.x/id.x/ 1 ./ @K Z Z 1 D . u.x//2 d.x/u D 1 ./ u.x/2 d.x/: 1 K K
We conclude that the inequalities are indeed equalities. Hence, Z hHess .x/ru.x/; ru.x/idx D 0 @K
2.4 Klartag’s Theorems for Unconditional bodies
99
and hHess .x/ru.x/; ru.x/idx D 0
8x 2 @K:
But if we assume that K is strictly convex necessarily Hess is positive definite, so ru.x/ D 0 on @K and u is constant on @K which is not possible for a Neumann eigenfunction corresponding to the first non-zero eigenvalue. As a consequence of Borell’s lemma we have Lemma 2.3 Let K be an isotropic convex body and the uniform probability measure on L1 K K. Then there exists an absolute constant C > 0 such that 1 fx 2 Rn I kxk1 C log ng 1 : n Proof Using the 1 -decay of the mass for log-concave probabilities [8] (see also Proposition A.5), we have that for any 1 i n fx 2 Rn I jxi j > sg D jfx 2 KI jxi j > sLK gj 2ecs for every s > 0 (c > 0 is an absolute constant). Hence, fx 2 Rn I jxi j > s; for some i g 2necs : We get the result by choosing s D C log n, for C an appropriate absolute constant. Proof (of Theorem 2.9) Let K be strictly convex, unconditional and isotropic. By using Lemma 2.3 we can consider the unconditional convex body K 0 D fx 2 L1 K KI kxk1 C log ng. It is clear that if is the uniform probability measure on K 0 then E x D E xi xj D 0 whenever i 6D j and E xi2
n E xi2 2; n1
where is the uniform probability on L1 K K: We use a result by E. Milman [15] which ensures 1 ./ 1 ./ (with absolute constants). Hence we have to estimate 1 ./. Without loss of generality, by Lemma 2.2, there exists an eigenfunction v 6D 0 associated to 1 ./ such that v.x1 ; x2 ; : : : ; xn / D v.x1 ; x2 ; : : : ; xn /. If x D 1 .t; y/ with y 2 Rn1 , let Ay D fs 2 R; .s; y/ 2 K 0 g and dy .t/ D A .t/dt jAy j1 y
100
2 Main Examples
Z v.t; y/dy .t/ D 0 for any y 2
a log-concave symmetric probability on R. Thus R
Rn1 . By Proposition 1.5 Z
Z
Z
v 2 .t; y/dy .t/ C R
t 2 dy .t/ Z
R
.@t v.t; y//2 dy .t/ Z
R
2
C
jrv.t; y/j2 dy .t/
t dy .t/ R
R
Z
C sup t 2 t 2Ay
jrv.t; y/j2 dy .t/ R
Z
C log2 n
jrv.t; y/j2 dy .t/: R
Hence, since v is an eigenfunction, Z
Z K0
Z
v.x/2 d D P
e1?
K0
v.t; y/2 dy .t/dy
jAy j1 R
Z
C log2 n Z D C log2 n
Z PRn1 .K 0 /
K0
jrv.t; y/j2 dy .t/dy
jAy j R
jrv.x/j2 d.x/ D .by (1.9)/ Z
2
D C log n 1 ./
K0
v 2 d
and we get 1 ./
C : log2 n
By an approximation argument the result is true for any K.
References 1. D. Alonso-Gutiérrez, J. Bastero, The variance conjecture on some polytopes, in Asymptotic Geometric Analysis, Proceedings of the Fall 2010, Fields Institute Thematic Program, Fieds Institute Communications, vol. 68 (Springer, Berlin, 2013), pp. 1–20 2. M. Anttila, K. Ball, I. Perissinaki, The central limit problem for convex bodies. Trans. Am. Math. Soc. 355(12), 4723–4735 (2003) 3. K. Ball, Isometric Problems in `p and Sectios odf Convex Sets. Ph.D. thesis, Cambridge University, 1986
References
101
4. F. Barthe, D. Cordero-Erausquin, Invariances in variance estimates. Proc. Lond. Math. Soc. (3) 106(1), 33–64 (2013) 5. F. Barthe, P. Wolff, Remarks on non-interacting conservative spin systems: the case of gamma distributions. Stochast. Process. Appl. 119, 2711–2723 (2009) 6. F. Barthe, O. Guédon, S. Mendelson, A. Naor, A probabilistic approach to the geometry of the `np -ball. Ann. Probab. 33(2), 480–513 (2005) 7. S. Bobkov, Spectral gap and concentration for some spherically symmetric probability measures, in Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, vol. 1807 (Springer, Berlin, 2003), pp. 37–43 8. C. Borell, Convex measures on locally convex spaces, Ark. Math. 12, 239–252 (1974) 9. D. Hensley, Slicing convex bodies, bounds of slice area in terms of the body’s covariance. Proc. Am. Math. Soc. 79, 619–625 (1980) 10. N. Huet, Spectral gap for some invariant log-concave probability measures. Mathematika 57(1), 51–62 (2011) 11. R. Kannan, L. Lovász, M. Simonovits, Isoperimetric problems for convex bodies and a localization lemma. Discret. Comput. Geom. 13(3–4), 541–559 (1995) 12. B. Klartag, A Berry-Esseen type inequality for convex bodies with an unconditional basis. Probab. Theory Relat. Fields 145(1–2), 1–33 (2009) 13. B. Klartag, Poincaré inequalities and moment maps. Ann. Fac. Sci. Toulouse Math. 22(1), 1–41 (2013) 14. R. Latała, J.O. Wojtaszczyk, On the infimum convolution inequality. Stud. Math. 189(2), 147– 187 (2008) 15. E. Milman, On the role of convexity in isoperimetry, spectral gap and concentration. Invent. Math. 177(1), 1–43 (2009) 16. V.D. Milman, A. Pajor, in Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space, GAFA Seminar 87–89, Springer Lecture Notes in Mathematics, vol. 1376 (1989), pp. 64–104 17. C.A. Rogers, G.C. Shephard, Convex bodies associated with a given convex body. J. Lond. Math. Soc. 33, 270–281 (1958) 18. G. Schechtman, J. Zinn, Concentration on the `np ball, in Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 1745 (Springer, Berlin, 2000), pp. 245–256 19. S. Sodin, An isoperimetric inequality on the `p balls. Ann. Inst. H. Poincar é Probab. Stat. 44(2), 362–373 (2008) 20. J.O. Wojtaszczyk, The square negative correlation property for generalized Orlicz balls, in Geometric Aspects of Functional Analysis. Israel seminar, Lecture Notes in Mathematics, vol. 1910 (Springer, Berlin, 2007), pp. 305–313
Chapter 3
Relating the Conjectures
In the third chapter we present four important results that relate the conjectures with the hyperplane conjecture and give the best known estimate for the variance conjecture. We will only sketch the proofs in this chapter since our intention is to offer the main ideas and give the results in a compelling way. In Sects. 3.1 and 3.2 we connect the variance and the KLS conjectures with the hyperplane conjecture or slicing problem. We present the theorems by Eldan-Klartag and Ball-Nguyen. In Sect. 3.3 we offer an approach to Eldan’s work on the relation between the thin-shell width and the KLS conjecture. In Sect. 3.4 we present the main ideas to prove the best known estimate for the thin shell width given by Guédon-Milman.
3.1 From the Variance Conjecture to the Slicing Problem Via Eldan-Klartag’s Method The slicing problem (or hyperplane conjecture) conjectures that for any convex body K Rn with volume jKjn D 1 there exists a hyperplane section, K \ H , with .n 1/-dimensional volume jK \ H jn1 > C , for some absolute constant C > 0. This problem, in a different formulation, was posed by Bourgain in [6] (see also [2, 24]), who gave the first non trivial estimate (see, for instance, [7]) jK \ H jn1
C
:
1 4
n log n
Klartag (see [17]) improved this estimate to jK \ H jn1
C 1
:
n4
© Springer International Publishing Switzerland 2015 D. Alonso-Gutiérrez, J. Bastero, Approaching the Kannan-Lovász-Simonovits and Variance Conjectures, Lecture Notes in Mathematics 2131, DOI 10.1007/978-3-319-13263-1_3
103
104
3 Relating the Conjectures
It is known that this conjecture is true for many classes of convex bodies and that in order to prove it for general convex bodies it is enough to prove it for centrally symmetric convex bodies. We can quantify the conjecture in the following way: let Z K be a convex body in Rn with its barycenter at the origin, i.e.
xdx D 0. We K
define LK , the isotropic constant of K, to be the isotropic constant of its isotropic linear image, which equals nL2K WD min
Z
1
T 2GL.n/
1C 2 jTKjn n
jTxj2 dx: K
This quantity is linear invariant and it is easy to check that LK LB2n C > 0 for some numerical constant and for any K. Proving the hyperplane conjecture is equivalent to proving that LK C for some absolute constant C > 0 independent of the dimension. The best known upper bound depending on the dimension is, see [17], 1
LK Cn 4 : More generally, this question can also be asked in the class of log-concave probabilities, since a theorem by Ball [3] asserts that the uniform boundedness of the isotropic constant of convex bodies is equivalent to the uniform boundedness of the isotropic constant of log-concave probabilities sup LK sup L C sup LK ; n;
n;K
n;K
where C > 0 is an absolute constant, 1
1
n L WD kk1 j det M j 2n
(here kk1 D supx2Rn f .x/ whenever d.x/ D f .x/dx, which is affine invariant), and M D .E xi xj /ni;j D1 is the covariance matrix of which, as in all the monograph, is assumed to have its barycenter at the origin. If is isotropic, by a result by Fradelizi [14], we know that f .0/ kf k1 en f .0/ so 1
1
f .0/ n L ef .0/ n :
3.1 The Variance Conjecture Implies the Slicing Problem
105
Conjecture 3.1 (Hyperplane Conjecture) There exists an absolute constant C > 0 such that for any log-concave probability measure on Rn we have L C: The variance conjecture is stronger than the hyperplane conjecture in the following way. Theorem 3.1 (Eldan-Klartag [10]) There exist absolute constants C1 ; C2 > 0 such that C1 sup L p sup sup E hx; ijxj2 C2 n ; n 2S n1 where the supremum in is taken when runs in the class of isotropic log-concave probabilities on Rn . We will sketch here the original proof given by R. Eldan and B. Klartag modified by a remark/simplification of Eldan-Klartag’s argument given by CorderoErausquin (D. Cordero-Erausquin, La preuve de Eldan-Klartag un peu allégée, unpublished manuscript), in order to avoid the Riemannian structure which appears in the proof given in [10]. Proof (Sketch) Recall that n D sup . The right-hand side inequality is easy to prove and similar to the one in Proposition 1.4, since for every 2 S n1 we have E hx; ijxj2 D E hx; i.jxj2 n/ .by Cauchy-Schwartz inequality/ q Var jxj2 : For some C 1, to be chosen later, we have Var jxj2 D E .jxj2 n/2 D E .jxj2 n/2 fjxjC png C E .jxj2 n/2 fjxj>C png p 1 .C C 1/2 n E.jxj n/2 C 1 C 4 E jxj4 fjxj>C png C p n
.C C 1/2 n 2 C C 0 n2 e
by Borell’s lemma p and Paouris’s strong inequality. Since a simple computation shows that n 2 (try the standard Gaussian probability in Rn ) we get that p E hx; ijxj2 C2 n n :
106
3 Relating the Conjectures
In order to prove the left-hand side inequality we use the following facts. We define 1 n D p sup sup E hx; ijxj2 : n 2S n1 p It is easy p to check that n 2. p If n n , then the trivial estimate for the isotropic constant L C n gives the result. p We consider the case in which n n. We may assume that is the isotropic probability uniformly supported on a symmetric convex body K (see Proposition 1.2). In such case 1
L D
1
jKjnn and we have to prove that 1
jKjnn
c n
(3.1)
for some c > 0 numerical constant. Let us consider the logarithmic Laplace transform of , defined for every y 2 Rn by Z ehy;xi d.x/:
L .y/ D L.y/ WD log Rn
L is a strictly convex C 1 -smooth function on Rn . It is clear that L.0/ D 0, rL.0/ D 0. Furthermore, rL.Rn / K since K is the support of and for every y 2 K, z 2 K ı we have hrL.y/; zi 1. Let us consider, for any y 2 Rn , the probability measure y with density proportional to x ! ehy;xi , i.e., ehy;xi d.x/ : hy;xi d.x/ Rn e
dy .x/ D R
Since Hess L.y/ D Cov y , the covariance matrix of y , we have that Hess L.0/ D I . p Now consider for any 1 t n Kt D fy 2 Rn I L.2y/ t 2 g:
3.1 The Variance Conjecture Implies the Slicing Problem
107
We have Z jKjn jrL.Kt /jn D
det Hess L.y/dy: Kt
The result is a consequence of the two following lemmas: p Lemma 3.1 Let 1 t n, then 1 ct jKt jnn p n
for some absolute constant c > 0. Lemma 3.2 Let y 2 Rn , then p
det Hess L.y/ ce
n n
p
L.2y/
:
p n= n and then
Once the lemmas are proved, we choose t D
n 1 ct t p c n jKjnn p e n n
and this finishes the proof. Proof (of Lemma 3.1. See Lemma 3.3 in [10]) Without loss of generality we may assume that t is an integer. Let E Rn be any t 2 -dimensional linear subspace and denote fE the even log-concave density of the push-forward of under the projection onto E, PE . It is clear that 1
fE .0/ t 2 D LfE c; where c > 0 is an absolute constant. It was proved in Lemma 2.8 in [20] that the volume radius of Kt \ E verifies the following inequality.
v.rad.Kt \ E/ WD
jKt \ Ejt 2
! 12 t
1
ctf E .0/ t 2 c 0 t:
2 jB2t jt 2
Since this bound holds for any subspace we have v.rad.Kt / WD
jKt j jB2n j
n1
(see [16], Corollary 3.1) which implies the result.
c1 t
108
3 Relating the Conjectures
Proof (of Lemma 3.2. See D. Cordero-Erausquin, La preuve de Eldan-Klartag un peu allégée, Unpublished Manuscript) Let y 2 Rn Z
1
d log det Hess L.sy/ds ds 0 Z 1 d D Tr Hess L.sy/1 Hess L.sy/ ds: ds 0
log det Hess L.y/ D
We fix s0 2 Œ0; 1 and let H0 D
p Hess L.s0 y/1 . Then
! ˇ ˇ ˇ d d ˇˇ 2 ˇ Tr H0 Hess L.sy/ D Tr H02 Hess L.sy/ ds ˇsDs0 ds ˇsDs0 ˇ d ˇˇ D Tr H02 Cov sy ˇ ds sDs0 ˇ ˇ2 Z Z ˇ ˇ ˇ d ˇˇ ˇ H0 x D H0 zds0 y .z/ˇˇ dsy .x/: n ds ˇsDs0 Rn ˇ R R Since the vector H0 x Rn H0 zds0 y .z/ is orthogonal to the constant vectors in L2 .ds0 y / we only have to differentiate the part corresponding to the other factor, i.e, ˇ Z d ˇˇ d .x/ D hy; xi hy; zid .z/ ds0 y .x/: sy s0 y ds ˇsDs0 Rn Thus, we get ! ˇ d ˇˇ Tr Hess L.sy/ ds ˇsDs0 ˇ2 Z ˇ Z Z ˇ ˇ ˇH0 x ˇ D H zd .z/ hy; zid .z/ ds0 y .x/: hy; xi 0 s0 y s0 y ˇ ˇ H02
Rn
Rn
Rn
Consider now a log-concave random vector X distributed according to ds0 y . If we denote by Z the random vector Z D H0 X Es0 y H0 X , it is clear that Z is log-concave and isotropic by the definition of H0 . Hence ˇ ˇ2 Z Z ˇ ˇ ˇ ˇ ˇH0 x n H0 zds0 y .z/ˇ hy; xi hy; zids0 y .z/ ds0 y .x/ Rn R ˝ ˇ2 ˛ˇ D Es0 y y; X Es0 y X ˇH0 X Es0 y H0 X ˇ Z
3.2 The KLS Conjecture Implies the Slicing Problem
109
˝ ˛ D Es0 y H01 y; Z jZj2 ˛ ˝ D H01 y; Es0 y ZjZj2 p p p n n jH01 yj D n n hHess L.s0 y/y; yi: Then p log det Hess L.y/ n n
Z
p D 2 n n
1
p hHess L.sy/y; yids
0
Z
1=2
p hHess L.2sy/y; yids:
0
Using Cauchy-Schwartz’s inequality we obtain Z
1=2
p hHess L.2sy/y; yids
0
Z
1=2
!1=2 Z .1 s/hHess L.2sy/y; yids
0
Z
0
!1=2 1 ds 1s
1=2
1
1=2
.1 s/hHess L.2sy/y; yids
:
0
It is also clear that, integrating, Z 4
1
.1 s/ hHess L.2sy/y; yi ds D L.2y/ L.0/ hrL.0/; 2yi D L.2y/: 0
This finishes the proof.
3.2 KLS Conjecture Versus Hyperplane Conjecture According to Ball and Nguyen In this section we present the approach by Ball and Nguyen (see [4]) to the proof of the fact that the KLS conjecture is stronger than the hyperplane conjecture. We have seen in the previous section that if the variance conjecture (which is a particular case of the KLS conjecture) is verified by every log-concave probability then the hyperplane conjecture is verified by every log-concave probability. Ball’s and Nguyen’s approach shows that if a family of log-concave probabilities verifies
110
3 Relating the Conjectures
the KLS conjecture then the same family of log-concave probabilities verifies the hyperplane conjecture. Theorem 3.2 Let be an isotropic log-concave probability in Rn . Assume that has an spectral gap 1 ./. Then 16
L e 1 ./ : We will work in the framework of information theory. First we recall that if X is a random vector in Rn distributed according to a probability with density f .x/, then its entropy is defined by Z f .x/ log f .x/dx;
Ent .X / D Rn
Z provided that Rn
f .x/ logC f .x/dx < 1. If f is log-concave, f .x/ D eV .x/ ,
with V a convex function on Rn then Z V .x/e V .x/ dx:
Ent .X / D Rn
Let G be a standard Gaussian random vector. It is well known that among random vectors with a given covariance matrix the corresponding Gaussian has the largest entropy. The gap Ent .G/ Ent .X / controls the distance between the densities (Pinsker-Csiszár-Kullback inequality, see [5, 8, 25]). Theorem 3.3 (K. Ball) Let X be a random vector in Rn distributed according to the isotropic log-concave probability . Assume that it satisfies an entropy jump with constant 2 .0; 1/, i.e. Ent
X CY p 2
Ent .X / .Ent .G/ Ent.X //;
where Y is an independent copy of X . Then we have 2
L e : Proof (Sketch. See [4], Theorem 5.1) Assume that X is distributed according to d.x/ D eV .x/ dx. Using the convexity of V , Jensen’s inequality, and integration by parts we get V .0/ Ent .X / n C V .0/:
3.2 The KLS Conjecture Implies the Slicing Problem
111
X CY is log-concave, we can deduce p 2 X CY 3 Ent V .0/ C n: p 2 2
If X is an even random vector, since
In the general case, by symmetrization techniques, we obtain Ent
X CY p 2
V .0/ C 2n:
Hence
X CY .1 /Ent .X / Ent p 2
Ent .G/ Ent
X CY p 2
;
since Ent .G/ 0. This fact and the previous estimates imply that .1 /V .0/ V .0/ C 2n and this gives the result since L e
V .0/ n
.
The other important result is the following by Ball and Nguyen. Theorem 3.4 Let X be a random vector on Rn distributed according to an isotropic log-concave probability and let Y be an independent copy of X . Then
X CY p Ent 2
Ent .X /
1 ./ .Ent .G/ Ent .X //; 8
where 1 ./ is the spectral gap of . Proof (Sketch) Let us recall that the spectral gap of a log-concave probability is the best constant in the inequality 1 ./E jf Ef j2 E jrf j2 for any locally Lipschitz integrable f . We know that 1 ./ Is./2 , where Is./ is the Cheeger’s constant. We also know, since the inequality is obviously true for linear functions, that 1 ./ 1, when is isotropic and log-concave. In order to establish this theorem we define the Fisher information of a random vector X with smooth density f by Z J.X / D J.f / WD Rn
jrf .x/j2 dx: f .x/
112
3 Relating the Conjectures
The Fisher information appears as the derivative of the entropy along the OrnsteinUhlenbeck semi-group, in the following way: if X is a random vector with density f and G is the standard Gaussian independent of X , we consider the random vector p Xt D et X C 1 e2t G, whose law has a density ft , solution of the evolution equation @ ft .x/ D L.ft /.x/ @t f0 D f;
8 t > 0; 8 x 2 Rn
where L.ft /.x/ D x ft C divx .xf t /. The entropy gap is Z
1
.J.ft / n/dt:
Ent .G/ Ent .X / D 0
Assuming that X is isotropic and log-concave, after several computations we have that Z Z J.t/ WD J.ft / D ft log ft D Tr ft .x/Hess log.ft /.x/dx; Rn
Rn
Z ft .x/ .H log.ft /.x//2 dx;
@t J.t/ D 2J.t/ 2 Tr Rn
and Z
1
e2t .J.t/ n/dt
Ent .G/ Ent .X / 2
(3.2)
0
(see a detailed proof of these facts in [4], Lemmas 2.1 and 2.2). In order to bound from below the left-hand side term of the inequality we proceed X CY as follows: Let Zt be the Orstein-Uhlenbeck evolute of p . Denote by 2 • ht D e Zt , the smooth density of Zt , h.x/ .Hess log f .x//2 dx,
• K D Tr Rn
• J2 .t/ WD J.Z Z t /, and ht .x/ .Hess log ft .x//2 dx:
• K2 .t/ D Tr Rn
Then K2 .t/
K.t/ C M.t/ ; 2
3.3 From the Variance Conjecture to the KLS Conjecture
113
where 2 #
"Z M.t/ D Tr
.Hess log.ft /.x//ft .x/dx Rn
(see [4], Theorem 3.2). Next, applying Poincaré’s inequality, we get K.t/ M.t/
1 ./ .K.t/ J.t// 1 C 1 ./
and 1 ./ 2t J.t/ J2 .t/ e 1 C 1 ./
Z
1
e2s .K.s/ J.s//ds: t
Hence
X CY Ent p 2
1 ./ Ent .X / 2.1 C 1 .//
Z
1
e2t .J.t/ n/dt 0
(see a detailed proof of these facts in [4], Proof of Theorem 1.1) which finishes the proof by (3.2).
3.3 From the Thin-Shell Width to the KLS Conjecture: An Approach to R. Eldan’s Method From its own definition, it is clear that the KLS conjecture is stronger than the variance conjecture. In this section we are interested in the reverse relation. Theorem 1.14 by Bobkov gives a reverse estimate 1 1 C Var jxj2 2 : 2 Is./ By Propositions 1.3 and 1.4 if we assume that is a symmetric and isotropic logconcave probability we have Var jxj2 2 E jxj2 and so p 1 C n Cn2 : 2 Is./
114
3 Relating the Conjectures
This bound has been dramatically improved by Eldan [9] (see the Theorem 3.5 below), who proved that, up to a log n factor, the variance and the KLS conjectures are equivalent for every log-concave probability on Rn . In this section we give an approach to this recent result by Eldan in which he shows how to deduce a logarithmic estimate for the KLS conjecture in terms of the variance conjecture. The theorem we want to present is the following: Theorem 3.5 (Eldan [9]) There exists an absolute constant C > 0 such that n X k2 1 C.log n/2 n2 C log n Is./2 k i D1
for any log-concave probability in Rn , where k D sup and the supremum is taken over all isotropic log-concave probabilities on Rk . The main idea of the following lines is to sketch the proof of this result. The items in which this approach is based are the following: 1. The first tool is E. Milman’s Theorem 3.7 below (see [23]). Roughly speaking, this result says that for isotropic log-concave probabilities we can bound the Cheeger constant if we only control the enlargement of the measure of the Borel sets E of measure .E/ D 12 when we dilate them. More precisely, in order to prove the KLS conjecture we should only prove that there exist two absolute constants C1 ; C2 > 0 such that .E C1 n E/ C2 for any isotropic log-concave and for any Borel set E 2 Rn such that .E/ D 1 , where E C1 is the C1 -dilation of E. 2 In Eldan’s approach the constant C1 obtained depends on some parameter n , which depends on the maximum thin-shell width of isotropic log-concave p measures ’s in dimension n plus a logarithmic factor. Up to this extra log n factor, Eldan’s result shows the equivalence between the KLS conjecture and the Variance conjecture (for isotropic and, consequently, for any log-concave probabilities). 2. The second tool, Theorem 3.8, is based in a classical result saying that if a log-concave probability is “more log-concave than Gaussian” it has a bounded spectral gap and so, concentrates enough in order to use Theorem 3.7. 3. The third step in the theorem is to show that, given an isotropic log-concave probability, we can modify it to construct a new isotropic log-concave probability which is not far from the original one and is “more convex than Gaussian” in order to apply 2. Eldan’s original idea in the theorem is to introduce a stochastic process, .t /t >0 , associated to every isotropic log-concave probability in Rn , . These t are random isotropic, log-concave probabilities, solutions of a stochastic differential equation, with initial conditions in t D 0.
3.3 From the Variance Conjecture to the KLS Conjecture
115
If d.x/ D f .x/dx, then dt;! .x/ D ft;! .x/dx, (t 0, ! 2 ˝, a probability space) satisfy 1
df t .x/ D ft .x/hAt 2 .x at /; dW t i;
8t > 0
in the sense of Itô’s differential calculus, where Wt is the classical Wiener process in Rn , At is the covariance matrix, and at the barycenter In some sense the idea of this process is the continuous extension of the following random walk, in Eldan’s words: at every time step we multiply the density by a linear function equal to 1 at the barycenter whose gradient has a random direction distributed uniformly on the inertia ellipsoid. This construction is a variant of a Brownian motion on a Riemannian manifold which also appears in [10]. 4. This process has a martingale property in the sense that Z
Z .x/d.x/ D E!
.x/dt;! .x/
Rn
8t > 0
Rn
for any test function . This property ensures that we can recover averaging at any instant t and, moreover, we are not far from . In particular, if E Rn is such that .E/ D 12 then 1 D E! 2
Z
dt .x/
8t > 0:
E
We will see that for t far from 0, (t > 1=.n2 log n/), the probabilities t are “more convex than Gaussian”, more convex for a big set of !’s (i.e., P! > 1 n10 ). This fact implies that we have strong concentration and so, dilations of E, are also “big”, and so we can pass from E! t .ED / in the martingale process to .ED / uniformly, in order to apply the first step. In the following subsections we either prove or sketch the corresponding results and properties which we expect will enlighten the reader about this remarkable approach.
3.3.1 How to Approach Theorem 3.5 Let us recall that for an isotropic log-concave probability on Rn the parameter 2 is equivalent to Var jxj, since Var jxj 2 D E j jxj
p 2 nj 2Var jxj:
116
3 Relating the Conjectures
Also, if is symmetric, 2
Var jxj2 C1 2 : E jxj2
We introduce a new parameter n associated to log-concave probabilities. This new concept is closely related to the thin-shell width Definition 3.1 (See [9, 10]) We define the parameter n by n2 D sup 2 ;
where n X
2 2 D sup E x ˝ xhx; i HS D sup .E xi xj hx; i/2 2S n1
2S n1 i;j D1
and runs over all isotropic log-concave probabilities on Rn . The relation between the parameters n D sup and n appears in the following probabilistic lemma: Lemma 3.3 The parameter n is bounded from above by n2
C
n X 2 k
i D1
k
:
Proof (See also [10]) Fix 2 S n1 . Let A the matrix whose entries are E xi xj hx; i. A is symmetric and let 1 2 s be its non-negative eigenvalues (s n). Given 1 k s we want to prove that 2k C1
k2 : k
Indeed, let Ek Rn be the span of the eigenvectors associated to 1 ; : : : k . The trace of the matrix PEk APEk is k X
i D E hx; ijPEk xj2 D E hx; i jPEk xj2 k
i D1
q (by Cauchy-Schwartz inequality)
Var jPEk xj2 C
p kk ;
3.3 From the Variance Conjecture to the KLS Conjecture
117
since PEk x is an isotropic k-dimensional log-concave random variable (see Proposition 1.4). Hence 2k verifies the inequality. A similar argument works with the non-positive eigenvalues and the lemma holds. The proof of Theorem 3.5 is now a consequence of Theorem 3.6 which, with the help of E. Milman’s Theorem 3.7, that uses a combination of differential geometry and geometric measure theory arguments, is the key result in the proof of Theorem 3.5. Theorem 3.6 There exist absolute constants c1 > 0; c2 > 12 , such that for every isotropic log-concave probability on Rn and every Borel set E Rn , with .E/ D 12 we have .E c1 n
p
log n
/ c2 ;
where E c1 n
p
log n
n o p D x 2 Rn W d.x; E/ < c1 n log n
is the corresponding dilation of E. Theorem 3.7 (See [23], Theorem 2.1) Let be a log-concave probability on Rn . Assume that there exist 1 > > 12 and ı > 0 such that for any Borel set E Rn 1 ˚ 1 with .E/ D 12 we have E ı , where E ı D x 2 Rn I d.x; E/ 1ı . Then 1 : Is./ ı 2 We present a sketch of the proof of this last result. Proof (Sketch) Recall that for a log-concave probability, Cheeger’s isoperimetric inequality says that for every Borel set E Rn C .E/ Is./ minf.E/; 1 .E/g; being Is./ the best possible constant. Let I W .0; 1/ ! RC be the isoperimetric profile, defined by I .t/ D inf C .E/ E
0 < t < 1;
where the infimum is taken over all the Borel sets E such that .E/ D t. It is well known that I is concave and so 1 I .t/ 2I minft; 1 tg 2
0
118
3 Relating the Conjectures
(see Claim 1.4.2). Then Is./ D I 12 . Let A denote an open set with .A/ D 1 and having minimal boundary measure C .A/ D I 12 . Geometric Measure 2 Theory ensures that such an isoperimetric minimizer indeed exists, that its boundary @A cannot have many singularities, and provides a description of the structure of these possible singularities. In particular, the regular open subset of @A is an analytic (n 1)-dimensional submanifold having a well defined unit outer normal and the other we can prove that C .A/ D C .Ac / D 1 part is negligible. In consequence, c I 2 and so either for A or A , which is also a minimizer, we have .At n A/ tC .A/ D tI If we take t D
1 ı
1 : 2
and apply the hypothesis either to A (or Ac ) we have 1 1 1 ı I ı A 1=2 ı : 2 2
and the result holds.
3.3.2 How to Approach Theorem 3.6 Roughly speaking, we need to prove that if we enlarge enough (with some dependence on the dimension) sets of measure .E/ D 12 then their measure increases uniformly, independently of the measure and of the dimension. Theorem 1.4 says that if we have a log-concave probability d.x/ D eW .x/ dx, where W is a C 2 -convex function and Hess W c I , then the probability measure satisfies Poincaré’s inequality with spectral gap greater than or equal to c. Furthermore, the concentration theorem for the spectral gap by Gromov-Milman, Theorem 1.6, says that the concentration function ˛ .t/
1 t p c 16 ; e 2
8t > 0
and hence pc .E t / 1 et 16 ; 8t > 0: q Taking, for instance, t 16 we would obtain Theorem 3.6. c Assume that d.x/ D f .x/dx is a log-concave isotropic probability, consider 1
N
1
d.x/ D f .x/e .x/C 2 hBx;xi dx D e .x/C 2 hBx;xi dx;
3.3 From the Variance Conjecture to the KLS Conjecture
119
N are C 2 -convex functions and B is a symmetric positive definite where , and so , matrix, in such way that also is isotropic. Now, 1 1 N N C 1 hB ; i/ D Hess. . // C B B: Hess. . / 2 2 2 We know that 1
1
jxj2
1
2 hBx; xi D hB 2 x; B 2 xi kB 2 k2 `n !`n jxj D 2
2
kB 1 k`n2 !`n2
;
8x 2 Rn
and so 1 1 B I: 2 2kB 1 k`n2 !`n2 Thus, we could take t C1 kB 1 k1=2 , C1 > 0 absolute, to use Theorem 3.6. Hence, the important thing is to bound from above kB 1 k. The following result summarizes all these ideas. Theorem 3.8 Let be a convex function W Rn ! R and K > 0. Assume that jxj2
d.x/ D Ze .x/ 2K 2 dx is a probability measure on Rn , such that E x D 0. Then (i) For every Borel set A Rn such that 1 9 .A/ 10 10 we have .AKD /
95 ; 100
where D > 0 is some absolute constant. (ii) E hx; i2 K 2 , for every 2 S n1 . Proof (of Theorem 3.8) Part (ii) is a direct consequence of Theorem 1.4, since Hess
1 j j2 2I . / C 2 2K K
120
3 Relating the Conjectures
and so E hx; i2 D Var hx; i K 2 (also a direct proof of this fact can be found in [11], Lemma 5). Part (i) says that we can enlarge uniformly sets with measure far from 0 and 1 and its proof is mainly a consequence of Prékopa-Leindler’s inequality, (see [9], Proposition 2.6) Indeed, denote by .x/ the density of . Consider two functions: f .x/ D .x/A .x/ and g.x/ D .x/.AKD /c .x/. Let x 2 A and y 2 .AKD /c . By the parallelogram law we have
x C y 2 1 1 1 2 2 2 2
2 2 kxk C 2 kyk 4 K D and so,
e
2
1 xCy
2 2K 2
e
D2 8
q 1
1
2
2
e 2 kxk e 2 kyk :
Since is convex,
xCy 2
e
D2 8
p f .x/g.y/
and Prékopa-Leindler’s inequality implies that .A/..AKD /c / e
D2 4
:
Hence we obtain .AKD / 1
1 D2 e 4 ; .A/
which implies (i).
3.3.3 Stochastic Construction In order to take advantage of the results above we will manage the situation in the following way. Given a probability measure on Rn we construct an adapted random process .t /t 0 taking values in the space of absolute continuous 1 probability measures on Rn such that 0 D . For t large enough, t > 2 log , we n n are in the conditions of the previous proposition and t is close to the original .
3.3 From the Variance Conjecture to the KLS Conjecture
121
We are going to consider a stochastic process, solution of a stochastic differential equation. This should be compared with the construction given by Lehec in [21]. We introduce some notation. Let c 2 Rn be a vector, B an n n matrix and f an isotropic log-concave density on Rn . We define a new density associated to f; c; and B having • Mass: Z
1
e hc;xi 2 hBx;xi f .x/dx
Vf .c; B/ D Rn
• Barycenter: af D af .c; B/ D
1 Vf
Z
1
xehc;xi 2 hBx;xi f .x/dx Rn
• Covariance matrix: Af D Af .c; B/ D
1 Vf .c; B/
Z
1 .x af / ˝ .x af / ehc;xi 2 hBx;xi f .x/dx: Rn
Let Wt be a standard Wiener process (or classical Brownian motion) in Rn . Without loss of generality we can assume that is compactly supported so the system of stochastic differential equations c0 D 0; B0 D 0;
1
dct D Af 2 dW t C A1 f af dt dBt D A1 f dt
has a unique solution in some non-empty interval Œ0; t0 , since Vf ; af and Af are smooth functions and suppf is compact. We define the stochastic family of densities 1
t .f /.x/ D ft .x/ WD Ft .x/f .x/ D Vf1 .ct ; Bt /ehct ;xi 2 hBtx ;xi f .x/: They verify the following properties (see [9], Lemmas 2.1, 2.4 and 2.5) Lemma 3.4 The process t .f / has the following properties: (i) The functions ft .x/ are well defined, almost surely finite 8t > 0. Also they are log-concave probability densities and verify 1
df t .x/ D ft .x/hAt 2 .x at /; dW t i;
8 t > 0;
where at and At are their corresponding barycenter and covariance matrix. (ii) The process has a semigroup property, namely,
122
3 Relating the Conjectures
p 1 sCt .f / p t . det As s .f / ı L1 / ı L; det As where 1
L.x/ D As 2 .x as /: (iii) For every x 2 Rn the real process fft .x/gt >0 is a martingale. Using these facts we can prove the important result Proposition 3.1 There exist two absolute constants, C; c > 0 for which the event F defined by F D f!I kAt k`n2 !`n2 C n2 log n ect ; 8 t > 0g has probability P.F / 1 n10 : Furthermore, EP .tr .At // n. Moreover if ! 2 F , for every t > a convex function t W Rn ! R, such that ft is ft .x/ D e
jxj2 t .x/ C 2 n2 log n
1 n2 log n
there exists
:
Proof (Sketch) We only sketch the main ideas for this proof. The main task here is to estimate from above the operator norm for the covariance matrix kAt k`n2 !`n2 . By using Itô’s formula and several computations (see [9], Lemmas 2.4 and 2.5) we arrive at Z dAt D At dt C .x at / ˝ .x at /df t .x/dx: Rn
Define ANt WD At C clear that
Rt 0
As ds At , AN D AN0 D I , a positive definite matrix. It is
p 1 kAt k`n2 !`n2 kANt k`n2 !`n2 tr At p ;
8 p 2 N:
With fine and quite involved computations (see [9], Proposition 3.1 and Lemma 3.2) one can prove that p log tr At D Yt C Zt ; where Yt is a local martingale, Y0 D 0, with
3.3 From the Variance Conjecture to the KLS Conjecture
123
P !I max Yt > C2 p e10p ; t 2Œ0;1=p
and Zt is an adapted process of locally bounded variation and dZ t p 2 n2 : dt Hence 8 < p P !I max log tr At log n > C : t 2Œ0; 21
9 = p
n p
;
e10p :
We take p D dlog ne and obtain 8 < P !I max : t 2Œ0; 2 1
n log n
n
dlog ne
tr At
for some absolute constant C1 > 0. Let 8 < F0 D !I max : t 2Œ0; 2 1
n log n
o log1 n
9 = > C1
dlog ne
tr At
log1 n
;
n10
9 = C1 : ;
Integrating the formula in Lemma 3.4(i) we obtain that the measure t satisfies 1
ft .x/ D f .x/ect Chbt ;xi 2 hBt x;xi where ct , bt are processes and Z
t
Bt D 0
A1 s ds:
On the other hand, At Bt1 and so At kBt1 k`n2 !`n2 I . Thus dBt 1 D A1 I t dt kBt1 k and therefore 1 1 d : 1 1 dt kBt k`n2 !`n2 kBt k`n2 !`n2
124
3 Relating the Conjectures
By integrating this differential inequality we eventually obtain that if the event F0 occurs Bt
C t 2 1 n log n I; e n2 log n
8t
1 n2 log n
with C > 0 an absolute constant, which implies the proposition. As a corollary we deduce Corollary 3.1 There exist absolute constants C; c; D > 0 such that for every ! 2 1 F D fkAt k`n2 !`n2 C n2 log n; 8 t > og we have that if E 2 Rn and t 2 log n n satisfies 1 10
Z ft .x/dx E
9 10
then Z Dn
p
f .x/dx c: log nEnE
3.3.4 Thin-Shell Implies Spectral Gap Let f be the density of an isotropic log-concave probability on Rn . Let E Rn be a measurable set such that Z 1 f .x/dx D : 2 E We need to show that Z f .x/dx c E CD nE
p for some absolute constants c; C and D D n log n, where E CD is the CD extension of E. Consider the stochastical process ft .x/, t > 0. By the martingale property we have Z
Z
f .x/dx D E E CD nE
ft .x/dx
8t > 0:
E CD nE
According to Corollary 3.1 we proceed to introduce the function
3.4 Guédon and Milman’s Estimate for the Thin-Shell Width
125
Z g.t/ D
ft .x/dx: E
If we prove the following Lemma 3.5 There exists an absolute constant T > 0 such that 9 1 1 g.T / ; : P !I 10 10 2 then we can follow, since 9 4 1 P F\ g.T / : 10 10 10 Hence Z
Z
f .x/dx D E E CD nE
fT .x/dx E CD nE
.using Corollary 3.1/
4c : 10
p We finish taking an absolute constant D > 0 such that, Dn log n T . In order to prove Lemma 3.5, we use Itô’s formula (see [9], Lemma 4.1) and deduce that 1 2 E g.t/ t: 2 Then the result follows by Markov’s inequality.
3.4 Guédon and Milman’s Estimate for the Thin-Shell Width In this section we will present the ideas approaching Guédon and Milman’s estimate for the thin-shell width. The result is the following: Theorem 3.9 (Guédon and Milman, see [15]) Let be an isotropic log-concave measure in Rn then ˇ ˇ p ˇ jxj ˇ 3 n ˇ ˇ x 2 R W ˇ p 1ˇ t C ec n minft ;t g n for every t > 0, where C; c > 0 are absolute constants. In particular 1
Cn 3 :
126
3 Relating the Conjectures
Two consequences of this theorem are consequences of Paouris’s strong deviation inequality and a small ball probability estimate. Corollary 3.2 (Guédon and Milman, see [15]) Let be an isotropic log-concave measure on Rn . Then (i) For every t 0 we have p ˚ p 3 x 2 Rn W jxj .1 C t/ n ec n minft ;t g ;
where c > 0 is an absolute constant. (ii) For every t 2 .0; 1/ we have p ˚ c2 p 3 x 2 Rn W jxj .1 t/ n ec1 n minft ;log 1t g ;
where c1 ; c2 > 0 are absolute constants. Moreover, better and suitable results can be obtained if we assume that the logconcave probability satisfies a better concentration inequality. The main theorem is a consequence of the strong technical inequality Theorem 3.10 (Guédon and Milman, see [15]) Let be an isotropic log-concave probability on Rn . Then 1
(i) If 1 jp 2j c1 n 6 , we have 1C
jp 2j n
1 3
1
.E jxjp / p .E
1
jxj2 / 2
1CC
jp 2j 1
:
n3
p 1 (ii) If c1 n 6 jp 2j c2 n, we have 1C
p jp 2j 1
n4
1
.E jX jp / p 1
.E jX j2 / 2
1CC
p jp 2j 1
n4
:
Before sketching the ideas of the proof of Theorem 3.10 let us recall the previous known results. Anttila, Ball and Perissinaki, in his paper [1] introduced the "-concentration property, related to the central limit problem for convex bodies and a Berry-Essentype theorem and they posed the following question: Does there exist a sequence "n # 0 such that for every isotropic log-concave measure on Rn ˇ ˇ ˇ jxj ˇ ˇ ˇ x 2 R W ˇ p 1ˇ "n "n ‹ n
n
3.4 Guédon and Milman’s Estimate for the Thin-Shell Width
127
Klartag, in a breakthrough work (see [18]), gave a positive answers to this question proving that ˇ ˇ ˇ jxj ˇ 2 x 2 Rn W ˇˇ p 1ˇˇ " C nc" n
(3.3)
for any isotropic log-concave probability on Rn . Moreover, in the same paper Klartag gave a complete solution to the central limit problem for convex bodies. Soon after, an almost similar estimate was obtained in [13]. In both papers the rates of "n were weak, only of the order of some negative power of log n. Klartag, in [19], improved his estimate (3.3) from logarithmic to polynomial in n as follows (for any small " > 0). ˇ ˇ 1 " 10 " ˇ jxj ˇ p 3 3 ˇ ˇ x 2 R W ˇ p 1ˇ t n C" ec" n t n
n
8 t 2 Œ0; 1:
His main idea was to prove the result, first for radially symmetric densities for which jxj is highly concentrated around his mean and after, using concentration of measure arguments, to reduce the general case to the radial one. More exactly, using the fact that for any 2 S n1 , a k-dimensional subspaces F 2 Gn;k satisfies with large probability that 1 1 p jPF j p : n k jxj In this way Klartag reduces the study of deviations of p to the one of jPpF xj for n k most F 2 Gn;k . A key step is to get a version of Dvoretzky’s theorem for logconcave measures. In fact, once projected onto subspaces whose dimension is a power of n, PF x becomes approximately spherically-symmetric. In order to build almost radial projection measures, Klartag uses the following arguments: In order to gain smoothness, Klartag shows that, without loss of generality, one can prove the result for Y D X C Gn , where X is a random vector distributed according to and Gn is an n-dimensional standard Gaussian, random vector independent of X . He obtains then a Lipschitz estimate for the function h W SO.n/ ! R given by h.U / D log PF0 f .U.x0 ///, where F0 is a fixed k-dimensional subspace in Rn , x0 2 F0 and PF0 .f / is a marginal of the density of Y . Then he applies concentration of measure phenomena for this Lipschitz function on SO.n/. More recently Fleury (see [12]) improved Klartag’s technique and estimate to:
1 jxj 2 x 2 Rn W p 1 C t C ecn 4 t n 1 jxj 8 x 2 Rn W p 1 t C ecn t n
8 t 2 Œ0; 1 8 t 2 Œ0; 1:
Note that for t D nı (ı > 0, small) Klartag’s estimate is still better.
128
3 Relating the Conjectures
3.4.1 Main Estimate Guédon and Milman follow the ideas in the works by Paouris, Klartag and Fleury. X C Gn They consider the random variable Y D p , where Gn is an independent 2 standard Gaussian random vector in Rn . We will denote the distribution law of Y by Let k be a fixed integer 2 k n 1, to be defined later. They consider the projections of Y onto a k-dimensional subspace F 2 Gn;k in order to use V. Milman’s approach to Dvoretzky’s theorem to identify lower-dimensional structures in most marginals PF Y . It is easy to check that 1
.E jyjp / p 1
.E jyj2 / 2
1
1
.E ˝ jPF yjp / p 1
.E ˝ jPF yj2 / 2
D
.E hk;p .U // p 1
;
.E hk;2 .U // 2
(3.4)
where hk;p W SO.n/ ! RC is defined by Z hk;p .U / WD jS
k1
1
t pCk1 U.E0 / g.tu.0 //dt;
jk1 0
E0 2 Gn;k and 0 2 SE0 are fixed, denotes the Haar probability measure on Gn;k and on SO.n/, g is the density of Y in Rn and U.E0 / g denotes the marginal density of g on U.E0 /, i.e., Z U.E0 / g.x/ D
U.E0 /?
g.x C y/dy ;
x 2 U.E0 /:
The most important tool is to control the log-Lipschitz constant of hk;p , i.e, the Lipschitz constant of the logarithm of hk;p . They prove Theorem 3.11 (Guédon-Milman) If p k C 1 then the log-Lipschitz constant of hk;p W SO.n/ ! RC is bounded by 3
Lk;p C maxfk; pg 2 ; where C > 0 is an absolute constant. This result improves Klartag’s and Fleury’s previous estimates. In order to prove this estimate Guédon and Milman use geometric convexity arguments. They consider the convex bodies Kk;q introduced by Ball [3] and a variation of the Lq C centroid bodies, introduced by Lutwak and Zhang [22]. Indeed, let Zmax.k;p/ .g/ n R be the one-sided Lq -centroid body defined by its support functional hZ C
max.k;p/
Z .y/ D 2 .g/
Rn
q1 maxfhx; yi; 0gg.x/dx :
3.4 Guédon and Milman’s Estimate for the Thin-Shell Width
129
Recall that the geometric distance between two sets K; L in Rn is dist.K; L/ WD inffC2 =C1 W C1 L K C2 L; C1 ; C2 > 0g: The main result they proved is the following Theorem 3.12 (Guédon-Milman) If p k C 1 then the log-Lipschitz constant of hk;p W SO.n/ ! RC is bounded by C Lk;p C maxfk; pg dist.Zmax.k;p/ .g/; B2n /;
where C > 0 is an absolute constant. After that, since for q 2, p ZqC .g/ c qB2n ; and p ZqC .g/ .C1 q C C2 q/B2n (see the proof of these facts in [15], Lemmas 2.2 and 2.3) they deduce Theorem 3.11. The proof of Theorem 3.12 is a tour de force (see the precise details in [15], 2.2 Proof of Theorem 2.1). We sketch them here: By the symmetry and transitivity of SO.n/ and since E0 2 Gn:k is arbitrary, it is enough to bound the Euclidean norm of the gradient jrU0 log hk;p j at U0 D I . We consider an orthonormal basis in E0 containing 0 and we complete it to an orthonormal basis in Rn . In this basis the anti-symmetric matrix M WD rI log hk;p 2 TISO .n/, the tangent space to SO.n/ at the identity element corresponding to the standard Riemannian metric in SO.n/, has an special expression which allows us to decompose it in three summands. jrI log hk;p j2 D kV1 k2HS C kV2 k2HS C kV3 k2HS : They are associated to three subspaces of Ti SO.n/, i D 1; 2; 3. Given B 2 Ti the geodesic emanating from I in the direction of B, Us WD expI .sB/ 2 SO.n/, s 2 R is a Typei movement. Recall that jBj D hB; Bi WD gI .B; B/ D 12 kBk2HS . Since d log hk;p .Us / jsD0 D hrI log hk;p ; Bi ds and we can compute kVi kHS D sup 06DB2Ti
hrI log hk;p ; Bi ; jBj
130
3 Relating the Conjectures
the goal is to obtain a uniform upper bound on the derivative of log hk;p induced by a Typei movement. After analyzing the three cases independently and several computations (see 2.2.1–2.2.3 in [15]) the authors arrive at the result using a crucial fact proved by Ball in [3] in the even case and by Klartag [17] in general. Lemma 3.6 If g is a log-concave density in Rn and g.0/ > 0 and q 1, the expression Z kxk WD q
q1
1
t
q1
g.tx/dt
;
x 2 Rn
0
is almost a norm, with the only difference that kxk D kxk only for 0. They can prove m C ; 1 d.Zmaxfm;pg C max .w/; B2m /; mCp
d.KmCp .w/; B2m /
R where w denotes a log-concave function on Rm with 0 < Rn w < 1 , barycenter at the origin and greater than or equal to m C 1 (see, [15] Theorem 2.5). Eventually the authors prove their estimate, Theorem 3.11 here, which improves the previous one by Klartag of order k 2 (see [19]). Proof (of Theorem 3.10. Sketch) In order to prove Theorem 3.10 for the measure the authors have to estimate the moments, (3.4), by passing to SO.n/. According to Fleury’s argument they need to estimate 1 1 d d log .E jyjp / p D log E hk;p .U / p dp dp ..p C n/=2/ .k=2/ d 1 log : C dp p .n=2/ ..p C k/=2/ The second term in the right-hand side of the inequality is smaller than or equal d to 0, as it can be shown using the fact that the function dp log .p/ is concave. 1 1 Entk;p .t p / 1 Entk;p .t p / d log E hk;p .U / p D 2 D ; dp p Ek;p .t p / p 2 E hk;p .U / where Z
1
'.t/ jS k1 jk1 t k1 U.E0 / g.tU.0 //dt:
Ek;p .'/ D E 0
The expression
3.4 Guédon and Milman’s Estimate for the Thin-Shell Width
131
1 Entk;k .t p / p 2 E hk;p .U / can be decomposed in two summands. The first one is controlled by using the logarithmic Sobolev inequality Ent .f /
c E jrf j2 q
which is satisfied by any Lipschitz function f W SO.n/ ! RC . The second summand is also controlled by Cauchy-Schwartz and Hölder’s inequalities and Stirling formula. Both together give the following estimate 1 d c d log .E jyjp / p 2 .2L2k;p C 3L2k;0 / C dp p n dp
.k C p/ 1 log p .k/
c C .2L2k;p C 3L2k;0 / C 2 p n k 3 1 k C C 2 p n k
for every integer k 2 Œmaxf2; 2jpj C 1g; n. Optimizing in k in that range k 1
1
1
jpj 2 n 4 , when p 2 Πp4n ; n642 and we achieve 1 C2 d log .E jyjp / p : 1 1 dp jpj 2 n 4 Integrating in p the following estimates are obtained: 1 (i) If p 2 p4n ; n642 , !1 p
1
.E jyj /
1 p 1
.E jyj2 / 2
C
e
jp2j 1 n2
2
:
1 (ii) If p 2 n642 ; p4n ,
p
.E jyj / .E jyj
1 p
p4 n
/
C p n 4
e
1 4 j!2 jp p n 1 n2
:
132
3 Relating the Conjectures
The gap between the p4n and
p4 n
moments needs another estimate and is treated
by using Fleury’s arguments. Let p0 D p4n be the critical exponent and k0 fixed, let’s say, k0 D 5 for instance. Borell’s concavity implies that 1
1
1
hk20 ;p0 .U /hk20 ;p0 .U / .1 C Cp20 /hk20 ;p0 .U /: Taking expectation and using Cauchy-Schwartz and Hölder’s inequalities (to compare L 1 and L1 norms) we achieve 2
" .1CCp20 / .E hk0 ;p0 .U //E hk0 ;p0 .U //
1 2
e
C2
L2k ;p CL2k ;p 0 0 0 0 n
Lk ;p Lk ;p C 0 0 0 0 n
# ;
which implies 1
.E jyjp0 / p0 .E jyjp0 /
p1
0
C 1C p : n
This finishes the proof of Theorem 3.10 (see the original proof in [15], 3.1–3.4 for a more detailed explanation of these estimates).
3.4.2 How to Derive the Deviation Estimates First of all we deduce the deviation estimates for , the distribution measure of X C Gn Y D p . 2 Proposition 3.2 Under the same assumptions as in Theorem 3.10 we have (i) For every t 0, p p 3 fy 2 Rn W jyj .1 C t/ ng ec n minft ;t g :
(ii) For every t 2 Œ0; 1, p c2 p 3 fy 2 Rn W jyj .1 t/ ng C ec n maxft ;log 1t g :
Proof (Sketch) We consider t 2 RC D Œ0; "n / [ Œ"n ; t0 / [ Œt0 ; 1/, "n minf1; pCn g. For t t0 , Paouris’s estimate is enough. For t 2 Œ0; "n / we have, by Markov’s inequality,
3.4 Guédon and Milman’s Estimate for the Thin-Shell Width
p fy 2 Rn W jyj .1 C t/ ng
133
p 3 E jyj2 1 2t c nt D e e : n.1 C t/2 .1 C t/2 1
For "n < t < t0 , we choose p1 in the corresponding range, such that t D Then p1
.E jyj /
2C jp1 2j 2 1 n4
.
p t n 1C 2
1 p1
and Markov’s inequality gives the result. p The other inequality can be obtained in a similar way. We take p2 2 .c n; 0/ 1
such that t D
2C jp2 2j 2 1 n4
. Then
o n ˚ 1 p y 2 Rn W jyj .1 t/ n y 2 Rn W jyj .1 t=2/.E jyjp2 / p2 p2 t t p2 e 2 : 1 2 Hence we arrive at 1 ˚ p 3 y 2 Rn W jyj .1 t/ n C2 ecn 2 t ;
for every t 2 Œ
c 1 n2
p ; t0 . Let now p3 D c n such that 1
.E jyjp3 / p3
1p n: 2
For every " 2 0; 12 o n ˚ p 1 y 2 Rn W jyj " n y 2 Rn W jyj 2" .EjY jp3 / p3 .2"/p3 1
1
D ec3 n 2 log. 2" / and the result follows. In order to deduce the corresponding inequalities in Theorem 3.9 for the measure , the authors use the following result by Klartag [18] Proposition 4.1, which immediately implies the result: n
p
(
r n
fx 2 R W jxj .1 C t/ ng C y 2 R W jyj
.1 C t/2 C 1 p n 2
)
134
3 Relating the Conjectures
and (
p
n
r n
fx 2 R W jxj .1 t/ ng C y 2 R W jyj
) .1 t/2 C 1 p n 2
for some absolute constant C 1. If we want to get the corresponding estimates for appearing in Theorem 3.10 we need to work a bit more. We use an argument of Fleury and convexity. Then, if n is the Gaussian measure and y D x C z, E jyj2p E˝n
jxj2 C jzj2 2
p
p
n 2 E jxjp ;
E jxj2 D E jyj2 , and 1
.E jxjp / p 1
.E jxj2 / 2
1
.E jyj2p / 2p
!2 ;
1
.E jyj2 / 2
8 p 1:
Hence, repeating the arguments before we have the inequality and one can prove
1
.E jX jp / p 1
.E jX j2 / 2 1
1CC
jp 2j
12
1
n2 1
for p 3. The estimates for C1 n 6 p C2 n 4 in Theorem 3.10 follow. Using the same arguments as in Proposition 3.2 with we can obtain the part (i) of this proposition and so, with Fleury’s arguments in [12] Lemma 6, the rest of the estimates for the moments can be deduced. For the negative moments estimates we use Paouris’s small-ball estimate together with the inequality 1 p 3 fx 2 Rn W jxj .1 t/ ng C ecn 2 t
8 t 2 Œ0; 1
and integration by parts, although the computation is not entirely straightforward. This finishes the proof.
References 1. M. Anttila, K. Ball, I. Perissinaki, The central limit problem for convex bodies. Trans. Am. Math. Soc. 355(12), 4723–4735 (2003) 2. K. Ball, Isometric Problems in `p and Sectios odf Convex Sets. Ph.D. theses, Cambridge University, 1986
References
135
3. K. Ball, Logarithmic concave functions and sections of convex bodies in Rn . Studia Math. 88, 69–84 (1988) 4. K. Ball, V.H. Nguyen, Entropy jumps for random vectors with log-concave density and spectral gap. Studia Math. 213, 81–96 (2012) 5. N.M. Blachman, The convolution inequality for entropy powers. IEEE Trans. Inf. Theory 2, 267–271 (1965) 6. J. Bourgain, On high dimensional maximal functions associated to convex bodies. Am. J. Math. 108, 1467–1476 (1986) 7. J. Bourgain, On the Isotropy Constant Problem for 2 -bodies. Lecture Notes in Mathematics, vol. 1807 (Springer, 2003), pp. 114–121 8. I. Csiszár, Informationstheoretische Konvergenzbegriffe im Raum der Wahrscheinalichkeitsverteilungen. Magyar Tud. Akad. Mat. Kutató Int. Kozl. 7, 137–158 (1962) 9. R. Eldan, Thin shell implies spectral gap up to polylog via stochastic localization scheme. Geom. Funct. Anal. 23, 532–569 (2013) 10. R. Eldan, B. Klartag, Approximately gaussian marginals and the hyperplane conjecture. Contemp. Math. 545, 55–68 (2011) 11. R. Eldan, J. Lehec, Bounding the norm of a log-concave vector via thin-shell estimates. Lecture Notes in Math. Israel Seminar (GAFA) 2116, 107–122, (Springer, Berlin 2003) 12. B. Fleury, Concentration in a thin shell for log-concave measures. J. Funct. Anal. 259, 832–841 (2010) 13. B. Fleury, O. Guédon, G. Paouris, A stability result for mean width of Lp -centroid bodies. Adv. Math. 214(4), 865–877 (2007) 14. M. Fradelizi, Sections of convex bodies through therir centroid. Arch. Math. 204, 515–522 (1997) 15. O. Guédon, E. Milman, Interpolating thin-shell and sharp large-deviation estimates for isotropic log-concave measures. Geom. Funct. Anal. 21(5), 1043–1068 (2011) 16. B. Klartag, A geometric inequality and a low M -estimate. Proc. Am. Math. Soc. 132(9), 2919– 2628 (2004) 17. B. Klartag, On convex perturbation with a bounded isotropic constant. Geom. Funct. Anal. 16(6), 1274–1290 (2006) 18. B. Klartag, A central limit theorem for convex sets . Invent. Math. 168, 91–131 (2007) 19. B. Klartag, Power-law estimates for the central limit theorem for convex sets. J. Funct. Anal. 245, 284–310 (2007) 20. B. Klartag, Uniform almost sub-gaussian estimates for linear functionalson convex sets. Algebra i Analiz (St. Peesburg Math. J.) 19(1), 109–148 (2007) 21. J. Lehec, Representation formula for the entropy and functional inequalities. Ann. Inst. H. Poincaré Probab. Stat. 49(3), 885–899 (2013) 22. E. Lutwak, G. Zhang, Blaschke-Santaló inequalities. J. Differ. Geom. 47(1), 1–16 (1997) 23. E. Milman, in Isoperimetric Bounds on Convex Manifolds, Proceedings of the Workshop on Concentration, Functional Inequalities and Isoperimetry, Contemporary Math., vol. 545 (2011), pp. 195–208 24. V.D. Milman, A. Pajor, Isotropic Position and Inertia Ellipsoids and Zonoids of the Unit Ball of a Normed n-dimensional Space, GAFA Seminar 87–89, Springer Lecture Notes in Math., vol. 1376 (1989), pp. 64–104 25. M.S. Pinsker, Information and Information Stability of Random Variables and Processes (Holden-Day, San Francisco, 1964)
Appendix A
A.1 Brunn–Minkowski Inequality The most important integral inequality in convexity is Hölder’s inequality which states that for any two non-negative, measurable functions f; g W Rn ! RC and 0 1 we have 1 Z
Z
Z f .x/
1
g.x/ dx
Rn
f .x/dx
g.x/dx
Rn
:
Rn
In the case that f D A and g D B are the characteristic functions of A; B, measurable sets in Rn , Hölder’s inequality reads jA \ Bjn jAjn1 jBjn
8 0 1;
which is equivalent to jA \ Bjn minfjAjn; jBjn g: It is clear that these inequalities cannot be reversed at all. However, we can give a kind of reverse inequality, due to Prékopa and Leindler, using one type of convex convolution of functions. Given two non-negative measurable functions f; g and 0 1 defined on Rn , we consider the function f 1 sup g defined by f 1 sup g .z/ WD
sup
f .x/1 g.y/ :
zD.1/xCy
© Springer International Publishing Switzerland 2015 D. Alonso-Gutiérrez, J. Bastero, Approaching the Kannan-Lovász-Simonovits and Variance Conjectures, Lecture Notes in Mathematics 2131, DOI 10.1007/978-3-319-13263-1
137
138
A Appendix
This function is not necessarily measurable, but we can consider its exterior Lebesgue integral Z
Z
h.z/dz W f 1 sup g .z/ h.z/ :
f 1 sup g .z/dz D inf Rn
Rn
Then we have Theorem A.1 Let f; g be two non-negative measurable functions defined on Rn and 0 1. Then 1 Z
Z
f .x/dx
g.x/dx
Rn
Z
f 1 sup g .x/dx:
Rn
Rn
This result is a consequence of the following inequality: Theorem A.2 (Prékopa–Leindler’s Inequality) Let f; g; h be three non-negative measurable functions defined on Rn and 0 1 such that f .x/1 g.y/ h.z/
z D .1 /x C y:
whenever
Then 1 Z
Z
f .x/dx Rn
g.y/dy
Z
Rn
h.z/dz: Rn
Proof We present the approach learned from K. Ball (see [3] and [9]). We can assume, by homogeneity, that kf k1 D kgk1 D 1. In dimension n D 1, let A, B be two non-empty compact sets in R. It is clear that A C B .min A C B/ [ .A C max B/ and .min A C B/ \ .A C max B/ D min A C max B; which has volume 0, so we have jA C Bj1 jAj1 C jBj1 for compact sets in R and by an approximation procedure, for any couple of Borel sets in R. Then for any 0 t < 1, since fx 2 R W h.x/ tg .1 /fx 2 R W f .x/ tg C fx 2 R W g.x/ tg;
A.1 Brunn–Minkowski Inequality
139
we have Z
Z
1
h.x/dx
jfx 2 R W h.x/ tgjdt 0
R
Z
Z
1
.1 /
1
jfx 2 R W f .x/ tgjdt C 0
jfx 2 R W g.x/ tgjdt 0
(by the arithmetic-geometric mean inequality) 1 Z Z f .x/dx g.x/dx : R
R
The case n > 1 is deduced by induction. Fix x1 2 R, define fx1 W Rn1 ! Œ0; 1/ by fx1 .x2 ; : : : ; xn / D f .x1 ; : : : ; xn /. By assumption we have hz1 ..1 /.x2 ; : : : ; xn / C .y2 ; : : : ; yn // fx1 .x2 ; : : : ; xn /1 gy1 .y2 ; : : : ; yn / for any .x2 ; : : : ; xn /; .y2 ; : : : ; yn / 2 Rn1 , whenever z1 D .1 /x1 C y1 . By the induction hypothesis, 1 Z
Z
Z Rn1
hz1 .z/d z
Rn1
fx1 .x/d x
Rn1
gy1 .y/d y
:
Applying again the inequality for n D 1 and Fubini’s theorem we obtain the result. If we apply this inequality to f D A and g D B , characteristic functions of A and B Borel sets in Rn , we obtain Theorem A.3 (Brunn–Minkowski Inequality) Let A; B two Borel sets in Rn . For any 0 1 jAj1 jBj j.1 /A C Bj;
(A.1)
or, equivalently, 1
1
1
jAj n C jBj n jA C Bj n ;
(A.2)
whenever A 6D ; and B 6D ;. Inequality (A.1) is a dimension-free version of Brunn–Minkowski inequality (note that in this case the set .1 /A C B is measurable). A B Inequalities (A.1) and (A.2) are equivalent. By taking A0 D , B0 D 1 1 jAj n jBj n 1 jBj n and D in (A.1), we get (A.2). 1 1 jAj n C jBj n
140
A Appendix
The reverse implication is easy to obtain, given any 0 1, 1
1
1
j.1 /A C Bj n .1 /jAj n C jBj n (by the arithmetic-geometric mean inequality) jAj
1 n
jBj n :
A.2 Consequences of Brunn–Minkowski Inequality Proposition A.1 Any log-concave probability on Rn satisfies Brunn–Minkowski inequality, i.e., ..1 /A C B/ .A/1 .B/ for any A; B Rn non-empty Borel sets and any 0 1. Proof We have that d.x/ D eV .x/ dx where V W Rn ! .1; 1 is a convex function. We take f .x/ D A .x/eV .x/ , g.y/ D B .y/eV .y/ and h.z/ D .1/ACB .z/eV .z/ : Then we apply Prékopa–Leindler’s inequality. Proposition A.2 (Isoperimetric Inequality in Rn ) Let A be a bounded Borel set in Rn then 1 n1 j@Ajn1 1 n
1
n1 jS n1 jn1 1 n
jB2n jn
jAjn
1
1
D n n1 jB2n j n.n1/ ;
where j@Ajn1 D lim inf t !0
jAt jn jAjn t
and At D fx 2 Rn I d.x; A/ tg D A C tBn2 . Proof It is clear that n 1 1 jAjn jAt jn jAjn D jA C tBn2 jn jAjn jAjnn C tjB2n j n n1
1
ntjAjn n jB2n j n :
A.2 Consequences of Brunn–Minkowski Inequality
141
Hence, n1
1
j@Ajn1 njAjn n jB2n j n and the result follows. Proposition A.3 (Isoperimetric Inequality in S n1 by P. Levy) Let A be any Borel set in A S n1 such that .A/ 1=2, where is the uniform probability on S n1 . Then 2n
.A" / 1 2eC "
for any
0 < " < 1;
where C > 0 is an absolute constant. (Caps are the minimizers for measuring the boundary). We show a proof given by Arias de Reyna et al. [2]. The original proof gives better constants: r "2 n " .A / 1 e 2 : 8 We begin showing the following lemma: Lemma A.1 Let be the uniform probability on B2n , i.e, .A/ D A; B be Borel sets in B2n . Then
jA \ B2n j . Let jB2n j
d.A; B/2 n 8 minf.A/; .B/g e :
Proof Assume that A; B are closed in B2n and let ˛ D minf.A/; .B/g , D d.A; B/. By Brunn–Minkowski inequality ˇ1 ˇ ˇn ˇ1 ˇ A C 1 B ˇ 1 jAj n1 C 1 jBj n1 H) A C B ˛: ˇ2 2 ˇ 2 2 2 If a 2 A, b 2 B, H) ja C bj2 D 2jaj2 C 2jbj2 ja bj2 4 2 and then ACB 2
r 1
2 n B : 4 2
Thus,
ACB ˛ 2
n 2 n 2 2 D 1 e 8 : 4
142
A Appendix
Proof (of Proposition A.3) Let A S n1 with .A/ 1=2. Given " > 0 denote B D .A" /c . Fix 0 < < 1. Define AN D fta 2 Rn W t 1; a 2 Ag and BN D fsb 2 Rn W s 1; b 2 Bg B2n . N bN D sb 2 B, N we have If aN D ta 2 A; N D jta sbj ja bj D ja bj ": jaN bj Besides, notice that N D .A/
1 jB2n j
Z
1
r n1 dr.A/ D .1 n /.A/
N D .1 n /.B/. and, in the same way, .B/ Since .A/ 1=2 we have that .B/ 1=2 and then, by the previous lemma, n2 "2 8 : .1 n /.B/ D ˛ e
1
Hence, taking D 2 n , we obtain 2n
..A" /c / 2eC " and the result follows.
A.3 Borell’s Inequality and Concentration of Mass The following inequality, proved by C. Borell [4], is verified by every log-concave probability measure. As a consequence, we show the exponential decay of the distribution function and the equivalence of all the p-th moments of the Euclidean norm. Proposition A.4 Let be a log-concave probability on Rn . Let 12 < 1. Then, for every symmetric convex set A Rn with .A/ , we have that c
..tA/ / for every t > 1.
1
1Ct 2
A.3 Borell’s Inequality and Concentration of Mass
143
Proof It is clear that 2 t 1 .tA/c C A: t C1 t C1
Ac
Then, by Brunn–Minkowski inequality, 2
t 1
1 .Ac / ..tA/c / t C1 .A/ t C1 ; which implies the result. Proposition A.5 (Reverse Hölder’s Inequality and Exponential Decay) There exist absolute constants C1 ; C2 D 2C1 e > 0 such that for any log-concave probability on Rn and for any semi-norm f W Rn ! Œ0; 1/ we have 1 (i) E f p p C1 p E f; 8 p > 1, f
(ii) E˚e C2 E f 2, and (iii) x 2 Rn W f .x/ C2 tE f 2et ;
8 t > 0:
Proof (i) Since any semi-norm is integrable we can assume E f D 1. Let A be the set A D fx 2 Rn W f .x/ < 3g. By Markov’s inequality .A/ 23 . Then, 2 fx 2 R W f .x/ 3tg D ..tA/ / 3 n
c
1Ct log 2 1 2 t 2 2 et 2 2
whenever t > 1. Let p > 1. Then Z
3
E f p D
p t p1 fx 2 Rn W f .x/ > tgdt 0
Z
1
p t p1 fx 2 Rn W f .x/ > tgdt
C 3
Z
1
p s p1 e2s ds .C1 p/p
3p C 3p 1
for some absolute constant C1 > 0 and i) follows. (ii) Assume again that E f D 1. Let A > 0 to be fixed later. f
E e A D 1 C
p 1 X f 1 E pŠ A pD1
1 1 p X X C1 e p 1 C1 p p 1C 1C : pŠ Ap A pD1 pD1 The result follows choosing A D 2C1 e.
144
A Appendix
(iii) By Markov’s inequality, we have fx 2 Rn W f .x/ > tE f g D x 2 Rn W
t f .x/ > C 2 E f C2
f
et =C2 E e C2 E f 2e
Ct
2
and (iii) follows. Remark A.1 In the case that f .x/ D jxj, by repeating the arguments and taking 1 A D fx W jxj e3 E jxjp p g in the proof before, p 2, we obtain n
1 o x 2 R W jxj te E jxjp p .1 e3p / n
3
e3p 1 e 3p
1Ct 2
e3pt
for every t 1. Remark A.2 Alesker (see [1]) proved that for isotropic convex bodies, jfx 2 KI jxj > ctEjxjgjn 2et
2
8t > 0
for some absolute c > 0. Remark A.3 Paouris [7] proved the following strong inequality: There exists an absolute constant C > 0 such that for every log-concave probability in Rn we have ( ) 1 1 1 p p 2 2 p p E jxj C max E jxj ; sup E jhx; ij 2S n1
for any p 1. Using Borell’s inequality we have
E jhx; ijp
p1
1 C1 p E jhx; ij2 2 C1 p
for some absolute constant C1 > 0 and for any 2 S n1 . Hence 1 1 E jxjp p C max E jxj2 2 ; p
A.3 Borell’s Inequality and Concentration of Mass
145
for any p 1. If we take p D
)
(
1
t .E jxj2 / 2
, with t max 1;
1
.E jxj2 / 2
we obtain,
by (i) in the latter proposition, 3
jxj > Cte E jxj
2
12
n 1 o jxj > e3 E jxjp p
e
3p
De
3
1 t E jxj2 2
.
/
:
In particular when is isotropic and t 1 p p fx 2 Rn W jxj C1 t ng eC2 t n :
This inequality can also be expressed in the following way: p p fx 2 Rn W jxj .1 C s/ ng eC3 s n
for some s s0 . Indeed, we take t D 1Cs C1 1 (so, s C1 1) and C2 t C3 s. This inequality had been previously obtained by Bobkov and Nazarov in the case of isotropic unconditional log-concave probabilities. Remark A.4 R. Latała and O. Guédon (see [6] and [5]) extended previous results for the range 1 < p 1, since they proved the following “small-ball probability” result: Proposition A.6 There exists an absolute constant C > 0 such that for any norm f W Rn ! Œ0; 1/ and for any log-concave probability on Rn we have (i) fx 2 Rn I f .x/ tE f g Ct
8t > 0;
(ii) For any 1 < p 1 we have
E f p
p1
E f
1 C E f p p : pC1
Proof (Only of (ii)) We can assume 1 < p < 0. Let q D p 2 .0; 1/. Then 1 > t dt D qt x 2 R W f .x/ 0 Z 1 1 C > t dt qtq1 x 2 Rn W 1 f .x/ E f Z
E f
p
1 E f
q1
n
146
A Appendix
Z
p ˚ ds E f q x 2 Rn W f .x/ < sE f qC1 s 0 Z 1 Cp p p 1 C Cq p e ds E f : 1 C Cq E f E f q 1q 1Cp 0 s p E f C
1
Thus,
1
.Ef p / p
1Cp eCp
p1 Ef C1 .1 C p/Ef:
p Remark A.5 Paouris [8] extended this result showing that for any 1 q C3 n we have
E jxjq
q1
1 E jxjq q
for some absolute constant 0 < C3 < 1. Furthermore a small-ball probability estimate can be deduced for every isotropic measure since, in that case, one has p p fx 2 Rn W jxj " ng "c4 n
for any 0 < " < "0 , where "0 ; c4 are absolute constants.
References 1. S. Alesker, 2 -Estimate for the Euclidean norm on a convex body in isotropic position, in Geometric Aspects of Functional Analysis, ed. by J. Lindenstrauss, V.D. Milman. Operator Theory: Advances and Applications, vol. 77 Birkhäuser, Basel (1995), pp. 1–4 2. J. Arias-de-Reyna, K. Ball, R. Villla, Concentration of the distance in finite-dimensional normed spaces. Mathematika 45(2), 245–252 (1998) 3. K. Ball, Logarithmic concave functions and sections of convex bodies in Rn . Stud. Math. 88, 69–84 (1988) 4. C. Borell, Convex measures on locally convex spaces. Ark. Math. 12, 239–252 (1974) 5. O. Guédon, Kahane-Khinchine type inequalities for negative exponent. Mathematika 46, 165– 173 (1999) 6. R. Latała, On the equivalence between geometric and arithmetic means for log-concave measures, in Convex Geometric Analysis (Berkeley, CA, 1996), Mathematical Sciences Research Institute Publications, vol. 34 (Cambridge University Press, Cambridge, 1999), pp. 123–127 7. G. Paouris, Concentration of mass on convex bodies. Geom. Funct. Anal. (GAFA) 16, 1021– 1049 (2006) 8. G. Paouris, Small ball probability estimates for log-concave measures. Trans. Am. Math. Soc. 364(1), 287–308 (2012) 9. G. Pisier, The Volume of Convex Bodies and Banach Space Geometry, vol 94 (Cambridge University Press, Cambridge, 1989)
Index
I s./, 2, 10, 18, 20, 21, 25, 31, 33, 39–41, 111, 113, 114, 117, 118 L20 ./, 15, 17 `np -balls, 4, 72, 79 1 -convex, 96 2 1 , 12, 13, 18, 22, 33, 35–37, 53, 61, 98, 110, 111, 116 1 ./, 11, 22, 23, 34, 37, 41–43 , 3–5, 34, 36, 37, 41, 43–45, 51, 52, 55, 59, 60, 70, 90, 93–95, 144 D , 16, 93, 94 D .˝/, 12, 98 F , 2, 3, 11, 22, 26, 27, 29, 31, 37 C .A/, 2 rf , 2 n , 4, 105 , 44, 116 n , 116 Almost isotropic, 84 Barycenter, 3 Borell’s lemma, 33, 43, 55, 142 Brunn-Minkowski inequality, 137, 139, 140, 143 Cauchy-Schwartz inequality, 57, 105 Central limit problem, 4, 44, 58 Centroid body, 128 Cheeger’s constant, 2, 3, 34 Cheeger’s isoperimetric inequality, 2, 3, 7, 26, 32, 33, 117
Co-area formula, 7, 10 Concentration, 11, 22, 41, 43, 44, 51, 58, 142 Convex body, 2, 5, 104, 106 Convex function, 2, 18 Covariance matrix, 3, 53 Cross-polytope, 90 Cube, 86
Dilation, 1
Eigenvalue, 12, 13 Eigenvector, 12 Entropy, 110 gap, 112 Euclidean, 1, 7 Expectation, 2 Exponential concentration inequality, 26, 32, 33
First-moment concentration inequality, 26, 32, 33
Gaussian, 36, 105, 110, 112, 114, 127 Gradient, 2
Hölder’s inequality, 58, 137 Hörmander’s method, 11, 13–15 Hausdorff measure, 1
© Springer International Publishing Switzerland 2015 D. Alonso-Gutiérrez, J. Bastero, Approaching the Kannan-Lovász-Simonovits and Variance Conjectures, Lecture Notes in Mathematics 2131, DOI 10.1007/978-3-319-13263-1
147
148 Hess, 16, 17, 32, 95, 112 Hyperplane conjecture, vii, 4, 45, 103–105, 109 Inertia matrix, 5 Isoperimetric inequality, 1, 140, 141 Isoperimetric profile, 30 Isotropic, 3, 4, 11, 35, 53, 56, 66, 67, 85, 104–106, 145 constant, 5, 104 KLS conjecture, 3, 4, 34–36, 38, 41, 44, 66, 69, 73, 109, 113 Laplace operator, 13 Laplacian, 11 Largest eigenvalue, 3 Lipschitz, 7, 9, 34, 35, 56, 57, 131 Localization lemma, 38 Locally Lipschitz, 7 Log-concave probability, 2, 53, 105, 145
Index Random walk, 6 Revolution bodies, 4, 66 Riemannian manifold, 28, 32
Sampling algorithm, 6 Simplex, 4, 69 Slicing problem, vii, 103 Small-ball probability, 145 Sobolev inequality, 2 Spectral condition number, 53, 84 Spectral gap, 11, 13, 33, 34, 43, 111, 124 Square negative correlation property, 44, 58, 59, 61, 79, 81, 86 weak averaged, 59 Steiner symmetrization, 85
Talagrand’s inequality, 18, 21 Thin shell, 124, 125 width, 4, 44, 45, 49
Martingale, 115 Median, 10, 18 Minkowski inequality, 57
Unconditional, 4, 41, 92, 93, 98 Uniform probability, 25, 37, 59
Orlicz balls, 81 Outer Minkowski content, 1
Variance, 2 conjecture, 4, 44, 45, 51, 53, 55, 56, 59, 90, 103, 105, 113 Volume-computing algorithm, 5
Poincaré’s inequality, 2, 3, 7, 11, 13, 15, 18, 22, 25, 26, 67 Prékopa-Leindler’s inequality, 137, 138, 140
Young function, 81
LECTURE NOTES IN MATHEMATICS
123
Edited by J.-M. Morel, B. Teissier; P.K. Maini Editorial Policy (for the publication of monographs) 1. Lecture Notes aim to report new developments in all areas of mathematics and their applications - quickly, informally and at a high level. Mathematical texts analysing new developments in modelling and numerical simulation are welcome. Monograph manuscripts should be reasonably self-contained and rounded off. Thus they may, and often will, present not only results of the author but also related work by other people. They may be based on specialised lecture courses. Furthermore, the manuscripts should provide sufficient motivation, examples and applications. This clearly distinguishes Lecture Notes from journal articles or technical reports which normally are very concise. Articles intended for a journal but too long to be accepted by most journals, usually do not have this “lecture notes” character. For similar reasons it is unusual for doctoral theses to be accepted for the Lecture Notes series, though habilitation theses may be appropriate. 2. Manuscripts should be submitted either online at www.editorialmanager.com/lnm to Springer’s mathematics editorial in Heidelberg, or to one of the series editors. In general, manuscripts will be sent out to 2 external referees for evaluation. If a decision cannot yet be reached on the basis of the first 2 reports, further referees may be contacted: The author will be informed of this. A final decision to publish can be made only on the basis of the complete manuscript, however a refereeing process leading to a preliminary decision can be based on a pre-final or incomplete manuscript. The strict minimum amount of material that will be considered should include a detailed outline describing the planned contents of each chapter, a bibliography and several sample chapters. Authors should be aware that incomplete or insufficiently close to final manuscripts almost always result in longer refereeing times and nevertheless unclear referees’ recommendations, making further refereeing of a final draft necessary. Authors should also be aware that parallel submission of their manuscript to another publisher while under consideration for LNM will in general lead to immediate rejection. 3. Manuscripts should in general be submitted in English. Final manuscripts should contain at least 100 pages of mathematical text and should always include – a table of contents; – an informative introduction, with adequate motivation and perhaps some historical remarks: it should be accessible to a reader not intimately familiar with the topic treated; – a subject index: as a rule this is genuinely helpful for the reader. For evaluation purposes, manuscripts may be submitted in print or electronic form (print form is still preferred by most referees), in the latter case preferably as pdf- or zipped ps-files. Lecture Notes volumes are, as a rule, printed digitally from the authors’ files. To ensure best results, authors are asked to use the LaTeX2e style files available from Springer’s web-server at: ftp://ftp.springer.de/pub/tex/latex/svmonot1/ (for monographs) and ftp://ftp.springer.de/pub/tex/latex/svmultt1/ (for summer schools/tutorials).
Additional technical instructions, if necessary, are available on request from
[email protected]. 4. Careful preparation of the manuscripts will help keep production time short besides ensuring satisfactory appearance of the finished book in print and online. After acceptance of the manuscript authors will be asked to prepare the final LaTeX source files and also the corresponding dvi-, pdf- or zipped ps-file. The LaTeX source files are essential for producing the full-text online version of the book (see http://www.springerlink.com/ openurl.asp?genre=journal&issn=0075-8434 for the existing online volumes of LNM). The actual production of a Lecture Notes volume takes approximately 12 weeks. 5. Authors receive a total of 50 free copies of their volume, but no royalties. They are entitled to a discount of 33.3 % on the price of Springer books purchased for their personal use, if ordering directly from Springer. 6. Commitment to publish is made by letter of intent rather than by signing a formal contract. Springer-Verlag secures the copyright for each volume. Authors are free to reuse material contained in their LNM volumes in later publications: a brief written (or e-mail) request for formal permission is sufficient. Addresses: Professor J.-M. Morel, CMLA, École Normale Supérieure de Cachan, 61 Avenue du Président Wilson, 94235 Cachan Cedex, France E-mail:
[email protected] Professor B. Teissier, Institut Mathématique de Jussieu, UMR 7586 du CNRS, Équipe “Géométrie et Dynamique”, 175 rue du Chevaleret 75013 Paris, France E-mail:
[email protected] For the “Mathematical Biosciences Subseries” of LNM: Professor P. K. Maini, Center for Mathematical Biology, Mathematical Institute, 24-29 St Giles, Oxford OX1 3LP, UK E-mail:
[email protected] Springer, Mathematics Editorial, Tiergartenstr. 17, 69121 Heidelberg, Germany, Tel.: +49 (6221) 4876-8259 Fax: +49 (6221) 4876-8259 E-mail:
[email protected]
