Pozitivni polinomi in realna algebraična geometrija

predavatelja Jaka Cimprič (1. semester) in Igor Klep (2. semester)



Prva domača naloga.

Druga domača naloga.

Povzetki predavanj:
  1. Definirali smo pojem semialgebraične množice v Rn. Definirali smo tudi naslednje razrede smialgebraičnih množic: realne algebraične množice, zaprte oz. odprte bazične semialgebraične množice, bazične semialgebraične množice. Pokazali smo,
  2. Definirali smo pojem semilinearne in bazične semilinearne množice v Rn. Vsaka semilinearna množica je končna unija bazičnih semilinearnih množic oblike {P1=0,...,Pk=0,Q1>0,...,Ql>0}. Semilinearne množice v R1=R ravno končne unije točk, intervalov in poltrakov.

    S pomočjo Fourier-Motzkinove eliminacije smo dokazali, da je projekcija bazične semilinearne množice (iz Rn+1 v Rn vzdolž xn+1) spet bazična semilinerana množica. Odtod sledi, da je projekcija semilinarne množice spet semilinearna množica. Na primeru {(A,B,X) | A+BX=0} smo se prepričali, da projekcija bazične semialgebraične množice ni nujno bazična semialgebraična množica. Na koncu smo formulirali izrek Tarskega, ki pravi, da je projekcija semialgebraične množice spet semialgebraična množica.

  3. Definirali smo pojem formule prvega reda in formule brez kvantifikatorjev (v jeziku urejenih obsegov s parametri v R). Pokazali smo, da so semialgebraične množice ravno množice, ki so definirane s formulami brez kvantifikatorjev. Iz izreka Tarskega sledi, da so tudi množice, ki so definirane s formulami prvega reda, semialgebraične. Torej je vsaka formula prvega reda ekvivalentna formuli brez kvantifikatorjev. Kot primer uporabe smo pokazali, da sta zaprtje in notranjost semialgebraične množice spet semialgebraični množici in da je kompozitum semialgebraičnih funkcij spet semialgebraična funkcija. (Semialgebraična funkcija je funkcija med dvema semialgebraičnima množicama, katere graf je semialgebraična množica.) Omenili smo tudi semilinearne verzije teh rezultatov.

    O zaptjih semilinearnih množic lahko povemo še več. Dokazali smo, da je zaprtje neprazne bazične semilinearne množice {P1 ≥ 0,...,Pk ≥ 0,Q1>0,...,Ql>0} enako {P1 ≥ 0,...,Pk ≥ 0,Q1≥0,...,Ql≥0}, notranjost pa je enaka {P1 > 0,...,Pk > 0,Q1>0,...,Ql>0}. (Odtod takoj sledi semilinearna verzija izreka o končnosti. Spotoma smo dokazali semilinearno verzijo leme o izbiri krivulje.) Podoben rezultat za semialgebraične množice ne velja, saj zaprtje množice {(X,Y) | Y 2 < X3-X2} ni enako {(X,Y) | Y 2 ≤ X3-X2}.

  4. Formulirali smo izrek o cilindrični algebraični dekompoziciji in ga ilustrirali na primeru. Spotoma smo spoznali, kako cilindrični algebraični dekompoziciji priredimo tabele predznakov. Pokazali smo tudi, da iz tega izreka sledi izrek Tarskega. Nato smo se lotili dokaza:

    1. korak Končni množici S v R[X1,...,Xn,T] priredimo njeno Muchnikovo zaprtje CS. To je najmanjša množica, ki je zaprta za operacije D=odvajanje po T, O=opustitev člena z najvišjo potenco T in prem = psevdoostanek pri psevdodeljenju dveh polinomov. Dokazali smo, da je množica CS končna in da za vsak element p=cd Td+... iz CS tudi E(p)=d! cd pripada CS.

    2. korak Naj bo CS0={p1,...,ps} množica vseh polinomov v CS, ki so stopnje 0 v T (=T-konstantnih polinomov). Za vsak ε=(ε1,...,εs} iz {-1,0,1}s definiramo množico Aε={sign p11,...,sign pss}. Množice Aε so iskana dekompozicija množice Rn. Prihodnjič bomo razrezali še cilindre Aε × R.

  5. Dokončali smo dokaz izreka o cilindrični algebraični dekompoziciji. Celoten dokaz je tukaj.

  6. Dokazali smo, da so funkcije ξj, ki nastopajo v cilindrični algebraični dekompoziciji zvezne in semialgebraične. Odtod smo izpeljali, da je vsaka semialgebraična množica disjunktna unija semialgebraičnih množic, ki so semialgebraično homeomorfne (0,1)d za primeren d. Odtod sledi, da imajo semialgebraične množice končno komponent povezanosti in da lahko na smiseln način definiramo dimenzijo. Na koncu smo definirali pojem kvazieničnega polinoma in dokazali Noethersko normalizacijo, ki jo bomo potrebovali prihodnjič pri obravnavi Thomove leme s parametri.

  7. Dokazali smo Thomovo lemo in Thomovo lemo s parametri. Celoten dokaz je tukaj.

  8. Dokazali smi izrek o stratifikaciji in nekaj posledic, recimo izrek o končnosti, lemo o izbiri krivulje, dobro definiranost dimenzije. Omenili smo tudi izrek o triangulaciji (vsaka semialgebraična množica je semialgebraično homeomorfna omejeni semilinearni množici) ter skicirali idejo dokaza. Drugo uro smo definirali urejene obsege in dokazali, da relacijo urejenosti lahko podamo tudi s pozitivnim stožcem. Definirali smo tudi pojem predureditve in prave predureditve in dokazali, da je maksimalna predureditev ureditev. Odtod smo izpeljali, da ima dani obseg ureditev natanko tedaj, ko v njem -1 ni vsota kvadratov.

  9. Predavanja so odpadla zaradi bolezni predavatelja.

  10. Dokazali smo, da je vsaka predureditev presek vseh ureditev, ki jo vsebujejo. Definirali smo pojem razširitve ureditve. Formulirali smo leme o razširjanju ureditev na kvadratne razširitve, razširitve lihe stopnje in transcendentne razširitve. Definirali smo pojem maksimalno urejenega obsega in realno zaprtega obsega ter dokazali lemo o zvezi med tema dvema pojmoma.

  11. Dokazali smo eksistenco realnega zaprtja in podali nekaj primerov. Dokaz enoličnosti smo izpustili. Dokazali smo karakterizacijo realno zaprtih obsegov. Dokazali smo tudi verzijo izreka o vmesno vrednosti in Rolleovega izreka za realno zaprte obsege. Formulirali smo tudi princip prenosa.
  12. Dokazali smo princip prenosa. Kot posledico smo dokazali, da je vsak realen polinom, ki je povsod nenegativen, enak vsoti kvadratov racionalnih funkcij. Nato smo definirali pojem ureditve na kolobarju. Realni spekter kolobarja je množica vseh njegovih ureditev. Definirali smo konstruktibilno, Harrisonovo in Zariskijevo topologijo na realnem spektru. Povedali smo, kako se prostor Rn vloži v realni spekter kolobarja R[X1,...,Xn]. Povedali smo tudi, da je slika te vložitve gosta v konstruktibilni topologiji realnega spektra, nismo pa še dokazali.

  13. Algebrajska in geometrijska verzija izreka o pozitivnosti. Podrobnosti so tukaj.



