3
$\begingroup$

The brackets denote the fractional part function. It is well known that the distribution (defined as the limit of the empirical distribution) is $F(x)=(e^x - 1)/(e-1)$, with $x\in [0, 1]$, if $\alpha=1$, see here. Also, $\{n^\alpha\}$ is equidistributed if $\alpha>0$ is not an integer, that is, the distribution is uniform on $[0, 1]$, in other words $F(x)=x$. I suspect $\{(\log n)^\alpha\}$ is equidistributed if $\alpha>1$.

For slow growing functions, we don't have equidistribution, and one might even argue that there is no limiting distribution due to lack of convergence. Here I propose a simple framework to make the limiting distribution exist and be well and uniquely defined. My questions are:

  • What is the distribution of $\{(\log n)^\alpha\}$ when $0<\alpha\leq 1$?
  • Is $\{(\log n)^\alpha\}$ indeed equidistributed when $\alpha>1$?
  • What is the "slowest growth" function that guarantees equidistribution? For instance, is $\{(\log n)(\log \log n)\}$ equidistributed, given that $\{\log n\}$ is not, and $\{(\log n)^2\}$ seems to be?

Potential approach to this problem

Here I summarize my research. It allows you to quickly find the limiting distribution for $\{h(n)\}$ (or a least provides a sure way to find it), whether equidistributed or not, for strictly increasing sequences $h(n)$ satisfying both $h(n)=o(n)$ and $h(n)\rightarrow \infty$. With this methodology, it becomes trivial to prove that $\{ \sqrt{n}\}$ is equidistributed, and that $\{\log_b n\}$ has limiting distribution $(b^x-1)/(b-1)$. Thus my question focuses on less trivial examples.

To find the limiting distribution whether uniform on not (if uniform on $[0, 1]$ it implies equidistribution), proceed as follows:

  • Find a large $m$ such that $h(m) = n$ is an (obviously large) integer. Thus $m = h^{-1}(n)$. Find $m'$ such that $h(m')=n+1$, thus $m'=h^{-1}(n+1)$.
  • We are interested in the distribution of $h(m+k)$ between $m$ and $m'$, with $k=0,1,2,\dots, m'-m$. Let $x=k/(m'-m)$ so that $0\leq x\leq 1$.
  • Let $g_n(x) = h(m+k)-h(m) = h(m+x(m'-m))-h(m)$, and $k(n)=h^{-1}(n)$. Thus $g_n(x) = -n + h(k(n) + [k(n+1)-k(n)]\cdot x)$.
  • Define $g(x) =\lim_{n\rightarrow\infty} g_n(x)$. Then the distribution of interest is $F(x)=g^{-1}(x)$, with $0\leq x\leq 1$.

I used this to find that $\{(\log_2 n)^2\}$ is equidistributed ($F(x)=x$) and $\{ \log_2 n\}$ has distribution $F(x) = 2^x -1$. I am wondering if Mathematica would have found it, the computation of the limiting function $g_n(x)$, in the end, being purely mechanical.

I haven't computed it for the general case $\{(\log_2 n)^\alpha\}$, and that's part of my question. In that case, we have

$$g_n(x)=\Big[\log_2(2^{n^{1/\alpha}} + (2^{(n+1)^{1/\alpha}} - 2^{n^{1/\alpha}})\cdot x)\Big]^\alpha -n .$$

The next step is to compute $\lim_{n\rightarrow\infty} g_n(x)$.

Update on 10/28/2021

I computed the above limit $g(x)=\lim_{n\rightarrow \infty} g_n(x)$, with Mathematica, see here for $\alpha=\frac{1}{2}$. It confirms the answer provided below by Iosif. If $\alpha<1$ then $g(x) = 1$ if $x>0$, thus $g$ can not be inverted, so there is no limiting distribution of any kind. If $\alpha = 1$ then $g(x)=\log(1+(e-1)\cdot x)$ which is correct, yielding $F(x)=g^{-1}(x)=(e^x-1)/(e-1)$. And if $\alpha>1$ then $g(x)=x$, thus $F(x)=x$ is the uniform distribution. It is possible that regardless of $h(n)$ satisfying my requirements, these are the only three options.

Using Fejer's criterium mentioned in the comments, we also have equidistribution for $\{(\log n) (\log \log n)^\alpha\}$ if $\alpha>0$.

Below is the output from Mathematica:

enter image description here

$\endgroup$
6
  • $\begingroup$ It is "easy" to work on the case $\{(\log_b n)^\alpha\}$ using my methodology. Replace the number $2$ in my last formula, by $b$. $\endgroup$ Oct 28, 2021 at 0:17
  • $\begingroup$ As I am doing more research, I've found this MO answer to a question closely related to mine: mathoverflow.net/questions/107195/…. It confirms $\{(\log n)^{1+\epsilon}\}$ is equidistributed. So the originality of my question is in the case where equidistribution fails. $\endgroup$ Oct 28, 2021 at 2:15
  • 3
    $\begingroup$ Many years ago, an undergraduate student did an honours project on this topic: math.ucla.edu/~tao/preprints/ThesisSyd.pdf $\endgroup$
    – Terry Tao
    Oct 28, 2021 at 2:41
  • 4
    $\begingroup$ Feijer criterion trivially implies the equidistribution of $(\log n)^a, a>1$ modulo $1$ ($f'(x) \to 0, x|f'(x)| \to \infty$ for $x \to \infty$ and $f'$ monotonic implies $f(n)$ is uniformly distributed modulo $1$ $\endgroup$
    – Conrad
    Oct 28, 2021 at 2:41
  • $\begingroup$ @Conrad: yes, and my previous comment (about an answer to an MO question) actually is based on the Fejer criteria, which I was not aware of. What I offer here is a method to find what the limiting distribution might be, and if uniform it means equidistribution. Not sure if it is somehow related to Fejer's result, but it is an effective method that will tell you what that distribution is, either way. $\endgroup$ Oct 28, 2021 at 2:56

1 Answer 1

8
$\begingroup$

There is no limit distribution at all for $a:=\alpha\in(0,1)$: for each $x\in(0,1)$, the relative frequency \begin{equation*} f_n:=f_n(x):=\frac1n\,\sum_{j=1}^{n-1}1(x_j<x) \end{equation*} will be forever oscillating between $0$ and $1$ as $n\to\infty$, where \begin{equation*} x_j:=\{\ln^a j\}. \end{equation*} (The oscillations will be very slow for large $n$, because the function $\ln$ is varying slowly.)

Indeed, take any $a\in(0,1)$ and any $x\in(0,1)$. If $k$ and $j$ are natural numbers and $k\le\ln^a j<k+1$, then $x_j<x\iff e^{k^p}\le j<e^{(k+x)^p}$, where $p:=1/a>1$.

So, with $u\wedge v:=\min(u,v)$, \begin{equation*} \begin{aligned} S&:=\sum_{j=1}^{n-1}1(x_j<x) \\ &=\sum_{j=1}^{n-1}\sum_{k=1}^\infty 1(e^{k^p}\le j<e^{(k+x)^p}) \\ &=\sum_{k=1}^\infty\sum_{j=1}^{n-1} 1(e^{k^p}\le j<e^{(k+x)^p}) \\ &=\sum_{k=1}^\infty\sum_{j=1}^\infty 1(e^{k^p}\le j<n\wedge e^{(k+x)^p}) \\ &=\sum_{1\le k<\ln^a n}\;\sum_{j=1}^\infty 1(e^{k^p}\le j<n\wedge e^{(k+x)^p}) \\ &=\sum_{1\le k<\ln^a n}\;(n\wedge e^{(k+x)^p}-e^{k^p}+O(1)) \\ &=S_1+S_2+O(\ln^a n)=S_1+S_2+o(n), \end{aligned} \end{equation*} where \begin{equation*} S_1:=\sum_{k=1}^{k_n}(e^{(k+x)^p}-e^{k^p}),\quad S_2:=\sum_{k_n+1\le k<\ln^a n}(n-e^{k^p}), \end{equation*} \begin{equation*} k_n:=k_{x,n}:=\lceil \ln^a n-x\rceil-1, \end{equation*} so that \begin{equation*} \ln^a n-x\le k_n+1<\ln^a n-x+1. \tag{1} \end{equation*} Since $p>1$ and $x\in(0,1)$, for $k\to\infty$ and natural $l<k$ we have $e^{(k+x)^p}>>e^{k^p}>>e^{(l+x)^p}$, where $A>>B$ means $A/B\to\infty$, so that $e^{(k+x)^p}-e^{k^p}\sim e^{(k+x)^p}>> e^{(l+x)^p}-e^{l^p}$. So, \begin{equation*} S_1\sim e^{(k_n+x)^p}. \end{equation*} Next, \begin{equation*} S_2=1(k_n+1<\ln^a n)(n-e^{(k_n+1)^p}) \end{equation*} and \begin{equation*} 1(k_n+1<\ln^a n)=1(\ln^a n-x\le k_n+1<\ln^a n). \end{equation*}

Take any $y\in(x,1+x)$. Note that $\ln^a(n+1)-\ln^a n\sim a\ln^a n/(n\ln n)$. So, there is a sequence $(n_k)=(n_{y;k})$ of integers such that $\ln^a n<k+y\le (\ln^a n)(1+1/(n\ln n))=\ln^a n+o(1)$ for $n=n_k$ and all $k$. So, by (1), eventually (that is, for all large enough natural $k$) we have $k_n=k$ if $n=n_k$, and hence \begin{equation*} (k_n+y)^p =(\ln n)[1+O(1)/(n\ln n)]^p=\ln n+O(1/n)=\ln n+o(1), \end{equation*} so that \begin{equation*} n\sim e^{(k_n+y)^p}>>e^{(k_n+x)^p}\sim S_1, \end{equation*} whereas $\ln^a n<k_n+y<k_n+1$ if $y\in(x,1)$, so that $S_2=0$, and thus $f_n=(S+o(1))/n\to0$.

However, if $y\in(1,1+x)$, then eventually we have $\ln^a n=k_n+y+o(1)>k_n+1$, so that \begin{equation*} S_2=n-e^{(k_n+1)^p}=n-o(e^{(k_n+y)^p})=n-o(n), \end{equation*} which implies $f_n\ge(S_2+o(n))/n\to1$, whence $f_n\to1$.

Thus, as $k\to\infty$, we have $f_{n_{y;k}}\to0$ if $y\in(x,1)$ and $f_{n_{y;k}}\to1$ if $y\in(1,1+x)$.


As an illustration, here are the connected graphs $\{(n,f_n)\colon1\le n\le 10^2\}$ and $\{(n,f_n)\colon10^2\le n\le 10^6\}$ for $a=5/10$ and $x=4/10$:

enter image description here


In the case $a=1$, one can use reasoning mostly quite similar to the above reasoning for $a\in(0,1)$, but the conclusion here is a bit different. Namely, here, for $y\in(x,1+x)$ (as above) and $n=n_k=n_{y;k}$, \begin{equation} S_1\sim\frac{e^x-1}{e-1}\,e^{1-y}n, \end{equation} and also $S_2=0$ eventually if $y\in(x,1)$, so that \begin{equation} f_{n_{y;k}}\to\frac{e^x-1}{e-1}\,e^{1-y} \end{equation} if $y\in(x,1)$, so that $\lim_k f_{n_{y;k}}$ depends on the choice of $y\in(x,1)$. So, there is no limit distribution for $a=1$ either.

The case $a>1$ is covered in comments. In this case, the limit distribution is uniform.

Thus, the borderline case is $a=1$, in terms of the existence of a limit distribution.

$\endgroup$
3
  • $\begingroup$ Thank you for your great insights. I noticed empirically that even for $\alpha=1$, there is no limit (no distribution) and you formally proved it. That said, when talking about a distribution in that case (as some authors including myself do, namely $(e^x-1)/(e-1)$), it is obtained by looking only at very specific windows. The term "limit distribution", in that case, is a misnomer; it should be called something else. $\endgroup$ Oct 28, 2021 at 17:21
  • $\begingroup$ I recommend to take a look at the book O. Strauch and S. Porubský: Distribution of sequences: a sampler. Series of the Slovak Academy of Sciences, 2005. Online version available here: mat.savba.sk/musav/… See in particular Section 2.12 on page 2-132. $\endgroup$ Oct 29, 2021 at 7:57
  • $\begingroup$ @KurisutoAsutora : Thank you for the reference. Wow, I did not know about all that work. $\endgroup$ Oct 29, 2021 at 12:58

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.