TD 2

Exo 1.3

In [1]:
A.<x> = ZZ[]
In [2]:
P = x^7 + x^5 + 2*x^3 + 2*x^2 + 3*x + 2
P
Out[2]:
x^7 + x^5 + 2*x^3 + 2*x^2 + 3*x + 2
In [3]:
P.change_ring(GF(2)).factor()
Out[3]:
x * (x^3 + x^2 + 1)^2
In [4]:
P.change_ring(GF(7)).factor()
Out[4]:
(x + 4) * (x^6 + 3*x^5 + 3*x^4 + 2*x^3 + x^2 + 5*x + 4)

On voit que soit $P$ est irreductible, soit il a une racine congrue à $-4 \bmod 14$. On vérifie aisément que $P(x) > 0$ si $x>0$. On vérifie aussi que $P(-4)$ n'est pas racine:

In [5]:
P(-4)
Out[5]:
-17514

Reste à vérifier que $P(-4 - c·14) ≠ 0$ pour tout $c>1$. Exercice.

In [12]:
P.is_irreducible()
Out[12]:
True

Exo 1.4

In [13]:
p = 2
k = GF(p)
A.<X> = k[]
for a in k:
    print((x^p - x + a).factor())
x * (x + 1)
x^2 + x + 1
In [14]:
p = 3
k = GF(p)
A.<X> = k[]
for a in k:
    print((x^p - x + a).factor())
x * (x + 1) * (x + 2)
x^3 + 2*x + 1
x^3 + 2*x + 2
In [15]:
p = 5
k = GF(p)
A.<X> = k[]
for a in k:
    print((x^p - x + a).factor())
x * (x + 1) * (x + 2) * (x + 3) * (x + 4)
x^5 + 4*x + 1
x^5 + 4*x + 2
x^5 + 4*x + 3
x^5 + 4*x + 4
In [16]:
p = 7
k = GF(p)
A.<X> = k[]
for a in k:
    print((x^p - x + a).factor())
x * (x + 1) * (x + 2) * (x + 3) * (x + 4) * (x + 5) * (x + 6)
x^7 + 6*x + 1
x^7 + 6*x + 2
x^7 + 6*x + 3
x^7 + 6*x + 4
x^7 + 6*x + 5
x^7 + 6*x + 6

On conjecture que $x^p - x + c$ est scindé pour $c=0$ (facile) et irréductible pour $c≠0$ (plus dur).

Exo 2.1

In [17]:
A.<x,y> = QQ[]
In [18]:
P = x*y^5 + 2*y^4 + 3*y^3*x^3 + 4*x^2*y^2 + 5*x*y^2 + 6*y*x^3 + 7*y
P
Out[18]:
3*x^3*y^3 + x*y^5 + 6*x^3*y + 4*x^2*y^2 + 2*y^4 + 5*x*y^2 + 7*y
In [19]:
P.degree()
Out[19]:
6
In [20]:
Q = P.polynomial(x)
Q
Out[20]:
(3*y^3 + 6*y)*x^3 + 4*y^2*x^2 + (y^5 + 5*y^2)*x + 2*y^4 + 7*y
In [21]:
Q.parent()
Out[21]:
Univariate Polynomial Ring in x over Univariate Polynomial Ring in y over Rational Field
In [22]:
B = QQ['y']['x']
B
Out[22]:
Univariate Polynomial Ring in x over Univariate Polynomial Ring in y over Rational Field
In [23]:
B(P)
Out[23]:
(3*y^3 + 6*y)*x^3 + 4*y^2*x^2 + (y^5 + 5*y^2)*x + 2*y^4 + 7*y

Attention, le nom des variables doit être exactement le même pour que Sage accepte de faire la conversion.

In [24]:
C = QQ['Y']['X']
C
Out[24]:
Univariate Polynomial Ring in X over Univariate Polynomial Ring in Y over Rational Field
In [25]:
C(P)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-25-d7215608f13a> in <module>()
----> 1 C(P)

