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

Abstract

Trigonometric polynomials are usually defined on the lattice of integers.We consider the larger class of weight and root lattices with crystallographic symmetry.This article gives a new approach to minimize trigonometric polynomials, which are invariant under the associated reflection group.The invariance assumption allows us to rewrite the objective function in terms of generalized Chebyshev polynomials. The new objective function is defined on a compact basic semi-algebraic set, so that we can benefit from the rich theory of polynomial optimization.We present an algorithm to compute the minimum: Based on the Hol-Scherer Positivstellensatz, we impose matrix-sums of squares conditions on the objective function in the Chebyshev basis.The degree of the sums of squares is weighted, defined by the root system. Increasing the degree yields a converging Lasserre-type hierarchy of lower bounds.This builds a bridge between trigonometric and polynomial optimization, allowing us to compare with existing techniques.The chromatic number of a set avoiding graph in the Euclidean space is defined through an optimal coloring.It can be computed via a spectral bound by minimizing a trigonometric polynomial. If the to be avoided set has crystallographic symmetry, our method has a natural application.Specifically, we compute spectral bounds for the first time for boundaries of symmetric polytopes.For several cases, the problem has such a simplified form that we can give analytical proofs for sharp spectral bounds.In other cases, we certify the sharpness numerically.

References in corpus (9)

• The sphere packing problem in dimension 8
• New upper bounds for the density of translative packings of three-dimensional convex bodies with tetrahedral symmetry
• Spectral bounds for the independence ratio and the chromatic number of an operator
• Maximal Theta Functions -- Universal Optimality of the Hexagonal Lattice for Madelung-Like Lattice Energies
• Density estimates of 1-avoiding sets via higher order correlations
• Coloring the Voronoi tessellation of lattices
• The density of planar sets avoiding unit distances
• On symmetry adapted bases in trigonometric optimization
• Orbit spaces of Weyl groups acting on compact tori: a unified and explicit polynomial description

Cited by in corpus (2)

• On symmetry adapted bases in trigonometric optimization
• Additive and Multiplicative Coinvariant Spaces of Weyl Groups in the Light of Harmonics and Graded Transfer