# On symmetry adapted bases in trigonometric optimization

Tobias Metzlaff

► To cite this version:

Tobias Metzlaff. On symmetry adapted bases in trigonometric optimization. Journal of Symbolic Computation, 2023, pp.102369. 10.1016/j.jsc.2024.102369. hal-04236200v2

HAL Id: hal-04236200

https://hal.science/hal-04236200v2

Submitted on 25 Jun 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>
# On symmetry adapted bases in trigonometric optimization

Tobias Metzlaff*

Tuesday 25th June, 2024

**Abstract**

The problem of computing the global minimum of a trigonometric polynomial is computationally hard. We address this problem for the case, where the polynomial is invariant under the exponential action of a finite group. The strategy is to follow an established relaxation strategy in order to obtain a converging hierarchy of lower bounds. Those bounds are obtained by numerically solving semi-definite programs (SDPs) on the cone of positive semi-definite Hermitian Toeplitz matrices, which is outlined in the book of Dumitrescu [Dum07]. To exploit the invariance, we show that the group has an induced action on the Toeplitz matrices and prove that the feasible region of the SDP can be restricted to the invariant matrices, whilst retaining the same solution. Then we construct a symmetry adapted basis tailored to this group action, which allows us to block-diagonalize invariant matrices and thus reduce the computational complexity to solve the SDP.

The approach is in its generality novel for trigonometric optimization and complements the one that was proposed as a poster at the ISSAC 2022 conference [HMMR22] and later extended to [HMMR24]. In the previous work, we first used the invariance of the trigonometric polynomial to obtain a classical polynomial optimization problem on the orbit space and subsequently relaxed the problem to an SDP. Now, we first make the relaxation and then exploit invariance.

Partial results of this article have been presented as a poster at the ISSAC 2023 conference [Met23].

**Keywords:** Trigonometric Optimization, Sums of Squares, Lattices, Finite Groups, Symmetry

**MSC:** 13A50 33B10 90C23

<footnote>*Department of Mathematics, University of Kaiserslautern–Landau, 67663 Kaiserslautern, Germany
tobias.metzlaff@rptu.de</footnote>
# Contents

1 Introduction 3

2 Trigonometric polynomials with crystallographic symmetry 4

2.1 Periodicity domain 4

2.2 Degree concept 5

2.3 Toeplitz matrix representations 6

2.4 Group symmetry 6

2.5 Symmetry adapted bases 7

3 Optimization 7

3.1 Sums of squares 8

3.2 Symmetry reduction 8

4 Computing symmetry adapted bases 10

4.1 Projection onto isotopic components 10

4.2 Computing the basis 11

4.3 Example 11

A Lattices and Weyl groups associated to crystallographic root systems 19
# 1 Introduction

We present a sums-of-squares-based algorithm to minimize a multivariate trigonometric polynomial under symmetry assumptions, which reduces computational complexity whilst preserving numerical accuracy and convergence rate. The algorithm allows exploitation of symmetry with respect to any finite group that acts on a lattice.

Trigonometric polynomials are good $L^2$-approximations for real-valued, periodic functions [MKNR13]. Minimizing a trigonometric polynomial is a problem that arises, for example, in filter design [Dum07], computation of spectral bounds [BDFV14], and optimal power flow [BWFW08, JM18].

Compared to classical polynomials, trigonometric ones are associated to a lattice. This makes them relevant for a variety of problems in geometry and information theory, with incidence in physics and chemistry, where lattices often provide optimal configurations. For example, 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, such lattices describe Gaussian cubature [LX10, MP11], a rare occurrence on multidimensional domains, and are relevant in graphics and computational geometry, see for instance [CKW20] and references therein.

The distinguishing feature of the above lattices is their intrinsic symmetry. The latter is given by the action of a finite group on the lattice, which induces a linear action on trigonometric polynomials. For the goal of trigonometric optimization, it is this feature that is emphasized and exploited in an optimization context.

Computing the global minimum of a polynomial is algorithmically hard and can be achieved numerically with an algorithm based on sums-of-squares reinforcements [Dum07, JM18]. The convergence rate of this approach for trigonometric polynomials was recently shown to be exponential [BR23].

The approach is summarized as follows. One restricts to suitable finite subsets $\Omega_d \subseteq \Omega_{d+1} \subseteq \dots \subseteq \Omega$ of the lattice, to obtain a degree bound. Then a lower bound for the minimum of a trigonometric polynomial $f$ is obtained by computing the maximal $r \in \mathbb{R}$, such that $f-r$ is a Hermitian sum of squares, where the summands are bounded in the degree. This means, that $f-r$ can be represented as a positive semi-definite Hermitian Toeplitz matrix so that the problem of computing $r$ becomes a semi-definite program (SDP). By increasing the parameter $d$, that is, the degree bound, one improves the quality of the approximation, but the problem becomes more and more costly to solve.

It is at this point, where we exploit symmetry. If the objective function is invariant under the action of a finite group, then the Hermitian matrices in the SDP can be block diagonalized according to a symmetry adapted basis. This reduces the number of variables of the SDP significantly and thus reduces required memory for storing and computational effort for solving the problem.

The main tool in this article, the symmetry adapted basis, is computed by decomposing a representation that corresponds to the finite subset $\Omega_d$ into isotypic components [Ser77]. The fact that one can do so is widely used in several areas, such as combinatorics [Sta79, Ber09], optimization [GP04, Val09, ALRT13], approximation [KdK23], interpolation [RBH21, RBH22b], dynamical systems [Gat00, HL13], polynomial systems [Gat90, FR09], computational invariant theory [HL16, RBH22a], as well as their fields of application [FS92]. It was exploited for the special case of the symmetric group in [KdK23] and is here extended to finite groups acting on lattices.

An alternative approach to exploiting symmetry in trigonometric optimization was explored by Hubert, Moustrou, Riener and the author in [HMMR22, HMMR24] and the thesis [Met22]. The idea there was to rewrite an invariant trigonometric polynomial to a classical one and then use relaxation tools from polynomial optimization [Las01, Par03]. The present paper complements this work in the sense that we first rewrite the problem to a semi-definite program and then exploit symmetry. One goal is to provide a framework for a fair comparison between polynomial and Hermitian sums of squares. This completes a recently presented poster at the ISSAC 2023 conference [Met23].

Next to symmetry, one can also exploit sparsity in the optimization of complex polynomials at a cost of numerical accuracy and convergence, see [WM22, LFF$^{+20}$, WSKM23]. A further step towards improved computational efficiency would be to exploit both sparsity and symmetry.

The article is structured as follows: In Section 2, we define trigonometric polynomials and the associated concepts
of periodicity and degree. We recall how to rewrite a trigonometric polynomial in terms of a Hermitian Toeplitz matrix. The first novelty is to construct a representation of a finite group that induces the action on trigonometric polynomials up to a fixed degree. Under the assumption that the trigonometric polynomial is invariant, we show that the associated Hermitian Toeplitz matrix is equivariant with respect to the constructed representation and can thus be block diagonalized via a symmetry adapted basis according to the isotypic decomposition of the representation.

The Hermitian sums-of-squares reinforcement is recalled in Section 3. The feasible region of the arising semidefinite program can be restricted to equivariant Hermitian Toeplitz matrices. Thus, it suffices to consider block diagonal matrices. We show how to apply symmetry reduction in this context with a clarifying example.

Finally, in Section 4, we show how to compute the symmetry adapted basis for our setup and consider a larger example to discuss possible implementations in practice.

There is a MAPLE worksheet dedicated to the examples and computations in this article, which requires the MAPLE package GENERALIZEDCHEBYSHEV<fnref n="1" />. Beyond that, the package offers a large variety of functionalities such as an implementation of the irreducible root systems and computational aspects of multiplicative invariants.

## 2 Trigonometric polynomials with crystallographic symmetry

Let $V$ be a finite-dimensional real vector space with inner product $\langle \cdot, \cdot \rangle$. Let $\Omega$ be a full-dimensional lattice in $V$ with dual lattice $\Lambda := \{\lambda \in V | \forall \mu \in \Omega : \langle \mu, \lambda \rangle \in \mathbb{Z}\}$. A function $f: V \to \mathbb{R}$ which is $\Lambda$-periodic and $L^2$-integrable on the periodicity domain has a Fourier expansion

$$f(u) = \sum_{\mu \in \Omega} f_{\mu} e^{\mu}(u), \qquad (2.1)$$

with $e^{\mu}(u) := \exp(-2\pi i \langle \mu, u \rangle)$ and coefficients $f_{\mu} = \overline{f_{-\mu}} \in \mathbb{C}$, see [DM85, CS99]. If all but finitely many coefficients $f_{\mu}$ are zero, then we call $f$ a **trigonometric polynomial**. The set of all trigonometric polynomials is a vector space with basis $\{e^{\mu} | \mu \in \Omega\}$.