/opt/conda/lib/python3.6/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9727)()
    918         if mor is not None:
    919             if no_extra_args:
--> 920                 return mor._call_(x)
    921             else:
    922                 return mor._call_with_args(x, args, kwds)

/opt/conda/lib/python3.6/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.NamedConvertMap._call_ (build/cythonized/sage/structure/coerce_maps.c:6016)()
    269             raise TypeError("Cannot coerce {} to {}".format(x, C))
    270         cdef Map m
--> 271         cdef Element e = method(C)
    272         if e is None:
    273             raise RuntimeError("BUG in coercion model: {} method of {} returned None".format(self.method_name, type(x)))

/opt/conda/lib/python3.6/site-packages/sage/rings/polynomial/multi_polynomial.pyx in sage.rings.polynomial.multi_polynomial.MPolynomial._polynomial_ (build/cythonized/sage/rings/polynomial/multi_polynomial.c:5669)()
    195             return R(self.polynomial(self._parent(var)))
    196         else:
--> 197             return R([self])
    198 
    199     def coefficients(self):

/opt/conda/lib/python3.6/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9727)()
    918         if mor is not None:
    919             if no_extra_args:
--> 920                 return mor._call_(x)
    921             else:
    922                 return mor._call_with_args(x, args, kwds)

/opt/conda/lib/python3.6/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4554)()
    143                 print(type(C), C)
    144                 print(type(C._element_constructor), C._element_constructor)
--> 145             raise
    146 
    147     cpdef Element _call_with_args(self, x, args=(), kwds={}):

/opt/conda/lib/python3.6/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4422)()
    138         cdef Parent C = self._codomain
    139         try:
--> 140             return C._element_constructor(x)
    141         except Exception:
    142             if print_warnings:

/opt/conda/lib/python3.6/site-packages/sage/rings/polynomial/polynomial_ring.py in _element_constructor_(self, x, check, is_gen, construct, **kwds)
    405         C = self.element_class
    406         if isinstance(x, (list, tuple)):
--> 407             return C(self, x, check=check, is_gen=False, construct=construct)
    408         if isinstance(x, range):
    409             return C(self, list(x), check=check, is_gen=False,

/opt/conda/lib/python3.6/site-packages/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial_generic_dense.__init__ (build/cythonized/sage/rings/polynomial/polynomial_element.c:96766)()
  10489         if isinstance(x, list):
  10490             if check:
> 10491                 self.__coeffs = [R(t) for t in x]
  10492                 self.__normalize()
  10493             else:

/opt/conda/lib/python3.6/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9727)()
    918         if mor is not None:
    919             if no_extra_args:
--> 920                 return mor._call_(x)
    921             else:
    922                 return mor._call_with_args(x, args, kwds)

/opt/conda/lib/python3.6/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.NamedConvertMap._call_ (build/cythonized/sage/structure/coerce_maps.c:6016)()
    269             raise TypeError("Cannot coerce {} to {}".format(x, C))
    270         cdef Map m
--> 271         cdef Element e = method(C)
    272         if e is None:
    273             raise RuntimeError("BUG in coercion model: {} method of {} returned None".format(self.method_name, type(x)))

/opt/conda/lib/python3.6/site-packages/sage/rings/polynomial/multi_polynomial.pyx in sage.rings.polynomial.multi_polynomial.MPolynomial._polynomial_ (build/cythonized/sage/rings/polynomial/multi_polynomial.c:5669)()
    195             return R(self.polynomial(self._parent(var)))
    196         else:
--> 197             return R([self])
    198 
    199     def coefficients(self):

/opt/conda/lib/python3.6/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9727)()
    918         if mor is not None:
    919             if no_extra_args:
--> 920                 return mor._call_(x)
    921             else:
    922                 return mor._call_with_args(x, args, kwds)

/opt/conda/lib/python3.6/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4554)()
    143                 print(type(C), C)
    144                 print(type(C._element_constructor), C._element_constructor)
