Types and Functions

@ring! ℚ[x,y]

Define and return the specified polynomial ring, and bind the variable names to its generators.

Currently, the supported rings are: ℚ (Rational{BigInt}), ℤ (BigInt), ℝ (BigFloat) and ℂ (Complex{BigFloat}).

Note: @ring! returns the ring and injects the variables. The macro @ring only returns the ring.

If you need different coefficient rings, or need to specify a non-default monomial order or exponent integer type, use polynomial_ring instead.

Examples

julia> using PolynomialRings

julia> @ring! ℚ[x,y];

julia> x^3 + y
x^3 + y

See also

polynomial_ring

@ring ℚ[x,y]

Define and return the specified polynomial ring.

Currently, the supported rings are: ℚ (Rational{BigInt}), ℤ (BigInt), ℝ (BigFloat) and ℂ (Complex{BigFloat}).

Note: @ring! returns the ring and injects the variables into the surrounding scope. The macro @ring only returns the ring.

If you need different coefficient rings, or need to specify a non-default monomial order or exponent integer type, use polynomial_ring instead.

Examples

julia> using PolynomialRings

julia> @ring ℚ[x,y]
@ring(ℚ[x,y])

See also

polynomial_ring @ring!

@polyvar var [var...]

Define a polynomial ring in the given variables, and inject them into the surrounding scope.

This is equivalent to @ring! Int[var...].

If you need different coefficient rings, or need to specify a non-default monomial order or exponent integer type, use @ring! or polynomial_ring instead.

Examples

julia> using PolynomialRings

julia> @polyvar x y;

julia> x + 3y
x + 3*y

julia> @polyvar ε[];

julia> 1 + ε()*x + ε()*y
ε[1]*x + ε[2]*y + 1

See also

polynomial_ring @ring!

@polynomial x^3 + 3x^2 + 3x + 1

Create a multi-variate polynomial from an expression by creating the ring generated by all symbols appearing in the expression.

Examples

julia> using PolynomialRings

julia> @polynomial x^3 + x^2*y + x*y^2 + y^3
x^3 + x^2*y + x*y^2 + y^3

julia> @polynomial x^3 + x^2*y + x*y^2 + y^3
x^3 + x^2*y + x*y^2 + y^3

d = 4
@polynomial d*x

@polynomial(x^d) == @polynomial(x)^d

@polynomial(d*x^(d-1))

See also

@ring, polynomial_ring, convert(R, symbol)

polynomial_ring(symbols::Symbol...; basering=Rational{BigInt}, exptype=Int16, monomialorder=:degrevlex)

Create a type for the polynomial ring over basering in variables with names specified by symbols, and return the type and a tuple of these variables.

The exptype parameter defines the integer type for the exponents.

The monomialorder defines an order for the monomials for e.g. Gröbner basis computations; it also defines the internal sort order. Built-in values are :degrevlex, :deglex and :lex. This function will accept any symbol, though, and you can define your own monomial order by implementing

Base.Order.lt(::MonomialOrder{:myorder}, a::M, b::M) where M <: AbstractMonomial

See PolynomialRings.MonomialOrderings for examples.

Examples

julia> using PolynomialRings

julia> R,(x,y,z) = polynomial_ring(:x, :y, :z);

julia> x*y + z
x*y + z

formal_coefficients(R, name::Symbol)

Return an object representing formal coefficients for the polynomial ring R.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x];


julia> c = formal_coefficients(R, :c);



julia> c[1:3]
3-element Array{@ring(ℤ[c[]][x]),1}:
 c[1]
 c[2]
 c[3]

julia> [c()*x^2 + c()*x + c() , c()*x^2 + c()*x + c()]
2-element Array{@ring(ℤ[c[]][x]),1}:
 c[1]*x^2 + c[2]*x + c[3]
 c[4]*x^2 + c[5]*x + c[6]

f_red = rem(f, G)

Return the multivariate reduction of a polynomial f by a vector of polynomials G. By definition, this means that no leading term of a polynomial in G divides any monomial in f, and f_red + factors * G == f for some factors.

If you need to obtain the vector of factors, use divrem instead.

Examples

In one variable, this is just the normal Euclidean algorithm:

julia> using PolynomialRings

julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});

julia> rem(x^2 + 1, [x-im])
0

julia> rem(x^2 + y^2 + 1, [x, y])
1 + 0im

factors, f_red = divrem(f, G)

Return the multivariate reduction of a polynomial f by a vector of polynomials G, together with row vector of factors. By definition, this means that no leading term of a polynomial in G divides any monomial in f, and f_red + factors * G == f.

Examples

In one variable, this is just the normal Euclidean algorithm:

julia> using PolynomialRings

julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});

julia> divrem(x^2 + 1, [x-im])
(@ring(Complex{Int64}[x,y])[x + 0 + 1im], 0)

