Polynomial Sequences¶

We call a finite list of polynomials a Polynomial Sequence.

Polynomial sequences in Sage can optionally be viewed as consisting of various parts or sub-sequences. These kind of polynomial sequences which naturally split into parts arise naturally for example in algebraic cryptanalysis of symmetric cryptographic primitives. The most prominent examples of these systems are: the small scale variants of the AES [CMR2005] (cf. sage.crypto.mq.sr.SR()) and Flurry/Curry [BPW2006]. By default, a polynomial sequence has exactly one part.

AUTHORS:

Martin Albrecht (2007ff): initial version
Martin Albrecht (2009): refactoring, clean-up, new functions
Martin Albrecht (2011): refactoring, moved to sage.rings.polynomial
Alex Raichev (2011-06): added algebraic_dependence()
Charles Bouillaguet (2013-1): added solve()

EXAMPLES:

As an example consider a small scale variant of the AES:

Sage

sage: sr = mq.SR(2, 1, 2, 4, gf2=True, polybori=True)                               # needs sage.rings.polynomial.pbori
sage: sr                                                                            # needs sage.rings.polynomial.pbori
SR(2,1,2,4)

Python

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(1), Integer(2), Integer(4), gf2=True, polybori=True)                               # needs sage.rings.polynomial.pbori
>>> sr                                                                            # needs sage.rings.polynomial.pbori
SR(2,1,2,4)

Sage Live

sr = mq.SR(2, 1, 2, 4, gf2=True, polybori=True)                               # needs sage.rings.polynomial.pbori
sr                                                                            # needs sage.rings.polynomial.pbori

We can construct a polynomial sequence for a random plaintext-ciphertext pair and study it:

Sage

sage: set_random_seed(1)
sage: while True:  # workaround (see :issue:`31891`)                                # needs sage.rings.polynomial.pbori
....:     try:
....:         F, s = sr.polynomial_system()
....:         break
....:     except ZeroDivisionError:
....:         pass
sage: F                                                                             # needs sage.rings.polynomial.pbori
Polynomial Sequence with 112 Polynomials in 64 Variables

sage: r2 = F.part(2); r2                                                            # needs sage.rings.polynomial.pbori
(w200 + k100 + x100 + x102 + x103,
 w201 + k101 + x100 + x101 + x103 + 1,
 w202 + k102 + x100 + x101 + x102 + 1,
 w203 + k103 + x101 + x102 + x103,
 w210 + k110 + x110 + x112 + x113,
 w211 + k111 + x110 + x111 + x113 + 1,
 w212 + k112 + x110 + x111 + x112 + 1,
 w213 + k113 + x111 + x112 + x113,
 x100*w100 + x100*w103 + x101*w102 + x102*w101 + x103*w100,
 x100*w100 + x100*w101 + x101*w100 + x101*w103 + x102*w102 + x103*w101,
 x100*w101 + x100*w102 + x101*w100 + x101*w101 + x102*w100 + x102*w103 + x103*w102,
 x100*w100 + x100*w102 + x100*w103 + x101*w100 + x101*w101 + x102*w102 + x103*w100 + x100,
 x100*w101 + x100*w103 + x101*w101 + x101*w102 + x102*w100 + x102*w103 + x103*w101 + x101,
 x100*w100 + x100*w102 + x101*w100 + x101*w102 + x101*w103 + x102*w100 + x102*w101 + x103*w102 + x102,
 x100*w101 + x100*w102 + x101*w100 + x101*w103 + x102*w101 + x103*w103 + x103,
 x100*w100 + x100*w101 + x100*w103 + x101*w101 + x102*w100 + x102*w102 + x103*w100 + w100,
 x100*w102 + x101*w100 + x101*w101 + x101*w103 + x102*w101 + x103*w100 + x103*w102 + w101,
 x100*w100 + x100*w101 + x100*w102 + x101*w102 + x102*w100 + x102*w101 + x102*w103 + x103*w101 + w102,
 x100*w101 + x101*w100 + x101*w102 + x102*w100 + x103*w101 + x103*w103 + w103,
 x100*w102 + x101*w101 + x102*w100 + x103*w103 + 1,
 x110*w110 + x110*w113 + x111*w112 + x112*w111 + x113*w110,
 x110*w110 + x110*w111 + x111*w110 + x111*w113 + x112*w112 + x113*w111,
 x110*w111 + x110*w112 + x111*w110 + x111*w111 + x112*w110 + x112*w113 + x113*w112,
 x110*w110 + x110*w112 + x110*w113 + x111*w110 + x111*w111 + x112*w112 + x113*w110 + x110,
 x110*w111 + x110*w113 + x111*w111 + x111*w112 + x112*w110 + x112*w113 + x113*w111 + x111,
 x110*w110 + x110*w112 + x111*w110 + x111*w112 + x111*w113 + x112*w110 + x112*w111 + x113*w112 + x112,
 x110*w111 + x110*w112 + x111*w110 + x111*w113 + x112*w111 + x113*w113 + x113,
 x110*w110 + x110*w111 + x110*w113 + x111*w111 + x112*w110 + x112*w112 + x113*w110 + w110,
 x110*w112 + x111*w110 + x111*w111 + x111*w113 + x112*w111 + x113*w110 + x113*w112 + w111,
 x110*w110 + x110*w111 + x110*w112 + x111*w112 + x112*w110 + x112*w111 + x112*w113 + x113*w111 + w112,
 x110*w111 + x111*w110 + x111*w112 + x112*w110 + x113*w111 + x113*w113 + w113,
 x110*w112 + x111*w111 + x112*w110 + x113*w113 + 1)

Python

>>> from sage.all import *
>>> set_random_seed(Integer(1))
>>> while True:  # workaround (see :issue:`31891`)                                # needs sage.rings.polynomial.pbori
...     try:
...         F, s = sr.polynomial_system()
...         break
...     except ZeroDivisionError:
...         pass
>>> F                                                                             # needs sage.rings.polynomial.pbori
Polynomial Sequence with 112 Polynomials in 64 Variables

>>> r2 = F.part(Integer(2)); r2                                                            # needs sage.rings.polynomial.pbori
(w200 + k100 + x100 + x102 + x103,
 w201 + k101 + x100 + x101 + x103 + 1,
 w202 + k102 + x100 + x101 + x102 + 1,
 w203 + k103 + x101 + x102 + x103,
 w210 + k110 + x110 + x112 + x113,
 w211 + k111 + x110 + x111 + x113 + 1,
 w212 + k112 + x110 + x111 + x112 + 1,
 w213 + k113 + x111 + x112 + x113,
 x100*w100 + x100*w103 + x101*w102 + x102*w101 + x103*w100,
 x100*w100 + x100*w101 + x101*w100 + x101*w103 + x102*w102 + x103*w101,
 x100*w101 + x100*w102 + x101*w100 + x101*w101 + x102*w100 + x102*w103 + x103*w102,
 x100*w100 + x100*w102 + x100*w103 + x101*w100 + x101*w101 + x102*w102 + x103*w100 + x100,
 x100*w101 + x100*w103 + x101*w101 + x101*w102 + x102*w100 + x102*w103 + x103*w101 + x101,
 x100*w100 + x100*w102 + x101*w100 + x101*w102 + x101*w103 + x102*w100 + x102*w101 + x103*w102 + x102,
 x100*w101 + x100*w102 + x101*w100 + x101*w103 + x102*w101 + x103*w103 + x103,
 x100*w100 + x100*w101 + x100*w103 + x101*w101 + x102*w100 + x102*w102 + x103*w100 + w100,
 x100*w102 + x101*w100 + x101*w101 + x101*w103 + x102*w101 + x103*w100 + x103*w102 + w101,
 x100*w100 + x100*w101 + x100*w102 + x101*w102 + x102*w100 + x102*w101 + x102*w103 + x103*w101 + w102,
 x100*w101 + x101*w100 + x101*w102 + x102*w100 + x103*w101 + x103*w103 + w103,
 x100*w102 + x101*w101 + x102*w100 + x103*w103 + 1,
 x110*w110 + x110*w113 + x111*w112 + x112*w111 + x113*w110,
 x110*w110 + x110*w111 + x111*w110 + x111*w113 + x112*w112 + x113*w111,
 x110*w111 + x110*w112 + x111*w110 + x111*w111 + x112*w110 + x112*w113 + x113*w112,
 x110*w110 + x110*w112 + x110*w113 + x111*w110 + x111*w111 + x112*w112 + x113*w110 + x110,
 x110*w111 + x110*w113 + x111*w111 + x111*w112 + x112*w110 + x112*w113 + x113*w111 + x111,
 x110*w110 + x110*w112 + x111*w110 + x111*w112 + x111*w113 + x112*w110 + x112*w111 + x113*w112 + x112,
 x110*w111 + x110*w112 + x111*w110 + x111*w113 + x112*w111 + x113*w113 + x113,
 x110*w110 + x110*w111 + x110*w113 + x111*w111 + x112*w110 + x112*w112 + x113*w110 + w110,
 x110*w112 + x111*w110 + x111*w111 + x111*w113 + x112*w111 + x113*w110 + x113*w112 + w111,
 x110*w110 + x110*w111 + x110*w112 + x111*w112 + x112*w110 + x112*w111 + x112*w113 + x113*w111 + w112,
 x110*w111 + x111*w110 + x111*w112 + x112*w110 + x113*w111 + x113*w113 + w113,
 x110*w112 + x111*w111 + x112*w110 + x113*w113 + 1)

Sage Live

set_random_seed(1)
while True:  # workaround (see :issue:`31891`)                                # needs sage.rings.polynomial.pbori
    try:
        F, s = sr.polynomial_system()
        break
    except ZeroDivisionError:
        pass
F                                                                             # needs sage.rings.polynomial.pbori
r2 = F.part(2); r2                                                            # needs sage.rings.polynomial.pbori

We separate the system in independent subsystems:

Sage

