Polynomials

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

Run Symbolica in your browser

Python examples with a Run button can be edited and run here. The first run loads Python, Symbolica, hover documentation, and code completion.

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 constructed directly from a string with P. Use vars to specify the variable ordering:

Python

from symbolica import P, S
p = P('x^2*y + 1 + 2*x + y^4', vars=S('x', 'y'))
p

Rust

use symbolica::prelude::*;

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

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

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

or can be converted from any Symbolica expression:

Python

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

Rust

use symbolica::prelude::*;

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

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

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

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

Python

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_variables()):
    print('var {} = {}'.format(i, var))

Rust

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\):

Python

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

Rust

use symbolica::prelude::*;

fn main() {
    let p = parse!("x^2+7x+2").to_polynomial::<_, u8>(&Zp::new(3), None);
    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)\):

Python

from symbolica import *
p = P('x^2+7x+2', modulus=3, power=(2, S('t')))
print('poly =', p)

Rust

use symbolica::prelude::*;

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

where the minimal polynomial is determined automatically.

Algebraic numbers

Choose the coefficient domain explicitly. By default, conversion treats non-polynomial parts, including radicals, as independent variables. Pass extensions=[] to discover algebraic numbers in an expression and put them in a common coefficient field instead:

from symbolica import *

expression = E('x + sqrt(2)')
ordinary = expression.to_polynomial()
algebraic = expression.to_polynomial(extensions=[])
print('Default variables:', ordinary.get_variables())
print('Number-field variables:', algebraic.get_variables())
assert algebraic.get_variables() == [S('x')]
algebraic

The default polynomial has variables x and sqrt(2). The number-field polynomial has only x as a variable; sqrt(2) is a coefficient.

Adding generators

Supply generators in extensions to include algebraic numbers even when they do not occur in the input. For example, \(x^2-2\) factors into linear factors over \(\mathbb{Q}(\sqrt{2})\):

Python

from symbolica import *

p = E('x^2-2').to_polynomial(extensions=[E('sqrt(2)')])
factors = p.factor()
assert len(factors) == 2
[f.to_expression() for f, multiplicity in factors]

Rust

use symbolica::prelude::*;

fn main() {
    let (context, polynomial) = parse!("x^2-2")
        .to_polynomial_in_algebraic_extension::<u16>(
            symbol!("x"), &[parse!("sqrt(2)")],
        )
        .unwrap();

    for (factor, multiplicity) in polynomial.factor() {
        let expression = factor.to_expression_with_context(&context).unwrap();
        println!("{expression} (multiplicity {multiplicity})");
    }
}

In Rust, the returned AlgebraicContext records the embedding of the coefficients. Keep it to convert results back with to_expression_with_context. An empty generator slice enables automatic discovery. For a reusable field, construct an AlgebraicContext with from_atom or from_generators, extend it with adjoin_generators, and convert expressions with its to_polynomial method.

Multiple generators form a common field. The following polynomial splits into four linear factors over \(\mathbb{Q}(\sqrt{2},\sqrt{3})\):

from symbolica import *

p = E('x^4-10x^2+1').to_polynomial(
    extensions=[E('sqrt(2)'), E('sqrt(3)')],
)
factors = p.factor()
assert len(factors) == 4
[f.to_expression() for f, multiplicity in factors]

A selected algebraic root can also generate the field:

from symbolica import *

alpha = E('t^3-2').root(0, variable=S('t'))
p = E('x^3-2').to_polynomial(extensions=[alpha])
[f.to_expression() for f, multiplicity in p.factor()]

Use vars to choose the polynomial variable ordering. The extensions option cannot be combined with modulus, power, or minimal_poly. P supports the latter three options; for extensions, use E(...).to_polynomial(...).

A field defined by a minimal polynomial

If you want a formal generator t satisfying \(t^2=2\), use minimal_poly. A defining polynomial alone does not choose one of its real or complex roots; use radicals or selected roots as above when that embedding matters.

Python

from symbolica import *

p = P('x^4-10x^2+1', minimal_poly=P('t^2-2'))
[f for f, multiplicity in p.factor()]

Rust

use symbolica::prelude::*;

fn main() {
    let minimal = parse!("t^2-2").to_polynomial::<_, u16>(&Q, None);
    let field = AlgebraicExtension::new(minimal);
    let p = parse!("x^4-10x^2+1")
        .to_polynomial::<_, u16>(&Q, None)
        .to_number_field(&field);
    for (factor, multiplicity) in p.factor() {
        println!("{factor} (multiplicity {multiplicity})");
    }
}

The factors are \(x^2-2tx-1\) and \(x^2+2tx-1\), with \(t^2=2\).

You can also convert an existing polynomial:

from symbolica import *

p = P('x^2-2').to_number_field(P('t^2-2'))
[f for f, multiplicity in p.factor()]

Composing formal fields

adjoin returns a minimal polynomial for the combined field and the representations of both original generators. Substitute these representations before converting a polynomial to the new field:

from symbolica import *

a, b = S('a', 'b')
minimal, rep_a, rep_b = P('a^2-2').adjoin(P('b^2-3'))
p = (P('x+a+b')
     .replace(b, rep_b)
     .replace(a, rep_a)
     .to_number_field(minimal))
p

Here the new field uses b as its generator. The substitutions are ordered so that occurrences of b introduced by rep_a are not substituted again. This explicit route is useful when working with formal minimal polynomials; extensions handles embedded radicals and roots directly.

Factoring an expression directly

If only the factored expression is needed, use factor with the singular keyword extension:

from symbolica import *

E('x^2-2').factor(extension=[E('sqrt(2)')])

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.

Python

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

Rust

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).to_polynomial(&Zp::new(13), None)
        })
        .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:

Python

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

Rust

use symbolica::prelude::*;

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

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

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

or can be converted from a Symbolica expression.

Python

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

Rust

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:

Python

from symbolica import *
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_variables()):
    print('var {} = {}'.format(i, var))

Rust

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.get_vars_ref().iter().enumerate() {
        println!("var {} = {}", i, a.to_string());
    }
}

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

In Rust, algebraic coefficients can be discovered when constructing a rational polynomial too:

use symbolica::prelude::*;

fn main() {
    let (context, p) = parse!("(x+sqrt(2))/(x-sqrt(2))")
        .to_rational_polynomial_in_algebraic_extension::<u16>(symbol!("x"))
        .unwrap();
    let numerator = p.numerator.to_expression_with_context(&context).unwrap();
    let denominator = p.denominator.to_expression_with_context(&context).unwrap();
    println!("{}", numerator / denominator);
}

Python’s to_rational_polynomial does not currently accept extensions.

TipSmall-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.