Academic literature on the topic 'Ensemble semi-algébrique'

On sait que par le choix d’ un langage suffisamment complexe, toute structure peut admettre une élimination des quantificateurs, malheureusement cette extension du langage peut nous éloigner des phénomènes algébriques. Nous allons nous intéresser à l’ élimination des quantificateurs pour des paires de corps. Dans le cas des paires de corps algébriquement clos et des paires denses de corps réel clos, on obtient une élimination en ajoutant au langage des prédicats ayant une signification algébrique: on peut les exprimer en disant que pour deux ensembles algébriques et donnés, il existe des points du sous-corps rationnels pour et pas pour , ou qu’ un ensemble semi-algébrique donné a des points rationnels sur le sous-corps. Robinson avait déjà abordé de façon informelle le cas des paires denses de corps réel-clos (cf. [Ro 2, p. 198]). Partant du langage des paires de corps ordonnés, enrichi de symboles de relations correspondant à l’ indépendance algébrique, il proposait d’ ajouter pas à pas des fonctions de Skolem Herbrand pour faire disparaitre les quantificateurs existentiels des formules, mais sans préciser le langage obtenu. Ici nous approchons le problème différemment en explicitant dès le départ le langage utilisé.Grâce à ces résultats nous pourrons étudier le cas des paires séparées de corps réels clos ainsi que des paires de corps valués henseliens. En élargissant la définition d’ ensemble algébrique à tous les symboles du langage, les prédicats relationnels ajoutés ont la même signification que dans le cas des paires de corps algébriquement clos.En comparant les techniques employées ici avec celles déjà utilisées dans [K], [B], [D 1] et [L], on remarque qu’il est possible de traîter une grande partie de l’ étude (complétude, modèle complétude, élimination des quantificateurs) des paires de corps algébriquement clos, réel-clos ou henseliens en se basant sur des prolongements d’ isomorphismes entre sous-structures dénombrables où l’ une des deux est contenue dans une structure ω1-saturée.

Par une approche algebrique de la limite semi-classique, nous etudions deux problemes de mecanique quantique moderne. Dans une premiere partie, nous nous interessons au comportement des electrons sur un reseau en champ magnetique. A deux dimensions et dans l'approximation des liaisons fortes, un tel systeme est decrit par le hamiltonien de harper. Les techniques algebriques permettent l'obtention d'un developpement systematique des niveaux de landau en fonction de la constante de planck effective, ici proportionnelle au champ magnetique. A l'aide d'une diagonalisation numerique exacte du hamiltonien, nous montrons la precision des developpements semi-classiques pour differents modeles de type harper. La deuxieme partie est consacree a l'etude de la localisation dynamique pour des systemes quantiques dependant du temps. Le modele de base est represente par une tige rigide tournant, sans frottements, autour d'un axe fixe. On applique, a intervalles reguliers, une force a ce rotateur. Un tel modele presente une transition vers le chaos pour certaines valeurs des parametres tandis que son analogue quantique conserve un mouvement stable. Par une analogie en termes de localisation d'anderson sur ce modele, constante de diffusion classique et longueur de localisation quantique sont liees par la formule de chirikov-izrailev-shepelyansky, faisant apparaitre la constante de planck effective du probleme, proportionnelle au rapport des frequences du rotateur quantique et de la force appliquee. Par les techniques algebriques, nous relions la longueur de localisation a la valeur moyenne dans le temps de l'energie cinetique du rotateur quantique

