The brackets represent the integer part function. Is it correct to say that the limit is equivalent to $$\lim_{T\rightarrow\infty} \frac{1}{T}\int_0^T (2^x \alpha - \lfloor 2^x \alpha \rfloor) dx = \lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=1}^n (2^k \alpha - \lfloor 2^k \alpha \rfloor) ?$$ Here $\alpha \in [0, 1]$. This sounds like a straighforward application of the Euler-Maclaurin summation formula. If that's correct, then the limit in question is the proportion of binary digits of the number $\alpha$, that are equal to one (see exercise 15 in this article for details.) However, I have a vague feeling that this is not right: $2^x \alpha = 2^{x+\log_2\alpha}$, and with the change of variable $y=x + \log_2 \alpha$, the limit with the integral becomes $$ \begin{split} \lim_{T\rightarrow\infty} \frac{1}{T}\int_0^T (2^x \alpha - \lfloor 2^x \alpha \rfloor) dx & = & \lim_{T\rightarrow\infty} \frac{1}{T}\int_{\log_2 \alpha}^{T+\log_2 \alpha} (2^y - \lfloor 2^y \rfloor) dy \\ & = & \lim_{T\rightarrow\infty} \frac{1}{T}\int_0^T (2^y - \lfloor 2^y \rfloor) dy& \end{split} $$ In short, the limit with the integral does not depend on $\alpha$ while the limit with the summation does. Since for the vast majority of numbers $\alpha$ except for a set set of Lebesgue measure zero, consisting of non-normal numbers, the limit involving the summation is $\frac{1}{2}$, my guess is that the limit with the integral is always equal to $\frac{1}{2}$ regardless of $\alpha$ (except for $\alpha = 0$).

Am I missing something? My brain is a bit foggy about this whole thing.

  • $\begingroup$ You can replace $\{ 2^x \alpha\}$ by $1/2$ without fear because the small $x$ don't contribute to the limit. $\endgroup$ – reuns Sep 21 '19 at 17:35
  • $\begingroup$ @Reuns: But why can you do it with the integral, but not with the summation? $\endgroup$ – Vincent Granville Sep 21 '19 at 17:48
  • 1
    $\begingroup$ Who said you can't ? Now it is non-trivial to find for which $\alpha \in \Bbb{R}$, $\lim\int=\lim\sum$ whereas it is trivial to show $\lim\int=1/2$ $\endgroup$ – reuns Sep 21 '19 at 17:52
  • $\begingroup$ @Reuns: Then there must be something with the Euler-Maclaurin summation formula, that makes it non-applicable in this case, for instance if $\alpha = 1/2$. What would that be? $\endgroup$ – Vincent Granville Sep 21 '19 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.