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 example, 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)

This returns an object of type Factorization:

sage: type(F)
<class 'sage.structure.factorization.Factorization'>

It prints in a nice factored form:

sage: F
-1 * 3^2 * 5

There is an underlying list representation, emph{which ignores the unit part} (!).

sage: list(F)
[(3, 2), (5, 1)]

A Factorization is not actually a list:

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

To get at the unit part, use the Factorization.unit() function:

sage: F.unit()
-1

All factorizations are immutable. 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)
...
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: 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: expand(F)   
-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: list(F)
[(x - 3, 1), (x - 2, 1)]
sage: len(F)
2
sage: F[1]
(x - 2, 1)

In the ring \ZZ[x], the integer -5 is not a unit, so the factorization has three factors:

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: expand(F) 
-5*x^2 + 25*x - 30
sage: len(F)
3

On the other hand, -1 is a unit in \ZZ, so it is included in the unit.

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)]

Factorizations can involve fairly abstract mathematical objects:

sage: F = ModularSymbols(11,4).factorization()
sage: 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: 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

TESTS:

sage: F = factor(-20); F
-1 * 2^2 * 5
sage: G = loads(dumps(F)); G
-1 * 2^2 * 5
sage: G == F
True
sage: G is F
False

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)

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)])
...
TypeError: powers of factors must be integers
__add__(other)

Return the (unfactored) sum of self and other.

EXAMPLES:

sage: factor(-10) + 16
6
sage: factor(10) - 16
-6
sage: factor(100) + factor(19)
119
__cmp__(other)

Compare self and other. This compares the underlying lists of self and other (ignoring the unit!)

EXAMPLES: We compare two contrived formal factorizations:

sage: a = Factorization([(2, 7), (5,2), (2, 5)])
sage: b = Factorization([(2, 7), (5,10), (7, 3)])
sage: a
2^12 * 5^2
sage: b
2^7 * 5^10 * 7^3
sage: a < b
True
sage: b < a
False
sage: a.expand()
102400
sage: b.expand()
428750000000

We compare factorizations of some polynomials:

sage: x = polygen(QQ)
sage: x^2 - 1 > x^2 - 4
True
sage: factor(x^2 - 1) > factor(x^2 - 4)
True
__copy__()

Return a copy of self.

This is of course not a deepcopy – only references to the factors are returned, not copies of them. Use deepcopy(self) if you need a deep copy of self.

EXAMPLES: We create a factorization that has mutable primes:

sage: F = Factorization([([1,2], 5), ([5,6], 10)]); F
([1, 2])^5 * ([5, 6])^10

We make a copy of it:

sage: G = copy(F); G
([1, 2])^5 * ([5, 6])^10
sage: G is F
False

Note that if we change one of the mutable “primes” of F, this does change G.

sage: F[1][0][0] = 'hello'
sage: G
([1, 2])^5 * (['hello', 6])^10
__deepcopy__(memo)

Return a deep copy of self.

This is of course not a deepcopy – only references to the factors are returned, not copies of them.

EXAMPLES: We make a factorization that has mutable entries:

sage: F = Factorization([([1,2], 5), ([5,6], 10)]); F
([1, 2])^5 * ([5, 6])^10

Now we make a copy of it and a deep copy:

sage: K = copy(F)
sage: G = deepcopy(F); G
([1, 2])^5 * ([5, 6])^10

We change one of the mutable entries of F:

sage: F[0][0][0] = 10

This of course changes F:

sage: F
([10, 2])^5 * ([5, 6])^10

It also changes the copy K of F:

sage: K
([10, 2])^5 * ([5, 6])^10

It does not change the deep copy G:

sage: G
([1, 2])^5 * ([5, 6])^10
__div__(other)

Return the quotient of two factorizations, which is obtained by multiplying the first by the inverse of the second.

EXAMPLES:

sage: factor(-10) / factor(-16)
2^-3 * 5
sage: factor(-10) / factor(16)
-1 * 2^-3 * 5

