# On Cayley algorithm for double partition

Boris Y. Rubinstein
Stowers Institute for Medical Research
1000 50th St., Kansas City, MO 64110, U.S.A

###### Abstract

A double partition problem asks for a number of nonnegative integer solutions
to a system of two linear Diophantine equations with integer coefficients.
Artur Cayley suggested [2] a reduction of a double partition to a sum of
scalar partitions with an algorithm subject to a set of conditions. We show
that when these conditions are not satisfied and the original algorithm fails
its modification solves the reduction problem.

Keywords: double partition.

2010 Mathematics Subject Classification: 11P82.

##  1 Scalar and vector restricted partition functions

###  1.1 Scalar partitions

The problem of integer partition into a set of integers is equivalent to a
problem of number of nonnegative integer solutions of the Diophantine equation

$\sum_{i=1}^{m}x_{i}d_{i}={\bf x}\cdot{\bf d}=s.$ (1)

A scalar partition function $W(s,{\bf d})\equiv
W(s,\\{d_{1},d_{2},\ldots,d_{m}\\})$ solving the above problem is a number of
partitions of an integer $s$ into positive integers
$\\{d_{1},d_{2},\ldots,d_{m}\\}$. The generating function for $W(s,{\bf d})$
has a form

$G(t,{\bf d})=\prod_{i=1}^{m}\frac{1}{1-t^{d_{i}}}=\sum_{s=0}^{\infty}W(s,{\bf
d})\;t^{s}\;,$ (2)

Introducing notation $C[t^{s}](f(t))$ for a coefficient of $t^{s}$ in the
expansion of a function $f(t)$ we have

$W(s,{\bf d})=C[t^{s}]\left(\prod_{i=1}^{m}(1-t^{d_{i}})^{-1}\right).$ (3)

Sylvester proved [9] a statement about splitting of the scalar partition
function (SPF) into periodic and non-periodic parts and showed that it may be
presented as a sum of ”waves”

$W(s,{\bf d})=\sum_{j=1}W_{j}(s,{\bf d})\;,$ (4)

where summation runs over all distinct factors of the elements of the
generator vector ${\bf d}$. The wave $W_{j}(s,{\bf d})$ is a quasipolynomial
in $s$ closely related to prime roots $\rho_{j}$ of unity, namely, is a
coefficient of ${t}^{-1}$ in the series expansion in ascending powers of $t$
of a function

$F_{j}(s,t)=\sum_{\rho_{j}}\frac{\rho_{j}^{-s}e^{st}}{\prod_{k=1}^{m}\left(1-\rho_{j}^{d_{k}}e^{-d_{k}t}\right)}\;.$
(5)

The summation is made over all prime roots of unity $\rho_{j}=\exp(2\pi in/j)$
for $n$ relatively prime to $j$ (including unity) and smaller than $j$. It was
shown [4] that it is possible to express the wave $W_{j}(s,{\bf d})$ as a
finite sum of the Bernoulli polynomials of higher order.

###  1.2 Vector partitions

Consider a function $W({\bf s},{\bf D})$ counting the number of integer
nonnegative solutions ${\bf x}\geq 0$ to a linear system ${\bf D}\cdot{\bf
x}={\bf s}$, where ${\bf D}$ is a nonnegative integer $l\times m$ generator
matrix. The function $W({\bf s},{\bf D})$ is called vector partition function
(VPF) as a natural generalization of SPF to the vector argument.

The generating function for the VPF reads

$G({\bf t},{\bf D})=\prod_{i=1}^{m}\frac{1}{1-{\bf t}^{{\bf
c}_{i}}}=\sum_{{\bf s}}W({\bf s},{\bf D}){\bf t^{s}},\quad{\bf
t^{s}}=\prod_{k=1}^{l}t_{k}^{s_{k}},\quad{\bf t}^{{\bf
c}_{i}}=\prod_{k=1}^{l}t_{k}^{c_{ik}},$ (6)

where ${\bf c}_{i}=\\{c_{i1},c_{i2},\ldots,c_{il}\\},\ (1\leq i\leq m)$
denotes the $i$-th column of the matrix ${\bf D}=\\{{\bf c}_{1},{\bf
c}_{2},\ldots,{\bf c}_{m}\\}$. Note that some elements $c_{ik}$ might equal
zero. Generalizing the coefficient notation (3) to the case of function of
several variables find for $W({\bf s},{\bf D})$

$W({\bf s},{\bf D})=C[{\bf t}^{\bf s}]\left(\prod_{i=1}^{m}\frac{1}{1-{\bf
t}^{{\bf c}_{i}}}\right).$ (7)

Several approaches were suggested for VPF computation including method of
residues [1, 10] and geometric decomposition into so called chambers [7] –
regions in $m$-dimensional space where the partition function is characterized
by a specific expression. A method of VPF computation was suggested [5] being
a direct generalization of the approach developed in [4]. To this end vector
Bernoulli and Eulerian polynomials of higher order were introduced to find
explicit expression for $W({\bf s},{\bf D})$. A drawback of this approach is
that it does not provide any mechanism to define chamber boundaries. As SPF
computation requires just well-known functions [4] it is promising to obtain a
reduction method expressing vector partition through scalar ones.

###  1.3 Sylvester-Cayley method of vector partition reduction

The problem of scalar and vector integer partitions has a long history and
J.J. Sylvester made a significant contribution to its solution. In addition to
the splitting algorithm for SPF [9] he suggested [8] an idea to reduce VPF
into a sum of scalar partitions. The reduction is an iterative process based
on the variable elimination in the generating function (6). Sylvester
considered a specific double partition problem as an illustration of his
method and determined regions of a plane $\\{s_{1},s_{2}\\}$ each having a
unique expression for VPF valid in this region only. He showed that the
expressions in the adjacent chambers coincide at their common boundary (see
also [7]).

This approach was successfully applied by A. Cayley [2] to double partitions
subject to some restrictions on the elements of matrix ${\bf D}$ – the vectors
${\bf c}_{i}$ are noncollinear, the elements of every column ${\bf c}_{i}$ are
relatively prime and for all elements $c_{i2}$ of the second row the
inequality $c_{i2}<s_{2}+2,1\leq i\leq m$ holds. It should be noted that
Cayley mentions that the elements of the matrix ${\bf D}$ as well as $s_{i}$
“being all positive integer numbers, not excluding zero” [2]. Direct
computation shows that when the number of columns containing zero is larger
than two, with zeros appearing in both rows of the matrix ${\bf D}$, and also
nonzero elements in such columns are larger than unity, the Cayley method
fails. It also fails when the column elements have the greatest common divisor
(GCD) larger than unity. These deficiencies call for a search of alternative
approach of double partition reduction to scalar partitions.

###  1.4 Partial fraction expansion algorithm

Computation of vector partition $W({\bf s},{\bf D})$ in (7) can be performed
by iterative elimination [1] of $(l-1)$ variables $t_{k},(2\leq k\leq l)$.
Each elimination step includes partial fraction expansion (PFE) w.r.t. the
eliminated variable with subsequent coefficient evaluation. This step is
equivalent to elimination of $k$-th row of augmented $l\times(m+1)$ matrix
${\bf E}=\\{{\bf s}={\bf c}_{0},{\bf c}_{1},{\bf c}_{2},\ldots,{\bf c}_{m}\\}$
made of the generator matrix ${\bf D}$ and argument vector ${\bf s}$; the same
time one of the columns of ${\bf D}$ is eliminated too. The number of newly
generated $(l-1)\times m$ matrices is equal to $m$. This algorithm was
employed in [2] for a two-row positive matrix (see also [8]).

##  2 Cayley algorithm of double partition reduction

Consider the simplest vector partition case $l=2$ following the algorithm
described in [2]. Denote matrix ${\bf E}$ columns as ${\bf s}={\bf
c}_{0}=\\{r,\rho\\}^{T}$ and ${\bf c}_{i}=\\{b_{i},\beta_{i}\\}^{T},\ (1\leq
i\leq m),$ where T stands for transposition. Cayley specified following
conditions that should be met in order to apply the algorithm [2]. First, all
fractions $b_{i}/\beta_{i}$ should be unequal, in other words, the columns
${\bf c}_{i}$ must be pairwise linearly independent. It is also required that
the elements of each column ${\bf c}_{i}$ are relatively prime
$\gcd(b_{i},\beta_{i})=1$. Finally, all elements of the second row should
satisfy a condition $\beta_{i}<\rho+2$.

Assuming that all $b_{i},\beta_{i}>0$ perform PFE step to present $G({\bf
t},{\bf D})$ as sum of $m$ fractions (${\bf t}=\\{x,y\\}$)

$G({\bf t},{\bf
D})=\prod_{i=1}^{m}(1-x^{b_{i}}y^{\beta_{i}})^{-1}=\sum_{i=1}^{m}T_{i}(x,y),\quad
T_{i}=\frac{A_{i}(x,y)}{1-x^{b_{i}}y^{\beta_{i}}},$ (8)

where the functions $A_{i}$ are rational in $x$ and rational and integral (of
degree $\beta_{i}-1$) in $y$.

###  2.1 Partial fraction expansion

Consider $A_{1}(x,y)$ – we have for $y=y_{0}=x^{-b_{1}/\beta_{1}}$,

$A_{1}(x,y)=\prod_{i\neq 1}^{m}(1-x^{b_{i}}y^{\beta_{i}})^{-1},$ (9)

that is

$A_{1}(x,x^{-b_{1}/\beta_{1}})=\prod_{i\neq
1}^{m}(1-x^{b_{i}-b_{1}\beta_{i}/\beta_{1}})^{-1}.$ (10)

Introduce a set of complex quantities $\omega_{1j}=\omega_{1}^{j},\;1\leq
j\leq\beta_{1}-1$, where $\omega_{1}=\exp(2\pi i/\beta_{1})$. Multiply both
the numerator and denominator of the fraction in r.h.s. in (10) by

$S_{1}(x,y_{0})=\prod_{i\neq
1}^{m}\prod_{j=1}^{\beta_{1}-1}(1-\omega_{1j}x^{b_{i}}y_{0}^{\beta_{i}})=\prod_{i\neq
1}^{m}\prod_{j=1}^{\beta_{1}-1}(1-\omega_{1j}x^{b_{i}-b_{1}\beta_{i}/\beta_{1}}).$

The denominator turns into

$\Pi_{1}(x)=\prod_{i\neq 1}^{m}(1-x^{\beta_{1}b_{i}-b_{1}\beta_{i}}),$ (11)

while the numerator reads

$S_{1}(x,y_{0})=\Pi_{1}(x)A_{1}(x,y_{0})=\sum_{k=0}^{\beta_{1}-1}A_{1k}(x)x^{-kb_{1}/\beta_{1}}=\sum_{k=0}^{\beta_{1}-1}A_{1k}(x)y_{0}^{k},$
(12)

where $A_{1k}$ are rational functions in $x$. This leads to

$A_{1}(x,y_{0})=\frac{1}{\Pi_{1}(x)}\sum_{k=0}^{\beta_{1}-1}A_{1k}(x)y_{0}^{k},$

and we obtain for $T_{1}(x,y)$

$T_{1}(x,y)=\frac{A_{1}(x,y)}{1-x^{b_{1}}y^{\beta_{1}}}=\frac{1}{\Pi_{1}(x)(1-x^{b_{1}}y^{\beta_{1}})}\sum_{k=0}^{\beta_{1}-1}A_{1k}(x)y^{k}\;.$
(13)

###  2.2 Contribution evaluation

Our goal is to find a contribution
$C_{r,\rho}^{1}=C[x^{r}y^{\rho}](T_{1}(x,y)).$ Cayley employs a relation [2]

$C[x^{r}y^{\rho}]\left(\frac{A_{1}(x,y)}{1-x^{b_{1}}y^{\beta_{1}}}\right)=C[x^{r}y^{\rho}]\left(\frac{A_{1}(x,y)}{1-x^{b_{1}/\beta_{1}}y}\right),$
(14)

that allows to write

$\frac{A_{1}(x,y)}{1-x^{b_{1}/\beta_{1}}y}=U_{\beta_{1}-2}+\frac{A_{1}(x,x^{-b_{1}/\beta_{1}})}{1-x^{b_{1}/\beta_{1}}y},$
(15)

where $U_{\beta_{1}-2}$ is “a rational and integral function of the degree
$\beta_{1}-2$ in $y$” [2]. Introduce $\delta y=y-y_{0}$, and perform a
sequence of transformations

$\displaystyle S_{1}(x,y)$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{\beta_{1}-1}A_{1k}(x)y^{k}=\sum_{k=0}^{\beta_{1}-1}A_{1k}(x)(y_{0}+\delta
y)^{k}$ (16) $\displaystyle=$
$\displaystyle\sum_{k=0}^{\beta_{1}-1}\sum_{m=0}^{k}A_{1k}(x)C(k,m)y_{0}^{m}(\delta
y)^{k-m}$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{\beta_{1}-1}A_{1k}(x)y_{0}^{k}+\sum_{k=1}^{\beta_{1}-1}\sum_{m=0}^{k-1}A_{1k}(x)C(k,m)y_{0}^{m}(\delta
y)^{k-m}$ $\displaystyle=$ $\displaystyle
S_{1}(x,y_{0})+\sum_{k=1}^{\beta_{1}-1}\sum_{m=0}^{k-1}A_{1k}(x)C(k,m)y_{0}^{m}(y-x^{-b_{1}/\beta_{1}})^{k-m}=$
$\displaystyle=$ $\displaystyle S_{1}(x,x^{-b_{1}/\beta_{1}})+\hat{U},$

where $C(k,m)$ denotes binomial coefficient and $\hat{U}$ is an integral
function of the degree $\beta_{1}-1$ in $y$

