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

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

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

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

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

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

Примеры

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

Если а1, а2, а3, ..., - это строго возрастающая бесконечная последовательность натуральных чисел такая, что Lim п → ∞ (ап+1 / ап) = 1,
тогда для любого положительного целого числа м и любое целое число основание б ≥ 2 существует ап чье выражение в базе б начинается с выражения м в базе б.
(Следовательно, бесконечная последовательность, полученная конкатенацией базовыхб выражения для а1, а2, а3, ..., дизъюнктивна по алфавиту {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}.
Например, последовательности
23571113171923 ... (по основанию десять),
10111011111011110110001 ... (с использованием второй базы),
так далее.,

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

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

Если ап = этаж(ж(п)), куда ж любая непостоянная многочлен с настоящий коэффициенты такие, что ж(Икс)> 0 для всех Икс > 0,
затем конкатенация а1а2а3... (с ап выражается в базе б) это нормальный последовательность в базе б, и поэтому дизъюнктивна на {0, 1, ..., б-1}.

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

818429218031851879211521610 ... (с ж(Икс) = 2Икс3 - 5Икс2 + 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

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