Let $d(n)$ be the number of divisors function, i.e., $d(n)=\sum_{k\mid 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 $\varepsilon,$ we have $d(n) < n^{\varepsilon}$ for $n$ large enough.

Any pointers, comments appreciated.

  • 1
    $\begingroup$ 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$. $\endgroup$
    – GH from MO
    Apr 3 '12 at 6:52
  • $\begingroup$ @GH: I am sorry, I meant to put in min, so Large values of d(n) get truncated. $\endgroup$
    – kodlu
    Apr 3 '12 at 7:00
  • $\begingroup$ 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? $\endgroup$
    – Woett
    Apr 3 '12 at 17:49
  • $\begingroup$ @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$? $\endgroup$
    – kodlu
    Apr 3 '12 at 23:47
  • $\begingroup$ 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. $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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