Opérations sur les bases de Groebner

_images/groebner.png

Opérations de base

baseGroebner([f1, f2, ..., fn, ][var1, var2, ..., vark, ]domaine, ordre)

la base de Groebner réduite engendrant l’ideal \(I = <f_1,f_2,...,f_k>\) selon l’ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Paramètres

  • [f1,f2,..,fn] – une liste de polynômes

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • domaine – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : baseGroebner([x*y-y, x-y^2], [x,y], QQ, lex)

Base     : [x - y^2, y^3 - y]
Domaine  : QQ
Ordre    : lex
Variables: (x, y) , x > y

simula : baseGroebner([x*y-y^2, x^2-z^2], [x,y,z], QQ, grevlex)

Base     : [y^3 - y*z^2, x^2 - z^2, x*y - y^2]
Domaine  : QQ
Ordre    : grevlex
Variables: (x, y, z) , x > y > z

Note

Pour avoir une base de groebner avec l’algorithme F5, il faut utiliser la fonction baseGroebnerF5. Par exemple :

simula : baseGroebnerF5([x*y-y, x-y^2], [x,y], QQ, lex)

Base     : [x - y^2, y^3 - y]
Domaine  : QQ
Ordre    : lex
Variables: (x, y) , x > y

simula : baseGroebnerF5([x*y-y^2, x^2-z^2], [x,y,z], QQ, grevlex)

Base     : [y^3 - y*z^2, x^2 - z^2, x*y - y^2]
Domaine  : QQ
Ordre    : grevlex
Variables: (x, y, z) , x > y > z
buchberger([f1, f2, ..., fn, ][var1, var2, ..., vark, ]domaine, ordre)

la base de Groebner (obtenue à partir de l’algorithme de Buchberger classique) engendrant l’ideal \(I = <f_1,f_2,...,f_k>\) selon l’ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Paramètres

  • [f1,f2,..,fn] – une liste de polynômes

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • domaine – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : buchberger([x*y-y, x-y^2], [x,y], QQ, lex)

Base     : [x*y - y, x - y^2, y^3 - y]
Domaine  : QQ
Ordre    : lex
Variables: [x, y] , x > y

simula : buchberger([x*y-y^2, x^2-z^2], [x,y,z], QQ, grevlex)

Base     : [x*y - y^2, x^2 - z^2, y^3 - y*z^2]
Domaine  : QQ
Ordre    : grevlex
Variables: [x, y, z] , x > y > z
estBaseGroebner([f1, f2, ..., fn, ][var1, var2, ..., vark, ]domaine, ordre)

renvoie “OUI” si \([f_1,f_2,...,f_k]\) est une base de Groebner engendrant l’ideal \(I = <f_1,f_2,...,f_k>\) selon l’ordre monomial (“lex”, “grevlex”, “grlex”, etc) et “NON” dans le cas contraire

Paramètres

  • [f1,f2,..,fn] – une liste de polynômes

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • domaine – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : estBaseGroebner([z+x, y-x], [z,y,x], QQ, lex)

Oui

simula : estBaseGroebner([x*y-y^2, x^2-z^2], [x,y,z], QQ, grevlex)

Non
spoly(f, g, [var1, var2, ..., vark, ]domaine, ordre)

le S-polynôme de f et g

Paramètres

  • f – un polynôme

  • g – un polynôme

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • domaine – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : spoly(x^3*y^2-x^2*y^3+x, 3x^4*y+y^2, [x,y], QQ, lex)

-x^3*y^3 + x^2 - y^3/3
coefDominant(f, [var1, var2, ..., vark, ]domaine, ordre)

le coefficient dominant de f selon l’ordre monomial (“lex”, “grevlex”, “grlex”, etc).

Paramètres

  • f – un polynôme

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • domaine – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : coefDominant(4x+y^2+y*z, [x,y,z], QQ, lex)

4

simula : coefDominant(3x*y-y^2-2x*y^5, [x,y,z], QQ, grevlex)

-2
monomeDominant(f, [var1, var2, ..., vark, ]domaine, ordre)

le monôme dominant de f selon l’ordre monomial (“lex”, “grevlex”, “grlex”, etc).

Paramètres

  • f – un polynôme

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • domaine – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : monomeDominant(4x+y^2+y*z, [x,y,z], QQ, lex)

x

simula : monomeDominant(3x*y-y^2-2x*y^5, [x,y,z], QQ, grevlex)

x*y^5
termeDominant(f, [var1, var2, ..., vark, ]domaine, ordre)

le terme dominant de f selon l’ordre monomial (“lex”, “grevlex”, “grlex”, etc).

Paramètres

  • f – un polynôme

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • domaine – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : termeDominant(4x+y^2+y*z, [x,y,z], QQ, lex)

4*x

