Polynomials

Symbolica documentation for getting started, symbolic expressions, numerical evaluation, pattern matching, and APIs in Python and Rust.

Polynomials are an important sub-type of general mathematical expression and lie at the heart of many mathematical problems. Since polynomials have a constrained form, Symbolica has its own data structures for univariate and multivariate polynomials, which allow for state-of-the-art polynomial arithmetic.

Construction

Polynomials can be efficiently constructed directly from a string if the variables are provided and if it occurs in expanded form:

from symbolica import Polynomial
p = Polynomial.parse('x^2*y + 1 + 2*x + y^4', ['x', 'y'])
print(p)

use symbolica::prelude::*;

fn main() {
    let var_name_map = ["x".into(), "y".into()];
    let vars: Vec<_> = var_name_map
        .iter()
        .map(|x| symbol!(x))
        .collect();

    let p: MultivariatePolynomial<IntegerRing, u8> = Token::parse("x^2*y + 1 + 2*x + y^4")
        .unwrap()
        .to_polynomial(IntegerRing::new(), &vars, &var_name_map)
        .unwrap();

    println!("{}", p);
}

or can be converted from any Symbolica expression:

from symbolica import Expression
x, y = S('x', 'y')
e = x**2*y + 1 + 2*x + y**4
p = e.to_polynomial()
print(p)

use symbolica::prelude::*;

fn main() {
    let a = parse!("x^2*y + 1 + 2*x + y^4");

    let p: MultivariatePolynomial<IntegerRing, u8> =
        a.to_polynomial(IntegerRing::new(), None).unwrap();

    println!("{}", p);
}

Converting from a Symbolica expressions will automatically define non-polynomial parts as new independent variables:

from symbolica import *
e = E("x^2 + x + f(z + 1) / y + f(z + 1)^2")
p = e.to_polynomial()

print('poly =', p)
for i, var in enumerate(p.get_var_list()):
    print('var {} = {}'.format(i, var))

use symbolica::prelude::*;

fn main() {
    let a = parse!("x^2 + x + f(z + 1) / y + f(z + 1)^2");
    let p: MultivariatePolynomial<_, u8> = a
        .to_polynomial(&IntegerRing::new(), None);

    println!("poly = {}", p);
    for (i, a) in p.get_vars_ref().iter().enumerate() {
        println!("var {} = {}", i, a.to_string());
    }
}

where f(z + 1) and 1/y are newly created variables.

Prime fields and Galois fields

The coefficient ring of the polynomial can be a prime field or Galois field. For example, below we define a polynomial over \(\mathbb{Z}_3\):

from symbolica import *
p = E('x^2+7x+2').to_polynomial(modulus=3)
print('poly =', p)

use symbolica::prelude::*;

fn main() {
    let p = parse!("x^2+7x+2").to_polynomial::<_, u8>(&Zp::new(3));
    println!("poly = {}", p);
}

Note that in Rust, \(\mathbb{Z_2}\) is represented with the Z2 type.

Output

x^2+x+2

Below we construct the Galois field \(GF(3^2)\):

from symbolica import *
p = E('x^2+7x+2').to_polynomial(modulus=3, extension=(2, S('t')))
print('poly =', p)

use symbolica::prelude::*;

fn main() {
    let g = AlgebraicExtension::galois_field(3, 2, symbol!("t"));
    let p = parse!("x^2+7x+2").to_polynomial::<_, u8>(&g);
    println!("poly = {}", p);
}

where the minimal polynomial is determined automatically.

Algebraic numbers

Algebraic numbers can be defined by providing their minimal polynomial. For example, the extension \(\mathbb{Q}[\sqrt{2}]\) has the minimal polynomial \(t^2-2\). In the example below we define a polynomial in \(\mathbb{Q}[\sqrt{2}]\) and factor it:

p = E('x^4 - 10x^2 + 1').to_polynomial(minimal_poly=E('t^2-2'))
for f, e in p.factor():
    print(f)

use symbolica::prelude::*;

fn main() {
    let g = AlgebraicExtension::new(parse!("t^2-2"));
    let p = parse!("x^4 - 10x^2 + 1").to_polynomial::<_, u8>(&Q, None).to_number_field(&g);

    for (f, _) in p.factor() {
        println!("{}", f);
    }
}

We obtain:

Output

-1+(-2*t)*x+x^2 % -2+t^2
-1+(2*t)*x+x^2 % -2+t^2

Algebraic number fields can be extended with another algebraic number field. For example, let us extend \(\mathbb{Q}[\sqrt{2}]\) with \(\mathbb{Q}[\sqrt{3}]\):

sqrt2 = E('t^2-2')
p = E('x^4-10x^2+1').to_polynomial(minimal_poly=sqrt2)
p2, _, _ = p.extend(E('z^2-3').to_polynomial(minimal_poly=sqrt2))

for z, e in p2.factor():
    print(z, e)

use symbolica::prelude::*;

