On Partition Functions and Divisor Sums

Neville Robbins

Mathematics Department San Francisco State University San Francisco, CA 94132

                    robbins@math.sfsu.edu

Abstract

Let n, r be natural numbers, with r ≥ 2. We present convolution-type formulas for the number of partitions of n that are (1) not divisible by r; (2) coprime to r. Another result obtained is a formula for the sum of the odd divisors of n.

1 Introduction

We derive several convolution-type identities linking partition functions to divisor sums, thereby extending some prior results. In addition, we obtain a Lambert series-like identity for sums of odd divisors.

2 Preliminaries

Let A ⊂ N, the set of all natural numbers. Let n, m, r ∈ N with r ≥ 2, m ≥ 2, m squarefree. Let x ∈ C, |x| < 1.

\underline{Definition 1} Let p_{A}(n) denote the number of partitions of n into parts that belong to A.

\underline{Definition 2} Let σ_{A}(n) denote the sum of the divisors, d , of n such that d ∈ A.

\underline{Definition 3} Let p(n) denote the number of partitions of n.

\underline{Definition 4} Let q(n) denote the number of partitions of n into distinct parts (or into odd parts).

\underline{Definition 5} Let q_{0}(n) denote the number of partitions of n into distinct odd parts (the number of self-conjugate partitions of n).

\underline{Definition 6} Let b_{r}(n) denote the number of r-regular partitions of n (the number of partitions of n such that no part is a multiple of r or such that no part occurs r or more times).

\underline{Remark:} Note that b_{2}(n) = q(n).

\underline{Definition 7} Let f_{m}(n) denote the number of partitions of n such that all parts are coprime to m.

\underline{Definition 8} Let σ_{r}(n) denote the sum of the divisors, d , of n such that d does not divide r.

\underline{Definition 9} Let σ_{m}^{∗}(n) denote the sum of the divisors, d , of n such that d is coprime to m.

\underline{Definition 10} Let ϕ(n) denote Euler’s totient function.

\underline{Remark:} If p is prime, then f_{p}(n) = b_{p}(n) and σ_{p}^{∗}(n) = σ_{p}(n).

∑_{n=0}^{∞} q(n)x^{n} = ∏_{n=1}^{∞}(1 + x^{n})  (1)

\underline{Proposition 1} Let f : A → N be a function such that

F_{A}(x) = ∏_{n∈A}(1 − x^{n})^{−f(n)/n} = 1 + ∑_{n=1}^{∞} p_{A,f}(n)x^{n}

and

G_{A}(x) = ∑_{n∈A} \frac{f(n)}{n}x^{n}

converge absolutely and represent analytic functions in the unit disc: |x| < 1. Let p_{A,f}(0) = 1 and

f_{A}(k) = ∑{f(d) : d|k, d ∈ A} .

Then

np_{A,f}(n) = ∑_{k=1}^{n} p_{A,f}(n − k)f_{A}(k) .

\underline{Remarks:} Proposition 1 is Theorem 14.8 in [1]. If we let A = N, f(n) = n, then we obtain

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

(See [1, p. 323]). If we let A = N − 2N (the set of odd natural numbers) and f(n) = n, we obtain

nq(n) = ∑_{k=1}^{n} q(n − k)σ_{2}(k) .  (2)

This is given as Theorem 1 in [2], and is a special case of Theorem 1(a) below.

3 The Main Results

\underline{Theorem 1}

nb_{r}(n) = ∑_{k=1}^{n} b_{r}(n − k)σ_{r}(k)  (3)

nf_{m}(n) = ∑_{k=1}^{n} f_{m}(n − k)σ_{m}^{∗}(k)  (4)

\underline{Proof:} We apply Proposition 1 with f(n) = n. If we let A = N − rN (the set of natural numbers not divisible by r) then (3) follows. If we let A = {n ∈ N : (m, n) = 1}, then (4) follows.

Next, we present a theorem regarding odd divisors of n.

\underline{Theorem 2} Let f : N → N be a multiplicative function. Let n = 2^{k}m, where k ≥ 0 and m is odd. Then

∑_{d|n}(−1)^{d−1}f(\frac{n}{d}) = \{f(2^{k}) − ∑_{j=0}^{k−1} f(2^{j})\} ∑_{d|n , 2 |̸d} f(d) .  (5)

\underline{Proof:} If d|n, then by hypothesis, d = 2^{i}r where 0 ≤ i ≤ k, r|m. Now

∑_{d|n}(−1)^{d−1}f(\frac{n}{d}) = ∑_{d|n , 2 |̸d} f(\frac{n}{d}) − ∑_{2|d|n} f(\frac{n}{d})