$\displaystyle\hat{U}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{\beta_{1}-1}\sum_{m=0}^{k-1}A_{1k}(x)C(k,m)y_{0}^{m}(y-x^{-b_{1}/\beta_{1}})^{k-m}$
(17) $\displaystyle=$
$\displaystyle\sum_{k=1}^{\beta_{1}-1}\sum_{m=0}^{k-1}(-1)^{m-k}A_{1k}(x)C(k,m)x^{-kb_{1}/\beta_{1}}(1-x^{b_{1}/\beta_{1}}y)^{k-m}.$

Now return to $A_{1}(x,y)$ in (14) and find for $U_{\beta_{1}-2}$ in (15)

$U_{\beta_{1}-2}=\frac{1}{\Pi_{1}(x)}\cdot\frac{\hat{U}}{{1-x^{b_{1}/\beta_{1}}y}}=\frac{1}{\Pi_{1}(x)}\sum_{k=1}^{\beta_{1}-1}\sum_{m=0}^{k-1}(-1)^{m-k}A_{1k}(x)C(k,m)x^{-kb_{1}/\beta_{1}}(1-x^{b_{1}/\beta_{1}}y)^{k-1-m}\;,$

so that $U_{\beta_{1}-2}$ is an integral function of the degree $\beta_{1}-2$
in $y$ and the assumption $\beta_{i}<\rho+2$ allows to drop this term from
further consideration. Then using (15) we have

$\displaystyle C_{r,\rho}^{1}$ $\displaystyle=$ $\displaystyle
C[x^{r}y^{\rho}]\left(\frac{A_{1}(x,y)}{1-x^{b_{1}/\beta_{1}}y}\right)=C[x^{r}y^{\rho}]\left(\frac{A_{1}(x,x^{-b_{1}/\beta_{1}})}{1-x^{b_{1}/\beta_{1}}y}\right)$
$\displaystyle=$ $\displaystyle C[x^{r}]\left(x^{\rho
b_{1}/\beta_{1}}A_{1}(x,x^{-b_{1}/\beta_{1}})\right)=C[x^{r-\rho
b_{1}/\beta_{1}}]\left(A_{1}(x,x^{-b_{1}/\beta_{1}})\right)$ $\displaystyle=$
$\displaystyle C[x^{r\beta_{1}-\rho
b_{1}}]\left(A_{1}(x^{\beta_{1}},x^{-b_{1}})\right).$

From (10) we obtain

$A_{1}(x^{\beta_{1}},x^{-b_{1}})=\prod_{i\neq
1}^{m}(1-x^{b_{i}\beta_{1}-b_{1}\beta_{i}})^{-1},$

and arrive at

$C_{r,\rho}^{1}=C[x^{r\beta_{1}-\rho b_{1}}]\left(\prod_{i\neq
1}^{m}(1-x^{b_{i}\beta_{1}-b_{1}\beta_{i}})^{-1}\right)=C[x^{r\beta_{1}-\rho
b_{1}}]\left(1/\Pi_{1}(x)\right).$ (19)

###  2.3 Double partition as a sum of scalar partitions

Repeating computation in Sections 2.1 and 2.2 for each $T_{i}(x,y),\ 1\leq
i\leq m,$ we obtain for double partition function using (19)

$W(\bm{s},{\bf
D})=\sum_{k=1}^{m}C_{r,\rho}^{k}=\sum_{k=1}^{m}C[x^{r\beta_{k}-\rho
b_{k}}]\left(\prod_{i\neq
k}^{m}(1-x^{b_{i}\beta_{k}-b_{k}\beta_{i}})^{-1}\right).$

Recall the SPF definition (3) and rewrite it as

$W(s,{\bf d})=C[t^{s}]\left(\prod_{i=1}^{m}(1-t^{d_{i}})^{-1}\right).$

It allows to obtain an expression of double partition as a sum of scalar
partitions

$W({\bf s},{\bf D})=\sum_{i=1}^{m}W^{2}_{i}({\bf
s})=\sum_{i=1}^{m}W(L_{i},{\bf d}_{i}),\quad L_{i}=r\beta_{i}-b_{i}\rho,\quad
d_{ij}=b_{j}\beta_{i}-b_{i}\beta_{j},\ j\neq i.$ (20)

This compact expression is the main result of Cayley algorithm presented in
[2]. Introducing $2\times 2$ matrices made of ${\bf c}_{i}$ and the columns of
augmented matrix ${\bf E}_{i}=\\{{\bf c}_{0},{\bf c}_{1},\ldots,{\bf
c}_{i-1},{\bf c}_{i+1},\ldots,{\bf c}_{m}\\}$ obtained from ${\bf E}$ by
removal of ${\bf c}_{i}$

${\bf D}_{i0}=\\{{\bf c}_{0}={\bf s},{\bf c}_{i}\\},\quad{\bf D}_{ij}=\\{{\bf
c}_{j},{\bf c}_{i}\\},\quad j\neq i,$ (21)

we observe that $L_{i}={\cal D}_{i0}$ and elements of ${\bf d}_{i}$ are given
by $d_{ij}={\cal D}_{ij}$, where ${\cal D}_{ij}=\det{\bf D}_{ij}$.

Introduce an operation $\mathscr{R}_{i}$ acting on $2\times(m+1)$ augmented
matrix ${\bf E}$ as follows – first ${\bf E}$ is split into the column ${\bf
c}_{i}$ and the matrix ${\bf E}_{i}$, and then $m$ determinants ${\cal
D}_{ij}$ are computed to form vector argument ${\cal
E}_{i}=\mathscr{R}_{i}[{\bf E}]$ of the scalar partition

$W_{i}^{2}({\bf s})=W({\cal E}_{i}),\quad{\cal E}_{i}=\mathscr{R}_{i}[{\bf
E}]=\\{{\cal D}_{ij}\\},\quad 0\leq j\leq m,\ j\neq i.$ (22)

Linear independence of columns ${\bf c}_{i}$ implies that all elements in the
generator sets ${\bf d}_{i}$ are nonzero, but some of these might be negative
(say, $d_{ij_{k}}<0$ for $1\leq k\leq K$). Noting that
$(1-t^{-a})^{-1}=-t^{a}(1-t^{a})^{-1}$ we find from (20)

$W(L_{i},{\bf d}_{i})=(-1)^{K}W(L_{i}+\sum_{k=1}^{K}d_{ij_{k}},|{\bf
d}_{i}|),\quad|{\bf d}_{i}|=\\{|d_{ij}|\\}.$ (23)

The solution (20) is not unique as we can eliminate the first row of ${\bf E}$
and obtain

$W({\bf s},{\bf D})=\sum_{i=1}^{m}W(L^{\prime}_{i},{\bf d}^{\prime}_{i}),\quad
L^{\prime}_{i}=-L_{i},\quad{\bf d}^{\prime}=-{\bf d}.$ (24)

As the term $W(L_{i},{\bf d}_{i})$ in (20) and its counterpart
$W(L^{\prime}_{i},{\bf d}^{\prime}_{i})$ in (24) contribute only for
nonnegative $L_{i}$ and $L^{\prime}_{i}$ respectively, we observe that the
terms $W(L_{i},{\bf d}_{i})$ and $W(L^{\prime}_{i},{\bf d}^{\prime}_{i})$
belong to two adjacent chambers separated by the line $L_{i}=0$ on which they
coincide.

##  3 General case of double partition reduction

It was underlined above that reduction of double partition into a sum of
scalar partitions (20) is possible when several conditions on the elements of
generator matrix are met. In this Section we present an alternative approach
that allows to drop these conditions and obtain less compact but equivalent
reduction to scalar partitions.

###  3.1 Partial fraction expansion

Consider expansion of $S_{1}$ in (12) into rational functions $A_{1k}(x)$. To
find these functions write

$S_{1}(x,y_{0})=\prod_{i\neq
1}^{m}\frac{(1-x^{\beta_{1}b_{i}}y_{0}^{\beta_{1}\beta_{i}})}{(1-x^{b_{i}}y_{0}^{\beta_{i}})}=\prod_{i\neq
1}^{m}\left(\sum_{k_{i}=0}^{\beta_{1}-1}x^{k_{i}b_{i}}y_{0}^{k_{i}\beta_{i}}\right).$
(25)

Introduce $(m-1)$-dimensional vectors

$\bm{b}^{\prime}_{1}=\\{b_{2},b_{3},\ldots,b_{m}\\},\
\bm{\beta}^{\prime}_{1}=\\{\beta_{2},\beta_{3},\ldots,\beta_{m}\\},\
\bm{K}^{\prime}_{p}=\\{k_{2},k_{3},\ldots,k_{m}\\},$ (26)

with $0\leq k_{i}\leq\beta_{1}-1$. Expanding r.h.s. of (25) we obtain a sum

$S_{1}(x,y_{0})=\sum_{p=1}^{n_{1}}x^{\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}}y_{0}^{\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1}},\quad
n_{1}=\beta_{1}^{m-1},\quad y_{0}=x^{-b_{1}/\beta_{1}}.$ (27)

For each $\bm{K}^{\prime}_{p}$ we have

$x^{\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}}y_{0}^{\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1}}=x^{\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}}=x^{\nu}=x^{j_{x}}y_{0}^{j_{y}},$

where the rational exponent $\nu$ of $x$ is split into an integer $j_{x}$ and
a fractional $(\nu-j_{x})$ parts. The fractional part of $\nu$ gives an
exponent $j_{y}$ of $y_{0}$, while $x^{j_{x}}$ contributes to $A_{1k}(x)$ in
(12). We observe that

$j_{y}=(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})\bmod{\beta_{1}}.$
(28)

Introduce $L_{1}$-norm of $m$-component vector $|\bm{a}|=\sum_{i=1}^{m}a_{i}$
and use (28) to obtain

$\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1}=\beta_{1}t+j_{y},\
t=\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}\rfloor,\
0\leq t=t(j_{y})\leq\lfloor(B_{1}-j_{y})/\beta_{1}\rfloor,\
B_{1}=(\beta_{1}-1)|\bm{\beta}^{\prime}_{1}|,$ (29)

where $\lfloor\cdot\rfloor$ denotes the greatest integer less than or equal to
real number. This leads to

$x^{\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}}y_{0}^{\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1}}=x^{\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}\rfloor}y_{0}^{(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})\bmod{\beta_{1}}}.$
(30)

and we have for $A_{1}(x,y)$

$A_{1}(x,y)=\frac{1}{\Pi_{1}(x)}\sum_{j_{y}=0}^{\beta_{1}-1}A_{1,j_{y}}(x)y^{j_{y}}\;,$
(31)

with

$A_{1,j_{y}}(x)=\sum_{j_{x}=N_{1}^{-}}^{N_{1}^{+}}a_{1,j_{x},j_{y}}x^{j_{x}},\quad
N_{1}^{-}=\min(\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}\rfloor),\quad
N_{1}^{+}=(\beta_{1}-1)|\bm{b}^{\prime}_{1}|.$ (32)

The integer coefficients $a_{1,j_{x},j_{y}}$ are computed from the relation

$\sum_{j_{y}=0}^{\beta_{1}-1}\sum_{j_{x}=N_{1}^{-}}^{N_{1}^{+}}a_{1,j_{x},j_{y}}x^{j_{x}}y^{j_{y}}=\sum_{p=1}^{n_{1}}x^{\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}\rfloor}y^{(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})\bmod{\beta_{1}}},\quad
n_{1}=\beta_{1}^{m-1},$ (33)

and the details of the computation are presented in Appendix A. The relation
(31) leads to

$T_{1}(x,y)=\frac{A_{1}(x,y)}{1-x^{b_{1}}y^{\beta_{1}}}=\frac{1}{\Pi_{1}(x)(1-x^{b_{1}}y^{\beta_{1}})}\sum_{j_{y}=0}^{\beta_{1}-1}A_{1,j_{y}}(x)y^{j_{y}}\;.$
(34)

###  3.2 Contribution evaluation

Drop the assumption (14) and find $C^{1}_{r,\rho}$

$C^{1}_{r,\rho}=C[x^{r}]\left(\Pi_{1}^{-1}(x)C[y^{\rho}]\left(S_{1}(x,y)/(1-x^{b_{1}}y^{\beta_{1}})\right)\right).$
(35)

Consider the inner term in (35) using (12)

$C[y^{\rho}]\left(\frac{S_{1}(x,y)}{1-x^{b_{1}}y^{\beta_{1}}}\right)=C[y^{\rho}]\left(\sum_{j_{y}=0}^{\beta_{1}-1}\sum_{p=0}^{\infty}A_{1,j_{y}}(x)x^{pb_{1}}y^{j_{y}+p\beta_{1}}\right)=\sum_{j_{y}=0}^{\beta_{1}-1}\sum_{p=0}^{\infty}A_{1,j_{y}}(x)x^{pb_{1}}C[y^{\rho-
j_{y}}]\left(y^{p\beta_{1}}\right).$

The condition $p\beta_{1}=\rho-j_{y}$ on integer value of $p$ reduces the
inner sum to a single term and we find

$C[y^{\rho}]\left(\frac{S_{1}(x,y)}{1-x^{b_{1}}y^{\beta_{1}}}\right)=\sum_{j_{y}=0}^{\beta_{1}-1}A_{1,j_{y}}(x)x^{pb_{1}}=\sum_{j_{y}=0}^{\beta_{1}-1}A_{1,j_{y}}(x)x^{(\rho-
j_{y})b_{1}/\beta_{1}}=\sum_{j_{y}=0}^{\beta_{1}-1}A_{1,j_{y}}(x)x^{\rho
b_{1}/\beta_{1}}y_{0}^{j_{y}}.$ (36)

Note that the same condition on $p$ implies that the sum (36) is equivalent to
a single term

$C[y^{\rho}]\left(S_{1}(x,y)/(1-x^{b_{1}}y^{\beta_{1}})\right)=A_{1,j_{y}}(x)x^{pb_{1}}=A_{1,j_{y}}(x)x^{(\rho-
j_{y})b_{1}/\beta_{1}},\ j_{y}=\rho\bmod{\beta_{1}},$ (37)

