## Growth Rate of Signed Sum of Divisor Function

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

-

I believe I can show that the sum is growing, details to follow.

-
 I wrote the above at 2:15 am as a result of inequality signs facing the wrong way, sorry. – kodlu Mar 14 2012 at 6:24

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

-
 Thanks, very good answer. – kodlu Mar 14 2012 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 2012 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.

-