\documentclass[12pt,reqno]{article}

\usepackage{amssymb}
\usepackage
[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{amsthm,amssymb,color,epsf}


\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}


\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo130.eps}
\end{center}

\begin{center}
%\epsfxsize=4in
%\leavevmode\epsffile{logo0019.eps}
\vskip 1cm
{\LARGE\bf On Partition Functions and Divisor Sums}
\vskip 1cm
\large Neville Robbins\\
\vskip 0.5cm
Mathematics Department\\
San Francisco State University\\
San Francisco, CA 94132\\
\vskip 0.5cm
{ \href{mailto:robbins@math.sfsu.edu}{\tt robbins@math.sfsu.edu} }
\vskip 1cm
\bf {Abstract}
\end{center}
{\em  
 Let $n, r$ be natural numbers, with $r \geq 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$.
}

%\vspace*{+.1in}

\vspace{.1in}
\noindent
\section{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.

\vspace{.2in}
\noindent
\section{Preliminaries}

Let $A\subset N$, the
set of all natural numbers.\,  Let $n, \, m, \, r \in N$ with\\ $r\geq 2,
\, m\geq 2, \, m$ squarefree.  Let $x\in C, \, |x|<1$.

\vspace{.2in}
\noindent
\textbf{\underline{Definition 1}}\hspace{.2in}Let $p_{A}(n)$ denote the number
of partitions of $n$ into parts that belong to $A$.

\vspace{.2in}
\noindent
\textbf{\underline{Definition 2}}\hspace{.2in}Let $\sigma_{A}(n)$
denote the sum of the divisors, $d$ , of $n$ such that $d\in A$.

\vspace{.2in}
\noindent
\textbf{\underline{Definition 3}}\hspace{.2in}Let $p(n)$ denote the number of
partitions of $n$.

\vspace{.2in}
\noindent
\textbf{\underline{Definition 4}}\hspace{.2in}Let $q(n)$ denote the number of
partitions of $n$ into distinct parts (or into odd parts).

\vspace{.2in}
\noindent
\textbf{\underline{Definition 5}}\hspace{.2in}Let $q_0(n)$ denote the
number of
partitions of $n$ into distinct odd parts (the number of
self-conjugate partitions of $n$).

\vspace{.2in}
\noindent
\textbf{\underline{Definition 6}}\hspace{.2in}Let $b_r(n)$ denote the number
of \emph{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).

\vspace{.1in}
\noindent
\textbf{\underline{Remark:}}\hspace{.2in}Note that $b_2(n) = q(n)$.

\vspace{.2in}
\noindent
\textbf{\underline{Definition 7}}\hspace{.2in}Let $f_m(n)$ denote the number
of partitions of $n$ such that all parts are coprime to $m$.

\vspace{.2in}
\noindent
\textbf{\underline{Definition 8}}\hspace{.2in}Let $\sigma_r(n)$
denote the sum of the divisors, $d$ , of $n$ such that $d$ does not
divide $r$.

\vspace{.2in}
\noindent
\textbf{\underline{Definition 9}}\hspace{.2in}Let  $\sigma_m^{*}(n)$
denote the sum of the divisors, $d$ , of $n$ such that $d$ is coprime
to $m$.

\vspace{.2in}
\noindent
\textbf{\underline{Definition 10}}\hspace{.2in}Let  $\phi(n)$ denote
Euler's totient function.

\vspace{.1in}
\noindent
\textbf{\underline{Remark:}}\hspace{.2in}If $p$ is prime, then $f_p(n) =
b_p(n)$ and $\sigma_p^{*}(n) = \sigma_p(n)$.

\begin{equation}
\sum_{n=0}^{\infty}q(n)x^n = \prod_{n=1}^{\infty}(1 + x^n)
\end{equation}

\vspace{.1in}
\noindent
\textbf{\underline{Proposition 1}}\hspace{.2in}Let $f: A \rightarrow N$ be a
function such that

\[ F_A(x) = \prod_{n\in A}(1 - x^n)^{-f(n)/n} = 1 +
\sum_{n=1}^{\infty}p_{A,f}(n)x^n  \]

\noindent
and

\[ G_A(x) = \sum_{n\in A}\frac{f(n)}{n}x^n  \]

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

\[  f_A(k) = \sum\{f(d): d|k, \, d\in A\} \quad . \]
\noindent
Then

\[ np_{A,f}(n) = \sum_{k=1}^{n}p_{A,f}(n-k)f_A(k) \quad . \]

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

\[np(n) = \sum_{k=1}^{n}p(n-k)\sigma(k) \quad . \]

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

\begin{equation}
 nq(n) = \sum_{k=1}^{n}q(n-k)\sigma_2(k) \quad .
\end{equation}

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

\section{The Main Results}

\vspace{.1in}
\noindent
\textbf{\underline{Theorem 1}}

\begin{equation}
 nb_r(n) = \sum_{k=1}^{n}b_r(n-k)\sigma_r(k)
\end{equation}

\begin{equation}
 nf_m(n) = \sum_{k=1}^{n}f_m(n-k)\sigma_m^{*}(k)
\end{equation}


\vspace{.1in}
\noindent
\textbf{\underline{Proof:}}\hspace{.2in} 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\in N : (m,n) = 1\}$,
then (4) follows.  \quad \rule{1ex}{1ex}

