Disjunctive sequence

A disjunctive sequence is an infinite sequence (over a finite alphabet of characters) in which every finite string appears as a substring. For instance, the binary Champernowne sequence

$0\ 1\ 00\ 01\ 10\ 11\ 000\ 001 \ldots$

formed by concatenating all binary strings in shortlex order, clearly contains all the binary strings and so is disjunctive. (The spaces above are not significant and are present solely to make clear the boundaries between strings).

Any normal sequence (a sequence in which each string of equal length appears with equal frequency) is disjunctive, but the converse is not true. For example, letting 0ⁿ denote the string of length n consisting of all 0s, consider the sequence

$0\ 0^1\ 1\ 0^2\ 00\ 0^4\ 01\ 0^8\ 10\ 0^{16}\ 11\ 0^{32}\ 000\ 0^{64}\ldots$

obtained by splicing exponentially long strings of 0s into the shortlex ordering of all binary strings. Most of this sequence consists of long runs of 0s, and so it is not normal, but it is still disjunctive.

Examples

The following result^[1][2] can be used to generate a variety of disjunctive sequences:

If a₁, a₂, a₃, ..., is a strictly increasing infinite sequence of positive integers such that lim _{n → ∞} (a_n+1 / a_n) = 1,

then for any positive integer m and any integer base b ≥ 2, there is an a_n whose expression in base b starts with the expression of m in base b.

(Consequently, the infinite sequence obtained by concatenating the base-b expressions for a₁, a₂, a₃, ..., is disjunctive over the alphabet {0, 1, ..., b-1}.)

Two simple cases illustrate this result:

• a_n = n^k, where k is a fixed positive integer. (In this case, lim _{n → ∞} (a_n+1 / a_n) = lim _{n → ∞} ( (n+1)^k / n^k ) = lim _{n → ∞} (1 + 1/n)^k = 1.)

E.g., using base-ten expressions, the sequences

123456789101112... (k = 1, positive natural numbers),

1491625364964... (k = 2, squares),

182764125216343... (k = 3, cubes),

etc.,

are disjunctive on {0,1,2,3,4,5,6,7,8,9}.

• a_n = p_n, where p_n is the n^th prime number. (In this case, lim _{n → ∞} (a_n+1 / a_n) = 1 is a consequence of p_n ~ n ln n.)

E.g., the sequences

23571113171923... (using base ten),

10111011111011110110001 ... (using base two),

etc.,

are disjunctive on the respective digit sets.

References

1. ^ Calude, C.; Priese, L.; Staiger, L. (1997), Disjunctive sequences: An overview, University of Auckland, New Zealand, pp. 1–35, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1370 
2. ^ Istrate, G.; Păun, Gh. (1994), "Some combinatorial properties of self-reading sequences", Discrete Applied Mathematics 55: 83–86, doi:10.1016/0166-218X(94)90037-X