3
$\begingroup$

I've seen a few other threads on here, namely this and this, which mention and discuss the Divisor Summatory Function $D(x)=\sum_{n=1}^x\sigma_0(n)$ for parameters other than $x$. But neither quite fit what I'm looking for: in the first link (and the wikipedia page for $D(x)$), it is noted that $$D(x)=\sum_{k=1}^x\bigg\lfloor\frac{x}{k}\bigg\rfloor=2\sum_{k=1}^u\bigg\lfloor\frac{x}{k}\bigg\rfloor-u^2, u=\lfloor\sqrt x\rfloor$$ Which can compute $D(x)$ in $\mathcal{O}(\sqrt x)$ time. Now suppose I define $D'(x) = \sum_{n=1}^x\sigma_0(kn)$ for some integer $k$. I need to compute this for different values of $k$ in far faster than $\mathcal{O}(x)$ time, but I don't think that formula applies any longer and I can't seem to find or derive anything similar. Any ideas?

EDIT 1: At this rate, I've started moving on from that above expression in favor of fiddling around with the prime powers. If $k$ and $n$ are relatively prime, then clearly $\sigma_0(kn)=\sigma_0(k)\sigma_0(n)$. Suppose $n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$. I've noticed that if $k=p_i$ is prime, \begin{equation} \begin{split} \sigma_0(kn) & = (a_1+1)(a_2+1)...((a_i+1)+1)...(a_n+1) \\ & = (a_1+1)...(a_{i-1}+1)(a_{i+1}+1)...(a_n+1)+\sigma_0(n) \\ & = \frac{\sigma_0(n)}{p_i^{a_i}}+\sigma_0(n) \\ & = \frac{p_i^{a_i}+1}{p_i^{a_i}}\sigma_0(n) \end{split} \end{equation}

Similarly, if $k=p_i^q$ is a prime power then $\sigma_0(kn)=(p_i^{a_i}+q)p_i^{-a_i}\sigma_0(n)$. The only case I have not put in some terms of $\sigma_0(n)$ are composite factors of $x$, which for $x$ which aren't absolutely enormous are computable in negligible time. All that's needed now is to somehow simplify to lower the number of terms necessary, probably by combining certain cases when $k$ relatively prime to $x$ and/or a prime power somehow. It is here I once again hit a wall.

$\endgroup$
6
  • $\begingroup$ Why would you need it, and for what $k$ ? (do you need it for every $k \le x/K$ ? Is $K$ small ?) $\endgroup$
    – reuns
    Jul 11, 2017 at 1:36
  • $\begingroup$ If you need it for every $k$, then compute $\sigma_0(n)$ for $n \le x$ $\endgroup$
    – reuns
    Jul 11, 2017 at 1:40
  • $\begingroup$ I need it for any $k$ really, just curious about an arbitrary $k$. But I do need it for $x$ as large as $10^{12}$, which makes a brute up to $x$ both impractical and unsatisfying. $\endgroup$
    – Vedvart1
    Jul 11, 2017 at 1:43
  • $\begingroup$ Computing $\sigma_0(n)$ for $n \le x$ takes $x \log x$ operations, this is satisfying when you need the value for every $n \le x$. $\endgroup$
    – reuns
    Jul 11, 2017 at 1:44
  • $\begingroup$ Also why do you need it, really ? $\endgroup$
    – reuns
    Jul 11, 2017 at 1:46

1 Answer 1

0
+50
$\begingroup$

Let us use $\tau(n):=\sigma_0(n)$. For given $k$, the function $n\mapsto \tau(kn)$ is not multiplicative in general. But, if it is possible to write down Dirichlet series of this function, then it will give us a useful formula for $\sum_{n\leq x} \tau(kn)$. i.e. We aim for finding $F(s)$ in the expression: $$ \sum_{n=1}^{\infty} \frac{\tau(kn)}{n^s} = F(s) \zeta(s)^2. \ \ \ (1) $$

A similar treatment has been done with the Dirichlet series $\sum_{n=1}^{\infty}\frac1{\tau(kn)n^s}$ in II.6, page 209 in Tenenbaum's Introduction to Analytic and Probabilistic Number Theory. A link to Google books is here.

