Дизъюнктивная последовательность - Disjunctive sequence - Wikipedia

А дизъюнктивная последовательность бесконечный последовательность (над конечным алфавит из символы ), в котором каждый конечная строка появляется как подстрока. Например, двоичный Последовательность Champernowne

${\displaystyle 0\ 1\ 00\ 01\ 10\ 11\ 000\ 001\ldots }$

формируется путем объединения всех двоичных строк в заказ шортлекс, явно содержит все двоичные строки и поэтому дизъюнктивен. (Пробелы выше не имеют значения и используются только для того, чтобы прояснить границы между строками). В функция сложности дизъюнктивной последовательности S над алфавитом размера k является п_S(п) = k^п.^[1]

Любой нормальная последовательность (последовательность, в которой каждая строка одинаковой длины появляется с одинаковой частотой) дизъюнктивна, но разговаривать не правда. Например, если 0^п обозначают строку длины п состоящую из всех нулей, рассмотрим последовательность

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

полученный путем сращивания экспоненциально длинных цепочек нулей в заказ шортлекс всех двоичных строк. Большая часть этой последовательности состоит из длинных серий нулей, поэтому это ненормально, но все же дизъюнктивно.

Дизъюнктивная последовательность повторяющийся но никогда не бывает равномерно повторяющимся / почти периодическим.

Примеры

Следующий результат^[2][3] можно использовать для генерации множества дизъюнктивных последовательностей:

Если а₁, а₂, а₃, ..., - это строго возрастающая бесконечная последовательность натуральных чисел такая, что Lim _{п → ∞} (а_п+1 / а_п) = 1,

тогда для любого положительного целого числа м и любое целое число основание б ≥ 2 существует а_п чье выражение в базе б начинается с выражения м в базе б.

(Следовательно, бесконечная последовательность, полученная конкатенацией базовыхб выражения для а₁, а₂, а₃, ..., дизъюнктивна по алфавиту {0, 1, ..., б-1}.)

Этот результат иллюстрируют два простых случая:

• а_п = п^k, куда k - фиксированное положительное целое число. (В этом случае, Lim _{п → ∞} (а_п+1 / а_п) = Lim _{п → ∞} ( (п+1)^k / п^k ) = Lim _{п → ∞} (1 + 1/п)^k = 1.)

Например, используя выражения с основанием десять, последовательности

123456789101112... (k = 1, положительные натуральные числа ),

1491625364964... (k = 2, квадраты ),

182764125216343... (k = 3, кубики ),

так далее.,

дизъюнктивны на {0,1,2,3,4,5,6,7,8,9}.

• а_п = п_п, куда п_п это п^th простое число. (В этом случае, Lim _{п → ∞} (а_п+1 / а_п) = 1 является следствием п_п ~ п пер п.)

Например, последовательности

23571113171923 ... (по основанию десять),

10111011111011110110001 ... (с использованием второй базы),

так далее.,

дизъюнктивны на соответствующих наборах цифр.

Другой результат^[4] который обеспечивает множество дизъюнктивных последовательностей, выглядит следующим образом:

Если а_п = этаж(ж(п)), куда ж любая непостоянная многочлен с настоящий коэффициенты такие, что ж(Икс)> 0 для всех Икс > 0,

затем конкатенация а₁а₂а₃... (с а_п выражается в базе б) это нормальный последовательность в базе б, и поэтому дизъюнктивна на {0, 1, ..., б-1}.

Например, используя выражения с основанием десять, последовательности

818429218031851879211521610 ... (с ж(Икс) = 2Икс³ - 5Икс² + 11Икс )

591215182124273034 ... (с ж(Икс) = πИкс + е )

дизъюнктивны на {0,1,2,3,4,5,6,7,8,9}.

Богатые числа

А богатое число или же дизъюнктивное число это настоящий номер чье разложение по некоторой базе б дизъюнктивная последовательность над алфавитом {0, ...,б−1}. Каждый нормальный номер в базе б дизъюнктивно, но не наоборот. Настоящее число Икс богат базой б тогда и только тогда, когда множество { х б^п mod 1} - это плотный в единичный интервал.^[5]

Число, дизъюнктивное для каждой базы, называется абсолютно дизъюнктивный или называется лексикон. Каждый нить в каждом алфавите встречается в лексиконе. Набор называется "пришелец "или" остаточный ", если он содержит пересечение счетного семейства открытых плотных множеств. Множество абсолютно дизъюнктивных вещественных чисел остаточно.^[6] Предполагается, что любое вещественное иррациональное алгебраическое число абсолютно дизъюнктивно.^[7]

Примечания

1. Бюжо (2012) стр.91
2. Калуд, К.; Приезе, Л.; Штайгер, Л. (1997), Дизъюнктивные последовательности: обзор, Оклендский университет, Новая Зеландия, стр. 1–35, CiteSeerX  10.1.1.34.1370
3. Истрате, Г.; Păun, Gh. (1994), "Некоторые комбинаторные свойства самочитающихся последовательностей", Дискретная прикладная математика, 55: 83–86, Дои:10.1016 / 0166-218X (94) 90037-X, Zbl  0941.68656
4. Накаи, Ёсинобу; Сиокава, Иеката (1992), «Несоответствие оценок для класса нормальных чисел» (PDF), Acta Arithmetica, LXII.3 (3): 271–284, Дои:10.4064 / aa-62-3-271-284
5. Бюжо (2012) стр.92
6. Калуд и Замфиреску (1999)
7. Адамчевски и Бюжо (2010), стр.414

Рекомендации

• Адамчевский, Борис; Бюжо, Янн (2010). «8. Трансцендентность и диофантово приближение». В Берте, Валери; Риго, Майкл (ред.). Комбинаторика, автоматы и теория чисел. Энциклопедия математики и ее приложений. 135. Кембридж: Издательство Кембриджского университета. С. 410–451. ISBN  978-0-521-51597-9. Zbl  1271.11073.
• Бюжо, Янн (2012). Распределение по модулю один и диофантово приближение. Кембриджские трактаты по математике. 193. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-11169-0. Zbl  1260.11001.
• Калуд, К.С.; Замфиреску, Т. (1999). «Большинство чисел не подчиняются законам вероятности». Publicationes Mathematicae Debrecen. 54 (Дополнение): 619–623.