where the polynomial $A_{1,j_{y}}(x)$ given by (32) has integer coefficients
$a_{1,j_{x},j_{y}}$ determined by (33). It provides an expression for the
contribution $C^{1}_{r,\rho}$ of the column ${\bf c}_{1}$

$C^{1}_{r,\rho}=C[x^{r}]\left(\Pi_{1}^{-1}(x)\\!\\!\\!\sum_{j=N_{1}^{-}}^{N_{1}^{+}}\\!\\!a_{1,j_{x},j_{y}}x^{j+p}\right)=\\!\\!\sum_{j_{x}=N_{1}^{-}}^{N_{1}^{+}}\\!\\!a_{1,j_{x},j_{y}}C[x^{r-j_{x}-(\rho-
j_{y})b_{1}/\beta_{1}}]\left(\Pi^{-1}_{1}(x)\right).$ (38)

On the other hand using (36) in (35) we obtain

$\displaystyle C^{1}_{r,\rho}$ $\displaystyle=$ $\displaystyle
C[x^{r}]\left(\Pi_{1}^{-1}\sum_{j_{y}=0}^{\beta_{1}-1}A_{1,j_{y}}(x)x^{\rho
b_{1}/\beta_{1}}y_{0}^{j_{y}}\right)=C[x^{r-\rho
b_{1}/\beta_{1}}]\left(\Pi_{1}^{-1}\sum_{j_{y}=0}^{\beta_{1}-1}A_{1,j_{y}}(x)y_{0}^{j_{y}}\right)$
(39) $\displaystyle=$ $\displaystyle C[x^{r-\rho
b_{1}/\beta_{1}}]\left(S_{1}(x,y_{0})/\Pi_{1}\right)=C[x^{r-\rho
b_{1}/\beta_{1}}]\left(A_{1}(x,y_{0})\right).$

Recalling that $y_{0}=x^{-b_{1}/\beta_{1}}$ and comparing (39) to (2.2) we
observe that both approaches produce the same result. Note however that the
transformation

$C[x^{r-\rho
b_{1}/\beta_{1}}]\left(A_{1}(x,x^{-b_{1}/\beta_{1}})\right)=C[x^{r\beta_{1}-\rho
b_{1}}]\left(A_{1}(x^{\beta_{1}},x^{-b_{1}})\right),$

used in (2.2) allowing to obtain (19) and (20) fails when
$b_{1}=0,\beta_{1}>1$. It is important to underline that the presented
algorithm does not impose any restrictions on the value of $\rho$.

Now using the reasoning in Section 2.3 we write

$\displaystyle C^{1}_{r,\rho}=\bar{W}^{2}_{1}({\bf
s})=\sum_{j_{x}=N_{1}^{-}}^{N_{1}^{+}}a_{1,j_{x},j_{y}}W(r-j_{x}-(\rho-
j_{y})b_{1}/\beta_{1},{\bf d}_{1}),$ (40) $\displaystyle
j_{y}=\rho\bmod{\beta_{1}},\quad
N_{1}^{+}=(\beta_{1}-1)|\bm{b}^{\prime}_{1}|,\quad
d_{1j}=b_{j}\beta_{1}-b_{1}\beta_{j},\ j\neq 1.$

The vector ${\bf d}_{1}$ coincides with that of in (20) and its elements can
be computed a $2\times 2$ determinants ${\bf D}_{ik}$ as shown in (21). The
only difference is in the first symbolic argument of SPFs in (43). We observe
that it also can be written as a determinant of $\\{({\bf s}-{\bf
j})/\beta_{1},{\bf c}_{1}\\}$, where ${\bf j}=\\{j_{x},j_{y}\\}^{T}$.
Introduce a modified augmented matrix ${\bf E}_{1}({\bf j})$ and write
$W^{2}_{1}$ in (40) as

$\bar{W}_{1}^{2}({\bf
s})=\\!\\!\sum_{j_{x}=N_{1}^{-}}^{N_{1}^{+}}\\!\\!a_{1,{\bf
j}}W(\mathscr{R}_{1}[{\bf E}_{1}({\bf j})]),\quad{\bf E}_{1}({\bf j})=\\{({\bf
s}-{\bf j})/\beta_{1},{\bf c}_{1},{\bf c}_{2},\ldots,{\bf c}_{m}\\},$

that can be presented in more general form

$\displaystyle\bar{W}_{1}^{2}({\bf s})=\\!\\!\sum_{{\bf j}={\bf
N}_{1}^{-}}^{{\bf N}_{1}^{+}}\\!\\!a_{1,{\bf j}}W(\mathscr{R}_{1}[{\bf
E}_{1}({\bf j})])\delta_{j_{y},\rho\bmod{\beta_{1}}},\quad{\bf
j}=\\{j_{x},j_{y}\\}^{T},$ (41) $\displaystyle{\bf
N}_{1}^{-}=\\{\min(\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}\rfloor),0\\}^{T},\quad{\bf
N}_{1}^{+}=(\beta_{1}-1)\\{|\bm{b}^{\prime}_{1}|,1\\}^{T}.$

Comparing (41) to (22) we present $\bar{W}_{1}^{2}$ as a weighted sum of
$W_{1}^{2}$ with shifted argument

$\bar{W}_{1}^{2}({\bf s})=\sum_{{\bf j}={\bf N}_{1}^{-}}^{{\bf
N}_{1}^{+}}a_{1,{\bf j}}W_{1}^{2}(({\bf s}-{\bf
j})/\beta_{1})\delta_{j_{y},\rho\bmod{\beta_{1}}},\quad\sum_{{\bf j}={\bf
N}_{1}^{-}}^{{\bf N}_{1}^{+}}a_{1,{\bf j}}=\beta_{1}^{m-1}.$ (42)

###  3.3 Column with nonrelatively prime elements

The Cayley reduction method for double partition fails when at least one of
the columns, say the first column ${\bf c}_{1}$, has GCD of its elements
larger than unity $\gcd({\bf c}_{1})=\gcd(b_{1},\beta_{1})=g_{1}>1,$ and we
write $b_{1}=g_{1}b^{\star},\ \beta_{1}=g_{1}\beta^{\star}$. This case can be
treated as discussed above in Sections 3.1 and 3.2 leading to $C_{r,\rho}^{1}$
in (38). The only difference that this expansion cannot be reduced to a single
term as in (39). The reason is that
$y_{0}=x^{-b_{1}/\beta_{1}}=x^{-b^{\star}/\beta^{\star}}$ and thus upper limit
in the sum in (39) would equal not $\beta_{1}$ but $\beta^{\star}$, thus
preventing a desired compactification.

###  3.4 Double partition as a sum of scalar partitions

The solution (38) extended to other terms in PFE gives an expanded form of
double partition equivalent to (20)

$\displaystyle W({\bf s},{\bf D})=\sum_{i=1}^{m}\bar{W}^{2}_{i}({\bf
s}),\quad\bar{W}_{i}^{2}({\bf
s})=\sum_{j_{x}=N_{i}^{-}}^{N_{i}^{+}}a_{i,j_{x},j_{y}}W(r-j_{x}-(\rho-
j_{y})b_{i}/\beta_{i},{\bf d}_{i}),$ (43) $\displaystyle
N_{i}^{+}=(\beta_{i}-1)|\bm{b}^{\prime}_{i}|,\quad
d_{ij}=b_{j}\beta_{i}-b_{i}\beta_{j},\ j\neq i,$ $\displaystyle
N_{i}^{-}=\min(\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{i}-b_{i}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{i})/\beta_{i}\rfloor),\
\bm{K}^{\prime}_{p}=\\{k_{1},k_{2},\ldots,k_{i-1},k_{i+1},\ldots,k_{m}\\},$

where the vectors $\bm{b}^{\prime}_{i},\bm{\beta}^{\prime}_{i}$ are given by

$\bm{b}^{\prime}_{i}=\\{b_{1},b_{2},\ldots,b_{i-1},b_{i+1},\ldots,b_{m}\\},\quad\bm{\beta}^{\prime}_{i}=\\{\beta_{1},\beta_{2},\ldots,\beta_{i-1},\beta_{i+1},\ldots,\beta_{m}\\}.$

Using the notation introduced in (41) present $\bar{W}^{2}_{i}({\bf s})$ in
(43) as

$\displaystyle\bar{W}_{i}^{2}({\bf s})=\sum_{{\bf j}={\bf N}_{i}^{-}}^{{\bf
N}_{i}^{+}}a_{i,{\bf j}}W_{i}^{2}(({\bf s}-{\bf
j})/\beta_{i})\delta_{j_{y},\rho\bmod{\beta_{i}}},\quad{\bf
j}=\\{j_{x},j_{y}\\}^{T},$ (44) $\displaystyle{\bf
N}_{i}^{-}=\\{\min(\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{i}-b_{i}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{i})/\beta_{i}\rfloor),0\\}^{T},\quad{\bf
N}_{i}^{+}=(\beta_{i}-1)\\{|\bm{b}^{\prime}_{i}|,1\\}^{T}.$

Note that when columns ${\bf c}_{i}$ are noncollinear the contributions
$C^{i}_{r,\rho}$ can be computed independently of each other and in this case
one can write an expression for double partition as a mixture of terms
$W^{2}_{i}$ and $\bar{W}^{2}_{j}$.

###  3.5 Double partition with collinear columns

The strongest condition for Cayley algorithm applicability is the linear
independence of the generator matrix columns. It appears that in case when it
fails a double partition can be reduced to a superposition of scalar partition
convolutions.

Assume that vectors corresponding to the first $n$ columns of the generator
matrix D are parallel and rewrite the linear system ${\bf D}\cdot{\bf x}={\bf
s}$ as follows

$\sum_{i=1}^{m}{\bf c}_{i}x_{i}={\bf s},\quad{\bf c}_{i}=u_{i}{\bf
c},\quad{\bf c}=\\{b,\beta\\},\quad 1\leq i\leq n<m,$ (45)

where $u_{i}$ are positive integers. The problem (45) is equivalent to

$\sum_{i=n+1}^{m}{\bf c}_{i}x_{i}={\bf s}-l{\bf
c},\quad\sum_{i=1}^{n}u_{i}x_{i}=l,\quad 0\leq l\leq
l_{max}=\min(r/b,\rho/\beta).$ (46)

Introduce a vector ${\bf u}=\\{u_{1},u_{2},\ldots,u_{n}\\}$ and a new matrix
with $(m-n)$ columns ${\bf D}_{n+1}=\\{{\bf c}_{n+1},\ldots,{\bf c}_{m}\\},$
for which the corresponding double partition $W({\bf D}_{n+1},{\bf s}-l{\bf
c})$ admits a reduction to SPFs either as a sum of $W_{i}^{2}$ or a mixture of
$W^{2}_{i}$ and $\bar{W}^{2}_{j}$. The number of solutions of (46) for given
value of $l$ is equal to a number of solutions of the first equation given by
double partition $W({\bf D}_{n+1},{\bf s}-l{\bf c})$ multiplied by a number of
solutions of the second equation, i.e., scalar partition $W(l,{\bf u})$. Then
the double partition $W({\bf D},{\bf s})$ is equivalent to a convolution

$W({\bf D},{\bf s})=\sum_{l=0}^{l_{max}}W(l,{\bf u})W({\bf D}_{n+1},{\bf
s}-l{\bf c}),\quad l_{max}=\min(r/b,\rho/\beta).$ (47)

##  4 Double partitions with zero column

Computation of contribution to double partition related to a column ${\bf
c}_{1}$ with zero element can be divided into three separate cases: a)
$b_{1}>0,\ \beta_{1}=0$, b) $b_{1}=0,\ \beta_{1}=1$, c) $b_{1}=0,\
\beta_{1}>1$.

###  4.1 $b_{1}>0,\ \beta_{1}=0$

In this case application of (19) gives

$C_{r,\rho}^{1}=C[x^{-\rho
b_{1}}]\left(1/\Pi_{1}(x)\right)=0,\quad\Pi_{1}(x)=\prod_{i\neq
1}^{m}(1-x^{-b_{1}\beta_{i}}),$

as the coefficient of $x$ with negative exponent vanishes. The corresponding
scalar partition function reads

$\displaystyle C_{r,\rho}^{1}=W(-\rho
b_{1},\\{-b_{1}\beta_{2},-b_{1}\beta_{3},\ldots,-b_{1}\beta_{m}\\})=(-1)^{m-1}W(-b_{1}\rho-
b_{1}\sum_{i=2}^{m}\beta_{i},\\{b_{1}\beta_{2},b_{1}\beta_{3},\ldots,b_{1}\beta_{m}\\})$
$\displaystyle=(-1)^{m-1}W(-\rho-\sum_{i=2}^{m}\beta_{i},\\{\beta_{2},\beta_{3},\ldots,\beta_{m}\\})=0,$
(48)

where the last expression is obtained by cancelling the common factor $b_{1}$
in the elements of the augmented single row matrix. Thus all columns with
$\beta_{i}=0$ do not contribute into the sum in (20) and (43). This result is
easy to understand by noticing that for every column with $\beta_{i}=0$ the
corresponding factor in (8) does not depend on $y$ and thus the procedure of
$y$ elimination does not involve these terms. In other words, the
corresponding term $T_{i}$ in the sum in (8) is just equal to zero.

###  4.2 $b_{1}=0,\ \beta_{1}=1$

In a particular case $\beta_{1}=1$ we have (31) with $A_{10}=1$, i.e.,
$S_{1}(x,y)=1$ and $\Pi_{1}(x)=\prod_{i\neq 1}^{m}(1-x^{b_{i}})$. Use (39) to
find