\vspace{.2in}
\noindent
Next, we present a theorem regarding odd divisors of $n$.

\vspace{.1in}
\noindent
\textbf{\underline{Theorem 2}}\hspace{.2in}   Let $f:N \rightarrow N$ be a
multiplicative function.  Let  $n = 2^{k}m$, where $k\geq 0$ and $m$ is
odd. Then

\begin{equation}
\sum_{d|n}(-1)^{d-1}f(\frac{n}{d}) = \{f(2^k) -
\sum_{j=0}^{k-1}f(2^j)\}\sum_{d|n \,, \, 2\not\,|d}f(d)  \quad .
\end{equation}


\noindent
\textbf{\underline{Proof:}}\hspace{.2in}If $d|n$, then by hypothesis, $d =
2^{i}r$ where $0\leq i\leq k, \,r|m$.  Now

\[  \sum_{d|n}(-1)^{d-1}f(\frac{n}{d}) =
 \sum_{d|n \,,\, 2\not\,|d}f(\frac{n}{d})  -
 \sum_{2|d|n}f(\frac{n}{d})    \]

 \[= \sum_{r|m}f(2^{k}m/r) - \sum_{r|m}\sum_{i=1}^{k}f(2^{k-i}m/r) =
 f(2^k)\sum_{r|m}f(r) - \sum_{i=1}^{k}f(2^{k-i})\sum_{r|m}f(r) \]

 \[= \{f(2^k) - \sum_{i=1}^{k}f(2^{k-i})\}\sum_{r|m}f(r) =
  \{f(2^k) - \sum_{j=0}^{k-1}f(2^j)\}\sum_{d|n \,, \, 2\not\,|d}f(d)
  \quad .  \quad
  \rule{1ex}{1ex} \]


 \vspace{.1in}
 \noindent
 \textbf{\underline{Corollary 1}}

 \begin{equation}
 \sum_{d|n}(-1)^{d-1}\frac{n}{d} = \sum_{d|n \,, \, 2\not\,|d}d
 \end{equation}

 \begin{equation}
 \sum_{d|n}(-1)^{d-1}\phi(\frac{n}{d}) = 0
 \end{equation}

\vspace{.1in}
\noindent
\textbf{\underline{Proof:}}\hspace{.2in}If $f$ is multiplicative and $n =
2^{k}m$, where $k\geq 0$ and $m$ is odd,
let

\[ g(f,k) = \{f(2^k) - \sum_{j=0}^{k-1}f(2^j)\}  \]

\noindent
Theorem 2 may be written as:

\begin{equation}
\sum_{d|n}(-1)^{d-1}f(\frac{n}{d}) = g(f,k)\sum_{d|n\,, \,
2\not\,|d}f(d)
\end{equation}

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


\begin{equation}
 g(n,k) = 2^k - \sum_{j=0}^{k-1}2^j = 1
\end{equation}

