Philippe Moustrou
email: philippe.moustrou@math.univ-toulouse.fr

Cordian Riener
email: cordian.riener@uit.no

Hugues Verdure
email: hugues.verdure@uit.no

Symmetries in polynomial optimization

This chapter investigates how symmetries can be used to reduce the computational complexity in polynomial optimization problems. A focus will be specifically given on the Moment-SOS hierarchy in polynomial optimization, where results from representation theory and invariant theory of groups can be used. In addition, symmetry reduction techniques which are more generally applicable are also presented.

Introduction

Symmetry is a vast subject, significant in art and nature. Mathematics lies at its root, and it would be hard to find a better one on which to demonstrate the working of the mathematical intellect.

Hermann Weyl

Polynomial optimization is concerned with optimization problems expressed by polynomial functions. Problems of this kind can arise in many different contexts, including engineering, finance, and computer science. Although these problems may be formulated in a rather elementary way, they are in fact challenging and solving such problems is known to be algorithmically hard in general. It is therefore beneficial to explore the algebraic and geometric structures underlying a given problem to design more efficient algorithms, and a kind of structure which is omnipresent in algebra and geometry is symmetry. In the language of algebra, symmetry is the invariance of an object or a property by some action of a group. The goal of the present chapter is to present techniques which allow to reduce the complexity of an optimization problem with symmetry. Since it is impossible to give an exhaustive and detailed description of this vast domain, our goal here is to focus mainly on the Moment-SOS hierarchy in polynomial optimization and elaborate how the computation of such approximations can be simplified using results from representation theory and invariant theory of groups. In addition to these approaches we also mention some more general results, which allow to reduce the symmetry directly on the formulation of the polynomial optimization problem.

Overview

We begin first with a short presentation of the basic Moment-SOS hierarchy in global polynomial optimization and semidefinite programming in the following Section. We do not give a very extended exposition of this topic but limit Section 2 to defining the concepts which are essential for this chapter. Section 3, which is devoted to the representation theory of (finite) groups, lays out a first set of tools allowing for reduction of complexity. We begin in Subsection 3.1 with a survey of the central ideas of representation theory from the point of view of symmetry reduction, where the main focus is on Schur's Lemma and its consequences. Subsection 3.2 then gives a short collection of central combinatorial objects which are used to understand the representation theory of the symmetric group. Finally, Subsection 3.3 outlines how representation theory can be used to simplify semidefinite programs via blockdiagonalization of matrices which are commuting with the group action. Building on representation theory we then turn to invariant theory in Section 4 which allows to closer study the specific situation of sums of squares which are invariant by a group. We begin with a basic tutorial on invariant theory in Subsection 4.1. Since this theory is easier in the particular situation of finite reflection groups, we put a special emphasis on these groups. Following this introduction we show in Subsection 4.2 how the algebraic relationship between polynomials and invariant polynomials can be used to gain additional understanding of the structure of invariant sums of squares. These general results are then exemplified in Subsection 4.3 for the case of symmetric sums of squares. Finally, Section 5 highlights some additional techniques for symmetry reduction: firstly, we overview in Subsection 5.1 how rewriting the polynomial optimization problem in terms of invariants and combining it with the semialgebraic description of the orbit space of the group action can be used. In Subsection 5.2, we show that even in situations where Schur's Lemma from representation theory does not directly apply, one can already obtain good complexity reduction by structuring computations per orbit, and we illustrate this idea in the context of so-called SAGE certificates. We conclude, in Subsection 5.3 with some results guaranteeing the existence of structured optimizers in the context of polynomial optimization problems with symmetries.

As motivated above, the task of finding the optimal value of a such problems arises naturally in many applications. However, it is also known that this class of problems is algorithmically hard ( [START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF]) and a given problem might be practically impossible to solve. One approach to overcome such challenges consists in relaxing the problem: instead of solving the original hard problem, one can relax the hard conditions and define a new problem, easier to solve, and whose solution might still be close to the solution of the original problem. This idea has produced striking new ways to approximate hard combinatorial problems, such as the Max-Cut problem [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF]. One quite successful approach to relax polynomial optimization problems uses the connection of positive polynomials to moments and sums of squares of polynomials. We shortly outline this approach in the beginning since a big focus of this chapter deals with using symmetries in this setup. The overview we give here is short and a reader who is not familiar with the concepts is also advised to consult [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF][START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF] and in particular the original works by Lasserre [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] and Parrilo [START_REF] Parrilo | Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization[END_REF]. For simplifications we explain the main ideas only in the case of global optimization, i.e., when the additional polynomial constraints are trivial. In this case the problem we are interested to solve is to find

* = inf { ( ) : ∈ R } . ( 2
)
This problem is in general a non-convex optimization problem and it can be beneficial to slightly change perspective in order to obtain the following equivalent formulations which are in fact convex optimization problems. Firstly, one can associate to a point ∈ R the Dirac measure which leads to the following reformulation of the problem:

* = inf ∫ ( ) ( ) : ∫ 1 ( ) = 1 , (3)
where the infimum is considered over all probability measures supported in R . Since the Dirac measures of every point are feasible solutions this reformulation clearly yields the same solution. Secondly, one can also reformulate in the following way:

* = sup { : ( ) -≥ 0 ∀ ∈ R } . (4)
It follows from results of Haviland [START_REF] Haviland | On the momentum problem for distribution functions in more than one dimension. ii[END_REF] that both of the above presented reformulations are dual to each other. Even though the second formulation is equivalent from the algorithmic perspective, it points to the core of the algorithmic hardness of the polynomial optimization problem: it is algorithmically hard to test if a given polynomial ∈ R[ 1 , . . . , ] is non-negative, i.e., if ( ) ≥ 0 for all ∈ R . Therefore an approach to obtain approximations for * which are easier to calculate consists in replacing this condition with one that is easier to check, but still ensures non-negativity. We say that a polynomial ∈ R[ 1 , . . . , ] is a sum of squares (SOS) if it can be written as = 2 1 + . . . + 2 for some polynomials 1 , . . . , ∈ R[ 1 , . . . , ]. Clearly every such polynomial is also non-negative and we can consider the problem = sup { : ( ) -is a SOS} .

(

) 5
Clearly we have ≤ * , and as not every non-negative polynomial is a sum of squares, as was shown by Hilbert [START_REF] Hilbert | Über die Darstellung definiter Formen als Summe von Formenquadraten[END_REF], this inequality will not be sharp in general. On the other hand, having a concrete decomposition into sums of squares provides an algebraic certificate of non-negativity. So one obtains an algebraically verifiable proof for the solution of the bound. This strengthening of the optimization problem gives, on the dual side, a relaxation of the moment formulation. The main feature which makes this approach also interesting for practical purposes comes from the fact that one can find a SOS-decomposition with the help of semidefinite programming. This was used by Lasserre [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] to define a hierarchy for polynomial optimization based on the sums of squares strengthening [START_REF] Basu | Bounding the equivariant betti numbers of symmetric semi-algebraic sets[END_REF] and the corresponding relaxation of (3). In the context of polynomial optimization on compact sets semi algebraic sets this yields (some additional assumptions) yields a converging sequence of approximations each of which can be obtained by a semidefinite program (see [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF][START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF] for more details on these hierarchies).

Semidefinite programming

Semidefinite programming (SDP) is an optimization paradigm which was developed in the 1970s as a generalization of linear programming. The main setup is to maximize/minimize a linear function over a convex set which is defined by the requirement that a certain matrix is positive semidefinite. We denote by Sym (R) the set of all real symmetric × matrices. Then a matrix ∈ Sym (R) is called positive semidefinite if ≥ 0 for all ∈ R . In this case, we write 0. Furthermore for , ∈ Sym (R) we consider their scalar product

, = Tr( • ).
The set of all symmetric matrices ∈ Sym (R) which are positive semidefinite defines a convex cone inside Sym (R). With these notations we can define what an SDP is.

Definition 1 Let , 1 , . . . , ∈ Sym (R) be symmetric matrices and let ∈ R Ṫhen a semidefinite program is an optimization problem of the form * := inf , . . , = , 1 ≤ ≤ , 0, where ∈ Sym (R) .

The feasible set

L := { ∈ Sym (R) : , = , 1 ≤ ≤ , 0}
is a convex set.

The main feature which spiked the interest in this class of optimization problem is that they are on the one hand practically solvable (see [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF][START_REF] Ramana | An exact duality theory for semidefinite programming and its complexity implications[END_REF] for more details) but on the other hand can be used to design good approximation of otherwise algorithmically hard optimization problems (see for example [START_REF] Wolkowicz | Handbook of semidefinite programming: theory, algorithms, and applications[END_REF] for a detailed overview).

The Lovász number of a graph

One example in which SDPs have proven to be especially powerful is in combinatorial optimization. In fact the seminal paper [START_REF] Lovász | On the shannon capacity of a graph[END_REF] in which Lovász introduced the parameter defined below as the solution to a semidefinite program was one of the first instances where the formulation of SDPs arose. The combinatorial problem for which these notions were designed is related to the following parameters of a graph. Definition 2 Let Γ = ( , ) be a finite graph.

1. A set ⊂ is called independent, if no two elements in are connected by an edge. Let (Γ) denote the cardinality of the largest independent set in Γ. 2. For ∈ N a -coloring of the vertices of Γ is a distribution of colors to the vertices of Γ such that two neighbouring vertices obtain different colors. The number (Γ) denotes the smallest such that there is a -coloring of the vertices in Γ.

Let = 1 , . . . , and ⊂ be any independent vertex set. We consider the characteristic function 1 of . Using this function, we can construct the following × matrix :

, = 1 | | 1 ( )1 ( ).
It is clear that ∈ Sym (R). Furthermore, clearly 0. Additionally, since 1 is the characteristic function of and consists only of vertices that do not share an edge, the following three properties of the matrix hold:

1. , = 0 if { , } ∈ , 2. ∈ , = 1, 3. { , } ∈ × , = | |.
With these properties of in mind, one defines the -number of a graph Γ. Definition 3 Let Γ = ( , ) be a graph with vertex set = { 1 , 2 , . . . , }. Then the -number of Γ is defined as the solution to the following SDP:

(Γ) = sup , , : ∈ Sym (R), 0 , = 1, , = 0 ∀( , ) ∈ (6)
Note that the above mentioned graph invariants are known to be hard to compute (see [START_REF] Gare | Some simplified np-complete problems[END_REF][START_REF] Karp | Reducibility among combinatorial problems[END_REF]). On the other hand, the -number is defined as the optimal solution of a semidefinite program and thus easier to calculate. In fact, Lovász could show the following remarkable relationship.

Theorem 1 (Sandwich theorem) With the notions defined above we have:

(Γ) ≤ (Γ) ≤ (Γ)
Furthermore, for the class of perfect graphs the -number actually provides a sharp bound. Thus, in these cases, and as (Γ) is an integer, semidefinite programming yields polynomial time algorithms for computing these graph parameters. Following Lovász's work, various different SDP approximations of hard problems have been proposed, for instance in coding theory and sphere packing (see [START_REF] Gijswijt | New upper bounds for nonbinary codes based on the terwilliger algebra and semidefinite programming[END_REF][START_REF] Laurent | Strengthened semidefinite programming bounds for codes[END_REF][START_REF] Bachoc | New upper bounds for kissing numbers from semidefinite programming[END_REF][START_REF] De Laat | A semidefinite programming hierarchy for packing problems in discrete geometry[END_REF][START_REF] De Laat | The Lasserre hierarchy for equiangular lines with a fixed angle[END_REF]).

Connecting SDPs with sums of squares

