User gideon schechtman - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T21:21:20Z http://mathoverflow.net/feeds/user/6921 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66084/open-problems-with-monetary-rewards/66166#66166 Answer by Gideon Schechtman for Open problems with monetary rewards Gideon Schechtman 2011-05-27T09:28:55Z 2011-05-27T09:28:55Z <p>See <a href="http://people.math.jussieu.fr/~talagran/prizes.pdf" rel="nofollow">http://people.math.jussieu.fr/~talagran/prizes.pdf</a> for a total of $\$7000$offered by Michel Talagrand for a solution of three problems. In particular$\$5000$ for the "Bernoulli conjecture". You may also be interested in the following picture of Mazur awarding Per Enflo a live goose as promised for the solution of the approximation problem. <a href="http://en.wikipedia.org/wiki/File:MazurGes.jpg" rel="nofollow">http://en.wikipedia.org/wiki/File:MazurGes.jpg</a></p> http://mathoverflow.net/questions/56118/spaces-with-a-quasi-triangle-inequality/56155#56155 Answer by Gideon Schechtman for Spaces with a quasi triangle inequality Gideon Schechtman 2011-02-21T09:12:06Z 2011-02-21T09:17:31Z <p>Here is a negative answer for your additional remark concerning Banach's fixed point theorem: Consider $d(x,y)=(\int_0^1|x-y|^p)^{1/p},$ <code>$0&lt;p&lt;1$</code> which satisfies the quasi-triangle inequality. Look at the set of all (measurable real) functions on $[0,1]$ boundaed between 0 and 2 and of integral 1. Look at the Baker transformation on this set: first map $x$ to $y(t)=2x(2t)$, $0\le t\le 1/2$ then trancate at hight 2 and shift what remains ($(y-1)^{+}$) by $1/2$ to the right and $2$ down. I think I checked that it is a contraction (with constant $2^{p-1}$). This map is known not to have a fixed point, see the following paper of Dale Alspach: <a href="http://www.claremontmckenna.edu/math/moneill/Math%20138/papers138/Alspach.pdf" rel="nofollow">http://www.claremontmckenna.edu/math/moneill/Math%20138/papers138/Alspach.pdf</a></p> http://mathoverflow.net/questions/54954/why-is-the-dimension-of-gaussian-variables-is-bounded-by-the-dimension-of-the-spa/55017#55017 Answer by Gideon Schechtman for Why is the dimension of Gaussian variables is bounded by the dimension of the space? Gideon Schechtman 2011-02-10T11:12:53Z 2011-02-10T11:12:53Z <p>None of these estimates is trivial. The upper bound follows from John's theorem that the Banach-Mazur distance between an N dimensional normed space and an N dimensional Euclidean space is at most $\sqrt N$. The lower bound is more involved and uses the Dvoretzky-Rogers lemma. A good reference for the Gaussian approach to Dvoretzky's theorem is Pisier's book: The volume of convex bodies and Banach space geometry. For a more geometrical approach see: Milman and Schechtman: Asymptotic theory of finite-dimensional normed spaces. The theorem and it's proof is presented in other books as well.</p> http://mathoverflow.net/questions/54130/when-does-inner-product-with-fixed-vectors-determine-joint-distribution/54133#54133 Answer by Gideon Schechtman for when does inner product with fixed vectors determine joint distribution? Gideon Schechtman 2011-02-02T21:04:00Z 2011-02-02T21:04:00Z <p>The first question has an affirmative answer. If two 2-dimensional distributions have the same (2-dim) characteristic functions they coincide. The characteristic function of the 2-dimensional distribution of (X,Y) is determined only by the distributions of aX+bY for all a and b. The proof of that fact (Fourier inversion formula) may help to solve the second question as well.</p> http://mathoverflow.net/questions/49688/explicit-embedding-of-ell1-as-a-closed-subalgebra-of-a-direct-sum-of-matrix/49780#49780 Answer by Gideon Schechtman for "Explicit" embedding of $\ell^1$ as a closed subalgebra of a direct sum of matrix algebras Gideon Schechtman 2010-12-18T06:34:56Z 2010-12-18T08:30:25Z <p>Here is simple construction for $m(n)=2^n$. As is indicated in the remarks above one can't get an essentially lower dimension.</p> <p>The $E_i$-s will be diagonal matrices. $E_1$ will have the first half diagonal entries equal to 1 the second half 0. $E_2$ the first and third fourths 1-s the rest zeroes, ..., $E_n$ alternatively 1 and zero. (These are $(r_i+1)/2$ where $r_i$ are the Rademacher functions). The point is that for each subset $A$ of ${1,\dots,n}$ there is a $j$ such that ${E_1(j,j),\dots,E_n(j,j)}$ is exactly the indicator function of $A$. The $E_i$ are idempotents.</p> <p>Using the equivalent $\ell_1$ norm $\|\cdot\|_S$ at the end of the question, it is easy to see that these satisfy the inequalities. They satisfy them with constants 1 for the $\|\cdot\|_S$ norm.</p> <p><strong>Update:</strong> Disregard this answer. It relates to a previous version of Yemon's question.</p> http://mathoverflow.net/questions/49136/norms-over-some-subspaces/49140#49140 Answer by Gideon Schechtman for Norms over some subspaces Gideon Schechtman 2010-12-12T13:32:33Z 2010-12-12T21:15:45Z <p>The answer is negative. You can achieve at most $O(\sqrt{n\log n})$.</p> <p>Since more than half of the $\pm 1$ vectors are in $C$, </p> <p><code>$$\|A\|_{C,\infty} \leq 2 Aver(\|Av\|_\infty),$$</code></p> <p>where the Average is taken over all $\pm 1$ vectors.</p> <p>To give an upper bound on $Aver(\|Av\|_\infty)$, note that each of the coordinates of $Av$ has distribution whose tail is subgaussian with parameter $\sqrt n$. By that I mean $Prob(|\sum_ja_{ij}v_j|>C\sqrt n t)\le e^{-t^2}$, for some absolute constant $C$.</p> <p>It follows that the expectation of the maximum of $\Lambda n$ such variables is at most $O(\sqrt{n\log n})$. (Note that independence of these variables is not needed).</p> http://mathoverflow.net/questions/47869/orthogonal-complement-of-a-subspace-of-a-banach-space/47880#47880 Answer by Gideon Schechtman for "Orthogonal complement" of a subspace of a Banach space Gideon Schechtman 2010-12-01T08:06:14Z 2010-12-01T08:06:14Z <p>You can make the norm of $\|\Phi^{-1}\|$ to be of order $\sqrt n$. This is basically a theorem of Kadets and Snobar. A good reference is III.B.11 in Wojtaszczyk, P., Banach spaces for analysts, Cambridge Studies in Advanced Mathematics, 25. Cambridge University Press, Cambridge, 1991.</p> http://mathoverflow.net/questions/47661/concentration-bound-using-azumas-inequality-and-law-of-total-probability/47665#47665 Answer by Gideon Schechtman for Concentration bound using Azuma's inequality and Law of total probability Gideon Schechtman 2010-11-29T11:38:28Z 2010-11-29T11:38:28Z <p>See my comment above for some problem in your argument but anyhow (3) is wrong. If the $X_i$-s are constants then the right hand side of (3) is 0, while the left hand side is not in general. If you don't like to use constant r.v.: if each of the $X_i$ takes values in a small interval, the right hand side is arbitrarily close to zero while the left hand side not, in general (say, for the function $f(x_1,...,x_n,y)=y$ and any reasonable $Y$).</p> http://mathoverflow.net/questions/46991/brownian-bridge-interpreted-as-brownian-motion-on-the-circle/47058#47058 Answer by Gideon Schechtman for Brownian bridge interpreted as Brownian motion on the circle Gideon Schechtman 2010-11-23T06:17:09Z 2010-11-23T10:43:27Z <p>What is wrong with the following simple definition? Let $g_1$ and $g_2$ be two independent standard Gaussian variables. For $t=(a,b)\in S^1$ (so $a^2+b^2=1$), let $B_t=ag_1+bg_2$. You get a Gaussian process whose distribution is invariant under rotation. Each $B_t$ is a standard Gaussian variable and the variance of $B_t-B_s$ is $\|t-s\|^2$. </p> <p>Following Ori's remark below, concerning the 2-dimensionality, maybe a better simple suggestion is the following: Take two independent Brownian motions on $(-\infty, \infty)$, $C_a,D_a$ ($C_0=D_0=0$) and for $t=(a,b)\in S^1$ define $B_t=C_a+D_b$.</p> <p>On third thought, this is probably just a Brownian motion on $R^2$ (zero at the origin) restricted to $S^1$.</p> http://mathoverflow.net/questions/46883/examples-of-using-physical-intuition-to-solve-math-problems/46905#46905 Answer by Gideon Schechtman for Examples of using physical intuition to solve math problems Gideon Schechtman 2010-11-22T05:06:40Z 2010-11-22T05:06:40Z <p>For electrical network intuition/applications to random walks see the beautiful little book of Doyle and Snell <a href="http://arxiv.org/abs/math/0001057" rel="nofollow">http://arxiv.org/abs/math/0001057</a></p> http://mathoverflow.net/questions/45594/how-small-can-the-set-of-p-such-that-the-lp-norms-are-different-for-two-fixe/45649#45649 Answer by Gideon Schechtman for How small can the set of $p$ such that the $L^p$ norms are different for two fixed functions? Gideon Schechtman 2010-11-11T05:47:28Z 2010-11-11T09:28:00Z <p>The complement of $S$ in $(1,\infty)$ can't contain an interval or even a sequence converging to a point in $(1,\infty)$. Let $f$ and $g$ be two real functions on ${\mathbb{R}}$ all whose moments exist. Assume $\int|f|^p=\int|g|^p$ for all $p\in S^c$. put $h(z)=\int|f|^z-\int|g|^z$. where $z\in \mathbb{C}$. $h$ is an analytic functions in $\{Real z>1\}$ which we assume is not constantly zero (since $S$ is not empty) so can't vanish on a converging sequence.</p> http://mathoverflow.net/questions/45422/maximal-coordinate-on-a-sphere/45425#45425 Answer by Gideon Schechtman for maximal coordinate on a sphere Gideon Schechtman 2010-11-09T12:42:09Z 2010-11-09T12:42:09Z <p>For some positive $c$ bounded away from zero, the probability that a standard gaussian variable is larger than $c\sqrt{\log n}$ is $1/n$. It follows that the probability that at least one variable out of $n$ independent standard gaussians is larger than $c\sqrt{\log n}$ is $1-(1-1/n)^n$ which tends to $1-1/e$. From that one gets that the expectation of the maximum of $n$ standard gaussians is at least (basically) $(1-1/e)c\sqrt{\log n}$. As you said the question about variables on the sphere is equivalent to that.</p> http://mathoverflow.net/questions/41453/synthetic-proof-for-ratio-of-volumes-of-concentric-spheres/41458#41458 Answer by Gideon Schechtman for Synthetic Proof for Ratio of Volumes of Concentric Spheres? Gideon Schechtman 2010-10-07T21:17:11Z 2010-10-07T21:17:11Z <p>${\text{Vol}(B^n(r))}=r^n{\text{Vol}(B^n(1))}$ by the homogeneity of degree $n$ of the Lebegue measure. Consequently, $\frac{\text{Vol}(B^n(r))}{\text{Vol}(B^n(1)\setminus B^n(r))}=\frac{r^n}{1-r^n}\to 0$ exponentialy fast.</p> <p>But maybe this is too analytic?</p> http://mathoverflow.net/questions/35932/cosine-sum-problem/35939#35939 Answer by Gideon Schechtman for Cosine sum problem Gideon Schechtman 2010-08-18T07:11:20Z 2010-08-18T07:11:20Z <p>Assume $\sum_{i=1}^n a_i x_i=0$ with $x_i$ on the circle and $a_i>0$, $\sum a_i=1$. Then $\sum_{i=1}^n\sum_{j=1}^n a_i\langle x_i,x_j\rangle=0$.</p> <p>It follows that for some $i$, $\sum_{j=1}^n\langle x_i,x_j\rangle\le 0$.</p> <p>Since $\langle x_i,x_i\rangle=1$, it implies $\sum_{j; j\not=i} \langle x_i,x_j\rangle\le -1$ which is what you want.</p> http://mathoverflow.net/questions/31208/inner-products-and-norms/31246#31246 Answer by Gideon Schechtman for Inner products and Norms Gideon Schechtman 2010-07-09T20:51:13Z 2010-07-09T23:09:09Z <p>Such questions have been dealt with. Note first that your $m$ is just the norm of the matrix $F$ (see Robin's comment) as an operator from $\ell_1^n$ to $\ell_\infty^n$. $M$ also has a name, it is the $\gamma_2$ norm of this operator (This is the minimal product of <code>$$\|Y\|_{1\to 2}\|X\|_{2\to\infty}$$</code> over all factorizations $F=XY$ . <code>$\|Z\|_{p\to q}$</code> denotes the norm of Z as an operator from $\ell_p$ to $\ell_q$.) It is not hard to see that <code>$M=\gamma_2(F)\le \sqrt n \|F\|_{1\to\infty}=\sqrt n m$</code>. For a random $0,1$ matrix $F$ one gets that this estimate is tight, up to a universal constant. You can look here <a href="http://www.springerlink.com/content/px2324p527n19xj2/" rel="nofollow">http://www.springerlink.com/content/px2324p527n19xj2/</a> for details. In particular Cor 5.2 there (it deals with random $\pm 1$ matrices but it is easy to go between those and random $0,1$ matrices).</p> http://mathoverflow.net/questions/28610/probability-of-a-point-on-a-unit-sphere-lying-within-a-cube/28818#28818 Answer by Gideon Schechtman for Probability of a Point on a Unit Sphere lying within a Cube Gideon Schechtman 2010-06-20T08:42:00Z 2010-06-20T08:42:00Z <p>Denote the median of $\max_{i=1,\dots,n}|x_i|$ on the sphere by $M_n$. It is known that the ratio between $M_n$ and $\sqrt{\log n/n}$ is universally bounded and bounded away from zero. If you take $d=M_n$ then the quantity you are looking for is exactly $1/2$. It is also known that the $\infty$-norm ($\max_{i=1,\dots,n}|x_i|$) is well concentrated" on the sphere meaning in particular that for any $\epsilon>0$, if you take $d&lt;(1-\epsilon)M_n$ the probability you're interested in tends to zero and if you take $d>(1+\epsilon)M_n$, it tends to 1. Quite precise estimates are known.</p> <p>The way these things are estimated is by relating the uniform distribution on the sphere to the distribution of a standard Gaussian vector: If $g_1,\dots,g_n$ are independent standard Gaussian variables then the distribution of $$\frac{(g_1,\dots,g_n)}{(\sum g_i^2)^{1/2}}$$ is equal to the uniform distribution on the sphere. So the quantity you're looking for is the probability that $\max_{i=1,\dots,n}|g_i|\le d (\sum g_i^2)^{1/2}$. Since $(\sum g_i^2)^{1/2}$ is very well concentrated near the constant $\sqrt n$, this is asymptotically the same as the probability that $\max_{i=1,\dots,n}|g_i|\le d \sqrt n$. </p> <p>For general reference in a much more general setting you can look here: Milman, Schechtman, Asymptotic theory of finite-dimensional normed spaces. For a finer treatment of the special case of the $\infty$-norm, look here: <a href="http://www.wisdom.weizmann.ac.il/mathusers/gideon/papers/ranDv.pdf" rel="nofollow">http://www.wisdom.weizmann.ac.il/mathusers/gideon/papers/ranDv.pdf</a>.</p> http://mathoverflow.net/questions/49688/explicit-embedding-of-ell1-as-a-closed-subalgebra-of-a-direct-sum-of-matrix Comment by Gideon Schechtman Gideon Schechtman 2010-12-17T20:56:30Z 2010-12-17T20:56:30Z Hi Bill. The type 2 constant of $M_m$ is of order $\sqrt{\log m}$, by comparing with that of $S_p^n$ (which is of order $\sqrt p$). This gives that if $\ell_1^n$ nicely embeds in $M_m$ then m in exponential in $n$. http://mathoverflow.net/questions/49688/explicit-embedding-of-ell1-as-a-closed-subalgebra-of-a-direct-sum-of-matrix Comment by Gideon Schechtman Gideon Schechtman 2010-12-17T10:56:11Z 2010-12-17T10:56:11Z Yemon, are you sure about the dimension $2n+2$? I think it is wrong. Maybe you mean $2^n$? http://mathoverflow.net/questions/49395/behaviour-of-power-series-on-their-circle-of-convergence Comment by Gideon Schechtman Gideon Schechtman 2010-12-14T16:27:35Z 2010-12-14T16:27:35Z Until Andres return you can look at the paper below (can be found by google search) which has a lot of information. In particular any $G_\delta$ set and any $F_\sigma$ sets of logarithmic measure zero is a set of divergence. Erd&#246;s, Paul; Herzog, Fritz; Piranian, George, Sets of divergence of Taylor series and of trigonometric series. Math. Scand. 2, (1954). 262ā266. http://mathoverflow.net/questions/49219/idiosyncratic-characterizations-of-ellp-for-p-not1-2-infty/49230#49230 Comment by Gideon Schechtman Gideon Schechtman 2010-12-13T10:05:08Z 2010-12-13T10:05:08Z There are p-stable distributions for all 0&lt;pā¤2. I think this is usually attributed to Paul Levy. You can find this in many books. I particularly like the construction in Chung's A course in probability theory. http://mathoverflow.net/questions/49136/norms-over-some-subspaces/49140#49140 Comment by Gideon Schechtman Gideon Schechtman 2010-12-12T21:15:15Z 2010-12-12T21:15:15Z Right, the $\frac12$ should have been 2. I'll correct it now. http://mathoverflow.net/questions/47661/concentration-bound-using-azumas-inequality-and-law-of-total-probability Comment by Gideon Schechtman Gideon Schechtman 2010-11-29T10:45:07Z 2010-11-29T10:45:07Z (2) doesn't follow from the preceeding line. For example if all the $X_i$ are constants, so that $f$ is a function of $Y$ only, then the left hand side of the preceeding line is 0 for all $y$ and $t&gt;0$ while the left hand side of (2) is in general not 0 . http://mathoverflow.net/questions/46991/brownian-bridge-interpreted-as-brownian-motion-on-the-circle/47058#47058 Comment by Gideon Schechtman Gideon Schechtman 2010-11-23T08:20:19Z 2010-11-23T08:20:19Z Following Ori's two dimensionality objection, I editted my answer. http://mathoverflow.net/questions/46991/brownian-bridge-interpreted-as-brownian-motion-on-the-circle/47058#47058 Comment by Gideon Schechtman Gideon Schechtman 2010-11-23T07:55:51Z 2010-11-23T07:55:51Z As somebody above already remarked, it can't be an actual Brownian bridge. http://mathoverflow.net/questions/35932/cosine-sum-problem/35939#35939 Comment by Gideon Schechtman Gideon Schechtman 2010-08-18T11:54:15Z 2010-08-18T11:54:15Z By the circle above I meant the unit circle (so $\langle x, y\rangle$ is the cosine of the angle between $x$ and $y$. BTW, this works in any dimension just replace the unit circle with the unit sphere. http://mathoverflow.net/questions/31208/inner-products-and-norms/31246#31246 Comment by Gideon Schechtman Gideon Schechtman 2010-07-10T04:46:18Z 2010-07-10T04:46:18Z Bill, Thanks for the editing. http://mathoverflow.net/questions/31208/inner-products-and-norms/31246#31246 Comment by Gideon Schechtman Gideon Schechtman 2010-07-10T04:44:02Z 2010-07-10T04:44:02Z Mateus, you are right but it is easy to go between my $M$ and your $N$ (for the minimal representation). $M=N^2$. (Note that for the $i,j$ for which the max is attained in $N$ one has $\|x_i\|=\|y_j\|$). So $N= M^{1/2}\le n^{1/4}m^{1/2}$. and the random example shows that this is best possible, up to a universal constant. I hope it's OK now. http://mathoverflow.net/questions/30374/problem-in-banach-space Comment by Gideon Schechtman Gideon Schechtman 2010-07-04T06:41:08Z 2010-07-04T06:41:08Z Let $y_1,y_2,\dots$ be the monotone basis. Let $P_k$ be the projection onto the span of $y_1,y_2,\dots,y_k$ which annihilates $y_{k+1},y_{k+2},\dots$. Monotonicity means that $\|P_k\|\le 1$. It follows that $\|I-P_k\|\le 2$. The hint is to use this fact. ā Gideon Schechtman 14 secs ago http://mathoverflow.net/questions/30374/problem-in-banach-space Comment by Gideon Schechtman Gideon Schechtman 2010-07-03T19:18:27Z 2010-07-03T19:18:27Z Hint: Prove first that the norm of the natural projection onto any tail of the basis is of norm at most 2. http://mathoverflow.net/questions/30374/problem-in-banach-space Comment by Gideon Schechtman Gideon Schechtman 2010-07-03T09:06:39Z 2010-07-03T09:06:39Z Dan, Is the exercise for credit? If not let us know, I can give you a useful hint. http://mathoverflow.net/questions/29000/volumes-of-sets-of-constant-width-in-high-dimensions Comment by Gideon Schechtman Gideon Schechtman 2010-07-01T10:10:38Z 2010-07-01T10:10:38Z The two 1988 papers of Oded Schramm mentioned in Gil's question were essentially Oded's MSc thesis written under the guidance of Gil.