Factorizations#
The Factorization
class provides a structure for holding quite
general lists of objects with integer multiplicities. These may hold
the results of an arithmetic or algebraic factorization, where the
objects may be primes or irreducible polynomials and the
multiplicities are the (non-zero) exponents in the factorization. For
other types of examples, see below.
Factorization
class objects contain a list
, so can be
printed nicely and be manipulated like a list of prime-exponent pairs,
or easily turned into a plain list. For example, we factor the
integer \(-45\):
sage: F = factor(-45)
>>> from sage.all import *
>>> F = factor(-Integer(45))
This returns an object of type Factorization
:
sage: type(F)
<class 'sage.structure.factorization_integer.IntegerFactorization'>
>>> from sage.all import *
>>> type(F)
<class 'sage.structure.factorization_integer.IntegerFactorization'>
It prints in a nice factored form:
sage: F
-1 * 3^2 * 5
>>> from sage.all import *
>>> F
-1 * 3^2 * 5
There is an underlying list representation, which ignores the unit part:
sage: list(F)
[(3, 2), (5, 1)]
>>> from sage.all import *
>>> list(F)
[(3, 2), (5, 1)]
A Factorization
is not actually a list:
sage: isinstance(F, list)
False
>>> from sage.all import *
>>> isinstance(F, list)
False
However, we can access the Factorization
F itself as if it were a list:
sage: F[0]
(3, 2)
sage: F[1]
(5, 1)
>>> from sage.all import *
>>> F[Integer(0)]
(3, 2)
>>> F[Integer(1)]
(5, 1)
To get at the unit part, use the Factorization.unit()
function:
sage: F.unit()
-1
>>> from sage.all import *
>>> F.unit()
-1
All factorizations are immutable, up to ordering with sort()
and
simplifying with simplify()
. Thus if you write a function that
returns a cached version of a factorization, you do not have to return
a copy.
sage: F = factor(-12); F
-1 * 2^2 * 3
sage: F[0] = (5,4)
Traceback (most recent call last):
...
TypeError: 'Factorization' object does not support item assignment
>>> from sage.all import *
>>> F = factor(-Integer(12)); F
-1 * 2^2 * 3
>>> F[Integer(0)] = (Integer(5),Integer(4))
Traceback (most recent call last):
...
TypeError: 'Factorization' object does not support item assignment
EXAMPLES:
This more complicated example involving polynomials also illustrates that the unit part is not discarded from factorizations:
sage: # needs sage.libs.pari
sage: x = QQ['x'].0
sage: f = -5*(x-2)*(x-3)
sage: f
-5*x^2 + 25*x - 30
sage: F = f.factor(); F
(-5) * (x - 3) * (x - 2)
sage: F.unit()
-5
sage: F.value()
-5*x^2 + 25*x - 30
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> x = QQ['x'].gen(0)
>>> f = -Integer(5)*(x-Integer(2))*(x-Integer(3))
>>> f
-5*x^2 + 25*x - 30
>>> F = f.factor(); F
(-5) * (x - 3) * (x - 2)
>>> F.unit()
-5
>>> F.value()
-5*x^2 + 25*x - 30
The underlying list is the list of pairs \((p_i, e_i)\), where each \(p_i\) is a ‘prime’ and each \(e_i\) is an integer. The unit part is discarded by the list:
sage: # needs sage.libs.pari
sage: list(F)
[(x - 3, 1), (x - 2, 1)]
sage: len(F)
2
sage: F[1]
(x - 2, 1)
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> list(F)
[(x - 3, 1), (x - 2, 1)]
>>> len(F)
2
>>> F[Integer(1)]
(x - 2, 1)
In the ring \(\ZZ[x]\), the integer \(-5\) is not a unit, so the factorization has three factors:
sage: # needs sage.libs.pari
sage: x = ZZ['x'].0
sage: f = -5*(x-2)*(x-3)
sage: f
-5*x^2 + 25*x - 30
sage: F = f.factor(); F
(-1) * 5 * (x - 3) * (x - 2)
sage: F.universe()
Univariate Polynomial Ring in x over Integer Ring
sage: F.unit()
-1
sage: list(F)
[(5, 1), (x - 3, 1), (x - 2, 1)]
sage: F.value()
-5*x^2 + 25*x - 30
sage: len(F)
3
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> x = ZZ['x'].gen(0)
>>> f = -Integer(5)*(x-Integer(2))*(x-Integer(3))
>>> f
-5*x^2 + 25*x - 30
>>> F = f.factor(); F
(-1) * 5 * (x - 3) * (x - 2)
>>> F.universe()
Univariate Polynomial Ring in x over Integer Ring
>>> F.unit()
-1
>>> list(F)
[(5, 1), (x - 3, 1), (x - 2, 1)]
>>> F.value()
-5*x^2 + 25*x - 30
>>> len(F)
3
On the other hand, -1 is a unit in \(\ZZ\), so it is included in the unit:
sage: # needs sage.libs.pari
sage: x = ZZ['x'].0
sage: f = -1 * (x-2) * (x-3)
sage: F = f.factor(); F
(-1) * (x - 3) * (x - 2)
sage: F.unit()
-1
sage: list(F)
[(x - 3, 1), (x - 2, 1)]
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> x = ZZ['x'].gen(0)
>>> f = -Integer(1) * (x-Integer(2)) * (x-Integer(3))
>>> F = f.factor(); F
(-1) * (x - 3) * (x - 2)
>>> F.unit()
-1
>>> list(F)
[(x - 3, 1), (x - 2, 1)]
Factorizations can involve fairly abstract mathematical objects:
sage: # needs sage.modular
sage: F = ModularSymbols(11,4).factorization(); F
(Modular Symbols subspace of dimension 2 of Modular Symbols space
of dimension 6 for Gamma_0(11) of weight 4 with sign 0 over Rational Field) *
(Modular Symbols subspace of dimension 2 of Modular Symbols space
of dimension 6 for Gamma_0(11) of weight 4 with sign 0 over Rational Field) *
(Modular Symbols subspace of dimension 2 of Modular Symbols space
of dimension 6 for Gamma_0(11) of weight 4 with sign 0 over Rational Field)
sage: type(F)
<class 'sage.structure.factorization.Factorization'>
sage: # needs sage.rings.number_field
sage: x = ZZ['x'].0
sage: K.<a> = NumberField(x^2 + 3); K
Number Field in a with defining polynomial x^2 + 3
sage: f = K.factor(15); f
(Fractional ideal (1/2*a + 3/2))^2 * (Fractional ideal (5))
sage: f.universe()
Monoid of ideals of Number Field in a with defining polynomial x^2 + 3
sage: f.unit()
Fractional ideal (1)
sage: g = K.factor(9); g
(Fractional ideal (1/2*a + 3/2))^4
sage: f.lcm(g)
(Fractional ideal (1/2*a + 3/2))^4 * (Fractional ideal (5))
sage: f.gcd(g)
(Fractional ideal (1/2*a + 3/2))^2
sage: f.is_integral()
True
>>> from sage.all import *
>>> # needs sage.modular
>>> F = ModularSymbols(Integer(11),Integer(4)).factorization(); F
(Modular Symbols subspace of dimension 2 of Modular Symbols space
of dimension 6 for Gamma_0(11) of weight 4 with sign 0 over Rational Field) *
(Modular Symbols subspace of dimension 2 of Modular Symbols space
of dimension 6 for Gamma_0(11) of weight 4 with sign 0 over Rational Field) *
(Modular Symbols subspace of dimension 2 of Modular Symbols space
of dimension 6 for Gamma_0(11) of weight 4 with sign 0 over Rational Field)
>>> type(F)
<class 'sage.structure.factorization.Factorization'>
>>> # needs sage.rings.number_field
>>> x = ZZ['x'].gen(0)
>>> K = NumberField(x**Integer(2) + Integer(3), names=('a',)); (a,) = K._first_ngens(1); K
Number Field in a with defining polynomial x^2 + 3
>>> f = K.factor(Integer(15)); f
(Fractional ideal (1/2*a + 3/2))^2 * (Fractional ideal (5))
>>> f.universe()
Monoid of ideals of Number Field in a with defining polynomial x^2 + 3
>>> f.unit()
Fractional ideal (1)
>>> g = K.factor(Integer(9)); g
(Fractional ideal (1/2*a + 3/2))^4
>>> f.lcm(g)
(Fractional ideal (1/2*a + 3/2))^4 * (Fractional ideal (5))
>>> f.gcd(g)
(Fractional ideal (1/2*a + 3/2))^2
>>> f.is_integral()
True
AUTHORS:
William Stein (2006-01-22): added unit part as suggested by David Kohel.
William Stein (2008-01-17): wrote much of the documentation and fixed a couple of bugs.
Nick Alexander (2008-01-19): added support for non-commuting factors.
John Cremona (2008-08-22): added division, lcm, gcd, is_integral and universe functions
- class sage.structure.factorization.Factorization(x, unit=None, cr=False, sort=True, simplify=True)[source]#
Bases:
SageObject
A formal factorization of an object.
EXAMPLES:
sage: N = 2006 sage: F = N.factor(); F 2 * 17 * 59 sage: F.unit() 1 sage: F = factor(-2006); F -1 * 2 * 17 * 59 sage: F.unit() -1 sage: loads(F.dumps()) == F True sage: F = Factorization([(x, 1/3)]) # needs sage.symbolic Traceback (most recent call last): ... TypeError: no conversion of this rational to integer
>>> from sage.all import * >>> N = Integer(2006) >>> F = N.factor(); F 2 * 17 * 59 >>> F.unit() 1 >>> F = factor(-Integer(2006)); F -1 * 2 * 17 * 59 >>> F.unit() -1 >>> loads(F.dumps()) == F True >>> F = Factorization([(x, Integer(1)/Integer(3))]) # needs sage.symbolic Traceback (most recent call last): ... TypeError: no conversion of this rational to integer
- base_change(U)[source]#
Return the factorization
self
, with its factors (including the unit part) coerced into the universe \(U\).EXAMPLES:
sage: F = factor(2006) sage: F.universe() Integer Ring sage: P.<x> = ZZ[] sage: F.base_change(P).universe() Univariate Polynomial Ring in x over Integer Ring
>>> from sage.all import * >>> F = factor(Integer(2006)) >>> F.universe() Integer Ring >>> P = ZZ['x']; (x,) = P._first_ngens(1) >>> F.base_change(P).universe() Univariate Polynomial Ring in x over Integer Ring
This method will return a
TypeError
if the coercion is not possible:sage: g = x^2 - 1 sage: F = factor(g); F # needs sage.libs.pari (x - 1) * (x + 1) sage: F.universe() # needs sage.libs.pari Univariate Polynomial Ring in x over Integer Ring sage: F.base_change(ZZ) # needs sage.libs.pari Traceback (most recent call last): ... TypeError: Impossible to coerce the factors of (x - 1) * (x + 1) into Integer Ring
>>> from sage.all import * >>> g = x**Integer(2) - Integer(1) >>> F = factor(g); F # needs sage.libs.pari (x - 1) * (x + 1) >>> F.universe() # needs sage.libs.pari Univariate Polynomial Ring in x over Integer Ring >>> F.base_change(ZZ) # needs sage.libs.pari Traceback (most recent call last): ... TypeError: Impossible to coerce the factors of (x - 1) * (x + 1) into Integer Ring
- expand()[source]#
Return the product of the factors in the factorization, multiplied out.
EXAMPLES:
sage: F = factor(-2006); F -1 * 2 * 17 * 59 sage: F.value() -2006 sage: R.<x,y> = FreeAlgebra(ZZ, 2) # needs sage.combinat sage.modules sage: F = Factorization([(x,3), (y, 2), (x,1)]); F # needs sage.combinat sage.modules x^3 * y^2 * x sage: F.value() # needs sage.combinat sage.modules x^3*y^2*x
>>> from sage.all import * >>> F = factor(-Integer(2006)); F -1 * 2 * 17 * 59 >>> F.value() -2006 >>> R = FreeAlgebra(ZZ, Integer(2), names=('x', 'y',)); (x, y,) = R._first_ngens(2)# needs sage.combinat sage.modules >>> F = Factorization([(x,Integer(3)), (y, Integer(2)), (x,Integer(1))]); F # needs sage.combinat sage.modules x^3 * y^2 * x >>> F.value() # needs sage.combinat sage.modules x^3*y^2*x
- gcd(other)[source]#
Return the gcd of two factorizations.
If the two factorizations have different universes, this method will attempt to find a common universe for the gcd. A
TypeError
is raised if this is impossible.EXAMPLES:
sage: factor(-30).gcd(factor(-160)) 2 * 5 sage: factor(gcd(-30,160)) 2 * 5 sage: R.<x> = ZZ[] sage: (factor(-20).gcd(factor(5*x+10))).universe() # needs sage.libs.pari Univariate Polynomial Ring in x over Integer Ring
>>> from sage.all import * >>> factor(-Integer(30)).gcd(factor(-Integer(160))) 2 * 5 >>> factor(gcd(-Integer(30),Integer(160))) 2 * 5 >>> R = ZZ['x']; (x,) = R._first_ngens(1) >>> (factor(-Integer(20)).gcd(factor(Integer(5)*x+Integer(10)))).universe() # needs sage.libs.pari Univariate Polynomial Ring in x over Integer Ring
- is_commutative()[source]#
Return whether the factors commute.
EXAMPLES:
sage: F = factor(2006) sage: F.is_commutative() True sage: # needs sage.rings.number_field sage: K = QuadraticField(23, 'a') sage: F = K.factor(13) sage: F.is_commutative() True sage: # needs sage.combinat sage.modules sage: R.<x,y,z> = FreeAlgebra(QQ, 3) sage: F = Factorization([(z, 2)], 3) sage: F.is_commutative() False sage: (F*F^-1).is_commutative() False
>>> from sage.all import * >>> F = factor(Integer(2006)) >>> F.is_commutative() True >>> # needs sage.rings.number_field >>> K = QuadraticField(Integer(23), 'a') >>> F = K.factor(Integer(13)) >>> F.is_commutative() True >>> # needs sage.combinat sage.modules >>> R = FreeAlgebra(QQ, Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3) >>> F = Factorization([(z, Integer(2))], Integer(3)) >>> F.is_commutative() False >>> (F*F**-Integer(1)).is_commutative() False
- is_integral()[source]#
Return whether all exponents of this Factorization are non-negative.
EXAMPLES:
sage: F = factor(-10); F -1 * 2 * 5 sage: F.is_integral() True sage: F = factor(-10) / factor(16); F -1 * 2^-3 * 5 sage: F.is_integral() False
>>> from sage.all import * >>> F = factor(-Integer(10)); F -1 * 2 * 5 >>> F.is_integral() True >>> F = factor(-Integer(10)) / factor(Integer(16)); F -1 * 2^-3 * 5 >>> F.is_integral() False
- lcm(other)[source]#
Return the lcm of two factorizations.
If the two factorizations have different universes, this method will attempt to find a common universe for the lcm. A
TypeError
is raised if this is impossible.EXAMPLES:
sage: factor(-10).lcm(factor(-16)) 2^4 * 5 sage: factor(lcm(-10,16)) 2^4 * 5 sage: R.<x> = ZZ[] sage: (factor(-20).lcm(factor(5*x + 10))).universe() # needs sage.libs.pari Univariate Polynomial Ring in x over Integer Ring
>>> from sage.all import * >>> factor(-Integer(10)).lcm(factor(-Integer(16))) 2^4 * 5 >>> factor(lcm(-Integer(10),Integer(16))) 2^4 * 5 >>> R = ZZ['x']; (x,) = R._first_ngens(1) >>> (factor(-Integer(20)).lcm(factor(Integer(5)*x + Integer(10)))).universe() # needs sage.libs.pari Univariate Polynomial Ring in x over Integer Ring
- prod()[source]#
Return the product of the factors in the factorization, multiplied out.
EXAMPLES:
sage: F = factor(-2006); F -1 * 2 * 17 * 59 sage: F.value() -2006 sage: R.<x,y> = FreeAlgebra(ZZ, 2) # needs sage.combinat sage.modules sage: F = Factorization([(x,3), (y, 2), (x,1)]); F # needs sage.combinat sage.modules x^3 * y^2 * x sage: F.value() # needs sage.combinat sage.modules x^3*y^2*x
>>> from sage.all import * >>> F = factor(-Integer(2006)); F -1 * 2 * 17 * 59 >>> F.value() -2006 >>> R = FreeAlgebra(ZZ, Integer(2), names=('x', 'y',)); (x, y,) = R._first_ngens(2)# needs sage.combinat sage.modules >>> F = Factorization([(x,Integer(3)), (y, Integer(2)), (x,Integer(1))]); F # needs sage.combinat sage.modules x^3 * y^2 * x >>> F.value() # needs sage.combinat sage.modules x^3*y^2*x
- radical()[source]#
Return the factorization of the radical of the value of
self
.First, check that all exponents in the factorization are positive, raise
ValueError
otherwise. If all exponents are positive, returnself
with all exponents set to 1 and with the unit set to 1.EXAMPLES:
sage: F = factor(-100); F -1 * 2^2 * 5^2 sage: F.radical() 2 * 5 sage: factor(1/2).radical() Traceback (most recent call last): ... ValueError: all exponents in the factorization must be positive
>>> from sage.all import * >>> F = factor(-Integer(100)); F -1 * 2^2 * 5^2 >>> F.radical() 2 * 5 >>> factor(Integer(1)/Integer(2)).radical() Traceback (most recent call last): ... ValueError: all exponents in the factorization must be positive
- radical_value()[source]#
Return the product of the prime factors in
self
.First, check that all exponents in the factorization are positive, raise
ValueError
otherwise. If all exponents are positive, return the product of the prime factors inself
. This should be functionally equivalent toself.radical().value()
.EXAMPLES:
sage: F = factor(-100); F -1 * 2^2 * 5^2 sage: F.radical_value() 10 sage: factor(1/2).radical_value() Traceback (most recent call last): ... ValueError: all exponents in the factorization must be positive
>>> from sage.all import * >>> F = factor(-Integer(100)); F -1 * 2^2 * 5^2 >>> F.radical_value() 10 >>> factor(Integer(1)/Integer(2)).radical_value() Traceback (most recent call last): ... ValueError: all exponents in the factorization must be positive
- sort(key=None)[source]#
Sort the factors in this factorization.
INPUT:
key
– (default:None
); comparison key
OUTPUT:
changes this factorization to be sorted (inplace)
If
key
isNone
, we determine the comparison key as follows:If the prime in the first factor has a dimension method, then we sort based first on dimension then on the exponent.
If there is no dimension method, we next attempt to sort based on a degree method, in which case, we sort based first on degree, then exponent to break ties when two factors have the same degree, and if those match break ties based on the actual prime itself.
Otherwise, we sort according to the prime itself.
EXAMPLES:
We create a factored polynomial:
sage: x = polygen(QQ, 'x') sage: F = factor(x^3 + 1); F # needs sage.libs.pari (x + 1) * (x^2 - x + 1)
>>> from sage.all import * >>> x = polygen(QQ, 'x') >>> F = factor(x**Integer(3) + Integer(1)); F # needs sage.libs.pari (x + 1) * (x^2 - x + 1)
We sort it by decreasing degree:
sage: F.sort(key=lambda x: (-x[0].degree(), x)) # needs sage.libs.pari sage: F # needs sage.libs.pari (x^2 - x + 1) * (x + 1)
>>> from sage.all import * >>> F.sort(key=lambda x: (-x[Integer(0)].degree(), x)) # needs sage.libs.pari >>> F # needs sage.libs.pari (x^2 - x + 1) * (x + 1)
- subs(*args, **kwds)[source]#
Implement the substitution.
This is assuming that each term can be substituted.
There is another mechanism for substitution in symbolic products.
EXAMPLES:
sage: # needs sage.combinat sage.modules sage: R.<x,y> = FreeAlgebra(QQ, 2) sage: F = Factorization([(x,3), (y, 2), (x,1)]) sage: F(x=4) (1) * 4^3 * y^2 * 4 sage: F.subs({y:2}) x^3 * 2^2 * x sage: R.<x,y> = PolynomialRing(QQ, 2) sage: F = Factorization([(x,3), (y, 2), (x,1)]) sage: F(x=4) 4 * 4^3 * y^2 sage: F.subs({y:x}) x * x^2 * x^3 sage: F(x=y+x) (x + y) * y^2 * (x + y)^3
>>> from sage.all import * >>> # needs sage.combinat sage.modules >>> R = FreeAlgebra(QQ, Integer(2), names=('x', 'y',)); (x, y,) = R._first_ngens(2) >>> F = Factorization([(x,Integer(3)), (y, Integer(2)), (x,Integer(1))]) >>> F(x=Integer(4)) (1) * 4^3 * y^2 * 4 >>> F.subs({y:Integer(2)}) x^3 * 2^2 * x >>> R = PolynomialRing(QQ, Integer(2), names=('x', 'y',)); (x, y,) = R._first_ngens(2) >>> F = Factorization([(x,Integer(3)), (y, Integer(2)), (x,Integer(1))]) >>> F(x=Integer(4)) 4 * 4^3 * y^2 >>> F.subs({y:x}) x * x^2 * x^3 >>> F(x=y+x) (x + y) * y^2 * (x + y)^3
- unit()[source]#
Return the unit part of this factorization.
EXAMPLES:
We create a polynomial over the real double field and factor it:
sage: x = polygen(RDF, 'x') sage: F = factor(-2*x^2 - 1); F # needs numpy (-2.0) * (x^2 + 0.5000000000000001)
>>> from sage.all import * >>> x = polygen(RDF, 'x') >>> F = factor(-Integer(2)*x**Integer(2) - Integer(1)); F # needs numpy (-2.0) * (x^2 + 0.5000000000000001)
Note that the unit part of the factorization is \(-2.0\):
sage: F.unit() # needs numpy -2.0 sage: F = factor(-2006); F -1 * 2 * 17 * 59 sage: F.unit() -1
>>> from sage.all import * >>> F.unit() # needs numpy -2.0 >>> F = factor(-Integer(2006)); F -1 * 2 * 17 * 59 >>> F.unit() -1
- universe()[source]#
Return the parent structure of my factors.
Note
This used to be called
base_ring
, but the universe of a factorization need not be a ring.EXAMPLES:
sage: F = factor(2006) sage: F.universe() Integer Ring sage: R.<x,y,z> = FreeAlgebra(QQ, 3) # needs sage.combinat sage.modules sage: F = Factorization([(z, 2)], 3) # needs sage.combinat sage.modules sage: (F*F^-1).universe() # needs sage.combinat sage.modules Free Algebra on 3 generators (x, y, z) over Rational Field sage: F = ModularSymbols(11,4).factorization() # needs sage.modular sage: F.universe() # needs sage.modular
>>> from sage.all import * >>> F = factor(Integer(2006)) >>> F.universe() Integer Ring >>> R = FreeAlgebra(QQ, Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)# needs sage.combinat sage.modules >>> F = Factorization([(z, Integer(2))], Integer(3)) # needs sage.combinat sage.modules >>> (F*F**-Integer(1)).universe() # needs sage.combinat sage.modules Free Algebra on 3 generators (x, y, z) over Rational Field >>> F = ModularSymbols(Integer(11),Integer(4)).factorization() # needs sage.modular >>> F.universe() # needs sage.modular
- value()[source]#
Return the product of the factors in the factorization, multiplied out.
EXAMPLES:
sage: F = factor(-2006); F -1 * 2 * 17 * 59 sage: F.value() -2006 sage: R.<x,y> = FreeAlgebra(ZZ, 2) # needs sage.combinat sage.modules sage: F = Factorization([(x,3), (y, 2), (x,1)]); F # needs sage.combinat sage.modules x^3 * y^2 * x sage: F.value() # needs sage.combinat sage.modules x^3*y^2*x
>>> from sage.all import * >>> F = factor(-Integer(2006)); F -1 * 2 * 17 * 59 >>> F.value() -2006 >>> R = FreeAlgebra(ZZ, Integer(2), names=('x', 'y',)); (x, y,) = R._first_ngens(2)# needs sage.combinat sage.modules >>> F = Factorization([(x,Integer(3)), (y, Integer(2)), (x,Integer(1))]); F # needs sage.combinat sage.modules x^3 * y^2 * x >>> F.value() # needs sage.combinat sage.modules x^3*y^2*x