Exercice 1.1

Avec des variables symboliques

In [1]:
P1 = x^6 + 2*x^5 - 2*x^4 + 2*x^2 - 2*x - 1
P2 = x^5 + x^4 - 2*x^3 + x^2 + x - 2
In [2]:
P1
Out[2]:
x^6 + 2*x^5 - 2*x^4 + 2*x^2 - 2*x - 1
In [3]:
parent(P1)
Out[3]:
Symbolic Ring
In [4]:
P = P1*P2
P
Out[4]:
(x^6 + 2*x^5 - 2*x^4 + 2*x^2 - 2*x - 1)*(x^5 + x^4 - 2*x^3 + x^2 + x - 2)
In [5]:
P.degree()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-5-9e45d9af985d> in <module>()
----> 1 P.degree()

TypeError: degree() takes exactly one argument (0 given)

Le message d'erreur nous indique que .degree() s'attend à recevoir un paramètre. Lisons la doc pour savoir quel est ce paramètre.

In [6]:
P.degree?
In [7]:
P.degree(x)
Out[7]:
11
In [8]:
P.leading_coeff()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-8-92c5cbae2251> in <module>()
----> 1 P.leading_coeff()

TypeError: leading_coefficient() takes exactly one argument (0 given)
In [9]:
P.leading_coeff?
In [10]:
P.leading_coeff(x)
Out[10]:
0

Comportement surprenant de .leading_coeff()... mais $P$ n'est pas vraiment un polynôme:

In [11]:
P
Out[11]:
(x^6 + 2*x^5 - 2*x^4 + 2*x^2 - 2*x - 1)*(x^5 + x^4 - 2*x^3 + x^2 + x - 2)

Évaluons l'expression symbolique pour obtenir le coefficient de tête

In [12]:
PP = P.expand()
PP
Out[12]:
x^11 + 3*x^10 - 2*x^9 - 5*x^8 + 9*x^7 - 2*x^6 - 13*x^5 + 9*x^4 + 2*x^3 - 7*x^2 + 3*x + 2
In [13]:
PP.leading_coeff(x)
Out[13]:
1

.leading_coefficient() est un synonime de .leading_coeff()

In [14]:
PP.leading_coefficient(x)
Out[14]:
1

Cette fonction fait à peu près ce qui est demandé: elle donne une liste de paires coefficient-degré

In [15]:
PP.coefficients(x)
Out[15]:
[[2, 0],
 [3, 1],
 [-7, 2],
 [2, 3],
 [9, 4],
 [-13, 5],
 [-2, 6],
 [9, 7],
 [-5, 8],
 [-2, 9],
 [3, 10],
 [1, 11]]
In [16]:
PP.coefficient(x,3)
Out[16]:
2
In [17]:
P1 / P2
Out[17]:
(x^6 + 2*x^5 - 2*x^4 + 2*x^2 - 2*x - 1)/(x^5 + x^4 - 2*x^3 + x^2 + x - 2)
In [18]:
P1 // P2
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-18-743d0af7da88> in <module>()
----> 1 P1 // P2

/local/SageMath-8.0/src/sage/structure/element.pyx in sage.structure.element.Element.__floordiv__ (/local/SageMath-8.0/src/build/cythonized/sage/structure/element.c:13144)()
   1767         cdef int cl = classify_elements(left, right)
   1768         if HAVE_SAME_PARENT(cl):
-> 1769             return (<Element>left)._floordiv_(right)
   1770         if BOTH_ARE_ELEMENT(cl):
   1771             return coercion_model.bin_op(left, right, floordiv)

/local/SageMath-8.0/src/sage/structure/element.pyx in sage.structure.element.Element._floordiv_ (/local/SageMath-8.0/src/build/cythonized/sage/structure/element.c:13470)()
   1802             python_op = (<object>self)._floordiv_
   1803         except AttributeError:
-> 1804             raise bin_op_exception('//', self, other)
   1805         else:
   1806             return python_op(other)

TypeError: unsupported operand parent(s) for //: 'Symbolic Ring' and 'Symbolic Ring'
In [19]:
P1 % P2
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-19-ee58285ce103> in <module>()
----> 1 P1 % P2

/local/SageMath-8.0/src/sage/structure/element.pyx in sage.structure.element.Element.__mod__ (/local/SageMath-8.0/src/build/cythonized/sage/structure/element.c:13586)()
   1867         cdef int cl = classify_elements(left, right)
   1868         if HAVE_SAME_PARENT(cl):
-> 1869             return (<Element>left)._mod_(right)
   1870         if BOTH_ARE_ELEMENT(cl):
   1871             return coercion_model.bin_op(left, right, mod)