In the context of polynomial optimization the relation to semidefinite approximations comes through the following observation originally due to Powers and Wörmann [START_REF] Powers | An algorithm for sums of squares of real polynomials[END_REF] that one can obtain a sums of squares decomposition of a given polynomial via the so-called Gram Matrix method, which transfers this question into a semi-definite program. This connection is established in the following way: Let ∈ R[ 1 , . . . , ] be a polynomial of even degree 2 . With a slight abuse of notation we denote by a vector containing all + monomials in the variables 1 , . . . , of degree at most . Thus, every polynomial = ( ) of degree is uniquely determined by its coefficients relative to . Now assume that decomposes into a form = ( ( )) 2 with polynomials of degree at most .

Then with the above notation we can rewrite this as

= ( ) ,

where now each denotes the coefficient vector of the polynomials ( ). In this case the matrix := is positive semi-definite. Since by the so called Cholesky decomposition every positive semidefinite matrix ∈ Sym (R) can be written in the form = for some ∈ R we see that the above line of argument is indeed an equivalence and so the existence of a sum of squares decomposition of follows by providing a feasible solution to a semi-definite program, i.e we have Proposition 1 A polynomial ∈ R[ ] of degree 2 is a sum of squares, if and only if there is a positive semi-definite matrix with = .

With this observation the formulation (5) can be directly transferred into the framework of semidefinite programming. This first approximation can already yield good bounds for the global optimum * and in particular in the constraint case, it can be developed further to a hierarchy of SDP-approximations: for a given optimization problem in the form (2) which satisfies relatively general conditions on the feasible set one can construct a hierarchy of growing SDP-approximations whose optimal solutions converge towards the optimal solution of the initial problem. This approach gives a relatively general method to approximate and in some cases solve the initial problem.

Even though the Moment-SOS formulation described above yields a computational viable way to approximate the optimal solution the dimension of the matrices in the resulting SDPs can grow fast with the problem size. This is why this approach is limited to small or medium size problems unless some specific characteristics are taken into account. The focus of this chapter is on presenting ways to overcome this bottleneck in the case when additional symmetry is present in the problem.

Using Representation theory in SDPs for sums-of-squares

Representation theory is a branch of mathematics that studies symmetries and their relation to algebraic structures. More concretely, it studies the ways in which groups can be represented as linear transformations of vector spaces by representing the elements of the groups as invertible matrices. In this way it becomes possible to examine the structure of the group using the tools of linear algebra, making easier the study of structural algebraic properties of the group. Representation theory has also proven to be a powerful tool to simplify computations, in the situation where a group action is assumed on a vector space of matrices. In this situation we can use representation theory to describe the set of matrices stabilized by the action in a simplified way, reducing the sizes of the matrices as well as the dimension of the matrix spaces. In turn, this allows to study other algebraic properties, such as positive semidefiniteness of the invariant matrices in a more efficient way. This computational aspect of representation theory gives rise to practical applications in many fields, including physics, chemistry, computer science, and engineering. For example, it can be used to study the behavior of particles in quantum mechanics and the properties of molecules in chemistry and many more (see for example [START_REF] Judd | Lie groups in atomic and molecular spectroscopy[END_REF][START_REF] Turski | Geometric fourier analysis of the conformal camera for active vision[END_REF][START_REF] Wigner | Reduction of direct products and restriction of representations to subgroups: The everyday tasks of the quantum theorists[END_REF][START_REF] Hannabuss | Sound and symmetry[END_REF][START_REF] Bien | Constructions of telephone networks by group representations[END_REF]). In this section, we outline the basic ideas of representation theory and its use in particular in semidefinite programming, where representation theory has successfully served as a key for many fascinating applications (see [START_REF] Bachoc | Invariant semidefinite programs[END_REF][START_REF] Vallentin | Symmetry in semidefinite programs[END_REF] for other tutorials on the topic). Our main focus here lies in the reduction of semi-definite optimization problems and sums of squares representations of invariant polynomials. We start by providing a basic introduction to representation theory. A comprehensive and approachable introduction to this topic can be found in Serre's book [START_REF] Serre | Linear representations of finite groups[END_REF]. Further readings on the subject can be found in [START_REF] Stanley | Enumerative combinatorics volume 1 second edition[END_REF][START_REF] Stiefel | Group theoretical methods and their applications[END_REF][START_REF] Fulton | Representation theory: a first course[END_REF][START_REF] James | The representation theory of the symmetric groups[END_REF].

Basic representation theory

We begin by introducing the central definitions of representation theory. Definition 4 Let be a group.

1. A representation of is a pair ( , ), where is a vector space over a field K and : → GL( ) is a group homomorphism from to the group of invertible linear transformations of . The degree of the representation is the dimension of the vector space . 2. Two representations ( , ) and ( ′ , ′ ) of the same group are considered equivalent, or isomorphic, if there exists an isomorphism : → ′ such that ′ ( ) = ( ) -1 for all ∈ . 3. Given a representation ( , ), we can associate to it its character : → K, which is defined as ( ) = Tr( ( )).

Remark 1 A character of a group is a class function: it is constant on the conjugacy classes of .

If is a finite-dimensional vector space, we can identify the image of under as a matrix subgroup ( ) of the invertible × matrices with coefficients in K by choosing a basis for . We will denote the matrix corresponding to ∈ as ( ) and refer to the family { ( ) | ∈ } as a matrix representation of .

Examples of representations

To give a selection of examples, we consider the group of permutations of a set = {1, 2, . . . , }. The group has several representations:

1. The trivial representation = C with ( ) = for all ∈ and ∈ C. This trivial representation can analogously be defined for all groups. 2. The natural representation of on C . In this representation, acts linearly on the -dimensional space

= C = =1 C .
For ∈ , we define • = ( ) and extend this to a linear map on . With respect to the basis 1 , . . . , we obtain thus a matrix representation given by permutation matrices which are defined as ( ) = ( ) ∈ C × with entries

= ( ), = 1, if ( ) = 0, else.
-algebras C[ 1 , • • • , ] -→ C[ 1 , • • • , ].
In this case we write for the image of a polynomial under the action of . This notation analogously applies to more general groups. 4. The regular representation, where ( , •) acts on the vector space

C = ∈ C
with formal symbols ( ∈ ) via ( ) = • . Also, this regular representation can analogously be defined for other finite groups.

The notion of -module

Another way to define representations is to consider the linear action of a group on a vector space which gives the structure of a -module. A -module is an abelian group on which the action of respects the abelian group structure on M. In the case when is a vector space , this just means that the group action is compatible with the operations on . Given a vector space that is a -module, we can define a map : → GL( ) that sends an element ∈ to the linear map ↦ → on . This map is then a representation of . Thus in the context of linear spaces, the notions of -modules and representations of are equivalent, and it can be more convenient to use the language of -modules. In this case, we call a linear map : → between two -modules a -homomorphism if ( ( )) = ( ( )) for all ∈ and ∈ .

The set of all -homomorphisms between and is denoted by Hom ( , ). Two -modules are considered isomorphic (or equivalent) as -modules if there exists a -isomorphism from to .

Given a representation , the set of all -homomorphisms from to itself is called the endomorphism algebra of . It is denoted by End( ). If we have a matrix representation ( ) of a group , the endomorphism algebra corresponds to the commutant algebra Com(( ( )). This is the set of all matrices commuting with the group action, i.e., Com( ( )

) := { ∈ C × such that ( ) = ( ) for all ∈ }.
When studying the action of a group on a vector space , it is important to consider subspaces that are closed under the action. Such a subspace is called a subrepresentation or -submodule of . If a representation has a proper submodule, it is called reducible. If the only submodules of are and the zero subspace, the representation is called irreducible.

Decomposition of the natural representation of

Consider the natural representation of on the -dimensional vector space C . This representation is not irreducible. It has in fact two non-trivial subrepresentations, namely

1 = C • ( 1 + 2 + . . . + ) and 2 = ⊥ 1
the orthogonal complement of 1 for the usual inner product. Clearly, 1 is irreducible since it is one-dimensional. Furthermore, also 2 is in fact irreducible.

In the previous example, the vector space is an orthogonal sum of irreducible representations. This is generally the case when the order of the group is not divisible by the characteristic of the ground field. In this case, a -invariant inner product can be defined starting from any inner product •, • via

, = 1
| ] ∈ ( ), ( ) .
The existence of such a -invariant scalar product is in fact the key to the following Theorem.

Theorem 2 (Maschke's Theorem) Let be a finite group and consider a representation ( , ) defined over a field with a characteristic which is prime to | |. Then, for every subrepresentation we have that the orthogonal complement of with respect to •, • is also a subrepresentation.

Remarks on Maschke's Theorem

As a consequence of Maschke's Theorem, every reducible representation can be decomposed as an orthogonal sum of irreducible representations. Note that such a decomposition is not necessarily unique. Indeed, if we consider a group which acts trivially on a -dimensional vector space, every one-dimensional subspace is an irreducible subrepresentation. Furthermore, the assumption that the group is finite is not necessary and a -invariant inner product also exists in the case of compact groups. So, a version of Maschke's theorem also holds, for example, for compact groups, like ( ).

A very central statement in representation theory, which is, in particular, the key to the symmetry reductions in the further sections, is the following statement which goes back to Schur.

Theorem 3 (Schur's Lemma) Let and be two irreducible -modules of a group

. Every -endomorphism from to is either zero or invertible. Furthermore, End( ) is a skew field over K. In particular, if the ground field K is algebraically closed, every invariant endomorphism between and is a scalar multiple of the identity.

Corollary 1 Let be a complex irreducible -module and •, • be an invariant Hermitian form on . Then •, • is unique up to a real scalar multiple.

One can define an inner product on the set of complex valued functions on a finite group by

, = 1 | | ∈ ( ) ( ).
Using Schur's Lemma, one can show the following important property of irreducible characters.

Theorem 4 Let be a finite group and K be algebraically closed. Then, for every pair of characters ( , ) corresponding to a pair of non-isomorphic irreducible representations we have , = 0.

Moreover, the set of irreducible characters { , ∈ } form an orthonormal basis for the K-vector space of class functions of .

Recall that a class function on is a function → K which is constant on the different conjugacy classes of . Therefore, the following is a direct consequence.

Corollary 2 Assume that is finite. Then there exists a finite number of nonequivalent irreducible representations of . If K is algebraically closed, this number is equal to the number of conjugacy classes of .

Motivated by the notion of irreducible representations is the following notion of the isotypic decomposition of a representation. Here, isotypic means that we aim to decompose a representation as a direct sum of subrepresentaions, where each summand is the direct sum of equivalent irreducible subrepresentations. Specifically, for a finite group , suppose that I = { 1 , 2 , . . . , } are all the isomorphism classes of irreducible representations of . Then the isotypic decomposition of is a decomposition

= =1 =1
, where each is a subrepresentation of that is equivalent to the irreducible representation . In other words, for each , there exist -isomorphisms , :

→ , for all 1 ≤ ≤

The subspace

= =1
is called the isotypic component associated of type . Since there is a bijection between the set of characters and the set of isomorphism classes of representations, we can also index the isotypic components of a representation by the corresponding irreducible character. We then denote by the isotypic component of associated to the irreducible representation of character . The resulting isotypic decomposition of

= =1 =
is unique up to the ordering of the direct sum.

Computing an isotypic decomposition

Using the characters of the irreducible representations, it is possible to calculate the isotypic decomposition as images of the projections

: -→ ↦ -→ dim | | ∈ ( ) • (7)
where is the character associated to the irreducible representation .

Combining the isotypic decomposition with Schur's Lemma, we obtain the following for representations defined over C.

Corollary 3 Let

:= 1 1 ⊕ 2 2 ⊕ . . . ⊕
be a complete decomposition of a representation over C such that dim = . Then we have:

1. dim = 1 1 + . . . , 2. End ≃ =1 C × .

Let be the character of and the character of

then we have , = . 4. There is a basis of such that a. The matrices of the corresponding matrix group ( ) are of the form

( ) = =1 =1 ( ) ( ),
where ( ) ( ) is a matrix representation of corresponding to . b. The corresponding commutant algebra is of the form

Com ( ) ≃ =1 ( ⊗ ),
where ∈ C × and denotes the identity in C × .

A basis for as in the corollary above is called symmetry adapted basis. Given a matrix representation of a representation of a group , Corollary 3 amounts to construct a basis of such that the corresponding matrix representation has a particularly simple form. Specifically, we can decompose into a direct sum of subrepresentations , that are isomorphic to an irreducible representation of , and the matrices of the representation will be block diagonal with blocks corresponding to these subrepresentations.

How to construct a symmetry adapted basis

To construct such a basis, we consider a matrix representation corresponding to an irreducible representation of dimension and define the map

, : → for each , = 1, . . . , , as , = | | ∈ , ( -1 ) ( ).
Here, is the number of copies of that appear in the decomposition of . It can be shown (see [START_REF] Serre | Linear representations of finite groups[END_REF]Section 2.6]) that the map 1,1 is a projection from onto a subspace ,1 isomorphic to , and 1, maps ,1 onto , , which is another subrepresentation of isomorphic to . Thus we arrive at the announced decomposition and can use the maps to construct a symmetry-adapted basis.

A representation that admits a very beautiful isotypic decomposition is the regular representation of a finite group . Recall that this is defined on the vector space

= ∈ C , via ( ) ( ℎ ) = •ℎ for every , ℎ ∈ .
| | = dim = ∈I (dim ) 2 .

Cyclic permutation matrices and the associated commutant

Consider the cyclic group 4 and let be a generating element of this group, i.e., 4 = { 0 , 1 , 2 , 3 }. The regular representation of this group is of dimension 4. It can be defined as a matrix representation via the cyclic permutation matrices given via

↦ → ( ) = 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 .
Furthermore, 4 has 4 pairwisely non-isomorphic irreducible representations, each of which is one-dimensional and we get these representations via

: -→ C ↦ -→ 2 i 4
for 0 3. With the projection defined above in [START_REF] Basu | On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities[END_REF] we obtain that the symmetry adapted basis

:= {(1, 1, 1, 1), (1, i, -1, -i), (1, -1, 1, -1), (1, -i, -1, i)} .
With respect to this basis, the representation is given via the diagonal matrix

↦ → ˜ ( ) = 1 0 0 0 0 i 0 0 0 0 -1 0 0 0 0 -i
Now, consider a circulant matrix, i.e., a matrix of the from := .

Clearly, this matrix commutes with the matrix representation and doing the change of basis to the symmetry adapted basis we obtain

˜ = + + + 0 0 0 0 + i --i 0 0 0 0 -+ - 0 0 0 0 -i -+ i
More generally, for the cyclic group we see that this regular representation will contain irreducible representations 0 , . . . , -1 , all of which are 1-dimensional and given by : ↦ →

2 i
, and corresponding symmetric adapted bases is also known as the Fourier-basis.

Complex irreducible versus real irreducible

The statements in Corollary 3 rely on the ground field to be algebraically closed. Therefore, a little bit of caution is necessary when working, for example, over the real numbers. Since this will be important for optimization we briefly highlight this situation. For a real irreducible representation ( , ), there are two possible situations that lead to three different types (see [START_REF] Serre | Linear representations of finite groups[END_REF]Section 13.2]):