--> 145             raise
    146 
    147     cpdef Element _call_with_args(self, x, args=(), kwds={}):

/opt/conda/lib/python3.6/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4422)()
    138         cdef Parent C = self._codomain
    139         try:
--> 140             return C._element_constructor(x)
    141         except Exception:
    142             if print_warnings:

/opt/conda/lib/python3.6/site-packages/sage/rings/polynomial/polynomial_ring.py in _element_constructor_(self, x, check, is_gen, construct, **kwds)
    405         C = self.element_class
    406         if isinstance(x, (list, tuple)):
--> 407             return C(self, x, check=check, is_gen=False, construct=construct)
    408         if isinstance(x, range):
    409             return C(self, list(x), check=check, is_gen=False,

/opt/conda/lib/python3.6/site-packages/sage/rings/polynomial/polynomial_rational_flint.pyx in sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint.__init__ (build/cythonized/sage/rings/polynomial/polynomial_rational_flint.cpp:5083)()
    236                 return
    237             elif len(x) == 1:
--> 238                 Polynomial_rational_flint.__init__(self, parent, x[0],
    239                                 check=check, is_gen=False, construct=construct)
    240                 return

/opt/conda/lib/python3.6/site-packages/sage/rings/polynomial/polynomial_rational_flint.pyx in sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint.__init__ (build/cythonized/sage/rings/polynomial/polynomial_rational_flint.cpp:6066)()
    285 
    286         else:
--> 287             x = parent.base_ring()(x)
    288             Polynomial_rational_flint.__init__(self, parent, x, check=check,
    289                                             is_gen=is_gen, construct=construct)

/opt/conda/lib/python3.6/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9727)()
    918         if mor is not None:
    919             if no_extra_args:
--> 920                 return mor._call_(x)
    921             else:
    922                 return mor._call_with_args(x, args, kwds)

/opt/conda/lib/python3.6/site-packages/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.ConstantPolynomialSection._call_ (build/cythonized/sage/rings/polynomial/polynomial_element.c:105936)()
  11377                 return <Element>((<Polynomial>x).constant_coefficient())
  11378         else:
> 11379             raise TypeError("not a constant polynomial")
  11380 
  11381 cdef class PolynomialBaseringInjection(Morphism):

TypeError: not a constant polynomial

Exo 2.2

In [26]:
A.<x,y> = QQ[]
P = (x^2 + x*y + x + y) * (x + y)
P
Out[26]:
x^3 + 2*x^2*y + x*y^2 + x^2 + 2*x*y + y^2
In [27]:
fac = P.factor()
fac
Out[27]:
(x + 1) * (x + y)^2

Attention: en Sage, une "factorisation" est un objet différent d'un polynôme.

In [28]:
parent(fac)
Out[28]:
<class 'sage.structure.factorization.Factorization'>
In [29]:
type(fac)
Out[29]:
<class 'sage.structure.factorization.Factorization'>
In [30]:
fac in A
Out[30]:
False
In [31]:
e = fac.expand()
e
Out[31]:
x^3 + 2*x^2*y + x*y^2 + x^2 + 2*x*y + y^2
In [32]:
e in A
Out[32]:
True
In [33]:
P.polynomial(x)
Out[33]:
x^3 + (2*y + 1)*x^2 + (y^2 + 2*y)*x + y^2
In [34]:
P.polynomial(y)
Out[34]:
(x + 1)*y^2 + (2*x^2 + 2*x)*y + x^3 + x^2

Exo 3.1

