# Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs

Evelyne Hubert, Tobias Metzlaff, Philippe Moustrou, Cordian Riener

► To cite this version:

Evelyne Hubert, Tobias Metzlaff, Philippe Moustrou, Cordian Riener. Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs. Mathematical Programming, 2024, 10.1007/s10107-024-02149-1. hal-03768067v3

HAL Id: hal-03768067

https://hal.science/hal-03768067v3

Submitted on 23 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Optimization of trigonometric polynomials
with crystallographic symmetry and
spectral bounds for set avoiding graphs

Evelyne Hubert*, Tobias Metzlaff†, Philippe Moustrou‡, Cordian Riener§

Thursday 23rd May, 2024

Abstract

We provide a new approach to the optimization of trigonometric polynomials under the hypothesis of a crystallographic symmetry. This approach widens the bridge between trigonometric and polynomial optimization.

The trigonometric polynomials considered are supported on weight lattices associated to crystallo-
graphic root systems and are assumed invariant under the associated reflection group. On one hand the
invariance allows us to rewrite the objective function in terms of generalized Chebyshev polynomials of
the generalized cosines; On the other hand the generalized cosines parametrize a compact basic semi
algebraic set, this latter being given by an explicit polynomial matrix inequality. The initial problem
thus boils down to a polynomial optimization problem that is straightforwardly written in terms of gen-
eralized Chebyshev polynomials. The minimum is to be computed by a converging sequence of lower
bounds as given by a hierarchy of relaxations based on the Hol-Scherer Positivstellensatz and indexed
by the weighted degree associated to the root system.

This new method for trigonometric optimization was motivated by its application to estimate the
spectral bound on the chromatic number of set avoiding graphs. We examine cases of the literature
where the avoided set affords crystallographic symmetry. In some cases we obtain new analytic proofs
for sharp bounds on the chromatic number while in others we compute new lower bounds numerically.

**Keywords:** Trigonometric Optimization, Crystallographic Symmetry, Weyl Groups, Root Systems, Lattices, Chebyshev Polynomials, Chromatic Numbers, Set Avoiding Graphs, Spectral Bounds

MSC: 05C15 17B22 33C52 52C07 90C23

<footnote>*Inria d'Université Côte d'Azur</footnote>

<footnote>†University of Kaiserslautern–Landau</footnote>

<footnote>‡Université Toulouse Jean Jaurès</footnote>

<footnote>§UiT The Arctic University</footnote>
# Contents

1 Introduction 3

2 Crystallographic symmetries 5

2.1 Root systems and Weyl groups 5

2.2 Trigonometric polynomials with Weyl group symmetry 8

2.3 The image of the generalized cosines as a basic semi-algebraic set 10

2.4 Optimizing trigonometric polynomials with crystallographic symmetry 11

3 Optimization in terms of generalized Chebyshev polynomials 12

3.1 Matrix version of Putinar's theorem 12

3.2 Lasserre hierarchy with Chebyshev polynomials 14

3.3 Optimizing on coefficients 17

3.4 A case study 18

4 Spectral bounds for set avoiding graphs 21

4.1 Computing spectral bounds with Chebyshev polynomials 21

4.2 The chromatic number of a coroot lattice 23

4.3 The chromatic number of $Z^n$ for the crosspolytope 25

4.4 The chromatic number of $\mathbb{R}^n$ for Voronoï cells 29

4.5 Discussion on the results 36

A Irreducible root systems of type $A_{n-1}$, $C_n$, $B_n$, $D_n$, $G_2$ 42

B Coefficients for discrete measures 43

E. Hubert, CENTRE INRIA D'UNIVERSITÉ CÔTE D'AZUR, 06902 SOPHIA ANTIPOLIS, FRANCE

E-mail address: evelyne.hubert@inria.fr

ORCID: 0000-0003-1456-9524

T. Metzlaff, DEPARTMENT OF MATHEMATICS, UNIVERSITY OF KAISERSLAUTERN-LANDAU, 67663 KAISERSLAUTERN, GERMANY

Former Association: CENTRE INRIA D'UNIVERSITÉ CÔTE D'AZUR, 06902 SOPHIA ANTIPOLIS, FRANCE

E-mail address: tobias.metzlaff@rptu.de

ORCID: 0000-0002-0688-7074

P. Moustrou, INSTITUT DE MATHÉMATIQUES DE TOULOUSE, UNIVERSITÉ TOULOUSE JEAN JAURÈS, 31100 TOULOUSE, FRANCE

E-mail address: philippe.moustrou@math.univ-toulouse.fr

ORCID: 0000-0003-3432-4954

C. Riener, DEPARTMENT OF MATHEMATICS, UIT THE ARCTIC UNIVERSITY, 9037 TROMSØ, NORWAY

E-mail address: cordian.riener@uit.no

ORCID: 0000-0002-1192-3500
# 1 Introduction

Given an $n$-dimensional lattice $\Omega \subseteq \mathbb{R}^n$, a trigonometric polynomial is a function

$$f: \mathbb{R}^n \to \mathbb{R}, u \mapsto f(u) := \sum_{\mu \in \Omega} c_{\mu} \exp(-2\pi i \langle \mu, u \rangle),$$

where $\langle \cdot, \cdot \rangle$ denotes the Euclidean scalar product and the finitely many nonzero coefficients $c_{\mu} \in \mathbb{C}$ satisfy $c_{-\mu} = \bar{c}_{\mu}$. Such functions are good $L^2$-aproximations for real-valued $\Lambda$-periodic functions, where $\Lambda$ is the dual lattice, and assume their global maximum and minimum on the periodicity domain. This article offers a new approach to optimizing such a trigometric function over $\mathbb{R}^n$, when it is invariant under a crystallographic reflection group. We show how the problem can then be reduced to polynomial optimization on a semi-algebraic set and handled with a variation on the Lasserre hierarchy. The resulting algorithm is applied to the exploration of the spectral bound on the chromatic numbers of set avoiding graphs.

The global minimum of a trigonometric polynomial can be approximated numerically with a hierarchy of Hermitian sums of squares reinforcements [Dum07, BR23]. Alternatively, one can apply Lasserre's hierarchy with complex variables [JM18], where one has to restrict to the compact torus. A symmetry reduction scheme can be introduced at each step of the hierarchy, as exploited for a special case in [KdK23] and further explored in [Met23]. In this article we factor out the symmetry from the original problem, boiling it down to the minimization of a polynomial on a compact basic semi-algebraic set.

In this article, $\Omega$ is the weight lattice of a crystallographic root system in $\mathbb{R}^n$. Root and weight lattices provide optimal configurations for a variety of problems in geometry and information theory, with incidence in physics and chemistry. The $A_2$ lattice (the hexagonal lattice) is classically known to be optimal for sampling, packing, covering, and quantization in the plane [CS99, KAH05], but also proved, or conjectured, to be optimal for energy minimization problems [PS20, BF23]. More recently, the $E_8$ lattice was proven to give an optimal solution for the sphere packing problem and a large class of energy minimization problems in dimension 8 [Via17, CKM$^+$22]. From an approximation point of view, weight lattices of root systems describe Gaussian cubatures [LX10, MP11], a rare occurrence on multidimensional domains. In a different direction, the triangulations associated with infinite families of root systems are relevant in graphics and computational geometry, see for instance [CKW20] and references therein.

The distinguishing feature of the lattices associated to crystallographic root systems is their intrinsic symmetry. This latter is given by the so called Weyl group $W$, a finite group generated by orthogonal reflections w.r.t. $\langle \cdot, \cdot \rangle$. It is this feature that we emphasize and offer to exploit in an optimization context. We present a new approach to numerically solve the trigonometric optimization problem

$$f^* := \min_{u \in \mathbb{R}^n} f(u) \qquad (1.1)$$

under the assumption of crystallographic symmetry, that is, for $s \in W$, we have $f(s(u)) = f(u)$, or equivalently $c_{s(\mu)} = c_{\mu}$. The first step of our approach, in Section 2, is a symmetry reduction that translates the trigonometric optimization above to the problem of optimizing a polynomial over a semi-algebraic set, a subject that ripened in the last two decades [Las01, Par03, PS03, PPSP05, KLP05, Las09, Lau09, BPT12, HKL21]. The second step of our approach, in Section 3, is thus an adaptation of Lasserre's hierarchy of moment relaxations and sums of squares reinforcements. We indeed modify the hierarchy introduced in [HS05, HS06, Las06] to work directly in the basis of generalized Chebyshev polynomials. These are not homogeneous but naturally filtered by a weighted degree, different from the usual degree.

The simplest case of this symmetry reduction scheme, the univariate case, is obvious but maybe worth reviewing to get the initial idea. The lattice is $\Omega = \mathbb{Z} \subset \mathbb{R}$ and hence the periodicity domain is the interval $[-1, 1]$. The associated Weyl group is $W = \{1, -1\}$ so that the fundamental domain is the interval $[0, 1]$ and the invariance condition is $f(-u) = f(u)$, for all $u \in \mathbb{R}$. That implies that one can write

$$f(u) = \sum_{k \in \mathbb{N}} \frac{c_k}{2} (\exp(2\pi i k u) + \exp(-2\pi i k u)) = \sum_{k \in \mathbb{N}} c_k \cos(2\pi k u) = \sum_{k \in \mathbb{N}} c_k T_k(\cos(2\pi u)),$$
where {$T_k$}$_{k \in \mathbb{N}}$ are the Chebyshev polynomials of the first kind. We thus have

$$f^* := \min_{u \in \mathbb{R}} f(u) = \min_{z^2 \le 1} \sum_{k \in \mathbb{N}} c_k T_k(z)$$

the right hand side being a polynomial optimization problem with semi-algebraic constraints.

We look at all the lattices associated to crystallographic root systems, offering a wide range of domains of periodicity (hexagon, rhombic dodecahedron, icositetrachoron, hypercube, ...) and simplices of any dimension, or cartesian products of these, as fundamental domains. In higher dimension we thus go beyond the cartesian product symmetry $W = \{1, -1\}^n$ with a hyperrectangle as periodicity domain. The key to the symmetry reduction then is the existence and properties of generalized Chebyshev polynomials. They allow to rewrite any invariant trigonometric polynomials as polynomials of the fundamental generalized cosines. In the case $W = \{1, -1\}^n$ mentioned earlier, the generalized Chebyshev polynomials are simply the product of univariate Chebyshev polynomials in each variable. The zoo of generalized Chebyshev is yet conspicuously larger.

The generalized Chebyshev polynomials arose in different contexts, in particular in the search of multivariate orthogonal polynomials [DL80, EL82, HW88, Mac90, Bee91]. A more recent development is the description of their domain of orthogonality, the image of the generalized cosines, as a compact semi-algebraic set given by a unified and explicit polynomial matrix inequality [HMR24, Met22]. Such a description is necessary to proceed algorithmically with the obtained polynomial optimization problem.

In the algorithmic approach, we solve a primal/dual semi-definite program (SDP) that models a moment-relaxation/sums of squares reinforcement in terms of generalized Chebyshev polynomials. The MAPLE package GENERALIZEDCHEBYSHEV provides the necessary tools. It is available here:

https://github.com/TobiasMetzlaff/GeneralizedChebyshev

The package allows to produce the data for the SDP, specifically the matrices that impose the semi-definite constraints. The user can then solve the problem with a SDP solver of their personal preference. Beyond that, the package offers a large variety of functionalities, including the matrices from [HMR24], an implementation of the irreducible root systems and computational aspects of multiplicative invariants<fnref n="1" />. We can thus compare our method with the one in [Dum07] in practice. Under the symmetry hypothesis, we observe in several examples throughout Section 3.4 that the quality of the approximation is improved, while the computational complexity is reduced.

As a second set of contributions, in Section 4, we apply our method to the computation of spectral bounds for chromatic numbers of set avoiding graphs. The first such graph considered was the Euclidean distance graph [Soi09, BDFV14, BPT15, Gre18], where the vertices are the points of $\mathbb{R}^n$ and the set to be avoided is the sphere. As set of vertices we consider either $\mathbb{R}^n$, or a lattice thereof. As for the set to be avoided we mostly consider the boundary of a polytope with crystallographic symmetry. Choosing appropriate discrete measures on the boundary of the polytope, the spectral bound from [BDFV14] made specific to the chromatic number can be expressed as the solution of a max-min optimization problem on a trigonometric polynomial. Our symmetry reduction technique of Section 2 then allows us to retrieve, with simple proofs, the chromatic number of the $A_{n-1}$ lattice (Theorem 4.6), of the graph avoiding the crosspolytope of radius 2 in $\mathbb{Z}^n$ (Theorem 4.11), and of the graph avoiding the cube in $\mathbb{R}^n$ (Proposition 4.17). In other cases, we apply the algorithm in Section 3 to compute lower bounds numerically. We improve the previous lower bound from [FK04] on the chromatic number of $\mathbb{Z}^4$ avoiding the crosspolytope from 9 to 11 (Table 4). We also give further bounds for the rhombic dodecahedron (Table 6) as well as the icositetrachoron (Table 7). Our results are summarized and commented in more details in Section 4.5.

<footnote n="1">¹See https://tobiasmetzlaff.com/html_guides/GeneralizedChebyshevHelp.html for a documentation.</footnote>
# 2 Crystallographic symmetries

In order to rewrite the trigonometric optimization problem in Equation (1.1) to a polynomial optimization problem, we require the lattice $\Omega$ to be full-dimensional and stable under some finite reflection group $W$, that is, $W\Omega = \Omega$. Then $W$ must be the Weyl group of some crystallographic root system [Kan01, Ch. 9] and $\Omega$ is the associated weight lattice. We need several facts from the theory of Lie algebras, root systems and lattices, which come from [Bou68, Hum72, CS99]. In particular, we need Theorem 2.5, which states that any trigonometric polynomial with crystallographic symmetry can be written uniquely as a polynomial in fundamental invariants, also known as the generalized cosines. Subsequently, the feasible region of the so obtained polynomial optimization problem is the image of the generalized cosines, a compact basic semi-algebraic set whose equations were given explicitely in [HMR24, Met22].

The computations for the examples in this section are documented here:

https://tobiasmetzlaff.com/html_guides/crystallographic symmetries.html

## 2.1 Root systems and Weyl groups

The nonnegative integers are denoted by $\mathbb{N} = \{0, 1, 2, ...\}$. Let $1 \le n \in \mathbb{N}$ and $\langle \cdot, \cdot \rangle$ be the Euclidean scalar product on $\mathbb{R}^n$. A subset $R \subseteq \mathbb{R}^n$ is called a **root system** in $\mathbb{R}^n$, if the following conditions hold.

R1 R is finite, spans $\mathbb{R}^n$ and does not contain 0.

R2 If $\rho, \tilde{\rho} \in R$, then $\langle \tilde{\rho}, \rho^\vee \rangle \in \mathbb{Z}$, where $\rho^\vee := \frac{2\rho}{\langle \rho, \rho \rangle}$.

R3 If $\rho, \tilde{\rho} \in R$, then $s_\rho(\tilde{\rho}) \in R$, where $s_\rho$ is the reflection defined by $s_\rho(u) = u - \langle u, \rho^\vee \rangle\rho$ for $u \in \mathbb{R}^n$.

The elements of $R$ are called **roots** and the $\rho^\vee$ are called the **coroots**. Furthermore, $R$ is called **reduced**, if additionally the following condition holds.

R4 For $\rho \in R$ and $c \in \mathbb{R}$, we have $c\rho \in R$ if and only if $c = \pm 1$.

We assume that the “reduced” property R4 always holds when we speak of a “root system”. Sometimes the “crystallographic” property R2 is emphasized as a separate condition [Kan01]. For visualizations, see Example 2.4.

### 2.1.1 Weyl group and weights

The **Weyl group** $W$ of $R$ is the group generated by the reflections $s_\rho$ for $\rho \in R$. This is a finite subgroup of the orthogonal group on $\mathbb{R}^n$ with respect to the inner product $\langle \cdot, \cdot \rangle$. The Weyl groups are the groups we consider in this article and now we define the lattices of interest.

A subset $B = \{\rho_1, \dots, \rho_n\} \subseteq R$ is called a **base**, if the following conditions hold.

B1 B is a basis of $\mathbb{R}^n$.

B2 Every root $\rho \in R$ can be written as $\rho = \alpha_1 \rho_1 + \dots + \alpha_n \rho_n$ or $\rho = -\alpha_1 \rho_1 - \dots - \alpha_n \rho_n$ for some $\alpha \in \mathbb{N}^n$.

Every root system contains a base [Bou68, Ch. VI, §1, Thm. 3].

A **weight** of $R$ is an element $\mu \in \mathbb{R}^n$, such that, for all $\rho \in R$, we have $\langle \mu, \rho^\vee \rangle \in \mathbb{Z}$. The set of weights forms a lattice $\Omega$, called the **weight lattice**. By the condition R2, every root is a weight. For a base $B = \{\rho_1, \dots, \rho_n\}$, the **fundamental weights** are the elements $\{\omega_1, \dots, \omega_n\}$, such that, for $1 \le i, j \le n$, $\langle \omega_i, \rho_j^\vee \rangle = \delta_{i,j}$. The weight lattice is left invariant under the Weyl group, that is, $W\Omega = \Omega$.
The fundamental Weyl chamber of W relative to B is

$$ \Lambda := \{u \in \mathbb{R}^n \mid \forall 1 \le i \le n : \langle u, \rho_i \rangle > 0\}. $$

The closure $\bar{\Lambda}$ is a fundamental domain of W [Bou68, Ch. V, §3, Thm. 2]. Hence, $\bar{\Lambda}$ contains exactly one element per W-orbit and the weights in $\bar{\Lambda}$ are called **dominant**. We denote $\Omega^+ := \Omega \cap \bar{\Lambda}$.

**Proposition 2.1.** For $\mu \in \Omega^+$, there exists a unique $\hat{\mu} \in \Omega^+$ with $-\mu \in W\hat{\mu}$. Furthermore, there exists a permutation $\sigma \in \mathfrak{S}_n$ of order at most 2, such that, for all $1 \le i \le n$, we have $\hat{\omega}_i = \omega_{\sigma(i)}$.

*Proof.* Fix a base $\{\rho_1, \dots, \rho_n\}$ and recall that W is generated by the reflection $s_{\rho_i}$ [Bou68, Ch. VI, §1, Thm. 2]. There is a unique element $s_0 \in W$, which has maximal length with respect to the $s_{\rho_i}$ and it is an involution that takes $\{\rho_1, \dots, \rho_n\}$ to $\{-\rho_1, \dots, -\rho_n\}$ [Bou68, Ch. VI, §1, Prop. 17, Coro. 3]. Hence, there is a permutation $\sigma \in \mathfrak{S}_n$ with $s_0(\rho_i) = -\rho_{\sigma(i)}$. Since $s_0^2 = \text{Id}_n$ and the inner product is W-invariant, $\sigma$ has order 1 or 2 and

$$ -s_0(\omega_i) = \sum_{j=1}^{n} \langle -s_0(\omega_i), \rho_j^{\vee} \rangle \omega_j = \sum_{j=1}^{n} \langle \omega_i, -s_0(\rho_j^{\vee}) \rangle \omega_j = \sum_{j=1}^{n} \langle \omega_i, \rho_{\sigma(j)}^{\vee} \rangle \omega_j = \omega_{\sigma(i)} $$

is also a fundamental weight. In particular, $\hat{\mu} := -s_0(\mu) \in \Omega^+$ is unique. $\square$

### 2.1.2 The Voronoï cell

The set of all coroots $\rho^{\vee}$ spans a lattice $\Lambda$ in $\mathbb{R}^n$, called the **coroot lattice**. This Abelian group acts on $\mathbb{R}^n$ by translation and is the dual lattice of the weight lattice, that is, $\Lambda = \Omega^* = \{\lambda \in \mathbb{R}^n \mid \forall \mu \in \Omega : \langle \mu, \lambda \rangle \in \mathbb{Z}\}$. Denote by $\|\cdot\|$ the Euclidean norm. The **Voronoï cell** of $\Lambda$ is

$$ \text{Vor}(\Lambda) := \{u \in \mathbb{R}^n \mid \forall \lambda \in \Lambda : \|u\| \le \|u - \lambda\|\} $$

and tiles $\mathbb{R}^n$ by $\Lambda$-translation, that is,

$$ \mathbb{R}^n = \bigcup_{\lambda \in \Lambda} (\text{Vor}(\Lambda) + \lambda), \qquad (2.1) $$

where “+” denotes the Minkowski sum. The interiors of the cells $\text{Vor}(\Lambda) + \lambda$ are disjoint and the intersection of two adjacent cells is an entire face of both of them [CS99, Ch. 2, §1.2]. Faces of codimension 1 are called facets.

The **affine Weyl group** is the infinite group generated by the reflections $s_{\rho, \ell}(u) := s_{\rho}(u) + \ell \rho^{\vee}$ for $\rho \in \mathbb{R}$. It can also be seen as the semi-direct product $W \times \Lambda$ [Bou68, Ch. VI, §2, Prop. 1]. We are interested in the chambers of this infinite reflection group, which are called **alcoves** to avoid confusion. In particular, the closure of any alcove is a fundamental domain for $W \times \Lambda$.

**Proposition 2.2.** [Bou68, Ch. VI, §2, Prop. 4] and [CS99, Ch. 21, §3, Thm. 5] There is a unique alcove of $W \times \Lambda$ in $\Lambda$, which contains 0 in its closure $\Delta$. We have $\text{Vor}(\Lambda) = W \Delta$.

The rest of this subsection is devoted to describe the closure $\Delta$ of the unique alcove in Proposition 2.2. Assume that $\mathbb{R}^n = V^{(1)} \oplus \dots \oplus V^{(k)}$ is the direct sum of proper orthogonal subspaces and that, for each $1 \le i \le k$, $\mathbb{R}^{(i)}$ is a root system in $V^{(i)}$. Then $\mathbb{R} := \mathbb{R}^{(1)} \cup \dots \cup \mathbb{R}^{(k)}$ is a root system in $\mathbb{R}^n$ and called the **direct sum** of the $\mathbb{R}^{(i)}$. If a root system is not the direct sum of at least two root systems, then it is called **irreducible**.

The Weyl group $W$ is the product of the Weyl groups corresponding to the irreducible components, see the discussion before [Bou68, Ch. VI, §1, Prop. 5]. Furthermore, any alcove of the affine Weyl group is the
product of alcoves corresponding to the irreducible components, see the discussion after [Bou68, Ch. VI, §2, Prop. 2]. We are thus left to determine $\Delta$ for irreducible root systems. If R is irreducible and B is a fixed base, then there exists a unique positive root $\rho_0 \in \mathbb{R}^+$, so that, for all $\rho \in \mathbb{R}$, there is some $\alpha \in \mathbb{N}^n$ with $\rho_0 - \rho = \alpha_1 \rho_1 + \dots + \alpha_n \rho_n$ [Bou68, Ch. VI, §1, Prop. 25]. We call $\rho_0$ the **highest root**.

**Proposition 2.3.** [Bou68, Ch. VI, §2, Prop. 5, Coro.] Let R be an irreducible root system and B = {$\rho_1, \dots, \rho_n$} be a base, so that $\rho_0 = \alpha_1 \rho_1^\vee + \dots + \alpha_n \rho_n^\vee$ is the highest root of R for some $\alpha \in \mathbb{R}^n$. Then

$$ \Delta = \{u \in \mathbb{R}^n \mid \forall 1 \le i \le n : \langle u, \rho_i \rangle \ge 0 \text{ and } \langle u, \rho_0 \rangle \le 1\} $$

is a fundamental domain for $W \times \Lambda$. Furthermore, for $1 \le i \le n$, we have $\alpha_i > 0$ and

$$ \Delta = \mathrm{ConvHull} \left( 0, \frac{\omega_1}{\alpha_1}, \dots, \frac{\omega_n}{\alpha_n} \right). $$

In particular, if R is irreducible, then any closed alcove of the affine Weyl group is a simplex.

Every root system can be uniquely decomposed into irreducible components [Bou68, Ch. VI, §1, Prop. 6] and there are only finitely many cases [Bou68, Ch. VI, §4, Thm. 3] denoted by $A_{n-1}$, $B_n$, $C_n$ ($n \ge 2$), $D_n$ ($n \ge 4$), $E_6$, $E_7$, $E_8$, $F_4$ and $G_2$. Throughout this article, we shall focus on the four infinite families $A_{n-1}$, $B_n$, $C_n$, $D_n$ and the special case $G_2$. For those root systems, the base, fundamental weights and Weyl group are given in Appendix A.

**Example 2.4.** We consider the following irreducible root systems in dimension 2. (Column vectors are denoted by square brackets $[\cdot]$, transpose by $^t$.)

<figure><img src="image_2.png" /></figure>

$$ \begin{align*} W(A_2) &\cong \mathfrak{S}_3 \\ \omega_1 &= [2, -1, -1]^t/3 \\ \omega_2 &= [1, 1, -2]^t/3 \\ \rho_1 &= [1, -1, 0]^t = \rho_1^\vee \\ \rho_2 &= [0, 1, -1]^t = \rho_2^\vee \\ \rho_0 &= \rho_1^\vee + \rho_2^\vee \end{align*} $$