simula : termeDominant(3x*y-y^2-2x*y^5, [x,y,z], QQ, grevlex)

-2*x*y^5
NF(f, G, [var1, var2, ..., vark, ]domaine, ordre)

la forme normale de f par rapport à G selon l’ordre monomial (“lex”, “grevlex”, “grlex”, etc).

Paramètres

  • f – un polynôme

  • G – une famille de polynôme

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • domaine – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : NF(x^3*y^2-x^2*y^3+x, [x^2-y,x*y-1], [x,y], QQ, lex)

x - y^4 + y^2

simula : NF(3x*y-y^2-2x*y^5, [x*y-y, y^2-1], [x,y,z], QQ, grevlex)

1 - y
weakNF(f, G, [var1, var2, ..., vark, ]domaine, ordre)

la forme normale faible de f par rapport à G selon l’ordre monomial (“lex”, “grevlex”, “grlex”, etc).

Paramètres

  • f – un polynôme

  • G – une famille de polynôme

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • domaine – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : weakNF(x^3*y^2-x^2*y^3+x, [x^2-y,x*y-1], [x,y], QQ, lex)

x - y^4 + y^2

simula : weakNF(3x*y-y^2-2x*y^5, [x*y-y, y^2-1], [x,y,z], QQ, grevlex)

1 - y

Applications des bases de Groebner

ideal(G, [var1, var2, ..., vark, ]K, ordre)

l’ideal de \(K[var_1,...,var_k]\) engendré par la famille des polynômes G.

Paramètres

  • G – une famille de polynôme

  • [var1,var2,..,vark] – la liste des variables avec var1>var2>…>vark

  • K – en ensemble (QQ pour \(\mathbb{Q}\), RR pour \(\mathbb{R}\), CC pour \(\mathbb{C}\))

  • ordre – un ordre monomial (“lex”, “grevlex”, “grlex”, etc)

Exemple :

simula : I = ideal([x^2*y-z, x*y-1], [x,y,z], QQ, grevlex)

I = idéal de QQ[x, y, z] engendré par [x^2*y - z, x*y - 1]

Note

Vous pouvez déterminer la base de Groebner engendrant un idéal I comme suit:

simula : I = ideal([x^2*y-z, x*y-1], [x,y,z], QQ, grevlex)
simula : baseGroebner(I)

Base     : [y*z - 1, x - z]
Domaine  : QQ
Ordre    : grevlex
Variables: (x, y, z) , x > y > z

simula : baseGroebnerF5(I)

Base     : [y*z - 1, x - z]
Domaine  : QQ
Ordre    : grevlex
Variables: (x, y, z) , x > y > z
idealMonomial(I)

l’ideal engendré par la famille des monômes de I.

Paramètres

I – un idéal

Exemple :

simula : I = ideal([x^2*y-y, x*y-1], [x,y], QQ, grevlex)

I = idéal de QQ[x, y] engendré par [x^2*y - y, x*y - 1]

simula : Im = idealMonomial(I)

Im = idéal de QQ[x, y] engendré par [y^2, x]

Appartenance à un idéal

estDansIdeal(f, I)

renvoie “OUI” si f appartient à l’ideal I et “NON” dans le cas contraire.

Paramètres

  • I – un idéal

  • f – un polynôme

Exemple :

simula : I = ideal([x^2*y-z, x*y-1], [x,y,z], QQ, grevlex)

I = idéal de QQ[x, y, z] engendré par [x^2*y - z, x*y - 1]

simula : estDansIdeal(x*y-z, I)

Non

simula : estDansIdeal(x-z, I)

Oui

Appartenance au radical d’un idéal

estDansRadIdeal(f, I)

renvoie “OUI” si f appartient radical de l’ideal I (\(\sqrt{I}\)) et “NON” dans le cas contraire.

Paramètres

  • f – un polynôme

  • I – un idéal

Exemple :

simula : I = ideal([x^2*y-z, x*y-1], [x,y,z], QQ, grevlex)

I = idéal de QQ[x, y, z] engendré par [x^2*y - z, x*y - 1]

simula : estDansRadIdeal(x*y-z, I)

Non

Egalité de deux idéaux

ideauxEgaux(I1, I2)

renvoie “OUI” si l’idéal I1 est égal à l’ideal I2 et “NON” dans le cas contraire.

Paramètres

  • I1 – un idéal

  • I2 – un idéal

Exemple :

simula : I = ideal([x^2*y-z, x*y-1], [x,y,z], QQ, grevlex)

I = idéal de QQ[x, y, z] engendré par [x^2*y - z, x*y - 1]

simula : J = ideal([x^2*y-z, x*y-1, x-z], [x,y,z], QQ, grevlex)

J = idéal de QQ[x, y, z] engendré par [x^2*y - z, x*y - 1, x + z]

simula : ideauxEgaux(I, J)

Oui