For any prime $p$ and an integer $n$, denote by $\nu_p(n)$ the maximal nonnegative integer $a$ with $p^a |n$. (In such case, we write $p^a ||n$. ) Then $$ \tau(kn)=\prod_p (\nu_p(k)+\nu_p(n)+1) $$ where the product runs over all primes. Then we have $$\begin{align} \sum_{n=1}^{\infty} \frac{\tau(kn)}{n^s}&= \prod_p \left( \sum_{v=0}^{\infty} \frac{\nu_p(k)+v+1}{p^{vs}}\right)\\ &=\prod_{p^a||k }\left(\sum_{v=0}^{\infty}\frac{a+v+1}{p^{vs}}\right)\prod_{p\nmid k}\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right)\\ &=\prod_{p^a||k }\left(\sum_{v=0}^{\infty}\frac{a+v+1}{p^{vs}}\right)\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right)^{-1}\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right) \prod_{p\nmid k}\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right)\\ &=\prod_{p^a||k} \left(\sum_{v=0}^{\infty} \frac{a+v+1}{p^{vs}}\right)\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right)^{-1} \zeta(s)^2\\ &=\prod_{p^a||k} \left(\left( 1-\frac1{p^s}\right)^{-2} +a \left(1-\frac1{p^s}\right)^{-1}\right) \left(1-\frac1{p^s}\right)^2 \zeta(s)^2\\ &=\prod_{p^a||k} \left(1+a\left(1-\frac1{p^s}\right)\right) \zeta(s)^2\\ &=\prod_{p^a||k}\left(1+a -\frac a{p^s}\right) \zeta(s)^2 \end{align} $$ We write $$F(s): = \prod_{p^a||k}\left(1+a -\frac a{p^s}\right):=\sum_{n=1}^{\infty} \frac{f(n)}{n^s}.$$ This is a Dirichlet series with finite number of terms, and we achieved (1).

The formula (1) yields the convolution expression $$ \tau(kn)=\sum_{d|n} f(d)\tau\left(\frac nd\right). $$ Now, we write the summatory function for $\tau(kn)$ as follows: $$ \begin{align} \sum_{n\leq x}\tau(kn) &= \sum_{n\leq x }\sum_{d|n} f(d)\tau\left(\frac nd \right)\\ &=\sum_{d\leq x} f(d) \sum_{m\leq \frac xd} \tau(m) \\ &=\sum_{d\leq x} f(d) D\left( \frac xd \right). \end{align} $$

In the formula $$ \sum_{n\leq x }\tau(kn) = \sum_{d\leq x } f(d) D\left( \frac xd \right), $$ we can compute each $D\left(\frac xd \right)$ in $O(\sqrt x)$ time. Moreover, the sum over $d\leq x$ is in fact a finite sum. We consider the computation times for $f(d)$. This can be done with $O(2^{w(k)})$ multiplications. The number of $d\geq 1$ such that $f(d)\neq 0$ is also $O(2^{w(k)})$. This gives a bound for computation time $O(4^{w(k)} \sqrt x)$.

$\endgroup$
15
  • $\begingroup$ You said so : $h(n) = C \tau(kn)$ is not multiplicative, so how do you get an Euler product for it ? Your factorization of the Dirichlet series into Euler factors is not correct since $h(n) \ne \prod_{p^k \| n} h(p^k)$ $\endgroup$
    – reuns
    Jul 11, 2017 at 2:43
  • $\begingroup$ It is product over all primes. $h(n)$ also contain some $h(p^m)$ for prime $p$ that comes from $p^m |k$. So, not only prime factors from $n$ contribute to $\tau(kn)$, but also the prime factors from $k$ do so. $\endgroup$ Jul 11, 2017 at 2:47
  • $\begingroup$ Your formula $\sum_{n=1}^\infty \tau(nk)n^{-s} =\zeta(s)^2 \prod_{p^a||k}\left(1+a -\frac a{p^s}\right)$ implies that $\frac{\tau(kn)}{\tau(k)}$ is multiplicative, whereas it is not. With $k=2$ and $n,m$ odd : $\frac{\tau(2 (2n)(2m))}{\tau(2)} = \frac{\tau(8)}{\tau(2)}\tau(n)\tau(m) \ne \frac{\tau(4)^2}{\tau(2)^2}\tau(n)\tau(m)$ $\endgroup$
    – reuns
    Jul 11, 2017 at 2:56
  • $\begingroup$ Ah, you are saying about $\tau(kn)/\tau(k)$, not the $\tau(kn)$. I will check your comment more carefully. $\endgroup$ Jul 11, 2017 at 3:10
  • $\begingroup$ In your example, it seems that you are regarding multiplicative as $g(mn)=g(m)g(n)$ for all $m,n \in \mathbb{N}$. Your example is showing that $g(2n 2m) \neq g(2n) g(2m)$. And my definition I meant in my post, is $g(mn)=g(m)g(n)$ for all coprime $m, n$. $\endgroup$ Jul 11, 2017 at 3:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .