User guillaume aubrun - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T08:03:52Z http://mathoverflow.net/feeds/user/908 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77681/isoperimetric-like-inequality-for-non-convex-sets Isoperimetric-like inequality for non-convex sets Guillaume Aubrun 2011-10-10T09:58:57Z 2011-10-12T22:12:11Z <p>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$.</p> <p>There are several ways to define the perimeter. Here is a unusual one: if $A \subset \mathbb{R}^2$ is a <strong>convex</strong> set, the <a href="http://en.wikipedia.org/wiki/Crofton_formula" rel="nofollow">Cauchy-Crofton formula</a> says that the perimeter of $A$ equals the measure of the set of lines that hit $A$, or</p> <p>$$p(A) = \frac{1}{2} \int_{S^1} \lambda(P_{\theta} A) d\theta,$$</p> <p>where $P_\theta$ is the orthogonal projection in the direction $\theta \in S^1$, and $\lambda$ the Lebesgue measure on any line.</p> <p>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$ ?</p> <p>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).</p> http://mathoverflow.net/questions/56218/the-volume-of-the-unit-ball-in-mathbbrm-times-n-with-respect-to-the-cut/77798#77798 Answer by Guillaume Aubrun for The volume of the “unit ball” in $\mathbb{R}^{m\times n}$ with respect to the cut norm Guillaume Aubrun 2011-10-11T09:08:40Z 2011-10-11T09:08:40Z <p>A standard argument (Lemma 3.1 <a href="http://www.cims.nyu.edu/~naor/homepage%2520files/cutnorm.pdf" rel="nofollow">here</a>) 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 <a href="http://mathoverflow.net/questions/60062/volume-of-the-unit-ball-of-the-banach-space-ell-1n-otimes-epsilon-ell-1n/60175#60175" rel="nofollow">this question</a> (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. </p> <p>I guess this logarithm is not necessary, but I don't know how to remove it.</p> http://mathoverflow.net/questions/60062/volume-of-the-unit-ball-of-the-banach-space-ell-1n-otimes-epsilon-ell-1n/60175#60175 Answer by Guillaume Aubrun for volume of the unit ball of the Banach space $\ell_1^n\otimes_{\epsilon}\ell_1^n$? Guillaume Aubrun 2011-03-31T11:50:41Z 2011-03-31T11:50:41Z <p>Here is an argument that is certainly overkill and introduces a logarithmic factor which is probably unnecessary.</p> <p>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 </p> <p>$$w(K) = \int_{S} \|x\|_{K^\circ} d\sigma(x)$$</p> <p>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</p> <p>$$w(K^\circ)^{-1} \leq vrad(K^\circ)^{-1} \lesssim vrad(K) \leq w(K)$$</p> <p>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.</p> <p>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).</p> <p>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</p> <p>$$w(K^\circ) \approx \sqrt{n}$$</p> <p>and therefore</p> <p>$$1/\sqrt{n} \lesssim vrad(K) \lesssim \log n/\sqrt{n} .$$ </p> <p>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".</p> http://mathoverflow.net/questions/47656/polynomial-upper-approximation-with-respect-to-the-gaussian-measure Polynomial upper approximation with respect to the Gaussian measure Guillaume Aubrun 2010-11-29T09:46:37Z 2010-11-29T14:19:43Z <p>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 <code>$$\lim_{n\to \infty} \int_{\mathbf{R}} P_n d\gamma = \int_{\mathbf{R}} f d\gamma,$$</code> where $\gamma$ denotes the usual Gaussian measure ?</p> http://mathoverflow.net/questions/41758/pinching-and-positive-definite-matrices/41799#41799 Answer by Guillaume Aubrun for Pinching and positive definite matrices Guillaume Aubrun 2010-10-11T15:57:52Z 2010-10-11T20:13:42Z <p>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 </p> <p>(4) T is positive,</p> <p>and that it can be proved via the following: if a $0/1$-matrix $T$, with $1$ on the diagonal, avoids the pattern <code>$\left( \begin{array}{ccc} 1 &amp; 1 &amp; 0 \\ 1 &amp; 1 &amp; 1 \\ 0 &amp; 1 &amp; 1 \end{array} \right)$</code>, then $T$ must be block-diagonal.</p> <p>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).</p> http://mathoverflow.net/questions/13356/orthogonal-matrices-with-small-entries Orthogonal matrices with small entries Guillaume Aubrun 2010-01-29T08:43:08Z 2010-08-29T17:21:58Z <p>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 ?</p> <p>Some remarks :</p> <ul> <li>If we want $C=1$, the matrix must be a Hadamard matrix.</li> <li>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.</li> <li>A random matrix doesn't work (the largest entry is typically of order $\sqrt{\log(n)}/\sqrt{n}$).</li> </ul> http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm/1729#1729 Answer by Guillaume Aubrun for Euclidean volume of the unit ball of matrices under the matrix norm Guillaume Aubrun 2009-10-21T21:30:01Z 2010-02-01T06:06:52Z <p>The volume of the unit ball for the spectral norm in nxn real matrices is given by the formula</p> <p>$$c_n \int\limits_{[-1,1]^n} \prod_{i &lt; j} |x_i^2-x_j^2| dx_1\dots dx_n$$</p> <p>where $c_n = n! 4^{-n} \prod_{k=1}^n v_k^2$</p> <p>and $v_k=\pi^{k/2}/\Gamma(1+k/2)$ is the volume of the unit ball in R^n.</p> <p>A much more general formula for calculating all kind of similar quantities appears e.g. <a href="http://analysis.math.uni-kiel.de/koenig/inhalte/isotropy.pdf" rel="nofollow">here</a> (Lemma 1). The proof is by applying the SVD decomposition as a change of variables.</p> <p>The first values are</p> <ul> <li>2/3 &pi;<sup>2</sup> for 2x2 matrices</li> <li>8/45 &pi;<sup>4</sup> for 3x3 matrices</li> <li>4/1575 &pi;<sup>8</sup> for 4x4 matrices ...</li> </ul> <p>There might be a closed formula for the integral above. Edit : such a formula appears in Armin's post below !!</p> http://mathoverflow.net/questions/8258/whats-a-nice-argument-that-shows-the-volume-of-the-unit-n-ball-in-rn-approaches/12418#12418 Answer by Guillaume Aubrun for What's a nice argument that shows the volume of the unit n-ball in R^n approaches 0? Guillaume Aubrun 2010-01-20T15:21:13Z 2010-01-27T07:38:26Z <p>There is a simple argument by comparing to the unit ball of $\ell_1^n$.</p> <p>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!$.</p> <p>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$.</p> <p>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$.</p> http://mathoverflow.net/questions/6444/how-long-for-a-simple-random-walk-to-exceed-sqrtt/6545#6545 Answer by Guillaume Aubrun for How long for a simple random walk to exceed sqrt(T)? Guillaume Aubrun 2009-11-23T08:47:27Z 2009-11-23T08:47:27Z <p>I doubt whether you can write down an exact formula for the distribution of T.</p> <p>If you are interested in large values of k, the <a href="http://en.wikipedia.org/wiki/Law%5Fof%5Fthe%5Fiterated%5Flogarithm" rel="nofollow">law of the iterated logarithm</a> will enter into the picture. The typical value of T (say, the expectation) should be of order $exp(exp(k^2/2))$.</p> http://mathoverflow.net/questions/452/characterizing-the-radon-transforms-of-log-concave-functions/1838#1838 Answer by Guillaume Aubrun for Characterizing the Radon transforms of log-concave functions Guillaume Aubrun 2009-10-22T07:32:54Z 2009-10-22T07:32:54Z <p>If I understand the question correctly, I think the answer is no.</p> <p>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).</p> <p>Now, let h be the indicator function of the ball of radius r&lt;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.</p> <p>(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)</p> http://mathoverflow.net/questions/75059/recognizing-a-measure-whose-moments-are-the-motzkin-numbers Comment by Guillaume Aubrun Guillaume Aubrun 2013-06-03T12:37:28Z 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. <a href="http://arxiv.org/abs/1011.0275" rel="nofollow">arxiv.org/abs/1011.0275</a>. If this showed up in another context, I'm very interested ! http://mathoverflow.net/questions/119570/convex-bodies-with-symmetric-shadows Comment by Guillaume Aubrun Guillaume Aubrun 2013-01-22T14:52:20Z 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, &quot;Sections and projections of convex bodies&quot;, <a href="http://purl.pt/2464/1/j-5293-b-vol24-fasc2-art3_PDF/j-5293-b-vol24-fasc2-art3_PDF_01-B-R0300/j-5293-b-vol24-fasc2-art3_0000_capa1-103_t01-B-R0300.pdf" rel="nofollow">purl.pt/2464/1/j-5293-b-vol24-fasc2-art3_PDF/&hellip;</a> http://mathoverflow.net/questions/105438/square-root-of-a-positive-c-infty-function Comment by Guillaume Aubrun Guillaume Aubrun 2012-08-27T15:11:49Z 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 &quot;there is an unpublished counterexample by S.Cohen and D.Epstein&quot;. Does anybody know what this counterexample look like ? http://mathoverflow.net/questions/97875/random-permutations-from-brownian-motion Comment by Guillaume Aubrun Guillaume Aubrun 2012-05-25T16:32:50Z 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$. http://mathoverflow.net/questions/96782/vector-balancing-problem/97726#97726 Comment by Guillaume Aubrun Guillaume Aubrun 2012-05-23T09:50:52Z 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. http://mathoverflow.net/questions/96782/vector-balancing-problem Comment by Guillaume Aubrun Guillaume Aubrun 2012-05-22T09:01:38Z 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 <a href="http://arxiv.org/abs/1101.4324" rel="nofollow">arxiv.org/abs/1101.4324</a> http://mathoverflow.net/questions/78486/maximal-set-on-hypersphere-that-does-not-contain-pairs-of-orthogonal-vectors Comment by Guillaume Aubrun Guillaume Aubrun 2011-10-19T14:55:34Z 2011-10-19T14:55:34Z I think this is known as the &quot;double cap conjecture&quot;, and in particular would imply better estiamtes in the &quot;Borsuk problem&quot;. The person to ask is probably Gil Kalai. See e.g. <a href="http://gilkalai.wordpress.com/2009/05/22/how-large-can-a-spherical-set-without-two-orthogonal-vectors-be/" rel="nofollow">gilkalai.wordpress.com/2009/05/22/&hellip;</a> http://mathoverflow.net/questions/77681/isoperimetric-like-inequality-for-non-convex-sets/77784#77784 Comment by Guillaume Aubrun Guillaume Aubrun 2011-10-13T08:58:29Z 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 ? http://mathoverflow.net/questions/77681/isoperimetric-like-inequality-for-non-convex-sets/77784#77784 Comment by Guillaume Aubrun Guillaume Aubrun 2011-10-12T12:00:29Z 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 ? http://mathoverflow.net/questions/56218/the-volume-of-the-unit-ball-in-mathbbrm-times-n-with-respect-to-the-cut/77798#77798 Comment by Guillaume Aubrun Guillaume Aubrun 2011-10-12T04:37:17Z 2011-10-12T04:37:17Z I see you are interested in quantum complexity, so maybe a source is <a href="http://arxiv.org/pdf/1106.2264" rel="nofollow">arxiv.org/pdf/1106.2264</a>. 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. http://mathoverflow.net/questions/77681/isoperimetric-like-inequality-for-non-convex-sets/77815#77815 Comment by Guillaume Aubrun Guillaume Aubrun 2011-10-11T17:15:16Z 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. http://mathoverflow.net/questions/77681/isoperimetric-like-inequality-for-non-convex-sets/77815#77815 Comment by Guillaume Aubrun Guillaume Aubrun 2011-10-11T14:21:16Z 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 ! http://mathoverflow.net/questions/77681/isoperimetric-like-inequality-for-non-convex-sets Comment by Guillaume Aubrun Guillaume Aubrun 2011-10-10T10:09:18Z 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 ... http://mathoverflow.net/questions/53359/commuting-unitaries Comment by Guillaume Aubrun Guillaume Aubrun 2011-02-04T08:22:31Z 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 <a href="http://www.tau.ac.il/~tsirel/download/qbell87.html" rel="nofollow">tau.ac.il/~tsirel/download/qbell87.html</a> http://mathoverflow.net/questions/47656/polynomial-upper-approximation-with-respect-to-the-gaussian-measure Comment by Guillaume Aubrun Guillaume Aubrun 2010-12-01T09:30:10Z 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 &gt;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: &quot;Koosis, The logarithmic integral&quot;. Once you know this, few tricks suffice to prove what I asked (for example, positivity can be enforced by squaring the polynomial).