The Omega Package

Axel Riese

http://www.risc.uni-linz.ac.at/research/combinat/software

Research Institute for Symbolic Computation (RISC)
J. Kepler University Linz, Austria

February 21, 2005

History

Partition Analysis ("Omega Calculus") has been introduced by P.A. MacMahon (≈1900) as a computational method for solving problems in connection with linear homogeneous (in)equalities.

It was revisited by G.E.   Andrews (1998) for proving results from partition theory, where it turned out that Partition Analysis for the most part can be implemented in modern computer algebra systems.

During Andrews' stay at RISC (1998), P. Paule and me carried out a first prototype in Mathematica. Further investigation of both the mathematical and computational background led to a completely rewritten version which we are going to present now.

Theoretical Background

As an application consider the Lecture Hall Partition Theorem due to M. Bousquet–Mélou and K. Eriksson (1997).

Theorem. The number of partitions of n of the form n=(Subscript[b, j])+(Subscript[b, j-1])+⋯+(Subscript[b, 1]) wherein

((Subscript[b, j])/j)≥((Subscript[b, j-1])/(j-1))≥⋯≥((Subscript[b, 1])/1)≥0

equals the number of partitions of n into odd parts each ≤2j-1.

We will prove a special case of this result using Partition Analysis. For this recall that MacMahon's Omega Operator (Subscript[Ω, ≥]) is given by

(Underscript[Ω, ≥])  (∑_((Subscript[s, 1])=-∞)^∞)⋯(∑_((Subscript[s, r])=-∞)^∞)(Subscript[A, (Subscript[s, 1]),…,(Subscript[s, r])]) (Subscript[λ, 1]^(Subscript[s, 1]))⋯ (Subscript[λ, r]^(Subscript[s, r])):=(∑_((Subscript[s, 1])=0)^∞)⋯(∑_((Subscript[s, r])=0)^∞)(Subscript[A, (Subscript[s, 1]),…,(Subscript[s, r])]).

For the j=3 case of the LHP Theorem the generating function for the LHP's equals

L(q):=(Underscript[(Underscript[(∑_((Subscript[b, 1]), (Subscript[b, 2]), (Subscript[b, 3]) ⩾ 0,)), 2(Subscript[b, 3]) ≥ 3(Subscript[b, 2]),]), (Subscript[b, 2 ])≥ 2(Subscript[b, 1])])(q^((Subscript[b, 1])+(Subscript[b, 2])+(Subscript[b, 3]))),

or, encoded as an (Subscript[Ω, ≥])–expression,

L(q)=(Underscript[Ω, ≥])  (∑_((Subscript[b, 1]), (Subscript[b, 2]), (Subscript[b, 3]) ⩾ 0))(Subscript[λ, 1]^(2(Subscript[b, 3])-3(Subscript[b, 2])))(Subscript[λ, 2]^((Subscript[b, 2])-2(Subscript[b, 1])))(q^((Subscript[b, 1])+(Subscript[b, 2])+(Subscript[b, 3]))).

By geometric series expansion we rewrite L(q) as

(Underscript[Ω, ≥])(1/((1-q/(Subscript[λ, 2]^2))(1-(Subscript[λ, 2])q/(Subscript[λ, 1]^3))(1-(Subscript[λ, 1]^2)q))).

Now we could either take MacMahon's catalogue of rules for the (Subscript[Ω, ≥])–operator and carry out the computation with pencil and paper, or just invoke our package.

<<RISC`Omega`

Omega Package version 2.49
written by Axel Riese
(in cooperation with George E. Andrews and Peter Paule)
Copyright 2001-2010, Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

First we compute the expression the (Subscript[Ω, ≥])–operator acts on:

OSum[q^((Subscript[b, 1])+(Subscript[b, 2])+(Subscript[b, 3])),{2(Subscript[b, 3])≥3(Subscript[b, 2]),(Subscript[b, 2])≥2(Subscript[b, 1])},λ]

Then we eliminate the λ–variables (Subscript[λ, 1]) and (Subscript[λ, 2]):