sage: C = Sequence(r2).connected_components(); C                                    # needs sage.rings.polynomial.pbori
[[w200 + k100 + x100 + x102 + x103,
  w201 + k101 + x100 + x101 + x103 + 1,
  w202 + k102 + x100 + x101 + x102 + 1,
  w203 + k103 + x101 + x102 + x103,
  x100*w100 + x100*w103 + x101*w102 + x102*w101 + x103*w100,
  x100*w100 + x100*w101 + x101*w100 + x101*w103 + x102*w102 + x103*w101,
  x100*w101 + x100*w102 + x101*w100 + x101*w101 + x102*w100 + x102*w103 + x103*w102,
  x100*w100 + x100*w102 + x100*w103 + x101*w100 + x101*w101 + x102*w102 + x103*w100 + x100,
  x100*w101 + x100*w103 + x101*w101 + x101*w102 + x102*w100 + x102*w103 + x103*w101 + x101,
  x100*w100 + x100*w102 + x101*w100 + x101*w102 + x101*w103 + x102*w100 + x102*w101 + x103*w102 + x102,
  x100*w101 + x100*w102 + x101*w100 + x101*w103 + x102*w101 + x103*w103 + x103,
  x100*w100 + x100*w101 + x100*w103 + x101*w101 + x102*w100 + x102*w102 + x103*w100 + w100,
  x100*w102 + x101*w100 + x101*w101 + x101*w103 + x102*w101 + x103*w100 + x103*w102 + w101,
  x100*w100 + x100*w101 + x100*w102 + x101*w102 + x102*w100 + x102*w101 + x102*w103 + x103*w101 + w102,
  x100*w101 + x101*w100 + x101*w102 + x102*w100 + x103*w101 + x103*w103 + w103,
  x100*w102 + x101*w101 + x102*w100 + x103*w103 + 1],
 [w210 + k110 + x110 + x112 + x113,
  w211 + k111 + x110 + x111 + x113 + 1,
  w212 + k112 + x110 + x111 + x112 + 1,
  w213 + k113 + x111 + x112 + x113,
  x110*w110 + x110*w113 + x111*w112 + x112*w111 + x113*w110,
  x110*w110 + x110*w111 + x111*w110 + x111*w113 + x112*w112 + x113*w111,
  x110*w111 + x110*w112 + x111*w110 + x111*w111 + x112*w110 + x112*w113 + x113*w112,
  x110*w110 + x110*w112 + x110*w113 + x111*w110 + x111*w111 + x112*w112 + x113*w110 + x110,
  x110*w111 + x110*w113 + x111*w111 + x111*w112 + x112*w110 + x112*w113 + x113*w111 + x111,
  x110*w110 + x110*w112 + x111*w110 + x111*w112 + x111*w113 + x112*w110 + x112*w111 + x113*w112 + x112,
  x110*w111 + x110*w112 + x111*w110 + x111*w113 + x112*w111 + x113*w113 + x113,
  x110*w110 + x110*w111 + x110*w113 + x111*w111 + x112*w110 + x112*w112 + x113*w110 + w110,
  x110*w112 + x111*w110 + x111*w111 + x111*w113 + x112*w111 + x113*w110 + x113*w112 + w111,
  x110*w110 + x110*w111 + x110*w112 + x111*w112 + x112*w110 + x112*w111 + x112*w113 + x113*w111 + w112,
  x110*w111 + x111*w110 + x111*w112 + x112*w110 + x113*w111 + x113*w113 + w113,
  x110*w112 + x111*w111 + x112*w110 + x113*w113 + 1]]
sage: C[0].groebner_basis()                                                         # needs sage.rings.polynomial.pbori
Polynomial Sequence with 30 Polynomials in 16 Variables

Python

>>> from sage.all import *
>>> C = Sequence(r2).connected_components(); C                                    # needs sage.rings.polynomial.pbori
[[w200 + k100 + x100 + x102 + x103,
  w201 + k101 + x100 + x101 + x103 + 1,
  w202 + k102 + x100 + x101 + x102 + 1,
  w203 + k103 + x101 + x102 + x103,
  x100*w100 + x100*w103 + x101*w102 + x102*w101 + x103*w100,
  x100*w100 + x100*w101 + x101*w100 + x101*w103 + x102*w102 + x103*w101,
  x100*w101 + x100*w102 + x101*w100 + x101*w101 + x102*w100 + x102*w103 + x103*w102,
  x100*w100 + x100*w102 + x100*w103 + x101*w100 + x101*w101 + x102*w102 + x103*w100 + x100,
  x100*w101 + x100*w103 + x101*w101 + x101*w102 + x102*w100 + x102*w103 + x103*w101 + x101,
  x100*w100 + x100*w102 + x101*w100 + x101*w102 + x101*w103 + x102*w100 + x102*w101 + x103*w102 + x102,
  x100*w101 + x100*w102 + x101*w100 + x101*w103 + x102*w101 + x103*w103 + x103,
  x100*w100 + x100*w101 + x100*w103 + x101*w101 + x102*w100 + x102*w102 + x103*w100 + w100,
  x100*w102 + x101*w100 + x101*w101 + x101*w103 + x102*w101 + x103*w100 + x103*w102 + w101,
  x100*w100 + x100*w101 + x100*w102 + x101*w102 + x102*w100 + x102*w101 + x102*w103 + x103*w101 + w102,
  x100*w101 + x101*w100 + x101*w102 + x102*w100 + x103*w101 + x103*w103 + w103,
  x100*w102 + x101*w101 + x102*w100 + x103*w103 + 1],
 [w210 + k110 + x110 + x112 + x113,
  w211 + k111 + x110 + x111 + x113 + 1,
  w212 + k112 + x110 + x111 + x112 + 1,
  w213 + k113 + x111 + x112 + x113,
  x110*w110 + x110*w113 + x111*w112 + x112*w111 + x113*w110,
  x110*w110 + x110*w111 + x111*w110 + x111*w113 + x112*w112 + x113*w111,
  x110*w111 + x110*w112 + x111*w110 + x111*w111 + x112*w110 + x112*w113 + x113*w112,
  x110*w110 + x110*w112 + x110*w113 + x111*w110 + x111*w111 + x112*w112 + x113*w110 + x110,
  x110*w111 + x110*w113 + x111*w111 + x111*w112 + x112*w110 + x112*w113 + x113*w111 + x111,
  x110*w110 + x110*w112 + x111*w110 + x111*w112 + x111*w113 + x112*w110 + x112*w111 + x113*w112 + x112,
  x110*w111 + x110*w112 + x111*w110 + x111*w113 + x112*w111 + x113*w113 + x113,
  x110*w110 + x110*w111 + x110*w113 + x111*w111 + x112*w110 + x112*w112 + x113*w110 + w110,
  x110*w112 + x111*w110 + x111*w111 + x111*w113 + x112*w111 + x113*w110 + x113*w112 + w111,
  x110*w110 + x110*w111 + x110*w112 + x111*w112 + x112*w110 + x112*w111 + x112*w113 + x113*w111 + w112,
  x110*w111 + x111*w110 + x111*w112 + x112*w110 + x113*w111 + x113*w113 + w113,
  x110*w112 + x111*w111 + x112*w110 + x113*w113 + 1]]
>>> C[Integer(0)].groebner_basis()                                                         # needs sage.rings.polynomial.pbori
Polynomial Sequence with 30 Polynomials in 16 Variables

Sage Live

C = Sequence(r2).connected_components(); C                                    # needs sage.rings.polynomial.pbori
C[0].groebner_basis()                                                         # needs sage.rings.polynomial.pbori

and compute the coefficient matrix:

Sage

sage: A,v = Sequence(r2).coefficients_monomials()                                   # needs sage.rings.polynomial.pbori
sage: A.rank()                                                                      # needs sage.rings.polynomial.pbori
32

Python

>>> from sage.all import *
>>> A,v = Sequence(r2).coefficients_monomials()                                   # needs sage.rings.polynomial.pbori
>>> A.rank()                                                                      # needs sage.rings.polynomial.pbori
32

Sage Live

A,v = Sequence(r2).coefficients_monomials()                                   # needs sage.rings.polynomial.pbori
A.rank()                                                                      # needs sage.rings.polynomial.pbori

Using these building blocks we can implement a simple XL algorithm easily:

Sage

sage: sr = mq.SR(1,1,1,4, gf2=True, polybori=True, order='lex')                     # needs sage.rings.polynomial.pbori
sage: while True:  # workaround (see :issue:`31891`)                                # needs sage.rings.polynomial.pbori
....:     try:
....:         F, s = sr.polynomial_system()
....:         break
....:     except ZeroDivisionError:
....:         pass

sage: # needs sage.rings.polynomial.pbori
sage: monomials = [a*b for a in F.variables() for b in F.variables() if a < b]
sage: len(monomials)
190
sage: F2 = Sequence(map(mul, cartesian_product_iterator((monomials, F))))
sage: A, v = F2.coefficients_monomials(sparse=False)
sage: A.echelonize()
sage: A
6840 x 4474 dense matrix over Finite Field of size 2...
sage: A.rank()
4056
sage: A[4055] * v
k001*k003

Python

>>> from sage.all import *
>>> sr = mq.SR(Integer(1),Integer(1),Integer(1),Integer(4), gf2=True, polybori=True, order='lex')                     # needs sage.rings.polynomial.pbori
>>> while True:  # workaround (see :issue:`31891`)                                # needs sage.rings.polynomial.pbori
...     try:
...         F, s = sr.polynomial_system()
...         break
...     except ZeroDivisionError:
...         pass

>>> # needs sage.rings.polynomial.pbori
>>> monomials = [a*b for a in F.variables() for b in F.variables() if a < b]
>>> len(monomials)
190
>>> F2 = Sequence(map(mul, cartesian_product_iterator((monomials, F))))
>>> A, v = F2.coefficients_monomials(sparse=False)
>>> A.echelonize()
>>> A
6840 x 4474 dense matrix over Finite Field of size 2...
>>> A.rank()
4056
>>> A[Integer(4055)] * v
k001*k003

Sage Live

sr = mq.SR(1,1,1,4, gf2=True, polybori=True, order='lex')                     # needs sage.rings.polynomial.pbori
while True:  # workaround (see :issue:`31891`)                                # needs sage.rings.polynomial.pbori
    try:
        F, s = sr.polynomial_system()
        break
    except ZeroDivisionError:
        pass
# needs sage.rings.polynomial.pbori
monomials = [a*b for a in F.variables() for b in F.variables() if a < b]
len(monomials)
F2 = Sequence(map(mul, cartesian_product_iterator((monomials, F))))
A, v = F2.coefficients_monomials(sparse=False)
A.echelonize()
A
A.rank()
A[4055] * v

Note

In many other computer algebra systems (cf. Singular) this class would be called Ideal but an ideal is a very distinct object from its generators and thus this is not an ideal in Sage.

Classes¶

sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence(arg1, arg2=None, immutable=False, cr=False, cr_str=None)[source]¶

Construct a new polynomial sequence object.

INPUT:

arg1 – a multivariate polynomial ring, an ideal or a matrix
arg2 – an iterable object of parts or polynomials (default: None)
- immutable – if True the sequence is immutable (default: False)
- cr, cr_str – see Sequence()

EXAMPLES:

Sage

sage: P.<a,b,c,d> = PolynomialRing(GF(127), 4)
sage: I = sage.rings.ideal.Katsura(P)                                           # needs sage.libs.singular

Python