sage: R.<x,y> = FreeAlgebra(QQ, 2)
sage: F = Factorization([(x,3), (y, 2), (x,1)]); F
x^3 * y^2 * x
sage: G = Factorization([(y, 1), (x,1)],1); G
y * x
sage: F / G
x^3 * y
__getitem__(i)

Return i^{th} factor of self.

EXAMPLES:

sage: a = factor(-75); a
-1 * 3 * 5^2
sage: a[0]
(3, 1)
sage: a[1]
(5, 2)
sage: a[-1]
(5, 2)
sage: a[5]
...
IndexError: list index out of range
__init__(x, unit=None, cr=False, sort=True, simplify=True)

Create a Factorization object.

INPUT:

  • x - a list of (p, e) pairs with e an integer (or a TypeError is raised).
  • unit - (default: 1) the unit part of the factorization
  • cr - (default: False) if True, print the factorization with carriage returns between factors
  • sort - (default: True) if True, sort the factors by calling the sort function after creating the factorization. See the documentation for self.sort for how this works.

OUTPUT:

  • a Factorization object

EXAMPLES: We create a factorization with all the default options:

sage: Factorization([(2,3), (5, 1)])
2^3 * 5

We create a factorization with a specified unit part:

sage: Factorization([(2,3), (5, 1)], unit=-1)
-1 * 2^3 * 5

We try to create a factorization but with a string an exponent, which results in a TypeError:

sage: Factorization([(2,3), (5, 'x')])
...
TypeError: powers of factors must be integers

We create a factorization that puts newlines after each multiply sign when printing. This is mainly useful when the primes are large.

sage: Factorization([(2,3), (5, 2)], cr=True)
2^3 * 
5^2

Another factorization with newlines and nontrivial unit part (which appears on a line by itself):

sage: Factorization([(2,3), (5, 2)], cr=True, unit=-2)
-2 * 
2^3 * 
5^2

A factorization, but where we do not sort the factors:

sage: Factorization([(5,3), (2, 3)], sort=False)
5^3 * 2^3

By default factorizations are sorted by the prime base (for commutative bases):

sage: Factorization([(2, 7), (5,2), (2, 5)])
2^12 * 5^2
sage: R.<a,b> = FreeAlgebra(QQ,2)
sage: Factorization([(a,1),(b,1),(a,2)])
a * b * a^2

Autosorting (the default) swaps around the factors below:

sage: F = Factorization([(ZZ^3, 2), (ZZ^2, 5)], cr=True); F
(Ambient free module of rank 2 over the principal ideal domain Integer Ring)^5 * 
(Ambient free module of rank 3 over the principal ideal domain Integer Ring)^2            
__invert__()

Return the formal inverse of the factors in the factorization.

EXAMPLES:

sage: F = factor(2006); F
2 * 17 * 59
sage: F^-1
2^-1 * 17^-1 * 59^-1

sage: R.<x,y> = FreeAlgebra(QQ, 2)
sage: F = Factorization([(x,3), (y, 2), (x,1)], 2); F
(2) * x^3 * y^2 * x
sage: F^-1
(1/2) * x^-1 * y^-2 * x^-3
__len__()

Return the number of prime factors of self, not counting the unit part.

EXAMPLES:

sage: len(factor(15))
2

Note that the unit part is not included in the count.

sage: a = factor(-75); a
-1 * 3 * 5^2
sage: len(a)
2
sage: list(a)
[(3, 1), (5, 2)]
sage: len(list(a))
2
__mul__(other)

Return the product of two factorizations, which is obtained by combining together like factors.

If the two factorizations have different universes, this method will attempt to find a common universe for the product. A TypeError is raised if this is impossible.

EXAMPLES:

sage: factor(-10) * factor(-16)
2^5 * 5
sage: factor(-10) * factor(16)
-1 * 2^5 * 5

sage: R.<x,y> = FreeAlgebra(ZZ, 2)
sage: F = Factorization([(x,3), (y, 2), (x,1)]); F
x^3 * y^2 * x
sage: F*F
x^3 * y^2 * x^4 * y^2 * x
sage: -1 * F
(-1) * x^3 * y^2 * x