In [35]:
A.<x,y> = QQ[]
P = x*y^5 + 2*y^4 + 3*y^3*x^3 + 4*x^2*y^2 + 5*x*y^2 + 6*y*x^3 + 7*y
P
Out[35]:
3*x^3*y^3 + x*y^5 + 6*x^3*y + 4*x^2*y^2 + 2*y^4 + 5*x*y^2 + 7*y
In [36]:
B.<x,y> = PolynomialRing(QQ, order='lex')
B
Out[36]:
Multivariate Polynomial Ring in x, y over Rational Field
In [37]:
B.term_order()
Out[37]:
Lexicographic term order
In [38]:
A.term_order()
Out[38]:
Degree reverse lexicographic term order
In [39]:
B(P)
Out[39]:
3*x^3*y^3 + 6*x^3*y + 4*x^2*y^2 + x*y^5 + 5*x*y^2 + 2*y^4 + 7*y
In [40]:
C = A.change_ring(order='deglex')
C
Out[40]:
Multivariate Polynomial Ring in x, y over Rational Field
In [41]:
C.term_order()
Out[41]:
Degree lexicographic term order
In [42]:
C(P)
Out[42]:
3*x^3*y^3 + x*y^5 + 6*x^3*y + 4*x^2*y^2 + 2*y^4 + 5*x*y^2 + 7*y
In [43]:
P
Out[43]:
3*x^3*y^3 + x*y^5 + 6*x^3*y + 4*x^2*y^2 + 2*y^4 + 5*x*y^2 + 7*y
In [44]:
P.parent().term_order()
Out[44]:
Degree reverse lexicographic term order
In [45]:
%display latex
In [46]:
A.<x,y,z,t> = QQ[]
Q = x*y^3*z*t + x^2*y*z^3*t + x^2*y*z^2*t + x^3*z^2*t^2
Q
Out[46]:
In [47]:
A.change_ring(order='lex')(Q)
Out[47]:
In [48]:
A.change_ring(order='deglex')(Q)
Out[48]:

Exo 3.4

In [49]:
A.<x,y> = PolynomialRing(QQ, order='lex')
g = x - y
h = x - y^2
p = x*y - x
In [50]:
g, h, p
Out[50]:
In [51]:
p.reduce([g, h])
Out[51]:
In [52]:
p.reduce([h, g])
Out[52]:

Le résultat de reduce n'est pas uniquement défini si la liste des polynômes passés ne forme pas une base de Gröbner. Ceci est précisé dans la doc

In [53]:
help(p.reduce)
Help on built-in function reduce:

reduce(...) method of sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular instance
    MPolynomial_libsingular.reduce(self, I)
    File: sage/rings/polynomial/multi_polynomial_libsingular.pyx (starting at line 4482)
    
            Return a remainder of this polynomial modulo the 
            polynomials in ``I``.
            
            INPUT:
    
            - ``I`` - an ideal or a list/set/iterable of polynomials. 
    
            OUTPUT:
    
            A polynomial ``r``  such that:
    
            - ``self`` - ``r`` is in the ideal generated by ``I``.
    
            - No term in ``r`` is divisible by any of the leading monomials
              of ``I``.
    
            The result ``r`` is canonical if:
    
            - ``I`` is an ideal, and Sage can compute a Groebner basis of it.
    
            - ``I`` is a list/set/iterable that is a (strong) Groebner basis
              for the term order of ``self``. (A strong Groebner basis is 
              such that for every leading term ``t`` of the ideal generated
              by ``I``, there exists an element ``g`` of ``I`` such that the
              leading term of ``g`` divides ``t``.)
    
            The result ``r`` is implementation-dependent (and possibly 
            order-dependent) otherwise. If ``I`` is an ideal and no Groebner
            basis can be computed, its list of generators ``I.gens()`` is
            used for the reduction.
    
            EXAMPLES::
    
                sage: P.<x,y,z> = QQ[]
                sage: f1 = -2 * x^2 + x^3
                sage: f2 = -2 * y + x* y
                sage: f3 = -x^2 + y^2
                sage: F = Ideal([f1,f2,f3])
                sage: g = x*y - 3*x*y^2
                sage: g.reduce(F)
                -6*y^2 + 2*y
                sage: g.reduce(F.gens())
                -6*y^2 + 2*y
    
            `\ZZ` is also supported. ::
    
                sage: P.<x,y,z> = ZZ[]
                sage: f1 = -2 * x^2 + x^3
                sage: f2 = -2 * y + x* y
                sage: f3 = -x^2 + y^2
                sage: F = Ideal([f1,f2,f3])
                sage: g = x*y - 3*x*y^2
                sage: g.reduce(F)
                -6*y^2 + 2*y
                sage: g.reduce(F.gens())
                -6*y^2 + 2*y
    
                sage: f = 3*x
                sage: f.reduce([2*x,y])
                3*x
    
            The reduction is not canonical when ``I`` is not a Groebner 
            basis::
    
                sage: A.<x,y> = QQ[]
                sage: (x+y).reduce([x+y, x-y])
                2*y
                sage: (x+y).reduce([x-y, x+y])
                0

On retrouve facilement quel est le calcul qui a été fait par reduce

In [54]:
p.mod(h)
Out[54]:
In [55]:
p.mod(g)
Out[55]:
In [56]:
p.mod(h).mod(g)
Out[56]:
In [57]:
p.mod(g).mod(h)
Out[57]:

On pourrait croire que reduce reduit modulo la liste de polynômes dans l'ordre dans lequel ils sont donnés, c'est plus compliqué que cela, cependant. Dans cet exemple, on voit que le résultat n'est pas canonique, mais ne depend pas de l'ordre.

In [58]:
g = x^2*y^2 - x
h = x*y^2 + y
In [59]:
g.reduce([g,h])
Out[59]:
In [60]:
h.reduce([g,h])
Out[60]:
In [61]:
g.reduce([h,g])
Out[61]:
In [62]:
A.ideal([g,h]).reduce(g)
Out[62]:
In [63]:
g.mod([g,h])
Out[63]:

Exo 3.6

In [64]:
%display plain
In [65]:
A.<x,y> = PolynomialRing(QQ, order='lex')
f = x^7*y^2 + x^3*y^2 - y - 1
In [66]:
f1 = x*y^2 - x
f2 = x - y^3
In [67]:
I = A.ideal([f1, f2])
I
Out[67]:
Ideal (x*y^2 - x, x - y^3) of Multivariate Polynomial Ring in x, y over Rational Field

Cette fois-ci la réduction calcule bien une base de Gröbner

In [69]:
I.reduce(f)
Out[69]:
2*y^3 - y - 1
In [70]:
f.mod(I)
Out[70]:
2*y^3 - y - 1
In [71]:
f.mod([f1, f2])
Out[71]:
2*y^3 - y - 1
In [72]:
B = A.change_ring(order='deglex')
B
Out[72]:
Multivariate Polynomial Ring in x, y over Rational Field
In [73]:
J = I.change_ring(B)
J
Out[73]:
Ideal (x*y^2 - x, -y^3 + x) of Multivariate Polynomial Ring in x, y over Rational Field
In [74]:
g = B(f).mod(J)
g
Out[74]:
2*x - y - 1
In [75]:
g.parent().term_order()
Out[75]:
Degree lexicographic term order
In [76]:
f.mod([f2, f1])
Out[76]:
2*y^3 - y - 1
In [77]:
I2 = A.ideal([f2, f1])
In [78]:
f.mod(I2)
Out[78]:
2*y^3 - y - 1

Exo 3.7

In [79]:
A.<x,y,z> = QQ[]
p = z^2 - x^4*y
g1, g2 = y - x^2, z - x^3
I = A.ideal([g1, g2])
I
Out[79]:
Ideal (-x^2 + y, -x^3 + z) of Multivariate Polynomial Ring in x, y, z over Rational Field
In [80]:
p in I
Out[80]:
True
In [81]:
p.mod(I)
Out[81]:
0
In [82]:
a, b = p.lift(I)
a, b
Out[82]:
(-x*z, x*y + z)
In [83]:
a*g1 + b*g2 == p
Out[83]:
True