Exercice 5.2

On peut construire en Sage l'ordre de l'exercice (pour des variables $x_1,x_2,y_1,y_2,y_3$) avec le constructeur TermOrder

In [1]:
o = TermOrder('lex', 2) + TermOrder('degrevlex', 3)
o
Out[1]:
Block term order with blocks:
(Lexicographic term order of length 2,
 Degree reverse lexicographic term order of length 3)
In [2]:
A.<x1,x2,y1,y2,y3> = PolynomialRing(QQ, order=o)
A
Out[2]:
Multivariate Polynomial Ring in x1, x2, y1, y2, y3 over Rational Field
In [3]:
x1*y1*y2 < x1*y1^2
Out[3]:
True

Exercice 5.3

In [4]:
A.<x,y,z> = PolynomialRing(QQ, order='lex')
I = A.ideal([x^2-2*x*z+5, x*y^2+y*z^3, 3*y^2-8*z^3])
In [5]:
I.groebner_basis()
Out[5]:
[x^2 - 2*x*z + 5, x*z^3 + 9/640*z^8 - 3/20*z^7 + 3/16*z^5, y^2 - 8/3*z^3, y*z^3 - 3/80*z^8 + 2/5*z^7 - 1/2*z^5, z^9 - 32/3*z^8 + 80/3*z^6 + 1600/9*z^3]
In [6]:
J = I.change_ring(A.change_ring(order='degrevlex'))
J.groebner_basis()
Out[6]:
[y^4 + 16/3*y^3*z + 320/9*y^2, x*y^2 + 3/8*y^3, z^3 - 3/8*y^2, x^2 - 2*x*z + 5]

Exercice 7.1

In [7]:
A.<x,y> = PolynomialRing(QQ, order='lex')
I = A.ideal(x^2*y^2 - x, x*y^3 + y)
G = I.groebner_basis()
G
Out[7]:
[x, y]
In [8]:
x in I, y in I
Out[8]:
(True, True)
In [9]:
I.reduce(x)
Out[9]:
0
In [10]:
a, b = x.lift(I)
a, b
Out[10]:
(-1/2*x*y^2 - 1, 1/2*x^2*y)
In [11]:
a*I.0 + b*I.1
Out[11]:
x
In [12]:
P = x^3*y^2 + 2*x*y^4
P.mod(I)
Out[12]:
0

Exercice 7.2

In [13]:
A.<x,y,z> = QQ[]
I = A.ideal(x*y*z + z^3, y^2)
I.groebner_basis()
Out[13]:
[z^5, y*z^3, x*y*z + z^3, y^2]

Exercice 7.4

In [14]:
I = A.ideal(x + y + z, x*y + y*z + z*x, x*y*z + 1)
I.reduce(x^3 + 1)
Out[14]:
0

En regardant la base de Gröbner, et par symétrie de l'ensemble générateur, on aurait pu conclure directement que $x^3+1∈I$

In [15]:
I.groebner_basis()
Out[15]:
[z^3 + 1, y^2 + y*z + z^2, x + y + z]

Exercice 7.6

In [16]:
A.<x,y,z,t> = PolynomialRing(QQ, order='lex')
I = A.ideal(z^5-y^3*t^2, x^2*t - y*z^2, x^2*z^3 - y^4*t, x^4*z - y^5)
In [17]:
G = I.groebner_basis()
G
Out[17]:
[x^4*z - y^5, x^2*z^3 - y^4*t, x^2*t - y*z^2, y^3*t^2 - z^5]

On vérifie que la base de Gröbner calculée par Sage coïncide (à des constantes près) avec les générateurs

In [18]:
sorted(I.gens()), sorted(G)
Out[18]:
([-y^3*t^2 + z^5, x^2*t - y*z^2, x^2*z^3 - y^4*t, x^4*z - y^5],
 [y^3*t^2 - z^5, x^2*t - y*z^2, x^2*z^3 - y^4*t, x^4*z - y^5])

