A threshold phenomenon for embeddings of Euclidean snowflakes and impossibility of dimension reduction

Abstract

Fix 0<θleqslant 1. We prove that if 1leqslant p leqslant 2/θ, then the θ-snowflake of ℓ₂^k, namely, ℝ^k equipped with the metric ((x,y)∈ ℝ^k× ℝ^k)↦ |x−y|₂^θ, embeds with distortion O(1) into ℓ_p^m for some integer m≲_p,θk, which is optimal as k→ ∞, as seen by comparing dimensions. However, for p larger than the sharp threshold 2/θ the following change in behavior occurs: If a (1/√k)-dense subset of the Euclidean sphere S^k−1 embeds into ℓ_p^m with distortion O(1), then necessarily m≳_p,θ( k/log k)^pθ/2, which grows super-linearly in k as pθ/2>1, and this dimension bound is optimal as k→ ∞ up to lower order factors. We deduce from this statement that if 2<p<∞, then there exist arbitrarily large n-point subsets of ℓ_p with the property that if they embed with distortion O(1) into ℓ_p^m, then necessarily m≳_p ((log n)/(loglog n)²)^p/2, thus demonstrating that the statement of the Johnson--Lindenstrauss dimension reduction lemma fails to hold for ℓ_p

Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion
Jack Spalding-Jamieson
arXiv30 Oct 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
The sharp and non-sharp threshold phenomenon in buffered and Go-or-Grow systems
Ruben Taieb, Arnaud Ducrot
HAL20 Sep 2026PreprintCC BY-NC-ND 4.0Full textAnalysis & PDEsHAL
Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance
Fengqi Hou
arXiv30 Sep 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
The No-Meaning Falsity: The Structural Impossibility of the Arbitrary Sign in Classical Arabic
Elnaserledinellah Mahmoud Abdelwahab
HAL27 Oct 2026PreprintPublisher termsFull textGeneral mathematicsHAL
On the Impossibility of Estimating the Average Mixing Time
Nathan A. Judd, Amedeo Roberto Esposito
arXiv7 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{naor2026threshold,
  title = {{A threshold phenomenon for embeddings of Euclidean snowflakes and impossibility of dimension reduction}},
  author = {Assaf Naor and Kevin Ren},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.01079},
  eprint = {2609.01079},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.01079},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A threshold phenomenon for embeddings of Euclidean snowflakes and impossibility of dimension reduction
AU  - Assaf Naor
AU  - Kevin Ren
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.01079
UR  - https://arxiv.org/abs/2609.01079
AB  - Fix 0<θleqslant 1. We prove that if 1leqslant p leqslant 2/θ, then the θ-snowflake of ℓ_2^k, namely, ℝ^k equipped with the metric ((x,y)∈ ℝ^k× ℝ^k)↦ |x−y|_2^θ, embeds with distortion O(1) into ℓ_p^m for some integer m≲_p,θk, which is optimal as k→ ∞, as seen by comparing dimensions. However, for p larger than the sharp threshold 2/θ the following change in behavior occurs: If a (1/√k)-dense subset of the Euclidean sphere S^k−1 embeds into ℓ_p^m with distortion O(1), then necessarily m≳_p,θ( k/log k)^pθ/2, which grows super-linearly in k as pθ/2>1, and this dimension bound is optimal as k→ ∞ up to lower order factors. We deduce from this statement that if 2<p<∞, then there exist arbitrarily large n-point subsets of ℓ_p with the property that if they embed with distortion O(1) into ℓ_p^m, then necessarily m≳_p ((log n)/(loglog n)^2)^p/2, thus demonstrating that the statement of the Johnson--Lindenstrauss dimension reduction lemma fails to hold for ℓ_p
ER  -

Abstract

Related

Cite