= ∑_{r|m} f(2^{k}m/r) − ∑_{r|m} ∑_{i=1}^{k} f(2^{k−i}m/r) = f(2^{k}) ∑_{r|m} f(r) − ∑_{i=1}^{k} f(2^{k−i}) ∑_{r|m} f(r)

= {f(2^{k}) − ∑_{i=1}^{k} f(2^{k−i})} ∑_{r|m} f(r) = {f(2^{k}) − ∑_{j=0}^{k−1} f(2^{j})} ∑_{d|n , 2 |̸d} f(d) .

\underline{Corollary 1}

∑_{d|n}(−1)^{d−1} \frac{n}{d} = ∑_{d|n , 2 |̸d} d  (6)

∑_{d|n}(−1)^{d−1}ϕ(\frac{n}{d}) = 0  (7)

\underline{Proof:} If f is multiplicative and n = 2^{k}m, where k ≥ 0 and m is odd, let

g(f, k) = {f(2^{k}) − ∑_{j=0}^{k−1} f(2^{j})}

Theorem 2 may be written as:

∑_{d|n}(−1)^{d−1}f(\frac{n}{d}) = g(f, k) ∑_{d|n , 2 |̸d} f(d)  (8)

Now each of the functions: f(n) = n, f(n) = ϕ(n) is multiplicative, so Theorem 1 applies. Furthermore,

g(n, k) = 2^{k} − ∑_{j=0}^{k−1} 2^{j} = 1  (9)

g(ϕ(n), k) = ϕ(2^{k}) − ∑_{j=0}^{k−1} ϕ(2^{j}) = 0  (10)

We see that (6) follows from (8) and (9), and (7) follows from (8) and (10).

\underline{Theorem 3}

∑_{n=1}^{∞} σ_{2}(n)x^{n} = ∑_{n=1}^{∞} \frac{nx^{n}}{1 + x^{n}}

\underline{First Proof:}

∑_{m=1}^{∞} \frac{mx^{m}}{1 + x^{m}} = ∑_{m,k=1}^{∞}(−1)^{k−1}mx^{km}

= ∑_{n=1}^{∞} x^{n}(∑_{d|n}(−1)^{d−1} \frac{n}{d} = ∑_{n=1}^{∞} σ_{2}(n)x^{n}

by (6) . \underline{Second Proof:} (2) implies

∑_{n=0}^{∞}(∑_{k=0}^{n} q(n − k)σ_{2}(k))x^{n} = ∑_{n=0}^{∞} nq(n)x^{n}

so that

(∑_{n=0}^{∞} q(n)x^{n})(∑_{n=0}^{∞} σ_{2}(n)x^{n}) = ∑_{n=0}^{∞} nq(n)x^{n}  (11)

Now (1) implies

\frac{d}{dx}(∑_{n=0}^{∞} q(n)x^{n}) = \frac{d}{dx}(∏_{n=1}^{∞}(1 + x^{n}))

that is,

∑_{n=1}^{∞} nq(n)x^{n−1} = ∑_{n=1}^{∞} nx^{n−1} ∏_{m≠n}(1 + x^{m})

hence

∑_{n=0}^{∞} nq(n)x^{n} = ∑_{n=0}^{∞} \frac{nx^{n}}{1 + x^{n}} ∏_{n=1}^{∞}(1 + x^{n})

= ∑_{n=0}^{∞} \frac{nx^{n}}{1 + x^{n}} ∑_{n=0}^{∞} q(n)x^{n}

by (1). The conclusion now follows from (11) . \underline{Remarks:} Theorem 3 may be compared to the well-known Lambert series identity:

∑_{n=1}^{∞} σ(n)x^{n} = ∑_{n=1}^{∞} \frac{nx^{n}}{1 − x^{n}}

In [2], Theorem 2, part (b), we obtained an explicit formula for σ_{2}(n) in terms of q(n) and q_{0}(n), namely:

σ_{2}(n) = ∑_{k=1}^{n}(−1)^{k−1}kq_{0}(k)q(n − k)

\underline{References}

1. Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.

2. N. Robbins, Some identities connecting partition functions to other number theoretic functions, Rocky Mountain J. Math 29 (1999), 335–345.

2000 Mathematics Subject Classification: 11P81 Keywords: partitions, divisor sums, Lambert series

Received March 21, 2002; revised version received August 20, 2002. Published in Journal of Integer Sequences August 21, 2002.

Return to Journal of Integer Sequences home page.