In cooperation with the European Research Training Network “Real Algebraic and Analytic Geometry”

Real Algebra, Quadratic Forms and Model Theory; Algorithms and Applications

Paris, 02-09 November 2005

Abstracts

• Francesca Acquistapace Looking for a Positivstellensatz for real analytic functions
  Let X in Rⁿ be a coherent real analytic set and g₁,..., g_r, f  be global analytic functions on X. Set S = {h₁ >= 0 ,..., h_r >= 0} and Y = {f = 0}. We consider in this framework  the classical question usually called Positivstellensatz
  
  Assume  S \ Y = Ø. Is there an algebraic identity involving the given functions equivalent to this fact?
  
  We find a kind of local global principle which says, roughly speaking, that this question has a positive answer if and only if it has a positive answer locally in a neighbourhood of each connected component of Y. In particular we get a complete solution in the following cases:
  
  • When X is an analytic curve
  • When X is a normal analytic surface    
  • When all the connected components of Y are compact.
  (Joint work with F. Broglia and J.F. Fernando)
  
  
• Mari Emi Alonso Algorithms in the Henselization
  In this talk, we show how to compute canonical forms for ideals in the henselization of the ring A = K[x]_(x) in a dynamic way. For that we use some essentially finite A algebras. Recall that the henselization  of A is the ring of algebraic power series. This ring  is the more natural setting, after polynomials, to develop algorithms to make exact computations. From a theoretical point of view, the  is "unique" in an strong way, up to unique A-homomorphism, as it happens with the real closure of an ordered field. From a more "practical" viewpoint, the algebraic power series allow to describe the local structure of an algebraic varieties and have a crucial role for the approximation of analytic or formal structures. On the other hand, they have also importance for Combinatorics, Classical Functions and Automata Theory. With respect to more general settings, we are dealing with a constructive description of the henselization of a local ring.
  
  
• Vincent Astier Axiomatization of the pp-conjecture for spaces of orderings
  The positive-primitive conjecture for spaces of orderings states tha a certain very general local-global principle should be true for every space of orderings. It was recently disproved by Gladki and Marshall, but it is still interesting to study the class of spaces or orderings which satisfy it. We show that the corresponding class of reduced special groups is axiomatizable and present a few consequences. This is a joint work with Marcus Tressl.
  
  
• Saugata Basu Asymptotically tight bounds on the number of connected components of the realizations of sign conditions
  In this talk I will discuss recent results on bounding the various Betti numbers (in particular the number of connected components)  of the realizations of sign conditions of a family of real polynomials.
  
  
• Emmanuel Briand The configurations of two real projective quadrics
  In the RAAG Conference at Passau I explained the principles for a singular-isotopic classification of pairs of real projective quadrics. It relies on a known Normal Form for the classification of pairs of real quadratic forms under linear changes of variables.
  In this talk, after recalling the whole story, I will focus on this Normal Form, and the geometric interpretation of its discrete and continuous parameters. This sheds light on the objects labelling the configurations.
  
  
• Fabrizio Caruso Some Algorithms in Real Algebraic Geometry
  The aim of this demo is to present the Maxima library SARAG (``Some Algorithms in Real Algebraic Geometry'') and its use within the interactive version of the next edition of the book ``Algorithms in Real Algebraic Geometry'' by S. Basu, R. Pollack, M-F. Roy.
  As of this time, the SARAG library contains implementations of algorithms in the following domains: determinants and characteristic polynomials, theory of signed subresultants, Cauchy index and its applications, real roots isolation, sign determination of real roots, Thom encodings.
  The integration of SARAG in the book is extremely simple because the book is written in TeXmacs, which is designed to integrate text with various computer algebra systems.
  
  
