

\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<b_0$. We may assume that
$\ell _n(a_0)\le \ell _n(b_0)$ for infinitely many indices (otherwise,
we may exchange $a_0$ and $b_0$ for the argument below). We may also
assume that each $\ell _n$ is normalized so that $\ell _n(b_0)=1$.
Let $\gamma_n=\ell _n(a_0)$.  We may also assume that $\gamma_n \to
\gamma$ and $(1-\gamma_n)n\to\gamma'$ for some $0\le \gamma \le 1$ and
$0\le\gamma'\le\infty$, for an infinite sequence of values of
$n$. (Note : $\gamma^\prime $ may be infinity.)

If $\gamma\not= 1$ then $\ell _n^n\to 0$ for every $a_0\le t < b_0$.
But then, dividing both sides of (2.5) by $\left(\int_{a_n}^{b_n}\ell
_n(t)^n\,dt\right)^{\alpha +\beta }$ and letting $n\to\infty$, we get
that
$$
f_1(b_0)^\alpha f_2(b_0)^\beta \ge (f_3(b_0)+\varepsilon)^\alpha
(f_4(b_0)+\varepsilon)^\beta,
$$
which contradicts (2.3).

So we have $\gamma=1$. Then $\ell _n(t)\to 1$ and so we have
for each $a_0\le t\le b_0$
$$
\ell _n(t)^n = (1 - (1-\ell _n(t)))^n =
\left[(1 - (1-\ell _n(t)))^{1\over 1-\ell _n(t)}\right]^{n(1-\ell _n(t))}
$$
Here the base (in the square brackets) tends to $1/e$.
If $\gamma'=\infty$ then $\ell _n(t)^n\to 0$ for $t<b_0$, which leads to
a contradiction as before. If $\gamma'$ is finite, then (using that
$\ell _n$ is linear) we have $n(1-\ell _n(t))\to \gamma'(b_0-t)/(b_0-a_0)$,
and so
$$
\ell _n(t)^n \to e^{\gamma'(t-b_0)/(b_0-a_0)}.
$$
Thus it follows that (with $\gamma''=\gamma' / (b_0-a_0)$)
$$
\left(\int_{a_0}^{b_0} e^{\gamma''(t-b_0)} f_1(t) \,dt\right)^\alpha
\left(\int_{a_0}^{b_0} e^{\gamma''(t-b_0)} f_2(t) \,dt\right)^\beta \ge
$$
$$
\left(\int_{a_0}^{b_0} e^{\gamma''(t-b_0)}
(f_3(t)+\varepsilon)\,dt\right)^\alpha \left(\int_{a_0}^{b_0}
e^{\gamma''(t-b_0)} (f_4(t)+\varepsilon)\,dt\right)^\beta, $$
and hence $$ \left(\int_{a_0}^{b_0} e^{\gamma''t} f_1(t)
\,dt\right)^\alpha \left(\int_{a_0}^{b_0} e^{\gamma''t} f_2(t)
\,dt\right)^\beta > \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<p<q$ then clearly $\|f\|_p\le\|f\|_q$; the next theorem asserts
that if $f$ is linear, then the following converse also holds:


\Theorem 3.1. There exists a constant
$c_{p,q}$ depending only on $p$ and $q$ (so
independent of the dimension and of $K$) such that for every
convex body $K$ in $\R^n$ and every linear function
$f:~K\to\R$,
$$
\|f\|_q\le c_{p,q}\|f\|_p  \,. \eqno(3.1)
$$


\proof. We write the inequality (3.1) in the following form:
$$
\left(\int_K |f|^q\right)^{1/q} \left(\int_K 1\right)^{1/p}
\le c_{p,q} \left(\int_K |f|^p\right)^{1/p}\left(\int_K 1\right)^{1/q}.
$$
By Theorem 2.7, it suffices to prove that for every exponential
needle $E$,
$$
\left(\int_E |f|^q\right)^{1/q}\left(\int_E 1\right)^{1/p}
\le c_{p,q} \left(\int_E |f|^p\right)^{1/p}\left(\int_E 1\right)^{1/q}.
$$
Translating this into one-dimensional integrals, we must prove (for
every fixed $0<p<q$) that there
exists a constant $c_{p,q}$ such that for every linear function $f$, every
$a<b$, and every real $\gamma$,
$$
\left({\int_a^b e^{\gamma
t}|f(t)|^q \,dt \over \int_a^b e^{\gamma t}\,dt}\right)^{1/q} \le c_{p,q}
\left({\int_a^b e^{\gamma t} |f(t)|^p\,dt \over \int_a^b e^{\gamma t}\,dt
}\right)^{1/p}.
$$
Without loss of generality, we may assume that $f(t)=t$
and $\gamma=1$ (this implies the case $\gamma\not=0$ by substitution, and
then the cases $\gamma=0$ and $f(t)=c$ also follow by going to the limits).
Let
$$\varphi(a,b):=
\left({\int_a^b e^t
|f(t)|^q \,dt \over \int_a^b e^t\,dt}\right)^{1/q} \left /
\left({\int_a^b e^t |f(t)|^p\,dt \over \int_a^b e^t\,dt
}\right)^{1/p}\right. .
$$
So we have
$c_{p,q}=\sup_{a<b} \varphi(a,b)$,
provided this is finite.
But $\varphi(a,b)$
is continuous for $a<b$, and we can extedn it to $a\le b$ continuously,
putting
$\varphi(a,a)=1$, (since
for every $\alpha$ $\varphi(a,b)$ tends to
1 if $a<b$ and $a,b\to\alpha$, \foot{the case $\alpha=0$ should be handled
with some extra care} # and $\varphi(a,b)\to 1$ uniformly in $a$ if
$b\to\infty$, and $a<b$ is arbitrary. Moreover, $\varphi(a,b)$
remains bounded if $b$ is bounded and $a\to-\infty$.  This implies that
$\varphi(a,b)$ remains bounded.
To determine the best value of the constant, one has to find the supremum
numerically, which is tedious but rather straightforward.  For example, one
gets $c_{1,2}<2.5$.  \proofend

\bigskip

\noindent{\bf 4. Isotropy}

\bigskip

Given a convex body $K\subseteq\R^n$ and a
function $f:~K\to\R^m$, we denote by $E_K(f)$ the ``average of $f$
over $K$'', i.e.,
$$
E_K(f)={1\over\vol(K)}\int_K f(x)\,dx
$$
We denote by $b=b(K)=E_K(x)$ the center of
gravity (baricenter) of $K$. We also let $A(K)$ denote the
$n\times n$ matrix of
``inertia'' about $b(K)$ :
$$
E_K \bigl((x-b)(x-b)^T \bigr),
$$
where $^T$ denotes the transpose. The {\it $p$-th moment} ($p\ge 0$) of a
convex body $K$ is defined by $$ M_p(K)= E_K(|x-b|^p). $$ The second moment
is just the trace of $A(K)$. It is easy to see that the average square
distance between points in $K$ is $2M_2(K)$ $$ {1\over\vol(K)^2}\int_K\int_K
|x-y|^2\,dx\,dy = 2M_2(K). $$

It is clear that $M_p(K)^{(1/p)}$ tends to $\max\{|x-b|:~x\in K\}$
monotone increasing, as $p\to\infty$.

A body $K\subseteq \R^n$ is in {\it isotropic position} if $b(K)=0$ and
$A(K)=I$, the identity matrix. Clearly, if $K$ is in isotropic position then
its second moment is $n$. (This definition is somewhat different from that in
Milman and Pajor (1989), where it is assumed that $\vol(K)=1$ and
$A(K)=\lambda_K I$. We have found our definition to be more convenient to
use, in particular in the probabilistic applications.  It is known that
$\lambda_K$ is bounded from below by an absolute constant, and it is a major
conjecture that $\lambda_K$ is bounded from above by an absolute constant.)

We start with a lemma which is, in a sense, folklore. For centrally
symmetric bodies, the corresponding result (in which case the bounds
are somewhat sharper, but only by absolute constants) was proved by
Milman and Pajor (1987).  For the non-symmetric case, the inequality,
up to absolute constants, was proved by Sonnevend (1989).

\Theorem 4.1. If $K$ is in isotropic position and $B$ is
the unit ball about 0, then $$\sqrt{n+2\over n}B\subseteq K\subseteq
\sqrt{n(n+2)}B.\eqno(4.1)$$

\noindent (Note the slightly weaker but simpler inequalities
$B\subseteq K \subseteq (n+1)B$. The inequalities as stated are tight
for the regular simplex. Also, they imply the theorem of F. John (1948) on
the inscribed and circumscribed ellipsoid of a convex body.)

\medskip

\proof. To prove the first containment, we use Corollary~2.4.
Assume that $\sqrt{(n+2)/n}B\not\subseteq K$.
Now, choosing the coordinate system appropriately $K$ is contained in the
halfspace $x_1 > -\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