<figure><img src="image_3.png" /><figcaption>Figure 1: The root system $A_2$ in $\mathbb{R}^3/\langle [1, 1, 1]^t \rangle$.</figcaption></figure>

$$ \begin{align*} W(B_2) &\cong \mathfrak{S}_2 \times \{\pm 1\}^2 \\ \omega_1 &= [1, 0]^t \\ \omega_2 &= [1, 1]^t/2 \\ \rho_1 &= [1, -1]^t = \rho_1^\vee \\ \rho_2 &= [0, 1]^t = \rho_2^\vee/2 \\ \rho_0 &= \rho_1^\vee + \rho_2^\vee \end{align*} $$

<figure><img src="image_4.png" /><figcaption>Figure 2: The root system $B_2$ in $\mathbb{R}^2$.</figcaption></figure>

$$ \begin{align*} W(G_2) &\cong \mathfrak{S}_3 \times \{\pm 1\} \\ \omega_1 &= [0, -1, 1]^t \\ \omega_2 &= [-1, -1, 2]^t \\ \rho_1 &= [1, -1, 0]^t = \rho_1^\vee \\ \rho_2 &= [-2, 1, 1]^t = 3 \rho_1^\vee \\ \rho_0 &= 3 \rho_1^\vee + 6 \rho_2^\vee \end{align*} $$

<figure><img src="image_5.png" /><figcaption>Figure 3: The root system $G_2$ in $\mathbb{R}^3/\langle [1, 1, 1]^t \rangle$.</figcaption></figure>

$$ \begin{align*} W(C_2) &\cong \mathfrak{S}_2 \times \{\pm 1\}^2 \\ \omega_1 &= [1, 0]^t \\ \omega_2 &= [1, 1]^t \\ \rho_1 &= [1, -1]^t = \rho_1^\vee \\ \rho_2 &= [0, 2]^t = 2 \rho_2^\vee \\ \rho_0 &= 2 \rho_1^\vee + 2 \rho_2^\vee \end{align*} $$

<caption>Figure 4: The root system $C_2$ in $\mathbb{R}^2$.</caption>

Here, the roots are depicted in green, the base in red and the fundamental weights in blue. The Voronoi cell of the coroot lattice $\Lambda$ is the gray shaded region: there are two squares ($C_2$ and $B_2$) and two hexagons ($A_2$ and $G_2$). The fundamental domain of the affine Weyl group is the blue shaded simplex.
## 2.2 Trigonometric polynomials with Weyl group symmetry

From now on, $\mathbb{R}$ is a root system in $\mathbb{R}^n$ with Weyl group $W$, weight lattice $\Omega = \mathbb{Z}\omega_1 \oplus \dots \oplus \mathbb{Z}\omega_n$ and coroot lattice $\Lambda = \Omega^*$. For $\mu \in \Omega$, we define the function

$$ \mathfrak{c}^{\mu}: \mathbb{R}^n \to \mathbb{C}, \\ u \mapsto \exp(-2\pi i \langle \mu, u \rangle). $$

A $\mathbb{C}$-linear combination of these functions is a **trigonometric polynomial**. The set of all trigonometric polynomials forms an algebra that we denote by $\mathbb{C}[\Omega]$.

The set $\{\mathfrak{c}^{\mu} | \mu \in \Omega\}$ is closed under multiplication $\mathfrak{c}^{\mu} \mathfrak{c}^{\tilde{\mu}} = \mathfrak{c}^{\mu+\tilde{\mu}}$ and thus a group with neutral element $\mathfrak{c}^0$ and inverse $(\mathfrak{c}^{\mu})^{-1} = \mathfrak{c}^{-\mu}$. Since $\Omega$ is the free $\mathbb{Z}$-module generated by the $\omega_i$, $\mathbb{C}[\Omega]$ is generated by $\{\mathfrak{c}^{\pm\omega_1}, \dots, \mathfrak{c}^{\pm\omega_n}\}$.

Since the coroot lattice $\Lambda$ is the dual lattice of $\Omega$, any element $f \in \mathbb{C}[\Omega]$ is $\Lambda$-periodic, that is, for all $u \in \mathbb{R}^n$ and $\lambda \in \Lambda$, we have $f(u + \lambda) = f(u)$.

### 2.2.1 Generalized cosines and Chebyshev polynomials

The Weyl group $W$ acts linearly on $\mathbb{C}[\Omega]$ by the action described on its basis as

$$ \begin{array}{ccc} \cdot: & W \times \mathbb{C}[\Omega] & \to \mathbb{C}[\Omega], \\ & (s, \mathfrak{c}^{\mu}) & \mapsto \mathfrak{c}^{s(\mu)}. \end{array} $$

A trigonometric polynomial $f \in \mathbb{C}[\Omega]$ is called **$W$-invariant**, if, for all $s \in W$, we have $s \cdot f = f$. The **generalized cosine function** associated to $\mu \in \Omega$ is the $W$-invariant trigonometric polynomial

$$ \mathfrak{c}_{\mu}: \mathbb{R}^n \to \mathbb{C}, \\ u \mapsto \frac{1}{|W|} \sum_{s \in W} \mathfrak{c}^{s(\mu)}(u). \qquad (2.2) $$

**Theorem 2.5.** [Bou68, Ch. VI, §3, Thm. 1] The following statements hold.

1. The $\mathfrak{c}_{\omega_1}, \dots, \mathfrak{c}_{\omega_n}$ are $\mathbb{C}$-algebraically independent.

2. The set of $W$-invariants is the polynomial $\mathbb{C}$-algebra generated by the $\mathfrak{c}_{\omega_1}, \dots, \mathfrak{c}_{\omega_n}$, that is,

$$ \mathbb{C}[\Omega]^W = \mathbb{C}[\mathfrak{c}_{\omega_1}, \dots, \mathfrak{c}_{\omega_n}]. $$

The above Theorem 2.5 states that, for every $f \in \mathbb{C}[\Omega]^W$, there exists a unique polynomial $g \in \mathbb{C}[z] := \mathbb{C}[z_1, \dots, z_n]$ with the property $f(u) = g(\mathfrak{c}(u))$, where $\mathfrak{c}$ is the function

$$ \mathfrak{c}: \mathbb{R}^n \to \mathbb{C}^n, \\ u \mapsto (\mathfrak{c}_{\omega_1}(u), \dots, \mathfrak{c}_{\omega_n}(u)). $$

This property is exclusive for Weyl groups [Far86].

**Definition 2.6.** The generalized Chebyshev polynomial of the first kind associated to $\mu \in \Omega$ is the unique $T_{\mu} \in \mathbb{C}[z]$ satisfying $T_{\mu}(\mathfrak{c}(u)) = \mathfrak{c}_{\mu}(u)$.

The coefficients of the $T_{\mu}$ are rational. We have $T_0 = 1$, $T_{\omega_i} = z_i$ and, for $\mu, \nu \in \Omega$,

$$ |W| T_{\mu} T_{\nu} = \sum_{s \in W} T_{s(\mu)+\nu}. \qquad (2.3) $$

Moreover, if $\hat{\mu} \in \Omega^+$ is the unique dominant weight with $\mu \in W\hat{\mu}$, then $T_{\mu} = T_{\hat{\mu}}$. The set $\{T_{\mu} | \mu \in \Omega^+\}$ forms a vector space basis of $\mathbb{C}[z]$ [Lor05, Eq. (3.4)].

This definition is a generalization of the univariate Chebyshev polynomials of the first kind $T_{\ell}(\cos(u)) = \cos(\ell u)$ with $\ell \in \mathbb{Z}$, which correspond to the root system $A_1$.
### 2.2.2 Real cosines and Chebyshev polynomials

For our approach in Section 3, we need the generalized Chebyshev polynomials to be defined on a real domain. For $u \in \mathbb{R}^n$ and $1 \le i \le n$, we observe

$$ \overline{\mathbf{c}_i(u)} = \mathbf{c}_i(-u) = (-\mathrm{Id}_n \cdot \mathbf{c}_i)(u) = \mathbf{c}_{\sigma(i)}(u), \qquad (2.4) $$

where $\mathrm{Id}_n$ is the identity on $\mathbb{R}^n$ and $\sigma \in \mathfrak{S}_n$ is the permutation from Proposition 2.1. Hence, if $-\mathrm{Id}_n \notin \mathcal{W}$, or equivalently, if $\sigma$ is not trivial, then the image of the map $\mathbf{c}$ is not contained in $\mathbb{R}^n$. The irreducible root systems, for which this is the case, are both $A_{n-1}$ and $D_{2n-1}$ whenever $n \ge 3$ as well as $E_6$.

We fix this circumstance in a straightforward manner: When $j = \sigma(j)$, we set $\mathbf{c}_{j,\mathbb{R}} := \mathbf{c}_{j,\mathbb{R}} \in \mathbb{C}[\Omega]^W$. When $j < \sigma(j)$, we replace the $j$-th, respectively $\sigma(j)$-th, coordinate of $\mathbf{c}$ by $\mathbf{c}_{j,\mathbb{R}} := (\mathbf{c}_j + \mathbf{c}_{\sigma(j)})/2 \in \mathbb{C}[\Omega]^W$, respectively $\mathbf{c}_{\sigma(j),\mathbb{R}} := (\mathbf{c}_j - \mathbf{c}_{\sigma(j)})/(2i) \in \mathbb{C}[\Omega]^W$. For $u \in \mathbb{R}^n$, we have $\mathbf{c}_{j,\mathbb{R}}(u) = \Re(\mathbf{c}_{j,\mathbb{R}}(u)) \in \mathbb{R}$ and $\mathbf{c}_{\sigma(j),\mathbb{R}}(u) = \Im(\mathbf{c}_{j,\mathbb{R}}(u)) \in \mathbb{R}$. Thus, the image of the map

$$ \begin{array}{rcl} \mathbf{c}_{\mathbb{R}}: & \mathbb{R}^n & \to \mathbb{R}^n, \\ & u & \mapsto (\mathbf{c}_{1,\mathbb{R}}(u), \dots, \mathbf{c}_{n,\mathbb{R}}(u)) \end{array} \qquad (2.5) $$

is contained in the cube $[-1, 1]^n \subseteq \mathbb{R}^n$.

**Proposition 2.7.** Let $\mu, \hat{\mu} \in \Omega$ with $-\mu \in \mathcal{W}\hat{\mu}$. Then there exist unique $\hat{T}_{\mu}, \hat{T}_{\hat{\mu}} \in \mathbb{R}[z]$, such that

$$ T_{\mu}(\mathbf{c}(u)) = \hat{T}_{\mu}(\mathbf{c}_{\mathbb{R}}(u)) + i \hat{T}_{\hat{\mu}}(\mathbf{c}_{\mathbb{R}}(u)) \quad \text{and} \quad T_{\hat{\mu}}(\mathbf{c}(u)) = \hat{T}_{\mu}(\mathbf{c}_{\mathbb{R}}(u)) - i \hat{T}_{\hat{\mu}}(\mathbf{c}_{\mathbb{R}}(u)). $$

*Proof.* Assume that $T_{\mu} = \sum_{\nu} c_{\nu} z^{\nu}$ for some $c_{\nu} \in \mathbb{Q}$ and $\nu \in \mathbb{N}^n$. For $u \in \mathbb{R}^n$, we observe that

$$ T_{\mu}(\mathbf{c}(u)) = \sum_{\nu} c_{\nu} \prod_{j=1}^{n} (\Re(\mathbf{c}_{j}(u)) + i \Im(\mathbf{c}_{j}(u)))^{\nu_{j}} \quad \text{and} \quad T_{\hat{\mu}}(\mathbf{c}(u)) = \sum_{\nu} c_{\nu} \prod_{j=1}^{n} (\Re(\mathbf{c}_{\sigma(j)}(u)) + i \Im(\mathbf{c}_{\sigma(j)}(u)))^{\nu_{j}} $$

are complex conjugates.

Furthermore, if $j = \sigma(j)$, then $\Re(\mathbf{c}_j(u)) = \mathbf{c}_{j,\mathbb{R}}(u)$ and $\Im(\mathbf{c}_j(u)) = 0$. Otherwise, our definition of $\mathbf{c}_{j,\mathbb{R}}$ implies

$$ \Re(\mathbf{c}_j(u)) = \begin{cases} \mathbf{c}_{j,\mathbb{R}}(u), & \text{if } j < \sigma(j) \\ \mathbf{c}_{\sigma(j),\mathbb{R}}(u), & \text{if } j > \sigma(j) \end{cases} \quad \text{and} \quad \Im(\mathbf{c}_j(u)) = \begin{cases} \mathbf{c}_{\sigma(j),\mathbb{R}}(u), & \text{if } j < \sigma(j) \\ -\mathbf{c}_{j,\mathbb{R}}(u), & \text{if } j > \sigma(j) \end{cases}. $$

Altogether, we obtain

$$ \frac{T_{\mu}(\vartheta(u)) + T_{\hat{\mu}}(\mathbf{c}(u))}{2} = \sum_{\nu} \frac{c_{\nu}}{2} \prod_{j=\sigma(j)} \mathbf{c}_{j,\mathbb{R}}(u)^{\nu_j} \left( \prod_{j<\sigma(j)} (\mathbf{c}_{j,\mathbb{R}}(u) + i \mathbf{c}_{\sigma(j),\mathbb{R}}(u))^{\nu_j} (\mathbf{c}_{j,\mathbb{R}}(u) - i \mathbf{c}_{\sigma(j),\mathbb{R}}(u))^{\nu_{\sigma(j)}} \right. \\ \left. + \prod_{j<\sigma(j)} (\mathbf{c}_{j,\mathbb{R}}(u) - i \mathbf{c}_{\sigma(j),\mathbb{R}}(u))^{\nu_j} (\mathbf{c}_{j,\mathbb{R}}(u) + i \mathbf{c}_{\sigma(j),\mathbb{R}}(u))^{\nu_{\sigma(j)}} \right). $$

The right hand side is a unique polynomial in $\mathbf{c}_{\mathbb{R}}(u) = (\mathbf{c}_{1,\mathbb{R}}(u), \dots, \mathbf{c}_{n,\mathbb{R}}(u))$, denoted by $\hat{T}_{\mu}$. Since the left hand side is real for every $u \in \mathbb{R}^n$, the coefficient of $\hat{T}_{\mu}$ in front of $i$ must be 0. Hence, we have $\hat{T}_{\mu} \in \mathbb{C}[z]$. Similarly, by computing $(T_{\mu} - T_{\hat{\mu}})/(2i)$, we obtain $\hat{T}_{\hat{\mu}} \in \mathbb{C}[z]$. $\square$

**Convention 2.8.** From now on, we will write $T_{\mu}$ and $\mathbf{c}$ for $\hat{T}_{\mu}$ and $\mathbf{c}_{\mathbb{R}}$, even if $-\mathrm{Id}_n \notin \mathcal{W}$. As we have shown above, the reformulation follows from a permutation $\sigma$ and a substitution $z_i \mapsto z_i \pm i z_{\sigma(i)}$. For computations, it is important to remember this caveat, but for the article itself, we shall simplify the notation.
## 2.3 The image of the generalized cosines as a basic semi-algebraic set

We call $\mathcal{T} := \mathfrak{c}(\mathbb{R}^n)$ the **image of the generalized cosines**. If $\Delta$ is a fundamental domain for the affine Weyl group $\mathcal{W} \times \Lambda$, then $\mathcal{T} = \mathfrak{c}(\Delta)$ due to the $\mathcal{W}$-invariance and $\Lambda$-periodicity. In particular, $\mathcal{T}$ is compact. With Convention 2.8, $\mathcal{T}$ is a real set and contained in the cube $[-1, 1]^n$.

For the purpose of optimization, we need a polynomial description of $\mathcal{T}$ as a basic semi-algebraic set. Recently, a closed formula was given via a polynomial matrix inequality. This formula is available in the standard monomial basis $z$ and in the basis of generalized Chebyshev polynomials $T_\mu$ [HMR24, Met22].

**Theorem 2.9.** [HMR24, Thm. 10.1] Let $\mathbb{R}$ be a root system of type $A_{n-1}$, $B_n$, $C_n$, $D_n$ or $G_2$. A point $z \in \mathbb{R}^n$ is contained in $\mathcal{T}$ if and only if $\mathbf{P}(z)$ is positive semi-definite, where $\mathbf{P} \in \mathbb{R}[z]^{n \times n}$ has entries<fnref n="2" />

$$ \mathbf{P}(z)_{ij} = -T_{(i+j)\omega_1}(z) + \sum_{\ell=1}^{\lceil(i+j)/2\rceil-1} \left(4\binom{i+j-2}{\ell-1} - \binom{i+j}{\ell}\right) T_{(i+j-2\ell)\omega_1}(z) \\ + \frac{1}{2} \begin{cases} 4\binom{i+j-2}{(i+j)/2-1} - \binom{i+j}{(i+j)/2}, & \text{if } i+j \text{ is even} \\ 0, & \text{if } i+j \text{ is odd} \end{cases} $$

In other words, $\mathcal{T}$ is the positivity locus of $\mathbf{P} \in \mathbb{R}[z]^{n \times n}$ in $\mathbb{R}^n$. From now on we write $\mathbf{P}(z) \succeq 0$ to denote positive semi-definiteness. The matrix $\mathbf{P}$ follows the Hankel pattern

$$ \begin{bmatrix} T_0 - T_2 \omega_1 & T_1 - T_3 \omega_1 & T_4 - T_5 \omega_1 & T_6 - T_7 \omega_1 & T_8 - T_9 \omega_1 & \cdots \\ T_0 - T_2 \omega_1 & T_1 - T_3 \omega_1 & T_4 - T_5 \omega_1 & T_6 - T_7 \omega_1 & T_8 - T_9 \omega_1 & \cdots \\ T_0 - T_2 \omega_1 & T_1 - T_3 \omega_1 & T_4 - T_5 \omega_1 & T_6 - T_7 \omega_1 & T_8 - T_9 \omega_1 & \cdots \\ 2 T_1 - T_3 \omega_1 & 2 T_1 - T_3 \omega_1 & 2 T_1 - T_3 \omega_1 & 2 T_1 - T_3 \omega_1 & 2 T_1 - T_3 \omega_1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ 2 T_1 - T_3 \omega_1 & 2 T_1 - T_3 \omega_1 & 2 T_1 - T_3 \omega_1 & 2 T_1 - T_3 \omega_1 & 2 T_1 - T_3 \omega_1 & \cdots \end{bmatrix} $$

<figure><img src="image_6.png" /><figcaption>Figure 5: The image of the generalized cosines for the irreducible root systems of rank 2 and 3.</figcaption></figure>

<footnote n="2">²If $\mathbb{R}$ is of type $A_{n-1}$ and $n \ge 3$, then $z \in \mathbb{R}^{n-1}$, but $\mathbf{P}$ is $n \times n$ (similar for $G_2$).</footnote>
**Remark 2.10.**

1. If we are in one of the special cases E$_6$, E$_7$, E$_8$ or F$_4$, then such a polynomial description of $\mathcal{T}$ can also be obtained with [PS85, §4]. In this case, one obtains a Gram matrix of differentials and has to rewrite the entries in the coordinates $z$ of $\mathcal{T}$.

2. The root system may not be irreducible, that is, $\mathbb{R} = \mathbb{R}^{(1)} \cup \dots \cup \mathbb{R}^{(k)}$ for some $k \in \mathbb{N}$ and irreducible $\mathbb{R}^{(i)}$. Then we write the fundamental domain of the affine Weyl group as $\Delta = \Delta^{(1)} \times \dots \times \Delta^{(k)}$ and obtain $\mathcal{T} = \mathfrak{c}(\Delta)$ as the positivity locus of a block-diagonal matrix polynomial

$$ \mathbf{P}(z^{(1)}, \dots, z^{(k)}) = \mathrm{diag}(\mathbf{P}^{(1)}(z^{(1)}), \dots, \mathbf{P}^{(k)}(z^{(k)})) $$

where $\mathbf{P}^{(i)}$ is a matrix polynomial in indeterminates $z_1^{(i)}, z_2^{(i)}, \dots$ corresponding to $\mathbb{R}^{(i)}$.

As an example, take $k$ orthogonal copies of $A_1$. Then $\mathcal{T} = [-1, 1]^k$ is the positivity locus of the matrix polynomial $\mathbf{P} = \mathrm{diag}(1 - (z_1^{(1)})^2, \dots, 1 - (z_1^{(k)})^2)$.

## 2.4 Optimizing trigonometric polynomials with crystallographic symmetry

We now address the trigonometric optimization problem from Equation (1.1). With the theory that was presented in the previous subsections, we can rewrite the objective function uniquely in terms of generalized Chebyshev polynomials using Theorem 2.5. Indeed, with the generalized cosines from Equation (2.2) we can write any $f \in \mathbb{C}[\Omega]^W$ uniquely as

$$ f = \sum_{\mu \in S} c_{\mu} \mathfrak{c}_{\mu} $$

for some finite set $S \subseteq \Omega^+$ of dominant weights. If $c_{\mu} = \overline{c_{\mu}} \in \mathbb{R}$ whenever $-\mu \in W\hat{\mu}$, then $f$ takes only real values and

$$ f^* := \min_{u \in \mathbb{R}^n} f(u) = \min_{z \in \mathcal{T}} \sum_{\mu \in S} c_{\mu} T_{\mu}(z) \quad (2.6) $$

is the global minimum of $f$ on $\mathbb{R}^n$. This transforms the region of optimization from $\mathbb{R}^n$ into the image $\mathcal{T}$ of the generalized cosines. Thanks to Theorem 2.9, we can describe the latter explicitly as a compact basic semi-algebraic set with the Chebyshev basis. This makes it possible to solve the problem numerically with techniques from classical polynomial optimization, which is subject to Section 3.

**Example 2.11.** The symmetric group $\mathfrak{S}_3$ acts on $\mathbb{R}^3/\langle[1, 1, 1]^t\rangle$ by permutation of coordinates and leaves the lattice $\Omega := \mathbb{Z}\omega_1 + \mathbb{Z}\omega_2 := \mathbb{Z}[0, -1, -1]^t + \mathbb{Z}[-1, -1, 2]^t$ invariant. This is the weight lattice of the root system $G_2$ with Weyl group $\mathcal{W} := \mathfrak{S}_3 \times \{\pm 1\}$. We consider the $\mathcal{W}$-invariant trigonometric polynomial

$$ \begin{aligned} f(u) &:= \mathfrak{c}_{2\omega_1}(u) + 2\mathfrak{c}_{\omega_2}(u) \\ &= (\cos(2\pi\langle 2\omega_1, u \rangle) + \cos(2\pi\langle 2\omega_1 - 2\omega_2, u \rangle) + \cos(2\pi\langle 4\omega_1 - 2\omega_2, u \rangle) \\ &\quad + 2\cos(2\pi\langle \omega_2, u \rangle) + 2\cos(2\pi\langle 3\omega_1 - \omega_2, u \rangle) + 2\cos(2\pi\langle 3\omega_1 - 2\omega_2, u \rangle))/3 \end{aligned} $$

with $u = (u_1, u_2, -u_1 - u_2) \in \mathbb{R}^3/\langle[1, 1, 1]^t\rangle$. In the coordinates $z = \mathfrak{c}(u) = (\mathfrak{c}_{\omega_1}(u), \mathfrak{c}_{\omega_2}(u)) \in \mathcal{T}$, we have

$$ f(z) = T_{2\omega_1}(z) + 2T_{\omega_2}(z) = (6z_1^2 - 2z_1 - 2z_2 - 1) + 2(z_2) = 6z_1^2 - 2z_1 - 1. $$

Hence, the minimum of $f$ is

$$ f^* = \min_{u_1, u_2 \in \mathbb{R}} f(u_1, u_2, -u_1 - u_2) = \min_{z \in \mathcal{T}} 6z_1^2 - 2z_1 - 1 = -\frac{7}{6} $$

(We compute the minimum later in Equation (4.6)).
<figure><img src="image_7.png" /><figcaption>Figure 6: The support of $f$ as a trigonometric polynomial on the left consists of the $W$-orbits of $2\omega_1$ and $\omega_2$. The graph of this $W$-invariant $\Lambda$-periodic function is depicted in the middle. The image of the generalized cosines $\mathcal{T}$ on the right is the new feasible region of the polynomial optimization problem.</figcaption></figure>

# 3 Optimization in terms of generalized Chebyshev polynomials

In the previous section, we have shown that the trigonometric optimization problem with crystallographic symmetry from Equation (1.1) is equivalent to optimizing a classical polynomial in the Chebyshev basis

$$f(z) = \sum_{\mu \in S} c_{\mu} T_{\mu}(z) \in \mathbb{R}[z] \qquad (3.1)$$

over $\mathcal{T}$, where $S \subseteq \Omega^+$ finite and $c_{\mu} \in \mathbb{R}$. Here, $\mathcal{T}$ is the image of the generalized cosines, a compact basic semi-algebraic set that can be represented as

$$\mathcal{T} = \{c(u) | u \in \mathbb{R}^n\} = \{z \in \mathbb{R}^n | \mathbf{P}(z) \geq 0\},$$

where $\mathbf{P} \in \mathbb{R}[z]^{n \times n}$ is a symmetric matrix polynomial, for example given by Theorem 2.9. In the present section, we show how to solve this new polynomial optimization problem

$$f^* = \min_{z \in \mathcal{T}} f(z) = \min_{\substack{f(z) \\ \text{s.t. } z \in \mathbb{R}^n, \mathbf{P}(z) \geq 0}} f(z) \qquad (3.2)$$

numerically. We do this by adapting Lasserre's hierarchy. The novelty lies in exploiting the representation of the objective function in terms of generalized Chebyshev polynomials, which leads to an adapted notion of the hierarchy order.

The computations for the examples in this section are documented here:

https://tobiasmetzlaff.com/html_guides/polynomial_optimization.html

## 3.1 Matrix version of Putinar's theorem

In [Las01], Lasserre proposes a hierarchy of dual moment relaxations and sums of squares (SOS) reinforcements based on Putinar's Positivstellensatz [Put93] to approximate the minimum, when the polynomial matrix inequality $\mathbf{P}(z) \geq 0$ (PMI) is replaced by finitely many scalar constraints. In principle, our problem falls in this setting. Indeed, the PMI can be rewritten to scalar inequalities by taking the coefficients of the characteristic polynomial and using Descartes' rule of signs [BPR06, Theorem 2.33]. We would prefer to avoid such an approach, since the degrees of the so obtained scalar constraints are generically much larger than the entries of the matrix polynomial $\mathbf{P}$.
To overcome this degree problem, Henrion and Lasserre [HL06] suggest using another Positivstellensatz due to Hol and Scherer, see Theorem 3.1, and propose a hierarchy of dual moment relaxations and matrix SOS reinforcements, that benefits from the matrix structure.

### 3.1.1 Matrix SOS reinforcement

A matrix polynomial $\mathbf{Q} \in \mathbb{R}[z]^{n \times n}$ is said to be a **sum of squares**, if there exist $k \in \mathbb{N}$ and $\mathbf{Q}_1, \dots, \mathbf{Q}_k \in \mathbb{R}[z]^n$, such that

$$ \mathbf{Q}(z) = \sum_{i=1}^{k} \mathbf{Q}_i(z) \mathbf{Q}_i(z)^t. $$

We write $\mathbf{Q} \in \text{SOS}(\mathbb{R}[z]^n)$ and denote by

$$ \text{QM}(\mathbf{P}) := \{q + \text{Trace}(\mathbf{P} \mathbf{Q}) \mid q \in \text{SOS}(\mathbb{R}[z]), \mathbf{Q} \in \text{SOS}(\mathbb{R}[z]^n)\} $$

the quadratic module of $\mathbf{P}$. Then every element of $\text{QM}(\mathbf{P})$ is nonnegative on $\mathcal{T}$ and enforcing this constraint gives a lower bound

$$ \begin{array}{ll} f^* = \max & \lambda \\ \text{s.t.} & \lambda \in \mathbb{R}, \forall z \in \mathcal{T}: f(z) - \lambda \ge 0 \end{array} \qquad \begin{array}{ll} \ge f_{\text{sos}} := \sup & \lambda \\ \text{s.t.} & \lambda \in \mathbb{R}, f - \lambda \in \text{QM}(\mathbf{P}). \end{array} \qquad (3.3) $$

### 3.1.2 Moment relaxation

A linear functional $\mathcal{L} \in \mathbb{R}[z]^*$ is said to have a **representing probability measure on $\mathcal{T}$**, if there exists a probability measure $\eta$ on $\mathbb{R}^n$ with support in $\mathcal{T}$, such that, for all $p \in \mathbb{R}[z]$, $\int_{\mathcal{T}} p(z) d\eta(z) = \mathcal{L}(p)$. For example, since $\mathcal{T}$ is compact, there exists a minimizer $z^* \in \mathcal{T}$ with $f^* = f(z^*)$. Then the evaluation $\mathcal{L}(p) := p(z^*)$ is a linear functional and represented by a normalized Dirac measure. On the other hand, for any $\mathcal{L}$ with representing probability measure $\eta$, we have

$$ \mathcal{L}(f) = \int_{\mathcal{T}} f(z) d\eta(z) \ge \int_{\mathcal{T}} f^* d\eta(z) = f^* \underbrace{\int_{\mathcal{T}} 1 d\eta(z)}_{=1} = f^* $$

and, if $p = q + \text{Trace}(\mathbf{P} \mathbf{Q}) \in \text{QM}(\mathbf{P})$, then

$$ \mathcal{L}(p) = \int_{\mathcal{T}} q(z) + \text{Trace}(\mathbf{P}(z) \mathbf{Q}(z)) d\eta(z) = \sum_{i=1}^{k} \int_{\mathcal{T}} \underbrace{q_i(z)^2}_{\ge 0} d\eta(z) + \sum_{j=1}^{\ell} \int_{\mathcal{T}} \underbrace{\mathbf{Q}_j(z)^t \mathbf{P}(z) \mathbf{Q}_j(z)}_{\ge 0} d\eta(z) \ge 0. $$

Altogether, we obtain another lower bound

$$ \begin{array}{ll} f^* = \min & \mathcal{L}(f) \\ \text{s.t.} & \mathcal{L} \in \mathbb{R}[z]^* \text{ has a representing probability measure on } \mathcal{T} \end{array} \qquad \begin{array}{ll} \ge f_{\text{mom}} := \inf & \mathcal{L}(f) \\ \text{s.t.} & \mathcal{L} \in \mathbb{R}[z]^*, \mathcal{L}(1) = 1, \\ & \forall p \in \text{QM}(\mathbf{P}): \mathcal{L}(p) \ge 0. \end{array} \qquad (3.4) $$

We have $f_{\text{sos}} \le f_{\text{mom}}$. Indeed, if $\mathcal{L}$ is feasible for $f_{\text{mom}}$ and $\lambda$ is feasible for $f_{\text{sos}}$, then

$$ \mathcal{L}(f) - \lambda = \mathcal{L}(\underbrace{f - \lambda}_{\in \text{QM}(\mathbf{P})}) \ge 0. \qquad (3.5) $$

We say that $\text{QM}(\mathbf{P})$ is **Archimedean**, if there exists $p \in \text{QM}(\mathbf{P})$, such that $\{z \in \mathbb{R}^n | p(z) \ge 0\}$ is compact.
**Theorem 3.1.** [HS05, HS06] If QM(P) is Archimedean, then the following statements hold.

1. Let $p \in \mathbb{R}[z]$. If $p > 0$ on $T$, then $p \in \text{QM}(\mathbf{P})$.

2. Let $\mathcal{L} \in \mathbb{R}[z]^*$. If $\mathcal{L} \ge 0$ on QM($\mathbf{P}$), then $\mathcal{L}$ has a representing probability measure on $T$.

3. Equality holds in both Equation (3.3) and Equation (3.4).

**Remark 3.2.** In practice, the Archimedean property is enforced by adding a ball constraint: For $z \in T \subseteq [-1, 1]^n$, we have $n \ge \|z\|^2$, and thus $T = \{z \in \mathbb{R}^n | \hat{\mathbf{P}}(z) \ge 0\}$, where $\hat{\mathbf{P}} := \text{diag}(\mathbf{P}, n - \|z\|^2) \in \mathbb{R}[z]^{(n+1)\times(n+1)}$. With $\mathbf{Q} = \text{diag}(0, \dots, 0, 1) \in \text{SOS}(\mathbb{R}[z]^{n+1})$, we have $n - \|z\|^2 = \text{Trace}(\hat{\mathbf{P}} \mathbf{Q}) \in \text{QM}(\hat{\mathbf{P}})$ and the set $\{z \in \mathbb{R}^n | n - \|z\|^2 \ge 0\}$ is compact. In particular, QM($\hat{\mathbf{P}}$) is Archimedean.

## 3.2 Lasserre hierarchy with Chebyshev polynomials

The conditions $f - \lambda \in \text{QM}(\mathbf{P})$ from Equation (3.3) and $\mathcal{L} \ge 0$ on QM($\mathbf{P}$) from Equation (3.4) can be parametrized through positive semi-definite constraints, but for computations we need to restrict to finite dimensional subspaces of $\mathbb{R}[z]$. We shall now introduce these constraints in the basis of generalized Chebyshev polynomials and then adapt Lasserre's hierarchy [Las01] to approximate the optimal value $f^*$ with semi-definite programs [BV96]. In particular, we present these positive semi-definite conditions in the way they are implemented in the MAPLE package.

### 3.2.1 Chebyshev filtration

For $\mathcal{L} \in \mathbb{R}[z]^*$, we define the infinite symmetric matrix $\mathbf{H}^{\mathcal{L}} := \mathcal{L}(\mathbf{T}\mathbf{T}^t)$, where $\mathbf{T}$ is the vector of basis elements $T_\mu$ with $\mu \in \Omega^+$ and $\mathcal{L}$ applies entry-wise.

Then we can also define the $\mathbf{P}$-localized matrix $\mathbf{H}^{\mathbf{P}*\mathcal{L}} := \mathcal{L}(\mathbf{P} \otimes (\mathbf{T}\mathbf{T}^t))$. Here, $\otimes$ denotes the Kronecker product. The entries of this infinite matrix, indexed by $\mu, \nu \in \Omega^+$, are symmetric $n \times n$ blocks.

As in [HL06], we observe that $\mathcal{L} \ge 0$ on QM($\mathbf{P}$) is equivalent to $\mathbf{H}^{\mathcal{L}} \ge 0$ and $\mathbf{H}^{\mathbf{P}*\mathcal{L}} \ge 0$. By Equation (2.3), for $\mu, \nu \in \Omega^+$, the entries of $\mathbf{H}^{\mathcal{L}}$ are

$$ \mathbf{H}_{\mu\nu}^{\mathcal{L}} = \mathcal{L}(T_{\mu} T_{\nu}) = \frac{1}{|W|} \sum_{s \in W} \mathcal{L}(T_{s(\mu)+\nu}) \in \mathbb{R}. \quad (3.6) $$

Furthermore, let us assume that the matrix $\mathbf{P}$ in Equation (3.2) is represented in the Chebyshev basis as

$$ \mathbf{P}(z) = \sum_{\gamma \in \Omega^+} \mathbf{P}_{\gamma} T_{\gamma}(z) \in \mathbb{R}[z]^{n \times n} $$

with $\mathbf{P}_{\gamma} \in \mathbb{R}^{n \times n}$. The entries of $\mathbf{H}^{\mathbf{P}*\mathcal{L}}$ are the blocks

$$ \mathbf{H}_{\mu\nu}^{\mathbf{P}*\mathcal{L}} = \sum_{\gamma \in \Omega^+} \mathbf{P}_{\gamma} \mathcal{L}(T_{\mu} T_{\nu} T_{\gamma}) = \frac{1}{|W|^2} \sum_{\gamma \in \Omega^+} \sum_{s,r \in W} \mathcal{L}(T_{s(\mu)+r(\nu)+\gamma}) \in \mathbb{R}^{n \times n}. \quad (3.7) $$

Restricting $\mathcal{L}$ to a finite dimensional subspace of $\mathbb{R}[z]$ in Equation (3.4) means to truncate the matrices $\mathbf{H}^{\mathcal{L}}$ and $\mathbf{H}^{\mathbf{P}*\mathcal{L}}$ to the corresponding rows and columns. However, since we have chosen the Chebyshev polynomials as a basis, we need to ensure that these matrices are well-defined: For an index of the form $s(\mu) + \nu$ in Equation (3.6), there is a unique dominant weight in the same $\mathcal{W}$-orbit, say $\tilde{\mu} \in \Omega^+$, and $\mathcal{L}$ must be defined on $T_{\tilde{\mu}}$, so that we can compute the matrix entries of $\mathbf{H}^{\mathcal{L}}$ (and similarly for $\mathbf{H}^{\mathbf{P}*\mathcal{L}}$).
**Proposition 3.3.** Let $\mathbb{R}$ be an irreducible root system with highest root $\rho_0$. For $d \in \mathbb{N}$, we define the finite dimensional $\mathbb{R}$-vector subspace

$$ \mathcal{F}_d := \langle \{T_\mu | \mu \in \Omega^+, \langle \mu, \rho_0^\vee \rangle \le d \} \rangle_{\mathbb{R}} $$

of $\mathbb{R}[z]$. Then $(\mathcal{F}_d)_{d \in \mathbb{N}}$ is a filtration of $\mathbb{R}[z]$ as an $\mathbb{R}$-algebra, that is,

$$ 1. \mathbb{R}[z] = \bigcup_{d \in \mathbb{N}} \mathcal{F}_d \text{ and} $$

$$ 2. \mathcal{F}_{d_1} \mathcal{F}_{d_2} \subseteq \mathcal{F}_{d_1+d_2} \text{ whenever } d_1, d_2 \in \mathbb{N}. $$

*Proof.* 1. Take an arbitrary polynomial $p = \sum_\mu \tilde{c}_\mu T_\mu \in \mathbb{R}[z]$ and choose $d \in \mathbb{N}$ with $d \ge \langle \mu, \rho_0^\vee \rangle$ whenever $\tilde{c}_\mu \ne 0$. Then we have $p \in \mathcal{F}_d$.

2. Let $T_\mu \in \mathcal{F}_{d_1}$ and $T_\nu \in \mathcal{F}_{d_2}$. Then $|\mathcal{W}| T_\mu T_\nu = \sum_{s \in \mathcal{W}} T_{s(\mu)+\nu}$. For all $s \in \mathcal{W}$, there exists $r \in \mathcal{W}$, such that $r(s(\mu) + \nu) \in \Omega^+$. By [Bou68, Ch. VI, §1, Prop. 18], $\mu - r(\mu)$ and $\nu - r(s(\nu))$ are sums of positive roots. Hence, there exists $\alpha \in \mathbb{N}^n$, such that

$$ \langle r(s(\mu) + \nu), \rho_0^\vee \rangle = \langle \mu + \nu, \rho_0^\vee \rangle - \sum_{i=1}^{n} \alpha_i \langle \rho_i, \rho_0^\vee \rangle. $$

By [Bou68, Ch. VI, §1, Prop. 25], we have $\rho_0^\vee \in \overline{\mathbb{M}}$ and thus $\langle \rho_i, \rho_0^\vee \rangle \ge 0$. We obtain

$$ \langle r(s(\mu) + \nu), \rho_0^\vee \rangle \le \langle \mu + \nu, \rho_0^\vee \rangle \le d_1 + d_2. $$

Therefore, $T_\mu T_\nu \in \mathcal{F}_{d_1+d_2}$.

□

**Remark 3.4.** For irreducible root systems, the filtration from Proposition 3.3 induces a weighted degree on $\mathbb{R}[z]$. Otherwise, we can always construct a filtration by choosing an order on the irreducible components. From now on, we may therefore assume all root systems to be irreducible.

### 3.2.2 Modified Lasserre hierarchy

When $\mathcal{L}$ is only defined on $\mathcal{F}_{2d}$, that is, $\mathcal{L} \in \mathcal{F}_{2d}^*$, then the matrix $\mathbf{H}^{\mathcal{L}}$ is by Proposition 3.3 well-defined for all rows and columns up to weighted degree $d$. We denote this truncated matrix of size $\dim(\mathcal{F}_d)$ by $\mathbf{H}_d^{\mathcal{L}}$. Analogously, for

$$ d \ge D := \min\{\lceil \ell/2 \rceil | \ell \in \mathbb{N}, \mathbf{P} \in (\mathcal{F}_\ell)^{n \times n}\}, $$

the truncated $\mathbf{P}$-localized matrix $\mathbf{H}_{d-D}^{\mathcal{P}*\mathcal{L}}$ is well-defined and of size $\dim(\mathcal{F}_{d-D})$.

On the other hand, if $\mathbf{Q}_1, \dots, \mathbf{Q}_k \in \mathcal{F}_d^n$ are polynomial vectors with entries of weighted degree at most $d$, then the polynomial matrix $\mathbf{Q} = \sum_i \mathbf{Q}_i \mathbf{Q}_i^t \in \mathcal{F}_{2d}^{n \times n}$ is a sum of squares. We write $\mathbf{Q} \in \text{SOS}(\mathcal{F}_d^n)$ and see that the truncated quadratic module

$$ \text{QM}(\mathbf{P})_d := \{q + \text{Trace}(\mathbf{P} \mathbf{Q}) | q \in \text{SOS}(\mathcal{F}_d), \mathbf{Q} \in \text{SOS}(\mathcal{F}_{d-D}^n)\} $$

is contained in $\mathcal{F}_{2d}$. We fix a **hierarchy order** $d \in \mathbb{N}$, that has to satisfy

$$ d \ge \max\{\min\{\lceil \ell/2 \rceil | \ell \in \mathbb{N}, f \in \mathcal{F}_\ell\}, D\}, \quad (3.8) $$

where $f$ is the objective function from Equation (3.2). The **Chebyshev moment and SOS hierarchy of order** $d$ is

$$ f_{\text{mom}}^d := \inf_{\text{s.t.}} \mathcal{L}(f) \quad \text{and} \quad f_{\text{sos}}^d := \sup_{\text{s.t.}} \lambda \quad (3.9) $$

$$ \mathcal{L} \in \mathcal{F}_{2d}^*, \mathcal{L}(1) = 1, $$

$$ \mathbf{H}_d^{\mathcal{L}}, \mathbf{H}_{d-D}^{p*\mathcal{L}} \ge 0, $$

$$ \lambda \in \mathbb{R}, $$

$$ f - \lambda \in \text{QM}(\mathbf{P})_d. $$
**Theorem 3.5.** The following statements hold.

1. The sequences $(f_{sos}^d)_{d \in \mathbb{N}}$ and $(f_{mom}^d)_{d \in \mathbb{N}}$ are monotonously non-decreasing.

2. For $d \in \mathbb{N}$, we have $f_{sos}^d \le f_{mom}^d$.

3. If $\mathrm{QM}(\mathbf{P})$ is Archimedean, then $\lim_{d \to \infty} f_{sos}^d = \lim_{d \to \infty} f_{mom}^d = f^*$.

*Proof.* 1. follows from the chain of inclusions $\mathcal{F}_1 \subseteq \mathcal{F}_2 \subseteq \dots$

2. is analogous to Equation (3.5).

3. By Theorem 3.1, for any $\varepsilon > 0$, there exist sums of squares $q$ and $\mathbf{Q}$, such that

$$f - f^* + \varepsilon = q + \mathrm{Trace}(\mathbf{P} \mathbf{Q}).$$

Since $\varepsilon$ is arbitrary and $\bigcup_{d \in \mathbb{N}} \mathcal{F}_d = \mathbb{R}[z]$, we obtain $\lim_{d \to \infty} f_{sos}^d = f^*$. With $\mathcal{P}$, the same holds for $f_{mom}^d$. $\square$

### 3.2.3 SDP formulation

We translate Equation (3.9) to a semi-definite program (SDP). For $d \in \mathbb{N}$ and a linear functional $\mathcal{L} \in \mathcal{F}_{2d}^*$, we write

$$\begin{pmatrix} \mathbf{H}_d^{\mathcal{L}} & 0 \\ 0 & \mathbf{H}_{d-D}^{\mathbf{P}^*\mathcal{L}} \end{pmatrix} = \sum_{\mu \in \Omega^+} \mathcal{L}(T_\mu) \mathbf{A}_\mu, \qquad (3.10)$$

where $\mathbf{A}_\mu$ is the symmetric matrix coefficient of $\mathcal{L}(T_\mu)$. For $d \ge D$, $\mathcal{L}(T_\mu)$ is well-defined whenever $\mathbf{A}_\mu \ne 0$. We write $\mathrm{Sym}^{(d)} := \mathrm{Sym}^{\dim(\mathcal{F}_d)} \times \mathrm{Sym}^{n \dim(\mathcal{F}_{d-D})}$ for the space of symmetric matrices with two blocks. The positive semi-definite elements are denoted by $\mathrm{Sym}^{(d)}_{\ge 0}$ and we define the dual problems

$$ (P_d) \quad \inf_{\mu \in S} \sum_{\mathbf{y} \in \mathbb{R}^{\dim(\mathcal{F}_{2d})}} c_\mu \mathbf{y}_\mu \quad \text{and} \quad (D_d) \sup_{c_0} \mathrm{Trace}(\mathbf{A}_0 \mathbf{X}) = c_0 \quad (3.11) \\ \text{s.t.} \quad \mathbf{y} \in \mathbb{R}^{\dim(\mathcal{F}_{2d})}, \mathbf{y}_0 = 1, \quad \text{s.t.} \quad \mathbf{X} \in \mathrm{Sym}^{(d)}_{\ge 0}, \forall \mu \in S \setminus \{0\}: \\ \mathbf{Z} = \sum_{\mu \in \Omega^+} \mathbf{y}_\mu \mathbf{A}_\mu \in \mathrm{Sym}^{(d)}_{\ge 0}, \quad \mathrm{Trace}(\mathbf{A}_\mu \mathbf{X}) = c_\mu. $$

**Proposition 3.6.** The optimal value of $(P_d)$ is $f_{mom}^d$ and the optimal value of $(D_d)$ is $f_{sos}^d$.

*Proof.* The statement for $(P_d)$ follows immediately with $\mathbf{y}_\mu = \mathcal{L}(T_\mu)$ and $\mathbf{Z} = \mathrm{diag}(\mathbf{H}_d^{\mathcal{L}}, \mathbf{H}_{d-D}^{\mathbf{P}^*\mathcal{L}})$. Let $\mathcal{L} \in \mathcal{F}_{2d}^*$ and $\lambda \in \mathbb{R}$ be feasible for Equation (3.9). Then there exist $q \in \mathrm{SOS}(\mathcal{F}_d)$ and $\mathbf{Q} \in \mathrm{SOS}(\mathcal{F}_{d-D})$ with

$$\mathcal{L}(f) - \lambda = \mathcal{L}(f - \lambda) = \mathcal{L}(q) + \mathcal{L}(\mathrm{Trace}(\mathbf{P} \mathbf{Q})).$$

We construct a feasible matrix $\mathbf{X} = \mathrm{diag}(\mathbf{X}_1, \mathbf{X}_2)$ for $(D_d)$ as follows. Since $\mathbf{Q}$ is a sum of squares, we can write $\mathbf{Q} = \mathbf{Q}_1 \mathbf{Q}_1^t + \dots + \mathbf{Q}_k \mathbf{Q}_k^t$ and denote by $\mathbf{T}_{d-D}$ the vector of generalized Chebyshev polynomials $T_\mu \in \mathcal{F}_{d-D}$. For $1 \le i \le k$, we have $\mathbf{Q}_i = \mathrm{mat}(\mathbf{Q}_i) \mathbf{T}_{d-D}$, where $\mathrm{mat}(\mathbf{Q}_i)$ is the coordinate matrix of the polynomial vector $\mathbf{Q}_i$ in the Chebyshev basis with $n$ rows and $\mathrm{dim}(\mathcal{F}_{d-D})$ columns. Then

$$ \mathrm{Trace}(\mathbf{P} \mathbf{Q}) = \sum_{i=1}^{k} \mathrm{Trace}(\mathbf{P} \mathrm{mat}(\mathbf{Q}_i) \mathbf{T}_{d-D} \mathbf{T}_{d-D}^t \mathrm{mat}(\mathbf{Q}_i)^t) \\ = \mathrm{Trace}((\mathbf{P} \otimes \mathbf{T}_{d-D} \mathbf{T}_{d-D}^t) \underbrace{\sum_{i=1}^{k} \mathrm{vec}(\mathrm{mat}(\mathbf{Q}_i)) \mathrm{vec}(\mathrm{mat}(\mathbf{Q}_i))^t}_{=: \mathbf{X}_2}) $$
where $\text{vec}(\text{mat}(\mathbf{Q}_i)) := ((\text{mat}(\mathbf{Q}_i))_1^t, \dots, (\text{mat}(\mathbf{Q}_i)_{N_{d-D}})^t)^t$ are the stacked columns of $\text{mat}(\mathbf{Q}_i)$. The matrix $\mathbf{X}_2$ is symmetric positive semi-definite of size $n$ $\dim(\mathcal{F}_{d-D})$. By definition of the truncated localized moment matrix, we have $\mathcal{L}(\text{Trace}(\mathbf{P}\mathbf{Q})) = \text{Trace}(\mathbf{H}_{d-D}^{\mathcal{L}} \mathbf{X}_2)$. Analogously, there exists a symmetric positive semi-definite $\mathbf{X}_1$ of size $\dim(\mathcal{F}_d)$ with $\mathcal{L}(q) = \text{Trace}(\mathbf{H}_d^{\mathcal{L}} \mathbf{X}_1)$. When we fix $\mathbf{X} := \text{diag}(\mathbf{X}_1, \mathbf{X}_2) \in \text{Sym}_{\ge 0}^{(d)}$ and $\mathbf{A}_{\mu}$ as in Equation (3.10), comparing coefficients yields

