Introduction
What is Algebraeon?
Algebraeon is a computer algebra system written in Rust.
This guide is for the Python module algebraeon which provides a more user-friendly interface to the capabilities of Algebraeon.
Stability
The API is subject to large breaking changes at this time. I hope to stabilize things more in the not too distant future.
Installation
The latest version can be installed with pip
pip install algebraeon
There are no other dependencies. Most platforms should be supported.
Links
Numbers
Naturals, Integers, and Rationals
Algebraeon provides Nat, Int, and Rat types for representing natural numbers, integers, and rational numbers respectively.
Constructing Numbers
The types can all be constructed using the primitive int type.
from algebraeon import *
# Construct a `Nat` from non-negative primitive `int`s.
Nat(0)
Nat(7)
# ValueError because it is possible to construct a
# `Nat` from a non-negative primitive `int`.
try:
Nat(-5)
except ValueError:
pass
else:
raise Exception()
# Construct an `Int` from primitive `int`s.
Int(-7)
Int(0)
Int(7)
# Construct a `Rat` from primitive `int`s.
Rat(-7)
Rat(0)
Rat(7)
Rat(2, 3) # 2/3
Rational numbers can also be constructed from instaces of Fraction from the fractions module of the standard library.
from algebraeon import *
import fractions
assert(Rat(fractions.Fraction(3, 5)) == Rat(3) / Rat(5))
They can also be implicitly casted to larger sets, but not to smaller ones.
from algebraeon import *
# Creating numbers in a larger set from numbers in a smaller set.
Int(Nat(5))
Rat(Nat(5))
Rat(Int(-5))
# Numbers can be created from the same set too.
Nat(Nat(3))
Int(Int(-3))
Rat(Rat(3))
# Explicit casting from a larger set to a smaller set is allowed.
Nat(Int(5))
try:
Nat(Int(-5))
except ValueError:
pass
else:
raise Exception()
Operations
The usual operations are defined for Algebraeon’s number types.
For operations involving more than one number, the type of the result is the largest of the input types. For example, adding a Nat to an Int produces an Int.
from algebraeon import *
# The type of the result is the largest of the input types.
assert((Nat(2) + Int(3)).set() == Int)
assert(Int(4) + 5 == Rat(9))
assert(Int(-3) ** 3 == -27)
Division exampes:
from algebraeon import *
# Integer division is ok as long as the result is an integer.
assert(Int(6) / Int(2) == 3)
try:
Int(7) / Int(3)
except ValueError:
pass
else:
raise Exception()
# Rational division is ok, as long as we're not dividing by 0.
assert(Rat(6) / Rat(2) == 3)
assert(Rat(7) / Rat(3) == Rat(7, 3))
# Division by 0 raises a `ValueError`.
try:
Int(2) / Int(0)
except ValueError:
pass
else:
raise Exception()
Modular Arithmetic
Operations modulo \(10\).
from algebraeon import *
mod10 = Int.mod(10)
assert(mod10(7) + mod10(8) == mod10(5))
assert(mod10(3) - mod10(8) == mod10(5))
assert(mod10(8) * mod10(9) == mod10(2))
assert(mod10(3) ** 555 == mod10(7))
Modular inverses
from algebraeon import *
# 3 * 21 = 1 mod 31
mod31 = Int.mod(31)
assert(mod31(3) ** -1 == mod31(21))
# 5 * 13 = 1 mod 16
mod16 = Int.mod(16)
assert(mod16(5) ** -1 == mod16(13))
# 4 has no inverse mod 12
mod12 = Int.mod(12)
try:
mod12(4) ** -1
except ValueError:
pass
else:
raise Exception()
Automatic casting between moduli.
from algebraeon import *
mod10 = Int.mod(10)
mod100 = Int.mod(100)
assert(mod100(71) + mod10(8) == 9)
Prime Numbers
Nat.primes() gives an iterator over all prime numbers.
from algebraeon import *
primes = Nat.primes()
for i in range(5):
print(f"prime #{i+1} = {next(primes)}")
# Output
"""
prime #1 = 2
prime #2 = 3
prime #3 = 5
prime #4 = 7
prime #5 = 11
"""
Factoring Natural Numbers
Factoring natural numbers:
from algebraeon import *
assert(Nat(12).factor().primes() == [2, 2, 3])
assert(Nat(12).factor().distinct_primes() == [2, 3])
assert(Nat(12).factor().powers() == {2 : 2, 3 : 1})
assert(Nat(0).factor().primes() is None)
assert(Nat(0).factor().distinct_primes() is None)
assert(Nat(0).factor().powers() is None)
# We can factor numbers much bigger than a naive algorithm is capable of
assert(
Nat(706000565581575429997696139445280900).factor().powers()
== {2: 2, 5: 2, 6988699669998001: 1, 1010203040506070809: 1}
)
Checking if a natural number is prime
from algebraeon import *
assert(not Nat(0).is_prime())
assert(not Nat(1).is_prime())
assert(Nat(2).is_prime())
assert(Nat(3).is_prime())
assert(not Nat(4).is_prime())
# The numbers from the factoring example above
assert(Nat(6988699669998001).is_prime())
assert(Nat(1010203040506070809).is_prime())
assert(not Nat(706000565581575429997696139445280900).is_prime())
Factoring Integers
Factoring integers:
from algebraeon import *
assert(Int(12).factor().sign() == 1)
assert(Int(12).factor().primes() == [2, 2, 3])
assert(Int(12).factor().distinct_primes() == [2, 3])
assert(Int(12).factor().powers() == {2 : 2, 3 : 1})
assert(Int(-12).factor().sign() == -1)
assert(Int(-12).factor().primes() == [2, 2, 3])
assert(Int(-12).factor().distinct_primes() == [2, 3])
assert(Int(-12).factor().powers() == {2 : 2, 3 : 1})
assert(Int(0).factor().sign() == 0)
assert(Int(0).factor().primes() is None)
assert(Int(0).factor().distinct_primes() is None)
assert(Int(0).factor().powers() is None)
Checking if an integer is prime
from algebraeon import *
assert(not Int(-4).is_prime())
assert(Int(-3).is_prime())
assert(Int(-2).is_prime())
assert(not Int(-1).is_prime())
assert(not Int(0).is_prime())
assert(not Int(1).is_prime())
assert(Int(2).is_prime())
assert(Int(3).is_prime())
assert(not Int(4).is_prime())
Polynomials
Integer Polynomials
from algebraeon import *
x = Int.Poly().var()
assert((x + 2) ** 2 == x**2 + 4*x + 4)
assert((x**2 + 3*x + 2) / (x + 1) == x + 2)
# not divisible
try:
x / (2 * x)
except ValueError:
pass
else:
raise Exception()
Rational Polynomials
from algebraeon import *
x = Rat.Poly().var()
assert((x + 2) ** 2 == x**2 + 4*x + 4)
assert((x**2 + 3*x + 2) / (x + 1) == x + 2)
assert(x / (2 * x) == Rat(1, 2))
Polynomials Over the Natural Numbers
from algebraeon import *
x = Nat.Poly().var()
assert((x + 2) ** 2 == x**2 + 4*x + 4)
Factoring Integer Polynomials
from algebraeon import *
x = Int.Poly().var()
poly = -12 * x**2 + 60*x - 72
poly_factored = poly.factor()
print(f"poly =", poly)
print(f"poly_factored =", poly_factored)
# A list of the irreducible factors with their multiplicity
print(f".powers() =", poly_factored.powers())
# A list of the irreducible factors with repetitions
print(f".irreducibles() =", poly_factored.irreducibles())
# A list of the irreducible factors without repetitions
print(f".distinct_irreducibles() =", poly_factored.distinct_irreducibles())
# The integer part of the factorisation
print(f".content() =", poly_factored.content())
# The primitive polynomial part of the factorisation
print(f".primitive() =", poly_factored.primitive())
"""
Output:
poly = -12λ^2+60λ-72
poly_factored = -1 * (2)^2 * (3) * (λ-2) * (λ-3)
.powers() = [(Polynomial(2, Int), 2), (Polynomial(3, Int), 1), (Polynomial(λ-2, Int), 1), (Polynomial(λ-3, Int), 1)]
.irreducibles() = [Polynomial(2, Int), Polynomial(2, Int), Polynomial(3, Int), Polynomial(λ-2, Int), Polynomial(λ-3, Int)]
.distinct_irreducibles() = [Polynomial(2, Int), Polynomial(3, Int), Polynomial(λ-2, Int), Polynomial(λ-3, Int)]
.content() = - 2^2 × 3
.primitive() = 1 * (λ-2) * (λ-3)
"""
Algebraic Numbers
Real Algebraic
Algebraeon provides RealAlg for representing real algebraic numbers.
Real Roots of Polynomials
Real algebraic numbers can be obtained from polynomials.
from algebraeon import *
x = Int.Poly().var()
f = (x ** 3 - 2 * x) ** 2 * (x ** 2 + 1)
print("all roots : ", RealAlg.roots(f))
print("distinct roots : ", RealAlg.distinct_roots(f))
# Output:
"""
all roots : [RealAlg(0), RealAlg(0), RealAlg(-√2), RealAlg(-√2), RealAlg(√2), RealAlg(√2)]
distinct roots : [RealAlg(0), RealAlg(-√2), RealAlg(√2)]
"""
Arithmetic Operations
Standard arithmetic operations are implemented for real algebraic numbers.
from algebraeon import *
x = Int.Poly().var()
f = (x ** 3 - 2 * x) * (x ** 4 - 3)
for root in RealAlg.distinct_roots(f):
print("root =", root)
print(" root^2+1 =", root ** 2 + 1)
# Output:
"""
root = 0
root^2+1 = 1
root = -√2
root^2+1 = 3
root = √2
root^2+1 = 3
root = ≈-1.315
root^2+1 = 1+√3
root = ≈1.315
root^2+1 = 1+√3
"""
Minimal Polynomial and Isolating Interval
.is_rational()returnsTrueorFalsedepending upon whether it is a rational number..minimal_polynomial()returns the rational monic minimal polynomial..isolate()may return different things depending on the number:- If the number is rational, it returns the number as a
Rat. - If the number is irrational, it returns an open rational isolating interval \((a, b)\) such that the real algebraic number is the unique root of its minimal polynomial within the interval.
- If the number is rational, it returns the number as a
from algebraeon import *
x = Int.Poly().var()
f = (x ** 3 - 2 * x) * (x ** 4 - 3)
for root in RealAlg.distinct_roots(f):
print("root:", root)
print(f" is_rational : {root.is_rational()}")
print(f" minimal_polynomial: {root.minimal_polynomial()}")
print(f" isolate : {repr(root.isolate())}")
# Output:
"""
root: 0
is_rational : True
minimal_polynomial: λ
isolate : Rat(0)
root: -√2
is_rational : False
minimal_polynomial: λ^2-2
isolate : (Rat(-4), Rat(0))
root: √2
is_rational : False
minimal_polynomial: λ^2-2
isolate : (Rat(0), Rat(4))
root: ≈-1.315
is_rational : False
minimal_polynomial: λ^4-3
isolate : (Rat(-5), Rat(0))
root: ≈1.315
is_rational : False
minimal_polynomial: λ^4-3
isolate : (Rat(0), Rat(5))
"""
Rational Approximation
x.approximate(r)returns a rational number \(y\) such that \(|x - y| < r\).
from algebraeon import *
x = Int.Poly().var()
f = x**5 - x + 1
for root in RealAlg.distinct_roots(f):
print("root:", root)
print(f" approximate: {root.approximate(Rat(1, 10 ** 10))}")
# Output
"""
root: ≈-1.172
approximate: -271383/232487
"""
Complex Algebraic
Algebraeon provides CpxAlg for representing complex algebraic numbers.
Complex Roots of Polynomials
Complex algebraic numbers can be obtained from polynomials.
from algebraeon import *
x = Int.Poly().var()
f = (x ** 3 - 2 * x) ** 2 * (x ** 2 + 1)
print("all roots : ", CpxAlg.roots(f))
print("distinct roots : ", CpxAlg.distinct_roots(f))
# Output:
"""
all roots : [RealAlg(-i), RealAlg(i), RealAlg(0), RealAlg(0), RealAlg(-√2), RealAlg(-√2), RealAlg(√2), RealAlg(√2)]
distinct roots : [RealAlg(0), RealAlg(-√2), RealAlg(√2), RealAlg(-i), RealAlg(i)]
"""
Arithmetic Operations
Standard arithmetic operations are implemented for complex algebraic numbers.
from algebraeon import *
x = Int.Poly().var()
f = (x ** 3 - 2 * x) * (x ** 4 + 3)
for root in CpxAlg.distinct_roots(f):
print("root =", root)
print(" root^2+1 =", root ** 2 + 1)
# Output:
"""
root = 0
root^2+1 = 1
root = -√2
root^2+1 = 3
root = √2
root^2+1 = 3
root = ≈-0.931-0.931i
root^2+1 = 1+i√3
root = ≈-0.931+0.931i
root^2+1 = 1-i√3
root = ≈0.931-0.931i
root^2+1 = 1-i√3
root = ≈0.931+0.931i
root^2+1 = 1+i√3
"""
Minimal Polynomial and Isolating Box
.is_rational()returnsTrueorFalsedepending upon whether it is a rational number..is_real()returnsTrueorFalsedepending upon whether it is a real number..minimal_polynomial()returns the rational monic minimal polynomial..isolate()may return different things depending on the number:- If the number is rational, it returns the number as a
Rat. - If the number is irrational and real, it returns an open rational isolating interval \((a, b)\) such that the real algebraic number is the unique root of its minimal polynomial within the interval.
- If the number is irrational and complex, it returns a pair of open intervals \((a, b)\) and \((c, d)\) such that the real algebraic number \(z\) is the unique root of its minimal polynomial with \(a < \operatorname{Re}(z) < b\) and \(c < \operatorname{Im}(z) < d\).
- If the number is rational, it returns the number as a
from algebraeon import *
x = Int.Poly().var()
f = (x ** 3 - 2 * x) * (x ** 4 + 3)
for root in CpxAlg.distinct_roots(f):
print("root:", root)
print(f" is_rational : {root.is_rational()}")
print(f" is_real : {root.is_real()}")
print(f" minimal_polynomial: {root.minimal_polynomial()}")
print(f" isolate : {repr(root.isolate())}")
# Output:
"""
root: 0
is_rational : True
is_real : True
minimal_polynomial: λ
isolate : Rat(0)
root: -√2
is_rational : False
is_real : True
minimal_polynomial: λ^2-2
isolate : (Rat(-4), Rat(0))
root: √2
is_rational : False
is_real : True
minimal_polynomial: λ^2-2
isolate : (Rat(0), Rat(4))
root: ≈-0.931-0.931i
is_rational : False
is_real : False
minimal_polynomial: λ^4+3
isolate : ((Rat(-1), Rat(0)), (Rat(-2), Rat(-1/2)))
root: ≈-0.931+0.931i
is_rational : False
is_real : False
minimal_polynomial: λ^4+3
isolate : ((Rat(-1), Rat(0)), (Rat(1/2), Rat(2)))
root: ≈0.931-0.931i
is_rational : False
is_real : False
minimal_polynomial: λ^4+3
isolate : ((Rat(0), Rat(1)), (Rat(-2), Rat(-1/2)))
root: ≈0.931+0.931i
is_rational : False
is_real : False
minimal_polynomial: λ^4+3
isolate : ((Rat(0), Rat(1)), (Rat(1/2), Rat(2)))
"""
Rational Approximation
x.approximate(r)returns a complex number \(y\) as a pair of rational numbers representing the real and imaginary parts such that \(|x - y| < r\).
from algebraeon import *
x = Int.Poly().var()
f = x**5 - x + 1
for root in CpxAlg.distinct_roots(f):
print("root:", root)
print(f" approximate: {root.approximate(Rat(1, 10 ** 10))}")
# Output
"""
root: ≈-1.172
approximate: (Rat(-210940/180707), Rat(0))
root: ≈-0.179-1.087i
approximate: (Rat(-13614/75119), Rat(-35714285333/32948152776))
root: ≈-0.179+1.087i
approximate: (Rat(-13614/75119), Rat(35714285333/32948152776))
root: ≈0.767-0.352i
approximate: (Rat(79125/103447), Rat(-19928216461/56538511220))
root: ≈0.767+0.352i
approximate: (Rat(79125/103447), Rat(19928216461/56538511220))
"""
\(p\)-Adic Algebraic
Algebraeon provides PAdicAlg(p) for representing \(p\)-adic algebraic numbers where \(p\) is a prime.
\(p\)-Adic Roots of Polynomials
\(p\)-adic algebraic numbers can be obtained from polynomials.
from algebraeon import *
x = Int.Poly().var()
f = (x - 3) * (4 * x ** 2 - 17) ** 2
print("all roots : ", PAdicAlg(2).roots(f))
print("distinct roots : ", PAdicAlg(2).distinct_roots(f))
# Output:
"""
all roots : [PAdicAlg(2)(...000011), PAdicAlg(2)(...110100.1), PAdicAlg(2)(...110100.1), PAdicAlg(2)(...001011.1), PAdicAlg(2)(...001011.1)]
distinct roots : [PAdicAlg(2)(...000011), PAdicAlg(2)(...110100.1), PAdicAlg(2)(...001011.1)]
"""
Arithmetic Operations
Standard arithmetic operations are implemented for \(p\)-adic algebraic numbers.
from algebraeon import *
x = Int.Poly().var()
f = (x - 3) * (4 * x ** 2 - 17)
for root in PAdicAlg(2).roots(f):
print("root =", root)
print(" root^2+1 =", root ** 2 + 1)
# Output:
"""
root = ...000011
root^2 = ...001001
root = ...110100.1
root^2 = ...000100.01
root = ...001011.1
root^2 = ...000100.01
"""
Minimal Polynomial and Isolating Ball
.is_rational()returnsTrueorFalsedepending upon whether it is a rational number..minimal_polynomial()returns the rational monic minimal polynomial..isolate()may return different things depending on the number:- If the number is rational, it returns the number as a
Rat. - If the number is irrational and real, it returns \((c, v)\) where \(c \in \mathbb{Q}\) is the center of a \(p\)-adic ball and \(v \in \mathbb{Z}\) is the radius of the \(p\)-adic ball specified as a valuation. The ball is such that the irrational \(p\)-adic number is the unique root of its minimal polynomial inside the ball.
- If the number is rational, it returns the number as a
from algebraeon import *
x = Int.Poly().var()
f = (16 * x ** 2 - 17) * (x - 3)
for root in PAdicAlg(2).roots(f):
print("root:", root)
print(f" is_rational : {root.is_rational()}")
print(f" minimal_polynomial: {root.minimal_polynomial()}")
print(f" isolate : {repr(root.isolate())}")
# Output
"""
root: ...000011
is_rational : True
minimal_polynomial: λ-3
isolate : Rat(3)
root: ...111010.01
is_rational : False
minimal_polynomial: 16λ^2-17
isolate : (Rat(1/4), Int(0))
root: ...000101.11
is_rational : False
minimal_polynomial: 16λ^2-17
isolate : (Rat(3/4), Int(0))
"""
Digits and Approximation
There are a few ways to get an approximation of a \(p\)-adic value. There are methods to get arbitrarily many \(p\)-adic digits, and to find a rational number arbitrarily close.
x.digits(v)returns a pair(digits, shift)wheredigitsis a list of natural numbers \(0, \dots, p-1\) making up the digits of the \(p\)-adic expansion of \(x\) up to valuation \(v\).shiftis the valuation of the first digit in the list.x.approximate(v)returns a rational number \(y\) approximating \(x\) in the sense that the valuation of the difference between \(x\) and \(y\) is at least \(v\).
from algebraeon import *
x = Int.Poly().var()
f = (16 * x ** 2 - 17) * (x - 6) * x
for root in PAdicAlg(2).roots(f):
print("root:", root)
print(" digits :", root.digits(3))
print(" approximate:", root.approximate(3))
# Output
"""
root: ...000110
digits : ([Nat(1), Nat(1)], Int(1))
approximate: 6
root: ...000000
digits : ([], Int(3))
approximate: 0
root: ...111010.01
digits : ([Nat(1), Nat(0), Nat(0), Nat(1), Nat(0)], Int(-2))
approximate: 9/4
root: ...000101.11
digits : ([Nat(1), Nat(1), Nat(1), Nat(0), Nat(1)], Int(-2))
approximate: 23/4
"""
Meta
Checking Versions
To check which version of the python library algebraeon is installed:
import algebraeon
assert(algebraeon.algebraeon_python_library_version() == "0.0.3")
To check which version of the Rust library for algebraeon is being used behind the scenes:
import algebraeon
assert(algebraeon.algebraeon_rust_library_version() == "0.0.17")