A.<x> = ZZ[]
P = x^7 + x^5 + 2*x^3 + 2*x^2 + 3*x + 2
P
x^7 + x^5 + 2*x^3 + 2*x^2 + 3*x + 2
P.change_ring(GF(2)).factor()
x * (x^3 + x^2 + 1)^2
P.change_ring(GF(7)).factor()
(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:
P(-4)
-17514
Reste à vérifier que $P(-4 - c·14) ≠ 0$ pour tout $c>1$. Exercice.
P.is_irreducible()
True
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
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
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
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).
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
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
P.degree()
6
Q = P.polynomial(x)
Q
(3*y^3 + 6*y)*x^3 + 4*y^2*x^2 + (y^5 + 5*y^2)*x + 2*y^4 + 7*y
Q.parent()
Univariate Polynomial Ring in x over Univariate Polynomial Ring in y over Rational Field
B = QQ['y']['x']
B
Univariate Polynomial Ring in x over Univariate Polynomial Ring in y over Rational Field
B(P)
(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.
C = QQ['Y']['X']
C
Univariate Polynomial Ring in X over Univariate Polynomial Ring in Y over Rational Field
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
A.<x,y> = QQ[]
P = (x^2 + x*y + x + y) * (x + y)
P
x^3 + 2*x^2*y + x*y^2 + x^2 + 2*x*y + y^2
fac = P.factor()
fac
(x + 1) * (x + y)^2
Attention: en Sage, une "factorisation" est un objet différent d'un polynôme.
parent(fac)
<class 'sage.structure.factorization.Factorization'>
type(fac)
<class 'sage.structure.factorization.Factorization'>
fac in A
False
e = fac.expand()
e
x^3 + 2*x^2*y + x*y^2 + x^2 + 2*x*y + y^2
e in A
True
P.polynomial(x)
x^3 + (2*y + 1)*x^2 + (y^2 + 2*y)*x + y^2
P.polynomial(y)
(x + 1)*y^2 + (2*x^2 + 2*x)*y + x^3 + x^2
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
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
B.<x,y> = PolynomialRing(QQ, order='lex')
B
Multivariate Polynomial Ring in x, y over Rational Field
B.term_order()
Lexicographic term order
A.term_order()
Degree reverse lexicographic term order
B(P)
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
C = A.change_ring(order='deglex')
C
Multivariate Polynomial Ring in x, y over Rational Field
C.term_order()
Degree lexicographic term order
C(P)
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
P
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
P.parent().term_order()
Degree reverse lexicographic term order
%display latex
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
A.change_ring(order='lex')(Q)
A.change_ring(order='deglex')(Q)
A.<x,y> = PolynomialRing(QQ, order='lex')
g = x - y
h = x - y^2
p = x*y - x
g, h, p
p.reduce([g, h])
p.reduce([h, g])
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
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
p.mod(h)
p.mod(g)
p.mod(h).mod(g)
p.mod(g).mod(h)
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.
g = x^2*y^2 - x
h = x*y^2 + y
g.reduce([g,h])
h.reduce([g,h])
g.reduce([h,g])
A.ideal([g,h]).reduce(g)
g.mod([g,h])
%display plain
A.<x,y> = PolynomialRing(QQ, order='lex')
f = x^7*y^2 + x^3*y^2 - y - 1
f1 = x*y^2 - x
f2 = x - y^3
I = A.ideal([f1, f2])
I
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
I.reduce(f)
2*y^3 - y - 1
f.mod(I)
2*y^3 - y - 1
f.mod([f1, f2])
2*y^3 - y - 1
B = A.change_ring(order='deglex')
B
Multivariate Polynomial Ring in x, y over Rational Field
J = I.change_ring(B)
J
Ideal (x*y^2 - x, -y^3 + x) of Multivariate Polynomial Ring in x, y over Rational Field
g = B(f).mod(J)
g
2*x - y - 1
g.parent().term_order()
Degree lexicographic term order
f.mod([f2, f1])
2*y^3 - y - 1
I2 = A.ideal([f2, f1])
f.mod(I2)
2*y^3 - y - 1
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
Ideal (-x^2 + y, -x^3 + z) of Multivariate Polynomial Ring in x, y, z over Rational Field
p in I
True
p.mod(I)
0
a, b = p.lift(I)
a, b
(-x*z, x*y + z)
a*g1 + b*g2 == p
True