User guillaume aubrun - MathOverflow

Isoperimetric-like inequality for non-convex sets

2011-10-10T09:58:57Z

The classical isoperimetric inequality can be stated as follows: if $A$ and $B$ are sets in the plane with the same area, and if $B$ is a disk, then the perimeter of $A$ is larger than the perimeter of $B$.

There are several ways to define the perimeter. Here is a unusual one: if $A \subset \mathbb{R}^2$ is a convex set, the Cauchy-Crofton formula says that the perimeter of $A$ equals the measure of the set of lines that hit $A$, or

$$ p(A) = \frac{1}{2} \int_{S^1} \lambda(P_{\theta} A) d\theta, $$

where $P_\theta$ is the orthogonal projection in the direction $\theta \in S^1$, and $\lambda$ the Lebesgue measure on any line.

Now, this definition of $p(A)$ makes sense for non-necessarily convex sets, excepts that it is not the usual notion of perimeter, so let's call it rather "mean shadow". My question if whether the isoperimetric inequality holds for the mean shadow instead of perimeter: if $A,B$ are (open, say) subsets of the plane with equal area, and if $B$ is a disk, is the mean shadow of $A$ larger that the mean shadow of $B$ ?

The inequality is true if $A$ is convex, and we can assume that $A$ is a disjoint union of convex sets (since taking the convex hull of a connected set does not change the mean shadow).

Answer by Guillaume Aubrun for The volume of the “unit ball” in $\mathbb{R}^{m\times n}$ with respect to the cut norm

2011-10-11T09:08:40Z

A standard argument (Lemma 3.1 here) shows that the cut-norm is 4-equivalent to the operator norm from $\ell_{\infty}^m$ to $\ell_1^n=(\ell_\infty^n)^*$. Therefore the volume you ask is almost the same (up to a factor $4^{mn}$) as the volume of the unit ball in the projective tensor product $\ell_{\infty}^m \otimes_\pi \ell_\infty^n$. This is exactly this question (at least for $m=n$), and I gave an answer saying basically that (from general theorems) your lower bound on $V(m,n)^{1/mn}$ is sharp up to a logarimthic factor.

I guess this logarithm is not necessary, but I don't know how to remove it.

Answer by Guillaume Aubrun for volume of the unit ball of the Banach space $\ell_1^n\otimes_{\epsilon}\ell_1^n$?

2011-03-31T11:50:41Z

Here is an argument that is certainly overkill and introduces a logarithmic factor which is probably unnecessary.

Let $K$ be the unit ball in $\ell_1^n \otimes_\epsilon \ell_1^n$ and $K^\circ$ the polar body (the unit ball in $\ell_{\infty}^n \otimes_\pi \ell_{\infty}^n$). It is convenient to introduce the volume radius $vrad(K)=(vol(K)/vol(B_2^n))^{1/n}$ (this is the radius of the Euclidean ball with the same volume as $K$) and the mean (half-)width

$$ w(K) = \int_{S} \|x\|_{K^\circ} d\sigma(x)$$

where $\sigma$ is the uniform probability measure on the Euclidean sphere $S$ in $\mathbf{R}^n \otimes \mathbf{R}^n$. One has the following chain of inequalities

$$ w(K^\circ)^{-1} \leq vrad(K^\circ)^{-1} \lesssim vrad(K) \leq w(K) $$

The first and third inequalities are Uryshon's inequality and the central one is the reverse Santalo inequality (a deep theorem). Now there is another deep theorem that whenever a $n$-dimensional symmetric convex body is in $\ell$-position (which means that in some sense it is well-balanced) the product $w(K)w(K^\circ)$ is bounded by $C \log n$, and thefore the four quantities in the chain of inequalities above are comparable up to a logarithmic factor.

A convex body is in $\ell$-position as long as it has "enough symmetries" (i.e. the group of isometries acts irreducibly, this is the case here).

The simplest quantity to estimate seems to be $w(K^\circ)$. Replacing spherical integration by Gaussian integration, one essentially has to compute the norm of a Gaussian matrix as an operator from $\ell_{\infty}^n$ to $\ell_1^n$. If I am correct one obtains

$$ w(K^\circ) \approx \sqrt{n} $$

and therefore

$$ 1/\sqrt{n} \lesssim vrad(K) \lesssim \log n/\sqrt{n} .$$

Depending on your background (who are you ??), this may be quite obscure to you. I think everything relevant here is in the book by Gilles Pisier "the volume of convex bodies and Banach space geometry".

Polynomial upper approximation with respect to the Gaussian measure

2010-11-29T09:46:37Z

Let $f = 1_{[a,+\infty)}$ be the indicator function of a half-line. Does there exist a sequence $(P_n)$ of polynomials such that $f(x) \leq P_n(x)$ for every real $x$ and $$ \lim_{n\to \infty} \int_{\mathbf{R}} P_n d\gamma = \int_{\mathbf{R}} f d\gamma, $$ where $\gamma$ denotes the usual Gaussian measure ?

