7
$\begingroup$

For positive integers $n$, define $H(n)$ as the sum of the reciprocals of divisors of $n$: $$ H(n) = \sum_{k: k|n} 1/k$$ where a divisor includes both $1$ and $n$. For $t\geq 0$ define \begin{align} f(t) &= \limsup_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n1_{\{H(i)\geq t\}} \end{align} I would like to understand the $f(t)$ function (as well as perhaps its $\liminf$ version). In particular, I would be interested in comments or strengthened forms of the following conjecture I just made (based on a previous question linked below). My conjecture uses only a Markov inequality, but perhaps there is some stronger Gaussian approximation that can be used. Or perhaps the conjecture is false?


Conjecture: $f(t) \leq \frac{\pi^2}{6t} \quad \forall t >0$

Intuition: For all positive integers $N$ we have $$ H(N) = \sum_{k=1}^{\infty} 1_{\{k|N\}}\frac{1}{k} \quad (*)$$ We can imagine that for every positive integer $k$, the "probability" that a "randomly selected integer $N$" is divisible by $k$ is $1/k$. This can be made precise by observing $$ \lim_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n 1_{\{\mbox{$k$ divides $i$}\}} = 1/k$$ However, for the sake of this intuitive idea, let's keep the notion of "randomly selected integer" and "probability" imprecise. So if we imagine $N$ as a "randomly selected large integer" then from (*) $$ E[H(N)] = \sum_{k=1}^{\infty} P[\mbox{$k$ divides $N$}]\frac{1}{k}= \sum_{k=1}^{\infty}\frac{1}{k^2}=\frac{\pi^2}{6}$$ and by using the Markov inequality (imagining that it still works in this imprecise probability world) we obtain for all $t>0$: $$ P[H(N)\geq t] \leq \frac{E[H(N)]}{t} = \frac{\pi^2}{6t}$$ I suspect that a variation of this argument can be made rigorous by carrying out a sample path version of the Markov inequality.


This was inspired by comments on the question here:

$\lim_{n \to \infty} ​ H(a_n)=\infty$ where $H(a_n)$ is the sum of the inverses of the divisors of $a_n$

$\endgroup$
4
  • $\begingroup$ I guess one way to make the argument rigorous is to define $H^m(n)=\sum_{k=1}^m1_{\{k|n\}}\frac{1}{k}$. Then define $N$ as a random integer uniform over $\{1, ..., m\}$ and use standard probability theory to get $P[H^m(N)\geq t] \leq E[H^m(N)]/t = \frac{1}{t}\sum_{k=1}^mP[\mbox{$k$ divides $N$}]\frac{1}{k}$. Then take $m\rightarrow \infty$. Perhaps a better bound can be obtained by using second moments and Chebyshev. $\endgroup$
    – Michael
    Commented Jun 12 at 23:21
  • $\begingroup$ Just to be clear, the function $H(n)$ is the abundancy of the integer $n$? More commonly expressed as $\frac{\sigma(n)}{n}$. $\endgroup$
    – Servaes
    Commented Jun 13 at 7:26
  • 1
    $\begingroup$ @Servaes We have $H(1)=1$, $H(2)=1 + 1/2$, $H(3) = 1+1/3$, $H(4)=1+1/2+1/4$, $H(5)=1+1/5$, and so on. The Sungjin answer relates this to a $\sigma(n)/n$ function that I am not familiar with. I formulated the problem by trying to cast the linked question into a precise statement. The linked question seems to suggest that $f(t)\rightarrow 1$, but I realized the above informal argument suggested it decays like $O(1/t)$. It turns out that my $\pi^2/(6t)$ conjecture is correct (even in a nonasymptotic sense), and also $\frac{1}{n}\sum_{i=1}^nH(i)\rightarrow \pi^2/6$. $\endgroup$
    – Michael
    Commented Jun 13 at 13:17
  • $\begingroup$ Thanks for the clarification. Here $\sigma(n)$ denotes the sum of all positive divisors of $n$, so indeed $H(n)=\tfrac{\sigma(n)}{n}$. The function $\sigma(n)$ has been studied very extensively, and any similar questions you might have are likely easily answered with known asymptotics of $\sigma(n)$ in a fairly straightforward way. Either way, nice question and glad your question was answered! $\endgroup$
    – Servaes
    Commented Jun 13 at 17:23

2 Answers 2

6
$\begingroup$