$$ \lambda = c_0 \mathcal{L}(1) - \mathcal{L}(q(0)) - \mathcal{L}(\text{Trace}(\mathbf{P}(0)\mathbf{Q}(0))) = c_0 - \text{Trace}(\mathbf{A}_0 \mathbf{X}) $$

and, for $\mu \neq 0$, we have $c_{\mu} = \text{Trace}(\mathbf{A}_{\mu} \mathbf{X})$.

Conversely, we can always construct sums of squares $q$ and $\mathbf{Q}$ from a matrix $\mathbf{X} = \text{diag}(\mathbf{X}_1, \mathbf{X}_2)$ by writing $\mathbf{X}_1$ and $\mathbf{X}_2$ as sums of rank 1 matrices. $\square$

If $(\mathbf{X}, \mathbf{y}, \mathbf{Z})$ are optimal for $(\mathbf{P}_d)$ and $(\mathbf{D}_d)$, then the duality gap of the Chebyshev moment and SOS hierarchy in Equation (3.9) is $f_{\text{mom}}^d - f_{\text{sos}}^d = \text{Trace}(\mathbf{X}\mathbf{Z}) \geq 0$.

**Remark 3.7.** The coefficients $c_{\mu}$ are known from the original problem in Equation (3.2). The key in setting up Equation (3.11) is the computation of the matrices $\mathbf{A}_{\mu}$. For fixed order $d$, we define

* the **matrix size** $N := \dim(\mathcal{F}_d) + n \dim(\mathcal{F}_{d-D})$ and

* the **number of constraints** $m := \dim(\mathcal{F}_{2d}) - 1$.

Note that $m$ is the number of matrices $\mathbf{A}_{\mu}$ with $\mu \neq 0$ and $N$ is their size. The primal and dual in Equation (3.11) are conic optimization problems over $\text{QM}(\mathbf{P})_d \cong \text{Sym}_{\ge 0}^{(d)}$.

Computing the matrices $\mathbf{A}_{\mu}$ of the SDP involves the recurrence formula from Equation (2.3). If we used the standard monomial basis $\{1, z_1, z_2, \dots, z_1^2, z_1z_2, \dots\}$, this computation would be trivial, but the matrices would be larger when truncating at the usual degree instead of the weighted degree. Hence, our technique is more efficient, if the numerical effort to solve a larger SDP in the standard monomial basis is bigger than the combined effort to numerically solve a smaller SDP in the Chebyshev basis plus matrix computation.

A limiting factor in solving an SDP is the matrix size $N$. For the computations in this article we used a conventional laptop (Intel(R) Core(TM) i5-10600 CPU @ 3.30GHz, 16.0 GB RAM).

How to obtain the matrices with the MAPLE package is explained here:

https://tobiasmetzlaff.com/html_guides/generating_SDP_data.html

<table><caption>Table 1: The SDP parameters $(N, m)$ for Equation (3.11) depend on the root system $R$ and the order $d$.</caption><thead><tr><th></th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><td>B<sub>2</sub>, C<sub>2</sub></td><td>6 + 2, 14</td><td>10 + 6, 27</td><td>15 + 12, 44</td><td>21 + 20, 65</td><td>28 + 30, 90</td><td>36 + 42, 119</td><td>45 + 56, 152</td><td>55 + 72, 189</td><td>66 + 90, 230</td></tr><tr><td>G<sub>2</sub></td><td>—</td><td>6 + 3, 15</td><td>9 + 6, 24</td><td>12 + 12, 35</td><td>16 + 18, 48</td><td>20 + 27, 63</td><td>25 + 36, 80</td><td>30 + 48, 99</td><td>36 + 60, 120</td></tr><tr><td>A<sub>2</sub></td><td>—</td><td>10 + 3, 27</td><td>15 + 9, 44</td><td>21 + 18, 65</td><td>28 + 30, 90</td><td>36 + 45, 119</td><td>45 + 63, 152</td><td>55 + 84, 189</td><td>66 + 108, 230</td></tr><tr><td>B<sub>3</sub></td><td>—</td><td>13 + 3, 49</td><td>22 + 9, 94</td><td>34 + 21, 160</td><td>50 + 39, 251</td><td>70 + 66, 371</td><td>95 + 102, 524</td><td>125 + 150, 714</td><td>161 + 210, 945</td></tr><tr><td>C<sub>3</sub></td><td>—</td><td>20 + 3, 83</td><td>35 + 12, 164</td><td>56 + 30, 285</td><td>84 + 60, 454</td><td>120 + 105, 679</td><td>165 + 168, 968</td><td>220 + 252, 1329</td><td>286 + 360, 1770</td></tr><tr><td>A<sub>3</sub></td><td>—</td><td>—</td><td>35 + 4, 164</td><td>56 + 16, 285</td><td>84 + 40, 454</td><td>120 + 80, 679</td><td>165 + 140, 968</td><td>220 + 224, 1329</td><td>286 + 336, 1770</td></tr><tr><td>B<sub>4</sub></td><td>—</td><td>—</td><td>30 + 4, 174</td><td>50 + 12, 335</td><td>80 + 32, 587</td><td>120 + 64, 959</td><td>175 + 120, 1484</td><td>245 + 200, 2199</td><td>336 + 320, 3145</td></tr><tr><td>C<sub>4</sub></td><td>—</td><td>—</td><td>70 + 4, 494</td><td>126 + 20, 1000</td><td>210 + 60, 1819</td><td>330 + 140, 3059</td><td>495 + 280, 4844</td><td>715 + 504, 7314</td><td>1001 + 840, 10625</td></tr><tr><td>D<sub>4</sub></td><td>—</td><td>—</td><td>46 + 4, 294</td><td>80 + 16, 580</td><td>130 + 44, 1035</td><td>200 + 96, 1715</td><td>295 + 184, 2684</td><td>420 + 320, 4014</td><td>581 + 520, 5785</td></tr></tbody></table>

### 3.3 Optimizing on coefficients

For a finite set $S \subseteq \Omega^+ \setminus \{0\}$ of dominant weights, we shall be confronted in Section 4 with a bilevel optimization problem, where we have to minimize not only the objective function $f$ from Equation (3.1)
with respect to $z \in \mathcal{T}$, but also maximize with respect to the coefficients $c_\mu$ under some compact affine constraints. The problem can be represented as

$$F(S) := \max_{c} \min_{z} \sum_{\mu \in S} c_{\mu} T_{\mu}(z) \\ \text{s.t.} \quad z \in \mathcal{T}, c \in \mathbb{R}^{S}, b^t c = 1, \\ \qquad \ell_{\mu} \le c_{\mu} \le u_{\mu} \quad \text{for } \mu \in S,$$

where $0 \neq b \in \mathbb{R}^S$ defines a hyperplane and $\ell_\mu \le u_\mu \in \mathbb{R}$ are lower and upper bounds. For scalar polynomial constraints defining the basic semi-algebraic set $\mathcal{T}$, a hierarchy of SDPs to approximate $F(S)$ was introduced in [Las09, Chapter 13]. In our case with a polynomial matrix constraint, the theory is similar: For $d \in \mathbb{N}$ large enough, that is, for $T_\mu \in \mathcal{F}_{2d}$ whenever $\mu \in S$, we define

$$F(S, d) := \sup_{\mathbf{X} \in \mathrm{Sym}_{\ge 0}^{(d)}} -\mathrm{Trace}(\mathbf{A}_0 \mathbf{X}) \\ \text{s.t.} \quad \mathbf{X} \in \mathrm{Sym}_{\ge 0}^{(d)}, \sum_{\mu \in S} b_\mu \mathrm{Trace}(\mathbf{A}_\mu \mathbf{X}) = 1, \\ \qquad \ell_\mu \le \mathrm{Trace}(\mathbf{A}_\mu \mathbf{X}) \le u_\mu \quad \text{for } \mu \in S, \\ \qquad \mathrm{Trace}(\mathbf{A}_\nu \mathbf{X}) = 0 \quad \text{for } \nu \notin S \cup \{0\},$$

where the $\mathbf{A}_0, \mathbf{A}_\mu, \mathbf{A}_\nu \in \mathrm{Sym}^{(d)}$ are the dim($\mathcal{F}_{2d}$) many matrices defined via Equation (3.10).

**Theorem 3.8.** The sequence $(F(S, d))_{d \in \mathbb{N}}$ is monotonously non-decreasing. If $\mathrm{QM}(\mathbf{P})$ is Archimedean, then $\lim_{d \to \infty} F(S, d) = F(S)$.

*Proof.* The proof is analogous to the one of [Las09, Theorem 13.1], but uses the Positivstellensatz of Hol and Scherer instead of Putinar's. Let $\mathbf{X}$ be optimal for $F(S, d)$ and set $c_\mu := \mathrm{Trace}(\mathbf{A}_\mu \mathbf{X})$ for $\mu \in S$. Then $F(S, d) \le (f_c)^* \le F(S)$, where $(f_c)^*$ denotes the minimum of $f_c := \sum_{\mu \in S} c_\mu T_\mu \in \mathbb{R}[z]$ on $\mathcal{T}$.

On the other hand, $\mathcal{T} = \{z \in \mathbb{R}^n | \mathbf{P}(z) \succeq 0\}$ is compact and the $T_\mu$ are continuous. Hence, the map $g: c \mapsto (f_c)^*$ is continuous on a compact set and there exists a feasible $c^* \in \mathbb{R}^S$, such that $F(S) = g(c^*)$. For any $\varepsilon > 0$, the polynomial $\sum_{\mu \in S} c_\mu^* T_\mu - F(S) + \varepsilon$ is strictly positive on $\mathcal{T}$. Thus, by Theorem 3.1, there exist sums of squares $q \in \mathrm{SOS}(\mathbb{R}[z])$ and $\mathbf{Q} \in \mathrm{SOS}(\mathbb{R}[z]^n)$, such that

$$\sum_{\mu \in S} c_{\mu}^{*} T_{\mu} - (F(S) - \varepsilon) = q + \mathrm{Trace}(\mathbf{P} \mathbf{Q}).$$

For $d \in \mathbb{N}$ sufficiently large, we can follow our proof of Proposition 3.6 to construct a matrix $\mathbf{X} \in \mathrm{Sym}_{\ge 0}^{(d)}$ with $-\mathrm{Trace}(\mathbf{A}_0 \mathbf{X}) = F(S) - \varepsilon$, $\mathrm{Trace}(\mathbf{A}_\mu \mathbf{X}) = c_\mu^*$ for $\mu \in S$ and $\mathrm{Trace}(\mathbf{A}_\nu \mathbf{X}) = 0$ for $\nu \notin S \cup \{0\}$. Then $\mathbf{X}$ is feasible for $F(S, d)$, and so we have $F(S, d) \ge F(S) - \varepsilon$. Since $\varepsilon > 0$ is arbitrary, the statement follows. $\square$

## 3.4 A case study

We apply the Chebyshev moment and SOS hierarchy to solve a trigonometric optimization problem with crystallographic symmetry and compare with another technique: One alternative approach to ours is to reinforce from positivity constraints to SOHS constraints (sums of Hermitian squares), which goes back to the generalized Riesz-Fejér theorem [Dum07, Theorem 4.11]. Specifically, one can approximate the minimum of a trigonometric polynomial $f \in \mathbb{R}[\Omega]$ by solving a semi-definite program

$$f^* \ge f_{\mathrm{rf}}^S := \sup_{\mathbf{f} \in \mathrm{SOHS}(S)} \lambda \qquad (3.12) \\ \text{s.t.} \quad f - \lambda \in \mathrm{SOHS}(S),$$

where $S \subseteq \Omega$ is a finite set containing the support of $f$ up to central symmetry (rf as in Riesz-Fejér). The SDP standard form is given in [Dum07, Equation (3.71)].
**Example 3.9.** We search the global minima $f^*$, $g^*$, $h^*$ and $k^*$ of the following W-invariant trigonometric polynomials with graphs depicted in Figure 7.

1. Let $R = G_2$, $W = \mathfrak{S}_3 \times \{\pm 1\}$, $\Omega = \mathbb{Z}\omega_1 \oplus \mathbb{Z}\omega_2 = \mathbb{Z}[0, -1, 1]^t \oplus \mathbb{Z}[-1, -1, 2]^t$ and

$$ 
\begin{aligned}
f(u) &:= c_{2\omega_1}(u) + 2c_{\omega_2}(u) \\
&= (\cos(2\pi\langle 2\omega_1, u \rangle) + \cos(2\pi\langle 2\omega_1 - 2\omega_2, u \rangle) + \cos(2\pi\langle 4\omega_1 - 2\omega_2, u \rangle) \\
&\quad + 2\cos(2\pi\langle 2\omega_2, u \rangle) + 2\cos(2\pi\langle 3\omega_1 - \omega_2, u \rangle) + 2\cos(2\pi\langle 3\omega_1 - 2\omega_2, u \rangle))/3.
\end{aligned}
$$

In the coordinates $z = c(u)$, we have $f(z) = 6z_1^2 - 2z_1 - 1$ (see Example 2.11).

2. Let $R = G_2$, $W = \mathfrak{S}_3 \times \{\pm 1\}$, $\Omega = \mathbb{Z}\omega_1 \oplus \mathbb{Z}\omega_2 = \mathbb{Z}[0, -1, 1]^t \oplus \mathbb{Z}[-1, -1, 2]^t$ and

$$ 
\begin{aligned}
g(u) &:= 2c_{\omega_1}(u) + c_{\omega_2}(u) + c_{\omega_1+\omega_2}(u) + 4c_{3\omega_1}(u) \\
&= (2 \cos(2\pi\langle\omega_1, u\rangle) + 2 \cos(2\pi\langle\omega_1 - \omega_2, u\rangle) + 2 \cos(2\pi\langle 2\omega_1 - \omega_2, u\rangle) \\
&\quad + \cos(2\pi\langle\omega_2, u\rangle) + \cos(2\pi\langle 3\omega_1 - 2\omega_2, u\rangle) + \cos(2\pi\langle 3\omega_1 - \omega_2, u\rangle) \\
&\quad + 4 \cos(2\pi\langle 3\omega_1, u\rangle) + 4 \cos(2\pi\langle 3\omega_1 - 3\omega_2, u\rangle) + 4 \cos(2\pi\langle 6\omega_1 - 3\omega_2, u\rangle))/3 \\
&\quad + (\cos(2\pi\langle\omega_1, u\rangle + \langle\omega_2, u\rangle) + \cos(2\pi\langle\omega_1 - 2\omega_2, u\rangle) + \cos(2\pi\langle 4\omega_1 - \omega_2, u\rangle) \\
&\quad + \cos(2\pi\langle 4\omega_1 - 3\omega_2, u\rangle) + \cos(2\pi\langle 5\omega_1 - 2\omega_2, u\rangle) + \cos(2\pi\langle 5\omega_1 - 3\omega_2, u\rangle))/6.
\end{aligned}
$$

In the coordinates $z = c(u)$, we have $g(z) = 144z_1^3 - 6z_1^2 - 69z_1z_2 - 33z_1 - 21z_2 - 7$.

3. Let $R = C_2$, $W = \mathfrak{S}_2 \times \{\pm 1\}^2$, $\Omega = \mathbb{Z}\omega_1 \oplus \mathbb{Z}\omega_2 = \mathbb{Z}[1, 0]^t \oplus \mathbb{Z}[1, 1]^t$ and

$$ 
\begin{aligned}
h(u) &:= 2c_{\omega_1}(u) + c_{\omega_2}(u) - c_{2\omega_2}(u) - 3c_{\omega_1+\omega_2}(u) \\
&= \cos(2\pi\langle\omega_1, u\rangle) + \cos(2\pi\langle\omega_1 - \omega_2, u\rangle) \\
&\quad + (\cos(2\pi\langle\omega_2, u\rangle) + \cos(2\pi\langle 2\omega_1 - \omega_2, u\rangle) - \cos(2\pi\langle 2\omega_2, u\rangle) - \cos(2\pi\langle 4\omega_1 - 2\omega_2, u\rangle))/2 \\
&\quad - 3/4(\cos(2\pi\langle\omega_1 - 2\omega_2, u\rangle) + \cos(2\pi\langle\omega_1 + \omega_2, u\rangle) \\
&\quad + \cos(2\pi\langle 3\omega_1 - 2\omega_2, u\rangle) + \cos(2\pi\langle 3\omega_1 - \omega_2, u\rangle)).
\end{aligned}
$$

In the coordinates $z = c(u)$, we have $h(z) = 8z_1^2 - 6z_1z_2 - 4z_2^2 + 5z_1 - 3z_2 - 1$.

4. Let $R = C_2$, $W = \mathfrak{S}_2 \times \{\pm 1\}^2$, $\Omega = \mathbb{Z}\omega_1 \oplus \mathbb{Z}\omega_2 = \mathbb{Z}[1, 0]^t \oplus \mathbb{Z}[1, 1]^t$ and

$$ 
\begin{aligned}
k(u) &:= 2c_{2\omega_1}(u) + c_{2\omega_2}(u) \\
&= \cos(2\pi\langle 2\omega_1, u \rangle) + \cos(2\pi\langle 2\omega_1 - 2\omega_2, u \rangle) + \cos(2\pi\langle 2\omega_2, u \rangle)/2 + \cos(2\pi\langle 4\omega_1 - 2\omega_2, u \rangle)/2
\end{aligned}
$$

In the coordinates $z = c(u)$, we have $k(z) = 4z_2^2 - 1$.

For $3 \le d \le 7$, we choose $\tilde{S}$ to be the set of all dominant weights $\mu \in \Omega^+$ with $\deg_W(T_\mu) \le d$. In Equation (3.12), $S = (\tilde{S} - \tilde{S}) \cap (H \setminus \{0\})$ is an admissible choice for any halfspace $H$, since $S$ contains all exponents of the objective functions up to central symmetry. In this case, we denote the optimal value by $f_{\text{rf}}^d$. On the other hand, we apply the Chebyshev SOS reinforcement $f_{\text{sos}}^d$ from Equation (3.9), where we only need to take exponents up to Weyl group symmetry, that is, $\tilde{S}$ itself.
<figure><img src="image_8.png" /><figcaption>Figure 7: The graphs of the objective functions for $u \in \mathbb{R}^3/[1, 1, 1]^t \cong \mathbb{R}^2$.</figcaption></figure>

With the two techniques, we obtain the results in Table 2. Since we compare lower bounds, it suffices to check which bound is larger and therefore closer to the actual minimum.

<table><thead><tr><th>d</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><td>f<sup>d</sup><sub>rf</sub><br>N, m</td><td>-1.18824<br>49, 33</td><td>-1.180240<br>81, 58</td><td>-1.17058<br>121, 90</td><td>-1.16970<br>169, 129</td><td>-1.16719<br>225, 175</td></tr><tr><td>f<sup>d</sup><sub>sos</sub><br>N, m</td><td>-1.16667<br>9, 15</td><td>-1.16667<br>15, 24</td><td>-1.16667<br>24, 35</td><td>-1.16667<br>34, 48</td><td>-1.16667<br>47, 63</td></tr><tr><td>g<sup>d</sup><sub>rf</sub><br>N, m</td><td>-3.50118<br>49, 33</td><td>-3.40372<br>81, 58</td><td>-3.31195<br>121, 90</td><td>-3.25383<br>169, 129</td><td>-3.22049<br>225, 175</td></tr><tr><td>g<sup>d</sup><sub>sos</sub><br>N, m</td><td>-3.20499<br>9, 15</td><td>-3.10220<br>15, 24</td><td>-2.98718<br>24, 35</td><td>-2.98718<br>34, 48</td><td>-2.98718<br>47, 63</td></tr><tr><td>h<sup>d</sup><sub>rf</sub><br>N, m</td><td>-2.12159<br>25, 24</td><td>-2.10672<br>49, 54</td><td>-2.1012<br>81, 96</td><td>-2.09959<br>121, 150</td><td>-2.09073<br>169, 217</td></tr><tr><td>h<sup>d</sup><sub>sos</sub><br>N, m</td><td>-2.27496<br>16, 27</td><td>-2.06250<br>27, 44</td><td>-2.06250<br>41, 65</td><td>-2.06250<br>58, 90</td><td>-2.06250<br>78, 119</td></tr><tr><td>k<sup>d</sup><sub>rf</sub><br>N, m</td><td>-1.00000<br>25, 84</td><td>-1.00000<br>41, 144</td><td>-1.00000<br>61, 220</td><td>-1.00000<br>85, 312</td><td>-1.00000<br>113, 420</td></tr><tr><td>k<sup>d</sup><sub>sos</sub><br>N, m</td><td>-1.00000<br>16, 27</td><td>-1.00000<br>27, 44</td><td>-1.00000<br>41, 65</td><td>-1.00000<br>58, 90</td><td>-1.00000<br>78, 119</td></tr></tbody></table>

Table 2: We compare the two techniques in terms of approximation and SDP parameters. The columns are indexed by the order of the relaxation *d*. The matrix size is denoted by *N*, the number of constraints by *m*.

**Remark 3.10.** In Table 2, we observe $f^* \ge f_{\text{sos}}^d \ge f_{\text{rf}}^d$ for $d \ge 4$. Hence, our approximation of $f^*$ appears to be better in those cases, while the parameters $N, m$ that indicate the size of the SDP are smaller (analogous for $g, h, k$). Differences in the quality of the approximation might depend on the stability of the SDP [CAPT22].
# 4 Spectral bounds for set avoiding graphs

In this last section, we apply our method for trigonometric optimization problems with crystallographic symmetry to the computation of spectral bounds for chromatic numbers. The chromatic number of a graph gives the minimal number of colors needed to paint the vertices, so that no edge connects two vertices of the same color. When dealing with set avoiding graphs, [BDFV14] provides a lower bound, which involves minimizing the Fourier transformation of a measure.

While this bound has been used and strengthened for the graph $\mathbb{R}^n$ avoiding Euclidean distance 1 [Soi09, Gre18, BDFV14, BPT15], it has not been widely used as a tool for polytopes. Crystallographic symmetry in the trigonometric optimization problem arises when the polytope has Weyl group symmetry. Then we can rewrite the spectral bound in terms of generalized Chebyshev polynomials and use the results of Sections 2 and 3.

An advantage of our approach is that rewriting the optimization problem in terms of polynomials allows in several cases to compute bounds with simple proofs and to recover many results. In other cases, we compute numerical bounds with the modified Lasserre hierarchy from Section 3. Our approach allows to study the quality of the spectral bound and to speculate on the optimal involved measure, see Figure 11.

## 4.1 Computing spectral bounds with Chebyshev polynomials

Let $V \subseteq \mathbb{R}^n$ be an Abelian group and $S \subseteq V$ be bounded, centrally-symmetric with $0 \notin \bar{S}$. We consider the set avoiding graph $G(V, S)$, where $V$ is the set of vertices and two vertices $u, v \in V$ are connected by an edge if and only if $u - v \in S$. In this context, we call $S$ the **avoided set**.

A set of vertices $I \subseteq V$ is called **independent** for $G(V, S)$, if no pair of vertices in $I$ are connected by an edge, that is, for all $u, v \in I$, we have $u - v \notin S$. A **measurable coloring** $X$ of $G(V, S)$ is a partition of $V$ in independent Lebesgue-measurable sets. The **measurable chromatic number** of $G(V, S)$ is

$$ \chi_m(V, S) := \inf\{|X| \mid X \text{ is a measurable coloring of } G(V, S)\}. $$

### 4.1.1 The spectral bound

In [BDFV14], Bachoc, Decorte, de Oliveira Filho and Vallentin generalized bounds for chromatic numbers by Hoffman [Hof70] and Lovász [Lov79] from finite graphs to the case $V = \mathbb{R}^n$, using the framework of bounded self-adjoint operators. Showing that the result holds for any set avoiding graph $G(V, S)$ is a straightforward adaptation of [DSMMV19, §5.1] and so we state it here without a proof.

**Theorem 4.1.** [BDFV14, §3.1] Let $\mathcal{B}$ be a finite Borel measure supported on $S$ with Fourier transformation

$$ \hat{\mathcal{B}}(u) = \int_S \exp(-2\pi i \langle u, v \rangle) d\mathcal{B}(v). $$

Then the measurable chromatic number of $G(V, S)$ satisfies

$$ \chi_m(V, S) \ge 1 - \frac{\sup_{u \in \mathbb{R}^n} \hat{\mathcal{B}}(u)}{\inf_{u \in \mathbb{R}^n} \hat{\mathcal{B}}(u)}. $$

The problem of computing the measurable chromatic number of $G(V, S)$ gained fame after Hadwiger and Nelson formulated it in 1950 for the case $V = \mathbb{R}^2$ and $S = \mathbb{S}^1$, the Euclidean unit sphere, which remains unsolved. Current bounds and the history of the problem can be found in [Soi09] and [Gre18].

More generally, for $V = \mathbb{R}^n$ and $S = \mathbb{S}^{n-1}$, the bounds obtained from Theorem 4.1 for $\chi_m(\mathbb{R}^n, \mathbb{S}^{n-1})$ have been studied, see for example [BPT15]. In this case, the optimal measure is the surface measure on $\mathbb{S}^{n-1}$. Beyond the spectral bound, the computation of $\chi_m(\mathbb{R}^n, \mathbb{S}^{n-1})$ itself was treated in [BPS21, AM22, ACM+22].
### 4.1.2 Reformulation in terms of Chebyshev polynomials