/local/SageMath-8.0/src/sage/structure/element.pyx in sage.structure.element.Element._mod_ (/local/SageMath-8.0/src/build/cythonized/sage/structure/element.c:13912)()
   1902             python_op = (<object>self)._mod_
   1903         except AttributeError:
-> 1904             raise bin_op_exception('%', self, other)
   1905         else:
   1906             return python_op(other)

TypeError: unsupported operand parent(s) for %: 'Symbolic Ring' and 'Symbolic Ring'

Pas de division Euclidienne dans l'anneau symbolique!

In [20]:
G = gcd(P1, P2)
G
Out[20]:
x^4 - x^3 + x - 1

Vérifions que $G$ divise bien $A$. Pour forcer l'anneau symbolique à simplifier les fractions rationnelles, nous appelons la méthode .simplify_full().

In [21]:
A = P1 / G
A.simplify_full()
Out[21]:
x^2 + 3*x + 1
In [22]:
(P2 / G).simplify_full()
Out[22]:
x + 2
In [23]:
factor(PP)
Out[23]:
(x^2 + 3*x + 1)*(x^2 - x + 1)^2*(x + 2)*(x + 1)^2*(x - 1)^2
In [24]:
PP.factor()
Out[24]:
(x^2 + 3*x + 1)*(x^2 - x + 1)^2*(x + 2)*(x + 1)^2*(x - 1)^2
In [25]:
P.factor()
Out[25]:
(x^2 + 3*x + 1)*(x^2 - x + 1)^2*(x + 2)*(x + 1)^2*(x - 1)^2
In [26]:
P(2)
/local/SageMath-8.0/local/lib/python2.7/site-packages/IPython/core/interactiveshell.py:2881: DeprecationWarning: Substitution using function-call syntax and unnamed arguments is deprecated and will be removed from a future release of Sage; you can use named arguments instead, like EXPR(x=..., y=...)
See http://trac.sagemath.org/5930 for details.
  exec(code_obj, self.user_global_ns, self.user_ns)
Out[26]:
3564

Nous avons obtenu un warning nous avertissant que la syntaxe P(a) n'est pas la bonne façon d'évaluer un polynôme symbolique P en a.

Il faut indiquer explicitement quelle variable est remplacée par a, comme ici:

In [27]:
P(x=2)
Out[27]:
3564

Même exercice, avec des anneaux de polynomes

In [28]:
A.<X> = QQ[]
In [29]:
A
Out[29]:
Univariate Polynomial Ring in X over Rational Field
In [30]:
# Syntaxes alternatives
A = QQ['X']
X = A.gen()
#
A.<X> = QQ['X']

Pour convertir le polynôme symbolique P1 en polynôme de cette anneau, nous devons jongler un peu avec l'évaluation et la coercion.

La coercion toute seule ne suffit pas (les noms des variables sont différents):

In [31]:
A(P1)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-31-898672382792> in <module>()
----> 1 A(P1)

/local/SageMath-8.0/src/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (/local/SageMath-8.0/src/build/cythonized/sage/structure/parent.c:9799)()
    932         if mor is not None:
    933             if no_extra_args:
--> 934                 return mor._call_(x)
    935             else:
    936                 return mor._call_with_args(x, args, kwds)

/local/SageMath-8.0/src/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.NamedConvertMap._call_ (/local/SageMath-8.0/src/build/cythonized/sage/structure/coerce_maps.c:6293)()
    280             raise TypeError("Cannot coerce {} to {}".format(x, C))
    281         cdef Map m
--> 282         cdef Element e = method(C)
    283         if e is None:
    284             raise RuntimeError("BUG in coercion model: {} method of {} returned None".format(self.method_name, type(x)))

/local/SageMath-8.0/src/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression._polynomial_ (/local/SageMath-8.0/src/build/cythonized/sage/symbolic/expression.cpp:39927)()
   6695             else:
   6696                 return R([self])
-> 6697         return self.polynomial(None, ring=R)
   6698 
   6699     def fraction(self, base_ring):

/local/SageMath-8.0/src/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression.polynomial (/local/SageMath-8.0/src/build/cythonized/sage/symbolic/expression.cpp:39375)()
   6570         """
   6571         from sage.symbolic.expression_conversions import polynomial
-> 6572         return polynomial(self, base_ring=base_ring, ring=ring)
   6573 
   6574     def laurent_polynomial(self, base_ring=None, ring=None):

/local/SageMath-8.0/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py in polynomial(ex, base_ring, ring)
   1212          1.87813065119873*x^2 + 20.0855369231877
   1213     """
