The Membership Problem for quadratic modules with focus on the one dimensional case

Abstract (English)

The Membership Problem for a subset Q of the polynomial ring R[X] over a real closed field R asks: Is there an algorithm to decide whether a given polynomial f lies in Q or not? For the case of a finitely generated quadratic module Q of IR[X] in dimension 1 we succeed and solve the Membership Problem affirmatively. We achieve the solution by first showing that Q is definable or equivalently ...

Abstract (English)

The Membership Problem for a subset Q of the polynomial ring R[X] over a real closed field R asks: Is there an algorithm to decide whether a given polynomial f lies in Q or not?

For the case of a finitely generated quadratic module Q of IR[X] in dimension 1 we succeed and solve the Membership Problem affirmatively. We achieve the solution by first showing that Q is definable or equivalently weakly semialgebraic. The positive solution of the Membership Problem then follows by Tarski�s result about the decidability of the theory of real closed fields in the language of ordered rings. If the basic closed semialgebraic set associated to Q is bounded we explicitly describe the algorithm.

Under the additional assumption that the basic closed semialgebraic set associated to the finitely generated quadratic module Q is finite, we obtain a positive solution of the Membership Problem as well as an explicit algorithm also over arbitrary real closed fields R.

Furthermore we generalize the model theoretic concept of heirs which plays an important role in the solution of the Membership Problem for orderings. We define the heir of an arbitrary subset Q of R[X] on a real closed extension field R� of R as a certain subset of R�[X] such that the definability of Q becomes equivalent to the existence of a unique heir on every real closed extension field of R. This is a main tool for a possible affirmative answer to the Membership Problem in arbitrary dimension.
For the case of a finitely generated quadratic module Q of IR[X] in dimension 1 we explicitly compute the heirs on real closed extension fields of IR, if the basic closed semialgebraic set associated to Q is not empty and bounded.

Translation of the abstract (German)

Das Mitgliedschaftsproblem für eine Teilmenge Q des Polynomrings R[X] über einem reell abgeschlossenen Körper R fragt, ob es einen Algorithmus gibt, der für ein gegebenes Polynom f entscheidet, ob f in Q liegt oder nicht. Für den Fall eines endlich erzeugten quadratischen Moduls Q in IR[X] in Dimension 1 geben wir in dieser Arbeit eine positive Antwort auf das Mitgliedschaftsproblem. Die Lösung ...

Translation of the abstract (German)

Das Mitgliedschaftsproblem für eine Teilmenge Q des Polynomrings R[X] über einem reell abgeschlossenen Körper R fragt, ob es einen Algorithmus gibt, der für ein gegebenes Polynom f entscheidet, ob f in Q liegt oder nicht.

Für den Fall eines endlich erzeugten quadratischen Moduls Q in IR[X] in Dimension 1 geben wir in dieser Arbeit eine positive Antwort auf das Mitgliedschaftsproblem. Die Lösung erreichen wir dadurch, dass wir zunächst zeigen, dass Q definierbar bzw. schwach semialgebraisch ist. Mit Hilfe des Ergebnisses von Tarski über die Entscheidbarkeit der Theorie der reell abgeschlossenen Körper in der Sprache der angeordneten Ringe folgt dann die positive Lösung des Mitgliedschaftsproblems. Falls die zu Q korrespondierende basisch abgeschlossene semialgebraische Menge beschränkt ist, beschreiben wir den Algorithmus explizit.

Unter der zusätzlichen Voraussetzung, dass die zum endlich erzeugten quadratischen Modul Q korrespondierende basisch abgeschlossene semialgebraische Menge endlich ist, erhalten wir eine positive Lösung des Mitgliedschaftsproblems einschließlich eines expliziten Algorithmus auch über einem beliebigen reell abgeschlossenen Körper R.

Darüber hinaus verallgemeinern wir das modelltheoretische Konzept der Erben, das bei der Lösung des Mitgliedschaftsproblems für Anordnungen eine entscheidende Rolle spielt. Wir definieren den Erben einer beliebigen Teilmenge Q von R[X] auf einem reell abgeschlossenen Oberkörper R� von R als diejenige Teilmenge von R�[X], so dass die Definierbarkeit von Q zur Existenz eines eindeutigen Erben in jedem reell abgeschlossenen Erweiterungskörper von R äquivalent wird. Dies ist ein entscheidendes Hilfsmittel für eine mögliche positive Lösung des Mitgliedschaftsproblems in beliebiger Dimension.
Für den Fall eines endlich erzeugten quadratischen Moduls Q in IR[X] in Dimension 1 berechnen wir explizit die Erben auf reell abgeschlossenen Erweiterungskörpern von IR, falls die zu Q korrespondierende basisch abgeschlossene semialgebraische Menge nichtleer und beschränkt ist.

Details

Preview

Export bibliographical data

Abstract (English)

Abstract (English)

Translation of the abstract (German)

Translation of the abstract (German)

Download Statistics

Downloads

More literature (via CORE)

University Library