Growth rate of signed sum of divisor function

Question

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

Answer 1

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

Answer 2

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: \mathbb{N} \to \mathbb{N}$ 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.