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

Arne Heimendahl<EMAIL_ADDRESS>,  Moritz Lücke
<EMAIL_ADDRESS>,  Frank Vallentin<EMAIL_ADDRESS>and  Marc Christian Zimmermann<EMAIL_ADDRESS>
###### Abstract.

We derive and analyze an infinite-dimensional semidefinite program which
computes least distortion embeddings of flat tori $\mathbb{R}^{n}/L$, 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 tours is optimal, and we determine least distortion embeddings of
all $2$-dimensional flat tori.

###### 1991 Mathematics Subject Classification:

46B85, 52C07, 90C22

##  1\. Introduction

Least distortion embeddings of flat tori into Hilbert spaces were first
studied by Khot and Naor [11] in 2006. One motivation is that studying the
Euclidean distortion of flat tori might have applications to the complexity of
lattice problems, like the closest vector problem, and might also lead to more
efficient algorithms for lattice problems through the use of least distortion
embeddings. Another motivation comes from comparing the Riemannian setting to
the bi-Lipschitz setting we are discussing here. On the one hand, by the Nash
embedding theorem, flat tori can be embedded isometrically as Riemannian
submanifolds into Euclidean space; we refer to [4] for spectacular
visualizations of such an isometric embedding in the case of the two-
dimensional square flat torus. On the other hand, Khot and Naor showed that
flat tori can be highly non-Euclidean in the bi-Lipschitz setting.

###  1.1. Notation and review of the relevant literature

We review the relevant results of the literature which appeared since the
pioneering work of Khot and Naor. At the same time we set the notation for
this paper.

A flat torus is the metric space given by the quotient $\mathbb{R}^{n}/L$ with
some $n$-dimensional lattice $L\subseteq\mathbb{R}^{n}$ and with metric

$d_{\mathbb{R}^{n}/L}(x,y)=\min_{v\in L}|x-y-v|.$

An $n$-dimensional lattice is a discrete subgroup of $(\mathbb{R}^{n},+)$
consisting of all integral linear combinations of a basis of $\mathbb{R}^{n}$.
Furthermore, $|\cdot|$ denotes the standard norm of $\mathbb{R}^{n}$ given by
$|x|=\sqrt{x^{\sf T}x}$.

A Euclidean embedding of $\mathbb{R}^{n}/L$ is an injective function
$\varphi\colon\mathbb{R}^{n}/L\to H$ mapping the flat torus $\mathbb{R}^{n}/L$
into some (complex) Hilbert space $H$. The _distortion_ of $\varphi$ is

$\operatorname{dist}(\varphi)=\sup_{\begin{subarray}{c}x,y\in\mathbb{R}^{n}/L\\\
x\neq
y\end{subarray}}\frac{\|\varphi(x)-\varphi(y)\|}{d_{\mathbb{R}^{n}/L}(x,y)}\cdot\sup_{\begin{subarray}{c}x,y\in\mathbb{R}^{n}/L\\\
x\neq
y\end{subarray}}\frac{d_{\mathbb{R}^{n}/L}(x,y)}{\|\varphi(x)-\varphi(y)\|},$

where $\|\cdot\|$ is the norm of the Hilbert space $H$. Here the first
supremum is called the _expansion_ of $\varphi$ and the second supremum is the
_contraction_ of $\varphi$. When we minimize the distortion of $\varphi$ over
all possible embeddings of $\mathbb{R}^{n}/L$ into Hilbert spaces we speak of
the _least (Euclidean) distortion_ of the flat torus; it is denoted by

$c_{2}(\mathbb{R}^{n}/L)=\inf\\{\operatorname{dist}(\varphi)\;:\;\varphi\colon\mathbb{R}^{n}/L\to
H\text{ for some Hilbert space }H,\;\varphi\text{ injective}\\}.$

Similarly one can define $c_{1}(\mathbb{R}^{n}/L)$ by replacing the Hilbert
space by some $L_{1}$ space.

Khot and Naor showed (see [11, Corollary 4]) that flat tori can be highly non-
Euclidean in the sense that there is a family of flat tori
$\mathbb{R}^{n}/L_{n}$ with

(1) $c_{2}(\mathbb{R}^{n}/L_{n})=\Omega(\sqrt{n}).$

On the other hand, they noticed (see [11, Remark 5]) that the standard
embedding of the standard flat torus $\mathbb{R}^{n}/\mathbb{Z}^{n}$ embeds
into $\mathbb{R}^{2n}$ with distortion $O(1)$111In fact, we have
$\operatorname{dist}(\varphi)=\pi/2$ and $\varphi$ is an optimal embedding,
see Theorem 6.1.. The standard embedding is given by

(2) $\varphi(x_{1},\ldots,x_{n})=(\cos 2\pi x_{1},\sin 2\pi x_{1},\ldots,\cos
2\pi x_{n},\sin 2\pi x_{n}).$

In fact, Khot and Naor are mainly concerned with bounding
$c_{1}(\mathbb{R}^{n}/L)$, which immediately provides bounds for
$c_{2}(\mathbb{R}^{n}/L)$ because $c_{1}(\mathbb{R}^{n}/L)\leq
c_{2}(\mathbb{R}^{n}/L)$. To state their main result, leading to (1), we make
use of the Voronoi cell of $L$, which is an $n$-dimensional polytope defined
as

$V(L)=\\{x\in\mathbb{R}^{n}:|x|\leq|x-v|\text{ for all }v\in L\\}.$

The Voronoi cell is a fundamental domain of $\mathbb{R}^{n}/L$ under the
action of $L$. We denote the volume of $V(L)$ by $\operatorname{vol}L$.
Clearly, $|x|=d_{\mathbb{R}^{n}/L}(x,0)$ for all $x\in V(L)$. The covering
radius of $L$ is $\mu(L)=\max\\{|x|:x\in V(L)\\}$, which is the circumradius
of $V(L)$. The length of a shortest vector of $L$ is
$\lambda(L)=\min\\{|v|:v\in L\setminus\\{0\\}\\}$ that is two times the
inradius of $V(L)$. Now the main result (see [11, Theorem 5]) is

(3)
$c_{1}(\mathbb{R}^{n}/L)=\Omega\left(\frac{\lambda(L^{*})\sqrt{n}}{\mu(L^{*})}\right).$

Here, as usual, $L^{*}=\\{u\in\mathbb{R}^{n}:u^{\sf T}v\in\mathbb{Z}\text{ for
all }v\in L\\}$ denotes the dual lattice of $L$. They also give an alternative
proof of their main result for $c_{2}(\mathbb{R}^{n}/L)$ (see [11, Lemma 11]).
The main result leads to the lower bound (1) when plugging in duals of
lattices which simultaneously provide dense packings and economical coverings.
Such a family of lattices exist by a theorem of Butler [5].

Using Korkine-Zolotarev reduction Khot and Naor determine an embedding of
$\mathbb{R}^{n}/L$ into $\mathbb{R}^{2n}$ with distortion $O(n^{3n/2})$ (see
[11, Theorem 6]).

Haviv and Regev [10, Theorem 1.3] found an improved embedding that yields
$c_{2}(\mathbb{R}^{n}/L)=O(n\sqrt{\log n})$. They also improved on (3) and
showed in [10, Theorem 1.5] that for any $n$-dimensional lattice $L$ we have

(4) $c_{2}(\mathbb{R}^{n}/L)\geq\frac{\lambda(L^{*})\mu(L)}{4\sqrt{n}},$

which improves on (3) because $\mu(L)\mu(L^{*})\geq\Omega(n)$ holds for every
$n$-dimensional lattice. This follows from a simple volume argument giving
$\mu(L)=\Omega(\sqrt{n}(\operatorname{vol}L)^{1/n})$ and
$\operatorname{vol}L^{*}=(\operatorname{vol}L)^{-1}$.

Recently, Agarwal, Regev, Tang [2] constructed excellent embeddings of flat
tori having low distortion and showed that the lower bound (1) is nearly
tight: For every lattice $L\subseteq\mathbb{R}^{n}$ there exists an embedding
of $\mathbb{R}^{n}/L$ into Hilbert space with distortion $O(\sqrt{n\log n})$.

###  1.2. Aim and method

In this paper we want to add a semidefinite optimization perspective to this
story.

For finite metric spaces it is known that one can compute least distortion
Euclidean embeddings via a semidefinite program (SDP), which is linear
optimization over the cone of positive semidefinite matrices. We want to
extend this result from finite metric spaces to flat tori. This will yield,
via semidefinite programming duality, an algorithmic method for proving
nonembeddability results. In particular, this leads to a new, simple proof of
(4). In fact we even get a constant factor improvement that is tight in the
case of the standard torus.

First we recall the semidefinite program for finding least Euclidean
distortion embeddings of finite metric spaces. Suppose we consider a finite
metric space $X$ with distance function $d$. Then, as first observed by
Linial, London, Rabinovich [15], we can find a least distortion embedding of
$(X,d)$ into a Hilbert space algorithmically by solving the following
semidefinite program

(5) $\begin{split}\min\\{C\;:\;&C\in\mathbb{R}_{+},Q\in\mathcal{S}^{X}_{+},\\\
&d(x,y)^{2}\leq Q_{xx}-2Q_{xy}+Q_{yy}\leq Cd(x,y)^{2}\text{ for all }x,y\in
X\\},\end{split}$

where $\mathcal{S}^{X}_{+}$ denotes the convex cone of positive semidefinite
matrices whose rows and columns are indexed by the elements of $X$. The
optimal solution $C$ of this semidefinite program equals $c_{2}(X,d)^{2}$ and
if $Q$ attains the optimal solution, then we can determine a least distortion
embedding $\varphi:X\to\mathbb{R}^{X}$ with the property
$\varphi(x)\cdot\varphi(y)=Q_{xy}$ by considering a Cholesky decomposition of
$Q$.

