Antonio Lerario: Low-degree approximation of random polynomials

Abstract:  A classical theorem of Seifert asserts that a smooth and compact hypersurface in euclidean space can be approximated by a polynomial one arbitrarily well -- this is a baby version of Nash-Tognoli Theorem, and it is based on a combination of Weierstrass' approximation Theorem and Thom's Isotopy Lemma.

Looking closely at the construction, one can see that the degree of the approximating polynomial depends on the distance, in the C^1 topology, of the smooth hypersurface from the discriminant (i.e. the set of hypersurfaces which are singular). When the hypersurface we want to approximate is already algebraic and the space of all polynomials is endowed with a Gaussian measure, one can estimate the size (the probability) of a neighborhood of the discriminant and prove that for most polynomials the approximation procedure produces a polynomial of lower degree! This has, for example, an impact on the complexity of real root isolation algorithms, but it also sheds some new light on the conceptual understanding of the geometry of the space of algebraic hypersurfaces. For instance: hypersurfaces with a complicated topology exist, but they are extremely hard to find!

In this course I will discuss various facets of this problem, starting from the basic (Weirstrass' Theorem and Thom's Isotopy Lemma), then moving to the quantitative aspect (i.e. looking at the classical questions by paying attention to the various epsilons and deltas), looking a bit Hilbert's Sixteenth problem on the topology of real algebraic sets, and finally switching to the metric-probabilistic point of view (the study of the geometry of Gaussian polynomials, and the real discriminant). I will assume no prerequisites other than some basic knowledge of differential geometry and algebraic topology, and I will make some notes available. 

Published Nov. 17, 2019 11:29 AM - Last modified Nov. 17, 2019 11:29 AM