RAAG Server: Research activities

The Network's research plans

The network will concentrate its research efforts on the core areas of RAAG, which are: Real Geometry the study of geometric objects arising from the real numbers; Real Algebra the study of algebraic systems, in particular function rings, that arise in real geometry; Algorithms and Complexity the study of computational methods, including applications in an industrial context. This section contains a description of these subtopics together with a number of major problems that guide the current development of RAAG. The network will work towards each of these goals; major advances are anticipated the expected progress is described in the section "4 Work Plan".

A. Real Geometry Rings of polynomial functions have their origin in the arithmetic operations of the real numbers. Larger classes of functions occur in applications, e.g., analytic functions that arise as solutions of differential equations in physics or engineering. The most basic objects in real geometry are real algebraic varieties and real analytic varieties, the solution sets of equations between polynomial functions or analytic functions. A large class of important geometric forms, such as a square in the plane, a connected component of a real variety or a solid model in Computer Aided Design, become accessible to real geometry if inequalities, instead of only equalities, are used to define geometric objects. This leads first to the study semialgebraic sets and semianalytic sets, and eventually to tame geometry, which also encompasses o-minimal structures. Tame geometries are flexible, being stable under a small number of geometric constructions, and are of a finitary nature, which makes them amenable to explicit computations and to an intuitive geometric understanding. Collectively, the various geometric objects of real geometry are referred to as real spaces.

Every real space carries a topology; the underlying space is the topological space which is obtained if all other structure associated with a real space is disregarded. Underlying spaces are a source of important and difficult problems, first of all the Realization Problem: Given a class of real varieties or real spaces, such as hypersurfaces of a given degree, what are the underlying spaces? Invariants, among them the classical invariants of algebraic topology (homotopy groups... ), are important tools they help to recognize restrictions on those spaces that occur as underlying spaces. A variant of the first question is the Problem: What values does a given invariant assign to the underlying spaces of some class of real spaces? E.g., which are the sequences of Betti numbers that are associated with real varieties?

An invariant always assigns the same value to two isomorphic real spaces, for nonisomorphic spaces the values may be different. Thus, invariants play a large role in the Classification Problem: Describe the different isomorphism types in a given class of real spaces or of underlying spaces. One looks for a set of invariants such that two spaces are isomorphic exactly when they have the same values under all invariants. For any particular class of spaces, suitable invariants for this task have to be identified or devised. Problem: Find new, more sensitive invariants, using new constructions such as algebraically constructible or arc-analytic functions, or refining existing invariants such as homology groups of real varieties by considering algebraic homology classes.

Real spaces have a rich structure that is important both for their intuitive understanding and for applications, but cannot be explained solely in terms of invariants or the underlying topology. Problem: Study singularities, as well as the combinatorial and differential structure of real spaces, of Pfaffian and dynamical systems, e.g., using triangulations and stratifications. Problem: Study metric properties of real spaces to obtain measures of curvature and extend classical formulas of differential geometry, such as the formula of Gauss-Bonnet, to new classes of spaces.

Maps are ubiquitous in real geometry as the means to relate different spaces to each other; thus the study of maps is as important as the study maps of spaces. Parts of real algebra, to be discussed below, can be seen as a study of maps. There are also geometric questions concerned with maps, some are about individual maps, others about sets of maps. Problem: Given a map between two real spaces: What is its image? Which maps are triangulable, when are triangulations unique? What is the behavior at asymptotic critical values? Problem: What is the precise relationship between the space of continuous maps and the subset of regular maps from one real algebraic variety into another one?

B. Real Algebra Function rings are basic algebraic tools in RAAG, e.g., polynomial functions, analytic functions, semialgebraic functions. The part of real algebra concerned with function rings contributes to the study of maps in real geometry. For a unified treatment it is useful to include also general rings. Often the rings are equipped with some additional structure: quadratic forms, partial orders, or valuations, that reflect the realness of the context. Rings intervene in the definition of many real spaces; thus linking algebra and geometry together inseparably: Real algebra, the study of these algebraic systems, is an indispensable part of RAAG.

It is an important task of real algebra to relate algebraic and geometric structures to each other. A successful method is to construct spectra, most prominently the real spectrum, from the data supplied by a ring. They are interpreted as new classes of geometric objects the given ring is viewed as a ring of functions on the spectrum. Problem: Study spectra, the real spectrum, the order spectrum, the valuation spectrum, and possibly others, their topological and geometric properties, their role as a link between algebra and geometry.

Positivity of functions is a key notion in real algebra; thus it is the object of intensive investigations, both qualitative and quantitative. Problem: Given a ring of functions on a real space: How does one recognize which functions are nonnegative? Do they have some standard representation, e.g., as sums of squares (cf. Hilbert's 17-th Problem)? Problem: What are the structure and the properties of the collection of all positive functions?

The rings of real algebra are highly complex structures, they follow their own rules and introduce phenomena that cannot be accounted for in purely geometric terms. Problem: A systematic study of preordered rings, partially ordered rings and of rings with valuations by algebraic, model theoretic and category theoretic techniques. This task includes as a particularly important part the Problem: Study algebraic constructions with preordered and partially ordered rings: closure constructions, real holomorphy rings, rings of quotients.

C. Algorithms and Complexity Applications of RAAG in industrial and scientific environments require explicit computations. Many algebraic and geometric structures in RAAG are of a finitary nature and are therefore amenable to computer based methods. Complexity studies determine upper and lower bounds for the difficulty of particular problems. Given an algorithm, its complexity can be compared with such bounds to recognize whether it is an efficient tool or not. Frequently computational tasks in RAAG can be formulated as quantifier elimination (QE) problems. The complexity of QE and other fundamental methods is so large that general purpose algorithms are not suitable for practical applications. The design of efficient methods always depends on a careful analysis of the particular problem at hand.

Some computational tasks play a key role since they occur in many applications. Efficient methods for their solution, or a better understanding of their complexity, are of central importance. Problem: Study complexity questions connected with the real Nullstellensatz and the Positivstellensatz. Problem: Find an efficient algorithm to decide whether a function is nonnegative on some semialgebraic set, or to determine its minimum value. Problem: Design an efficient algorithm that determines whether a semialgebraic set is nonempty (e.g., using the critical point method), or, more ambitiously, solves a system of inequalities.

Explicit computations concerning the geometry of real spaces are important both for a better understanding of the spaces, but also for their use in applications. Problem: Design algorithms that compute the topological type or invariants (dimension) of a real space.

Pfaffian functions arise in applications as solutions of algebraic differential equations. They are of a finitary nature and are the source of o-minimal structures. Problem: Is it possible to extend computational methods and complexity results from semialgebraic geometry to Pfaffian functions, or to even more general o-minimal structures?

The use in industrial processes is one ultimate goal of efficient computations. Recent progress proves that this goal can be achieved; but much remains to be done. Problem: Identify tasks (e.g. in robotics, control theory, network design, ) that are accessible to the computational tools of RAAG, and provide an efficient solution