Cross-correlations in digit distributions

Question

*Update on 5/4/2023. The strictly positive integers $p$ and $q$ discussed in this post, in addition to being co-prime, must not contain any factor that is power of $2$, such $2,4,8$ and so on.

Let $B_1, B_2,\cdots$ be i.i.d. Bernouilli with mean $\frac{1}{2}$, and $$X=\sum_{k=1}^\infty \frac{B_k}{2^k}.$$ The random variables $B_k$ are the binary digits of the random number $X \in [0,1]$. Let's $p, q$ be strictly positive co-prime integers (that is, they have no common factors other than $1$). In addition, $p,q$ are odd numbers.

Let $C_k, D_k, k=1,2\cdots$ be the binary digits respectively of $pX$ and $qX$, starting after the decimal point. We define the cross-correlation $\rho_N$ as

$$\rho_N(p,q) = \mbox{Correl}(C_1,\cdots,C_N; D_1,\cdots,D_N).$$

The purpose here is three-fold:

1. Establish that the limit $\rho_\infty$ exists
2. Prove or disprove that $\rho_\infty=\frac{1}{pq}$
3. Prove that the empirical correlation between the binary digits of (say) $\sqrt{2}$ and $\sqrt{3}$, is zero.

I am by a long shot mostly interested in answering the third question, which would be a spectacular result, unproven to this day. However, answering the second question is also of great interest, and probably of bigger interest to the readers.

Some great progress (with respect to the third question) was accomplished in a previous answer to a CV question, see here. @Whuber proved that the cross-correlation between the terms in the sequences $\{kp\alpha\}$ and $\{kq\alpha\}, k=1,2,\cdots$, is $\frac{1}{pq}$. Here the brackets represent the fractional part function, and $\alpha$ is irrational.

In my question here, the relevant sequences would be $\{2^k p\alpha\}$ and $\{2^k q\alpha\}$ as the $k$-th binary digit of $\alpha$ is $\lfloor 2\{2^k\alpha\}\rfloor$.

To answer the third question, note that $\sqrt{2}$ and $\sqrt{3}$ are linearly independent over the set of rational numbers, and $\rho_\infty$ can be approximated as close as you want using $p\alpha$ and $q\alpha$ instead of $\sqrt{2}$ and $\sqrt{3}$ for some irrational $\alpha$. But to get better and better approximations, you need $p$ and $q$ to tend to infinity, and the resulting correlation, equal to $\frac{1}{pq}$, tends to zero.

Example and code

Below is the code used for my computations, creating simulated random numbers $X$ and computing the correlations between the binary digits of $pX$ and $qX$. It shows the variability from one sample to the other.

$nsimul=10;
$kmax=1000000;
$p=13;
$q=31;

open(OUT2,">correl.txt");      

for ($simul=0; $simul< $nsimul; $simul++) {

$rand=107*100000*$simul;
$prod=0;
$count=0;

for ($k=0; $k<$kmax; $k++) { # digits in reverse order
  $rand=(10232193*$rand + 3701101) % 54198451371;
  $b=int(2*$rand/54198451371); # digit of X

  $c1=$p*$b;
  $old_d1=$d1;
  $old_e1=$e1; 
  $d1=($c1+ $old_e1/2) %2;  # digit of pX
  $e1=($old_e1/2) + $c1 - $d1;

  $c2=$q*$b;
  $old_d2=$d2;
  $old_e2=$e2; 
  $d2=($c2+ $old_e2/2) %2;  #digit of qX
  $e2=($old_e2/2) + $c2 - $d2;

  $prod+=($d1*$d2);
  $count++;
  $correl=4*$prod/$count - 1;
  $limit=1/($p*$q);

  if ($k% 1000 == 0) { 
    print "$simul\t$k\t$correl\t$x\n"; 
    print OUT2 "$simul\t$k\t$correl\t$limit\n";
  }
     
}

print "correl: $correl - $x\n"; 

} 

close(OUT2);

Below is the chart showing one simulation, with 10 million random binary digits, with $p=1$ and $q=3$. The orange line corresponds to the limit $\rho_\infty = \frac{1}{3}$. The Y-axis represents the correlation computed over the first $n$ digits, for $n=1,2,\cdots, 10^7$ on the abcissa.