This shows how to compute (in fact in polynomial time) an optimal Euclidean
embedding of a finite metric space. Another benefit of this formulation is
that we can apply duality theory of semidefinite programs. Then the dual
maximization problem will play a key role to determine lower bounds for
$c_{2}(X,d)$. By using strong duality we arrive at the following result: The
least distortion of a finite metric space $(X,d)$, with
$X=\\{x_{1},\ldots,x_{n}\\}$, into Euclidean space is given by

(6)
$c_{2}(X,d)^{2}=\max\left\\{\frac{\sum_{i,j=1:Y_{ij}>0}^{n}Y_{ij}d(x_{i},x_{j})^{2}}{-\sum_{i,j=1:Y_{ij}<0}^{n}Y_{ij}d(x_{i},x_{j})^{2}}:Y\in\mathcal{S}^{n}_{+},Y\mathbf{e}=0\right\\}.$

The condition $Y\mathbf{e}=0$ says that the all-ones vector $\mathbf{e}$ lies
in the kernel of $Y$. A proof of this result is detailed in Matoušek [18] or
in Laurent, Vallentin [14].

This lower bound has been extensively used to determine the least distortion
Euclidean embeddings of the shortest path metric of several graph classes.
Linial, Magen [16] computed least distortion embeddings of products of cycles
and of expander graphs. Least distortion Euclidean embeddings of strongly
regular graphs and of more general distance regular graphs were first
considered by Vallentin [20]. This was further extended by Kobayashi, Kondo
[12], Cioabă, Gupta, Ihringer, Kurihara [6]. Linial, Magen, Naor [17]
considered graphs of high girth using this approach.

To apply the bound (6) one has to construct a matrix $Y$, which sometimes
appears to come out of the blue. By complementary slackness, which is the same
as analyzing the case of equality in the proof of weak duality, we get hints
where to search for an appropriate matrix $Y$: If $Y$ is an optimal solution
of the maximization problem (6), then $Y_{ij}>0$ only for the _most contracted
pairs_. These are pairs $(x_{i},x_{j})$ for which
$\frac{d(x_{i},x_{j})}{\|f(x_{i})-f(x_{j})\|}$ is maximized. Similarly, then
$Y_{ij}<0$ only for the _most expanded pairs_ , maximizing
$\frac{\|f(x_{i})-f(x_{j})\|}{d(x_{i},x_{j})}$.

Linial, Magen [16] realized that for graphs most expanded pairs are simply
adjacent vertices. However, most contracted pairs are more mysterious and
there is no characterization known. The first intuition that the largest
contraction occurs at pairs at maximum distance is wrong in general.

###  1.3. Contribution and structure of the paper

In Section 2 of this paper we derive a new infinite-dimensional semidefinite
program for determining a least distortion embedding of flat tori into Hilbert
spaces which is analogous to (5). It is given in Theorem 2.1 where we
additionally apply symmetry reduction techniques in the spirit of [3] to
reduce the original infinite-dimensional SDP into an infinite-dimensional
linear program that involves Fourier analysis. Then we realize that in a
Euclidean embedding of a flat torus there are no most expanded pairs: The
expansion is only attained in the limit by pairs whose distance tends to zero.
This is in perfect analogy to the graph case where the most expanded pairs are
also attained at minimal distance. This insight has the advantage that in the
infinite dimensional linear program some of the infinitely many constraints
can be replaced by only one finite-dimensional semidefinite constraint. This
is the content of Theorem 2.4. Its dual program is derived in Theorem 2.5
which is analogous to (6).

In Section 3 we further investigate the properties of the optimization
problems given in Theorem 2.4 and Theorem 2.5. These properties will be used
in the next sections.

In the last sections we apply our new methodology. In Section 4 we prove that
an $n$-dimensional flat torus always admits a finite dimensional least
distortion embedding, a space of (complex) dimension $2^{n}-1$ suffices.
Section 5 contains a new and simple proof of our constant factor improvement
of the lower bound given in (4). In Section 6 we show that the standard
embedding (2) of the standard torus is indeed optimal and has distortion
$\pi/2$. In Section 7 we determine least distortion embeddings of all two-
dimensional flat tori. A few open questions are discussed in Section 8.

##  2\. An infinite-dimensional SDP

Starting from (5) we want to derive a similar, but now infinite-dimensional,
semidefinite program which can be used to determine $c_{2}(\mathbb{R}^{n}/L)$.

###  2.1. Primal program

The first step is to apply a classical theorem of Moore [19] which enables us
to optimize over all embeddings $\varphi:\mathbb{R}^{n}/L\to H$ into some
Hilbert space $H$. In our situation Moore’s theorem says that there exists a
(complex) Hilbert space $H$ and a map $\varphi:\mathbb{R}^{n}/L\to H$ if and
only if there is a positive definite kernel222A kernel $Q$ is called positive
definite if and only if for all $N\in\mathbb{N}$ and for all
$x_{1},\ldots,x_{N}\in\mathbb{R}^{n}/L$ the matrix $(Q(x_{i},x_{j}))_{1\leq
i,j\leq\mathbb{N}}\in\mathbb{C}^{N\times N}$ is Hermitian and positive
semidefinite. This naming convention is unfortunate but for historical reasons
unavoidable.

$Q:\mathbb{R}^{n}/L\times\mathbb{R}^{n}/L\to\mathbb{C}\;\text{ such that
}\;Q(x,y)=(\varphi(x),\varphi(y))\text{ for all }x,y\in\mathbb{R}^{n}/L,$

where $(\cdot,\cdot)$ denotes the inner product of $H$. Therefore we get

$\begin{split}c_{2}(\mathbb{R}^{n}/L)^{2}=\inf\\{C\;:\;&C\in\mathbb{R}_{+},Q\text{
positive definite},\\\
&\begin{array}[]{rcl}d_{\mathbb{R}^{n}/L}(x,y)^{2}&\leq&Q(x,x)-2\Re(Q(x,y))+Q(y,y)\\\
&\leq&Cd_{\mathbb{R}^{n}/L}(x,y)^{2}\;\text{ for all
}x,y\in\mathbb{R}^{n}/L\\}.\end{array}\end{split}$

Here we scaled the embedding $\varphi$ which is defined through $Q$ so that
the contraction of $\varphi$ equals $1$. The real part $\Re(Q)$ of a positive
definite kernel is positive definite again and we can restrict to real-valued
positive definite kernels for determining $c_{2}(\mathbb{R}^{n}/L)$.

For the second step we apply a standard group averaging argument. If $Q$ is a
feasible solution for the minimization problem above, so is its group average

$\overline{Q}(x,y)=\frac{1}{\operatorname{vol}(\mathbb{R}^{n}/L)}\int_{\mathbb{R}^{n}/L}Q(x-z,y-z)\,dz.$

By this averaging the kernel $\overline{Q}$ becomes continuous and only
depends on the difference $x-y$. Thus, instead of minimizing over positive
definite kernels $Q$ it suffices to minimize over continuous, real functions
$f\colon\mathbb{R}^{n}/L\to\mathbb{R}$ which are of positive type, i.e. the
kernel $(x,y)\mapsto f(x-y)$ is positive definite; see also the proof of
Theorem 3.1 in the paper [1] by Aharoni, Maurey, Mityagin.

For the convenience of the reader we provide the argument why the positive
type function $f(x)=\overline{Q}(x,0)$ is continuous: For every $x$, $y$ the
matrix

$\begin{pmatrix}f(0)&f(x)&f(x+y)\\\ f(x)&f(0)&f(y)\\\
f(x+y)&f(y)&f(0)\end{pmatrix}$

is positive semidefinite and it is congruent (simultaneously subtract the
second row/column of the third row/column) to the positive semidefinite matrix

$\begin{pmatrix}f(0)&f(x)&f(x+y)-f(x)\\\ f(x)&f(0)&f(y)-f(0)\\\
f(x+y)-f(x)&f(y)-f(0)&2f(0)-2f(y)\end{pmatrix}$

Taking the minor of the first and third row/column gives

$2f(0)(f(0)-f(y))\geq(f(x+y)-f(x))^{2}.$

This inequality implies that $f$ is continuous at every $x$ if and only if $f$
is continuous at $0$. Then $f$ is continuous at $0$ because it satisfies the
constraint

$d_{\mathbb{R}^{n}/L}(0,y)^{2}\leq\overline{Q}(0,0)-2\overline{Q}(0,y)+\overline{Q}(y,y)=2(f(0)-f(y))\leq
Cd_{\mathbb{R}^{n}/L}(0,y)^{2}$

for every $y$.

Note that also $(x,y)\mapsto d_{\mathbb{R}^{n}/L}(x,y)^{2}$ only depends on
the difference $x-y$. So we can replace $(x,y)$ by $(x-y,0)$ and we can move
$x-y$ by a lattice vector translation into the Voronoi cell $V(L)$. Hence,

$\begin{split}c_{2}(\mathbb{R}^{n}/L)^{2}=\inf\\{C\;:\;&C\in\mathbb{R}_{+},f\colon\mathbb{R}^{n}/L\to\mathbb{R}\text{
continuous and of positive type},\\\ &|x|^{2}\leq 2(f(0)-f(x))\leq
C|x|^{2}\;\text{ for all }x\in V(L)\\}.\end{split}$

In the third step we parametrize continuous positive type functions by the
Fourier coefficients using Bochner’s theorem, cf. Folland [9, (4.18)], which
says that a continuous function $f:\mathbb{R}^{n}/L\to\mathbb{C}$ is of
positive type if and only if all its Fourier coefficients

$\widehat{f}(u)=\int_{\mathbb{R}^{n}/L}f(x)e^{-2\pi iu^{\sf T}x}\,dx,$

