The  Ω-Package

Axel Riese

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

Axel.Riese@risc.uni-linz.ac.at

June 1, 2000

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.

The latest version of the package is available at

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

To get the password send an email to

Axel.Riese@risc.uni-linz.ac.at

Introduction

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 the definition of MacMahon's Omega Operator (Subscript[Ω, ≥]).

Definition. The operator (Subscript[Ω, ≥]) is given by

(Underscript[Ω, ≥])  (∑_((Subscript[s, 1])=-∞)^∞)⋯(∑_((Subscript[s, r])=-∞)^∞)(Subscript[A, (Subscript[s, 1]),…,(Subscript[s, r])]) (Subscript[(Subscript[λ, 1]^s), 1])⋯ (Subscript[(Subscript[λ, r]^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])},λ]

And then we eliminate the variables (Subscript[λ, 1]) and (Subscript[λ, 2]):

OR[%]

Further Applications

Solid partitions on a cube

Following MacMahon (1912) let us now study the "simplest lattice in solido", i.e., we put (nonnegative integer) weights (Subscript[a, i]) on the vertices of a cube:

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}]},TextStyle->{"Text",FontSize->16, FontWeight->"Bold"}, Boxed->False]]

The vertices are then connected by directed edges which 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]):

Show[cube, Graphics3D[{Hue[1],Thickness[0.0125],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,0,0},{1,0.5,0}}],Line[{{1,1,1},{1,1,0.5}}]}, Boxed->False]]

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[%]

k-gon partitions

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) automatically in terms of the (Subscript[Ω, ≥])-operator:

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 into parts 2, 3, and 4 with at least one part equal to 3. For example, t(9)=3 corresponds to 9=4+3+2=3+3+3=3+2+2+2.

Stanley's exercise is the k=3 instance of the following more general problem:

Problem: Let (Subscript[t, k])(n) be the number of non-degenerate k-gon partitions of n, i.e.,

(Subscript[t, k])(n)=#{((Subscript[a, 1]),…,(Subscript[a, k]))∈(ℕ^k)|(Subscript[a, 1])≤(Subscript[a, 2])≤⋯≤(Subscript[a, k]), (Subscript[a, 1])+⋯+(Subscript[a, k])=n, and  (Subscript[a, k])<(Subscript[a, 1])+⋯+(Subscript[a, k-1])}.

Find (Subscript[T, k])(x):=(∑_(n≥k)) (Subscript[t, k])(n) (x^n).

For k=4 we obtain:

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

OR[%]

For k=5 we obtain:

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

OR[%]

And for k=6 we obtain:

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

OR[%]

Open Problem:  Find a closed form for (Subscript[T, k])(x).

Magic squares

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

Definition. The operator (Subscript[Ω, =]) is given by

(Underscript[Ω, =])  (∑_((Subscript[s, 1])=-∞)^∞)⋯(∑_((Subscript[s, r])=-∞)^∞)(Subscript[A, (Subscript[s, 1]),…,(Subscript[s, r])]) (Subscript[(Subscript[λ, 1]^s), 1])⋯ (Subscript[(Subscript[λ, r]^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.,

a:=(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]).

The generating function

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

can then be computed as follows.

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

OEqR[%]

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

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

if n=3m and 0 otherwise.

For instance, if n=3:

({{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}), ({{0, 2, 1}, {2, 1, 0}, {1, 0, 2}}), ({{1, 0, 2}, {2, 1, 0}, {0, 2, 1}}), ({{1, 2, 0}, {0, 1, 2}, {2, 0, 1}}), ({{2, 0, 1}, {0, 1, 2}, {1, 2, 0}}).

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, to appear.

G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis III: The Omega Package, SFB Report n. 99-24, J. Kepler University Linz, 1999.

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, to appear.

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.