-> 1214     converter = PolynomialConverter(ex, base_ring=base_ring, ring=ring)
   1215     res = converter()
   1216     return converter.ring(res)

/local/SageMath-8.0/local/lib/python2.7/site-packages/sage/symbolic/expression_conversions.py in __init__(self, ex, base_ring, ring)
   1025             for v in ex.variables():
   1026                 if repr(v) not in self.varnames and v not in base_ring:
-> 1027                     raise TypeError("%s is not a variable of %s" %(v, ring))
   1028             self.ring = ring
   1029             self.base_ring = base_ring

TypeError: x is not a variable of Univariate Polynomial Ring in X over Rational Field

L'évaluation toute seule nous laisse avec un élément de l'anneau symbolique

In [32]:
Q1 = P1(x=X)
Q1
Out[32]:
X^6 + 2*X^5 - 2*X^4 + 2*X^2 - 2*X - 1
In [33]:
parent(Q1)
Out[33]:
Symbolic Ring

Les deux ensemble nous donnent le résultat cherché

In [34]:
Q1 = A(P1(x=X))
Q1
Out[34]:
X^6 + 2*X^5 - 2*X^4 + 2*X^2 - 2*X - 1
In [35]:
parent(Q1)
Out[35]:
Univariate Polynomial Ring in X over Rational Field
In [36]:
Q2 = A(P2(x=X))
Q2
Out[36]:
X^5 + X^4 - 2*X^3 + X^2 + X - 2
In [37]:
Q = Q1*Q2
Q
Out[37]:
X^11 + 3*X^10 - 2*X^9 - 5*X^8 + 9*X^7 - 2*X^6 - 13*X^5 + 9*X^4 + 2*X^3 - 7*X^2 + 3*X + 2

.degree() et .leading_coefficient() ne prennent pas d'argument ici:

In [38]:
Q.degree()
Out[38]:
11
In [39]:
Q.leading_coefficient()
Out[39]:
1
In [40]:
Q.coefficients()
Out[40]:
[2, 3, -7, 2, 9, -13, -2, 9, -5, -2, 3, 1]
In [41]:
Q.list()
Out[41]:
[2, 3, -7, 2, 9, -13, -2, 9, -5, -2, 3, 1]

Il n'y a pas de méthode pour obtenir la liste des termes, mais nous pouvons écrire une boucle compacte, en faisant appel à la fonction Python enumerate().

In [42]:
for i,c in enumerate(Q):
    print(c*x^i)
2
3*x
-7*x^2
2*x^3
9*x^4
-13*x^5
-2*x^6
9*x^7
-5*x^8
-2*x^9
3*x^10
x^11

Solution similaire, mais avec une compréhension de listes

In [43]:
[c*X^i for (i,c) in enumerate(Q)]
Out[43]:
[2,
 3*X,
 -7*X^2,
 2*X^3,
 9*X^4,
 -13*X^5,
 -2*X^6,
 9*X^7,
 -5*X^8,
 -2*X^9,
 3*X^10,
 X^11]

La division promeut les polynômes en fractions rationnelles