with $u\in L^{*}$ are nonnegative and $\widehat{f}$ lies in

$\ell^{1}(L^{*})=\left\\{z\colon L^{*}\to\mathbb{C}:\sum_{u\in
L^{*}}|z(u)|<\infty\right\\}.$

Then if $f$ is real, continuous and of positive type we have the
representation

$f(x)=\sum_{u\in L^{*}}\widehat{f}(u)e^{2\pi iu^{\sf T}x},$

where the convergence is absolute and uniform, with
$\widehat{f}\in\ell^{1}(L^{*})$, $\widehat{f}(u)\geq 0$ and
$\widehat{f}(u)=\widehat{f}(-u)$ for all $u\in L^{*}$. Thus,

$f(x)=\sum_{u\in L^{*}}\widehat{f}(u)\cos(2\pi u^{\sf T}x).$

Writing $f$ in this form, one can express $c_{2}(\mathbb{R}^{n}/L)^{2}$ as an
infinite-dimensional linear program:

######  Theorem 2.1.

The least distortion Euclidean embedding of a flat torus $\mathbb{R}^{n}/L$ is
given by

(7)
$\begin{split}c_{2}(\mathbb{R}^{n}/L)^{2}=\inf\big{\\{}C\;:\;&C\in\mathbb{R}_{+},z\in\ell^{1}(L^{*}),z(u)=z(-u)\geq
0\text{ for all }u\in L^{*},\\\ &|x|^{2}\leq 2\sum_{u\in
L^{*}}z(u)(1-\cos(2\pi u^{\sf T}x))\leq C|x|^{2}\\\ &\quad\text{ for all }x\in
V(L)\big{\\}}.\end{split}$

A feasible solution of the above minimization problem $(C,z)$ determines a
Euclidean embedding $\varphi$ of $\mathbb{R}^{n}/L$ with distortion
$dist(\varphi)\leq\sqrt{C}$ by

(8) $\varphi:\mathbb{R}^{n}/L\to\ell^{2}(L^{*}),\quad
x\mapsto\left(\sqrt{z(u)}e^{2\pi iu^{\sf T}x}\right)_{u\in L^{*}},$

with complex Hilbert space

$\ell^{2}(L^{*})=\left\\{z:L^{*}\to\mathbb{C}:\left(\sum_{u\in
L^{*}}|z(u)|^{2}\right)^{1/2}<\infty\right\\}.$

######  Remark 2.2.

The $\inf$ in (7) is in fact a $\min$ because the set of bounded continuous
functions of positive type is weak* compact due to the Banach-Alaoglu theorem;
see for example Folland [9, Chapter 3.3].

It is worth to mention that the embedding $\varphi$ of Theorem 2.1 embeds the
flat torus $\mathbb{R}^{n}/L$ into a direct product of circles

$\prod_{u\in
L^{*}}\sqrt{z(u)}S^{1}\quad\text{with}\quad\|\varphi(x)\|^{2}=\sum_{u\in
L^{*}}z(u)\text{ for all }x\in L.$

The support of $z$ contains a basis of $L^{*}$ since the embedding is
injective. Using the fact $z(u)=z(-u)$ we could also use the real embedding
$\varphi^{\prime}$ with

$[\varphi^{\prime}(x)]_{u}=\sqrt{z(u)}(\cos 2\pi u^{\sf T}x,\sin 2\pi u^{\sf
T}x),$

where $u$ runs through $L^{*}/\\{\pm 1\\}$ and which has the same distortion
as $\varphi$.

On the other hand, the constraint $z(u)=z(-u)$ is clearly redundant in the
minimization problem of Theorem 2.1.

Now we want to simplify the infinitely many inequalities

(9) $2\sum_{u\in L^{*}}z(u)(1-\cos(2\pi u^{\sf T}x))\leq C|x|^{2}\text{ for
all }x\in V(L),$

which occur in (7), by only one finite-dimensional semidefinite condition. For
this we observe that in any embedding there are no most expanded pairs: the
corresponding supremum
$\sup\left\\{\frac{\|\varphi(x)-\varphi(y)\|}{d_{\mathbb{R}^{n}/L}(x,y)}:x,y\in\mathbb{R}^{n}/L,x\neq
y\right\\}$ is only attained by a limit of pairs whose distance tends to $0$.

######  Lemma 2.3.

Let $L\subseteq\mathbb{R}^{n}$ be an $n$-dimensional lattice. Let $(C,z)$ be
as in (7). Inequality (9) is satisfied if and only if

(10) $4\pi^{2}\sum_{u\in L^{*}}z(u)(u^{\sf T}x)^{2}\leq C|x|^{2}\text{ for all
}x\in\mathbb{R}^{n}.$

Note that (9) holds for all $x\in\mathbb{R}^{n}$.

###### Proof.

By the cosine double angle formula $1-\cos(\alpha)=2\sin(\alpha/2)^{2}$ and by
the inequality $|\sin(\alpha)|\leq|\alpha|$ we have

$2\sum_{u\in L^{*}}z(u)(1-\cos(2\pi u^{\sf T}x))\leq 4\pi^{2}\sum_{u\in
L^{*}}z(u)(u^{\sf T}x)^{2}.$

Thus, (10) implies (9).

Conversely, assume that (10) is not satisfied. There exists
$x^{*}\in\mathbb{R}^{n}$ with

$4\pi^{2}\sum\limits_{u\in L^{*}}z(u)(u^{\sf T}x^{*})^{2}>C|x^{*}|^{2}.$

For $r\geq 0$ define the function

$f(r)=2\sum_{u\in L^{*}}z(u)(1-\cos(2\pi u^{\sf T}(rx^{*})))-C|rx^{*}|^{2}$

and consider its Taylor expansion

$f(r)=\left(4\pi^{2}\sum\limits_{u\in L^{*}}z(u)(u^{\sf
T}x^{*})^{2}-C|x^{*}|^{2}\right)r^{2}+\text{h.o.t. }(\text{in }r)$

Writing $f$ this way and using the assumption, $f(r)$ is positive for
sufficiently small $r$. Thus, (9) is not satisfied. ∎

Inequality (10) can also be rewritten as an inequality of the largest
eigenvalue $\lambda_{\max}$ of a corresponding matrix

$\lambda_{\max}\left(4\pi^{2}\sum\limits_{u\in L^{*}}z(u)uu^{\sf T}\right)\leq
C$

or equivalently as a semidefinite condition

$CI-4\pi^{2}\sum\limits_{u\in L^{*}}z(u)uu^{\sf T}\in\mathcal{S}_{+}^{n},$

where $I$ denotes the identity matrix. With this lemma we arrive at the
following simplification of (7).

######  Theorem 2.4.

The least distortion Euclidean embedding of a flat torus $\mathbb{R}^{n}/L$ is
given by

(11)
$\begin{split}c_{2}(\mathbb{R}^{n}/L)^{2}=\inf\big{\\{}C\;:\;&C\in\mathbb{R}_{+},z\in\ell^{1}(L^{*}),z(u)=z(-u)\geq
0\text{ for all }u\in L^{*},\\\ &|x|^{2}\leq 2\sum_{u\in
L^{*}}z(u)(1-\cos(2\pi u^{\sf T}x))\text{ for all }x\in V(L),\\\
&CI-4\pi^{2}\sum_{u\in L^{*}}z(u)uu^{\sf
T}\in\mathcal{S}^{n}_{+}\big{\\}}.\end{split}$

###  2.2. Dual program

We derive the dual of (11) to systematically find lower bounds for
$c_{2}(\mathbb{R}^{n}/L)$.

######  Theorem 2.5.

Suppose that $(C,z)$ is feasible for (11), then

(12) $\begin{split}C\geq
c_{2}(\mathbb{R}^{n}/L)^{2}\geq\sup\big{\\{}&2\pi^{2}\int_{V(L)}|x|^{2}\,d\nu(x)\;:\\\
&\quad\nu\in\mathcal{M}_{+}(V(L)),Y\in\mathcal{S}^{n}_{+},\operatorname{Tr}(Y)=1,\\\
&\quad\int_{V(L)}(1-\cos(2\pi u^{\sf T}x))\,d\nu(x)\leq u^{\sf T}Yu\\\
&\qquad\text{ for all }u\in L^{*}\big{\\}},\end{split}$

where $\mathcal{M}_{+}(V(L))$ is the cone of Borel measures supported on
$V(L)$. In (12) equality holds for a feasible $(\nu,Y)$ if and only if

$\left(CI-4\pi^{2}\sum_{u\in L^{*}}z(u)uu^{\sf T}\right)Y=0,$

and the measure $\nu$ is only supported on vectors $x\in V(L)$ for which
equality

$|x|^{2}=2\sum_{u\in L^{*}}z(u)(1-\cos(2\pi u^{\sf T}x))$

holds, and for all vectors $u\in L^{*}$ with $z(u)\neq 0$ we have

$\int_{V(L)}(1-\cos(2\pi u^{\sf T}x))\,d\nu(x)=u^{\sf T}Yu.$

###### Proof.

For two symmetric matrices $A,B$ we define $\langle
A,B\rangle=\operatorname{Tr}(AB)$. Using the feasibility of $(C,z)$ and
$(\nu,Y)$ we get

$\displaystyle C-2\pi^{2}\int_{V(L)}|x|^{2}\,d\nu(x)$ $\displaystyle\geq\;$
$\displaystyle\left\langle 4\pi^{2}\sum_{u\in L^{*}}z(u)uu^{\sf
T},Y\right\rangle-4\pi^{2}\int_{V(L)}\sum_{u\in L^{*}}z(u)(1-\cos(2\pi u^{\sf
T}x))\,d\nu(x)$ $\displaystyle=\;$ $\displaystyle 4\pi^{2}\sum_{u\in
L^{*}}z(u)\left(\langle uu^{\sf T},Y\rangle-\int_{V(L)}(1-\cos(2\pi u^{\sf
T}x))\,d\nu(x)\right)$ $\displaystyle\geq\;$ $\displaystyle 0.$