On se propose de montrer par une variante méromorphe du tubage que : PF(lambda = 0; som::(V)|F|**(2)lambda omega 'lambda omega ) = trace::(V) ((N) union (omega )) = tomega ',omega ou V est une variété analytique complexe compacte de dimension N + 1, F: V->C une application meromorphe telle que div(F) = PD::(O) - QD::(1) ou P,Q appartient à N*, D::(O) et D::(1) sont des hypersurfaces lisses transverses. Omega,omega ' des 1-formes sur V, holomorphe et meromorphe respectivement, telles que les poles de omega ' soient dans D::(O) et RES::(DO)omega ' = O dans H**(N)(D::(O),C). Trace::(V) : H**(2N+2)(V,C)->C est l'intégration sur V. (N=) est une classe de H**(N+1)(V,C) qui prolonge celle de omega ' sur V-D::(O); tomega ' est un courant de degré N+1 sur V D-ferme dont la classe induit celle de omega ' sur V-D::(O) construit suivant herrara-lieberman

Le calcul géométrique en modélisation et en CAO nécessite la résolution approchée, et néanmoins certifiée, de systèmes polynomiaux. Nous introduisons de nouveaux algorithmes de sous-division afin de résoudre ce problème fondamental, calculant des développements en fractions continues des coordonnées des solutions. Au delà des exemples concrets, nous fournissons des estimations de la complexité en bits et des bornes dans le modèle de RAM réelle. La difficulté principale de toute méthode de résolution consiste en les points singuliers isolés. Nous utilisons les systèmes locaux inverses et des calculs numériques certifiés afin d'obtenir un critère de certification pour traiter les solutions singulières. Ce faisant, nous sommes en mesure de vérifier l'existence et l'unicité des singularités d'une structure de multiplicité donnée. Nous traitons deux principales applications géométriques. La première: l'approximation des ensembles semi-algébriques plans, apparaît fréquemment dans la résolution de contraintes géométriques. Nous présentons un algorithme efficace pour identifier les composants connexes et pour calculer des approximations polygonales et isotopiques à l'ensemble exact. Dans un deuxième temps, nous présentons un cadre algébrique afin de calculer des diagrammes de Voronoi. Celui-ci sera applicable à tout type de diagramme dans lequel la distance à partir d'un site peut être exprimé par une fonction polynomiale à deux variables (anisotrope, diagramme de puissance etc). Si cela n'est pas possible (par exemple diagramme de Apollonius, VD des ellipses etc), nous étendons la théorie aux distances implicitement données.

Le théorème de h-cobordisme est bien connu en topologie différentielle et PL. Il a été démontré par Stephen Smale et avec comme conséquence la preuve de la conjecture de Poincaré en dimension supérieure à 4. Une généralisation pour les h-cobordismes possiblement non simplement connexe est appelée théorème de s-cobordisme. Dans cette thèse, nous démontrons les versions semi-algébrique et Nash de ces théorèmes. C'est à dire, avec des données semi-algébriques ou Nash, nous obtenons un homéomorphisme semi-algébrique (respectivement un difféomorphisme Nash). Les principaux outils intervenant sont la triangulation semi-algébrique et les approximations Nash. Un aspect de la nature algébrique des objets semi-algébriques et Nash est qu'on peut mesurer leurs complexités. Nous montrons les théorèmes de h et s-cobordisme avec borne uniforme sur la complexité de l'homéomorphisme semi-algébrique (difféomorphisme Nash) voulu, en fonction de complexité des données du cobordisme. Pour finir, nous déduisons la validité de ces théorèmes version semi-algébrique et Nash sur tout corps réel clos.

Dans la présente thèse, on établit des bornes supérieures sur les nombres de Betti des ensembles définis à l'aide de fonctions pfaffiennes, en fonction de la complexité pfaffienne (ou format) de ces ensembles. Les fonctions pfaffiennes ont été définies par Khovanskii, comme solutions au comportement quasi-polynomial de certains systèmes polynomiaux d'équations différentielles. Les ensembles semi-pfaffiens satisfont une condition de signe booléene sur des fonctions pfaffiennes, et les ensembles sous-pfaffiens sont projections de semi-pfaffiens. Wilkie a démontré que les fonctions pfaffiennes engendrent une structure o-minimale, et Gabrielov a montré que cette structure pouvait etre efficacement décrite par des ensembles pfaffiens limites. A l'aide de la théorie de Morse, de déformations, de recurrences sur le niveau combinatoire et de suites spectrales, on donne dans cette thèse des bornes effectives pourtoutes les catégories d'ensembles pré-citées.

Introduite par B. Totaro, la filtration par le poids sur l'homologie des variétés algébriques réelles, analogue réel de la filtration par le poids de P. Deligne sur les variétés algébriques complexes, a été réalisée via un complexe de chaînes filtré par C. McCrory et A. Parusinski, qui en ont enrichi la compréhension, notamment à travers l'étude de la suite spectrale induite. Au milieu des nombreuses informations recelées par cette suite spectrale de poids, on retrouve les nombres de Betti virtuels. Dans cette thèse, on montre l'existence d'une filtration par le poids équivariante sur l'homologie équivariante des variétés algébriques réelles munies d'une action d'un groupe fini. On la réalise par un complexe filtré et, via la construction de plusieurs suites spectrales, on effectue des avancées significatives pour extraire des invariants additifs. Lors de notre étude, on définit fonctoriellement un complexe de poids avec action et on montre qu'un résultat de découpage d'une variété Nash munie d'une involution algébrique entraîne un analogue de la suite exacte de Smith, tenant compte de la filtration Nash-constructible. A travers la construction d'un complexe de poids invariant dans le cadre d'involutions algébriques, on retrouve également les nombres de Betti virtuels équivariants de G. Fichou. Enfin, en appliquant les bons foncteurs aux résultats sur les produits de filtrations par le poids réelles de T. Limoges, on donne des résultats sur les produits de filtrations par le poids équivariantes.

Un problème de géométrie algébrique réelle s'exprime sous forme d’un système d’équations et d’inéquations polynomiales, dont l’ensemble des solutions est un ensemble semi-algébrique. L'objectif de cette thèse est de montrer comment les algorithmes de ce domaine peuvent être décrits formellement dans le langage du système de preuve Coq.Un premier résultat est la définition formelle et la certification de l’algorithme de transformation de Newton présentée dans la thèse d'A. Bostan. Ce travail fait intervenir non seulement des polynômes, mais également des séries formelles tronquées. Un deuxième résultat est la description d'un type de donnée représentant les ensembles semi-algébriques. Un ensemble semialgébrique est représenté par une formule logique du premier ordre basée sur des comparaisons entre expressions polynomiales multivariées. Pour ce type de données, nous montrons comment obtenir les différentes opérations ensemblistes et allons jusqu'à décrire les fonctions semi-algébriques. Pour toutes ces étapes, nous fournissons des preuves formelles vérifiées à l'aide de Coq. Enfin, nous montrons également comment la continuité des fonctions semi-algébrique peut être décrite, mais sans en fournir une preuve formelle complète
A real algebraic geometry problem is expressed as a system of polynomial equations and inequalities, and the set of solutions are semi-algebraic sets. The objective of this thesis is to show how the algorithms of this domain can be formally described in the language of the Coq proof system. A first result is the formal definition and certification of the Newton transformation algorithm presented in A. Bostan's thesis. This work involves not only polynomials, but also truncated formal series. A second result is the description of a data type representing semi-algebraic sets. A semi-algebraic set is represented by a first-order logical formula based on comparisons between multivariate polynomial expressions. For this type of data, we show how to obtain the different set operations all the way to describing semialgebraic functions. For all these steps, we provide formal proofs verified with Coq. Finally, we also show how the continuity of semi-algebraic functions can be described, but without providing a fully formalized proof

La majorité des courbes et surfaces rencontrées dans la modélisation géométrique sont définies comme l'ensemble des solutions d'un système d'équations et d'inéquations algébriques (ensemble semi-algébrique). De nombreux problèmes dans différentes disciplines scientifiques font appel à des requètes de proximité telles que la recherche du ou des voisins les plus proches ou la quantification du voisinage de deux objets.

Le diagramme de Voronoï d'un ensemble d'objets est une décomposition de l'espace en zones de proximité. La zone de proximité d'un objet est l'ensemble des points plus proches de cet objet que de tout autre objet. Les diagrammes de Voronoï permettent de répondre aux requètes de proximité après avoir identifié la zone de proximité à laquelle le point objet de la requète appartient. Le graphe dual du diagramme de Voronoï est appelé le graphe de Delaunay. Seules les approximations par des coniques peuvent garantir un ordre de continuité approprié au niveau des points de contact, ce qui est nécessaire pour garantir l'exactitude du graphe de Delaunay.

L'objectif théorique de cette thèse est la mise en évidence des propriétés algébriques et géométriques élémentaires de la courbe déplacée d'une courbe algébrique et de réduire le calcul semi-algébrique du graphe de Delaunay à des calculs de valeurs propres. L'objectif pratique de cette thèse est le calcul certifié du graphe de Delaunay pour des ensembles semi-algébriques de faible degré dans le plan euclidien.

La méthodologie associe l'analyse par intervalles et la géométrie algébrique algorithmique. L'idée centrale de cette thèse est qu'un pré-traitement symbolique unique peut accélérer l'évaluation numérique certifiée du détecteur de conflits dans le graphe de Delaunay. Le pré-traitement symbolique est le calcul de l'équation implicite de la courbe déplacée généralisée d'une conique. La réduction du problème semi-algébrique de la détection de conflits dans le graphe de Delaunay à un problème d'algèbre linéaire a été possible grâce à la considération du sommet de Voronoï généralisé (un concept introduit dans cette thèse).

Le calcul numérique certifié du graphe de Delaunay a été éffectué avec une librairie de résolution de systèmes zéro-dimensionnels d'équations et d'inéquations algébriques basée sur l'analyse d'intervalles (ALIAS). Le calcul certifié du graphe de Delaunay repose sur des théorèmes sur l'unicité de racines dans des intervalles donnés (Kantorovitch et Moore-Krawczyk). Pour les coniques, les calculs sont accélérés lorsque l'on ne considère que les équations implicites des courbes déplacées.