In the first part of the lecture I present results obtained recently with F. Boudaoud and F. Caruso in the univariate case: Let P∈ ℤ [X] be a polynomial of degree p with coefficients in the monomial basis of bit-size bounded by τ. If P is positive on [- 1, 1], we obtain a certificate of positivity using Bernstein's basis (i.e. a description of P making obvious that it is positive) of bit-size O (p⁴ (τ + log₂ p)). Previous comparable results had a bit-size complexity exponential in p and τ.

In the second part I discuss multivariate certificates of positivity. New results of R. Leroy on the distance between control polygon and graph expressed in terms of relevant "second differences of the Bernstein coefficients" introduced in 1992 by Goodman and Peters will be presented. Finally the current state of the art on the size of certificates of positivity in the multivariate case will be described and open problems presented.

A linear matrix inequality (LMI) is an inequality of the form L(x):=A₀+x₁A₁+...+x_nA_n≽ 0 where x=(x₁,...,x_n) is the vector of unknowns and the A_i are real symmetric matrices of equal size. A solution is a real vector x such that L(x) is a positive semidefinite matrix. We say that a set has a (lifted) LMI representation if it is (a projection of) the set of solutions of an LMI. The sets having a (lifted) LMI representation involving only diagonal matrices are exactly the closed convex polyhedrons. Like one can optimize a linear function over such polyhedra with linear optimization, one can optimize a linear function over sets having a (lifted) LMI representation with semidefinite optimization. Therefore it is an important question which sets have a (lifted) LMI representation and how such representions can actually be found. Using classical constructions of Jordan- and T-algebras due to Koecher and Vinberg, one can show that homogeneous closed convex cones always have an LMI representation. Vinnikov's determinantal representations of real plane curves have been used to solve the Lax conjecture and to show that three-dimensional hyperbolicity cones also have an LMI representation. It seems open if this remains true for higher dimensional hyperbolicity cones. In contrast to linear inequalities, LMIs become much more expressive if one allows lifted representations. In fact, the only condition known to be necessary for a set to have such a representation seems to be that it is convex and semialgebraic. Helton and Nie have recently shown that compact convex semialgebraic sets have a lifted LMI representation if they are given by polynomials satisfying a certain second order curvature condition. We will try to sketch some basic ideas of the proof of this important result on a very elementary level.

Two famous problems in geometry are the computation of the kissing number and the chromatic number in n-dimensional Euclidean space. The kissing number is the maximal number of unit spheres which can simultaneously touch a central unit sphere without pairwise overlapping. It is the starting point of discrete geometry when, in 1694, Newton and Gregory discussed if the solution in dimension 3 is 12 or 13. The chromatic number is the minimal number of colors one needs to paint all points in space so that pairs of points at distance 1 receive different colors. This problem was made popular by Erdős since the 1950s. The number in the plane is only known to lie between 4 and 7. By restricting to the case where sets of points having the same color are measurable the best known lower bound is 5.

In this talk I present a unified approach to find upper bounds for the kissing number and lower bounds for the measurable chromatic number based on a combination of semidefinite optimization and harmonic analysis. For the kissing number we found, with computer assistance, new upper bounds in various dimensions. For the measurable chromatic number we solved the optimization problem analytically and found new lower bounds in various dimensions and a new proof that it grows exponentially with the dimension.

Based on joint works with Christine Bachoc, Gabriele Nebe, Fernando Mario de Oliveira Filho.

I present a generalization of a theorem of Schrijver which characterizes spaces of tensors which are invariant under a compact Lie group.