We have $$ H(n)=\sum_{k=1}^{\infty} 1_{\{k|n\}}\frac{1}{k} =\sum_{k|n}\frac kn $$ by reversing the role of $k$ and $n/k$. Then a well-known sum-of-divisor fuction appears. From the above, $$ H(n)=\frac{\sigma(n)}n. $$ Thus, the sum you are looking for $$ A(t)=\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^n1_{\{H(i)\geq t\}} $$ is an asymptotic density of positive integers with $\sigma(i)/i \geq t$. Such asymptotic density is known to exist and continuous in the variable $t>0$.

Andreas Weingartner has number of results in this direction. I will point you to one of his results here: PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 135, Number 9, September 2007, Pages 2677–2681 S 0002-9939(07)08771-0

His Theorem 1 states that as $t\rightarrow\infty$, $$ A(t)=\exp\left( -e^{te^{-\gamma}}\right)(1+O(t^{-2})) $$ where $\gamma=0.5772...$ is Euler's constant.

$\endgroup$
1
  • $\begingroup$ Thanks! From the paper you include, it looks like $f(t)$ decays much faster than $O(1/t)$. I have added an answer that shows the $\pi^6/(6t)$ bound holds nonasymptotically for all $n$ (just refining the Markov inequality argument in my question). $\endgroup$
    – Michael
    Commented Jun 13 at 1:13
1
$\begingroup$

This just makes my Markov inequality argument rigorous and stronger.


Define $\mathbb{N}$ as the set of positive integers. Let $g:\mathbb{N}\rightarrow [0, \infty)$ be a nonnegative function. For $n \in \mathbb{N}$ define $$ G(n) = \sum_{k:k|n} g(k)$$ The special case $g(k)=1/k$ for all $k$ yields $G(n)=H(n)$.

Claim 1: For all $n \in\mathbb{N}$ and $t>0$ we have $$ \frac{1}{n}\sum_{i=1}^n1_{\{G(i)\geq t\}} \leq \frac{1}{t}\sum_{k=1}^{\infty}\frac{g(k)}{k}$$ The special case $g(k)=1/k$ for all $k$ yields $\frac{1}{n}\sum_{i=1}^n1_{\{G(i)\geq t\}} \leq \frac{\pi^2}{6t}$.

Claim 2: If $\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^ng(i)=0$ then $$\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^nG(i)=\sum_{k=1}^{\infty}\frac{g(k)}{k}$$ The special case $g(k)=1/k$ for all $k$ yields $\frac{1}{n}\sum_{i=1}^nG(i)\rightarrow\pi^2/6$.


Proof of Claim 1: Fix $n \in \mathbb{N}$ and $t>0$. For each $i \in \{1, ..., n\}$ we have $$G(i) = \sum_{k=1}^n 1_{\{k|i\}} g(k) \quad (Eq \: 1)$$ Define a discrete random variable $N \sim \mbox{Unif}\{1, ..., n\}$. By the law of total probability $$P[G(N)\geq t] = \sum_{i=1}^nP[G(i)\geq t | N=i]P[N=i] = \frac{1}{n}\sum_{i=1}^n1_{\{G(i)\geq t\}}$$ On the other hand, since $G(N)$ is a nonnegative random variable, the Markov inequality gives \begin{align} P[G(N)\geq t] &\leq \frac{E[G(N)]}{t} \\ &\overset{(a)}{=}\frac{1}{t}E\left[\sum_{k=1}^n1_{\{k|N\}}g(k)\right]\\ &= \frac{1}{t}\sum_{k=1}^nP[\mbox{$k$ divides $N$}]g(k) \end{align} where equality (a) holds by Eq (1). Now observe for all $k \in \{1, ..., n\}$ that $$P[\mbox{$k$ divides $N$}] =\frac{\lfloor n/k\rfloor}{n}\leq 1/k $$ $\Box$

Proof of Claim 2: Fix $n \in \mathbb{N}$. Define random variable $N \sim \mbox{Unif}\{1, ..., n\}$. Then $$E[G(N)] = \frac{1}{n}\sum_{i=1}^nG(i)$$ On the other hand, from Eq (1) we have $$ G(N) = \sum_{k=1}^n1_{\{k|N\}}g(k)$$ Taking expectations of both sides gives $$E[G(N)] = \sum_{k=1}^nP[\mbox{$k$ divides $N$}]g(k)$$ Also $$P[\mbox{$k$ divides $N$}] = \frac{\lfloor n/k\rfloor}{n} \in \left[\frac{1}{k}-\frac{1}{n}, \frac{1}{k}\right]$$ and so $$\sum_{k=1}^n\frac{g(k)}{k} - \sum_{k=1}^n\frac{g(k)}{n} \leq E[G(N)]\leq \sum_{k=1}^n\frac{g(k)}{k}$$ Taking $n\rightarrow\infty$ gives the result. $\Box$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .