This is an announcement for the paper "Pythagorean powers of hypercubes" by Assaf Naor and Gideon Schechtman.
Abstract: For $n\in \mathbb{N}$ consider the $n$-dimensional hypercube as equal to the vector space $\mathbb{F}_2^n$, where $\mathbb{F}_2$ is the field of size two. Endow $\mathbb{F}_2^n$ with the Hamming metric, i.e., with the metric induced by the $\ell_1^n$ norm when one identifies $\mathbb{F}_2^n$ with ${0,1}^n\subseteq \mathbb{R}^n$. Denote by $\ell_2^n(\mathbb{F}_2^n)$ the $n$-fold Pythagorean product of $\mathbb{F}_2^n$, i.e., the space of all $x=(x_1,\ldots,x_n)\in \prod_{j=1}^n \mathbb{F}_2^n$, equipped with the metric $$ \forall, x,y\in \prod_{j=1}^n \mathbb{F}_2^n,\qquad d_{\ell_2^n(\mathbb{F}_2^n)}(x,y)= \sqrt{ |x_1-y_1|_1^2+\ldots+|x_n-y_n|_1^2}. $$ It is shown here that the bi-Lipschitz distortion of any embedding of $\ell_2^n(\mathbb{F}_2^n)$ into $L_1$ is at least a constant multiple of $\sqrt{n}$. This is achieved through the following new bi-Lipschitz invariant, which is a metric version of (a slight variant of) a linear inequality of Kwapie{'n} and Sch"utt (1989). Letting ${e_{jk}}_{j,k\in {1,\ldots,n}}$ denote the standard basis of the space of all $n$ by $n$ matrices $M_n(\mathbb{F}_2)$, say that a metric space $(X,d_X)$ is a KS space if there exists $C=C(X)>0$ such that for every $n\in 2\mathbb{N}$, every mapping $f:M_n(\mathbb{F}_2)\to X$ satisfies \begin{equation*}\label{eq:metric KS abstract} \frac{1}{n}\sum_{j=1}^n\mathbb{E}\left[d_X\Big(f\Big(x+\sum_{k=1}^ne_{jk}\Big),f(x)\Big)\right]\le C \mathbb{E}\left[d_X\Big(f\Big(x+\sum_{j=1}^ne_{jk_j}\Big),f(x)\Big)\right], \end{equation*} where the expectations above are with respect to $x\in M_n(\mathbb{F}_2)$ and $k=(k_1,\ldots,k_n)\in {1,\ldots,n}^n$ chosen uniformly at random. It is shown here that $L_1$ is a KS space (with $C= 2e^2/(e^2-1)$, which is best possible), implying the above nonembeddability statement. Links to the Ribe program are discussed, as well as related open problems.
Archive classification: math.FA math.MG
Submitted from: naor@math.princeton.edu
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/1501.05213
or