For a root system $\mathbb{R}$ in $\mathbb{R}^n$ with Weyl group $\mathcal{W}$ and weight lattice $\Omega$, we consider those avoided sets $S \subseteq V$, which have Weyl group symmetry, that is, $WS = S$. We will see that the $\mathcal{W}$-invariant trigonometric polynomials $\mathbb{R}[\Omega]^W$ with support in $S$ are the Fourier transformations of atomic $\mathcal{W}$-invariant Borel measures supported on $\Omega \cap S$. We treat the optimization problem in Theorem 4.1 for this class of measures with the theory developed in Section 3. In fact, by an averaging argument on all orbits, we see that an optimal measure for Theorem 4.1 is obtained from such a $\mathcal{W}$-invariant trigonometric polynomial. Recall from Theorem 2.9 that the image of the generalized cosines is a basic semi-algebraic set

$$ \mathcal{T} = \{ \mathfrak{c}(u) | u \in \mathbb{R}^n \} = \{ z \in \mathbb{R}^n | \mathbf{P}(z) \geq 0 \} $$

and define

$$ F(S) := \max_{c} \min_{z} \sum_{\mu \in S \cap \Omega^{+}} c_{\mu} T_{\mu}(z) \qquad (4.1) \\ \text{s.t.} \quad z \in \mathcal{T}, c \in \mathbb{R}_{\geq 0}^{S \cap \Omega^{+}}, \sum_{\mu \in S \cap \Omega^{+}} c_{\mu} = 1. $$

**Theorem 4.2.** Let $WS = S$ and $S \cap \Omega \neq \emptyset$. The measurable chromatic number of $G(V, S)$ satisfies

$$ \chi_m(V, S) \geq 1 - \frac{1}{F(S)}. $$

*Proof.* Since $S$ is bounded, the nonempty set $S \cap \Omega$ is finite. We consider the atomic Borel measure

$$ \mathcal{B} = \sum_{\mu \in S \cap \Omega} \frac{c_{\mu}}{|\mathcal{W}\mu|} \delta_{\mu} $$

with $\delta_{\mu}$ Dirac and $0 \le c_{\mu} = c_{-\mu} \in \mathbb{R}$, so that, for all $s \in \mathcal{W}$, $c_{s(\mu)} = c_{\mu}$. Then the Fourier transformation is

$$ \hat{\mathcal{B}}(u) = \int_S \exp(-2\pi i \langle u, v \rangle) d\mathcal{B}(v) = \sum_{\mu \in S \cap \Omega} \frac{c_{\mu}}{|\mathcal{W}\mu|} \exp(-2\pi i \langle \mu, u \rangle) = \sum_{\mu \in S \cap \Omega^{+}} c_{\mu} \mathfrak{c}_{\mu}(u) = \sum_{\mu \in S \cap \Omega^{+}} c_{\mu} T_{\mu}(\mathfrak{c}(u)). $$

In particular, we have

$$ \hat{\mathcal{B}}(u) \le \sum_{\mu \in S \cap \Omega} \frac{c_{\mu}}{|\mathcal{W}\mu|} = \sum_{\mu \in S \cap \Omega^{+}} c_{\mu} $$

and equality holds for $u = 0$. Optimizing over the coefficients $c$ under the condition $\sum_{\mu} c_{\mu} = 1$ and using Equation (2.6) with Theorem 4.1 gives the lower bound $1 - 1/F(S)$ for $\chi_m(V, S)$. $\square$

In practice, the problem of computing $F(S)$ analytically is not always possible. Instead we can use the theory of Section 3 to obtain a numerical lower bound. For $d \in \mathbb{N}$ sufficiently large, we consider the SDP

$$ F(S, d) := \sup_{\mathbf{X} \in \mathrm{Sym}_{\ge 0}^{(d)}, \sum_{\mu \in S \cap \Omega^+} \mathrm{Trace}(\mathbf{A}_\mu \mathbf{X}) = 1} -\mathrm{Trace}(\mathbf{A}_0 \mathbf{X}) \qquad (4.2) \\ \text{s.t.} \quad \mathrm{Trace}(\mathbf{A}_\mu \mathbf{X}) \ge 0 \quad \text{for} \quad \mu \in S \cap \Omega^+, \\ \mathrm{Trace}(\mathbf{A}_\nu \mathbf{X}) = 0 \quad \text{for} \quad \nu \in \Omega^+ \setminus (S \cup \{0\}), $$

where the semi-definite cone $\mathrm{Sym}_{\ge 0}^{(d)}$ and the finitely many matrices $\mathbf{A}_0, \mathbf{A}_\mu, \mathbf{A}_\nu \in \mathrm{Sym}^{(d)}$ are defined as in Equation (3.10).
**Corollary 4.3.** [of Theorems 3.8 and 4.2] Let $WS = S$ and $S \cap \Omega \neq \emptyset$. The sequence $(F(S, d))_{d \in \mathbb{N}}$ is monotonously non-decreasing and we have

$$ \chi_m(V, S) \geq 1 - \frac{1}{F(S, d)}. $$

Furthermore, if $QM(P)$ is Archimedean, then $\lim_{d \to \infty} F(S, d) = F(S)$.

**Remark 4.4.** For $1 \le \ell \in \mathbb{N}$ and $S \cap \Omega \neq \emptyset$, we have $\ell(S \cap \Omega) \subseteq (\ell S) \cap \Omega \neq \emptyset$ and $F(S) \le F(\ell S)$. On the other hand, $F(S, d) \le F(\ell S, d)$ is only certain for $d \to \infty$. It may (and does) happen that $F(S, d) \ge F(\ell S, d)$ when $d$ is fixed, see for example Tables 3, 4, 6 and 7.

## 4.2 The chromatic number of a coroot lattice

For an $n$-dimensional lattice $V = \Lambda$ in $\mathbb{R}^n$, we call $\lambda \in \Lambda \setminus \{0\}$ a **strict Voronoï vector** if the intersection $(\lambda + \text{Vor}(\Lambda)) \cap \text{Vor}(\Lambda)$ is a facet of $\text{Vor}(\Lambda)$, that is, a face of dimension $n-1$ of the Voronoï cell. In this case, a natural choice for the avoided set $S$ is the set of all strict Voronoï vectors of $\Lambda$. The chromatic number $\chi(\Lambda)$ of the lattice $\Lambda$ is defined as the chromatic number of the graph $G(\Lambda) := G(\Lambda, S)$.

<figure><img src="image_9.png" /><figcaption>Figure 8: The chromatic number of the $A_2$ coroot lattice is $\chi(\Lambda(A_2)) = 3$.</figcaption></figure>

The chromatic number of several instances of these graphs was computed in [DSMMV19], some of them through the spectral bound from Theorem 4.1. In this subsection, we give new, simple proofs for these bounds for the case, where $\Lambda$ is the coroot lattice of an irreducible root system.

**Proposition 4.5.** Assume that $\Lambda$ is the coroot lattice of an irreducible root system $R$ with highest root $\rho_0$. Then the set of strict Voronoï vectors of $\Lambda$ is the orbit $S = W\rho_0^\vee$.

*Proof.* By [Bou68, Ch. VI, §1, Prop. 11 & 12], there are at most two distinct root lengths and two roots have the same length if and only if they are in the same $W$-orbit. If $\rho \in R$, then $\langle \rho_0, \rho_0 \rangle \ge \langle \rho, \rho \rangle$ and so

$$ \langle \rho_0^\vee, \rho_0^\vee \rangle = \frac{4}{\langle \rho_0, \rho_0 \rangle} \le \frac{4}{\langle \rho, \rho \rangle} = \langle \rho^\vee, \rho^\vee \rangle. $$

Thus, $\rho_0^\vee$ is a short root of the coroot system $R^\vee$. The lattice generated by $R^\vee$ is $\Lambda$ and, by the discussion before [CS99, Chapter 21, Theorem 8], the short roots $W(R^\vee)\rho_0^\vee$ are the strict Voronoï vectors. As $W(R) = W(R^\vee)$, the statement follows. $\square$

If $\rho_0^\vee \in \Omega$, then we obtain

$$ \chi(\Lambda) \ge 1 - \frac{1}{\min_{z \in T} T_{\rho_0^\vee}(z)}. \qquad (4.3) $$
Indeed, since the strict Voronoï vectors form a single W-orbit, there is no freedom for the coefficients in Theorem 4.2 and we are left with minimizing with respect to $z \in \mathcal{T}$.

If $\rho_0^\vee \notin \Omega$, we can replace $T_{\rho_0^\vee}$ by $T_\mu$ with $\mu = \ell \rho_0^\vee \in \Omega$ for some $\ell > 0$, because $\mathbb{R}^n$ is invariant under scaling. For example, this is the case for $G_2$, where $\rho_0^\vee = \rho_0/3 = \omega_2/3$ (and this is the only exception for the irreducible root systems). However, since the coroot lattice of $G_2$ is the hexagonal one from Figure 8, this case is covered by $A_2$.

We now reprove the bounds from [DSMMV19].

**Theorem 4.6.** The following statements hold.

1. The spectral bound is sharp for $\chi(\Lambda(C_n)) = 2$.

2. The spectral bound is sharp for $\chi(\Lambda(A_{n-1})) = n$.

3. We have $\chi(\Lambda(B_n)) = \chi(\Lambda(D_n)) \ge n$.

*Proof. 1.* We have $\Lambda(C_n) = \mathbb{Z}^n$. When we partition $\mathbb{Z}^n$ in elements with even and odd $\ell_1$-norm, then this gives an admissible coloring with $\chi(\Lambda(C_n)) \le 2$. To see that the spectral bound is sharp, note that $\rho_0^\vee = \rho_0/2 = \omega_1$ and consider the Chebyshev polynomial $T_{\rho_0^\vee} = T_{\omega_1} = z_1$. With Equation (4.3), we obtain

$$ \chi(\Lambda(C_n)) \ge 1 - \frac{1}{\min_{z \in \mathcal{T}} T_{\rho_0^\vee}(z)} = 1 - \frac{1}{\min_{z \in \mathcal{T}} z_1} \ge 1 - \frac{1}{\min_{z \in [-1,1]^n} z_1} = 1 - \frac{1}{-1} = 2. $$

2. We have $\chi(\Lambda(A_{n-1})) = n$ [DSMMV19] and $\rho_0^\vee = \rho_0 = \omega_1 + \omega_{n-1}$ with $-\omega_1 \in W\omega_{n-1}$. Using the recurrence formula from Equation (2.3), the to be minimized polynomial in Equation (4.3) is

$$ T_{\rho_0^\vee} = T_{\omega_1+\omega_{n-1}} = |W\omega_1|T_{\omega_1}T_{\omega_{n-1}} - \sum_{\substack{\mu \in W\omega_1 \\ \mu \neq \omega_1}} T_{\mu+\omega_{n-1}} = n z_1 z_{n-1} - (T_0 + (n-2)T_{\omega_1+\omega_{n-1}}). $$

The last equation follows from the fact that, if $\mu = -\omega_{n-1}$, then $\mu + \omega_{n-1} = 0$, and, if $\mu \neq -\omega_{n-1}$, then $\mu + \omega_{n-1} \in W(\omega_1 + \omega_{n-1})$, see Equation (A). Since $-\omega_1 \in W\omega_{n-1}$, we also have $z_1 z_{n-1} = z_1 \bar{z}_1 = |z_1|^2$ for $z \in \mathcal{T}$ (in the case of $A_{n-1}$, $\mathcal{T}$ is complex and can be embedded in $\mathbb{R}^{n-1}$ with Equation (2.5)). Altogether, we obtain

$$ \chi(\Lambda(A_{n-1})) \ge 1 - \frac{1}{\min_{z \in \mathcal{T}} T_{\rho_0^\vee}(z)} = 1 - \frac{n-1}{\min_{z \in \mathcal{T}} n z_1 z_{n-1} - 1} = 1 - \frac{n-1}{\min_{z \in \mathcal{T}} n |z_1|^2 - 1} \ge 1 - \frac{n-1}{-1} = n. $$

3. For $R = B_2$, we are in the situation of 1. with $\chi(\Lambda(B_2)) = 2$ (the square lattice). For $R = B_3$, we are in the situation of 2. with $\chi(\Lambda(B_3)) = 3$ (the rhombic lattice, see Figure 16). The root system $D_n$ is not defined for $n \le 3$. Thus, let $n \ge 4$ and $R \in \{B_n, D_n\}$. For $1 \le i \le n-1$, we have $\rho_i^\vee(B_n) = \rho_i^\vee(D_n)$ and $\rho_n^\vee(B_n) = \rho_n^\vee(D_n) - \rho_{n-1}^\vee(D_n)$ as well as $\rho_n^\vee(D_n) = \rho_n^\vee(B_n) + \rho_{n-1}^\vee(B_n)$. Hence, we have $\Lambda(B_n) = \Lambda(D_n)$ with $\rho_0^\vee = \rho_0 = \omega_2$. We consider $T_{\rho_0} = T_{\omega_2}(z) = z_2$ and minimize on $\mathcal{T}$. By Theorem 2.9, we have $\mathcal{T} = \{z \in \mathbb{R}^n | \mathbf{P}(z) \ge 0\}$ and the first entry of $\mathbf{P}$ is $\mathbf{P}_{11} = T_0 - T_{2\omega_1}$ with

$$ T_{2\omega_1} = |W\omega_1|T_{\omega_1}^2 - \sum_{\substack{\mu \in W\omega_1 \\ \mu \neq \omega_1}} T_{\mu+\omega_1} = 2n z_1^2 - (1+2(n-1)z_2). $$

The last equation follows from the fact that, if $\mu = -\omega_1$, then $\mu + \omega_1 = 0$, and, if $\mu \neq -\omega_1$, then $\mu + \omega_1 \in W(\omega_2)$, see Equations (B) and (D). Thus, for $z \in \mathcal{T}$, we have

$$ 0 \le \mathbf{P}_{11}(z) = T_0(z) - T_{2\omega_1}(z) = 1 - (2n z_1^2 - 1 - 2(n-1)z_2) \Leftrightarrow z_2 \ge \frac{n z_1^2 - 1}{n-1} \ge \frac{-1}{n-1} $$
and obtain

$$ \chi(\Lambda(\mathbb{R})) \geq 1 - \frac{1}{\min_{z \in \mathcal{T}} T_{\rho_0^\wedge}(z)} = 1 - \frac{1}{\min_{z \in \mathcal{T}} T_{\omega_2}(z)} = 1 - \frac{1}{\min_{z \in \mathcal{T}} z_2} \geq 1 - \frac{n-1}{-1} = n. $$

□

**Remark 4.7.** Since, up to rescaling, two adjacent vertices in $G(\Lambda)$ are also adjacent in the graph $G(\Lambda, \Lambda \cap \partial \mathrm{Vor}(\Lambda))$, the value of $\chi(\Lambda)$ also gives a lower bound on $\chi_m(\mathbb{R}^n, \partial \mathrm{Vor}(\Lambda))$, even if the two numbers can be far from each other. For instance, we have $\chi(\Lambda(\Lambda_n)) = n+1$, but $\chi(\mathbb{R}^n, \partial \mathrm{Vor}(\Lambda(\Lambda_n))) = 2^n$ [BBMP19].

A MAPLE worksheet dedicated to this subsection is available here:

https://tobiasmetzlaff.com/html_guides/chromatic_coroot_lattice.html

## 4.3 The chromatic number of $\mathbb{Z}^n$ for the crosspolytope

We consider the integer lattice $V = \mathbb{Z}^n$ and, for $r \in \mathbb{N}$, the avoided set

$$ \mathbb{B}_r^1 := \{u \in \mathbb{Z}^n \mid \|u\|_1 = |u_1| + \dots + |u_n| = r\}. $$

The convex hull of $\mathbb{B}_r^1$ is the ball of radius $r$ for the $\ell_1$-norm, known as the crosspolytope in Figure 9.

<figure><img src="image_10.png" /><figcaption>(a) $r=1$</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(b) $r=2$</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(c) $r=3$</figcaption></figure>

<caption>Figure 9: The crosspolytope is the ball of radius $r$ with respect to the $\ell_1$-norm. The boundary points with integer coordinates form the avoided set $\mathbb{B}_r^1$.</caption>

Two vertices in the graph $G(\mathbb{Z}^n, \mathbb{B}_r^1)$ are adjacent whenever the absolute values of the differences between their coordinates sum up to $r$. Several bounds for the chromatic number $\chi(\mathbb{Z}^n, \mathbb{B}_r^1)$ were given in [FK04] without using spectral bounds, but through combinatorial arguments.

If $\Omega$ is the weight lattice of some root system in $\mathbb{R}^n$ with $\mathbb{B}_r^1 \subseteq \Omega$, then we can compare by computing

$$ \chi(\mathbb{Z}^n, \mathbb{B}_r^1) \geq 1 - \frac{1}{F(r)}, \qquad (4.4) $$

where $F(r) := F(\mathbb{B}_r^1)$ is defined before Theorem 4.2.
**Lemma 4.8.** Let $0 < r \in \mathbb{N}$. If $R$ is a root system of type $B_n$, $C_n$ or $D_n$, then $\mathbb{B}_r^1 \subseteq \Omega$ and the dominant weights are $\mathbb{B}_r^1 \cap \Omega^+ =$