When analyzing the case of equality we find the three conditions of the
theorem. ∎

######  Remark 2.6.

As a side note we would like to mention that in (12) we even have equality
$c_{2}(\mathbb{R}^{n}/L)^{2}=\sup$. This follows again by the weak*
compactness of the set of bounded, continuous functions of positive type
together with the Hahn-Banach (strict) separation theorem.

##  3\. Properties and observations

We collect some results that are consequences of the primal and dual
formulation of the preceding section, including some auxiliary results used in
later sections.

###  3.1. Subquadratic inequality

First, we show that the functions of the form

(13) $f(x)=2\sum_{u\in L^{*}}z(u)(1-\cos(2\pi u^{\sf T}x))\text{ with
}z(u)\geq 0$

are subquadratic, this auxiliary result is going to be used a number of times.
Note that we have

$f(x-y)=\|\varphi(x)-\varphi(y)\|^{2}$

for the embedding $\varphi$ in (8). Suppose for a moment that $\varphi$ was an
isometry, then $f$ would satisfy the parallelogram law

$f(x-y)+f(x+y)=2f(x)+2f(y)$

and it would be a homogeneous quadratic form

$f(\lambda x)=\lambda^{2}f(x).$

However, $\varphi$ cannot be a Hilbert space isometry, but the next lemma
shows that we have at least two inequalities.

######  Lemma 3.1.

The function $f$ defined in (13) is subquadratic, i.e. it satisfies

(14) $f(x+y)+f(x-y)\leq 2f(x)+2f(y)\quad\text{for all }x,y\in\mathbb{R}^{n}.$

Furthermore,

(15) $f(\lambda x)\leq\lambda^{2}f(x)\quad\text{for all
}\lambda\in\mathbb{N},x\in\mathbb{R}.$

If $f$ defines an embedding, we have equality in (14) and (15) if and only if
$x$ or $y$ lie in $L$.

A proof for (15) can also be found in [13]; we provide it here for the
convenience of the reader.

###### Proof.

To show that $f$ is subquadratic it suffices to prove the inequality

$1-\cos(\alpha+\beta)+1-\cos(\alpha-\beta)\leq 2(1-\cos\alpha)+2(1-\cos\beta)$

for all $\alpha,\beta\in\mathbb{R}$. This is elementary by the cosine addition
formula:

$\begin{split}1-\cos(\alpha+\beta)+1-\cos(\alpha-\beta)&=\,2-2\cos\alpha\cos\beta\\\
&=\,2\cos\beta(1-\cos\alpha)+2(1-\cos\beta)\\\
&\leq\,2(1-\cos\alpha)+2(1-\cos\beta),\end{split}$

where equality holds if and only if $\alpha$ or $\beta$ is an integral
multiple of $2\pi$.

Now consider $f$ as in (13) and assume $f$ defines an embedding. Then the
claim about equality comes from the fact that $\alpha=2\pi u^{\sf T}x$ or
$\beta=2\pi u^{\sf T}y$ is an integral multiple of $2\pi$ for all
$u\in\operatorname{supp}(z)$ if and only if $x\in L$ or $y\in L$, since
$\operatorname{supp}(z)$ contains a basis of $L^{*}$.

For even $\lambda$ we directly use (14)

$\begin{split}f(\lambda
x)&=\,f\left(\frac{\lambda}{2}x+\frac{\lambda}{2}x\right)+f\left(\frac{\lambda}{2}x-\frac{\lambda}{2}x\right)\\\
&\,\leq 4\left(\frac{\lambda}{2}\right)^{2}f(x)=\lambda^{2}f(x)\end{split}$

since $f(0)=0$. For odd $\lambda\geq 3$ we use (14) and proceed by induction

$\begin{split}f(\lambda
x)+f(x)&=\,f\left(\left(\frac{\lambda-1}{2}+1\right)x+\frac{\lambda-1}{2}x\right)+f\left(\left(\frac{\lambda-1}{2}+1\right)x-\frac{\lambda-1}{2}x\right)\\\
&\leq\,2f\left(\left(\frac{\lambda-1}{2}+1\right)x\right)+2f\left(\frac{\lambda-1}{2}x\right)\\\
&\leq\,2\left(\left(\frac{\lambda-1}{2}+1\right)^{2}+\left(\frac{\lambda-1}{2}\right)^{2}\right)f(x)\\\
&=\,\lambda^{2}f(x)+f(x).\end{split}$

∎

###  3.2. Dual feasibility

In general the dual program (12) has infinitely many conditions of the form

(16) $\displaystyle\int_{V(L)}(1-\cos(2\pi v^{\sf
T}x))\,d\nu(x)\leq\operatorname{Tr}(vv^{\sf T}Y),\qquad v\in L^{*}.$

We will now show that sometimes already finitely many constraints are
sufficient to imply all conditions (16). The first observation is the
following:

######  Lemma 3.2.

Let $q_{a}(x)=1-\cos(2\pi a^{\sf T}x)$. The (in-)equalities

(17) $\displaystyle\int_{V(L)}q_{a}(x)\,d\nu(x)$
$\displaystyle\leq\operatorname{Tr}(aa^{\sf
T}Y),\quad\int_{V(L)}q_{b}(x)\,d\nu(x)\leq\operatorname{Tr}(bb^{\sf T}Y),$
(18) $\displaystyle\int_{V(L)}q_{a-b}(x)\,d\nu(x)$
$\displaystyle=\operatorname{Tr}((a-b)(a-b)^{\mathsf{T}}Y)$

imply

$\displaystyle\int_{V(L)}q_{a+b}(x)\,d\nu(x)\leq\operatorname{Tr}((a+b)(a+b)^{\mathsf{T}}Y).$

The corresponding result also holds when $q_{a-b}$ and $q_{a+b}$ are
interchanged.

###### Proof.

As shown in the proof of Lemma 3.1, the function $q_{a}$ is subquadratic and
therefore

$\displaystyle\int_{V(L)}q_{a+b}(x)\,d\nu(x)+\int_{V(L)}q_{a-b}(x)\,d\nu(x)$
$\displaystyle\leq 2\int_{V(L)}q_{a}(x)+q_{b}(x)\,d\nu(x)$ $\displaystyle\leq
2\operatorname{Tr}(aa^{\mathsf{T}}Y)+2\operatorname{Tr}(bb^{\mathsf{T}}Y),$

which by (18) is equivalent to

$\displaystyle\int_{V(L)}q_{a+b}(x)\,d\nu(x)$ $\displaystyle\leq
2\operatorname{Tr}(aa^{\mathsf{T}}Y)+2\operatorname{Tr}(bb^{\mathsf{T}}Y)-\operatorname{Tr}((a-b)(a-b)^{\mathsf{T}}Y)$
$\displaystyle=\operatorname{Tr}((a+b)(a+b)^{\mathsf{T}}Y).\qed$

The above lemma can be used to replace the infinitely many constraints (16) by
finitely many using the shortest vectors in cosets of the form $v+2L^{*}$ for
$v\in L^{*}$.

The proof of the lemma relies on a characterization of _Voronoi vectors_.
These are lattice vectors $v\in L\setminus\\{0\\}$ such that the set
$F_{v}:=V(L)\cap\\{x\,:\,v^{\mathsf{T}}x\leq\frac{1}{2}v^{\mathsf{T}}v\\}$
defines a non-empty face of $V(L)$. Moreover, $v\in L$ is called _Voronoi
relevant_ if $F_{v}$ is a facet of $V(L)$, i.e. an $(n-1)$-dimensional face of
$V(L)$.

An element $v\in L\setminus\\{0\\}$ is a Voronoi vector of $V(L)$ if and only
if $\pm v$ are shortest vectors in the coset $v+2L$ and $\pm v$ are Voronoi
relevant if and only if they are the _only_ shortest vectors in $v+2L$. For a
proof see [7, Chapter 21, Theorem 10] and [8, Theorem 2].

######  Lemma 3.3.

If (16) is tight for at least one shortest vector in each coset of the form
$v+2L^{*},\,v\in L^{*}$, then (16) holds for all $v\in L^{*}$.

###### Proof.

Assume that (16) is tight for at least one shortest vector in each coset
$v+2L^{*}$. We will first prove by induction that (16) also holds for all
Voronoi vectors.

The statement holds by assumption for all Voronoi relevant vectors $v$ because
in this case the normal vectors $v$ and $-v$ are the only shortest vectors in
$v+2L^{*}$ due to the above characterization.

So assume that the statement holds for all vectors $u\in L^{*}$ such that
$F_{u}$ is a face of dimension smaller than $n-k$. Now consider $v\in L^{*}$
such that $v$ is the normal vector of some $(n-(k+1))$-dimensional face of
$V(L^{*})$ with $k\geq 2$. Further, assume that $u\in v+2L^{*}$ with $u\neq v$
is such that (16) is tight for $u$ (otherwise there is nothing to show for
$v$).

Now $\frac{1}{2}(u\pm v)\in L^{*}$ and the inequality
$v^{\mathsf{T}}x\leq\frac{1}{2}v^{\mathsf{T}}v$ for all $x\in V(L^{*})$ is
implied by

$\displaystyle\frac{1}{2}(u+v)^{\mathsf{T}}x+\frac{1}{2}(u-v)^{\mathsf{T}}x$
$\displaystyle\;\leq\;\frac{1}{4}(u+v)^{\mathsf{T}}(u+v)+\frac{1}{4}(u-v)^{\mathsf{T}}(u-v)$
$\displaystyle\;\leq\;\frac{1}{4}u^{\mathsf{T}}u+\frac{1}{4}v^{\mathsf{T}}v\;\leq\;\frac{1}{2}v^{\mathsf{T}}v.$