>>> from sage.all import *
>>> P = PolynomialRing(GF(Integer(127)), Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = P._first_ngens(4)
>>> I = sage.rings.ideal.Katsura(P)                                           # needs sage.libs.singular

Sage Live

P.<a,b,c,d> = PolynomialRing(GF(127), 4)
I = sage.rings.ideal.Katsura(P)                                           # needs sage.libs.singular

If a list of tuples is provided, those form the parts:

Sage

sage: F = Sequence([I.gens(),I.gens()], I.ring()); F  # indirect doctest        # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c,
 a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
sage: F.nparts()                                                                # needs sage.libs.singular
2

Python

>>> from sage.all import *
>>> F = Sequence([I.gens(),I.gens()], I.ring()); F  # indirect doctest        # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c,
 a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
>>> F.nparts()                                                                # needs sage.libs.singular
2

Sage Live

F = Sequence([I.gens(),I.gens()], I.ring()); F  # indirect doctest        # needs sage.libs.singular
F.nparts()                                                                # needs sage.libs.singular

If an ideal is provided, the generators are used:

Sage

sage: Sequence(I)                                                               # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]

Python

>>> from sage.all import *
>>> Sequence(I)                                                               # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]

Sage Live

Sequence(I)                                                               # needs sage.libs.singular

If a list of polynomials is provided, the system has only one part:

Sage

sage: F = Sequence(I.gens(), I.ring()); F                                       # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
 sage: F.nparts()                                                               # needs sage.libs.singular
 1

Python

>>> from sage.all import *
>>> F = Sequence(I.gens(), I.ring()); F                                       # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
>>> F.nparts()                                                               # needs sage.libs.singular
 1

Sage Live

F = Sequence(I.gens(), I.ring()); F                                       # needs sage.libs.singular
F.nparts()                                                               # needs sage.libs.singular

We test that the ring is inferred correctly:

Sage

sage: P.<x,y,z> = GF(2)[]
sage: from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence
sage: PolynomialSequence([1,x,y]).ring()
Multivariate Polynomial Ring in x, y, z over Finite Field of size 2

sage: PolynomialSequence([[1,x,y], [0]]).ring()
Multivariate Polynomial Ring in x, y, z over Finite Field of size 2

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x, y, z']; (x, y, z,) = P._first_ngens(3)
>>> from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence
>>> PolynomialSequence([Integer(1),x,y]).ring()
Multivariate Polynomial Ring in x, y, z over Finite Field of size 2

>>> PolynomialSequence([[Integer(1),x,y], [Integer(0)]]).ring()
Multivariate Polynomial Ring in x, y, z over Finite Field of size 2

Sage Live

P.<x,y,z> = GF(2)[]
from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence
PolynomialSequence([1,x,y]).ring()
PolynomialSequence([[1,x,y], [0]]).ring()

class sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_generic(parts, ring, immutable=False, cr=False, cr_str=None)[source]¶

Bases: Sequence_generic

Construct a new system of multivariate polynomials.

INPUT:

parts – a list of lists with polynomials
ring – a multivariate polynomial ring
immutable – if True the sequence is immutable (default: False)
cr, cr_str – see Sequence()

EXAMPLES:

Sage

sage: P.<a,b,c,d> = PolynomialRing(GF(127), 4)
sage: I = sage.rings.ideal.Katsura(P)                                       # needs sage.libs.singular

sage: Sequence([I.gens()], I.ring())  # indirect doctest                    # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c]

Python

>>> from sage.all import *
>>> P = PolynomialRing(GF(Integer(127)), Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = P._first_ngens(4)
>>> I = sage.rings.ideal.Katsura(P)                                       # needs sage.libs.singular

>>> Sequence([I.gens()], I.ring())  # indirect doctest                    # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c]

Sage Live

P.<a,b,c,d> = PolynomialRing(GF(127), 4)
I = sage.rings.ideal.Katsura(P)                                       # needs sage.libs.singular
Sequence([I.gens()], I.ring())  # indirect doctest                    # needs sage.libs.singular

If an ideal is provided, the generators are used.:

Sage

sage: Sequence(I)                                                           # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c]

Python

>>> from sage.all import *
>>> Sequence(I)                                                           # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c]

Sage Live

Sequence(I)                                                           # needs sage.libs.singular

If a list of polynomials is provided, the system has only one part.:

Sage

sage: Sequence(I.gens(), I.ring())                                          # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c]

Python

>>> from sage.all import *
>>> Sequence(I.gens(), I.ring())                                          # needs sage.libs.singular
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c]

Sage Live

Sequence(I.gens(), I.ring())                                          # needs sage.libs.singular

algebraic_dependence()[source]¶

Return the ideal of annihilating polynomials for the polynomials in self, if those polynomials are algebraically dependent. Otherwise, return the zero ideal.

OUTPUT:

If the polynomials $f_{1}, \dots, f_{r}$ in self are algebraically dependent, then the output is the ideal ${F \in K [T_{1}, \dots, T_{r}] : F (f_{1}, \dots, f_{r}) = 0}$ of annihilating polynomials of $f_{1}, \dots, f_{r}$ . Here $K$ is the coefficient ring of polynomial ring of $f_{1}, \dots, f_{r}$ and $T_{1}, \dots, T_{r}$ are new indeterminates. If $f_{1}, \dots, f_{r}$ are algebraically independent, then the output is the zero ideal in $K [T_{1}, \dots, T_{r}]$ .

EXAMPLES:

Sage

sage: # needs sage.libs.singular
sage: R.<x,y> = PolynomialRing(QQ)
sage: S = Sequence([x, x*y])
sage: I = S.algebraic_dependence(); I
Ideal (0) of Multivariate Polynomial Ring in T0, T1 over Rational Field

Python

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> R = PolynomialRing(QQ, names=('x', 'y',)); (x, y,) = R._first_ngens(2)
>>> S = Sequence([x, x*y])
>>> I = S.algebraic_dependence(); I
Ideal (0) of Multivariate Polynomial Ring in T0, T1 over Rational Field

Sage Live

# needs sage.libs.singular
R.<x,y> = PolynomialRing(QQ)
S = Sequence([x, x*y])
I = S.algebraic_dependence(); I

Sage

sage: # needs sage.libs.singular
sage: R.<x,y> = PolynomialRing(QQ)
sage: S = Sequence([x, (x^2 + y^2 - 1)^2, x*y - 2])
sage: I = S.algebraic_dependence(); I
Ideal (16 + 32*T2 - 8*T0^2 + 24*T2^2 - 8*T0^2*T2 + 8*T2^3 + 9*T0^4 - 2*T0^2*T2^2
        + T2^4 - T0^4*T1 + 8*T0^4*T2 - 2*T0^6 + 2*T0^4*T2^2 + T0^8)
 of Multivariate Polynomial Ring in T0, T1, T2 over Rational Field
sage: [F(S) for F in I.gens()]
[0]

Python

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> R = PolynomialRing(QQ, names=('x', 'y',)); (x, y,) = R._first_ngens(2)
>>> S = Sequence([x, (x**Integer(2) + y**Integer(2) - Integer(1))**Integer(2), x*y - Integer(2)])
>>> I = S.algebraic_dependence(); I
Ideal (16 + 32*T2 - 8*T0^2 + 24*T2^2 - 8*T0^2*T2 + 8*T2^3 + 9*T0^4 - 2*T0^2*T2^2
        + T2^4 - T0^4*T1 + 8*T0^4*T2 - 2*T0^6 + 2*T0^4*T2^2 + T0^8)
 of Multivariate Polynomial Ring in T0, T1, T2 over Rational Field
>>> [F(S) for F in I.gens()]
[0]

Sage Live

# needs sage.libs.singular
R.<x,y> = PolynomialRing(QQ)
S = Sequence([x, (x^2 + y^2 - 1)^2, x*y - 2])
I = S.algebraic_dependence(); I
[F(S) for F in I.gens()]

Sage

sage: # needs sage.libs.singular
sage: R.<x,y> = PolynomialRing(GF(7))
sage: S = Sequence([x, (x^2 + y^2 - 1)^2, x*y - 2])
sage: I = S.algebraic_dependence(); I
Ideal (2 - 3*T2 - T0^2 + 3*T2^2 - T0^2*T2 + T2^3 + 2*T0^4 - 2*T0^2*T2^2
       + T2^4 - T0^4*T1 + T0^4*T2 - 2*T0^6 + 2*T0^4*T2^2 + T0^8)
 of Multivariate Polynomial Ring in T0, T1, T2 over Finite Field of size 7
sage: [F(S) for F in I.gens()]
[0]

Python

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> R = PolynomialRing(GF(Integer(7)), names=('x', 'y',)); (x, y,) = R._first_ngens(2)
>>> S = Sequence([x, (x**Integer(2) + y**Integer(2) - Integer(1))**Integer(2), x*y - Integer(2)])
>>> I = S.algebraic_dependence(); I
Ideal (2 - 3*T2 - T0^2 + 3*T2^2 - T0^2*T2 + T2^3 + 2*T0^4 - 2*T0^2*T2^2
       + T2^4 - T0^4*T1 + T0^4*T2 - 2*T0^6 + 2*T0^4*T2^2 + T0^8)
 of Multivariate Polynomial Ring in T0, T1, T2 over Finite Field of size 7
>>> [F(S) for F in I.gens()]
[0]

Sage Live

# needs sage.libs.singular
R.<x,y> = PolynomialRing(GF(7))
S = Sequence([x, (x^2 + y^2 - 1)^2, x*y - 2])
I = S.algebraic_dependence(); I
[F(S) for F in I.gens()]

Note

This function’s code also works for sequences of polynomials from a univariate polynomial ring, but i don’t know where in the Sage codebase to put it to use it to that effect.

AUTHORS:

Alex Raichev (2011-06-22)

coefficient_matrix(sparse=True)[source]¶

Return tuple (A,v) where A is the coefficient matrix of this system and v the matching monomial vector.

Thus value of A[i,j] corresponds the coefficient of the monomial v[j] in the i-th polynomial in this system.

Monomials are order w.r.t. the term ordering of self.ring() in reverse order, i.e. such that the smallest entry comes last.

INPUT:

sparse – construct a sparse matrix (default: True)

EXAMPLES:

Sage

sage: # needs sage.libs.singular
sage: P.<a,b,c,d> = PolynomialRing(GF(127), 4)
sage: I = sage.rings.ideal.Katsura(P)
sage: I.gens()
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
sage: F = Sequence(I)
sage: A,v = F.coefficient_matrix()
doctest:warning...
DeprecationWarning: the function coefficient_matrix is deprecated; use coefficients_monomials instead
See https://github.com/sagemath/sage/issues/37035 for details.
sage: A
[  0   0   0   0   0   0   0   0   0   1   2   2   2 126]
[  1   0   2   0   0   2   0   0   2 126   0   0   0   0]
[  0   2   0   0   2   0   0   2   0   0 126   0   0   0]
[  0   0   1   2   0   0   2   0   0   0   0 126   0   0]
sage: v
[a^2]
[a*b]
[b^2]
[a*c]
[b*c]
[c^2]
[b*d]
[c*d]
[d^2]
[  a]
[  b]
[  c]
[  d]
[  1]
sage: A*v
[        a + 2*b + 2*c + 2*d - 1]
[a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a]
[      2*a*b + 2*b*c + 2*c*d - b]
[        b^2 + 2*a*c + 2*b*d - c]

Python

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> P = PolynomialRing(GF(Integer(127)), Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = P._first_ngens(4)
>>> I = sage.rings.ideal.Katsura(P)
>>> I.gens()
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
>>> F = Sequence(I)
>>> A,v = F.coefficient_matrix()
doctest:warning...
DeprecationWarning: the function coefficient_matrix is deprecated; use coefficients_monomials instead
See https://github.com/sagemath/sage/issues/37035 for details.
>>> A
[  0   0   0   0   0   0   0   0   0   1   2   2   2 126]
[  1   0   2   0   0   2   0   0   2 126   0   0   0   0]
[  0   2   0   0   2   0   0   2   0   0 126   0   0   0]
[  0   0   1   2   0   0   2   0   0   0   0 126   0   0]
>>> v
[a^2]
[a*b]
[b^2]
[a*c]
[b*c]
[c^2]
[b*d]
[c*d]
[d^2]
[  a]
[  b]
[  c]
[  d]
[  1]
>>> A*v
[        a + 2*b + 2*c + 2*d - 1]
[a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a]
[      2*a*b + 2*b*c + 2*c*d - b]
[        b^2 + 2*a*c + 2*b*d - c]

Sage Live

# needs sage.libs.singular
P.<a,b,c,d> = PolynomialRing(GF(127), 4)
I = sage.rings.ideal.Katsura(P)
I.gens()
F = Sequence(I)
A,v = F.coefficient_matrix()
A
v
A*v

coefficients_monomials(order=None, sparse=True)[source]¶

Return the matrix of coefficients A and the matching vector of monomials v, such that A*v == vector(self).

Thus value of A[i,j] corresponds the coefficient of the monomial v[j] in the i-th polynomial in this system.

Monomials are ordered w.r.t. the term ordering of order if given; otherwise, they are ordered w.r.t. self.ring() in reverse order, i.e., such that the smallest entry comes last.

INPUT:

sparse – construct a sparse matrix (default: True)
order – list or tuple specifying the order of monomials (default: None)

EXAMPLES:

Sage

sage: # needs sage.libs.singular
sage: P.<a,b,c,d> = PolynomialRing(GF(127), 4)
sage: I = sage.rings.ideal.Katsura(P)
sage: I.gens()
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
sage: F = Sequence(I)
sage: A,v = F.coefficients_monomials()
sage: A
[  0   0   0   0   0   0   0   0   0   1   2   2   2 126]
[  1   0   2   0   0   2   0   0   2 126   0   0   0   0]
[  0   2   0   0   2   0   0   2   0   0 126   0   0   0]
[  0   0   1   2   0   0   2   0   0   0   0 126   0   0]
sage: v
(a^2, a*b, b^2, a*c, b*c, c^2, b*d, c*d, d^2, a, b, c, d, 1)
sage: A*v
(a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c)

Python

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> P = PolynomialRing(GF(Integer(127)), Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = P._first_ngens(4)
>>> I = sage.rings.ideal.Katsura(P)
>>> I.gens()
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
>>> F = Sequence(I)
>>> A,v = F.coefficients_monomials()
>>> A
[  0   0   0   0   0   0   0   0   0   1   2   2   2 126]
[  1   0   2   0   0   2   0   0   2 126   0   0   0   0]
[  0   2   0   0   2   0   0   2   0   0 126   0   0   0]
[  0   0   1   2   0   0   2   0   0   0   0 126   0   0]
>>> v
(a^2, a*b, b^2, a*c, b*c, c^2, b*d, c*d, d^2, a, b, c, d, 1)
>>> A*v
(a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c)

Sage Live

# needs sage.libs.singular
P.<a,b,c,d> = PolynomialRing(GF(127), 4)
I = sage.rings.ideal.Katsura(P)
I.gens()
F = Sequence(I)
A,v = F.coefficients_monomials()
A
v
A*v

connected_components()[source]¶

Split the polynomial system in systems which do not share any variables.

EXAMPLES:

As an example consider one part of AES, which naturally splits into four subsystems which are independent:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: sr = mq.SR(2, 4, 4, 8, gf2=True, polybori=True)
sage: while True:  # workaround (see :issue:`31891`)
....:     try:
....:         F, s = sr.polynomial_system()
....:         break
....:     except ZeroDivisionError:
....:         pass
sage: Fz = Sequence(F.part(2))
sage: Fz.connected_components()
[Polynomial Sequence with 128 Polynomials in 128 Variables,
 Polynomial Sequence with 128 Polynomials in 128 Variables,
 Polynomial Sequence with 128 Polynomials in 128 Variables,
 Polynomial Sequence with 128 Polynomials in 128 Variables]

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> sr = mq.SR(Integer(2), Integer(4), Integer(4), Integer(8), gf2=True, polybori=True)
>>> while True:  # workaround (see :issue:`31891`)
...     try:
...         F, s = sr.polynomial_system()
...         break
...     except ZeroDivisionError:
...         pass
>>> Fz = Sequence(F.part(Integer(2)))
>>> Fz.connected_components()
[Polynomial Sequence with 128 Polynomials in 128 Variables,
 Polynomial Sequence with 128 Polynomials in 128 Variables,
 Polynomial Sequence with 128 Polynomials in 128 Variables,
 Polynomial Sequence with 128 Polynomials in 128 Variables]

Sage Live

# needs sage.rings.polynomial.pbori
sr = mq.SR(2, 4, 4, 8, gf2=True, polybori=True)
while True:  # workaround (see :issue:`31891`)
    try:
        F, s = sr.polynomial_system()
        break
    except ZeroDivisionError:
        pass
Fz = Sequence(F.part(2))
Fz.connected_components()

connection_graph()[source]¶

Return the graph which has the variables of this system as vertices and edges between two variables if they appear in the same polynomial.

EXAMPLES:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: B.<x,y,z> = BooleanPolynomialRing()
sage: F = Sequence([x*y + y + 1, z + 1])
sage: G = F.connection_graph(); G
Graph on 3 vertices
sage: G.is_connected()
False
sage: F = Sequence([x])
sage: F.connection_graph()
Graph on 1 vertex

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> B = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> F = Sequence([x*y + y + Integer(1), z + Integer(1)])
>>> G = F.connection_graph(); G
Graph on 3 vertices
>>> G.is_connected()
False
>>> F = Sequence([x])
>>> F.connection_graph()
Graph on 1 vertex

Sage Live

# needs sage.rings.polynomial.pbori
B.<x,y,z> = BooleanPolynomialRing()
F = Sequence([x*y + y + 1, z + 1])
G = F.connection_graph(); G
G.is_connected()
F = Sequence([x])
F.connection_graph()

groebner_basis(*args, **kwargs)[source]¶

Compute and return a Groebner basis for the ideal spanned by the polynomials in this system.

INPUT:

args – list of arguments passed to MPolynomialIdeal.groebner_basis call
kwargs – dictionary of arguments passed to MPolynomialIdeal.groebner_basis call

EXAMPLES:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: sr = mq.SR(allow_zero_inversions=True)
sage: F, s = sr.polynomial_system()
sage: gb = F.groebner_basis()
sage: Ideal(gb).basis_is_groebner()
True

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> sr = mq.SR(allow_zero_inversions=True)
>>> F, s = sr.polynomial_system()
>>> gb = F.groebner_basis()
>>> Ideal(gb).basis_is_groebner()
True

Sage Live

# needs sage.rings.polynomial.pbori
sr = mq.SR(allow_zero_inversions=True)
F, s = sr.polynomial_system()
gb = F.groebner_basis()
Ideal(gb).basis_is_groebner()

ideal()[source]¶

Return ideal spanned by the elements of this system.

EXAMPLES:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: sr = mq.SR(allow_zero_inversions=True)
sage: F, s = sr.polynomial_system()
sage: P = F.ring()
sage: I = F.ideal()
sage: J = I.elimination_ideal(P.gens()[4:-4])
sage: J <= I
True
sage: set(J.gens().variables()).issubset(P.gens()[:4] + P.gens()[-4:])
True

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> sr = mq.SR(allow_zero_inversions=True)
>>> F, s = sr.polynomial_system()
>>> P = F.ring()
>>> I = F.ideal()
>>> J = I.elimination_ideal(P.gens()[Integer(4):-Integer(4)])
>>> J <= I
True
>>> set(J.gens().variables()).issubset(P.gens()[:Integer(4)] + P.gens()[-Integer(4):])
True

Sage Live

# needs sage.rings.polynomial.pbori
sr = mq.SR(allow_zero_inversions=True)
F, s = sr.polynomial_system()
P = F.ring()
I = F.ideal()
J = I.elimination_ideal(P.gens()[4:-4])
J <= I
set(J.gens().variables()).issubset(P.gens()[:4] + P.gens()[-4:])

is_groebner(singular=Singular)[source]¶

Return True if the generators of this ideal (self.gens()) form a Groebner basis.

Let $I$ be the set of generators of this ideal. The check is performed by trying to lift $S y z (L M (I))$ to $S y z (I)$ as $I$ forms a Groebner basis if and only if for every element $S$ in $S y z (L M (I))$ :

S ⋆ G = \sum_{i = 0}^{m} h_{i} g_{i} ⟶_{G} 0.

EXAMPLES:

Sage

sage: # needs sage.libs.singular
sage: R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127), 10)
sage: I = sage.rings.ideal.Cyclic(R, 4)
sage: I.basis.is_groebner()
False
sage: I2 = Ideal(I.groebner_basis())
sage: I2.basis.is_groebner()
True

Python

>>> from sage.all import *
>>> # needs sage.libs.singular
>>> R = PolynomialRing(GF(Integer(127)), Integer(10), names=('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',)); (a, b, c, d, e, f, g, h, i, j,) = R._first_ngens(10)
>>> I = sage.rings.ideal.Cyclic(R, Integer(4))
>>> I.basis.is_groebner()
False
>>> I2 = Ideal(I.groebner_basis())
>>> I2.basis.is_groebner()
True

Sage Live

# needs sage.libs.singular
R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127), 10)
I = sage.rings.ideal.Cyclic(R, 4)
I.basis.is_groebner()
I2 = Ideal(I.groebner_basis())
I2.basis.is_groebner()