Possible approach to solve the problem

Instead of $X$ being irrational, consider a rational number with a large period, much larger than $p$ or $q$ (use same source code to produce the period) and let the period tends to infinity.

Answer 1

Not an easy question it seems. My answer here is still based on empirical evidence, but far easier to check. First, note that if we shift the digits of either $pX$ or $qX$ (that is by multiplying $pX$ or $qY$ by a power of two, positive or negative) any apparent cross-correlation in the two digit distributions vanishes. Only one particular shift produces a non-zero cross-correlation, and that's the shift produced when running the code posted in my question.

Here I will use the following notation:

• $b_k$ represents the $k$-th binary digit of $X$
• $d_k$ and $d'_k$ are the $k$-th binary digits of $pX$ and $qX$ respectively
• $e_k$ and $e'_k$ are auxiliary variables used in the computations, attached to $pX$ and $qX$ respectively

The digits satisfy the recursions

$$d_k=\mbox{mod}\Big(pb_k+ \frac{1}{2}e_{k+1},2\Big) , e_k=\frac{1}{2}e_{k+1} + pb_k - d_k$$

$$d'_k=\mbox{mod}\Big(qb_k+ \frac{1}{2}e'_{k+1},2\Big) , e'_k=\frac{1}{2}e'_{k+1} + qb_k - d'_k$$

In practice, assuming we compute the iterates in reverse order, starting with a large $k=N$ (say $N=10^6$) with $d_N=d'_N=e_N=e'_N=0$ all the way back to $k=0$, then all the digits except a couple of them at the very end (next to $k=N$) will be correct.

Based on empirical evidence, we observe that

• The sequences $\{d_k\}$ and $\{e_{k-1}\}$ are independent; same with $\{d'_k\}$ and $\{e'_{k-1}\}$
• The digits $b_k$ behave as i.i.d Bernouilli of parameter $\frac{1}{2}$, by design
• The terms in the sequences $e_k$ and $e'_k$ are uniformly distributed, respectively on $\{0, 2, 4,\cdots,2(p-1)\}$ and $\{0, 2, 4,\cdots,2(q-1)\}$

Thus the cross-correlation between the binary digit sequences $\{d_k\}$ and $\{d'_k\}$ is equal to

$$\rho=-1+\lim_{N\rightarrow\infty} \frac{4}{N}\sum_{k=0}^{N-1} d_k d'_k.$$

Note that $p, q$ are assumed to be odd co-prime integers. As a result, it is easy to prove that $d_k d'_k =1$ if and only if $\frac{1}{2}e_{k-1} = \frac{1}{2}e'_{k-1} \pmod{2} $, and otherwise $d_kd'_k = 0$.

Let us consider the $p\times q$ matrix $M$ defined as follows: $M_{ij}$ is a positive integer, with

• $M_{ij} = 0$ if and only if the joint event $e_{k-1} = 2i, e'_{k-1}=2j$ never occurs regardless of $k$. Otherwise $M_{ij}$ is strictly positive.
• The sum of the elements of $M$ in any row is equal to $q$
• The sum of the elements of $M$ in any column is equal to $p$

These three properties define $M$ uniquely. Let's $M^* = \frac{1}{pq}M$. Now $M^*_{ij}$ is the probability that $e_{k-1} = 2i$ and $e'_{k-1}=2j$ simultaneously, measured as the asymptotic frequency of this event computed on all observed $(e_k,e'_k)$. The probability $P$ that $d_kd'_k=1$ is the sum of the terms $M^*_{ij}$ over all indices $i,j$ with $i = j \pmod{2}$. And of course, the sum of all $M^*_{ij}$ (regardless of parity) is equal to $1$. To conclude, it suffices to prove that $P=\frac{pq +1}{2pq}$ and $\rho = 2P-1 = \frac{1}{pq}$.

Example

Here $p=7, q=11$. Non-null entries in $M$ are starred below, based on empirical evidence.

The above starred entries are based on counts computed on $10^6$ values of $(e_k,e'_k)$. These counts are featured in the table below. The binary digits $b_k$ were generated as i.i.d Bernouilli with parameter $\frac{1}{2}$ using the source code posted in my question.

The resulting matrix $M$ is as follows:

Below is the matrix $M$ for $p=31, q=71$: