# Estimating $\sum_{n\leq x: n \in A} d(n)^a$ from below for large sets $A\subset \{1,2,\ldots,x\}.$

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.

• 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.) – 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)}.$$

• 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}$? – kodlu Sep 17 '19 at 22:33
• 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? – kodlu Sep 17 '19 at 23:47
• @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$ – 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.

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