macaulay_matrix(degree, homogeneous=False, variables=None, return_indices=False, remove_zero=False, reverse_column_order=False, row_order=None)[source]¶

Return the Macaulay matrix of degree degree for this sequence of polynomials.

INPUT:

homogeneous – boolean (default: False); when False, the polynomials in the sequence do not need to be homogeneous the rows of the Macaulay matrix correspond to all possible products between a polynomial from the sequence and monomials of the polynomial ring up to degree degree; when True, all polynomials in the sequence must be homogeneous, and the rows of the Macaulay matrix then represent all possible products between a polynomial in the sequence and a monomial of the polynomial ring such that the resulting product is homogeneous of degree degree + d_max, where d_max is the maximum degree among the input polynomials
variables – list (default: None); when None, variables is interpreted as being the list of all variables of the ring of the polynomials in the sequence; otherwise variables is a list describing a subset of these variables, and only these variables are used (instead of all ring variables) when forming monomials to multiply the polynomials of the sequence
return_indices – boolean (default: False); when False, only return the Macaulay matrix; when True, return the Macaulay matrix and two lists: the first one is a list of pairs, each of them containing a monomial and the index in the sequence of the input polynomial, whose product describes the corresponding row of the matrix; the second one is the list of monomials corresponding to the columns of the matrix
remove_zero – boolean (default: False); when False, all monomials of the polynomial ring up to degree degree``are included as columns in the Macaulay matrix; when ``True, only the monomials that actually appear in the polynomial sequence are included
reverse_column_order – boolean (default: False); when False, by default, the order of the columns is the same as the order of the polynomial ring; when True, the order of the columns is the reverse of the order of the polynomial ring
row_order – str (default: None); determines the ordering of the rows in the matrix; when None (or "POT"), a position over term (POT) order is used: rows are first ordered by the index of the corresponding polynomial in the sequence, and then by the (multiplicative) monomials; when set to "TOP", the rows follow a term over position (TOP) order: rows are first ordered by the (multiplicative) monomials and then by the index of the corresponding polynomial in the sequence

