A semidefinite program for least distortion embeddings of flat tori into Hilbert spaces

• 成果类型: Article
• 署名作者: Heimendahl, Arne; Lucke, Moritz; Vallentin, Frank; Zimmermann, Marc Christian
• 署名单位: University of Cologne
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02369-7
• 发表日期: 2026-07
• 页码: 477-504
• 关键词: Low distortion Euclidean embeddings; semidefinite optimization; lattices; flat tori; Voronoi vectors; graphs

摘要

We derive and analyze an infinite-dimensional semidefinite program which computes least distortion embeddings of flat tori Rn/L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}<^>n/L$$\end{document}, where L is an n-dimensional lattice, into Hilbert spaces. This enables us to provide a constant factor improvement over the previously best lower bound on the minimal distortion of an embedding of an n-dimensional flat torus. As further applications we prove that every n-dimensional flat torus has a finite dimensional least distortion embedding, that the standard embedding of the standard torus is optimal, and we determine least distortion embeddings of all 2-dimensional flat tori.