“Disjunctive sequence”的意思、由来-开放百科全书

词条 Disjunctive sequence

释义

Examples
Rich numbers
Notes
References

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

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). The complexity function of a disjunctive sequence S over an alphabet of size k is p_S(n) = kⁿ.^[1]

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

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^[2]^[3] 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.

Another result^[4] that provides a variety of disjunctive sequences is as follows:

If a_n = floor(f(n)), where f is any non-constant polynomial with real coefficients such that f(x) > 0 for all x > 0,

then the concatenation a₁a₂a₃... (with the a_n expressed in base b) is a normal sequence in base b, and is therefore disjunctive on {0, 1, ..., b-1}.

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

818429218031851879211521610... (with f(x) = 2x³ - 5x² + 11x )

591215182124273034... (with f(x) = πx + e)

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

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 {0,...,b−1}. 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 { x bⁿ mod 1} is dense in the unit interval.^[5]

{{anchor|Lexicon}} 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.^[6] It is conjectured that every real irrational algebraic number is absolutely disjunctive.^[7]

Notes

1. ^Bugeaud (2012) p.91
2. ^{{citation | last1 = Calude | first1 = C. | author1-link = Cristian S. Calude | last2 = Priese | first2 = L. | author2-link = Lutz Priese | last3 = Staiger | first3 = L. | author3-link = Ludwig Staiger | publisher = University of Auckland, New Zealand | pages = 1–35 | title = Disjunctive sequences: An overview | url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1370 | year = 1997 }}
3. ^{{citation | last1 = Istrate | first1 = G. | author1-link = Gabriel Istrate | last2 = Păun | first2 = Gh. | author2-link = Gheorghe Păun | journal = Discrete Applied Mathematics | pages = 83–86 | title = Some combinatorial properties of self-reading sequences | volume = 55 | doi = 10.1016/0166-218X(94)90037-X | year = 1994 | zbl=0941.68656 }}
4. ^http://matwbn.icm.edu.pl/ksiazki/aa/aa81/aa8143.pdf
5. ^Bugeaud (2012) p.92
6. ^Calude & Zamfirescu (1999)
7. ^Adamczewski & Bugeaud (2010) p.414

References

{{cite book | last1=Adamczewski | first1=Boris | last2=Bugeaud | first2=Yann | chapter=8. Transcendence and diophantine approximation | editor1-last=Berthé | editor1-first=Valérie | editor1-link = Valérie Berthé | editor2-last=Rigo | editor2-first=Michael | title=Combinatorics, automata, and number theory | location=Cambridge | publisher=Cambridge University Press | series=Encyclopedia of Mathematics and its Applications | volume=135 | pages=410–451 | year=2010 | isbn=978-0-521-51597-9 | zbl=1271.11073}}
{{cite book | last=Bugeaud | first=Yann | title=Distribution modulo one and Diophantine approximation | series=Cambridge Tracts in Mathematics | volume=193 | location=Cambridge | publisher=Cambridge University Press | year=2012 | isbn=978-0-521-11169-0 | zbl= 1260.11001}}
{{cite journal | last1 = Calude | first1 = C.S.| author-link = Cristian S. Calude | last2 = Zamfirescu | first2 = T. | issue = Supplement | journal = Publicationes Mathematicae Debrecen | pages = 619–623 | title = Most numbers obey no probability laws | volume = 54 | year = 1999 | zbl= }}

1 : Sequences and series

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。