8
$\begingroup$

Let $\sigma(n)$ denote the sum of divisors of $n$, that is, $$ \sigma(n) = \sum_{d | n} d. $$ It is known that $\sigma$ can have values as large as order $n \log \log n$. However, obviously the sum is reduced when we restrict it to divisors which are smaller than some threshold $D$.

Question 1: How large can $D$ be (as a function of $n$), such that $$ \sum_{\substack{1 \leq d \leq D,\\ ~d | n}} d \leq n, $$ for all (sufficiently large) $n$?

One admissible value for $D$ is roughly $n / \exp(c \log n / \log \log n)$, since the number of divisors of $n$ is bounded by $\exp(c \log n / \log \log n)$, and the sum above is obviously dominated by $D$ times the number of divisors of $n$. However, my feeling is that the "right" order for $D$ should rather be around $n/\log n$ or even closer to $n$.

Question 2: Can we further increase the bound for $D$ from Question 1 if we only consider those $n$ for which $\varphi(n) > \varepsilon n$, for some fixed constant $\varepsilon$?

$\endgroup$
  • $\begingroup$ You might consider the partial sum as a function S(D,n), and play around with inequalities. For example, when is (1+p)S(D,n) greater than S(pD,pn)? You may find that you can tweak D in a multiplicative fashion to get some bound that works for you. Gerhard "Play In A Bigger Field" Paseman, 2018.06.14. $\endgroup$ – Gerhard Paseman Jun 14 '18 at 15:55
  • $\begingroup$ Also, the "right" order for n may be wrong if all (or enough) of the prime factors of n are bigger than log n. Gerhard "Talking About Really Big N" Paseman, 2018.06.14. $\endgroup$ – Gerhard Paseman Jun 14 '18 at 16:02
  • 1
    $\begingroup$ Yes, of course one may find bounds on D assuming additional number-theoretic properties of n, such as having only large prime powers. But this is not what I want to have, D is supposed to be a "nice" function of n which does not consider arithmetic properties but depends only on the size of n. $\endgroup$ – Kurisuto Asutora Jun 15 '18 at 4:03
  • 2
    $\begingroup$ When $n$ is so highly composite that $\sigma(n) > (e^\gamma-o(1))n\log\log n$, then the divisors above $D$ have to include enough numbers in the set $n,\frac n2, \frac n3,\dots,\frac n{n/D}$ so that their sum is at least $(e^\gamma-o(1))n\log\log n$. This means that $D$ cannot be taken to be $n/(\log n)^{e^\gamma-\epsilon}$ for any $\epsilon>0$. $\endgroup$ – Greg Martin Jun 15 '18 at 7:38
  • 3
    $\begingroup$ Try using Rankin's trick: $\sum_{d\mid n,\, d\le D} d \le \sum_{d\mid n} d (D/d)^\epsilon$, the right-hand side of which is a multiplicative function of $n$. I think that taking $\epsilon = o(1/\log\log n)$ yields the result that $D = n/\exp\big( (\log\log n)^2 f(n) \big)$ is valid if $f(n)\to\infty$. $\endgroup$ – Greg Martin Jun 15 '18 at 7:52
11
$\begingroup$

Put $$ B= C \frac{\log (10\sigma(n)/n)}{\log \log (10 \sigma(n)/n)} $$ for a suitably large positive constant $C$. Then I claim that the desired inequality holds with $$ D = \frac{n}{(\log n)^B}, $$ for all large $n$. Since $\sigma(n)/n \ll \log \log n$, it follows that one may always take $$ D = n \exp\Big( -C \frac{\log_2 n \log_3 n}{\log_4 n}\Big), \tag{1} $$ with $\log_j$ denoting the $j$-th iterated logarithm, and in fact this is in general the best possible. If $\sigma(n)/n$ is bounded by $1/\epsilon$ (as in Question 2) obviously one can obtain a stronger result, as $B =C \log(1/\epsilon)/\log \log (1/\epsilon)$ is now permissible.

Now for the proof. Put $$ A = \frac 12 \log \log (10\sigma(n)/n), \text{ and } \alpha= \frac{A}{\log \log n}. $$ Note that (writing $d=n/k$) $$ \sum_{\substack{ d|n \\ d\le D}} d =n \sum_{\substack{k|n \\ k > (\log n)^B}} \frac{1}{k} \le n (\log n)^{-B\alpha} \sum_{k|n} \frac{1}{k^{1-\alpha}} = ne^{-AB} \sum_{k|n} \frac{1}{k^{1-\alpha}}. \tag{2} $$ For large $n$ we have $$ \sum_{k|n} \frac{1}{k^{1-\alpha}} \ll \prod_{p|n} \Big(1 + \frac{1}{p^{1-\alpha}}\Big) \ll \exp\Big( \sum_{p|n} \frac{1}{p^{1-\alpha}}\Big). $$ To estimate this, divide the primes $p|n$ into three ranges: $p\le (\log n)^{1/A}$, $(\log n)^{1/A} \le p \le (\log n)$ and $p> \log n$. The contribution of the first range is $$ \sum_{\substack{ p|n \\ p\le (\log n)^{1/A}} } \frac{e}{p} \ll \log (\sigma(n)/n). $$ The second range gives $$ \le \sum_{(\log n)^{1/A} \le p\le (\log n)} \frac{1}{p^{1-\alpha}} \le e^A \sum_{(\log n)^{1/A} \le p\le (\log n)} \frac 1p \ll e^A \log A. $$ The final range gives (since the number of distinct primes dividing $n$ is $\ll \log n/\log \log n$) $$ \ll \sum_{\substack{p|n \\ p>\log n}} \frac{1}{p^{1-\alpha}} \le \frac{1}{(\log n)^{1-\alpha}} \sum_{p|n} 1 \ll \frac{e^A}{\log \log n}. $$ Combining all these bounds, and using it in (2) we find $$ \sum_{\substack{d|n \\ d\le D}} d \ll n e^{-AB} \exp\Big( O(\log (10\sigma(n)/n))\Big) \le n, $$ upon taking $C$ suitably large. This completes the proof that the claimed choice for $D$ works.

Let me now quickly say why the general form (1) is optimal. Take $n$ to be the lcm of all the integers up to some point (which is roughly $\log n$ by the prime number theorem). Then, roughly speaking, $$ \sum_{\substack{k |n \\ k >(\log n)^u}} \frac{1}{k} \gg \sum_{\substack{ (\log n)^{u+1} \ge k \ge (\log n)^u \\ p|k \implies p\le (\log n)}} \frac 1k \gg \rho(u+1) \log \log n, $$ where $\rho$ denotes the Dickman function. That is, the divisors of $n$ basically correspond to $\log n$ smooth numbers, and I have invoked the asymptotic for smooth numbers here. Since $\rho(u)$ behaves like $u^{-u}$ we see that $u$ has to be about as large as $\log_3 n/\log_4 n$ in order for $\rho(u+1) \log \log n$ to become negligible. This shows that the range in (1) cannot be improved (apart from the constant $C$).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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