• Charles Delzell  Suprema of infima of generalized rational functions
  Let R₊ denote the positive reals. We define a generalized polynomial to be a function resembling a polynomial function in R[x₁,...,x_n], but whose exponents are allowed to be arbitrary real numbers; it is real analytic on (R₊)ⁿ. Generalized rational functions are defined to be quotients of generalized polynomials.
  Let A be any subset of (R₊)ⁿ. Suppose f : A --> R is "piecewise generalized rational" (not necessarily continuous). We prove that there exist finitely many generalized rational functions s_jk such that for all x in A at which each s_jk is defined, f(x) = sup_j inf_k s_jk(x). The proof uses the fact that functions definable from generalized polynomials are polynomially bounded (Chris Miller, 1994).
  In 1987 we had proved an analogous result for (ordinary) piecewise-rational functions (with nonnegative integer exponents); there A was allowed to be any subset of Rⁿ, where R was any real closed field; "Abstracts of Papers Presented to the Amer. Math. Soc." (1990), p. 337, # 858-14-80. That result would also follow from, but does not seem to imply, the Pierce-Birkhoff conjecture (1956): every *continuous* piecewise-polynomial function f : Rⁿ --> R is sup_j inf_k s_jk, for finitely many s_jk in R[x₁,...,x_n]. This conjecture is known only for n < 3, in which case the analog for generalized polynomials has also been shown to hold (2005).
  
  
• Andreas Fischer  Zero-set property of infinitely Peano differentiable functions in o-minimal structures
  Let M be an o-minimal expansion of the real field which is not polynomially bounded. Provided that we have P^\infty (infinitely Peano differentiable)  cell decomposition we show that each definable closed set is the zero set of a definable P^\infty function. The validity of the corresponding result for C^\infty is not yet known.
  
  
• Jose F. Fernando Galvan  On the Hilbert 17th problem for global analytic function in dimension 3
  Among the invariant factors g of a positive semidefinite analytic function f on R³, those g whose zero set Y is a  curve are called special. We show that if each special g is a  sum of squares of global meromorphic functions on a neighbourhood of  Y, then f is a sum of squares of global meromorphic functions. Here  sums can be (convergent) infinite, and we also find some sufficient  conditions to get finite sums of squares. In addition, we   construct several examples of positive semidefinite analytic functions which are infinite sums of squares but maybe could not be finite sum of squares.
  
  
• Xavier Goaoc Visibility computations on 3-dimensional algebraic objects
  Real algebraic geometry questions naturally arise in the design of robust algorithms, i.e. algorithms that are provably correct on arbitrarily degenerate inputs. I will discuss two problems related to visibility computations in three dimensions where some solutions have been obtained by a dialogue between algebraic and computational geometers:
  - what are the configurations of 4 real spheres in R³ that have infinitely many common real tangent lines?
  - how to make correct and efficient decisions in the course of an algorithm?
  
  
• Laureano Gonzalez Vega  Real Algebraic Geometry in Industry: the Computer-Aided Design example
  By using the surface--to--surface intersection problem as motivation, it will be shown how Real Algebraic Geometry can be very helpful in order to remove some of the limitations of current Computer-Aided Design technology. These limitations  are due to conflicts between the underlying mathematical background and the capabilities expected by various application areas where Computer-Aided Design is one of the main working tools.
  It will be also shown how the current technology has gradually evolved from very simple objects (polyhedra and natural quadrics) to include free-form objects, but without taking into account the mathematical background sufficiently.  And some of the resulting problems will be solved by changing the underlying paradigms and using, for example, language (semialgebraic sets) and techniques (quantifier elimination) from Real Algebraic Geometry.
  
  
• Deirdre Haskell  Being integral
  In a valued field, it is natural to ask for an algebraic characterisation of rational functions which always take integral values, in the sense of the valuation. We call such a result a ganzestellensatz, by analogy with a positivstellensatz in real algebraic geometry. Based on a lemma of Kochen, Yoav Yaffe and I have given a model theoretic argument for deriving ganzestellensatze in different theories of valued fields. In this talk, I will explain the general result, and show how to apply it in particular to real closed valued fields.
  
  