sage: P.<x> = ZZ[]
sage: f = 2*x + 2
sage: c = f.content(); g = f//c
sage: Fc = factor(c); Fc.universe()
Integer Ring
sage: Fg = factor(g); Fg.universe()
Univariate Polynomial Ring in x over Integer Ring
sage: F = Fc * Fg; F.universe()
Univariate Polynomial Ring in x over Integer Ring
sage: [type(a[0]) for a in F]
[<type 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>,
 <type 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>]
__neg__()

Return negative of this factorization.

EXAMPLES:

sage: a = factor(-75); a
-1 * 3 * 5^2
sage: -a
3 * 5^2
sage: (-a).unit()
1
__pow__(n)

Return the n^{th} power of a factorization, which is got by combining together like factors.

EXAMPLES:

sage: f = factor(-100); f
-1 * 2^2 * 5^2
sage: f^3
-1 * 2^6 * 5^6
sage: f^4
2^8 * 5^8

sage: F = factor(2006); F
2 * 17 * 59
sage: F**2
2^2 * 17^2 * 59^2

sage: R.<x,y> = FreeAlgebra(ZZ, 2)
sage: F = Factorization([(x,3), (y, 2), (x,1)]); F
x^3 * y^2 * x
sage: F**2
x^3 * y^2 * x^4 * y^2 * x
__rmul__(left)

Return the product left * self, where left is not a Factorization.

EXAMPLES:

sage: a = factor(15); a
3 * 5
sage: -2 * a
-2 * 3 * 5
sage: a * -2
-2 * 3 * 5
sage: R.<x,y> = FreeAlgebra(QQ,2)
sage: f = Factorization([(x,2),(y,3)]); f
x^2 * y^3
sage: x * f
x^3 * y^3
sage: f * x
x^2 * y^3 * x
__setitem__(i, v)

Set the i^{th} factor of self.

Warning

NOT ALLOWED – Factorizations are immutable.

EXAMPLES:

sage: a = factor(-75); a
-1 * 3 * 5^2
sage: a[0] = (2,3)
...
TypeError: 'Factorization' object does not support item assignment
__sub__(other)

Return the (unfactored) difference of self and other.

EXAMPLES:

sage: factor(-10) + 16
6
sage: factor(10) - 16
-6
__weakref__
list of weak references to the object (if defined)
_cr()

Return whether or not factorizations are printed with carriage returns between factors.

EXAMPLES: Our first example involves factoring an integer:

sage: F = factor(-93930); F
-1 * 2 * 3 * 5 * 31 * 101
sage: F._cr()
False
sage: F._set_cr(True)
sage: F._cr()
True

This of course looks funny:

sage: F
-1 * 
2 * 
3 * 
5 * 
31 * 
101

Next we factor a modular symbols space:

sage: F = ModularSymbols(11).factor(); F
(Modular Symbols subspace of dimension 1 of ...) * 
(Modular Symbols subspace of dimension 1 of ...) * 
(Modular Symbols subspace of dimension 1 of ...)
_latex_()

Return the LaTeX representation of this factorization.

EXAMPLES:

sage: f = factor(-100); f
-1 * 2^2 * 5^2
sage: latex(f)
-1 \cdot 2^{2} \cdot 5^{2}
sage: f._latex_()
'-1 \\cdot 2^{2} \\cdot 5^{2}'
_repr_()

Return the string representation of this factorization.

EXAMPLES:

sage: f = factor(-100); f
-1 * 2^2 * 5^2
sage: f._repr_()
'-1 * 2^2 * 5^2'

Note that the default printing of a factorization can be overloaded using the rename method.

sage: f.rename('factorization of -100')
sage: f
factorization of -100

However _repr_ always prints normally.

sage: f._repr_()
'-1 * 2^2 * 5^2'

EXAMPLES:

