3
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Commented Aug 14, 2019 at 17:39

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .