N1-0217 Free Real Algebraic Geometry with trace

FMF Logo Ang.jpg
imfm logo 198x120.png
ARRSLogo_2016_ang.png

Research project is (co) funded by the Slovenian Research Agency.

UL Member: Faculty of Mathematics and Physics

Code: N1-0217

Project: Free Real Algebraic Geometry with trace

Period: 1. 10. 2021 - 30. 9. 2024

Range per year: 0,7 FTE category: C

Head: Igor Klep

Research activity: Natural sciences and mathematics

Research Organisations, researchers, citations for bibliographic records

Project description:

Optimization problems involving polynomial data arise across many sciences, e.g. in control theory, operations research, statistics and probability, combinatorics and graph theory, computer science, and elsewhere. They are however di2cult to solve. For example, already simple instances of polynomial optimization problems (POPs) are known to be NP hard. Because of their importance, various algorithms have been devised to approximately solve POPs. Newer techniques for solving POPs are based on sums of squares concepts taken from real algebraic geometry and inspired by the theory of moments from functional analysis.

In this proposal our focus is on polynomial optimization problems in matrix unknowns, i.e., noncommutative POPs or NCPOPs for short. Many applied problems, for example those in all the textbook classics in control theory, have matrices as variables, and the formulas naturally involve polynomials in matrices. These polynomials depend only on the system layout and do not change with the size of the matrices involved; such problems are “dimension-free”. Analyzing them is in the realm of free analysis and free real algebraic geometry (free RAG). These booming areas provides a framework for dealing with quantities with the highest degree of noncommutativity, such as large

(random) matrices.

We next discuss free real algebraic geometry, an elegant subject which is unfolding very quickly, in more detail. Starting with Hilbert’s 17th problem, the classical area of RAG gives a systematic theory of classical (commutative) polynomial inequalities. For example, “p is positive where q is positive” is closely related to p having an algebraic relationship to q, called a Positivstellensatz. We are making good progress on free analogues, discovering the free noncommutative case is often much nicer.

Free RAG studies positivity of polynomials in freely noncommuting (nc) matrix variables, and has found many applications across many sciences in the last two decades. For instance, Pironio, Navascues, Acin (2008, 2010, …) give applications to quantum theory, quantum information science; Helton et al. (2008) survey applications and connections to control and systems engineering; Cimprič (2010, 2019) used NCPOPs to investigate PDEs and eigenvalues of polynomial partial diIerential operators; inspired by randomized algorithms in machine learning, Recht and Re (2012) investigate the arithmetic-geometric mean inequality for matrices with the aid of NCPOPs, etc.

This proposal will focus on nc inequalities involving the trace. There are two main fundamental challenges ahead. This proposal intends to overcome them by using analytic, algebraic and geometric tools in a novel way. Problem 1 is an appropriate version of Hilbert’s 17th problem for NCPOP involving the trace in a dimension-free setting. Recently this has been established by the PI with Pascoe and Volčič in the univariate case, giving us a solid starting point for tackling the general case. Problem 2 is solving the n>3 case of the Procesi-Schacher conjecture (Annals of Math, 1976), which is an analog of Hilbert’s 17th problem for NCPOP in a dimension-dependent context. n=3 was settled by the PI with Špenko and Volčič in 2018, and a similar strategy could be followed for n=4,5. New ideas from representation theory, orthogonal groups and central simple algebras will be needed for the general case.

Thus, the project is designed modularly consisting of two strands, one focusing on the dimension-free setting, and the second one on the dimension-dependent context. We will also vigorously pursue applications to closely related fields such as operator theory and quantum information theory. Key for this will be advances in algorithms and their implementations which we intend to make available online to the wider scientific community.