Number of bounded divisors of an integer

99 Views Asked by At

Given integers $n,t$, what is an upper bound for the number of integers dividing $n$ in the interval $\{1,\ldots,t\}$?

When $t=n$ this boils down to the classical divisor bound (https://terrytao.wordpress.com/2008/09/23/the-divisor-bound/) and the tight answer is $\exp(O(\log n / \log\log n))$. On the other hand, when $t <\log n / \log\log n$ the answer can be easily seen to be as high as t - the whole interval.

For the application in mind, I'm interested in the setting $t = poly(\log n)$. The proof for the classical divisor bound does not seem to be applicable in this bounded range variant.

I suspect this problem is well-known, but could not find a reference anywhere (a very similar question was asked here (Number of divisiors of $n$ less than $m$) and on Tao's blog above, but got no replies.)

Thanks in advance!

Gil Cohen

1

There are 1 best solutions below

0
On

In case anyone is interested, I think I found some partial answer to the question I posed above. One can prove that for t = $\log^{c}{n}$, an upper bound for the number of integers dividing $n$ in the interval $\{1,\ldots,t\}$ is $O(t/{c^c})$.

I don't have a direct reference but one can get this result by looking at the the following paper by Chari et al. and references therein.

http://epubs.siam.org.ezproxy.weizmann.ac.il/doi/pdf/10.1137/S0097539793250330