### 2.1 Periodicity domain

The property “$\Lambda$-periodic” means that, for all $u \in V$ and $\lambda \in \Lambda$, we have $f(u + \lambda) = f(u)$. In particular, $\Lambda$ acts on $V$ as an additive group by translation and $f$ is constant on all residue classes $u + \Lambda$ of the compact torus $V/\Lambda$. To understand the periodicity domain of a trigonometric polynomial, we consider the **Voronoï cell** of $\Lambda$

$$\mathrm{Vor}(\Lambda) := \{u \in V | \forall \lambda \in \Lambda : \|u\| \le \|u - \lambda\|\},$$

where $\|u\| := \sqrt{\langle u, u \rangle}$ is the induced norm. This is a compact, convex set and tiles the space by $\Lambda$-translation, that is,

$$V = \bigcup_{\lambda \in \Lambda} (\mathrm{Vor}(\Lambda) + \lambda). \qquad (2.2)$$

The interiors of the cells $\mathrm{Vor}(\Lambda) + \lambda$ are disjoint and the intersections of two adjacent cells is an entire face of both of them [CS99, Ch. 2, §1.2]. The origin $0 \in V$ is contained in the cell $\mathrm{Vor}(\Lambda) + 0 = \mathrm{Vor}(\Lambda)$ itself.

We conclude that the Voronoï cell $\mathrm{Vor}(\Lambda)$ is the closure of the periodicity domain.

<footnote n="1">¹MAPLE software: https://maplesoft.com</footnote>

<footnote>GENERALIZEDCHEBYSHEV package: https://github.com/TobiasMetzlaff/GeneralizedChebyshev</footnote>

<footnote>documentation of the package: https://tobiasmetzlaff.com/html_guides/GeneralizedChebyshevHelp.html</footnote>

<footnote>worksheet for this article: https://tobiasmetzlaff.com/html_guides/trigonometric_symmetry_reduction.html</footnote>
## 2.2 Degree concept

We now introduce the notion of degree for trigonometric polynomials. For $d \in \mathbb{N}$,

$$ \Omega_d := \Omega \cap d \operatorname{Vor}(\Lambda) \qquad (2.3) $$

is a finite subset of the lattice, because $\Omega$ is discrete and $\operatorname{Vor}(\Lambda)$ is compact. We say that a trigonometric polynomial $f \neq 0$ with coefficients $f_\mu$ has **degree** $\operatorname{deg}(f) = d \in \mathbb{N}$ if $\mu \in \Omega_d$ whenever $\mu \neq 0$ and $d$ is minimal with this property. The following statement shows that this is a suitable notion of degree.

**Lemma 2.1.** We have

$$ 1. \{0\} = \Omega_0 \subseteq \Omega_1 \subseteq \Omega_2 \subseteq \dots \subseteq \Omega, $$

$$ 2. \Omega_d + \Omega_{d'} \subseteq \Omega_{d+d'} \text{ whenever } d, d' \in \mathbb{N}, $$

$$ 3. \Omega = \bigcup_{d \in \mathbb{N}} \Omega_d. $$

*Proof.* The first and third statement are clear. Furthermore,