$$ \left\{ \begin{array}{ll} \{\alpha_1 \omega_1 + \dots + \alpha_n \omega_n | \alpha \in \mathbb{N}^n, \sum_{i=1}^n i \alpha_i = r\}, & \text{if } R = C_n \\ \\ \{\alpha_1 \omega_1 + \dots + \alpha_{n-1} \omega_{n-1} + 2 \alpha_n \omega_n | \alpha \in \mathbb{N}^n, \sum_{i=1}^n i \alpha_i = r\}, & \text{if } R = B_n \\ \\ \{\alpha_1 \omega_1 + \dots + \alpha_{n-2} \omega_{n-2} + 2(\alpha_{n-1} \omega_{n-1} + \alpha_n \omega_n) | \alpha \in \mathbb{N}^n, \sum_{i=1}^n i \alpha_i + \alpha_{n-1} = r\}, & \text{if } R = D_n \end{array} \right. $$

*Proof.* This follows from Equations (C) to (D) in the appendix. □

**Remark 4.9.** Denote by $\mathcal{P}$ the crosspolytope from Figure 9 for $r = 1$, that is, $\mathcal{P} = \text{ConvHull}(\mathbb{B}_1^1)$. Then $G(\mathbb{Z}^n, \mathbb{B}_r^1)$ is a discrete subgraph of $G(\mathbb{R}^n, \partial(r\mathcal{P}))$ and, since $\mathbb{R}^n$ is scaling invariant, we have

$$ \chi_m(\mathbb{R}^n, \partial\mathcal{P}) = \chi_m(\mathbb{R}^n, \partial(r\mathcal{P})) \geq \chi(\mathbb{Z}^n, \mathbb{B}_r^1). $$

Hence, computing the spectral bound for the chromatic number of $\mathbb{Z}^n$ always yields a lower bound for the chromatic number of $\mathbb{R}^n$.

### 4.3.1 Analytical bounds

We compute the spectral bound for $\chi(\mathbb{Z}^n, \mathbb{B}_r^1)$ first for the cases, where our rewriting technique allows for an analytical proof.

**Proposition 4.10.** Let $r \in \mathbb{N}$ be odd. The spectral bound is sharp for $\chi(\mathbb{Z}^n, \mathbb{B}_r^1) = 2$.

*Proof.* Since $r$ is odd, partitioning the vertices of $G(\mathbb{Z}^n, \mathbb{B}_r^1)$ in those with even and those with odd $\ell_1$-norm yields two independent sets. Hence, $\chi(\mathbb{Z}^n, \mathbb{B}_r^1) = \chi(\mathbb{Z}^n, \mathbb{B}_1^1) = 2$. To see that the spectral bound is sharp, let $R$ be a root system of type $C_n$. By Lemma 4.8, we have $\mathbb{B}_1^1 = W\omega_1$ and so

$$ \chi(\mathbb{Z}^n, \mathbb{B}_1^1) \geq 1 - \frac{1}{F(1)} \geq 1 - \frac{1}{\min_{z \in \mathcal{T}} z_1} \geq 1 - \frac{1}{-1} = 2. $$

The chromatic number of $\mathbb{Z}^n$ for $\ell_1$-distance $r = 2$ is $2n$. This was proven in [FK04, Theorem 1] with a purely combinatorial argument by fixing a coloring and showing that it is admissible and minimal.

**Theorem 4.11.** The spectral bound is sharp for $\chi(\mathbb{Z}^n, \mathbb{B}_2^1) = 2n$.

*Proof.* Let $R$ be a root system of type $C_n$. Thanks to Lemma 4.8, we have $\mathbb{B}_2^1 = W(2\omega_1) \cup W\omega_2$. We choose $c = 1/(2n-1) \in [0, 1]$ and consider

$$ cT_{2\omega_1} + (1-c)T_{\omega_2} = \frac{2nz_1^2 - 2(n-1)z_2 - 1}{2n-1} + \frac{2(n-1)z_2}{2n-1} = \frac{2nz_1^2 - 1}{2n-1}, $$

where the expression for $T_{2\omega_1}$ is obtained as in the proof of Theorem 4.6 (3). We have

$$ \chi(\mathbb{Z}^n, \mathbb{B}_2^1) \geq 1 - \frac{1}{F(2)} \geq 1 - \frac{1}{\min_{z \in \mathcal{T}} cT_{2\omega_1}(z) + (1-c)T_{\omega_2}(z)} \geq 1 - \frac{1}{(2nz_1^2 - 1)/(2n-1)} \geq 1 - \frac{2n-1}{-1} = 2n, $$

where we applied Equation (4.4). □
**Corollary 4.12.** Let $0 < r \in \mathbb{N}$ be even. The spectral bound is sharp for $\chi(\mathbb{Z}^2, \mathbb{B}_r^1) = 4$.

*Proof.* For $r = 2$, this is a special case of Theorem 4.11. In particular, for $r$ even, the spectral bound gives at least 4 for $\chi(\mathbb{Z}^2, \mathbb{B}_r^1)$. Let $\mathcal{P} = \text{ConvHull}(\mathbb{B}_1^1)$ be the crosspolytope in $\mathbb{R}^2$, that is, a square. We have

$$4 = \chi_m(\mathbb{R}^2, \partial\mathcal{P}) = \chi_m(\mathbb{R}^2, \partial(r\mathcal{P})) \geq \chi(\mathbb{Z}^2, \mathbb{B}_r^1) \geq \chi(\mathbb{Z}^2, \mathbb{B}_2^1) \geq 4,$$

where we used [BBMP19] and Remark 4.9. □

<figure><img src="image_13.png" /></figure>

### 4.3.2 Numerical bounds

Now, we compute spectral bounds for $\chi(\mathbb{Z}^n, \mathbb{B}_r^1)$ numerically for the dimensions $n = 3$ and $n = 4$. In order to do so, we approximate $F(r)$ from Equation (4.4) by computing $F(r, d) := F(\mathbb{B}_r^1, d)$ in Corollary 4.3 for $d \in \mathbb{N}$ sufficiently large.

**Dimension $n = 3$**

<table><caption>Table 3: The lower bound $\chi(\mathbb{Z}^3, \mathbb{B}_r^1) \geq 1 - 1/F(r, d)$ for dimension $n = 3$. The first column indicates the root system R, that is, the crystallographic symmetry we exploited. Then the rows are indexed by the relaxation order $d$ and the columns by the radius $r$ of the crosspolytope.</caption><thead><tr><th>R</th><th>d\r</th><th>2</th><th>4</th><th>6</th><th>8</th><th>10</th><th>12</th><th>14</th></tr></thead><tbody><tr><td rowspan="5">B<sub>3</sub></td><td>3</td><td>6.00000</td><td>6.28148</td><td>6.01551</td><td>—</td><td>—</td><td>—</td><td>—</td></tr><tr><td>4</td><td>6.00000</td><td>6.28148</td><td>6.07717</td><td>6.28148</td><td>—</td><td>—</td><td>—</td></tr><tr><td>5</td><td>6.00000</td><td>6.28148</td><td>6.29004</td><td>6.28183</td><td>6.12543</td><td>—</td><td>—</td></tr><tr><td>6</td><td>6.00000</td><td>6.28148</td><td>6.30244</td><td>6.29799</td><td>6.27850</td><td>6.28234</td><td>—</td></tr><tr><td>7</td><td>6.00000</td><td>6.28148</td><td>6.30269</td><td>6.30435</td><td>6.30031</td><td>6.29708</td><td>6.27830</td></tr><tr><td rowspan="5">C<sub>3</sub></td><td>3</td><td>6.00000</td><td>6.28148</td><td>6.02310</td><td>—</td><td>—</td><td>—</td><td>—</td></tr><tr><td>4</td><td>6.00000</td><td>6.28148</td><td>6.29021</td><td>6.28198</td><td>—</td><td>—</td><td>—</td></tr><tr><td>5</td><td>6.00000</td><td>6.28148</td><td>6.30182</td><td>6.29951</td><td>6.29810</td><td>—</td><td>—</td></tr><tr><td>6</td><td>6.00000</td><td>6.28148</td><td>6.30269</td><td>6.30455</td><td>6.30048</td><td>6.30069</td><td>—</td></tr><tr><td>7</td><td>6.00000</td><td>6.28148</td><td>6.30269</td><td>6.30494</td><td>6.30057</td><td>6.30229</td><td>6.30156</td></tr></tbody></table>

<figure><img src="image_14.png" /></figure>

<table><caption>Figure 10: The crosspolytope with radius $r = 4$ and the obtained optimal coefficients. Boundary points $\mu = \alpha_1 \omega_1 + \alpha_2 \omega_2 + \alpha_3 \omega_3 \in \mathbb{Z}^3$, which lie in the same Weyl group orbit, have the same coefficients $c_\alpha$, denoted by red, blue, green and purple dots.</caption><thead><tr><th colspan="2">C<sub>3</sub></th><th colspan="2">B<sub>3</sub></th></tr><tr><th>1 - 1/F(4, 7)</th><th>c<sub>α</sub></th><th>1 - 1/F(4, 9)</th><th>c<sub>α</sub></th></tr></thead><tbody><tr><td>6.28148</td><td>c<sub>400</sub> = 0.01752<br>c<sub>210</sub> = 0.22681<br>c<sub>101</sub> = 0.59380<br>c<sub>020</sub> = 0.16185</td><td>6.28148</td><td>c<sub>400</sub> = 0.01754<br>c<sub>210</sub> = 0.22680<br>c<sub>102</sub> = 0.59375<br>c<sub>020</sub> = 0.16189</td></tr></tbody></table>
<figure><img src="image_15.png" /><figcaption>Figure 11: The coefficients $c_\alpha$ for $F(r, 9)$ in the case of $R = B_3$, encoded by the intensity of the color red as $\text{RGB}(1, \varepsilon_\alpha, \varepsilon_\alpha)$, where $\varepsilon_\alpha := 1 - (c_\alpha - c_{\min})/(c_{\max} - c_{\min}) \in [0, 1]$. In particular, $c_{\max}$ is red, $c_{\min}$ is white.</figcaption></figure>
The theoretical value $\chi(Z^3, \mathbb{B}_2^1) = 6$ from Theorem 4.11 is obtained immediately with $F(2, 1)$. The highest value in the table is given by $F(9, 10)$ for $B_3$. We display the obtained optimal coefficients, which coincide for $B_3$ and $C_3$ in Figures 10 and 11 and Table 10.

**Remark 4.13.** By [FK04, Prop. 9], we have $\chi(Z^3, \mathbb{B}_4^1) \ge 7$. Our computation yields the same bound.

**Dimension $n = 4$**

<table><caption>Table 4: The lower bound $\chi(Z^4, \mathbb{B}_r^1) \ge 1 - 1/F(r, d)$ for dimension $n = 4$. The first column indicates the root system R, that is, the crystallographic symmetry we exploited. Then the rows are indexed by the relaxation order $d$ and the columns by the radius $r$ of the crosspolytope.</caption><thead><tr><th>R</th><th>d\r</th><th>2</th><th>4</th><th>6</th><th>8</th><th>10</th><th>12</th><th>14</th></tr></thead><tbody><tr><td rowspan="4">B<sub>4</sub></td><td>4</td><td>8.00000</td><td>10.33968</td><td>9.09234</td><td>10.33968</td><td>—</td><td>—</td><td>—</td></tr><tr><td>5</td><td>8.00000</td><td>10.33969</td><td>9.72339</td><td>10.33969</td><td>9.17503</td><td>—</td><td>—</td></tr><tr><td>6</td><td>8.00000</td><td>10.83655</td><td>10.18050</td><td>10.33969</td><td>9.90514</td><td>10.33968</td><td>—</td></tr><tr><td>7</td><td>8.00000</td><td>10.86019</td><td>10.51696</td><td>10.51282</td><td>10.16103</td><td>10.33968</td><td>10.03938</td></tr><tr><td rowspan="2">C<sub>4</sub></td><td>4</td><td>8.00000</td><td>10.33993</td><td>9.72014</td><td>10.33968</td><td>—</td><td>—</td><td>—</td></tr><tr><td>5</td><td>8.00000</td><td>10.83902</td><td>10.07664</td><td>10.33968</td><td>9.94864</td><td>—</td><td>—</td></tr><tr><td rowspan="3">D<sub>4</sub></td><td>4</td><td>8.00000</td><td>10.34750</td><td>9.08887</td><td>10.33969</td><td>—</td><td>—</td><td>—</td></tr><tr><td>5</td><td>8.00000</td><td>10.39184</td><td>9.72430</td><td>10.34011</td><td>9.52887</td><td>—</td><td>—</td></tr><tr><td>6</td><td>8.00000</td><td>10.83844</td><td>10.34886</td><td>10.35578</td><td>9.97888</td><td>10.33971</td><td>—</td></tr></tbody></table>

The value $\chi(Z^4, \mathbb{B}_2^1) = 8$ is obtained immediately with $F(2, 1)$. The highest value is $F(4, 7)$ for $B_4$. The computed bounds $F(r, d)$ are strictly increasing along the columns, that is, when we increase $d$.

**Remark 4.14.** By [FK04, Prop. 9], we have $\chi(Z^4, \mathbb{B}_4^1) \ge 9$. Our computation strengthens the bound to 11.

The computations for the examples in this subsection are documented here:

https://tobiasmetzlaff.com/html_guides/chromatic_Zn-crosspolytope.html

## 4.4 The chromatic number of $\mathbb{R}^n$ for Voronoï cells

Finally we consider the case of the Euclidean space $V = \mathbb{R}^n$ as a set of vertices, where the avoided set $S = \partial P$ is the boundary of a convex centrally-symmetric polytope $P$. This setting was studied in [BBMP19], giving bounds on $\chi_m(\mathbb{R}^n, \partial P)$ without using spectral bounds. There it was proven that $\chi_m(\mathbb{R}^n, \partial P) \le 2^n$ whenever $P$ tiles $\mathbb{R}^n$ and equality is conjectured. We now investigate the strength of the spectral bound for certain instances of this graph.
<figure><img src="image_16.png" /><figcaption>Figure 12: The chromatic number of $\mathbb{R}^2$ for the hexagon is $2^2 = 4$ [BBMP19].</figcaption></figure>

Given a Weyl group $W$ associated to a root systems in $\mathbb{R}^n$, the Voronoï cell $\text{Vor}(\Lambda)$ of the coroot lattice is a convex centrally-symmetric polytope, invariant under $W$ and tiles $\mathbb{R}^n$ by $\Lambda$-translation, see Equation (2.1). If the root system is irreducible with highest root $\rho_0$, then we have $\text{Vor}(\Lambda) = W\Delta$, where

$$ \Delta = \{u \in \mathbb{R}^n | \forall 1 \le i \le n : \langle u, \rho_i \rangle \ge 0 \text{ and } \langle u, \rho_0 \rangle \le 1\} $$

is a fundamental domain of the affine Weyl group $W \times \Lambda$, see Proposition 2.3. In particular, the part of the boundary $\partial \text{Vor}(\Lambda) \cap \bar{\Lambda}$, which is also contained in the fundamental Weyl chamber, lies on a hyperplane parallel to $\langle \cdot, \rho_0 \rangle = 0$. Rescaling the polytope $\text{Vor}(\Lambda)$ by a factor $\tilde{r} > 0$ does not affect the chromatic number, that is, $\chi_m(\mathbb{R}^n, \partial \text{Vor}(\Lambda)) = \chi_m(\mathbb{R}^n, \partial(\tilde{r} \text{Vor}(\Lambda)))$. If we choose $\tilde{r} = r \langle \rho_0, \rho_0 \rangle / 2$ for some $0 \ne r \in \mathbb{N}$, then $\partial(\tilde{r} \text{Vor}(\Lambda)) \cap \Omega \ne \emptyset$ and we obtain a hierarchy of lower bounds

$$ \chi_m(\mathbb{R}^n, \partial \text{Vor}(\Lambda)) \ge \dots \ge 1 - \frac{1}{F(4r)} \ge 1 - \frac{1}{F(2r)} \ge 1 - \frac{1}{F(r)} \ge 1 - \frac{1}{F(1)}, \quad (4.5) $$

where $F(r) := F(S_r)$ is as in Theorem 4.2 with $S_r := W\{u \in \bar{\Lambda} | \langle u, \rho_0 \rangle = r\}$.

**Remark 4.15.** The quantity $1 - 1/F(r)$ is a lower bound for $\chi_m(\mathbb{R}^n, \partial \text{Vor}(\Lambda))$. More precisely, we have

$$ \chi_m(\mathbb{R}^n, \partial \text{Vor}(\Lambda)) \ge \chi(\Omega, S_r) \ge 1 - \frac{1}{F(r)} $$

and $F(r)$ is the minimum of the Fourier transformation of the optimal measure $B$ (with mass 1) in Theorem 4.1 for the graph $G(\Omega, S_r)$.

To compute $F(r)$ numerically, we use Corollary 4.3 and write $F(r, d) := F(S_r, d)$. Recall from Remark 4.4 that $F(r, d) \ge F(\ell r, d)$ is only certain when $d \to \infty$.

<figure><img src="image_17.png" /><figcaption>Figure 13: Rescaling the hexagon increases the number of weights $S_r \cap \Omega$ on the boundary.</figcaption></figure>
### 4.4.1 The hexagon in $\mathbb{R}^2$

The hexagon in $\mathbb{R}^2 \cong \mathbb{R}^3 / \langle [1, 1, 1]^t \rangle$, as it has appeared several times now in the article, is the Voronoï cell of the coroot lattice $\Lambda$ for $A_2$ and $G_2$. It has 6 vertices and 6 edges. For $A_2$, the vertices of the hexagon are the orbits of the fundamental weights $\omega_1$ and $\omega_2$. The centers of the edges are the orbit of $(\omega_1 + \omega_2)/2$. We fix a hierarchy order $d \ge 3$ and consider $F(r, d)$ for $1 \le r \le 2d$. For $G_2$, the vertices are the orbit of $\omega_1/3$. The centers of edges are the orbit of $\omega_2/6$. If $r \in \mathbb{N}$ is not a multiple of 3, then $S_r = \emptyset$. Thus we consider $F(3r, d)$ for $1 \le r \le 2d$, but still write $F(r, d)$ for simplicity.

<table><caption>Table 5: The lower bound $\chi_m(\mathbb{R}^2, \partial\mathrm{Vor}(\Lambda(A_2))) = \chi_m(\mathbb{R}^2, \partial\mathrm{Vor}(\Lambda(G_2))) \ge 1 - 1/F(r, d)$ for the hexagon. The first column indicates the root system $R$, that is, the crystallographic symmetry we exploited. Then the rows are indexed by the relaxation order $d$ and the columns by the scaling factor $r$ of the Voronoï cell.</caption><thead><tr><th>R</th><th>d\r</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th></tr></thead><tbody><tr><td rowspan="6">A<sub>2</sub></td><td>3</td><td>2.99386</td><td>3.57143</td><td>3.52451</td><td>3.57143</td><td>3.37484</td><td>3.57143</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>4</td><td>3.00000</td><td>3.57143</td><td>3.52911</td><td>3.57143</td><td>3.54698</td><td>3.57143</td><td>3.47461</td><td>3.57143</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>5</td><td>3.00000</td><td>3.57143</td><td>3.52912</td><td>3.57143</td><td>3.54789</td><td>3.57143</td><td>3.54016</td><td>3.57143</td><td>3.51384</td><td>3.57143</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>6</td><td>3.00000</td><td>3.57143</td><td>3.52912</td><td>3.57143</td><td>3.54789</td><td>3.57143</td><td>3.54786</td><td>3.57143</td><td>3.55920</td><td>3.57143</td><td>3.47623</td><td>3.57143</td><td>-</td><td>-</td></tr><tr><td>7</td><td>3.00000</td><td>3.57143</td><td>3.52912</td><td>3.57143</td><td>3.54789</td><td>3.57143</td><td>3.55183</td><td>3.57143</td><td>3.55921</td><td>3.57143</td><td>3.51433</td><td>3.57143</td><td>3.14739</td><td>3.57143</td></tr><tr><td>8</td><td>3.00000</td><td>3.57143</td><td>3.52912</td><td>3.57143</td><td>3.54789</td><td>3.57143</td><td>3.55347</td><td>3.57143</td><td>3.55921</td><td>3.57143</td><td>3.53571</td><td>3.57143</td><td>3.25411</td><td>3.57143</td></tr><tr><td rowspan="6">G<sub>2</sub></td><td>3</td><td>2.99732</td><td>3.57143</td><td>3.39930</td><td>3.57143</td><td>2.47997</td><td>3.57143</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>4</td><td>2.99962</td><td>3.57143</td><td>3.52821</td><td>3.57143</td><td>3.41805</td><td>3.57143</td><td>2.54024</td><td>3.57143</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>5</td><td>3.00000</td><td>3.57143</td><td>3.52908</td><td>3.57143</td><td>3.49102</td><td>3.57143</td><td>2.76603</td><td>3.57143</td><td>2.45902</td><td>3.57143</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>6</td><td>3.00000</td><td>3.57143</td><td>3.52912</td><td>3.57143</td><td>3.52318</td><td>3.57143</td><td>3.39290</td><td>3.57143</td><td>2.70265</td><td>3.57143</td><td>2.98423</td><td>3.57143</td><td>-</td><td>-</td></tr><tr><td>7</td><td>3.00000</td><td>3.57143</td><td>3.52912</td><td>3.57143</td><td>3.54301</td><td>3.57143</td><td>3.54780</td><td>3.57143</td><td>3.53627</td><td>3.57143</td><td>3.28144</td><td>3.57143</td><td>2.50993</td><td>3.57143</td></tr><tr><td>8</td><td>3.00000</td><td>3.57143</td><td>3.52912</td><td>3.57143</td><td>3.54656</td><td>3.57143</td><td>3.55294</td><td>3.57143</td><td>3.54181</td><td>3.57143</td><td>3.54139</td><td>3.57143</td><td>3.13764</td><td>3.57143</td></tr></tbody></table>

For $r = 1$, there is no choice for the coefficients $c_\mu$, as $S_1$ only contains one element in both cases $A_2$ and $G_2$. The value $F(1)$ is $-1/2$. This gives spectral bound 3 and is obtained from $F(r, d)$ for $d \ge 4$, respectively $d \ge 5$. Furthermore, this fits with the bound from Theorem 4.6, where $\chi(\Lambda) \ge n$ for $A_{n-1}$.

For $r \ge 2$, the best possible bound we obtained is already assumed at $r = 2$ and $d = 3$. We display the optimal coefficients for the corresponding measure below. This bound is assumed in all $F(r, d)$ with $r$ even at lowest possible order. For $r$ odd, the value converges but does not stabilize.

Although we recover that the chromatic number of $\mathbb{R}^2$ for the hexagon is 4, see Figure 13, our computations indicate that the spectral bound is not sharp and never will be with $r, d \to \infty$.

<figure><img src="image_18.png" /></figure>

<table><caption>Figure 14: The scaled Voronoï cell and the optimal coefficients for $F(2, 8)$. Boundary points $\mu = \alpha_1 \omega_1 + \alpha_2 \omega_2$, which lie in the same Weyl group orbit, and their diametrically opposites $\hat{\mu} = \hat{\alpha}_2 \omega_1 + \hat{\alpha}_1 \omega_2$ have the same coefficients $c_\alpha = c_{\hat{\alpha}}$, denoted by either red or blue dots.</caption><thead><tr><th></th><th colspan="2">A<sub>2</sub></th><th colspan="2">G<sub>2</sub></th></tr><tr><th>r</th><th>1 - 1/F(r, 8)</th><th>c<sub>α</sub> = c<sub>α̂</sub></th><th>1 - 1/F(r, 8)</th><th>c<sub>α</sub></th></tr></thead><tbody><tr><td>1</td><td>3.00000</td><td>c<sub>10</sub> = 1.00000</td><td>3.00000</td><td>c<sub>10</sub> = 1.00000</td></tr><tr><td>2</td><td>3.57143</td><td>c<sub>20</sub> = 0.33333<br>c<sub>11</sub> = 0.66667</td><td>3.57143</td><td>c<sub>20</sub> = 0.33333<br>c<sub>01</sub> = 0.66667</td></tr></tbody></table>

From Figure 14, we guess that the coefficients $1/3$ for the vertices and $2/3$ for the centers of faces are optimal.
Then, for $r \in \mathbb{N}$, we have

$$ F(2r) = \begin{cases} \min_{z \in \mathcal{T}} \frac{2}{3} T_{rr}(z) + \frac{1}{6} (T_{2r0}(z) + T_{02r}(z)) = \min_{z \in \mathcal{T}} \frac{2}{3} T_{11}(z) + \frac{1}{6} (T_{20}(z) + T_{02}(z)), & \text{if } R = A_2 \\ \min_{z \in \mathcal{T}} \frac{2}{3} T_{0r}(z) + \frac{1}{3} T_{2r0}(z) = \min_{z \in \mathcal{T}} \frac{2}{3} T_{01}(z) + \frac{1}{3} T_{20}(z), & \text{if } R = G_2 \\ \min_{z \in \mathcal{T}} 2z_1^2 - 2/3 z_1 - 1/3 = -7/18 & \end{cases} \tag{4.6} $$

(for $A_2$, we have to substitute $z_i = z_1 \pm i z_2$, so that $\mathcal{T} \subseteq \mathbb{R}^2$). In both cases, $1 - 1/F(2r) = 25/7 \approx 3.57143$. Note that $F(2)$ corresponds to the trigonometric polynomial in Example 2.11 up to a factor 1/3.

<figure><img src="image_19.png" /><figcaption>Figure 15: The minimizers $z$ (lines, above) for $F(2r)$ in the image $\mathcal{T}$ of the generalized cosines with preimages $u$ (ovals, below). In the coordinates $u$, we can observe the $\Lambda$-periodicity and $W$-invariance, yielding the crystallographic symmetry on the alcove $\Delta$ of $W \times \Lambda$ (simplex).</figcaption></figure>

### 4.4.2 The rhombic dodecahedron in $\mathbb{R}^3$

The rhombic dodecahedron in $\mathbb{R}^3$ (Figure 16) is the Voronoi cell of the coroot lattice $\Lambda$ for $A_3$ and $B_3$. It has 14 vertices, 24 edges and 12 faces. For $A_3$, the vertices are the orbits of $\omega_1, \omega_2$ and $\omega_3$. The centers of the edges are the orbits of $(\omega_i + \omega_2)/2$ for $i = 1, 2$, and the centers of the facets are the orbit of $(\omega_1 + \omega_3)/2$.
For $B_3$, the vertices are the orbits of $\omega_1$ and $\omega_3$. The centers of the edges are the orbit of $(\omega_1 + \omega_3)/2$, and the centers of the facets are the orbit of $\omega_2/2$.

<figure><img src="image_20.png" /><figcaption>Figure 16: The rhombic dodecahedron is the Voronoï cell of the coroot lattice for $A_3$ and $B_3$.</figcaption></figure>

<table><caption>Table 6: The lower bound $\chi_m(\mathbb{R}^3, \partial\text{Vor}(\Lambda(A_3))) = \chi_m(\mathbb{R}^3, \partial\text{Vor}(\Lambda(B_3))) \ge 1 - 1/F(r, d)$ for the rhombic dodecahedron. The first column indicates the root system R, that is, the crystallographic symmetry we exploited. Then the rows are indexed by the relaxation order d and the columns by the scaling factor r of the Voronoï cell.</caption><thead><tr><th>R</th><th>d<sub>r</sub></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th></tr></thead><tbody><tr><td rowspan="4">A<sub>3</sub></td><td>4</td><td>3.99424</td><td>6.10767</td><td>5.86933</td><td>6.10766</td><td>5.81858</td><td>6.10766</td><td>4.77576</td><td>6.10766</td><td>—</td><td>—</td><td>—</td><td>—</td><td>—</td><td>—</td></tr><tr><td>5</td><td>3.99611</td><td>6.10767</td><td>5.86964</td><td>6.10766</td><td>5.90988</td><td>6.10767</td><td>5.85369</td><td>6.10766</td><td>5.46888</td><td>6.10766</td><td>—</td><td>—</td><td>—</td><td>—</td></tr><tr><td>6</td><td>3.99653</td><td>6.10767</td><td>5.86972</td><td>6.10767</td><td>5.93658</td><td>6.10767</td><td>5.85762</td><td>6.10766</td><td>5.85825</td><td>6.10766</td><td>3.78978</td><td>6.10766</td><td>—</td><td>—</td></tr><tr><td>7</td><td>3.99702</td><td>6.10767</td><td>5.86988</td><td>6.10767</td><td>5.94146</td><td>6.10766</td><td>5.96334</td><td>6.10767</td><td>5.85986</td><td>6.10766</td><td>4.12186</td><td>6.10766</td><td>—</td><td>6.10766</td></tr><tr><td rowspan="4">B<sub>3</sub></td><td>8</td><td>3.99719</td><td>6.10767</td><td>5.86992</td><td>6.10767</td><td>5.94327</td><td>6.10767</td><td>6.05399</td><td>6.10767</td><td>5.86357</td><td>6.10766</td><td>5.59839</td><td>6.10766</td><td>3.88490</td><td>6.10766</td></tr><tr><td>3</td><td>3.83791</td><td>6.10767</td><td>3.39918</td><td>6.10766</td><td>—</td><td>6.10766</td><td>—</td><td>—</td><td>—</td><td>—</td><td>—</td><td>—</td><td>—</td><td>—</td></tr><tr><td>4</td><td>3.84571</td><td>6.10767</td><td>4.11626</td><td>6.10766</td><td>—</td><td>6.10766</td><td>—</td><td>6.10766</td><td>—</td><td>—</td><td>—</td><td>—</td><td>—</td><td>—</td></tr><tr><td>5</td><td>3.98454</td><td>6.10767</td><td>5.80542</td><td>6.10766</td><td>5.08174</td><td>6.10767</td><td>—</td><td>6.10766</td><td>—</td><td>6.10766</td><td>—</td><td>—</td><td>—</td><td>—</td></tr><tr><td rowspan="4"></td><td>6</td><td>3.99667</td><td>6.10767</td><td>5.87057</td><td>6.10767</td><td>5.86644</td><td>6.10767</td><td>5.82630</td><td>6.10766</td><td>—</td><td>6.10766</td><td>—</td><td>6.10766</td><td>—</td><td>—</td></tr><tr><td>7</td><td>3.99872</td><td>6.10767</td><td>5.87057</td><td>6.10767</td><td>5.94578</td><td>6.10766</td><td>5.96989</td><td>6.10767</td><td>5.88810</td><td>6.10766</td><td>—</td><td>6.10766</td><td>—</td><td>6.10766</td></tr><tr><td>8</td><td>3.99925</td><td>6.10767</td><td>5.87057</td><td>6.10767</td><td>5.96374</td><td>6.10767</td><td>5.99825</td><td>6.10767</td><td>5.94949</td><td>6.10766</td><td>5.92157</td><td>6.10766</td><td>5.31568</td><td>6.10766</td></tr><tr><td>9</td><td>3.99972</td><td>6.10767</td><td>5.87057</td><td>6.10767</td><td>5.97050</td><td>6.10767</td><td>6.00193</td><td>6.10767</td><td>5.98345</td><td>6.10767</td><td>5.98654</td><td>6.10766</td><td>5.93977</td><td>6.10766</td></tr></tbody></table>

<figure><img src="image_21.png" /></figure>

<table><caption>Figure 17: The scaled Voronoï cell and the obtained optimal coefficients. Supporting points $\mu = \alpha_1 \omega_1 + \alpha_2 \omega_2 + \alpha_3 \omega_3$ in the same Weyl group orbit and their additive inverse $\hat{\mu}$ have the same coefficients $c_\alpha = c_{\alpha\hat{\alpha}}$, denoted by red, blue, green and purple dots.</caption><thead><tr><th></th><th colspan="2">A<sub>3</sub></th><th colspan="2">B<sub>3</sub></th></tr><tr><th>r</th><th>1 - 1/F(r, 8)</th><th>c<sub>α</sub> = c<sub>α̂</sub></th><th>1 - 1/F(r, 9)</th><th>c<sub>α</sub></th></tr></thead><tbody><tr><td>1</td><td>3.99719</td><td>c<sub>010</sub> = 0.33298<br>c<sub>100</sub> = 0.66702</td><td>3.99972</td><td>c<sub>100</sub> = 0.33332<br>c<sub>001</sub> = 0.66668</td></tr><tr><td>2</td><td>6.10767</td><td>c<sub>020</sub> = 0.10282<br>c<sub>110</sub> = 0.24392<br>c<sub>200</sub> = 0.06050<br>c<sub>101</sub> = 0.59276</td><td>6.10767</td><td>c<sub>200</sub> = 0.10283<br>c<sub>101</sub> = 0.24388<br>c<sub>002</sub> = 0.06050<br>c<sub>010</sub> = 0.59279</td></tr></tbody></table>
For $r = 1$, the numerically computed bound seems to converge to 4 in Table 6. For $r \ge 2$, the best possible bound we obtain is already assumed at $r = 2$ and $d = 3$, respectively $d = 4$. We display the optimal coefficients for the corresponding measure in Figure 17. This bound is approximately assumed in all $F(r, d)$ with $r$ even at lowest possible order $d$. For $r$ odd, the value does not stabilize with $r$ or $d$ growing. The root systems $A_3$ and $B_3$ give the same coefficients for the same supporting points. As in the case of the hexagon, the gap between the spectral bound for such discrete measures and the actual chromatic number of $\mathbb{R}^3$ for the rhombic dodecahedron (known to be 8 by [BBMP19]) seems quite large.

As we can observe from Figure 17, the most amount of weight is on the center of faces, then on the centers of edges and only a small weight lies on the vertices. We investigate the minimizers of the associated sum of generalized Chebyshev polynomials. Similar to Equation (4.6), one finds the following.

1. For $R = B_3$, the minimizers for $F(2, 8)$ are $z_{\min} \approx (0.05927, z_2, 0.22212)$ with $z_2 \in \mathbb{R}$ so that $z_{\min} \in \mathcal{T}$.

2. For $R = A_3$, the minimizers for $F(2, 8)$ are $z_{\min} \approx (0.22209, 0.05915, z_3)$ with $z_3 \in \mathbb{R}$ so that $z_{\min} \in \mathcal{T}$.

<figure><img src="image_22.png" /><figcaption>Figure 18: In the case of $A_3$, there are two minimizers $z_{\min} \approx (0.22209, 0.05915, \pm 0.23708)$ for $F(2, 8)$ on the boundary of $\mathcal{T}$, the image of the generalized cosines, with two preimages $u_{\min} \approx (0.40432, \pm 0.15713, 0.17550)$ on the boundary of $\Delta$, the fundamental domain of $W \times \Lambda$.</figcaption></figure>

### 4.4.3 The icositetrachoron in $\mathbb{R}^4$

The icositetrachoron in $\mathbb{R}^4$ is the Voronoï cell of the coroot lattice $\Lambda$ for $B_4$ and $D_4$. It has 24 vertices, 96 edges, 96 faces and 24 facets. The facets are octahedral cells. For $B_4$, the vertices are the orbits of $\omega_1$ and $\omega_4$. The centers of edges are the orbits of $(\omega_1 + \omega_4)/2$ and $\omega_3/2$. The centers of faces are the orbit of $(\omega_1 + \omega_3)/3$. The centers of facets are the orbit of $\omega_2/2$. For $D_4$, the vertices are the orbits of $\omega_1$, $\omega_3$ and $\omega_4$. The centers of edges are the orbits of $(\omega_1 + \omega_3)/2$, $(\omega_1 + \omega_4)/2$ and $(\omega_3 + \omega_4)/2$. The centers of faces are the orbit of $(\omega_1 + \omega_3 + \omega_4)/3$. The centers of facets are the orbit of $\omega_2/2$.

<table><caption>Table 7: The bound $\chi_m(\mathbb{R}^4, \partial\mathrm{Vor}(\Lambda(B_4))) = \chi_m(\mathbb{R}^4, \partial\mathrm{Vor}(\Lambda(D_4))) \ge 1 - 1/F(r, d)$ for the icositetrachoron. The first column indicates the root system R, that is, the crystallographic symmetry we exploited. Then the rows are indexed by the relaxation order $d$ and the columns by the scaling factor $r$ of the Voronoï cell.</caption><thead><tr><th>R</th><th>d\r</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th></tr></thead><tbody><tr><td rowspan="4">B<sub>4</sub></td><td>4</td><td>3.01160</td><td>10.00001</td><td>-</td><td>10.00000</td><td>-</td><td>10.0000</td><td>-</td><td>10.00000</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>5</td><td>3.77462</td><td>10.00035</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>-</td></tr><tr><td>6</td><td>3.99453</td><td>10.02433</td><td>9.10927</td><td>10.01295</td><td>8.91701</td><td>10.00001</td><td>4.69147</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td></tr><tr><td>7</td><td>3.99961</td><td>10.02434</td><td>9.12574</td><td>10.01902</td><td>9.26148</td><td>10.00819</td><td>9.32108</td><td>10.00000</td><td>8.35442</td><td>10.00000</td><td>4.15681</td><td>10.00000</td></tr><tr><td rowspan="3">D<sub>4</sub></td><td>4</td><td>3.07035</td><td>10.00004</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>5</td><td>3.94031</td><td>10.00231</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>-</td></tr><tr><td>6</td><td>3.99496</td><td>10.02432</td><td>9.11312</td><td>10.01314</td><td>8.93873</td><td>10.00001</td><td>5.12215</td><td>10.00000</td><td>-</td><td>10.00000</td><td>-</td><td>10.00000</td></tr></tbody></table>
For $r = 1$, the numerically computed bound seems to converge to 4. For $r \ge 2$, the best possible bound we obtained is assumed at $r = 2$ and $d = 7$, respectively $d = 6$. For $r$ odd, the value is always smaller than for $r$ even. For $B_4$, we observe that $F(2, 7) \ge F(4, 7)$, see Remark 4.4. In the $D_4$ case, the same happens with $F(2, 6) \ge F(4, 6)$. We display the optimal coefficients for the corresponding measure in Table 8.

<table><caption>Table 8: The optimal coefficients for $F(r, 7)$, respectively $F(r, 6)$. The coefficients associated to $\mu = \alpha_1 \omega_1 + \dots + \alpha_4 \omega_4$ are denoted by $c_\alpha$.</caption><thead><tr><th></th><th colspan="2">B<sub>4</sub></th><th colspan="2">D<sub>4</sub></th></tr><tr><th>r</th><th>1 - 1/F(r, 7)</th><th>c<sub>α</sub></th><th>1 - 1/F(r, 6)</th><th>c<sub>α</sub></th></tr></thead><tbody><tr><td rowspan="2">1</td><td rowspan="2">3.99961</td><td>c<sub>1000</sub> = 0.33303</td><td rowspan="2">3.99496</td><td>c<sub>1000</sub> = 0.33305</td></tr><tr><td>c<sub>0001</sub> = 0.66697</td><td>c<sub>0010</sub> = 0.33348</td></tr><tr><td rowspan="6">2</td><td rowspan="6">10.02434</td><td>c<sub>0100</sub> = 0.40062</td><td rowspan="6">10.02432</td><td>c<sub>0100</sub> = 0.40188</td></tr><tr><td>c<sub>1001</sub> = 0.35491</td><td>c<sub>1001</sub> = 0.17692</td></tr><tr><td>c<sub>0010</sub> = 0.17769</td><td>c<sub>1010</sub> = 0.17692</td></tr><tr><td>c<sub>0002</sub> = 0.04444</td><td>c<sub>0011</sub> = 0.17726</td></tr><tr><td>c<sub>2000</sub> = 0.02234</td><td>c<sub>0002</sub> = 0.02228</td></tr><tr><td>c<sub>2000</sub> = 0.02245</td><td>c<sub>0020</sub> = 0.02228</td></tr></tbody></table>

Recall from Equations (B) and (D) that the fundamental weights satisfy $\omega_i(B_4) = \omega_i(D_4)$ for $i = 1, 2, 4$ and $\omega_3(B_4) = \omega_3(D_4) + \omega_4(D_4)$. For $r = 2$, we observe in Table 8 that

1. the centers of facets are weighted with $0.40062 \approx 0.40188$,

2. the centers of faces are not weighted,

3. the centers of edges are weighted with $0.35491 \approx 0.17692 + 0.17692$ and $0.17769 \approx 0.17726$ and

4. the vertices are weighted with $0.02234 \approx 0.02245$ and $0.04444 \approx 0.02228 + 0.02228$.

**Remark 4.16.** The chromatic number of $\mathbb{R}^4$ for the icositetrachoron is at least 15, which is proven analytically in [BBMP19, Theorem 5] by constructing a discrete subgraph and computing its clique density.

#### 4.4.4 The hypercube in $\mathbb{R}^n$

The hypercube $[-1/2, 1/2]^n$ is the Voronoï cell of the coroot lattice for the root system $C_n$, that is, for the integer lattice $\Lambda(C_n) = \mathbb{Z}^n$. In this case, the chromatic number is known to be $2^n$, see [BBMP19] for a counting argument that does not involve spectral bounds. We reprove this fact with the spectral bound by taking a $W$-invariant measure, which is supported on the vertices and centers of edges, faces, etc. of $\text{Vor}(\Lambda(C_n))$.

**Proposition 4.17.** The spectral bound is sharp for $\chi_m(\mathbb{R}^n, \partial\text{Vor}(\Lambda(C_n))) = 2^n$.

*Proof.* The set of dominant weights $\mu \in \Omega^+$ of $C_n$ with $\langle\mu, \rho_0^\vee\rangle = 1$ consists precisely of the fundamental weights $\omega_1, \dots, \omega_n$. We set $(2^n - 1) c_i := \binom{n}{i}$. Then $c_1, \dots, c_n \ge 0$ with $c_1 + \dots + c_n = 1$ and the polynomial

$$ \sum_{\langle \mu, \rho_0^\vee \rangle = 1} c_\mu T_\mu(z) = \sum_{i=1}^{n} c_i z_i. $$
is an admissible choice for Equation (4.5). We show that it provides the optimal bound $2^n$. To do so, we rely on the formula for the fundamental weights from Equation (C), which gives us

$$ (2^n - 1) c_i c_i(u) = \sigma_i(\cos(2\pi u_1), \dots, \cos(2\pi u_n)), $$

where $\sigma_i$ is the i-th elementary symmetric function. When we substitute $z_i = c_i(u)$ for $u \in \mathbb{R}^n$, then

$$ (2^n - 1) \sum_{i=1}^{n} c_i z_i = \sum_{i=1}^{n} (2^n - 1) c_i c_i(u) = \sum_{i=1}^{n} \sigma_i(\cos(2\pi u_1), \dots, \cos(2\pi u_n)) = \prod_{k=1}^{n} \underbrace{(1 + \cos(2\pi u_k))}_{\ge 0} - 1 \ge -1 $$

follows from Vieta's formula and equality holds for $u = 1/2 \omega_j$. Altogether,

$$ 2^n \ge \chi_m(\mathbb{R}^n, \partial\mathrm{Vor}(\Lambda(C_n))) \ge 1 - \frac{1}{\min_{z \in \mathcal{T}} \sum_{i=1}^n c_i z_i} \ge 1 - \frac{2^n - 1}{-1} = 2^n $$

completes the proof. $\square$

**Remark 4.18.** The choice for the coefficients $c_i$ in the proof of Proposition 4.17 comes from the following observation: Let $\mathbf{P} \in \mathbb{R}[z]^{n \times n}$ be the matrix polynomial from Theorem 2.9. For small $n$ (say $n \le 10$), one can check that the determinant $\mathrm{Det}(\mathbf{P})$ has two factors of degree 1 and one of them is the polynomial in the proof, namely

$$ p := 1 + \sum_{i=1}^{n} \binom{n}{i} z_i \in \mathbb{R}[z]. $$

The image of the generalized cosines $\mathcal{T}$ is contained in the halfspace $\{z \in \mathbb{R}^n | p(z) \ge 0\}$, see Figure 5. This simplifies the proof, giving it completely in terms of generalized Chebyshev polynomials.

The computations for the examples in this subsection are documented here:

https://tobiasmetzlaff.com/html_guides/chromatic_Rn_voronoi.html

## 4.5 Discussion on the results

Beyond the numerical lower bounds obtained on the chromatic numbers of several graphs, our results can be analyzed through several different points of view. First, Theorem 4.6 shows how the reformulation in terms on Chebyshev polynomials may lead to simple analytic computations of the spectral bound for discrete graphs, already computed in [DSMMV19] without any polynomial reformulation. Then, this allowed us to compute estimations on the spectral bound for other infinite graphs that were so far studied only with different, mostly combinatorial, tools. Table 9 shows a comparison between our approach and previous results.
<table><caption>Table 9: We compare the previous lower bounds on $\chi_m(V, S)$ and our estimates on the spectral bounds ($V$ vertices, $S$ avoided set). The symbol $\dagger$ means that the lower bound gives the chromatic number of the graph.</caption><thead><tr><th>V</th><th>S</th><th>Previous lower bound for &chi;<sub>m</sub>(V, S)</th><th>Spectral bound</th></tr></thead><tbody><tr><td>Z<sup>n</sup></td><td>B<sup>1</sup><sub>2r+1</sub> (discrete crosspolytope)</td><td>2<sup>&dagger;</sup> [FK04]</td><td>2 [Proposition 4.10]</td></tr><tr><td>Z<sup>n</sup></td><td>B<sup>1</sup><sub>2</sub></td><td>2n<sup>&dagger;</sup> [FK04]</td><td>2n [Theorem 4.11]</td></tr><tr><td>Z<sup>2</sup></td><td>B<sup>1</sup><sub>2r</sub></td><td>4<sup>&dagger;</sup> [FK04]</td><td>4 [Corollary 4.12]</td></tr><tr><td>Z<sup>3</sup></td><td>B<sup>1</sup><sub>4</sub></td><td>7 [FK04]</td><td>&gt; 6.30 [Table 3]</td></tr><tr><td>Z<sup>4</sup></td><td>B<sup>1</sup><sub>4</sub></td><td>9 [FK04]</td><td>&gt; 10.86 [Table 4]</td></tr><tr><td>R<sup>2</sup></td><td>hexagon</td><td>4<sup>&dagger;</sup> [BBMP19]</td><td>&gt; 3.57 [Table 5]</td></tr><tr><td>R<sup>3</sup></td><td>rhombic dodecahedron</td><td>8<sup>&dagger;</sup> [BBMP19]</td><td>&gt; 6.10 [Table 6]</td></tr><tr><td>R<sup>4</sup></td><td>icositetrachoron</td><td>15 [BBMP19]</td><td>&gt; 10.02 [Table 7]</td></tr><tr><td>R<sup>n</sup></td><td>hypercube</td><td>2<sup>n&dagger;</sup> [BBMP19]</td><td>2<sup>n</sup> [Proposition 4.17]</td></tr></tbody></table>

In the case of the discrete graph $Z^n$ with the $\ell_1$-norm, on the one hand we could show that for the few cases in which the chromatic number was exactly computed, the spectral bound is sharp, namely it gives the chromatic number. One the other hand, while in $Z^3$ we recover the lower bound 7 by rounding up our bound 6.3 to the next integer, we are able to improve the best known lower bound for $Z^4$. For the last set of results about $\mathbb{R}^n$ endowed with norms coming from Voronoi cells of lattices, except for the case of the hypercube, the numbers we obtain might look far from the expected chromatic number of $\mathbb{R}^n$. This might happen for several reasons. First, when considering our discrete measures supported on lattices, we are always implicitly computing a bound for a discrete subgraph of $\mathbb{R}^n$, that might have a chromatic number smaller than $\mathbb{R}^n$. However, this is not the only reason: in the case of the hexagon, the measure supported on the vertices and the middles of edges we consider gives a bound for a discrete graph. However, it was proven in [BBMP19] that this graph has chromatic number 4. In this case, it is likely that the spectral bound is exactly 25/7, and does not give the chromatic number. Such a phenomenon was already observed in [DSMMV19], where, for the lattice $E_7$, the optimal spectral bound was computed to be 10, while the chromatic number of this lattice is 14.

Since we do not know a priori how large is the gap between the spectral bound and the actual chromatic number, it is interesting to understand better the behavior of the spectral bound for such graphs in itself. In this direction, in addition to provide bounds on the chromatic number of the graphs that we consider, our method gives information on the discrete measures supported on lattice points up to scaling. For example, in the case of the hexagon, even by increasing the number of support points, we did not get a discrete measure providing a better bound, see Table 5. Our experiments then suggest that the optimal measure supported on rational points is the one supported by two orbits: the vertices of the hexagon, with weight 1/3, and the middle of the edges, with weight 2/3. In the case of the cross-polytope from Section 4.3, we observe a different phenomenon: when increasing the number of possible support points, the optimal measure distribution does not appear to stabilize. It seems then reasonable to expect the bound to get better when increasing the number of points, even though it is hard to conjecture for an optimal discrete measure after our experiments, see Figure 11. Moreover, we note that the larger the set of possible support points is, the higher we need to go in the order of the hierarchy to get a good bound. This can be explained by the fact that the weighted degrees of the involved Chebyshev polynomials get higher, making the semi-definite programs harder to solve.

Finally, let us mention that we only provide in the tables the numerical results from the solver. In general, since SDP solvers work with floating point numbers, the solution observed might only be an approximation of a feasible solution, and one need further work to certify a rigorous bound. This can be done for instance by using interval arithmetics (see for example [DGFV17]), or general procedures to round numerical solutions to rational solutions (see the introduction of [DLM21]). However, in our situation, if we are only interested in bounding chromatic numbers that are integers, we are less sensitive to numerical precision. On the other
hand, when we prove that the spectral bound is sharp, we could do it analytically. Another approach that
can be interesting consists in the combination of both methods, like in Section 4.4.1: numerical computations
help us to guess a good weight distribution for the measure, and then we can compute the corresponding
bound analytically. However, unfortunately, for the other examples, computations did not suggest obvious
optimal measures.

Conclusion

We give an algorithm to minimize a trigonometric polynomial with crystallographic symmetry. To do so, we rewrite the problem in terms of generalized Chebyshev polynomials and use established techniques from polynomial optimization with matrix inequalities. This results in a hierarchy of SDPs, similar to Lasserre's hierarchy but with Chebyshev moments and matrix sums of squares. We provide a MAPLE package that supports the examples and symbolic computations (https://github.com/TobiasMetzlaff/GeneralizedChebyshev). For the chromatic number of set avoiding graphs, we present a hierarchy of semi-definite lower bounds that originates from a bilevel polynomial optimization problem. For such problems, it would be interesting to compute the spectral bound for continuous measures supported on the boundary of our polytopes, to conclude whether such an approach could be at least as powerful as the combinatorial approach. Improving the implementation would allow at some point to handle the famous $E_8$ lattice.

Acknowledgments

We want to thank Christine Bachoc (Université de Bordeaux), since the idea of computing the spectral
bound for polytope-distance graphs through polynomial optimization was initiated by her, in discussion
with Philippe Moustrou.

The authors are also grateful to Michal Kocvara (University of Birmingham), Milan Korda, Victor Magron (CNRS LAAS Toulouse) and Bernard Mourrain (Inria d'Université Côte d'Azur) for fruitful suggestions and discussions.

The majority of the work of Tobias Metzlaff was carried out during his doctoral studies [Met22] at Inria d'Université Côte d'Azur, supported by European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Actions, grant agreement 813211 (POEMA). Minor revisions and changes were applied during his postdoctoral research at the University of Kaiserslautern-Landau, supported by the Deutsche Forschungsgemeinschaft transregional collaborative research centre (SFB-TRR) 195 “Symbolic Tools in Mathematics and their Application”.

References

[ACM+22] G. Ambrus, A. Csiszárik, M. Matolcsi, D. Varga, and P. Zsámboki. The density of planar sets avoiding unit distances. *Preprint* https://arxiv.org/abs/2207.14179, 2022.

[AM22] G. Ambrus and M. Matolcsi. Density estimates of 1-avoiding sets via higher order correlations. *Discrete Comput. Geom.*, 67(4):1245–1256, 2022.

[BBMP19] C. Bachoc, T. Bellitto, P. Moustrou, and A. Pêcher. On the Density of Sets avoiding Parallelephedron distance 1. *Discret. Comput. Geom.*, 62(3):497–524, 2019.

[BDFV14] C. Bachoc, E. DeCorte, F. de Oliveira Filho, and F. Vallentin. Spectral bounds for the independence ratio and the chromatic number of an operator. *Israel Journal of Mathematics*, 202(1):227–254, 2014.
[Bee91] R. Beerends. Chebyshev polynomials in several variables and the radial part of the Laplace-Beltrami operator. *Transactions of the American Mathematical Society*, 328(2):779-814, 1991.

[BF23] L. Bétermin and M. Faulhuber. Maximal theta functions universal optimality of the hexagonal lattice for madelung-like lattice energies. *Journal d'Analyse Mathématique*, 2023.

[Bou68] N. Bourbaki. *Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Titres. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines*. Actualités Scientifiques et Industrielles, No. 1337. Hermann, Paris, 1968.

[BPR06] S. Basu, R. Pollack, and M.-F. Roy. *Algorithms in Real Algebraic Geometry*. Algorithms and Computation in Mathematics. Springer, Berlin, Heidelberg, 2006.

[BPS21] T. Bellitto, A. Pêcher, and A. Sédillot. On the density of sets of the Euclidean plane avoiding distance 1. *Discrete Mathematics & Theoretical Computer Science*, 23(1):8-13, 2021.

[BPT12] G. Blekherman, P. Parrilo, and R. Thomas. *Semidefinite Optimization and Convex Algebraic Geometry*. MOS-SIAM Series on Optimization. SIAM, Philadelphia, PA, 2012.

[BPT15] C. Bachoc, A. Passuello, and A. Thiery. The density of sets avoiding distance 1 in Euclidean space. *Discrete Comput. Geom.*, 53(4):783-808, 2015.

[BR23] F. Bach and A. Rudi. Exponential convergence of sum-of-squares hierarchies for trigonometric polynomials. *SIAM Journal on Optimization*, 33(3):2137-2159, 2023.

[BV96] S. Boyd and L. Vandenberghe. Semidefinite Programming. *SIAM Review*, 38(1):49-95, 1996.

[CAPT22] D. Cifuentes, S. Agarwal, P. Parrilo, and R. Thomas. On the local stability of semidefinite relaxations. *Mathematical Programming*, 193(2):629-663, 2022.

[CKM$^{+}$22] H. Cohn, A. Kumar, S. Miller, D. Radchenko, and M. Viazovska. Universal optimality of the E8 and Leech lattices and interpolation formulas. *Annals of Mathematics*, 196(3):983-1082, 2022.

[CKW20] A. Choudhary, S. Kachanovich, and M. Wintraecken. Coxeter triangulations have good quality. *Mathematics in Computer Science*, 14:141-176, 2020.

[CS99] J. Conway and N. Sloane. *Sphere packings, lattices and groups*, volume 290 of *Grundlehren der Mathematischen Wissenschaften*. Springer-Verlag, New York, third edition, 1999.

[DGFV17] M. Dostert, C. Guzman, F. de Oliveira Filho, and F. Vallentin. New upper bounds for the density of translative packings of three-dimensional convex bodies with tetrahedral symmetry. *Discret. Comput. Geom.*, 58(2):S. 449-482, 2017.

[DL80] K. Dunn and R. Lidl. Multi-dimensional generalizations of the Chebyshev polynomials, I, II. *Proc. Japan Acad.*, 56:154-165, 1980.

[DLM21] M. Dostert, D. de Laat, and P. Moustrou. Exact semidefinite programming bounds for packing problems. *SIAM Journal on Optimization*, 31(2):1433-1458, 2021.

[DSMMV19] M. Dutour Sikirić, D. Madore, P. Moustrou, and F. Vallentin. Coloring the Voronoi tessellation of lattices. *Journal of the London Mathematical Society*, 2019.

[Dum07] B. Dumitrescu. *Positive Trigonometric Polynomials and Signal Processing Applications*. Signals and Communication Technology. Springer Netherlands, 2007.
[EL82] R. Eier and R. Lidl. A class of orthogonal polynomials in $k$ variables. *Mathematische Annalen*, 260:93–100, 1982.

[Far86] D. Farkas. Reflection groups and multiplicative invariants. *Rocky Mountain Journal of Mathematics*, 16:215–222, 1986.

[FK04] Z. Fürredi and J.-H. Kang. Distance graph on $\mathbb{Z}^n$ with $\ell_1$ norm. *Theoretical Computer Science*, 319:357–366, 2004.

[Gre18] A. de Grey. The chromatic number of the plane is at least 5. *Geombinatorics*, 28(1):18–31, 2018.

[HKL21] D. Henrion, M. Korda, and J.-B. Lasserre. *The Moment-SOS Hierarchy*. Series on Optimization and its Applications. Singapore: World Scientific, 2021.

[HL06] D. Henrion and J.-B. Lasserre. Convergent relaxations of polynomial matrix inequalities and static output feedback. *IEEE Transactions on Automatic Control*, 51(2):192–202, 2006.

[HMR24] E. Hubert, T. Metzlaff, and C. Riener. Orbit spaces of Weyl groups acting on compact tori: a unified and explicit polynomial description. To appear in *SIAM Journal on Applied Algebra and Geometry*, 2024.

[Hof70] A. Hoffman. On eigenvalues and colorings of graphs. In *Graph Theory and its Applications*, Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., pages 79–91. Academic Press, New York, 1970.

[HS05] C. Hol and C. Scherer. Sum of squares relaxations for robust polynomial semi-definite programs. *IFAC Proceedings Volumes*, 38(1):451–456, 2005.

[HS06] C. Hol and C. Scherer. Matrix Sum-of-Squares Relaxations for Robust Semi-Definite Programs. *Mathematical Programming*, 107(1):189–211, 2006.

[Hum72] J. Humphreys. *Introduction to Lie Algebras and Representation Theory*. Graduate Texts in Mathematics. Springer, New York, NY, 1972.

[HW88] M. Hoffman and W. Withers. Generalized Chebyshev polynomials associated with affine Weyl groups. *Transactions of the American Mathematical Society*, 308(1):91–104, 1988.

[JM18] C. Josz and D. Molzahn. Lasserre hierarchy for large scale polynomial optimization in real and complex variables. *SIAM Journal of Optimization*, 28(2):1017–1048, 2018.

[KAH05] H. Künsch, E. Agrell, and F. Hamprecht. Optimal lattices for sampling. *IEEE Transactions on Information Theory*, 51(2):634–647, 2005.

[Kan01] R. Kane. *Reflection Groups and Invariant Theory*. CMS Books in Mathematics. Springer, New York, NY, 2001.

[KdK23] F. Kirschner and E. de Klerk. Construction of multivariate polynomial approximation kernels via semidefinite programming. *SIAM Journal on Optimization*, 33(2):513–537, 2023.

[KLP05] E. de Klerk, M. Laurent, and P. Parrilo. On the equivalence of algebraic approaches to the minimization of forms on the simplex. In *Positive Polynomials in Control*, pages 121–132. Springer, Berlin, Heidelberg, 2005.

[Las01] J.-B. Lasserre. Global Optimization with Polynomials and the Problem of Moments. *SIAM Journal of Optimization*, 11(3):796–817, 2001.
[Las06] J.-B. Lasserre. Convergent sdp-relaxations in polynomial optimization with sparsity. *SIAM Journal on Optimization*, 17(3):822–843, 2006.

[Las09] J.-B. Lasserre. *Moments, Positive Polynomials and Their Applications*. Series on Optimization and its Applications. Imperial College Press, 2009.

[Lau09] M. Laurent. Sums of Squares, Moment Matrices and Optimization Over Polynomials. In *Emerging Applications of Algebraic Geometry*, pages 157–270. Springer, New York, NY, 2009.

[Lor05] M. Lorenz. *Multiplicative Invariant Theory*. Encyclopaedia of Mathematical Sciences. Springer, Berlin, Heidelberg, 2005.

[Lov79] L. Lovász. On the Shannon capacity of a graph. *IEEE Trans. Inform. Theory*, 25(1):1–7, 1979.

[LX10] H. Li and Y. Xu. Discrete Fourier analysis on fundamental domain and simplex of $A_d$ lattice in $d$ variables. *The Journal of Fourier Analysis and Applications*, 16(3):383–433, 2010.

[Mac90] I. MacDonald. Orthogonal polynomials associated with root systems. In *Orthogonal Polynomials: Theory and Practice*, volume 294 of NATO ASI Series, pages 311–318. Springer, Netherlands, Dordrecht, 1990.

[Met22] T. Metzlaff. *Groupes Cristallographiques et Polynômes de Chebyshev en Optimisation Globale*. Thèse de doctorat en Mathématiques d'Université Côte d'Azur: https://www.theses.fr/2022COAZ4094, 2022.

[Met23] Tobias Metzlaff. On symmetry adapted bases in trigonometric optimization. Preprint: https://hal.science/hal-04236200, 2023.

[MP11] R. Moody and J. Patera. Cubature formulae for orthogonal polynomials in terms of elements of finite order of compact simple Lie groups. *Advances in Applied Mathematics*, 47:509–535, 2011.

[Par03] P. Parrilo. Semidefinite programming relaxations for semialgebraic problems. *Mathematical Programming*, 96(2):293–320, 2003.

[PPSP05] S. Prajna, A. Papachristodoulou, P. Seiler, and P. Parrilo. SOSTOOLS and its control applications. In *Positive Polynomials in Control*, pages 273–292. Springer, Berlin, Heidelberg, 2005.

[PS85] C. Procesi and G. Schwarz. Inequalities defining orbit spaces. *Inventiones mathematicae*, 81:539–554, 1985.

[PS03] P. Parrilo and B. Sturmfels. Minimizing polynomial functions. In *Series in discrete mathematics and theoretical computer science*, volume 60, pages 83–99. AMS, Providence, R.I., 2003.

[PS20] M. Petrache and S. Serfaty. Crystallization for coulomb and riesz interactions as a consequence of the cohn-kumar conjecture. *Proceedings of the AMS*, 148(7):3047–3057, 2020.

[Put93] M. Putinar. Positive polynomials on compact semi-algebraic sets. *Indiana University Mathematics Journal*, 42(3):969–984, 1993.

[Soi09] A. Soifer. *The mathematical coloring book*. Springer, New York, 2009. Mathematics of coloring and the colorful life of its creators.

[Via17] M. Viazovska. The sphere packing problem in dimension 8. *Annals of Mathematics*, 185(3):991–1015, 2017.
# A Irreducible root systems of type $A_{n-1}$, $C_n$, $B_n$, $D_n$, $G_2$

For $1 \le i \le n$, we denote by $e_i \in \mathbb{R}^n$ the Euclidean standard basis vectors.

## $A_{n-1}$ [Bou68, Planche I]

The group $\mathfrak{S}_n$ acts on $\mathbb{R}^n$ by permutation of coordinates and leaves the subspace $V = \mathbb{R}^n/\langle[1, \dots, 1]^t\rangle = \{u \in \mathbb{R}^n | u_1 + \dots + u_n = 0\}$ invariant. The root system $A_{n-1}$ given in [Bou68, Planche I] is a root system of rank $n-1$ in $V$ with base and fundamental weights

$$ \rho_i = e_i - e_{i+1} \quad \text{and} \quad \omega_i = \sum_{j=1}^{i} e_j - \frac{i}{n} \sum_{j=1}^{n} e_j = \frac{1}{n} \underbrace{[n-i, \dots, n-i]}_{i \text{ times}} - \underbrace{-i, \dots, -i]}_{n-i \text{ times}}^t. \quad (A) $$

