# Some geometric applications of the discrete heat flow

Alexandros Eskenazis  CNRS, Institut de Mathématiques de Jussieu, Sorbonne
Université, France and Trinity College, University of Cambridge, UK.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We present two geometric applications of heat flow methods on the discrete
hypercube $\\{-1,1\\}^{n}$. First, we prove that if $X$ is a finite-
dimensional normed space, then the bi-Lipschitz distortion required to embed
$\\{-1,1\\}^{n}$ equipped with the Hamming metric into $X$ satisfies

$\mathsf{c}_{X}\big{(}\\{-1,1\\}^{n}\big{)}\gtrsim\sup_{p\in[1,2]}\frac{n}{\mathsf{T}_{p}(X)\min\\{n,\mathrm{dim}(X)\\}^{1/p}},$

where $\mathsf{T}_{p}(X)$ is the Rademacher type $p$ constant of $X$. This
estimate yields a mutual refinement of distortion lower bounds which follow
from works of Oleszkiewicz (1996) and Ivanisvili, van Handel and Volberg
(2020) for low-dimensional spaces $X$. The proof relies on an extension of an
important inequality of Pisier (1986) on the biased hypercube combined with an
application of the Borsuk–Ulam theorem from algebraic topology. Secondly, we
introduce a new metric invariant called metric stable type as a functional
inequality on the discrete hypercube and prove that it coincides with the
classical linear notion of stable type for normed spaces. We also show that
metric stable type yields bi-Lipschitz nonembeddability estimates for weighted
hypercubes.

2020 Mathematics Subject Classification. Primary: 46B85; Secondary: 30L15,
42C10, 46B07.

Key words. Hamming cube, Rademacher type, metric embeddings, Borsuk–Ulam
theorem, stable type.

##  1\. Introduction

Let $\\{-1,1\\}^{n}$ be the $n$-dimensional discrete hypercube equipped with
the Hamming metric

$\forall\
x,y\in\\{-1,1\\}^{n},\qquad\rho(x,y)=\frac{1}{2}\sum_{i=1}^{n}|x(i)-y(i)|,$
(1)

where $x=(x(1),\ldots,x(n))$ and $y=(y(1),\ldots,y(n))$. The purpose of the
present paper is to investigate certain metric properties of the Hamming cube
via heat flow methods.

###  1.1. Dimensionality of Hamming metrics

If $(\mathsf{M},d_{\mathsf{M}})$ is a metric space and $(Y,\|\cdot\|_{Y})$ is
a normed space, we say that $\mathsf{M}$ embeds into $Y$ with bi-Lipschitz
distortion at most $D\in[1,\infty)$, if there exists a mapping
$f:\mathsf{M}\to Y$ satisfying

$\forall\ p,q\in\mathsf{M},\qquad d_{\mathsf{M}}(p,q)\leq\|f(p)-f(q)\|_{Y}\leq
Dd_{\mathsf{M}}(p,q).$ (2)

The least $D\geq 1$ for which such an embedding exists will be denoted by
$\mathsf{c}_{Y}(\mathsf{M})$. The rapidly growing field of metric dimension
reduction aims to uncover conditions under which given families of metric
spaces admit (or do not admit) embeddings into low-dimensional normed spaces
with prescribed properties. Without attempting to survey this vast area, we
note that important contributions have been made on low-dimensional embeddings
of finite subsets of Hilbert space [29], arbitrary finite metric spaces [30,
3, 41, 42], discrete hypercubes [56, 34], diamond graphs [14, 35, 52], Laakso
graphs [24, 34], ultrametric spaces [8], series-parallel graphs [15],
recursive cycle graphs [1], Heisenberg-type metrics [32, 54], $\ell_{p}$
variants of thin Laakso structures [7, 9] and expander graphs [48, 50]. We
refer to the survey [49] for more bibliographic information and to [26, 38,
69, 2] for a sample of algorithmic applications.

The first to study the bi-Lipschitz embeddability of hypercubes into normed
spaces was Enflo. In the seminal work [20], he introduced the notion of
roundness of a metric space and used it to show that any embedding of the
Hamming cube $\\{-1,1\\}^{n}$ into an $L_{p}(\mu)$ space, where $p\in[1,2]$,
incurs bi-Lipschitz distortion at least $n^{1-1/p}$ (see also [19, 21] for
additional early results along these lines). More specifically, Enflo proved
that if $p\in[1,2]$, then any mapping of the form $f:\\{-1,1\\}^{n}\to
L_{p}(\mu)$ satisfies the estimate

$\int_{\\{-1,1\\}^{n}}\big{\|}f(x)-f(-x)\big{\|}_{L_{p}(\mu)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\leq\sum_{i=1}^{n}\int_{\\{-1,1\\}^{n}}\big{\|}f(x)-f\big{(}x(1),\ldots,-x(i),\ldots,x(n)\big{)}\big{\|}_{L_{p}(\mu)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x),$
(3)

where $\sigma_{n}$ is the uniform probability on $\\{-1,1\\}^{n}$. This
readily implies that if $f$ has bi-Lipschitz distortion $D$, then $D\geq
n^{1-1/p}$. In the follow-up work [21], he raised an influential problem by
asking for which normed spaces $(X,\|\cdot\|_{X})$, inequality (3) is
satisfied for $X$-valued functions $f$ up to a multiplicative constant $T$,
independent of the choice of $f$ or the dimension $n$. Restricting this
requirement to linear functions $f(x)=\sum_{i=1}^{n}x_{i}v_{i}$, one recovers
the necessary condition

$\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}x_{i}v_{i}\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\leq
T^{p}\sum_{i=1}^{n}\|v_{i}\|_{X}^{p},$ (4)

which must be satisfied for every $n\in\mathbb{N}$ and vectors
$v_{1},\ldots,v_{n}\in X$. If a normed space $X$ satisfies (4), we say that
$X$ has _Rademacher type_ $p$ and the least constant $T$ is denoted by
$\mathsf{T}_{p}(X)$. After decades of substantial efforts (see [13, 64, 53,
25, 22]), Ivanisvili, van Handel and Volberg resolved Enflo’s problem in the
breakthrough work [27] by proving the sufficiency of this condition, namely
that any normed space of Rademacher type $p$ also has Enflo’s nonlinear type
$p$. Consequently, any bi-Lipschitz embedding of $\\{-1,1\\}^{n}$ into a
normed space $X$ of Rademacher type $p$ incurs distortion at least a constant
multiple of $\mathsf{T}_{p}(X)^{-1}n^{1-1/p}$. We note in passing that,
conversely, a classical theorem of Pisier [57] implies that if $X$ does not
have type $p$ for any $p>1$, then $\\{-1,1\\}^{n}$ embeds into $X$ with bi-
Lipschitz distortion at most $1+\varepsilon$, for any $\varepsilon>0$.

Independently of this line of research, the beautiful (but perhaps overlooked)
work [56] of Oleszkiewicz established a nonembeddability result for discrete
hypercubes in the context of dimensionality reduction. Following Ball, Carlen
and Lieb [5], we say that a normed space is $p$-uniformly smooth, where
$p\in[1,2]$, if there exists a constant $S>0$ such that

$\forall\ x,y\in
X,\qquad\frac{\|x\|_{X}^{p}+\|y\|_{X}^{p}}{2}\leq\Big{\|}\frac{x+y}{2}\Big{\|}_{X}^{p}+S^{p}\Big{\|}\frac{x-y}{2}\Big{\|}_{X}^{p};$
(5)

the least such constant $S$ is denoted by $\mathsf{S}_{p}(X)$. A well-known
tensorization argument due to Pisier [60] shows that
$\mathsf{T}_{p}(X)\leq\mathsf{S}_{p}(X)$, yet there exist examples of normed
spaces $X$ for which $\mathsf{T}_{p}(X)<\infty$ whereas
$\mathsf{S}_{p}(X)=\infty$ for $p\in(1,2]$, see [61, 28, 65]. The main result
of Oleszkiewicz’s paper [56] asserts that the distortion required to embed
$\\{-1,1\\}^{n}$ into a finite-dimensional normed space $X$ satisfies

$\mathsf{c}_{X}\big{(}\\{-1,1\\}^{n}\big{)}\geq\sup_{p\in[1,2]}\frac{n}{\mathsf{S}_{p}(X)\min\\{n,\dim(X)\\}^{1/p}}$
(6)

(see also [6] for a precursor of this result for linear embeddings). This
substantially improves the bound
$\mathsf{c}_{X}(\\{-1,1\\}^{n})\gtrsim\sup_{p\in[1,2]}\mathsf{T}_{p}(X)^{-1}n^{1-1/p}$
which follows from [27], at least for spaces $X$ with $p$-smoothness constant
$\mathsf{S}_{p}(X)\asymp 1$ and dimension $\dim(X)<\\!\\!\\!<n$.

The first goal of the present paper is to revisit the technique used for
Oleszkiewicz’s nonembeddability theorem [56], in particular proving the
following mutual refinement of his result and of the recent work of
Ivanisvili, van Handel and Volberg [27].

######  Theorem 1.

Let $(X,\|\cdot\|_{X})$ be a finite-dimensional normed space. Then, for any
$n\geq 1$, we have

$\mathsf{c}_{X}\big{(}\\{-1,1\\}^{n}\big{)}\gtrsim\sup_{p\in[1,2]}\frac{n}{\mathsf{T}_{p}(X)\min\\{n,\dim(X)\\}^{1/p}}$
(7)

We emphasize that, in contrast to Oleszkiewicz’s bound (6), Theorem 1 captures
more accurately the nonembeddability of the hypercube into (finite-dimensional
subspaces of) normed spaces which have Rademacher type $p$ but are not
$r$-smooth for any $r\in(1,2]$, see [28, 65].

#### About the proof

Theorem 1 is proven by a combination of semigroup tools with a clever
topological trick of [56]. More specifically, let $f:\\{-1,1\\}^{n}\to X$ be a
function, where $X$ is a $d$-dimensional normed space and $d<n$. An
application of the Borsuk–Ulam theorem [43] for the unique multilinear
extension of $f$ implies that there exists a subset
$\sigma\subseteq\\{1,\ldots,n\\}$ with $|\sigma|=d$, a _product_ measure $\nu$
on $\\{-1,1\\}^{\sigma}$ and a point $w\in\\{-1,1\\}^{\sigma^{c}}$ such that

$\int_{\\{-1,1\\}^{\sigma}}f(x,w)\,\mathop{}\\!\mathrm{d}\nu(x)=\int_{\\{-1,1\\}^{\sigma}}f(-x,-w)\,\mathop{}\\!\mathrm{d}\nu(x).$
(8)

Then, a Poincaré inequality à la Enflo for the product measure $\nu$ (instead
of the uniform measure $\sigma_{d}$) on the $d$-dimensional subcubes
$\\{-1,1\\}^{\sigma}\times\\{w\\}$ and $\\{-1,1\\}^{\sigma}\times\\{-w\\}$
yields the distortion bounds of Theorem 1 (see Theorem 14 and also equation
(78) below).

In the case of $p$-uniformly smooth spaces, Oleszkiewicz [56] used (8) and a
bootstrap argument for the Lipschitz constant of $f$, based on the two-point
inequality (5), to obtain (6). In our case, the biased Poincaré inequality
which will yield (7) is an extension of an inequality for the uniform measure
that was proven in [27]. The key technical contribution of [27] was a novel
representation of the time derivative of the heat flow on $\\{-1,1\\}^{n}$.
Instead, we consider a Markov process having the product measure $\nu$ as
stationary measure (see Section 2) and prove a formula for the time derivative
of the corresponding semigroup (see Proposition 13) which extends the formula
of [27] (see also (47) below). Due to the fact that our product measure $\nu$
is no longer the stationary measure of the random walk on a group, the
resulting identity lacks some homogeneity properties that were used in [27],
but nevertheless it is sufficient for the proof of the biased Poincaré
inequality which is needed for our geometric application.

###  1.2. A Pisier–Talagrand inequality on the biased cube

For $\alpha\in(0,1)$ we denote by $\mu_{\alpha}$ the $\alpha$-biased
probability measure on $\\{-1,1\\}$ with $\mu_{\alpha}\\{1\\}=\alpha$ and
$\mu_{\alpha}\\{-1\\}=1-\alpha$. The proof of Theorem 1 yields as a
consequence the following extension and refinement of Pisier’s inequality
[64].

######  Theorem 2.

For every $p\in[1,\infty)$ and $\alpha\in(0,1)$, there exist
$\mathsf{K}_{p,\alpha},\mathsf{C}_{\alpha}\in(0,\infty)$ such that the
following holds. For any normed space $(X,\|\cdot\|_{X})$ and any
$n\in\mathbb{N}$, every function $f:\\{-1,1\\}^{n}\to X$ satisfies

