Дизъюнктивная последовательность
— Дизъюнктивная последовательность это бесконечная последовательность символов , взятая из конечного алфавита , в которой каждая конечная строка является подстрокой . Например, двоичная последовательность Чамперноуна
образованный путем объединения всех двоичных строк в коротком порядке , явно содержит все двоичные строки и поэтому является дизъюнктивным. (Пробелы выше не имеют значения и используются исключительно для обозначения границ между строками). Функция сложности дизъюнктивной последовательности S над алфавитом размера k равна p S ( n ) = k н . [1]
Любая нормальная последовательность (последовательность, в которой каждая строка одинаковой длины встречается с одинаковой частотой) является дизъюнктивной, но обратное неверно . Например, положив 0 н обозначим строку длины n, состоящую из всех нулей, рассмотрим последовательность
получается путем объединения экспоненциально длинных строк нулей в короткий порядок всех двоичных строк. Большая часть этой последовательности состоит из длинных серий нулей, поэтому она не является нормальной, но все же является дизъюнктивной.
Дизъюнктивная последовательность рекуррентна , но никогда не бывает равномерно повторяющейся/почти периодической.
Примеры
[ редактировать ]Следующий результат [2] [3] может использоваться для генерации различных дизъюнктивных последовательностей:
- Если a 1 , a 2 , a 3 , ... является строго возрастающей бесконечной последовательностью натуральных чисел такой, что lim n → ∞ ( a n +1 / a n ) = 1,
- тогда для любого положительного целого числа m и любого целого числа по основанию b ≥ 2 существует a n , выражение которого в базе b начинается с выражения m в базе b .
- (Следовательно, бесконечная последовательность, полученная путем объединения выражений с основанием b для a 1 , a 2 , a 3 , ..., является дизъюнктивной по алфавиту {0, 1, ..., b -1}.)
Два простых случая иллюстрируют этот результат:
- и п = п к , где k — фиксированное положительное целое число. (В этом случае, lim п → ∞ ( а п +1 / а п ) знак равно lim n → ∞ ( ( n +1) к / н к ) = lim n → ∞ (1 + 1/ n ) к = 1.)
- Например, при использовании десятичных выражений последовательности
- 123456789101112... ( k = 1, положительные натуральные числа ),
- 1491625364964... ( к = 2, квадраты ),
- 182764125216343... ( k =3, кубики ),
- и т. д.,
- дизъюнктивны на {0,1,2,3,4,5,6,7,8,9}.
- a n = p n , где p n — это n й простое число . (В этом случае, lim n → ∞ ( a n +1 / a n ) = 1 является следствием p n ~ n ln n .)
- Например, последовательности
- 23571113171923... (по основанию десять),
- 10111011111011110110001 ... (по основанию два),
- и т. д.,
являются дизъюнктивными в соответствующих наборах цифр.
Другой результат [4] который обеспечивает разнообразие дизъюнктивных последовательностей, выглядит следующим образом:
- Если n = Floor ( f ( n )), где f — любой непостоянный многочлен с действительными коэффициентами такой, что f ( x ) > 0 для всех x > 0,
- тогда конкатенация a 1 a 2 a 3 ... (с a n, выраженным по основанию b ) является нормальной последовательностью по основанию b и, следовательно, является дизъюнктивной на {0, 1, ..., b -1}.
Например, при использовании десятичных выражений последовательности
дизъюнктивны на {0,1,2,3,4,5,6,7,8,9}.
Богатые числа
[ редактировать ]Богатое число или дизъюнктивное число — это действительное число , разложение которого по некоторому основанию b представляет собой дизъюнктивную последовательность по алфавиту {0,..., b −1}. Каждое нормальное число по основанию b является дизъюнктивным, но не наоборот. Действительное число x богато по основанию b тогда и только тогда, когда набор { xb н mod 1} плотно в единичном интервале . [5]
Число, дизъюнктивное по любому основанию, называется дизъюнктивным или словарным абсолютно . Каждая строка в каждом алфавите встречается в словаре. Множество называется « соединяющим » или «остаточным», если оно содержит пересечение счетного семейства открытых плотных множеств. Множество абсолютно дизъюнктивных вещественных чисел является остаточным. [6] Предполагается, что всякое действительное иррациональное алгебраическое число абсолютно дизъюнктивно. [7]
Примечания
[ редактировать ]- ^ Бюжо (2012) стр.91
- ^ Калуд, К. ; Призе, Л .; Стайгер, Л. (1997), Дизъюнктивные последовательности: обзор , Университет Окленда, Новая Зеландия, стр. 1–35, CiteSeerX 10.1.1.34.1370.
- ^ Истрате, Г .; Паун, Г. (1994), «Некоторые комбинаторные свойства самосчитывающихся последовательностей», Discrete Applied Mathematics , 55 : 83–86, doi : 10.1016/0166-218X(94)90037-X , Zbl 0941.68656
- ^ Накаи, Ёсинобу ; Сиокава, Иеката (1992), «Оценки расхождения для класса нормальных чисел» (PDF) , Acta Arithmetica , LXII.3 (3): 271–284, doi : 10.4064/aa-62-3-271-284
- ^ Бюжо (2012) стр.92
- ^ Калуде и Замфиреску (1999)
- ^ Адамчевски и Бюжо (2010) стр.414
Ссылки
[ редактировать ]- Адамчевский, Борис; Бюжо, Янн (2010). «8. Трансцендентность и диофантово приближение». В Берте, Валери ; Риго, Майкл (ред.). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том. 135. Кембридж: Издательство Кембриджского университета . стр. 410–451. ISBN 978-0-521-51597-9 . Збл 1271.11073 .
- Бюжо, Янн (2012). Распределение по модулю единицы и диофантово приближение . Кембриджские трактаты по математике. Том. 193. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-11169-0 . Збл 1260.11001 .
- Калуде, CS ; Замфиреску, Т. (1999). «Большинство чисел не подчиняются законам вероятности». Публикации Mathematicae Дебрецен . 54 (Приложение): 619–623.