5
$\begingroup$

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

$\endgroup$

2 Answers 2

9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$ Mar 14, 2012 at 6:52
  • $\begingroup$ You might be interested in the related question mathoverflow.net/questions/390464/… $\endgroup$
    – kodlu
    Apr 21, 2021 at 4:00
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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