$\begin{split}\bigg{\|}f-\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\mu_{\alpha}^{n}\bigg{\|}_{L_{p}(\log
L)^{p/2}(\mu_{\alpha}^{n};X)}\leq\mathsf{K}_{p,\alpha}&\left(\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}^{\alpha}f\Big{\|}_{L_{p}(\mu_{\alpha}^{n};X)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\right)^{1/p}\\\
&+\mathsf{C}_{\alpha}(\log
n+1)\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}^{\alpha}f\Big{\|}_{L_{1}(\mu_{\alpha}^{n};X)}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta).\end{split}$
(9)

If additionally $X$ is assumed to be of finite cotype, then there exists
$\mathsf{K}_{p,\alpha}(X)\in(0,\infty)$ such that

$\bigg{\|}f-\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\mu_{\alpha}^{n}\bigg{\|}_{L_{p}(\log
L)^{p/2}(\mu_{\alpha}^{n};X)}\leq\mathsf{K}_{p,\alpha}(X)\left(\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}^{\alpha}f\Big{\|}_{L_{p}(\mu_{\alpha}^{n};X)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\right)^{1/p}.$
(10)

The (standard) definitions of Orlicz norms, cotype and discrete derivatives
will be given at the main part of the article. Theorem 2 is an optimal vector-
valued version of a deep logarithmic Sobolev inequality of Talagrand [67]. In
the case of the uniform measure which corresponds to $\alpha=\tfrac{1}{2}$,
Theorem 2 was proven recently in [16].

###  1.3. Metric stable type

Besides its interest in the context of embedding theory, the work [27] of
Ivanisvili, van Handel and Volberg was a major contribution to a long-standing
research program in nonlinear functional analysis called the _Ribe program_.
Put simply, the foundational idea of the program (as put forth by Bourgain
[12], who was inspired by a landmark rigidity theorem of Ribe [66]) is that
isomorphic local properties of normed spaces can be equivalently reformulated
using only distances between pairs of points, with no reference to the spaces’
linear structure (see also [46, 4]). In this sense, the main result of [27]
completes the Ribe program for Rademacher type by proving that it is
equivalent to nonlinear Enflo type.

Among the various isomorphic properties studied in the local theory of normed
spaces, _stable type_ (see [58, 59]) plays a prominent role, in particular due
to its relation to the problem of identifying $\ell_{p}^{n}$ subspaces of
Banach spaces [63]. Recall that a symmetric random variable $\theta$ is
distributed according to the standard $p$-stable law, where $p\in(0,2]$, if it
satisfies $\mathbb{E}\exp(it\theta)=\exp(-|t|^{p})$ for every
$t\in\mathbb{R}$. A Banach space $(X,\|\cdot\|_{X})$ is said to have stable
type $p$ if for every $r<p$, every $n\in\mathbb{N}$ and every vectors
$v_{1},\ldots,v_{n}\in X$, we have

$\Big{(}\mathbb{E}\Big{\|}\sum_{i=1}^{n}\theta_{i}v_{i}\Big{\|}_{X}^{r}\Big{)}^{1/r}\leq\mathsf{C}_{p,r}(X)\Big{(}\sum_{i=1}^{n}\|v_{i}\|_{X}^{p}\Big{)}^{1/p},$
(11)

where the constant $\mathsf{C}_{p,r}(X)$ depends only on $p,r$ and $X$, but
not on $n$ or the choice of $v_{1},\ldots,v_{n}$, and
$\theta_{1},\theta_{2},\ldots$ are independent standard symmetric $p$-stable
random variables.

In the special case $p=2$, $p$-stable random variables are Gaussians and thus
stable type 2 coincides with Rademacher type 2. Moreover, any space with
stable type $p\in[1,2)$ also has Rademacher type $p$ but the converse does not
necessarily hold. In fact, early results of Maurey and Pisier in the theory of
type (see [58, Proposition 3] and [59, Théorème 1]), show that a normed space
$X$ has stable type $p\in[1,2)$ if and only if $X$ has Rademacher type
$p+\varepsilon$ for some $\varepsilon>0$. Therefore, formally, the Ribe
program for stable type $p\in[1,2)$ has been completed by [27]: a normed space
$X$ has stable type $p$ if and only if $X$ has Enflo type $p+\varepsilon$ for
some $\varepsilon>0$. In other words, stable type $p$ of a normed space $X$
can be characterized by the validity of some, a priori unknown, $X$-valued
Poincaré-type inequality from a given family.

To amend this, we shall introduce a new nonlinear invariant called _metric
stable type_ which is again a Poincaré-type inequality for functions defined
on the discrete hypercube and will serve as a metric characterization of
stable type for normed spaces. If $(\mathsf{M},d_{\mathsf{M}})$ is a metric
space and $f:\\{-1,1\\}^{n}\to\mathsf{M}$ is an $\mathsf{M}$-valued function,
we denote

