Asymptotic decay rate of a simple sequence

73 Views Asked by At

Define $$a_{i,j} = \frac{1}{i^2 j^2},\quad i,j=1,2,\dots.$$ If we arrange the sequence $a_{i,j}$ in decreasing order: $$b_1,b_2,b_3,\dots$$ where $b_n$ denotes the $n$-th largest number(counted with multiplicity), e.g., $b_1= 1, b_2=b_3=1/4$.

Is there an asymptotic decay rate for the sequence $\{b_n\}_{n=1}^{\infty}$ ? Do we have $b_n=O(n^{-k})$ for some $k$ ?

2

There are 2 best solutions below

2
On BEST ANSWER

For a fixed $1/ k$, define $$m(k) = \inf\{ n : b_n < 1/k\}.$$

Then $m(k)$ is equal to the number of $i,j$ so that $1/(i^2 j^2) > 1/k$, i.e. the number of $i,j$ so that $i\cdot j < \sqrt{k}$. For each fixed $i$, there are $\sqrt{k}/i + O(1)$ many $j$ for which $i\cdot j < \sqrt{k}$. Summing over all $i$ gives $$m(k) = \frac{1}{2}\sqrt{k} \log(k) + O(\sqrt{k}).$$

This means that $b_n \sim m^{-1}(n)$ where $m^{-1}$ is the inverse of $m$; there's no nice closed form for the inverse of $\sqrt{x} \log (x)$, so exact asymptotics don't have a nice closed form. You do have that $b_n = O(n^{-2 + \varepsilon})$ for each $\varepsilon > 0$, at the very least though.

1
On

The number of $b_n$s such that $b_n\geq \frac{1}{k}$ is given by the number of points $(a,b)\in\mathbb{N}^+\times\mathbb{N}^+$ such that $ab\leq \sqrt{k}$, which by Dirichlet's hyperbola method are $$ \frac{1}{2}\sqrt{k}\log(k)+(2\gamma-1)\sqrt{k}+O(k^{1/4}). $$ The inverse function of $\frac{1}{2}\sqrt{x}\log(x)$ is given by $\frac{x^2}{W(x)^2}$ with $W$ being Lambert's function.
By well-known asymptotics $$ b_n \sim \frac{\log^2(n)}{n^2}\quad\text{as }n\to +\infty. $$