MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $d(n)$ be the number of divisors function, i.e., $d(n)=\sum_{k|n} 1$ of the positive integer $n.$ I know about some of the ''gross'' averages for this function, such as the estimate $$ \sum_{n\leq x} d(n)=x \log x + (2 \gamma -1) x +{\cal O}(\sqrt{x}) $$ as well as its variability, e.g., the lim sup of the fraction $$ \frac{\log d(n)}{\log n/\log \log n} $$ is $\log 2$ while the lim inf of $d(n)$ is $2,$ achieved whenever $n$ is prime.

How much is known about the statistics of $d(n)$? In particular, if we let $N$ grow to infinity, is there any way to bound a sum of the form $$ \left| \sum_{n=1}^N \varepsilon_n d(n) \right| $$ from below for all or almost all $(\varepsilon_1,\cdots,\varepsilon_N)\in \{\pm 1\}^N$?

share|cite|improve this question

Studying your sum $$ X(\varepsilon) = \sum_{n=1}^N \varepsilon_n d(n) $$ for almost all $\varepsilon = (\varepsilon_1,\dots,\varepsilon_N) \in \{\pm1\}^N$ is basically equivalent to a probability problem: assign each such $\varepsilon$ a probability of $2^{-N}$. Then $X(\varepsilon)$ is a random variable with expectation $0$ and variance $$ \sigma^2(X(\varepsilon)) = \sum_{n=1}^N d(n)^2 \sim \frac{N(\log N)^3}{\pi^2}. $$ Therefore for the vast majority of $\varepsilon$, your sum will have order of magnitude $\sqrt N (\log N)^{3/2}$.

As for bounding from below, I claim that for sufficiently large $N$ the sum can always be made to be at most $2$ in absolute value. Choose $\varepsilon$ at random; then almost surely your sum $X(\varepsilon)$ will be less than say $N^{2/3}$ in absolute value. Without loss of generality, let's say the sum is positive. Also, almost surely at least a third of the primes $p$ will have $\varepsilon_p = 1$. Since "a third of the primes" has order of magnitude $N/\log N$, much larger than $N^{2/3}$, we can choose $X(\varepsilon)/4$ (rounded) primes $p$ for which $\varepsilon_p = 1$ and change them to $\varepsilon_p = -1$. The resulting $X(\varepsilon)$ will then have absolute value at most 2.

Note that the perfect squares are the only integers for which $d(n)$ is odd. A similar argument shows that almost surely there are perfect squares with $\varepsilon_{m^2} = 1$ and $\varepsilon_{n^2} = -1$. These can be used to adjust the sum so that it equals either 0 or 1, depending on the parity of the integer $X(1) = \sum_{n=1}^N d(n)$. (And note, by the same characterization of the integers with $d(n)$ odd, that the parity of $X(1)$ is exactly the parity of $\lfloor \sqrt N \rfloor$ !)

share|cite|improve this answer
Thanks, very good answer. – kodlu Mar 14 '12 at 6:23
In fact, I think a slight variant of this argument shows that $\varepsilon$ can be chosen so that $X(\varepsilon)$ can take on any integer between $-X(1)$ and $X(1)$ that has the same parity as $X(1)$. – Greg Martin Mar 14 '12 at 6:52

An answer to Greg's comment. It's true about the parity. However the sum can take on any value between $-\sum_{n=1}^N d(n)$ to $\sum_{n=1}^N d(n)$ if it has the right parity. It's because if $k$ is any number between $0$ and $D(N)=\sum_{n=1}^N d(n),$ then there exists some subset $A_{k,N}$ of $\{1,\dots, n\}$ such that $\sum_{n\in A_{k,N}} d(n)=k.$

It follows from the relatively easy fact that $2D(N)+1 \geq D(N+1)$ or equivalently $D(N)+1 \geq d(n+1).$ Then the result follows by induction.

It's true for $N=1$ since $A_{0,1}$ the empty set and A_{1,1}={1}.$

Suppose it's true for $N$, then if $0\le k \le D(N)$, let $A_{k,N+1}=A_{k,N}$ If $D(N+1)-D(N) \le k \le D(N+1),$ then let $A_{k,N+1}=A_{K,N} \cup N+1,$ where $K=D(N+1)-k.$

$2D(N)+1 \geq D(N+1),$ this covers all $k$ between $0$ and $D(N+1)$ finishing the induction.

Note that this idea shows the same can be done for any arithmetic function $f: \Nat \to \Nat $ with the same inequality $2F(N)+1 \geq F(N+1).$ Examples include the Euler totient function $\phi,$ the Carmichael lambda function $\lambda$ and many others.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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