OR[%]

Algorithmic Aspects

The computation is done recursively w.r.t. the factors in the denominator of the input function by using partial fraction decomposition. Omega 1.x was based on a complete factorization of these factors over the complex numbers, which caused severe problems because Mathematica (as other systems) is not able to handle roots of unity efficiently. For instance, consider the factorization of 1-x (λ^5) into

fac = Product[1 - E^(2j Pi I/5) x^(1/5) λ, {j, 0, 4}]

Trying to reconstruct the original term results in a surprise:

Expand[fac]

Simplify[%]

FullSimplify[Expand[fac]] // Timing

We could finally solve (?) this problem by a numerical approach:

Expand[fac] // N // Chop // Rationalize // Timing

Since complete factorization is no longer needed in Version 2 (due to a generalized partial fraction decomposition approach developed by Andrews), the program is now much faster and more stable. However, we are still suffering from the fact that immediate results after eliminating some of the variables sometimes grow enormously.

Applications

Triangles with sides of integer size

The following problem is posed as an exercise in R. Stanley's book (1986).

Problem: Let t(n) be the number of non–congruent triangles whose sides have integer length and whose perimeter is n. Find T(x):=(∑_(n≥3)) t(n) (x^n).

For instance, t(9)=3, corresponding to 9=3+3+3=2+3+4=1+4+4.

This means, we have to count all positive integer triples (a,b,c) satisfying a≤b≤c, a+b>c, and a+b+c=n. For this we again encode T(x) in terms of the (Subscript[Ω, ≥])–operator as

T(x) = (Underscript[Ω, ≥])  (∑_(a,b,c ⩾ 1))(Subscript[λ, 1]^(b-a))(Subscript[λ, 2]^(c-b))(Subscript[λ, 3]^(a+b-c-1))(x^(a+b+c)) = (Underscript[Ω, ≥])  ((x^3)/((1-x (Subscript[λ, 3])/(Subscript[λ, 1]))(1-x (Subscript[λ, 1])(Subscript[λ, 3])/(Subscript[λ, 2]))(1-x (Subscript[λ, 2])/(Subscript[λ, 3])).))

OSum[x^(a+b+c),{a≥1,b≥1,c≥1,a≤b,b ≤c,a+b>c}, λ]

OR[%]

From this it is easily seen that t(n) equals the number of partitions of n-3 into parts 2, 3, and 4. For instance, t(9)=3 corresponds to 6=2+2+2=3+3=4+2.

Solid partitions on a cube

Following MacMahon (1912) let us now study the "simplest lattice in solido", i.e., the lattice "in which the points are the summits of a cube and the branches the edges of the cube". In other words we put (nonnegative integer) weights (Subscript[a, i]) on the vertices of a cube:

Show[Graphics3D[{Cuboid[{0,0,0}],Text["(Subscript[a, 7])",{-0.1,0,0}],Text["(Subscript[a, 8])",{1,-0.1,0}],Text["(Subscript[a, 3])",{-0.1,0,1}],Text["(Subscript[a, 4])",{0.9,0.1,1}],Text["(Subscript[a, 1])",{0,1.1,1}],Text["(Subscript[a, 2])",{1,1.1,1}],Text["(Subscript[a, 6])",{1.1,1,0}],Hue[1],Thickness[0.01],Line[{{0,1,1},{0.5,1,1}}],Line[{{0,1,1},{0,0.5,1}}],Line[{{1,1,1},{1,0.5,1}}],Line[{{0,0,1},{0.5,0,1}}],Line[{{0,0,1},{0,0,0.5}}],Line[{{0,0,0},{0.5,0,0}}],Line[{{1,0,1},{1,0,0.5}}],Line[{{1,1,0},{1,0.5,0}}],Line[{{1,1,1},{1,1,0.5}}]},TextStyle->{"Text",FontSize->16, FontWeight->"Bold"}, Boxed->False]]