Due to $u\neq v$ and the above inequality, the sets
$F_{\frac{1}{2}(u+v)},F_{\frac{1}{2}(u-v)}$ define non-empty faces of
$V(L^{*})$ of dimension strictly larger than $n-(k+1)$. Hence, (16) holds for
$\frac{1}{2}(u+v),\frac{1}{2}(u-v)$ by the induction hypothesis. Applying
Lemma 3.2 (with $a=\frac{1}{2}(u+v),\,b=\frac{1}{2}(u-v),\,a+b=u$) shows that
(16) also holds for $v$.

Now assume that $v$ is a not a Voronoi vector. Then there exists a a shortest
vector $u\in v+2L^{*}$ for which (16) is tight and $|u|<|v|$.

Then, again $\frac{1}{2}(u\pm v)\in L^{*}$ and as

$\displaystyle|\frac{1}{2}(u\pm v)|\leq\frac{1}{2}(|u|+|v|)<|v|,$

we can argue by an analogous inductive argument (based on the norm) as before
that (16) holds for $\frac{1}{2}(u\pm v)$. Finally, we can use Lemma 3.2 to
infer that (16) is valid for $v$ as well. ∎

##  4\. Least Euclidean distortion embeddings always have finite dimension

The goal of this section is to prove that for every $n$-dimensional lattice,
there always exists a least distortion embedding of $\mathbb{R}^{n}/L$ that is
finite-dimensional. In the sense of Theorem 2.1, this means that there is
always an optimal solution $(C,z)$ for (11) such that the support of $z$ is
finite.

Additionally, our arguments will reveal that the constructed optimal solution
with finite support has only support on at most one vector per coset
$v+2L^{*}$ of $L^{*}/2L^{*}$ and that $\operatorname{supp}(z)$ only contains
primitive lattice vectors. An element $v\in L$ is called _primitive_ for $L$
if $\alpha v\in L$ with $\alpha\in\mathbb{Z}$ implies $\alpha=\pm 1$.

The first step towards proving that there is always a finite-dimensional least
Euclidean distortion embedding is the following observation.

######  Lemma 4.1.

Assume that $(C,z)$ is a solution for (11).

  1. (1)

If there are $u,v\in\operatorname{supp}(z),\,u\neq v$ with $u\pm v\in 2L^{*}$
and $z(v)\leq z(u)$, then $(C,\tilde{z})$ with

$\displaystyle\tilde{z}(t)=\begin{cases}z(u)-z(v),&\text{if }t=\pm u\\\
0,&\text{if }t=\pm v,\\\ 2z(v)+z(t),&\text{if }t\in\\{\frac{\pm u\pm
v}{2}\\},\\\ z(t),&\text{otherwise,}\end{cases}$

is a solution for (11).

  2. (2)

If there is $u\in\operatorname{supp}(z)$ and $u=kv$ for some integer $k\geq
2$, then $(C,\tilde{z})$ with

$\displaystyle\tilde{z}(t)=\begin{cases}0,&\text{if }t=\pm u,\\\
z(v)+k^{2}z(u),&\text{if }t=\pm v,\\\ z(t),&\text{otherwise,}\end{cases}$

is a solution for (11).

In both cases, $\tilde{z}$ satisfies

$\displaystyle\sum_{t\in L^{*}}z(t)tt^{\mathsf{\top}}=\sum_{t\in
L^{*}}\tilde{z}(t)tt^{\mathsf{\top}}\quad\text{and}\quad\sum_{t\in
L^{*}}z(t)<\sum_{t\in L^{*}}\tilde{z}(t).$

###### Proof.

(1) By construction, we have

$\sum_{t\in L^{*}}z(t)<\sum_{t\in L^{*}}z(t)+4z(v)=\sum_{t\in
L^{*}}\tilde{z}(t).$

Computing

$\displaystyle
z(u)uu^{\sf{\top}}+z(v)vv^{\sf{\top}}=(z(u)-z(v))uu^{\sf{\top}}+z(v)(uu^{\mathsf{\top}}+vv^{\mathsf{\top}})$
$\displaystyle=\,$
$\displaystyle(z(u)-z(v))uu^{\sf{\top}}+2z(v)\left(\left(\frac{u+v}{2}\right)\left(\frac{u+v}{2}\right)^{\mathsf{\top}}+\left(\frac{u-v}{2}\right)\left(\frac{u-v}{2}\right)^{\mathsf{\top}}\right),$

(and analogously for the pair $-u,-v$) we obtain $\sum_{t\in
L^{*}}z(t)tt^{\mathsf{\top}}=\sum_{t\in L^{*}}\tilde{z}(t)tt^{\mathsf{\top}}$
and $CI-4\pi^{2}\sum_{t\in
L^{*}}\tilde{z}(t)tt^{\mathsf{\top}}\in\mathcal{S}_{n}^{+}$.

Moreover, by the subquadratic inequality,

$\displaystyle 1-\cos(2\pi u^{\mathsf{\top}}x)+1-\cos(2\pi
v^{\mathsf{\top}}x)$ $\displaystyle=\,$ $\displaystyle
1-\cos\left(2\pi\left(\frac{u+v}{2}+\frac{u-v}{2}\right)^{\mathsf{\top}}x\right)+1-\cos\left(2\pi\left(\frac{u+v}{2}-\frac{u-v}{2}\right)^{\mathsf{\top}}x\right)$
$\displaystyle\leq\,$ $\displaystyle
2\left(1-\cos\left(2\pi\left(\frac{u+v}{2}\right)^{\mathsf{\top}}x\right)\right)+2\left(1-\cos\left(2\pi\left(\frac{u-v}{2}\right)^{\mathsf{\top}}x\right)\right).$

Thus, for every $x\in V(L)$

$\displaystyle|x|^{2}\leq 2\sum_{t\in L^{*}}z(t)(1-\cos(2\pi t^{\sf T}x))\leq
2\sum_{t\in L^{*}}\tilde{z}(t)(1-\cos(2\pi t^{\sf T}x)),$

implying that $(C,\tilde{z})$ is feasible for (11) with the desired
properties.

(2) The proof is analogous to (1). ∎

The lemma gives rise to an algorithmic way to transform a feasible solution
$(C,z)$ towards a solution $(C,\tilde{z})$ such that $\tilde{z}$ has only
support on at most one primitive lattice element per coset $u+2L^{*}$. Roughly
speaking, start with any solution and apply the above lemma “as long as
possible”, i.e. as long as there are pairs of vectors that satisfy (1) or (2)
of the above lemma.

######  Theorem 4.2.

For any $n$-dimensional lattice $L$, the torus $\mathbb{R}^{n}/L$ has a
finite-dimensional least Euclidean distortion embedding. In particular, the
program (11) has an optimal solution $(C,z)$ such that

  1. (1)

$|\operatorname{supp}(\tilde{z})\cap(v+2L^{*})|\leq 1$ for every coset
$v+2L^{*}$ of $L^{*}/2L^{*}$.

  2. (2)

Every $u\in\operatorname{supp}(z)$ is primitive in $L^{*}$.

Note that claim (1) shows that there are at most $2^{n}-1$ non-zero elements
in the support of $z$, therefore we obtain an embedding into a space of
dimension at most $2^{n}-1$.

###### Proof.

As a consequence of Remark 2.2, there is an optimal solution $(C,z_{0})$ with
$z_{0}\in\ell_{1}(L^{*})$ for (11). Our goal is to construct a sequence of
solutions $(C,z_{m})$ for (11) that converges to a solution that satisfies (1)
and (2). Let

(19) $\displaystyle A_{z}$ $\displaystyle=\\{\\{u,v\\}\,:\,u\neq-v,u\pm v\in
2L^{*},u,v\in\operatorname{supp}(z)\\}$

and let $(z_{m})_{m}$ be a sequence where $z_{m}$ is obtained from $z_{m-1}$
by applying transformation (1) of Lemma 4.1 to an arbitrary pair $\\{u,v\\}\in
A_{z}$ (the actual choice of the pair does not matter). Due to Lemma 4.1, the
pair $(C,z_{m})$ is feasible for (11) and we have

$\displaystyle\sum_{u\in L^{*}}z_{m}(u)uu^{\mathsf{\top}}=\sum_{u\in
L^{*}}z_{m+1}(u)uu^{\mathsf{\top}}\quad\text{and}\quad
Z_{m}<Z_{m+1}\quad\text{for all }m\in\mathbb{N},$

where $Z_{m}:=\sum_{u\in L^{*}}z_{m}(u)$. The sequence $Z_{m}$ is monotonously
increasing but bounded since $CI-4\pi^{2}\sum_{u\in
L^{*}}z_{m}(u)uu^{\mathsf{\top}}\in\mathcal{S}_{n}^{+}$ enforces that

$\displaystyle 0\leq\operatorname{Tr}\Big{(}CI-4\pi^{2}\sum_{u\in
L^{*}}z_{m}(u)uu^{\mathsf{\top}}\Big{)}$ $\displaystyle=Cn-4\pi^{2}\sum_{u\in
L^{*}}z_{m}(u)|u|^{2}$ $\displaystyle\leq Cn-4\pi^{2}\lambda(L^{*})\sum_{u\in
L^{*}}z_{m}(u).$

Hence, by monotone convergence, the sequence $Z_{m}$ converges.

Now we claim that $\lim_{m\to\infty}z_{m}(u)$ exists for all $u\in L^{*}$.
Therefore, assume that $\\{u_{m},v_{m}\\}\in A_{z_{m-1}}$ is chosen in the
iteration from $z_{m-1}$ to $z_{m}$. Assume that $z_{m-1}(u_{m})\geq
z_{m-1}(v_{m})$. Then, using Lemma 4.1, we obtain

