Search

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.

The Weyl group of a crystallographic root system has a nonlinear action on the compact torus. The orbit space of this action is a compact basic semi-algebraic set. We present a polynomial description of this set for the Weyl groups of type A, B, C, D and G. Our description is given through a polynomial matrix inequality. The novelty lies in an approach via Hermite quadratic forms and a closed formula for the matrix entries. The orbit space of the nonlinear Weyl group action is the orthogonality region of generalized Chebyshev polynomials. In this polynomial basis, we show that the matrices obtained for the five types follow the same, surprisingly simple pattern. This is applied to the optimization of trigonometric polynomials with crystallographic symmetries.

Sparse interpolation} refers to the exact recovery of a function as a short linear combination of basis functions from a limited number of evaluations. For multivariate functions, the case of the monomial basis is well studied, as is now the basis of exponential functions. Beyond the multivariate Chebyshev polynomial obtained as tensor products of univariate Chebyshev polynomials, the theory of root systems allows to define a variety of generalized multivariate Chebyshev polynomials that have connections to topics such as Fourier analysis and representations of Lie algebras. We present a deterministic algorithm to recover a function that is the linear combination of at most r such polynomials from the knowledge of r and an explicitly bounded number of evaluations of this function.

In this article we determine a generating set of rational invariants of minimal cardinality for the action of the orthogonal group $\mathrm{O}_3$ on the space $\mathbb{R}[x,y,z]_{2d}$ of ternary forms of even degree $2d$. The construction relies on two key ingredients: On one hand, the Slice Lemma allows us to reduce the problem to dermining the invariants for the action on a subspace of the finite subgroup $\mathrm{B}_3$ of signed permutations. On the other hand, our construction relies in a fundamental way on specific bases of harmonic polynomials. These bases provide maps with prescribed $\mathrm{B}_3$-equivariance properties. Our explicit construction of these bases should be relevant well beyond the scope of this paper. The expression of the $\mathrm{B}_3$-invariants can then be given in a compact form as the composition of two equivariant maps. Instead of providing (cumbersome) explicit expressions for the $\mathrm{O}_3$-invariants, we provide efficient algorithms for their evaluation and rewriting. We also use the constructed $\mathrm{B}_3$-invariants to determine the $\mathrm{O}_3$-orbit locus and provide an algorithm for the inverse problem of finding an element in $\mathbb{R}[x,y,z]_{2d}$ with prescribed values for its invariants. These are the computational issues relevant in brain imaging., Comment: v3 Changes: Reworked presentation of Neuroimaging application, refinement of Definition 3.1. To appear in "Foundations of Computational Mathematics"

Lagrangian curves in 4-space entertain intriguing relationships with second order deformation of plane curves under the special affine group and null curves in a 3-dimensional Lorentzian space form. We provide a natural affine symplectic frame for Lagrangian curves. It allows us to classify Lagrangrian curves with constant symplectic curvatures, to construct a class of Lagrangian tori and determine Lagrangian geodesics., Comment: (04/2013)

Given a group action, known by its infinitesimal generators, we exhibit a complete set of syzygies on a generating set of differential invariants. For that we elaborate on the reinterpretation of Cartan's moving frame by Fels and Olver (1999). This provides constructive tools for exploring algebras of differential invariants., Comment: Journal of Symbolic Computation (2008)

We show that, for both the conformal and projective groups, all the differential invariants of a generic surface in three-dimensional space can be written as combinations of the invariant derivatives of a single differential invariant. The proof is based on the equivariant method of moving frames., Comment: This is a contribution to the Proceedings of the 2007 Midwest Geometry Conference in honor of Thomas P. Branson, published in SIGMA (Symmetry, Integrability and Geometry: Methods and Applications) at http://www.emis.de/journals/SIGMA/

Lie group theory states that knowledge of a $m$-parameters solvable group of symmetries of a system of ordinary differential equations allows to reduce by $m$ the number of equation. We apply this principle by finding dilatations and translations that are Lie point symmetries of considered ordinary differential system. By rewriting original problem in an invariant coordinates set for these symmetries, one can reduce the involved number of parameters. This process is classically call nondimensionalisation in dimensional analysis. We present an algorithm based on this standpoint and show that its arithmetic complexity is polynomial in input's size.

The paper presents a new algorithmic construction of a finite generating set of rational invariants for the rational action of an algebraic group on the affine space. The construction provides an algebraic counterpart of the moving frame method in differential geometry. The generating set of rational invariants appears as the coefficients of a Groebner basis, reduction with respect to which allows to express a rational invariant in terms of the generators. The replacement invariants, introduced in the paper, are tuples of algebraic functions of the rational invariants. Any invariant, whether rational, algebraic or local, can be can be rewritten terms of replacement invariants by a simple substitution., Comment: 37 pages