MacMahon’s Partition Analysis Omega Operator#

This module implements MacMahon's Omega Operator [Mac1915], which takes a quotient of Laurent polynomials and removes all negative exponents in the corresponding power series.

Examples#

In the following example, all negative exponents of \(\mu\) are removed. The formula

\[\Omega_{\ge} \frac{1}{(1 - x\mu) (1 - y/\mu)} = \frac{1}{(1 - x) (1 - xy)}\]

can be calculated and verified by

Sage

sage: L.<mu, x, y> = LaurentPolynomialRing(ZZ)
sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y/mu])
1 * (-x + 1)^-1 * (-x*y + 1)^-1

Python

>>> from sage.all import *
>>> L = LaurentPolynomialRing(ZZ, names=('mu', 'x', 'y',)); (mu, x, y,) = L._first_ngens(3)
>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y/mu])
1 * (-x + 1)^-1 * (-x*y + 1)^-1

Various#

AUTHORS:

Daniel Krenn (2016)

ACKNOWLEDGEMENT:

Daniel Krenn is supported by the Austrian Science Fund (FWF): P 24644-N26.

Functions#

sage.rings.polynomial.omega.MacMahonOmega(var, expression, denominator=None, op=<built-in function ge>, Factorization_sort=False, Factorization_simplify=True)[source]#

Return \(\Omega_{\mathrm{op}}\) of expression with respect to var.

To be more precise, calculate

\[\Omega_{\mathrm{op}} \frac{n}{d_1 \dots d_n}\]

for the numerator \(n\) and the factors \(d_1\), …, \(d_n\) of the denominator, all of which are Laurent polynomials in var and return a (partial) factorization of the result.

INPUT:

var – a variable or a representation string of a variable
expression – a Factorization of Laurent polynomials or, if denominator is specified, a Laurent polynomial interpreted as the numerator of the expression
denominator – a Laurent polynomial or a Factorization (consisting of Laurent polynomial factors) or a tuple/list of factors (Laurent polynomials)
op – (default: operator.ge) an operator

At the moment only operator.ge is implemented.
Factorization_sort (default: False) and Factorization_simplify (default: True) – are passed on to sage.structure.factorization.Factorization when creating the result

OUTPUT:

A (partial) Factorization of the result whose factors are Laurent polynomials

Note

The numerator of the result may not be factored.

REFERENCES:

EXAMPLES:

Sage

sage: L.<mu, x, y, z, w> = LaurentPolynomialRing(ZZ)

sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y/mu])
1 * (-x + 1)^-1 * (-x*y + 1)^-1

sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y/mu, 1 - z/mu])
1 * (-x + 1)^-1 * (-x*y + 1)^-1 * (-x*z + 1)^-1
sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y*mu, 1 - z/mu])
(-x*y*z + 1) * (-x + 1)^-1 * (-y + 1)^-1 * (-x*z + 1)^-1 * (-y*z + 1)^-1
sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y/mu^2])
1 * (-x + 1)^-1 * (-x^2*y + 1)^-1
sage: MacMahonOmega(mu, 1, [1 - x*mu^2, 1 - y/mu])
(x*y + 1) * (-x + 1)^-1 * (-x*y^2 + 1)^-1

sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y*mu, 1 - z/mu^2])
(-x^2*y*z - x*y^2*z + x*y*z + 1) *
(-x + 1)^-1 * (-y + 1)^-1 * (-x^2*z + 1)^-1 * (-y^2*z + 1)^-1

sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y/mu^3])
1 * (-x + 1)^-1 * (-x^3*y + 1)^-1
sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y/mu^4])
1 * (-x + 1)^-1 * (-x^4*y + 1)^-1
sage: MacMahonOmega(mu, 1, [1 - x*mu^3, 1 - y/mu])
(x*y^2 + x*y + 1) * (-x + 1)^-1 * (-x*y^3 + 1)^-1
sage: MacMahonOmega(mu, 1, [1 - x*mu^4, 1 - y/mu])
(x*y^3 + x*y^2 + x*y + 1) * (-x + 1)^-1 * (-x*y^4 + 1)^-1

