User:Virginia-American/Sandbox/divisor convolution

Divisor sum convolutions

The sequence $c_{n}=\sum _{i=0}^{n}a_{i}b_{n-i}$ is called the discrete convolution or the Cauchy product of the sequences a_n and b_n. For integers $e$ and $f$ define the convolution sum $S_{e,f}(n)=\sum _{i=1}^{n-1}\sigma _{e}(i)\sigma _{f}(n-i)$. Note that $S_{e,f}(n)=S_{f,e}(n)$

For odd integers $e<=f,\;\;e+f=2,4,6,8,12$, the sum $S_{e,f}(n)$ can be evaluated in terms of $\sigma _{e+f+1},\sigma _{e+f-1},\cdots ,\sigma _{3},\sigma ,$. Namely:

$\sum _{i=1}^{n-1}\sigma (i)\sigma (n-i)={\frac {5}{12}}\sigma _{3}(n)+\left({\frac {1}{12}}-{\frac {1}{2}}n\right)\sigma (n).$

$\sum _{i=1}^{n-1}\sigma (i)\sigma _{3}(n-i)={\frac {7}{80}}\sigma _{5}(n)+\left({\frac {1}{24}}-{\frac {1}{8}}n\right)\sigma _{3}(n)-{\frac {1}{240}}\sigma (n).$

$\sum _{i=1}^{n-1}\sigma (i)\sigma _{5}(n-i)={\frac {5}{126}}\sigma _{7}(n)+\left({\frac {1}{24}}-{\frac {1}{12}}n\right)\sigma _{5}(n)+{\frac {1}{504}}\sigma (n).$

$\sum _{i=1}^{n-1}\sigma _{3}(i)\sigma _{3}(n-i)={\frac {1}{120}}\sigma _{7}(n)-{\frac {1}{120}}\sigma _{3}(n).$

$\sum _{i=1}^{n-1}\sigma (i)\sigma _{7}(n-i)={\frac {11}{480}}\sigma _{9}(n)+\left({\frac {1}{24}}-{\frac {1}{16}}n\right)\sigma _{7}(n)-{\frac {1}{480}}\sigma (n).$

$\sum _{i=1}^{n-1}\sigma _{3}(i)\sigma _{5}(n-i)={\frac {11}{5040}}\sigma _{9}(n)-{\frac {1}{240}}\sigma _{5}(n)+{\frac {1}{504}}\sigma _{3}(n).$

$\sum _{i=1}^{n-1}\sigma (i)\sigma _{11}(n-i)={\frac {691}{65520}}\sigma _{13}(n)+\left({\frac {1}{24}}-{\frac {1}{24}}n\right)\sigma _{11}(n)-{\frac {691}{65520}}\sigma (n).$

$\sum _{i=1}^{n-1}\sigma _{3}(i)\sigma _{9}(n-i)={\frac {1}{2640}}\sigma _{13}(n)-{\frac {1}{240}}\sigma _{9}(n)+{\frac {1}{264}}\sigma _{3}(n).$

$\sum _{i=1}^{n-1}\sigma _{5}(i)\sigma _{7}(n-i)={\frac {1}{10080}}\sigma _{13}(n)+{\frac {1}{504}}\sigma _{7}(n)-{\frac {1}{480}}\sigma _{5}(n).$

These are the only $S_{e,f}(n)$ that can be evaluated in terms of divisor sums and polynomials in $n$. For odd integers $e<=f,\;\;e+f=10,14,16,18,20,24$, evaluating the sum requires the Ramanujam function $\tau (n)$. For example:

$\sum _{i=1}^{n-1}\sigma _{5}(i)\sigma _{5}(n-i)={\frac {65}{174132}}\sigma _{11}(n)+{\frac {1}{252}}\sigma _{5}(n)-{\frac {3}{691}}\tau (n).$

There are many other similar formulas. For example:

$\sum _{\begin{aligned}r+s+t=n\\r,\;s,\;t>0\end{aligned}}\sigma (r)\sigma (s)\sigma (t)={\frac {7}{192}}\sigma _{5}(n)+\left({\frac {5}{96}}-{\frac {5}{12}}n\right)\sigma _{3}(n)-\left({\frac {1}{192}}-{\frac {1}{16}}n+{\frac {1}{8}}n^{2}\right)\sigma (n).$

See Eisenstein series for a discussion of the series and functional identities involved in these formulas.

$\sigma _{3}(n)={\frac {1}{5}}\left\{6n\sigma _{1}(n)-\sigma _{1}(n)+12\sum _{0<k<n}\sigma _{1}(k)\sigma _{1}(n-k)\right\}.$    

$\sigma _{5}(n)={\frac {1}{21}}\left\{10(3n-1)\sigma _{3}(n)+\sigma _{1}(n)+240\sum _{0<k<n}\sigma _{1}(k)\sigma _{3}(n-k)\right\}.$    

${\begin{aligned}\sigma _{7}(n)&={\frac {1}{20}}\left\{21(2n-1)\sigma _{5}(n)-\sigma _{1}(n)+504\sum _{0<k<n}\sigma _{1}(k)\sigma _{5}(n-k)\right\}\\&=\sigma _{3}(n)+120\sum _{0<k<n}\sigma _{3}(k)\sigma _{3}(n-k).\end{aligned}}$    

${\begin{aligned}\sigma _{9}(n)&={\frac {1}{11}}\left\{10(3n-2)\sigma _{7}(n)+\sigma _{1}(n)+480\sum _{0<k<n}\sigma _{1}(k)\sigma _{7}(n-k)\right\}\\&={\frac {1}{11}}\left\{21\sigma _{5}(n)-10\sigma _{3}(n)+5040\sum _{0<k<n}\sigma _{3}(k)\sigma _{5}(n-k)\right\}.\end{aligned}}$    

$\tau (n)={\frac {65}{756}}\sigma _{11}(n)+{\frac {691}{756}}\sigma _{5}(n)-{\frac {691}{3}}\sum _{0<k<n}\sigma _{5}(k)\sigma _{5}(n-k),$     where τ(n) is Ramanujan's function.    

Since σ_k(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences for the functions. See Ramanujan tau function for some examples.

Extend the domain of the partition function by setting p(0) = 1.

$p(n)={\frac {1}{n}}\sum _{1\leq k\leq n}\sigma (k)p(n-k).$       This recurrence can be used to compute p(n).