A Truncated Divisor Function Sum

Let $d(n)$ be the number of divisors function, i.e., $d(n)=\sum_{k|n} 1$ of the positive integer $n.$ The following estimate is well known $$\sum_{n\leq x} d(n)=x \log x + (2 \gamma -1) x +{\cal O}(\sqrt{x})$$ as well as its variability, e.g., the lim sup of the fraction $$\frac{\log d(n)}{\log n/\log \log n}$$ is $\log 2$ while the lim inf of $d(n)$ is $2,$ achieved whenever $n$ is prime.

I am interested in estimating instead the following sum $$A(x)=\sum_{n\leq x} \min[ d(n), f(x)]$$ for functions of $x$ where $f(x) = c (x / log x)$ or $f(x) = c x^{\alpha}$ for some $\alpha \in (0,1)$ are possible candidates. Intuitively, the sum should not change much, but large infrequent values contribute a lot to the sum, so I am not so sure. The lim-sup mentioned above would seem to imply that d(n) can achieve a value as large as $$n^{c/\log \log n}$$ while I seem to recall that it is also known that for any fixed exponent $\epsilon,$ we have $d(n) < n^{\epsilon}$ for $n$ large enough.

• The difference between the two sums comes from small values of $d(n)$, namely from those less than $f(x)$. Your candidates $f(x)$ make the second sum very simple, namely $xf(x)$. Things become interesting for much smaller $f(x)$ such as a power $\log x$. – GH from MO Apr 3 '12 at 6:52
• @GH: I am sorry, I meant to put in min, so Large values of d(n) get truncated. – kodlu Apr 3 '12 at 7:00
• We definitely have $d(n) = o(n^{\epsilon})$. So $min[d(n), f(x)] = d(n)$ if $f(x) \ge cx^{\alpha}$. Am I missing something? – Woett Apr 3 '12 at 17:49
• @Woett: Thanks, you're right. So $A(x)$ is the same value as the second sum for $x$ large enough. @GH: Are you able to comment some more on the case $f(x)$ a power of $\log x$? – kodlu Apr 3 '12 at 23:47
• Of course I meant $A(x)$ is the same value as the first sum, i.e., is asymptotically $\sum_{n\leq x} d(n)$, for $x$ large enough. – kodlu Apr 3 '12 at 23:56

The key is to count integers with a given number of prime factors: if $\omega(n)=\sum_{p|n}1$ and $\Omega(n)=\sum_{p^a|n,\,a\ge1}1$, then $2^{\omega(n)}\le\tau(n)\le2^{\Omega(n)}$ and there are results that control the number of integers with a given value of $\omega(n)$, or of $\Omega(n)$. The simplest one of them is the Hardy-Ramanujan theorem: there are absolute constants $A$ and $B$ such that

$$\#\{n\le x: \omega(n)=r\}\le\frac{Ax}{\log x}\frac{(\log\log x+B)^{r-1}}{(r-1)!}\tag{*}$$ for all $x\ge3$ and $r\ge1$.

There are also lower bounds for certain ranges of $r$ and $x$ that are harder to obtain (due to Sathe-Selberg, see the chapter "The Selberg-Delange method" in Tenenbaum's book "Introduction to Analytic and Probabilistic Number Theory").

So here is a way to implement (*) in order to bound your sum from above. First, we need a technical trick: Every $n$ can be written in a unique way as $n=ab$, where $a$ is square-free and $b$ is square-full (i.e. $p|n\Rightarrow p^2|n$). Now, we have that

\begin{align}\sum_{n\le x}\min(d(n),M) & \le \sum_{\substack{b\le x\\\ b\,\text{square-full}}} d(b) \sum_{\substack{a\le x/b \\\ a\,\text{square-free}}}\min(d(a),M) \\\ &\le \sum_{\substack{b\le x\\\ b\,\text{square-full}}} d(b) \sum_{a\le x/b}\min(2^{\omega(a)},M)\\\ &=\sum_{\substack{b\le x\\\ b\,\text{square-full}}} d(b) \sum_{r\ge0} \min(2^{r},M)\#\{a\le x/b:\omega(a)=r\} \end{align} So you can insert (*) to control this sum when $b\le\sqrt{x}$. When $b>\sqrt{x}$, apply the trivial bound

$$\sum_{r\ge0} \min(2^{r},M)\#\{a\le x/b:\omega(a)=r\}\le\sum_{a\le x/b}d(a)\ll\frac{x\log(x/b)}{b}$$

and note that $$\sum_{b\le y}d(b)\le\sum_{k^2l^3\le y}d(k^2l^3)\ll\sqrt{y}\log y,$$

so that

$$\sum_{\substack{\sqrt{x} \le b\le x \\\ b\,\text{square-full} }} d(b)\sum_{r\ge0}\min(2^r,M)\#\{a\le x/b:\omega(a)=r\}\ll\sqrt{x}\log^2x,$$

by partial summation.

This method will give you an upper bound of the right order of magnitude for all $M$. For the lower bound, you could use that $d(n)\ge 2^{\omega(n)}$ and insert the Sathe-Selberg result (here you need to assume that $M\le(\log x)^{10}$, which is OK; the case $M\ge (\log x)^{10}$ follows by the case $M=(\log x)^{10}$). This would give you lower bounds of matching order essentially for all $M$. You could even get asymptotics but the error term will be weak.

An instructive remark here is that if $M=x$ (i.e. we have the full divisor sum), then this method suggests that

$$\sum_{n\le x}d(n)\approx \frac{x}{\log x}\sum_{r\ge1}\frac{(2\log\log x)^{r-1}}{(r-1)!}.$$

This sum is dominated by $r\approx2\log\log x$. And indeed, this is the case (the contribution of $r$ different from $2\log\log x$ can be bounded by (*)). So for $M\ge(\log x)^{\log 4}$, then your sum is asymptotic to the full divisor sum. However, when $M\le(\log x)^{\log 4-\epsilon}$, then it starts getting smaller, dominated by $r\approx \log M/\log 2$.

The $n=ab$ trick is very effective. There is a similar trick of writing in a unique way $n=ab$ with $n$ squarefree, $b$ a square and I was wondering whether this could also work here.