sage: MacMahonOmega(mu, 1, [1 - x*mu^2, 1 - y/mu, 1 - z/mu])
(x*y*z + x*y + x*z + 1) *
(-x + 1)^-1 * (-x*y^2 + 1)^-1 * (-x*z^2 + 1)^-1
sage: MacMahonOmega(mu, 1, [1 - x*mu^2, 1 - y*mu, 1 - z/mu])
(-x*y*z^2 - x*y*z + x*z + 1) *
(-x + 1)^-1 * (-y + 1)^-1 * (-x*z^2 + 1)^-1 * (-y*z + 1)^-1

sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y*mu, 1 - z*mu, 1 - w/mu])
(x*y*z*w^2 + x*y*z*w - x*y*w - x*z*w - y*z*w + 1) *
(-x + 1)^-1 * (-y + 1)^-1 * (-z + 1)^-1 *
(-x*w + 1)^-1 * (-y*w + 1)^-1 * (-z*w + 1)^-1
sage: MacMahonOmega(mu, 1, [1 - x*mu, 1 - y*mu, 1 - z/mu, 1 - w/mu])
(x^2*y*z*w + x*y^2*z*w - x*y*z*w - x*y*z - x*y*w + 1) *
(-x + 1)^-1 * (-y + 1)^-1 *
(-x*z + 1)^-1 * (-x*w + 1)^-1 * (-y*z + 1)^-1 * (-y*w + 1)^-1

sage: MacMahonOmega(mu, mu^-2, [1 - x*mu, 1 - y/mu])
x^2 * (-x + 1)^-1 * (-x*y + 1)^-1
sage: MacMahonOmega(mu, mu^-1, [1 - x*mu, 1 - y/mu])
x * (-x + 1)^-1 * (-x*y + 1)^-1
sage: MacMahonOmega(mu, mu, [1 - x*mu, 1 - y/mu])
(-x*y + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1
sage: MacMahonOmega(mu, mu^2, [1 - x*mu, 1 - y/mu])
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

Python

>>> from sage.all import *
>>> L = LaurentPolynomialRing(ZZ, names=('mu', 'x', 'y', 'z', 'w',)); (mu, x, y, z, w,) = L._first_ngens(5)

>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y/mu])
1 * (-x + 1)^-1 * (-x*y + 1)^-1

>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y/mu, Integer(1) - z/mu])
1 * (-x + 1)^-1 * (-x*y + 1)^-1 * (-x*z + 1)^-1
>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y*mu, Integer(1) - z/mu])
(-x*y*z + 1) * (-x + 1)^-1 * (-y + 1)^-1 * (-x*z + 1)^-1 * (-y*z + 1)^-1
>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y/mu**Integer(2)])
1 * (-x + 1)^-1 * (-x^2*y + 1)^-1
>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu**Integer(2), Integer(1) - y/mu])
(x*y + 1) * (-x + 1)^-1 * (-x*y^2 + 1)^-1

>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y*mu, Integer(1) - z/mu**Integer(2)])
(-x^2*y*z - x*y^2*z + x*y*z + 1) *
(-x + 1)^-1 * (-y + 1)^-1 * (-x^2*z + 1)^-1 * (-y^2*z + 1)^-1

>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y/mu**Integer(3)])
1 * (-x + 1)^-1 * (-x^3*y + 1)^-1
>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y/mu**Integer(4)])
1 * (-x + 1)^-1 * (-x^4*y + 1)^-1
>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu**Integer(3), Integer(1) - y/mu])
(x*y^2 + x*y + 1) * (-x + 1)^-1 * (-x*y^3 + 1)^-1
>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu**Integer(4), Integer(1) - y/mu])
(x*y^3 + x*y^2 + x*y + 1) * (-x + 1)^-1 * (-x*y^4 + 1)^-1

>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu**Integer(2), Integer(1) - y/mu, Integer(1) - z/mu])
(x*y*z + x*y + x*z + 1) *
(-x + 1)^-1 * (-x*y^2 + 1)^-1 * (-x*z^2 + 1)^-1
>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu**Integer(2), Integer(1) - y*mu, Integer(1) - z/mu])
(-x*y*z^2 - x*y*z + x*z + 1) *
(-x + 1)^-1 * (-y + 1)^-1 * (-x*z^2 + 1)^-1 * (-y*z + 1)^-1

