Vector Partition Functions (Mattias Beck) Question(s)

Question

On page 35 of Beck's exposition on Vector Partition Functions (found here: http://math.sfsu.edu/beck/papers/vectorpar.slides.pdf), Beck introduces the notion of the quasi-polynomial

$$\phi _{\textbf{A}} ( \textbf{b}) = \text{const} \left( \frac{1}{(1- \textbf{z} ^{\textbf{c}_1})(1-\textbf{z}^{\textbf{c}_2}) (1- \textbf{z} ^{\textbf{c}_3}) (1 - \textbf{z}^{\textbf{c}_4}) \textbf{z} ^{ \textbf{b}}} \right)$$ Which he then expands into partial fractions, treating $z_1$ as a variable and the rest of $z_k$ as constants to attain the form

$$\text{const} \left( \frac{1}{(1- \textbf{z} ^{\textbf{c}_1})(1-\textbf{z}^{\textbf{c}_2}) (1- \textbf{z} ^{\textbf{c}_3}) (1 - \textbf{z}^{\textbf{c}_4}) \textbf{z} ^{ \textbf{b}}} \right) = \frac{1}{z_2^{b_2} \cdots z_m ^{b_m}} \left( \sum ^d _{k = 1} \frac{A_k(\textbf{z},b_1)}{1-\textbf{z}^{c_k}} + \sum ^{b_1} _{j=1} \frac{B_j(\textbf{z})}{z_1^j} \right)$$ where "$A_k$ and $B_j$ are polynomials in $z_1$, rational functions in $z_2, ..., z_m$ and exponential in $b_1$." First off, what does this even mean? How do you get such a form, and how would you find these polynomials for a given example?

Then, how does Beck reduce this to

$$\text{const} \frac{1}{z_2^{b_2} \cdots z_m ^{b_m}} \sum ^d _{k=1} \frac{A_k (0, z_2, ..., z_m, b_1)}{1-(0,z_2,...,z_m)^{c_k}} $$ ???

And finally, how in the world is this applicable to my (very concrete) example at Finding Constant Term in Product of Series ?

I would greatly appreciate any help with understanding what is going on here and especially how I can apply it. I'm sorry, I don't really have "progress" to speak about because I'm honestly very lost.

Answer 1

General remark: the slides by Matthias Beck are not a tutorial, so it was quite challenging to extract what was intended from just the slides. Trying to do examples was my best shot at getting to understand them.

So I'll do another example that probably better shows what Beck is up to. This example is $2$-dimensional, so we'll see some $z_i$ being used formally in rational expressions rather than as indeterminate. Also, importantly, the set of vectors $\def\c{\mathbf c}\c_i$ for which the partition function is computed will avoid having some being rational multiples of others (as was inevitable in dimension$~1$), which causes the polynomials $1-z^{\c_i}$ to be mutually relatively prime; one can then do partial fraction decomposition while leaving these denominator factors intact.

