User gideon schechtman - MathOverflow

Answer by Gideon Schechtman for Open problems with monetary rewards

2011-05-27T09:28:55Z

See http://people.math.jussieu.fr/~talagran/prizes.pdf 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. http://en.wikipedia.org/wiki/File:MazurGes.jpg

Answer by Gideon Schechtman for Spaces with a quasi triangle inequality

2011-02-21T09:12:06Z

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},$ $0<p<1$ 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: http://www.claremontmckenna.edu/math/moneill/Math%20138/papers138/Alspach.pdf

Answer by Gideon Schechtman for Why is the dimension of Gaussian variables is bounded by the dimension of the space?

2011-02-10T11:12:53Z

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.

Answer by Gideon Schechtman for when does inner product with fixed vectors determine joint distribution?

2011-02-02T21:04:00Z

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.

Answer by Gideon Schechtman for "Explicit" embedding of $\ell^1$ as a closed subalgebra of a direct sum of matrix algebras

2010-12-18T06:34:56Z

Here is simple construction for $m(n)=2^n$. As is indicated in the remarks above one can't get an essentially lower dimension.

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.

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.

Update: Disregard this answer. It relates to a previous version of Yemon's question.

Answer by Gideon Schechtman for Norms over some subspaces

2010-12-12T13:32:33Z

The answer is negative. You can achieve at most $O(\sqrt{n\log n})$.

Since more than half of the $\pm 1$ vectors are in $C$,

$$\|A\|_{C,\infty} \leq 2 Aver(\|Av\|_\infty),$$

where the Average is taken over all $\pm 1$ vectors.

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$.

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).

Answer by Gideon Schechtman for "Orthogonal complement" of a subspace of a Banach space

2010-12-01T08:06:14Z

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.

Answer by Gideon Schechtman for Concentration bound using Azuma's inequality and Law of total probability

2010-11-29T11:38:28Z

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$).

Answer by Gideon Schechtman for Brownian bridge interpreted as Brownian motion on the circle

2010-11-23T06:17:09Z

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$.

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$.

On third thought, this is probably just a Brownian motion on $R^2$ (zero at the origin) restricted to $S^1$.

Answer by Gideon Schechtman for Examples of using physical intuition to solve math problems

2010-11-22T05:06:40Z

For electrical network intuition/applications to random walks see the beautiful little book of Doyle and Snell http://arxiv.org/abs/math/0001057

Answer by Gideon Schechtman for How small can the set of $p$ such that the $L^p$ norms are different for two fixed functions?

2010-11-11T05:47:28Z

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.

Answer by Gideon Schechtman for maximal coordinate on a sphere

2010-11-09T12:42:09Z

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.

Answer by Gideon Schechtman for Synthetic Proof for Ratio of Volumes of Concentric Spheres?

2010-10-07T21:17:11Z

${\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.

But maybe this is too analytic?

Answer by Gideon Schechtman for Cosine sum problem

2010-08-18T07:11:20Z

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$.

It follows that for some $i$, $\sum_{j=1}^n\langle x_i,x_j\rangle\le 0$.

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.

Answer by Gideon Schechtman for Inner products and Norms

2010-07-09T20:51:13Z

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 $$\|Y\|_{1\to 2}\|X\|_{2\to\infty}$$ over all factorizations $F=XY$ . $\|Z\|_{p\to q}$ denotes the norm of Z as an operator from $\ell_p$ to $\ell_q$.) It is not hard to see that $M=\gamma_2(F)\le \sqrt n \|F\|_{1\to\infty}=\sqrt n m$ . For a random $0,1$ matrix $F$ one gets that this estimate is tight, up to a universal constant. You can look here http://www.springerlink.com/content/px2324p527n19xj2/ 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).

Answer by Gideon Schechtman for Probability of a Point on a Unit Sphere lying within a Cube

2010-06-20T08:42:00Z

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<(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.

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$.

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: http://www.wisdom.weizmann.ac.il/mathusers/gideon/papers/ranDv.pdf.

Comment by Gideon Schechtman

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$.

Comment by Gideon Schechtman

2010-12-17T10:56:11Z

Yemon, are you sure about the dimension $2n+2$? I think it is wrong. Maybe you mean $2^n$?

Comment by Gideon Schechtman

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ös, Paul; Herzog, Fritz; Piranian, George, Sets of divergence of Taylor series and of trigonometric series. Math. Scand. 2, (1954). 262–266.

Comment by Gideon Schechtman

2010-12-13T10:05:08Z

There are p-stable distributions for all 0<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.

Comment by Gideon Schechtman

2010-12-12T21:15:15Z

Right, the $\frac12$ should have been 2. I'll correct it now.

Comment by Gideon Schechtman

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>0$ while the left hand side of (2) is in general not 0 .

Comment by Gideon Schechtman

2010-11-23T08:20:19Z

Following Ori's two dimensionality objection, I editted my answer.

Comment by Gideon Schechtman

2010-11-23T07:55:51Z

As somebody above already remarked, it can't be an actual Brownian bridge.

Comment by Gideon Schechtman

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.

Comment by Gideon Schechtman

2010-07-10T04:46:18Z

Bill, Thanks for the editing.

Comment by Gideon Schechtman

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.

Comment by Gideon Schechtman

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

Comment by Gideon Schechtman

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.

Comment by Gideon Schechtman

2010-07-03T09:06:39Z

Dan, Is the exercise for credit? If not let us know, I can give you a useful hint.

Comment by Gideon Schechtman

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.