  We prove that not every metric space embeds coarsely into an Alexandrov space
of nonpositive curvature. This answers a question of Gromov (1993) and is in
contrast to the fact that any metric space embeds coarsely into an Alexandrov
space of nonnegative curvature, as shown by Andoni, Naor and Neiman (2015). We
establish this statement by proving that a metric space which is
$q$-barycentric for some $q\in [1,\infty)$ has metric cotype $q$ with sharp
scaling parameter. Our proof utilizes nonlinear (metric space-valued)
martingale inequalities and yields sharp bounds even for some classical Banach
spaces. This allows us to evaluate the bi-Lipschitz distortion of the
$\ell_\infty$ grid $[m]_\infty^n=(\{1,\ldots,m\}^n,\|\cdot\|_\infty)$ into
$\ell_q$ for all $q\in (2,\infty)$, from which we deduce the following discrete
converse to the fact that $\ell_\infty^n$ embeds with distortion $O(1)$ into
$\ell_q$ for $q=O(\log n)$. A rigidity theorem of Ribe (1976) implies that for
every $n\in \mathbb{N}$ there exists $m\in \mathbb{N}$ such that if
$[m]_\infty^n$ embeds into $\ell_q$ with distortion $O(1)$, then $q$ is
necessarily at least a universal constant multiple of $\log n$. Ribe's theorem
does not give an explicit upper bound on this $m$, but by the work of Bourgain
(1987) it suffices to take $m=n$, and this was the previously best-known
estimate for $m$. We show that the above discretization statement actually
holds when $m$ is a universal constant.