...o, plus simplement:

In [19]:
I.basis_is_groebner()
Out[19]:
True

Une petite fonction pour changer l'ordre de $I$ et renvoyer les termes de tête de sa base de Gröbner

In [20]:
# `ord` et `names` prennent des valeurs par défaut,
# s'ils ne sont pas donnés explicitement
def LT(I, ord='lex', names='x,y,z,t'):
    A = I.ring()
    J = I.change_ring(A.change_ring(names=names, order=ord))
    G = J.groebner_basis()
    return [g.lt() for g in G]

sans parametres ord et names, les valeurs par défaut sont prises

In [21]:
LT(I)
Out[21]:
[x^4*z, x^2*z^3, x^2*t, y^3*t^2]
In [22]:
LT(I, 'degrevlex')
Out[22]:
[y^5, x^2*z^3, z^5, y*z^2]

syntaxe équivalente à la précédente

In [23]:
LT(I, ord='degrevlex')
Out[23]:
[y^5, x^2*z^3, z^5, y*z^2]
In [24]:
LT(I, 'invlex')
Out[24]:
[y^3*t^2, y^4*t, x^2*t, x^4*z]
In [25]:
LT(I, 'deglex')
Out[25]:
[x^4*z, x^2*z^3, y^3*t^2, x^2*t]

En utilisant TermOrder, on peut construire d'autres ordres, par exemple l'ordre degrevlex gradué:

In [26]:
sage.rings.polynomial.term_order?
In [27]:
LT(I, TermOrder('wdegrevlex', (2,2,1,1)))
Out[27]:
[y^5, y^4*t, y^3*t^2, x^2*t]

Et, finalement, la solution, avec un autre ordre lexicographique

In [28]:
LT(I, names='y,z,t,x')
Out[28]:
[y^5, y^4*t, y^3*t^2, y^2*t^3*x^2, y*z^2, y*t^4*x^4, z^11]

Le même ordre, exprimé de façon matricielle

In [29]:
p = SymmetricGroup(4)([2,3,4,1])
p
Out[29]:
(1,2,3,4)
In [30]:
p.matrix()
Out[30]:
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 0 0 0]
In [31]:
lt = LT(I, ord=TermOrder(p.matrix()))
lt
Out[31]:
[y^5, y^4*t, y^3*t^2, x^2*y^2*t^3, y*z^2, x^4*y*t^4, z^11]

On peut s'arrêter là, mais si vraiement on a envie de tester tous les ordres lexicographiques possibles, on peut s'appuyer sur les capacités

  • de Sage en combinatoire, pour énumérer toutes les permutations de $x,y,z,t$ ;
  • de Python en manipulation de chaînes de caractères, pour former les paramètres à passer aux fonctions.
In [32]:
S = Permutations(['x','y','z','t'])
S
Out[32]:
Permutations of the set ['x', 'y', 'z', 't']
In [33]:
for s in S:
    print(s, LT(I, names=','.join(s)))