julia> divrem(x^2 + y^2 + 1, [x, y])
(@ring(Complex{Int64}[x,y])[x y], 1 + 0im)

diff(polynomial, variable)

Return the derivative of polynomial w.r.t. variable.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> diff(x^3, :x)
3*x^2

julia> diff(x^3, :y)
0

factors = div!(f, G)

Compute the multivariate reduction of a polynomial f by a vector of polynomials G, in-place. By definition, this means that after applying rem! no, leading term of a polynomial in G divides any monomial in f, and f + factors * G is equal to the original value of f.

The return value is nothing if no reduction has taken place. This situation could also be represented by the zero vector, but we choose nothing for efficiency.

If you want to allow clearing denominators, e.g. reduce 2x^2 by 3x even though your base ring is ℤ, use xdiv! instead.

Examples

In one variable, this is just the normal Euclidean algorithm:

julia> using PolynomialRings

julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});

julia> f = x^2 + 1 + 0im
x^2 + 1 + 0im

julia> collect(div!(f, [x-im]))
1×1 Array{@ring(Complex{Int64}[x,y]),2}:
 x + 0 + 1im

julia> f
0

julia> g = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im

julia> collect(div!(g, [x, y]))
1×2 Array{@ring(Complex{Int64}[x,y]),2}:
 x  y

julia> g
1 + 0im

any_reductions = rem!(f, G)

Compute the multivariate reduction of a polynomial f by a vector of polynomials G, in-place. By definition, this means that after applying rem! no, leading term of a polynomial in G divides any monomial in f, and f + factors * G is equal to the original value of f for some row vector factors.

The return value any_reductions is true if and only if factors is nonzero. Note that factors itself is not actually computed and not returned. If you need to obtain it, use div!.

If you want to allow clearing denominators, e.g. reduce 2x^2 by 3x even though your base ring is ℤ, use xrem! instead.

Examples

In one variable, this is just the normal Euclidean algorithm:

julia> using PolynomialRings

julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});

julia> f = x^2 + 1
x^2 + 1 + 0im

julia> rem!(f, [x-im])
true

julia> f
0

julia> g = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im

julia> rem!(g, [x, y])
true

julia> g
1 + 0im

f_red = xrem(f, G)

Return the multivariate reduction of a polynomial f by a vector of polynomials G. By definition, this means that no leading term of a polynomial in G divides any monomial in f, and f_red + factors * G == m * f for some factors and for some integer m.

If you need to obtain the vector of factors, use xdivrem instead.

Examples

In one variable, this is just the normal Euclidean algorithm:

julia> using PolynomialRings

julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});

julia> xrem(x^2 + 1, [x-im])
0

julia> xrem(x^2 + y^2 + 1, [x, y])
1 + 0im

m, factors = xdiv!(f, G)

Compute the multivariate reduction of a polynomial f by a vector of polynomials G, in-place. By definition, this means that after applying rem! no, leading term of a polynomial in G divides any monomial in f, and f + factors * G is equal to m times the original value of f.

The difference between xdiv! and div is that the former allows clearing denominators, e.g. reduce 2x^2 by 3x even when the base ring is ℤ.

Examples

In one variable, this is just the normal Euclidean algorithm:

julia> using PolynomialRings

julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});

julia> f = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im

julia> xdiv!(f, [x-im])
(1 + 0im, @ring(Complex{Int64}[x,y])[x + 0 + 1im])

julia> f
y^2

julia> g = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im

julia> xdiv!(g, [x, y])
(1 + 0im, @ring(Complex{Int64}[x,y])[x y])

julia> g
1 + 0im

any_reductions = xrem!(f, G)

Compute the multivariate reduction of a polynomial f by a vector of polynomials G, in-place. By definition, this means that after applying rem! no, leading term of a polynomial in G divides any monomial in f, and f + factors * G is equal to m times the original value of f for some scalar m and for some row vector factors.

The return value any_reductions is true if and only if factors is nonzero. Note that factors itself is not actually computed and not returned. If you need to obtain it, use xdiv!. The same holds for m.

The difference between xdiv! and div is that the former allows clearing denominators, e.g. reduce 2x^2 by 3x even when the base ring is ℤ.

Examples

In one variable, this is just the normal Euclidean algorithm:

julia> using PolynomialRings

julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});

julia> f = x^2 + 1
x^2 + 1 + 0im

julia> xrem!(f, [x-im])
true

julia> f
0

julia> g = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im

julia> xrem!(g, [x, y])
true

julia> g
1 + 0im

p = map_coefficients(f, q)

Apply a function f to all coefficients of q, and return the result.

abstract type MonomialOrder{Names} <: Base.Order.Ordering end

Represents a total order between monomials.

@expansion(f, var, [var...])

