"L-normal" finite strings?

83 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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$.