OpenFrontiers
Join
← Back to the index
OP-0464OpenAnalysis

L Embeddings of the Heisenberg Group and Fast Estimation of Graph Isoperimetry · 2010-ana-179

Functional Analysis · ICM 2010: L Embeddings of the Heisenberg Group and Fast Estimation of Graph Isoperimetry

Source assessment · not reviewedAs of 2026-08-18Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

For a finite metric space (X,d)(X,d) and p∈{1,2}p\in\{1,2\}, define its least bi-Lipschitz distortion into LpL_p by

cp(X,d)=inf⁡{A≥1: there exist a map f:X→Lp and a scale s>0 such thats d(x,y)≤∥f(x)−f(y)∥p≤As d(x,y)for all x,y∈X}.c_p(X,d)=\inf\left\{A\geq 1:\ \begin{array}{l} \text{there exist a map }f:X\to L_p\text{ and a scale }s>0\text{ such that}\\ s\,d(x,y)\leq \lVert f(x)-f(y)\rVert_p\leq A s\,d(x,y)\quad\text{for all }x,y\in X \end{array}\right\}.

Prove or disprove that, for every D≥1D\geq 1, there exists a finite constant K(D)K(D) such that, for every positive integer nn and every translation-invariant metric ρ\rho on the cyclic group Cn=Z/nZC_n=\mathbb Z/n\mathbb Z (meaning that ρ(x+z,y+z)=ρ(x,y)\rho(x+z,y+z)=\rho(x,y) for all x,y,z∈Cnx,y,z\in C_n),

c2(Cn,ρ)≤D⟹c1(Cn,ρ)≤K(D),c_2\bigl(C_n,\sqrt{\rho}\bigr)\leq D \quad\Longrightarrow\quad c_1(C_n,\rho)\leq K(D),

where ρ\sqrt{\rho} is the metric (x,y)↦ρ(x,y)(x,y)\mapsto\sqrt{\rho(x,y)} and K(D)K(D) is independent of nn and ρ\rho.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗
Remaining questions in this record

Remaining questions recorded by the source

These are retained within the parent record and are not counted as additional index entries.

Question 1

For a finite metric space (X,d)(X,d), let c1(X,d)c_1(X,d) be the infimum of all A≥1A\geq 1 for which there exist a map f:X→L1f:X\to L_1 and a scale s>0s>0 such that

s d(x,y)≤∥f(x)−f(y)∥1≤As d(x,y)s\,d(x,y)\leq \lVert f(x)-f(y)\rVert_1\leq A s\,d(x,y)

for all x,y∈Xx,y\in X. Determine whether there exist positive integers nj→∞n_j\to\infty and translation-invariant metrics ρj\rho_j on the cyclic groups Cnj=Z/njZC_{n_j}=\mathbb Z/n_j\mathbb Z such that each metric space (Cnj,ρj)(C_{n_j},\sqrt{\rho_j}) embeds isometrically into a Hilbert space, but

c1(Cnj,ρj)⟶∞.c_1(C_{n_j},\rho_j)\longrightarrow\infty.

Source reference: Assaf Naor, "L1L_1 Embeddings of the Heisenberg Group and Fast Estimation of Graph Isoperimetry," Proceedings of the International Congress of Mathematicians 2010, Vol. III, 2010, pp. 1549-1575, Section 4.3.4 (unnumbered open question), doi:10.1142/9789814324359_0110, arXiv:1003.4261, https://arxiv.org/abs/1003.4261.

Progress & source assessment

Source-reported assessment from the ICM catalogue snapshot. This is not an independent review by Frontier Science.

The problem is unresolved. No citable result was found that either gives an nn-independent bound K(D)K(D) for all translation-invariant metrics on cyclic groups or constructs a family of such metrics with uniformly bounded c2(Cn,ρ)c_2(C_n,\sqrt{\rho}) and unbounded c1(Cn,ρ)c_1(C_n,\rho).

The principal partial result is Proposition 3.3 of Tim Austin, Assaf Naor, and Alain Valette, "The Euclidean Distortion of the Lamplighter Group," Discrete & Computational Geometry 44 (2010), 55-74, doi:10.1007/s00454-009-9162-6, arXiv:0705.4662. It proves that if GG is a finite Abelian group, mx=0mx=0 for every x∈Gx\in G, and D=c2(G,ρ)D=c_2(G,\sqrt{\rho}), then

c1(G,ρ)≲D4log⁡m.c_1(G,\rho)\lesssim D^4\log m.

For G=CnG=C_n this gives an upper bound that still depends on nn, and hence does not yield the required K(D)K(D). The paper explicitly says that the exponent dependence may be removable.

Sanjeev Arora, James R. Lee, and Assaf Naor, "Euclidean Distortion and the Sparsest Cut," Journal of the American Mathematical Society 21 (2008), 1-21, doi:10.1090/S0894-0347-07-00573-5, arXiv:math/0508154, prove that every nn-point negative-type metric embeds into Hilbert space, and hence into L1L_1, with distortion O(log⁡nlog⁡log⁡n)O\bigl(\sqrt{\log n}\log\log n\bigr). Austin-Naor-Valette note that this improves the cyclic-group dependence in their estimate, but it remains unbounded as n→∞n\to\infty.

Assaf Naor, "L1L_1 Embeddings of the Heisenberg Group and Fast Estimation of Graph Isoperimetry," Proceedings of the International Congress of Mathematicians 2010, Vol. III (2010), 1549-1575, doi:10.1142/9789814324359_0110, arXiv:1003.4261, restates the Abelian-group bound as Theorem 4.14 and then explicitly poses the exact cyclic-group question appearing here.

General counterexamples do not settle the cyclic invariant case. For example, Subhash Khot and Nisheeth K. Vishnoi, "The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ1\ell_1," Journal of the ACM 62(1) (2015), Article 8, 1-39, doi:10.1145/2629614, arXiv:1305.4581, construct negative-type metrics with unbounded L1L_1 distortion, but their metrics are not translation-invariant metrics on cyclic groups. Thus the known upper bounds retain nn-dependence, while the known lower-bound constructions do not satisfy the required cyclic symmetry.

References
  1. [1]ICM Conjectures · 2010-ana-179 link
  2. [2]ICM 2010: L Embeddings of the Heisenberg Group and Fast Estimation of Graph Isoperimetry link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.