Answer by Guillaume Aubrun for Pinching and positive definite matrices

2010-10-11T15:57:52Z

A pinching has the form $M \mapsto T * M$, where $*$ is the entrywise product and $T$ is a $0/1$-matrix. I have the impression that (1)-(3) are all equivalent to

(4) T is positive,

and that it can be proved via the following: if a $0/1$-matrix $T$, with $1$ on the diagonal, avoids the pattern $\left( \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{array} \right)$ , then $T$ must be block-diagonal.

Either (1) or (2) imply that $T$ avoids this pattern: for (1) via your example, for (2) because it implies (4) (apply the pitching to the matrix with all entries equal to 1).

Orthogonal matrices with small entries

2010-01-29T08:43:08Z

Is it true that for any $n$, there exists a $n \times n$ real orthogonal matrix with all coefficients bounded (in absolute value) by $C/\sqrt{n}$, $C$ being an absolute contant ?

Some remarks :

If we want $C=1$, the matrix must be a Hadamard matrix.
The complex analogue has an easy answer: the Fourier matrix $(\exp(2\pi \imath jk/n)/\sqrt{n})_{(j,k)}$. Forgetting the complex structure gives a positive answer to the question in the real case when $n$ is even.
A random matrix doesn't work (the largest entry is typically of order $\sqrt{\log(n)}/\sqrt{n}$).

Answer by Guillaume Aubrun for Euclidean volume of the unit ball of matrices under the matrix norm

2009-10-21T21:30:01Z

The volume of the unit ball for the spectral norm in nxn real matrices is given by the formula

$$ c_n \int\limits_{[-1,1]^n} \prod_{i < j} |x_i^2-x_j^2| dx_1\dots dx_n $$

where $c_n = n! 4^{-n} \prod_{k=1}^n v_k^2$

and $v_k=\pi^{k/2}/\Gamma(1+k/2)$ is the volume of the unit ball in R^n.

A much more general formula for calculating all kind of similar quantities appears e.g. here (Lemma 1). The proof is by applying the SVD decomposition as a change of variables.

The first values are

2/3 π² for 2x2 matrices
8/45 π⁴ for 3x3 matrices
4/1575 π⁸ for 4x4 matrices ...

There might be a closed formula for the integral above. Edit : such a formula appears in Armin's post below !!

Answer by Guillaume Aubrun for What's a nice argument that shows the volume of the unit n-ball in R^n approaches 0?

2010-01-20T15:21:13Z

There is a simple argument by comparing to the unit ball of $\ell_1^n$.

Let $K$ be the unit ball of $\ell_1^n$, i.e. the set of points with sum of coordinates (in absolute value) bounded by $1$. Then $K$ is the disjoint union of $2^n$ simplices (one per octant), and each simplex has volume $1/n!$.

Now the Euclidean unit ball is contained in $\sqrt{n}K$, so its volume is at most $n^{n/2}2^n/n!$. This tends to $0$ and behaves like $(c/\sqrt{n})^n$ for some constant $c$.

The value is sharp up to the value of $c$, as shown by the dual argument : the unit ball contains the cube $[-1/\sqrt{n},1/\sqrt{n}]^n$.

Answer by Guillaume Aubrun for How long for a simple random walk to exceed sqrt(T)?

2009-11-23T08:47:27Z

I doubt whether you can write down an exact formula for the distribution of T.

If you are interested in large values of k, the law of the iterated logarithm will enter into the picture. The typical value of T (say, the expectation) should be of order $exp(exp(k^2/2))$.

Answer by Guillaume Aubrun for Characterizing the Radon transforms of log-concave functions

2009-10-22T07:32:54Z

If I understand the question correctly, I think the answer is no.

Start with the following : if f is the indicator function of the unit ball, then the function g(r) is strictly log-concave close to 0 (this function does not depend on theta).

Now, let h be the indicator function of the ball of radius r<1. Then f-epsilon.h is never log-concave for any epsilon>0, and its Radon transform (which again is independent of theta) remains log-concave is epsilon is small enough.

(this is especially easy to see in dimension 2, in which case the Radon transforms of both f and h are second-degree polynomials on their support)

Comment by Guillaume Aubrun

2013-06-03T12:37:28Z

A side remark: this non-centered semicircle distribution whose moments are the Motzkin numbers appears in some problems connected to quantum information theory, see e.g. arxiv.org/abs/1011.0275. If this showed up in another context, I'm very interested !

Comment by Guillaume Aubrun

2013-01-22T14:52:20Z

For the first question, yes. This is a theorem due to Blaschke and Hessenberg, see Theorem 2 in C.A. Rogers, "Sections and projections of convex bodies", purl.pt/2464/1/j-5293-b-vol24-fasc2-art3_PDF/…