fn main() {
    let g = AlgebraicExtension::new(parse!("t^2-2"));
    let g2 = AlgebraicExtension::new(parse!("z^2-3"));
    let gn = g.extend(&g2);
    et p = parse!("x^4-10x^2+1").to_polynomial::<_, u8>(&Q, None).to_number_field(&gn);

    for (f, _) in p.factor() {
        println!("{}", f);
    }
}

Output

(10*z-z^3)+x % 1-10*z^2+z^4 1
(z)+x % 1-10*z^2+z^4 1
(-10*z+z^3)+x % 1-10*z^2+z^4 1
(-z)+x % 1-10*z^2+z^4 1

Groebner basis

A Groebner basis of a polynomial system can be computed using lexicographical ordering or reverse graded lexicographical order (grevlex). The latter is often much faster.

from symbolica import Polynomial
basis = Polynomial.groebner_basis(
    [E("a b c d - 1").to_polynomial(),
     E("a b c + a b d + a c d + b c d").to_polynomial(),
     E("a b + b c + a d + c d").to_polynomial(),
     E("a + b + c + d").to_polynomial()],
    grevlex=False,
    print_stats=True
)
for p in basis:
    print(p)

use symbolica::prelude::*;

fn main() {
    for x in 'a'..='z' {
        symbol!(x.to_string());
    }

    // cyclic-4
    let polys = [
        "a b c d - 1",
        "a b c + a b d + a c d + b c d",
        "a b + b c + a d + c d",
        "a + b + c + d",
    ];

    let ideal: Vec<MultivariatePolynomial<_, u16>> = polys
        .iter()
        .map(|x| {
            parse!(x)
                .unwrap()
                .to_polynomial(&FiniteField::<u32>::new(13), None)
                .unwrap()
        })
        .collect();

    // compute the Groebner basis with lex ordering
    let gb = GroebnerBasis::new(&ideal, true);

    println!("Lex order basis:");
    for g in &gb.system {
        println!("\t{}", g);
    }

    // compute the Groebner basis with grevlex ordering by converting the polynomials
    let grevlex_ideal: Vec<_> = ideal.iter().map(|p| p.reorder::<GrevLexOrder>()).collect();
    let gb = GroebnerBasis::new(&grevlex_ideal, true);
    println!("Grevlex order basis:");
    for g in &gb.system {
        println!("\t{}", g);
    }
}

Rational polynomials

Rational polynomials can also be efficiently constructed directly from a string:

from symbolica import RationalPolynomial
p = RationalPolynomial.parse('1/x+(1+x)^2/(1+x+y)', ['x', 'y'])
print(p)

use symbolica::prelude::*;

fn main() {
    let var_name_map = ["x".into(), "y".into()];
    let vars: Vec<_> = var_name_map
        .iter()
        .map(|x| symbol!(x))
        .collect();

    let p: RationalPolynomial<IntegerRing, u8> = Token::parse("x^2*y + 1 + 2*x + y^4")
        .unwrap()
        .to_rational_polynomial(
            &Q,
            &Z,
            &vars,
            &var_name_map,
        )
        .unwrap();

    println!("{}", p);
}

or can be converted from a Symbolica expression.

from symbolica import Expression
x, y = S('x', 'y')
e = 1/x+(1+x)^2/(1+x+y)
p = e.to_rational_polynomial()
print(p)

use symbolica::prelude::*;

fn main() {
    let a = parse!("x^2*y + 1 + 2*x + y^4");

    let p: RationalPolynomial<IntegerRing, u8> = a
        .to_rational_polynomial(
            &Q,
            &Z,
            None,
        );

    println!("{}", p);
}

Contrary to polynomials conversion, all rational polynomial conversion routines attempt to do expansions internally.

If the input contains non-rational polynomial parts, these will be considered as new independent variables. For example:

from symbolica import Expression
e = E("x^2 + x + f(z + 1) / y + f(z + 1)^2")
p = e.to_rational_polynomial()

print('poly =', p)
for i, var in enumerate(p.get_var_list()):
    print('var {} = {}'.format(i, var))

use symbolica::prelude::*;

fn main() {
    let a = parse!("x^2 + x + f(z + 1) / y + f(z + 1)^2");

    let p: RationalPolynomial<_, u8> = a
        .to_rational_polynomial(&IntegerRing::new(), &IntegerRing::new(), None);

    println!("poly = {}", p);
    for (i, a) in p.numerator.variables.unwrap().iter().enumerate() {
        println!("var {} = {}", i, a.to_string());
    }
}

where f(z + 1), is a newly created variable.

Small-exponent versions

Both polynomials and rational polynomials have variants that limit the power of the variables, which increases performance.

Symbolica notation

The fastest way to parse a rational polynomial from a string is to provide it in Symbolica notation, which is the following format:

[numerator,denominator]

with square brackets. The greatest common divisor of the numerator and the denominator must be 1. Each term in the two polynomials must be in one the following format:

The product operator is *
The coefficient must be placed first. If the coefficient is one, it can be omitted.
The variable with exponent is given as x^n. If the power is one, it can be omitted

For example:

[2*x+x^2+x^3*y^2,1+x+y]

The terms do not have to be sorted in Symbolica ordering, but the such a conversion will impact performance.