I apologise for the long-windedness of this question.

Let $a$ be a positive real constant and let $d(n)$ denote the number of divisors of $n.$ Define $$ S_a(x)=\sum_{n\leq x} d(n)^a. $$ For $a=1,$ the following is well known $$ S_1(x)=\sum_{n\leq x} d(n)=x \log x + (2 \gamma -1) x +{\cal O}(\sqrt{x}) $$ while for more general $a$, one has $S_a(x) \sim C(a) x (\log x)^{2^a -1}$ where $$ C(a) = \Gamma(2^a)^{-1} \prod_p \left( 1 - \frac{1}{p} \right)^{2^a} \left( \sum_{k \geq 0} \frac{(k+1)^a}{p^k}\right). $$ More accurate estimates are available via the Selberg-Delange method, though the details get quite technical.

My question is the following. Let the subset $A$ be defined by $A\subset \{1,2,\ldots,x\},$ (assume $x$ is integer or use the floor function) with $$\#A\geq \frac{x}{2}+ c \frac{\log x}{\log \log x}:=Z(x).$$ Now define $$ S^{A}_{a}(x)=\sum_{n\leq x:n \in A} d(n)^a. $$ I want to lower bound this sum, as $A$ varies subject to the size condition, i.e., to derive a lower bound to $$ M:=\min \left\{ S_a^A(x): A \subset \{1,\ldots,x\}, \#A =Z(x) \right\}. $$ For $a=1,$ I hope a lower bound of the form $M\gg x \log x$ may be possible if the Poisson approximation is good enough. Essentially this would say that half the points achieve a constant factor of the full sum, even when restricted to those points with the fewest number of divisors.

From a Poisson approximation point of view, it would seem that approximately half the points $n\in \{1,\ldots,x\}$ have $\omega(n)\leq \log\log n,$ with the relevant Poisson distribution having mean $\log\log n.$

I am unsure if the known techniques are strong enough to address such a delicate size specification, compared to say $\lceil x/2 \rceil,$ but some comments related to Selberg-Delange have a discussion of how a multiplicative $O(1+(\log x)^{-c'})$ factor can be shown for various sums, which may imply that it is indeed possible.

  • 2
    $\begingroup$ The quantity $c\log x/\log\log x$ can't possibly affect the size of the lower bound, since the contribution of $d(n)^a$ over that few integers is $\ll x^\varepsilon$. I imagine that the answer will be essentially $x(\log x)^{a\log 2}$ (for $a>0$), since as you say most integers have around $2^{\log\log n} = (\log n)^{\log 2}$ divisors. (That the exponent of $\log x$ in the asymptotic for $S_a(x)$ grows exponentially with $a$ is due to a relatively few integers with a huge number of divisors.) $\endgroup$ – Greg Martin Sep 17 '19 at 18:10

Even if you take $Z(x)=(1-\varepsilon)x$ for some fixed $0<\varepsilon<1$, you are going to get

$$ M=x(\ln x)^{a\ln 2+o(1)}. $$

To prove this, observe that both $\omega(n)$ and $\Omega(n)$ have normal order $\ln\ln n$ (here $\Omega$ and $\omega$ are numbers of prime factors with and without multiplicity respectively). Also note that

$$ 2^{\omega(n)}\leq d(n)\leq 2^{\Omega(n)} $$

for every $n$, which implies that for any $\delta>0$ for all but $o(x)$ numbers $n\leq x$ we have

$$ (\ln x)^{\ln 2-\delta}\leq d(n) \leq (\ln x)^{\ln 2+\delta}. $$

Therefore, for any $A\subset [1,x]\cap \mathbb N$ with $|A|\geq cx$ for some $c>0$ we have

$$ S_a^A\geq |A|(\ln x)^{a(\ln 2-\delta)}-o(x), $$

so that $M\gg x(\ln x)^{a(\ln 2-\delta)}$. On the other hand, if you throw all the $n$ with $n>(\ln x)^{\ln 2+\delta}$ out of your interval, you will still have $x-o(x)$ numbers left. This implies that for any $\varepsilon>0$ and $x$ large enough there is $A$ with $|A|\geq (1-\varepsilon)x$ such that

$$ S_a^A\leq |A|(\ln x)^{a(\ln 2+\delta)}. $$

  • $\begingroup$ Thanks. Do you mean "for all but $o(x)$ numbers $n\leq x$ we have $(\ln x)^{\ln 2-\delta}\leq d(n) \leq (\ln x)^{\ln 2+\delta}$? $\endgroup$ – kodlu Sep 17 '19 at 22:33
  • $\begingroup$ And unless I'm totally confused, it should be "if you [discard] all the $n$ with $d(n)>(\ln x)^{\ln 2+\delta}$ out of your set $A$", in the penultimate paragraph. Are you assuming $A$ is an interval in any way? $\endgroup$ – kodlu Sep 17 '19 at 23:47
  • 1
    $\begingroup$ @kodlu, 1. Yes, of course. Corrected, thanks. 2. No, I'm not assuming that $A$ is an interval. I mean that if you discard all the $n$ with large $d(n)$, you will still have enough numbers left to construct your set $A$ $\endgroup$ – Asymptotiac K Sep 18 '19 at 7:37

There is a cheap way via Cauchy's inequality in case you do no want to use Erdos--Kac. I will only do it for $a=1$ just to outline the idea. $$\frac{x}{2} (1+o(1) ) \leq \sum_{n \leq x } 1_A(x)= \sum_{n \leq x } 1_A(x)\sqrt{\tau(n)} \tau(n)^{-1/2}\leq (S_1^A(x))^{1/2} (\sum_{n\leq x } \tau(n)^{-1} )^{1/2} .$$ Now use $$ \sum_{n\leq x } \tau(n)^{-1} \ll \frac{x}{\sqrt{\log x } }$$ to get $$ M \gg x (\log x)^{1/2}.$$ This is a long way from $M\gg x \log x$ but it is better than the trivial bound $M \geq x/2 (1+o(1) ) $. You might try to use H"older's inequality instead to find a better logarithmic exponent.

  • $\begingroup$ The other answer would seem to imply that perhaps such an optimization of the lower bound via Ho"lder may not be possible. $\endgroup$ – kodlu Sep 17 '19 at 23:45
  • $\begingroup$ I meant, it can probably only be optimized to $x(\log x)^{\ln 2}.$ $\endgroup$ – kodlu Sep 18 '19 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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