Return a collection of (monomial, coefficient) tuples decomposing f into its consituent parts.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> collect(@expand(x^3 + y^2, y))
2-element Array{Tuple{Tuple{Int16},@ring(ℤ[x])},1}:
 ((0,), x^3)
 ((2,), 1)

julia> collect(@expand(x^3 + y^2, x, y))
2-element Array{Tuple{Tuple{Int16,Int16},BigInt},1}:
 ((0, 2), 1)
 ((3, 0), 1)

See also

expansion(...), @coefficient and coefficient

expansion(f, symbol, [symbol...])

Return a collection of (monomial, coefficient) tuples decomposing f into its consituent parts.

In the REPL, you likely want to use the friendlier version @expansion instead.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> collect(expansion(x^3 + y^2, :y))
2-element Array{(Term over @ring(ℤ[x]) in @degrevlex(y)),1}:
 x^3
 y^2

julia> collect(expansion(x^3 + y^2, :x, :y))
2-element Array{(Term over BigInt in @degrevlex(x > y)),1}:
 y^2
 x^3

See also

@expansion(...), @coefficient and coefficient

@expand(f, var, [var...])

Return a collection of (exponent tuple, coefficient) tuples decomposing f into its consituent parts.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> collect(@expand(x^3 + y^2, y))
2-element Array{Tuple{Tuple{Int16},@ring(ℤ[x])},1}:
 ((0,), x^3)
 ((2,), 1)

julia> collect(@expand(x^3 + y^2, x, y))
2-element Array{Tuple{Tuple{Int16,Int16},BigInt},1}:
 ((0, 2), 1)
 ((3, 0), 1)

See also

@expansion, expand(...), @coefficient and coefficient

@coefficient(f, monomial)

Return a the coefficient of f at monomial.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> @coefficient(x^3*y + x, x)
1

julia> @coefficient(x^3*y + x, x^3)
y

julia> @coefficient(x^3*y + x, x^3*y^0)
0

julia> @coefficient(x^3*y + x, x^3*y^1)
1

See also

coefficient, expansion and @expansion

coefficient(f, exponent_tuple, symbol, [symbol...])

Return a the coefficient of f at monomial. In the REPL, you likely want to use the friendlier version @coefficient.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> coefficient(x^3*y + x, (1,), :x)
1

julia> coefficient(x^3*y + x, (3,), :x)
y

julia> coefficient(x^3*y + x, (3,0), :x, :y)
0

julia> coefficient(x^3*y + x, (3,1), :x, :y)
1

See also

@coefficient, expansion and @expansion

@expandcoefficients(f, vars...)

Return the coefficients of f when expanded as a polynomial in the given variables.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> collect(@expandcoefficients(x^3 + y^2, y))
2-element Array{@ring(ℤ[x]),1}:
 x^3
 1

julia> collect(@expandcoefficients(x^3 + y^2, x, y))
2-element Array{BigInt,1}:
 1
 1

See also

expandcoefficients, @expansion, expansion, @coefficient and coefficient

expandcoefficients(f, symbol, [symbol...])

Return the coefficients of f when expanded as a polynomial in the given variables.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> collect(expandcoefficients(x^3 + y^2, :y))
2-element Array{@ring(ℤ[x]),1}:
 x^3
 1

julia> collect(expandcoefficients(x^3 + y^2, :x, :y))
2-element Array{BigInt,1}:
 1
 1

See also

@expandcoefficients, @expansion, expansion, @coefficient and coefficient

@deg(f, vars...)

Return the total degree of f when expanded as a polynomial in the given variables.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> @deg (x^2 + x*y - 1) x
2

julia> @deg (x^2 + x*y - 1) y
1

See also

deg, @expansion

deg(f, vars...)

Return the total degree of f when regarded as a polynomial in vars. Returns -1 for the zero polynomial.

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> deg(x^2, :x)
2

julia> deg(x^2, :x, :y)
2

julia> deg(x^2, :y)
0

@linear_coefficient(f, vars...)
linear_coefficients(f, vars...)

Return the linear coefficients of f as a function of vars.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> @linear_coefficients(x^3*y + x + y + 1, x)
1-element Array{@ring(ℤ[y]),1}:
 1

julia> @linear_coefficients(x^3*y + x + y + 1, x, y)
2-element Array{BigInt,1}:
 1
 1

See also

@constant_coefficient, @coefficient, and @expansion

linear_coefficients(f, vars...)

Return the linear coefficients of f as a function of vars.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> linear_coefficients(x^3*y + x + y + 1, :x)
1-element Array{@ring(ℤ[y]),1}:
 1

julia> linear_coefficients(x^3*y + x + y + 1, :x, :y)
2-element Array{BigInt,1}:
 1
 1

See also

@constant_coefficient, @coefficient, and @expansion

@constant_coefficient(f, vars...)

Return the constant coefficient of f as a function of vars.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> @constant_coefficient(x^3*y + x + y + 1, x)
y + 1