$\displaystyle\sum_{u\in L^{*}}|z_{m}(u)-z_{m-1}(u)|=3\cdot
4z_{m-1}(v_{m})=3(Z_{m}-Z_{m-1}).$

The right hand side converges to zero, therefore the sequence $z_{m}$
converges pointwise, i.e. there is $z\in\ell_{1}(L^{*})$ such that

$\displaystyle\lim_{m\to\infty}z_{m}(u)=z(u)\quad\text{for all }u\in L^{*}.$

Next, we will show that $z$ satisfies (1), which is equivalent to
$A_{z}=\emptyset$. But this simply follows by construction: For every pair
$\\{u,v\\}\in A_{z_{m}}$ we have

$\displaystyle\lim_{m\to\infty}\min\\{z_{m}(u),z_{m}(v)\\}=0.$

This holds because if there was $\\{u,v\\}\in A_{z}$ and $\varepsilon>0$ such
that for all $M$ there was $m\geq M$ with
$\min\\{z_{m}(u),z_{m}(v)\\}\geq\varepsilon$, then according to the
construction of $z_{m}$ there would also be $m^{\prime}\geq m$ with

$\displaystyle Z_{m^{\prime}}-Z_{m}\geq 4\min\\{z_{m}(u),z_{m}(v)\\}\geq
4\varepsilon.$

This would be a contradiction to the convergence of the sequence $Z_{m}$.

Now, if there is $u\in\operatorname{supp}(z)$ with $u=kv$ for some $k\geq 2$,
we may apply (2) of Lemma 4.1 to obtain a new feasible solution $\tilde{z}$
with $v\in\operatorname{supp}(\tilde{z})$ and $z(u)=0$. This solution may
contain a pair $(u,v)\in A_{\tilde{z}}$. But in this case, we may again apply
(1) of Lemma 4.1.

By continuing like this, we will finally end up with a solution that has only
support on primitive vectors and on one vector per coset, thus satisfying
properties (1) and (2). ∎

Unfortunately, the proof does not give a bound on
$\max\\{|u|\,:\,u\in\operatorname{supp}(\tilde{z})\\}$ for $\tilde{z}$
constructed in Theorem 4.2.

##  5\. Improved lower bound

In this section we apply Theorem 2.5 to get a constant factor improvement over
(4), basically without any effort.

######  Theorem 5.1.

Let $L$ be an $n$-dimensional lattice, then

$c_{2}(\mathbb{R}^{n}/L)\geq\frac{\pi\lambda(L^{*})\mu(L)}{\sqrt{n}}.$

###### Proof.

Let $y$ be a vertex of the Voronoi cell $V(L)$ which realizes the covering
radius, that is $|y|=\mu(L)$ and so $y$ is a “deep hole” of $L$. Choose
$\nu=\frac{\lambda(L^{*})^{2}}{2n}\delta_{y}$ to be a point measure supported
at $y$ and set $Y=\frac{1}{n}I$. Then $(\nu,Y)$ is feasible for (12) because

$\int_{V(L)}(1-\cos(2\pi u^{\sf T}x))\,d\nu(x)=(1-\cos(2\pi u^{\sf
T}y))\frac{\lambda(L^{*})^{2}}{2n}\leq\frac{\lambda(L^{*})^{2}}{n}\leq\frac{|u|^{2}}{n}=u^{\sf
T}Yu$

for every $u\in L^{*}\setminus\\{0\\}$. Hence, by Theorem 2.5,

$c_{2}(\mathbb{R}^{n}/L)^{2}\geq
2\pi^{2}\int_{V(L)}|x|^{2}\,d\nu(x)=\frac{\pi^{2}\lambda(L^{*})^{2}\mu(L)^{2}}{n}.\qed$

##  6\. Least distortion embeddings of $\mathbb{R}^{n}/\mathbb{Z}^{n}$ and of
orthogonal decompositions

As our second application of Theorem 2.5, through Theorem 5.1, we prove that
the standard embedding (2) of the standard torus is indeed a least distortion
embedding. It is somewhat surprising that this result is new. We also note
that one can easily use the same argument to capture the case of flat tori
whose lattices have an orthogonal basis.

######  Theorem 6.1.

The standard embedding
$\varphi:\mathbb{R}^{n}/\mathbb{Z}^{n}\to\mathbb{R}^{2n}$ of the standard
torus $\mathbb{R}^{n}/\mathbb{Z}^{n}$ given by

$\varphi(x_{1},\ldots,x_{n})=(\cos 2\pi x_{1},\sin 2\pi x_{1},\ldots,\cos 2\pi
x_{n},\sin 2\pi x_{n})$

is a least distortion embedding with distortion
$c_{2}(\mathbb{R}^{n}/\mathbb{Z}^{n})=\pi/2$.

###### Proof.

We have $\lambda(\mathbb{Z}^{n})=1$ and $\mu(\mathbb{Z}^{n})=\sqrt{n/4}$, so
$c_{2}(\mathbb{R}^{n}/\mathbb{Z}^{n})\geq\pi/2$ by Theorem 5.1.

To show the corresponding upper bound we show that the embedding

$\phi(x_{1},\ldots,x_{n})=\frac{1}{\sqrt{32}}(e^{-2\pi ix_{1}},\ldots,e^{-2\pi
ix_{n}})$

has contraction $1$ and expansion $\pi/2$. Then turning $\phi$ into a real
embedding and rescaling does not change the distortion and gives the standard
embedding $\varphi$.

To show that $\phi$ has contraction $1$ and expansion $\pi/2$ it suffices to
prove that $(\frac{\pi^{2}}{4},z)$ with

$z(u)=\begin{cases}\frac{1}{32}&\text{if }u=\pm e_{i},\\\
0&\text{otherwise},\end{cases}$

is a feasible solution for (11).

The expansion equals $\pi/2$ because

$CI-4\pi^{2}\sum_{u\in\mathbb{Z}^{n}}z(u)uu^{\sf
T}=\frac{\pi^{2}}{4}I-4\pi^{2}\frac{2}{32}I=0.$

Moreover, to show that the contraction equals $1$ we need to verify the
inequality

(20) $\sum_{i=1}^{n}x_{i}^{2}\leq\frac{4}{32}\sum_{i=1}^{n}(1-\cos(2\pi
x_{i}))\quad\text{for all }x\in V(\mathbb{Z}^{n})=[-1/2,1/2]^{n},$

which we check summand by summand, that is
$x_{i}^{2}\leq\frac{1}{8}(1-\cos(2\pi x_{i}))$, where we have equality if
$x_{i}=\pm 1/2$. To do so we show that the logarithm of the quotient

$x_{i}\mapsto\log\left(\frac{x_{i}^{2}}{1-\cos(2\pi x_{i})}\right)$

is convex on $(-1/2,1/2)$ which follows by taking the second derivative: For
$x_{i}\in(0,1/2)$ we have

$\frac{\partial^{2}}{\partial x_{i}^{2}}\log\left(\frac{x_{i}^{2}}{1-\cos(2\pi
x_{i})}\right)=-\frac{2}{x_{i}^{2}}+\frac{4\pi^{2}}{1-\cos(2\pi x_{i})}\geq
0,$

where we used the inequality $1-\cos(2\pi x_{i})\leq 2\pi^{2}x_{i}^{2}$. ∎

Here it is interesting to note that even for the rather trivial standard
embedding of the standard torus the structure of the most contracted pairs is
rich. Every center of every face of the Voronoi cell $V(\mathbb{Z}^{n})$ gives
a most contracted pair, see Figure 1(a).

Recapulating the above proof, one recognizes that at its heart is the
verification of inequality (20). Here one reduces the situation from
$\mathbb{Z}^{n}$ to $\mathbb{Z}$. This works because $\mathbb{Z}^{n}$ can be
orthogonally decomposed as the direct sum of $n$ copies of $\mathbb{Z}$ and
this can be done in generality as the following theorem demonstrates.

######  Theorem 6.2.

Let $L\subseteq\mathbb{R}^{n}$ be a lattice such that $L$ decomposes as the
orthogonal direct sum of lattices $L_{1},\ldots,L_{m}$, i.e.

$L=L_{1}\perp L_{2}\perp\ldots\perp L_{m}.$

Then

$c_{2}(\mathbb{R}^{n}/L)=\max\\{c_{2}(\mathbb{R}^{n_{j}}/L_{j}):j=1,\ldots,m\\},$

where $\mathbb{R}^{n_{j}}$ is (isometric) to the Euclidean space spanned by
$L_{j}$.

###### Proof.

Any Euclidean embedding of $\mathbb{R}^{n}/L$ gives a Euclidean embedding of
$\mathbb{R}^{n_{j}}/L_{j}$ which immediately gives the inequality
$c_{2}(\mathbb{R}^{n}/L)\geq\max\\{c_{2}(\mathbb{R}^{n_{j}}/L_{j}):j=1,\ldots,m\\}$.

Also the reverse inequality is easy to see. Let
$\varphi_{j}:\mathbb{R}^{n_{j}}/L_{j}\to H_{j}$ be a Euclidean embedding of
$\mathbb{R}^{n_{j}}/L_{j}$ with distortion $C_{j}$ scaled so that the
contraction is $1$ and the expansion is $C_{j}$. We identify
$\mathbb{R}^{n}/L\cong\mathbb{R}^{n_{1}}/L_{1}\perp\ldots\perp\mathbb{R}^{n_{m}}/L_{m}$,
write $x\in\mathbb{R}^{n}/L$ as $x=(x_{1},\ldots,x_{m})$ with
$x_{j}\in\mathbb{R}^{n_{j}}/L_{j}$ so that
$d_{\mathbb{R}^{n}/L}(x,y)^{2}=\sum_{j=1}^{m}d_{\mathbb{R}^{n_{j}}/L_{j}}(x_{j},y_{j})^{2}$.
Then