The Weyl group of $A_{n-1}$ is $W \cong \mathfrak{S}_n$ and the reflection $s_{\rho_i}$ permutes the coordinates $i$ and $i+1$. Thus, $-\omega_{n-i} \in W\omega_i$ and the orbit $W\omega_i$ has cardinality $\binom{n}{i}$ for $1 \le i \le n-1$.

## $C_n$ [Bou68, Planche III]

The groups $\mathfrak{S}_n$ and $\{\pm 1\}^n$ act on $\mathbb{R}^n$ by permutation of coordinates and multiplication of coordinates by $\pm 1$. The root system $C_n$ given in [Bou68, Planche III] is a root system in $\mathbb{R}^n$ with base and fundamental weights

$$ \rho_i = e_i - e_{i+1}, \quad \rho_n = 2e_n \quad \text{and} \quad \omega_i = e_1 + \dots + e_i. \quad (C) $$

The Weyl group of $C_n$ is $W \cong \mathfrak{S}_n \times \{\pm 1\}^n$. We have $-I_n \in W$ and thus, $-\omega_i \in W\omega_i$. Furthermore, the orbit $W\omega_i$ has cardinality $2^i \binom{n}{i}$ for $1 \le i \le n$.

## $B_n$ [Bou68, Planche II]

The root system $B_n$ given in [Bou68, Planche II] is a root system in $\mathbb{R}^n$. Its Weyl group is isomorphic to that of $C_n$. The base and fundamental weights are