1. If the complexification ⊗ C is also irreducible (type I), then representation can be directly transferred from ⊗ C to and we can directly apply Corollary 3. 2. If the complexification ⊗ C is reducible, then it will decompose into two complex-conjugate irreducible -submodules 1 and 2 . These submodules may be non-isomorphic (type II) or isomorphic (type III).

If the complexification ⊗C of a real -module has the isotypic decomposition

⊗ C = 1 ⊕ • • • ⊕ 2 ⊕ 2 +1 ⊕ • • • ⊕ ℎ ,
where each pair ( 2 -1 , 2 ) is complex conjugate (1 ≤ ≤ ) and 2 +1 , . . . , ℎ are real, we can keep track of this decomposition in the real representation, in the following way: consider a pair of complex conjugated -modules

( 2 -1 , 2 ) with = dim 2 -1 . Then a basis B 2 -1 of 2 -1 and the conjugated basis B 2 = B 2 -1 of 2 can be used to obtain a real basis of 2 -1 ⊕ 2 by considering 1 + ′ 1 , . . . , + ′ , 1 i ( 1 -′ 1 ), . . . , 1 i ( -′ )
where ∈ B 2 -1 and ′ ∈ B 2 -1 . Therefore, with a slight abuse of notation, we can translate the isotypic decomposition of ⊗ C above to a decomposition into real irreducible representations via

= ( 1 + 2 ) ⊕ 1 i 1 -2 ⊕ • • • ⊕ ( 2 -1 + 2 ) ⊕ 1 i 2 -1 -2 ⊕ 2 +1 ⊕ • • • ⊕ ℎ.
Note that in the case of a real irreducible representation , also the structure of the corresponding endomorphism algebras differs from the complex case, depending on which of the three cases we are in. Indeed, in the case of non-algebraically closed fields, the second statement in Schur's Lemma 3 only yields that End( ) is isomorphic to a skew field. There are exactly three skew fields over R, namely R itself, C, and the Quaternions H, and these three cases exactly correspond to the types discussed above. Therefore, in the case of a real irreducible representation, we get that the endomorphism algebra is isomorphic to R if it is of (type I), it is isomorphic to C if we are of (type II) and it is isomorphic to H in the case of (type III).

Real symmetry adapted basis for circulant matrices

We consider again the cyclic group 4 acting linearly on R 4 by cyclically permuting coordinates. This representation is isomorphic to the regular representation, and we know a complex symmetry-adapted basis. If we denote by (1) , . . . , (4) the basis elements of the symmetry-adapted basis given above, then the 4 real vectors

B := (1) , (3) , (2)
+ (4) , 1 i ( ( 2) - (4) ) yield a decomposition into real irreducible representations. The matrix considered in the example above is then of the form

B = + + + 0 0 0 0 -+ - 0 0 0 0 --+ 0 0 - - .
We thus see that the two non-real irreducible representations of 4 give one real irreducible representation. We are in (type II) as these two complex irreducible representations are not isomorphic and therefore the corresponding endomorphism algebra decomposes into the blocks as above. Note that in the case of a symmetric circulant matrix we would have obtained the same diagonal form as in the complex case.

Representation theory of

The representation theory of the symmetric group, which is of particular importance due to its historical significance and connections to combinatorics, is outlined here for future reference. It is known that the conjugacy classes of the symmetric group correspond one-to-one with partitions of , which are non-decreasing sequences of positive integers that sum to . A Young diagram, corresponding to a partition

= ( 1 , • • • , ) ⊢
, is a collection of cells arranged in left-aligned rows, with 1 cells in the top row, 2 cells in the row below, and so on.

Example of a Young diagram

Consider the partition (4, 3, 1) ⊢ 8. To this partition we associate the following Young diagram:

A Young tableau of shape is obtained by filling the cells of the Young diagram of with the integers 1 to . Two tableaux are considered equivalent if their corresponding rows contain the same integers. Given a tableau , its row-equivalent class { } can be visualized by removing the vertical lines separating the boxes in each row. Such a row equivalence class is also called a tabloid. We call the formal K-vector space M which is spanned by all -tabloids the partition module associated to .

Example of equivalent Young tableaux

Continuing with the above example and the partition (4, 3, 1) ⊢ 8 we have, for example, the following two equivalent tableaux .

We can represent the row equivalence class to which these two tableaux belong by

{ 1 } = { 2 } = 3 1 7 5 4 6 2 8
.

Combinatorics reveals further that the associated permutation module M (4,3,1) is spanned by the 8! 4!•3! = 280 different tabloids.

Given a tableau , we denote its columns by 1 , • • • , and consider the column stabilizer subgroup CStab ⊂ defined by

CStab = 1 × 2 × • • • × .
This setup of notations allows to define the following class of representations, which turn out to give a complete list of irreducible representations in the case char(K) = 0. Definition 5 Let ⊢ be a partition. For a Young tableau of shape we define

:= ∈CStab sgn( ){ }.
Then, the Specht module ⊆ M associated to is the K-vector space spanned by the corresponding to all Young tableaux of shape .

A tableau is standard if every row and every column is filled in increasing order and it can be shown that the set of Young tabloids corresponding to standard Young tableaux is a minimal generating set of a Specht module. More importantly we have the following theorem:

Theorem 6 If char(K) = 0 then the set { , ⊢ } is the set of non-isomorphic irreducible representations of .
The Specht modules of 3

The Specht modules, and hence the irreducible representations of 3 , are the following three.

(3) = < 1 2 3 >,

(2,1) = 1 2 3 -3 2 1 , 1 3 2 -2 3 1 , (1,1,1) = 1 2 3 - 2 1 3 - 3 2 1 - 1 3 2 + 2 3 1 + 3 1 2 .
We further give the associated characters. These are constant on the 3 conjugacy classes of 3 , namely 1 = {Id}, 2 = {(12), ( 13), [START_REF] Friedl | Reflection groups, reflection arrangements, and invariant real varieties[END_REF]} and 3 = {(123), (132)}. (3)

1 1 1 (2,1) 2 0 -1 (1,1,1) 1 -1 1
This understanding of the irreducible representations allows us to examine the following example.

Diagonalization of a 3 -invariant Gram matrix

We consider the permutation action of the group 3 on R 3 and construct a Gram Matrix of the invariant scalar product. Since it is supposed to be 3 -invariant, we find , 3 = for = 1..3, and , 3 = for ≠ . The associated Gram matrix is therefore of the form .

We further have seen that this representation decomposes into two irreducible ones, one of them being the trivial one, the other one being (2,1) . Thus, we find that, in this situation, the vectors { 1 + 2 + 3 , 1 -2 , 1 -3 } form a symmetry adapted basis. Indeed, with respect to this basis, the Gram matrix is of the form

+ 2 0 0 0 - 0 0 0 - .

Using representation theory to simplify semidefinite formulations

We have seen that Schur's Lemma allows for a block-diagonalization for matrices which commute with a given group action. Now assume that (R , ) is an -dimensional representation of a finite group . As we can always choose an orthonormal basis for R with respect to a -invariant scalar product, we can assume without loss of generality that the corresponding matrices are unitary, i.e we have ( ) ( ) = Id for all ∈ . Now this representation naturally carries over to a representation on Sym (R) via := ( ) ( ) , for ∈ Sym (R) and ∈ .

A set L ⊆ Sym (K) is called invariant with respect to if for all ∈ L we have ∈ L, for all ∈ . A linear functional , is -invariant, if , = ,
for all ∈ and an SDP is -invariant if both the cost function , as well as the feasible set L are -invariant.

Definition 6 For a given SDP we consider

* := inf , s.t. , = , 1 ≤ ≤ , = for all ∈ , 0, where ∈ Sym (R) .
Clearly, * ≤ * . Even more, we have the following. Notice that the additional condition we impose in the above formulation, namely that = for all ∈ clearly reduces the dimension of the space of possible solutions and therefore the number of free variables in the formulation. This first step of a reduction to orbits therefore reduces the intrinsic dimension of the problem. But in order to further simplify the formulation we also notice that Theorem 7 allows us to restrict to invariant matrices (i.e., the commutant of the associated matrix representation). By Schur's Lemma we know that we can find a basis that block-diagonalises the matrices in this space. Let