$$ \Omega_d + \Omega_{d'} = (\Omega \cap d \operatorname{Vor}(\Lambda)) + (\Omega \cap d' \operatorname{Vor}(\Lambda)) \subseteq \Omega \cap (d \operatorname{Vor}(\Lambda) + d' \operatorname{Vor}(\Lambda)) = \Omega \cap (d + d') \operatorname{Vor}(\Lambda) = \Omega_{d+d'}, $$

because $\Omega$ is additively closed and $\operatorname{Vor}(\Lambda)$ is convex. $\square$

<figure><img src="image_2.png" /><figcaption>Figure 1: The subsets $\{0\} = \Omega_0 \subseteq \Omega_1 \subseteq \dots \subseteq \Omega_4$ of the hexagonal lattice in the plane (specifically the weight lattice of the root system $\Lambda_2$) are contained in scaled copies of the Voronoï cell of the dual lattice.</figcaption></figure>

**Example 2.2** (Using the notation from Appendix A).

1. It may happen that $\Omega_d + \Omega_{d'}$ is a proper subset of $\Omega_{d+d'}$: Consider the (self-dual) lattice $\Omega = \Lambda = \mathbb{Z}\omega_1 \oplus \dots \oplus \mathbb{Z}\omega_8$ of the root system $\Lambda_8$ from [Bou68, Pl. VII]. None of the lattice generators $\omega_i$ lies in the Voronoï cell and thus $\Omega_1 = \Omega_0 = \{0\}$. On the other hand, we have $\Omega_2 = \mathcal{W}\{0, \omega_1, \omega_8\}$, where $\mathcal{W}$ is the Weyl group. Hence, $\Omega_1 + \Omega_1 = \{0\} \subsetneq \Omega_2$.

2. This definition of degree yields a filtration of the trigonometric polynomials in the sense that the product of two degree $d$ polynomials is of degree at most $2d$. However, it is not a grading, as the degree might be strictly smaller than $2d$. A counter example is given by the hexagonal lattice in Figure 1.
## 2.3 Toeplitz matrix representations

Given a trigonometric polynomial $f = \sum_{\mu} f_{\mu} e^{\mu}$, let $d \in \mathbb{N}$ be the minimal integer, such that $\mu \in \Omega_d + \Omega_d$ whenever $f_{\mu} \neq 0$. We shall write $f$ as

$$f(u) = \mathbf{E}_d(u)^{\dagger} \mathbf{mat}(f) \mathbf{E}_d(u), \qquad (2.4)$$

where $\dagger$ denotes the complex conjugate transpose and

* $\mathbf{E}_d(u)$ is the vector of all $e^{\mu}(u)/\sqrt{|\Omega_d|}$ with $\mu \in \Omega_d$,

* $\mathbf{mat}(f)$ is a matrix with rows and columns indexed by $\Omega_d$ and independent of $u \in V$.

By comparing coefficients in Equation (2.4), we obtain the equation

$$f_{\eta} = \frac{1}{|\Omega_d|} \sum_{\substack{\mu, v \in \Omega_d \\ \mu - v = \eta}} \mathbf{mat}(f)_{\mu v} \qquad (2.5)$$

for $\eta \in \Omega$. Therefore, we may assume without loss of generality that the entries $\mathbf{mat}(f)_{\mu v}$ depend only on the lattice element $\eta = \mu - v$. Hence, $\mathbf{mat}(f)$ can be chosen uniquely as a Toeplitz matrix. Then the conjugate sign symmetry $f_{\mu} = \overline{f}_{-\mu}$ implies that $\mathbf{mat}(f)$ is Hermitian, that is, $\mathbf{mat}(f)^{\dagger} = \mathbf{mat}(f)$. The space of all Hermitian Toeplitz matrices with rows and columns indexed by $\Omega_d$ is denoted by $\text{Toep}_d$.

## 2.4 Group symmetry

Let $\mathcal{W} \subseteq \text{GL}(V)$ be a finite group. We shall define a group action of $\mathcal{W}$ on the space of Hermitian Toeplitz matrices. In order to do so, we assume that $\Omega$ is a $\mathcal{W}$-lattice, that is, $\mathcal{W}(\Omega) = \Omega$. Then a group element $s \in \mathcal{W}$ acts on a trigonometric polynomial $f$ with coefficients $f_{\mu}$ by

$$s \cdot f(u) := \sum_{\mu \in \Omega} f_{\mu} e^{s(\mu)}(u) = \sum_{\mu \in \Omega} f_{s^{-1}(\mu)} e^{\mu}(u) = \sum_{\mu \in \Omega} f_{\mu} e^{\mu}((s^t)^{-1}(u)), \qquad (2.6)$$

where $s^t$ denotes the transpose of $s$ with respect to $\langle \cdot, \cdot \rangle$. We call $f$ $\mathcal{W}$-invariant, if $s \cdot f = f$ for all $s \in \mathcal{W}$. To proceed, we need to assume that $\mathcal{W}(\Omega_d) = \Omega_d$. Then a group element $s \in \mathcal{W}$ also acts on a matrix $X \in \text{Toep}_d$ with entries $X_{\mu v}$ by

$$(s \star X)_{\mu v} := X_{s^{-1}(\mu) s^{-1}(v)}. \qquad (2.7)$$

We denote the fixed-point space of this action by $\text{Toep}_d^{\mathcal{W}} := \{X \in \text{Toep}_d | \forall s \in \mathcal{W} : s \star X = X\}$.

**Lemma 2.3.** We have $\mathbf{mat}(f) \in \text{Toep}_d^{\mathcal{W}}$ if and only if $f$ is $\mathcal{W}$-invariant.

*Proof.* Let $s \in \mathcal{W}$ and $\eta \in \Omega$. Then

$$f_{s^{-1}(\eta)} = \frac{1}{|\Omega_d|} \sum_{\substack{\mu, v \in \Omega_d \\ \mu - v = s^{-1}(\eta)}} \mathbf{mat}(f)_{\mu v} = \frac{1}{|\Omega_d|} \sum_{\substack{\mu, v \in \Omega_d \\ \mu - v = \eta}} \mathbf{mat}(f)_{s^{-1}(\mu) s^{-1}(v)} = \frac{1}{|\Omega_d|} \sum_{\substack{\mu, v \in \Omega_d \\ \mu - v = \eta}} (s \star \mathbf{mat}(f))_{\mu v}.$$

Therefore, we have $s \star \mathbf{mat}(f) = \mathbf{mat}(f)$ if and only if $s \cdot f = f$. $\square$
## 2.5 Symmetry adapted bases

We show that the matrices $\text{Toep}_d^W$ are block diagonal for a certain choice of basis. In order to do so, we start with a representation $\vartheta$ of $\mathcal{W}$, which induces the action on $\text{Toep}_d$ by Equation (2.7).

Note that a trigonometric polynomial of degree at most $d$ can be written uniquely in terms of the $e^\mu$ with $\mu \in \Omega_d$. The coordinates in this basis yield a vector $\mathbf{x} \in \mathbb{C}^{\Omega_d}$ with $\mathbf{x}_{-\mu} = \overline{\mathbf{x}_\mu}$, where $\mathbb{C}^{\Omega_d}$ denotes the space of complex-valued vectors indexed by $\Omega_d$. For $s \in \mathcal{W}$, let $\vartheta(s)$ be the permutation matrix that takes $\mathbf{x} \in \mathbb{C}^{\Omega_d}$ to the vector with entries

$$ (\vartheta(s)\mathbf{x})_\mu := \mathbf{x}_{s^{-1}(\mu)}. \qquad (2.8) $$

Then we obtain the following version of Maschke's theorem.

**Proposition 2.4.** The space $\mathbb{C}^{\Omega_d}$ is a semi-simple $\mathcal{W}$-module with representation $\vartheta$. For all $\mathbf{X} \in \text{Toep}_d$, we have

$$ s \star \mathbf{X} = \vartheta(s) \mathbf{X} \vartheta(s^{-1}). $$

*Proof.* The $\vartheta(s)$ are permutation matrices and thus orthogonal. Furthermore, they satisfy $\vartheta(st) = \vartheta(s)\vartheta(t)$. Hence, $\mathbb{C}^{\Omega_d}$ is a $\mathcal{W}$-module with representation $\vartheta$ over $\mathbb{C}$ and as such semi-simple, see [Ser77, Ch. 1]. Now, let $s \in \mathcal{W}$ and $\mathbf{X} \in \text{Toep}_d$. Then

$$ (\vartheta(s) \mathbf{X} \vartheta(s^{-1}))_{\mu\nu} = (\vartheta(s) \mathbf{X} \vartheta(s)^t)_{\mu\nu} = \sum_{\kappa, \eta \in \Omega_d} \vartheta(s)_{\mu\kappa} \mathbf{X}_{\kappa\eta} \vartheta(s)_{\nu\eta} = \mathbf{X}_{s^{-1}\mu} \mathbf{X}_{s^{-1}\nu} = (s \star \mathbf{X})_{\mu\nu}, $$

because $\vartheta(s)_{\mu\kappa} = 1$ when $\kappa = s^{-1}\mu$ and 0 otherwise. $\square$

In particular, if $\mathbf{X} \in \text{Toep}_d^W$, then $\vartheta(s)\mathbf{X} = \mathbf{X}\vartheta(s)$. Hence, $\mathbf{X}$ commutes with the representation $\vartheta$ and is therefore equivariant. Now, since the $\mathcal{W}$-module $\mathbb{C}^{\Omega_d}$ is semi-simple, it decomposes into simple submodules. By Schur's lemma, any $\mathcal{W}$-homomorphism between complex simple modules is either a scalar isomorphism or zero. Hence, $\mathbb{C}^{\Omega_d}$ has an **isotypic decomposition**

$$ \mathbb{C}^{\Omega_d} = \bigoplus_{i=1}^{h} \left( \bigoplus_{j=1}^{m_i} V_{ij} \right), \qquad (2.9) $$

where, for all $1 \le i \le h$, the $V_{i1}, \dots, V_{im_i}$ are isomorphic, simple $\mathcal{W}$-submodules with dimension $d_i := \dim(V_{ij})$ and multiplicity $m_i \in \mathbb{N}$ so that $\sum_i d_i m_i = |\Omega_d|$, see [Ser77, Ch. 2].

According to this decomposition, there is a change of basis matrix $\mathbf{T} \in \text{GL}(\mathbb{C}^{\Omega_d})$ that transforms any $\mathbf{X} \in \text{Toep}_d^W$ into

$$ \mathbf{T}^{-1} \mathbf{X} \mathbf{T} = \left( \begin{array}{c} \boxed{\mathbf{X}_1} \\ \vdots \\ \boxed{\mathbf{X}_h} \end{array} \right) \quad \text{with} \quad \mathbf{X}_i = \left( \begin{array}{c} \boxed{\tilde{\mathbf{X}}_i} \\ \vdots \\ \boxed{\tilde{\mathbf{X}}_h} \end{array} \right) \in \mathbb{C}^{d_i m_i \times d_i m_i}, \qquad (2.10) $$

where each $\mathbf{X}_i$ consists of $d_i$ equal blocks $\tilde{\mathbf{X}}_i$ of size $m_i \times m_i$. By applying Gram-Schmidt, we may assume additionally that $\mathbf{T}$ is unitary, that is, $\mathbf{T}^{-1} = \mathbf{T}^\dagger$. The column vectors of $\mathbf{T}$ form a **symmetry adapted basis** of $\mathbb{C}^{\Omega_d}$. In particular, we obtain a basis for the trigonometric polynomials of degree at most $d$ according to the decomposition.

## 3 Optimization

We present a numerical algorithm to minimize a $\mathcal{W}$-invariant trigonometric polynomial $f$ with coefficients $f_\mu = \overline{f_{-\mu}} = f_{s^{-1}(\mu)}$ for $s \in \mathcal{W}$ a finite group and $\mu \in \Omega$ a full-dimensional $\mathcal{W}$-lattice in a finite-dimensional real vector space $V$ as in the previous Section 2. The global minimum

$$ f^* := \min_{u \in V} f(u) $$
exists and is assumed in some minimizer in the compact periodicity domain Vor(Λ), where Λ is the dual lattice of Ω.
Our strategy is to follow a known relaxation technique of this optimization problem to a hierarchy of semi-definite
programs (SDP), whose solutions will provide lower bounds of increasing quality for the minimum. This technique
is explained in the book of Dumitrescu for the case Ω = Zⁿ [Dum07, Ch. 2, 3, 4], which is adapted to any lattice
Ω with the notion of degree (= order of the hierarchy) as it was defined in the previous section in a straightforward
manner. We then exploit the symmetry of f by writing the SDP matrices in block diagonal form according to the
isotypic decomposition in Equation (2.10).

The fundamental difference to [HMMR24] is that we first relax to an SDP and then exploit symmetry.

**3.1 Sums of squares**

To begin, let $f$ be a trigonometric polynomial and let $d \in \mathbb{N}$ be the minimal integer so that $\mu \in \Omega_d + \Omega_d$ whenever $f_\mu \neq 0$. The number $d$ can be seen as the starting index of a hierarchy of lower bounds, which is non-decreasing and converges to $f^*$. We shall see that exploiting symmetry in this setup does not effect the quality of the bound, but reduces the computational effort.

Recall from Equation (2.4) that there is a unique Hermitian Toeplitz matrix $\mathbf{mat}(f) \in \text{Toep}_d$, such that

$$f(u) = \mathbf{E}_d(u)^{\dagger} \mathbf{mat}(f) \mathbf{E}_d(u).$$

On the space of Hermitian Toeplitz matrices, the trace admits an inner product, so that we have an SDP

$$f^* \geq f_d := \min_{\mathbf{X} \in \text{Toep}_d} \text{Trace}(\mathbf{mat}(f)\mathbf{X}) \quad \text{s.t.} \quad \mathbf{X} \geq 0, \text{Trace}(\mathbf{X}) = 1. \qquad (3.1)$$

Here, $\mathbf{X} \geq 0$ means that $\mathbf{X}$ is Hermitian positive semi-definite. This defines an ascending sequence of lower bounds $f_d \leq f_{d+1} \leq \dots \leq f^*$ with asymptotic convergence, that is, $f^* = f_d$ for $d \to \infty$. The convergence rate is exponential [BR23].

**Example 3.1.** Consider the case $n = 1$ with $\Omega = \Lambda = \mathbb{Z}$ and $W = \{\pm 1\}$ (see also Example A.1). Then $\Omega_1 = \{1, 0, -1\}$ and $\mathbf{E}_1 = (e^1, 1, e^{-1})^t / \sqrt{3}$. We have

$$\mathbf{E}_1^\dagger \mathbf{E}_1 = \frac{1}{3} \begin{pmatrix} e^1 & 1 & e^1 \end{pmatrix} \begin{pmatrix} e^1 \\ 1 \\ e^{-1} \end{pmatrix} = 1 \quad \text{and} \quad \mathbf{E}_1 \mathbf{E}_1^\dagger = \frac{1}{3} \begin{pmatrix} 1 & e^1 & e^2 \\ e^{-1} & 1 & e^1 \\ e^{-2} & e^{-1} & 1 \end{pmatrix}.$$

As a toy example, take $f(u) := e^2(u) - 2e^1(u) + 3 - 2e^{-1}(u) + e^{-2}(u) = 2 \cos(4\pi u) - 4 \cos(2\pi u) + 3$ with degree 2 and global minimum $f^* = f(\lambda \pm 1/6) = 0$ for $\lambda \in \mathbb{Z}$. Note that $f$ can be rewritten as

$$f(u) = \mathbf{E}_1(u)^{\dagger} \mathbf{mat}(f) \mathbf{E}_1(u), \quad \text{where} \quad \mathbf{mat}(f) = \begin{pmatrix} 3 & -3 & 3 \\ -3 & 3 & -3 \\ 3 & -3 & 3 \end{pmatrix} \in \text{Toep}_1.$$

Thus, the SDP from Equation (3.1) is

$$f_1 = \min_{b,c \in \mathbb{C}} \text{Trace} \left( \begin{pmatrix} 3 & -3 & 3 \\ -3 & 3 & -3 \\ 3 & -3 & 3 \end{pmatrix} \begin{pmatrix} 1/3 & b & c \\ \bar{b} & 1/3 & b \\ \bar{c} & \bar{b} & 1/3 \end{pmatrix} \right) \quad \text{s.t.} \quad \begin{pmatrix} 1/3 & b & c \\ \bar{b} & 1/3 & b \\ \bar{c} & \bar{b} & 1/3 \end{pmatrix} \geq 0$$

and the optimal value $f^* = f_1 = 0$ is obtained with $b = -c = 1/6$.

**3.2 Symmetry reduction**

Now that we have formulated the hierarchy of SDPs, let us assume that $f$ is $W$-invariant.
**Proposition 3.2.** We have $f_d = f_{d,W}$, where $f_d$ is as in Equation (3.1) and

$$f_{d,W} := \min_{\mathbf{X} \in \text{Toep}_d^W} \text{Trace}(\mathbf{mat}(f)(\mathbf{X})) \quad \text{s.t.} \quad \mathbf{X} \ge 0, \text{Trace}(\mathbf{X}) = 1.$$

*Proof.* If $\mathbf{X} \in \text{Toep}_d^W$ is feasible for $f_{d,W}$, then it is especially feasible for $f_d$. Hence, we have $f_d \le f_{d,W}$. For the converse, let $\mathbf{X} \in \text{Toep}_d$ be feasible for $f_d$ and define

$$\tilde{\mathbf{X}} := \frac{1}{|\mathcal{W}|} \sum_{s \in \mathcal{W}} s \star \mathbf{X} \in \text{Toep}_d^W.$$

We claim that $\tilde{\mathbf{X}}$ is feasible for $f_{d,W}$. Indeed, for $\mathbf{X} \ge 0$, $s \in \mathcal{W}$ and $\mathbf{x} \in \mathbb{C}^{\Omega_d}$, we have

$$\mathbf{x}^{\dagger} (s \star \mathbf{X}) \mathbf{x} = \mathbf{x}^{\dagger} (\vartheta(s) \mathbf{X} \vartheta(s)^{\dagger}) \mathbf{x} = (\vartheta(s)^{\dagger} \mathbf{x})^{\dagger} \mathbf{X} (\vartheta(s)^{\dagger} \mathbf{x}) \ge 0,$$

because $\vartheta(s)^{\dagger} = \vartheta(s)^{\dagger}$. Thus, $s \star \mathbf{X}$ is Hermitian positive semi-definite. Furthermore, if $\text{Trace}(\mathbf{X}) = 1$, then

$$\text{Trace}(s \star \mathbf{X}) = \sum_{\mu \in \Omega_d} \mathbf{X}_{s^{-1}(\mu)} s^{-1}(\mu) = \sum_{\nu \in \Omega_d} \mathbf{X}_{\nu\nu} = \text{Trace}(\mathbf{X}) = 1.$$

Thus, $s \star \mathbf{X}$ is also feasible for $f_d$. Since the feasibility region of $f_d$ is convex, it also contains the convex combination $\tilde{\mathbf{X}}$. In particular, $\tilde{\mathbf{X}}$ is feasible for $f_{d,W}$ with

$$\text{Trace}(\mathbf{mat}(f)(\tilde{\mathbf{X}})) = \frac{1}{|\mathcal{W}|} \sum_{s \in \mathcal{W}} \text{Trace}(\mathbf{mat}(f)(s \star \mathbf{X})) = \frac{1}{|\mathcal{W}|} \sum_{s \in \mathcal{W}} \text{Trace}((s^{-1} \star \mathbf{mat}(f))(\mathbf{X})) = \text{Trace}(\mathbf{mat}(f)(\mathbf{X})),$$

because $\mathbf{mat}(f) \in \text{Toep}_d^W$. Hence, we also have $f_d \ge f_{d,W}$. $\square$

Recall from Equation (2.10) that matrices in $\text{Toep}_d^W$ can be block diagonalized with a change of basis $\mathbf{T}$.

**Theorem 3.3.** Assume that $\mathbf{T}^{\dagger} \mathbf{mat}(f) \mathbf{T}$ has blocks $\tilde{\mathbf{F}}_i \in \mathbb{C}^{m_i \times m_i}$. Then $f_d = f_{d,W} = f_{d,W}^{\text{block}}$, where

$$f_{d,W}^{\text{block}} := \min_{\mathbf{X} \in \text{Toep}_d^W} \sum_{i=1}^{h} d_i \text{Trace}(\tilde{\mathbf{F}}_i \tilde{\mathbf{X}}_i) \quad \text{s.t.} \quad \text{Trace}(\mathbf{X}) = 1, \mathbf{T}^{\dagger} \mathbf{T} \mathbf{T}^{\dagger} \mathbf{X} \mathbf{T} \text{ has blocks } \tilde{\mathbf{X}}_i \ge 0.$$

*Proof.* Since the trace does not depend on the basis, we have

$$\text{Trace}(\mathbf{mat}(f)(\mathbf{X})) = \text{Trace}(\mathbf{T}^{\dagger} \mathbf{mat}(f) \mathbf{T} \mathbf{T}^{\dagger} \mathbf{X} \mathbf{T}) = \sum_{i=1}^{h} d_i \text{Trace}(\tilde{\mathbf{F}}_i \tilde{\mathbf{X}}_i).$$

Note that $\mathbf{X} \ge 0$ if and only if $\mathbf{T}^{\dagger} \mathbf{T} \mathbf{T}^{\dagger} \mathbf{X} \ge 0$, that is, for all $1 \le i \le h$, we have $\tilde{\mathbf{X}}_i \ge 0$. Thus, $f_{d,W} = f_{d,W}^{\text{block}}$ and the statement follows from Proposition 3.2. $\square$

**Example 3.4.** We continue with Example 3.1 with $n = 1$, $d = 1$ and $\mathcal{W} = \{\pm \text{id}\}$. An arbitrary $\mathbf{X} \in \text{Toep}_1$ shall have rows and columns indexed by $\Omega_1 = \{1, 0, -1\}$. Then the group element $-\text{id} \in \mathcal{W}$ acts on $\text{Toep}_1$ by

$$\begin{pmatrix} 1 & 0 & -1 \\ \frac{a}{b} & b & c \\ \frac{a}{c} & \frac{b}{a} & a \end{pmatrix} \xrightarrow{(-\text{id}) \star \dots} \begin{pmatrix} 1 & 0 & -1 \\ a & \bar{b} & \bar{c} \\ b & a & \bar{b} \end{pmatrix}$$
for $a \in \mathbb{R}$ and $b, c \in \mathbb{C}$. Thus, the fixed point space $\text{Toep}_1^W$ consists of those $\mathbf{X} \in \text{Toep}_1$ with $a, b, c \in \mathbb{R}$. The above action is induced by the orthogonal representation $\rho : W \to \text{GL}(\mathbb{C}^{\Omega_1}) = \text{GL}_3(\mathbb{C})$ with

$$ \rho(-\text{id}) = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}. $$