sage: x = polygen(QQ)
sage: Factorization([(x-1,1), (x-2,2)])
 (x - 1) * (x - 2)^2
_set_cr(cr)

Change whether or not the factorization is printed with carriage returns after each factor.

EXAMPLES:

sage: x = polygen(QQ,'x')
sage: F = factor(x^6 - 1); F
(x - 1) * (x + 1) * (x^2 - x + 1) * (x^2 + x + 1)
sage: F._set_cr(True); F
(x - 1) * 
(x + 1) * 
(x^2 - x + 1) * 
(x^2 + x + 1)
sage: F._set_cr(False); F
(x - 1) * (x + 1) * (x^2 - x + 1) * (x^2 + x + 1)
base_change(U)

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            

This method will return a TypeError if the coercion is not possible:

sage: g = x^2 - 1
sage: F = factor(g); F
(x - 1) * (x + 1)
sage: F.universe()
Univariate Polynomial Ring in x over Integer Ring
sage: F.base_change(ZZ)
...
TypeError: Impossible to coerce the factors of (x - 1) * (x + 1) into Integer Ring
expand()

Same as value(), so this returns the product of the factors, multiplied out.

EXAMPLES:

sage: x = polygen(QQ, 'x')
sage: F = factor(-x^5 + 1); F
(-1) * (x - 1) * (x^4 + x^3 + x^2 + x + 1)
sage: F.expand()
-x^5 + 1
gcd(other)

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()
Univariate Polynomial Ring in x over Integer Ring
is_commutative()

Return True if my factors commute.

EXAMPLES:

sage: F = factor(2006)
sage: F.is_commutative()
True
sage: K = QuadraticField(23, 'a')
sage: F = K.factor(13)
sage: F.is_commutative()
True
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
is_integral()

Return True iff 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
lcm(other)

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()
Univariate Polynomial Ring in x over Integer Ring
prod()

Same as value().

EXAMPLES:

sage: F = factor(100)
sage: F.prod()
100
simplify()

Combine adjacent products that commute as much as possible.

TESTS:

sage: R.<x,y> = FreeAlgebra(ZZ, 2)
sage: F = Factorization([(x,3), (y, 2), (y,2)], simplify=False); F
x^3 * y^2 * y^2
sage: F.simplify(); F
x^3 * y^4
sage: F * Factorization([(y, -2)], 2)
(2) * x^3 * y^2
sort(_cmp=None)

Sort the factors in this factorization.

INPUT:

  • _cmp - (default: None) comparison function

OUTPUT:

  • changes this factorization to be sorted

If _cmp is None, we determine the comparison function 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. If there is no degree method, we sort based on dimension.

EXAMPLES: We create a factored polynomial:

sage: x = polygen(QQ,'x')
sage: F = factor(x^3 + 1); F
(x + 1) * (x^2 - x + 1)

Then we sort it but using the negated version of the standard Python cmp function:

sage: F.sort(_cmp = lambda x,y: -cmp(x,y))
sage: F
(x^2 - x + 1) * (x + 1)        
unit()

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
(-2.0) * (1.0*x^2 + 0.5)

Note that the unit part of the factorization is -2.0.

sage: F.unit()
-2.0        

sage: F = factor(-2006); F
-1 * 2 * 17 * 59
sage: F.unit()
-1
universe()

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)
sage: F = Factorization([(z, 2)], 3)
sage: (F*F^-1).universe()
Free Algebra on 3 generators (x, y, z) over Rational Field

sage: F = ModularSymbols(11,4).factorization()
sage: F.universe()
value()

Return the product of the factors in the factorization, multiplied out.

EXAMPLES:

sage: F = factor(2006); F
2 * 17 * 59
sage: F.value()
2006

sage: R.<x,y> = FreeAlgebra(ZZ, 2)
sage: F = Factorization([(x,3), (y, 2), (x,1)]); F
x^3 * y^2 * x
sage: F.value()
x^3*y^2*x 

Previous topic

Formal sums

Next topic

Elements

This Page