$\forall\
x\in\\{-1,1\\}^{n},\qquad\mathfrak{d}_{i}f(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\tfrac{1}{2}d_{\mathsf{M}}\big{(}f(x),f\big{(}x(1),\ldots,-x(i),\ldots,x(n)\big{)}\big{)}.$
(12)

Moreover, we shall denote the weak $\ell_{p}$ norm on $\mathbb{R}^{n}$ by

$\forall\
w\in\mathbb{R}^{n},\qquad\|w\|_{\ell_{p,\infty}^{n}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sup_{r\geq
0}\big{\\{}r\cdot\\#\\{i:\ |w_{i}|\geq r\\}^{1/p}\big{\\}},$ (13)

where $\\#S$ denotes the cardinality of a finite set $S$.

######  Definition 3.

A metric space $(\mathsf{M},d_{\mathsf{M}})$ has metric stable type
$p\in(0,2)$ with constant $S\in(0,\infty)$ if for any $n\in\mathbb{N}$, every
function $f:\\{-1,1\\}^{n}\to\mathsf{M}$ satisfies

$\int_{\\{-1,1\\}^{n}}d_{\mathsf{M}}\big{(}f(x),f(-x)\big{)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\leq
S^{p}\int_{\\{-1,1\\}^{n}}\big{\|}\big{(}\mathfrak{d}_{1}f(x),\ldots,\mathfrak{d}_{n}f(x)\big{)}\big{\|}^{p}_{\ell_{p,\infty}^{n}}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x).$
(14)

Since $\|\cdot\|_{\ell_{p,\infty}^{n}}\leq\|\cdot\|_{\ell_{p}^{n}}$ by
Markov’s inequality, any space with metric stable type $p$ also has Enflo type
$p$ with the same constant. We shall prove the following metric
characterization.

######  Theorem 4.

A normed space $X$ has metric stable type $p\in[1,2)$ if and only if $X$ has
stable type $p$.

Pisier’s K-convexity theorem [62], asserts that a Banach space $X$ is K-convex
if and only if it has Rademacher type $p$ for some $p>1$. In view of the
aforementioned characterization of stable type [58, 59], this is equivalent to
$X$ having stable type 1 and thus we derive the following metric
characterization of $K$-convexity by a Poincaré inequality.

######  Corollary 5.

A normed space $X$ is K-convex if and only if $X$ has metric stable type $1$.

#### Embeddings

The fact that stable type of Banach spaces is a refinement of Rademacher type
can also be seen at the level of (linear) embeddings. Indeed, if $X$ is a
space of Rademacher type $p$, then standard considerations show that the
Banach–Mazur distance between $\ell_{1}^{n}$ and any $n$-dimensional subspace
of $X$ is at least a constant multiple of $n^{1-1/p}$. This estimate is sharp
for $X=\ell_{p}$. On the other hand, if $X$ has stable type $p$, then the
characterization of [58, 59] implies that $X$ has Rademacher type $r$ for some
$r>p$. Hence, there exists $\varepsilon(X)>0$ such that the Banach–Mazur
distance between $\ell_{1}^{n}$ and any $n$-dimensional subspace of $X$ is at
least $n^{1-1/p+\varepsilon(X)}$.

In the metric setting, Enflo type gives distortion lower bounds for embeddings
of $\\{-1,1\\}^{n}$. More generally, given a vector ${\bf
w}=(w_{1},\ldots,w_{n})\in\mathbb{R}_{+}^{n}$, consider the metric space
$\\{-1,1\\}^{n}_{{\bf w}}$ which is the hypercube $\\{-1,1\\}^{n}$ equipped
with the _weighted_ Hamming metric

$\forall\ x,y\in\\{-1,1\\}^{n},\qquad\rho_{{\bf
w}}(x,y)=\frac{1}{2}\sum_{i=1}^{n}w_{i}|x(i)-y(i)|.$ (15)

It follows readily from the definitions that if $\mathsf{M}$ has Enflo type
$p$, then any embedding of $\\{-1,1\\}^{n}_{{\bf w}}$ into $\mathsf{M}$ incurs
distortion at least a constant multiple of $\|{\bf w}\|_{\ell_{1}^{n}}/\|{\bf
w}\|_{\ell_{p}^{n}}$. For spaces of metric stable type $p$, we have the
following improvement for the distortion of weighted hypercubes.

######  Proposition 6.

If a metric space $(\mathsf{M},d_{\mathsf{M}})$ has metric stable type $p$
with constant $S$, then

$\forall\ {\bf
w}\in\mathbb{R}_{+}^{n},\qquad\mathsf{c}_{\mathsf{M}}\big{(}\\{-1,1\\}^{n}_{{\bf
w}}\big{)}\geq\frac{\|{\bf w}\|_{\ell_{1}^{n}}}{S\|{\bf
w}\|_{\ell_{p,\infty}^{n}}}.$ (16)

Concretely, choosing the weight vector ${\bf w}$ with $w_{i}=i^{-1/p}$, we
have that $\|{\bf w}\|_{\ell_{p,\infty}^{n}}\asymp 1$, whereas $\|{\bf
w}\|_{\ell_{p}^{n}}\asymp(\log n)^{1/p}$, therefore any embedding of
$\\{-1,1\\}^{n}_{{\bf w}}$ into a metric space of Enflo type $p$ incurs
distortion at least $n^{1-1/p}/(\log n)^{1/p}$ instead of the asymptotically
stronger lower bound $n^{1-1/p}$ which one gets for target spaces of metric
stable type $p$.

#### On the nonlinear Maurey–Pisier problem for type

A landmark theorem of Maurey and Pisier [44] asserts that if $p_{X}\in[1,2]$
is the supremal Rademacher type of an infinite-dimensional Banach space $X$,
then $X$ containts the spaces $\ell_{p_{X}}^{n}$ uniformly. In [63], Pisier
used stable type to give a much simpler proof of this important theorem, while
simultaneously obtaining the following quantitative refinement: for any
$\varepsilon>0$ and $p\in[1,2)$, every normed space $X$ containts a subspace
which is $(1+\varepsilon)$-isomorphic to $\ell_{p}^{d}$ provided that $d$ is
smaller than some explicit (unbounded) function of $\varepsilon$ and the
stable type $p$ constant of $X$. When $X$ is infinite-dimensional, this yields
the result of [44] since $X$ does not have stable type $p_{X}$ by the results
of [58, 59].

In [13], Bourgain, Milman and Wolfson introduced a notion of nonlinear type,
which is now referred to as BMW type, and showed that if a metric space
$\mathsf{M}$ does not have BMW type $p$ for any $p>1$, then
$\mathsf{c}_{\mathsf{M}}(\\{-1,1\\}^{n})=1$ for any $n\in\mathbb{N}$. Finding
a satisfactory nonlinear Maurey–Pisier theorem for metric spaces of supremal
nonlinear type $p>1$ remains an open problem (see also [47, Section 6]). It
would be interesting to understand whether the newly introduced notion of
metric stable type can lead to a nonlinear version of the result of [63]. We
refer to Section 6 for further remarks and open problems which naturally arise
from this work.

### Acknowledgements

I wish to thank Florent Baudier, Paata Ivanisvili and Assaf Naor for their
constructive feedback on this work.

##  2\. Preliminaries

###  2.1. Probability

In this section, we outline the basics of analysis on the biased hypercube,
with an emphasis on the underlying semigroup structure.

#### The biased measure

Recall that, for $\alpha\in(0,1)$, the $\alpha$-biased probability measure
$\mu_{\alpha}$ on $\\{-1,1\\}$ is given by $\mu_{\alpha}\\{1\\}=\alpha$ and
$\mu_{\alpha}\\{-1\\}=1-\alpha$. Moreover, if
$\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{n})\in(0,1)^{n}$, then we
shall denote by $\mu_{\boldsymbol{\alpha}}$ the product measure
$\mu_{\alpha_{1}}\otimes\cdots\otimes\mu_{\alpha_{n}}$ on the hypercube
$\\{-1,1\\}^{n}$.

#### The Markov process

For $\alpha\in(0,1)$, consider the transition matrices
$\\{p_{t}^{\alpha}\\}_{t\geq 0}$ on $\\{-1,1\\}$ given by

$\forall\ t\geq
0,\qquad\begin{pmatrix}p_{t}^{\alpha}(1,1)&p_{t}^{\alpha}(1,-1)\\\
p_{t}^{\alpha}(-1,1)&p_{t}^{\alpha}(-1,-1)\end{pmatrix}=\begin{pmatrix}1-(1-e^{-t})(1-\alpha)&(1-e^{-t})(1-\alpha)\\\
(1-e^{-t})\alpha&1-(1-e^{-t})\alpha\end{pmatrix}$ (17)

Moreover, for $\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{n})\in(0,1)^{n}$
consider the corresponding tensor products
$\\{p_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$ on $\\{-1,1\\}^{n}$ given by

$\forall\ x,y\in\\{-1,1\\}^{n},\qquad
p_{t}^{\boldsymbol{\alpha}}(x,y)=\prod_{i=1}^{n}p_{t}^{\alpha_{i}}\big{(}x(i),y(i)\big{)}.$
(18)

As each $p_{t}^{\alpha_{i}}$ is a row-stochastic $2\times 2$ matrix with
nonnegative entries, the same holds also for the $2^{n}\times 2^{n}$ matrices
$p_{t}^{\boldsymbol{\alpha}}$. Therefore,
$\\{p_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$ is the transition kernel of a
time-homogeneous Markov chain $\\{X_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$ on
$\\{-1,1\\}^{n}$, that is

$\forall\ t,s\geq 0,\qquad\mathbb{P}\big{\\{}X_{t+s}^{\boldsymbol{\alpha}}=y\
\big{|}\
X_{s}^{\boldsymbol{\alpha}}=x\big{\\}}=p_{t}^{\boldsymbol{\alpha}}(x,y),$ (19)

where $x,y\in\\{-1,1\\}^{n}$. We shall need the following simple facts for
this process.

######  Lemma 7.

Fix $\boldsymbol{\alpha}\in(0,1)^{n}$ and let
$\\{X_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$ be a Markov process on
$\\{-1,1\\}^{n}$ with transition kernels
$\\{p_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$. Then,
$\\{X_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$ is stationary and reversible
with respect to $\mu_{\boldsymbol{\alpha}}$.

###### Proof.

Due to the product structure of the Markov chain, it suffices to consider the
case $n=1$, that is, to prove that for $\alpha\in(0,1)$,

$\forall\
x,y\in\\{-1,1\\},\qquad\mu_{\alpha}(x)p_{t}^{\alpha}(x,y)=\mu_{\alpha}(y)p_{t}^{\alpha}(y,x).$
(20)

This follows automatically by the expression (17) for the transition matrix.
The simple fact that reversibility implies stationarity is well-known [37,
Proposition 1.20]. ∎

The stationary Markov process $\\{X_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$
has a simple probabilistic interpretation which we shall now describe. For
$i=1,\ldots,n$, let $\\{N_{t}(i)\\}_{t\geq 0}$ be $n$ independent Poisson
processes of unit rate and suppose that $X_{0}^{\boldsymbol{\alpha}}$ is
sampled from $\mu_{\boldsymbol{\alpha}}$ independently of $\\{N_{t}\\}_{t\geq
0}$. Then, at any time $t>0$ for which the process $N_{t}(i)$ jumps for some
$i\in\\{1,\ldots,n\\}$, the corresponding value
$X_{t}^{\boldsymbol{\alpha}}(i)$ is updated independently from
$\mu_{\alpha_{i}}$. An explicit calculation shows that this probabilistic
construction gives rise exactly to the transition kernel of (17) and (18).

#### The corresponding semigroup

Fix $\boldsymbol{\alpha}\in(0,1)^{n}$ and let
$\\{P_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$ be the Markov semigroup
associated to the process $\\{X_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$.
Concretely, if $X$ is a vector space, then for every function
$f:\\{-1,1\\}^{n}\to X$ and $t\geq 0$, we denote by

$\forall\ x\in\\{-1,1\\}^{n},\qquad
P_{t}^{\boldsymbol{\alpha}}f(x)=\mathbb{E}\big{[}f\big{(}X_{t}^{\boldsymbol{\alpha}}\big{)}\
\big{|}\ X_{0}^{\boldsymbol{\alpha}}=x\big{]}.$ (21)

In view of the above interpretation of
$\\{X_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$ by means of a Poisson process,
the action of the semigroup $\\{P_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$ can
be computed via the identity

$\begin{split}P_{t}^{\boldsymbol{\alpha}}f&=\sum_{S\subseteq\\{1,\ldots,n\\}}\mathbb{P}\big{\\{}N_{t}(i)>0\
\mbox{for }i\in S\mbox{ and }N_{t}(i)=0\mbox{ for }i\notin
S\big{\\}}\int_{\\{-1,1\\}^{S}}f\,\mathop{}\\!\mathrm{d}\prod_{i\in
S}\mu_{\alpha_{i}}\\\
&=\sum_{S\subseteq\\{1,\ldots,n\\}}(1-e^{-t})^{|S|}e^{-t(n-|S|)}\int_{\\{-1,1\\}^{S}}f\,\mathop{}\\!\mathrm{d}\prod_{i\in
S}\mu_{\alpha_{i}}.\end{split}$ (22)

######  Lemma 8.

Fix $\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{n})\in(0,1)^{n}$ and let
$\\{P_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$ be the semigroup (21). Then, the
action of its generator $\mathscr{L}_{\boldsymbol{\alpha}}$ on a function
$f:\\{-1,1\\}^{n}\to X$, where $X$ is a vector space, is given by

$\forall\
x\in\\{-1,1\\}^{n},\qquad\mathscr{L}_{\boldsymbol{\alpha}}f(x)=-\sum_{i=1}^{n}\partial_{i}^{\alpha_{i}}f(x)$
(23)

where
$\partial_{i}^{\beta}f(x)=f(x)-\int_{\\{-1,1\\}}f(x_{1},\ldots,x_{i-1},y,x_{i+1},\ldots,x_{n})\,\mathop{}\\!\mathrm{d}\mu_{\beta}(y)$
for $\beta\in(0,1)$.

###### Proof.

The claim follows from the expression (22) of the semigroup and the definition

$\forall\
x\in\\{-1,1\\}^{n},\qquad\mathscr{L}_{\boldsymbol{\alpha}}f(x)=\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}t}\Big{|}_{t=0}P_{t}^{\boldsymbol{\alpha}}f(x).\qed$

###  2.2. Topology

Apart from the probabilistic elements from analysis on biased hypercubes, the
proof of Theorem 1 also has a crucial topological component, following an idea
of [56].

#### The Borsuk–Ulam theorem

While the Poincaré-type inequality of Enflo for $X$-valued functions on
$\\{-1,1\\}^{n}$ cannot capture the dimension of the target space $X$, a key
part of the argument towards Theorem 1 is to show that there exists a
$\dim(X)$-dimensional subcube of $\\{-1,1\\}^{n}$ along with a bias vector
$\boldsymbol{\alpha}$ for which the $\boldsymbol{\alpha}$-biased Poincaré
inequalities (see Theorem 14 below) on this subcube and its antipodal yield
much better distortion lower bounds. This will be proven using the Borsuk–Ulam
theorem from algebraic topology, see [43].

######  Theorem 9 (Borsuk–Ulam).

For every continuous function $g:\mathbb{S}^{d}\to\mathbb{R}^{d}$, where
$d\in\mathbb{N}$, there exists a point $w\in\mathbb{S}^{d}$ such that
$g(w)=g(-w)$.

#### Multilinear extension and low-dimensional faces of the cube

Every function $f:\\{-1,1\\}^{n}\to X$ admits a unique multilinear extension
on the solid cube $[-1,1]^{n}$, given by

$\forall\ y\in[-1,1]^{n},\qquad
F(y)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{S\subseteq\\{-1,1\\}^{n}}\Big{(}\frac{1}{2^{n}}\sum_{x\in\\{-1,1\\}^{n}}f(x)w_{S}(x)\Big{)}w_{S}(y),$
(24)

where $w_{S}(a)=\prod_{i\in S}a_{i}$, which is usually referred to as the
Fourier–Walsh expansion of $f$. Extending $f$ to the continuous cube allows
for the use of topological methods. In what follows, we will exploit the fact
that the cube $[-1,1]^{n}$ is equipped with a canonical CW complex structure.
Concretely, for $d\in\\{1,\ldots,n\\}$, consider the subsets

$\mathscr{C}_{d}^{n}=\big{\\{}x\in[-1,1]^{n}:\ \mbox{there exists
}\sigma\subseteq\\{1,\ldots,n\\}\mbox{ with }|\sigma|\geq n-d\mbox{ and
}|x(i)|=1,\ \forall\ i\in\sigma\big{\\}}$ (25)

consisting of all $\ell$-dimensional faces of $[-1,1]^{n}$ for $\ell\leq d$,
so that $\mathscr{C}_{n}^{n}=[-1,1]^{n}$ and
$\mathscr{C}_{0}^{n}=\\{-1,1\\}^{n}$. We shall use the following elementary
topological fact (see [56, Lemma 1]).

######  Lemma 10.

If $d<n$, there exists a continuous map
$h_{d}:\mathbb{S}^{d}\to\mathscr{C}_{d}^{n}$ with $h_{d}(-x)=-h_{d}(x)$,
$\forall\ x\in\mathbb{S}^{d}$.

Combining this and the Borsuk–Ulam theorem, we deduce the following useful
lemma.

######  Lemma 11.

If $n,d\in\mathbb{N}$ with $d<n$, then for every continuous function
$F:\mathscr{C}_{d}^{n}\to\mathbb{R}^{d}$ there exists a point
$z\in\mathscr{C}_{d}^{n}$ such that F(z)=F(-z).

###### Proof.

Consider the function $g\stackrel{{\scriptstyle\mathrm{def}}}{{=}}F\circ
h_{d}:\mathbb{S}^{d}\to\mathbb{R}^{d}$, where $h_{d}$ is the function of Lemma
10. By the Borsuk–Ulam theorem and the oddness of $h_{d}$, there exists a
point $w\in\mathbb{S}^{d}$ such that

$F(h_{d}(w))=g(w)=g(-w)=F(h_{d}(-w))=F(-h_{d}(w))$ (26)

and the conclusion follows by choosing $z=h_{d}(w)\in\mathscr{C}_{d}^{n}$. ∎

##  3\. Proof of Theorem 1

We are now ready to proceed to the main part of the proof. The main analytic
component is a biased version of the key formula of [27] for the time
derivative of the heat flow on $\\{-1,1\\}^{n}$. Given $t\geq 0$,
$\alpha\in(0,1)$ and an auxiliary parameter $\theta\in\mathbb{R}$, consider
the matrix $\eta_{t}^{\alpha}(\cdot,\cdot;\theta)$ given by

$\forall\ t\geq
0,\qquad\begin{pmatrix}\eta_{t}^{\alpha}(1,1;\theta)&\eta_{t}^{\alpha}(1,-1;\theta)\\\
\eta_{t}^{\alpha}(-1,1;\theta)&\eta_{t}^{\alpha}(-1,-1;\theta)\end{pmatrix}=\begin{pmatrix}\frac{e^{-t}-\theta}{p_{t}^{\alpha}(1,1)}&\frac{-\theta}{p_{t}^{\alpha}(-1,1)}\\\
\frac{\theta-e^{-t}}{p_{t}^{\alpha}(1,-1)}&\frac{\theta}{p_{t}^{\alpha}(-1,-1)}\end{pmatrix}.$
(27)

For future reference, we record the following straightforward properties of
$\eta_{t}^{\alpha}(\cdot,\cdot;\theta)$.

######  Lemma 12.

Fix $t\geq 0$ and $\alpha\in(0,1)$. Then,

$\forall\ x\in\\{-1,1\\},\ \theta\in\mathbb{R},\qquad
p_{t}^{\alpha}(x,1)\eta_{t}^{\alpha}(1,x;\theta)+p_{t}^{\alpha}(x,-1)\eta_{t}^{\alpha}(-1,x;\theta)=0$
(28)

and

$\begin{split}\min_{\theta\in\mathbb{R}}\max_{x\in\\{-1,1\\}}\Big{\\{}p_{t}^{\alpha}(x,1)\eta_{t}^{\alpha}(1,x;\theta)^{2}&+p_{t}^{\alpha}(x,-1)\eta_{t}^{\alpha}(-1,x;\theta)^{2}\Big{\\}}\\\
&=\frac{e^{-t}}{(e^{t}-1)(\sqrt{\alpha
p_{t}^{\alpha}(-1,-1)}+\sqrt{(1-\alpha)p_{t}^{\alpha}(1,1)})^{2}}\leq\frac{1}{e^{t}-1}.\end{split}$
(29)

###### Proof.

The centering condition (28) can be checked easily using the explicit formulas
(17) and (27) of the matrices. For (29), we compute that for any
$\theta\in\mathbb{R}$,

$\begin{split}\max_{x\in\\{-1,1\\}}\Big{\\{}p_{t}^{\alpha}(x,1)\eta_{t}^{\alpha}(1,x;\theta)^{2}&+p_{t}^{\alpha}(x,-1)\eta_{t}^{\alpha}(-1,x;\theta)^{2}\Big{\\}}\\\
&=\max\Big{\\{}\frac{(e^{-t}-\theta)^{2}}{p_{t}^{\alpha}(1,1)p_{t}^{\alpha}(1,-1)},\frac{\theta^{2}}{p_{t}^{\alpha}(-1,1)p_{t}^{\alpha}(-1,-1)},\Big{\\}}.\end{split}$
(30)

As this is the maximum of two quadratic functions in $\theta$, its minimum is
attained at the point $\theta^{\ast}$ where they intersect in the interval
$(0,e^{-t})$, namely at

$\theta^{\ast}=\frac{e^{-t}\sqrt{\alpha p_{t}^{\alpha}(-1,-1)}}{\sqrt{\alpha
p_{t}^{\alpha}(-1,-1)}+\sqrt{(1-\alpha)p_{t}^{\alpha}(1,1)}}.$ (31)

The first equality in (29) is immediate, whereas for the inequality we compute

$\begin{split}\frac{e^{-t}}{(e^{t}-1)(\sqrt{\alpha
p_{t}^{\alpha}(-1,-1)}+\sqrt{(1-\alpha)p_{t}^{\alpha}(1,1)})^{2}}&\leq\frac{e^{-t}}{(e^{t}-1)(\alpha
p_{t}^{\alpha}(-1,-1)+(1-\alpha)p_{t}^{\alpha}(1,1))}\\\
&=\frac{e^{-t}}{(e^{t}-1)\big{(}1-(1-e^{-t})(\alpha^{2}+(1-\alpha)^{2})\big{)}}\leq\frac{1}{e^{t}-1},\end{split}$
(32)

where both inequalities follow from the convexity of $x\mapsto x^{2}$. ∎

The key technical ingredient in the proof of Theorem 1 is the following
identity.

######  Proposition 13.

Fix $n\in\mathbb{N}$,
$\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{n})\in(0,1)^{n}$, $t\geq 0$
and $\theta_{1},\ldots,\theta_{n}\in\mathbb{R}$. Then, for every function
$f:\\{-1,1\\}^{n}\to X$, where $X$ is a vector space, we have

$\forall\
x\in\\{-1,1\\}^{n},\qquad\mathscr{L}_{\boldsymbol{\alpha}}P_{t}^{\boldsymbol{\alpha}}f(x)=-\mathbb{E}\Big{[}\sum_{i=1}^{n}\eta_{t}^{\alpha_{i}}\big{(}x(i),X_{t}^{\boldsymbol{\alpha}}(i);\theta_{i}\big{)}\partial_{i}^{\alpha_{i}}f(X_{t}^{\boldsymbol{\alpha}})\
\Big{|}\ X_{0}^{\boldsymbol{\alpha}}=x\Big{]}.$ (33)

###### Proof.

In view of (23) and the product structure of the process
$\\{X_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$, it suffices to check the claim
for $n=1$, namely that for every $\beta\in(0,1)$, $\theta\in\mathbb{R}$ and
$f:\\{-1,1\\}\to X$,

$\forall\ x\in\\{-1,1\\},\qquad
e^{-t}\partial^{\beta}f(x)=P_{t}^{\beta}\partial^{\beta}f(x)=\mathbb{E}\big{[}\eta_{t}^{\beta}(x,X_{t}^{\beta};\theta)\partial^{\beta}f(X_{t}^{\beta})\
\big{|}\ X_{0}^{\beta}=x\big{]},$ (34)

where the first equality follows from the probabilistic representation (22).
Taking into account that
$\beta\partial^{\beta}f(1)+(1-\beta)\partial^{\beta}f(-1)=0$, this amounts to
the system of equations

$\begin{cases}e^{-t}=p_{t}^{\beta}(1,1)\eta_{t}^{\beta}(1,1;\theta)-\frac{\beta}{1-\beta}p_{t}^{\beta}(1,-1)\eta_{t}^{\beta}(1,-1;\theta)\\\
e^{-t}=-\frac{1-\beta}{\beta}p_{t}^{\beta}(-1,1)\eta_{t}^{\beta}(-1,1;\theta)+p_{t}^{\beta}(-1,-1)\eta_{t}^{\beta}(-1,-1;\theta)\end{cases}$
(35)

which can be easily verified by direct computation. ∎

######  Theorem 14.

Fix $p\in[1,2]$ and let $(X,\|\cdot\|_{X})$ be a normed space of Rademacher
type $p$. Then, for any $n\in\mathbb{N}$ and
$\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{n})\in(0,1)^{n}$, every
function $f:\\{-1,1\\}^{n}\to X$ satisfies

$\int_{\\{-1,1\\}^{n}}\Big{\|}f(x)-\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\leq\big{(}2\pi\mathsf{T}_{p}(X)\big{)}^{p}\sum_{i=1}^{n}\int_{\\{-1,1\\}^{n}}\big{\|}\partial_{i}^{\alpha_{i}}f(x)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x).$
(36)

###### Proof.

Writing

$f(x)-\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}=P_{0}^{\boldsymbol{\alpha}}f(x)-P_{\infty}^{\boldsymbol{\alpha}}f(x)=-\int_{0}^{\infty}\mathscr{L}_{\boldsymbol{\alpha}}P_{t}^{\boldsymbol{\alpha}}f(x)\,\mathop{}\\!\mathrm{d}t$
(37)

and using Jensen’s inequality and Proposition 13, we see that for
$\theta_{1}(t),\ldots,\theta_{n}(t)\in\mathbb{R}$,

$\begin{split}\Bigg{(}\int_{\\{-1,1\\}^{n}}\Big{\|}&f(x)-\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\Bigg{)}^{1/p}\leq\int_{0}^{\infty}\Bigg{(}\int_{\\{-1,1\\}^{n}}\Big{\|}\mathscr{L}_{\boldsymbol{\alpha}}P_{t}^{\boldsymbol{\alpha}}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\Bigg{)}^{1/p}\,\mathop{}\\!\mathrm{d}t\\\
&=\int_{0}^{\infty}\Bigg{(}\int_{\\{-1,1\\}^{n}}\Bigg{\|}\mathbb{E}\Big{[}\sum_{i=1}^{n}\eta_{t}^{\alpha_{i}}\big{(}x(i),X_{t}^{\boldsymbol{\alpha}}(i);\theta_{i}(t)\big{)}\partial_{i}^{\alpha_{i}}f(X_{t}^{\boldsymbol{\alpha}})\
\Big{|}\
X_{0}^{\boldsymbol{\alpha}}=x\Big{]}\Bigg{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\Bigg{)}^{1/p}\,\mathop{}\\!\mathrm{d}t\\\
&\leq\int_{0}^{\infty}\Bigg{(}\mathbb{E}\Big{\|}\sum_{i=1}^{n}\eta_{t}^{\alpha_{i}}\big{(}X_{0}^{\boldsymbol{\alpha}}(i),X_{t}^{\boldsymbol{\alpha}}(i);\theta_{i}(t)\big{)}\partial_{i}^{\alpha_{i}}f(X_{t}^{\boldsymbol{\alpha}})\Big{\|}_{X}^{p}\Bigg{)}^{1/p}\,\mathop{}\\!\mathrm{d}t,\end{split}$
(38)

where in the last expectation $X_{0}^{\boldsymbol{\alpha}}$ is distributed
according to $\mu_{\boldsymbol{\alpha}}$. Now, by the reversibility of the
chain, this expectation can be written as

$\begin{split}\mathbb{E}\Big{\|}\sum_{i=1}^{n}\eta_{t}^{\alpha_{i}}\big{(}X_{0}^{\boldsymbol{\alpha}}(i),X_{t}^{\boldsymbol{\alpha}}(i);&\theta_{i}(t)\big{)}\partial_{i}^{\alpha_{i}}f(X_{t}^{\boldsymbol{\alpha}})\Big{\|}_{X}^{p}\\\
&=\int_{\\{-1,1\\}^{n}}\sum_{y\in\\{-1,1\\}^{n}}p_{t}^{\boldsymbol{\alpha}}(x,y)\Big{\|}\sum_{i=1}^{n}\eta_{t}^{\alpha_{i}}\big{(}y(i),x(i);\theta_{i}(t)\big{)}\partial_{i}^{\alpha_{i}}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x).\end{split}$
(39)

Fixing $x\in\\{-1,1\\}^{n}$, equation (28) asserts that each
$\eta_{t}^{\alpha_{i}}(y(i),x(i);\theta_{i}(t))$ is a centered random variable
when $y(i)$ is distributed according to $p_{t}^{\alpha_{i}}(x(i),\cdot)$.
Therefore, as $p_{t}^{\boldsymbol{\alpha}}(x,\cdot)$ is a product measure, the
Rademacher type condition for sums of centered independent random vectors (see
[33, Proposition 9.11]) yields the bound

$\begin{split}&\int_{\\{-1,1\\}^{n}}\sum_{y\in\\{-1,1\\}^{n}}p_{t}^{\boldsymbol{\alpha}}(x,y)\Big{\|}\sum_{i=1}^{n}\eta_{t}^{\alpha_{i}}\big{(}y(i),x(i);\theta_{i}(t)\big{)}\partial_{i}^{\alpha_{i}}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\\\
&\leq\big{(}2\mathsf{T}_{p}(X)\big{)}^{p}\int_{\\{-1,1\\}^{n}}\sum_{i=1}^{n}\sum_{y(i)\in\\{-1,1\\}}p_{t}^{\alpha_{i}}\big{(}x(i),y(i)\big{)}\
\big{|}\eta_{t}^{\alpha_{i}}\big{(}y(i),x(i);\theta_{i}(t)\big{)}\big{|}^{p}\big{\|}\partial_{i}^{\alpha_{i}}f(x)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\\\
&\leq\big{(}2\mathsf{T}_{p}(X)\big{)}^{p}\sum_{i=1}^{n}\int_{\\{-1,1\\}^{n}}\Big{(}\sum_{y(i)\in\\{-1,1\\}}p_{t}^{\alpha_{i}}\big{(}x(i),y(i)\big{)}\
\big{|}\eta_{t}^{\alpha_{i}}\big{(}y(i),x(i);\theta_{i}(t)\big{)}\big{|}^{2}\Big{)}^{p/2}\big{\|}\partial_{i}^{\alpha_{i}}f(x)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x),\end{split}$
(40)

where we also used that $p\leq 2$. Now, choosing the $\theta_{i}(t)$ which
minimize the quantity in the left-hand side of (29) with bias $\alpha_{i}$,
and combining (38), (39) and (40), we conclude that

$\begin{split}\Bigg{(}\int_{\\{-1,1\\}^{n}}\Big{\|}f(x)-&\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\Bigg{)}^{1/p}\\\
&\leq
2\mathsf{T}_{p}(X)\int_{0}^{\infty}\Bigg{(}\sum_{i=1}^{n}\int_{\\{-1,1\\}^{n}}\big{\|}\partial_{i}^{\alpha_{i}}f(x)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\Bigg{)}^{1/p}\,\frac{\mathop{}\\!\mathrm{d}t}{\sqrt{e^{t}-1}},\end{split}$
(41)

which is precisely the desired estimate. ∎

Equipped with the biased Poincaré inequality of Theorem 14, we can conclude
the proof.

###### Proof of Theorem 1.

Let $X=(\mathbb{R}^{d},\|\cdot\|_{X})$ be a $d$-dimensional normed space and
suppose that $f:\\{-1,1\\}^{n}\to X$ is a function such that

$\forall\ x,y\in\\{-1,1\\}^{n},\qquad\rho(x,y)\leq\|f(x)-f(y)\|_{X}\leq
D\rho(x,y)$ (42)

for some $D\geq 1$. The conclusion of the theorem follows from [27] when
$d\geq n$ so we shall assume that $d<n$. Let $F:[-1,1]^{n}\to X$ be the
multilinear extension of $f$ given by (24). Then, $F$ is clearly continuous as
a polynomial and therefore, by Lemma 11, there exists a point
$z\in\mathscr{C}_{d}^{n}$ such that $F(z)=F(-z)$. As $z$ has at least $n-d$
coordinates equal to 1 in absolute value we shall assume without loss of
generality that $|z({d+1})|=\ldots=|z(n)|=1$ and consider the functions
$h_{+},h_{-}:\\{-1,1\\}^{d}\to X$ which are defined as

$\forall\ x\in\\{-1,1\\}^{d},\qquad h_{\pm}(x)=f\big{(}\pm x(1),\ldots,\pm
x(d),\pm z(d+1),\ldots,\pm z(n)\big{)}.$ (43)

Consider also the bias vector
$\boldsymbol{\alpha}_{z}=\big{(}\frac{1+z(1)}{2},\ldots,\frac{1+z(d)}{2}\big{)}\in(0,1)^{d}$
and notice that, by the multilinearity of $F$, we have the identity

$\int_{\\{-1,1\\}^{d}}h_{+}(x)\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}_{z}}(x)=F(z)=F(-z)=\int_{\\{-1,1\\}^{d}}h_{-}(x)\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}_{z}}(x).$
(44)

Therefore, by the triangle inequality and Theorem 14 we get

$\begin{split}\int_{\\{-1,1\\}^{d}}\big{\|}h_{+}(x)&-h_{-}(x)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}_{z}}(x)\\\
&\leq
2^{p-1}\int_{\\{-1,1\\}^{d}}\big{\|}h_{+}(x)-F(z)\big{\|}_{X}^{p}+\big{\|}h_{-}(x)-F(-z)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}_{z}}(x)\\\
&\leq
2^{2p-1}\big{(}\pi\mathsf{T}_{p}(X)\big{)}^{p}\sum_{i=1}^{d}\int_{\\{-1,1\\}^{d}}\big{\|}\partial_{i}^{\frac{1+z(i)}{2}}h_{+}(x)\big{\|}_{X}^{p}+\big{\|}\partial_{i}^{\frac{1+z(i)}{2}}h_{-}(x)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}_{z}}(x).\end{split}$
(45)