We have an isotopic decomposition

$$ \mathbb{C}^3 = \left( \left\langle \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \right\rangle \oplus \left\langle \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \right\rangle \right) \oplus \left\langle \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix} \right\rangle $$

with $h = 2$ irreducible representations with multiplicities $m_1 = 2, m_2 = 1$ and dimensions $d_1 = 1, d_2 = 1$. When $\mathbf{T}$ is the matrix with columns given by the above three basis vectors and $f$ is the $\mathcal{W}$-invariant trigonometric polynomial from Example 3.1, then

$$ \mathbf{T}^{\dagger} \mathbf{X} \mathbf{T} = \begin{pmatrix} a & \sqrt{2} \bar{b} & 0 \\ \sqrt{2} b & a+c & 0 \\ 0 & 0 & a-c \end{pmatrix} \quad \text{and} \quad \mathbf{T}^{\dagger} \mathbf{mat}(f) \mathbf{T} = \begin{pmatrix} 3 & -3 \sqrt{2} & 0 \\ -3 \sqrt{2} & 6 & 0 \\ 0 & 0 & 0 \end{pmatrix}. $$

Note that the condition $\text{Trace}(\mathbf{X}) = 1$ implies $a = 1/3$. Thus,

$$ f_{1,\mathcal{W}}^{\text{block}} = \min_{b,c \in \mathbb{R}} \text{Trace} \left( \begin{pmatrix} 3 & -3\sqrt{2} \\ -3\sqrt{2} & 6 \end{pmatrix} \begin{pmatrix} 1/3 & \sqrt{2}b \\ \sqrt{2}b & 1/3+c \end{pmatrix} \right) \quad \text{s.t.} \quad \begin{pmatrix} 1/3 & \sqrt{2}b \\ \sqrt{2}b & 1/3+c \end{pmatrix} \ge 0, 1/3 \ge c. $$

