Lesson plan

Disjunctive sequence

A disjunctive sequence is an infinite sequence of characters drawn from a finite alphabet, in which every finite string appears as a substring. For instance, the Champernowne constant defined by concatenating the base-10 representations of the positive integers: : clearly contains all the strings and so is disjunctive. 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 n 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. The complexity function of a disjunctive sequence S over an alphabet of size k is p S (n) = k n . A disjunctive sequence is recurrent but never uniformly recurrent/almost periodic.

Back to article

Article summary

A disjunctive sequence is an infinite sequence of characters drawn from a finite alphabet, in which every finite string appears as a substring. For instance, the Champernowne constant defined by concatenating the base-10 representations of the positive integers: : clearly contains all the strings and so is disjunctive. 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 n 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. The complexity function of a disjunctive sequence S over an alphabet of size k is p S (n) = k n . A disjunctive sequence is recurrent but never uniformly recurrent/almost periodic.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.