Now, in view of the lower Lipschitz condition (42), we clearly have

$\big{\|}h_{+}(x)-h_{-}(x)\big{\|}_{X}=\big{\|}f\big{(}x(1),\ldots,x(d),z(d+1),\ldots,z(n)\big{)}-f\big{(}-x(1),\ldots,-x(d),-z(d+1),\ldots,-z(n)\big{)}\big{\|}_{X}\geq
n$

for every $x\in\\{-1,1\\}^{d}$. On the other hand, for a fixed
$i\in\\{1,\ldots,d\\}$ and $\beta=\frac{1+z(i)}{2}$, we have

$\begin{split}\int_{\\{-1,1\\}}\big{\|}\partial_{i}^{\beta}&h_{+}(x)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\beta}(x(i))=\beta\|\partial_{i}^{\beta}h_{+}(x(1),\ldots,1,\ldots,x(d))\|_{X}^{p}+(1-\beta)\|\partial_{i}^{\beta}h_{+}(x(1),\ldots,-1,\ldots,x(d))\|_{X}^{p}\\\
&=\big{(}\beta(1-\beta)^{p}+(1-\beta)\beta^{p}\big{)}\
\big{\|}h_{+}(x(1),\ldots,1,\ldots,x(d))-h_{+}(x(1),\ldots,-1,\ldots,x(d))\big{\|}_{X}^{p}\leq\frac{D^{p}}{2^{p}},\end{split}$