Sym (R) = 1,1 ⊥ 1,2 ⊥ 1, ⊥ 2,1 ⊥ • • • ⊥ ,
be an orthogonal decomposition into irreducibles, and pick an orthonormal basis ,1, for each ,1 . Choose , : ,1 → , to obtain orthogonal bases , , = , ( ,1, ) for each , . This then gives us an orthonormal symmetry adapted basis. Now, for ever irreducible representation and every ( , ) ∈ {1, . . . , } 2 we can define zonal matrices ( , ) with coefficients ( ( , )) , := ℎ=1 , ,ℎ ( ) • , ,ℎ ( ).

These characterise invariant ∈ Sym (R) via , = =1 ( , ),
, for some ∈ Sym (R), 1 ≤ ≤ . Summing up we have provided:

Theorem 8 A -invariant SDP is equivalent to the following reduced SDP: inf , s.t. , , = , 1 ≤ , ≤ , 1 ≤ ≤ , , = =1 ( , ), , 0, where ∈ Sym (R), 1 ≤ ≤ .

Some remarks

The main work that has to be done to obtain this nice form (i.e., the actual calculation of the zonal matrices) is far from trivial. However the possible reductions can make a difference that enables one to actually compute a given SDP which otherwise might be too big to be handled by a SDP-solver. Furthermore, in the context of semidefinite programming the issue with real irreducible representations versus complex irreducible representations can be easily avoided by replacing symmetric matrices with hermitian matrices. This is why the definition of the zonal matrices was given with the complex conjugate, which is necessary only in the case of a complex symmetry adapted basis.

We want to highlight this potential reduction of complexity by studying the example of the -number introduced in Definition 3 for graphs with symmetry.

Symmetry reduction for the -number of a cyclic graph

Consider a cyclic graph shown in the picture below for = 10. The -number in this case is given by

( ) = sup , , : ∈ Sym (R), 0 =1 , = 1, , = 0 ≡ + 1 (mod ) . (8)
We see that this SDP is invariant under the natural action of the cyclic group Z/ Z. We get a symmetry adapted basis for the (complexification) of this representation through the Fourier basis, and a corresponding real decomposition. Then one obtains the following equivalent formulation for the SDP ( 8)

( ) = sup • 0 : ( 0 , . . . , ⌊ 2 ⌋ ) ∈ R ≥0 ⌊ 2 ⌋ =0 = 1, ⌊ 2 ⌋ =0 • cos( 2 ) = 0 (9)
Through this formulation of the -number as a linear program, it is possible to calculate the -number directly. Indeed, we can deduce [46, Corollary 5]

( ) = cos( / ) 1+cos ( / )
for odd , 2 for even .

Recall that our main objective is polynomial optimization. We now turn our attention to specific SDPs stemming from sums of squares approximations. Note that in this situation the action of a group on R also induces an action on the R-vector space R[ ], as we have seen before and a matrix representation ( ) for the space of polynomials of degree at most . Thus, if

= for all ∈ we can define

:= 1 | | ∈ ( ) ( ),
and will have = ( ) with the property that now commutes with the matrix representation ( ). Therefore the above methods for general SDPs can be used again to block-diagonalize the matrix and thus simplify the calculations. This was first explored in detail by Gatermann and Parillo [START_REF] Gatermann | Symmetry groups, semidefinite programs, and sums of squares[END_REF] and several other authors [START_REF] Cimprič | Sums of squares and moment problems in equivariant situations[END_REF][START_REF] Riener | Exploiting symmetries in sdprelaxations for polynomial optimization[END_REF][START_REF] Dostert | New upper bounds for the density of translative packings of three-dimensional convex bodies with tetrahedral symmetry[END_REF]. We want to highlight this in the following example.

Symmetry reduction of the SOS decomposition of a symmetric quadratic

Consider the homogeneous polynomial

= • =1 2 + • < .
We want to examine the conditions on and such that is a sum of squares. Since is homogeneous and of degree 2, a sum of squares decomposition will involve only squares of homogeneous polynomials of degree 1. In other words, by Proposition 1 we consider the vector = ( 1 , . . . , ) comprised of all monomials of degree 1 and have that the polynomial is a sum of squares if and only if we can find a positive semidefinite matrix of size × such that = .

Now, by construction, remains invariant by the permutation action of on the monomials 1 , . . . , . This action is represented by the permutation matrices, and we can therefore assume that commutes with every permutation matrix. As we have seen above, this representation decomposes into two non-isomorphic irreducible representations, one isomorphic to the trivial representation and the other one to the Specht module ( -1,1) . Therefore, in a symmetry adapted basis, we may assume that the matrix is of the from = 0 0 . . . 0 0 0 . . . 0 . . . . . . 0 0 . . .

. Doing the calculations we obtain that a sums of squares decomposition of is of the form

= ( 1 + 2 +. . .+ ) 2 + < ( -) 2 = ( +( -1) ) =1 2 +2( -) < ,
with , ≥ 0.

In the above example we have seen that the sum of squares decomposition essentially consisted of two type of summands. Firstly the square of the invariant polynomial 1 + 2 , + . . . + and summands which are squares of elements in the -orbit of 1 -2 . This observation can be made more precise with the following setup: if we want to decide for a given polynomial of degree 2 which is invariant by a group if it is a sum of squares we consider the vector space R[ ] ≤ of polynomials of degree at most , which is finite dimensional. Then the linear action of a group on R also induces a linear action on R[ ] ≤ and we can consider the isotypic decomposition

R[ ] ≤ = ∈ = ∈ =1 , ( 10
)
where the are again the non-isomorphic irreducible representations of , and any , is an irreducible representation isomorphic to . For the discussion we now assume for simplicity that every irreducible component of this decomposition is real irreducible. In this case we can construct a set of real polynomials

{ 11 , 12 , . . . , } ⊂ R[ ] ≤
with the following two properties:

1. The polynomial 1 cyclically generates 1 i.e., for every fixed the -span 1 = ,1 .

2. The polynomial ∈ , is the image of 1 under the (up to scalar multiplication) unique -isomorphism between ,1 to , . This in particular implies that generates cyclically , .

We denote by 1 , . . . , 2 R a sum of squares of elements in the vector space spanned by the polynomials 1 , . . . ,

. With this notation, and integrating the described construction with the consequences of Schur's Lemma (Theorem 3), one arrives at the following which agrees with the observation from the example above (see also [START_REF] Blekherman | Symmetric non-negative forms and sums of squares[END_REF][START_REF] Cimprič | Sums of squares and moment problems in equivariant situations[END_REF][START_REF] Gatermann | Symmetry groups, semidefinite programs, and sums of squares[END_REF][START_REF] Riener | Exploiting symmetries in sdprelaxations for polynomial optimization[END_REF][START_REF] Debus | Reflection groups and cones of sums of squares[END_REF] for more details on the following statement).

Theorem 9 With the notation defined above any -invariant polynomial of degree 2 that is a sum of squares can be written in the from

= ∈ =1 ∈
where every ∈ 1 , . . . ,

2

R . Proof Let be a sum of squares. Then there is symmetric positive semidefinite bilinear from

:

R[ ] ≤ × R[ ] ≤ → R
which is a Gram matrix for , i.e. for every ∈ R we can write

( ) = ( , ),
where stands for the vector of monomials up to degree . Since is -invariant, by linearity, we may assume that is a -invariant bilinear form. We get from Corollary 3 that ( , ) = 0 for all ∈ and ∈ , i.e., the isotypic components appearing in [START_REF] Bergeron | Algebraic combinatorics and coinvariant spaces[END_REF] are orthogonal with respect to and hence it suffices to look at : × → R individually. If = 0, there is nothing to prove. Otherwise, consider the decomposition

:= =1 , ,
where with the notation above each , is generated by the orbit of a polynomial , . We can freely identify with its complexification C since by assumption all irreducible representations are irreducible over C. Furthermore, since is positive semidefinite and 1 cylically generates 1 , we may assume that ( 1 , 1 ) > 0. We extend 1 to a basis

. ,

).

To conclude we need to see that the form is essentially , i.e., that it is obtained from by multiplication with a positive scalar. This can be done by direct calculations using the fact that each for ∈ can be expressed in the basis of , defined above. It then follows that there exists a ′ , independent on , ′ such that

( , ′ ′ ) = ′ ( , ′ ′ ).
Since and can be seen as elements of Hom ( 1 , * 1 ), applying Schur's lemma one can prove that ′ is actually independent of , ′ , that is = for some constant ∈ R * + . In analogy to the zonal matrices defined before, we can also reformulate Theorem 9 in terms of matrix polynomials, i.e., matrices with polynomial entries. To do this we define a block-diagonal symmetric matrix with blocks (1) , . . . , ( ) with the entries of each block given by:

( ) = ∈ ( • ) , . (11)
With these notations Theorem 9 can be stated in the following equivalent form.

Corollary 4 Let ∈ R[ ] ≤2 .
Then is a sum of squares if and only if

= 1 • (1) + . . . + • ( ) ,
for some symmetric and positive semidefinite matrices ∈ Mat × (R).

Remark 2

The restriction to type I real irreducible representations in the description above is mainly due to convenience of the presentation. Using the discussion in in Section 3 on real irreducible representations it is possible to generalize to type II and to adapt to type III representations.

These first examples give a hint on the power of symmetry reduction to simplify optimization problems affording some symmetries. This approach has been used quite successfully in a wide range of applications and settings. In the next section, we focus on the case of sums of squares and explore how the additional algebraic structure of polynomials can be combined with the above approach to get a better understanding of invariant sums of squares.

Invariant theory

Polynomial functions that remain unchanged under the action of a symmetry transformation naturally appeared in the previous section. Such functions are called polynomial invariants, and they play a crucial role in invariant theory, a branch of algebra that studies symmetry in algebraic structures, such as groups, rings, and fields. The structural insights into the set of invariant polynomials can give important additional comprehension and different ways of simplifications for polynomial optimization, as we will outline in this section. In order to do this, we give first an overview of the basic concepts and important results in invariant theory which will prove useful in order to take advantage of symmetries in polynomial optimization problems. For details and further insights we refer the reader to [START_REF] Sturmfels | Algorithms in invariant theory[END_REF][START_REF] Derksen | Computational invariant theory[END_REF][START_REF] Benson | Polynomial invariants of finite groups[END_REF][START_REF] Springer | Invariant theory[END_REF][START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF].

Basics of invariant theory

We begin with examining the situation of a linear action of a group on the ring of polynomials more closely. As was introduced before, given a finite group and a representation :

-→ K we can define a linear action on the polynomial functions on , denoted K[ ] via := • ( -1 ). Choosing a basis of we can identify K[ ] with K[ 1 , . . . , ] and consider the associated isotypic decomposition of the module:

K[ 1 , . . . , ] = ∈ K[ 1 , . . . , ] , (12)
where as before is the set of isomorphism classes of irreducible representations and for ∈ is a list of irreducible characters. In addition to being a K-vector space with group action, K[ 1 , . . . , ] is in fact an algebra and this additional algebraic structure also allows for a finer analysis of the group action. If corresponds to the trivial character the polynomials in K[ 1 , . . . , ] will not be affected by the action of . Polynomials with this property, i.e, elements ∈ K[ 1 , . . . , ] such that = for all ∈ are called invariant polynomials. Since the property of being invariant is not affected by addition or multiplication with other invariant polynomials the set of invariant polynomials forms a sub-algebra denoted by K[ ] . The polynomials belonging to the other isotypic components are sometimes also called semi-invariants.

The Motzkin polynomial as an example for a symmetric polynomial

We consider the group 2 acting linearly on C 2 by permuting coordinates. Then, the Motzkin polynomial

:= 4 1 2 2 + 2 1 4 2 -3 2 1 2 2 + 1
is invariant with respect to this action. In the case of invariant polynomials we also speak of symmetric polynomials.

A very useful tool to work with polynomials in invariant setting is the so-called Reynolds operator defined as follows.

Definition 7 For a finite group the map

