Strongly Regular Binary Sequences in Measure Theory and Combinatorics

infinite-combinatoricsinteger-sequencesmeasure-theorysequences-and-series

Let $\mathbb{N} = \{0,1,2,\ldots\}$ denote the set of non-negative integers. If $n\in\mathbb{N}$ we let $[n] = \{0,\ldots,n-1\}$. For $A
\subseteq \mathbb{N}$
we let $$\mu^+(A) = \lim\sup_{n\to\infty}\frac{|A\cap [n+1]|}{n+1}, $$ and $\mu^-(A)$ is defined in the same way, except $\sup$ is replaced by $\inf$.

Suppose that $b:\mathbb{N}\to\{0,1\}$ is a (binary) sequence, let $n\in \mathbb{N}\setminus\{0\}$ be a positive integer, and let $s\in\{0,1\}^n$ be a finite binary string. We define the set of starting points of $s$ in $b$ by $$\text{start}(s,b) = \{k\in \mathbb{N}: b(j) = s(k+j) \text{ for all }j\in [n]\}.$$ We say $s$ has a fair occurrence in $b$ if $$\mu^+(\text{start}(s)) = \mu^-(\text{start}(s)) = 1/2^n.$$ Finally we call $b:\mathbb{N}\to\{0,1\}$ strongly regular if whenever $n$ is a positive integer and $s\in\{0,1\}^n$, then $s$ has a fair occurrence in $s$.

This concept is related (but possibly not equivalent) to normalcy.

Question. What is an example of a strongly regular binary sequence $b:\mathbb{N}\to\{0,1\}$?

Note. A candidate might be the binary Champernowne constant $C_2$, which is normal, but I don't know if it is strongly regular.

Best Answer

As suggested in the comments, unless I'm mistaken, $b:\mathbb{N}\to\{0,1\}$ is strongly regular in your sense if and only if the number $0.b(0)b(1)\ldots$ is normal in base $2$.

Indeed, considering Wikipedia's formulation of normalcy: if $w$ is a finite binary string of length $k$ and $n\geq 1$, we write $N_b(w,n)$ for the number of times $w$ appears as a substring of $b(0)\cdots b(n-1)$; we then say that $0.b(0)b(1)\ldots$ is normal (in base $2$) if $\lim_{n\to\infty}\frac{N_b(w,n)}{n}=2^{-k}$ for each $k\geq 1$ and $w$ of length $k$.

But note that $|N_b(w,n)|\leq|\mathrm{start}(s,b)\cap[0,n-1]|\leq |N_b(w,n+k)|$, so we immediately have $\frac{N_b(w,n)}{n}\to 2^{-k}$ if and only if $\frac{|\mathrm{start}(s,b)\cap[0,n-1]|}{n}\to 2^{-k}$.

So, to answer your question: any number that is normal in base $2$ gives a strongly regular sequence (and conversely)

Related Question