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

Abstract

We provide a new approach to the optimization of trigonometric polynomials with crystallographic symmetry. This approach widens the bridge between trigonometric and polynomial optimization. The trigonometric polynomials considered are supported on weight lattices associated to crystallographic root systems and are assumed invariant under the associated reflection group. On one hand the invariance allows us to rewrite the objective function in terms of generalized Chebyshev polynomials of the generalized cosines; On the other hand the generalized cosines parameterize a compact basic semi algebraic set, this latter being given by an explicit polynomial matrix inequality. The initial problem thus boils down to a polynomial optimization problem that is straightforwardly written in terms of generalized Chebyshev polynomials. The minimum is to be computed by a converging sequence of lower bounds as given by a hierarchy of relaxations based on the Hol–Scherer Positivstellensatz and indexed by the weighted degree associated to the root system. This new method for trigonometric optimization was motivated by its application to estimate the spectral bound on the chromatic number of set avoiding graphs. We examine cases of the literature where the avoided set affords crystallographic symmetry. In some cases we obtain new analytic proofs for sharp bounds on the chromatic number while in others we compute new lower bounds numerically.