R ( ) := 1 | | ∈ is called the Reynolds operator of .
The Reynolds operator of a finite group has the following properties:

1. R is a K[ ] -linear map. 2. For ∈ K[ ] we have R ( ) ∈ K[ ] . 3. R is the identity map on K[ ] , i.e R ( ) = for all ∈ [ ] .
Remark 3 Whereas we introduced the Reynolds operator for finite groups, it can be more generally defined for compact and reductive groups and most of the results we state for finite groups mostly can be adapted for this more general case. We refer the reader to [START_REF] Sturmfels | Algorithms in invariant theory[END_REF][START_REF] Derksen | Computational invariant theory[END_REF] for more details and algorithmic questions.

As seen above, K[ ] is a subalgebra of K[ ]. In the second half of the 19th century, invariant theory was very much concerned with the following question: is this subalgebra generated by finitely many elements? The following Theorem, proven by Hilbert in 1890, initiated modern invariant theory.

Theorem 10 (Hilbert) Let be a finite group. Then the invariant subalgebra K[ ] is generated by finitely many homogeneous invariants, i.e., there is a finite set of invariant homogeneous polynomials 1 , . . . , such that every invariant polynomial ∈ K[ ] can be written as a polynomial in 1 , . . . , . Remark 4 Hilbert himself asked in his 14th problem whether the above Theorem holds generally for all groups. Indeed, it holds for a large class of infinite groups. However, with a concrete counter example, Nagata [START_REF] Nagata | On the 14-th problem of Hilbert[END_REF] could prove in 1959 that not all invariant algebras are finitely generated.

In the case of the symmetric group the following families of generators are well known and used in many different parts of algebra and combinatorics. Definition 8 For ∈ N, consider the following two families of symmetric polynomials.

1. For 0 ≤ ≤ let := = denote the -th power sum polynomial, 2. For 0 ≤ ≤ let :

= 1≤ 1 < 2 <...< ≤ 1 2 • • •
denote the -th elementary symmetric polynomial.

Theorem 11

The two families { 1 , . . . , } and { 1 , . . . , } both are algebraically independent generating sets for the algebra of -invariant polynomials, namely

C[ 1 , . . . , ] = C[ 1 , . . . , ] = C[ 1 , . . . , ].

The Motzkin polynomial expressed in elementary symmetric polynomials

Consider the action of 2 on C 2 . Then, every symmetric polynomial can be uniquely written as a polynomial in 1 := 1 + 2 , and 2 := 1 2 , and the Motzkin polynomial from the example above can be expressed as

= 2 1 2 2 -2 3 2 -3 2 2 + 1.
Remark 5 Since both the power sum polynomials and the elementary symmetric polynomials generate the ring of symmetric polynomials, each of two families of symmetric polynomials can be expressed by the other. The expression can be deduced from the so-called Newton identities (see e.g. [START_REF] Mourrain | On the complexity of isolating real roots and computing with certainty the topological degree[END_REF]):

(-1) ( ) + =1 (-1) + ( ) -( ) = 0. ( 13
)
In contrast to the above example of the symmetric polynomials, for general groups we might need more than generators. We can, however, give a bound for the number of generators needed.

Theorem 12 (Noether's bound) Let be a finite group acting linearly on K . Then K[ ] is generated as an algebra over K by not more than +| | many homogeneous invariants of degree not exceeding | |. So, in particular, it is not guaranteed that a set of algebraically independent generators exists. However, more generally, it can be shown that the invariant ring is Cohen-Macaulay and that a Hironaka decomposition exists, i.e., that we can find algebraically independent polynomials 1 , . . . , and polynomials 1 , . . . , such that

K[ ] = =1 K[ 1 , . . . , ].
The algebraic invariant polynomials 1 , . . . , are called primary invariants, and the 1 , . . . , are called secondary invariants. With these families of polynomials, every invariant polynomial can be uniquely written in such a way that the secondary invariants appear only linearly.

Invariant polynomials for the alternating group

Consider the group 3 which is the subgroup of 3 of even permutations and define Δ = ( 1 -2 ) ( 1 -3 ) ( 2 -3 ) Then for every 3 invariant polynomial there exist two unique symmetric polynomials 0 ( 1 , 2 , 3 ) and 1 ( 1 , 2 , 3 ) such that

( 1 , 2 , 3 ) = 0 ( 1 , 2 , 3 ) + 1 ( 1 , 2 , 3 ) • Δ.
In other words, the 1 , 2 , 3 (or any other generating set for the 3 -invariant polynomials) can be used as primary invariants and Δ serves as the secondary invariant.

As we have seen now, the trivial component of the isotypic decomposition [START_REF] Bergeron | Algebraic combinatorics and coinvariant spaces[END_REF] enjoys the property of being a finitely generated K-algebra. We now turn to the other isotypic components. Let be any character of and ∈ K[ ] be an invariant polynomial. Then clearly the application

• : K[ ] -→ K[ ] ↦ -→ •

Decomposition of polynomials in two variables

We consider the case of polynomials in two variables K[ 1 , 2 ] and their relation to 2 symmetric polynomials. Here we have that K[ 1 , 2 ] is generated as an K[ 1 , 2 ] 2 -module by 1 and 1 -2 , i.e., every polynomial can be written as

= 0 + 1 • ( 1 -2 ), where 1 , 2 ∈ K[ 1 , 2 ] 2 .
Moreover, in this case the representation is in fact unique.

Definition 9 A reflection is a mapping from a Euclidean space to itself that is an isometry whose set of fixed points is a hyperplane. If is an Euclicean vector space we can view a reflection as an element in O( ) that has exactly one eigenvalue different from 1, i.e., one other eigenvalue that is -1. If ( , ) is a representation of , then ∈ is a reflection if the mapping ↦ → ( ) is a reflection and we say that is a reflection group if it is generated by reflections.

It is very important to remember that the property of being a reflection group is not a property of the group itself, but it is crucially linked to the representation. This can be seen in the following example.

Two different representations of

We consider the symmetric group . This group is generated by the transpositions

= ( , + 1) for ∈ {1, • • • , -1}.
1. Consider the defining representation of given by permuting the coordinates in R . In this representation, elements in ( ) corresponding to transpositions have the eigenvectors for ≠ , + 1 with eigenvalue 1, as well as + +1 with eigenvalue 1 and -+1 with eigenvalue -1. Therefore these elements are reflections, which geometrically correspond to the reflection through the hyperplane of equation -+1 = 0 in . With this representation is acting as a reflection group. 2. Now, let = 2 and consider the representation on

= R • 1 ⊕ R • 2 ⊕ R • 3 given by (1, 2) • 1 = 2 , (1, 2) • 2 = 1 and (1, 2) • 3 = -3 .
Then, the image of the transposition (1, 2) has eigenvalues 1, -1, -1 and thus is not a reflection. Therefore, 2 is not a reflection group if acting in this way.

The following theorem is due to Shephard, Todd, Chevalley and motivates the study of reflection groups. Theorem 14 (Shephard, Todd, Chevalley) Let be a group with a finite dimensional representation . Then the following properties are equivalent:

is a reflection group; 2. the corresponding invariant ring K[ ] is a polynomial algebra; 3. the polynomial ring

K[ ] is a free K[ ] module.
In the case of a finite reflection group the collection 1 , . . . , which generate the invariant ring are called basic invariants. These basic invariants are not unique, but their sequence of degrees ( ) := deg is unique. The following example highlights the equivalence of the statements in Theorem 14.

Invariants of a different 2 action

We consider the group 2 with the action on K 3 above such that 2 is not acting as a reflection group. Then,

K[ 1 , 2 , 3 ] = K[ 1 , 2 , 3 , 4 ] with 1 = 1 + 2 , 2 = 1 2 , 3 = 2 3 and 4 = 3 ( 1 -2 ).
Clearly, these three polynomials cannot be algebraically independent and indeed, there is an algebraic dependency between the 's, namely

2 1 3 -4 2 3 -2 4 = 0.
Similarly one can find that

K[ 1 , 2 , 3 ] is not a free K[ 1 , 2 , 3 , 4 ]-module.
Definition 10 Let be a finite reflection group. Then, the quotient K-algebra of the polynomial ring modulo the ideal generated by the non-constant elements of the invariant ring is called the covariant algebra of and denoted by K[ 1 , . . . , ] . If 1 , . . . , are a minimal set of algebraically independent generators of the invariant ring, we have

K[ 1 , . . . , ] := K[ 1 , . . . , ]/( 1 , . . . , ) K[ 1 ,..., ] .
The covariant algebra of has the structure of a -module and we find in fact the following.

Theorem 15 Let be a real reflection group acting linearly on R . Then the covariant algebra R[ 1 , . . . , ] is as -module isomorphic to the regular representation R[ ] and

R[ 1 , . . . , ] R[ 1 , . . . , ] ⊗ R R[ 1 , . . . , ]
as graded R-algebras.

In fact, for general finite groups we have the following analog which follows from the Hironaka decomposition.

Theorem 16

Let be a finite group with a linear action on a finite dimensional vector space . Let 1 , . . . , be the primary invariants and suppose that the rank

of the K[ 1 , . . . , ]-module K[ ] is . Then K[ ]/( 1 , . . . ) is isomorphic as
-module to times the regular representation.

An algorithmic approach to efficiently compute the decomposition above can for example be found in [START_REF] Hubert | Algorithms for fundamental invariants and equivariants[END_REF].

Going via -harmonic polynomials

Computing a basis of the covariant algebra may be complicated and involve calculation of a Groebner basis. We shortly mention that also the set of -harmonic polynomials defined below can be efficiently used.

Definition 11

For a polynomial = 1 , . . . , ∈ R[ 1 , . . . , ] we denote by ( ) the linear operator

( ) : R[ 1 , . . . , ] -→ R[ 1 , . . . , ] ↦ -→ | | 1 1 ... ,
i.e., ( ) is the formal sum of scaled partial derivatives considered as a linear map.

Example for ( )

Let = 2 1 + 1 2 ∈ R[ 1 , 2 , 3 ], then ( ) = 2 1 1 + 2 1 2 and
( ) 2 1 + 2 2 + 2 3 + 1 2 3 = 1 + 3 .

Definition 12

Let be a reflection group with invariant ring R[ 1 , . . . , ]. Then the R-vector space of harmonic polynomials is defined as

H := R[ 1 , . . . , ] ⊥ ,
with respect to the scalar product on R[ 1 , . . . , ] given by

•, • : R[ 1 , . . . , ] × R[ 1 , . . . , ] -→ R[ 1 , . . . , ] ( , )
↦ -→ eval (0,...,0) ( ( ) ( 1 , . . . , )) .

Now the following statement shows that -harmonic polynomials have some remarkable similarities with the covariant algebra as presented in Theorem 15. We refer the reader also to [START_REF] Bergeron | Algebraic combinatorics and coinvariant spaces[END_REF] for details on the following Theorem.

Theorem 17 Let be a real reflection group and Δ := , be the product of the linear polynomials defining the reflection hyperplanes.

The vector space of -harmonic polynomials H is generated by all partial derivatives of

Δ, i.e., H = Δ : ∈ N 0 R . 2. Furthermore, H is as -representation isomorphic to the regular representation of and R[ 1 , . . . , ] = R[ 1 , . . . , ] ⊗ R H .
Let be a finite reflection group and 1 , . . . , be generators of the invariant ring. Consider the map

Ψ : R -→ R 1 , . . . , ↦ -→ ( 1 ( 1 , . . . , ), . . . , ( 1 , . . . , )).
Then, thanks to a statement of Steinberg in [START_REF] Steinberg | Invariants of finite reflection groups[END_REF], we have

Δ = • Jac Ψ,
where ∈ R \ {0} and Jac Ψ denotes the Jacobian matrix of Ψ. The choice of fundamental invariants 1 , . . . , does not matter.

Jacobian of

For the symmetric group acting on R via coordinate permutation and

:= = =1
the power sums, we obtain Δ = < ( -) equals (up to a scalar) the determinant of the Vandermonde matrix. The form defined above Δ which is the product over all reflections ( , ) of equals therefore up to a scalar the Jacobian of Ψ.

Building on the notions of invariant theory outlined here we now can outline how to use the observation that the polynomial ring is a module over the invariant ring in the context of sums of squares formulations.

Invariant theory and sums of squares

In Section 3 where we focused on representation theory, we already saw how to apply Schur's Lemma to obtain simplifications for sums of squares computations. We shall explain how to combine the techniques developed with Schur's Lemma with results from invariant theory in the situation of symmetric sums of squares. Note that an invariant polynomial which can be expressed as a sum of squares in the ring R[ 1 , . . . , ] will not necessarily have a sum of squares decomposition in invariant polynomials, i.e.,

R[ 1 , . . . , ] R[ 1 , . . . , ] 2 ≠ (R[ 1 , . . . , ] ) 2 ,
as can be seen in the following example.

A symmetric sum of squares is not a sum of symmetric squares

Consider the symmetric sums of squares polynomial = 2 1 + 2 2 + . . . + 2 . Up to scalar multiplication there is only one symmetric polynomial of degree 1, namely 1 := 1 + 2 + ... + . Clearly, if > 1 we have • 2 1 ≠ for every ∈ R.

The above example suggests that it is at first sight not clear which algebraic property in the ring R[ ] certifies that a given invariant polynomial is a sum of squares of elements in R[ ]. However, we have seen that R[ ] is a finitely generated module over the invariant ring. This observation allows for a refined version of Theorem 9. Following the presentation in [START_REF] Debus | Reflection groups and cones of sums of squares[END_REF], we focus here mainly on finite reflection groups, since, as we have seen, their representation theory is particularly nice. However, these results can be generalized to all finite groups using the Hironaka decomposition with appropriate adaptations. We begin with the following observation which makes use of the decomposition

R[ 1 , . . . , ] ≃ R[ 1 , . . . , ] ⊗ R[ 1 , . . . , ]
provided in Theorem 15. Since the covariant algebra is isomorphic to the regular representation of , we can pick a basis := { 1 , . . . , | | }. Relatively to this basis we now construct a matrix polynomial with entries

, := R ( • ), where 1 ≤ , ≤ | |.
Since now every entry R ( • ) is by construction -invariant we can express the entries in terms of the 1 , . . . , , i.e., we obtain a matrix polynomial in new variables 1 , . . . ,

( 1 , . . . , ) ∈ R[ 1 , . . . , ] | |× | | .
Given any matrix-polynomial ( 1 , . . . , ) ∈ R[ 1 , . . . , ] × , we can construct a square matrix polynomial = . We say that a × matrix polynomial is a sum of squares matrix polynomial if it can be obtained in this way. With this notion at hand one can deduce from the decomposition in Theorem 15 the following algebraic certificate for an invariant polynomial to be a sum of squares. Proposition 2 Let be a finite reflection group and let be an invariant polynomial. Consider the polynomial ∈ R[ 1 , . . . , ] with ( 1 , . . . , ) = . Then is a sum of squares if and only if admits a representation of the form

= Tr( • ),
where is a sum of squares matrix polynomial.

The above construction works for every basis of the covariant algebra. But since we know that the group representation on the covariant algebra is the regular representation one can pick a basis that decomposes this covariant algebra into irreducible representations. We note this explicitly in the following Proposition. Note that the summation index equals the multiplicity of the corresponding irreducible representation in the isotypic decomposition, which in turn equals the dimension of the irreducible representation.

Definition 13

With the notation used above, we can construct a matrix polynomial ∈ R[ 1 , . . . , ] × for every irreducible representation ( ) of via

, = R ( , • , ), where 1 ≤ , ≤ .
Combining the above definition with the results from Schur's lemma we immediately get the following.

Theorem 18 Let be a finite reflection group with

R[ 1 , . . . , ] ≃ R[ 1 , . . . , ],
then we have

ΣR[ 1 , . . . , ] 2 ∩R[ 1 , . . . , ] =      ∈ R[ 1 , . . . , ] : = =1 Tr( • )      ,
where ∈ R[ 1 , . . . , ] × is a sum of squares matrix polynomial.

Although the above Theorem 18 is not too different in spirit from Theorem 9, it allows to transfer the decision if an invariant polynomial is a sum of squares into the invariant ring. Furthermore, this in turn allows for a more global approach. Indeed, Theorem 9 was stated for polynomials of a given degree 2 and relied in the decomposition of the space R[ 1 , . . . , ] ≤ . The use of the covariant algebra implicitly also directly yields a decomposition of the space R[ 1 , . . . , ] ≤ . Therefore, understanding the decomposition of the covariant algebra also provides important quantitative information. More precisely: we denote the dimension of the R-vector space of -invariant forms of degree by ( ), and write ℎ for the multiplicity of an irreducible representation in (R[ 1 , . . . , ] ) ≤ , i.e., for the multiplicity of in the isotypic decomposition of the subspace of polynomials of degree at most in the covariant algebra. Then we get the following quantitative information necessary for applying Theorem 9 directly.

:= =1 ( )-1 ,
where ( ) is the index of the row of containing . Note that for any -tabloid { } the monomial is well defined, and the mapping { } ↦ → is a isomorphism. For any column C of we denote by C ( ) the element in the -th row and we associate to it a Vandermonde determinant:

Δ C := det 0 C (1) . . . 0 C ( ) . . . . . . . . . -1 C (1) . . . -1 C ( ) = < ( C ( ) -C ( ) ).
The Specht polynomial associated to is defined as

:= =1 Δ C = ∈CStab sgn( ) ( ) ,
where CStab is the column stabilizer of .

By the -isomorphism { } ↦ → , acts on in the same way as on the polytabloid . If ,1 , . . . , , denote all standard Young tableaux associated to , then the set of polynomials ,1 , . . . , , are called the Specht polynomials associated to . We then have the following result due to Specht [START_REF] Specht | Zur Darstellungstheorie der symmetrischen Gruppe[END_REF]: Proposition 5 The Specht polynomials ,1 , . . . , , span an -submodule of R[ ] which is isomorphic to the Specht module . Using the construction of Specht polynomials we aim now to obtain a version of Theorem 18 in the case of the symmetric polynomials. For this we rely on a basis for the corresponding covariant ring. Such a basis was described by Ariki, Terasoma, and Yamada in [START_REF] Ariki | Higher Specht polynomials[END_REF] with the construction of the so-called Higher Specht polynomials. These polynomials generalize the Specht polynomials in such a way that they yield a concrete basis as in Proposition 3. Their definition is given by a pair of Young tableaux.

Definition 15 Let ∈ N be a natural number. 1. We call a finite sequence = ( 1 , . . . , ) of non-negative integers a word of length . 2. A word of length is called a permutation if the set of its non-negative integers is {1, . . . , }. 3. Given a word and a permutation we define the monomial associated to the pair as :=

1 1 • • • . 4.
To a given permutation its index denoted by ( ), is the word of length constructed the following way: the word ( ) contains 0 exactly at the same position where 1 occurs in . The other entries are defined recursively with the following rule: if is in position in the word (that is, = ) and + 1 is in position , then ( ) = ( ) if > , and ( ) = ( ) + 1 otherwise.

is an irreducible

-module isomorphic to the Specht module .

The higher Specht polynomials for 3

Consider the group 3 . The complete list of higher Specht polynomials is given by 1) .