where in the last equality we used that $p\leq 2$ along with the upper
Lipschitz condition (42). The same bound also holds for $h_{-}$. Integrating
the last two inequalities and combining them with (45), we deduce that

$n^{p}\leq(2\pi\mathsf{T}_{p}(X))^{p}dD^{p},$ (46)

which completes the proof of the theorem. ∎

######  Remark 15.

The identity of Proposition 13 in the case of the uniform measure $\sigma_{n}$
(which was obtained in [27]) is simpler. Let $\xi_{1}(t),\ldots,\xi_{n}(t)$ be
i.i.d. random variables distributed according to $\mu_{\beta(t)}$, where
$\beta(t)=\frac{1+e^{-t}}{2}$. Then, for any point $x\in\\{-1,1\\}^{n}$, the
corresponding unbiased process $\\{X_{t}(i)\\}_{t\geq 0}$ with $X_{0}=x$ has
distribution equal to $x(i)\xi_{i}(t)$ at time $t$. Thus applying formula (33)
with $\alpha_{i}=\frac{1}{2}$ and $\theta_{i}(t)=\tfrac{e^{-t}}{2}$, we
recover the usual identity

$\forall\
x\in\\{-1,1\\}^{n},\qquad\mathscr{L}P_{t}f(x)=-\mathbb{E}\Big{[}\sum_{i=1}^{n}\frac{\xi_{i}(t)-e^{-t}}{e^{t}-e^{-t}}\cdot\partial_{i}f\big{(}x\xi(t)\big{)}\Big{]},$
(47)

where $x\xi(t)=(x(1)\xi_{1}(t),\ldots,x(n)\xi_{n}(t))$, as was proven in [27].

##  4\. Proof of Theorem 2

Recall that a normed space $(X,\|\cdot\|_{X})$ has cotype $q\in[2,\infty)$
with constant $C\in(0,\infty)$ if for every $n\in\mathbb{N}$ and
$v_{1},\ldots,v_{n}\in X$, we have

$\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}x_{i}v_{i}\Big{\|}_{X}^{q}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\geq\frac{1}{C^{q}}\sum_{i=1}^{n}\|v_{i}\|_{X}^{q}.$
(48)

We say that $X$ has finite cotype if it has cotype $q$ for some
$q\in[2,\infty)$.

The proof of Theorem 2 is similar to the arguments of [27, 16] using as input
the new identity (33) for the time derivative of the biased semigroup
$\\{P_{t}^{\boldsymbol{\alpha}}\\}_{t\geq 0}$. In view of that, we shall omit
various simple details and we will be less attentive with the values of the
implicit constants.

We start by proving the (weaker) biased Pisier inequality, in which the Orlicz
norm on the left hand side of the conclusions of Theorem 2 is replaced by an
$L_{p}$ norm.

######  Theorem 16.

For every $\alpha\in(0,1)$, there exists $\mathsf{K}_{\alpha}\in(0,\infty)$
such that the following holds when $p\in[1,\infty)$. For any normed space
$(X,\|\cdot\|_{X})$ and any $n\in\mathbb{N}$, every function
$f:\\{-1,1\\}^{n}\to X$ satisfies

$\bigg{\|}f-\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\mu_{\alpha}^{n}\bigg{\|}_{L_{p}(\mu_{\alpha}^{n};X)}\leq\mathsf{K}_{\alpha}(\log
n+1)\left(\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}^{\alpha}f\Big{\|}_{L_{p}(\mu_{\alpha}^{n};X)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\right)^{1/p}.$
(49)

If additionally $X$ is assumed to be of finite cotype, then there exists
$\mathsf{K}_{p,\alpha}(X)$ such that

$\bigg{\|}f-\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\mu_{\alpha}^{n}\bigg{\|}_{L_{p}(\mu_{\alpha}^{n};X)}\leq\mathsf{K}_{p,\alpha}(X)\left(\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}^{\alpha}f\Big{\|}_{L_{p}(\mu_{\alpha}^{n};X)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\right)^{1/p}.$
(50)

###### Proof.

Let $\boldsymbol{\alpha}=(\alpha,\ldots,\alpha)$ and without loss of
generality assume that $\int
f\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}=0$. We start by proving the
general inequality (49). Notice that, by convexity,

$\big{\|}\mathscr{L}_{\boldsymbol{\alpha}}f\big{\|}_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}\stackrel{{\scriptstyle\eqref{eq:gen}}}{{\leq}}\sum_{i=1}^{n}\big{\|}\partial_{i}^{\alpha}f\big{\|}_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}\leq
2n\|f\|_{L_{p}(\mu_{\boldsymbol{\alpha}};X)},$ (51)

where the last inequality follows from the definitions of
$\partial_{i}^{\alpha}$. Therefore,

$\begin{split}\forall\ t\geq
0,\qquad\big{\|}e^{-t\mathscr{L}_{\boldsymbol{\alpha}}}f\big{\|}_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}\leq\sum_{m=0}^{\infty}\frac{t^{m}}{m!}\big{\|}\mathscr{L}_{\boldsymbol{\alpha}}^{m}f\big{\|}_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}\leq\sum_{m=0}^{\infty}\frac{(2nt)^{m}}{m!}\|f\|_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}=e^{2nt}\|f\|_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}.\end{split}$

Since $P_{t}^{\boldsymbol{\alpha}}=e^{t\mathscr{L}_{\boldsymbol{\alpha}}}$ for
$t\geq 0$, this inequality applied to $P_{t}^{\boldsymbol{\alpha}}f$ with
$t=\tfrac{1}{n}$ implies that

$\|f\|_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}\leq
e^{2}\big{\|}P_{1/n}^{\boldsymbol{\alpha}}f\big{\|}_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}.$
(52)

Similarly to (38) and (39), we thus have

$\begin{split}\|f&\|_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}\leq
e^{2}\big{\|}P_{1/n}^{\boldsymbol{\alpha}}f\big{\|}_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}.\\\
&\leq
e^{2}\int_{1/n}^{\infty}\left(\int_{\\{-1,1\\}^{n}}\sum_{y\in\\{-1,1\\}^{n}}p_{t}^{\boldsymbol{\alpha}}(x,y)\Big{\|}\sum_{i=1}^{n}\eta_{t}^{\alpha}\big{(}y(i),x(i);\theta_{i}(t)\big{)}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\right)^{1/p}\,\mathop{}\\!\mathrm{d}t\end{split}$
(53)

Fix $t\geq 0$ and $x\in\\{-1,1\\}^{n}$. Since
$p_{t}^{\boldsymbol{\alpha}}(x,\cdot)$ is a product measure, the centering
condition (28) gives

$\begin{split}\sum_{y\in\\{-1,1\\}^{n}}p_{t}^{\boldsymbol{\alpha}}(x,y)&\Big{\|}\sum_{i=1}^{n}\eta_{t}^{\alpha}\big{(}y(i),x(i);\theta_{i}(t)\big{)}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\\\
&\leq
2^{p}\int_{\\{-1,1\\}^{n}}\sum_{y\in\\{-1,1\\}^{n}}p_{t}^{\boldsymbol{\alpha}}(x,y)\Big{\|}\sum_{i=1}^{n}\delta_{i}\big{|}\eta_{t}^{\alpha}\big{(}y(i),x(i);\theta_{i}(t)\big{)}\big{|}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta).\end{split}$
(54)

To prove (49), set $\theta_{i}(t)=\frac{e^{-t}}{2}$ and observe that by the
contraction principle [33, Theorem 4.4], we can further bound this quantity by

$\begin{split}2^{p}\sum_{y\in\\{-1,1\\}^{n}}p_{t}^{\boldsymbol{\alpha}}(x,y)&\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\big{|}\eta_{t}^{\alpha}\big{(}y(i),x(i);\tfrac{e^{-t}}{2}\big{)}\big{|}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\\\
&\leq
2^{p}\max_{\chi,\psi\in\\{-1,1\\}}\big{|}\eta_{t}^{\alpha}\big{(}\psi,\chi;\tfrac{e^{-t}}{2}\big{)}\big{|}^{p}\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta).\end{split}$
(55)

It is now elementary to check that we have

$\max_{\chi,\psi\in\\{-1,1\\}}\big{|}\eta_{t}^{\alpha}\big{(}\psi,\chi;\tfrac{e^{-t}}{2}\big{)}\big{|}\lesssim_{\alpha}\begin{cases}\frac{1}{t},&\mbox{for
}t\in(0,1)\\\ e^{-t},&\mbox{for }t\geq 1\end{cases}$ (56)

and thus combining all the above we get

$\|f\|_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}\lesssim_{\alpha}\left(\int_{1/n}^{1}\frac{\mathop{}\\!\mathrm{d}t}{t}+\int_{1}^{\infty}e^{-t}\,\mathop{}\\!\mathrm{d}t\right)\cdot\left(\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}f\Big{\|}_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\right)^{1/p},$
(57)

