Number with all digits equally frequent
В математике вещественное число называется просто нормальным в целочисленной базе b [1], если его бесконечная последовательность цифр распределена равномерно в том смысле, что каждое из значений b цифр имеет одинаковую естественную плотность 1/ b . Число называется нормальным по основанию b , если для каждого положительного целого числа n все возможные строки длиной n цифр имеют плотность b − n .
Интуитивно, если число просто нормальное, это означает, что ни одна цифра не встречается чаще, чем любая другая. Если число нормальное, никакая конечная комбинация цифр заданной длины не встречается чаще, чем любая другая комбинация той же длины. Нормальное число можно рассматривать как бесконечную последовательность подбрасываний монеты ( двоичная система ) или бросков игральной кости ( основание 6 ). Несмотря на то, что будут такие последовательности, как 10, 100 или более последовательных решек (двоичная система) или пятёрки (по основанию 6), или даже 10, 100 или более повторений такой последовательности, как решка-голова (два последовательных подбрасывания монеты) или 6 -1 (два последовательных броска игральной кости), также будет равно много любой другой последовательности равной длины. Никакая цифра или последовательность не являются «предпочтительными».
Число называется нормальным ( иногда его называют абсолютно нормальным ), если оно нормально во всех целочисленных основаниях, больших или равных 2.
Хотя можно дать общее доказательство того, что почти все действительные числа нормальны (это означает, что множество ненормальных чисел имеет нулевую меру Лебега ), это доказательство не является конструктивным , и было показано, что только несколько конкретных чисел являются нормальный. Например, любая константа Чайтина является нормальной (и невычислимой ). Широко распространено мнение, что (вычислимые) числа √ 2 , π и e нормальны, но доказательство остается неясным. [3]
Определения
Пусть Σ — конечный алфавит из b -цифр, Σ ω — множество всех бесконечных последовательностей , которые можно извлечь из этого алфавита, и Σ ∗ — множество конечных последовательностей или строк . [4] Пусть S ∈ Σ ω — такая последовательность. Для каждого a в Σ пусть N S ( a , n ) обозначает количество раз, когда цифра a появляется в первых n цифрах последовательности S. Мы говорим, что S просто нормально , если предел
для каждого а . Теперь пусть w — любая конечная строка из Σ ∗ , а N S ( w , n ) — количество раз, когда строка w появляется в качестве подстроки в первых n цифрах последовательности S. (Например, если S = 01010101 ... , то N S ( 010 , 8) = 3. ) S является нормальным , если для всех конечных строк w ∈ Σ ∗
где | ш | обозначает длину строки w . Другими словами, S является нормальным, если все строки одинаковой длины встречаются с одинаковой асимптотической частотой. Например, в нормальной двоичной последовательности (последовательность в алфавите { 0 , 1 } ) каждый из 0 и 1 встречается с частотой 1/2 ; 00 , 01 , 10 и 11 каждый встречается с частотой 1/4 ; 000 , 001 , 010 , 011 , 100 , 101 , 110 и 111 каждый встречается с частотой 1/8 ; и т. д. Грубо говоря, вероятность найти строку w в любой заданной позиции в S точно такая же, как и ожидалось, если бы последовательность была создана случайным образом .
Предположим теперь, что b — целое число , большее 1, а x — действительное число . Рассмотрим разложение бесконечной последовательности цифр S x , b числа x в позиционной системе счисления по основанию b (мы игнорируем десятичную точку). Мы говорим, что x просто нормален по основанию b, если последовательность S x , b просто нормальна , и что x нормален по базе b , если последовательность S x , b нормальна. Число x называется нормальным числом (или иногда абсолютно нормальным числом ), если оно нормально по основанию b для любого целого числа b , большего 1.
Данная бесконечная последовательность либо нормальна, либо ненормальна, тогда как действительное число, имеющее разное разложение по основанию b для каждого целого числа b ≥ 2 , может быть нормальным в одном основании, но не в другом (в этом случае это не обычное число). Для баз r и s с рациональным log r /log s (так что r = b m и s = bn ) каждое число, нормальное в базе r, является нормальным в базе s . Для оснований r и s с иррациональным log r / log s в каждом основании имеется несчетное количество чисел, нормальных, но не в другом.
Дизъюнктивная последовательность — это последовательность, в которой присутствует каждая конечная строка. Нормальная последовательность является дизъюнктивной, но дизъюнктивная последовательность не обязательно должна быть нормальной. Богатое число по основанию b — это число, разложение которого по основанию b является дизъюнктивным: число, которое дизъюнктивно по отношению к каждому основанию, называется абсолютно дизъюнктивным или называется словарем . Число, нормальное по основанию b, является богатым по основанию b , но не обязательно наоборот. Действительное число x богато базой b тогда и только тогда , когда множество { x b n mod 1: n ∈ N } плотно в единичном интервале . [12]
Мы определили, что число является просто нормальным по основанию b , если каждая отдельная цифра появляется с частотой 1 ⁄ b . Для данной базы b число может быть просто нормальным (но не нормальным или b -плотным, [ необходимо пояснение ] ), b -плотным (но не просто нормальным или нормальным), нормальным (и, следовательно, просто нормальным и b -плотным), или ничего из этого. Число является абсолютно ненормальным или абсолютно ненормальным, если оно не является просто нормальным ни по одному основанию.
Свойства и примеры
Понятие нормального числа было введено Эмилем Борелем (1909). Используя лемму Бореля–Кантелли , он доказал, что почти все действительные числа нормальны, установив существование нормальных чисел. Вацлав Серпинский (1917) показал, что можно указать конкретное такое число. Бехер и Фигейра (2002) доказали, что существует вычислимое абсолютно нормальное число. Хотя эта конструкция не дает непосредственно цифр построенных чисел, она показывает, что в принципе можно пересчитать каждую цифру того или иного нормального числа.
Набор ненормальных чисел, несмотря на то, что он «большой» в смысле несчетности , также является нулевым набором (поскольку его мера Лебега как подмножества действительных чисел равна нулю, поэтому он по существу не занимает места внутри действительного числа). цифры). Кроме того, ненормальные числа (как и нормальные числа) плотны в действительных числах: множество ненормальных чисел между двумя различными действительными числами непусто, поскольку оно содержит каждое рациональное число (фактически оно неисчислимо). бесконечен и даже сходится ). Например, существует бесчисленное множество чисел, десятичное представление которых (по основанию 3 или выше) не содержит цифры 1, и ни одно из этих чисел не является нормальным.
Постоянная Чамперноуна
0.1234567891011121314151617181920212223242526272829...,
полученный путем объединения десятичных представлений натуральных чисел по порядку, является нормальным по основанию 10. Аналогично, различные варианты константы Чамперноуна (выполненные путем выполнения того же объединения в других основаниях) являются нормальными в своих соответствующих основаниях (например, основание -2 Константы Чамперноуна являются нормальными для основания 2), но их нормальность в других основаниях не доказана.
Константа Коупленда – Эрдеша
0.23571113171923293137414347535961677173798389...,
полученное путем объединения простых чисел по основанию 10, является нормальным по основанию 10, как доказали А. Х. Коупленд и Пол Эрдеш (1946). В более общем плане последние авторы доказали, что действительное число, представленное в базе b путем конкатенации
0. ж (1) ж (2) ж (3)...,
где f ( n ) — n-е простое число, выраженное по основанию b , является нормальным по основанию b . Безикович (1935) доказал, что число, представленное одним и тем же выражением, с f ( n ) = n 2 ,
0,149162536496481100121144...,
полученное путем объединения квадратных чисел по основанию 10, является нормальным по основанию 10. Гарольд Давенпорт и Эрдеш (1952) доказали, что число, представленное одним и тем же выражением, где f представляет собой любой непостоянный многочлен, значения которого в положительных целых числах являются положительными целыми числами. , выраженное по основанию 10, является нормальным по основанию 10.
Накаи и Сиокава (1992) доказали, что если f ( x ) — любой непостоянный многочлен с действительными коэффициентами такой, что f ( x ) > 0 для всех x > 0, то действительное число, представленное конкатенацией
0.[ ж (1)][ ж (2)][ ж (3)]...,
где [ f ( n )] — целая часть f ( n ) , выраженная в базе b , является нормальной в базе b . (Этот результат включает в себя в качестве частных случаев все вышеупомянутые результаты Чамперноуна, Безиковича, Давенпорта и Эрдеша.) Авторы также показывают, что тот же результат справедлив даже в более общем случае, когда f — любая функция вида
ж ( Икс ) знак равно α · Икс β + α 1 · Икс β 1 + ... + α d · Икс β d ,
где αs и βs — действительные числа с β > β 1 > β 2 > ... > β d ≥ 0 и f ( x ) > 0 для всех x > 0.
Бэйли и Крэндалл (2002) показывают явный несчетный бесконечный класс b -нормальных чисел, возмущая числа Стоунхэма .
Доказать нормальность чисел, которые не были созданы искусственно, было труднодостижимой целью. Хотя √ 2 , π , ln(2) и e строго предполагаются нормальными, до сих пор неизвестно, нормальны они или нет. Не было даже доказано, что все цифры на самом деле встречаются бесконечно много раз в десятичных разложениях этих констант (например, в случае π популярное утверждение «каждая строка чисел в конечном итоге встречается в π» не является верным). ). Также высказывалась гипотеза, что каждое иррациональное алгебраическое число абсолютно нормально (что означало бы, что √ 2 нормально), и ни в одной базе не известны контрпримеры. Однако не было доказано, что ни одно иррациональное алгебраическое число является нормальным в каком-либо основании.
Мартин (2001) приводит пример иррационального числа, которое является абсолютно ненормальным. Пусть
Тогда α — число Лиувилля и абсолютно ненормально.
Ненормальные числа
Никакое рациональное число не является нормальным ни в одной системе счисления, поскольку последовательности цифр рациональных чисел в конечном итоге являются периодическими .
Характеристики
Дополнительные свойства нормальных чисел включают в себя:
- Каждое ненулевое действительное число является произведением двух нормальных чисел. Это следует из того общего факта, что каждое число является произведением двух чисел из множества, если дополнение к X имеет меру 0.
- Если x нормально по основанию b и a ≠ 0 — рациональное число, то оно также нормально по основанию b .
- Если плотно (для каждого и для всех достаточно больших n , ) и являются разложениями по основанию b элементов A , то число , образованное конкатенацией элементов A , является нормальным по базе b (Copeland and Erdős 1946) . Отсюда следует, что число Чамперноуна нормально по основанию 10 (поскольку множество всех натуральных чисел очевидно плотно) и что константа Коупленда–Эрдёша нормальна по основанию 10 (поскольку из теоремы о простых числах следует, что множество простых чисел плотно). ).
- Последовательность является нормальной тогда и только тогда, когда каждый блок одинаковой длины появляется с одинаковой частотой. (Блок длины k — это подстрока длины k , появляющаяся в позиции последовательности, кратной k : например, первый блок длины k в S — это S [1.. k ], второй блок длины k есть S [ k +1..2 k ] и т. д.) Это подразумевалось в работе Зива и Лемпеля (1978) и явно выражено в работе Бурка, Хичкока и Винодчандрана (2005).
- Число является нормальным по основанию b тогда и только тогда , когда оно просто нормально по основанию bk для всех . Это следует из предыдущей характеристики нормальности блока: поскольку n -й блок длины k в его разложении по основанию b соответствует n -й цифре в его разложении по основанию b k , число является просто нормальным по базе b k тогда и только тогда, когда блоки длины k появляются в разложении по основанию b с одинаковой частотой.
- Число является нормальным тогда и только тогда, когда оно просто нормально по любому основанию. Это следует из предыдущей характеристики нормальности по основанию b .
- Число является b -нормальным тогда и только тогда, когда существует набор натуральных чисел, где это число просто нормально по основаниям b m для всех Никакого конечного множества недостаточно, чтобы показать, что это число b - нормально.
- Все нормальные последовательности замкнуты при конечных вариациях : добавление, удаление или изменение конечного числа цифр в любой нормальной последовательности делает ее нормальной. Аналогично, если конечное число цифр добавляется, удаляется или изменяется в любой просто нормальной последовательности, новая последовательность все равно остается просто нормальной.
Подключение к конечным автоматам
Агафонов показал раннюю связь между конечными автоматами и нормальными последовательностями: каждая бесконечная подпоследовательность, выбранная из нормальной последовательности регулярным языком, также является нормальной. Другими словами, если кто-то запускает конечный автомат в нормальной последовательности, где каждое из состояний конечного автомата помечено либо «выход», либо «нет выхода», и машина выводит цифру, которую она читает следующей после ввода состояние «вывод», но не выводит следующую цифру после входа в состояние «нет вывода», тогда выводимая последовательность будет нормальной.
Более глубокая связь существует с игроками с конечным состоянием (FSG) и компрессорами с конечными состояниями без потерь информации (ILFSC).
- Игрок с конечным числом состояний (также известный как мартингал с конечным числом состояний ) — это конечный автомат с конечным алфавитом , каждое из состояний которого помечено процентами денег, которые можно поставить на каждую цифру в . Например, для FSG в двоичном алфавите текущее состояние q ставит некоторый процент денег игрока на бит 0, а оставшуюся часть денег игрока на бит 1. Ставка денег на цифру, которая идет следующей в вводимые данные (общая сумма денег, умноженная на процент ставки) умножаются на , а остальная часть денег теряется. После считывания бита FSG переходит в следующее состояние в соответствии с полученным входным сигналом. FSG d добивается успеха в бесконечной последовательности S, если, начиная с $1, он делает неограниченные ставки на эту последовательность; то есть, если
где — сумма денег, которую получает игрок d после прочтения первых n цифр S (см. верхний предел ). - Компрессор с конечным числом состояний — это конечный автомат с выходными строками, обозначающими переходы состояний , включая, возможно, пустую строку. (Поскольку для каждого перехода состояний из входной последовательности считывается одна цифра, необходимо иметь возможность выводить пустую строку, чтобы вообще добиться какого-либо сжатия). Компрессор с конечным состоянием без потерь информации — это компрессор с конечным состоянием, входные данные которого могут быть однозначно восстановлены из его выходного и конечного состояния. Другими словами, для компрессора C с конечным состоянием с набором состояний Q C является без потерь информации , если функция , отображающая входную строку C в выходную строку и конечное состояние C , равна 1–1 . Методы сжатия, такие как кодирование Хаффмана или кодирование Шеннона-Фано, могут быть реализованы с помощью ILFSC. ILFSC C сжимает бесконечную последовательность S , если
где — количество цифр, выводимых C после чтения первых n цифр S. Степень сжатия ( нижний предел, указанный выше) всегда можно сделать равным 1 с помощью ILFSC с 1 состоянием, который просто копирует свои входные данные на выходные.
Шнорр и Стимм показали, что ни одна ФСГ не может добиться успеха в любой нормальной последовательности, а Бурк, Хичкок и Винодчандран показали обратное . Поэтому:
Последовательность является нормальной тогда и только тогда, когда не существует игрока с конечным числом состояний, добившегося успеха в ней.
Зив и Лемпель показали:
Последовательность является нормальной тогда и только тогда, когда она несжимаема любым конечным компрессором без потерь информации.
(на самом деле они показали, что оптимальная степень сжатия последовательности для всех ILFSC — это именно степень ее энтропии , количественная мера ее отклонения от нормальности, которая равна 1 именно тогда, когда последовательность нормальна). Поскольку алгоритм сжатия LZ сжимает асимптотически так же хорошо, как и любой ILFSC, это означает, что алгоритм сжатия LZ может сжимать любую ненормальную последовательность.
Эти характеристики нормальных последовательностей можно интерпретировать как означающие, что «нормальный» = «случайный с конечным состоянием»; т. е. нормальные последовательности — это именно те последовательности, которые кажутся случайными для любого конечного автомата. Сравните это с алгоритмически случайными последовательностями , которые представляют собой те бесконечные последовательности, которые кажутся случайными для любого алгоритма (и фактически имеют схожие характеристики игры и сжатия с машинами Тьюринга, заменяющими конечные автоматы).
Подключение к равнораспределенным последовательностям
Число x является нормальным в базе b тогда и только тогда, когда последовательность равномерно распределена по модулю 1, или, что то же самое, с использованием критерия Вейля , тогда и только тогда, когда
Эта связь приводит к терминологии, согласно которой x является нормальным по основанию β для любого действительного числа β тогда и только тогда, когда последовательность равномерно распределена по модулю 1.
Примечания
Смотрите также
Рекомендации
- Адамчевский, Борис; Бюжо, Ян (2010), «8. Трансцендентность и диофантова аппроксимация», в Берте, Валери ; Риго, Майкл (ред.), Комбинаторика, автоматы и теория чисел , Энциклопедия математики и ее приложений, том. 135, Кембридж: Издательство Кембриджского университета , стр. 410–451, ISBN. 978-0-521-51597-9, Збл 1271.11073
- Агафонов, В. Н. (1968), "Нормальные последовательности и конечные автоматы", Советская математика - Доклады , 9 : 324–325, Збл 0242.94040
- Бейли, Дэвид Х .; Борвейн, Джонатан М .; Калуде, Кристиан С .; Диннин, Майкл Дж.; Думитреску, Моника; Йи, Алекс (2012), «Эмпирический подход к нормальности числа π», Experimental Mathematics , 21 (4): 375–384, doi : 10.1080/10586458.2012.665333, hdl : 2292/10566 , S2CID 17273684
- Бейли, DH ; Крэндалл, RE (2002), «Случайные генераторы и нормальные числа» (PDF) , Experimental Mathematics , 11 (4): 527–546, doi : 10.1080/10586458.2002.10504704, S2CID 8944421
- Бехер, В.; Фигейра, С. (2002), «Пример вычислимого абсолютно нормального числа» (PDF) , Theoretical Computer Science , 270 (1–2): 947–958, doi : 10.1016/S0304-3975(01)00170-0 , HDL : 20.500.12110/paper_03043975_v270_n1-2_p947_Becher
- Бек, Йожеф (2009), Неизбежная случайность в дискретной математике (иллюстрированное издание), American Mathematical Soc., стр. 13, ISBN 978-0-8218-4756-5
- Безикович, А.С. (1935), «Асимптотическое распределение цифр в десятичном представлении квадратов натуральных чисел», Mathematische Zeitschrift , 39 : 146–156, doi : 10.1007/BF01201350, S2CID 123025145
- Биллингсли, Патрик (2012), Вероятность и мера (юбилейное издание), Хобокен, Нью-Джерси: Wiley, стр. 15, ISBN 9781118122372, OCLC 780289503
- Борель, Э. (1909), «Les probilités dénombrables et leurs application arithmétiques», Rendiconti del Circolo Matematico di Palermo , 27 : 247–271, doi : 10.1007/BF03019651, S2CID 184479669
- Бурк, К.; Хичкок, Дж. М.; Винодчандран, Невада (2005), «Уровни энтропии и размерность конечного состояния», Theoretical Computer Science , 349 (3): 392–406, CiteSeerX 10.1.1.101.7244 , doi : 10.1016/j.tcs.2005.09.040
- Бюжо, Янн (2012), Распределение по модулю один и диофантово приближение , Cambridge Tracts in Mathematics, vol. 193, Кембридж: Издательство Кембриджского университета , ISBN 978-0-521-11169-0, Збл 1260.11001
- Кассельс, JWS (1959), «К проблеме Штейнгауза о нормальных числах», Colloquium Mathematicum , 7 : 95–101, doi : 10.4064/cm-7-1-95-101
- Чамперноун, Д.Г. (1933), «Построение нормальных десятичных дробей в десятичной шкале», Журнал Лондонского математического общества , 8 (4): 254–260, doi : 10.1112/jlms/s1-8.4.254
- Коупленд, США ; Эрдеш, П. (1946), «Заметки о нормальных числах», Бюллетень Американского математического общества , 52 (10): 857–860, doi : 10.1090/S0002-9904-1946-08657-7
- Давенпорт, Х. ; Эрдеш, П. (1952), «Заметки об обычных десятичных дробях», Canadian Journal of Mathematics , 4 : 58–63, doi : 10.4153/CJM-1952-005-3 , S2CID 14621341
- Эверест, Грэм ; ван дер Портен, Альф ; Шпарлинский, Игорь; Уорд, Томас (2003), Рекуррентные последовательности , Математические обзоры и монографии, том. 104, Провиденс, Род-Айленд : Американское математическое общество , ISBN 0-8218-3387-1, Збл 1033.11006
- Лонг, Коннектикут (1957), «Заметки о нормальных числах», Pacific Journal of Mathematics , 7 (2): 1163–1165, doi : 10.2140/pjm.1957.7.1163 , Zbl 0080.03604
- Мартин, Грег (2001), «Абсолютно ненормальные числа», American Mathematical Monthly , 108 (8): 746–754, arXiv : math/0006089 , doi : 10.2307/2695618, JSTOR 2695618, Zbl 1036.11035
- Мурти, Марути Рам (2007), Проблемы аналитической теории чисел (2-е изд.), Springer, ISBN 978-0-387-72349-5
- Накаи, Ю.; Сиокава, И. (1992), «Оценки расхождения для класса нормальных чисел», Acta Arithmetica , 62 (3): 271–284, doi : 10.4064/aa-62-3-271-284
- Шмидт, В. (1960), «О нормальных числах», Pacific Journal of Mathematics , 10 (2): 661–672, doi : 10.2140/pjm.1960.10.661
- Шнорр, CP ; Стимм, Х. (1972), «Endliche Automaten und Zufallsfolgen», Acta Informatica , 1 (4): 345–359, doi : 10.1007/BF00289514, S2CID 31943843
- Серпинский, В. (1917), «Элементарная демонстрация теории М. Бореля при абсолютных нормах и эффективном определении имени тела», Bulletin de la Société Mathématique de France , 45 : 125–132, doi : 10.24033/bsmf.977
- Уолл, Д.Д. (1949), Нормальные числа , доктор философии. диссертация, Беркли, Калифорния: Калифорнийский университет
- Зив, Дж .; Лемпель, А. (1978), «Сжатие отдельных последовательностей посредством кодирования с переменной скоростью», IEEE Transactions on Information Theory , 24 (5): 530–536, doi : 10.1109/TIT.1978.1055934, hdl : 10338.dmlcz/142945
дальнейшее чтение
- Бейли, DH ; Крэндалл, Р.Э. (2001), «О случайном характере разложений фундаментальных констант» (PDF) , Experimental Mathematics , 10 (2): 175–190, doi : 10.1080/10586458.2001.10504441, S2CID 2694690, заархивировано из оригинала (PDF) ) 23 ноября 2008 г.
- Бейли, DH ; Мисюревич, М. (2006), «Теорема о сильной горячей точке», Proceedings of the American Mathematical Society , 134 (9): 2495–2501, doi : 10.1090/S0002-9939-06-08551-0
- Калуд, К. (1994), «Борелевская нормальность и алгоритмическая случайность», Розенберг, Г.; Саломаа, Арто (ред.), Развитие теории языка: на перекрестке математики, информатики и биологии , World Scientific , Сингапур, стр. 113–119.
- Калуде, CS ; Замфиреску, Т. (1999), «Большинство чисел не подчиняются законам вероятности», Publicationes Mathematicae Debrecen , 54 (Дополнение): 619–623.
- Даджани, Карма ; Краайкамп, Кор (2002), Эргодическая теория чисел , Математические монографии Каруса , том. 29, Вашингтон, округ Колумбия: Математическая ассоциация Америки , ISBN. 0-88385-034-6, Збл 1033.11040
- Харман, Глин (2002), «Сто лет нормальных чисел», в Беннетте, Массачусетс; Берндт, Британская Колумбия ; Бостон, Северная Каролина ; Даймонд, ХГ; Хильдебранд, AJ; Филипп, В. (ред.), Обзоры по теории чисел: материалы тысячелетней конференции по теории чисел , Натик, Массачусетс: AK Peters, стр. 57–74, ISBN 1-56881-162-4, Збл 1062.11052
- Хошневисан, Давар (2006), «Нормальные числа нормальны» (PDF) , Годовой отчет Института математики Клэя за 2006 г .: 15, продолжение, стр. 27–31.
- Кеффлек, Мартин (2006), «Старые и новые результаты о нормальности», в Дентенир, Ди; ден Холландер, Ф.; Вербицкий, Э. (ред.), Динамика и стохастика: Festschrift в честь М. С. Кина , Конспекты лекций IMS - Серия монографий, том. 48, Бичвуд, Огайо: Институт математической статистики , стр. 225–236, arXiv : math.DS/0608249 , doi : 10.1214/074921706000000248, ISBN 0-940600-64-1, Збл 1130.11041
Внешние ссылки