• Didier Henrion  Algebraic formulations of some basic control problems
  In control theory, the problems that are very easy to formulate are quite often those that are difficult to solve numerically. A typical example is static output feedback stabilization: given real matrices A,B,C with A square of size n, find (numerically or symbolically) a real matrix K such that all the eigenvalues of the matrix A+BKC belong to the open left half of the complex plane. This problem has attracted the attention of researchers for many decades. Using polynomial root location conditions by Routh and Hurwitz or Hermite, the semialgebraic set of solutions to this problem can be explicitely described. However, up to our knowledge, there is currently no efficient algorithm that can find a point within the set (or detect emptiness of the set) for physically relevant problem dimensions, say n>7. Best available computer software generally fail for various reasons (problem ill-conditioning, instability of the algorithms, huge computational burden), and meaningul solutions can only be obtained after a tedious and time-consuming parameter tuning based on some physical insight provided by the designer.
  In this talk we will describe several similar open control problems, focusing on their algebraic formulations. We will provide simple illustrative examples that should help understand the basic mathematical statements without any specific control background.
  
  
• Michael Kettner Computing the first Betti numbers
  We describe an algorithm for computing the zero-th and the first Betti numbers of the union of n simply connected compact semi-algebraic sets  in R^k where each such set is defined by a constant number of  polynomials of constant degrees. The complexity of the algorithm is O(n³).We also describe an implementation of this algorithm in the particular case of arrangements of ellipsoids in R³ and describe some of our results.
  
  