$\varphi:\mathbb{R}^{n}/L\to H:=H_{1}\perp\ldots\perp
H_{m},\quad(x_{1},\ldots,x_{m})+L\mapsto(\varphi_{1}(x_{1}),\ldots,\varphi_{m}(x_{m}))$

is a Euclidean embedding of $\mathbb{R}^{n}/L$ into the Hilbert space $H$. Its
distortion is at most $\max\\{C_{j}:j=1,\ldots,m\\}$ because for every pair
$x,y\in\mathbb{R}^{n}/L$

$\begin{split}|\varphi(x)-\varphi(y)|^{2}&=\sum_{j=1}^{m}|\varphi_{j}(x_{j})-\varphi_{j}(y_{j})|^{2}\leq\sum_{j=1}^{m}C_{j}^{2}d_{\mathbb{R}^{n_{j}}/L_{j}}(x_{j},y_{j})^{2}\\\
&\leq\max_{j=1,\ldots,m}C_{j}^{2}\;\sum_{j=1}^{m}d_{\mathbb{R}^{n_{j}}/L_{j}}(x_{j},y_{j})^{2}=\max_{j=1,\ldots,m}C_{j}^{2}\;d_{\mathbb{R}^{n}/L}(x,y)^{2},\end{split}$

showing that the expansion of $\varphi$ at most $\max\\{C_{j}:j=1,\ldots,m\\}$
and, in exactly the same way, one shows that the contraction of $\varphi$ is
at most $1$. ∎

##  7\. Least distortion embeddings of two-dimensional flat tori

In this section we will construct least Euclidean distortion embeddings of
flat tori in dimension $2$.

First, as a simple corollary of Theorem 2.4, we will give a recipe to
construct (possibly non-optimal) embeddings of flat tori of arbitrary
dimension provided that they satisfy the following assumption:

(21) $\displaystyle\textup{There exist }u_{1},\ldots,u_{k}\in
L^{*},\,z_{1},\ldots,z_{k}\geq 0\text{ such that
}4\pi^{2}\sum_{i=1}^{k}z_{i}u_{i}u_{i}^{\sf T}=I.$

As we will prove in Lemma 7.2, condition (21) can be realized for every
$2$-dimensional lattice, Another example for lattices that satisfy condition
(21) are duals of root lattices. If $L^{*}$ is a root lattice, then assumption
(21) is satisfied. In this case the root system $R\subseteq L^{*}$ of $L^{*}$
forms a spherical $2$-design, implying that

$4\pi^{2}\alpha\sum_{u\in R}uu^{\sf T}=I$

for some positive constant $\alpha$. We refer to the monograph by Venkov [21]
for more information on root lattices and spherical designs.

######  Corollary 7.1.

Let $L\subseteq\mathbb{R}^{n}$ be a lattice that satisfies (21). Then

$\varphi:\mathbb{R}^{n}/L\to\mathbb{C}^{k},\quad\varphi(x)=(\sqrt{Dz_{1}}e^{2i\pi
u_{1}^{\sf T}x},\ldots,\sqrt{Dz_{k}}e^{2i\pi u_{k}^{\sf T}x})$

with

(22) $D=\max\left\\{\frac{|x|^{2}}{2\sum_{i=1}^{k}z_{i}(1-\cos(2\pi u_{i}^{\sf
T}x))}:x\in V(L)\setminus\\{0\\}\right\\}$

is a Euclidean embedding of $\mathbb{R}^{n}/L$ with distortion $\sqrt{D}$. In
particular,

(23) $c_{2}(\mathbb{R}^{n}/L)^{2}\leq D.$

###### Proof.

The pair $((Dz_{i})_{1\leq i\leq k},D)$ is a feasible solution for the primal
optimization problem (11). ∎

Except for the easiest case of the standard torus we do not know how to
determine $D$ explicitly. Unfortunately, it seems to be difficult to compute
most contracted pairs $(0,x$), i.e. vectors $x\in V(L)$ that are maximizers of
the right hand side of (22).

Next, we show that Corollary 7.1 can be applied to every $2$-dimensional
lattice. For this we will use the concept of an _obtuse superbasis_. An obtuse
superbasis of an $n$-dimensional lattice $L$ is a basis $u_{1},\ldots,u_{n}$
of $L$ enlarged by the vector $u_{0}=-u_{1}-\cdots-u_{n}$ so that these $n+1$
vectors pairwise form non-acute angles, i.e.

(24) $u_{i}^{\mathsf{T}}u_{j}\leq 0\;\text{ for all }\;0\leq i<j\leq n.$

It is known that up to dimension $3$ all lattices have an obtuse superbasis,
but from dimension $4$ on this is no longer the case, see for instance [8].

######  Lemma 7.2.

If $L$ is a two-dimensional lattice, then its dual lattice $L^{*}$ satisfies
(21).

###### Proof.

Let $u_{0},u_{1},u_{2}$ be an obtuse superbasis of $L^{*}$. We will show that
there are non-negative coefficients $z_{0},z_{1},z_{2}$ such that

$I=z_{0}u_{0}u_{0}^{\mathsf{T}}+z_{1}u_{1}u_{1}^{\mathsf{T}}+z_{2}u_{2}u_{2}^{\mathsf{T}},$

and therefore condition (21) holds.

We may assume that $|u_{1}|\geq|u_{0}|=1$, by scaling and renumbering. Then,
by Gram-Schmidt orthogonalization, $u_{0}$ and
$w_{1}:=u_{1}-(u_{0}^{\mathsf{T}}u_{1})u_{0}$ are orthogonal and so

$\begin{split}I&=u_{0}u_{0}^{\mathsf{T}}+\frac{1}{|w_{1}|^{2}}w_{1}w_{1}^{\mathsf{T}}\\\
&=\left(1+\frac{(u_{0}^{\mathsf{T}}u_{1})^{2}}{|w_{1}|^{2}}\right)u_{0}u_{0}^{\mathsf{T}}+\frac{1}{|w_{1}|^{2}}u_{1}u_{1}^{\mathsf{T}}-\frac{u_{0}^{\mathsf{T}}u_{1}}{|w_{1}|^{2}}(u_{0}u_{1}^{\mathsf{T}}+u_{1}u_{0}^{\mathsf{T}}).\end{split}$

Using

$u_{2}u_{2}^{\sf T}=(-u_{0}-u_{1})(-u_{0}-u_{1})^{\sf
T}=u_{0}u_{0}+u_{1}u_{0}^{\sf T}+u_{0}u_{1}^{\sf T}+u_{1}u_{1}^{\sf T},$

yields

$I=\left(1+\frac{(u_{0}^{\mathsf{T}}u_{1})^{2}+u_{0}^{\mathsf{T}}u_{1}}{|w_{1}|^{2}}\right)u_{0}u_{0}^{\mathsf{T}}+\frac{1+u_{0}^{\mathsf{T}}u_{1}}{|w_{1}|^{2}}u_{1}u_{1}^{\mathsf{T}}-\frac{u_{0}^{\mathsf{T}}u_{1}}{|w_{1}|^{2}}u_{2}u_{2}^{\mathsf{T}}.$

To prove that the three coefficients in the above sum are non-negative,
observe for the third coefficient that $u_{0}^{\mathsf{T}}u_{1}\leq 0$. For
the second coefficient

$0\leq-
u_{0}^{\mathsf{T}}u_{2}=u_{0}^{\mathsf{T}}u_{0}+u_{0}^{\mathsf{T}}u_{1}=1+u_{0}^{\mathsf{T}}u_{1}.$

For the first coefficient we compute the squared norm
$|w_{1}|^{2}=|u_{1}|^{2}-(u_{0}^{\sf T}u_{1})^{2}$ and see that the first
coefficient is nonnegative if and only if $|u_{1}|^{2}\geq-u_{0}^{\sf
T}u_{1}$, which is true because $|u_{1}|\geq|u_{0}|=1$ by assumption. ∎

Now, to verify that the embedding of Corollary 7.1 is indeed a least Euclidean
distortion embedding for two-dimensional flat tori, we construct a dual
solution for (12) that shows that the upper bound (23) is sharp.

######  Theorem 7.3.

Let $L\subseteq\mathbb{R}^{2}$ be a $2$-dimensional lattice, then
$c_{2}(\mathbb{R}^{2}/L)^{2}=D$, where $D$ is defined in (22).

###### Proof.

Let $u_{0},u_{1},u_{2}$ be an obtuse superbasis of $L^{*}$. We may assume, see
for example [8], that this superbasis is chosen in a way such that $u_{i}$ is
a shortest vector in its coset $u_{i}+2L^{*}$, with $i=0,1,2$. By Lemma 7.2 we
can determine coefficients $z_{0},z_{1},z_{2}\geq 0$ such that
$4\pi^{2}\sum_{i=0}^{2}z_{i}u_{i}u_{i}^{\mathsf{T}}=I$.

Furthermore, let $\bar{x}\in V(L)$ be a vector such that $(0,\bar{x})$ is a
most contracted pair for the embedding $\varphi$ of Corollary 7.1, that is,
$\bar{x}$ is a maximizer for (22).

We define the pair $(Y,\nu)$ as follows: Set
$\beta=\frac{D}{2\pi^{2}|\bar{x}|^{2}}$, define $Y$ via

(25)
$\displaystyle\operatorname{Tr}(u_{i}u_{i}^{\mathsf{T}}Y)=\beta(1-\cos(2\pi
u_{i}^{\mathsf{T}}\bar{x})),\quad i\in\\{0,1,2\\},$

