A New Class of Linear Relations for Scalar Partitions
Boris Y. Rubinstein · 2025
Read A New Class of Linear Relations for Scalar Partitions by Boris Y. Rubinstein (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-00677.txt.
Introduction
Boris Y Rubinstein finds new linear relations among answers to a classic counting problem. A scalar partition problem asks how many ways nonnegative whole numbers can solve one linear equation with positive whole-number weights. Counts like these appear across combinatorics and number theory.
His 2025 manuscript gives an algorithm that derives equations linking a finite set of such counts. The method rests on a theorem by Cayley that reduces a double partition problem to a sum of single ones. A variable elimination step does the heavy lifting. The result is a fresh family of identities for partition counts. The paper is short and technical, written for specialists in enumerative combinatorics.
Catalog record
| CREATOR | Boris Y. Rubinstein |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-00677
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A New Class of Linear Relations for Scalar Partitions Boris Y. Rubinstein Abstract A scalar integer partition problem asks for a number of nonnegative integer solutions to a linear Diophantine equation with integer positive coefficients. The manuscript discusses an algorithm of derivation of linear relations involving the finite number of scalar partitions. The algorithm employs the Cayley theorem about the reduction of a double partition to a sum of scalar partitions based on the variable elimination procedure. Keywords : integer partition, double partition. 2010 Mathematics Subject Classification : 11P82. 1 Integer scalar partitions The problem of integer partition into a set of integers is equivalent to counting number of nonnegative integer solutions of the Diophantine equation s=\sum_{i=1}^{m}d_{i}x_{i}={\bf d}\cdot{\bf x}. (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 integer generators \{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) Sylvester proved [ 11 ] a statement about splitting the scalar partition into periodic and non-periodic parts and showed that it might be presented as a sum of ”waves” W(s,{\bf d})=\sum_{j=1}W_{j}(s,{\bf d})\;, (3) where the summation runs over all distinct factors of the elements d_{i} of the generator vector {\bf d} , and each wave W_{j}(s,{\bf d}) is a quasipolynomial in s closely related to prime roots x=\rho_{j}=\exp(2\pi in/j) of the equation x^{j}=1 for n relatively prime to j (including unity) and smaller than j . It is possible to express any Sylvester wave W_{j}(s,{\bf d}) and thus the scalar partition W(s,{\bf d}) through the Bernoulli polynomials of higher order [ 7 ] . The definition ( 2 ) of the generating function for W(s,{\bf d}) implies the recursion relation W(s,{\bf d})-W(s-d_{i},{\bf d})=W(s,\{d_{1},d_{2},\ldots,d_{i-1},d_{i+1},\ldots,d_{m}\}), (4) involving three scalar partitions – two with m generators and one with m-1 generators. As the selection of the generator d_{i} to be dropped from the vector {\bf d} is arbitrary, one can produce m relations similar to ( 4 ). There are just a few relations involving the partitions W(s,{\bf d}) are known in addition to ( 4 ). For example it was shown in [ 6 ] that the similar relation holds for each Sylvester wave W_{j}(s,{\bf d}) W_{j}(s,{\bf d})-W_{j}(s-d_{i},{\bf d})=W_{j}(s,\{d_{1},d_{2},\ldots,d_{i-1},d_{i+1},\ldots,d_{m}\}), (5) In his pioneering work [ 2 ] on the analytical expression for the scalar partitions Cayley noted that the function W(s,{\bf d}) satisfies the following parity property for the positive values of s W(s,{\bf d})=(-1)^{m+1}W(-s-\sigma({\bf d}),{\bf d}),\quad\quad\sigma({\bf d})=\sum_{i=1}^{m}d_{i}, (6) and pointed out that W(s,{\bf d}) vanishes at all integer negative points in the range -\sigma({\bf d})<s<0 . It is worth to note that Cayley considered the parity property as “…uninterpretable in the theory of partitions” [ 2 ] . The same results were obtained independently in [ 4 ] using only the resursion ( 4 ). This manuscript introduces the linear relations of different structure – (a) each term in the relation has the same number m of generators; (b) the number of terms in the relation is (m+1) – one more than the number of generators; and (c) the number of such relations is unlimited. The algorithm of derivation of these relations is based on the reduction of a specially constructed double partition into a sum of scalar partitions. The general idea of the reduction was proposed by Sylvester in [ 12 ] and the actual reduction algorithm is due to Cayley [ 3 ] who also discussed the limitations of the method. The manuscript shows how these conditions should be employed for the double partition construction to obtain the required relations. 2 Sylvester-Cayley reduction algorithm for double partitions Double partitions used for the derivation of the scalar partition relations represent the simplest particular case of vector partitions . The vector partition function W({\bf s},{\bf D}) counts the number of integer nonnegative solutions {\bf x}\geq 0 to a linear system {\bf s}={\bf D}\cdot{\bf x} , where {\bf D}=\{{\bf c}_{1},{\bf c}_{2},\ldots,{\bf c}_{m}\} is a nonnegative integer l\times m generator matrix ( l<m ) made of columns {\bf c}_{i}=\{c_{i1},c_{i2},\ldots,c_{il}\}^{T},\ (1\leq i\leq m) with \{\cdot\}^{T} denoting transposition of a vector. Sylvester suggested an iterative procedure of reduction of a vector partition into a sum of scalar partitions [ 12 ] ; the procedure is based on the variable elimination from the system of linear equations {\bf s}={\bf D}\cdot{\bf x} . Based on this approach Cayley developed an algorithm of double partition reduction and established a set of conditions of the method applicability [ 3 ] . Cayley showed that each column {\bf c}_{i} of the two-row matrix {\bf D} gives rise to a scalar partition and elements of this column must be relatively prime (we call it P-column). Another limitation of the Sylvester-Cayley method is that the columns {\bf c}_{i} should represent noncollinear vectors. The practical application of the Cayley algorithm to the computation of the Gaussian polynomial coefficients is considered in [ 8 ] . The details of the Cayley reduction method for double partitions and its modification that works without any limitations for arbitrary double partition is described in [ 9 ] . It should be noted that similar restictions to those discussed by Cayley in [ 3 ] were earlier mentioned in [ 12 ] for vector partitions with arbitrary dimension l of vector {\bf s} . Later Sylvester in his lectures [ 13 ] offered an alternative approach to lifting these limitations and it appears to be quite useful for our derivation procedure. Consider the Sylvester idea in more details. The variable elimination algorithm for vector partition reduction fails when the generator matrix {\bf D} has either collinear columns or nonprime columns (NP-columns) or both, where the elements of the NP-column {\bf c} have the greatest common divisor (GCD) of its elements \mbox{gcd}({\bf c})>1 . Sylvester suggested to add to the system {\bf s}={\bf D}\cdot{\bf x} a single auxiliary equation and a new unknown x_{m+1} in order to convert the original system into a larger one \hat{\bf s}=\hat{\bf D}\cdot\hat{\bf x} , where \hat{\bf x}=\{x_{1},x_{2},\ldots,x_{m},x_{m+1}\} . The matrix \hat{\bf D}=\{\hat{\bf c}_{1},\hat{\bf c}_{2},\ldots,\hat{\bf c}_{m},\hat{\bf c}_{m+1}\} consists of (m+1) columns \hat{\bf c}_{i}=\{c_{i0},c_{i1},c_{i2},\ldots,c_{il}\}^{T} . The elements c_{i0} and the value of s_{0} in the added equation must be chosen to satisfy two conditions – (a) each nonnegative integer solution of the original system {\bf s}={\bf D}\cdot{\bf x} should correspond to a single solution of the system \hat{\bf s}=\hat{\bf D}\cdot\hat{\bf x} , and (b) the matrix \hat{\bf D} should be void of collinear and NP-columns. The first condition leads to W(\hat{\bf s},\hat{\bf D})=W({\bf s},{\bf D}), (7) while the second one guarantees that the vector partition W(\hat{\bf s},\hat{\bf D}) admits the variable elimination procedure of reduction (at least the first step of it). 3 Linear relations for scalar partitions Consider an application of the Sylvester method to the scalar partition W(s,{\bf d}) when we have the single original equation s={\bf d}\cdot{\bf x} and add an equation \sigma=x_{m+1}-\bm{\delta}\cdot{\bf x} producing the system of two equations \sigma=x_{m+1}-\sum_{i=1}^{m}\delta_{i}x_{i},\quad s=\sum_{i=1}^{m}d_{i}x_{i}, (8) with positive \delta_{i} and nonnegative \sigma (see the fifth lecture in [ 13 ] ). This system corresponds to the double partition W(\hat{\bf s},\hat{\bf D}) with \hat{\bf D}=\left(\begin{array}[]{ccccc}-\delta_{1}&-\delta_{2}&\ldots&-\delta_{m}&1\\ d_{1}&d_{2}&\ldots&d_{m}&0\end{array}\right),\quad\hat{\bf s}=\left(\begin{array}[]{c}\sigma\\ s\end{array}\right). (9) Each integer nonnegative solution {\bf x}=\bm{\xi}=\{\xi_{1},\xi_{2},\ldots,\xi_{m}\} of the