Finally, the optimal value $f^* = f_1 = f_{1,\mathcal{W}} = f_{1,\mathcal{W}}^{\text{block}} = 0$ is recovered with $b = -c = 1/6$.

# 4 Computing symmetry adapted bases

We have seen the advantage of using a symmetry adapted basis in trigonometric optimization in the previous Section 3. Using the computer algebra systems OSCAR<fnref n="2" /> and MAPLE<fnref n="3" />, we explain how to obtain said basis in practice with the algorithm from [Ser77, Ch. 2].

## 4.1 Projection onto isotopic components

The semi-simple $\mathcal{W}$-module $\mathbb{C}^{\Omega_d}$ has an isotopic decomposition

$$ \mathbb{C}^{\Omega_d} = V^{(1)} \oplus \dots \oplus V^{(h)}, \quad V^{(i)} = V_1^{(i)} \oplus \dots \oplus V_{m_i}^{(i)}, $$

where, for each $i$, the $V_j^{(i)}$ are isomorphic, simple $\mathcal{W}$-submodules with multiplicity $m_i$ and dimensions $d_i = \dim(V_j^{(i)})$. The characters $\chi_i$ of the representations associated to the $V_j^{(i)}$ are the complex irreducible characters of $\mathcal{W}$.

**Proposition 4.1.** [Ser77] For $1 \le i \le h$, a projection of $V$ onto $V^{(i)}$ is given by

$$ \mathbf{P}^{(i)} := \frac{d_i}{|\mathcal{W}|} \sum_{s \in \mathcal{W}} \chi_i(s^{-1}) \theta(s). $$

<footnote n="2">²https://www.oscar-system.org</footnote>

<footnote n="3">³https://maplesoft.com</footnote>
## 4.2 Computing the basis

To compute a basis for $\mathbb{C}^{\Omega_d}$ so that the $W$-invariant matrices have the block diagonal structure from Equation (2.10), we fix an index $1 \le i \le h$ and follow the steps below.

1. For an irreducible representation of $W$ with character $\chi_i$, choose representing matrices $(\mathbf{D}_{k\ell}^{(i)}(s))_{1\le k,\ell \le d_i}$.

2. For $1 \le \ell \le d_i$, set

$$ \mathbf{P}_{\ell}^{(i)} := \frac{d_i}{|W|} \sum_{s \in W} \mathbf{D}_{1\ell}^{(i)}(s^{-1}) \vartheta(s). $$

The column dimension of this matrix is $m_i$.

3. Compute an orthonormal basis $\{w_{11}^{(i)}, \dots, w_{1m_i}^{(i)}\}$ for the column space of $\mathbf{P}_1^{(i)}$.

4. For $2 \le \ell \le d_i$ and $1 \le j \le m_i$, set

$$ w_{\ell j}^{(i)} := \mathbf{P}_{\ell}^{(i)} w_{1j}^{(i)}. $$

Note that the representing matrices in step 1. are by no means unique. Finding $(\mathbf{D}_{k\ell}^{(i)}(s))_{1\le k,\ell \le d_i}$ is a problem on its own and addressed in the example below.

**Proposition 4.2.** [Ser77, FS92] For $1 \le i \le h$, $1 \le j \le m_i$, the set $\{w_{1j}^{(i)}, \dots, w_{d_i j}^{(i)}\}$ is an orthonormal basis for $V_j^{(i)}$. Furthermore, the matrix

$$ \tilde{\mathbf{T}} := \left( \underbrace{w_{11}^{(1)}, \dots, w_{d_1 1}^{(1)}}_{V_1^{(1)}} , \dots , \underbrace{w_{1m_1}^{(1)}, \dots, w_{d_1 m_1}^{(1)}}_{V_{m_1}^{(1)}} , \dots , \underbrace{w_{11}^{(h)}, \dots, w_{d_h 1}^{(h)}}_{V_1^{(h)}} , \dots , \underbrace{w_{1m_h}^{(h)}, \dots, w_{d_h m_h}^{(h)}}_{V_{m_h}^{(h)}} \right) $$

has rank $|\Omega_d|$ and, for $s \in W$, $\tilde{T}^\dagger \vartheta(s) \tilde{T}$ has $h$ blocks, each consisting of $m_i$ further equal $d_i \times d_i$ blocks.

On the other hand, when the columns are reordered to

$$ \mathbf{T} := \left( w_{11}^{(1)}, \dots, w_{1m_1}^{(1)}, \dots, w_{d_1 1}^{(h)}, \dots, w_{d_1 m_1}^{(h)}, \dots, w_{11}^{(h)}, \dots, w_{1m_h}^{(h)}, \dots, w_{d_h 1}^{(h)}, \dots, w_{d_h m_h}^{(h)} \right), $$

then, for $X \in \text{Toep}_{d}^{W}$, $\mathbf{T}^\dagger X \mathbf{T}$ has $h$ blocks, each consisting of $d_i$ further equal $m_i \times m_i$ blocks (see Equation (2.10)).

## 4.3 Example

We consider the Weyl group of the $A_2$ root system $W \cong \mathfrak{S}_3$. The group has order $|W| = 6$ and $h = 3$ irreducible representations, which is encoded by the character table $\chi$.

### 4.3.1 Computing multiplicities

We think of $\chi \in \text{GL}_h(\mathbb{Z})$ as an invertible integer matrix with rows indexed by the irreducible representations $1 \le i \le h$ and columns indexed by the conjugacy classes of the group elements $s \in W$, such that

$$ \text{Trace}(\vartheta(s)) = m_1 \chi_1(s) + \dots + m_h \chi_h(s). $$

In particular, the multiplicities $m_i$ are the solutions of a linear system and the dimensions are $d_i = \chi_i(\text{id})$, where $\text{id} \in W$ is the identity element. In the case of $W \cong \mathfrak{S}_3$, we have

$$ \chi = \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \left( \begin{array}{ccc} \text{id} & s_1 & s_1 s_2 \\ 1 & -1 & 1 \\ 2 & 0 & -1 \\ 1 & 1 & 1 \end{array} \right), $$
where $s_1 = (12), s_2 = (23) \in W$ are the generating transpositions of $\mathfrak{S}_3$. With the computer algebra system OSCAR$^4$, this matrix can be computed as follows.

julia> using Oscar;
julia> W = symmetric_group(3);
julia> X = character_table(W);

Note that the first and third row of $\chi$ correspond to the sign and trivial representation of dimension 1, respectively. By computing Trace($\theta(s)$) and solving for the $m_i$, we find the multiplicities in Table 1.