which readily concludes the proof of (49).

For the proof of (50), we combine (38) and (39) with (54) to get

$\|f\|_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}\leq
2\int_{0}^{\infty}\left(\int_{\\{-1,1\\}^{2n}}\sum_{y\in\\{-1,1\\}^{n}}p_{t}^{\boldsymbol{\alpha}}(x,y)\Big{\|}\sum_{i=1}^{n}\delta_{i}\big{|}\eta_{t}^{\alpha}\big{(}y(i),x(i);\tfrac{e^{-t}}{2}\big{)}\big{|}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\right)^{1/p}\\!\\!\\!\\!\mathop{}\\!\mathrm{d}t.$

Fix $x\in\\{-1,1\\}^{n}$ and $t\geq 0$. Denoting by $I(x)=\\{i:\ x(i)=1\\}$,
the inner term is bounded above by

$\begin{split}\int_{\\{-1,1\\}^{n}}&\sum_{y\in\\{-1,1\\}^{n}}p_{t}^{\boldsymbol{\alpha}}(x,y)\Big{\|}\sum_{i=1}^{n}\delta_{i}\big{|}\eta_{t}^{\alpha}\big{(}y(i),x(i);\tfrac{e^{-t}}{2}\big{)}\big{|}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\\\
&\leq
2^{p-1}\int_{\\{-1,1\\}^{I(x)}}\sum_{y\in\\{-1,1\\}^{I(x)}}p_{t}^{\boldsymbol{\alpha}}(x,y)\Big{\|}\sum_{i\in
I(x)}\delta_{i}\big{|}\eta_{t}^{\alpha}\big{(}y(i),1;\tfrac{e^{-t}}{2}\big{)}\big{|}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{I(x)}(\delta)\\\
&+2^{p-1}\int_{\\{-1,1\\}^{I(x)^{c}}}\sum_{y\in\\{-1,1\\}^{I(x)^{c}}}p_{t}^{\boldsymbol{\alpha}}(x,y)\Big{\|}\sum_{i\notin
I(x)}\delta_{i}\big{|}\eta_{t}^{\alpha}\big{(}y(i),-1;\tfrac{e^{-t}}{2}\big{)}\big{|}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{I(x)^{c}}(\delta).\end{split}$
(58)

When $y\in\\{-1,1\\}^{I(x)}$ is distributed according to
$p_{t}^{\boldsymbol{\alpha}}(x,\cdot)$ and $\delta$ is a uniformly random
sign, the random variables
$\delta_{i}|\eta_{t}^{\alpha}(y(i),1;\tfrac{e^{-t}}{2})|$, $i\in I(x)$, are
independent and identically distributed. Therefore, standard comparison
principles going back to works of Maurey and Pisier (see, e.g., [33,
Proposition 9.14]) show that if $X$ has cotype $q<\infty$ and
$r>\max\\{p,q\\}$, then

$\begin{split}\int_{\\{-1,1\\}^{I(x)}}&\sum_{y\in\\{-1,1\\}^{I(x)}}p_{t}^{\boldsymbol{\alpha}}(x,y)\Big{\|}\sum_{i\in
I(x)}\delta_{i}\big{|}\eta_{t}^{\alpha}\big{(}y(i),1;\tfrac{e^{-t}}{2}\big{)}\big{|}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{I(x)}(\delta)\\\
&\lesssim_{r,X}\Big{(}\sum_{\psi\in\\{-1,1\\}}p_{t}^{{\alpha}}\big{(}1,\psi;\tfrac{e^{-t}}{2}\big{)}\big{|}\eta_{t}^{\alpha}\big{(}\psi,1;\tfrac{e^{-t}}{2}\big{)}\big{|}^{r}\Big{)}^{p/r}\int_{\\{-1,1\\}^{I(x)}}\Big{\|}\sum_{i\in
I(x)}\delta_{i}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{I(x)}(\delta).\end{split}$
(59)

It is again elementary to show that

$\max_{\chi\in\\{-1,1\\}}\Big{(}\sum_{\psi\in\\{-1,1\\}}p_{t}^{{\alpha}}\big{(}\chi,\psi;\tfrac{e^{-t}}{2}\big{)}\big{|}\eta_{t}^{\alpha}\big{(}\psi,\chi;\tfrac{e^{-t}}{2}\big{)}\big{|}^{r}\Big{)}^{1/r}\lesssim_{r,\alpha}\begin{cases}\frac{1}{t^{1-\frac{1}{r}}},&\mbox{for
}t\in(0,1)\\\ e^{-t},&\mbox{for }t\geq 1\end{cases}.$ (60)

In view of the convergence of the integrals

$\int_{0}^{1}\frac{\mathop{}\\!\mathrm{d}t}{t^{1-\frac{1}{r}}}+\int_{1}^{\infty}e^{-t}\,\mathop{}\\!\mathrm{d}t\lesssim_{r}1,$
(61)

combining (59), the corresponding estimate on $I(x)^{c}$ and (58), we finally
get

$\begin{split}\|f\|_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}\lesssim_{r,\alpha,X}\left(\int_{\\{-1,1\\}^{n}}\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i\in
I(x)}\delta_{i}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}+\Big{\|}\sum_{i\notin
I(x)}\delta_{i}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}(x)}\right)^{1/p}.\end{split}$

Now, if $F,G$ are two independent centered $X$-valued random vectors, then

$\mathbb{E}\|F+G\|_{X}^{p}\geq\max\big{\\{}\mathbb{E}_{F}\|F+\mathbb{E}_{G}[G]\|_{X}^{p},\mathbb{E}_{G}\|\mathbb{E}_{F}[F]+G\|_{X}^{p}\big{\\}}=\max\big{\\{}\mathbb{E}\|F\|_{X}^{p},\mathbb{E}\|G\|_{X}^{p}\big{\\}}.$
(62)

Therefore,

$\begin{split}\Bigg{(}\int_{\\{-1,1\\}^{n}}\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i\in
I(x)}\delta_{i}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}+\Big{\|}\sum_{i\notin
I(x)}&\delta_{i}\partial_{i}^{\alpha}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}(x)}\Bigg{)}^{1/p}\\\
&\lesssim\left(\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}^{\alpha}f(x)\Big{\|}_{L_{p}(\mu_{\boldsymbol{\alpha}};X)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\right)^{1/p}\end{split}$
(63)

and this concludes the proof of the theorem. ∎

We now proceed to discuss the vector-valued $L_{p}$ logarithmic Sobolev
inequality of Theorem 2. Recall that given a function $f:(\Omega,\mu)\to X$,
we define the $L_{p}(\log L)^{a}$ Orlicz norm of $f$ as

$\|f\|_{L_{p}(\log L)^{a}(\mu;X)}=\inf\left\\{\gamma>0:\
\int_{\Omega}\tfrac{\|f(\omega)\|_{X}^{p}}{\gamma^{p}}\
\log^{a}\Big{(}e+\tfrac{\|f(\omega)\|_{X}^{p}}{\gamma^{p}}\Big{)}\,\mathop{}\\!\mathrm{d}\mu(\omega)\leq
1\right\\}.$ (64)

In the case of the unbiased cube, Theorem 2 was proven recently in [16] and
the proof used as a black box the unbiased analogue of Theorem 16 which is due
to [64, 27]. As the modifications which are required to derive Theorem 2 from
Theorem 16 in the biased case are almost mechanical, we shall only offer a
high-level description of the proof.

###### Sketch of the proof of Theorem 2.

Given a scalar-valued function $h:\\{-1,1\\}^{n}\to\mathbb{R}$, we denote by
$\mathsf{M}h:\\{-1,1\\}^{n}\to\mathbb{R}_{+}$ the asymmetric gradient of $h$,
given by

$\forall\
x\in\\{-1,1\\}^{n},\qquad\mathsf{M}h(x)=\bigg{(}\sum_{i=1}^{n}\partial_{i}h(x)_{+}^{2}\bigg{)}^{1/2},$
(65)

where $a_{+}=\max\\{a,0\\}$ for $a\in\mathbb{R}$. A combination of the
triangle inequality with a technical result of Talagrand [67, Proposition 5.1]
on the biased cube implies that if a vector-valued function
$f:\\{-1,1\\}^{n}\to X$ satisfies $\int
f\,\mathop{}\\!\mathrm{d}\mu_{\alpha}^{n}=0$, then

$\|f\|_{L_{p}(\log
L)^{p/2}(\mu_{\alpha}^{n};X)}\lesssim_{p,\alpha}\big{\|}\mathsf{M}\|f\|_{X}\big{\|}_{L_{p}(\mu_{\alpha}^{n};X)}+\|f\|_{L_{1}(\mu_{\alpha}^{n};X)}.$
(66)

The second term can be controlled by the right hand side of (9) or (10) using
the results of Theorem 16. For the first term, we use the key pointwise
inequality of [16], asserting that

$\forall\
x\in\\{-1,1\\}^{n},\qquad\mathsf{M}\|f\|_{X}(x)\leq\sqrt{2}\Bigg{(}\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\Bigg{)}^{1/p}.$
(67)

To further upper bound this by the square function where $\partial_{i}$ is
replaced by $\partial_{i}^{\alpha}$, observe that

$\partial_{i}^{\alpha}f(x)\in\big{\\{}2\alpha\partial_{i}f(x),2(1-\alpha)\partial_{i}f(x)\big{\\}}$
(68)

and thus the contraction principle and integration in $x$ yield the desired
conclusions. ∎

##  5\. Proof of Theorem 4

In this section we shall prove the equivalence of stable type and metric
stable type for norms. The key ingredient in the proof is the following
characterization of stable type (see, e.g., [33, Proposition 9.12 (iii)])
which goes back at least to [40].

######  Lemma 17.

A Banach space $(X,\|\cdot\|_{X})$ has stable type $p\in[1,2)$ if and only if
there exists a constant $\mathsf{ST}_{p}(X)\in(0,\infty)$ such that for every
$n\in\mathbb{N}$ and every vectors $v_{1},\ldots,v_{n}\in X$, we have

$\int_{\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}x_{i}v_{i}\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\leq\mathsf{ST}_{p}(X)^{p}\big{\|}\big{(}\|v_{1}\|_{X},\ldots,\|v_{n}\|_{X}\big{)}\big{\|}_{\ell_{p,\infty}^{n}}^{p}.$
(69)

###### Proof of Theorem 4.

It is clear from Lemma 17 that any normed space with metric stable type $p$
also has stable type $p$. For the converse implication, we treat the case
$p=1$ separately. Assuming that $X$ has stable type 1, it follows from [59]
that it also has nontrivial Rademacher type and thus (in view of [57]) finite
cotype. Therefore, by the $X$-valued Pisier inequality with a dimension-free
constant of [27], we get

$\begin{split}\int_{\\{-1,1\\}^{n}}\big{\|}f(x)-f(-x)\big{\|}_{X}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)&\leq
2\int_{\\{-1,1\\}^{n}}\Big{\|}f(x)-\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\sigma_{n}\Big{\|}_{X}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\\\
&\lesssim_{X}\int_{\\{-1,1\\}^{n}}\int_{\\{-1,1\\}^{n}}\mathbb{E}\Big{\|}\sum_{i=1}^{n}\delta_{i}\partial_{i}f(x)\Big{\|}_{X}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\mathop{}\\!\mathrm{d}\sigma_{n}(x).\end{split}$
(70)

Applying Lemma 17 conditionally on $x\in\\{-1,1\\}^{n}$, we can further bound
this quantity as

$\begin{split}\int_{\\{-1,1\\}^{n}}\int_{\\{-1,1\\}^{n}}\mathbb{E}\Big{\|}\sum_{i=1}^{n}&\delta_{i}\partial_{i}f(x)\Big{\|}_{X}\,\mathop{}\\!\mathrm{d}\sigma_{n}(\delta)\mathop{}\\!\mathrm{d}\sigma_{n}(x)\\\
&\leq\mathsf{ST}_{1}(X)\int_{\\{-1,1\\}^{n}}\big{\|}\big{(}\|\partial_{1}f(x)\|_{X},\ldots,\|\partial_{n}f(x)\|_{X}\big{)}\big{\|}_{\ell_{1,\infty}^{n}}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\end{split}$
(71)

and this proves the converse implication since
$\mathfrak{d}_{i}f(x)=\|\partial_{i}f(x)\|_{X}$.