julia> @constant_coefficient(x^3*y + x + y + 1, x, y)
1

See also

constant_coefficient, @coefficient, and @expansion

constant_coefficient(f, vars...)

Return the constant coefficient of f as a function of vars.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> constant_coefficient(x^3*y + x + y + 1, :x)
y + 1

julia> constant_coefficient(x^3*y + x + y + 1, :x, :y)
1

See also

@constant_coefficient, @coefficient, and @expansion

@flat_coefficients(a, var, [var...])

Return the polynomial coefficients of the matrix coefficients of a, when those matrix coefficients are regarded as polynomials in the given variables.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> collect(flat_coefficients([x^3 + y^2; y^5], :y))
3-element Array{@ring(ℤ[x]),1}:
 1
 x^3
 1

julia> collect(flat_coefficients([x^3 + y^2, y^5], :x, :y))
3-element Array{BigInt,1}:
 1
 1
 1

See also

flat_coefficients, @expansion, expansion, @coefficient and coefficient

flat_coefficients(a, symbol, [symbol...])

Return the polynomial coefficients of the matrix coefficients of a, when those matrix coefficients are regarded as polynomials in the given variables.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> collect(flat_coefficients([x^3 + y^2; y^5], :y))
3-element Array{@ring(ℤ[x]),1}:
 1
 x^3
 1

julia> collect(flat_coefficients([x^3 + y^2, y^5], :x, :y))
3-element Array{BigInt,1}:
 1
 1
 1

See also

@expandcoefficients, @expansion, expansion, @coefficient and coefficient

basis = gröbner_basis(polynomials)

Return a Gröbner basis for the ideal generated by polynomials.

This is computed using the GWV algorithm; see PolynomialRings.GröbnerGWV.gwv for details.

basis, transformation = gröbner_transformation(polynomials)

Return a Gröbner basis for the ideal generated by polynomials, together with a transformation that proves that each element in basis is in that ideal (i.e. basis == transformation * polynomials).

This is computed using the GWV algorithm with a few standard optmizations; see PolynomialRings.GröbnerGWV.gwv for details.

syz = syzygies(G)

Return all relations between the elements of G.

Examples

julia> using PolynomialRings

julia> R = @ring! ℤ[x,y];

julia> I = [x^5, x^2 + y, x*y + y^2];

julia> G, tr = gröbner_transformation(I);

julia> K = syzygies(G) * tr; # the kernel of the map R^3 -> I induced by these generators

julia> iszero(K * I)
true

factors = lift(polynomials, y)

Return a row vector of factors such that factors * polynomials is equal to y, or nothing if y is not in the ideal generated by polynomials.

This is computed using gröbner_transformation; see there for more information.

Note: if you need to compute many lifts for the same set of polynomials, it is beneficial to use gröbner_transformation yourself as it avoids re-doing the most computationally intensive part.

x = matrix_solve_affine(f, y, dims, Type=eltype(y))

Return the solution x to the equation

``f(x) = y``

where $x$ is assumed to be a matrix of size dims, and f is assumed to be a linear map over Type.

Note: I haven't really considered the proper semantics when type(x) is not necessarily equal to type(y), and the behaviour of this function may (will) change when I do.

gröbner_basis = gwv(monomialorder, polynomials)

An implementation of the GWV algorithm as popularized by

Shuhong Gao, Frank Volny, and Mingsheng Wang. "A new algorithm for computing Groebner bases." IACR Cryptology ePrint Archive 2010 (2010): 641.

AbstractMonomial{Order}

The abstract base type for multi-variate monomials.

Specifying a monomial is equivalent to specifying the exponents for all variables. The concrete type decides whether this happens as a tuple or as a (sparse or dense) array.

The type also encodes the monomial order, and as part of that, the names of the variables.

Each concrete implementation M should implement for elements m:

exp(M, exponents, deg=sum(exponents))
exponents(scheme::NamingScheme, m::M)
exptype(M)

In addition, one may choose to add specific optimizations by overloading other functions, as well.

TupleMonomial{N, I, Order} <: AbstractMonomial where I <: Integer where Order

An implementation of AbstractMonomial that stores exponents as a tuple of integers. This is a dense representation.

VectorMonomial{V,I,Order} <: AbstractMonomial where V <: AbstractVector{I} where I <: Integer where Order

An implementation of AbstractMonomial that stores exponents as a vector of integers. This can be a sparse or dense representation, depending on the type specialization.

This representation is intended for the case when the number of variables is unbounded. In particular, the indexing operation m[i] returns 0 when i is out-of-bounds, instead of throwing an exception.

Term{M, C} where M <: AbstractMonomial where C

This type represents a single term of a multivariate polynomial: that is, it represents the combination of a coefficient and a monomial.

f(var1=...,var2=...)

Substitute variables with Numbers