<table><thead><tr><th></th><th>d = 1</th><th>d = 2</th><th>d = 3</th><th>d = 4</th><th>d = 5</th><th>d = 6</th></tr></thead><tbody><tr><th>m<sub>1</sub></th><td>0</td><td>1</td><td>3</td><td>6</td><td>10</td><td>15</td></tr><tr><th>m<sub>2</sub></th><td>2</td><td>6</td><td>12</td><td>20</td><td>30</td><td>42</td></tr><tr><th>m<sub>3</sub></th><td>3</td><td>6</td><td>10</td><td>15</td><td>21</td><td>28</td></tr></tbody></table>

Table 1: The multiplicities $m_i$ of the irreducible representations of $W \cong \mathfrak{S}_3$ occurring in the representation $\theta$ by which $W$ acts on the trigonometric polynomials up to degree $d$. Those are the $m_1$: sign-, $m_2$: reflection- and $m_3$: trivial representation.

For $d = 1$, we have $\Omega_1 = \{0\} \cup W\omega_2 \cup W\omega_1 = \{0, -\omega_1, \omega_1 - \omega_2, \omega_2, -\omega_2, \omega_2 - \omega_1, \omega_1\}$ and, by Proposition 4.1, the projections of $C^{\Omega_1} = C^7$ onto $V_1, V_2, V_3$ are

$$ \mathbf{P}^{(1)} = 0, \quad \mathbf{P}^{(2)} = \frac{1}{3} \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & -1 & -1 & 0 & 0 & 0 \\ 0 & -1 & 2 & -1 & 0 & 0 & 0 \\ 0 & -1 & -1 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & -1 & -1 \\ 0 & 0 & 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & 0 & -1 & -1 & 2 \end{pmatrix}, \quad \mathbf{P}^{(3)} = \frac{1}{3} \begin{pmatrix} 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix} $$

### 4.3.2 Computing representing matrices

Next, we need the representing matrices associated to the irreducible characters. The representations associated to the characters $\chi_1$ and $\chi_2$ are 1-dimensional. Hence, the representing matrices are

$$ \mathbf{D}^{(1)}(s_1) = \mathbf{D}^{(1)}(s_2) = (-1) \quad \text{and} \quad \mathbf{D}^{(3)}(s_1) = \mathbf{D}^{(3)}(s_2) = (1). $$

For $\chi_2$, we discuss three possible approaches.

#### Over $\mathbb{Z}$ with MAPLE

This strategy works, because $W$ is a Weyl group (see Appendix A): It acts by permutation of coordinates on $V = \mathbb{R}^3 / \langle [1, 1, 1]^t \rangle$, which is a simple $W$-module with character $\chi_2$. The root system $A_2$ from Figure 2 is a root system for $V$ and the weight lattice $\Omega = \mathbb{Z}\omega_1 \oplus \mathbb{Z}\omega_2$ is hexagonal. The reflection associated to the root $\rho_i$ takes $\omega_j$ to

$$ \omega_j - \langle \omega_j, \rho_i^\vee \rangle \rho_i = \begin{cases} \omega_2 - \omega_1, & \text{if } i = j = 1 \\ \omega_2, & \text{if } i = 1, j = 2 \\ \omega_1, & \text{if } i = 2, j = 1 \\ \omega_1 - \omega_2, & \text{if } i = j = 2 \end{cases} $$

<footnote>$^4$https://www.oscar-system.org</footnote>
The row vectors of the representing matrices are the coordinates in the basis of the $\omega_i$, that is,

$$ \mathbf{D}^{(2)}(s_1) = \begin{pmatrix} -1 & 1 \\ 0 & 1 \end{pmatrix} \quad \text{and} \quad \mathbf{D}^{(2)}(s_2) = \begin{pmatrix} 1 & 0 \\ 1 & -1 \end{pmatrix}. $$

To obtain these matrices, one can use the following command from the MAPLE package GENERALIZEDCHEBYSHEV:

maple> with(LinearAlgebra):

maple> read("GeneralizedChebyshev.mpl"); with(GeneralizedChebyshev):

maple> ZWeylGroupGen(A,2);

### Over $\mathbb{Z}[\zeta]$ with OSCAR

Since $\mathcal{W}$ is a reflection group, it can be realized over $\mathbb{Q}[\zeta]$, where $\zeta \in \mathbb{C}$ is a third root of unity [ST54]. The matrices of $s_1$ and $s_2$ in this reflection representation are

$$ \mathbf{D}^{(2)}(s_1) = \begin{pmatrix} 0 & -\zeta - 1 \\ \zeta & 0 \end{pmatrix} \quad \text{and} \quad \mathbf{D}^{(2)}(s_2) = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}. $$

Note that the coefficients are actually in $\mathbb{Z}$. With OSCAR, those are obtained as follows.

julia> using Oscar;

julia> W = symmetric_group(3);

julia> V = irreducible_modules(W);

julia> g1, g2 = V[3].ac[1].matrix, V[3].ac[2].matrix;

julia> s1, s2 = g2, g1*g2

(In the OSCAR version used for this article (0.12.0-DEV), the representation $V[3]$ corresponds to the second irreducible character above. This might change in future versions.)

### Over $\mathbb{Q}$ with OSCAR

Alternatively, one can immediately compute rational matrices, but the entries are usually not integral. Those are

$$ \mathbf{D}^{(2)}(s_1) = \begin{pmatrix} -7/10 & -1/5 \\ -51/20 & 7/10 \end{pmatrix} \quad \text{and} \quad \mathbf{D}^{(2)}(s_2) = \begin{pmatrix} -7/15 & 8/15 \\ 22/15 & 7/15 \end{pmatrix} $$

and obtained as follows.

julia> using Oscar;

julia> W = symmetric_group(3);

julia> V = Oscar.irreducible_modules(AnticNumberField, W, minimal_degree = true);

julia> g = map(z -> map_entries(QQ, z), matrix.(action(V[3])));

julia> s1, s2 = g[2], g[1]*g[2]

### 4.3.3 Block diagonalization

We now compute the symmetry adapted basis. The basis itself of course depends on the used method to obtain $\mathbf{D}^{(2)}(s_1)$ and $\mathbf{D}^{(2)}(s_2)$, but since the SDP is invariant under change of basis, the equivariant matrices always have the same block diagonal structure. Following the steps preceding Proposition 4.2, we can obtain a symmetry adapted basis for the isotypic decomposition $\mathbb{C}^{\Omega_1}$. A basis for the space of trigonometric polynomials up to degree 1 according to this decomposition is given by

$$ \underbrace{e^{-\omega_1} - e^{\omega_1 - \omega_2}, \quad e^{\omega_1 - \omega_2} - e^{\omega_2}, \quad e^{\omega_2 - \omega_1} - e^{\omega_1}, \quad e^{-\omega_2} - e^{\omega_2 - \omega_1}}_{V_1^{(2)} \times V_2^{(2)}} \quad \underbrace{1, \quad e^{-\omega_1} + e^{\omega_1 - \omega_2} + e^{\omega_2}, \quad e^{-\omega_2} + e^{\omega_2 - \omega_1} + e^{\omega_1}}_{V_1^{(3)} \times V_2^{(3)} \times V_3^{(3)}} $$
It is the output of the following MAPLE command.

maple> with(LinearAlgebra):

maple> read("GeneralizedChebyshev.mpl"); with(GeneralizedChebyshev):

maple> IsotypicDecompositionBasisMultiplicative(A,2,1);

By putting the basis elements in the correct order, we obtain a matrix $\tilde{T}$, so that, for $s \in W$, the matrices $\tilde{T}^\dagger \theta(s) \tilde{T}$ have the block diagonal structure

$$ \left( \begin{bmatrix} \textcolor{red}{\blacksquare} & \textcolor{red}{\blacksquare} \\ \textcolor{red}{\blacksquare} & \textcolor{red}{\blacksquare} \end{bmatrix} \quad \begin{bmatrix} \textcolor{blue}{\blacksquare} \\ \textcolor{blue}{\blacksquare} \end{bmatrix} \quad \begin{bmatrix} \textcolor{red}{\blacksquare} \\ \textcolor{blue}{\blacksquare} \end{bmatrix} \right), $$

that is, $m_2 = 2$ blocks of size $d_2 = 2$ and $m_3 = 3$ blocks of size $d_3 = 1$.

By reordering the columns, we obtain a matrix $\mathbf{T}$, so that, for $\mathbf{X} \in \text{Toep}_d^W$, the matrices $\mathbf{T}^\dagger \mathbf{X} \mathbf{T}$ have the block diagonal structure

$$ \left( \begin{bmatrix} \textcolor{red}{\blacksquare} & \textcolor{red}{\blacksquare} \\ \textcolor{red}{\blacksquare} & \textcolor{red}{\blacksquare} \end{bmatrix} \quad \begin{bmatrix} \textcolor{blue}{\blacksquare} \\ \textcolor{blue}{\blacksquare} \end{bmatrix} \quad \begin{bmatrix} \textcolor{blue}{\blacksquare} \\ \textcolor{blue}{\blacksquare} \end{bmatrix} \right), $$

