I am looking for the best upper bound on $$\sum_{\substack{d | n\\ d \geq N}} 1.$$

I know that $$ d(n) = \sum_{\substack{d | n}} 1 \leq e^{O(\frac{\log n}{\log \log n})}. $$

For my application, I need something like $$\sum_{\substack{d | n\\ d \geq N}} 1 \leq \frac{o(n^{\epsilon})}{\log N} \quad \forall \epsilon > 0. $$

A reference where the bound can be found or a simple proof would be appreciated.


EDIT: Johan Andersson has pointed out that the third display follows from the second. (Thanks.) I am still interested to learn what the best known bound is.

  • $\begingroup$ You might be able to use the correspondence (d, n/d) to some effect. Thus your quantity is close to number of divisors below n/N. It is now a matter of how much n looks like a small multiple of a factorial, assuming N is close to n. I don't know, but imagine, that each interval (n^(j/(2^k)), n^((j+1)/(2^k)) has roughly 1/2^k divisors of n, for k small. Gerhard "Maybe You Are Proving This?" Paseman, 2013.06.10 $\endgroup$ – Gerhard Paseman Jun 10 '13 at 15:53
  • 1
    $\begingroup$ The last sum is clearly less than $d(n)$ since the sum is over a subset of the divisors. Also unless $N>n$ in which case the sum is empty and the inequality trivially true, $1/\log n \leq 1/\log N$. Thus it is sufficient to have that $d(n) \leq o(n^\epsilon)/\log n$ but that follows from the line you have above where you estimate $d(n)$ right? $\endgroup$ – Johan Andersson Jun 10 '13 at 15:57
  • $\begingroup$ Actually, instead of dividing the interval (0,n) into 2^k many pieces of the same size, I need to convert (1,n) to a logarithmic scale and do the equidivision over (0,log n). The divisors will "look" more uniformly distributed that way. I imagine, but do not know, that Erdos and Kac may have results applicable to your situation. Gerhard "But Read Their Results Regardless" Paseman, 2013.06.10 $\endgroup$ – Gerhard Paseman Jun 10 '13 at 16:02
  • $\begingroup$ The best bounds known by “robust” methods are something like $d(n)<<_{\epsilon} n^{1/4+\epsilon}$ (Bombieri), if you want to have a constant for your estimate with $\exp (O(\log(n)/(\log(\log(n)))$. $\endgroup$ – Dietrich Burde Jun 10 '13 at 17:46
  • $\begingroup$ And the question has been discussed already here: math.stackexchange.com/questions/63687/…. $\endgroup$ – Dietrich Burde Jun 10 '13 at 17:49

This is not an answer to what the best known upper bound is, but rather a comment that the (known) average distribution of divisors indicates you might not expect to do any better than the bounds on the divisor function itself. Tennenbaum's "Introduction to Analytic and Probabilistic Number Theory", $\S$ 6.2 p. 207 says

For each integer $n$, let us define a random variable $D_n$ taking the values $\log d/\log n$, as $d$ runs through the the set of the $\tau(n)$ divisors of $n$, with uniform probability $1/\tau(n)$. The distribution function $F_n$ of $D_n$ is then defined by $$ > F_n(u):=\text{Prob}(D_n\le > u)=\frac{1}{\tau(n)}\sum_{d|n,d\le > n^u}1\quad (0\le u\le 1). $$ It is clear that the sequence $\{F_n\}_{n=1}^\infty$ does not converge pointwise on $[0,1]$. However, we shall see the sequence of Cesaro means $$ > G_N(u):=\frac{1}{N}\sum_{n\le N}F_n(u) > $$ is uniformly convergent on $[0,1]$. Remarkably, the limit is the distribution function of a probability law well known to specialists: the arcsine law, with density $1/(\pi\sqrt{u(1-u)})$. Large and small values have high probability: if $D$ is a random variable with this distribution law, we have $$ > \text{Prob}(D<0.01\text{ or > }D>0.99)\approx0.128 $$ This indicates that, on average, an integer has many small (and correspondingly many large) divisors.

Update: One thing we learn is that the relevant parameter is not $N$, but $u:=\log_n(N)$.

| cite | improve this answer | |

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.