$C_{r,\rho}^{1}=C[x^{r}]\left(1/\Pi_{1}(x)\right)=W(r,{\bf d}_{1}),\quad
d_{1j}=b_{j},\ j\neq 1.$ (49)

It is worth to underline that (49) can be also obtained by direct
implementation of the original Cayley algorithm with $b_{1}=0,\;\beta_{1}=1$
to find from (19)

$C_{r,\rho}^{1}=C[x^{r}]\left(\prod_{i\neq
1}^{m}(1-x^{b_{i}})^{-1}\right)=C[x^{r}]\left(1/\Pi_{1}(x)\right)=W(r,{\bf
d}_{1}),\quad d_{1j}=b_{j},\ j\neq 1.$ (50)

###  4.3 $b_{1}=0,\ \beta_{1}>1$

Consider a case when a single element in the first row of matrix ${\bf D}$
equals zero and apply the algorithm presented above in Sections 3.1, 3.2.
Without loss of generality we can choose this zero column of ${\bf D}$ to be
the first one – ${\bf c}_{1}$, i.e., $b_{1}=0$. In this case (8) turns into

$G({\bf t},{\bf
D})=(1-y^{\beta_{1}})^{-1}\prod_{i=2}^{m}(1-x^{b_{i}}y^{\beta_{i}})^{-1}=G_{1}(x,y)+\sum_{i=2}^{m}T_{i}(x,y),\quad
G_{1}(x,y)=\frac{A_{1}(x,y)}{1-y^{\beta_{1}}},$ (51)

where $T_{i}(x,y)$ is given in (8) and processed as shown above leading to the
term $W(L_{i},{\bf d}_{i})$ in (20).

Repeating the steps discussed in Sections 3.1, 3.2 for $b_{1}=0$ we obtain a
particular case of (40)

$C^{1}_{r,\rho}=\bar{W}^{2}_{1}=\sum_{j_{x}=0}^{N_{1}^{+}}a_{1,j_{x},j_{y}}W(r-j_{x},\beta_{1}{\bf
d}_{1}),\quad j_{y}=\rho\bmod{\beta_{1}},\quad d_{1i}=b_{i},\ i\neq 1.$ (52)

Note that scalar partition function $W(s,\beta_{1}{\bf
d}_{1})=W(s/\beta_{1},{\bf d}_{1})$ is nonzero only if $s$ is divisible by
$\beta_{1}$, and thus only terms with $j_{x}\equiv r\ (\bmod{\beta_{1}})$
contribute into the sum in (52)

$\bar{W}^{2}_{1}=\sum_{j_{x}=0}^{N_{1}^{+}}a_{1,j_{x},j_{y}}W((r-j_{x})/\beta_{1},{\bf
d}_{1}),\ j_{y}=\rho\bmod{\beta_{1}},\ j_{x}\equiv r\ (\bmod{\beta_{1}}),\
d_{1i}=b_{i},\ i\neq 1.$ (53)

Computation of coefficients $a_{1,j_{x},j_{y}}$ is a particular case of the
general algorithm discussed in Appendix A; in Appendix B we present an example
of the reduction of a double partition with zero column to a set of SPFs.

###  4.4 Multiple zero columns

Generalization of the result for a single zero column discussed above to a
case of multiple such columns with $b_{i}=0,\ \beta_{i}>0,\ 1\leq i\leq n<m,$
presents a particular example of linear dependent columns. Use the results
(45-47) presented in Section 3.5 with ${\bf c}=\\{0,1\\},\ u_{i}=\beta_{i},\
1\leq i\leq n<m,$ and $l_{max}=\rho$ to obtain a convolution

$W({\bf D},{\bf s})=\sum_{l=0}^{\rho}W(l,{\bf u})W({\bf D}_{n+1},{\bf s}-l{\bf
c}).$ (54)

Note that the necessity to apply this approach arises quite rarely, namely,
when both rows of the generator matrix ${\bf D}$ have at least two zero
elements.

###  4.5 Alternative expression for zero column contribution

Performing the elimination of the second row we obtain

$\displaystyle W({\bf s},{\bf
D})=\bar{W}^{2}_{1}+\sum_{i=2}^{m}W^{2}_{i}=\bar{W}^{2}_{1}+\sum_{i=2}^{m}W(L_{i},{\bf
d}_{i}),\quad L_{i}=r\beta_{i}-b_{i}\rho,\quad
d_{ij}=b_{j}\beta_{i}-b_{i}\beta_{j},\ j\neq i.$ (55)

The same time the first row elimination as shown in (24) produces

$W({\bf s},{\bf D})=\sum_{i=2}^{m}W(L^{\prime}_{i},{\bf
d}^{\prime}_{i})=\sum_{i=2}^{m}W(-L_{i},-{\bf d}_{i}),$ (56)

as the term corresponding to the first column vanishes. From (55,56) we find
an alternative expression for the contribution of the column with $b_{1}=0$ as

$\bar{W}^{2}_{1}=\sum_{i=2}^{m}\left[W(-L_{i},-{\bf d}_{i})-W(L_{i},{\bf
d}_{i})\right].$ (57)

##  5 Conclusion

The double partition problem subject to specific conditions considered in [2]
admits an elegant compact solution in which the $i$-th column of the positive
generator matrix ${\bf D}$ leads to a single scalar partition contribution
$W_{i}$. This solution is obtained by elimination of a variable of a
corresponding generating function that in its turn requires application of
partial fraction expansion to the generating function. The main steps of
method are discussed in Section 2; it can be applied when the generator matrix
has linearly independent columns, and column elements are positive and
relatively prime.

In Section 3 we present a modification of Cayley method that instead of a
single term $W_{i}$ produces its equivalent $\bar{W}_{i}$ as a weighted sum of
$W_{i}$ with shifted argument. Computation of the coefficients in these
expressions can be reduced to a finite sum of double partitions with generator
matrix of smaller size (Appendix A). We show that the superposition
$\bar{W}_{i}$ is equivalent to the single term $W_{i}$ only when the specific
conditions on the generator matrix elements are met and such compactification
fails when the restrictions are lifted. An example of nonreducible
superposition $\bar{W}_{i}$ is given in Section 3.3 where we consider columns
with elements that are not relatively prime. In case of noncollinear columns
each column can be processed independently and thus a double partition can be
written as a mixture of terms $W_{i}$ and $\bar{W}_{i}$. When a few columns
are linear dependent a double partition leads to a convolution of scalar
partitions derived in Section 3.5.

The case of the generator matrix ${\bf D}$ with zero elements is considered in
Section 4. An example of a reduction of double partition with a single zero
column is presented in Appendix B. Matrix with multiple zero columns discussed
in Section 4.4 is particular case of collinear columns reducible to SPF
convolution.

In conclusion we show that any double partition can be expressed through
superposition or convolution of scalar partitions. All components of this
representation are computable using the same algorithm that makes the double
partition problem self-contained. As each scalar partition term $W(L_{i},{\bf
d}_{i})$ has nonzero contribution only for $L_{i}\geq 0$, reduction of double
partition to SPFs allows simple determination of partition chambers. A
possibility of extension of this result to multiple partitions corresponding
to matrices with more than two rows remains an open question and will be
discussed elsewhere.

## References

  * [1] M. Beck, The Partial-Fractions Method for Counting Solutions to Integral Linear Systems,
Journal of Discrete and Computational Geometry 32 (2004), 437-446.

  * [2] A. Cayley, On a Problem of Double Partitions, Philosophical Magazine XX (1860), 337-341; Coll. Math. Papers, Cambridge Univ. Press, IV (1891), 166-170.
  * [3] G.B. Mathews, On the Partition of Numbers, Proc. London Math. Soc. 28 (1896-97), 486-490.
  * [4] B.Y. Rubinstein, Expression for Restricted Partition Function through Bernoulli Polynomials,
Ramanujan Journal 15 (2008), 177-185.

  * [5] B.Y. Rubinstein, Extension of the Bernoulli and Eulerian Polynomials of Higher Order and Vector Partition Function, arXiv:math/0612076v1.
  * [6] B.Y. Rubinstein, Sylvester-Cayley vector partitions algorithm and the Gaussian polynomials, arXiv:2112.06983v2 [math.CO].
  * [7] B. Sturmfels, Note on Vector Partition Functions, J. Combinat. Theory A72 (1995), 302-309.
  * [8] J.J. Sylvester, On the Problem of the Virgins, and the General Theory of Compound Partitions,
Philosophical Magazine XVI (1858), 371-376; Coll. Math. Papers, Cambridge
Univ. Press, II (1908), 113-117.

  * [9] J.J. Sylvester, On Subinvariants, i.e. Semi-invariants to Binary Quantics of an Unlimited Order. With an Excursus on Rational Fractions and Partitions, American J. of Math. 5 (1882), 79-136; Coll. Math. Papers, Cambridge Univ. Press, III (1909), 568-622.
  * [10] A. Szenes and M. Vergne, Residue Formulae for Vector Partition Functions and Euler-MacLaurin Sums, Adv. in Appl. Math. 30 (2003), 294-342.

Appendices

##  Appendix A Computation of expansion coefficients

Consider computation of integer coefficients $a_{1,j_{x},j_{y}}$ in (32)
defined through relation (33) and the vectors
$\bm{b}^{\prime},\bm{\beta}^{\prime}$ and $\bm{K}^{\prime}_{i},\ 1\leq i\leq
n_{1},$ given by (26). For given value of $j_{y}$ we have from (33)

$\sum_{j_{x}=N_{1}^{-}}^{N_{1}^{+}}a_{1,j_{x},j_{y}}x^{j_{x}}y^{j_{y}}=\sum_{p=1}^{n_{1}}x^{\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}\rfloor}y^{(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})\bmod{\beta_{1}}},$

leading to
$j_{y}=(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})\bmod{\beta_{1}}$, and
for each value of $j_{y}$ we have to find number $a_{1,j_{x},j_{y}}$ of
vectors $\bm{K}^{\prime}_{p}=\\{k_{2},k_{3},\ldots,k_{m}\\}$ satisfying two
Diophantine equations with restriction on $k_{i}$ values

$\displaystyle\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}\rfloor=j_{x},\quad(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})\bmod{\beta_{1}}=j_{y},$
$\displaystyle 0\leq\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1}\leq
B_{1}=(\beta_{1}-1)|\bm{\beta}^{\prime}_{1}|,\quad 0\leq
k_{i}\leq\beta_{1}-1.$ (A1)

The problem (A1) thus asks for a total number of integer solutions of
$(T_{1}(j_{y})+1)$ systems

$\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}\rfloor=j_{x},\
\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1}=j_{y}(t)=j_{y}+\beta_{1}t,\
0\leq t\leq T_{1}(j_{y})=\left\lfloor(B_{1}-j_{y})/\beta_{1}\right\rfloor.$
(A2)

In the first equation in (A2) replace
$\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1}$ by $j_{y}+t\beta_{1}$ and
find
$\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}\lfloor(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})/\beta_{1}\rfloor=\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}-b_{1}t,$
leading to

$\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}=j_{x}(t)=j_{x}+b_{1}t,\quad\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1}=j_{y}(t)=j_{y}+\beta_{1}t,\quad
0\leq k_{i}\leq\beta_{1}-1.$ (A3)

Consider the problem (A3) for a specific value of $t$. To include $(m-1)$
independent conditions $k_{i}\leq\beta_{1}-1$ introduce a set of $(m-1)$
additional variables $\widehat{k}_{i},\ 2\leq i\leq m$ [6]. Then each
inequality $0\leq k_{i}\leq\beta_{1}-1$ turns into an equation
$k_{i}+\widehat{k}_{i}=\beta_{1}-1$. Thus instead of two Diophantine equations
in (A3) we obtain $(m+1)$ equations for $2(m-1)$ variables:

$\sum_{i=2}^{m}(k_{i}b_{i}+\widehat{k}_{i}\widehat{b}_{i})=j_{x}(t),\quad\sum_{i=2}^{m}(k_{i}\beta_{i}+\widehat{k}_{i}\widehat{\beta}_{i})=j_{y}(t),\quad
k_{i}+\widehat{k}_{i}=\beta_{1}-1,\quad\widehat{b}_{i}=\widehat{\beta}_{i}=0.$
(A4)

The system (A4) determines the coefficient $a_{1,j_{x},j_{y}}$ as a sum of
vector partitions

$a_{1,j_{x},j_{y}}=\sum_{t=0}^{T_{1}(j_{y})}W({\bf E}^{m+1}(t)),$ (A5)

where the augmented $(m+1)$-row matrix

${\bf E}^{m+1}(t)=\\{{\bf s}^{m+1}(t),{\bf c}^{m+1}_{2},{\bf
c}^{m+1}_{3},\ldots,{\bf c}^{m+1}_{m},\widehat{\bf c}^{m+1}_{2},\widehat{\bf
c}^{m+1}_{3},\ldots,\widehat{\bf c}^{m+1}_{m}\\}$

is made of vectors ${\bf c}^{m+1}_{i},\ \widehat{\bf c}^{m+1}_{i},\ m>2,$ and
${\bf s}^{m+1}(t),$ with vector upper index showing its length. The matrix
${\bf E}^{m+1}(t)$ reads

$\displaystyle\begin{array}[]{ccccccccccc}\hskip 22.76219pt{\bf s}&\hskip
12.80373pt{\bf c}_{2}&\hskip 2.84526pt{\bf c}_{3}&\ldots&{\bf c}_{m-1}&\hskip
1.13809pt{\bf c}_{m}&\hskip 1.13809pt\widehat{\bf c}_{2}&\hskip
2.56073pt\widehat{\bf c}_{3}&\hskip 1.13809pt\ldots&\widehat{\bf
c}_{m-1}&\hskip-7.39772pt\widehat{\bf c}_{m}\\\ \end{array}$ (A7)
$\displaystyle{\bf E}^{m+1}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{ccccccccccc}j_{x}(t)&b_{2}&b_{3}&\ldots&b_{m-1}&b_{m}&0&0&\ldots&0&0\\\
j_{y}(t)&\beta_{2}&\beta_{3}&\ldots&\beta_{m-1}&\beta_{m}&0&0&\ldots&0&0\\\
\beta_{1}-1&1&0&\ldots&0&0&1&0&\ldots&0&0\\\
\beta_{1}-1&0&1&\ldots&0&0&0&1&\ldots&0&0\\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\\
\beta_{1}-1&0&0&\ldots&1&0&0&0&\ldots&1&0\\\
\beta_{1}-1&0&0&\ldots&0&1&0&0&\ldots&0&1\end{array}\right),$ (A15)

where we added column descriptors ${\bf s},{\bf c}_{i},\widehat{\bf c}_{i}$
for sake of clarity.

Elimination of the last row produces nonzero contributions for columns ${\bf
c}_{m}$ and $\widehat{\bf c}_{m}$ while all other columns have zero in the
last position and thus their contributions vanish. Note that the last column
$\widehat{\bf c}_{m}$ has zeros except the last unit element. We show in
Section 4.2 that for zero column having last element $\beta_{i}=1$ its
contribution to double partition is computed using original Cayley algorithm.
Similar reasoning applies to $\widehat{\bf c}_{m}$ so that we obtain

$W({\bf E}^{m+1})=W(\bar{\bf E}^{m}_{0})+W(\bar{\bf E}^{m}_{1}),$

where

$\displaystyle\begin{array}[]{cccccccccc}\hskip 22.76219pt{\bf s}&\hskip
12.80373pt{\bf c}_{2}&\hskip 2.84526pt{\bf c}_{3}&\ldots&{\bf c}_{m-1}&\hskip
1.13809pt{\bf c}_{m}&\hskip 1.13809pt\widehat{\bf c}_{2}&\hskip
2.56073pt\widehat{\bf c}_{3}&\hskip 1.13809pt\ldots&\widehat{\bf c}_{m-1}\\\
\end{array}$ (A17) $\displaystyle\bar{\bf E}^{m}_{0}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cccccccccc}j_{x}(t)&b_{2}&b_{3}&\ldots&b_{m-1}&b_{m}&0&0&\ldots&0\\\
j_{y}(t)&\beta_{2}&\beta_{3}&\ldots&\beta_{m-1}&\beta_{m}&0&0&\ldots&0\\\
\beta_{1}-1&1&0&\ldots&0&0&1&0&\ldots&0\\\
\beta_{1}-1&0&1&\ldots&0&0&0&1&\ldots&0\\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\\
\beta_{1}-1&0&0&\ldots&1&0&0&0&\ldots&1\end{array}\right),$ (A24)

and

$\displaystyle\begin{array}[]{cccccccccc}\hskip 48.36967pt{\bf s}&\hskip
45.5244pt{\bf c}_{2}&\hskip 2.84526pt{\bf c}_{3}&\ldots&{\bf c}_{m-1}&\hskip
1.13809pt\widehat{\bf c}_{2}&\hskip 2.56073pt\widehat{\bf c}_{3}&\hskip
1.13809pt\ldots&\hskip-1.70717pt\widehat{\bf
c}_{m-1}&\hskip-4.55244pt\widehat{\bf c}_{m}\\\ \end{array}$ (A26)
$\displaystyle\bar{\bf E}^{m}_{1}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cccccccccc}j_{x}(t)+b_{m}-b_{m}\beta_{1}&b_{2}&b_{3}&\ldots&b_{m-1}&0&0&\ldots&0&-b_{m}\\\
j_{y}(t)+\beta_{m}-\beta_{m}\beta_{1}&\beta_{2}&\beta_{3}&\ldots&\beta_{m-1}&0&0&\ldots&0&-\beta_{m}\\\
\beta_{1}-1&1&0&\ldots&0&1&0&\ldots&0&0\\\
\beta_{1}-1&0&1&\ldots&0&0&1&\ldots&0&0\\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\\
\beta_{1}-1&0&0&\ldots&1&0&0&\ldots&1&0\end{array}\right).$ (A33)

Note that number of columns in $\bar{\bf E}^{m}_{i}$ is $2m-2$ – one less as
in ${\bf E}^{m+1}$. It is also worth to mention that the structure of the last
$(m-1)$ rows of matrix ${\bf E}^{m+1}$ guarantees that value of the elements
of all its rows except of the first two is not affected by the elimination
procedure and thus to save space we would show only first two rows of the
transformed matrices.

The matrix $\bar{\bf E}^{m}_{1}$ has negative elements in column $\widehat{\bf
c}_{m}$ and we apply a conversion procedure that generalizes the one employed
in (23)

$(1-x^{-b}y^{-\beta})^{-1}=-x^{b}y^{\beta}(1-x^{b}y^{\beta})^{-1},$

to obtain $W({\bf E}^{m+1})=W({\bf E}^{m}_{0})-W({\bf E}^{m}_{1}),$ where
${\bf E}^{m}_{0}=\bar{\bf E}^{m}_{0}$ and

$\displaystyle\begin{array}[]{cccccccccc}\hskip 34.1433pt{\bf s}&\hskip
30.72897pt{\bf c}_{2}&\hskip 2.56073pt{\bf c}_{3}&\hskip 1.13809pt\ldots&{\bf
c}_{m-1}&\hskip 2.84526pt\widehat{\bf c}_{2}&\hskip 2.84526pt\widehat{\bf
c}_{3}&\hskip 0.0pt\ldots&\hskip-3.98337pt\widehat{\bf
c}_{m-1}&\hskip-8.25128pt\widehat{\bf c}_{m}\\\ \end{array}$ (A35)
$\displaystyle{\bf E}^{m}_{1}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cccccccccc}j_{x}(t)-b_{m}\beta_{1}&b_{2}&b_{3}&\ldots&b_{m-1}&0&0&\ldots&0&b_{m}\\\
j_{y}(t)-\beta_{m}\beta_{1}&\beta_{2}&\beta_{3}&\ldots&\beta_{m-1}&0&0&\ldots&0&\beta_{m}\\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\\
\end{array}\right).$ (A39)

We observe that the differences between ${\bf E}^{m}_{1}$ and ${\bf
E}^{m}_{0}$ include transformation of the column ${\bf c}_{m}$ in ${\bf
E}^{m}_{0}$ into $\widehat{\bf c}_{m}$ in ${\bf E}^{m}_{1}$ as well as first
two elements of the argument column ${\bf s}^{m}_{i}$ of the matrix ${\bf
E}^{m}_{i}$. Namely, ${\bf s}^{m}_{1}={\bf s}^{m}-\beta_{1}{\bf c}^{m}_{m}$
and ${\bf s}^{m}_{0}={\bf s}^{m}$, where ${\bf s}^{m}$ (${\bf c}^{m}_{m}$) are
obtained from ${\bf s}^{m+1}$ (${\bf c}^{m+1}_{m}$) belonging to matrix ${\bf
E}^{m+1}$ in (A15) by dropping the last element of the column.

Noting that both ${\bf E}^{m}_{0}$ and ${\bf E}^{m}_{1}$ have only two unit
elements in the last row generate four matrices ${\bf E}^{m-1}_{ij},\
i,j=0,1,$ and find

$W({\bf E}^{m}_{0})=W({\bf E}^{m-1}_{00})-W({\bf E}^{m-1}_{01}),\quad W({\bf
E}^{m}_{1})=W({\bf E}^{m-1}_{10})-W({\bf E}^{m-1}_{11}),$

so that

$W({\bf E}^{m+1})=W({\bf E}^{m-1}_{00})-W({\bf E}^{m-1}_{01})-W({\bf
E}^{m-1}_{10})+W({\bf E}^{m-1}_{11}),$ (A40)

with

$\displaystyle\begin{array}[]{cccccccccc}\hskip 17.07164pt{\bf s}&\hskip
9.95845pt{\bf c}_{2}&\hskip 2.56073pt{\bf c}_{3}&\hskip 1.13809pt\ldots&{\bf
c}_{m-1}&{\bf c}_{m}&\hskip 0.0pt\widehat{\bf c}_{2}&\hskip
5.69054pt\widehat{\bf c}_{3}&\hskip 0.0pt\ldots&\hskip-4.55244pt\widehat{\bf
c}_{m-2}\\\ \end{array}$ (A42) $\displaystyle{\bf E}^{m-1}_{00}$
$\displaystyle=$
$\displaystyle\left(\begin{array}[]{cccccccccc}j_{x}(t)&b_{2}&b_{3}&\ldots&b_{m-1}&b_{m}&0&0&\ldots&0\\\
j_{y}(t)&\beta_{2}&\beta_{3}&\ldots&\beta_{m-1}&\beta_{m}&0&0&\ldots&0\\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\\
\end{array}\right),$ (A46) $\displaystyle\begin{array}[]{ccccccccc}\hskip
34.1433pt{\bf s}&\hskip 41.54103pt{\bf c}_{2}&\hskip 2.56073pt{\bf
c}_{3}&\hskip 1.13809pt\ldots&{\bf c}_{m}&\hskip 2.84526pt\widehat{\bf
c}_{2}&\hskip 2.84526pt\widehat{\bf c}_{3}&\hskip 0.0pt\ldots&\hskip
0.0pt\widehat{\bf c}_{m-1}\\\ \end{array}$ (A48) $\displaystyle{\bf
E}^{m-1}_{01}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{ccccccccc}j_{x}(t)-b_{m-1}\beta_{1}&b_{2}&b_{3}&\ldots&b_{m}&0&0&\ldots&b_{m-1}\\\
j_{y}(t)-\beta_{m-1}\beta_{1}&\beta_{2}&\beta_{3}&\ldots&\beta_{m}&0&0&\ldots&\beta_{m-1}\\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\\
\end{array}\right),$ (A52) $\displaystyle\begin{array}[]{ccccccccc}\hskip
34.1433pt{\bf s}&\hskip 31.01347pt{\bf c}_{2}&\hskip 2.56073pt{\bf
c}_{3}&\hskip 1.13809pt\ldots&{\bf c}_{m-1}&\hskip 2.84526pt\widehat{\bf
c}_{2}&\hskip 2.84526pt\widehat{\bf c}_{3}&\hskip 0.0pt\ldots&\hskip
0.0pt\widehat{\bf c}_{m}\\\ \end{array}$ (A54) $\displaystyle{\bf
E}^{m-1}_{10}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{ccccccccc}j_{x}(t)-b_{m}\beta_{1}&b_{2}&b_{3}&\ldots&b_{m-1}&0&0&\ldots&b_{m}\\\
j_{y}(t)-\beta_{m}\beta_{1}&\beta_{2}&\beta_{3}&\ldots&\beta_{m-1}&0&0&\ldots&\beta_{m}\\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\\
\end{array}\right),$ (A58)

and

$\displaystyle\begin{array}[]{cccccccccc}\hskip 59.75078pt{\bf s}&\hskip
52.63759pt{\bf c}_{2}&\hskip 2.56073pt{\bf c}_{3}&\hskip 0.56905pt\ldots&{\bf
c}_{m-2}&\hskip 2.84526pt\widehat{\bf c}_{2}&\hskip 2.84526pt\widehat{\bf
c}_{3}&\hskip 0.0pt\ldots&\hskip 0.0pt\widehat{\bf c}_{m-1}&\hskip
0.0pt\widehat{\bf c}_{m}\\\ \end{array}$ (A60) $\displaystyle{\bf
E}^{m-1}_{11}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cccccccccc}j_{x}(t)-(b_{m-1}+b_{m})\beta_{1}&b_{2}&b_{3}&\ldots&b_{m-2}&0&0&\ldots&b_{m-1}&b_{m}\\\
j_{y}(t)-(\beta_{m-1}+\beta_{m})\beta_{1}&\beta_{2}&\beta_{3}&\ldots&\beta_{m-2}&0&0&\ldots&\beta_{m-1}&\beta_{m}\\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\\
\end{array}\right).$ (A64)

The argument columns ${\bf s}^{m-1}_{ij}$ of ${\bf E}^{m-1}_{ij}$ in (A40)
read

${\bf s}^{m-1}_{11}={\bf s}^{m-1}-\beta_{1}({\bf c}^{m-1}_{m}+{\bf
c}^{m-1}_{m-1}),\quad{\bf s}^{m-1}_{10}={\bf s}^{m-1}-\beta_{1}{\bf
c}^{m-1}_{m},\quad{\bf s}^{m-1}_{01}={\bf s}^{m-1}-\beta_{1}{\bf
c}^{m-1}_{m-1},\quad{\bf s}^{m-1}_{00}={\bf s}^{m-1}.$

Note that ${\bf s}^{m-1}$ and ${\bf c}^{m-1}_{i}$ represent first $(m-1)$
elements of the vectors ${\bf s}^{m+1}$ and ${\bf c}^{m+1}_{i}$ (making up the
matrix ${\bf E}^{m+1}$) respectively. We find after the second transformation

$W({\bf E}^{m+1})=\sum_{i,j=0}^{1}(-1)^{i+j}W({\bf E}^{m-1}_{ij}),\quad{\bf
s}^{m-1}_{ij}(t)={\bf s}^{m-1}(t)-\beta_{1}\sum_{i,j=0}^{1}(i{\bf
c}^{m-1}_{m}+j{\bf c}^{m-1}_{m-1}).$ (A65)

It is easy to observe a pattern of iterative transformation of augmented
matrices. Introduce a vectorial index ${\bf
i}(r)=\\{i_{1},i_{2},\ldots,i_{r}\\}$ having $r$ binary elements $i_{k}=0,1$,
and denote its $L_{1}$-norm as $|{\bf i}(r)|=\sum_{k=1}^{r}i_{k}$. Then we
have for $r$-th transformation step