While this proof extends to all values of $p$, in the case $p>1$ we present a
more cumbersome argument which avoids the $X$-valued Pisier inequality and
thus gives better dependence on parameters of $X$. For $t\geq 0$, let
$\xi_{1}(t),\ldots,\xi_{n}(t)$ be i.i.d. random variables distributed
according to $\mu_{\beta(t)}$, where $\beta(t)=\tfrac{1+e^{-t}}{2}$, and
denote by $\eta_{i}(t)=\frac{\xi_{i}(t)-e^{-t}}{e^{t}-e^{-t}}$. Then, it
follows from the semigroup argument leading to (38) along with identity (47)
of [27] and Jensen’s inequality that

$\begin{split}\Bigg{(}\int_{\\{-1,1\\}^{n}}\big{\|}f(x)-f(-x)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\Bigg{)}^{1/p}&\leq
2\Bigg{(}\int_{\\{-1,1\\}^{n}}\Big{\|}f(x)-\int_{\\{-1,1\\}^{n}}f\,\mathop{}\\!\mathrm{d}\sigma_{n}\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\Bigg{)}^{1/p}\\\
&\leq
2\int_{0}^{\infty}\Bigg{(}\int_{\\{-1,1\\}^{n}}\mathbb{E}\Big{\|}\sum_{i=1}^{n}\eta_{i}(t)\partial_{i}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\Bigg{)}^{1/p}\,\mathop{}\\!\mathrm{d}t\end{split}$
(72)

Fixing $x\in\\{-1,1\\}^{n}$, the independent random vectors
$\eta_{1}(t)\partial_{1}f(x),\ldots,\eta_{n}(t)\partial_{n}f(x)$ are centered.
Thus, by standard symmetrization estimates, we can further bound the last term
by

$\begin{split}2\int_{0}^{\infty}\Bigg{(}\int_{\\{-1,1\\}^{n}}\mathbb{E}\Big{\|}\sum_{i=1}^{n}\eta_{i}(t)\partial_{i}f(x)\Big{\|}_{X}^{p}&\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\Bigg{)}^{1/p}\,\mathop{}\\!\mathrm{d}t\\\
&\leq
4\int_{0}^{\infty}\Bigg{(}\int_{\\{-1,1\\}^{n}}\mathbb{E}\Big{\|}\sum_{i=1}^{n}\delta_{i}\eta_{i}(t)\partial_{i}f(x)\Big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\Bigg{)}^{1/p}\,\mathop{}\\!\mathrm{d}t,\end{split}$
(73)

where the expectation on the right hand side is with respect to
$(\delta_{i},\eta_{i}(t))$, where the $\delta_{i}$ are uniformly random signs,
independent of the $\eta_{i}(t)$. Therefore, conditioning first on the values
of $\eta_{1}(t),\ldots,\eta_{n}(t)$ and using Lemma 17 for the integrand, we
get

$\mathbb{E}\Big{\|}\sum_{i=1}^{n}\delta_{i}\eta_{i}(t)\partial_{i}f(x)\Big{\|}_{X}^{p}\leq\mathsf{ST}_{p}(X)^{p}\mathbb{E}\bigg{\|}\sum_{i=1}^{n}\eta_{i}(t)\big{\|}\partial_{i}f(x)\big{\|}_{X}e_{i}\bigg{\|}_{\ell_{p,\infty}^{n}}^{p},$
(74)

where $\\{e_{1},\ldots,e_{n}\\}$ is the standard basis of $\mathbb{R}^{n}$. It
is well-known that, since $p>1$, $\ell_{p,\infty}^{n}$ is isomorphic to a
normed space up to constants depending only on $p$. Moreover, it has finite
cotype with a constant independent of $n$ (for instance because it can be
realized as a real interpolation space between $\ell_{1}^{n}$ and
$\ell_{2}^{n}$, see [11, Section 5.3]). Therefore, using again the comparison
principle [33, Proposition 9.14], we have

$\begin{split}\mathbb{E}\bigg{\|}\sum_{i=1}^{n}\eta_{i}(t)\big{\|}\partial_{i}f(x)\big{\|}_{X}e_{i}\bigg{\|}_{\ell_{p,\infty}^{n}}^{p}&\lesssim_{p}\|\eta_{1}(t)\|_{L_{r}}^{p}\mathbb{E}\bigg{\|}\sum_{i=1}^{n}\delta_{i}\big{\|}\partial_{i}f(x)\big{\|}_{X}e_{i}\bigg{\|}_{\ell_{p,\infty}^{n}}^{p}\\\
&=\|\eta_{1}(t)\|_{L_{r}}^{p}\big{\|}\big{(}\|\partial_{1}f(x)\|_{X},\ldots,\|\partial_{n}f(x)\|_{X}\big{)}\big{\|}_{\ell_{p,\infty}^{n}}^{p}\end{split}$
(75)

for any $r>\max\\{r^{\prime},p\\}$, where $r^{\prime}$ is the cotype of
$\ell_{p,\infty}^{n}$. Combining all the above along with the fact that
$t\mapsto\|\eta_{1}(t)\|_{L_{r}}$ is integrable for any $r<\infty$, we
conclude the proof. It is worth emphasizing that this proof shows additionally
that the metric stable type constant of $X$ is proportional to the parameter
$\mathsf{ST}_{p}(X)$ of (69) up to constants depending only on $p$, provided
that $p>1$. ∎

Finally, we present the simple proof of the distortion bound (16).

###### Proof of Proposition 6.

Suppose that $(\mathsf{M},d_{\mathsf{M}})$ has metric stable type $p$ with
constant $S$ and suppose that a function $f:\\{-1,1\\}^{n}\to\mathsf{M}$
satisfies

$\forall\ x,y\in\\{-1,1\\}^{n},\qquad s\rho_{\bf w}(x,y)\leq
d_{\mathsf{M}}\big{(}f(x),f(y)\big{)}\leq sD\rho_{\bf w}(x,y)$ (76)

for some constants $s>0$ and $D\geq 1$. Combined with the stable type
assumption, this gives

$\begin{split}s^{p}\|{\bf
w}\|_{\ell_{1}^{n}}^{p}\stackrel{{\scriptstyle\eqref{xx}}}{{\leq}}\int_{\\{-1,1\\}^{n}}d_{\mathsf{M}}\big{(}f(x)&,f(-x)\big{)}^{p}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\leq
S^{p}\int_{\\{-1,1\\}^{n}}\big{\|}\big{(}\mathfrak{d}_{1}f(x),\ldots,\mathfrak{d}_{n}f(x)\big{)}\big{\|}^{p}_{\ell_{p,\infty}^{n}}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)\\\
&\stackrel{{\scriptstyle\eqref{xx}}}{{\leq}}(sSD)^{p}\int_{\\{-1,1\\}^{n}}\|(w_{1},\ldots,w_{n})\|^{p}_{\ell_{p,\infty}^{n}}\,\mathop{}\\!\mathrm{d}\sigma_{n}(x)=(sSD)^{p}\|{\bf
w}\|_{\ell_{p,\infty}^{n}}^{p}.\end{split}$ (77)

Rearranging gives the desired lower bound (16) for the distortion $D$. ∎

##  6\. Discussion and open problems

1. The proof of Theorem 1 in fact implies a Poincaré-type inequality for _restrictions_ of functions $f:\\{-1,1\\}^{n}\to X$ if $\dim(X)<n$, which in turn yields the refined distortion lower bounds. An inspection of the argument reveals that for every such $f$ there exists a subset $\sigma\subseteq\\{1,\ldots,n\\}$ with $|\sigma|\leq\dim(X)$, a point $w\in\\{-1,1\\}^{\sigma^{c}}$ and a bias vector $\boldsymbol{\alpha}=(\alpha_{i})_{i\in\sigma}\in(0,1)^{\sigma}$ such that

$\begin{split}\int_{\\{-1,1\\}^{\sigma}}\big{\|}f(x,w)-&f(-x,-w)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x)\\\
&\leq
2^{2p-1}\big{(}\pi\mathsf{T}_{p}(X)\big{)}^{p}\sum_{i\in\sigma}\int_{\\{-1,1\\}^{\sigma}}\big{\|}\partial_{i}^{\alpha_{i}}f(x,w)\big{\|}_{X}^{p}+\big{\|}\partial_{i}^{\alpha_{i}}f(-x,-w)\big{\|}_{X}^{p}\,\mathop{}\\!\mathrm{d}\mu_{\boldsymbol{\alpha}}(x).\end{split}$
(78)

2. Such refinements of Poincaré-type inequalities for topological reasons had not been exploited since Oleszkiewicz’s original work [56]. The last decades have seen the development of many metric inequalities on graphs which yield nonembeddability results into normed spaces. We believe that investigating whether the distortion estimates which one obtains this way can be further improved assuming upper bounds for the dimension of the target space is a very worthwhile research program. As examples, we mention the nonembeddability of graphs with large girth into uniformly smooth spaces [39, 51], of $\ell_{\infty}$-grids into spaces of finite cotype [45] and of trees [12, 36] and diamond graphs [31, 23] into uniformly convex spaces.

3. The results of [27] in fact imply that any Lipschitz embedding of $\\{-1,1\\}^{n}$ into a normed space of Rademacher type $p$ incurs $p$-average distortion at least a constant multiple of $\mathsf{T}_{p}(X)^{-1}n^{1-1/p}$. It would be interesting to understand whether the bound of Theorem 1 can be extended to average distortion embeddings beyond bi-Lipschitz ones.

4. The Poincaré inequality (78) implies that any $f:\\{-1,1\\}^{n}\to X=(\mathbb{R}^{d},\|\cdot\|_{X})$ satisfies

$\sup_{(x,y):\ \rho(x,y)=n}\frac{n}{\|f(x)-f(y)\|_{X}}\sup_{(x,y):\
\rho(x,y)=1}\|f(x)-f(y)\|_{X}\gtrsim\frac{n}{\mathsf{T}_{p}(X)d^{1/p}},$ (79)

provided that $d<n$. This is stronger than the lower bound of Theorem 1 as it
implies that $f$ incurs large distortion only on _specific_ pairs of points,
namely those which are either antipodal or connected by an edge. Moreover
though, (79) is sharp for any value of $d$ and $p$. Indeed, assume without
loss of generality that $\tfrac{n}{d}$ is an odd integer and consider a
partition $I_{1},\ldots,I_{d}$ of $\\{1,\ldots,n\\}$ in $d$ parts of size
$\tfrac{n}{d}$. Then, the mapping $f:\\{-1,1\\}^{n}\to\ell_{p}^{d}$, where
$p\in[1,2]$, given by

