imported>Risee01: /* growthexperiments-addlink-summary-summary:2|0|1 */

2025-05-08T00:43:30Z

growthexperiments-addlink-summary-summary:2|0|1

New page

{{Short description|Sequence in which every finite string appears as a subsequence}}
A '''disjunctive sequence''' is an [[infinite sequence]] of [[character (computing)|characters]] drawn from a finite [[alphabet (computer science)|alphabet]], in which every [[String (computer science)#Formal theory|finite string]] appears as a [[substring]]. For instance, the binary [[Champernowne constant|Champernowne sequence]]

:<math>0\ 1\ 00\ 01\ 10\ 11\ 000\ 001 \ldots</math>

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''''n''.<ref name=Bug91>Bugeaud (2012) p.91</ref>

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

:<math>0\ 0^1\ 1\ 0^2\ 00\ 0^4\ 01\ 0^8\ 10\ 0^{16}\ 11\ 0^{32}\ 000\ 0^{64}\ldots</math>

obtained by splicing exponentially long strings of 0s into the [[shortlex order]]ing 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 word|recurrent]] but never uniformly recurrent/almost periodic.

==Examples==

The following result<ref>
{{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
| year = 1997 | citeseerx = 10.1.1.34.1370 }}</ref><ref>
{{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 | doi-access =
}}</ref> can be used to generate a variety of disjunctive sequences:

:If ''a''1, ''a''2, ''a''3, ..., is a strictly increasing infinite sequence of positive integers such that [[Limit of a sequence|{{mono|lim}}]] ''n'' → ∞ (''a''''n''+1 / ''a''''n'') = 1,
:then for any positive integer ''m'' and any integer [[Radix|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''1, ''a''2, ''a''3, ..., 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, {{mono|lim}} ''n'' → ∞ (''a''''n''+1 / ''a''''n'') = {{mono|lim}} ''n'' → ∞ ( (''n''+1)''k'' / ''n''''k'' ) = {{mono|lim}} ''n'' → ∞ (1 + 1/''n'')''k'' = 1.)
: E.g., using base-ten expressions, the sequences
:: 123456789101112... (''k'' = 1, [[natural numbers|positive natural number]]s),
:: 1491625364964... (''k'' = 2, [[square numbers|squares]]),
:: 182764125216343... (''k'' = 3, [[Cube (algebra)|cube]]s),
:: 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, {{mono|lim}} ''n'' → ∞ (''a''''n''+1 / ''a''''n'') = 1 is a consequence of [[Prime number theorem#Approximations for the nth prime number|''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<ref>{{citation
| last1 = Nakai | first1 = Yoshinobu | author1-link = Yoshinobu Nakai
| last2 = Shiokawa | first2 = Iekata | author2-link = Iekata Shiokawa
| journal = Acta Arithmetica
| pages = 271–284
| title = Discrepancy estimates for a class of normal numbers
| volume = LXII.3
| issue = 3 | url = http://matwbn.icm.edu.pl/ksiazki/aa/aa62/aa6235.pdf
| year = 1992 | doi = 10.4064/aa-62-3-271-284 | doi-access = free}}</ref> that provides a variety of disjunctive sequences is as follows:
:If ''a''''n'' = {{mono|[[Floor and ceiling functions|floor]]}}(''f''(''n'')), where ''f'' is any non-constant [[polynomial]] with [[Real number|real]] coefficients such that ''f''(''x'') > 0 for all ''x'' > 0,
:then the concatenation ''a''''1''''a''''2''''a''''3''... (with the ''a''''n'' expressed in base ''b'') is a [[Normal number#Definitions|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'') = 2''x''3 - 5''x''2 + 11''x'' )
:: 591215182124273034... (with ''f''(''x'') = [[pi|π]]''x'' + [[Euler's number|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 bn'' mod 1} is [[Dense set|dense]] in the [[unit interval]].<ref name=Bug92>Bugeaud (2012) p.92</ref>

{{anchor|Lexicon}} A number that is disjunctive to every base is called ''absolutely disjunctive'' or is said to be a ''lexicon''. Every [[String (computer science)|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.<ref name=CZ1999>Calude & Zamfirescu (1999)</ref> It is conjectured that every real irrational [[algebraic number]] is absolutely disjunctive.<ref name=AB414>Adamczewski & Bugeaud (2010) p.414</ref>

==Notes==
{{reflist}}

==References==
{{refbegin}}
*{{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 }}
{{refend}}

{{DEFAULTSORT:Disjunctive Sequence}}
[[Category:Sequences and series]]

Disjunctive sequence - Revision history

imported>Risee01: /* growthexperiments-addlink-summary-summary:2|0|1 */