Real Polynomial Inequalities: Where Logic Meets Algebra and Geometry

Előadó: Vajda Róbert
Időtartam: 60
Technikai eszközök:

laptop access, beamer, visual table

Hallgatóság: 20 persons, age 16-19

MeetImage2Almost every high school student knows when a quadratic equation has a real root in terms of the coefficents of the quadratic polynomial. Even more she/he can tell what is the relation between the quadratic and the aritmethic means of two nonnegative real numbers. In this lecture we investigate the question, whether one can give a universal algorithmic solution to a more complex problem class: namely, if there exists a solution of a sytem containing abritrary algebraic equations and inequalities over the reals. The thorough invastigation of these systems (also called constraint systems) could be difficult even if the constrained variables range over finite domains. The deep results by Tarski and Collins in the second half of the XX. century say that over the reals we have a universal procedure for solving the problem but the complexity of the algorithm is very high; this could have negative practical consequences even for small problems containing only a few variables.

We introduce the logical, algebraic and geometrical notions of the underlying theory. Through some toy exampes we illustrate the formalization and the algorithmic problem solving step by step. It turns out that in order to obtain the solution, we  have to construct a special decomposition of the r-dimensonial Euclidean space. The cells of the decompsotion are the so called semialgebraic sets. These very interesting objects can be even visualized in lower dimensions (see attached figure). The decomposition algorithm is avaliable in some of the  open source and commercial math software package. In this lecture we will focus on the implementaton in Mathematica.