The Euclidean distortion of flat tori

Ishay Haviv; Oded Regev

doi:10.1142/S1793525313500064

The Euclidean distortion of flat tori

Ishay Haviv, Oded Regev

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We show that for every n-dimensional lattice & scriptLsign the torus ⁿ/&scriptLsign can be embedded with distortion O(n√log n) into a Hilbert space. This improves the exponential upper bound of O(n3n/2) due to Khot and Naor (FOCS 2005, Math. Ann. 2006) and gets close to their lower bound of δ(√n). We also obtain tight bounds for certain families of lattices. Our main new ingredient is an embedding that maps any point u ε n/L to a Gaussian function centered at u in the Hilbert space L2(. ⁿ/L). The proofs involve Gaussian measures on lattices, the smoothing parameter of lattices and Korkine-Zolotarev bases.

Original language	English (US)
Pages (from-to)	205-223
Number of pages	19
Journal	Journal of Topology and Analysis
Volume	5
Issue number	2
DOIs	https://doi.org/10.1142/S1793525313500064
State	Published - Jun 2013

Keywords

Lattices
embedding
flat tori

ASJC Scopus subject areas

Analysis
Geometry and Topology

Access to Document

10.1142/S1793525313500064

Cite this

@article{e89e298b4646439c9f35b9006bd1e22d,

title = "The Euclidean distortion of flat tori",

abstract = "We show that for every n-dimensional lattice & scriptLsign the torus n/&scriptLsign can be embedded with distortion O(n√log n) into a Hilbert space. This improves the exponential upper bound of O(n3n/2) due to Khot and Naor (FOCS 2005, Math. Ann. 2006) and gets close to their lower bound of δ(√n). We also obtain tight bounds for certain families of lattices. Our main new ingredient is an embedding that maps any point u ε n/L to a Gaussian function centered at u in the Hilbert space L2(. n/L). The proofs involve Gaussian measures on lattices, the smoothing parameter of lattices and Korkine-Zolotarev bases.",

keywords = "Lattices, embedding, flat tori",

author = "Ishay Haviv and Oded Regev",

note = "Funding Information: I. Haviv was supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities. Work done while at Tel Aviv University. O. Regev was supported by the Binational Science Foundation, by the Israel Science Foundation, by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848, by the Wolfson Family Charitable Trust, and by a European Research Council (ERC) Starting Grant. Work done while at Tel Aviv University.",

year = "2013",

month = jun,

doi = "10.1142/S1793525313500064",

language = "English (US)",

volume = "5",

pages = "205--223",

journal = "Journal of Topology and Analysis",

issn = "1793-5253",

publisher = "World Scientific",

number = "2",

}

TY - JOUR

T1 - The Euclidean distortion of flat tori

AU - Haviv, Ishay

AU - Regev, Oded

N1 - Funding Information: I. Haviv was supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities. Work done while at Tel Aviv University. O. Regev was supported by the Binational Science Foundation, by the Israel Science Foundation, by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848, by the Wolfson Family Charitable Trust, and by a European Research Council (ERC) Starting Grant. Work done while at Tel Aviv University.

PY - 2013/6

Y1 - 2013/6

N2 - We show that for every n-dimensional lattice & scriptLsign the torus n/&scriptLsign can be embedded with distortion O(n√log n) into a Hilbert space. This improves the exponential upper bound of O(n3n/2) due to Khot and Naor (FOCS 2005, Math. Ann. 2006) and gets close to their lower bound of δ(√n). We also obtain tight bounds for certain families of lattices. Our main new ingredient is an embedding that maps any point u ε n/L to a Gaussian function centered at u in the Hilbert space L2(. n/L). The proofs involve Gaussian measures on lattices, the smoothing parameter of lattices and Korkine-Zolotarev bases.

AB - We show that for every n-dimensional lattice & scriptLsign the torus n/&scriptLsign can be embedded with distortion O(n√log n) into a Hilbert space. This improves the exponential upper bound of O(n3n/2) due to Khot and Naor (FOCS 2005, Math. Ann. 2006) and gets close to their lower bound of δ(√n). We also obtain tight bounds for certain families of lattices. Our main new ingredient is an embedding that maps any point u ε n/L to a Gaussian function centered at u in the Hilbert space L2(. n/L). The proofs involve Gaussian measures on lattices, the smoothing parameter of lattices and Korkine-Zolotarev bases.

KW - Lattices

KW - embedding

KW - flat tori

UR - http://www.scopus.com/inward/record.url?scp=84878324623&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84878324623&partnerID=8YFLogxK

U2 - 10.1142/S1793525313500064

DO - 10.1142/S1793525313500064

M3 - Article

AN - SCOPUS:84878324623

SN - 1793-5253

VL - 5

SP - 205

EP - 223

JO - Journal of Topology and Analysis

JF - Journal of Topology and Analysis

IS - 2

ER -

The Euclidean distortion of flat tori

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this