{1} for (3) {( 2 -1 ), ( 3 -1 )} , { 3 ( 2 -1 ), 2 ( 3 -1 )} for (2,1) {( 2 -3 ) ( 3 -1 ) ( 3 -2 )} for (1,1,
These correspond to the trivial representation (3) , the 2-dimensional Specht module (2,1) and the 1-dimensional Specht module (1,1,1) . We thus compute

(3) = 1 (2,1) = 3 (( 2 -1 ) 2 ) 3 (( 2 -1 ) 3 ( 2 -1 )) 3 (( 2 -1 ) 3 ( 2 -1 )) 3 ( 3 ( 2 -1 ) 2 ) = 2 -1 3 2 1 -1 3 3 1 + 4 3 1 2 -3 -1 3 3 1 + 4 3 1 2 -3 -1 6 4 1 + 2 3 2 1 2 -2 3 1 3 + 1 6 2 2 (1,1,1) = 3 (( 1 -2 ) ( 1 -3 ) ( 2 -3 )) = 1 6 (-1 6 + 9 1 4 2 -8 1 3 3 -21 1 2 2 2 + 36 1 2 3 + 3 2 3 -18 3 2 )
Using Theorem 18 one now obtains that every symmetric sum of squares polynomial ∈ R[ 1 , 2 , 3 ] 3 can be written in the from

= 0 ( 1 , 2 , 3 ) + 1 ( 1 , 2 , 3 ) (1,1,1) + ( ( 1 , 2 , 3 ) • (2,1) ),
where 0 ( 1 , 2 , 3 ), and 1 ( 1 , 2 , 3 ) are sums of squares in R[ 1 , . . . , 3 ] and ∈ R[ 1 , . . . , 3 ] 2×2 is a sum of squares matrix polynomial.

Furthermore, we can use the combinatorial description of the Higher Specht polynomials to gain understanding of the "complexity" of symmetric sums of squares decomposition of polynomials of fixed degree 2 . Indeed, we find that the multiplicities of the -modules which appear in an isotypic decomposition R[ 1 , . . . , ] = coincide with the number of standard -tableaux with charge at most , i.e., all with ( ) ≤ . This yields in particular the following observation which was first remarked in [START_REF] Riener | Exploiting symmetries in sdprelaxations for polynomial optimization[END_REF]Theorem 4.7.], and can be generalized to all infinite families of reflection groups [START_REF] Debus | Reflection groups and cones of sums of squares[END_REF]Theorem 3.31].

Theorem 20 Let

,2 denote the homogeneous symmetric polynomials of degree 2 . Then the matrix size needed to decide if ∈ ,2 is a sum of squares do not depend on once ≥ 2 .

A similar phenomenon was also shown in situations where is not acting as a reflection group [START_REF] Raymond | Symmetric sums of squares over k-subset hypercubes[END_REF]. The stabilization observed in Theorem 20 makes it in particular possible to give uniform descriptions for symmetric sums of squares of a given degree. For example we have the following representation theorem of symmetric quartics which was derived in [START_REF] Blekherman | Nonnegative polynomials and sums of squares[END_REF] with the methods presented in this section. are chosen such that ≥ 0 and the matrices 11 12 12 22

and 11 12 12 22 are positive semidefinite.

Miscellaneous approaches

So far we have been focused on ways to explore symmetries in sums of squares decompositions which are used to obtain an approximation hierarchy for polynomial optimization problems. To close our discussion, we present here some other ways to use symmetries in optimization problems. The selection we present here is non exhaustive and the presentation of the individual methods is rather short. However, we hope this overview will provide useful points of references for the reader.

Orbit spaces and polynomial optimization

The methods of invariant theory presented in Section 4 have provided that we can represent an invariant polynomial algebraically in terms of generators of the invariant ring. Indeed, Theorem 10 yields that K[ ] is finitely generated and therefore is the coordinate ring of an algebraic variety. So we can associate to a choice of generators

Π : K -→ K ↦ -→ ( 1 ( ), . .

. , ( )) .

This map is also called the Hilbert map. Let ∈ K , then the orbit of denoted by is the set of points to which is mapped to under the action of , i.e. := { ( ) ∈ }.

