- Polynômes à une variable
- Polynômes à plusieurs variables
- Préliminaires sur les ordres admissibles
- Représentation matricielle des ordres admissibles.
- Idéaux monomiaux
- Programmation Python/Sage
- Calcul de bases de Gröbner
- Critère de Buchberger
- Algorithme de Buchberger, Bases de Gröbner réduite
- Résultants et élimination
- Variétés affines
- Théorème d’élimination
- Rappel sur les idéaux
- Dimension d’un idéal
Polynômes à une variable
Fonctions utiles : degree
, leading_coefficient
, coefficients
,
expand
, factor
, gcd
, quo
, rem
.
– Soient les polynômes et .
- Déterminer le degré, le coefficient dominant et la liste des termes de .
- Effectuer la division euclidienne de par .
- Calculer .
- Factoriser . Calculer .
– Soit le polynôme .
- Factoriser dans .
- Factoriser dans et dans .
- Factoriser dans .
- Factoriser dans .
– Soit le polynôme .
- Factoriser dans et .
- En déduire une preuve de l’irréductibilité de dans .
- Vérifier l’irréductibilité de avec Sage.
– Soit un nombre premier. Factoriser en facteurs irréductibles dans pour . Formuler une conjecture sur le type de factorisation de ces polynômes, et la prouver. Suggestion: observer que deux racines du polynôme diffèrent nécessairement d’un élément de ; conclure en étudiant l’action du Frobenius sur les racines. Note: il est possible de se passer de la théorie de Galois, si on le souhaite.
– Soit un nombre premier. Factoriser le polynôme en facteurs irréductibles dans . Prouver que ces polynômes sont des produits de polynômes cyclotomiques.
Polynômes à plusieurs variables
À partir de maintenant, il est préférable de se servir des anneaux de polynômes de Sage, plutôt que des variables symboliques.
– Soit le polynôme .
- Donner le degré total de .
- Écrire comme polynôme en .
– Transformer le polynôme avec Sage sous les formes suivantes:
- ;
- ;
- ;
- .
Préliminaires sur les ordres admissibles
–
-
Soit le polynôme .
- Ordonner pour l’ordre lexicographique.
- Ordonner pour l’ordre lexicographique gradué.
- Ordonner pour l’ordre lexicographique inverse gradué.
- Montrer qu’en deux variables, l’ordre lexicographique gradué et l’ordre lexicographique inverse gradué coïncident.
-
Soit le polynôme .
- Ordonner à la main pour l’ordre lexicographique gradué.
- Ordonner à la main pour l’ordre lexicographique inverse gradué.
– Soit un ordre total compatible avec la multiplication. Montrer que est un ordre admissible si, et seulement si, pour tout monôme non constant, .
–
Montrer que l’ordre lexicographique est un ordre admissible. (voir aussi la proposition 4, p.55 du Cox, Little & O’Shea)
–
-
Soient , et dans muni de l’ordre lexicographique.
- À quoi correspond la commande
p.reduce([g, h])
? - À quoi correspond la commande
p.reduce([h, g])
? - Montrer que est dans l’idéal .
- À quoi correspond la commande
-
Soient et .
- À quoi correspond la commande
g.reduce([g, h])
? - À quoi correspond la commande
h.reduce([g, h])
? - Pleurer.
- À quoi correspond la commande
–
Déterminer quel ordre monomial (lex
, deglex
, degrevlex
) a été
utilisé pour ordonner les termes des polynômes suivants :
- .
- .
- .
–
Soient et l’ensemble ordonné .
- Calculer pour les ordres lexicographique et lexicographique gradué.
- Effectuer les mêmes calculs en inversant l’ordre de .
–
-
Montrer que tout polynôme peut s’écrire sous la forme
avec et .
-
Trouver une écriture explicite de la forme .
Représentation matricielle des ordres admissibles.
–
On étend l’ordre lexicographique à de la façon évidente. On définit une relation sur les monômes à variables à partir d’une matrice carrée réelle de taille comme suit :
- Montrer que si et alors n’est pas un ordre admissible.
-
Quelles conditions (nécessaires et suffisantes) doit vérifier pour que l’ordre associé soit un ordre admissible ?
-
Pour , trouver
telle que soit un ordre admissible.
-
Quelles conditions (nécessaires et suffisantes) doit vérifier pour que l’ordre associé soit un ordre admissible ?
- Donner successivement un exemple de matrice tel que
l’ordre associé soit l’ordre
lex
,deglex
,degrevlex
, un ordre produit (avec à chaque fois ).
Idéaux monomiaux
Fonction utiles : lc
, lm
, lt
.
– Soit un idéal monomial et l’ensemble des exposants qui apparaissent dans . On considère un ordre monomial. Montrer que le plus petit élément de appartient à .
–
Dans l’anneau , on considère l’ordre défini par l’ordre lexicographique sur les et par l’ordre degrevlex sur les :
Montrer que est un ordre monomial.
– Soit l’idéal de .
- Donner une base de Gröbner de pour l’ordre lexicographique.
- Même question pour l’ordre degrevlex.
Programmation Python/Sage
– Que fait la procédure suivante ? Quels sont les arguments de la procédure ? Comment les variables sont elles initialisées ? Quelle est la condition d’arrêt de la boucle ? Que doit renvoyer la procédure ?
def euclidepol (A,B):
A0 = A; A1 = B
S0 = 1; S1 = 0
T0 = 0; T1 = 1
while A1 != 0:
Q = A0//A1
U = A1; A1 = A0 - Q*A1; A0 = U
U = S1; S1 = S0 - Q*S1; S0 = U
U = T1; T1 = T0 - Q*T1; T0 = U
return (A0,S0,T0)
– Écrire une fonction qui prend en entrée un corps
et un entier et donne en sortie un polynôme aléatoire
irréductible de de degré . Consignes : Ne vous
servez pas de la méthode .irreducible_element()
. Écrivez une boucle
qui tire des polynômes au hasard jusqu’à en trouver un
irréductible. Vous pouvez utiliser la méthode .random_element()
des
anneaux de polynômes pour tirer des polynômes au hasard.
– Même question qu’à l’exercice précédent, mais cette fois-ci est un corps premier, et vous donnerez en sortie le plus petit polynôme irréductible par l’ordre lexicographique (sur les coefficients).
– Nous allons adopter une représentation distribuée creuse pour les polynômes : un monôme sera représenté par une liste à deux éléments. Le premier est le coefficient et le second la liste des exposants.
- Écrire une fonction qui teste si un monôme est plus petit qu’un monôme pour l’ordre lexicographique.
- Écrire une fonction qui, étant donnée une liste de monômes, renvoie son plus petit élément .
- Écrire une fonction qui, étant donnée une liste de monômes, énumère les monômes dans l’ordre croissant pour l’ordre lexicographique.
- Écrire une fonction qui affiche un monome de la manière
habituelle (par ex.
5 x^10 y^20
). Vous êtes libres de choisir la façon dont les noms des variables sont assignés (pour référence,chr(97)
équivaut au caractère'a'
). - (avancé) Transformer ces fonctions en une classe
Monome
, munie de deux champs, et au minimum des méthodes spéciales__lt__
,__repr__
et__mul__
.
Calcul de bases de Gröbner
–
Soit l’idéal de défini par
- Donner une base de Gröbner de pour l’ordre lexicographique.
- Vérifier que les éléments obtenus appartiennent effectivement à .
- Soit . Calculer .
– Dans , on choisit l’ordre degrevlex. Calculer une base de Gröbner de l’idéal .
– Soit une base de Gröbner pour l’idéal et supposons qu’il existe tels que divise . Montrer que est encore une base de Gröbner pour .
– Le polynôme est-il dans l’idéal engendré par , et ?
– Soit un idéal principal. Montrer que tout sous-ensemble fini contenant un générateur de est une base de Gröbner pour .
–
Soit l’ideal
de .
- Montrer que le système générateur de est une base de Gröbner pour l’ordre lexicographique avec .
- Trouver un ordre sur les variables tel que soit .
– On se place dans un anneau où est un corps commutatif. Soit un idéal de non nul. Une base de Gröbner universelle est un ensemble qui est une base de Gröbner de pour tous les ordres admissibles de . Calculer une base de Gröbner universelle de l’idéal de engendré par et .
–
Soit l’anneau des polynômes à indéterminées , à coefficients dans . Soit l’idéal de engendré par les polynômes .
- Pour , montrer que les forment une base de Gröbner universelle de .
- Pour , montrer que les forment une base de Gröbner universelle de .
–
Soit un sous-espace vectoriel de de dimension . Soit son idéal annulateur dans : l’idéal est engendré par formes linéaires indépendantes
On dit qu’une forme linéaire non nulle de est un circuit si son ensemble de variables est minimal pour l’inclusion. On dit qu’un -sous-ensemble est une base, si le déterminant de la matrice associée est non nul.
-
Montrer que les circuits sont précisément les formes linéaires non nulles
où .
- En déduire qu’il y a au plus circuits.
- Soit un idéal engendré par des formes linéaires. Montrer que l’ensemble des circuits dans est une base de Gröbner universelle de .
Critère de Buchberger
– Soient les polynômes et de avec l’ordre lexicographique.
- Calculer .
- Soit . La base est-elle de Gröbner ?
– Déterminer si les ensembles suivants sont des bases de Gröbner des idéaux qu’ils engendrent.
- pour l’ordre lexicographique gradué.
- pour l’ordre lexicographique avec puis .
- avec l’ordre lexicographique.
– La fonction dépend-elle du choix de l’ordre monomial ?
– Soit un idéal et une base de Gröbner de .
- Montrer que si, et seulement si, .
- En déduire que .
- En déduire que .
Algorithme de Buchberger, Bases de Gröbner réduite
– Déterminer une base de Gröbner des idéaux suivants :
- de pour l’ordre lexicographique.
- de pour l’ordre lexicographique inverse gradué.
- de pour les ordres lexicographique et lexicographique gradué.
- de pour les ordres lexicographique et lexicographique inverse gradué.
– Montrer que pour tout , la base de Gröbner réduite de
pour l’ordre lexicographique inverse gradué contient . En déduire la base de Gröbner réduite de .
–
Soient .
- Soient un entier et un idéal monomial de . Donner des générateurs de l’idéal . Dans la suite on fixe sur l’ordre lexicographique, on désigne par un idéal homogène non nul et par l’intersection .
- Montrer que .
- Soit une base de Gröbner de formée de polynômes homogènes. Déduire des questions précédentes des générateurs de . En déduire une base de Gröbner de .
- Soit une base de Gröbner réduite de formée de polynômes homogènes. Donner une condition nécessaire et suffisante pour que l’on ait .
– Soient et deux polynômes non nuls sans facteur commun et l’idéal qu’ils engendrent. On suppose que est une base de Gröbner de .
- On pose : , , où est un monôme, et sont deux monômes premiers entre eux et et deux scalaires. En utilisant la division du -polynôme par la suite , montrer qu’il existe un polynôme dont n’est pas divisible par et tel que divise .
- En déduire que .
- En déduire que est une base de Gröbner de si, et seulement si, et sont premiers entre eux.
- On pose , , où et n’ont pas de facteur commun. Montrer que est une base lde Gröbner de si, et seulement si, est une base de Gröbner de l’idéal engendré par et .
- Donner une condition nécessaire et suffisante pour que soit une base de Gröbner de .
Résultants et élimination
– Soit l’idéal .
- Montrer que .
- Montrer que .
–
- Calculer une base de Gröbner réduite de l’idéal engendré par pour l’ordre lexicographique induit par .
- En déduire que est un nombre algébrique sur le corps des rationnels , en exhibant un polynôme à une variable à coefficients rationnels dont il est racine.
- Quel est le résultant de et par rapport à ?
- En déduire que . Exprimer et en fonction de .
– Soient et deux polynômes de , où est un corps.
- Fabriquer un polynôme dont les racines sont les sommes d’une racine de et d’une racine de . (Quels sont les Y tels que le système ait une solution ?)
- Fabriquer un polynôme à coefficients entiers qui a pour racine.
–
Le degré (resp. le poids) du monôme non nul est (resp. ). Le degré (resp. le poids) d’un polynôme est le maximum des degrés (resp. des poids) de ses monômes non nuls. Un polynôme est dit symétrique si pour toute permutation Pour , on note le -ième polynôme symétrique élémentaire.
- Si est symétrique, montrer que le degré par rapport à n’importe quel variable est le même. Ce degré est appelé degré partiel de .
- Montrer que pour tout polynôme symétrique de degré , il existe un unique polynôme tel que où est de poids et de degré le degré partiel de .
– Déterminer à l’aide d’un résultant l’intersection des courbes de définies par
–
On considère la courbe plane d’équation rationnelle
-
Comment trouver une équation implicite de la courbe ?
-
On considère la paramétrisation rationnelle
Vérifier que les points sont sur la surface .
-
Soit l’idéal . Calculer .
-
Impliciter l’exemple , .
– Donner l’aire d’un triangle en fonction des longueurs de ses trois côtés.
– Soit un corps infini, un polynôme non nul de degré .
- Montrer qu’il existe dans tel que le polynôme soit de la forme , où est un élément non nul de et un polynôme de degré par rapport à .
- En utilisant un résultant en déduire le théorème des zéros de Hilbert.
Variétés affines
– En utilisant Sage, donner les solutions des équations suivantes :
- .
- .
- .
– En utilisant Sage, donner les solutions des systèmes d’équations suivants :
- .
- .
- où est un paramètre réel.
– Résoudre l’équation suivante dans :
– On considère la surface paramétrée par
et la courbe tracée sur et paramétrée par
- Obtenir une équation implicite de .
- Obtenir des équations implicites de .
- Vérifier à l’aide de ces équations que .
– Soient les idéaux de :
Montrer que .
– Soient les idéaux de :
- Montrer que .
- A-t-on ?
- A-t-on ?
– Soient satisfaisant le système :
- Montrer que
- Montrer que .
- Que valent et ?
– (Sagebook, exercice 36) Soit un idéal de dimension zéro de . Soit le polynôme caractéristique de l’application linéaire
Calculer dans le cas . Montrer que toute racine de est l’abscisse d’un point de la variété .
Théorème d’élimination
– Soit un idéal.
- Montrer que est un idéal de .
- Montrer que l’idéal est le premier idéal d’élimination de .
- En déduire comment appliquer le théorème d’élimination pour éliminer plusieurs variables.
– Soient le système d’équations
et l’idéal engendré par ces équations.
- Déterminer des bases de , et de .
- En déduire l’ensemble des solutions de ce système.
– Soit l’idéal déterminé par les équations
- Calculer les idéaux et .
- Combien le système associé admet-il de solutions ?
- Combien le système associé admet-il de solutions ?
–
Utiliser le théorème d’élimination pour résoudre le système suivant dans puis dans :
–
Soit . On cherche à calculer les valeurs critiques de vu comme fonction polynomiale de dans .
- Soit l’ideal . Quelle est la dimension de ? Peut-on calculer simplement les points critiques de ?
- En considérant l’idéal , trouver un polynôme de dont l’ensemble des racines contient les valeurs critiques de .
–
Soient et deux idéaux de . Soit . Montrer que est l’idéal d’élimination .
–
Calculer, dans , l’intersection des idéaux
–
Écrire un algorithme qui détermine l’intersection de deux idéaux.
Rappel sur les idéaux
–
Soit un idéal non trivial de et soit . L’ensemble des variables est dit indépendant modulo si . La dimension de est définie par
- Montrer qu’un idéal propre est de dimension zéro si, et seulement si, il contient un polynôme non constant en chaque variable .
Soit un idéal propre de .
- Si est de dimension zéro, montrer que pour tout ordre admissible sur et pour toute base de Gröbner de , pour tout , il existe avec pour un .
- Supposons qu’il existe un ordre sur et une base de Gröbner de telle que pour tout , il existe avec pour un . Montrer que est un -espace vectoriel de dimension finie.
- Si est un -espace vectoriel de dimension finie, montrer que est de dimension zéro.
- En déduire que est de dimension zéro si, et seulement si, est un -espace vectoriel de dimension finie.
–
Soit l’idéal de engendré par et . Montrer que est un idéal de dimension zéro.
–
Quelle est la dimension de l’idéal de engendré par ?
–
Écrire un algorithme qui teste si un idéal est de dimension .
–
À un -uplet on associe une application
On dit que est inversible s’il existe tels que , c.-à-d. si
Soit muni de l’ordre lexicographique.
-
On suppose que la base de Gröbner réduite de est de la forme
Montrer que est inversible.
-
On suppose dans cette question que est inversible d’inverse .
- Montrer que l’ensemble est un sous-ensemble réduit de .
- Montrer que .
- En déduire que est une base de Gröbner réduite de .
- Montrer que , .
-
Soit tels que , .
- Montrer que , .
- En déduire que implique .
Dimension d’un idéal
–
Soit un idéal monomial tel que .
- Montrer que les monômes de n’importe quel ensemble de générateurs de ont un facteur commun non constant.
-
On écrit , où les sont des sous-espaces de coordonnées tels que pour . On suppose de plus qu’un seul des est de dimension .
- Quelle est la valeur maximale que peut prendre ?
- Donner un exemple où ce maximum est atteint.
–
Soit un idéal monomial de .
- Si est de dimension , que peut être ?
- Montrer que est de dimension si et seulement si pour tout , il existe tel que .
–
Soit l’idéal de :
Calculer la fonction de Hilbert de plusieurs façons différentes avec et sans Sage.
–
Soit l’idéal de :
Calculer la fonction de Hilbert .
–
Soit l’idéal de :
Calculer la fonction de Hilbert .
–
Soient des idéaux de .
- Montrer que .
- Montrer que pour tout ,
- Montrer que
–
Soit un corps algébriquement clos. Calculer la dimension des variétés affines définies par les idéaux suivants :
- .
- .
–
On se donne des entiers strictement positifs et on considère l’idéal monomial . On se propose de calculer la fonction de Hilbert . On prolonge la fonction de Hilbert à par la valeur zéro sur les entiers négatifs.
- Montrer qu’il existe un entier tel qu’on ait et pour tout . Calculer et .
- Montrer que pour tout on a .
- Calculer quand pour tout .
- Calculer quand , .
–
Montrer qu’un point est une variété affine de dimension zéro.
–
Soit un corps algébriquement clos et .
- Montrer que mais que et ne sont pas nuls.
- Montrer que mais que .
- Quelle est la dimension de ?