Comment by Guillaume Aubrun

2012-08-27T15:11:49Z

A natural extension of the question is whether every non-negative smooth function is the sum of finitely many squares of smooth functions. The standard anwser from the literature seems to be "there is an unpublished counterexample by S.Cohen and D.Epstein". Does anybody know what this counterexample look like ?

Comment by Guillaume Aubrun

2012-05-25T16:32:50Z

For the unpinned Brownian motion, it seems to me that any permutation has probability at most $1/2^{n-1}$. To achieve any fixed permutation, for each $k$, condionnally on $(B(0), \dots, B(k)$, the difference $B(k+1)-B(k)$ must belong to some interval which is either contained in $[0,+\infty)$ or $(-\infty,0]$. This happens with probability less than $1/2$.

Comment by Guillaume Aubrun

2012-05-23T09:50:52Z

Note that a random subset of density 1/2 cannot work in general for Nik's question : if the initial set contains 1000 copies of a small multiple of each vector from the canonical basis in $\mathbb{R}^n$, and $n$ is very large, then typically a random half-set will miss one of the vectors.

Comment by Guillaume Aubrun

2012-05-22T09:01:38Z

Do you know the recent results by Srivastava and coauthors about sparsification of graphs ? There are able to select points by a clever inductive procedure, and prove results that were out of reach by random constructions. Maybe some variant of their ideas can be useful here ? See e.g. the survey arxiv.org/abs/1101.4324

Comment by Guillaume Aubrun

2011-10-19T14:55:34Z

I think this is known as the "double cap conjecture", and in particular would imply better estiamtes in the "Borsuk problem". The person to ask is probably Gil Kalai. See e.g. gilkalai.wordpress.com/2009/05/22/…

Comment by Guillaume Aubrun

2011-10-13T08:58:29Z

OK, I got it now, that's indeed a nice argument although it may be hard to write down. Thanks ! This gives also a proof of the usual isoperimetric inequality which I didn't know. Is this proof standard, or written somewhere ?

Comment by Guillaume Aubrun

2011-10-12T12:00:29Z

I don't understand why the total length of $\partial K \cap F$ is at least as big as the mean shadow of $F$. It seems to me that $\partial K \cap F$ can be arbitrary small for a given mean shadow (consider the case when $F_1,F_2,F_3$ are very small balls around the vertices of a large equilateral triangle, and $F_4$ anything inside the triangle). Did I miss something ?

Comment by Guillaume Aubrun

2011-10-12T04:37:17Z

I see you are interested in quantum complexity, so maybe a source is arxiv.org/pdf/1106.2264. We apply a more sophisticated version of the argument to a problem in quantum information, and we introduce all the material we need in Appendices.

Comment by Guillaume Aubrun

2011-10-11T17:15:16Z

Note that your argument works (shadows in every directions decrease) in the case when $A_1,\dots,A_n$ have a center of symmetry, basically by the one-dimensional version of the Hadwiger-Kneser-Poulsen conjecture.

Comment by Guillaume Aubrun

2011-10-11T14:21:16Z

That's a very interesting idea, but it's not clear to me that it works, and it does not seem true that the shadow in every direction is non-increasing when the sets move as you describe. For example take 2 (disjoint) congruent equilateral triangles, one pointing to the right, and one pointing to the left, such that their vertical shadows coincide. When you move them along the line passing though their barycenters, the vertical shadow is actually increasing !

Comment by Guillaume Aubrun

2011-10-10T10:09:18Z

For connected sets, taking the convex hull does not change the mean shadow, but for non-connected sets it increases ...

Comment by Guillaume Aubrun

2011-02-04T08:22:31Z

Are you aware of the fact that the answer is positive when the initial vectors belong to $\mathbb{R}^k$ ? This follows from the existence of a $k$-subspace in $B(R^{2^k})$ in which every matrix is a multiple of an orthogonal matrix (Clifford algebras give that); this was used by Tsirelson to connect Grothendieck theorem and Bell inequalities. See tau.ac.il/~tsirel/download/qbell87.html

Comment by Guillaume Aubrun

2010-12-01T09:30:10Z

I've been told offline that the relevant theorem to use is a weighted Weierstrass approximation theorem. Let $W(x)=\exp(x^2/2)$ ; given a continuous function $f$ so that $f(x)=o(W(x))$ at infinity, and $\epsilon >0$, there exists a polynomial $P$ so that $|P(x)-f(x)| \leq \epsilon W(x)$. This apparently is not so easy to prove (!?), but it is a standard problem to decide which functions $W$ satisfy this; a reference is: "Koosis, The logarithmic integral". Once you know this, few tricks suffice to prove what I asked (for example, positivity can be enforced by squaring the polynomial).