Literatura za 1. semester:

Knjige in skripte:
  1. S. Basu, R. Pollack, M.-F. Roy, Algorithms in real algebraic geometry. Springer, Berlin, 2003, viii+602 strani, signatura 11947/10. Novejše izdaje so dostopne tukaj.
  2. J. Bochnak, M. Coste, M.-F. Roy, Real algebraic geometry. Springer, Berlin, 1998, x+430 strani, signatura 4185/36.
  3. M. Coste, An introduction to semialgebraic geometry. Dip. Mat. Univ. Pisa, Dottorato di Ricerca in Matematica, Istituti Editoriali e Poligrafici Internazionali, Pisa (2000), 77 strani, pdf - 1.1 MB.
  4. M. Coste, An Introductionto O-minimal Geometry. Dip. Mat. Univ. Pisa, Dottorato di Ricerca in Matematica, Istituti Editoriali e Poligrafici Internazionali, Pisa (2000). 81 strani. pdf - 1.1 MB.
  5. M. Coste, Real algebraic sets. Skripta 2005, 35 strani, pdf - 0.4 MB.
  6. C. N. Delzell, A. Prestel, Positive polynomials : from Hilbert's 17th problem to real algebra. Springer, Berlin, 2001, signatura 12678/9.
  7. L. v.d. Dries, Tame topology and O-minimal structures. Cambridge University Press, Cambridge, 1998, x+180 strani, signatura 6120/248.
  8. M. Knebusch, C. Scheiderer, Einführung in die reelle Algebra. Vieweg, Wiesbaden, 1989, vi+184 strani, signatura 11438/63. Dostopno tudi na: pdf - 3.8 MB.
  9. S. Lall, Advanced topics in computation and control, Skripta 2005, dostopna tukaj.
  10. C. W. Lee, Linear Programming Notes. Skripta 1996, pdf - 0.5 MB.
  11. M. Marshall, Positive polynomials and sums of squares. AMS, Providence, 2008, xii+187 strani, signatura 10503/146.
  12. P. Parrilo, Algebraic Techniques and Semidefinite Optimization. Skripta 2006, dostopna tukaj.
  13. A. Prestel, Reelle Algebra. Skripta 2008, ii+120 strani, pdf - 0.7 MB.
  14. C. Scheiderer, Reelle algebraische geometrie. Skripta 2008, iv+175 strani, pdf - 1.4 MB.
Članki in preprinti:
  1. H. Schoutens, Muchnick's proof of Tarski-Seidenberg. Preprint 2001, dostopen tukaj.
  2. C. Michaux, A. Ozturk, Quantifier elimination following Muchnik. Preprint 2002, dostopen tukaj.
  3. C. Andradas, R. Rubio, M.P. Vélez, An Algorithm for convexity of semilinear sets over ordered fields. Preprint 2006, dostopen tukaj.
  4. M. Jirstrand, Cylindrical algebraic decomposition - an introduction . Preprint 1995, dostopen tukaj.
  5. L. Bröcker, Semialgebraische Geometrie. Jahresber. Deutsch. Math.-Verein. 97 (1995), no. 4, 130--156.
  6. E. Becker, On the real spectrum of a ring and its application to semialgebraic geometry. Bull. Amer. Math. Soc. (N.S.) 15 (1986), no. 1, 19--60.
  7. T. Y. Lam, An introduction to real algebra. Ordered fields and real algebraic geometry (Boulder, Colo., 1983). Rocky Mountain J. Math. 14 (1984), no. 4, 767--814.
  8. L. v.d. Dries, Alfred Tarski's elimination theory for real closed fields. J. Symbolic Logic 53 (1988), no. 1, 7--19.
  9. M. Laurent, Sums of squares, moment matrices and optimization over polynomials. Preprint 2008, dostopen tukaj.
  10. B. Mishra, Computational Real Algebraic Geometry. Handbook of discrete and computational geometry, 537--556, CRC, Boca Raton, FL, 1997, dostopen tukaj