1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Do you want an explicit sequence? Because, stupidly, a random one almost surely works. $\endgroup$
    – Aleksei Kulikov
    Commented Jan 24 at 14:36
  • $\begingroup$ Yes, it would be nice to see an explicit sequence like Champernowne sequence - it is well possible that this one already works. $\endgroup$
    – Dominic van der Zypen
    Commented Jan 24 at 16:18
  • 1
    $\begingroup$ Take a de Bruijn sequence for length $1$, repeat it often enough, concatenate one for for length $2$, also repeated often enough, then for length $3$, etc. I think this should work (but it's perhaps not quite obvious exactly what bounds we'll get). $\endgroup$
    – Gro-Tsen
    Commented Jan 24 at 16:23
  • 1
    $\begingroup$ How is "strongly regular" different from "normal"? Isn't what you wrote the definition of "normal"? $\endgroup$
    – bof
    Commented Jan 25 at 3:19
  • 2
    $\begingroup$ I guess there was nothing wrong with my deleted answer. I deleted it because I thought I must have misunderstood something, since I couldn't see any difference between "strongly regular" and "normal". $\endgroup$
    – bof
    Commented Jan 25 at 8:26

1 Answer 1

Reset to default
3
$\begingroup$

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)

Improve this answer
$\endgroup$

You must log in to answer this question.

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