>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y*mu, Integer(1) - z*mu, Integer(1) - w/mu])
(x*y*z*w^2 + x*y*z*w - x*y*w - x*z*w - y*z*w + 1) *
(-x + 1)^-1 * (-y + 1)^-1 * (-z + 1)^-1 *
(-x*w + 1)^-1 * (-y*w + 1)^-1 * (-z*w + 1)^-1
>>> MacMahonOmega(mu, Integer(1), [Integer(1) - x*mu, Integer(1) - y*mu, Integer(1) - z/mu, Integer(1) - w/mu])
(x^2*y*z*w + x*y^2*z*w - x*y*z*w - x*y*z - x*y*w + 1) *
(-x + 1)^-1 * (-y + 1)^-1 *
(-x*z + 1)^-1 * (-x*w + 1)^-1 * (-y*z + 1)^-1 * (-y*w + 1)^-1

>>> MacMahonOmega(mu, mu**-Integer(2), [Integer(1) - x*mu, Integer(1) - y/mu])
x^2 * (-x + 1)^-1 * (-x*y + 1)^-1
>>> MacMahonOmega(mu, mu**-Integer(1), [Integer(1) - x*mu, Integer(1) - y/mu])
x * (-x + 1)^-1 * (-x*y + 1)^-1
>>> MacMahonOmega(mu, mu, [Integer(1) - x*mu, Integer(1) - y/mu])
(-x*y + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1
>>> MacMahonOmega(mu, mu**Integer(2), [Integer(1) - x*mu, Integer(1) - y/mu])
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

We demonstrate the different allowed input variants:

Sage

sage: MacMahonOmega(mu,
....:     Factorization([(mu, 2), (1 - x*mu, -1), (1 - y/mu, -1)]))
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

sage: MacMahonOmega(mu, mu^2,
....:     Factorization([(1 - x*mu, 1), (1 - y/mu, 1)]))
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

sage: MacMahonOmega(mu, mu^2, [1 - x*mu, 1 - y/mu])
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

sage: MacMahonOmega(mu, mu^2, (1 - x*mu)*(1 - y/mu))  # not tested because not fully implemented
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

sage: MacMahonOmega(mu, mu^2 / ((1 - x*mu)*(1 - y/mu)))  # not tested because not fully implemented
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

Python

>>> from sage.all import *
>>> MacMahonOmega(mu,
...     Factorization([(mu, Integer(2)), (Integer(1) - x*mu, -Integer(1)), (Integer(1) - y/mu, -Integer(1))]))
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

>>> MacMahonOmega(mu, mu**Integer(2),
...     Factorization([(Integer(1) - x*mu, Integer(1)), (Integer(1) - y/mu, Integer(1))]))
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

>>> MacMahonOmega(mu, mu**Integer(2), [Integer(1) - x*mu, Integer(1) - y/mu])
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

>>> MacMahonOmega(mu, mu**Integer(2), (Integer(1) - x*mu)*(Integer(1) - y/mu))  # not tested because not fully implemented
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

>>> MacMahonOmega(mu, mu**Integer(2) / ((Integer(1) - x*mu)*(Integer(1) - y/mu)))  # not tested because not fully implemented
(-x*y^2 - x*y + y^2 + y + 1) * (-x + 1)^-1 * (-x*y + 1)^-1

sage.rings.polynomial.omega.Omega_ge(exponents)[source]#

Return \(\Omega_{\ge}\) of the expression specified by the input.

To be more precise, calculate

\[\Omega_{\ge} \frac{\mu^a}{ (1 - z_0 \mu^{e_0}) \dots (1 - z_{n-1} \mu^{e_{n-1}})}\]

and return its numerator and a factorization of its denominator. Note that \(z_0\), …, \(z_{n-1}\) only appear in the output, but not in the input.

INPUT:

a – an integer
exponents – a tuple of integers

OUTPUT:

A pair representing a quotient as follows: Its first component is the numerator as a Laurent polynomial, its second component a factorization of the denominator as a tuple of Laurent polynomials, where each Laurent polynomial \(z\) represents a factor \(1 - z\).

The parents of these Laurent polynomials is always a Laurent polynomial ring in \(z_0\), …, \(z_{n-1}\) over \(\ZZ\), where \(n\) is the length of exponents.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.omega import Omega_ge
sage: Omega_ge(0, (1, -2))
(1, (z0, z0^2*z1))
sage: Omega_ge(0, (1, -3))
(1, (z0, z0^3*z1))
sage: Omega_ge(0, (1, -4))
(1, (z0, z0^4*z1))

sage: Omega_ge(0, (2, -1))
(z0*z1 + 1, (z0, z0*z1^2))
sage: Omega_ge(0, (3, -1))
(z0*z1^2 + z0*z1 + 1, (z0, z0*z1^3))
sage: Omega_ge(0, (4, -1))
(z0*z1^3 + z0*z1^2 + z0*z1 + 1, (z0, z0*z1^4))

sage: Omega_ge(0, (1, 1, -2))
(-z0^2*z1*z2 - z0*z1^2*z2 + z0*z1*z2 + 1, (z0, z1, z0^2*z2, z1^2*z2))
sage: Omega_ge(0, (2, -1, -1))
(z0*z1*z2 + z0*z1 + z0*z2 + 1, (z0, z0*z1^2, z0*z2^2))
sage: Omega_ge(0, (2, 1, -1))
(-z0*z1*z2^2 - z0*z1*z2 + z0*z2 + 1, (z0, z1, z0*z2^2, z1*z2))

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.omega import Omega_ge
>>> Omega_ge(Integer(0), (Integer(1), -Integer(2)))
(1, (z0, z0^2*z1))
>>> Omega_ge(Integer(0), (Integer(1), -Integer(3)))
(1, (z0, z0^3*z1))
>>> Omega_ge(Integer(0), (Integer(1), -Integer(4)))
(1, (z0, z0^4*z1))

>>> Omega_ge(Integer(0), (Integer(2), -Integer(1)))
(z0*z1 + 1, (z0, z0*z1^2))
>>> Omega_ge(Integer(0), (Integer(3), -Integer(1)))
(z0*z1^2 + z0*z1 + 1, (z0, z0*z1^3))
>>> Omega_ge(Integer(0), (Integer(4), -Integer(1)))
(z0*z1^3 + z0*z1^2 + z0*z1 + 1, (z0, z0*z1^4))

>>> Omega_ge(Integer(0), (Integer(1), Integer(1), -Integer(2)))
(-z0^2*z1*z2 - z0*z1^2*z2 + z0*z1*z2 + 1, (z0, z1, z0^2*z2, z1^2*z2))
>>> Omega_ge(Integer(0), (Integer(2), -Integer(1), -Integer(1)))
(z0*z1*z2 + z0*z1 + z0*z2 + 1, (z0, z0*z1^2, z0*z2^2))
>>> Omega_ge(Integer(0), (Integer(2), Integer(1), -Integer(1)))
(-z0*z1*z2^2 - z0*z1*z2 + z0*z2 + 1, (z0, z1, z0*z2^2, z1*z2))

Sage

sage: Omega_ge(0, (2, -2))
(-z0*z1 + 1, (z0, z0*z1, z0*z1))
sage: Omega_ge(0, (2, -3))
(z0^2*z1 + 1, (z0, z0^3*z1^2))
sage: Omega_ge(0, (3, 1, -3))
(-z0^3*z1^3*z2^3 + 2*z0^2*z1^3*z2^2 - z0*z1^3*z2
 + z0^2*z2^2 - 2*z0*z2 + 1,
 (z0, z1, z0*z2, z0*z2, z0*z2, z1^3*z2))

Python

>>> from sage.all import *
>>> Omega_ge(Integer(0), (Integer(2), -Integer(2)))
(-z0*z1 + 1, (z0, z0*z1, z0*z1))
>>> Omega_ge(Integer(0), (Integer(2), -Integer(3)))
(z0^2*z1 + 1, (z0, z0^3*z1^2))
>>> Omega_ge(Integer(0), (Integer(3), Integer(1), -Integer(3)))
(-z0^3*z1^3*z2^3 + 2*z0^2*z1^3*z2^2 - z0*z1^3*z2
 + z0^2*z2^2 - 2*z0*z2 + 1,
 (z0, z1, z0*z2, z0*z2, z0*z2, z1^3*z2))

Sage

sage: Omega_ge(0, (3, 6, -1))
(-z0*z1*z2^8 - z0*z1*z2^7 - z0*z1*z2^6 - z0*z1*z2^5 - z0*z1*z2^4 +
 z1*z2^5 - z0*z1*z2^3 + z1*z2^4 - z0*z1*z2^2 + z1*z2^3 -
 z0*z1*z2 + z0*z2^2 + z1*z2^2 + z0*z2 + z1*z2 + 1,
 (z0, z1, z0*z2^3, z1*z2^6))

Python

>>> from sage.all import *
>>> Omega_ge(Integer(0), (Integer(3), Integer(6), -Integer(1)))
(-z0*z1*z2^8 - z0*z1*z2^7 - z0*z1*z2^6 - z0*z1*z2^5 - z0*z1*z2^4 +
 z1*z2^5 - z0*z1*z2^3 + z1*z2^4 - z0*z1*z2^2 + z1*z2^3 -
 z0*z1*z2 + z0*z2^2 + z1*z2^2 + z0*z2 + z1*z2 + 1,
 (z0, z1, z0*z2^3, z1*z2^6))

sage.rings.polynomial.omega.homogeneous_symmetric_function(j, x)[source]#

Return a complete homogeneous symmetric polynomial (Wikipedia article Complete_homogeneous_symmetric_polynomial).

INPUT:

j – the degree as a nonnegative integer
x – an iterable of variables

OUTPUT:

A polynomial of the common parent of all entries of x

EXAMPLES:

Sage

sage: from sage.rings.polynomial.omega import homogeneous_symmetric_function
sage: P = PolynomialRing(ZZ, 'X', 3)
sage: homogeneous_symmetric_function(0, P.gens())
1
sage: homogeneous_symmetric_function(1, P.gens())
X0 + X1 + X2
sage: homogeneous_symmetric_function(2, P.gens())
X0^2 + X0*X1 + X1^2 + X0*X2 + X1*X2 + X2^2
sage: homogeneous_symmetric_function(3, P.gens())
X0^3 + X0^2*X1 + X0*X1^2 + X1^3 + X0^2*X2 +
X0*X1*X2 + X1^2*X2 + X0*X2^2 + X1*X2^2 + X2^3

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.omega import homogeneous_symmetric_function
>>> P = PolynomialRing(ZZ, 'X', Integer(3))
>>> homogeneous_symmetric_function(Integer(0), P.gens())
1
>>> homogeneous_symmetric_function(Integer(1), P.gens())
X0 + X1 + X2
>>> homogeneous_symmetric_function(Integer(2), P.gens())
X0^2 + X0*X1 + X1^2 + X0*X2 + X1*X2 + X2^2
>>> homogeneous_symmetric_function(Integer(3), P.gens())
X0^3 + X0^2*X1 + X0*X1^2 + X1^3 + X0^2*X2 +
X0*X1*X2 + X1^2*X2 + X0*X2^2 + X1*X2^2 + X2^3

sage.rings.polynomial.omega.partition(items, predicate=<class 'bool'>)[source]#

Split items into two parts by the given predicate.

INPUT:

item – an iterator
predicate – a function

OUTPUT:

A pair of iterators; the first contains the elements not satisfying the predicate, the second the elements satisfying the predicate.

ALGORITHM:

Source of the code: http://nedbatchelder.com/blog/201306/filter_a_list_into_two_parts.html

EXAMPLES:

Sage

sage: from sage.rings.polynomial.omega import partition
sage: E, O = partition(srange(10), is_odd)
sage: tuple(E), tuple(O)
((0, 2, 4, 6, 8), (1, 3, 5, 7, 9))

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.omega import partition
>>> E, O = partition(srange(Integer(10)), is_odd)
>>> tuple(E), tuple(O)
((0, 2, 4, 6, 8), (1, 3, 5, 7, 9))