Glaisher’s Divisors and Infinite Products

Hartosh Singh Bal The Caravan Jhandewalan Extension New Delhi 110001 India

                       hartoshbal@gmail.com

Gaurav Bhatnagar Department of Mathematics Ashoka University Sonipat Haryana 131029 India

                       bhatnagarg@gmail.com

Abstract

Ramanujan gave a recurrence relation for the partition function in terms of the sum of the divisors function σ(n). In 1885, Glaisher considered seven divisor sums closely related to the sum of the divisors function. We develop a calculus to associate a partition generating function with each of these divisor sums. This yields analogues of Ramanujan’s recurrence relation for several partition-theoretic functions as well as r_{k}(n) and t_{k}(n), functions counting the number of ways of writing a number as a sum of squares (respectively, triangular numbers). As by-products of this association, we obtain several convolutions, recurrences and congruences for divisor functions. We give alternate proofs of two classical theorems, one due to Legendre and the other— Ramanujan’s congruence p(5n + 4) ≡ 0 (mod 5).

1 Introduction

Let σ(n) be the sum of divisors of n and p(n) the number of unordered integer partitions of n. There is a famous recurrence relation connecting them:

np(n) = ∑_{i=1}^{n} σ(i)p(n − i).  (1)

This has been found in Ramanujan’s work (see [6, p. 108]). There are several divisor functions studied in the literature. One can ask whether there are analogues of (1) which relate divisor functions to partition-theoretic functions.

The purpose of this paper is to answer this question for seven sums over divisors, studied by Glaisher [14]. Each of these can be expressed in terms of σ(n), where we take σ(n) = 0 whenever n is not a positive integer. The seven sums, which we call Glaisher’s divisors, are listed in Williams [28, p. xvi], and are as follows:

d_{A}(n) = ∑_{d|n} d = σ(n);  (2)
d_{B}(n) = ∑_{\begin{matrix}d|n \\ d odd \end{matrix}} d = σ(n) − 2σ(n/2);  (3)

d_{C}(n) = ∑_{\begin{matrix}d|n \\ d even \end{matrix}} d = 2σ(n/2);  (4)

d_{D}(n) = ∑_{\begin{matrix}d|n \\ n/d odd \end{matrix}} d = σ(n) − σ(n/2);  (5)

d_{E}(n) = ∑_{\begin{matrix}d|n \\ n/d even \end{matrix}} d = σ(n/2);  (6)

d_{F} (n) = ∑_{d|n}(−1)^{d−1}d = σ(n) − 4σ(n/2);  (7)
d_{G}(n) = ∑_{d|n}(−1)^{n/d−1}d = σ(n) − 2σ(n/2).  (8)

The expressions of Glaisher’s divisors in terms of the divisor function σ(n) on the right-hand side of each of the above follow by elementary number-theoretic considerations.

In this paper, we find connections of Glaisher’s divisors with the following functions (see Andrews and Eriksson [2] for an introduction to partition functions).

p_{o}(n) := p(n | odd parts), the number of partitions with all parts odd;
p_{d}(n) := p(n | distinct parts), the number of partitions with distinct parts;
p_{e}(n) := p(n | even parts), the number of partitions with all parts even;
\overline{p}(n) := the number of overpartitions of n.

Of these, only the last one—introduced by Corteel and Lovejoy [10]—is not self-explanatory. An overpartition is a partition where the first occurrence of a part may be overlined. For example, 5 + 3 + \overline{2} + 2 + \overline{1} + 1 + 1 is an overpartition of 15.

In addition, two other number-theoretic functions appear in our results.

r_{m}(n) := the number of ways of writing n as an ordered sum of m squares of integers;
t_{m}(n) := the number of ways of writing n as an ordered sum of m triangular numbers.

The analogues of (1) we find are all recurrence relations connecting Glaisher’s divisors to the above functions. Two other divisor functions appear naturally, as special cases. Let σ_{3}(n) be the sum of cubes of the divisors of n. Then we require:

\overline{σ}_{3}(n) := ∑_{\begin{matrix}d|n \\ n/d odd \end{matrix}} d^{3} = σ_{3}(n) − σ_{3}(n/2);  (9)

and

σ̃_{3}(n) := ∑_{d|n}(−1)^{d−1}d^{3} = σ_{3}(n) − 16σ_{3}(n/2).  (10)

Ramanujan had a very general entry (see Berndt [5, Entry 12a, p. 28]) which indicates an approach to recurrences such as (1). Our approach is a mild modification of Ramanujan’s approach. We begin with a definition.

Definition 1 (Series-divisor). Let

A(q) = ∑_{k=0}^{∞} a(k)q^{k}

be a formal power series. The series divisor (σ^{A}(k)) for k = 1, 2, … is defined by the equation

∑_{k=1}^{∞} ka(k)q^{k} = ∑_{k=1}^{∞} σ^{A}(k)q^{k} ∑_{k=0}^{∞} a(k)q^{k}.  (11)

We define

σ^{A}(r) = 0 unless r ∈ ℤ and r > 0.  (12)

Alternatively, (11) specifies the recurrence

na(n) = ∑_{i=1}^{n} σ^{A}(i)a(n − i),  (13)

which can also be used to define the series-divisor σ^{A}(n), for n = 1, 2, . . ..

We develop a calculus to associate a divisor function with an infinite product. In turn, this infinite product is the generating function of the relevant partition-theoretic or arithmetic sequence. The approach is elementary. Nevertheless, we succeed in finding several new results which fit in well with the existing literature.

Note that when the formal power series A(q) is the generating function for the number of partitions of p(n), that is,

∏_{k=0}^{∞} \frac{1}{(1 − q^{k})} = ∑_{n=0}^{∞} p(n)q^{n},

then (13) reduces to (1). This motivates the term “series-divisor”.

Evidently, the series-divisor is nothing but the coefficients of the logarithmic derivative of A(q). Finding the recurrence relation satisfied by a sequence whose generating function is known using logarithmic derivatives is standard in generatingfunctionology (see Wilf [27, p. 22]). Thus, we usually find the series-divisor from a generating function. Here we develop the calculus to go in the reverse direction—from the divisor sum to the generating function.

