Ramanujan J https://doi.org/10.1007/s11139-017-9985-3
On the restricted partition function Mircea Cimpoea¸s1 · Florin Nicolae1
Received: 7 April 2017 / Accepted: 29 December 2017 © Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract For a vector a = (a1 , . . . , ar ) of positive integers, we prove formulas for the restricted partition function pa (n) := the number of integer solutions (x1 , . . . , xr ) to rj=1 a j x j = n with x1 ≥ 0, . . . , xr ≥ 0 and its polynomial part. Keywords Restricted partition function · Barnes zeta function · Quasi-polynomial Mathematics Subject Classification Primary 11P81 · Secondary 11P82 · 11P83
1 Introduction Let a := (a1 , a2 , . . . , ar ) be a sequence of positive integers, r ≥ 1. The restricted partition function associated to a is pa : N → N, pa (n) := the number of integer solutions (x1 , . . . , xr ) of ri=1 ai xi = n with xi ≥ 0. Sylvester [15,16] decomposed the restricted partition function in a sum of “waves,” pa (n) =
W j (n, a),
j≥1
The first author was supported by a Grant of the Romanian National Authority for Scientific Research, CNCS - UEFISCDI, Project Number PN-II-ID-PCE-2011-1023.
B
Mircea Cimpoea¸s
[email protected] Florin Nicolae
[email protected]
1
Simion Stoilow Institute of Mathematics, Research Unit 5, P.O. Box 1-764, 014700 Bucharest, Romania
123
M. Cimpoea¸s, F. Nicolae
where the sum is taken over all distinct divisors j of the components of a and showed that for each such j, W j (n, a) is the coefficient of t −1 in ρ −νn ent j
0≤ν< j, gcd(ν, j)=1
r −ar t 1 −a1 t (1 − ρ νa ) · · · (1 − ρ νa ) j e j e
,
where ρ j = e2πi/j and gcd(0, 0) = 1 by convention. Glaisher [6] made computations of the waves in particular cases. Sills and Zeilberger [12] described an algorithm that provides explicit expressions for the number of partitions of n into at most m parts. Rubinstein and Fel [10] proved formulas for the Sylvester waves using Bernoulli and Euler polynomials of higher order. Rubinstein [9] showed that all Sylvester waves can be expressed in terms of Bernoulli polynomials only. Bayad and Beck [2, Theorem 3.1] proved an explicit expression of the partition function pa (n) in terms of Bernoulli– Barnes polynomials and the Fourier Dedekind sums, in the case that a1 , . . . , ar are pairwise coprime. Dilcher and Vignat [5, Theorem 1.1] proved an explicit formula for W1 (n, a), which is the polynomial part of pa (n). Let D be a common multiple of a1 , a2 , . . . , ar . Bell [4] has proved that pa (n) is a quasi-polynomial of degree r − 1, with the period D, i.e., pa (n) = da,r −1 (n)nr −1 + · · · + da,1 (n)n + da,0 (n), where da,m (n + D) = da,m (n) for 0 ≤ m ≤ r − 1 and n ≥ 0, and da,r −1 (n) is not identically zero. Our main result is the following formula for pa (n) which is stated in Theorem 2.8: n−1 1 pa (n) = (r − 1)!
r −1 r
m=0 0≤ j1 ≤
D D k=m a1 −1,...,0≤ jr ≤ ar −1 a1 j1 +···+ar jr ≡n( mod D)
k
(−1)
k−m
k m
× D −k (a1 j1 + · · · + ar jr )k−m n m , where rk are the unsigned Stirling numbers of the first kind. The novelty of this formula is that we reduce the computation of the restricted partition function pa (n) to solving the linear congruence a1 j1 + · · · + ar jr ≡ n(mod D) in the restricted range 0 ≤ j1 ≤ aD1 − 1, . . . , 0 ≤ jr ≤ aDr − 1. In Corollary 2.10, we prove that 1 pa (n) = (r − 1)!
r
−1
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 =1 1 a1 j1 +···+ar jr ≡n( mod D)
n − a1 j1 − · · · − ar jr + . D
In Remark 2.11, we present an algorithm to compute pa (n).
123
On the restricted partition function
In Corollary 2.12, we prove that pa (n) = 0 if and only if n < a1 j1 + · · · + ar jr for all ( j1 , . . . , jr ) such that 0 ≤ j1 ≤ aD1 −1, . . . , 0 ≤ jr ≤ aDr −1 and a1 j1 +· · ·+ar jr ≡ n(mod D). Our method is based on properties of the Barnes zeta function associated to a and w>0
ζa (s, w) :=
u 1 ,...,u r ≥0
1 , Re(s) > r, (a1 u 1 + · · · + ar u r + w)s
which is related to pa (n) by the formula ζa (s, w) =
n≥0
pa (n) . (n + w)s
As an illustration of our method, we provide new proofs for several results which are known in the literature. For r = 2, we prove in Corollary 2.13 the classical formula of Popoviciu [8] for pa (n) and in Corollary 2.14 the well-known formula F(a1 , a2 ) = a1 a2 − a1 − a2 for the Frobenius number of the coprime numbers a1 and a2 . For the polynomial part Pa (n) of pa (n), we prove in Corollary 3.6 that Pa (n) =
1 D(r − 1)!
r
−1
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 =1
n − a1 j1 − · · · − ar jr + . D
1
This extends Theorem 1.1 of Dilcher and Vignat [5]: the authors prove the formula for D = a1 · · · ar and we prove it for any common multiple of a1 , . . . , ar . pa (n) The Dirichlet series associated to pa (n) is ζa (s) := ∞ n=1 n s . This converges for Re(s) > r and defines a meromorphic function in the whole complex plane with poles at most in the set {1, . . . , r } which are simple with residues Rm := Ress=m ζa (s). In Theorem 3.10, we prove that Rm =
(−1)r −m Br −m (a1 , . . . , ar ), 1 ≤ m ≤ r, (m − 1)!
where Br −m (a1 , . . . , ar ) are the Bernoulli–Barnes numbers. This result can be obtained also as a direct consequence of formula (3.9) in Ruijsenaars [11]. In Corollary 3.11, we prove the result of Beck, Gessler and Komatsu [3] that the polynomial part of pa (n) is Pa (n) =
r −1 (−1)u 1 a1 · · · ar (r − 1 − u)! u=0
i 1 +···+ir =u
Bi1 · · · Bir i1 a · · · arir nr −1−u . i 1 ! · · · ir ! 1
These authors do not use the residues of the Barnes zeta function, as we are doing in the proof of Corollary 3.11.
123
M. Cimpoea¸s, F. Nicolae
2 A formula for the restricted partition function Let a := (a1 , a2 , . . . , ar ) be a sequence of positive integers, r ≥ 1. We use the following notations: • D is a common multiple of the numbers a1 , a2 , . . . , ar . • For 0 ≤ j1 ≤ aD1 − 1, 0 ≤ j2 ≤ aD2 − 1, . . . , 0 ≤ jr ≤ aDr − 1 let, by Euclidean division, q( j1 , . . . , jr ) and r( j1 , . . . , jr ) be the unique integers such that a1 j1 + · · · + ar jr = q( j1 , . . . , jr )D + r( j1 , . . . , jr ), 0 ≤ r( j1 , . . . , jr ) ≤ D − 1. (2.1) We have that a1 j1 + · · · + ar jr ≤ r D − a1 − · · · − ar ≤ r D − r < r D, hence 0 ≤ q( j1 , . . . , jr ) ≤ r − 1. • We denote the rising factorial by x (r ) := (x + 1)(x + 2) · · · (x + r − 1), x (0) = 1. It holds that r n +r −1 1 1 r r n (r ) = nr −1 + · · · + = n+ , (r − 1)! (r − 1)! r − 1 r −1 1 0 (2.2) where rk ’s are the unsigned Stirling numbers of the first kind. • Let w > 0 be a real number. The Barnes zeta function associated to a and w is ζa (s, w) :=
u 1 ,...,u r ≥0
1 , Re(s) > r. (a1 u 1 + · · · + ar u r + w)s
(2.3)
For basic properties of the Barnes zeta function see [1,11] and [13]. We have ζa (s, w) =
∞ n=0
pa (n) . (n + w)s
(2.4)
• Let ζa (s) :=
pa (n) . ns n≥1
Since pa (n) = O(nr −1 ), the Dirichlet series ζa (s) is convergent for Re(s) > r . We have (2.5) ζa (s) = lim (ζa (s, w) − w −s ). w0
123
On the restricted partition function
If r = 1 then ζa (s, w) =
n≥0
1 1 w 1 , ζa (s) = s ζ (s), = ζ s, s s (a1 n + w) a1 a1 a1
where ζ (s, w) :=
∞ n=0
1 , (n + w)s
Re(s) > 1,
is the Hurwitz zeta function and ζ (s) :=
∞ 1 , ns
Re(s) > 1,
n=1
is the Riemann zeta function. Lemma 2.1 We have D a1 −1 ar −1 r −1 k r k 1 ζa (s, w) = s ··· (−1) j k j D (r − 1)! j1 =0 jr =0 k=0 j=0 j a1 j1 + · · · + ar jr + w × D a1 j1 + · · · + ar jr + w . ×ζ s − k + j, D D
Proof Let u 1 ≥ 0, u 2 ≥ 0, . . . , u r ≥ 0 be integers. We write u 1 = u 2 = aD2 p2 + j2 , …, u r = aDr pr + jr , with 0 ≤ j1 ≤ aD1 − 1, 0 ≤ j2 ≤ 0 ≤ jr ≤ aDr − 1. We have that
D a1 D a2
p1 + j1 , − 1, . . .,
a1 u 1 + · · · + ar u r = D( p1 + · · · + pr ) + a1 j1 + · · · + ar jr . Let n := p1 +· · ·+ pr . If a1 u 1 +· · ·+ar u r = a1 u 1 +· · ·+ar u r with u 1 = aD1 p1 + j1 , u 2 = aD2 p2 + j2 , …, u r = aDr pr + jr then p1 +· · ·+ pr = n. Therefore, for fixed integers 0 ≤ j1 ≤ D −1, 0 ≤ j2 ≤ aD2 −1, . . . 0 ≤ jr ≤ aDr −1 we have in the sum (2.3) exactly n+r −1 a1 1 terms (a1 u 1 +···+a s with a1 u 1 + · · · + ar u r = Dn + a1 j1 + · · · + ar jr . r −1 r u r +w) Hence D D a1 −1 a2 −1
ζa (s, w) =
j1 =0 j2 =0
D ar
···
−1
∞ jr =0 n=0
n+r −1 r −1
(Dn + a1 j1 + · · · + ar jr + w)s
123
M. Cimpoea¸s, F. Nicolae D
−1
D
−1
D
−1
a1 a2 ∞ ar 1 = s ···
D j1 =0 j2 =0 jr =0 n=0 n +
n+r −1
r −1 s . a1 j1 +···+ar jr +w D
(2.6)
Using the identity k j k n = (n + α − α) = (n + α) j , (−1) j k
k
j=0
for α =
a1 j1 +···+ar jr +w D
and the identity (2.2) the conclusion follows from (2.6).
Note that Bayad and Beck give a decomposition of the Barnes zeta function as a linear combination of Hurwitz zeta functions in the case a1 , . . . , ar pairwise coprime in [2, Theorem 1.3]. Lemma 2.2 We have D a1 −1 ar −1 r −1 k r 1 j k ··· (−1) ζa (s, w) = s k j D (r − 1)! j1 =0 jr =0 k=0 j=0 j a1 j1 + · · · + ar jr + w × D r( j1 , . . . , jr ) + w . ×ζ s − k + j, D D
Proof From (2.1) it follows that a1 j1 + · · · + ar jr + w ζ s − k + j, D r( j1 , . . . , jr ) + w = ζ s − k + j, D q( j1 ,..., j )−1 r r( j1 , . . . , jr ) + w −(s−k+ j) + − D =0 r( j1 , . . . , jr ) + w = ζ s − k + j, D −s+k− j q( j 1 ,..., jr ) a1 j1 + · · · + ar jr + w − . − D =1
123
On the restricted partition function
By Lemma 2.1, it is enough to show that D D a1 −1 a2 −1
S :=
j1 =0 j2 =0
×
k r −1 r k a1 j1 + · · · + ar jr + w j ··· (−1) j k j D D ar
−1
jr =0 k=0
q( j 1 ,..., jr ) =1
j=0
−s+k− j a1 j1 + · · · + ar jr + w − = 0. D
Indeed, since k
(−1) j
j=0
−s+k− j k a1 j1 + · · · + ar jr + w j a1 j1 + · · · + ar jr + w − j D D −s a1 j1 + · · · + ar jr + w − D k− j k k a1 j1 + · · · + ar jr + w j a1 j1 + · · · + ar jr + w − × − j D D
=
=
j=0
−s a1 j1 + · · · + ar jr + w − (−)k , D
we get D D a1 −1 a2 −1
S=
j1 =0 j2 =0
−1 r −1 q( j1 ,..., jr ) −s r a1 j1 + · · · + ar jr + w − ··· (−)k k D D ar
jr =0 k=0
D D a1 −1 a2 −1
=
D ar
···
j1 =0 j2 =0
=1
−1 q( j1 ,..., jr )
jr =0
=1
−s r −1 a1 j1 + · · · + ar jr + w r (−)k . − · k D k=0
−s q( j ,..., j ) r jr +w − = 0, and hence S = 0. If q( j1 , . . . , jr ) = 0 then =11 r a1 j1 +···+a D then, since q( j , . . . , j ) ≤ r − 1, we have 1 ≤ ≤ If q( j1 , . . . , jr ) > 0 1 r −1 r k = (−)(r ) = 0, and hence S = 0. (−)
q( j1 , . . . , jr ) ≤ r − 1 so rk=0 k Lemma 2.3 We have ζa (s) =
1 D s (r − 1)! × +
k r
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 j=0 1 a1 j1 +···+ar jr ≡0( mod D)
a1 j1 + · · · + ar jr D
1 D s (r − 1)!
j
k
(−1) j
k j
r( j1 , . . . , jr ) ζ s − k + j, D r −1 k r k (−1) j k j
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 k=0 j=0 1 a1 j1 +···+ar jr ≡0( mod D)
123
M. Cimpoea¸s, F. Nicolae ×
a1 j1 + · · · + ar jr D
j
ζ (s − k + j).
Proof Since ζa (s) = limw0 (ζa (s, w) − w −s ), by Lemma 2.2 it is enough to prove that
1 D s (r − 1)!
k r −1 r k (−1) j k j
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 k=0 j=0 1 a1 j1 +···+ar jr ≡0( mod D)
×
a1 j1 + · · · + ar jr + w D −s =w ,
j
w −s+k− j D
which is equivalent to k r −1 r
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 k=0 1 a1 j1 +···+ar jr ≡0( mod D)
k
j=0
k a1 j1 + · · · + ar jr + w j w k− j (−1) j D D j
= (r − 1)!.
(2.7)
Let 0 ≤ j1 ≤ aD1 − 1, . . . , 0 ≤ jr ≤ 0(mod D). We have
D ar
− 1 be such that a1 j1 + · · · + ar jr ≡
r −1 k r a1 j1 + · · · + ar jr + w j w k− j j k (−1) k j D D k=0
j=0
=
r −1 r a1 j1 + · · · + ar jr k a1 j1 + · · · + ar jr (r ) − = − . k D D k=0
r jr ∈ {0, 1, . . . , (r − 1)} and a1 j1 + · · · + ar jr = 0 if and only if Note that a1 j1 +···+a D j1 = · · · = jr = 0. Since 0(r ) = (r − 1)! and (−c)(r ) = 0 for 1 ≤ c ≤ r − 1, the formula (2.7) is true.
Lemma 2.4 We have
ζa (s) =
r −1 D
1 v , γmv · ζ s − m, s (r − 1)!D D m=0 v=1
123
On the restricted partition function
where r −1 r
γmv =
k
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 k=m 1 a1 j1 +···+ar jr ≡0( mod D)
(−1)k−m
k a1 j1 + · · · + ar jr k−m . D m
Proof For 0 ≤ v ≤ D − 1, r( j1 , . . . , jr ) = v if and only if a1 j1 + · · · + ar j1 ≡ v(mod D). The conclusion follows immediately from Lemma 2.3.
We recall the classical result of Bell [4]: Proposition 2.5 pa (n) is a quasi-polynomial of degree r − 1, with the period D, i.e., pa (n) = da,r −1 (n)nr −1 + · · · + da,1 (n)n + da,0 (n), where da,m (n + D) = da,m (n) for 0 ≤ m ≤ r − 1 and n ≥ 0, and da,r −1 (n) is not identically zero. Lemma 2.6 For Re(s) > r , we have ζa (s) =
r −1 D
1 v m . d (v) · D · ζ s − m, a,m Ds D m=0 v=1
Proof From Proposition 2.5, it follows that ∞ r −1 da,m (n)
ζa (s) =
m=0 n=1
= =
1 Ds
n s−m
r −1 D m=0 v=1
=
D r −1
da,m (v)
m=0 v=1
da,m (v) · D m
∞ j=0
∞ j=0
1 (D j + v)s−m
1 j+
v s−m D
r −1 D
1 v m . d (v) · D · ζ s − m, a,m Ds D m=0 v=1
Lemma 2.7 Let k ≥ 1 and r ≥ 0 be two integers. The set of functions {ζ (s − j, k ) : 0 ≤ j ≤ r, 1 ≤ ≤ k} is linearly independent over C. Proof Suppose that r k =1 j=0
= 0, c j ∈ C, 0 ≤ j ≤ r, 1 ≤ ≤ k. c j · ζ s − j, k
123
M. Cimpoea¸s, F. Nicolae
We want to show that the c j ’s are 0. We have ∞
∞
∞
n=0
n=0
n=0
k s− j (nk + ) j 1 k s− j ζ (s − j, ) = = = . k (nk + )s− j (nk + )s (n + k )s− j It follows that 0=
k r =1 j=0
= ks ·
k r ∞ k s− j (nk + ) j = c j · ζ s − j, c j · k (nk + )s =1 j=0 n=0
r k ∞
c j ·
=1 j=0 n=0
k − j (nk + ) j , (nk + )s
so k r ∞
c j ·
=1 j=0 n=0
It follows that
r
j=0 k
−jc
j (nk
k − j (nk + ) j = 0. (nk + )s
+ ) j = 0 for every n ≥ 0, and hence c j = 0.
Theorem 2.8 (1) For 0 ≤ m ≤ r − 1 and n ≥ 0, we have da,m (n) =
1 (r − 1)!
r −1 r
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 k=m 1 a1 j1 +···+ar jr ≡n( mod D)
k
(−1)k−m
k m
×D −k (a1 j1 + · · · + ar jr )k−m . (2) We have pa (n) =
n−1 1 (r − 1)!
m=0 0≤ j1 ≤
r −1 r k (−1)k−m k m
D D k=m a1 −1,...,0≤ jr ≤ ar −1 a1 j1 +···+ar jr ≡n( mod D)
×D −k (a1 j1 + · · · + ar jr )k−m n m . Proof (1) From Lemmas 2.4, 2.6, and 2.7, it follows that da,m (v)D m =
1 γmv (r − 1)!
for 0 ≤ m ≤ r − 1 and 1 ≤ v ≤ D. The formulas (1) follow now from Lemma 2.6 and the fact that the coefficients da,m (n) are periodic with period D.
123
On the restricted partition function
(2) This follows from Proposition 2.5 and the above formulas (1).
For n ≥ 1, we have p(n) = p(1,2,...,n) (n), where p(n) is the number of partitions of n. Applying Theorem 2.8 for r = n and a = (1, 2, . . . , n), we obtain the following formula for p(n): Corollary 2.9 p(n) =
n−1 1 (n − 1)!
n−1 n k (−1)k−m k m
m=0 0≤ j1 ≤ Dn −1,...,0≤ jn ≤ Dn −1 k=m 1
n
j1 +2 j2 +···+n jn ≡n( mod Dn )
×Dn−k ( j1 + 2 j2 + · · · + n jn )k−m n m , where Dn is a common multiple of 1, 2, . . . , n. Corollary 2.10 We have 1 pa (n) = (r − 1)!
r
−1
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 =1 1 a1 j1 +···+ar jr ≡n( mod D)
n − a1 j1 − · · · − ar jr + . D
Proof From Theorem 2.8, it follows that pa (n) =
r −1 m=0
1 (r − 1)!
× =
r −1
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 k=m 1 a1 j1 +···+ar jr ≡n( mod D)
r k (−1)k−m k m
a1 j1 + · · · + ar jr k−m n m D D
1 (r − 1)!
r −1 r −1
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 m=0 k=m 1 a1 j1 +···+ar jr ≡n( mod D)
r k
k m
−
a1 j1 + · · · + ar jr k−m n m . D D
(2.8) The m-th derivative of x (r ) is r −1 k r k−m d m x (r ) x = m! · . dxm m k k=m
123
M. Cimpoea¸s, F. Nicolae
From (2.8), it follows that 1 pa (n) = (r − 1)!
=
r −1 1 d m x (r ) m! d x m
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 m=0 1 a1 j1 +···+ar jr ≡n( mod D)
a1 j1 + · · · + ar jr n m × − D D n − a1 j1 − · · · − ar jr (r ) 1 (r − 1)!
D
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 1 a1 j1 +···+ar jr ≡n( mod D)
,
using Taylor’s formula. Remark 2.11 Let g := gcd(a1 , . . . , ar ). For n ≥ 0 let D D Bn := ( j1 , . . . , jr ) : 0 ≤ j1 ≤ − 1, . . . , 0 ≤ jr ≤ − 1, a1 ar a1 j1 + · · · + ar jr ≡ n (mod D)} . It holds that
g· 0,
# Bn =
Dr −1 a1 ···ar
, g|n . gn
Indeed, the map ϕ:
Z D a1 Z
×
Z D a2 Z
× ··· ×
Z D ar Z
−→
Z , DZ
ϕ(x¯1 , . . . , x¯r ) := a1 x1 + · · · + ar xr Z is a group morphism with Im(ϕ) = g, ¯ the subgroup of DZ generated by g, ¯ and, for n ≥ 0, the fiber ϕ −1 (n) ¯ is in bijection with Bn . By Corollary 2.10, in order to determine the restriction partition function pa , we have to compute the fibers of ϕ. We have the following algorithm to compute pa (n).
Input n ≥ 0. Output pa (n). If g n, then pa (n) = 0. STOP. Let 0 ≤ m ≤ D − 1, m ≡ n(mod D). Let Bm := ∅. For each 0 ≤ j1 ≤ aD1 −1, . . . , 0 ≤ jr ≤ aDr −1, if a1 j1 +· · ·+ar jr ≡ m ( mod D) then Bm = Bm ∪ {( j1 , . . . , jr )}. r −1 n−a1 j1 −···−ar jr 1 + ). • pa (n) = (r −1)! ( j1 ,..., jr )∈Bm =1 ( D
• • • •
Corollary 2.10 implies the following characterization of the zeros of pa (n).
123
On the restricted partition function
Corollary 2.12 For n ≥ 0, we have pa (n) = 0 if and only if n < a1 j1 + · · · + ar jr for all 0 ≤ j1 ≤ aD1 − 1, . . . , 0 ≤ jr ≤ aDr − 1 with a1 j1 + · · · + ar jr ≡ n(mod D). Proof Note that k (r ) = 0 if and only if k ∈ {−r + 1, . . . , −1}. On the other hand, for all 0 ≤ j1 ≤ aD1 − 1, . . . , 0 ≤ jr ≤ aDr − 1 with a1 j1 + · · · + ar jr ≡ n(mod D), we have n − a1 j1 + · · · + ar jr n − a1 j1 − · · · − ar jr n − r D + a1 + · · · + ar = ≥ > −r, D D D and hence the integer
n−a1 j1 +···+ar jr D
is ≥ r − 1.
For r = 2 and a = (a1 , a2 ) with gcd(a1 , a2 ) = 1, Corollary 2.10 implies the classical result of Popoviciu: Corollary 2.13 (Popoviciu [8, Lemma 11]) We have pa (n) =
n + a1 a1 (n) + a2 a2 (n) − 1, n ≥ 0, a1 a2
where a1 (n) and a2 (n) are the unique integers such that a1 (n)a1 ≡ −n mod a2 , 1 ≤ a1 (n) ≤ a2 and a2 (n)a2 ≡ −n mod a1 , 1 ≤ a2 (n) ≤ a1 . Proof Since the map ϕ : Z/a2 Z × Z/a1 Z → Z/a1 a2 Z defined by ϕ( jˆ1 , jˆ2 ) := a1 j1 + a2 j2 is a group isomorphism, it follows that the congruence a1 j1 + a2 j2 ≡ n(mod a1 a2 ) has an unique solution ( j1 , j2 ) with 0 ≤ j1 ≤ a2 − 1 and 0 ≤ j2 ≤ 2 j2 + 1. The conclusion a1 − 1. From Corollary 2.10, it follows that pa (n) = n−a1a1j1a−a 2 follows from the fact that a1 (n) = a1 − j2 and a2 (n) = a2 − j1 .
Given a sequence of positive integers a = (a1 , . . . , ar ) with gcd(a1 , . . . , ar ) = 1, the Frobenius number of a, denoted by F(a) = F(a1 , . . . , ar ), is the largest integer n with the property that pa (n) = 0. Corollary 2.14 Let a = (a1 , a2 ) with gcd(a1 , a2 ) = 1. Then F(a1 , a2 ) = a1 a2 − a1 − a2 . Proof Let n = a1 a2 − a1 − a2 . Let ( j1 , j2 ) be the solution of the congruence a1 j1 + a2 j2 ≡ n(mod a1 a2 ) with 0 ≤ j1 ≤ a1 − 1 and 0 ≤ j2 ≤ a2 − 1. Assume that a1 j1 + a2 j2 = a1 a2 − a1 − a2 . It follows that a1 ( j1 + 1) + a2 ( j2 + 1) = a1 a2 , which + j2a+1 = 1, and hence we get a contradiction with the fact that is equivalent to j1a+1 2 1 gcd(a1 , a2 ) = 1. Therefore, by Corollary 2.12, pa (n) = 0. Now, let n > a1 a2 − a1 − a2 . Since a1 j1 + a2 j2 ≤ 2a1 a2 − a1 − a2 , it follows that 2 j2 > −1 and thus, as in the proof of Corollary 2.13, pa (n) = k +1 > 0. k := n−a1a1j1a−a 2
3 The polynomial part of the restricted partition function We recall the following basic facts on quasipolynomials [14, Proposition 4.4.1].
123
M. Cimpoea¸s, F. Nicolae
Proposition 3.1 The following conditions on a function p : N → C and integer D > 0 are equivalent. (i) p(n) is a quasi-polynomial of period D. ∞ L(z) n (ii) n=0 p(n)z = M(z) , where L(z), M(z) ∈ C[z], every zero λ of M(z) satisfies L(z) λ D = 1 (provided M(z) has been reduced to lowest terms), and deg L(z) < deg M(z). (iii) For all n ≥ 0, p(n) = λ D =1 Pλ (n)λ−n , where each Pλ (n) is a polynomial function. Moreover, deg Pλ (n) ≤ m(λ) − 1, where m(λ) is the multiplicity of λ as a root of M(z).
Let p : N → C be a quasi-polynomial of degree r − 1 ≥ 0, p(n) := dr −1 (n)nr −1 + · · · + d1 (n)n + d0 (n), where dm (n)’s are periodic functions with integral period D > 0 and dr −1 (n) is not identically zero. We define the polynomial part of p(n) to be the polynomial function P(n) := P1 (n), with the notation from Proposition 3.1(iii). Let γ ∈ C with γ D = 1. It holds that pγ (n) := γ n p(n) =
Pλ (n)(γ · λ−1 )n ,
λ D =1
and hence Pγ (n) is the polynomial part of pγ (n). Let w > 0 be a real number. We consider the function ζ p (s, w) :=
∞ n=0
p(n) , (n + w)s
which is defined for Re(s) > r . Similarly, for γ D = 1 and Re(s) > r , we consider ζ pγ (s, w) :=
∞ n=0
pγ (n) . (n + w)s
Proposition 3.2 We have r −1 D−1 m m 1 v+w m−k k (−w) , dm (v) D ζ s − k, ζ p (s, w) = s k D D m=0 v=0
k=0
and therefore ζ p (s, w) is a meromorphic function in the whole complex plane with poles at most in the set {1, . . . , r } which are all simple with residues R(w, k + 1) := Ress=k+1 ζ p (s, w) r −1 D−1 1 m (−w)m−k dm (v), 0 ≤ k ≤ r − 1. = k D m=k
123
v=0
On the restricted partition function
Proof We have that ζ p (s, w) = = =
∞
∞ r −1
p(n) nm = dm (n) s (n + w) (n + w)s
n=0 ∞ r −1
n=0 m=0 ∞ r −1
n=0 m=0
dm (n)
(n + w − w)m (n + w)s
dm (n)
m m 1 (−w)k k (n + w)s−m+k
n=0 m=0
=
r −1 D−1
k=0
dm (v)
m=0 v=0
m ∞ m 1 (−w)k · k ( j D + v + w)s−m+k k=0
j=0
r −1 D−1 m m 1 v+w k m−k (−w) D = s dm (v) ζ s − m + k, k D D m=0 v=0
k=0
m=0 v=0
k=0
r −1 D−1 m m v+w 1 m−k k dm (v) D ζ s − k, = s . (−w) D D k The second statement is a consequence of the above formula and the fact that ζ (s−k, α) has a simple pole at k + 1 with the residue 1.
Corollary 3.3 Let γ ∈ C with γ D = 1. We have ζ pγ (s, w) =
r −1 D−1 m m 1 m+v v+w m−k k (−w) . γ d (v) D ζ s − k, m k Ds D m=0 v=0
k=0
The function ζ pγ (s, w) is meromorphic in the whole complex plane with poles at most in the set {1, . . . , r } which are all simple with residues Rγ (w, k + 1) := Ress=k+1 ζ p (s, w) r −1 D−1 1 m (−w)m−k γ m+v dm (v), 0 ≤ k ≤ r − 1. = k D v=0
m=k
Proof This follows from Proposition 3.2.
We consider the Dirichlet series ζ p (s) :=
∞ p(n) , ns n=1
which is convergent for Re(s) > r . It holds that ζ p (s) := lim (ζ p (s, w) − p(0) · w −s ). w→0
123
M. Cimpoea¸s, F. Nicolae
The Dirichlet series associated to pγ (n) is ∞ pγ (n) . ns
ζ pγ (s) :=
n=1
It converges for Re(s) > r . It holds that ζ pγ (s) = lim (ζ pγ (s, w) − pγ (0) · w −s ). w→0
As a consequence of Proposition 3.2 and Corollary 3.3, we get Proposition 3.4 (i) We have ζ p (s) =
r −1 D
1
dm (v)ζ D s−m
v=1 m=0
s − m,
v . D
The function ζ p (s) is meromorphic in the whole complex plane with poles at most in the set {1, . . . , r } which are all simple with residues Rm := Ress=m ζ p(s) =
D−1 1 dm−1 (v), 1 ≤ m ≤ r. D v=0
(ii) We have ζ pγ (s) =
D r −1 v=1 m=0
v v . γ d (v)ζ s − m, m D s−m D 1
The function ζ pγ (s) is meromorphic in the whole complex plane with poles at most in the set {1, . . . , r } which are all simple with residues Rγ ,m := Ress=m ζ pγ (s) =
D−1 1 v γ dm−1 (v), 1 ≤ m ≤ r. D v=0
(iii) It holds that R(k + 1, w) = Rγ (k + 1, w) =
r −1 m=k r −1 m=k
123
Rm+1
m (−w)m−k , k
Rγ ,m+1
m (−w)m−k . k
On the restricted partition function
Proposition 3.5 Let γ ∈ C with γ D = 1. We have Pγ (n) = Rγ ,r nr −1 + · · · + Rγ ,2 n + Rγ ,1 . In particular, for γ = 1, we have P(n) = Rr nr −1 + · · · + R2 n + R1 . Proof Without loss of generality, we may assume that γ = 1 and we prove the last D−1 := αd n d +· · ·+α1 n+α0 di (v), 0 ≤ i ≤ r −1. Let P(n) statement. Let αi := D1 v=0 ¯ and U (n) := p(n)− P(n). It follows that U (n) = dr −1 (n)nr −1 +· · ·+ d¯1 (n)n+ d¯0 (n), where d¯i (n) = d i (n) − αi , for 0 ≤ i ≤ r − 1. i n i n n+i )(i) +· · ·+γ (z n+1 ) + ¯ Let Si (z) := ∞ i1 n=0 di (n)n z . It holds that n z = γii (z n γi0 z , for some γi j ∈ Z. It follows that Si (z) =
=
∞
d¯i (n)
i
γi j (z
n=0
j=0
D−1
i
v=0
d¯i (v)
n+ j ( j)
)
=
D−1 v=0
γi j
j=0
z v+ j 1 − zD
i ∞
d¯i (v)
( j) =
γi j (z m D+v+ j )( j)
m=0 j=0 i
γi j
D−1 ( j) d¯i (v)z v+ j v=0
j=0
1 − zD
.
Since D−1
d¯i (v) =
v=0
D−1
D−1
v=0
v=0
(di (v) − αi ) =
di (v) − Dαi = 0,
it follows that D−1 v=0
Vi j (z) d¯i (v)z v+ j = , D 1−z 1 + z + · · · + z D−1
where Vi j (z) is a polynomial with deg(Vi j (z)) ≤ D −2 + j. Therefore, Si (z) = where deg(L i (z)) < deg(Mi (z)) and Mi (1) = 0. It follows that ∞
U (n)z n =
n=0
r −1 i=0
Si (z) =
L(z) M(z)
L i (z) Mi (z) ,
,
where deg L(z) < deg M(z) and M(1) = 0. By [14, Corollary 4.3.1] it follows that ∞ n=0
n = P(n)z
L(z) , (1 − z)r
123
M. Cimpoea¸s, F. Nicolae
where L(z) ∈ C[z] is a polynomial with deg L(z) ≤ r − 1. It holds that ∞
L(z) L(z) + , r (1 − z) M(z)
p(n)z n =
n=0 ∞
A(z) , (1 − z)m+1
P1 (n)z n =
n=0
where A(z) ∈ C[z] is a polynomial of degree ≤ m, ⎛ ∞ ∞ ⎝ ( p(n) − P1 (n))z n = n=0
⎞
Pλ (n)λn ⎠ z n
λ D =1, λ =1 ∞
n=0
=
Pλ (n)(λz)n =
λ D =1, λ =1 n=0
B(z) , C(z)
where B(z), C(z) ∈ C[z] with deg(B(z)) < deg(C(z)) and C(1) = 0, and hence L(z) L(z) B(z) A(z) . + + = r m+1 (1 − z) (1 − z) C(z) M(z) It follows that
L(z) (1−z)r
=
A(z) , (1−z)m+1
so P1 (n) = P(n).
We return to the setting of Sect. 2. As an illustration of our method, we provide new proofs for several results which are known in the literature. The following corollary extends Theorem 1.1 of Dilcher and Vignat [5]: the authors prove the formula for D = a1 · · · ar , and we prove it for any common multiple of a1 , . . . , ar . Corollary 3.6 For the polynomial part Pa (n) of the quasi-polynomial pa (n), we have Pa (n) =
1 D(r − 1)!
r
−1
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 =1
n − a1 j1 − · · · − ar jr + . D
1
Proof The proof is similar to the proof of Corollary 2.10, taking into account Proposition 3.4(i) and Proposition 3.5.
For 1 ≤ m ≤ r let Rm := Ress=m (ζa (s)). For t ≥ 0 let αt :=
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr 1
123
(a1 j1 + · · · + ar jr )t . −1
On the restricted partition function
Corollary 3.7 For 1 ≤ m ≤ r , we have Rm =
r −1 r k 1 (−1)k−m+1 D −k αk−m+1 . k m−1 D(r − 1)! k=m−1
Proof According to Proposition 3.4(i), we have D−1 1 da,m−1 (v). D
Rm =
v=0
The conclusion follows from Theorem 2.8(1). The Bernoulli numbers B j are defined by ∞
zj z Bj , = ez − 1 j! j=0
1 B0 = 1, B1 = − 21 , B2 = 16 , B4 = − 30 , and Bn = 0 if n is odd and greater than 1. For k > 0, we have Faulhaber’s identity
k 1 k+1 B j n k+1− j . 1 + 2 + · · · + (n − 1) = j k+1 k
k
k
(3.1)
j=0
Lemma 3.8 We have i1
αt = t! ·
i 1 +···+ir =t 1 =0
···
ir r =0
B1 B2 · · · Br (i 1 + 1 − 1 )!1 ! · · · (ir + 1 − r )!r !
×D t+r −1 −···−r a11 −1 · · · arr −1 . Proof We have
αt =
(a1 j1 + · · · + ar jr )t
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 1
=
t (a1 j1 )i1 · · · (ar jr )ir i 1 , . . . , ir
0≤ j1 ≤ aD −1,...,0≤ jr ≤ aDr −1 i 1 +···+ir =t 1
=
i 1 +···+ir =t
D a1 −1 ar −1 i t i1 ir a · · · ar j11 · · · jrir . i 1 , . . . , ir 1
The conclusion follows from (3.1) and (3.2).
D
j1 =0
(3.2)
jr =0
123
M. Cimpoea¸s, F. Nicolae
Lemma 3.9 For r ≥ 2 and 0 ≤ j ≤ r − 2, we have
d j x (r ) (−t1 − · · · − tr )dt1 · · · dtr = 0. dx j
[0,1]r
Proof To ease notation we put Q(x) := x (r ) . Let I :=
[0,1]r
Q ( j) (−t1 − · · · − tr )dt1 · · · dtr .
Using the change of variables u i = ti − 21 , 1 ≤ i ≤ r , we have I =
− 21 , 12
r
r du 1 · · · du r , Q ( j) −u 1 − · · · − u r − 2
where Q ( j) is the jth derivative of Q. Let Q(x) := Q(x − r2 ). If r is even then r 2 2 2 2 2 2 = − Q(x). Q(x) = x(x − 1 )(x − 2 ) · · · (x − ( 2 − 1) ), and hence Q(−x) 1 3 r 2 2 2 2 2 2 If r is odd then Q(x) = (x − ( 2 ) )(x − ( 2 ) ) · · · (x − ( 2 − 1) ), and hence ( j) ( j) (x) is even if r − j is odd. Q(−x) = Q(x). So Q (x) is odd if r − j is even and Q If r − j is even then, using the change of variables vi = −u i , 1 ≤ i ≤ r , we have I =
r − 21 , 12
( j) (−u 1 − · · · − u r )du 1 · · · du r Q
= (−1)2r
− 21 , 12
r
( j) (v1 + · · · + vr )dv1 · · · dvr = −I, Q
( j) is odd. Thus I = 0. since Q If r − j is odd it holds that I = =
r − 21 , 12
( j) (−u 1 − · · · − u r )du 1 · · · du r Q
r −1 + r −1 × 0, 21 × − 21 ,0 − 21 , 12 − 21 , 12
=: I1 + I2 .
Using the change of variables vi = u i , for 1 ≤ i ≤ r − 1 and vr = −u r , it follows that ( j) (−u 1 − · · · − u r )du 1 · · · du r I2 = Q r −1 − 21 , 21
× − 21 ,0
r −1 × 0, 21
=−
123
− 21 , 21
( j) (−v1 − · · · − vr −1 + vr )dv1 · · · dvr . Q
On the restricted partition function
Thus I = I1 + I2 =
( j) (−u 1 r −1 ( Q × 0, 21 − 21 , 21
− · · · − ur )
( j) (−u 1 − · · · − u r −1 + u r ))du 1 · · · du r . −Q Using the change of variables vi = −u i for 1 ≤ i ≤ r − 1, vr = u r and the fact that ( j) is even it follows that Q I =
( j) (v1 r −1 ( Q × 0, 21 − 21 , 12
+ · · · + vr −1 − vr )
( j) (v1 + · · · + vr ))dv1 · · · dvr = −I, −Q and hence I = 0.
The Bernoulli–Barnes numbers B j (a1 , . . . , ar ) are defined by ∞ zn zj = . B (a , . . . , a ) j 1 r (ea1 z − 1) · · · (ear z − 1) j! j=0
The Bernoulli–Barnes numbers and Bernoulli numbers are related as j B j (a1 , . . . , ar ) = Bi1 · · · Bir a1i1 −1 · · · arir −1 , i 1 , . . . , ir
(3.3)
i 1 +···+ir = j
see [2, p. 2]. The following Theorem can be seen as a direct consequence of formula (3.9) in Ruijsenaars [11]. Theorem 3.10 For 1 ≤ m ≤ r we have Rm =
(−1)r −m Br −m (a1 , . . . , ar ). (m − 1)!
Proof From Corollary 3.7 and Lemma 3.8, it follows that r −1 r k 1 k−m+1 Rm = (−1) D −k αk−m+1 k m−1 D(r − 1)! k=m−1
=
r −1 r k! 1 (−1)k−m+1 D −k k D(r − 1)! (m − 1)! k=m−1
×
i1
i 1 +···+ir =k−m+1 1 =0
···
ir r =0
B1 B2 · · · Br (i 1 + 1 − 1 )!1 ! · · · (ir + 1 − r )!r !
×D k−m+1+r −1 −···−r a11 −1 · · · arr −1 .
(3.4)
123
M. Cimpoea¸s, F. Nicolae
Let R¯ m be the part of the above sum with k = r − 1 and 1 = i 1 , . . . , r = ir . We have R¯ m =
(−1)r −m (a1 · · · ar )(m − 1)!
i 1 +···+ir =r −m
Bi1 · · · Bir i1 a · · · arir . i 1 ! · · · ir ! 1
R¯ m . Assume r ≥ 2 and m < r . Let We show that Rm = R¯ m . If r = m then Rm = 1 ≥ 0, . . . , r ≥ 0 be some integers with := rj=1 j < r − m. The coefficient of B1 B2 · · · Br Dr −m−1 −···−r a11 · · · arr in (3.4) is S :=
r −m t=
r (t + m − 1)! (−1)t (m − 1)! t +m−1
i 1 ≥1 ,...,ir ≥r i 1 +···+ir =t
1 . (i 1 + 1 − 1 )!1 ! · · · (ir + 1 − r )!r !
Let s j = i j − j . It follows that r −m r (t + m − 1)! 1 (−1)t S= t +m−1 (m − 1)!1 ! · · · r ! (t − )! t= t− s1 ,...,rr × (s1 + 1) · · · (sr + 1) s1 +···+sr =t−
r −m r (−1) (t + m − 1)! (−1)t− = t +m−1 (m − 1)!1 ! · · · r ! (t − )! t= × (t1 + · · · + tr )t− dt1 · · · dtr [0,1]r
(−1) = (m − 1)!1 ! · · · r !
=
r −m
r (t + m − 1)! (t − )! t +m−1
[0,1]r t= × (−t1 − · · · − tr )t− dtu+1 · · · dtr d +m−1 x (r ) (−1)
(m − 1)!1 ! · · · r !
[0,1]r
d x +m−1
(−t1 − · · · − tr )dt1 · · · dtr = 0,
by Lemma 3.9. Since Rm − R¯ m is a sum of terms of the form S it follows that Rm = R¯ m . The conclusion follows from (3.3).
Bayad and Beck [2, Formula 1.8, p. 1323] use the Bernoulli–Barnes polynomials defined by ∞
(ea1 z
123
zn ex z zj = . B (x; (a , . . . , a )) j 1 r − 1) · · · (ear z − 1) j! j=0
On the restricted partition function
Our Bernoulli–Barnes numbers B j (a1 , . . . , ar ) are related to the Bernoulli–Barnes polynomials by the formula B j (a1 , . . . , ar ) = B j (0; (a1 , . . . , ar )). In the proof of their Theorem 3.1, Bayad and Beck compute the residue at z = 1 of the function Ft (z) =
z t+1
r
1
i=1 (1 −
z ai )
as being (−1)r Br −1 (−t; (a1 , . . . , ar )). (r − 1)! For t = 0 one obtains (−1)r (−1)r Br −1 (0; (a1 , . . . , ar )) = Br −1 (a1 , . . . , ar ) = −R1 , (r − 1)! (r − 1)! where R1 is the residue of the function ζa (s) at s = 1, which we have computed in our Theorem 3.10. In the last corollary, we provide a new proof for the formula of Beck, Gessler and Komatsu [3, p. 2] of the polynomial part of pa (n). Corollary 3.11 The polynomial part of pa (n) is Pa (n) :=
r −1 (−1)u 1 a1 · · · ar (r − 1 − u)! u=0
i 1 +···+ir =u
Bi1 · · · Bir i1 a · · · arir nr −1−u . i 1 ! · · · ir ! 1
Proof This follows from Proposition 2.6 and Theorem 3.10.
Acknowledgements We thank the referee for the valuable suggestions which helped to improve our paper.
References 1. Barnes, E.W.: On the theory of the multiple gamma function. Trans. Camb. Philos. Soc. 19, 374–425 (1904) 2. Bayad, A., Beck, M.: Relations for Bernoulli–Barnes numbers and Barnes zeta functions. Int. J. Number Theory 10, 1321–1335 (2014) 3. Beck, M., Gessel, I.M., Komatsu, T.: The polynomial part of a restricted partition function related to the Frobenius problem, Electron. J. Comb. 8(1), N7 (5 pp) (2001) 4. Bell, E.T.: Interpolated denumerants and Lambert series. Am. J. Math. 65, 382–386 (1943) 5. Dilcher, K., Vignat, C.: An explicit form of the polynomial part of a restricted partition function. Res. Number Theory 3, 1 (2017). https://doi.org/10.1007/s40993-016-0065-3 6. Glaisher, J.W.L.: Formulae for partitions into given elements, derived from Sylvesters theorem. Q. J. Pure Appl. Math. 40, 275348 (1908) 7. Pólya, G., Szegö, G.: Aufgaben und Lehrsätze aus der analysis. Springer, Berlin (1925)
123
M. Cimpoea¸s, F. Nicolae 8. Popoviciu, T.: Asupra unei probleme de parti¸tie a numerelor. Acad. Republicii Populare Române, Filiala Cluj, Studii s¸i cercet˘ari s¸tiin¸tifice (Romanian) 4, 7–58 (1953) 9. Rubinstein, B.Y.: Expression for restricted partition function through Bernoulli polynomials. Ramanujan J. 15(2), 177–185 (2008) 10. Rubinstein, B.Y., Fel, L.G.: Restricted partition functions as Bernoulli and Eulerian polynomials of higher order. Ramanujan J. 11(3), 331–347 (2006) 11. Ruijsenaars, S.N.M.: On Barnes’ multiple zeta and gamma functions. Adv. Math. 156, 107–132 (2000) 12. Sills, A.V., Zeilberger, D.: Formulae for the number of partitions of n into at most m parts (using the quasi-polynomial ansatz). Adv. Appl. Math. 48(5), 640645 (2012) 13. Spreafico, M.: On the Barnes double zeta and gamma function. J. Number Theory 129(9), 2035–2063 (2009) 14. Stanley, R.P.: Enumerative Combinatorics, vol. 1. Wadsworth and Brooks/Cole, Monterey (1986) 15. Sylvester, J.J.: On the partition of numbers. Q. J. Pure Appl. Math. 1, 141–152 (1857) 16. Sylvester, J.J.: On subinvariants, i.e. semi-invariants to binary quantics of an unli mited order with an excursus on rational fractions and partitions. Am. J. Math. 5, 79–136 (1882)
123
