Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

Any pointers, comments appreciated.

share|improve this question
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

3 Answers 3

up vote 3 down vote accepted

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$.

share|improve this answer

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.

share|improve this answer

Here is an experimental answer I obtained, via Mathematica. It seems something quite subtle may be going on--or maybe not.

The two functions f I am interested in were given in the question.

The first function $v=O(n/\log n)$ was tested in Mathematica as follows, e.g.,

$g[c_,d_,n_]:= c*n/Log[n]^d;$


$L2=Accumulate[L1]; DiscretePlot[L2[k]/(k*Log[k]),{k,2,10^4}]$

Note that DivisorSigma[0,n] is the function that sums 0th powers of divisors of n. I am comparing the accumulated truncated divisor sum to the well known approximation in the first equation for non-truncated divisor sums.

The ratio, as expected, was essentially 1 with very little variation, for all sorts of values of $[c,d] \in [0,1]\times [0,1]$, some of which were as follows: $$[0.5,1],[0.05,1], [0.5, 0.5], [0.5, 0.05]$$

The surprising results were obtained for the second function $v=O(n^{\alpha})$.

$h[a_,b_,n_]:= a*n^b;$


$L2=Accumulate[L1]; DiscretePlot[L2[k]/(k*Log[k]),{k,2,10^4}]$

In this case, very unexpectedly, the ratio in the plot was sometimes tending to values way below 1. I again tested for values of $[a,b]$, some of which were as follows:

$$[1,0.75],[1,0.5], [1,0.25], [1, 0.05],[0.5,1],[0.05,1],[0.25,0.5],[0.25,0.75],[0.05,0.75]$$

Again, if $b=1$ which is the exponent of $n$ in $v$ is 1, the ratio is trivially 1.

However, for example, $b=0.75$, with $a=0.05$ or larger still gives the ratio 1, all accross the plot for $k=2,\ldots,10^4$.

As for $b=0.5$ it gives 1 for $a=1$ but not for $a=0.25$ where it seems to tend to 0.95 but maybe it will shoot back up to 1 for extremely large values of $n$ which I can't test.

The same effect is more pronounced, for $b=0.25,$ where even $a=1$ can't stop the plot from going below 0.8 and for $b=0.05$ where it goes below 0.2 for $a=1$ and below 0.1 for $a=0.5$

I think that all this may be just finite effects and the answer for both truncation functions $v$ is that the sum of $\min [d(k),v(n)]$ over $1\leq k\leq n$ is $O(n \log n)$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.