Our approach was implicit in our earlier work [4]. In that paper, we applied this idea to embed Ramanujan’s congruences p(5n + 4) ≡ τ(5n) ≡ 0 (mod 5) into an infinite family of such recurrences. Here τ is Ramanujan’s τ function [7, p. 5], defined by

∏_{k=1}^{∞} (1 − q^{k})^{24} = ∑_{n=0}^{∞} τ(n + 1)q^{n}.

In the current work, the focus is on divisor functions and their correspondence with functions from additive number theory. As an immediate consequence of this correspondence, we obtain recurrence relations connecting the two. In §2 we develop the calculus and list these recurrence relations. As special cases, we obtain some more recurrence relations for divisor functions. There are further recurrence relations in §3 which are obtained by using an elementary idea that was used very effectively by Gould [16]. Next, in §4, we round off the applications of our calculus by deriving a pair of formulas for overpartitions of n, analogous to results for the partition function due to Euler and Glaisher.

Aside from (14), there seem to be few results connecting partition-theoretic functions with the multiplicative functions of number theory; see Merca [21] and previous work by the authors [4]. Christopher [9] and Merca [23] obtained results analogous to Euler’s recursion for partitions, which is obtained by using the pentagonal number theorem. Convolutions of Glaisher’s divisors appear in [19, 17]. Many such results have been obtained by using Liouville’s approach in Williams [28]. Regarding congruences for the divisor functions, congruences such as 3|σ(3n + 2) and 4|σ(4n + 3) follow from the definition of σ(n). Bonciocat [8] and Gallardo [13] proved congruences for the convolution of the sum of divisors functions. Merca [22] has examined congruence sums for d_{B}(n) over the extended pentagonal numbers. Fine [12] has shown the application of bilateral q-hypergeometric series evaluations to divisor functions; Berndt [7] uses similar techniques.

The results of this paper complement other work in the area. We illustrate this in §5 by giving alternate proofs of two classical results. One of them is due to Legendre:

t_{4}(j) = σ(2j + 1).

We also give an alternate proof of Ramanujan’s famous recurrence

p(5n + 4) ≡ 0 (mod 5).

Our proof gives an example of an equivalence between a congruence result from partition theory with one involving the convolution of the sum of divisors function σ(n). We conclude with another example of this kind involving overpartitions.

1.1 OEIS references

For further information about the sequences appearing in this paper, as well as an extensive list of sequences studied by Glaisher, consult the On-Line Encyclopedia of Integer Sequences (OEIS) [25]. This paper is concerned with the following sequences: d_{A}(n): \underline{A000203}; d_{B}(n) and d_{G}(n): \underline{A000593}; d_{C}(n): \underline{A146076}; d_{D}(n): \underline{A002131}; 2d_{E}(n): \underline{A146076}; d_{F} (n): \underline{A002129}; σ_{3}(n): \underline{A001158}; \overline{σ}_{3}(n): \underline{A007331}; σ̃_{3}(n): \underline{A138503}; p_{d}(n) and p_{o}(n): \underline{A000009}; p_{e}(n): \underline{A035363}; \overline{p}(n): \underline{A015128}; t_{4}(n) = σ(2n + 1): \underline{A008438}. The convolution of d_{A}(n) with itself (the sum on the left-hand side of (58)) appears in \underline{A000385}. In addition, we find congruences for the following sequences: \underline{A008439} (52); \underline{A226253} (55).

2 Recurrences for the sum of divisors function

We begin our development of a calculus of series-divisors, which allows us to virtually readoff the corresponding generating function—of an appropriate partition function—from the divisor function.

The following is the first of three useful lemmas about series-divisors (recall Definition 1).

Lemma 2 (Addition lemma). Let σ^{A}(k) and σ^{B}(k) be the series-divisors for the power series A(q) and B(q). Then σ^{A}(k) + σ^{B}(k) is the series-divisor for A(q)B(q). That is, the series-divisor of the product of two power series is the sum of the respective series-divisors.

Proof. The proof is immediate from the fact that the log of a product is the sum of the logs.

The following proposition allows us to compute series-divisors in many cases of interest. Proposition 3 (Calculus of series-divisors I). Let A(q) and (σ^{A}(k)) be as in Lemma 2. For k = 1, 2, …, we have the following.

(i) The series divisors of A(q)^{−1} are given by ( − σ^{A}(k)). (ii) The series divisors of A(−q) are given by ((−1)^{k}σ^{A}(k)). (iii) The series divisors of A(q^{n}) are given by (nσ^{A}(k/n)). (iv) The series divisors of A(q)^{n} are given by (nσ^{A}(k)). Proof. While parts (i) and (iv) follows from the addition lemma, the other two parts follow from (13). For part (iii), recall that we take σ^{A}(r) = 0 unless r is a positive integer. Corollary 4 (Recursion for powers). Let a_{m}(k) be the coefficients of the mth powers of the power series A(q), that is,

A(q)^{m} = ∑_{k=0}^{∞} a_{m}(k)q^{k}.

Then

na_{m}(n) = m ∑_{j=1}^{n} σ^{A}(i)a_{m}(n − j).  (14)

Proof. This is immediate from Proposition 3 (part (iv)) and (13). Example 5 (The calculus of series-divisors II). The following will allow us to compute the series-divisor for a host of infinite products. The first is trivial. The rest follow from the previous ones, using Proposition 3.

1. The series-divisor for A(q) = 1 − q is (−1, −1, −1, …) since

−q = (1 − q) ∑_{k=1}^{∞}(−1)q^{k}.

2. The series-divisor for (1 − q)^{−1} is (1, 1, 1, …).

3. The series-divisor for 1 + q is (1, −1, 1, …).

4. The series-divisor for (1 + q)^{−1} is (−1, 1, −1, …).

5. If A(q) = 1 − q^{n}, then the series-divisor is the sequence

σ^{A}(k) = \begin{cases}−n, & if k = mn, for some m ∈ ℕ; \\ 0, & otherwise. \end{cases}

