3:00pm - 5:00pmSymmetry in algorithmic questions of real algebraic geometry
Chair(s): Cordian Riener (UiT - The Arctic University of Norway, Norway), Philippe Moustrou (UiT - The Arctic University of Norway, Norway)
Symmetry arises quite naturally in many computational problems and from a computational perspective, it allows to reduce the complexity of problems. The mini-symposium aims to presents various instances of computational problems in real algebraic geometry, where symmetry playes an important role.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Orbit closures in the Zariski spectrum of the infinite polynomial ring
Mario Kummer
TU Berlin
We study orbit closures of zero sets of prime ideals under the action of the infinite symmetric group. This leads, for instance, to a characterization of invariant prime ideals of the polynomial ring with n sets of infinitely many variables in terms of families of subvarieties of affine n-space. We also discuss semi-algebraic aspects over the real numbers. This is joint work with Cordian Riener.
Sum-of-squares hierarchy for symmetric formulations.
Adam Kurpisz
ETH Zurich
We preset a method for proving Sum-of-Squares (SoS) lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semi-definiteness to the analysis of "well-behaved" univariate polynomial inequalities.
We illustrate the technique with few applications. For binary polynomial optimization problems of degree 2d and an odd number of variables n, we prove that frac{n+2d-1}{2} levels of the SoS hierarchy are necessary to provide the exact optimal value. This matches the recent upper bound result by Sakaue, Takeda, Kim and Ito. As a special case we give a short elementary proof of Grigoriev/Laurent lower bound for finding the integer cut polytope of the complete graph. Additionally, we show that the SoS hierarchy requires a non-constant number of rounds to improve the initial integrality gap of 2 for the Min-Knapsack linear program strengthened with cover inequalities.
Finally, we study a conjecture by Laurent, who considered the linear representation of a set with no integral points. She showed that the Sherali-Adams hierarchy requires n levels to detect the empty integer hull, and conjectured that the SoS rank for the same problem is n-1. We disprove this conjecture and derive lower and upper bounds for the rank.
Symmetry Preserving Interpolation
Erick Rodriguez Bazan
INRIA
I will talk about multivariate interpolation in the presence of symmetry. Interpolation is a prime tool in algebraic computation while symmetry is a qualitative feature that can be more relevant to a mathematical model than the numerical accuracy of the parameters. In my presentation, I will show how to exactly preserve symmetry in multivariate interpolation while exploiting it to alleviate the computational cost. We revisit minimal degree and least interpolation with symmetry adapted bases, rather than monomial bases. This allows to construct bases of invariant interpolation spaces in blocks, capturing the inherent redundancy in the computations. I will also show that the so constructed symmetry adapted interpolation bases alleviate the computational cost of any interpolation problem and automatically preserve any equivariance of this interpolation problem might have.
Separating invariants of finite groups
Fabian Reimers
TU Munich
Let X be an affine variety with an action of an algebraic group G (over an algebraically closed field K). A subset (e.g. a subalgebra) of the invariant ring K[X]^G is called separating if it has the same capability of separating the orbits as the whole invariant ring. In this talk we focus on finite groups and show how the existence of a separating set of small size, or a separating algebra which is a complete intersection, is related to the property of G being a reflection (or bireflection) group. Theorems of Serre, Dufresne, Kac-Watanabe and Gordeev about linear representations are extended to this setting of G-varieties.