EXAMPLES:

Sage

sage: R.<x,y,z> = PolynomialRing(GF(7), order='deglex')
sage: L = Sequence([2*x*z - y*z + 2*z^2 + 3*x - 1,
....:               2*x^2 - 3*y*z + z^2 - 3*y + 3,
....:               -x^2 - 2*x*z - 3*y*z + 3*x])
sage: L.macaulay_matrix(0)
[0 0 2 0 6 2 3 0 0 6]
[2 0 0 0 4 1 0 4 0 3]
[6 0 5 0 4 0 3 0 0 0]

Python

>>> from sage.all import *
>>> R = PolynomialRing(GF(Integer(7)), order='deglex', names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> L = Sequence([Integer(2)*x*z - y*z + Integer(2)*z**Integer(2) + Integer(3)*x - Integer(1),
...               Integer(2)*x**Integer(2) - Integer(3)*y*z + z**Integer(2) - Integer(3)*y + Integer(3),
...               -x**Integer(2) - Integer(2)*x*z - Integer(3)*y*z + Integer(3)*x])
>>> L.macaulay_matrix(Integer(0))
[0 0 2 0 6 2 3 0 0 6]
[2 0 0 0 4 1 0 4 0 3]
[6 0 5 0 4 0 3 0 0 0]

Sage Live

R.<x,y,z> = PolynomialRing(GF(7), order='deglex')
L = Sequence([2*x*z - y*z + 2*z^2 + 3*x - 1,
              2*x^2 - 3*y*z + z^2 - 3*y + 3,
              -x^2 - 2*x*z - 3*y*z + 3*x])
L.macaulay_matrix(0)

Example with a sequence of homogeneous polynomials:

Sage

sage: R.<x,y,z> = PolynomialRing(QQ)
sage: L = Sequence([x*y^2 + y^3 + x*y*z + y*z^2,
....:               x^2*y + x*y^2 + x*y*z + 3*x*z^2 + z^3,
....:               x^3 + 2*y^3 + x^2*z + 2*x*y*z + 2*z^3])
sage: L.macaulay_matrix(1, homogeneous=True)
[0 0 0 0 0 0 0 1 1 0 1 0 0 1 0]
[0 0 0 1 1 0 0 1 0 0 0 1 0 0 0]
[0 0 1 1 0 0 1 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 1 0 0 1 0 3 0 1]
[0 0 1 1 0 0 0 1 0 0 3 0 0 1 0]
[0 1 1 0 0 0 1 0 0 3 0 0 1 0 0]
[0 0 0 0 0 1 0 0 2 1 2 0 0 0 2]
[0 1 0 0 2 0 1 2 0 0 0 0 0 2 0]
[1 0 0 2 0 1 2 0 0 0 0 0 2 0 0]

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> L = Sequence([x*y**Integer(2) + y**Integer(3) + x*y*z + y*z**Integer(2),
...               x**Integer(2)*y + x*y**Integer(2) + x*y*z + Integer(3)*x*z**Integer(2) + z**Integer(3),
...               x**Integer(3) + Integer(2)*y**Integer(3) + x**Integer(2)*z + Integer(2)*x*y*z + Integer(2)*z**Integer(3)])
>>> L.macaulay_matrix(Integer(1), homogeneous=True)
[0 0 0 0 0 0 0 1 1 0 1 0 0 1 0]
[0 0 0 1 1 0 0 1 0 0 0 1 0 0 0]
[0 0 1 1 0 0 1 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 1 0 0 1 0 3 0 1]
[0 0 1 1 0 0 0 1 0 0 3 0 0 1 0]
[0 1 1 0 0 0 1 0 0 3 0 0 1 0 0]
[0 0 0 0 0 1 0 0 2 1 2 0 0 0 2]
[0 1 0 0 2 0 1 2 0 0 0 0 0 2 0]
[1 0 0 2 0 1 2 0 0 0 0 0 2 0 0]

Sage Live

R.<x,y,z> = PolynomialRing(QQ)
L = Sequence([x*y^2 + y^3 + x*y*z + y*z^2,
              x^2*y + x*y^2 + x*y*z + 3*x*z^2 + z^3,
              x^3 + 2*y^3 + x^2*z + 2*x*y*z + 2*z^3])
L.macaulay_matrix(1, homogeneous=True)

Same example for which we now ask to remove monomials that do not appear in the sequence (remove_zero=True), and to return the row and column indices:

Sage

sage: R.<x,y,z> = PolynomialRing(QQ)
sage: L = Sequence([x*y + 2*z^2, y^2 + y*z, x*z])
sage: L.macaulay_matrix(1, homogeneous=True, remove_zero=True, return_indices=True)
(
[0 0 0 0 1 0 0 0 2]
[0 1 0 0 0 0 0 2 0]
[1 0 0 0 0 0 2 0 0]
[0 0 0 0 0 1 0 1 0]
[0 0 1 0 0 1 0 0 0]
[0 1 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 0 0]
[0 0 0 0 1 0 0 0 0]
[0 0 0 1 0 0 0 0 0],
[(z, 0), (y, 0), (x, 0), (z, 1), (y, 1), (x, 1), (z, 2), (y, 2), (x, 2)],
[x^2*y, x*y^2, y^3, x^2*z, x*y*z, y^2*z, x*z^2, y*z^2, z^3]
)

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> L = Sequence([x*y + Integer(2)*z**Integer(2), y**Integer(2) + y*z, x*z])
>>> L.macaulay_matrix(Integer(1), homogeneous=True, remove_zero=True, return_indices=True)
(
[0 0 0 0 1 0 0 0 2]
[0 1 0 0 0 0 0 2 0]
[1 0 0 0 0 0 2 0 0]
[0 0 0 0 0 1 0 1 0]
[0 0 1 0 0 1 0 0 0]
[0 1 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 0 0]
[0 0 0 0 1 0 0 0 0]
[0 0 0 1 0 0 0 0 0],
[(z, 0), (y, 0), (x, 0), (z, 1), (y, 1), (x, 1), (z, 2), (y, 2), (x, 2)],
[x^2*y, x*y^2, y^3, x^2*z, x*y*z, y^2*z, x*z^2, y*z^2, z^3]
)

Sage Live

R.<x,y,z> = PolynomialRing(QQ)
L = Sequence([x*y + 2*z^2, y^2 + y*z, x*z])
L.macaulay_matrix(1, homogeneous=True, remove_zero=True, return_indices=True)

Example in which we build rows using monomials that involve only a subset of the ring variables (variables=['x']):

Sage

sage: R.<x,y,z> = PolynomialRing(QQ)
sage: L = Sequence([2*y*z - 2*z^2 - 3*x + z - 3,
....:               -3*y^2 + 3*y*z + 2*z^2 - 2*x - 2*y,
....:               -2*y - z - 3])
sage: L.macaulay_matrix(1, variables=['x'], remove_zero=True, return_indices=True)
(
[ 0  0  0  0  0  0  0  0  0  2 -2 -3  0  1 -3]
[ 0  0  0  2 -2 -3  0  0  1  0  0 -3  0  0  0]
[ 0  0  0  0  0  0  0 -3  0  3  2 -2 -2  0  0]
[ 0 -3  0  3  2 -2 -2  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0 -2 -1 -3]
[ 0  0  0  0  0  0 -2  0 -1  0  0 -3  0  0  0]
[-2  0 -1  0  0 -3  0  0  0  0  0  0  0  0  0],
[(1, 0), (x, 0), (1, 1), (x, 1), (1, 2), (x, 2), (x^2, 2)],
[x^2*y, x*y^2, x^2*z, x*y*z, x*z^2, x^2, x*y, y^2, x*z, y*z, z^2, x, y, z, 1]
)

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> L = Sequence([Integer(2)*y*z - Integer(2)*z**Integer(2) - Integer(3)*x + z - Integer(3),
...               -Integer(3)*y**Integer(2) + Integer(3)*y*z + Integer(2)*z**Integer(2) - Integer(2)*x - Integer(2)*y,
...               -Integer(2)*y - z - Integer(3)])
>>> L.macaulay_matrix(Integer(1), variables=['x'], remove_zero=True, return_indices=True)
(
[ 0  0  0  0  0  0  0  0  0  2 -2 -3  0  1 -3]
[ 0  0  0  2 -2 -3  0  0  1  0  0 -3  0  0  0]
[ 0  0  0  0  0  0  0 -3  0  3  2 -2 -2  0  0]
[ 0 -3  0  3  2 -2 -2  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0 -2 -1 -3]
[ 0  0  0  0  0  0 -2  0 -1  0  0 -3  0  0  0]
[-2  0 -1  0  0 -3  0  0  0  0  0  0  0  0  0],
[(1, 0), (x, 0), (1, 1), (x, 1), (1, 2), (x, 2), (x^2, 2)],
[x^2*y, x*y^2, x^2*z, x*y*z, x*z^2, x^2, x*y, y^2, x*z, y*z, z^2, x, y, z, 1]
)

Sage Live

R.<x,y,z> = PolynomialRing(QQ)
L = Sequence([2*y*z - 2*z^2 - 3*x + z - 3,
              -3*y^2 + 3*y*z + 2*z^2 - 2*x - 2*y,
              -2*y - z - 3])
L.macaulay_matrix(1, variables=['x'], remove_zero=True, return_indices=True)

REFERENCES:

[Mac1902], Chapter 1 of [Mac1916]

maximal_degree()[source]¶

Return the maximal degree of any polynomial in this sequence.

EXAMPLES:

Sage

sage: P.<x,y,z> = PolynomialRing(GF(7))
sage: F = Sequence([x*y + x, x])
sage: F.maximal_degree()
2
sage: P.<x,y,z> = PolynomialRing(GF(7))
sage: F = Sequence([], universe=P)
sage: F.maximal_degree()
-1

Python

>>> from sage.all import *
>>> P = PolynomialRing(GF(Integer(7)), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> F = Sequence([x*y + x, x])
>>> F.maximal_degree()
2
>>> P = PolynomialRing(GF(Integer(7)), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> F = Sequence([], universe=P)
>>> F.maximal_degree()
-1

Sage Live

P.<x,y,z> = PolynomialRing(GF(7))
F = Sequence([x*y + x, x])
F.maximal_degree()
P.<x,y,z> = PolynomialRing(GF(7))
F = Sequence([], universe=P)
F.maximal_degree()

minimal_degree()[source]¶

Return the minimal degree of any polynomial in this sequence.

EXAMPLES:

Sage

sage: P.<x,y,z> = PolynomialRing(GF(7))
sage: F = Sequence([x*y + x, x])
sage: F.minimal_degree()
1
sage: P.<x,y,z> = PolynomialRing(GF(7))
sage: F = Sequence([], universe=P)
sage: F.minimal_degree()
-1

Python

>>> from sage.all import *
>>> P = PolynomialRing(GF(Integer(7)), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> F = Sequence([x*y + x, x])
>>> F.minimal_degree()
1
>>> P = PolynomialRing(GF(Integer(7)), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> F = Sequence([], universe=P)
>>> F.minimal_degree()
-1

Sage Live

P.<x,y,z> = PolynomialRing(GF(7))
F = Sequence([x*y + x, x])
F.minimal_degree()
P.<x,y,z> = PolynomialRing(GF(7))
F = Sequence([], universe=P)
F.minimal_degree()

monomials()[source]¶

Return an unordered tuple of monomials in this polynomial system.

EXAMPLES:

Sage

sage: sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
sage: F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
sage: len(F.monomials())                                                    # needs sage.rings.polynomial.pbori
49

Python

>>> from sage.all import *
>>> sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
>>> F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
>>> len(F.monomials())                                                    # needs sage.rings.polynomial.pbori
49

Sage Live

sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
len(F.monomials())                                                    # needs sage.rings.polynomial.pbori

nmonomials()[source]¶

Return the number of monomials present in this system.

EXAMPLES:

Sage

sage: sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
sage: F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
sage: F.nmonomials()                                                        # needs sage.rings.polynomial.pbori
49

Python

>>> from sage.all import *
>>> sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
>>> F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
>>> F.nmonomials()                                                        # needs sage.rings.polynomial.pbori
49

Sage Live

sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
F.nmonomials()                                                        # needs sage.rings.polynomial.pbori

nparts()[source]¶

Return number of parts of this system.

EXAMPLES:

Sage

sage: sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
sage: F, s = sr.polynomial_system()                                         # needs sage.rings.polynomial.pbori
sage: F.nparts()                                                            # needs sage.rings.polynomial.pbori
4

Python

>>> from sage.all import *
>>> sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
>>> F, s = sr.polynomial_system()                                         # needs sage.rings.polynomial.pbori
>>> F.nparts()                                                            # needs sage.rings.polynomial.pbori
4

Sage Live

sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
F, s = sr.polynomial_system()                                         # needs sage.rings.polynomial.pbori
F.nparts()                                                            # needs sage.rings.polynomial.pbori

nvariables()[source]¶

Return number of variables present in this system.

EXAMPLES:

Sage

sage: sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
sage: F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
sage: F.nvariables()                                                        # needs sage.rings.polynomial.pbori
20

Python

>>> from sage.all import *
>>> sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
>>> F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
>>> F.nvariables()                                                        # needs sage.rings.polynomial.pbori
20

Sage Live

sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
F.nvariables()                                                        # needs sage.rings.polynomial.pbori

part(i)[source]¶

Return i-th part of this system.

EXAMPLES:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: sr = mq.SR(allow_zero_inversions=True)
sage: F, s = sr.polynomial_system()
sage: R0 = F.part(1)
sage: R0
(k000^2 + k001, k001^2 + k002, k002^2 + k003, k003^2 + k000)

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> sr = mq.SR(allow_zero_inversions=True)
>>> F, s = sr.polynomial_system()
>>> R0 = F.part(Integer(1))
>>> R0
(k000^2 + k001, k001^2 + k002, k002^2 + k003, k003^2 + k000)

Sage Live

# needs sage.rings.polynomial.pbori
sr = mq.SR(allow_zero_inversions=True)
F, s = sr.polynomial_system()
R0 = F.part(1)
R0

parts()[source]¶

Return a tuple of parts of this system.

EXAMPLES:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: sr = mq.SR(allow_zero_inversions=True)
sage: F, s = sr.polynomial_system()
sage: l = F.parts()
sage: len(l)
4

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> sr = mq.SR(allow_zero_inversions=True)
>>> F, s = sr.polynomial_system()
>>> l = F.parts()
>>> len(l)
4

Sage Live

# needs sage.rings.polynomial.pbori
sr = mq.SR(allow_zero_inversions=True)
F, s = sr.polynomial_system()
l = F.parts()
len(l)

reduced()[source]¶

If this sequence is $(f_{1}, . . ., f_{n})$ then this method returns $(g_{1}, . . ., g_{s})$ such that:

$(f_{1}, . . ., f_{n}) = (g_{1}, . . ., g_{s})$
$L T (g_{i}) \neq L T (g_{j})$ for all $i \neq j$
$L T (g_{i})$ does not divide $m$ for all monomials $m$ of ${g_{1}, . . ., g_{i - 1}, g_{i + 1}, . . ., g_{s}}$
$L C (g_{i}) = 1$ for all $i$ if the coefficient ring is a field.

EXAMPLES:

Sage

sage: R.<x,y,z> = PolynomialRing(QQ)
sage: F = Sequence([z*x+y^3,z+y^3,z+x*y])
sage: F.reduced()
[y^3 + z, x*y + z, x*z - z]

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> F = Sequence([z*x+y**Integer(3),z+y**Integer(3),z+x*y])
>>> F.reduced()
[y^3 + z, x*y + z, x*z - z]

Sage Live

R.<x,y,z> = PolynomialRing(QQ)
F = Sequence([z*x+y^3,z+y^3,z+x*y])
F.reduced()

Note that tail reduction for local orderings is not well-defined:

Sage

sage: R.<x,y,z> = PolynomialRing(QQ,order='negdegrevlex')
sage: F = Sequence([z*x+y^3,z+y^3,z+x*y])
sage: F.reduced()
[z + x*y, x*y - y^3, x^2*y - y^3]

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ,order='negdegrevlex', names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> F = Sequence([z*x+y**Integer(3),z+y**Integer(3),z+x*y])
>>> F.reduced()
[z + x*y, x*y - y^3, x^2*y - y^3]

Sage Live

R.<x,y,z> = PolynomialRing(QQ,order='negdegrevlex')
F = Sequence([z*x+y^3,z+y^3,z+x*y])
F.reduced()

A fixed error with nonstandard base fields:

Sage

sage: R.<t>=QQ['t']
sage: K.<x,y>=R.fraction_field()['x,y']
sage: I=t*x*K
sage: I.basis.reduced()
[x]

Python

>>> from sage.all import *
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> K = R.fraction_field()['x,y']; (x, y,) = K._first_ngens(2)
>>> I=t*x*K
>>> I.basis.reduced()
[x]

Sage Live

R.<t>=QQ['t']
K.<x,y>=R.fraction_field()['x,y']
I=t*x*K
I.basis.reduced()

The interreduced basis of 0 is 0:

Sage

sage: P.<x,y,z> = GF(2)[]
sage: Sequence([P(0)]).reduced()
[0]

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x, y, z']; (x, y, z,) = P._first_ngens(3)
>>> Sequence([P(Integer(0))]).reduced()
[0]

Sage Live

P.<x,y,z> = GF(2)[]
Sequence([P(0)]).reduced()

Leading coefficients are reduced to 1:

Sage

sage: P.<x,y> = QQ[]
sage: Sequence([2*x,y]).reduced()
[x, y]

sage: P.<x,y> = CC[]                                                        # needs sage.rings.real_mpfr
sage: Sequence([2*x,y]).reduced()
[x, y]

Python

>>> from sage.all import *
>>> P = QQ['x, y']; (x, y,) = P._first_ngens(2)
>>> Sequence([Integer(2)*x,y]).reduced()
[x, y]

>>> P = CC['x, y']; (x, y,) = P._first_ngens(2)# needs sage.rings.real_mpfr
>>> Sequence([Integer(2)*x,y]).reduced()
[x, y]

Sage Live

P.<x,y> = QQ[]
Sequence([2*x,y]).reduced()
P.<x,y> = CC[]                                                        # needs sage.rings.real_mpfr
Sequence([2*x,y]).reduced()

ALGORITHM:

Uses Singular’s interred command or sage.rings.polynomial.toy_buchberger.inter_reduction() if conversion to Singular fails.

ring()[source]¶

Return the polynomial ring all elements live in.

EXAMPLES:

Sage

sage: sr = mq.SR(allow_zero_inversions=True, gf2=True, order='block')       # needs sage.rings.polynomial.pbori
sage: F, s = sr.polynomial_system()                                         # needs sage.rings.polynomial.pbori
sage: print(F.ring().repr_long())                                           # needs sage.rings.polynomial.pbori
Polynomial Ring
 Base Ring : Finite Field of size 2
      Size : 20 Variables
  Block  0 : Ordering : deglex
             Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
  Block  1 : Ordering : deglex
             Names    : k000, k001, k002, k003

Python

>>> from sage.all import *
>>> sr = mq.SR(allow_zero_inversions=True, gf2=True, order='block')       # needs sage.rings.polynomial.pbori
>>> F, s = sr.polynomial_system()                                         # needs sage.rings.polynomial.pbori
>>> print(F.ring().repr_long())                                           # needs sage.rings.polynomial.pbori
Polynomial Ring
 Base Ring : Finite Field of size 2
      Size : 20 Variables
  Block  0 : Ordering : deglex
             Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
  Block  1 : Ordering : deglex
             Names    : k000, k001, k002, k003

Sage Live

sr = mq.SR(allow_zero_inversions=True, gf2=True, order='block')       # needs sage.rings.polynomial.pbori
F, s = sr.polynomial_system()                                         # needs sage.rings.polynomial.pbori
print(F.ring().repr_long())                                           # needs sage.rings.polynomial.pbori

subs(*args, **kwargs)[source]¶

Substitute variables for every polynomial in this system and return a new system. See MPolynomial.subs() for calling convention.

INPUT:

args – arguments to be passed to MPolynomial.subs()
kwargs – keyword arguments to be passed to MPolynomial.subs()

EXAMPLES:

Sage

sage: sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
sage: F, s = sr.polynomial_system(); F                                      # needs sage.rings.polynomial.pbori
Polynomial Sequence with 40 Polynomials in 20 Variables
sage: F = F.subs(s); F                                                      # needs sage.rings.polynomial.pbori
Polynomial Sequence with 40 Polynomials in 16 Variables

Python

>>> from sage.all import *
>>> sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
>>> F, s = sr.polynomial_system(); F                                      # needs sage.rings.polynomial.pbori
Polynomial Sequence with 40 Polynomials in 20 Variables
>>> F = F.subs(s); F                                                      # needs sage.rings.polynomial.pbori
Polynomial Sequence with 40 Polynomials in 16 Variables

Sage Live

sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
F, s = sr.polynomial_system(); F                                      # needs sage.rings.polynomial.pbori
F = F.subs(s); F                                                      # needs sage.rings.polynomial.pbori

universe()[source]¶

Return the polynomial ring all elements live in.

EXAMPLES:

Sage

sage: sr = mq.SR(allow_zero_inversions=True, gf2=True, order='block')       # needs sage.rings.polynomial.pbori
sage: F, s = sr.polynomial_system()                                         # needs sage.rings.polynomial.pbori
sage: print(F.ring().repr_long())                                           # needs sage.rings.polynomial.pbori
Polynomial Ring
 Base Ring : Finite Field of size 2
      Size : 20 Variables
  Block  0 : Ordering : deglex
             Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
  Block  1 : Ordering : deglex
             Names    : k000, k001, k002, k003

Python

>>> from sage.all import *
>>> sr = mq.SR(allow_zero_inversions=True, gf2=True, order='block')       # needs sage.rings.polynomial.pbori
>>> F, s = sr.polynomial_system()                                         # needs sage.rings.polynomial.pbori
>>> print(F.ring().repr_long())                                           # needs sage.rings.polynomial.pbori
Polynomial Ring
 Base Ring : Finite Field of size 2
      Size : 20 Variables
  Block  0 : Ordering : deglex
             Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
  Block  1 : Ordering : deglex
             Names    : k000, k001, k002, k003

Sage Live

sr = mq.SR(allow_zero_inversions=True, gf2=True, order='block')       # needs sage.rings.polynomial.pbori
F, s = sr.polynomial_system()                                         # needs sage.rings.polynomial.pbori
print(F.ring().repr_long())                                           # needs sage.rings.polynomial.pbori

variables()[source]¶

Return all variables present in this system. This tuple may or may not be equal to the generators of the ring of this system.

EXAMPLES:

Sage

sage: sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
sage: F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
sage: F.variables()[:10]                                                    # needs sage.rings.polynomial.pbori
(k003, k002, k001, k000, s003, s002, s001, s000, w103, w102)

Python

>>> from sage.all import *
>>> sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
>>> F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
>>> F.variables()[:Integer(10)]                                                    # needs sage.rings.polynomial.pbori
(k003, k002, k001, k000, s003, s002, s001, s000, w103, w102)

Sage Live

sr = mq.SR(allow_zero_inversions=True)                                # needs sage.rings.polynomial.pbori
F,s = sr.polynomial_system()                                          # needs sage.rings.polynomial.pbori
F.variables()[:10]                                                    # needs sage.rings.polynomial.pbori

class sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_gf2(parts, ring, immutable=False, cr=False, cr_str=None)[source]¶

Bases: PolynomialSequence_generic

Polynomial Sequences over $F_{2}$ .

coefficients_monomials(order=None, sparse=True)[source]¶

Return the matrix of coefficients A and the matching vector of monomials v, such that A*v == vector(self).

Thus value of A[i,j] corresponds the coefficient of the monomial v[j] in the i-th polynomial in this system.

Monomials are ordered w.r.t. the term ordering of order if given; otherwise, they are ordered w.r.t. self.ring() in reverse order, i.e., such that the smallest entry comes last.

INPUT:

sparse – construct a sparse matrix (default: True)
order – list or tuple specifying the order of monomials (default: None)

EXAMPLES:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: B.<x,y,z> = BooleanPolynomialRing()
sage: F = Sequence([x*y + y + 1, z + 1])
sage: A, v = F.coefficients_monomials()
sage: A
[1 1 0 1]
[0 0 1 1]
sage: v
(x*y, y, z, 1)
sage: A*v
(x*y + y + 1, z + 1)

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> B = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> F = Sequence([x*y + y + Integer(1), z + Integer(1)])
>>> A, v = F.coefficients_monomials()
>>> A
[1 1 0 1]
[0 0 1 1]
>>> v
(x*y, y, z, 1)
>>> A*v
(x*y + y + 1, z + 1)

Sage Live

# needs sage.rings.polynomial.pbori
B.<x,y,z> = BooleanPolynomialRing()
F = Sequence([x*y + y + 1, z + 1])
A, v = F.coefficients_monomials()
A
v
A*v

eliminate_linear_variables(maxlength=+Infinity, skip=None, return_reductors=False, use_polybori=False)[source]¶

Return a new system where linear leading variables are eliminated if the tail of the polynomial has length at most maxlength.

INPUT:

maxlength – an optional upper bound on the number of monomials by which a variable is replaced. If maxlength==+Infinity then no condition is checked. (default: +Infinity).
skip – an optional callable to skip eliminations. It must accept two parameters and return either True or False. The two parameters are the leading term and the tail of a polynomial (default: None).
return_reductors – if True the list of polynomials with linear leading terms which were used for reduction is also returned (default: False).
use_polybori – if True then polybori.ll.eliminate is called. While this is typically faster than what is implemented here, it is less flexible (skip is not supported) and may increase the degree (default: False)

OUTPUT:

With return_reductors=True, a pair of sequences of boolean polynomials are returned, along with the promises that:

The union of the two sequences spans the same boolean ideal as the argument of the method
The second sequence only contains linear polynomials, and it forms a reduced groebner basis (they all have pairwise distinct leading variables, and the leading variable of a polynomial does not occur anywhere in other polynomials).
The leading variables of the second sequence do not occur anywhere in the first sequence (these variables have been eliminated).

With return_reductors=False, only the first sequence is returned.

EXAMPLES:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: F = Sequence([c + d + b + 1, a + c + d, a*b + c, b*c*d + c])
sage: F.eliminate_linear_variables() # everything vanishes
[]
sage: F.eliminate_linear_variables(maxlength=2)
[b + c + d + 1, b*c + b*d + c, b*c*d + c]
sage: F.eliminate_linear_variables(skip=lambda lm,tail: str(lm)=='a')
[a + c + d, a*c + a*d + a + c, c*d + c]

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> F = Sequence([c + d + b + Integer(1), a + c + d, a*b + c, b*c*d + c])
>>> F.eliminate_linear_variables() # everything vanishes
[]
>>> F.eliminate_linear_variables(maxlength=Integer(2))
[b + c + d + 1, b*c + b*d + c, b*c*d + c]
>>> F.eliminate_linear_variables(skip=lambda lm,tail: str(lm)=='a')
[a + c + d, a*c + a*d + a + c, c*d + c]

Sage Live

# needs sage.rings.polynomial.pbori
B.<a,b,c,d> = BooleanPolynomialRing()
F = Sequence([c + d + b + 1, a + c + d, a*b + c, b*c*d + c])
F.eliminate_linear_variables() # everything vanishes
F.eliminate_linear_variables(maxlength=2)
F.eliminate_linear_variables(skip=lambda lm,tail: str(lm)=='a')

The list of reductors can be requested by setting return_reductors to True:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: F = Sequence([a + b + d, a + b + c])
sage: F, R = F.eliminate_linear_variables(return_reductors=True)
sage: F
[]
sage: R
[a + b + d, c + d]

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> F = Sequence([a + b + d, a + b + c])
>>> F, R = F.eliminate_linear_variables(return_reductors=True)
>>> F
[]
>>> R
[a + b + d, c + d]

Sage Live

# needs sage.rings.polynomial.pbori
B.<a,b,c,d> = BooleanPolynomialRing()
F = Sequence([a + b + d, a + b + c])
F, R = F.eliminate_linear_variables(return_reductors=True)
F
R

If the input system is detected to be inconsistent then [1] is returned, and the list of reductors is empty:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: R.<x,y,z> = BooleanPolynomialRing()
sage: S = Sequence([x*y*z + x*y + z*y + x*z, x + y + z + 1, x + y + z])
sage: S.eliminate_linear_variables()
[1]
sage: R.<x,y,z> = BooleanPolynomialRing()
sage: S = Sequence([x*y*z + x*y + z*y + x*z, x + y + z + 1, x + y + z])
sage: S.eliminate_linear_variables(return_reductors=True)
([1], [])

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> R = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> S = Sequence([x*y*z + x*y + z*y + x*z, x + y + z + Integer(1), x + y + z])
>>> S.eliminate_linear_variables()
[1]
>>> R = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> S = Sequence([x*y*z + x*y + z*y + x*z, x + y + z + Integer(1), x + y + z])
>>> S.eliminate_linear_variables(return_reductors=True)
([1], [])

Sage Live

# needs sage.rings.polynomial.pbori
R.<x,y,z> = BooleanPolynomialRing()
S = Sequence([x*y*z + x*y + z*y + x*z, x + y + z + 1, x + y + z])
S.eliminate_linear_variables()
R.<x,y,z> = BooleanPolynomialRing()
S = Sequence([x*y*z + x*y + z*y + x*z, x + y + z + 1, x + y + z])
S.eliminate_linear_variables(return_reductors=True)

Note

This is called “massaging” in [BCJ2007].

reduced()[source]¶

If this sequence is $f_{1}, . . ., f_{n}$ , return $g_{1}, . . ., g_{s}$ such that:

$(f_{1}, . . ., f_{n}) = (g_{1}, . . ., g_{s})$
$L T (g_{i}) \neq L T (g_{j})$ for all $i \neq j$
$L T (g_{i})$ does not divide $m$ for all monomials $m$ of $g_{1}, . . ., g_{i - 1}, g_{i + 1}, . . ., g_{s}$

EXAMPLES:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=True)
sage: while True:  # workaround (see :issue:`31891`)
....:     try:
....:         F, s = sr.polynomial_system()
....:         break
....:     except ZeroDivisionError:
....:         pass
sage: g = F.reduced()
sage: len(g) == len(set(gi.lt() for gi in g))
True
sage: for i in range(len(g)):
....:     for j in range(len(g)):
....:         if i == j:
....:             continue
....:         for t in list(g[j]):
....:             assert g[i].lt() not in t.divisors()

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4), gf2=True, polybori=True)
>>> while True:  # workaround (see :issue:`31891`)
...     try:
...         F, s = sr.polynomial_system()
...         break
...     except ZeroDivisionError:
...         pass
>>> g = F.reduced()
>>> len(g) == len(set(gi.lt() for gi in g))
True
>>> for i in range(len(g)):
...     for j in range(len(g)):
...         if i == j:
...             continue
...         for t in list(g[j]):
...             assert g[i].lt() not in t.divisors()

Sage Live

# needs sage.rings.polynomial.pbori
sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=True)
while True:  # workaround (see :issue:`31891`)
    try:
        F, s = sr.polynomial_system()
        break
    except ZeroDivisionError:
        pass
g = F.reduced()
len(g) == len(set(gi.lt() for gi in g))
for i in range(len(g)):
    for j in range(len(g)):
        if i == j:
            continue
        for t in list(g[j]):
            assert g[i].lt() not in t.divisors()

solve(algorithm='polybori', n=1, eliminate_linear_variables=True, verbose=False, **kwds)[source]¶

Find solutions of this boolean polynomial system.

This function provide a unified interface to several algorithms dedicated to solving systems of boolean equations. Depending on the particular nature of the system, some might be much faster than some others.

INPUT:

self – a sequence of boolean polynomials
algorithm – the method to use. Possible values are 'polybori', 'sat' and 'exhaustive_search'. (default: 'polybori', since it is always available)
n – (default: 1) number of solutions to return. If n == +Infinity then all solutions are returned. If $n < \infty$ then $n$ solutions are returned if the equations have at least $n$ solutions. Otherwise, all the solutions are returned.
eliminate_linear_variables – whether to eliminate variables that appear linearly. This reduces the number of variables (makes solving faster a priori), but is likely to make the equations denser (may make solving slower depending on the method).
verbose – boolean (default: False); whether to display progress and (potentially) useful information while the computation runs

EXAMPLES:

Without argument, a single arbitrary solution is returned:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: R.<x,y,z> = BooleanPolynomialRing()
sage: S = Sequence([x*y + z, y*z + x, x + y + z + 1])
sage: sol = S.solve()
sage: sol
[{z: 0, y: 1, x: 0}]

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> R = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> S = Sequence([x*y + z, y*z + x, x + y + z + Integer(1)])
>>> sol = S.solve()
>>> sol
[{z: 0, y: 1, x: 0}]

Sage Live

# needs sage.rings.polynomial.pbori
R.<x,y,z> = BooleanPolynomialRing()
S = Sequence([x*y + z, y*z + x, x + y + z + 1])
sol = S.solve()
sol

We check that it is actually a solution:

Sage

sage: S.subs(sol[0])                                                        # needs sage.rings.polynomial.pbori
[0, 0, 0]

Python

>>> from sage.all import *
>>> S.subs(sol[Integer(0)])                                                        # needs sage.rings.polynomial.pbori
[0, 0, 0]

Sage Live

S.subs(sol[0])                                                        # needs sage.rings.polynomial.pbori

We obtain all solutions:

Sage

sage: sols = S.solve(n=Infinity)                                            # needs sage.rings.polynomial.pbori
sage: sols                                                                  # needs sage.rings.polynomial.pbori
[{z: 0, y: 1, x: 0}, {z: 1, y: 1, x: 1}]
sage: [S.subs(x) for x in sols]                                             # needs sage.rings.polynomial.pbori
[[0, 0, 0], [0, 0, 0]]

Python

>>> from sage.all import *
>>> sols = S.solve(n=Infinity)                                            # needs sage.rings.polynomial.pbori
>>> sols                                                                  # needs sage.rings.polynomial.pbori
[{z: 0, y: 1, x: 0}, {z: 1, y: 1, x: 1}]
>>> [S.subs(x) for x in sols]                                             # needs sage.rings.polynomial.pbori
[[0, 0, 0], [0, 0, 0]]

Sage Live

sols = S.solve(n=Infinity)                                            # needs sage.rings.polynomial.pbori
sols                                                                  # needs sage.rings.polynomial.pbori
[S.subs(x) for x in sols]                                             # needs sage.rings.polynomial.pbori

We can force the use of exhaustive search if the optional package FES is present:

Sage

sage: sol = S.solve(algorithm='exhaustive_search')  # optional - fes        # needs sage.rings.polynomial.pbori
sage: sol                                           # optional - fes        # needs sage.rings.polynomial.pbori
[{z: 1, y: 1, x: 1}]
sage: S.subs(sol[0])                                # optional - fes        # needs sage.rings.polynomial.pbori
[0, 0, 0]

Python

>>> from sage.all import *
>>> sol = S.solve(algorithm='exhaustive_search')  # optional - fes        # needs sage.rings.polynomial.pbori
>>> sol                                           # optional - fes        # needs sage.rings.polynomial.pbori
[{z: 1, y: 1, x: 1}]
>>> S.subs(sol[Integer(0)])                                # optional - fes        # needs sage.rings.polynomial.pbori
[0, 0, 0]

Sage Live

sol = S.solve(algorithm='exhaustive_search')  # optional - fes        # needs sage.rings.polynomial.pbori
sol                                           # optional - fes        # needs sage.rings.polynomial.pbori
S.subs(sol[0])                                # optional - fes        # needs sage.rings.polynomial.pbori

And we may use SAT-solvers if they are available:

Sage

sage: sol = S.solve(algorithm='sat')        # optional - pycryptosat        # needs sage.rings.polynomial.pbori
sage: sol                                   # optional - pycryptosat        # needs sage.rings.polynomial.pbori
[{z: 0, y: 1, x: 0}]
sage: S.subs(sol[0])                                                        # needs sage.rings.polynomial.pbori
[0, 0, 0]

Python

>>> from sage.all import *
>>> sol = S.solve(algorithm='sat')        # optional - pycryptosat        # needs sage.rings.polynomial.pbori
>>> sol                                   # optional - pycryptosat        # needs sage.rings.polynomial.pbori
[{z: 0, y: 1, x: 0}]
>>> S.subs(sol[Integer(0)])                                                        # needs sage.rings.polynomial.pbori
[0, 0, 0]

Sage Live

sol = S.solve(algorithm='sat')        # optional - pycryptosat        # needs sage.rings.polynomial.pbori
sol                                   # optional - pycryptosat        # needs sage.rings.polynomial.pbori
S.subs(sol[0])                                                        # needs sage.rings.polynomial.pbori

class sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_gf2e(parts, ring, immutable=False, cr=False, cr_str=None)[source]¶

Bases: PolynomialSequence_generic

PolynomialSequence over $F_{2^{e}}$ , i.e extensions over $F_{(} 2)$ .

weil_restriction()[source]¶

Project this polynomial system to $F_{2}$ .

That is, compute the Weil restriction of scalars for the variety corresponding to this polynomial system and express it as a polynomial system over $F_{2}$ .

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(2^2)
sage: P.<x,y> = PolynomialRing(k, 2)
sage: a = P.base_ring().gen()
sage: F = Sequence([x*y + 1, a*x + 1], P)
sage: F2 = F.weil_restriction()
sage: F2
[x0*y0 + x1*y1 + 1, x1*y0 + x0*y1 + x1*y1, x1 + 1, x0 + x1, x0^2 + x0,
 x1^2 + x1, y0^2 + y0, y1^2 + y1]

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(2)**Integer(2), names=('a',)); (a,) = k._first_ngens(1)
>>> P = PolynomialRing(k, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> a = P.base_ring().gen()
>>> F = Sequence([x*y + Integer(1), a*x + Integer(1)], P)
>>> F2 = F.weil_restriction()
>>> F2
[x0*y0 + x1*y1 + 1, x1*y0 + x0*y1 + x1*y1, x1 + 1, x0 + x1, x0^2 + x0,
 x1^2 + x1, y0^2 + y0, y1^2 + y1]

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(2^2)
P.<x,y> = PolynomialRing(k, 2)
a = P.base_ring().gen()
F = Sequence([x*y + 1, a*x + 1], P)
F2 = F.weil_restriction()
F2

Another bigger example for a small scale AES:

Sage

sage: # needs sage.rings.polynomial.pbori
sage: sr = mq.SR(1, 1, 1, 4, gf2=False)
sage: while True:  # workaround (see :issue:`31891`)
....:     try:
....:         F, s = sr.polynomial_system()
....:         break
....:     except ZeroDivisionError:
....:         pass
sage: F
Polynomial Sequence with 40 Polynomials in 20 Variables
sage: F2 = F.weil_restriction(); F2
Polynomial Sequence with 240 Polynomials in 80 Variables

Python

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4), gf2=False)
>>> while True:  # workaround (see :issue:`31891`)
...     try:
...         F, s = sr.polynomial_system()
...         break
...     except ZeroDivisionError:
...         pass
>>> F
Polynomial Sequence with 40 Polynomials in 20 Variables
>>> F2 = F.weil_restriction(); F2
Polynomial Sequence with 240 Polynomials in 80 Variables