In [44]:
R = Q1 / Q2
R
Out[44]:
(X^2 + 3*X + 1)/(X + 2)
In [45]:
parent(R)
Out[45]:
Fraction Field of Univariate Polynomial Ring in X over Rational Field
In [46]:
Q1 // Q2
Out[46]:
X + 1
In [47]:
Q1 % Q2
Out[47]:
-X^4 + X^3 - X + 1
In [48]:
Q2 * (Q1 // Q2) + Q1 % Q2 == Q1
Out[48]:
True
In [49]:
Q1.quo_rem(Q2)
Out[49]:
(X + 1, -X^4 + X^3 - X + 1)
In [50]:
Q1.gcd(Q2)
Out[50]:
X^4 - X^3 + X - 1
In [51]:
F = Q.factor()
F
Out[51]:
(X + 2) * (X - 1)^2 * (X + 1)^2 * (X^2 + 3*X + 1) * (X^2 - X + 1)^2
In [52]:
parent(F)
Out[52]:
<class 'sage.structure.factorization.Factorization'>

L'évaluation de polynômes univariés ne nécessite pas de spécifier la variable remplacée.

In [53]:
Q(2)
Out[53]:
3564
In [54]:
Q(X=2)
Out[54]:
3564

Exercice 1.2

In [55]:
A.<x> = ZZ[]
P = x^11 + x^10 + x^9 + 2*x^8 + 2*x^6 + 2*x^4 + x^3 + x^2 + x
In [56]:
parent(x)
Out[56]:
Univariate Polynomial Ring in x over Integer Ring
In [57]:
P
Out[57]:
x^11 + x^10 + x^9 + 2*x^8 + 2*x^6 + 2*x^4 + x^3 + x^2 + x
In [58]:
P.factor()
Out[58]:
x * (x^2 + 1) * (x^2 + x + 1) * (x^6 - x^4 + 2*x^3 - x^2 + 1)

Pour obtenir une copie d'un objet, avec un anneau des coefficients changé

In [59]:
P.base_ring()
Out[59]:
Integer Ring
In [60]:
Q = P.change_ring(QQ)
Q
Out[60]:
x^11 + x^10 + x^9 + 2*x^8 + 2*x^6 + 2*x^4 + x^3 + x^2 + x
In [61]:
parent(Q)
Out[61]:
Univariate Polynomial Ring in x over Rational Field
In [62]:
Q.factor()
Out[62]:
x * (x^2 + 1) * (x^2 + x + 1) * (x^6 - x^4 + 2*x^3 - x^2 + 1)
In [63]:
parent(I)
Out[63]:
Symbolic Ring
In [64]:
I^2
Out[64]:
-1
In [65]:
ZZ[I]
Out[65]:
Order in Number Field in I with defining polynomial x^2 + 1
In [66]:
B.<x> = ZZ[I][]
B
Out[66]:
Univariate Polynomial Ring in x over Order in Number Field in I with defining polynomial x^2 + 1

Coercion d'un polynôme dans un nouvel anneau

In [67]:
R = B(P)
R
Out[67]:
x^11 + x^10 + x^9 + 2*x^8 + 2*x^6 + 2*x^4 + x^3 + x^2 + x
In [68]:
parent(R)
Out[68]:
Univariate Polynomial Ring in x over Order in Number Field in I with defining polynomial x^2 + 1
In [69]:
R.factor()
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-69-0b68b8e5d8fd> in <module>()
----> 1 R.factor()

/local/SageMath-8.0/src/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.factor (/local/SageMath-8.0/src/build/cythonized/sage/rings/polynomial/polynomial_element.c:39218)()
   4104             # This was copied from the general multivariate implementation
   4105             try:
-> 4106                 if R.is_finite():
   4107                     if R.characteristic() > 1<<29:
   4108                         raise NotImplementedError("Factorization of multivariate polynomials over prime fields with characteristic > 2^29 is not implemented.")

/local/SageMath-8.0/src/sage/rings/ring.pyx in sage.rings.ring.Ring.is_finite (/local/SageMath-8.0/src/build/cythonized/sage/rings/ring.c:8793)()
    912         if self.is_zero():
    913             return True
--> 914         raise NotImplementedError
    915 
    916     def cardinality(self):

NotImplementedError: 

On apprend que Sage ne sait pas factoriser dans $ℤ[i]$. Heureusement, il sait factoriser dans $ℚ[i]$.

In [70]:
R = P.change_ring(QQ[I])
R.factor()
Out[70]:
(x - I) * x * (x + I) * (x^2 + x + 1) * (x^6 - x^4 + 2*x^3 - x^2 + 1)
In [71]:
P.factor()
Out[71]:
x * (x^2 + 1) * (x^2 + x + 1) * (x^6 - x^4 + 2*x^3 - x^2 + 1)
In [72]:
S = P.change_ring(GF(2))
S.factor()
Out[72]:
x * (x + 1)^8 * (x^2 + x + 1)
In [73]:
GF(4)
Out[73]:
Finite Field in z2 of size 2^2
In [74]:
T = P.change_ring(GF(4))
T.factor()
Out[74]:
x * (x + z2) * (x + z2 + 1) * (x + 1)^8

Exercice 1.3

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

Exercice 1.4

In [80]:
for p in primes(12):
    A.<x> = GF(p)[]
    print('')
    print('p = %d' % p)
    for c in range(p):
        print((x^p - x + c).factor())
p = 2
x * (x + 1)
x^2 + x + 1

p = 3
x * (x + 1) * (x + 2)
x^3 + 2*x + 1
x^3 + 2*x + 2

p = 5
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

p = 7
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

p = 11
x * (x + 1) * (x + 2) * (x + 3) * (x + 4) * (x + 5) * (x + 6) * (x + 7) * (x + 8) * (x + 9) * (x + 10)
x^11 + 10*x + 1
x^11 + 10*x + 2
x^11 + 10*x + 3
x^11 + 10*x + 4
x^11 + 10*x + 5
x^11 + 10*x + 6
x^11 + 10*x + 7
x^11 + 10*x + 8
x^11 + 10*x + 9
x^11 + 10*x + 10