# Some distributions / auto-correlations associated with irrational numbers

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.

• 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. – 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.