Seminar • Computer Algebra — An Efficient Sum of Squares Certificate for 4-ary 4-ic

Wednesday, February 26, 2020 1:30 pm - 1:30 pm EST (GMT -05:00)

Dmitrii Pasechnik, Department of Computer Science
University of Oxford

Hilbert’s 17th problem (resolved by Artin and Schreier) can be formulated as the existence, for any globally nonnegative n-ary homogeneous polynomial (a.k.a. form) f, of a sum of squares (s.o.s., for short) form q so that fq is a sum of squares (thus f is nonnegative). Note that once the degree of q is known, finding it can be done by solving a semidefinite optimisation (SDP) feasibility problem.

For n=3, Hilbert has shown a quadratic, in the degree of f, bound on the degree of q. In general, the best known degree bounds are huge. The next interesting case is n=4, and f of degree 4. We show that in this case there exists a product of two non-negative quadrics q so that qf is an s.o.s. of quartics.

As a step towards deciding whether it is sufficient to use a quadratic multiplier q, we show that there exist non-s.o.s. non negative 3-ary sextics ac − b^2, with a, b, c of degrees 2, 3, 4, respectively (this gives a new class of nonnegative 3-ary sextics which are not s.o.s.).


Bio: Dmitrii (Dima) Pasechnik obtained his PhD in pure mathematics in 1995 from the University of Western Australia, and has held a number of postdoctoral and research jobs in several universities in the Netherlands and Germany. In 2006–2013 he was an Assistant Professor at the newly established Division of Mathematical Sciences of Nanyang Technological University (Singapore). Then he moved to Oxford, where he holds a research position at the CS Department, and tutors mathematics at Oxford’s Pembroke College.

Dmitrii’s research interests are in combinatorics, optimization, algebra and algebraic geometry, and in theory and practice of symbolic computing — he is involved in development of SageMath and GAP computer algebra systems, and is interested in reproducibility of mathematical computations and constructions.