that is, $d_2 = 2$ equal blocks of size $m_2 = 2$ and $d_3 = 1$ equal block of size $m_3 = 3$.

Specifically, a matrix $\mathbf{X} \in \text{Toep}_1^W$ is of the form

$$ \mathbf{X} = \begin{pmatrix} a & b & b & b & c & c & c \\ \bar{b} & d & e & e & f & f & g \\ \bar{b} & e & d & e & f & g & f \\ \bar{b} & e & e & d & g & f & f \\ \bar{c} & \bar{f} & \bar{f} & \bar{g} & h & k & k \\ \bar{c} & \bar{f} & \bar{g} & \bar{f} & k & h & k \\ \bar{c} & \bar{g} & \bar{f} & \bar{f} & k & k & h \end{pmatrix} \quad \mathbf{T}^{\dagger} \dots \mathbf{T} \quad \begin{pmatrix} d-e & f-g & 0 & 0 & 0 & 0 & 0 \\ \bar{f}-\bar{g} & h-k & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & d-e & f-g & 0 & 0 & 0 \\ 0 & 0 & \bar{f}-\bar{g} & h-k & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & a & \sqrt{3}b & \sqrt{3}c \\ 0 & 0 & 0 & 0 & \sqrt{3}\bar{b} & d+2e & 2f+g \\ 0 & 0 & 0 & 0 & \sqrt{3}\bar{c} & 2\bar{f}+\bar{g} & h+2k \end{pmatrix}. $$

for some $a, d, e, h, k \in \mathbb{R}$, $b, c, f, g \in \mathbb{C}$. Consider the $W$-invariant trigonometric polynomial

$$ f := 6+4e^{\omega_1}+4e^{\omega_2}+4e^{\omega_2-\omega_1}+4e^{\omega_1-\omega_2}+4e^{-\omega_1}+4e^{-\omega_2}+2e^{2\omega_1}+2e^{2\omega_2}+2e^{2\omega_2-2\omega_1}+2e^{2\omega_1-2\omega_2}+2e^{-2\omega_1}+2e^{-2\omega_2} $$

with $a = d = 6$, $b = c = f = 7$, $e = k = 0$, $g = 14$. Then we have

$$ f^* \ge f_{1,W}^{\text{block}} = \min_{\mathbf{X} \in \text{Toep}_1^W} \sum_{i=1}^h d_i \text{Trace}(\tilde{\mathbf{F}}_i \tilde{\mathbf{X}}_i) \quad \text{s.t.} \quad \text{Trace}(\mathbf{X}) = 1, \mathbf{T}^\dagger \mathbf{X} \mathbf{T} \text{ has blocks } \tilde{\mathbf{X}}_i \ge 0. $$

$$ = \min_{a, \dots, k} 2(6d - 6e - 7f + 7g - 7\bar{f} + 7\bar{g} + 6h - 6k) \\ + (6a + 21b + 21c + 21\bar{b} + 6d + 12e + 56f + 28g + 21\bar{c} + 56\bar{f} + 28\bar{g} + 6h + 12k) $$

$$ \text{s.t.} \quad a + 3d + 3h = 1, \quad \begin{pmatrix} d-e & f-g \\ \bar{f}-\bar{g} & h-k \end{pmatrix} \ge 0, \quad \begin{pmatrix} a & \sqrt{3}b & \sqrt{3}c \\ \sqrt{3}\bar{b} & d+2e & 2f+g \\ \sqrt{3}\bar{c} & 2\bar{f}+\bar{g} & h+2k \end{pmatrix} \ge 0. $$
Now, we only need to certify positive semi-definiteness for Hermitian matrices with $2^2 + 3^2 = 13$ real entries instead of matrices with $7^2 = 49$ entries.

## Conclusion

For large $n, d$ and $|W|$, solving the SDP via Theorem 3.3 is vastly more efficient than without the symmetry reduction via Equation (3.1), because (i) the group symmetry reduces the number of variables and (ii) the matrices are block-diagonal and thus the matrix size is reduced from $|\Omega_d|^2$ to $m_1^2, \dots, m_h^2$ (which simplifies the certification of positive semi-definiteness).

The bottleneck in the presented approach is the computation of the representing matrices $D_{k\ell}^{(i)}(s)$ for the irreducible representations. In the examples, we have used computer algebra systems, such as MAPLE and OSCAR. Current work in progress revolves around the implementation of the presented approach to the point where the input consists of an invariant trigonometric polynomial $f$, a finite group $W$ and an order of the relaxation $d$ and the output of the matrices defining the SDP from Theorem 3.3.

We compare with the approach via generalized Chebyshev polynomials in [HMMR24, HMMR22]. The SDP matrices have blocks and the sizes of the blocks are

1. dense: $|\Omega_d|^2$ (1 Hermitian block),

2. Chebyshev: $\frac{|\Omega_d|^2+n^2|\Omega_{d-n}|^2}{|W|^2}$ (2 symmetric blocks),

3. symmetry adapted basis: $\sum_{i=1}^h d_i (m_i^{(d)})^2$ (h Hermitian blocks with $d_i$ equal subblocks).

The dense approach is in any case the least efficient. To decide, whether 2. or 3. provides smaller matrices, one can compute $|\Omega_d|, |W|, d_i$ and $m_i^{(d)}$ using the MAPLE package GENERALIZEDCHEBYSHEV:

```
maple> with(LinearAlgebra): read("GeneralizedChebyshev.mpl"); with(GeneralizedChebyshev):
maple> Type,n,d := A,2,1;
maple> nops(WeightList(Type,n,d)); # number of lattice points up to degree d
maple> WeylGroupOrder(Type,n); # order of the Weyl group
maple> IrredRepDimMultiplicative(Type,n); # dimensions of irreducible representations
maple> IsotypicDecompositionMultiplicitiesMultiplicative(Type,n,d); # multiplicities
```

## Open problems

How to decide a priori which approach gives a better numerical result is unknown to the author. By Theorem 3.3, we already know that the approach via symmetry adapted basis gives the same solution as the one for the dense approach. The exponential convergence rate is proven in [BR23]. The Chebyshev approach on the other hand uses polynomial instead of trigonometric optimization techniques. In this case, the convergence rate is given in [BM23]. This article now provides the means to compare the two approaches, which the author intends to address in future work.

For the symmetric group $S_3$ in Table 1, one can observe a pattern for the multiplicities, namely $m_1^{(d+1)} = m_1^{(d)} + d$, $m_2^{(d+1)} = m_2^{(d)} + 2d + 2$ and $m_3^{(d+1)} = m_3^{(d)} + d + 2$. It would be very interesting to prove more general formulae for the behavior of the multiplicities.
## Acknowledgments

I wish to thank Evelyne Hubert (Sophia Antipolis), Cordian Riener (Tromsø) and Ulrich Thiel (Kaiserslautern) for their lessons and fruitful discussions on representation theory.

This work has been supported by the Deutsche Forschungsgemeinschaft transregional collaborative research centre (SFB-TRR) 195 "Symbolic Tools in Mathematics and their Application".

## References

[ALRT13] L. Andrén, J.-B. Lasserre, C. Riener, and T. Theobald. Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization. Mathematics of Operations Research, 38(1):122-141, 2013.