The directed edges are interpreted as inequalities, i.e., the "arrow" from vertex with weight (Subscript[a, 1]) to the vertex with weight (Subscript[a, 2]) corresponds to the relation (Subscript[a, 1])≥(Subscript[a, 2]). To the 12 diophantine inequalities we relate the corresponding generating function

C(q) = (Underscript[(∑_((Subscript[a, 1]), …, (Subscript[a, 8]) ⩾ 0,)), 12 constraints])(q^((Subscript[a, 1])+⋯+(Subscript[a, 8]))).

While MacMahon divided the computation of C(q) into 18 (!) parts, with our package it is a matter of seconds:

OSum[q^((Subscript[a, 1])+(Subscript[a, 2])+(Subscript[a, 3])+(Subscript[a, 4])+(Subscript[a, 5])+(Subscript[a, 6])+(Subscript[a, 7])+(Subscript[a, 8])), {(Subscript[a, 1])≥(Subscript[a, 2]),(Subscript[a, 1])≥(Subscript[a, 3]),(Subscript[a, 1])≥(Subscript[a, 5]),(Subscript[a, 2])≥(Subscript[a, 4]),(Subscript[a, 2])≥(Subscript[a, 6]),(Subscript[a, 3])≥(Subscript[a, 4]),(Subscript[a, 3])≥(Subscript[a, 7]),(Subscript[a, 4])≥(Subscript[a, 8]),(Subscript[a, 5])≥(Subscript[a, 6]),(Subscript[a, 5])≥(Subscript[a, 7]),(Subscript[a, 6])≥(Subscript[a, 8]),(Subscript[a, 7])≥(Subscript[a, 8])},λ]

OR[%]

Magic squares

Our package is also able to handle diophantine equations. For this recall the definition of MacMahon's Omega Operator (Subscript[Ω, =]),

(Underscript[Ω, =])  (∑_((Subscript[s, 1])=-∞)^∞)⋯(∑_((Subscript[s, r])=-∞)^∞)(Subscript[A, (Subscript[s, 1]),…,(Subscript[s, r])]) (Subscript[λ, 1]^(Subscript[s, 1]))⋯ (Subscript[λ, r]^(Subscript[s, r])) := (Subscript[A, 0,…,0]).

Let us consider Magic Squares of order 3, given by

({{(Subscript[a, 1]), (Subscript[a, 2]), (Subscript[a, 3])}, {(Subscript[a, 4]), (Subscript[a, 5]), (Subscript[a, 6])}, {(Subscript[a, 7]), (Subscript[a, 8]), (Subscript[a, 9])}})

where all the sums of the rows, columns, and diagonals are equal, i.e.,

(Subscript[a, 10]):=(Subscript[a, 1])+(Subscript[a, 2])+(Subscript[a, 3])=(Subscript[a, 4])+(Subscript[a, 5])+(Subscript[a, 6])=(Subscript[a, 7])+(Subscript[a, 8])+(Subscript[a, 9])=(Subscript[a, 1])+(Subscript[a, 4])+(Subscript[a, 7])=(Subscript[a, 2])+(Subscript[a, 5])+(Subscript[a, 8])=(Subscript[a, 3])+(Subscript[a, 6])+(Subscript[a, 9])=(Subscript[a, 1])+(Subscript[a, 5])+(Subscript[a, 9])=(Subscript[a, 3])+(Subscript[a, 5])+(Subscript[a, 7]).

We exactly follow MacMahon's proceeding to compute the generating function

MS((Subscript[x, 1]),…,(Subscript[x, 10])):=(Underscript[(∑_((Subscript[a, 1]), …, (Subscript[a, 10]) ⩾ 0,)), 8 constraints])((Subscript[x, 1])^(Subscript[a, 1]))⋯ (Subscript[x, 10]^(Subscript[a, 10])).