$$ \rho_i = e_i - e_{i+1}, \quad \rho_n = e_n \quad \text{and} \quad \omega_i = e_1 + \dots + e_i, \quad \omega_n = (e_1 + \dots + e_n)/2. \quad (B) $$

The Weyl group of $B_n$ is that of $C_n$, that is, $W \cong \mathfrak{S}_n \times \{\pm 1\}^n$. We have $-I_n \in W$ and thus, $-\omega_i \in W\omega_i$. Furthermore, the orbit $W\omega_i$ has cardinality $2^i \binom{n}{i}$ for $1 \le i \le n$.

## $D_n$ [Bou68, Planche IV]

The groups $\mathfrak{S}_n$ and $\{\pm 1\}_+^n := \{\epsilon \in \{\pm 1\}^n | \epsilon_1 \dots \epsilon_n = 1\}$ act on $\mathbb{R}^n$ by permutation of coordinates and multiplication of coordinates by $\pm 1$, where only an even amount of sign changes is admissible. The root system $D_n$ given in [Bou68, Planche IV] is a root system in $\mathbb{R}^n$ with base and fundamental weights

$$ \rho_i = e_i - e_{i+1}, \quad \rho_n = e_{n-1} + e_n \quad \text{and} \\ \omega_i = e_1 + \dots + e_i, \quad \omega_{n-1} = (e_1 + \dots + e_{n-1} - e_n)/2, \quad \omega_n = (e_1 + \dots + e_n)/2. \quad (D) $$

The Weyl group of $D_n$ is $W \cong \mathfrak{S}_n \times \{\pm 1\}_+^n$. For all $1 \le i \le n$, we have $-\omega_i \in W\omega_i$, except when $n$ is odd, where $-\omega_{n-1} \in W\omega_n$. Furthermore, the orbit $W\omega_i$ has cardinality $2^i \binom{n}{i}$ for $1 \le i \le n-2$ and $|W\omega_{n-1}| = |W\omega_n| = 2^{n-1}$.

## $G_2$ [Bou68, Planche IX]

The group $\mathfrak{S}_3 \times \{\pm 1\}$ acts on $\mathbb{R}^3$ by permutation of coordinates and scalar multiplication with $\pm 1$. The subspace $V = \mathbb{R}^3/\langle[1, 1, 1]^t\rangle = \{u \in \mathbb{R}^3 | u_1 + u_2 + u_3 = 0\}$ is left invariant. The root system $G_2$ given in [Bou68, Planche IX] is a root system of rank 2 in $V$ with base and fundamental weights

$$ \rho_1 = [1, -1, 0]^t, \quad \rho_2 = [-2, 1, 1]^t \quad \text{and} \quad \omega_1 = [1, -1, 0]^t, \quad \omega_2 = [-2, 1, 1]^t. \quad (G) $$

The Weyl group of $G_2$ is $W \cong \mathfrak{S}_3 \times \{\pm 1\}$. We have $-I_3 \in W$ and thus, $-\omega_1 \in W\omega_1$ as well as $-\omega_2 \in W\omega_2$. Furthermore, $|W\omega_1| = |W\omega_2| = 6$.
B Coefficients for discrete measures

<table><caption>Table 10: The coefficient for the obtained bounds.</caption><thead><tr><th rowspan="2">r</th><th colspan="3">G<sub>2</sub> (Figure 14)</th><th colspan="3">B<sub>3</sub> (Figure 17)</th><th colspan="3">B<sub>3</sub> (Figure 11)</th></tr><tr><th>1-1/F(r,9)</th><th>c<sub>α</sub></th><th>1-1/F(r,9)</th><th>c<sub>α</sub></th><th>1-1/F(r,9)</th><th>c<sub>α</sub></th><th>1-1/F(r,9)</th><th>c<sub>α</sub></th><th>1-1/F(r,9)</th></tr></thead><tbody><tr><td rowspan="3">2</td><td rowspan="3">3.5714293935747494</td><td>c<sub>01</sub> = 0.6666662750776622</td><td rowspan="3">6.10767134833497</td><td>c<sub>010</sub> = 0.5927896822441022</td><td rowspan="3">6.000001702602425</td><td>c<sub>010</sub> = 0.79999985332756</td><td rowspan="3">0.00000000682364782</td><td>c<sub>010</sub> = 0.79999985332756</td><td rowspan="3">0.00000000682364782</td></tr><tr><td>c<sub>020</sub> = 0.3333337066934456</td><td>c<sub>002</sub> = 0.06049713057719272</td><td>c<sub>010</sub> = 0.2438838152316104</td><td>c<sub>020</sub> = 0.20000000682364782</td></tr><tr><td></td><td>c<sub>040</sub> = 0.33333143067593424</td><td>c<sub>020</sub> = 0.10282935835880404</td><td>c<sub>020</sub> = 0.5927767228148009</td><td>c<sub>020</sub> = 0.16188833861440459</td><td>c<sub>020</sub> = 0.22680579314997618</td><td>c<sub>020</sub> = 0.017538297901656945</td></tr><tr><td rowspan="6">4</td><td rowspan="6">3.571429076541122</td><td>c<sub>021</sub> = 0.6666630238845522</td><td rowspan="6">6.107671578689443</td><td>c<sub>012</sub> = 1.1060691764569475e-07</td><td rowspan="6">6.281482112640609</td><td>c<sub>012</sub> = 0.5937675654811545</td><td rowspan="6">0.00000000682364782</td><td>c<sub>012</sub> = 0.5937675654811545</td><td rowspan="6">0.00000000682364782</td></tr><tr><td>c<sub>013</sub> = 5.533750816723066e-06</td><td>c<sub>011</sub> = 3.8973084159378557e-07</td><td>c<sub>011</sub> = 0.2072346714731282e-08</td><td>c<sub>010</sub> = 0.1561352016875235</td><td>c<sub>010</sub> = 0.2072346714731282e-08</td></tr><tr><td>c<sub>040</sub> = 0.33333143067593424</td><td>c<sub>022</sub> = 0.46761370259674e-08</td><td>c<sub>020</sub> = 0.359381080996721e-08</td><td>c<sub>020</sub> = 0.064373753036916</td><td>c<sub>020</sub> = 0.064373753036916</td></tr><tr><td></td><td>c<sub>013</sub> = 5.812486718152765e-08</td><td>c<sub>011</sub> = 2.3184776079239813e-08</td><td>c<sub>011</sub> = 1.4463186537305717e-08</td><td>c<sub>010</sub> = 0.18314795448892407</td><td>c<sub>010</sub> = 3.493798257127312e-07</td></tr><tr><td>c<sub>020</sub> = 0.2439027053567078</td><td>c<sub>022</sub> = 0.2680579314997618</td><td>c<sub>020</sub> = 0.2439027053567078</td><td>c<sub>020</sub> = 0.2439027053567078</td><td>c<sub>020</sub> = 0.2439027053567078</td><td>c<sub>020</sub> = 0.2439027053567078</td></tr><tr><td>c<sub>040</sub> = 1.123715533847226e-07</td><td>c<sub>020</sub> = 0.3487920151002896e-08</td><td>c<sub>020</sub> = 0.10282351530819676</td><td>c<sub>020</sub> = 0.3487920151002896e-08</td><td>c<sub>020</sub> = 0.10282351530819676</td><td>c<sub>020</sub> = 0.3487920151002896e-08</td></tr><tr><td rowspan="6">6</td><td rowspan="6">3.571428681101453</td><td>c<sub>031</sub> = 0.6666623416514681</td><td rowspan="6">6.107669002121958</td><td>c<sub>030</sub> = 0.59277786698957568</td><td rowspan="6">6.302692297425513</td><td>c<sub>030</sub> = 0.0949148422912926</td><td rowspan="6">0.00000000682364782</td><td>c<sub>030</sub> = 0.0949148422912926</td><td rowspan="6">0.00000000682364782</td></tr><tr><td>c<sub>032</sub> = 4.988015651434592e-06</td><td>c<sub>031</sub> = 6.061390472114625e-07</td><td>c<sub>031</sub> = 1.5014281939041977</td><td>c<sub>031</sub> = 0.24975682950947593</td><td>c<sub>031</sub> = 0.24975682950947593</td></tr><tr><td>c<sub>041</sub> = 5.706892501421417e-07</td><td>c<sub>032</sub> = 1.8206124414166247e-06</td><td>c<sub>030</sub> = 0.1561352016875235</td><td>c<sub>030</sub> = 0.1561352016875235</td><td>c<sub>030</sub> = 0.1561352016875235</td></tr><tr><td>c<sub>060</sub> = 0.3333320956275223</td><td>c<sub>032</sub> = 4.46761370259674e-08</td><td>c<sub>030</sub> = 0.359381080996721e-08</td><td>c<sub>030</sub> = 0.2439027053567078</td><td>c<sub>030</sub> = 0.2439027053567078</td><td>c<sub>030</sub> = 0.2439027053567078</td></tr><tr><td></td><td>c<sub>031</sub> = 5.812486718152765e-08</td><td>c<sub>032</sub> = 2.490367430203645e-07</td><td>c<sub>030</sub> = 0.102824343292709068</td><td>c<sub>030</sub> = 0.102824343292709068</td><td>c<sub>030</sub> = 0.102824343292709068</td></tr><tr><td>c<sub>040</sub> = 0.33333288627491457</td><td>c<sub>032</sub> = 3.3861885617269103e-06</td><td>c<sub>030</sub> = 0.5927413721445046</td><td>c<sub>030</sub> = 0.1342204654583938</td><td>c<sub>030</sub> = 0.1342204654583938</td><td>c<sub>030</sub> = 0.1342204654583938</td></tr><tr><td rowspan="6">8</td><td rowspan="6">3.571428656208869</td><td>c<sub>031</sub> = 0.6666503161482014</td><td rowspan="6">6.10766554179269</td><td>c<sub>031</sub> = 1.546207606818728e-05</td><td rowspan="6">6.305009836734212</td><td>c<sub>031</sub> = 0.19985959349100152</td><td rowspan="6">0.00000000682364782</td><td>c<sub>031</sub> = 0.19985959349100152</td><td rowspan="6">0.00000000682364782</td></tr><tr><td>c<sub>032</sub> = 1.51476518386996e-05</td><td>c<sub>031</sub> = 2.404130958217336e-05</td><td>c<sub>031</sub> = 0.24975682950947593</td><td>c<sub>031</sub> = 0.24975682950947593</td></tr><tr><td>c<sub>041</sub> = 3.33861885617269103e-06</td><td>c<sub>032</sub> = 6.319418130873309e-07</td><td>c<sub>030</sub> = 5.427029152509193e-07</td><td>c<sub>030</sub> = 5.427029152509193e-07</td></tr><tr><td>c<sub>060</sub> = 2.3138911862176023e-06</td><td>c<sub>032</sub> = 3.806799155209317e-07</td><td>c<sub>030</sub> = 4.508418519007733e-07</td><td>c<sub>030</sub> = 4.508418519007733e-07</td></tr><tr><td>c<sub>080</sub> = 0.33333288627491457</td><td>c<sub>032</sub> = 7.3604951230706e-07</td><td>c<sub>030</sub> = 0.114505759562393</td><td>c<sub>030</sub> = 0.114505759562393</td><td>c<sub>030</sub> = 0.114505759562393</td><td>c<sub>030</sub> = 0.114505759562393</td></tr><tr><td>c<sub>080</sub> = 0.102824343292709068</td><td>c<sub>032</sub> = 2.490367430203645e-07</td><td>c<sub>030</sub> = 0.11294210248506e-06</td><td>c<sub>030</sub> = 0.11294210248506e-06</td><td>c<sub>030</sub> = 0.11294210248506e-06</td><td>c<sub>030</sub> = 0.11294210248506e-06</td></tr><tr><td rowspan="10">10</td><td rowspan="10">3.5714286753163695</td><td>c<sub>031</sub> = 0.6666580152642103</td><td rowspan="10">6.107665208855795</td><td>c<sub>031</sub> = 0.592756438632703</td><td rowspan="10">6.305020412263947</td><td>c<sub>031</sub> = 0.0831684631973757</td><td rowspan="10">0.00000000682364782</td><td>c<sub>031</sub> = 0.0831684631973757</td><td rowspan="10">0.00000000682364782</td></tr><tr><td>c<sub>032</sub> = 6.815116335719704e-06</td><td>c<sub>031</sub> = 9.682801118376587e-06</td><td>c<sub>030</sub> = 0.045246108638332825</td><td>c<sub>030</sub> = 0.045246108638332825</td></tr><tr><td>c<sub>041</sub> = 2.193358658091023e-06</td><td>c<sub>032</sub> = 1.670078365629944e-05</td><td>c<sub>030</sub> = 0.34658821329785183</td><td>c<sub>030</sub> = 0.34658821329785183</td></tr><tr><td>c<sub>060</sub> = 7.69026506808464e-07</td><td>c<sub>032</sub> = 5.255662733075187e-07</td><td>c<sub>030</sub> = 3.348605878933986e-06</td><td>c<sub>030</sub> = 3.348605878933986e-06</td></tr><tr><td>c<sub>080</sub> = 1.3120927502321667e-06</td><td>c<sub>032</sub> = 3.392005937306701e-07</td><td>c<sub>030</sub> = 0.10956846871243874</td><td>c<sub>030</sub> = 0.10956846871243874</td></tr><tr><td>c<sub>080</sub> = 0.333333809013330625</td><td>c<sub>032</sub> = 7.020019227642831e-07</td><td>c<sub>030</sub> = 4.560289153936601e-06</td><td>c<sub>030</sub> = 4.560289153936601e-06</td></tr><tr><td></td><td>c<sub>031</sub> = 2.0282710528401052e-07</td><td>c<sub>030</sub> = 2.440368075704186e-06</td><td>c<sub>030</sub> = 2.440368075704186e-06</td><td>c<sub>030</sub> = 2.440368075704186e-06</td><td>c<sub>030</sub> = 2.440368075704186e-06</td></tr><tr><td>c<sub>032</sub> = 1.063037501921022e-07</td><td>c<sub>030</sub> = 5.147654565169418e-07</td><td>c<sub>030</sub> = 2.8049515946132317e-06</td><td>c<sub>030</sub> = 2.8049515946132317e-06</td><td>c<sub>030</sub> = 2.8049515946132317e-06</td><td>c<sub>030</sub> = 2.8049515946132317e-06</td></tr><tr><td>c<sub>041</sub> = 2.487195823711977e-07</td><td>c<sub>032</sub> = 1.991925614776585e-07</td><td>c<sub>030</sub> = 0.1678758005767563</td><td>c<sub>030</sub> = 0.1678758005767563</td><td>c<sub>030</sub> = 0.1678758005767563</td><td>c<sub>030</sub> = 0.1678758005767563</td></tr><tr><td>c<sub>040</sub> = 3.09387568657081e-07</td><td>c<sub>032</sub> = 2.86603717316962e-07</td><td>c<sub>030</sub> = 0.0031493463678010778</td><td>c<sub>030</sub> = 0.0031493463678010778</td><td>c<sub>030</sub> = 0.0031493463678010778</td><td>c<sub>030</sub> = 0.0031493463678010778</td></tr><tr><td>c<sub>050</sub> = 1.3683747352043666e-07</td><td>c<sub>032</sub> = 2.56256891737368394e-07</td><td>c<sub>030</sub> = 0.06305418908391902</td><td>c<sub>030</sub> = 0.06305418908391902</td><td>c<sub>030</sub> = 0.06305418908391902</td><td>c<sub>030</sub> = 0.06305418908391902</td></tr><tr><td>c<sub>060</sub> = 8.73535186056843e-08</td><td>c<sub>032</sub> = 1.308190531621658e-07</td><td>c<sub>030</sub> = 0.118377651589988159</td><td>c<sub>030</sub> = 0.118377651589988159</td><td>c<sub>030</sub> = 0.118377651589988159</td><td>c<sub>030</sub> = 0.118377651589988159</td></tr><tr><td>c<sub>080</sub> = 7.739160553574774e-08</td><td>c<sub>032</sub> = 6.171409199298282e-08</td><td>c<sub>030</sub> = 0.06295198879060124</td><td>c<sub>030</sub> = 0.06295198879060124</td><td>c<sub>030</sub> = 0.06295198879060124</td><td>c<sub>030</sub> = 0.06295198879060124</td></tr><tr><td>c<sub>080</sub> = 0.0064786290429874</td><td>c<sub>032</sub> = 8.297185248986314e-06</td><td>c<sub>030</sub> = 6.009291152696872e-06</td><td>c<sub>030</sub> = 6.009291152696872e-06</td><td>c<sub>030</sub> = 6.009291152696872e-06</td><td>c<sub>030</sub> = 6.009291152696872e-06</td></tr><tr><td>c<sub>080</sub> = 2.1225449116373842e-06</td><td>c<sub>032</sub> = 5.4058402907554265e-06</td><td>c<sub>030</sub> = 1.4189605438770391e-05</td><td>c<sub>030</sub> = 1.4189605438770391e-05</td><td>c<sub>030</sub> = 1.4189605438770391e-05</td><td>c<sub>030</sub> = 1.4189605438770391e-05</td></tr><tr><td>c<sub>080</sub> = 4.1932268201038956e-07</td><td>c<sub>032</sub> = 3.421556035470313e-07</td><td>c<sub>030</sub> = 0.10282755980669979</td><td>c<sub>030</sub> = 0.10282755980669979</td><td>c<sub>030</sub> = 0.10282755980669979</td><td>c<sub>030</sub> = 0.10282755980669979</td></tr></tbody></table>