As the orbits and of two points in K are either equal or disjoint, the action of on K naturally defines an equivalence relation by ∼ if and only if = ( ) for some ∈ and we can consider the set of equivalence classes, i.e., the set of all -orbits on K and denote this by K / . This set is called the orbit space. Notice that the Hilbert map is constant on -orbits, so it makes sense to view it as a mapping of the orbit space. Now if have a finite group acting on a linear space defined over an algebraically closed field, for example K = C, then the polynomial mapping defined above is surjective onto the dimensional variety Π ⊂ C defined by the algebraic relations between the polynomials 1 , . . . , . In particular, if the polynomials are algebraically independent, which is exactly the case if is a finite reflection group, each orbit is mapped to a point in C . Moreover if 1 , . . . , are invariant polynomials that describe an algebraic set in C the Hilbert map sends this set to a new algebraic set in C which is given by the polynomials 1 , . . . , which satisfy ( 1 , . . . , ) = for 1 ≤ ≤ . Therefore, the possibility to represent invariant functions in terms of generators can reduce the complexity of the description of invariant algebraic sets.

In contrast to the algebraically closed case where the Hilbert map is surjective, if we restrict Π to R the resulting map Π may fail to be surjective.

Failure of surjectivity in the 4 case

Let = 4 be the Dihedral group acting on R 2 . Then the invariant ring C[ , ] 4 is generated by 1 = 2 + 2 and 2 = 2 2 and since 4 is a reflection group 1 and 2 are algebraically independent. The Hilbert map thus provides a connection between the orbit space C 2 / 4 and C 2 . However, if we restrict the map to R 2 the image of Π is strictly contained in R 2 . Indeed, we must have 1 ( , ) ≥ 0 for all ( , ) ∈ R 2 , and thus for example Π -1 (-1, 0) ∉ R 2 . Hence, the restricted map Π is not surjective.

Nevertheless, the real Hilbert map

Π : R → R / ⊆ R ↦ → ( 1 ( ), . . . , ( ))
defines an embedding of the orbit space into R and by the Traski-Seidenberg principle of real algebraic geometry its image is a semi-algebraic subset of R . It can be shown that the failure of the map being surjective is related to the existence of abelian 2-subgroups of (see [START_REF] Bröcker | On symmetric semialgebraic sets and orbit spaces[END_REF]). Therefore, as soon as the order of the group is even, additional semi-algebraic conditions need to be imposed. For example, in the example above, every point in the image needs to satisfy

Π(R 2 ) ⊆ {( 1 , 2 ) ∈ R 2 : 1 ≥ 0} since 1 ( , ) ≥ 0 for all ( , ) ∈ R 2 .
It was shown by Procesi and Schwarz [START_REF] Procesi | Inequalities defining orbit spaces[END_REF] that the image of Π is in fact a basic semialgebraic set, i.e., there exist finitely many polynomial inequalities which are satisfied if and only if a point is in the image of the map. Moreover, in the case of compact groups, these inequalities can be obtained from the chosen fundamental invariants in a direct way:

For a polynomial we consider the differential defined by = =1 . For finite (compact) we have a -invariant inner product •, • which when carrying over the to the differentials yields , = =1

where we assume that the polynomials , 1 , . . . , are invariant by a group , then by choosing 1 , . . . , which generate the invariant ring we obtain corresponding polynomials ˜ , ˜ 1 , . . . ˜ ∈ R[ 1 , . . . , ], which might be of smaller degrees than the original polynomials. By using Theorem 22 we may now translate the optimization problem [START_REF] Bröcker | On symmetric semialgebraic sets and orbit spaces[END_REF] to the following equivalent optimization problem:

inf{ ˜ ( ) s.t. ∈ ( Π ), ˜ 1 ( ) ≥ 0, . . . , ˜ ( ) ≥ 0, ( ) 0 }. (15)
So the Hilbert map allows us to reformulate the initial polynomial optimization problem in new polynomial functions, which potentially can be of smaller degree or involve less variables, at the price that we obtain a new set of constraints that come from the fact that the Hilbert map fails in general to be surjective.

For a polynomial matrix ( ), define the localizing matrix as follows

( ★ ) , , , = ( • • ( ) , )
.

With this construction one can define the following moment relaxation for the orbit space formulation of a polynomial optimization problem defined in [START_REF] Chandrasekaran | Relative entropy relaxations for signomial optimization[END_REF] for ∈ N:

: inf ˜ ( ) 0 , -⌈deg ˜ /2⌉ ( ˜ ) 0, -( ★ ) 0 . (16)
For large enough, each solution to the sequence of semi-definite programs defined in ( 16) provides a lower bound for the problem and moreover, under additional conditions, the sequence of relaxations converges. (see [START_REF] Riener | Exploiting symmetries in sdprelaxations for polynomial optimization[END_REF] for details). This relaxation approach recently has also been adapted to multiplicative group actions (see [START_REF] Hubert | Optimization of trigonometric polynomials with crystallographic symmetry and applications[END_REF]).

Reduction via orbit decomposition

In the symmetry reduction techniques for sums of squares presented in this chapter, the first essential step consisted in the observation that for convex sets one can reduce easily to orbits and the second step was grounded in consequences of Schur's lemma. Approaches using the second step are however clearly limited to those situations that allow for an application of Schur's lemma. However, even in cases where sophisticated tools from representation theory will not directly apply, one can obtain substantial reductions by cleverly decomposing invariant problems according to orbits. A natural idea consists for example in turning a large symmetric problem into smaller problems, in such a way that solving these smaller problems gives at least a solution by orbit, therefore giving a full understanding of the solutions of the initial problem. Such ideas can be useful, and sometimes refined, in several situations, including in optimization and computation (see for instance [START_REF] Faugère | Computing critical points for invariant algebraic systems[END_REF][START_REF] Herr | Exploiting symmetry in integer convex optimization using core points[END_REF][START_REF] Schürmann | Exploiting symmetries in polyhedral computations[END_REF]). We showcase one example of this simple, but sometimes effective, idea in the context of polynomial optimization: the orbit decomposition of SAGE signomials.

In order to motivate this situation we recall that the main key for the approximations methods used in the previous sections comes from the observation that a polynomial which can be written as a sum of squares is non-negative. Of course, one can replace this condition with other certificates of non-negativity certification. Another example of such certificates relies on SAGE functions (see [START_REF] Chandrasekaran | Relative entropy relaxations for signomial optimization[END_REF]). A signomial is a function of the form

( ) = ∈A < , >
where A ⊂ R is a finite set. Under the change of variables = , this can be seen as a generalization of polynomial functions restricted to the positive orthant.

Suppose a signomial can be written in the from

( ) = ∈A < , > + < , > (17)
> 0 for ∈ A and ∈ relint(A).

= sup{ , -is SAGE} inf{ ( ), ∈ R }
to obtain a bound on the minimum of a given signomal function on R . The observation which makes this formulation computationally viable is that the task to decide if a given signomial is SAGE can be decided via relative entropy programming (a subclass of convex programs, see [START_REF] Chandrasekaran | Relative entropy relaxations for signomial optimization[END_REF]). Now, if we suppose that a signomial as written in ( 17) is invariant by the action of a group (linearly on the exponents) and denote by B be a set of orbit representatives for B by this action, then applications of the Reynolds operator reveal (see [START_REF] Moustrou | Symmetry reduction in am/gm-based optimization[END_REF] for details) that is SAGE if and only if for every ∈ B, there exists an AGE signomial where the functions ℎ can be chosen to be invariant under the action of the stabilizer Stab ( ) of .

SAGE decomposition of a symmetric signomial

Consider the symmetric signomial = 5 6 + 5 6 + 5 6 -2 + + -+2 + -+ +2 + 6.

With the notation above we have B = {(1, 1, 2)}. The stabilizer of (1, 1, 2) is 2 × 1 and is SAGE if and only if there exists an AGE polynomial of the form

= 1 6 + 2 6 + 3 6 + 4 -+ +2
such that = + (1 3) + (2 3) .

Moreover, since we can assume that is invariant under the action of 2 × 1 , we can assume that 1 = 2 . Identifying the coefficients we find therefore that 1 = 2 = 1, 3 = 3 and 4 = 2. Thus, is SAGE if and only if = 6 + 6 + 3 6 -+ +2 + 1 is AGE, and therefore we directly arrive at a substantial reduction of the associated relative entropy program.

In fact the reduction of complexity suggested in the example above can be made precise by understanding the orbits and stabilizers of the exponents appearing in the signomial. In particular in the case of symmetric AGE functions, i.e., invariant by the group , it can be shown (see [START_REF] Moustrou | Symmetry reduction in am/gm-based optimization[END_REF]Theorem 5.2]) that one can expect a stabilization of complexity with similar to Theorem 20: for some sequences of signomials, if the number of terms grows quickly, the number of variables and constraints in the corresponding relative-entropy program remains constant for large enough. Therefore, even in a situation where we are not able to use the power of representation theory, we can turn large optimization problems involving a lot of variable and constraints into a smaller one that can be solved efficiently.

Symmetries of optimizers

We conclude this section with a rather general approach, which may be used in some situations. Again, let be a group acting linearly on a vector space . Given an optimization problem that is symmetric, i.e., invariant by a group , one could expect that also the solutions exhibit symmetries. Firstly, and clearly, the set of optimal points will be closed under the action of the symmetry group. In the best case, also the optimal points themselves will be fixed by the group. If we know apriori that this is the case, we only need to look at the linear subspace of points which are invariant by . If the action of is not the trivial one, this subspace will be of smaller dimension thus, one obtains directly a reduction of the optimization problem. The following example is one easy and simple prototype of this idea.

A symmetric problem with a symmetric solution

Given > 0 we want to find the maximal area of an rectangle of perimeter . The solution is the square and one find directly that the side length is 1 4 .

However, it is in general not clear what conditions on the optimization problem guarantee this property (see for example [START_REF] Waterhouse | Do symmetric problems have symmetric solutions?[END_REF] for a beautiful exhibition of situations and some historical panorama). But in particular, if there is just one optimal point, this optimal point has to be invariant by the group. So, we can conclude that in particular for convex optimization problems, this approach might directly lead to a reduction of dimension. Building on this simple idea, it may also be beneficial if one knows apriori that the optimal points are fixed by some (non trivial) subgroup of . For a subgroup ′ ⊂ we denote by ′ the elements in fixed by ′ . It is a simple observation that ′ is a vector subspace of which might be of smaller dimension. Thus by restricting the original optimization problem to the smaller vector space ′ we reduce the dimension of the problem. We present some situations in which this approach can lead to some substantial reduction. Building on the example above, suppose that we deal with an optimization problem defined in symmetric polynomials and we thus consider the action of the symmetric group on R . The action of on R naturally decomposes the space into orbits. (

) 18
Remark 7 Note that |Λ , | ≤ + and therefore, for fixed , the amount of additional problems in variables grows only polynomially in .

