I am trying to bound a function that includes $\sum\limits\_{\substack{d < n^{1/3} \\ d \mid n}} 1$.


Is there an upper bound known for this sum, either in general or in terms of $\sum\limits\_{\substack{d \mid n}} 1$? Or in general is there a bound for $\sum\limits\_{\substack{d < n^{1/k} \\ d \mid n}} 1$? Any help is appreciated.


Edit: I am realizing that a lower bound for this sum in terms of $\sum\limits\_{\substack{d \mid n}} 1$ would also be useful if anyone can help with that.



How many divisors of $n$ are below $n^{1/3}$?
One thing you asked for is a lower bound.


Following FusRoDah, I will let $d\_k(n)$ be the number of divisors of $n$ of size less than $n^{1/k}$, and $d(n)$ be the number of divisors of $n$.


Then I claim $$ d\_1(n) \leq d\_3(n) (d\_3(n)+5),$$ giving an explicit lower bound of size roughly $d\_1(n)^{1/2}$.


Proof: First note that $2 d\_2(n) =d\_1(n)$ since, for $d$ a divisor, $n/d$ is also a divisor, so at least half the divisors have size at most $\sqrt{n}$.


Then $d\_2(n)$ is at most the number of divisors of $n$ of size $\leq \sqrt{n}$ that can be written as a product of two divisors of size $< n^{1/3}$ plus the number that cannot be written as a product. We bound both separately.


The number that can be written as a product of two is certainly at most $\frac{d\_3(n) (d\_3(n)+1)}{2}$.


If $d$ cannot be written as a product, then writing it as a product of a sequence of primes and taking the products of initial segments of the sequence, we must skip straight from $\leq d / n^{1/3}$ to $\geq n^{1/3}$, so one of the prime divisors must be at least $n^{2/3}/d \geq n^{1/6}$. Then the product of the remaining prime divisors is $\leq d/ n^{1/6} \leq n^{1/3}$, so is $<n^{1/3}$ unless $d$ has three prime divisors of size exactly $n^{1/6}$ (but there can be exactly one such $d$ and it is easily absorbed). Thus, this one large prime divisor must have size $n^{1/3}$.


The number of such $d$ is then at most $d\_3(n)$ times the number of prime divisors of $n$ of size $\geq n^{1/3}$, which is at most $2$ (since the bound is trivially true when $n$ is the perfect cube of a prime). This gives


$$d\_2(n) \leq \frac{d\_3(n) (d\_3(n)+1)}{2} + 2 d\_3(n) $$ and multiplying by $2$ we get the stated bound.


This lower bound is of roughly the correct shape, since if $n$ is the product of $r$ primes of size about $n^{1/r}$, for $r$ large, then $d\_1(n)=2^r$ while $$d\_3(n) \approx \left( \frac{1}{ (1/3)^{1/3} (2/3)^{2/3} } \right)^r = \left( \frac {27}{4} \right)^{r/3} = (2^r)^{.918 \dots } . $$


So the true optimal bound is indeed lower than $d\_1(n)$ by a power, although possibly a smaller one.


Similar arguments should get polynomial lower bounds for $d\_k(n)$ for all $k$.


