Question

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.

Answer 1

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

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

Answer 3

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

$L1=Table[Min[DivisorSigma[0,n],g[0.5,1,10^5]],{n,2,10^4}];$

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

$L1=Table[Min[DivisorSigma[0,n],h[1,0.5,10^5]],{n,2,10^4}];$

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