$W({\bf E}^{m+1})=\\!\\!\\!\sum_{{\bf i}(r)={\bf 0}}^{{\bf 1}}(-1)^{|{\bf
i}(r)|}W({\bf E}^{m+1-r}_{{\bf i}(r)}),\quad{\bf s}^{m+1-r}_{{\bf i}(r)}={\bf
s}^{m+1-r}-\beta_{1}\\!\\!\\!\\!\sum_{{\bf i}(r)={\bf 0}}^{{\bf
1}}\sum_{k=1}^{r}i_{k}{\bf c}^{m+1-r}_{m+1-k}.$ (A66)

After $(m-1)$ transformations we reduce $W({\bf E}^{m+1})$ to

$W({\bf E}^{m+1})=\\!\\!\\!\\!\\!\\!\sum_{{\bf i}(m-1)={\bf 0}}^{{\bf
1}}\\!\\!\\!\\!\\!\\!(-1)^{|{\bf i}(m-1)|}W({\bf E}^{2}_{{\bf
i}(m-1)}),\quad{\bf s}^{2}_{{\bf i}(m-1)}(t)={\bf
s}^{2}(t)-\beta_{1}\\!\\!\\!\\!\\!\\!\sum_{{\bf i}(m-1)={\bf 0}}^{{\bf
1}}\sum_{k=1}^{m-1}i_{k}{\bf c}^{2}_{m+1-k},$ (A67)

with ${\bf s}^{2}(t)={\bf
s}^{2}(j_{x}(t),j_{y}(t))=\\{j_{x}+b_{1}t,j_{y}+\beta_{1}t\\}^{T}$, to
computation of $2^{m-1}$ double partitions $W({\bf E}^{2}_{{\bf i}(m-1)})$ of
augmented matrices

${\bf E}^{2}_{{\bf i}(m-1)}(j_{x}(t),j_{y}(t))=\\{{\bf s}^{2}_{{\bf
i}(m-1)}(j_{x}(t),j_{y}(t)),{\bf c}^{2}_{2},{\bf c}^{2}_{3},\ldots,{\bf
c}^{2}_{m}\\},$ (A68)

with the columns ${\bf c}^{2}_{i}=\\{b_{i},\beta_{i}\\}^{T},\ 2\leq i\leq m,$
forming a smaller generator matrix

${\bf D}^{2}=\\{{\bf c}^{2}_{2},{\bf c}^{2}_{3},\ldots,{\bf
c}^{2}_{m}\\}=\left(\begin{array}[]{ccccc}b_{2}&b_{3}&\ldots&b_{m-1}&b_{m}\\\
\beta_{2}&\beta_{3}&\ldots&\beta_{m-1}&\beta_{m}\end{array}\right).$ (A69)

Introduce a reverse two-row matrix

$\bar{\bf D}^{2}=\\{{\bf c}^{2}_{m},{\bf c}^{2}_{m-1},\ldots,{\bf
c}^{2}_{3},{\bf c}^{2}_{2}\\},$

define a “scalar product” through the discrete convolution

$\bar{\bf D}^{2}\cdot{\bf i}(m-1)=\sum_{k=1}^{m-1}i_{k}{\bf c}^{2}_{m+1-k},$

and rewrite ${\bf s}^{2}_{{\bf i}(m-1)}(t)$ in (A67) as

${\bf s}^{2}_{{\bf i}(m-1)}(t)={\bf
s}(t)-\beta_{1}\\!\\!\\!\\!\\!\\!\sum_{{\bf i}(m-1)={\bf 0}}^{{\bf
1}}\\!\\!\\!\\!\\!\\!\ \bar{\bf D}^{2}\cdot{\bf i}(m-1).$ (A70)

Finally we use (A67) in (A3) to obtain the coefficient $a_{1,j_{x},j_{y}}$ as

$a_{1,j_{x},j_{y}}=\sum_{t=0}^{T_{1}(j_{y})}\sum_{{\bf i}(m-1)={\bf 0}}^{{\bf
1}}(-1)^{|{\bf i}(m-1)|}W({\bf E}^{2}_{{\bf i}(m-1)}(j_{x}(t),j_{y}(t))),$
(A71)

where $T_{1}(j_{y})$ is defined in (A2) and ${\bf E}^{2}_{{\bf
i}(m-1)}(j_{x}(t),j_{y}(t))$ in (A68). It is important to underline that each
double partition term in (A71) is computable using original Cayley algorithm.

The coefficients $a_{1,j_{x},j_{y}}$ for zero column contribution are computed
using (A71) with $j_{x}(t)=j_{x}$.

##  Appendix B Double partition with zero column: an example

Consider a double partition defined by the following augmented matrix

${\bf E}=\left(\begin{array}[]{ccccc}s_{1}&0&1&1&3\\\
s_{2}&4&2&3&1\end{array}\right),$ (B1)

with a zero column ${\bf c}_{1}=\\{0,4\\}^{T}$ and use the results presented
in Section 4 to reduce the VPF to a sum of SPFs. The terms $W^{2}_{i},\
i=2,3,4$ in (55) are computed using original Cayley algorithm and read

$\displaystyle W^{2}_{2}$ $\displaystyle=$ $\displaystyle
W(2s_{1}-s_{2}-5,\\{1,5,4\\}),$ $\displaystyle W^{2}_{3}$ $\displaystyle=$
$\displaystyle-W(3s_{1}-s_{2}-4,\\{1,8,4\\}),$ (B2) $\displaystyle W^{2}_{4}$
$\displaystyle=$ $\displaystyle-W(s_{1}-3s_{2}-25,\\{5,8,12\\}).$

The term $\bar{W}^{2}_{1}$ generated by elimination of zero column ${\bf
c}_{1}$ requires computation of the integer coefficients $a_{1,j_{x},j_{y}}$
in (52) where $0\leq j_{y}\leq 3$ and $0\leq j_{x}\leq 15$. We use the direct
procedure based of relation (33) with $b_{1}=0$. Start with vectors
$\bm{b}^{\prime}_{1},\bm{\beta}^{\prime}_{1}$ and set of vectors
$\bm{K}^{\prime}_{p}$ introduced in (26):

$\bm{b}^{\prime}_{1}=\\{1,1,3\\},\quad\bm{\beta}^{\prime}_{1}=\\{2,3,1\\},\quad\bm{K}^{\prime}_{p}=\\{k_{2},k_{3},k_{4}\\},\quad
0\leq k_{i}\leq 3.$

For every vector $\bm{K}^{\prime}_{p}$ compute
$x^{\bm{K}^{\prime}_{p}\cdot\bm{b}^{\prime}_{1}}$ and
$j_{y}=(\bm{K}^{\prime}_{p}\cdot\bm{\beta}^{\prime}_{1})\bmod{\beta_{1}}$ and
for given $j_{y}$ collect all terms $x^{j_{x}}$ that allows to evaluate the
coefficients $a_{1,j_{x},j_{y}}$. The results are presented in the table
below.