$\forall\ x\in\\{-1,1\\}^{n},\qquad
f(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Big{(}\sum_{i\in
I_{1}}x_{i},\ldots,\sum_{i\in I_{d}}x_{i}\Big{)}$ (80)

satisfies

$\inf_{(x,y):\
\rho(x,y)=n}\big{\|}f(x)-f(y)\big{\|}_{\ell_{p}^{d}}=\inf_{x\in\\{-1,1\\}^{n}}\bigg{(}\sum_{k=1}^{d}\Big{|}\sum_{i\in
I_{k}}x_{i}\Big{|}^{p}\bigg{)}^{1/p}=d^{1/p}$ (81)

and $\|f(x)-f(y)\|_{\ell_{p}^{d}}=1$ when $\rho(x,y)=1$.

5. The functional inequality (78) in fact implies that if $\theta\in(0,1)$, then the bi-Lipschitz distortion of the $\theta$-snowflake of $\\{-1,1\\}^{n}$ into a finite dimensional normed space $X$ satisfies

$\mathsf{c}_{X}\big{(}\\{-1,1\\}^{n},\rho^{\theta}\big{)}\gtrsim\frac{n^{\theta}}{\mathsf{T}_{p}(X)\min\\{n,\dim(X)\\}^{1/p}}.$
(82)

6. As the reasons behind the impossibility of dimension reduction of Theorem 1 are partly topological, it is natural to ask in what other settings can one deduce similar conclusions. For instance, do $d$-dimensional manifolds of nonpositive or nonnegative curvature (which have Enflo type 2, see [55]) admit the same distortion bounds as normed spaces of type 2?

7. In this paper we extended the semigroup machinery developed in [27] to the biased cube, driven by the geometric application obtained in Theorem 1. As an aside, this led to biased versions of the vector-valued Poincaré and logarithmic Sobolev inequalities of [27, 16]. The same reasoning also yields biased extensions of the vector-valued versions of Talagrand’s influence inequality [68] which were studied in [17] for the uniform probability measure on the hypercube. Moreover, combining the biased semigroup machinery with the arguments of [10, Section 2.5], one can derive biased versions of the isoperimetric-type inequalities of Eldan and Gross [18]. As these extensions are mostly mechanical given the material of this paper and in lack of a specific application which may follow from them, we omit them.

## References

  * [1] Alexandr Andoni, Moses S. Charikar, Ofer Neiman, and Huy L. Nguyen.  Near linear lower bound for dimension reduction in $\ell_{1}$.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pages 315–323. IEEE Computer Soc., Los Alamitos, CA, 2011.
  * [2] Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn.  Approximate nearest neighbor search in high dimensions.  In Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, pages 3287–3318. World Sci. Publ., Hackensack, NJ, 2018.
  * [3] Juan Arias-de-Reyna and Luis Rodríguez-Piazza.  Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces.  Israel J. Math., 79(1):103–111, 1992.
  * [4] Keith Ball.  The Ribe programme.  Astérisque, (352):Exp. No. 1047, viii, 147–159, 2013.  Séminaire Bourbaki. Vol. 2011/2012. Exposés 1043–1058.
  * [5] Keith Ball, Eric A. Carlen, and Elliott H. Lieb.  Sharp uniform convexity and smoothness inequalities for trace norms.  Invent. Math., 115(3):463–482, 1994.
  * [6] Imre Bárány and Victor S. Grinberg.  On some combinatorial questions in finite-dimensional spaces.  Linear Algebra Appl., 41:1–9, 1981.
  * [7] Yair Bartal, Lee-Ad Gottlieb, and Ofer Neiman.  On the impossibility of dimension reduction for doubling subsets of $\ell_{p}$.  SIAM J. Discrete Math., 29(3):1207–1222, 2015.
  * [8] Yair Bartal and Manor Mendel.  Dimension reduction for ultrametrics.  In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 664–665. ACM, New York, 2004.
  * [9] Florent Baudier, Krzysztof Swieçicki, and Andrew Swift.  No dimension reduction for doubling subsets of $\ell_{q}$ when $q>2$ revisited.  J. Math. Anal. Appl., 504(2):Paper No. 125407, 18, 2021.
  * [10] David Beltran, Paata Ivanisvili, and José Madrid.  On sharp isoperimetric inequalities on the hypercube.  Preprint available at https://arxiv.org/abs/2303.06738, 2023.
  * [11] Jöran Bergh and Jörgen Löfström.  Interpolation spaces. An introduction, volume No. 223 of Grundlehren der Mathematischen Wissenschaften.  Springer-Verlag, Berlin-New York, 1976.
  * [12] Jean Bourgain.  The metrical interpretation of superreflexivity in Banach spaces.  Israel J. Math., 56(2):222–230, 1986.
  * [13] Jean Bourgain, Vitali Milman, and Haim Wolfson.  On type of metric spaces.  Trans. Amer. Math. Soc., 294(1):295–317, 1986.
  * [14] Bo Brinkman and Moses Charikar.  On the impossibility of dimension reduction in $l_{1}$.  J. ACM, 52(5):766–788, 2005.
  * [15] Bo Brinkman, Adriana Karagiozova, and James R. Lee.  Vertex cuts, random walks, and dimension reduction in series-parallel graphs.  In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 621–630. ACM, New York, 2007.
  * [16] Dario Cordero-Erausquin and Alexandros Eskenazis.  Discrete logarithmic Sobolev inequalities in Banach spaces.  Preprint available at https://arxiv.org/abs/2304.03878, 2023.
  * [17] Dario Cordero-Erausquin and Alexandros Eskenazis.  Talagrand’s influence inequality revisited.  Anal. PDE, 16(2):571–612, 2023.
  * [18] Ronen Eldan and Renan Gross.  Concentration on the Boolean hypercube via pathwise stochastic analysis.  Invent. Math., 230(3):935–994, 2022.
  * [19] Per Enflo.  On a problem of Smirnov.  Ark. Mat., 8:107–109, 1969.
  * [20] Per Enflo.  On the nonexistence of uniform homeomorphisms between $L_{p}$-spaces.  Ark. Mat., 8:103–105, 1969.
  * [21] Per Enflo.  On infinite-dimensional topological groups.  In Séminaire sur la Géométrie des Espaces de Banach (1977–1978), pages Exp. No. 10–11, 11. École Polytech., Palaiseau, 1978.
  * [22] Alexandros Eskenazis.  On Pisier’s inequality for UMD targets.  Canad. Math. Bull., 64(2):282–291, 2021.
  * [23] Alexandros Eskenazis, Manor Mendel, and Assaf Naor.  Diamond convexity: a bifurcation in the Ribe program.  Preprint, 2023.
  * [24] Anupam Gupta, Robert Krauthgamer, and James R. Lee.  Bounded geometries, fractals, and low-distortion embeddings.  In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 534–543, 2003.
  * [25] Tuomas Hytönen and Assaf Naor.  Pisier’s inequality revisited.  Studia Math., 215(3):221–235, 2013.
  * [26] Piotr Indyk.  Algorithmic applications of low-distortion geometric embeddings.  In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pages 10–33. IEEE Computer Soc., Los Alamitos, CA, 2001.
  * [27] Paata Ivanisvili, Ramon van Handel, and Alexander Volberg.  Rademacher type and Enflo type coincide.  Ann. of Math. (2), 192(2):665–678, 2020.
  * [28] Robert C. James.  Nonreflexive spaces of type $2$.  Israel J. Math., 30(1-2):1–13, 1978.
  * [29] William B. Johnson and Joram Lindenstrauss.  Extensions of Lipschitz mappings into a Hilbert space.  In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189–206. Amer. Math. Soc., Providence, RI, 1984.
  * [30] William B. Johnson, Joram Lindenstrauss, and Gideon Schechtman.  On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces.  In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 177–184. Springer, Berlin, 1987.
  * [31] William B. Johnson and Gideon Schechtman.  Diamond graphs and super-reflexivity.  J. Topol. Anal., 1(2):177–189, 2009.
  * [32] Vincent Lafforgue and Assaf Naor.  A doubling subset of $L_{p}$ for $p>2$ that is inherently infinite dimensional.  Geom. Dedicata, 172:387–398, 2014.
  * [33] Michel Ledoux and Michel Talagrand.  Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)].  Springer-Verlag, Berlin, 1991.  Isoperimetry and processes.
  * [34] James R. Lee, Manor Mendel, and Assaf Naor.  Metric structures in $L_{1}$: dimension, snowflakes, and average distortion.  European J. Combin., 26(8):1180–1190, 2005.
  * [35] James R. Lee and Assaf Naor.  Embedding the diamond graph in $L_{p}$ and dimension reduction in $L_{1}$.  Geom. Funct. Anal., 14(4):745–747, 2004.
  * [36] James R. Lee, Assaf Naor, and Yuval Peres.  Trees and Markov convexity.  Geom. Funct. Anal., 18(5):1609–1659, 2009.
  * [37] David A. Levin and Yuval Peres.  Markov chains and mixing times.  American Mathematical Society, Providence, RI, second edition, 2017.  With contributions by Elizabeth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson.
  * [38] Nathan Linial.  Finite metric-spaces—combinatorics, geometry and algorithms.  In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), pages 573–586. Higher Ed. Press, Beijing, 2002.
  * [39] Nathan Linial, Avner Magen, and Assaf Naor.  Girth and Euclidean distortion.  Geom. Funct. Anal., 12(2):380–394, 2002.
  * [40] Michael B. Marcus and Gilles Pisier.  Characterizations of almost surely continuous $p$-stable random Fourier series and strongly stationary processes.  Acta Math., 152(3-4):245–301, 1984.
  * [41] Jiří Matoušek.  Note on bi-Lipschitz embeddings into normed spaces.  Comment. Math. Univ. Carolin., 33(1):51–55, 1992.
  * [42] Jiří Matoušek.  On the distortion required for embedding finite metric spaces into normed spaces.  Israel J. Math., 93:333–344, 1996.
  * [43] Jiří Matoušek.  Using the Borsuk-Ulam theorem.  Universitext. Springer-Verlag, Berlin, 2003.  Lectures on topological methods in combinatorics and geometry, Written in cooperation with Anders Björner and Günter M. Ziegler.
  * [44] Bernard Maurey and Gilles Pisier.  Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach.  Studia Math., 58(1):45–90, 1976.
  * [45] Manor Mendel and Assaf Naor.  Metric cotype.  Ann. of Math. (2), 168(1):247–298, 2008.
  * [46] Assaf Naor.  An introduction to the Ribe program.  Jpn. J. Math., 7(2):167–233, 2012.
  * [47] Assaf Naor.  Comparison of metric spectral gaps.  Anal. Geom. Metr. Spaces, 2(1):1–52, 2014.
  * [48] Assaf Naor.  A spectral gap precludes low-dimensional embeddings.  In 33rd International Symposium on Computational Geometry, volume 77 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 50, 16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017.
  * [49] Assaf Naor.  Metric dimension reduction: a snapshot of the Ribe program.  In Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. I. Plenary lectures, pages 759–837. World Sci. Publ., Hackensack, NJ, 2018.
  * [50] Assaf Naor.  An average John theorem.  Geom. Topol., 25(4):1631–1717, 2021.
  * [51] Assaf Naor, Yuval Peres, Oded Schramm, and Scott Sheffield.  Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces.  Duke Math. J., 134(1):165–197, 2006.
  * [52] Assaf Naor, Gilles Pisier, and Gideon Schechtman.  Impossibility of dimension reduction in the nuclear norm.  Discrete Comput. Geom., 63(2):319–345, 2020.
  * [53] Assaf Naor and Gideon Schechtman.  Remarks on non linear type and Pisier’s inequality.  J. Reine Angew. Math., 552:213–236, 2002.
  * [54] Assaf Naor and Robert Young.  Foliated corona decompositions.  Acta Math., 229(1):55–200, 2022.
  * [55] Shin-Ichi Ohta.  Markov type of Alexandrov spaces of non-negative curvature.  Mathematika, 55(1-2):177–189, 2009.
  * [56] Krzysztof Oleszkiewicz.  On a discrete version of the antipodal theorem.  Fund. Math., 151(2):189–194, 1996.
  * [57] Gilles Pisier.  Sur les espaces de Banach qui ne contiennent pas uniformément de $l^{1}_{n}$.  C. R. Acad. Sci. Paris Sér. A-B, 277:A991–A994, 1973.
  * [58] Gilles Pisier.  “Type” des espaces normés.  In Séminaire Maurey-Schwartz 1973–1974: Espaces $L^{p}$, applications radonifiantes et géométrie des espaces de Banach, Exp. No. 3,, pages 12 pp. (errata, p. E.1). ,, 1974.
  * [59] Gilles Pisier.  Une propriété du type $p$-stable.  In Séminaire Maurey-Schwartz 1973–1974: Espaces $L^{p}$, applications radonifiantes et géométrie des espaces de Banach, pages Exp. No. 8, 10 pp. (errata, p. E.1). École Polytech., Paris, 1974.
  * [60] Gilles Pisier.  Martingales with values in uniformly convex spaces.  Israel J. Math., 20(3-4):326–350, 1975.
  * [61] Gilles Pisier.  Un exemple concernant la super-réflexivité.  In Séminaire Maurey-Schwartz 1974–1975: Espaces $L^{p}$ applications radonifiantes et géométrie des espaces de Banach, Annexe No. 2,, page 12. ,, 1975.
  * [62] Gilles Pisier.  Holomorphic semigroups and the geometry of Banach spaces.  Ann. of Math. (2), 115(2):375–392, 1982.
  * [63] Gilles Pisier.  On the dimension of the $l^{n}_{p}$-subspaces of Banach spaces, for $1\leq p<2$.  Trans. Amer. Math. Soc., 276(1):201–211, 1983.
  * [64] Gilles Pisier.  Probabilistic methods in the geometry of Banach spaces.  In Probability and analysis (Varenna, 1985), volume 1206 of Lecture Notes in Math., pages 167–241. Springer, Berlin, 1986.
  * [65] Gilles Pisier and Quanhua Xu.  Random series in the real interpolation spaces between the spaces $v_{p}$.  In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 185–209. Springer, Berlin, 1987.
  * [66] Martin Ribe.  On uniformly homeomorphic normed spaces.  Ark. Mat., 14(2):237–244, 1976.
  * [67] Michel Talagrand.  Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem.  Geom. Funct. Anal., 3(3):295–314, 1993.
  * [68] Michel Talagrand.  On Russo’s approximate zero-one law.  Ann. Probab., 22(3):1576–1587, 1994.
  * [69] Santosh S. Vempala.  The random projection method, volume 65 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science.  American Mathematical Society, Providence, RI, 2004.  With a foreword by Christos H. Papadimitriou.