The problem of computing the global minimum of a trigonometric polynomial is computationally hard. We address this problem for the case, where the polynomial is invariant under the exponential action of a finite group. The strategy is to follow an established relaxation strategy in order to obtain a converging hierarchy of lower bounds. Those bounds are obtained by numerically solving semi-definite programs (SDPs) on the cone of positive semi-definite Hermitian Toeplitz matrices, which is outlined in the book of Dumitrescu Dumitrescu (2007). To exploit the invariance, we show that the group has an induced action on the Toeplitz matrices and prove that the feasible region of the SDP can be restricted to the invariant matrices, whilst retaining the same solution. Then we construct a symmetry adapted basis tailored to this group action, which allows us to block-diagonalize invariant matrices and thus reduce the computational complexity to solve the SDP. The approach is in its generality novel for trigonometric optimization and complements the one that was proposed as a poster at the ISSAC 2022 conference Hubert et al. (2022) and later extended to Hubert et al. (2024). In the previous work, we first used the invariance of the trigonometric polynomial to obtain a classical polynomial optimization problem on the orbit space and subsequently relaxed the problem to an SDP. Now, we first make the relaxation and then exploit invariance. Partial results of this article have been presented as a poster at the ISSAC 2023 conference Metzlaff (2023).

With this paper we present an extension of our recent ISSAC paper about computations of Groebner(-Shirshov) bases over free associative algebras Z . We present all the needed proofs in details, add a part on the direct treatment of the ring Z/mZ as well as new examples and applications to e.g. Iwahori-Hecke algebras.The extension of Groebner bases concept from polynomial algebras over fields to polynomial rings over rings allows to tackle numerous applications, both of theoretical and of practical importance.Groebner and Groebner-Shirshov bases can be defined for various non-commutative and even non-associative algebraic structures. We study the case of associative rings and aim at free algebras over principal ideal rings. We concentrate ourselves on the case of commutative coefficient rings without zero divisors (i.e. a domain). Even working over Z allows one to do computations, which can be treated as universal for fields of arbitrary characteristic. By using the systematic approach, we revisit the theory and present the algorithms in the implementable form. We show drastic differences in the behavior of Groebner bases between free algebras and algebras, close to commutative.Even the process of the formation of critical pairs has to be reengineered, together with the implementing the criteria for their quick discarding.We present an implementation of algorithms in the Singular subsystem called Letterplace, which internally uses Letterplace techniques (and Letterplace Groebner bases), due to La Scala and Levandovskyy. Interesting examples and applications accompany our presentation.

The extension of Gröbner bases concept from polynomial algebras over fields to polynomial rings over rings allows to tackle numerous applications, both of theoretical and of practical importance. Gröbner and Gröbner-Shirshov bases can be defined for various non-commutative and even non-associative algebraic structures. We study the case of associative rings and aim at free algebras over principal ideal rings. We concentrate ourselves on the case of commutative coefficient rings without zero divisors (i.e. a domain). Even working over Z allows one to do computations, which can be treated as universal for fields of arbitrary characteristic. By using the systematic approach, we revisit the theory and present the algorithms in the implementable form. We show drastic differences in the behavior of Gröbner bases between free algebras and algebras, close to commutative. Even the formation of critical pairs has to be reengineered, together with the criteria for their quick discarding. We present an implementation of algorithms in the Singular subsystem called Letterplace, which internally uses Letterplace techniques (and Letterplace Gröbner bases), due to La Scala and Levandovskyy. Interesting examples accompany our presentation.