Consider finite strings on a finite alphabet of size $b\ (\ge 2)$. Let's call such a finite string "$L$-normal" just if, for each $l\in\{1,2,...,L\}$, all $b^l$ possible length-$l$ substrings occur in it equally often.

NB: A "substring" consists of contiguous elements, and substrings may overlap; e.g., 00 occurs exactly twice in 00010, as (00)010 and as 0(00)10. E.g., the concatenation of 0 1 00 01 10 11 is $1$-normal but not $2$-normal.

Question: Do there exist $L$-normal finite strings with $L > 1$? In particular, are there such binary strings?

  • $\begingroup$ $00110$ is 2-normal. $\endgroup$ – J.-E. Pin Feb 15 '16 at 6:55
  • $\begingroup$ @J.-E.Pin - $00110$ is not $2$-normal, because not all length-$1$ substrings occur equally often. By the definition, $L$-normality requires that all length-$1$ substrings occur equally often, that all length-$2$ substrings occur equally often, etc., up to and including that all length-$L$ substrings occur equally often. $\endgroup$ – r.e.s. Feb 16 '16 at 4:10
  • $\begingroup$ Sorry, i missread the definition. $\endgroup$ – J.-E. Pin Feb 16 '16 at 6:31
  • $\begingroup$ I just arrived to the same conclusion for $L = b = 2$. Too late... But you should write your update as an answer. $\endgroup$ – J.-E. Pin Feb 16 '16 at 7:01
  • $\begingroup$ @J.-E.Pin - Thanks for your efforts. I've posted the update as an answer. $\endgroup$ – r.e.s. Feb 16 '16 at 13:59

I think the answer is "No". Here's my reasoning ...

Let $N_S(w)$ denote the number of times subword $w$ occurs in finite word $S$. Since there are exactly $|S|-|w|+1$ places for the subword to occur, $S$ is $L$-normal iff for each $l\in\{1,2,...,L\}$, $|S|-l+1 = N_S(w_l)\cdot b^l$, where $w_l$ denotes any length-$l$ word on the given alphabet of size $b$. Therefore, if $S$ is $L$-normal and has length $n$, then

$$\forall l\in\{1,\dots,L\},\ b^l \mid (n-l+1).$$

Now if $L>1$, this further implies that both $b\mid n$ and $b^2\mid (n-1)$; but $b^2\mid (n-1)$ implies $b\mid(n-1)$, contradicting $b\mid n$.

NB: Although this definition of $L$-normal finite strings is evidently vacuous for $L>1$, it leads to a non-vacuous parallel definition in the case of infinite strings. If $S$ is an infinite string on an alphabet of size $b$, it would be natural to say that $S$ is $L$-normal just if

$$\lim_{n\to\infty} \frac{N_S(w,n)}{n-|w|+1} \left(= \lim_{n\to\infty} \frac{N_S(w,n)}{n}\right) = \frac{1}{b^{|w|}}$$ for all finite words $w$ with $|w|\le L$, where now $N_S(w,n)$ is the number of times $w$ occurs as a subword in the first $n$ symbols of $S$. (Since the limit is being taken, the denominator on the LHS may be reduced to $n$, but it is $n-|w|+1$ that has the proper combinatorial interpretation as the number of possible places for the occurrence of subword $w$ in the first $n$ symbols of $S$.)

An infinite word is then normal in the standard sense iff it is $L$-normal for all positive integers $L$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.