6. If A(q) = (1 − q^{n})^{−1}, then

σ^{A}(k) = \begin{cases}n, & if k = mn, for some m ∈ ℕ; \\ 0, & otherwise. \end{cases}

7. If A(q) = 1 + q^{n}, then

σ^{A}(k) = \begin{cases}(−1)^{m−1}n, & if k = mn, for some m ∈ ℕ; \\ 0, & otherwise. \end{cases}

8. Finally, the series-divisor for A(q) = (1 + q^{n})^{−1} is

σ^{A}(k) = \begin{cases}(−1)^{m}n, & if k = mn, for some m ∈ ℕ; \\ 0, & otherwise. \end{cases}

Remark 6 (Alternative recursion for the binomial coefficients). Combining part (1) above with the recursion (14), we see that the series-divisor for A(q) = (1 − q)^{m} satisfies the recurrence equation

na_{m}(n) = −m ∑_{j=1}^{n} a_{m}(n − j) with a(0) = 1.

The first few terms of a_{m}(j), for j = 0, 1, 2, 3, are 1,−j, j(j − 1)/2 and −j(j − 1)(j − 2)/6. From here it it not difficult to obtain the usual formula for the binomial coefficients and prove it satisfies the above recursion.

Example 7 (The recurrence (1)). Let p(n) be the number of integer partitions of n. We apply the addition lemma term by term to the generating function

P (q) = ∏_{k=1}^{∞} \frac{1}{1 − q^{k}} = ∑_{k=0}^{∞} p(k)q^{k}.  (15)

From the above, the series divisors for (1−q)^{−1}, (1−q^{2})^{−1}, … are easy to find, and then they are summed using the addition lemma. Here we have used ↭ to denote the correspondence.

\frac{1}{1 − q} ↭ (1, 1, 1, 1, 1, 1, 1, 1, …)
\frac{1}{1 − q^{2}} ↭ (0, 2, 0, 2, 0, 2, 0, 2, …)
\frac{1}{1 − q^{3}} ↭ (0, 0, 3, 0, 0, 3, 0, 0, …)
⋮
∏_{k=1}^{∞} \frac{1}{1 − q^{k}} ↭ (1, 3, 4, 7, …)

Summing each component, we see that the series-divisor is σ(i), the sum of divisors function. The recurrence (1) is thus a special case of (13).

Notation 8. We use the notation ↭ to indicate the correspondence between series-divisors σ^{A}(k) and infinite products A(q).

The calculations in Example 7 are easily reversed to associate sums of divisors with an infinite product. In the rest of this section, we apply this to each one of Glaisher’s divisors. The associated infinite products are interesting in their own right, and lead to analogues of (1) with other partition-theoretic functions.

In the following, the generating functions of the various partition-theoretic functions are required. These can be found in [2] and [10]. In addition, we require two theta functions from Berndt [7, p. 7]:

φ(q) := ∑_{k=−∞}^{∞} q^{k^{2}} = ∏_{k=1}^{∞} (1 + q^{2k−1})^{2}(1 − q^{2k})  (16)

and

ψ(q) := ∑_{k=0}^{∞} q^{\frac{k(k+1)}{2}} = ∏_{k=1}^{∞} \frac{(1 − q^{2k})}{(1 − q^{2k−1})}.  (17)

The factorizations into infinite products are due to Gauss and special cases of Jacobi’s triple product identity; we refer to Andrews, Askey and Roy [1, p. 500] (a small typo in [1, (eq. (10.4.8)] is corrected in (17)). Note that these are the only identities in the list of such identities in [1, p. 500] where the sums have positive coefficients.

Theorem 9. Let d_{A}(n), d_{B}(n), …, d_{G}(n) be Glaisher’s divisor functions. They are seriesdivisors of the following products, which, in turn, are generating functions as given below.

d_{A}(n) = σ(n) ↭ ∏_{k=1}^{∞} \frac{1}{1 − q^{k}} = ∑_{k=0}^{∞} p(k)q^{k};  (18)

d_{B}(n) ↭ ∏_{k=1}^{∞} \frac{1}{1 − q^{2k−1}} = ∑_{k=0}^{∞} p_{o}(k)q^{k};  (19)

d_{C}(n) = 2d_{E}(n) ↭ ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} = ∑_{k=0}^{∞} p_{e}(k)q^{k};  (20)

2d_{D}(n) ↭ ∏_{k=1}^{∞} \frac{1 + q^{k}}{1 − q^{k}} = ∑_{k=0}^{∞} \overline{p}(k)q^{k};  (21)

(−1)^{n+1}2d_{D}(n) ↭ ∏_{k=1}^{∞}(1 + q^{2k−1})^{2}(1 − q^{2k}) = φ(q) = ∑_{k=−∞}^{∞} q^{k^{2}};  (22)

d_{F} (n) ↭ ∏_{k=1}^{∞} \frac{(1 − q^{2k})}{(1 − q^{2k−1})} = ψ(q) = ∑_{k=0}^{∞} q^{\frac{k(k+1)}{2}} ;  (23)

d_{G}(n) ↭ ∏_{k=1}^{∞}(1 + q^{k}) = ∑_{k=0}^{∞} p_{d}(k)q^{k}.  (24)

Proof. The proof of (18) outlined in Example 7 extends easily to prove (19) and (20). Here only the odd (respectively, even) divisors are there, with only the corresponding terms in the infinite product. That d_{C}(n) = 2d_{E}(n) follows from the right-hand side of (4) and (6).

Next we consider the sequence (d_{G}(n)). The sequence is generated by summing

(1, −1, 1, −1, …), (0, 2, 0, −2, …),

and so on. Thus, d_{G}(n) ↭ ∏_{k=1}^{∞}(1 + q^{k}) which is the generating function of partitions with distinct parts. This gives (24).

From here we obtain

2d_{D}(n) = d_{A}(n) + d_{B}(n) ↭ ∏_{k=1}^{∞} \frac{1}{1 − q^{k}} ∏_{k=1}^{∞} \frac{1}{1 − q^{2k−1}} = ∏_{k=1}^{∞} \frac{1 + q^{k}}{1 − q^{k}} ,

