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$ Commented Jan 24, 2024 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$ Commented Jan 24, 2024 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$ Commented Jan 24, 2024 at 16:23
  • 1
    $\begingroup$ How is "strongly regular" different from "normal"? Isn't what you wrote the definition of "normal"? $\endgroup$ Commented Jan 25, 2024 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$ Commented Jan 25, 2024 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.