Concretely I'll take the collection $\c_1=(1,0)$, $\c_2=(0,1)$ and $\c_3=(1,1)$, which is about the smallest interesting case possible (isomorphic to the $A_2$ system of positive roots, a case Beck mentions on a previous slide). So we have as matrix $$ A=\pmatrix{1&0&1\\0&1&1}.$$ As target vector I'll first take a vector of the form $\def\b{\mathbf b}\b=(b_1,b_2)$ with $b_1=3$, and then see what happens when $b_1$ is varied (the $b_2$ is separated out in the formula, so it really does not matter and can be left to vary right from the start. For readability call $z_1=X$ (which is being used as indeterminate, whence the capital letter) and $z_2=y$ (which is used as parameter whence the lower case).

Now $\phi_A(\b)$ is the coefficient of $X^3y^{b_2}$ in the expansion of $\frac1{(1-X)(1-y)(1-Xy)}$ as a formal power series in $X$. (Since we are not doing any series in $y$, it does not really make sense to mention $y^{b_2}$, and I only mention it because Beck does, but we'll soon get rid of it anyway). This question is translated into finding the constant term in the Laurent series expansion of $$ \frac1{(1-X)(1-y)(1-Xy)X^3y^{b_2}}. $$ To do so, Beck asks for a partial fraction decomposition of the expression using denominators $1-z^{\c_i}$, so concretely $1-X$, $1-y$, and $1-Xy$, as well as $X$, $X^2$ and $X^3$. A first thing to note is that $1-y$ is just a scalar in the field $\def\Q{\Bbb Q}\Q(y)$ we are going to work over, so it makes no sense to include a term with denominator $1-y$, and I will just drop it (though Beck mentions nothing about such cases). Also I will write $1-yX$ for $1-Xy$ so my brain has less difficulty of considering $y$ as a scalar. The factor $\frac1{1-y}$ is going to be present as a factor in all terms of our result, so it simplifies matters to single it out explicitly. Grouping together for now the terms with powers of $X$ as denominator, we are looking for polynomials $a,b,C\in\Q(y)[X]$ such that $$ \frac1{(1-X)(1-y)(1-Xy)X^3y^{b_2}}= \frac1{(1-y)y^{b_2}}\left(\frac a{1-X}+\frac b{1-yX}+\frac C{X^3}\right),\tag1 $$ and with numerators of degree less than their denominators, the is $\deg_X(a)<1$, $\deg_X(b)<1$ and $\deg(C)<3$ (so $a$ and $b$ are just scalars in $\Q(y)$, which is why I chose lower case for them). We turn equation $(1)$ into a polynomial one: $$ 1 = a(1-yX)X^3+b(1-X)X^3+C(1-X)(1-yX). \tag2 $$ The trick to avoid solving a linear system (over $\Q(y)$) is to use special evaluations for $a,b$, and some modular reduction for $C$. Concretely, setting $X:=1$ kills the last two factors and the remaining equation $1=a(1-y)$ gives $a=\frac1{1-y}$; similarly setting $X=\frac1y$ kills the outer two terms, and $1=b(1-y^{-1})y^{-3}$ solves to $b=\frac{y^3}{1-y^{-1}}=-\frac{y^4}{1-y}$. Finally $(2)$ clearly implies $C(1-X)(1-yX)\equiv1\pmod{X^3}$, which is most easily solved from the series expansion of $\frac1{(1-X)(1-yX)}$ to give (using the degree bound for $C$) $$ C=1+(1+y)X+(1+y+y^2)X^2. $$ Now the term $\frac C{X^3}$ can be split as $\frac{1+y+y^2}X+\frac{1+y}{X^2}+\frac1{X^3}$. So to get back to Beck's terminology we have found (taking care to reinsert the factor $\frac1{1-y}$ that we had set aside): $A_1(X,y,3)=\frac1{(1-y)^2}$, $A_2$ is absent (or zero), $A_3(X,y,3)=\frac{-y^4}{(1-y)^2}$, as well as $B_1(X,y)=\frac{1+y+y^2}{1-y}$, $B_2(X,y)=\frac{1+y}{1-y}$, and $B_3(X,y)=\frac1{1-y}$. Note that the dependency of the $B_i$ on $X$ is bogus: they must not contain $X$ as terms that have $X$ could be transferred to a lower-indexed $B_{i'}$; I only wrote $X$ because Beck did (and he calls them polynomials, while they are just scalars).

Now what will change if we replace $b_1=3$ by a larger value$~n$? Obviously in our argument $X^3$ gets replaced by $X^n$. The derivations of $a,b$ are very similar: we get $a=\frac1{1-y}$ independently of$~n$, and $b=-\frac{y^{n+1}}{1-y}$. For $C$ our series argument continues to work, and gives $C=\sum_{k=0}^{n-1}(\sum_{i=0}^ky^i)X^k$. This gives some justification to the claim that "the $A_k$ are exponential in $b_1$" (i.e., in $n$), though I cannot really see what the same claim for the $B_j$ should be taken to mean (possibly if one writes $B_j=\frac{1-y^{n+1-j}}{(1-y)^2}$ it makes some kind of sense).

Back to the original problem, we need to take the constant term of our result as a series in$~X$, which results in a rational function of$~y$, and then take the constant term in$~y$ of the Laurent series expansion of that rational function. The first step completely discards the terms coming from $C$ (with the $B_j$), as these have purely negative powers of $X$, and in the terms with $a$ and $b$ we can replace the denominators by$~1$ (as here we are basically setting $X:=0$). So in the general case we are looking for the constant term in the Laurent series expansion of $$\frac1{(1-y)y^{b_2}}\left(\frac1{1-y}-\frac{y^{n+1}}{1-y}\right) =\frac{1-y^{n+1}}{(1-y)^2y^{b_2}}. $$ This is the same a asking for the coefficient of $Y^{b_2}$ in the formal power series for $\frac{1-Y^{n+1}}{(1-Y)^2}$, which can be found to be $\min(b_2+1,n+1)$, and indeed this is the number of ways to write the vector $(n,b_2)$ as a non-negative integer linear combination of $(1,0)$, $(0,1)$, and $(1,1)$.

Answer 2

I will not give an answer to the question in its generality, but just focus on splitting into partial fraction in the context of an enumeration problem. For simplicity I will only consider the one-dimensional case $m=1$, so that there are no supplementary variables $z_2,\ldots,z_m$ to worry about (since partial fraction decomposition is done for one variable only, the others are going to be treated formally anyway, introducing rational functions of them; I will ignore this complication). Comparing with what Beck wrote, I must say that frankly I doubt whether I am even on the right path, since he is applying this to Laurent series (there are negative powers of $z_1$) while I am doing partial fractions in the context of ordinary formal power series. But anyway here it is, even if it should be entirely beside the point.

I considered the problem of enumerating the problem of counting the number of ways to write a natural number $n$ as the sum of a multiset of a given set of numbers, which for concreteness I take to be $\{2,3,7\}$. Elementary combinatorics translates this into finding the coefficient of $X^n$ in the formal power series $$\frac1{(1-X^2)(1-X^3)(1-X^7)}$$ (Beck would now divide this fraction by $X^n$ an search for the constant term of the resulting Laurent series, but for now I don't even see how this makes the problem any easier, and in any case I avoid Laurent series and won't do this.) Partial fraction decomposition can only be done to relatively prime denominators, and since each of the visible factors in the display hides a factor $(1-X)$, this here means denominators must be the relatively prime polynomial $Q=(1-X)^3$, $P_2=1+X$, $P_3=1+X+X^2$ and $P_7=1+X+X^2+X^3+X^4+X^5+X^6$. We are than looking to write $$ \frac1{(1-X^2)(1-X^3)(1-X^7)}=\frac AQ+\frac B{P_2} + \frac C{P_3} + \frac D{P_7},\tag{1} $$ with as numerators $A,B,C,D$ some polynomials of degree strictly less than their respective denominators, that is than $3,1,2,6$ respectively. Finding those numerators amounts to solving them from the polynomial equation $$1=AP_2P_3P_7 + BQP_3P_7 + CQP_2P_7 +DQP_2P_3.\tag{2}$$ There are tricks to separate the terms with $A,B,C,D$ by special evaluations of the polynomials. But in the end, although this avoids solving linear systems, it becomes quite complicated nonetheless, and if one is using a computer for the details anyway (as one should), it is probably easiest to just solve the linear system for $(2)$, which is a system $Mx=b$ in $x\in\Bbb Q^{12}$ with $$ M=\pmatrix { 1& 0& 0& 1& 1& 0& 1& 0& 0& 0& 0& 0 \cr 3& 1& 0& -1& -1& 1& -1& 1& 0& 0& 0& 0 \cr 5& 3& 1& 0& -1& -1& -1& -1& 1& 0& 0& 0 \cr 6& 5& 3& -1& 1& -1& 0& -1& -1& 1& 0& 0 \cr 6& 6& 5& 1& 0& 1& 1& 0& -1& -1& 1& 0 \cr 6& 6& 6& 0& 0& 0& 1& 1& 0& -1& -1& 1 \cr 6& 6& 6& 0& 0& 0& -1& 1& 1& 0& -1& -1 \cr 5& 6& 6& -1& -1& 0& 0& -1& 1& 1& 0& -1 \cr 3& 5& 6& 1& 1& -1& 0& 0& -1& 1& 1& 0 \cr 1& 3& 5& 0& 1& 1& 0& 0& 0& -1& 1& 1 \cr 0& 1& 3& 1& -1& 1& 0& 0& 0& 0& -1& 1 \cr 0& 0& 1& -1& 0& -1& 0& 0& 0& 0& 0& -1 } $$ and $b=(1,0,0,0,0,0,0,0,0,0,0,0)$ (the constant polynomial $1$ expressed on the monomial basis of polynomial of degree less than$~12$). The solution is given by $$ A=\frac{185}{504}-\frac{73}{126}X+\frac{17}{72}X^2,\\ B=\frac18,\quad C=\frac29+\frac19X,\quad D=\frac27+0X+\frac27X^2+\frac27X^3+\frac17X^4+0X^5. $$ The corresponding terms respectively give a contribution of polynomial growth in $n$, an period terms of periods $2$, $3$, $7$ respectively. More precisely the series $$ \frac{\frac{185}{504}-\frac{73}{126}X+\frac{17}{72}X^2}{(1-X)^3} =\frac{17}{72}\frac1{1-X}+\frac3{28}\frac1{(1-X)^2}+\frac1{42}\frac1{(1-X)^3} $$ has general term $\frac{17}{72}+(n+1)(\frac3{28}+\frac{(n+2)}2\frac1{42})$ (which you can rewrite to more traditional form if you like; the given form corresponds a rational combination of binomial coefficients $\binom n0, \binom{n+1}1,\binom{n+2}2$ that take positive integer values on $\Bbb N$), and the other terms give periodic contributions of zero average: $\frac{1/8}{1+X}$ gives $\overline{\frac18,-\frac18}$, then $\frac{\frac29+\frac19X}{1+X+X^2}$ gives $\overline{\frac29,-\frac19,-\frac19}$ and $\frac{\frac27+0X+\frac27X^2+\frac27X^3+\frac17X^4+0X^5}{1+X+X^2+X^3+X^4+X^5+X^6}$ gives $\overline{\frac27,-\frac27,\frac27,0,-\frac17,-\frac17,0}$.

Again, I realise that this is not what Beck does, who seems to be doing partial fraction decomposition only between purely negative powers of $X$ (or $z_1$) and terms $\frac1{1-X^k}$ (which while not relatively prime among each other are relatively prime with and $\frac1{X^l}$). Nonetheless the principle of partial fraction decomposition is the same. I'll leave it here for now.