[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.

[Ber09] F. Bergeron. Algebraic combinatorics and coinvariant spaces. CMS Treatises in Mathematics, Canadian Mathematical Society, 2009.

[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.

[BM23] L. Baldi and B. Mourrain. On the effective Putinar's Positivstellensatz and moment approximation. Mathematical Programming, 200:71-103, 2023.

[Bou68] N. Bourbaki. Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV - Chapitre VI. Actualités Scientifiques et Industrielles, No. 1337. Hermann, Paris, 1968.

[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.

[BWFW08] X. Bai, H. Wei, K. Fujisawa, and Y. Wang. Semidefinite programming for optimal power flow problems. International Journal of Electrical Power & Energy Systems, 30(6):383-392, 2008.

[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.

[DM85] H. Dym and H. McKean. Fourier Series and Integrals. Probability and Mathematical Statistics. Elsevier Science, 1985.

[Dum07] B. Dumitrescu. Positive Trigonometric Polynomials and Signal Processing Applications. Signals and Communication Technology. Springer Netherlands, 2007.

[FR09] J.-C. Faugere and S. Rahmany. Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases. In Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, Seoul, Republic of Korea, ISSAC'09, pages 151-158. 2009.

[FS92] A. Fässler and E. Stiefel. Group Theoretical Methods and Their Applications. Birkhäuser, Boston, MA, 1992.
[Gat90] K. Gatermann. Symbolic solution of polynomial equation systems with symmetry. In *Proceedings of the 1990 International Symposium on Symbolic and Algebraic Computation*, Tokyo, Japan, ISSAC'90, pages 112-119. 1990.

[Gat00] K. Gatermann. Orbit space reduction. In *Computer Algebra Methods for Equivariant Dynamical Systems*, Lecture Notes in Mathematics, pages 105-134. Springer, Berlin, Heidelberg, 2000.

[GP04] K. Gatermann and P. Parrilo. Symmetry groups, semidefinite programs, and sums of squares. *Journal of Pure and Applied Algebra*, 192:95-128, 2004.

[HL13] E. Hubert and G. Labahn. Scaling invariants and symmetry reduction of dynamical systems. *Foundations of Computational Mathematics*, 13(4):479-516, 2013.

[HL16] E. Hubert and G. Labahn. Computation of the invariants of finite abelian groups. *Mathematics of Computation*, 85(302):3029-3020, 2016.

[HMMR22] E. Hubert, T. Metzlaff, P. Moustrou, and C. Riener. T-orbit spaces of multiplicative actions and applications. *ACM Communications in Computer Algebra*, 56(2):72-75, 2022.

[HMMR24] E. Hubert, T. Metzlaff, P. Moustrou, and C. Riener. Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs. to appear in *Mathematical Programming*, 2024.

[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.

[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.

[Las01] J-B. Lasserre. Global Optimization with Polynomials and the Problem of Moments. *SIAM Journal of Optimization*, 11(3):796-817, 2001.

[LFF$^{+}$20] M. Lakshmi, G. Fantuzzi, J. Fernández-Caballero, Y. Hwang, and S. Chernyshenko. Finding extremal periodic orbits with polynomial optimization, with application to a nine-mode model of shear flow. *SIAM Journal on Applied Dynamical Systems*, 19(2):763-787, 2020.

[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.

[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] T. Metzlaff. Symmetry Adapted Bases for Trigonometric Optimization. *ACM Communications in Computer Algebra*, 57(3):137-140, 2023.

[MKNR13] H. Munthe-Kaas, M. Nome, and B. Ryland. Through the kaleidoscope: symmetries, groups and Chebyshev-approximations from a computational point of view. In *Foundations of computational mathematics*, Budapest 2011, London Mathematical Society Lecture Note Series, pages 188-229. Cambridge Univ. Press, Cambridge, 2013.

[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.
[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.

[RBH21] E. Rodriguez Bazan and E. Hubert. Multivariate interpolation: Preserving and exploiting symmetry. *Journal of Symbolic Computation*, 107:1-22, 2021.

[RBH22a] E. Rodriguez Bazan and E. Hubert. Algorithms for fundamental invariants and equivariants of finite groups. *Mathematics of Computation*, 91(337), 2022.

[RBH22b] E. Rodriguez Bazan and E. Hubert. Symmetry in multivariate ideal interpolation. *Journal of Symbolic Computation*, 115:174-200, 2022.

[Ser77] J.-P. Serre. *Linear Representations of Finite Groups*. Graduate Texts in Mathematics. Springer, New York, 1977.

[Ser01] J.-P. Serre. *Complex Semisimple Lie Algebras*. Monographs in Mathematics. Springer, Berlin, Heidelberg, 2001.

[ST54] G. Shephard and J. Todd. Finite unitary reflection groups. *Canadian Journal of Mathematics*, 6:274-304, 1954.

[Sta79] R. Stanley. Invariants of finite groups and their applications to combinatorics. *Bull. Amer. Math. Soc.*, 1(3):475-511, 1979.

[Val09] F. Vallentin. Symmetry in semidefinite programs. *Experimental Mathematics*, 430(1):360-369, 2009.

[Via17] M. Viazovska. The sphere packing problem in dimension 8. *Annals of Mathematics*, 185(3):991-1015, 2017.

[WM22] J. Wang and V Magron. Exploiting sparsity in complex polynomial optimization. *Journal of Optimization Theory and Applications*, 192:335-359, 2022.

[WSKM23] J. Wang, C. Schlosser, M. Korda, and V. Magron. Exploiting term sparsity in moment-sos hierarchy for dynamical systems. *IEEE Transactions on Automatic Control*, 68(12):8232-8237, 2023.
A Lattices and Weyl groups associated to crystallographic root systems

We recall the definition for the lattices and groups, which appeared in the examples throughout the article and which are of interest for the applications mentioned in the introduction. Such lattices arise from root systems, which appear, for example, in the representation theory of semi-simple complex Lie algebras, see [Bou68, Ser01].

Let $V$ be a finite-dimensional real vector space with inner product $\langle \cdot, \cdot \rangle$. A subset $R \subseteq V$ is called a (crystallographic, reduced) **root system** in $V$, if the following conditions$^5$ hold.

R1 R is finite, spans $V$ as a vector space 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 V$.

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

The elements of $R$ are called **roots** and the $\rho^{\vee}$ are called **coroots**. The lattice $\Lambda$ spanned by all coroots $\rho^{\vee}$ is full-dimensional in $V$ and called the **coroot lattice**.

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 $GL(V)$ and orthogonal with respect to the inner product $\langle \cdot, \cdot \rangle$. The coroot lattice is a $W$-lattice and the group product of $W$ by $\Lambda$ is semi-direct.

Every root system contains a **base**, that is, a subset $B = \{\rho_1, \dots, \rho_n\}$ of $R$ satisfying the following conditions [Bou68, Ch. VI, §1, Thm. 3].

B1 B is a vector space basis of $V$.

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$.

A **weight** of $R$ is an element $\mu \in V$, such that, for all $\rho \in R$, we have $\langle \mu, \rho^{\vee} \rangle \in \mathbb{Z}$. By the “crystallographic” property R2, every root is a weight. For a base $B = \{\rho_1, \dots, \rho_n\}$ of the root system, the **fundamental weights** are the elements $\{\omega_1, \dots, \omega_n\}$, where, for $1 \le i, j \le n$, we have $\langle \omega_i, \rho_j^{\vee} \rangle = \delta_{i,j}$. The set $\Omega$ of all weights $\mu$ is a full-dimensional $W$-lattice in $V$ and called the **weight lattice** of $R$. By definition, it is the dual lattice of the coroot lattice, that is, $\Omega^* = \Lambda$.

Assume that $V = V^{(1)} \oplus \dots \oplus V^{(k)}$ is the direct sum of proper orthogonal subspaces and that, for each $1 \le i \le k$, there is a root system $R^{(i)}$ in $V^{(i)}$. Then $R := R^{(1)} \cup \dots \cup R^{(k)}$ is a root system in $V$ called the **direct sum** of the $R^{(i)}$. If a root system is not the direct sum of at least two root systems, then it is called **irreducible**, see [Bou68, Ch. VI, §1.2].

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,7,8}$, $F_4$ and $G_2$. These are explicitly given in [Bou68, Pl. I - IX].

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]. If $R$ is irreducible and $B$ is a fixed base, then there exists a unique positive root $\rho_0 \in R^+$, so that, for all $\rho \in 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**.

**Example A.1.** For $n = 1$, a root system in $\mathbb{R}$ must be of the form $R = \{\pm \rho\}$ for some $\rho \in \mathbb{R}_{>0}$, which is the only base element and the highest root. It admits the reflection at the origin $s_{\rho} = -1$ and so the Weyl group is $W = \{\pm 1\}$. The fundamental Weyl chamber is $\Lambda = \mathbb{R}_{>0}$ and the coroot is $\rho^{\vee} = 2\rho/\langle \rho, \rho \rangle = 2/\rho$. For $\omega \in \mathbb{R}$ to be the fundamental weight, we require $1 = \langle \omega, \rho^{\vee} \rangle = 2\omega/\rho$, that is, $\omega = \rho/2$. When we choose $\rho = 2$, then $R$ admits the self-dual lattice $\Omega = \Lambda = \mathbb{Z}$.

For $n = 2$, the irreducible root systems are depicted in Figures 2 to 5. The roots are depicted in green, the base in red and the fundamental weights in blue. The gray shaded region is a Voronoï cell of the coroot lattice $\Lambda$: we have

<footnote>$^5$This is the definition given in [Bou68, Ch. VI, §1, Déf. 1] plus the “reduced” property R4.</footnote>
two squares ($C_2$ and $B_2$) and two hexagons ($A_2$ and $G_2$). The blue shaded triangle is a fundamental domain of the semi-direct product $W \times \Lambda$.

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

$$ 
\begin{aligned}
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{aligned}
 $$

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

$$ 
\begin{aligned}
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{aligned}
 $$

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

$$ 
\begin{aligned}
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{aligned}
 $$

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

$$ 
\begin{aligned}
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{aligned}
 $$

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