#### Volume 25, issue 4 (2021)

 Download this article For screen For printing
 Recent Issues
 The Journal About the Journal Editorial Board Editorial Interests Editorial Procedure Subscriptions Submission Guidelines Submission Page Policies for Authors Ethics Statement ISSN (electronic): 1364-0380 ISSN (print): 1465-3060 Author Index To Appear Other MSP Journals
This article is available for purchase or by subscription. See below.
An average John theorem

### Assaf Naor

Geometry & Topology 25 (2021) 1631–1717
##### Abstract

We prove that the $\frac{1}{2}$–snowflake of any finite-dimensional normed space $X$ embeds into a Hilbert space with quadratic average distortion

$O\left(\sqrt{logdim\left(X\right)}\right).$

We deduce from this (optimal) statement that if an $n$–vertex expander embeds with average distortion $D\ge 1$ into $X\phantom{\rule{-0.17em}{0ex}}$, then necessarily $dim\left(X\right)\ge {n}^{\Omega \left(1∕D\right)}$, which is sharp by the work of Johnson, Lindenstrauss and Schechtman (1987). This improves over the previously best-known bound $dim\left(X\right)\gtrsim {\left(logn\right)}^{2}∕{D}^{2}$ of Linial, London and Rabinovich (1995), strengthens a theorem of Matoušek (1996) which resolved questions of Johnson and Lindenstrauss (1982), Bourgain (1985) and Arias-de-Reyna and Rodríguez-Piazza (1992), and answers negatively a question that was posed (for algorithmic purposes) by Andoni, Nguyen, Nikolov, Razenshteyn and Waingarten (2016).

## PDF Access Denied

We have not been able to recognize your IP address 3.238.72.180 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recom­mendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

##### Keywords
metric embeddings, dimension reduction, expander graphs, nonlinear spectral gaps, Markov type
Primary: 30L05
##### Publication
Received: 7 December 2016
Revised: 7 February 2020
Accepted: 11 May 2020
Published: 12 July 2021
Proposed: Yasha Eliashberg
Seconded: David M Fisher, Tobias H Colding
##### Authors
 Assaf Naor Department of Mathematics Princeton University Princeton, NJ United States