14
$\begingroup$

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.

$\endgroup$
1
  • 13
    $\begingroup$ If one draws $d$ uniformly at random amongst the divisors of $n$, then $\log d$ is the sum of independent random variables (coming from each prime power in the factorisation of $n$), and $\sum_{d<n^{1/3}:d|n} 1 / \sum_{d|n} 1$ is the probability that this sum is less than $\frac{1}{3} \log n$. At this point one can apply one's favorite concentration of measure inequality (e.g., Bennett's inequality) to get an upper bound (the best bound to use depends on the regime of parameters such as $n$ or $\sum_{d|n} 1$ that you are most interested in). $\endgroup$
    – Terry Tao
    Aug 5, 2021 at 14:41

2 Answers 2

11
$\begingroup$

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

$\endgroup$
0
6
$\begingroup$

Let me define $d(n)=\sum_{d|n} 1$ and $d_3(n)=\sum_{d|n, d<n^{1/3}} 1$. I have plotted $d_3(n)$ vs. $d(n)$ for $n<500000$, and I got the resulting graph:

enter image description here

It seems that we have the bounds $d(n)/5 \leq d_3(n) \leq d(n)/2$ and that they may be attained infinitely often. However, this is only numerical evidence, not a full answer.

$\endgroup$
2
  • 7
    $\begingroup$ $d_3(n)\leq d(n)/2$ is indeed an upper bound, by the obvious symmetry that if $d$ is a divisor of $n$ then $n/d$ is a divisor, and it is attained whenever $n$ is the product of a single large prime $>n^{2/3}$ with some number of smaller primes. However, $d_3(n) \geq d(n)/5$ is certainly not true for all (or even most) $n$, by the concentration of measure statement Terry was mentioning. $\endgroup$
    – Will Sawin
    Aug 6, 2021 at 19:04
  • 2
    $\begingroup$ Actually, I was wrong about "most". It is not true for all $n$, but a typical $n$ has a large prime factor, meaning that the inequality $d_k(n) \geq d_2(n)/C$ is true with positive probability for all $k$ and all $C \geq 2$, and it might be quite a large probability. $\endgroup$
    – Will Sawin
    Aug 6, 2021 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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