(['x', 'y', 'z', 't'], [x^4*z, x^2*z^3, x^2*t, y^3*t^2])
(['x', 'y', 't', 'z'], [x^4*z, x^2*t, x^2*z^3, y^3*t^2])
(['x', 'z', 'y', 't'], [x^4*z, x^2*z^3, x^2*t, z^5])
(['x', 'z', 't', 'y'], [x^4*z, x^2*z^3, x^2*t, z^5])
(['x', 't', 'y', 'z'], [x^4*z, x^2*t, x^2*z^3, t^2*y^3])
(['x', 't', 'z', 'y'], [x^4*z, x^2*t, x^2*z^3, t^2*y^3])
(['y', 'x', 'z', 't'], [y^5, y^4*t, y^3*t^2, y^2*x^2*t^3, y*x^4*t^4, y*z^2, x^6*t^5])
(['y', 'x', 't', 'z'], [y^5, y^4*t, y^3*t^2, y^2*x^2*t^3, y*x^4*t^4, y*z^2, x^6*t^5])
(['y', 'z', 'x', 't'], [y^5, y^4*t, y^3*t^2, y^2*x^2*t^3, y*z^2, y*x^4*t^4, z^11])
(['y', 'z', 't', 'x'], [y^5, y^4*t, y^3*t^2, y^2*t^3*x^2, y*z^2, y*t^4*x^4, z^11])
(['y', 't', 'x', 'z'], [y^5, y^4*t, y^3*t^2, y^2*t^3*x^2, y*t^4*x^4, y*z^2, t^5*x^6])
(['y', 't', 'z', 'x'], [y^5, y^4*t, y^3*t^2, y^2*t^3*x^2, y*t^4*x^4, y*z^2, t^5*x^6])
(['z', 'x', 'y', 't'], [z^5, z^3*x^2, z^2*y, z*x^4, z*y^6, x^10*t])
(['z', 'x', 't', 'y'], [z^5, z^3*x^2, z^2*y, z*x^4, z*y^6, x^10*t])
(['z', 'y', 'x', 't'], [z^5, z^3*x^2, z^2*y, z*y^6, z*x^4, y^11])
(['z', 'y', 't', 'x'], [z^5, z^3*x^2, z^2*y, z*y^6, z*x^4, y^11])
(['z', 't', 'x', 'y'], [z^5, z^3*x^2, z^2*y, z*x^4, z*y^6, t*x^10])
(['z', 't', 'y', 'x'], [z^5, z^3*x^2, z^2*y, z*y^6, z*x^4, t*x^10])
(['t', 'x', 'y', 'z'], [t^2*y^3, t*x^2, t*y^4, x^4*z])
(['t', 'x', 'z', 'y'], [t^2*y^3, t*x^2, t*y^4, x^4*z])
(['t', 'y', 'x', 'z'], [t^2*y^3, t*y^4, t*x^2, y^5])
(['t', 'y', 'z', 'x'], [t^2*y^3, t*y^4, t*x^2, y^5])
(['t', 'z', 'x', 'y'], [t^2*y^3, t*x^2, t*y^4, z*x^4])
(['t', 'z', 'y', 'x'], [t^2*y^3, t*y^4, t*x^2, z*x^4])

Exercice 7.7

In [34]:
A.<x,y> = QQ[]
I = A.ideal(x - y^2, x*y - x)
I.groebner_basis()
Out[34]:
[x^2 - x, x*y - x, y^2 - x]
In [35]:
I.change_ring(A.change_ring(order='lex')).groebner_basis()
Out[35]:
[x - y^2, y^3 - y^2]
In [36]:
I.change_ring(A.change_ring(order='invlex')).groebner_basis()
Out[36]:
[y^2 - x, x*y - x, x^2 - x]

L'ensemble $G = \{x^2 - x,\; xy - x,\; y^2 - x,\; y^3 - y^2\}$ forme une base de Gröbner de l'idéal pour tous les ordres ci-dessus.

Selon l'ordre monomial choisi l'escalier de cette base (ensemble des monômes pas contenus dans $〈\mathrm{LT}(G)〉$) contient les monômes

$$\begin{cases} \{1, x, y\} &\text{si $x < y^2$,}\\ \{1, y, y^2\} &\text{sinon.} \end{cases}$$

Dans tous les cas, ceci coincide avec la dimension de l'algèbre quotient $ℚ[x,y]/I$, qui est $3$ (l'idéal est de dimension $0$).

In [37]:
I.dimension(), I.vector_space_dimension()
Out[37]:
(0, 3)

Puisque $G⊂I$, ceux-ci sont aussi les deux seuls escaliers possibles pour $\mathrm{LT}(I)$. Par conséquent, les monomes de tête de $G$ engendrent $\mathrm{LT}(I)$ pour n'importe quel ordre monomial.