OEqSum[Product[(Subscript[x, i])^(Subscript[a, i]),{i,10}],{(Subscript[a, 1])+(Subscript[a, 2])+(Subscript[a, 3])==(Subscript[a, 10]),(Subscript[a, 4])+(Subscript[a, 5])+(Subscript[a, 6])==(Subscript[a, 10]),(Subscript[a, 7])+(Subscript[a, 8])+(Subscript[a, 9])==(Subscript[a, 10]),(Subscript[a, 1])+(Subscript[a, 4])+(Subscript[a, 7])==(Subscript[a, 10]),(Subscript[a, 2])+(Subscript[a, 5])+(Subscript[a, 8])==(Subscript[a, 10]),(Subscript[a, 3])+(Subscript[a, 6])+(Subscript[a, 9])==(Subscript[a, 10]),(Subscript[a, 1])+(Subscript[a, 5])+(Subscript[a, 9])==(Subscript[a, 10]),(Subscript[a, 3])+(Subscript[a, 5])+(Subscript[a, 7])==(Subscript[a, 10])},λ]

First we neglect the conditions on the diagonals by eliminating only (Subscript[λ, 1]),…,(Subscript[λ, 6]).

M16 = OEqR[%[[1]],{(Subscript[λ, 1]), (Subscript[λ, 2]), (Subscript[λ, 3]), (Subscript[λ, 4]), (Subscript[λ, 5]), (Subscript[λ, 6])}]

%/.{(Subscript[λ, 7])->1,(Subscript[λ, 8])->1}

After replacing (Subscript[x, 1]),…,(Subscript[x, 9]) by x and (Subscript[x, 10]) by y,

%/.(Subscript[x, 10])->y/.(Subscript[x, _])->x

it is clear that the coefficient of (x^(3n))(y^n) in this expression represents the number of squares with row and column sums equal to n. It can be shown that this coefficient equals

(({{n+5}, {5}}))-(({{n+2}, {5}})).

Next we eliminate (Subscript[λ, 7]).

M17 = OEqR[M16,(Subscript[λ, 7])]

%/.(Subscript[λ, 8])->1

Finally we eliminate (Subscript[λ, 8]).

OEqR[M17,(Subscript[λ, 8])]

%/.(Subscript[x, 10])->y/.(Subscript[x, _])->x // Cancel

The coefficient of (x^(3n))(y^n) in this expression equals

2(m^2)+2m+1,

if n=3m and 0 otherwise.

All these results can be found in MacMahon's book  (Vol. II,  §§ 406–409).

References

G.E. Andrews, MacMahon's partition analysis I: The lecture hall partition theorem, Progr. Math. 161 (1998), 1–22.

G.E. Andrews, MacMahon's partition analysis II: Fundamental theorems, Ann. Comb., 4 (2000), 327–338.

G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis III: The Omega Package, European J. Combin. 22 (2001), 887–904.

G.E. Andrews and P. Paule, MacMahon's partition analysis IV: Hypergeometric Multisums, Sém. Lothar. Combin. B42i (1999), 1–24.

G.E. Andrews, P. Paule, A. Riese, and V. Strehl, MacMahon's partition analysis V: Bijections, recursions, and magic squares, in "Algebraic Combinatorics and Applications" (A. Betten et al., eds.), Lecture Notes in Math., pp. 1–39, Springer, 2001.

G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis VI: A New Reduction Algorithm, Ann. Comb., 5 (2001), 251–270.

G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis VII: Constrained Compositions, in "q–Series with Applications to Combinatorics, Number Theory, and Physics" (B.C. Berndt and K. Ono, eds.), Contemp. Math., Vol. 291, pp. 11–27, Amer. Math. Soc., 2001.

G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis VIII: Plane Partition Diamonds, Adv. in Appl. Math., 27 (2001), 231–242.

G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis IX: k–Gon Partitions, Bull. Austral. Math. Soc., 64 (2001), 321–329.

M. Bousquet–Mélou and K. Eriksson, Lecture hall partitions, Ramanujan J. 1 (1997), 101–111.

P.A. MacMahon, Memoir on the theory of partitions of numbers — Part VI, Phil. Trans. 211 (1912), 345–373.

P.A. MacMahon, Combinatory Analysis, 2 vols., Cambridge University Press, Cambridge, 1915–16. (Reprinted: Chelsea, New York, 1960.)

R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth, Monterey, 1986.