$\begin{array}[]{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline\cr
j_{x}&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\ \hline\cr
j_{y}=0&1&0&1&1&1&1&1&2&1&2&1&1&1&1&1&0\\\
j_{y}=1&0&0&1&2&1&2&1&1&1&1&2&1&2&1&0&0\\\
j_{y}=2&0&1&1&1&1&1&2&1&2&1&1&1&1&1&0&1\\\
j_{y}=3&0&1&0&1&2&1&2&1&1&2&1&2&1&0&1&0\\\ \hline\cr\end{array}$

Using this table we write following (52,53)

$\bar{W}^{2}_{1}=\sum_{j_{x}=0}^{15}a_{1,j_{x},j_{y}}W(s_{1}-j_{x},\\{4,4,12\\})=\sum_{j_{x}=0}^{15}a_{1,j_{x},j_{y}}W((s_{1}-j_{x})/4,\\{1,1,3\\}),$

and arrive at the desired expression of the double partition through scalar
partitions

$\displaystyle W({\bf E})$ $\displaystyle=$ $\displaystyle
W(2s_{1}-s_{2}-5,\\{1,5,4\\})-W(3s_{1}-s_{2}-4,\\{1,8,4\\})$ (B3)
$\displaystyle-$ $\displaystyle
W(s_{1}-3s_{2}-25,\\{5,8,12\\})+\sum_{j_{x}=0}^{15}a_{1,j_{x},j_{y}}W((s_{1}-j_{x})/4,\\{1,1,3\\}).$

Employing the algorithm presented in Appendix A, we have $m=4$, perform three
iterations and generate eight two-row matrices ${\bf E}^{2}_{{\bf
i}(3)}(j_{x},j_{y}(t))$ in (A68) with the following argument columns

$\displaystyle{\bf s}^{2}_{000}=\\{j_{x},j_{y}(t)\\}^{T},\ {\bf
s}^{2}_{001}=\\{j_{x}-4,j_{y}(t)-8\\}^{T},\ {\bf
s}^{2}_{010}=\\{j_{x}-4,j_{y}(t)-12\\}^{T},$ $\displaystyle{\bf
s}^{2}_{011}=\\{j_{x}-8,j_{y}(t)-20\\}^{T},\ {\bf
s}^{2}_{100}=\\{j_{x}-12,j_{y}(t)-4\\}^{T},\ {\bf
s}^{2}_{101}=\\{j_{x}-16,j_{y}(t)-12\\}^{T},$ $\displaystyle{\bf
s}^{2}_{110}=\\{j_{x}-16,j_{y}(t)-16\\}^{T},\ {\bf
s}^{2}_{111}=\\{j_{x}-20,j_{y}(t)-24\\}^{T},$

while the columns ${\bf c}^{2}_{i}=\\{b_{i},\beta_{i}\\}^{T},\ 2\leq i\leq m,$
form a generator matrix

${\bf D}^{2}=\left(\begin{array}[]{ccc}1&1&3\\\ 2&3&1\end{array}\right).$

Applying (20) together with (A71) we obtain the coefficients
$a_{1,j_{x},j_{y}}$ shown in the table above.


# Push-MOG: Efficient Pushing to Consolidate
Polygonal Objects for Multi-Object Grasping

Shrey Aeron1, Edith Llontop1, Aviv Adler1, Wisdom C. Agboh1,2, Mehmet Dogar2,
and Ken Goldberg1 1The AUTOLab at UC Berkeley (automation.berkeley.edu)
{aeron, goldberg} @berkeley.edu2University of Leeds, UK

###### Abstract

Recently, robots have seen rapidly increasing use in homes and warehouses to
declutter by collecting objects from a planar surface and placing them into a
container. While current techniques grasp objects individually, Multi-Object
Grasping (MOG) can improve efficiency by increasing the average number of
objects grasped per trip (OpT). However, grasping multiple objects requires
the objects to be aligned and in close proximity. In this work, we propose
_Push-MOG_ , an algorithm that computes “fork pushing” actions using a
parallel-jaw gripper to create graspable object clusters. In physical
decluttering experiments, we find that Push-MOG enables multi-object grasps,
increasing the average OpT by $\boldsymbol{34\%}$. Code and videos are
available at https://sites.google.com/berkeley.edu/push-mog.

##  I Introduction

Efficient object manipulation is a key task in industrial, commercial, and
domestic robotics, incorporating elements from motion planning, grasping, and
task planning [1, 2, 3, 4]. In particular, many applications focus on the task
of transferring a collection of objects from a surface into a bin or basket,
for the purpose of either clearing the surface or preparing the objects for
transportation to another location. This task is typically solved by picking
one object at a time. However, an alternative approach of removing multiple
objects at once with _multi-object grasping_ (MOG) has received relatively
little attention. MOG can provide better efficiency than traditional single-
object grasping [5, 6], especially when the bin is relatively far away. Prior
work on MOG mainly focused on developing techniques (such as MOG-Net [6]) for
detecting and executing effective multi-object grasps in a scene. However,
grasping multiple objects at once requires all of them to be close enough to
fit within the gripper width, which may be rare when the objects are
distributed randomly. Thus, to create graspable object clusters, pushing [7,
8] can be useful.

In this work, we propose _Push-MOG_ , an algorithm that uses pushes to
increase the average number of objects transported per trip to the bin. Push-
MOG uses hierarchical clustering to identify clusters of objects which could
potentially be grasped together. To execute stable pushes on polygonal objects
with a parallel-jaw gripper, Push-MOG utilizes _fork pushing_ , in which the
jaw is opened to an appropriate width and the object is pushed perpendicular
to the jaw, thus enabling a variety of stable pushes (see Fig. 3).

Figure 1: An example of Push-MOG pushing and grasping objects into a cluster.
(1) A cluster is identified containing three objects; (2) two objects are
moved toward the center object using fork pushing. (3) Once the cluster fits
within the robot’s gripper, (4) the gripper closes to create a tight fit and
grasps the objects that will be transported to the bin.

We also propose (mean) _objects per trip_ (OpT) as a metric for evaluating the
effectiveness of multi-object grasps. Thus, in single-object grasping, the OpT
is $1$ (or slightly less than $1$ due to failed grasp attempts), whereas MOG
improves efficiency by increasing OpT. We evaluate Push-MOG in a physical
environment consisting of randomly-distributed polygonal objects on a flat
surface, in which the robot executes both grasps and pushes using a parallel-
jaw gripper. We consider two baselines: (i) Single-Object Grasping (SOG),
which removes objects at random, one at a time; (ii) and MOG-Net, which
searches for multi-object grasps but does not apply rearrange objects with
pushes. In physical robot experiments, we find that prior work (MOG-Net)
achieves an OpT of $\approx 1$, suggesting that naturally occurring multi-
object grasps are rare, while Push-MOG achieves an OpT of $1.339$, though at a
cost of extra time for executing pushes. Since increasing OpT is more valuable
when the bin is further away, Push-MOG can improve picking efficiency when
trips are long. We make the same assumptions as Agboh et al. [5]: that the
objects are extruded convex polygons, and have roughly uniform mass so that
their centers of mass coincide with their geometric centers. However, unlike
[5], we also assume the objects are stable and do not topple when pushed.

In this work, we make the following contributions:

  * •

We formulate a new variant of the decluttering problem, in which a robot uses
pushing actions to increase the number of objects it can move simultaneously
to the bin. To solve this problem, we propose and implement Push-MOG. We also
propose objects per trip (OpT) as a metric for evaluating the effectiveness of
MOG algorithms.

  * •

We propose and implement _fork pushing_ as a way to quickly and stably move
objects on a work surface using a parallel-jaw gripper.

  * •

We evaluate the performance of Push-MOG and two baselines (one using only
single-object grasping and one using multi-object grasping without pushes) and
find that Push-MOG increases OpT by $34\%$.

##  II Related Work

###  II-A Multi-object grasps

Prior work on multi-object grasping [9, 10, 11, 12] used multi-fingered robot
hands and proposed conditions for a stable grasp of objects, focusing on
numerical simulations without physical robot multi-object grasps or a focus on
automation. Chen et al. [13] propose a method for a robot to dip its gripper
inside a pile of identical spherical objects, close it, and estimate the
number of grasped objects. Shenoy et al. [14] focus on the same problem but
with the goal of transporting the picked spherical objects to another bin.

Another line of work has focused on designing appropriate grippers for picking
up multiple objects at once. Jiang et. al. [15] proposed a multiple suction
cup vacuum gripper, while Nguyen et. al. [16] proposed a soft gripper based on
elastic wires for multi-object grasping.

Our work is focused on efficiently rearranging scenes with pushes [17, 18, 19,
20] before multi-object grasping. Sakamoto et al. [21] proposed such a picking
system where the robot first uses pushing [22, 23, 24], to move one cuboid to
the other and thereafter grasp both cuboids. Our approach handles any multi-
sided polygonal object and focuses on large-scale problems where clustering is
required to decide which objects to push and where.

###  II-B Pushing

Pushing is a fundamental primitive in robot manipulation [25]. Robotic pushing
has been used to move a target object to a goal location [8, 26], rearrange a
working surface [27, 28], and retrieve items from cluttered shelves [19, 20,
29].

During robotic pushing, uncertainty in the state, control, and model can
result in failures [30, 31]. Prior work [32, 7] has trained networks to
generate robust pushing actions. Others have taken an open-loop approach to
generate these robust pushes [33, 34]. For example, Johnson et. al. [35]
propose robustness metrics and use them to generate robust open-loop pushes.
They exploit gripper and object geometries to generate these robust pushes. We
take a similar open-loop pushing approach and leverage object and gripper
geometries to generate robust pushes.

###  II-C Point Clustering

Prior work in point clustering is well-established [36, 37], specifically in
the hierarchical variant [38, 39], which aims to cluster data in an
unsupervised fashion. This method constructs a distance-based tree that forms
clusters of points from the bottom up which is then split at a ‘height’ to
determine the final clusters. Additional work by Dao et al. [40] explores
clustering with human-defined constraints. It introduces the idea of
simplifying and solving NP-Hard problems by constraining them through a limit
on inter-cluster distance metrics, such as maximum cluster diameter, or
within-cluster variation [40]. In this work, we use a distance-based
hierarchical clustering algorithm but split object clusters to satisfy gripper
width constraints.

##  III Problem Statement

Agboh et al [5] studied the problem of using an overhead camera and a
parallel-jaw gripper to transport a collection $O$ of extruded polygonal
convex objects (prisms) from a flat work surface to a bin or box adjacent to
the workspace by taking advantage of _multi-object grasping_ , in which
multiple objects are grasped simultaneously and transported together to the
bin.

In this work, we extend this problem by adding the _fork push_ action, in
which the gripper pushes an object. By doing so, the robot can arrange the
objects to create more efficient grasps. Since pushing is faster to execute
than grasping and the objects are typically closer to each other than to the
bin, using pushes to facilitate multi-object grasps can reduce the number of
trips needed to clear the objects. As in Agboh et al. [6], we consider a
frictional model of planar grasping, which not only corresponds better to real
grasping problems but also permits a larger set of stable grasps, thus
allowing the algorithm to consider a wider range of potential solutions.

###  III-A State, Action, and Objective

Let the set of objects on the work surface be
$O=\\{o_{0},o_{1},\dots,o_{N_{o-1}}\\}$ where each $o_{i}$ is a convex
polygonal object and $N_{o}$ is the number of objects on the work surface. The
robot executes a sequence of _pushes_ and transports ( which we call _trips_);
each push translates and/or rotates a single object in the workspace without
colliding with others, while each trip grasps a set of closely clustered
objects and transfers them to the bin.

We divide this problem into three sub-problems:

  1. 1.

_Clustering:_ Divide the objects into clusters. No cluster should contain more
objects than can be stably grasped by the gripper.

  2. 2.

_Pushing:_ Push the objects in each cluster close together.

  3. 3.

_Trip:_ Perform grasps (containing as many objects as possible each time) and
transport the grasped objects to the bin until no clusters remain.

Due to the inherent uncertainty of working with real objects, a grasp might
not get every object in a cluster, so a cluster may need multiple grasps to
clear completely. The clustering step is purely computational and does not
involve any physical action.

Since we don’t optimize an explicit objective in the clustering or pushing
problems, we instead aim to guide the choice of algorithm to maximize overall
OpT.

###  III-B The Clustering Problem

In the clustering stage, the goal is to partition the set of objects $O$ into
clusters in such a way that (i) the objects in any cluster are close together
and (ii) each cluster consists of objects that can be stably grasped together
(provided they are pushed into an appropriate configuration). Finally, since
the goal of clustering the objects is to reduce the number of grasps necessary
to clear the workspace, a good overall clustering will partition the objects
into as few clusters as possible, as each cluster roughly corresponds to one
grasp. We denote the output of the clustering algorithm as a list of clusters
$C$, and each individual cluster as $c\subseteq O$ (since a cluster is a set
of objects).

In this problem, each object $o$’s position is represented by its geometric
centroid, which we denote $M_{o}$. This allows the application of an
appropriately modified version of the hierarchical clustering algorithm (which
clusters points).

An important characteristic of each object $o$ is its _minimum final grasp
diameter_ $d^{*}_{o}$, corresponding to the minimum width of a stable single-
object grasp on $o$. Then, given a cluster $c$, we denote the _minimum grasp
diameter of $c$_ as $d^{*}_{c}=\sum_{o\in c}d^{*}_{o}$. The gripper also has a
width $d^{\text{(gr)}}$, and if $d^{*}_{c}>d^{\text{(gr)}}$ we regard cluster
$c$ as ungraspable (thus requiring division into smaller clusters)111It is
possible that even if $d^{*}_{c}\leq d^{\text{(gr)}}$ the cluster does not
have a stable grasp. For example, a cluster of three identical equilateral
triangles cannot be stably grasped at all..

Also, it is important for the clusters to not interfere with each other during
the pushing step, which might happen if clusters are spatially intermingled.
While point clustering usually avoids this (such clusters are locally non-
optimal), the grasp diameter constraint may make such a solution to be
‘optimal’ unless it is specifically excluded. We thus add a constraint that
for any $c_{1},c_{2}\in C$, the centroids of the objects in $c_{1}$ (i.e. the
set $\\{M_{o}:o\in c_{1}\\}$) are linearly separable from the centroids of the
objects in $c_{2}$.

The clustering problem is then defined to partition $O$ into a set of clusters
$C$ such that: (1) $d^{*}_{c}\leq d^{(\text{gr})}$ for all $c\in C$; (2) any
$c_{1},c_{2}\in C$ have a line which separates the centers of mass of the
objects they contain; (3) each cluster has small pairwise distances between
its objects; and (4) there are few clusters overall. It is solved using a
modified hierarchical clustering algorithm.

###  III-C The Pushing and Grasping Problems

After the clusters have been defined, the next step is to push each cluster
closer together to make multi-object grasping more effective (see Fig. 1 for
an illustration). We assume that (due to the separating line constraint in the
clustering problem) each cluster can be treated as a separate instance of the
pushing problem.

Finally, once the pushing is done, we move the objects to the bin via multi-
object grasping. As in [6], the objective is to move the objects to the bin
with as few grasps as possible (without pushing, as that has already been
done).

Figure 2: As illustrated in Fig. 1, Push-MOG uses “fork pushes” to consolidate
objects for multi-object grasping as shown on the right.

##  IV Push-MOG Algorithm

We present the Push-MOG algorithm in Alg. 1. After perceiving an initial
scene, it computes a cluster of objects. We plan and execute a series of
pushing actions to bring together the clustered objects so that they are
touching each other. Finally, we query the MOG-Net algorithm [6] to transport
that cluster through Multi-Object grasps. Below, we outline how the Push-MOG
algorithm plans and executes these steps.

1 do

2 $I$ $\leftarrow$ Image of the workspace

3 Parse $I$ into a 2D object map of all objects $O$

4 Partition $O$ into clusters $C$ (Alg. 2, see IV-A)

5 Get a cluster $c$ from $C$ at random

6 Plan the pushes, $P$ (Alg. 3, see IV-B)

7 for  _push $p\in P$_ do

8 Predict post-push location of pushed object

9 Run MOG-Net (IV-C), using predicted post-push locations, to identify grasp
$g$

10 Execute $g$ to remove $c$

11

12while  _objects remain on the workspace_ ;

Algorithm 1 Push-MOG

###  IV-A Clustering Details (Alg 2)

As described in Section III-B, the goal of this step is to cluster objects
into graspable subsets. In order to accomplish this we compute the centroids
of each object and use a bottom-up hierarchical clustering. We find the
smallest bounding box that encloses each object and cluster them based on
their proximity to each other. Once these clusters are formed, we check that
the sum of the widths of all the objects in the cluster does not exceed the
width of the gripper. If we encounter a non-valid cluster $c$ (i.e. such that
$d^{*}_{c}>d^{(\text{gr})}$), then we split $c$ into two clusters
$c_{1},c_{2}$ using a separating line (objects are divided based on their
centroids), minimizing the difference between the cluster grasp diameters
$|d^{*}_{c_{1}}-d^{*}_{c_{2}}|$.

Input : $O$: List of objects

Output : $C$: List of clusters

1

2Compute centroids $M_{o}$ for all $o\in O$

3 Hierarchical clustering on $\\{M_{o}:o\in O\\}$ to generate clusters $C$

4 Check the validity of each cluster $c\in C$ based on max gripper width

5 for  _non-valid cluster $c\in C$_ do

6 Minimize weight $W$ over $\theta$ using the following: for
_$\theta\in[-{\frac{\pi}{4}},{\frac{\pi}{4}}]$_ do

7 $v=\langle\cos\theta,\sin\theta\rangle$

8 Split the objects into two clusters $c_{1},c_{2}$ on an infinite line
defined by $v$, through the centroid of $c$

9 For this $\theta$, calculate weight difference $W=|\sum_{o\in
c_{1}}d^{*}_{o}-\sum_{o\in c_{2}}d^{*}_{o}|$

10 Split the cluster on this $\theta$

Algorithm 2 Clustering Algorithm

###  IV-B Push Planning (Alg 3)

Push planning considers how to push objects in a cluster closer together in
order to facilitate grasping. This can be broken into two steps: (i)
determining the desired locations of the cluster’s objects; (ii) computing the
parameters of the pushes to get them there. For object $o$, we denote the
desired location of its centroid as $M^{\prime}_{o}$, which is chosen both to
make pushing easier and to position the objects for grasping. For simplicity,
we only specify a desired location for the centroid (and not a desired
orientation). All pushes are executed in one motion in a straight line; the
direction and distance that $o$ is pushed is given by the vector
$M^{\prime}_{o}-M_{o}$ (to move its center of mass from $M_{o}$ to
$M^{\prime}_{o}$).

For executing a push with a parallel-jaw gripper, we propose the technique of
_fork pushing_ : we angle the gripper so the line between the jaws is
perpendicular to the desired push direction. This allows the gripper to push
both along an edge or around a vertex of an object (see Fig. 3), whereas a
flat-edged pusher could not push against a vertex without the object
undergoing a major rotation, deviating from the desired path.

Input : $C$: List of Clusters

Output : $v_{start},v_{end}$: Start and end push points for each object

1

2for  _valid cluster $c\in C$_ do

3 $M_{c}=\frac{\sum_{\text{object }o\in c}M_{o}}{|c|}$

4 $m=\operatorname*{\arg\\!\min}_{o\in c}\|M_{o}-M_{c}\|$, the central object
in the cluster

5 for  _object $o\in c\backslash m$_ do

6 $v=M_{o}-M_{m},v_{l}$ line with endpoints $M_{o},M_{m}$

7 Calculate center of furthest edge $e_{o}$ and corner $d_{o}$ of object $o$
from $m$, which intersects with $v_{l}$

8 Calculate closest edge $e_{m}$ on $o$ to $o_{m}$ on $v_{l}$

9 Scale $v\to v_{p}$ to capture the length of the push vector $\|v\|$

10 Ensure no collisions by shortening $v_{p}$, such that $v_{p}+o$ does not
collide with $o_{m}$

Algorithm 3 Push Planning Algorithm

###  IV-C MOG-Net Integration

Following the pushing step, we use MOG-Net [6] on the clusters to clear the
workspace. To improve efficiency, we use the simulated coordinates of the push
action to plan grasps instead of taking an image of the workspace again.

However, this process is not fully robust, because pushes may cause other
blocks in the way to deviate from their estimated location, leading to a
faulty grasp.

To remedy this, whenever a trip is performed (thus moving the gripper out of
the camera’s view of the workspace), a new image of the workspace is taken,
allowing these errors to be corrected; the algorithm also uses this image to
re-plan the clustering (IV-A) and pushing (IV-B) on the remaining blocks
(which may have been pushed aside or missed during an earlier grasp).

Figure 3: Examples of fork pushing with a parallel-jaw gripper, both against
an edge ((a) and (d)) and around a vertex ((b) and (c)) noticing that the
direction the object will move to is roughly perpendicular to the parallel-jaw
gripper.

##  V Experiments and Results

To evaluate the performance of the policies developed in the paper, we run
experiments in a real workspace.

###  V-A Experimental Setup

An example input is shown in Fig. 4. We use a Universal Robotics (UR) 5 Robot
with a Robotiq 2F-85 gripper mounted to its wrist. We perform experiments on
34 convex objects of various sizes, ranging from 3-sided to 8-sided. All
experiments assume a random placement of the objects in the workspace, and one
such configuration is shown in Fig. 4. To generate a random placement, we
uniformly sample the workspace and create circles that encompass the max
radius of any object we are using. Before creating each circle we ensure that
they do not overlap, and continue sampling the object set without replacement
until all objects are placed. Then a human sets up the configuration in real,
mirroring the randomly generated image. We generated 5 random scenes, on which
we will perform all experiments. We add friction on the graspable faces of the
objects by wrapping them in frictional tape.

To perceive the environment, we use an Intel RealSense L515 Camera, which
outputs RGB-D images, mounted directly above the workspace. To calibrate the
Camera-Robot transform, use an ArUco marker [41] which is manually calibrated
with an accuracy of $\sim 1cm$.

The pushing action consists of 5 repeated steps:

  1. 1.

Open the jaws to 30 percent width

  2. 2.

Move the gripper above the desired push location

  3. 3.

Move down to the object’s Z-height

  4. 4.

Move the gripper and push it to its planned location

  5. 5.

Move the gripper above its planned location

The Multi-Object Grasping action is executed with the MOG-Net algorithm [6].
Here we repeat the following:

  1. 1.

Plan a grasp for each cluster

  2. 2.

Move the gripper above the desired grasp location

  3. 3.

Open the jaws fully

  4. 4.

Move down to the work surface

  5. 5.

Close the jaws to complete the grasp

  6. 6.

Move the gripper outside the workspace and open the jaws fully to drop the
objects into the basket

###  V-B Baselines

We compare Push-MOG against two baselines: Frictional SOG, which uses single-
object grasps, and MOG-Net [6], which uses multi-object grasps but does not
use additional actions to help group the objects together. See Section 1 for
detailed information on baselines.

###  V-C Results

Results are given in Table I. We find that randomly-placed objects are not
generally well-positioned for multi-object grasps, as OpT is almost identical
between MOG-Net and Frictional SOG, thus requiring the use of additional
actions such as pushes to assist MOG. Indeed, the similarity in the
performance of Frictional SOG and MOG-Net suggests that there are few if any,
‘naturally occurring’ multi-object grasps in a typical scene of randomly-
scattered objects. Push-MOG successfully uses the pushing action to generate
graspable object clusters, increasing OpT by roughly $34\%$. This
comparatively modest increase in OpT (as compared to the experimental results
on the original MOG-Net [6]) is because objects that are stable under pushing
tend to have larger minimum grasp diameters and the gripper we used has a
relatively small max opening width, so it can grasp at most 2 or 3 objects at
a time.

TABLE I: Physical decluttering experimental results for random scenes, comparing baselines Frictional SOG, MOG-Net, and the method Push-MOG. Experiments were conducted with a Robotiq 2F-85 parallel-jaw gripper mounted on a UR5 robot arm, on 5 random scenes of 34 objects, with the goal placed directly adjacent (see Figs 2 and 4). Methods | Objects per Trip (OpT)
---|---
Frictional SOG | 0.993 $\pm$ 0.014
MOG-Net | 0.986 $\pm$ 0.038
Push-MOG | 1.339 $\pm$ 0.145

##  VI Limitations and Future Work

This work proposes Push-MOG, a novel algorithm that consolidates polygonal
objects into optimal clusters which increase the number of objects per grasp.
This work has the following limitations: 1) pushing can cause misalignments
where grasps fail 2) Push-MOG does not always avoid collisions 3) total time
is slow, leading to fewer picks per hour, even though Push-MOG gets more
objects per trip. In future work, we can incorporate _vertical stacking_ to
create larger multi-object clusters.

