Disjunctive sequence


A disjunctive sequence is an infinite sequence in which every finite string appears as a substring. For instance, the binary Champernowne sequence
formed by concatenating all binary strings in shortlex order, clearly contains all the binary strings and so is disjunctive.. The complexity function of a disjunctive sequence S over an alphabet of size k is pS = kn.
Any normal sequence is disjunctive, but the converse is not true. For example, letting 0n denote the string of length n consisting of all 0s, consider the sequence
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.
A disjunctive sequence is recurrent but never uniformly recurrent/almost periodic.

Examples

The following result can be used to generate a variety of disjunctive sequences:
Two simple cases illustrate this result:
are disjunctive on the respective digit sets.
Another result that provides a variety of disjunctive sequences is as follows:
E.g., using base-ten expressions, the sequences
are disjunctive on.

Rich numbers

A rich number or disjunctive number is a real number whose expansion with respect to some base b is a disjunctive sequence over the alphabet. Every normal number in base b is disjunctive but not conversely. The real number x is rich in base b if and only if the set is dense in the unit interval.
A number that is disjunctive to every base is called absolutely disjunctive or is said to be a lexicon. Every string in every alphabet occurs within a lexicon. A set is called "comeager" or "residual" if it contains the intersection of a countable family of open dense sets. The set of absolutely disjunctive reals is residual. It is conjectured that every real irrational algebraic number is absolutely disjunctive.