and let $\nu=\beta\delta_{\bar{x}}$ be a point measure supported only on
$\bar{x}$. We now verify that this pair is a feasible dual solution with
objective value $D$.

We have

$\displaystyle\operatorname{Tr}(Y)=\operatorname{Tr}(YI)=4\pi^{2}\sum_{i}z_{i}\operatorname{Tr}(u_{i}u_{i}^{\mathsf{T}}Y)=4\pi^{2}\beta\sum_{i}z_{i}(1-\cos(2\pi
u_{i}^{\mathsf{T}}\bar{x}))=1.$

Equation (25) together with Lemma 3.3 implies

$\displaystyle\operatorname{Tr}(uu^{\mathsf{T}}Y)\geq\beta(1-\cos(2\pi
u^{\mathsf{T}}\bar{x}))\quad\text{ for all }u\in L^{*}.$

Finally, it remains to show that $Y$ is positive semidefinite. For this we
compute its Gram matrix $B$ with respect to $u_{0},u_{1}$, that is

$\displaystyle
B_{ij}=u_{i}^{\mathsf{T}}Yu_{j}=\frac{1}{2}\operatorname{Tr}((u_{i}u_{j}^{\mathsf{T}}+u_{j}u_{i}^{\mathsf{T}})Y),\quad
0\leq i,j\leq 1.$

Then $B_{ii}=\operatorname{Tr}(u_{i}u_{i}^{\mathsf{T}}{Y})=2\beta\sin^{2}(\pi
u_{i}^{\mathsf{T}}\bar{x})$. Since

$\displaystyle
u_{0}u_{1}^{\mathsf{T}}+u_{1}u_{0}^{\mathsf{T}}=u_{2}u_{2}^{\mathsf{T}}-u_{0}u_{0}^{\mathsf{T}}-u_{1}u_{1}^{\mathsf{T}},$

we get

$\displaystyle B_{01}$ $\displaystyle=\frac{\beta}{2}\Big{(}2\sin^{2}(\pi
u_{2}^{\mathsf{T}}\bar{x})-2\sin^{2}(\pi
u_{1}^{\mathsf{T}}\bar{x})-2\sin^{2}(\pi u_{0}^{\mathsf{T}}\bar{x})\Big{)}$
$\displaystyle=2\beta\sin(\pi u_{0}^{\mathsf{T}}\bar{x})\sin(\pi
u_{1}^{\mathsf{T}}\bar{x})\cos(\pi(u_{0}+u_{1})^{\mathsf{T}}\bar{x}).$

From this we see that matrix $B$ is the Schur-Hadamard (entry-wise) product of
the positive semidefinite rank-one matrix $xx^{\mathsf{T}}$ with
$x_{i}=\sqrt{2\beta}\sin(\pi u_{i}^{\mathsf{T}}\bar{x})$ and the symmetric
matrix $M\in\mathbb{R}^{2\times 2}$ defined by

$\displaystyle M_{ij}=\begin{cases}1&\text{ if }i=j\\\
\cos(\pi(u_{0}+u_{1})^{\mathsf{T}}\bar{x})&\text{ if
}(i,j)\in\\{(0,1),(1,0)\\}.\end{cases}$

The matrix $M$ is positive semidefinite because $M_{ii}\geq 0$ and

$\displaystyle\det(M)=1-\cos^{2}(\pi(u_{0}+u_{1})^{\mathsf{T}}\bar{x})\geq 0.$

Thus $B$, and therefore also $Y$, is positive semidefinite, which finishes the
proof. ∎

To conclude the discussion of $2$-dimensional lattices Figure 1 collects an
illustration of the behavior of the distortion function defined in (22) and
the most contracted pairs, applying the above results, for a selection of
$2$-dimensional lattices.

(a) $L_{90^{\circ}}$ ($\mathbb{Z}^{2}$)

(b) $L_{93^{\circ}}$

(c) $L_{105^{\circ}}$

(d) $L_{120^{\circ}}$ ($A_{2}^{*}$)

Figure 1.  Let $L_{\varphi}$ be the lattice spanned by $v_{1}=e_{1}$,
$v_{2}=R_{\varphi}e_{1}$, where $R_{\varphi}$ is the rotation by $\varphi$
degrees (counter-clockwise).
The Voronoi cell of any lattice in $\mathbb{R}^{2}$ is either a rectangle or a
hexagon. We plot contour lines of the distortion function for a selection of
lattices that illustrate how the distortion function and the most contracted
pairs vary with the shape of the Voronoi cell. $L_{93^{\circ}}$ shows what
happens for almost degenerated hexagons, i.e. lattices close to the standard
lattice. A zoom into the behavior around the short edge of the hexagon is
included to illustrate that the most contracted points are all vertices of the
Voronoi-cell.

##  8\. Discussion and open questions

In this paper we derived an infinite-dimensional semidefinite program to
determine the least distortion Euclidean embedding of a flat torus. It would
be very interesting to show that this infinite-dimensional semidefinite
program can in fact be turned into a finite-dimensional semidefinite program.
Then one could, similarly to the case of finite metric spaces, algorithmically
determine least distortion Euclidean embeddings of flat tori; at least up to
any desired precision.

For this a characterization of the most contracted pairs is needed. We believe
that the most contracted pairs are always of the form $(0,y)$ and $y$ is a
center of a face of the Voronoi cell. However, we do not know whether such a
$y$ can only lie on the Voronoi cell’s boundary. We do not even know whether
there are only finitely many most contracted pairs.

We also do not know how to restrict the variable $z\in\ell_{1}(L^{*})$ to
finite dimension, even though Theorem 4.2 shows that we can always find a
finite-dimensional least distortion embedding. Obtaining a bound on the
maximally needed length of a support vector in the cosets $L^{*}/2L^{*}$ would
solve this problem.

Another interesting problem is to determine $n$-dimensional lattices which
maximize the distortion among all $n$-dimensional lattices.

## Acknowledgements

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie agreement
No 764759. F.V. is partially supported by the SFB/TRR 191 “Symplectic
Structures in Geometry, Algebra and Dynamics”, F.V. and M.C.Z. are partially
supported “Spectral bounds in extremal discrete geometry” (project number
414898050), both funded by the DFG. A.H. is partially funded by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s
Excellence Strategy – Cluster of Excellence Matter and Light for Quantum
Computing (ML4Q) EXC 2004/1 – 390534769.

## References

  * [1] I. Aharoni, B. Maurey, B.S. Mityagin, Uniform embeddings of metric spaces and of Banach spaces into Hilbert spaces, Israel J. Math. 52 (1985), 251–265.
  * [2] I. Agarwal, O. Regev, Y. Tang, Nearly optimal embeddings of flat tori, APPROX/RANDOM 2020.
  * [3] C. Bachoc, D.C. Gijswijt, A. Schrijver, F. Vallentin, Invariant semidefinite programs, pp. 219–269 in: Handbook on semidefinite, conic, and polynomial optimization (M.F. Anjos, J.B. Lasserre, eds.), Springer, 2012.
  * [4] V. Borrelli, S. Jabrane, F. Lazarus, B. Thibert, Flat tori in three-dimensional space and convex integration, Proceedings of the National Academy of Sciences (PNAS) 109 (2012), 7218–7223.
  * [5] G.J. Butler, Simultaneous packing and covering in Euclidean space, Proc. London Math. Soc. 25 (1972) 721–735.
  * [6] S.M. Cioabă, H. Gupta, F. Ihringer, H. Kurihara, The least Euclidean distortion constant of a distance-regular graph, arXiv:2109.09708 [math.CO], 2021.
  * [7] J.H. Conway, N.J.A. Sloane, Sphere packings, lattices, and groups, Springer, 1988.
  * [8] J.H. Conway, N.J.A. Sloane, Low-Dimensional Lattices VI: Voronoi Reduction of Three-Dimensional Lattices, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 436 (1992), 55–68.
  * [9] G.B. Folland, A course in abstract harmonic analysis, CRC Press, 1995.
  * [10] I. Haviv, O. Regev, The Euclidean distortion of flat tori, J. Topol. Anal. 5 (2013), 205–223 (extended abstract appeared in APPROX/RANDOM 2010).
  * [11] S. Khot, A. Naor, Nonembeddability theorems via Fourier analysis, Math. Ann. 334 (2006), 821–852 (extended abstract appeared in FOCS 2005)
  * [12] T. Kobayashi, T. Kondo, The Euclidean distortion of generalized polygons, Adv. Geom. 15 (2015), 499–506.
  * [13] Z. Kominek, K. Troczka-Pawelec, Some remarks on subquadratic functions, Demonstratio Math. 39 (2006), 751–758.
  * [14] M. Laurent, F. Vallentin, A course on semidefinite optimization, Cambridge University Press, in preparation.
  * [15] N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), 215–246.
  * [16] N. Linial, A. Magen, Least-distortion Euclidean embeddings of graphs: products of cycles and expanders, J. Combin. Theory Ser. B 79 (2000), 157–171.
  * [17] N. Linial, A. Magen, A. Naor, Girth and Euclidean distortion, Geom. Funct. Anal. 12 (2002), 380–394.
  * [18] J. Matoušek, Lectures on discrete geometry, Springer, 2002.
  * [19] E.H. Moore, On properly positive Hermitian matrices, Bull. Amer. Math. Soc. 23 (1916), 66–67.
  * [20] F. Vallentin, Optimal distortion embeddings of distance regular graphs into Euclidean spaces, J. Combin. Theory Ser. B 98 (2008), 95–104.
  * [21] B.B. Venkov, Réseaux et designs sphériques, pages 10–86 in: Réseaux euclidiens, designs sphériques et formes modulaires, Monogr. Enseign. Math., 37, 2001.