where we have used the analytic form of Euler’s theorem that the number of partitions with distinct parts equals the number of partitions with odd parts. This shows (21).

To show (22), consider the following:

φ(q) = ∏_{k=1}^{∞}(1 − (−q)^{2k−1})^{2}(1 − (−q)^{2k}) ↭ −(−1)^{n}2d_{B}(n) − (−1)^{n}d_{C}(n)

= (−1)^{n+1}((2(σ(n) − 2σ(n/2)) + 2σ(n/2)) = (−1)^{n+1}2d_{D}(n).

Finally, observe that

d_{F} (n) = σ(n) − 4σ(n/2) = d_{B}(n) − d_{C}(n) ↭ ∏_{k=1}^{∞} \frac{(1 − q^{2k})}{(1 − q^{2k−1})} = ψ(q).

From the correspondence between Glaisher’s divisor functions and partition-theoretic generating functions, we obtain analogues of Ramanujan’s recurrence (1).

Theorem 10. The following recurrence relations hold.

np_{e}(n) = ∑_{i=1}^{n} d_{C}(i)p_{e}(n − i) = 2 ∑_{i=1}^{n} σ(i/2)p_{e}(n − i);  (25)

np_{d}(n) = ∑_{i=1}^{n} d_{B}(i)p_{o}(n − i) = ∑_{i=1}^{n} d_{G}(i)p_{d}(n − i);  (26)

= ∑_{i=1}^{n} (σ(i) − 2σ(i/2))p_{d}(n − i);  (27)

n\overline{p}(n) = 2 ∑_{i=1}^{n} d_{D}(i)\overline{p}(n − i) = 2 ∑_{i=1}^{n} (σ(i) − σ(i/2))\overline{p}(n − i).  (28)

Proof. These recurrence relations are just (13) when applied to (20), (19) and (24), and (21), respectively. In (26) and (27), we use Euler’s theorem p_{d}(n) = p_{o}(n).

Theorem 11. For integers n ≥ 0 and m > 0, let r_{m}(n), represent the number of ways n can be written as an ordered sum of m squares, and let t_{m}(n), represent the number of ways n can be written as an ordered sum of m triangular numbers. Then

nr_{m}(n) = m ∑_{j=1}^{n} 2(−1)^{j+1}(σ(j) − σ(j/2))r_{m}(n − j);  (29)

and,

nt_{m}(n) = m ∑_{j=1}^{n} (σ(j) − 4σ(j/2))t_{m}(n − j).  (30)

Remark 12. An equivalent version of Theorem 11 has been obtained independently by Andrews, Jha, and López-Bonilla [3] using methods similar to the ones in this paper.

Proof. Since the coefficient of q^{n} of φ(q)^{m} is the number of ways n can be written as a sum of m squares, by (14) we have (29). Similarly, the coefficients of ψ(q)^{m} are the number of ways n can be written as a sum of m triangular numbers; by (14) we have (30).

Remark 13. The calculus of series-divisors presented above is implicit in [4], where we consider any power series generated by an infinite product of the form

∏_{k=0}^{∞}(1 − q^{k})^{f(k)}.

In [4], f(k) can take complex values or could even be a polynomial with complex coefficients. Here we only require integral powers, so we provided a simpler exposition.

Next we take special cases of (29) and (30) to obtain several convolution recurrences for Glaisher’s divisor functions in terms of σ(n), \overline{σ}_{3}(n) and σ̃_{3}(n) (see (9) and (10)).

To take special cases, we use the following well-known identities given in [7, Theorems 3.3.1 and 3.3.4]. For n > 0, we have:

r_{1}(n) = \begin{cases}2, & if n = j^{2} for some j > 0; \\ 0, & otherwise. \end{cases}  (31)
r_{4}(n) = 8(σ(n) − 4σ(n/4)).  (32)
r_{8}(n) = (−1)^{n+1}16(σ_{3}(n) − 16σ_{3}(n/2)) = (−1)^{n+1}16σ̃_{3}(n).  (33)

In the above, r_{1}(0) = r_{4}(0) = r_{8}(0) = 1.

Next, we use the following for sums of triangular numbers (see [24, Theorems 3 and 5]):

t_{1}(n) = \begin{cases}1, & if n = j(j + 1)/2 for some j > 0; \\ 0, & otherwise. \end{cases}  (34)
t_{4}(n) = σ(2n + 1).  (35)
t_{8}(n) = σ_{3}(n + 1) − σ_{3}((n + 1)/2) = \overline{σ}_{3}(n + 1).  (36)

In the above, t_{1}(0) = t_{4}(0) = t_{8}(0) = 1.

Theorem 14. Let n be a positive integer. Then we have the following recursions:

d_{D}(n) + 2 ∑_{j=1}^{∞}(−1)^{j}d_{D}(n − j^{2}) = \begin{cases}(−1)^{n−1}n, & if n = j^{2} for some j; \\ 0, & otherwise. \end{cases} (37)

∑_{j=0}^{∞} d_{F} (n − \frac{j(j + 1)}{2}) = \begin{cases}n, & if n = j(j + 1)/2 for some j; \\ 0, & otherwise. \end{cases} (38)

8 ∑_{j=1}^{n−1}(−1)^{j+1}d_{D}(j)(σ(n − j) − 4σ(\frac{n − j}{4} )) = n(σ(n) − 4σ(\frac{n}{4})) + (−1)^{n}d_{D}(n).  (39)

4 ∑_{j=1}^{∞} d_{F} (j)σ(2n + 1 − 2j) = nσ(2n + 1).  (40)

16 ∑_{j=1}^{n−1} d_{D}(j)σ̃_{3}(n − j) = d_{D}(n) − nσ̃_{3}(n).  (41)

8 ∑_{j=1}^{n} d_{F} (j)\overline{σ}_{3}(n + 1 − j) = n\overline{σ}_{3}(n + 1).  (42)

Remark 15. Note that (37) is due to Liouville; see [28, Theorem 6.1]. Williams [28] also uses the notation σ^{∗}(n) for d_{D}(n) and σ̃(n) for d_{F} (n).

Proof. These results are special cases of (29) and (30). Plug in m = 1, 4 and 8 in (29), and use (31)-(33), to obtain (37), (39) and (41) (respectively). Similarly, (30) and (34)–(36) yield (38), (40) and (42).

Remark 16. We can obtain analogous results by specializing (29) and (30) using other values of m. For example, see [7, Theorems 3.2.1 and 3.4.1] for expressions for r_{m}(n) with m = 2 and 6, and [24, §3] for expressions for t_{m}(n) with several small values of m not considered here. All these give rise to analogous results. This remark applies to the theorems in §3 too.

3 Powers of a power series

The next set of results require an old trick involving powers of generating functions. It is a recurrence relation connecting powers of a generating function.

Lemma 17 (Power recursion lemma). For any power series A(q), the coefficients a_{u}, a_{v} of its powers (A(q))^{u} and (A(q))^{v}, where u and v are any two non-zero integers, satisfy:

∑_{k=0}^{n} (n − (u/v + 1)k)a_{u}(n − k)a_{v}(k) = 0.  (43)

Remark 18. This result holds as long as A(q)^{u} and A(q)^{v} are formal power series; see [4, Prop, 6.1]. Gould [16] credits this to Rothe (1793). For the sake of completeness, we repeat the proof from [4] for integral u and v.

Proof. We have

∑_{k=0}^{∞} ka_{u}(k)q^{k} = u( ∑_{k=1}^{∞} σ^{A}(k)q^{k})(A(q))^{u}; and, ∑_{k=0}^{∞} ka_{v}(k)q^{k} = v( ∑_{k=1}^{∞} σ^{A}(k)q^{k})(A(q))^{u}.

From here, we obtain

( ∑_{k=0}^{∞} ka_{u}(k)q^{k})( ∑_{k=0}^{∞} a_{v}(k)q^{k}) = \frac{u}{v}( ∑_{k=0}^{∞} ka_{v}(k)q^{k})( ∑_{k=1}^{∞} a_{u}(k)q^{k}).

Carrying out the Cauchy product and collecting terms we obtain (43).

Next, as in [4], we take u = 1, v = m, with A(q) = φ(q), ψ(q) to obtain

nr_{m}(n) = −2 ∑_{k=1}^{∞} (n − (m + 1)k^{2})r_{m}(n − k^{2}),  (44)

and,

nt_{m}(n) = − ∑_{k=1}^{∞} (n − (m + 1)k(k + 1)/2)t_{m}(n − k(k + 1)/2).  (45)

Of these, (44) appears in Venkov [26, p. 204] and Williams [28, p. 44]. These results yield recurrence relations for σ(n), \overline{σ}_{3}(n) and σ̃_{3}(n).

Theorem 19. Let n be a positive integer. Then we have the following recursions:

2nσ(2n + 1) = ∑_{j=1}^{∞} (5j(j + 1) − 2n)σ(2n + 1 − j(j + 1)).  (46)

n(σ(n)−4σ(\frac{n}{4}))−2 ∑_{j=1}^{∞}(5j^{2}−n)(σ(n−j^{2})−4σ(\frac{n − j^{2}}{4} )) = \begin{cases}n, & if n = j^{2} for some j; \\ 0, & otherwise. \end{cases} (47)

n\overline{σ}_{3}(n + 1) = ∑_{j=1}^{∞} (9\frac{j(j + 1)}{2} − n)\overline{σ}_{3}(n + 1 − \frac{j(j + 1)}{2}).  (48)

nσ̃_{3}(n) − 2 ∑_{j=1}^{∞}(−1)^{j}(9j^{2} − n)σ̃_{3}(n − j^{2}) = \begin{cases}(−1)^{n−1}n, & if n = j^{2} for some j; \\ 0, & otherwise. \end{cases}  (49)

∑_{j=0}^{∞}(3j − n)σ(2j + 1)\overline{σ}_{3}(n + 1 − j) = 0.  (50)

n(σ̃_{3}(n) + (−1)^{n}(σ(n) − 4σ(\frac{n}{4})) = 8 ∑_{j=1}^{n−1}(3j − n)(−1)^{j}(σ(j) − 4σ(\frac{j}{4}))σ̃_{3}(n − j). (51)

Proof. These results follow from (44) and (45) by taking n = 1, 4, 8, and using (31)-(33) and (34)-(36).

The recurrences in Theorem 14 and Theorem 19 yield several congruences for divisor functions.

Theorem 20. Let n be a positive integer. Then we have the following congruences:

If 5 ∤ n, then ∑_{j=0}^{∞} σ(2n + 1 − j(j + 1)) ≡ 0 (mod 5).  (52)

∑_{j=0}^{∞} σ(n − j(j + 1)/2) ≡ \begin{cases}0 (mod 4), & if n ≠ \frac{k(k+1)}{2} for some k; \\ n (mod 4), & if n = \frac{k(k+1)}{2} for some k. \end{cases}  (53)

If 5 ∤ n and n = 4m + 3 or 4m + 2, then

σ(n) + 2 ∑_{j=1}^{∞} σ(n − j^{2}) ≡ 0 (mod 5).  (54)

If (n, 3) = 1, then

∑_{j=0}^{∞} \overline{σ}_{3}(n + 1 − \frac{j(j + 1)}{2}) ≡ 0 (mod 3^{2}).  (55)

Proof. If 5 ∤ n, consider the identity (46) mod 5 and cancel the n to obtain (52). The identity (38) mod 4 immediately yields (53). Next, consider identity (47) mod 5 and note that j^{2} is always of the form 4k or 4k + 1

for some integer k so the terms σ((4m + 3 − j^{2})/4) = 0. Considering the resulting identity mod 5 gives (54).

Finally, (55) follows from (48).

Remark 21. The left-hand side of (52) is the sequence \underline{A008439}. It is the number of ways of writing a number n as a sum of 5 triangular numbers. Similarly, (55) (sequence \underline{A226253}) is the number of ways of writing the sequence as a sum of 9 triangular numbers.

Remark 22. There is a nice trick to deal with products when considering congruences modulo a prime number. It is convenient to introduce the notation of q-rising factorials. We define

(q; q)_{∞} := ∏_{k=0}^{∞} (1 − q^{k}).

Here we consider (q; q)_{∞} in the ring of formal power series. (As an analytic object, the product converges provided |q| < 1.)

Let p be a prime. Consider ℤ_{p}[[q]], the ring of power series with coefficients in ℤ_{p}, the finite field with p elements. In this ring, we have (1 − q^{k})^{p} = (1 − q^{pk}), and

((1 − q^{k})^{p})^{−1} = (1 − q^{kp})^{−1} = 1 + q^{kp} + q^{2kp} + · · · .

Thus, in ℤ_{p}[[q]],

(q; q)_{∞}^{p} = (q^{p}; q^{p})_{∞} and \frac{1}{(q; q)_{∞}^{p}} = \frac{1}{(q^{p}; q^{p})_{∞}} .

Thus, for any function f(q) which is a ratio of products of q-rising factorials, we must have

f(q)^{p} = f(q^{p}) (mod p).

In particular, this applies to ψ(q), which can be written as ψ(q) = (q^{2}; q^{2})_{∞}/(q; q^{2})_{∞} using q-rising factorials.

Regarding (52)—that is, \underline{A008439}—more is true.

Theorem 23. Let n be a positive integer. Then

∑_{j=0}^{∞} σ(2n + 1 − j(j + 1)) ≡ \begin{cases}0 (mod 5), & if n ≠ \frac{5k(k+1)}{2} for some k; \\ 1 (mod 5), & if n = \frac{5k(k+1)}{2} for some k. \end{cases}  (56)

Proof. Consider the product

ψ(q)^{5} = ψ(q)^{4}ψ(q),

and recall that t_{4}(n) = σ(2n + 1). On comparing coefficients, we obtain

t_{5}(n) = ∑_{j=0}^{∞} σ(2n + 1 − j(j + 1)).

Thus from Remark 22, we must have ψ(q)^{5} = ψ(q^{5}) (mod 5), and by comparing coefficients, we obtain (56).

Remark 24. We note that ψ(q)^{6} = ψ(q)^{4}ψ(q)ψ(q), so

t_{6}(n) = ∑_{j,k=0}^{∞} σ(2n + 1 − j(j + 1) − k(k + 1))

is divisible by 6 (in view of (30)) if n is relatively prime to 6. The process can be iterated.

4 Convolutions of series divisors

In this section, we give a pair of formulas for \overline{p}(n), the number of overpartitions of n. These are analogous to the following two results, due to Euler [11] and Glaisher [15] (respectively).

σ(n) = ∑_{i=−∞}^{∞}(−1)^{i}(n − \frac{i(3i − 1)}{2})p(n − \frac{i(3i − 1)}{2})  (57)

and

∑_{i=1}^{n} σ(n − i)σ(i) = ∑_{i=−∞}^{∞}(−1)^{i+1}(\frac{i(3i − 1)}{2})(n − \frac{i(3i − 1)}{2})p(n − \frac{i(3i − 1)}{2}).  (58)

We had derived (57) and (58) in [4], but had inadvertently omitted the reference to Glaisher. The following lemma formalizes our calculation in [4].

Lemma 25 (Convolution lemma). Let A(q) be a formal power series with coefficients a_{n}, and let B(q) = 1/A(q) have coefficients b(n). Then

σ^{A}(n) = ∑_{i=0}^{n}(n − i)a(n − i)b(i);  (59)

and,

∑_{i=1}^{n} σ^{A}(n − i)σ^{A}(i) = − ∑_{i=1}^{n} i(n − i)a(n − i)b(i).  (60)

Proof. Since

A(q) ∑_{i=1}^{∞} σ^{A}(i)q^{i} = ∑_{i=1}^{∞} ia(i)q^{i},

we get

∑_{i=1}^{∞} σ^{A}(i)q^{i} = B(q) ∑_{i=1}^{∞} a(i)q^{i}.

Carrying out the Cauchy product on the right-hand side gives us (59).

Since the series divisor of 1/A(q) is −σ^{A}, we also obtain

−\frac{A(q)}{A(q)} ∑_{i=1}^{∞} σ^{A}(i)q^{i} ∑_{i=1}^{∞} σ^{A}(i)q^{i} = ∑_{i=1}^{∞} ia(i)q^{i} ∑_{i=1}^{∞} ib(i)q^{i}.

Again, the Cauchy product on the right-hand side yields (60).

The results cited above follow from (59) and (60) by taking A(q) to be the generating function for partitions. The expansion of A(q)^{−1} as a power series is Euler’s pentagonal number theorem [1, p. 500]:

∏_{k=1}^{∞}(1 − q^{k}) = ∑_{n=−∞}^{∞}(−1)^{n}q^{\frac{n(3n−1)}{2}} .

The key idea is that the power series expansion of the reciprocal should be available.

Theorem 26. Let \overline{p}(n) be the number of overpartitions of n. Then

2d_{D}(n) = 2(σ(n) − σ(n/2)) = n\overline{p}(n) + 2 ∑_{i=1}^{∞}(−1)^{i}(n − i^{2})\overline{p}(n − i^{2});  (61)

and,

2 ∑_{i=1}^{n} d_{D}(n − i)d_{D}(i) = ∑_{i=1}^{∞}(−1)^{i+1}i^{2}(n − i^{2})\overline{p}(n − i^{2}).  (62)

Proof. By Theorem 9, the series-divisor 2d_{D}(n) is associated with the product

∏_{k=1}^{∞} \frac{(1 + q^{k})}{(1 − q^{k})} = ∑_{n=1}^{∞} \overline{p}(n)q^{n}

and

∏_{k=1}^{∞} \frac{(1 − q^{k})}{(1 + q^{k})} = 1 + 2 ∑_{n=1}^{∞}(−1)^{n}q^{n^{2}}.

The results follows from (59) and (60). The identity for the reciprocal of the generating function of \overline{p}(n) follows from (16) by replacing q by −q and manipulating the infinite products.

5 Two classical results

In this section, we give alternate proofs of two classical theorems, due to Legendre and Ramanujan. These illustrate the application of our approach to prove results involving the divisor functions or those in the theory of partitions.

First, we use (30) along with two results due to Melfi [20] to prove (35), a result of Legendre.

Proposition 27 (Legendre). For j = 0, 1, 2, 3, …,

t_{4}(j) = σ(2j + 1).

Proof. By (30), jt_{4}(j) = 4 ∑_{i=1}^{j} (σ(i) − 4σ(i/2))t_{4}(j − i). We show that σ(2j + 1) satisfies

the same recurrence by invoking two convolution identities proved by elementary means by Huard, Ou, Spearman, and Williams in [19]:

∑_{i=1}^{n} σ(i)σ(2n + 1 − 2i) = \frac{1}{24}(2σ_{3}(2n + 1) + (1 − 3(2n + 1))σ(2n + 1);

∑_{i=1}^{⌊n/2⌋} σ(i)σ(2n + 1 − 4i) = \frac{1}{48}(σ_{3}(2n + 1) + (2 − 3(2n + 1)))σ(2n + 1).

These are special cases of results of Melfi [20]; see [19, Th. 2] and [19, Th. 4)]. Substituting in these identities yields the desired result:

4 ∑_{i=1}^{j} (σ(i) − 4σ(i/2))σ(2j + 1 − 2i) = jσ(2j + 1).

For more proofs of Legendre’s result, see [7, p. 72] and [17, 19, 24].

Theorem 28. Let p(n) denote the number of partitions of n. Then the following statements are equivalent:

p(5m + 4) ≡ 0 (mod 5);  (63)
∑_{i≥1} σ(i)σ(5m + 1 − i) ≡ 0 (mod 5).  (64)

Proof. The key idea is to consider (58) mod 5, with n = 5m + 1. The left-hand side is the convolution sum in (64). As for the right-hand side of (58), note that for i = 0, 1, 2 (mod 5), the product

(\frac{i(3i − 1)}{2})(n − \frac{i(3i − 1)}{2}) ≡ 0 (mod 5).

So the only terms that survive in the product are when i = 3, 4 when i(3i−1)/2 ≡ 2 (mod 5) and the product is of the form 2(5m−1) ≡ −2 (mod 5). Thus, we see that when n = 5m+1, the sum on the right-hand side of (58) is over terms of the form

(∗)p(5m + 1 − k), with k ≡ 2 (mod 5).

To be precise, we change the index by replacing i = 5j − 1 and i = 5j − 2, and write (58) (mod 5) as

∑_{i≥1} σ(5m + 1 − i)σ(i) = ∑_{j=−∞}^{∞}(−1)^{j}2(p(5m + 1 − \frac{(5j − 1)(15j − 4)}{2})+

p(5m + 1 − \frac{(5j − 2)(15j − 7)}{2})) (mod 5). (65)

Replacing m by m + 1, we see that all the terms have p(5k + 4) for some k. If they are all 0 by (63), we immediately obtain (64).

Conversely, we assume (64), and use induction to show that p(5m + 4) ≡ 0 (mod 5). For m = 0, the result is true because p(4) = 5. Suppose it is true for numbers less than m.

Note that at j = 0, (5j − 1)(15j − 4)/2 is 2. Thus, using the right-hand side of (65) with m replaced by m + 1, we can write p(5m + 6 − 2) = p(5m + 4) in terms of p(5k + 4) with k < m. Since the sum is 0 (mod 5) by (64), we obtain (63) by induction.

Next, we give a new proof of one of Ramanujan’s congruences for partitions. This proof uses a result of Jacobi, as well as (58) (which relies on Euler’s pentagonal number theorem). Both these are special cases of Jacobi’s triple product identity.

Proposition 29 (Ramanujan). Let p(n) be the number of partitions of n. Then

p(5m + 4) ≡ 0 (mod 5).

Proof. In view of Theorem 28, it is enough to show (64). We use the following result due to Jacobi [1, p. 500]:

∏_{k=1}^{∞}(1 − q^{k})^{3} = ∑_{k=0}^{∞}(−1)^{k}(2k + 1)q^{\frac{k(k+1)}{2}} .  (66)

Let p_{3}(n) be defined from the generating function

A(q) = ∏_{k=1}^{∞} \frac{1}{(1 − q^{k})^{3}} = ∑_{n=0}^{∞} p_{3}(n)q^{n}.

(The quantity p_{3}(n) is the number of partitions of n where each part can occur in 3 colors.) Then (60) and Proposition 3 (part (iv)) yield

9 ∑_{i≥1} σ(i)σ(n − i) = ∑_{k=0}^{∞}(−1)^{k+1} \frac{k(k + 1)(2k + 1)}{2}(n − \frac{k(k + 1}{2})p_{3}(n − \frac{k(k + 1)}{2}).

Now when n = 5m + 1, consider the summand for k = 0, 1, 2, 3, 4. Clearly, it is 0 (mod 5). Now Theorem 28 implies (64).

We conclude with a theorem for overpartitions on the lines of Theorem 28.

Theorem 30. Let \overline{p}(n) denote the number of partitions of n. Then the following statements are equivalent:

\overline{p}(4m + 3) ≡ 0 (mod 8);  (67)
∑_{i≥1} d_{D}(i)d_{D}(4m − i) ≡ 0 (mod 4).  (68)

Proof. We first show (67) implies (68). We consider (62) when n = 4m. For all i, i^{2} ≡ 0 or 1 (mod 4), so 4m − i^{2} ≡ 0 or 3 (mod 4). When 4m − i^{2} ≡ 0 (mod 4), then i^{2} and 4m − i^{2} are both multiples of 4, so we see that the left-hand side of (62) is divisible by 16. The convolution

∑_{i≥1} d_{D}(i)d_{D}(4m − i)

is divisible by 8, and so by 4. When 4m − i^{2} ≡ 3 (mod 4), then by (67) the right-hand side of (62) is divisible by 8 and again (68) holds.

Conversely, if (68) holds, only the terms when 4m − i^{2} ≡ 3 (mod 4) survive in the sum

∑_{i=1}^{∞}(−1)^{i+1}i^{2}(4m − i^{2})\overline{p}(4m − i^{2})

when we take the sum mod 8. In this case, the sum is over terms of the form

(−1)^{i+1}3\overline{p}(4k + 3)

and (67) follows by induction.

Remark 31. Equation (67) follows from a theorem of Hirschhorn and Sellers [18, Equation (6)]. Thus (68) holds too.

Theorems 28 and 30 illustrate the correspondence between results in the theory of partitions theory and results for divisor functions.

6 Acknowledgments

We thank the referee for many helpful comments. In particular, the referee observed that ψ(q)^{p} = ψ(q^{p}) (mod p), used this to prove (56), and urged us to supply a proof. This led to Remark 22. In our original submission, we had stated (56) as a conjecture.

References

[1] G. E. Andrews, R. A. Askey, and R. Roy, Special Functions, Vol. 71 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 1999.

[2] G. E. Andrews and K. Eriksson, Integer Partitions, Cambridge University Press, 2004.

[3] G. E. Andrews, S. K. Jha, and J. López-Bonilla, Sums of squares, triangular numbers, and divisor sums, J. Integer Sequences 26 (2023), Article 23.2.5.

[4] H. S Bal and G. Bhatnagar, The partition-frequency enumeration matrix, Ramanujan J. 59 (2022), 51–86.

[5] B. C. Berndt, Ramanujan’s Notebooks. Part II, Springer-Verlag, 1989.

[6] B. C. Berndt, Ramanujan’s Notebooks. Part IV, Springer-Verlag, 1994.

[7] B. C. Berndt, Number Theory in the Spirit of Ramanujan, Vol. 34 of Student Mathematical Library, American Mathematical Society, 2006.

[8] N. C. Bonciocat, Congruences for the convolution of divisor sum function, Bull. Greek Math. Soc. 47 (2003), 19–29.

[9] A. D. Christopher, Euler-type recurrence relation for arbitrary arithmetical function, Integers 19 (2019), Paper No. A62.

[10] S. Corteel and J. Lovejoy, Overpartitions, Trans. Amer. Math. Soc. 356 (2004), 1623– 1635.

[11] L. Euler, Observatio de summis divisorum, Novi Commentarii Academiae scientiarum Imperialis Petropolitanae 5 (1760), 59–74. Reprinted in Euler Archive—All Works E243, English translation (by Jordan Bell) available at https://arxiv.org/abs/math/

0411587v3.

[12] N. J. Fine, Basic Hypergeometric Series and Applications, Vol. 27 of Mathematical Surveys and Monographs, American Mathematical Society, 1988.

[13] L. H. Gallardo, On Bonciocat’s congruences involving the sum of divisors function, Bull. Greek Math. Soc. 53 (2007), 69–70.

[14] J. W. L. Glaisher, On certain sums of products of quantities depending upon the divisors of a number., Messenger of Mathematics 15 (1886), 1–20.

[15] J. W. L. Glaisher, Expressions for the sum of the cubes of the divisors of a number in terms of partitions of inferior numbers., Messenger of Mathematics 21 (1891), 47–48.

[16] H. W. Gould, Coefficient identities for powers of Taylor and Dirichlet series, Amer. Math. Monthly 81 (1974), 3–14.

[17] H. Hahn, Convolution sums of some functions on divisors, Rocky Mountain J. Math. 37(5) (2007), 1593–1622.

[18] M. D. Hirschhorn and J. A. Sellers, Arithmetic relations for overpartitions, J. Combin. Math. Combin. Comput. 53 (2005), 65–73.

[19] J. G. Huard, Z. M. Ou, B. K. Spearman, and K. S. Williams, Elementary evaluation of certain convolution sums involving divisor functions. In Number Theory for the Millennium, II (Urbana, IL, 2000), pp. 229–274. A. K. Peters, 2002.

[20] G. Melfi, On some modular identities. In Number Theory (Eger, 1996), pp. 371–382. De Gruyter, 1998.

[21] M. Merca, New connections between functions from additive and multiplicative number theory, Mediterr. J. Math. 15 (2018), Paper No. 36.

[22] M. Merca, Congruence identities involving sums of odd divisors function, Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 22 (2021), 119–125.

[23] M. Merca, Overpartitions and functions from multiplicative number theory, Politehn. Univ. Bucharest Sci. Bull. Ser. A Appl. Math. Phys. 83 (2021), 97–106.

[24] K. Ono, S. Robins, and P. T. Wahl, On the representation of integers as sums of triangular numbers, Aequationes Math. 50 (1995), 73–94.

[25] N. J. A. Sloane, The on-line encyclopedia of integer sequences, https://oeis.org, 2023.

[26] B. A. Venkov, Elementary Number Theory, Translated from the Russian and edited by Helen Alderson, Wolters-Noordhoff Publishing, 1970.

[27] H. S. Wilf, Generatingfunctionology, A K Peters, Ltd., third edition, 2006.

[28] K. S. Williams, Number Theory in the Spirit of Liouville, Vol. 76 of London Mathematical Society Student Texts, Cambridge University Press, 2011.

2020 Mathematics Subject Classification: Primary 11P83; Secondary 11A25. Keywords: sum of divisors function, partition, overpartition.

(Concerned with sequences \underline{A000009}, \underline{A000203}, \underline{A000385}, \underline{A000593}, \underline{A001158}, \underline{A002129}, \underline{A002131}, \underline{A007331}, \underline{A008438}, \underline{A008439}, \underline{A015128}, \underline{A035363}, \underline{A138503}, \underline{A146076}, \underline{A226253}, and \underline{A350485}.)

Received August 11 2023; revised versions received August 20 2023; December 14 2023; January 13 2024. Published in Journal of Integer Sequences, January 14 2024.

Return to Journal of Integer Sequences home page.