Sage Live

# needs sage.rings.polynomial.pbori
sr = mq.SR(1, 1, 1, 4, gf2=False)
while True:  # workaround (see :issue:`31891`)
    try:
        F, s = sr.polynomial_system()
        break
    except ZeroDivisionError:
        pass
F
F2 = F.weil_restriction(); F2

sage.rings.polynomial.multi_polynomial_sequence.is_PolynomialSequence(F)[source]¶

Return True if F is a PolynomialSequence.

INPUT:

F – anything

EXAMPLES:

Sage

sage: P.<x,y> = PolynomialRing(QQ)
sage: I = [[x^2 + y^2], [x^2 - y^2]]
sage: F = Sequence(I, P); F
[x^2 + y^2, x^2 - y^2]

sage: from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence_generic
sage: isinstance(F, PolynomialSequence_generic)
True

Python

>>> from sage.all import *
>>> P = PolynomialRing(QQ, names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> I = [[x**Integer(2) + y**Integer(2)], [x**Integer(2) - y**Integer(2)]]
>>> F = Sequence(I, P); F
[x^2 + y^2, x^2 - y^2]

>>> from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence_generic
>>> isinstance(F, PolynomialSequence_generic)
True

Sage Live

P.<x,y> = PolynomialRing(QQ)
I = [[x^2 + y^2], [x^2 - y^2]]
F = Sequence(I, P); F
from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence_generic
isinstance(F, PolynomialSequence_generic)