\begin{equation}
 g(\phi(n), k) = \phi(2^k) - \sum_{j=0}^{k-1}\phi(2^j) = 0
 \end{equation}

\noindent
We see that (6) follows from (8) and (9), and (7) follows from (8)
and (10). \quad \rule{1ex}{1ex}

\vskip .2in
\noindent
\textbf{\underline{Theorem 3}}

\[ \sum_{n=1}^{\infty}\sigma_{2}(n)x^n =
\sum_{n=1}^{\infty}\frac{nx^n}{1 + x^n}  \]

\vspace{.1in}
\noindent
\textbf{\underline{First Proof:}}

\[ \sum_{m=1}^{\infty}\frac{mx^m}{1 + x^m}  =
 \sum_{m,k=1}^{\infty}(-1)^{k-1}mx^{km}  \]

\[ = \sum_{n=1}^{\infty}x^{n}(\sum_{d|n}(-1)^{d-1}\frac{n}{d}
= \sum_{n=1}^{\infty}\sigma_{2}(n)x^n \]

\noindent
by (6) . \quad \rule{1ex}{1ex}

\vspace{.1in}
\noindent
\textbf{\underline{Second Proof:}}\hspace{.2in} (2) implies

\[ \sum_{n=0}^{\infty}(\sum_{k=0}^{n}q(n-k)\sigma_2(k))x^n =
\sum_{n=0}^{\infty}nq(n)x^n  \]

\noindent
so that

\begin{equation}
 (\sum_{n=0}^{\infty}q(n)x^n)(\sum_{n=0}^{\infty}\sigma_{2}(n)x^n) =
 \sum_{n=0}^{\infty}nq(n)x^n
\end{equation}

\noindent
Now (1) implies

\[ \frac{d}{dx}(\sum_{n=0}^{\infty}q(n)x^n) =
\frac{d}{dx}(\prod_{n=1}^{\infty}(1 + x^n))  \]

\noindent
that is,

\[
\sum_{n=1}^{\infty}nq(n)x^{n-1} =
\sum_{n=1}^{\infty}nx^{n-1}\prod_{m\neq n}(1 + x^m)
\]

\noindent
hence

\[ \sum_{n=0}^{\infty}nq(n)x^n = \sum_{n=0}^{\infty}\frac{nx^n}{1 +
x^n}\prod_{n=1}^{\infty}( 1 + x^n )  \]

\[ = \sum_{n=0}^{\infty}\frac{nx^n}{1+x^n}\sum_{n=0}^{\infty}q(n)x^n
\]

\noindent
 by (1). The conclusion now follows from (11) . \quad \rule{1ex}{1ex}

\vspace{.1in}
\noindent
\textbf{\underline{Remarks:}}\hspace{.2in}Theorem 3 may be compared to the
well-known Lambert series identity:

\[ \sum_{n=1}^{\infty}\sigma(n)x^n =
\sum_{n=1}^{\infty}\frac{nx^n}{1 - x^n}  \]

\noindent
In [2], Theorem 2, part (b), we obtained an explicit formula for
$\sigma_2(n)$ in terms of $q(n)$ and $q_0(n)$, namely:

\[ \sigma_{2}(n) = \sum_{k=1}^{n}(-1)^{k-1}kq_0(k)q(n-k)  \]

\vspace{.3in}
\noindent
\centerline{\textbf{\underline{\large{References}}}}

\vskip .4in
\noindent
1.\,\,\, Tom M. Apostol, \emph{Introduction to Analytic
Number Theory}, Springer-Verlag, 1976.

\vspace{.1in}
\noindent
2.\,\,\, N. Robbins, Some identities connecting partition
functions to other number theoretic functions, \emph{Rocky
Mountain J. Math} \,\, \textbf{29} \,\,(1999),\, 335--345.

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: \ \ 11P81

\noindent \emph{Keywords:  partitions, divisor sums, Lambert series
}

\bigskip

%\noindent (Concerned with sequences \seqnum{A000045}...)

\vspace*{+.1in}
\noindent
Received March 21, 2002;
revised version received August 20, 2002.
Published in Journal of Integer Sequences August 21, 2002.



\bigskip
\hrule
\bigskip

\noindent 
Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.




\end{document}