Given a number $x\in [0, 1]$, let us consider the sequence $z_n=\{b^n x\}$ where the curly brackets represent the fractional part function, and $b>1$ is an integer. In particular, $\lfloor b z_n\rfloor$ is the $n$-digit of $x$ in base $b$. The following property is true for most real numbers $x\in [0, 1]$, for all positive integers $k$, though there are infinitely many exceptions (all rational numbers are exceptions):

$c(x,k) = \mbox{Correl}(z_n,z_{n+k}) = b^{-k}$.

The correlation here is an empirical auto-correlation of lag $k$ computed on the observed values in the sequence $z_n$. This result is true for all numbers $x$ but a set of Lebesgue measure zero. Not sure if it is a well known result or not, but I formally proved it, and this is not the object of this question. Empirical evidence also suggests it is correct. This result is true only for normal numbers, that is, in a nutshell, numbers having a uniform distribution on $[0, 1]$ for $z_n$ (the vast majority of numbers.) Not all irrational numbers are normal, for instance $0.101001000100001...$ is irrational but not normal in base $2$. The contants $\pi,\log(2), e, \sqrt 2, \sin(1)$ are believed to be normal, after extensive statistical testing up to 22 trillions of digits, though there is no proof.

Now is the interesting part of the discussion. I am doing some tests, computing the following correlations for some number $x$, with $b=2$ and $f(n)=n$:

$g(x,k) =\mbox{Correl}\Big(\{xf(n)\},\{b^k xf(n)\}\Big), k=0, 1, 2 \cdots.$

You would also expect, if $f(n)$ is a well behaved sequence of integers, say $f(n) = n$, that $g(x,k) = c(x, k)$. My question is whether you can find an irrational number $x$ that is non-normal, for which $g(x,k) \neq b^{-k}$ for at least some values of $k$, say $k=1, 2, 3$ or $4$. Here we can use $b=2$ for simplicity.

All the irrational numbers that I tested so far (even weird ones) seem to satisfy $g(x,k) = b^{-k}$, and none of the rational numbers I tested do. I am very interested in finding an irrational number (obviously it would be a non-normal one) for which this equality is NOT satisfied. A positive answer to my question may lead to new criteria to characterize normal numbers.

  • $\begingroup$ I would expect that the number $x$ having all its binary digits equal to zero except the digits in position $1, 4, 9, 16, 25$ and so on, is a good candidate. But the tests I did so far, due to limitations in machine precision, are not conclusive. $\endgroup$ – Vincent Granville Aug 14 '19 at 17:39

Let us focus on $k=1$ and let $z = bx$. Also, we assume that $f(n)$ preserves equidistribution, in the sense that if $x$ is irrational, then the sequence defined by $y_n = \{f(n) x\}$ is almost equidistributed. "Almost equidistributed" means that its associated limit distribution is a uniform distribution on $[0, 1]$ except possibly on a subset of Lebesgue measure zero. If in addition, $x$ and $z$ are linearly independent over the set of irrational numbers, with both $x$ and $z$ irrational, then $g(x, 1) = 0$.

Many functions $f(n)$ preserve equidistribution, for instance $f(n) = pn + q$ where $p\neq 0$ and $q$ are integers, or $f(n) = \lfloor \alpha n\rfloor$ where $\alpha \neq 0$ is a real number, irrational or not. Probably $f(n) = n^2$ also works.

Now Let's move to the case where $b$ is a rational number, say $b = p/q$ where $p,q$ are strictly positive integers, and $\mbox{gcd}(p, q) = 1$. Then $g(x, 1) = \frac{1}{pq}$. This result is based on strong numerical evidence, and probably not very difficult to prove. It generalizes my conjecture for the case $k=1$.

Now let's solve the general case: $k > 0$. Consider $p=b^k$ and $q=1$. Apply the result obtained in the previous paragraph ($g(x, 1) = \frac{1}{pq}$). This yields $g(x,k) = b^{-k}$. This result is useful from a numerical point of view: while the empirical computation $c(x, k)$ involves working with large powers of $b$ that quickly grow beyond the machine precision capacity, $g(x, k)$ requires far more gentle arithmetic.


Your Answer

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

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