Let $\tau(n)$ be the divisor function. Let $a$ be either a constant, or a function of $X$ that is slowly varying with $X,$ say $X/\log(X)<a(X)<X \log(X),$ for example. I want to lower bound sums of the following form $$ \sum_{1\leq n\leq X} a^{1-\frac{\tau(n)}{D}},\quad(1) $$ and $$ \sum_{1\leq n\leq X: n\in I} a^{1-\frac{\tau(n)}{D}},\quad(2) $$ where $I$ is an index set of roughly $n/2$ integers. Here, $0<D\leq X$ is also a function of $X$ that is slowly varying with $X.$

We can, of course, factor out an $a$.

I know the divisor function values for the interval $[1,X]$ obeys a kind of arcsine distribution law, and that should help obtain a bound, but I haven't been able to obtain one. Directly applying the AGM (arithmetic-geometric mean inequality) seems to be too weak.

Edit: For (1) we can apply the AGM $$ a X\left( X^{-1} \sum_{1\leq n\leq X} a^{-\tau(n)/D}\right)\geq a X\left( \prod_{1\leq n\leq X} a^{-\tau(n)/D}\right)^{1/X} $$ which gives $$ a X\left( a^{-\sum_{1\leq n\leq X} \tau(n)/DX}\right)\approx aX \left( a^{-(X \log X +(2\gamma-1)X+o(\sqrt{X}))/DX}\right)= X a^{1-O(\frac{\log X}{D})}. $$ As for 2, the question is how to obtain a worst case bound by using the distribution I alluded to in the original question, plus something else(?).

  • $\begingroup$ Do you mean I has about X/2 integers? $\endgroup$ – The Masked Avenger Mar 20 '15 at 16:17
  • $\begingroup$ @ The Masked Avenger: Yes. $\endgroup$ – kodlu Mar 20 '15 at 19:35
  • $\begingroup$ When I pick $I$ to be of cardinality $n/2$ and pick it to give the smallest value for the sum [at each $n$], it seems like the sum $\sum_{1\leq n \leq X: n \in I} \tau(n)$ may well be something like $X \log^2 X$ or $X^{1+\epsilon}$ though I doubt the second one. This was checked on Mathematica for $n\leq 4000$ for now. $\endgroup$ – kodlu Mar 22 '15 at 9:32
  • $\begingroup$ Oops, should have written $X \log X$ above, read the plot wrong. $\endgroup$ – kodlu Mar 22 '15 at 9:48

I think I have an answer, whereby the same asymptotic order lower bound as in (1) is obtained for (2). Please comment if there is an issue with the argument:

Consider $$ \sum_{1\leq n\leq X: n\in I} a^{1-\frac{\tau(n)}{D}},\quad(2) $$ where the question specified $I$ to be an index set of roughly $X/2$ integers. Thus I will take $\mid I\mid \in [(X-t)/2,(X+t)/2]$ for some fixed positive integer $t.$ By using the same argument as for (1) we obtain $$ \sum_{1\leq n\leq X: n\in I} a^{1-\frac{\tau(n)}{D}}\geq a \mid I\mid \left( a^{-\sum_{1\leq n\leq X:n\in I} \tau(n)/(D \mid I\mid)}\right)\quad(3). $$ Now focus on the sum in the exponent of (3). Let us assume that we choose $I$ to be an index set (there can be more than one) which achieves the maximal sum of divisors of $n\in I$ subject to the limits on $\mid I\mid$ given above.

If there were a function $f$ growing strictly faster than $O(X \log X)$ such that $$ \sum_{1\leq n\leq X: n\in I} \tau(n) \geq f(X), $$ as $X$ grows, then this would imply that $$ \sum_{1\leq n\leq X} \tau(n) \geq f(X), $$ since the divisor function is always positive. But this would contradict the fact that the full divisor sum is known to be $O(X \log X).$ Thus the partial sum is at most $O(X \log X).$

Now rewrite (3), using the order estimate from above and the fact that $\mid I\mid =\delta X$ where $\delta>0$ is constant. We get $$ \sum_{1\leq n\leq X: n\in I} a^{1-\frac{\tau(n)}{D}}\geq a \delta X \left( a^{-O(X \log X)/(D \delta X)}\right)\gg Xa^{1-O(\frac{\log X}{D})} . $$


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.