## Acknowledgements

This research was performed at the AUTOLAB at UC Berkeley in affiliation with
the Berkeley AI Research (BAIR) Lab, and the CITRIS “People and Robots” (CPAR)
Initiative. The authors were supported in part by donations from Toyota
Research Institute, Bosch, Google, Siemens, and Autodesk and by equipment
grants from PhotoNeo, NVidia, and Intuitive Surgical. Mehmet Dogar was
partially supported by an EPSRC Fellowship (EP/V052659). We thank our
colleagues who provided helpful feedback and suggestions, in particular
Mallika Parulekar and Zehan Ma.

Figure 4: This figure shows the clustering formed by Push-MOG of an initial
scene. The numbers on each cluster identify the order that the algorithm will
perform the pushing and grasping actions.

## References

  * [1] J. Ichnowski, M. Danielczuk, J. Xu, V. Satish, and K. Goldberg, “Gomp: Grasp-optimized motion planning for bin picking,” in _ICRA_ , 2020.
  * [2] J. Ichnowski, Y. Avigal, V. Satish, and K. Goldberg, “Deep learning can accelerate grasp-optimized motion planning,” _Science Robotics_ , vol. 5, no. 48, 2020.
  * [3] S. L. Herbert, M. Chen, S. Han, S. Bansal, J. F. Fisac, and C. J. Tomlin, “Fastrack: A modular framework for fast and guaranteed safe motion planning,” in _2017 IEEE 56th Annual Conference on Decision and Control (CDC)_ , 2017, pp. 1517–1522.
  * [4] J. Ichnowski, Y. Avigal, Y. Liu, and K. Goldberg, “Gomp-fit: Grasp-optimized motion planning for fast inertial transport,” in _2022 International Conference on Robotics and Automation (ICRA)_ , 2022, pp. 5255–5261.
  * [5] W. C. Agboh, J. Ichnowski, K. Goldberg, and M. R. Dogar, “Multi-object grasping in the plane,” 2022. [Online]. Available: https://arxiv.org/abs/2206.00229
  * [6] W. C. Agboh, S. Sharma, K. Srinivas, M. Parulekar, G. Datta, T. Qiu, J. Ichnowski, E. Solowjow, M. Dogar, and K. Goldberg, “Learning to efficiently plan robust frictional multi-object grasps,” 2022. [Online]. Available: https://arxiv.org/abs/2210.07420
  * [7] E. Arruda, M. J. Mathew, M. Kopicki, M. N. Mistry, M. Azad, and J. L. Wyatt, “Uncertainty averse pushing with model predictive path integral control,” _2017 IEEE-RAS 17th International Conference on Humanoid Robotics (Humanoids)_ , pp. 497–502, 2017.
  * [8] F. R. Hogan and A. Rodriguez, _Feedback Control of the Pusher-Slider System: A Story of Hybrid and Underactuated Contact Dynamics_. Cham: Springer International Publishing, 2020, pp. 800–815. [Online]. Available: https://doi.org/10.1007/978-3-030-43089-4_51
  * [9] K. Harada and M. Kaneko, “Enveloping grasp for multiple objects,” in _ICRA_ , 1998.
  * [10] K. Harada, M. Kaneko, and T. Tsujii, “Rolling-based manipulation for multiple objects,” _IEEE Transactions on Robotics and Automation_ , vol. 16, no. 5, pp. 457–468, 2000.
  * [11] T. Yamada, T. Ooba, T. Yamamoto, N. Mimura, and Y. Funahashi, “Grasp stability analysis of two objects in two dimensions,” in _ICRA_ , 2005.
  * [12] T. Yamada and H. Yamamoto, “Static grasp stability analysis of multiple spatial objects,” _Journal of Control Science and Engineering_ , vol. 3, 2015\.
  * [13] T. Chen, A. Shenoy, A. Kolinko, S. Shah, and Y. Sun, “Multi-object grasping - estimating the number of objects in a robotic grasp,” in _IROS_ , 2021.
  * [14] A. Shenoy, T. Chen, and Y. Sun, “Multi-object grasping - efficient robotic picking and transferring policy for batch picking,” _IEEE IROS_ , 2022.
  * [15] P. Jiang, J. Oaki, Y. Ishihara, and J. Ooga, “Multiple-object grasping using a multiple-suction-cup vacuum gripper in cluttered scenes,” 2023.
  * [16] V. P. Nguyen and W. T. Chow, “Wiring-claw gripper for soft-stable picking up multiple objects,” _IEEE Robotics and Automation Letters_ , vol. 8, no. 7, pp. 3972–3979, 2023.
  * [17] M. Dogar and S. S. Srinivasa, “A framework for push-grasping in clutter,” in _RSS_ , 2011.
  * [18] M. Danielczuk, J. Mahler, C. Correa, and K. Goldberg, “Linear Push Policies to Increase Grasp Access for Robot Bin Picking,” in _CASE_ , 2018.
  * [19] H. Huang, M. Dominguez-Kuhne, V. Satish, M. Danielczuk, K. Sanders, J. Ichnowski, A. Lee, A. Angelova, V. Vanhoucke, and K. Goldberg, “Mechanical search on shelves using lax-ray: Lateral access x-ray,” in _IEEE IROS_ , 2021.
  * [20] W. Agboh and M. Dogar, “Real-time online re-planning for grasping under clutter and uncertainty,” in _IEEE Humanoids_ , 2018.
  * [21] T. Sakamoto, W. Wan, T. Nishi, and K. Harada, “Efficient picking by considering simultaneous two-object grasping,” 2021.
  * [22] E. Huang, Z. Jia, and M. T. Mason, “Large-scale multi-object rearrangement,” in _ICRA_ , 2019.
  * [23] W. Bejjani, W. Agboh, M. Dogar, and M. Leonetti, “Occlusion-aware search for object retrieval in clutter,” in _IEEE IROS_ , 2021.
  * [24] M. Hasan, M. Warburton, W. Agboh, M. Dogar, M. Leonetti, H. Wang, F. Mushtaq, M. Mon-Williams, and A. Cohn, “Human-like planning for reaching in cluttered environments,” in _ICRA_ , 2020.
  * [25] M. Mason, _Mechanics of Robotic Manipulation_ , ser. Intelligent Robotics and Autonomous Agents series. MIT Press, 2001. [Online]. Available: https://books.google.com/books?id=Ngdeu3go014C
  * [26] W. C. Agboh, D. Ruprecht, and M. R. Dogar, “Combining coarse and fine physics for manipulation using parallel-in-time integration,” _ISRR_ , 2019.
  * [27] J. E. King, M. Cognetti, and S. S. Srinivasa, “Rearrangement planning using object-centric and robot-centric action spaces,” in _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , 2016, pp. 3940–3947.
  * [28] H. Song, J. A. Haustein, W. Yuan, K. Hang, M. Y. Wang, D. Kragic, and J. A. Stork, “Multi-object rearrangement with monte carlo tree search: A case study on planar nonprehensile sorting,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2020, pp. 9433–9440.
  * [29] Muhayyuddin, M. Moll, L. Kavraki, and J. Rosell, “Randomized physics-based motion planning for grasping in cluttered and uncertain environments,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 2, pp. 712–719, 2018\.
  * [30] W. C. Agboh and M. R. Dogar, “Pushing fast and slow: Task-adaptive planning for non-prehensile manipulation under uncertainty,” in _WAFR_ , 2018.
  * [31] W. Agboh and M. Dogar, “Robust physics-based manipulation by interleaving open and closed-loop execution,” _CoRR_ , vol. abs/2105.08325, 2021.
  * [32] W. Yuan, J. A. Stork, D. Kragic, M. Y. Wang, and K. Hang, “Rearrangement with nonprehensile manipulation using deep reinforcement learning,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 270–277.
  * [33] K. Y. Goldberg, “Orienting polygonal parts without sensors,” _Algorithmica_ , vol. 10, pp. 201–225, 1993.
  * [34] M. Erdmann and M. Mason, “An exploration of sensorless manipulation,” _IEEE Journal on Robotics and Automation_ , vol. 4, no. 4, pp. 369–379, 1988\.
  * [35] A. M. Johnson, J. King, and S. Srinivasa, “Convergent planning,” _IEEE Robotics and Automation Letters_ , vol. 1, no. 2, pp. 1044–1051, 2016.
  * [36] G. James, D. Witten, T. Hastie, and R. Tibshirani, _An Introduction to Statistical Learning: with Applications in R_. Springer, 2013. [Online]. Available: https://faculty.marshall.usc.edu/gareth-james/ISL/
  * [37] B. Mirkin and B. Mirkin, _Clustering for Data Mining: A Data Recovery Approach_ , 1st ed. Chapman and Hall/CRC, 2005.
  * [38] D. Müllner, “Modern hierarchical, agglomerative clustering algorithms,” 2011\. [Online]. Available: https://arxiv.org/abs/1109.2378
  * [39] Z. Bar-Joseph, D. K. Gifford, and T. S. Jaakkola, “Fast optimal leaf ordering for hierarchical clustering ,” pp. S22–S29, 06 2001. [Online]. Available: https://doi.org/10.1093/bioinformatics/17.suppl_1.S22
  * [40] T.-B.-H. Dao, K.-C. Duong, and C. Vrain, “Constrained clustering by constraint programming,” pp. 70–94, 2017, combining Constraint Solving with Mining and Learning. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0004370215000806
  * [41] S. Garrido-Jurado, R. Muñoz-Salinas, F. Madrid-Cuevas, and M. Marín-Jiménez, “Automatic generation and detection of highly reliable fiducial markers under occlusion,” pp. 2280–2292, 2014. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0031320314000235