# Sum of divisors below threshold

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

• 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. – Gerhard Paseman Jun 14 '18 at 15:55
• 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. – Gerhard Paseman Jun 14 '18 at 16:02
• 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. – Kurisuto Asutora Jun 15 '18 at 4:03
• 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$. – Greg Martin Jun 15 '18 at 7:38
• 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$. – Greg Martin Jun 15 '18 at 7:52

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