• Igor Klep A Stellensatz for nowhere negative semidefinite polynomials
  Helton recently proved that a symmetric polynomial in noncommuting  variables is positive semidefinite on all bounded self-adjoint  operators iff it is a sum of hermitian squares. We characterize those polynomials which are nowhere negative semidefinite on certain  `bounded basic closed semialgebraic sets' of bounde operators. The obtained representation for these polynomials involves multipliers  analogous to the representation known from the classical commutative Positivstellensatz. (Joint work with Markus Schweighofer)
  
  
• Salma Kuhlmann Positive polynomials and Invariant theory
  Let R be a real closed field, G a linear algebraic group over R, V an affine R-variety, and V(R) the set of R-points on V. We assume that G acts on V, and consider the induced dual action on the coordinate ring R[V]. If G is reductive, then the subring R[V]^G consisting of G-invariant elements is finitely generated. In this setting, given an invariant closed semi-algebraic subset K of V(R), we study the problem of approximating invariant non-negative polynomials on K by sums of squares. To this end, we analyse the relation between quadratic modules of R[V] and associated quadratic modules of R[V]^G. We apply our results to investigate the finite solvability of an equivariant version of the K-moment problem. (Joint work with Scheiderer and Cimpric).
  
  
• Jean-Bernard Lasserre SOS approximations of nonnegative polynomials
  We show that every real polynomial f nonnegative on [-1,1]ⁿ can be approximated in the l₁-norm of coefficients, by a sequence of polynomials {f_r}$ that are sums of squares. This complements the existence of s.o.s. approximations in the denseness result of Berg, Christensen and Ressel, as we provide a very simple and explicit approximation sequence. Then we show that if the Moment Problem holds for a basic closed semi-algebraic set with nonempty interior, then every polynomial nonnegative on this set can be approximated in the same way by elements from the corresponding preordering. Last we consider possible bounds on the degree of the approximating sequence.
  
  
• Nicolas Lerner Writing nonnegative functions as sum of squares
  We prove a decomposition of C^3,1 nonnegative functions as a sum of squares of C^1,1 functions with sharp estimates. In particular, we prove that a C^3,1 nonnegative function a can be written as a finite sum  a = b₁² + ... + b_N², where each b_j is C^1,1, but also where each function b_j² is C^3,1. We provide as well some bounds on (b_j' b_j")' and on (b_j b_j")".
  
  
• Henri Lombardi About "Sums of Squares" of Kreisel
  I shall try to give a "simple" deciphering of one of the sketches presented by G Kreisel (in the cited report), in order to construct the sum of squares in the solution of 17th Hilbert's Problem
  
  
• Assia Mahboubi Implementation and Certification of a CAD Algorithm
  A. Tarski has shown in 1948 that one can perform quantifier elimination in the theory of real closed fields. The introduction of the Cylindrical Algebraic Decomposition (CAD) method has later allowed to design rather feasible algorithms. Our aim is to program a reflectional decision procedure for the Coq system, which is a proof assistant based on the Calculus of Inductive Constructions.
  Using the CAD algorithm, we will be able to decide - and prove - whithin the system, whether a (possibly multivariate) system of polynomial inequalities with rational coefficients has a solution or not. We have therefore implemented various computer algebra tools like gcd computations, subresultant polynomials or real root isolation. We will present the Coq system, explain the design of such a procedure and the sketch of the formal proofs invoved.
  
  
• Murray Marshall  Boundary Hessian conditions and sums of squares
  There is a certain natural sufficient condition for a (polynomial) function to achieve a local minimum at some fixed point in a basic closed semialgebraic set K. We refer to this as the boundary Hessian condition. For an interior point of K it is just the standard Hessian condition (2nd derivative test) for local minima. Polynomial functions f which achieve a minimum value on K and are such that f satisfies the boundary Hessian condition at each minimum point on K are especially well behaved, and tend to have good representations in terms of sums of squares. This statement will be made more precise, and the application of this to optimization on a compact set K and to global optimization will be explained. Parts of the theory holds over an arbitrary real closed field, and this can be exploited to obtain degree bounds for representations in certain cases.
  
  
• Francisco Miraglia Algebraic K-theory of Special Groups
  In joint work with M. Dickmann, we describe how the K-theory functor associated to special groups behaves under certain natural operations, such as finite products, inductive limits and extensions. Moreover, we give a characterization of all graded ring morphisms in K-theory for a wide variety of special groups, including those of fields and semilocal rings.
  
  
• Tim Netzer The moment problem and representations of polynomials
  We consider a generalization of a theorem by Marshall, Kuhlmann and Schwartz which states sufficient conditions for the so called "double-dagger-condition" to hold. This condition yields a certain representation for polynomials nonnegative on a basic closed semi-algebraic set. From the theorem we deduce that the preordering PO(X,Y,1-XY) has this property .
  
  
• Dima Pasechnik Algebraic reduction of symmetric semidefinite programs with application to bounding crossing numbers of K_m,n ( joint work with E. de Klerk and A. Schrijver).
  Algebraic properties of semidefinite programming problems (SDP) depend upon their matrix data A₀,....,A_d, in particular, upon the algebra A generated by the A_i's. In particular, one can solve essentually the same SDP in another faithful C*-representation of A. This generalizes to a non-commutative setting an old idea of Delsarte used originally to obtain bounds on binary codes (the latter boils down to SDPs given by certain commuting matrices A_i's.)
  We apply this approach to obtain an efficient relaxation for computing minima of symmetric, w.r.t. certain groups, quadratic forms on the unit simplex. We use the latter to obtain new lower bounds on the crossing number of the complete bipartite graph K_m,n.
  Reference: Reduction of symmetric semidefinite programs using the regular *-representation, e-print nr. 2005-03-1083 at Optimization Online, to appear in Math. Prog. B
  
  
• Marc Pouget Ridges and umbilics of polynomial parametric surfaces
  Given a smooth surface, a blue (red) ridge is a curve along which the maximum (minimum) principal curvature has an extremum along its curvature line. Ridges are curves of extremal curvature and therefore encode important informations used in segmentation, registration, matching and surface analysis.
  State of the art methods for ridge extraction either report red and blue ridges simultaneously or separately ---in which case a local orientation procedure of principal directions is needed, but no method developed so far topologically certifies the curves reported.
  First, for any smooth parametric surface, we exhibit the implicit equation P=0 of the singular curve P encoding all ridges of the surface (blue and red), and analyze its singularities.
  Second, for a polynomial surface this equation defines an algebraic curve. We develop the first certified algorithm to produce a topologically certified approximation of the curve P. The algorithm exploits the singular structure of P --umbilics and purple points, and reduces the problem to solving zero dimensional systems using Rational Univariate Representations and isolate roots of univariate polynomials with rational coefficients. Experiments illustrate the efficiency of the algorithm on a Bezier patch.
  
  
• Alex Prestel  Archimedean quadratic modules
  Let h₁,...,h_m be finitely many real polynomials that define a non-empty basic closed semi-algebraic set W(h) in the affine n-dimensional real space. If the quadratic module M(h) generated by 1,h₁,...,h_m is archimedean, then every polynomial strictly positive on W(h), belongs to M(h), i.e., it has a representation
  
  f = s₀ + s₁.h₁ + ...+ s_m.h_m
  
  where all s_i are sums of polynomial squares. We shall discuss the Jacobi-Prestel Criterion for M(h) to be archimedean and explain an effective algorithm in dimension 2 to decide this. The last result is contained in the Ph.D. Thesis of Eugenia Cabral.
  
  
• Mohab Safey Putting the Critical Point Method Into Practice: Practical and Theoretical Issues
  This talk is in the continuity of the part of the course "Algorithms in Real Algebraic Geometry" provided by M.-F. Roy where algorithms computing sampling points in semi-algebraic sets are designed within a complexity which is polynomial in the Bézout bound and a combinatorial factor by the use of the critical point method (the complexity constant being here as an exponent).
  I will first overview the geometric developments which are required to obtain efficient algorithms in the case of real algebraic sets : the implicit aim is to design geometric procedures reducing as much as possible the size of the output and intermediate data in terms of geometric invariants (namely the geometric degree of the studied algebraic varieties).  Then, I will report on recent complexity results on Grobner bases due to Bardet, Faugère and Salvy on the one hand, and on Geometric resolution due to Lecerf on the other hand, which allow to provide complexity estimates of the presented algorithms where the complexity constant appearing as an exponent is less than the original algorithms due to Basu, Pollack and Roy.
  I will end with some perspectives by showing the practical interest of the use of the notion of generalized critical values introduced by Kurdyka, Orro, and Simon in algorithms dealing with semi-algebraic sets.
  Some parts of these works are joint with E. Schost (LIX, Ecole polytechnique) and separately with P. Trebuchet (LIP6, Paris 6 University).
  
  
• Claus Scheiderer Nichtnegativstellensätze for semi-algebraic sets of dimension two
  Let polynomials h₁, ..., h_r in R[x,y] be given, and assume that the semi-algebraic subset K = {h₁ >= 0 ,..., h_r >= 0} of R² is compact. We will discuss the question whether every polynomial which is non-negative on K is contained in the preordering T generated by h₁, ..., h_r. If this is the case, one says that T is saturated. The main point will be to reduce the problem to power series rings. From our results we will obtain plenty of new cases where T is saturated.
  
  
• Niels Schwartz  Convex subrings and convex extensions of partially ordered rings
  The formation of convex subrings is a natural and important construction with partially ordered rings (=porings). Convex subrings of rings with bounded inversion are quite well understood; otherwise very little is known. For example, it is not known how one can recognize whether a given poring has a convex extension, i.e., whether it is contained as a convex subring in another poring. First steps towards a systematic study of convex extensions will be explained.
  
  
• Markus SchweighoferPure states on ideals and nonnegative polynomials
  Consider a real vector space equipped with a convex cone. A state is a linear form sending the cone into the nonnegative reals. A pure state is a state that cannot be written as sum of other states in a non-trivial way. By an old theorem of Eidelheit, if the convex cone has an algebraic interior point, then a vector on which every pure state takes only positive values must belong to the cone.
  Now consider, for example, the case where the vector space is the polynomial ring in several variables and the cone is an archimedean subsemiring. By old theorems, the pure states are exactly the ring homomorphism into the reals preserving the subsemiring. Eidelheit's theorem therefore yields the representation theorem of Stone-Krivine-Kadison.
  We consider important cases where the vector space is an ideal in the polynomial ring. We prove theorems about the pure states which remind of blowing up from algebraic geometry. These new results yield together with Eidelheit's theorem new proofs for Jacobi's representation theorem for quadratic modules, for some of Scheiderer's theorems on nonnegative polynomials with zeros and for other old and new results.
  
  
• Frank Sottile The Shapiro conjecture
  

  About 10 years ago, Boris Shapiro and Michael Shapiro made a remarkable conjecture about real solutions to geometric problems coming from the classical Schubert calculus. While the conjecture remains open, there is truly overwhelming computational evidence supporting it, and Eremenko and Gabrielov proved it for Grassmannians of 2-planes, where the conjecture is the appealing statement that a rational function with only real critical points must be real. In my talk, I will introduce the Shapiro conjecture and discuss what we know about it. This includes a simple counterexample and a refinement which is supported by massive experimental evidence. This evidence includes tantalizing computations which suggest a strengthening: that a certain discriminant polynomial is a sum of squares, or more generally that it has such an algebraic certificate of positivity.

  
  
• Ahmed Srhir Towards a Nullstellensatz for the ring Q_p[[X]]
  We give in this lecture the ingredients for a proof of the Nullstellensatz for the ring Q_p[[X]] of power series with coefficients in the field Q_p of  p-adic numbers.
  
  
• Jean-Pierre Tecourt  Isotopic meshing of a real algebraic surface
  I will present an algorithm for computing an isotopic meshing of a real (singular) implicit surface. The correctness of the algorithm requires singularity theory, in particular we will show how to compute a Whitney stratification of the surface from resultant computation. We will also deduce from the algorithm an upper bound on the number of isotopy types of real algebraic surfaces. (Joint work with Bernard Mourrain).
  
  
• Marcus Tressl Abstract semi-algebraic functions of class C^k
  For every ring A (commutative, unital) one can construct so-called abstract semi-algebraic functions of A. The set of these functions carries a ring structure and the rings obtained in this way are the so - called real closed rings. Intuitively these are the rings of global sections of the sheaf of continuous functions on the real spectrum of A. I will generalize this construction to semi-algebraic functions of class C^k and give applications to the real spectrum.
  
  
• Roman Wencel Topological properties of sets definable in weakly o-minimal structures
  The notion of weak o-minimality was introduced by M. Dickmann and developed by D. Macpherson, D. Marker, C. Steinhorn and others. A structure , where is a dense linear ordering without endpoints, is called weakly o-minimal iff every subset of , definable in , is a finite union of convex sets. The ordering of induces a topology on , . Although there is no anologue of cell decomposition in general weakly o-minimal structures, we have a resonably behaving notion of dimension for definable sets. For an infinite definable set , we define , the dimension of , as the maximal for which there is a projection such that contains an open box. We say that if is nonempty and finite. To an empty set we ascribe dimension . In the first part I will present my development of the work of Macpherson, Marker and Steinhorn discussing several results concerning the topological dimension for definable sets.

  A substantial part of the talk will be devoted to the geometry of definable sets in a very special class of weakly o-minimal structures, namely weakly o-minimal non-valuational expansions of ordered groups. A weakly o-minimal structure expanding an ordered group is said to be non-valuational iff for any cut which is definable in , we have that . A weakly o-minimal expansion of a real closed field is non-valuational iff has no non-trivial valuations definable in . The geometry of sets definable in weakly o-minimal non-valuational expansions of ordered groups (fields) is closely related to the geometry of sets definable is o-minimal expansions of ordered groups (fields). In the weakly o-minimal non-valuational case, I will discuss an o-minimal style cell decomposition theorem and some of its most important consequences generalizing a relevant part of o-minimal geometry.

  
  
• Philippe Wenger Classification of Cuspidal Robots
  This lecture illustrates an application study of Real Algebraic Geometry in robotics, which has been conducted in the frame of a CNRS research program between IRCCyN, IRMAR and INRIA. The aim of this study is to classify a family of robots, according to  several global kinematic properties such as the number of inverse kinematic  solutions in the robot workspace and the ability of the robot to move from  one solution to another without meeting a singularity. These properties can  be set as the existence condition of real multiple roots in a fourth-degree  polynomial, which depends on several variables that need to be eliminated.  Separating surfaces are derived as polynomials in the design parameters,  which induce a partition of the design space into connected components in  which all robots have "similar properties". This classification is of interest for the design of new robots.

Back to the programme of the workshop