\newcount\footnumber \def\foot#1{\global\advance\footnumber by 1 \footnote{$^{\the\footnumber}$}{#1}~~} \def\Corollary #1. #2\par{ \goodbreak\medbreak\noindent{\bf #1 Corollary. \enspace}{\sl#2}\par\medbreak} \def\Lemma #1. #2\par{\goodbreak \medbreak\noindent{\bf #1 Lemma. \enspace}{\it#2}\par\medbreak} \def\Theorem #1. #2\par{ \goodbreak\medbreak\noindent{\bf #1 Theorem. \enspace}{\sl#2}\par\medbreak} \def\Remark #1. {\goodbreak\medbreak\noindent{\bf #1 Remark.}\enspace} \def\integ{\int\limits} \def\text#1{\qquad{\rm #1}\qquad} \def\proof.{\noindent{\bf Proof.}\enspace} \def\Proof #1. {\noindent{\bf Proof #1.}\enspace} \def\subtitle#1\par{\bigskip{\bf #1}\medskip} %=============================== \magnification=1200 \overfullrule=0pt\tolerance=2000 \scrollmode \font\BF=cmbx10 scaled\magstep2 \def\R{\hbox{\sl I\kern-.12em R}} % ???? \def\proofend{\nobreak\hfill\vrule height5pt width4pt depth2pt\break\medskip} \def\rk{\hbox{\rm rk}} \def\mod{\hbox{\rm mod~}} \def\conv{\hbox{\rm conv}} \def\vol{\hbox{\rm vol}} \def\diam{\hbox{\rm diam}} \def\prob{\hbox{\rm Prob}} \centerline{\BF Isoperimetric Problems for Convex Bodies} \centerline{\BF and a Localization Lemma} \bigskip \centerline{Ravi Kannan\footnote{$^1$}{Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA 15213, visiting Yale University; supported by NSF-grant CCR-9208597 to Carnegie-Mellon}} \smallskip \centerline{L\'aszl\'o Lov\'asz\footnote{$^2$}{Department of Computer Science, Yale University, New Haven, CT 06520}} \medskip \centerline{and} \medskip \centerline{Mikl\'os Simonovits\footnote{$^3$}{Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Re\'altanoda u. 13--15. H-1053 Hungary}} \bigskip \noindent{\bf Abstract.} We study the smallest number $\psi(K)$ such that a given convex body $K$ in $\R^n$ can be cut into two parts $K_1$ and $K_2$ by a surface with an $(n-1)$-dimensional measure $\psi(K)\vol(K_1)\cdot\vol(K_2)/\vol(K)$. Let $M_1(K)$ be the average distance of a point of $K$ from its center of gravity. We prove for the ``isoperimetric coefficient'' that $$\psi(K)\ge {{\ln 2}\over M_1(K)},$$ and give other upper and lower bounds. We conjecture that our upper bound is best possible up to a constant. Our main tool is a general ``Localization Lemma'' that reduces integral inequalities over the $n$-dimensional space to integral inequalities in a single variable. This lemma was first proved by two of the authors in an earlier paper, but here we give various extensions and variants that make its application smoother. We illustrate the usefulness of the lemma by showing how a number of well-known results can be proved using it. \subtitle 1. Isoperimetry in a convex body The classical isoperimetric problem is to find a surface with minimal measure which encloses a set of (at least) a given volume. We consider a ``relativized'' version of this problem, where we are given a convex body $K$, and want to find a surface which divides $K$ into two parts, and whose measure is minimum relative to the volumes of the two parts. To be more precise, \hfill\break\hbox{~~~~~~} (a) The $(n-1)$--dimensional Minkowski measure of a set $A\subseteq \R^n$ is defined as the limit (if it exists) of the volume of the $\varepsilon/2$--neighbourhood of $A$ divided by $\varepsilon$, when $\varepsilon\to 0$. (Volume means Lebesque measure.) \hfill\break\hbox{~~~~~~} Define the {\it isoperimetric coefficient} of a convex body $K\subseteq \R^n$ as the largest number $\psi=\psi(K)$ such that for every measurable subset $S\subseteq K$ for which $\partial S \cap K$ ($\partial S$ is the boundary of $S$) has an $(n-1)$-dimensional Minkowski measure, $$ \vol_{n-1}(\partial S\cap K) \ge \psi {\vol(S)\cdot\vol(K\setminus S)\over \vol(K)}\,.\eqno(1.1) $$ (1.1) is often replaced in the definition by $$ \vol_{n-1}(\partial S\cap K) \ge\psi \min\{\vol(S),\vol(K\setminus S)\}.\eqno(1.2) $$ Since the two values are always within a factor of 2 to each other, this does not influence our results in any essential way. Our formulation is more natural when applying the results to Markov chains. The problem of finding sharp lower bounds on the isoperimetric coefficient arose (among others) in connection with randomized volume algorithms. Dyer, Frieze and Kannan (1989) formulated the problem and conjectured a lower bound on $\psi$. Karzanov and Khachiyan (1991) and Lov\'asz and Simonovits (1990), proved (by different methods) a lower bound of $1/d$ (where $d$ is the diameter of $K$ and the conductance was defined according to (1.2)). This result was generalized to the case when Lebesgue measure is replaced by any measure given by a log-concave function $F$ (i.e., when $\vol (T)$ is replaced by $\int_T F$) by Applegate and Kannan (1990). The bound (still using (1.2)) was improved to $\psi(K)\ge 2/d$ by Dyer and Frieze (1991), which is the best possible bound (even for Lebesgue measure) in terms of the diameter, as shown by a very thin long cylinder. However, the diameter may not be the best possible measure to use here. In its applications to volume algorithms and related questions, we need these bounds in the case when the body is rather ``round'' (e.g., in isotropic position, see below), and hence the bound $2/d$ may not be sharp. In this paper we prove two improvements of this bound, in terms of somewhat more complicated measures of the ``linear dimensions'' of $K$. In particular, denote the average distance of a point in $K$ from its center of gravity by $M_1(K)$. Note that $M_1(K)$ may be much smaller than the diameter, e.g. in case of a regular simplex $S^n$ of diameter $d$, $M_1(S^n)\approx {d\over \sqrt{n}}$. \bigskip \noindent{\bf Main Theorem.} {\it For every convex body $K$, $$ \psi(K)\ge {\ln 2 \over M_1(K)}. $$} \bigskip We also formulate a conjecture that would determine the value of the isoperimetric coefficient up to a constant factor. We start with describing a general method for proving inequalities involving the volume and other measures (Localization Lemma). This method reduces high-dimensional integral inequalities to 1-dimensional ones. In Section 3 we illustrate the method by giving new proofs of some important inequalities in convex geometry, some of which are sharper than the earlier versions. Our results on the isoperimetric problem are contained in Section~5. \subtitle 2. Localization Lemma Below we shall use the notion of upper and lower semi-continuous functions. {\it Lower semi-continuous functions} are limits of monotone increasing sequences of continuous functions. They can also be characterized by that $$\liminf_{x\to x_0}f(x)=f(x_0)\text{for~every}x\in D_f$$ where $D_f$ is the domain of $f$, in our case mostly an open or closed convex set $K$ or the whole space $\R^n$. The indicator function of an open set is always lower semi-continuous but not continuous. This is the reason why we cannot restrict our considerations to continuous functions. {\it Upper semi-continuous functions} are the limits of monotone decreasing functions, and the indicator functions of closed sets are upper semi-continuous. \bigskip \leftskip=0.5cm \rightskip=0.5cm {\bf Corrigendum to Lov\'asz--Simonovits paper (1993):} In our earlier paper we exchanged the word "upper" and "lower" in speaking of semi-continuous functions. Otherwise everything was correct. Here we return to the usual (correct) definitions. \leftskip=0cm \rightskip=0cm \bigskip The following general tool for proving geometric inequalities was proved by Lov\'asz and Simonovits (1993). \medskip \noindent{\bf 2.1 Lemma.} {\it Let $g$ and $h$ be lower semi-continuous Lebesgue integrable functions on $\R^n$ such that $$ \int\limits\limits_{\R^n} g(x)\, dx > 0 \quad \hbox{ and }\quad \int\limits_{\R^n} h(x)\, dx> 0. $$ Then there exist two points $a,b\in\R^n$ and a linear function $\ell:\ [0,1]\to\R_+$ such that $$ \int\limits_0^1 \ell(t)^{n-1} g((1-t)a+tb)\,dt > 0 \quad\hbox{ and }\quad \int\limits_0^1 \ell(t)^{n-1} h((1-t)a+tb)\,dt > 0. $$ } To formulate the conclusion informally, we may consider $(\ell (t))^ {n-1} dA$ to be the cross-sectional area ($(n-1)$ dimensional volume) of an infinitesimal cone with base area $dA$; then the conclusion of the lemma just states that the integrals of both $g$ and $h$ over this cone truncated at $a,b$ are positive. In fact, it will be convenient to make this precise by introducing the following language. By a {\it needle} we mean a segment $I=[a,b]$ in $\R^n$, together with a non-negative linear function $\ell:~I\to \R_+$. If $N=(I,\ell)$ is a needle and $f$ is an integrable function defined on $I$, then we set $$ \int_N f = \int_0^{|b-a|} f(a+tu)\ell(a+tu)^{n-1}\,dt, $$ where $u=(1/|b-a|)(b-a)$. It is easy to show that we could not further restrict the family of these ``test bodies'' -- in Lemma 2.1 -- to (untruncated) infinitesimally narrow cones, or cylinders (i.e., choosing $\ell$ to be constant, or 0 at one of the endpoints). Furthermore, one cannot directly generalize this theorem to 3 integrals. (If one wants to preserve the sign of $k$ integrals, one has to use $(k-1)$- dimensional test-bodies. We do not elaborate on this idea here.) \medskip We state two corollaries of this lemma which will be sometimes more convenient to apply. \Corollary 2.2. Let $f_1,f_2,f_3,f_4$ be four nonnegative continuous functions defined on $\R^n$, and $\alpha,\beta>0$. Then the following are equivalent: \smallskip {\rm (a)} for every convex body $K$ in $\R^n$, $$ \left(\int_K f_1\right)^\alpha \left(\int_K f_2\right)^\beta\le \left(\int_K f_3\right)^\alpha \left(\int_K f_4\right)^\beta; $$\smallskip {\rm (b)} for every needle $N$ in $\R^n$, $$ \left(\int_N f_1\right)^\alpha \left(\int_N f_2\right)^\beta \le \left(\int_N f_3\right)^\alpha \left(\int_N f_4\right)^\beta. $$ \Proof of Corollary 2.2. It is clear that (a) implies (b). To prove the converse, assume (b) for a convex body $K$ and assume indirectly that $$ \left(\int_K f_1\right)^\alpha \left(\int_K f_2\right)^\beta > \left(\int_K f_3\right)^\alpha \left(\int_K f_4\right)^\beta .\eqno(2.1) $$ By adding a small constant to $f_3$ and $f_4$, we may assume that they are positive and (2.1) still holds. We also may assume that $\int_K f_i >0$ for $i=1,2,3,4$. Fix an $A$ such that $${\left(\int_K f_1\right)^\alpha \over\left(\int_K f_3\right)^\alpha } >A>{\left(\int_K f_4\right)^\beta \over\left(\int_K f_2\right)^\beta }>0. $$ Then $$\int_K (A^{1/\beta} f_2-f_4)>0\text{and}\int_K (f_1-A^{1/\alpha}f_3)>0.$$ By the Localization Lemma, we have a needle $N$ contained in $K$ such that $$\int_N (A^{1/\beta} f_2-f_4)>0\text{and}\int_N (f_1-A^{1/\alpha}f_3)>0.$$ These inequalities imply that $\int_N f_1 >0$ and $\int_N f_2 >0$. Clearly, $$ \left(\int_N f_1\right)^\alpha \left(\int_N f_2\right)^\beta > A \left(\int_N f_3\right)^\alpha \left(\int_N f_2\right)^\beta > \left(\int_N f_3\right)^\alpha \left(\int_N f_4\right)^\beta, $$ contradicting the assumption (b)\foot{The fact that we possibly added a small positive constant to $f_3$ and $f_4$ works in the right direction: we get a contradiction with the original $f_3$, $f_4$, too.}. \proofend \Remark 2.3. It is easy to see that Corollary 2.2 automatically extends to the more general case when $f_1, f_2$ are upper semi-continuous and $f_3, f_4$ are lower semi-continuous functions. Indeed, then we may choose 4 sequences of continuous functions, $f^{(k)}_i$ so that $f^{(k)}_1\nearrow f_1$, $f^{(k)}_2\nearrow f_2$, $f^{(k)}_3\searrow f_3$, $f^{(k)}_4\searrow f_4$: (b) will trivially be satisfied by the approximating functions. If (a) were violated by $f_1,f_2,f_3,f_4$, then for some sufficiently large $k$ the continuous $f^{(k)}_1,f^{(k)}_2,f^{(k)}_3,f^{(k)}_4$ would also violate it, contradicting the original corollary (continuous case). This observation is useful when we have functions defined and continuous on a subset $T$ of $\R^n$ and want to use the above arguments: we may extend these functions to the whole space by defining them outside to be 0. Thus continuous functions extend to upper semi-continuous functions if $T$ is closed, to lower semi-continuous ones if $T$ is open. # \medskip \Corollary 2.4. Suppose $T$ is a bounded open # convex set in $\R^n$, $g$ is a bounded # lower semi-continuous function on $T$ and $h$ a continuous function on $T$ such that $$ \int_T g(x)\ \ dx >0\qquad \hbox{and}\qquad \int_{T} h(x)\ \ dx = 0. $$ Then there exists a needle $N=(I,\ell )$ with $I\subseteq T$ such that $$ \int _N g\ \ dx >0\qquad\hbox{and}\qquad \int_N h\ \ dx =0. $$ \Remark 2.5. It is clear that we can replace strict inequality by $\ge$ in the assumption and in the conclusion, having a needle with $\ell$ {\it not} identically 0. \medskip \proof. One could prove this assertion along the lines of the original proof of Lemma~2.1 (Lemma~2.5 in Lov\'asz--Simonovits (1993)) but --- using a simple trick --- one can also reduce it to Lemma~2.1 as follows. Choose a $\delta >0$ such that $\int_T (g-\delta)>0$. Let $\varepsilon$ be any positive real (which will later tend to zero). We have $$\int_{T} \left(g-\delta +{1\over\varepsilon }h\right) > 0 \text{and}\int_{T}(\varepsilon^2-h)>0.\eqno(2.2)$$ We convert the above integrals over $T$ into integrals over $\R^n$ by multiplying the integrand by the (lower semi-continuous) indicator function of $T$ and then we apply Lemma~2.1. Thus we get a needle $N_\varepsilon$ for which $$ \int_{N_\varepsilon} \left(g-\delta +{1\over\varepsilon}h\right) > 0\text{and} \int_{N_\varepsilon} ( \varepsilon^2-h) >0. $$ Hence $$ \int_{N_\varepsilon } \left(g-\delta+\varepsilon\right) > 0 $$ and if $M$ is an upper bound on $g$ on all of $T$, then $$\int_{N_\varepsilon} h > \int_{N_\varepsilon} (-\varepsilon g) \ge -M\varepsilon\int_{N_\varepsilon} 1 \text{and} \int_{N_\varepsilon} h<\varepsilon^2\int_{N_\varepsilon}1.$$ We construct these needles $N_\varepsilon$ for $\varepsilon = 1/k$ for $k=1,2,3,\dots$ We may assume after scaling by a suitable positive real that the maximum of each linear function corresponding to the needles is $1$. There is then a subsequence of these needles that converges (in the sense that the intervals converge to an interval and the linear functions to some linear function with maximum =1). It is easy to see (using the continuity of $h$) that for the ``limit'' needle intersected by $T$, the conclusions are valid. \proofend Next we prove a version of Corollary 2.2 involving log-concave weight-functions. Here exponential needles, defined below, will replace the needles. But even if we are not concerned with log-concave functions, exponential needles are easier to use. The Localization Lemma (or its corollary stated above) reduces the problem of proving inequalities between integrals in $\R^n$ to inequalities between one-dimensional integrals. However, then $n$-th powers of linear functions in the definition of a ``needle'' are often difficult to handle. In the case when we want to prove inequalities that are independent of $n$ (in some sense), the following theorem may be easier to apply. To state it, we define an {\it exponential needle} $E$ as a segment $[a,b]\subseteq \R^n$, together with a real constant $\gamma$; and we define the integral over such a needle by $$ \int_E f = \int_0^{|b-a|} f(a+tu) e^{\gamma t} \,dt. $$ where $u=(1/|b-a|)(b-a)$. Recall that a function $f:\ \R^n\to \R_+$ is {\it log-concave} if it satisfies, for all $x,y\in\R^n$ and $0<\lambda <1$, $$f(\lambda x + (1-\lambda )y) \ge f(x)^{\lambda }f(y)^{(1-\lambda )}.$$ Equivalently, a (non-negative) function is log-concave if its support $K=\{x\in\R^n:\ f(x)>0\}$ is convex, and $\log f$ is a concave function on $K$. Every non-negative function that is concave over a convex domain is log-concave (we define its value to be 0 outside the original domain). In particular, the indicator function of a convex body # is log-concave. Log-concave functions include many density functions important in statistics, e.g. $e^{-x^2}$ and $e^{-|x|}$. If $\ell$ is a linear function, then $\max\{0, \ell^k\}$ is log-concave. We need a lemma about the one-dimensional case. \medskip \Lemma 2.6. Let $f_1,f_2,f_3,f_4$ be four non-negative continuous functions defined on an interval $[a,b]$, and $\alpha,\beta>0$. Then the following are equivalent: \smallskip {\rm (a)} For every log-concave function $F$ defined on $\R$, $$ \left(\int_a^b F(t) f_1(t) \,dt\right)^\alpha \left(\int_a^b F(t) f_2(t) \,dt\right)^\beta \le \left(\int_a^b F(t) f_3(t) \,dt\right)^\alpha \left(\int_a^b F(t) f_4(t) \,dt\right)^\beta\,; $$ {\rm (b)} For every subinterval $[a',b']\subseteq [a,b]$, and every real $\gamma$, $$ \left(\int_{a'}^{b'} e^{\gamma t} f_1(t)\,dt\right)^\alpha \left(\int_{a'}^{b'} e^{\gamma t} f_2(t) \,dt\right)^\beta \le \left(\int_{a'}^{b'} e^{\gamma t} f_3(t) \,dt\right)^\alpha \left(\int_{a'}^{b'} e^{\gamma t} f_4(t) \,dt\right)^\beta\,. $$ \medskip \proof. First we note that if there exists a point $t_0\in[a,b]$ such that $(f_1(t_0))^\alpha (f_2(t_0))^\beta > (f_3(t_0))^\alpha (f_4(t_0))^\beta $, then both assertions fail (by considering a very small interval containing $t_0$, or the log-concave function $e^{-C(t-t_0)^2}$ with a large constant $C$). So we may assume that for all $a\le t\le b$, $$ f_1(t)^\alpha f_2(t)^\beta\le f_3(t)^\alpha f_4(t)^\beta. \eqno(2.3) $$ It is obvious that (a) implies (b). (b) $\Rightarrow$ (a) : Assume that (a) fails for some log-concave function $F$. We may assume that $F(t)>0$ for all $a\le t\le b$, since replacing $F$ by, say, its convolution with $e^{-Ct^2}$ with a very large $C$ would still yield a counterexample: indeed, the convolution of log-concave functions is again log-concave (see Dinghas (1957) or Pr\'ekopa (1971)). By scaling, we may also assume that $F(t)\ge 1$ on $[a,b]$. So we can write $F=e^G$, where $G$ is a non-negative concave function on $[a,b]$. Also, we may choose an $\varepsilon >0$ sufficiently small such that $$ \left(\int_{a}^{b} F(t)f_1(t) \,dt\right)^\alpha \left(\int_{a}^{b} F(t) f_2(t) \,dt\right)^\beta > $$ $$ \left(\int_{a}^{b} F(t) (f_3(t)+\varepsilon) \,dt\right)^\alpha \left(\int_{a}^{b} F(t) (f_4(t)+\varepsilon) \,dt\right)^\beta \eqno (2.4). $$ For each natural number $n$, consider the convex body $K_n$ below in $\R^{n+1}$. $$ K_n=\left\{(t,x):~t\in[a,b], x\in\R^n, \|x\|\le 1+{G(t)\over n}\right\}. $$ We also extend each $f_i$ to a function $\hat f_i:~\R^{n+1}\to\R$ by $\hat f_i(t,x) = f_i(t)$. Then for sufficiently large $n$, we have $\left(1+{G(t)\over n}\right)^n\approx e^{G(t)}$ and (2.4) implies $$ \left(\int_{K_n} \hat f_1\right)^\alpha \left(\int_{K_n} \hat f_2\right)^\beta > \left(\int_{K_n} (\hat f_3+\varepsilon ) \right)^\alpha \left(\int_{K_n} (\hat f_4+\varepsilon )\right)^\beta . $$ By Corollary 2.2, there exists a needle $N_n=(I_n,\ell_n)$ in $\R^{n+1}$ such that $$ \left(\int_{N_n} \hat f_1\right)^\alpha \left(\int_{N_n} \hat f_2\right)^\beta > \left(\int_{N_n} (\hat f_3+\varepsilon )\right)^\alpha \left(\int_{N_n} (\hat f_4+\varepsilon )\right)^\beta. $$ If the needle is orthogonal to the $t$-axis, then this inequality violates (2.3), so we assume this is not the case. Thus, we may project to $[a,b]$ and assume that $I_n=[a_n,b_n]\subseteq [a,b]$ and that $\ell_n$ is a linear function of $t\in [a_n,b_n]$, so we have $$ \left(\int_{a_n}^{b_n} \ell _n(t)^n f_1(t) \,dt\right)^\alpha \left(\int_{a_n}^{b_n} \ell _n(t)^n f_2(t) \,dt\right)^\beta > $$ $$ \left(\int_{a_n}^{b_n} \ell _n(t)^n (f_3(t)+\varepsilon) \,dt\right)^\alpha \left(\int_{a_n}^{b_n} \ell _n(t)^n (f_4(t)+\varepsilon) \,dt\right)^\beta.\eqno(2.5) $$ There is a subsequence $(n)$ such that in the subsequence, $a_n\to a_0$ and $b_n\to b_0$. (2.3) implies that $a_0 \left(\int_{a_0}^{b_0} e^{\gamma''t} f_3(t) \,dt\right)^\alpha \left(\int_{a_0}^{b_0} e^{\gamma''t} f_4(t) \,dt\right)^\beta, $$ showing that (b) is violated.\proofend \Theorem 2.7. Let $f_1,f_2,f_3,f_4$ be four nonnegative continuous functions defined on $\R^n$, and $\alpha,\beta>0$. Then the following are equivalent: \smallskip {\rm (a)} For every log-concave function $F$ defined on $\R^n$ with compact support, $$ \left(\int_{\R^n} F(t) f_1(t)\,dt\right)^\alpha \left(\int_{\R^n} F(t) f_2(t)\,dt\right)^\beta \le \left(\int_{\R^n} F(t) f_3(t)\,dt\right)^\alpha \left(\int_{\R^n} F(t) f_4(t)\,dt\right)^\beta; $$ {\rm (b)} For every exponential needle $E$, $$ \left(\int_E f_1\right)^\alpha \left(\int_E f_2\right)^\beta \le \left(\int_E f_3\right)^\alpha \left(\int_E f_4\right)^\beta $$ \proof. The direction (a)$\Rightarrow$(b) is easy : Let the exponential needle $E$ be defined by the segment $[a,b]$ ($a,b\in\R^n$) and constant $\gamma$, and let $u={b-a\over |a-b|}$ as before. Apply (a) to the log-concave function $e^{\gamma ux}$, restricted to an $\varepsilon$-neighborhood of $[a,b]$, and let $\varepsilon\to 0$; we get then (b). Conversely, assume that (b) holds and consider any log-concave function $F$. Assume that (a) fails to hold. Apply Corollary 2.2 to the functions $Ff_i$; it follows that there is a segment $[a,b]$ and a linear function $\ell : [a,b]\to\R_+$ such that $$ \left(\int\limits_0^{|b-a|} f_1(a+tu)F(a+tu)\ell(a+tu)^{n-1}\,dt \right)^\alpha \left(\int\limits_0^{|b-a|} f_2(a+tu)F(a+tu)\ell(a+tu)^{n-1}\,dt \right)^\beta> $$ $$ \left(\int\limits_0^{|b- a|}f_3(a+tu)F(a+tu)\ell(a+tu)^{n-1}\,dt\right)^\alpha \left(\int\limits_0^{|b-a|}f_4(a+tu)F(a+tu)\ell(a+tu)^{n- 1}\,dt\right)^\beta\,. $$ Now here $F\ell^{n-1}$ is also log-concave, and hence Lemma 2.4 implies that there exists an exponential needle $E$ violating (b). \proofend \Remark 2.8. # An exponential needle consists of an interval and an exponent $\gamma$. We may often rescale, reducing the general case to the case $\gamma=1$. The case $\gamma=0$ can be neglected since in our cases it always follows from the case $\gamma\neq 0$ by going to limits. \subtitle 3. Applications As an illustration of the use of the localization lemma, we derive a generalization of Khintchine's inequality, due to Gromov and Milman (1984); see also Milman and Pajor (1989). Other geometric inequalities, like the extension of Theorem 3.1 below to norms of polynomials of bounded degree (Bourgain 1991), a spherical Brunn-Minkowski type theorem of Borell (1975), a theorem of Hensley (1980) on sections of isotropic bodies, or an inequality of Dinghas (1957) on log-concave functions can also be deduced using the localization lemma (cf. also Lov\'asz and Simonovits 1993). Typically, this method enables one also to find the best constants in these results, although (as is also illustrated below) at the cost of a tedious computation. Let $K$ be a convex body and $f: K\to \R$ an integrable function. We define its $L_p$-norm by $$ \|f\|_p=\left({1\over\vol(K)}\int_K |f(x)|^p\,dx\right)^{1/p}. $$ If $0 -\sqrt{(n+2)/n}$. By hypothesis, $$ \int_K x_1 = 0 \text{and} \int_K (x_1^2-1) = 0. $$ Applying the Remark 2.5 (extending Corollary 2.4) we get a needle $N=([a,b],\ell )$ contained in $K$, which we may assume is not orthogonal to the $x_1$ axis. Hence we may assume it is contained in the $x_1$ axis, such that $$ \int _a^b x_1(\ell(x_1))^{n-1}=0\quad \hbox{and}\quad \int_a^b x_1^2(\ell(x_1))^{n-1}\geq \int_a^b (\ell(x_1))^{n-1}. $$ Our indirect hypothesis implies that $a>-\sqrt {(n+2)/n}$. It is easy to see that $\ell$ must be decreasing and then we may assume that $\ell(x)=t-x$ for some $t\ge b$. Then the integrals in both conditions can be evaluated explicitly, and a contradiction can be obtained by a tedious but rather straightforward computation. \medskip The proof of the second inequality does not need the Localization Lemma. Let $v$ be the point of $K$ farthest from 0. We have to show that $|v|\le\sqrt{n(n+2)}$. Let $e=(1/|v|)v$. For each $u\in\R^n$ with $|u|=1$, let $\phi(u)$ denote the largest real number $t$ with $v+tu\in K$. Then we have $$ \vol(K) = \int_{\partial B} \int_0^{\phi(u)} t^{n-1} \,dt\,du = {1\over n}\int_{\partial B} \phi(u)^n\,du\,.$$ Moreover, $$\eqalign{ 1 & = {1\over\vol(K)}\int_K (e^Tx)^2 \,dx = {1\over\vol(K)}\int_{\partial B} \int_0^{\phi(u)} t^{n-1}(e^T(v+tu))^2 \,dt\,du \cr & = {1\over\vol(K)}\int_{\partial B} \left( {\phi(u)^n\over n} |v|^2 +2{\phi(u)^{n+1}\over n+1}|v| e^Tu + {\phi(u)^{n+2}\over n+2} (e^Tu)^2\right)\,du\, . \cr} $$ The integrand can be written as $$ {\phi(u)^n\over n} \left(\sqrt{n\over n+2}\phi(u)e^Tu + {\sqrt{n(n+2)}\over n+1}|v|\right)^2 + {1\over n(n+1)^2}\phi(u)^{n}|v|^2. \eqno(4.2) $$ Here the first term is non-negative, which gives the inequality $$ 1\ge {1\over\vol(K)}\int_{\partial B} {1\over n(n+1)^2}\phi(u)^{n}|v|^2 = {|v|^2\over (n+1)^2}, $$ and hence $|v|\le n+1$. To get the slightly stronger right hand side inequality of (4.1), we give a positive lower bound on the first term in (4.2). Similarly as above, we have $$ 0=b(K)={1\over\vol(K)}\int_{\partial B} \int_0^{\phi(u)} t^{n-1}(v+tu) \,dt\,du = v+{1\over\vol(K)}\int_{\partial B} {\phi(u)^{n+1}\over n+1} u \,du , $$ and hence $$ {1\over\vol(K)}\int_{\partial B} {\phi(u)^n\over n} \left(\sqrt{n\over n+2}\phi(u)e^Tu + {\sqrt{n(n+2)}\over n+1}|v|\right) \,du = -{1\over (n+1)\sqrt{n(n+2)}}|v|. $$ Thus by Cauchy-Schwarz, $$ {1\over\vol(K)}\int_{\partial B} {\phi(u)^n\over n} \left(\sqrt{n\over n+2}\phi(u)e^Tu + {\sqrt{n(n+2)}\over n+1}|v|\right)^2 \,du\ge {1\over n(n+2)(n+1)^2 }|v|^2. $$ Thus $$ 1 \ge \left({1\over n(n+2)(n+1)^2} + {1\over (n+1)^2}\right) |v|^2 = {1\over n(n+2)} |v|^2, $$ which proves the assertion. \proofend \subtitle 5. Isoperimetric inequalities. Now we state the main theorem of this paper. \Theorem 5.1. For every convex body $K$, $$\psi(K)\ge {\ln 2 \over M_1(K)}.$$ Generally surfaces are difficult to handle. Therefore, in the definition of the isoperimetric coefficient, in (1.1), we replace the original surface $\partial S$~ by its open $\varepsilon/2$--neighborhood intersected by $K$, whose closure we denote by $K_3$. Further, we replace $S$ by $K_1:=S\setminus K_3$ and $K\setminus S$ by $K_2:=(K\setminus S)\setminus K_3$. So we prove the following theorem, which implies Theorem~5.1 by letting $\varepsilon\to 0$. \Theorem 5.2. Let $K$ be a convex body and $K=K_1\cup K_2\cup K_3$, a decomposition of $K$ into three measurable sets such that the distance of $K_1$ and $K_2$ is $\varepsilon >0$. Then $$ \vol(K_1)\vol(K_2) \le {M_1(K)\over\varepsilon\ln 2 }\vol (K) \vol(K_3) . $$ \proof. # One can reduce the general case of measurable partition to the case when $K_1$ and $K_2$ are closed: replacing $K$ by its closure we do not change $\vol(K)$; replacing the original $K_1$ and $K_2$ by their closure we decrease neither $\vol(K_1)$ nor $\vol(K_2)$; putting $K_3:=\overline{K}\setminus(\overline{K_1}\cup \overline{K_2})$ we do not increase $\vol(K_3)$. Hence Theorem~5.2 for this new partition will imply Theorem~5.2 for the old one. We assume that $b(K)=0$. Let $f_i$ be the indicator function of $K_i$ ($i=1,2,3$) and $f_4(x)=|x|/(\varepsilon\ln 2) $. Then the assertion of the theorem is equivalent to $$ \int_K f_1 \int_K f_2 \le \int_K f_3 \int_K f_4 . $$ Theorem 2.7 can be applied and says that we only have to prove that $$ \int_E f_1 \int_E f_2 \le \int_E f_3 \int_E f_4 $$ for every exponential needle $E$ contained in $K$. Now let $E$ be defined by the segment $[a,b]$ and $\gamma$. We may assume that the segment intersects both $K_1$ and $K_2$. We may also assume that the origin corresponds to a point $u$ on the segment $[a,b]$, since otherwise we can move it to the nearest point on the segment and the function $f_4$ would only decrease while the other three would remain the same. We can rescale so that $\gamma=1$. This reduces the problem to the following inequality concerning one-dimensional integrals. Let $a\le 0\le b$ and $\gamma=1$. Let $[a,b]=J_1\cup J_2\cup J_3$ be a partition of $[a,b]$ into three measurable sets, so that the distance of $J_1$ and $J_2$ is at least $\varepsilon $. Then we want $$ \int_{J_1} e^t\,dt \int_{J_2} e^t\,dt \le {1 \over\varepsilon\ln 2 }\int_{J_3} e^t\,dt \int_a^b |t-u| e^t\,dt.\eqno(5.1) $$ We first prove the assertion in the (intuitively) most difficult case when $J_1$, $J_2$ and $J_3$ are intervals (naturally, $[c,d]=J_3$ is in the middle and has length at least $\varepsilon $). Dividing by $e^c$, we have to prove the inequality $$ \int_a^c e^t\,dt \int_{\varepsilon }^{b-c} e^t\,dt \le {1\over\varepsilon\ln 2} \int_0^{\varepsilon } e^t\,dt \int_a^b |t-u|e^t\,dt $$ One way to prove this elementary inequality is to notice that the left hand side is maximized when $c=(a+b-\varepsilon )/2$, while the right hand side is minimized when $u=\ln((e^a+e^b)/2)$. Substituting these values, and simplifying, we get that we have to prove $$ \left(e^{(b-a)/2}-e^{\varepsilon/2}\right)^2 \le {1\over \ln 2}{e^\varepsilon -1\over \varepsilon } \left(-\ln((e^{a-b}+1)/2) e^{b-a} + \ln((e^{b-a}+1)/2)\right). $$ If we decrease $\varepsilon $ the left hand side increases while $(e^\varepsilon-1)/\varepsilon$ decreases, so it suffices to prove the inequality in the limit case $\varepsilon =0$. Substituting $z=e^{(b-a)/2}$, we get that we have to prove $$ (\ln 2)(z-1)^2 + z^2 \ln((z^{-2}+1)/2) - \ln((z^2+1)/2) \le 0 $$ for $z\ge 1$. The function $f$ on the left hand side satisfies $$ {d\over dz}(f'(z)/z) = {4(z^3-z)+2(\ln 2)(z^2+1)\over z^2(1+z^2)^2} \ge 0 $$ for $z\ge 1$, which implies that $f'(z)/z$ is monotone increasing. Since $f'(z)/z\to 0$ as $z\to\infty$, this implies that $f'(z)\le 0$, i.e., $f$ is monotone decreasing. Now since $f(1)=0$, this implies that $f(z)\le 0$ for $z\ge 1$. Thus we know that (5.1) holds when $J_1$, $J_2$ and $J_3$ are intervals. From this the assertion follows by a general trick from Lov\'asz and Simonovits (1993). We may assume that $J_3$ is open, since replacing $J_1$ and $J_2$ by their closures would only make the inequality tighter. So $J_3$ is the union of disjoint open intervals; we may assume that these are of length at least $\varepsilon $, since the shorter intervals must have both endpoints in $J_1$ or both endpoints in $J_2$, and then accordingly we can add them to $J_1$ or $J_2$ and make the inequality tighter. Now let $(c_i,d_i)$ ($1\le i\le k$) be all maximal intervals contained in $J_3$. Then by the argument above, $$ \int_a^{c_i}e^t\,dt \int_{d_i}^b e^t\,dt \le {1\over\varepsilon\ln 2} \int_{c_i} ^{d_i}e^t\,dt \int_a^b |t-u|e^t\,dt\,. $$ Summing this for all $i$, we obtain $$ \sum_{i=1}^k \int_a^{c_i}e^t\,dt \int_{d_i}^b e^t\,dt \le {1\over\varepsilon\ln 2} \int_{J_3}e^t\,dt \int_a^b |t-u|e^t\,dt\,. $$ Since every point of $J_1$ and every point of $J_2$ are separated by at least one of the intervals $(c_i,d_i)$, we have $$ \sum_{i=1}^k \int_a^{c_i}e^t\,dt \int_{d_i}^b e^t\,dt \ge \int_{J_1} e^t\,dt \int_{J_2} e^t\,dt\,. $$ This proves the theorem.\proofend Let $K$ be an arbitrary convex body and let, for each $x\in K$, $\chi(x)$ denote the length of the longest segment contained in $K$ with midpoin t $x$ contained in $K$. (Equivalently, $\chi(x)$ is the diameter of $K\cap (2x-K)$.) Define $$\chi(K) = {1\over \vol(K) } \int_K \chi(x)\,dx.$$ \Theorem 5.3. For every convex body $K$, # $$\psi(K)\ge {1 \over \chi(K)}.$$ \proof. We prove, for every partition $K=K_1\cup K_2\cup K_3$ of $K$ into three measurable sets such that the distance of $K_1$ and $K_3$ is $\varepsilon >0$, the inequality $$ \vol(K_1)\vol(K_2) \le {1\over \varepsilon } \vol(K_3) \int_K \chi(x)\,dx\,. $$ Similarly as before, Theorem 2.7 # can be applied to reduce the problem to an assertion about one-dimensional integration: for every interval $[a,b]$ on the line, and every partition $[a,b]=J_1\cup J_2\cup J_3$ into three measurable sets, ($J_1$, $J_2$ are closed, $J_3$ is open in $[a,b]$) such that the distance of $J_1$ and $J_2$ is at least $\varepsilon$, $$ \int_{J_1}e^t\,dt \int_{J_2}e^t\,dt \le {1\over \varepsilon } \int_{J_3} e^t\,dt \int_a^b \min(t-a, b-t) e^t \,dt. $$ Again as before, it suffices to prove this in the case when $J_3$ is a single interval $(c, c+\varepsilon)$. As before, we evaluate these integrals and simplify to get the inequality $$ \left(e^{(b-a)/2}-e^{\varepsilon/2}\right)^2 \le \left({e^\varepsilon -1\over\varepsilon }\right)\left(e^{(b-a)/2}-1\right)^2, $$ which is clearly true.\proofend The two lower bounds on $\psi(K)$ in Theorems 5.1 and 5.3 are not comparable. The first theorem gives $\psi\ge\Omega(n^{-1/2})$ for every isotropic body. The second theorem gives $\psi\ge\Omega(1)$ for the isotropic ball, but only the trivial $\psi\ge\Omega(1/n)$ for the isotropic simplex. \medskip We present below an upper bound on $\psi(K)$. We conjecture that this upper bound is always within a constant factor to the truth. This is equivalent to the conjecture that there is hyperplane cut which is within a constant of the ``best'' cut. Let $K$ be a convex body in $\R^n$, and let $\alpha (K)$ be the largest eigenvalue of $A(K)$. \medskip \noindent{\bf Conjecture.} $\psi(K)=\Theta(1/\sqrt{\alpha(K)})$. \medskip \Theorem 5.4. For every convex body $K$ in $\R^n$, $$\psi(K)\le {10\over\sqrt{\alpha(K)}}.$$ The proof is immediate from the following lemma, which can be proved either using the localization lemma or (if the best constant is not important) a standard log-concavity argument. \medskip \noindent {\bf 5.5 Lemma.} {\it Let $K$ be a convex body in $\R^n$ and assume that $b(K)=0$. Let $u$ be any vector in $\R^n$ of length 1, and $\beta:=E_K ((u^T x)^2)$. Then $$ \vol ( K\cap \{ x : u^T x <0\} ) \vol ( K\cap \{ x : u^T x > 0\} ) \geq {1\over 10} \sqrt\beta\vol_{n-1} ( K\cap \{ x : u^T x =0\} )\vol (K). $$} \medskip We note that it could also be shown easily along the same lines that cuts by hyperplanes do not provide a counterexample to the conjecture. \bigskip \noindent{\bf References} \leftskip=0.5cm\parskip=3pt\parindent=-0.5cm \bigskip D.~Applegate and R.~Kannan (1990): Sampling and integration of near log-concave functions, {\it Proc. 23th ACM Symposium on the Theory of Computing}, 156--163. J~.Bokowski, (1980): Ungleichungen f\"ur des Inhalt von Trennfl\"achen, Arch. Math. {\bf 34} 84-89. J.~Bokowski and E.~Spencer Jr. (1979): Zerlegung Konvexen K\"orperdurch minimale Trennfl\"achen, J. Reine und Angew. Math. {\bf 311-312} 80-100. C.~Borell (1975): The Brunn-Minkowski inequality in Gauss spaces, {\it Invent. Math.} {\bf 30}, 207--216. J.~Bourgain (1991): On the distribution of polynomials on high dimensional convex sets, in: {\it Lecture Notes in Math.} {\bf 1469}, (Springer, Berlin) 127--137. A.~Dinghas (1957), \"Uber eine Klasse superadditiver Mengenfunktionale von Brunn--Minkowski--Lusternik-schem Typus, {\it Math. Zeitschr.} {\bf 68}, 111--125. M.~Dyer and A.~Frieze (1992): Computing the volume of convex bodies: a case where randomness provably helps, in: {\it Probabilistic Combinatorics and Its Applications} (ed. B\'ela Bollob\'as), Proceedings of Symposia in Applied Mathematics, Vol. 44, 123--170. M.~Dyer, A.~Frieze and R.~Kannan (1989): A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies, {\it Proc. of the 21st Annual ACM Symposium on Theory of Computing}, 375-381. H. Federer (1969): Geometric Measure theory, Springer Verlag, Berlin. ## E. Ginstr ??? (1984): Minimal surfaces and functions of bounded variation, Birkh\"auser, Boston ??? M.~Gromov and V.~D.~Milman (1984): Brunn Theorem and a concentration of volume of convex bodies, {\it GAFA Seminar Notes}, Tel Aviv University, Israel. D.~Hensley (1980): Slicing convex bodies and bounds on the slice area in terms of the body's covariance, {\it Proc. Amer. Math. Soc.} {\bf 79} 619--625. F. John (1948): Extremum problems with inequalities as subsidian (?) conditions, Studies and Essays presented to R. Courant, New York, 187-204. # ??? A.~Karzanov and L.~G.~Khachiyan (1991), On the conductance of order Markov chains, {\it Order} {\bf 8}, 7--15. L.~Lov\'asz and M. Simonovits (1990): Mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. {\it Proc. 31st Annual Symp. on Found. of Computer Science,} IEEE Computer Soc., 346--355. L.~Lov\'asz and M. Simonovits (1992): On the randomized complexity of volume and diameter, {\it Proc. 33rd IEEE FOCS}, 482--491. L.~Lov\'asz and M.~Simonovits (1993): Random walks in a convex body and an improved volume algorithm, {\it Random Structures and Alg.} {\bf 4}, 359--412. V.~D.~Milman and A.~Pajor (1989): Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed $n$-dimensional space, in: {\it Geometric Aspects of Functional Analysis} (eds. J.~Lindenstrauss and V.~D.~Milman), Lecture Notes in Math. {\bf 1376} (Springer, Berlin) 64--104. A. Pr\'ekopa (1971), Logarithmic concave measures with applications to stochastic programming, {\it Acta Sci. Math. Szeged.} {\bf 32} 301--316. G.~Sonnevend (1989): Applications of analytic centers for the numerical solution of semiinfinite, convex programs arising in control theory, DFG report Nr. 170/1989, Univ. W\"urzburg, Inst.f. angew. Mathematik. \bye