The main advantage of the simple approach based on Theorem 23 consists in the possibility to use any method to solve the resulting -dimensional polynomial optimization problems. In particular, it has been observed in [START_REF] Riener | Exploiting symmetries in sdprelaxations for polynomial optimization[END_REF][START_REF] Debus | Reflection groups and cones of sums of squares[END_REF] that combining this approach with the sum of squares approach can lead to qualitative improvements of the approximation. There have been several generalizations of Theorem 23: the paper [START_REF] Moustrou | Symmetric ideals, specht polynomials and solutions to symmetric systems of equations[END_REF] provides a finer criterion than only the degree of the polynomials involved to decide on the orbit type of solutions. In [START_REF] Riener | Symmetric semi-algebraic sets and non-negativity of symmetric polynomials[END_REF][START_REF] Riener | Linear slices of hyperbolic polynomials and positivity of symmetric polynomial functions[END_REF] special classes of symmetric polynomials are defined, depending on special representation of the polynomials in the power sum basis or in the basis of elementary symmetric polynomials. For these classes an approach identical to the one described above can be derived from [START_REF] Riener | Symmetric semi-algebraic sets and non-negativity of symmetric polynomials[END_REF]Theorem 2.6] or [START_REF] Riener | Linear slices of hyperbolic polynomials and positivity of symmetric polynomial functions[END_REF]Theorem 24]. Furthermore, it can be shown that a similar statement holds in fact for all finite reflection groups [START_REF] Acevedo | Test sets for nonnegativity of polynomials invariant under a finite reflection group[END_REF][START_REF] Friedl | Reflection groups, reflection arrangements, and invariant real varieties[END_REF] and even in the setup of the symmetric group not acting as a reflection group [START_REF] Görlach | Deciding positivity of multisymmetric polynomials[END_REF]. Finally, via Morse theory the fact that optimal points to special symmetric optimization problems tend to have some high symmetry also has impact on the topological complexity of the orbit space of -invariant semi-algebraic sets (see [START_REF] Basu | Bounding the equivariant betti numbers of symmetric semi-algebraic sets[END_REF][START_REF] Basu | On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities[END_REF]) and a refined statement can be used to give complexity reduction in various algorithmical questions related to the topology of symmetric semi-algebraic sets (see [START_REF] Basu | Efficient algorithms for computing the euler-poincaré characteristic of symmetric semi-algebraic sets[END_REF][START_REF] Basu | Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets[END_REF]). Finally, one can observe that that after the restriction to in some cases the resulting system will still have some symmetries. This was for example used in [START_REF] Faugère | Computing critical points for invariant algebraic systems[END_REF][START_REF] Vu | Computing critical points for algebraic systems defined by hyperoctahedral invariant polynomials[END_REF] to obtain more efficient algorithmic results for computing critical points.

3 .

 3 A representation of on the polynomial ring C[ 1 , . . . , ]. In this representation, we define • = ( ) for ∈ and ∈ 1, . . . , , and extend it to a morphism of C

Theorem 5

 5 Let be a finite group and ( , ) isomorphic to the regular representation of . Then, ≃ ∈I (dim ) , and in particular, we have

1 = 1

 1

Theorem 7

 7 If the original SDP is -invariant then we have * = * . Proof For every feasible and ∈ the matrix is feasible. We have , = , for every ∈ . Since the feasible region is convex we have ∈ . Thus * = * .

1 = 11 , 1 ,=1 2 )

 1112 12, • • • , 1 of ,1 , and denote by 1 , 2 , • • • , the image of this basis under the unique -isomorphism sending 1 to . Consider the vector space generated by 1 , • • • , . Since the restriction | × is a positive semi-definite bilinear form, • • • , R . Now, clearly there exists a symmetric, -invariant, bilinear form : × → R for which we have R ( = ( , ), where = ( 11 , . . . , 1 , 21 , . . . , 1 , . .

Theorem 13

 13 which corresponds to multiplication by is a -homomorphism. So K[ ] has in turn the structure of a K[ ] -module. We have in fact the following. Let be an irreducible character of a finite group . Then K[ ] is a is a finitely generated (even Cohen-Macaulay) K[ ] -module and K[ ] is generated by homogeneous elements of degree not exceeding | |. In particular, also K[ ] is a finitely generated K[ ] (Cohen-Macaulay) module.

Proposition 3

 3 Let be a finite reflection group, and let R[ 1 , . . . , ] = ∈ ( ) be the isotypic decomposition of the covariant algebra. Denote ℓ = | |. Then there are polynomials 11 , . . . , ℓ ℓ ∈ R[ 1 , . . . , ] such that any ∈ R[ 1 , . . . , ] can be written as = ∈ =1 ∈ , , where , ∈ R[ 1 , . . . , ] .

Definition 17 1 For = 1 1 , 2 2 ,

 1711122 For every ∈ R , the associated stabilizer subgroup Stab( ) ⊆ is of the form Stab() ≃ ℓ 1 × ℓ 2 × • • • × ℓ with ℓ 1 ≥ ℓ 2 ≥ . . . ≥ ℓ .We hence define the orbit type of to beΛ( ) := (ℓ 1 , ℓ 2 , • • • , ℓ ).Then, for a given ⊢ we can define := { ∈ K : Λ( ) = } , and := { ∈ R : the orbit type of has length at most k} Remark 6 For ∈ N, the set as defined above is a union of -dimensional linear (sub)spaces of R .Example we find 1 = { • (1, . . . , 1), ∈ R} and in general can be identified with the set of points having at most distinct coordinates Now we have the following (see[START_REF] Riener | On the degree and half-degree principle for symmetric polynomials[END_REF] Theorem 4.5], and[START_REF] Timofte | On the positivity of symmetric polynomial functions.: Part i: General results[END_REF]). Theorem 23 Let , 1 , . . . , ∈ R[ ] and let set := max 2, ⌊(deg )/2⌋, deg 1 , . . . , deg . Consider the optimization problem * = inf ∈ ( ), where = { ∈ R : 1 ( ) ≥ 0, . . . , ( ) ≥ 0}.If the set of optimizers is not empty it contains at least one point * ∈ , and in fact * = inf very direct approach to make use of this result consists in restricting to the different sub-spaces that build up individually. We consider the set Λ , of all partitions of into exactlt parts. Then for each ∈ Λ , , set := ( 1 , . . . , 1 , . . . , 2 . . . , , . . . ,) ∈ R[ 1 , . . . , ] .Similarly, let := { ∈ R : 1 ( ) ≥ 0, . . . , ( ) ≥ 0}. With this easy substitution the original optimization problem in variables can be transformed into a set of new optimization problems that involve only variables,

  Theorem 21 Let ∈ ,4 be a symmetric quartic. Then is a sum of squares if and only if it can be written in the form where = 1 ( 1 +. . . ) for 1 ≤ ≤ 4 and the parameters 11 , 12 22 , 11 , 12 , 22

	( ) = 11	4 1 + 2 12	2 1 2 + 22	2 2
	+ 11		2 1 2 -4 1 + 2 12 (3,1) -2 1 2 + 22 4 -2 2
	+	1 2	4 1 -2 1 2 +	2 -3 + 3 2 2	2 2 +	2 -2 2	1 3 +	1 -2 2 4 ,

  Then, it follows from arithmetic-geometric mean inequality that is non-negative on R if and only if there exists ∈ A + such that A function of this form is called an AGE function, and a sum of AGE functions is called a SAGE function. Clearly, a SAGE function is non-negative on R , and similarly to the sum of squares formulation one can define a SAGE-approximation of the polynomial optimization problem (2) via

	∈A	=	∈A	and	∈A	ln •	.

, . . . , and the corresponding inclusion K[ 1 , . . . , ] ⊆ K[ 1 , . . . , ] a morphism Π defined explicitly via

Acknowledgements This expository article originates from a minicourse "Symmetries in algorithmic questions in real algebraic geometry" held during the virtual POEMA (Polynomial Optimization, Efficiency Through Moments and Algebra) Learning Weeks in July 2020. The authors would like to thank the anonymous reviewers for helpful comments.

Proposition 4 Let be a finite reflection group and be an irreducible representation. Then the multiplicity of the corresponding irreducible representation in the

-module (R[ 1 , . . . , ] ) ≤ equals =0 ( -) • ℎ .

We are going to explore this theorem and its consequences a bit more in detail in the case of symmetric polynomials in the next Subsection and in the situation of a regular triangle in the next example, which is made more general in [START_REF] Debus | Reflection groups and cones of sums of squares[END_REF].

Sums of squares invariant by the dihedral group 3

Consider the dihedral group 3 of order 6 acting on the plane as a reflection group.

The corresponding invariant ring is generated by the two polynomials

2 . The group has three irreducible representations, two of which are one dimensional and one of which is two dimensional. We find that the corresponding covariant algebra R[ , ] 3 decomposes into

Then

2 )

, and we obtain

Symmetric sums of squares

To conclude our discussion on the representations of invariant sums of squares, we focus on the case of symmetric polynomials. This case has been studied by various authors (for example [START_REF] Kurpisz | Sum-of-squares hierarchy lower bounds for symmetric formulations[END_REF][START_REF] Riener | Symmetries in semidefinite and polynomial optimization: relaxations, combinatorics, and the degree principle[END_REF][START_REF] Raymond | Symmetric sums of squares over k-subset hypercubes[END_REF][START_REF] Heaton | An sos counterexample to an inequality of symmetric functions[END_REF]), and our presentation follows [START_REF] Blekherman | Symmetric non-negative forms and sums of squares[END_REF].

In Definition 5 we have seen how to combinatorially describe the irreducible representations of with the help of Young tabloids. A classical construction of Specht realizes these irreducible representations as submodules of the polynomial ring (see [START_REF] Specht | Zur Darstellungstheorie der symmetrischen Gruppe[END_REF]): Definition 14 For ⊢ let be a standard Young tableau of shape and C 1 , . . . , C be the columns of . To we associate the monomial 5. For a partition of and a standard Young tableau of shape , the word of -denoted by ( ) -is defined by collecting the entries of from the bottom to the top in consecutive columns starting from the left. 6. For a pair ( , ) of standard -tableaux we define the monomial associated to this pair as

The degree of the monomial is called the charge of , denoted ( ).

An example of a monomial built from a tableau

Consider the tableau = 1 2 4 3 5 .

The resulting word is given by

we obtain the monomial ( ( )) ( )

Definition 16

Let ⊢ and be a -tableau. Then the Young symmetrizer associated to is the element in the group algebra R[ ] defined to be

Now let be a standard Young tableau, and define the higher Specht polynomial associated with the pair ( , ) to be

The importance of these higher Specht polynomials now is summarized in the following Theorem which can be found in [2, Theorem 1].

Theorem 19

The following holds for the set of higher Specht polynomials.

The set

For any ⊢ and standard -tableau , the space spanned by the polynomials in F := { , where runs over all standard -tableaux}

The choice of generators matters

The matrix polynomial , as well as the specific description of the original problem in terms of generators, depend on the choices made for the generators. Thus different choices might lead to quite different optimization problems. Consider the Motzkin polynomial = 4

2 +1. We can rewrite this polynomial in terms of elementary symmetric polynomials, i.e., 1 = 1 + 2 and 2 = 1 2 . Then

The corresponding matrix polynomial is given by

.

Now the minimal value of on R 2 is the same as the minimal value of ˜ in the set of points ( 1 , 2 ) ∈ R 2 : ( 1 , 2 ) 0 . On the other hand we can choose the power sum polynomials 1 = 1 + 2 , 2 = 2 1 + 2 2 and we obtain

Furthermore, we find for the corresponding matrix polynomial

.

Now the minimal value of on R 2 is the same as the minimal value of ˜ in the set of points

The main advantages of the approach sketched above is that it may reduce the degrees of the polynomials describing the optimization problem and even can reduce the number of variables. Furthermore, optimal points to the equivalent optimization problem [START_REF] Chandrasekaran | Relative entropy relaxations for signomial optimization[END_REF] correspond to entire orbits of optimal points. Therefore the number of such points may also be drastically smaller. Finally, in contrast to the methods described in the main parts of this chapter, which were designed for sums of squares approximations, this approach reduces the symmetry on the formulation and therefore allows integration with other methods for solving polynomial optimization problems. However, it was observed in [START_REF] Riener | Exploiting symmetries in SDPrelaxations for polynomial optimization[END_REF] that the special structure of the optimization problem (15) -namely the fact that the additional constraints are expressed in terms of a polynomial matrix inequality ( ) 0 -allows to use a specially adapted version of the SOS-moment hierachy established by Hol and Scherer (and dually by Henrion and Lasserre). We briefly sketch this approach.

Orbit space formulations and moment relaxations