Нормальный номер

В математике , А действительное число называется просто нормальными в целом числе базовой б ^[1] , если его бесконечная последовательность цифр распределяются равномерно в том смысле , что каждый из б разрядов значений имеет такой же естественную плотность  1 / б . Число называется нормальным по основанию b, если для каждого положительного целого числа n все возможные строки длиной n цифр имеют плотность  b ^{- n} .

Интуитивно понятно, что число, являющееся просто нормальным, означает, что никакая цифра не встречается чаще, чем любая другая. Если число является нормальным, никакая конечная комбинация цифр заданной длины не встречается чаще, чем любая другая комбинация такой же длины. Нормальное число можно представить как бесконечную последовательность подбрасываний монеты ( двоичное число ) или броска кубика ( основание 6 ). Даже если будут такие последовательности, как 10, 100 или более последовательных решек (двоичные) или пятерок (основание 6) или даже 10, 100 или более повторений последовательности, такой как хвост-голова (два последовательных подбрасывания монеты) или 6 -1 (два последовательных броска кубика), также будет столько же любой другой последовательности равной длины. Никакая цифра или последовательность не являются «предпочтительными».

Число называется абсолютно нормальным, если оно нормальное для всех оснований целых чисел, больших или равных 2.

Хотя можно привести общее доказательство того, что почти все действительные числа являются нормальными (это означает, что множество ненормальных чисел имеет нулевую меру Лебега ), ^[2] это доказательство не является конструктивным , и было показано, что только несколько конкретных чисел являются обычный. Например, постоянная Чайтина нормальная (и невычислимая ). Широко распространено мнение, что (вычислимые) числа √ 2 , π и e нормальны, но до сих пор не удается доказать это.

Определения [ править ]

Пусть Σ - конечный алфавит из b -цифров, а Σ ^∞ - множество всех последовательностей, которые могут быть взяты из этого алфавита. Пусть S ∈ Σ ^∞ - такая последовательность. Для каждого а в Е пусть N _S ( , п ) обозначает число раз цифру , а появляется в первых п цифр последовательности S . Мы говорим , что S является просто нормальным , если предел

${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {N_ {S} (a, n)} {n}} = {\ frac {1} {b}}}$

для каждого а . Пусть теперь ш быть любая конечная строка в Е ^* и пусть N _S ( ш , п ) будет число раз , строку ш выглядит как подстроки в первых п цифр последовательности S . (Например, если S = 01010101 ..., то N _S (010, 8) = 3) S является нормальным , если для всех конечных строк ш Е Е ^* ,

${\displaystyle \lim _{n\to \infty }{\frac {N_{S}(w,n)}{n}}={\frac {1}{b^{|w|}}}}$

где |  w  | обозначает длину строки w . Другими словами, S является нормальным, если все строки одинаковой длины встречаются с одинаковой асимптотической частотой. Например, в нормальной двоичной последовательности (последовательность в алфавите {0,1}) 0 и 1 встречаются с частотой ¹ ⁄ ₂ ; 00, 01, 10 и 11 встречаются с частотой ¹ ⁄ ₄ ; 000, 001, 010, 011, 100, 101, 110 и 111 каждый имеет место с частотой ¹ / ₈ и т.д. Грубо говоря, вероятность нахождения строки ш в любом заданном положении в Sэто именно то, что ожидалось, если бы последовательность была произведена случайным образом .

Предположим теперь, что b - целое число больше 1, а x - действительное число . Рассмотрим расширение бесконечной последовательности цифр S _{x, b} числа x в позиционной системе счисления с основанием b (мы игнорируем десятичную точку). Скажем , что х это просто нормален в базовом б , если последовательность S _{х, Ь} просто нормальная ^[3] и что х является нормальной в базовом б , если последовательность S _{х, Ь} является нормальной. ^[4] Число xназывается нормальным числом (или иногда абсолютно нормальным числом ), если оно является нормальным по основанию b для любого целого числа b больше 1. ^{[5] [6]}

Данная бесконечная последовательность либо нормальна, либо не нормальна, тогда как действительное число, имеющее различное разложение по основанию b для каждого целого числа b ≥ 2, может быть нормальным в одном основании, но не в другом ^{[7] [8]} (в этом случае это не нормальное число). Для оснований r и s с логарифмом r  / log s рациональным (так что r = b ^m и s = b ⁿ ) каждое число, нормальное по основанию r, является нормальным по основанию s . Для оснований r и s с log r / Журнал S иррациональный, существует несчетное множество чисел нормальных в каждой базе , но не другие. ^[8]

Дизъюнктивная последовательность представляет собой последовательность , в которой появляется всякая конечная строка. Нормальная последовательность дизъюнктивна, но дизъюнктивная последовательность не обязательно должна быть нормальной. Богатые число в базовом б один, разложение в базовом б является дизъюнктивным: ^[9] тот , который дизъюнктивной к каждому основание называется абсолютно дизъюнктивным или называется лексикон . Число, нормальное по основанию b , богато основанием b , но не обязательно наоборот. Действительное число x богато основанием b тогда и только тогда, когда набор { xb ⁿ mod 1:  n ∈ N} равенплотный в единичном интервале . ^{[9] [10]}

Мы определили, что число будет просто нормальным по основанию b, если каждая отдельная цифра появляется с частотой 1 / b . Для данного основания b число может быть просто нормальным (но не нормальным или b- плотным ^{[ требуется пояснение ]} ), b- плотным (но не просто нормальным или нормальным), нормальным (и, следовательно, просто нормальным и b- плотным), или ничего из этого. Число является абсолютно ненормальным или абсолютно ненормальным, если оно не является просто нормальным для какой-либо базы. ^{[5] [11]}

Свойства и примеры [ править ]

Понятие нормального числа было введено Эмилем Борелем  ( 1909 ). Используя лемму Бореля – Кантелли , он доказал, что почти все действительные числа нормальны, установив существование нормальных чисел. Вацлав Серпинский  ( 1917 ) показал, что можно указать конкретное такое число. Бехер и Фигейра ( 2002 ) доказали, что существует вычислимое абсолютно нормальное число. Хотя эта конструкция не дает напрямую цифр построенных чисел, она показывает, что в принципе возможно перечислить все цифры конкретного нормального числа.

Набор ненормальных чисел, несмотря на то, что он «большой» в смысле несчетности , также является нулевым набором (поскольку его мера Лебега как подмножество действительных чисел равна нулю, поэтому он по существу не занимает места в реальном числа). Кроме того, ненормальные числа (как и нормальные числа) плотны в вещественных числах: набор ненормальных чисел между двумя различными действительными числами не пуст, поскольку он содержит каждое рациональное число (на самом деле, это несчетное число). бесконечно ^[12] и даже сходится ). Например, существует бесчисленное множество чисел, десятичные разложения которых (с основанием 3 или выше) не содержат цифры 1, и ни одно из этих чисел не является нормальным.

Постоянная Чамперноуна

0.1234567891011121314151617181920212223242526272829 ...,

полученная конкатенацией десятичных представлений натуральных чисел по порядку, нормальна по основанию 10. Точно так же различные варианты константы Чамперноуна (выполненные с помощью той же конкатенации в других основаниях) являются нормальными в своих соответствующих основаниях (например, основание -2 Константа Чамперноуна нормальна для базы 2), но не доказана, что она нормальна в других базах.

Постоянная Коупленда – Эрдеша.

0,23571113171923293137414347535961677173798389 ...,

полученная конкатенацией простых чисел с основанием 10, нормальна по основанию 10, как доказали AH Copeland и Paul Erds  ( 1946 ). В более общем плане последние авторы доказали, что действительное число, представленное в основании b конкатенацией

0. f (1) f (2) f (3) ...,

где f ( n ) - n- ^е простое число, выраженное по основанию b , нормально по основанию b . Безикович  ( 1935 ) доказал, что число, представленное тем же выражением, при f ( n ) = n ² ,

0,149162536496481100121144 ...,

полученное объединением квадратных чисел с основанием 10, нормально по основанию 10. Гарольд Дэвенпорт и Эрдеш ( 1952 ) доказали, что число, представленное тем же выражением, где f является любым непостоянным многочленом, значения которого на положительных целых числах являются положительными целыми числами. , выраженное в базе 10, нормально в базе 10.

Накай и Шиокава ( 1992 ) доказали, что если f ( x ) - любой непостоянный многочлен с действительными коэффициентами, такой что f ( x )> 0 для всех x > 0, то действительное число, представленное конкатенацией

0. [ f (1)] [ f (2)] [ f (3)] ​​...,

где [ е ( п )] является целой частью из F ( п ) , выраженный в базовом б , является нормальным в базовых б . (Этот результат включает в качестве частных случаев все упомянутые выше результаты Чамперноуна, Безиковича, Давенпорта и Эрдеша.) Авторы также показывают, что тот же результат имеет место даже в более общем случае, когда f является любой функцией вида

f ( x ) = α · x ^β + α ₁ · x ^{β ₁} + ... + α _d · x ^{β _d} ,

где αs и βs - действительные числа, причем β> β ₁ > β ₂ > ...> β _d ≥ 0, и f ( x )> 0 для всех x > 0.

Бейли и Крэндалл ( 2002 ) показывают явный несчетный бесконечный класс b -нормальных чисел путем возмущения чисел Стоунхема .

Доказать нормальность чисел, которые не созданы искусственно, было неуловимой целью. Хотя √ 2 , π , ln (2) и e строго предполагаются как нормальные, до сих пор неизвестно, нормальны они или нет. Не было даже доказано, что все цифры на самом деле встречаются бесконечно много раз в десятичных разложениях этих констант (например, в случае π популярное утверждение «каждая строка чисел в конечном итоге встречается в π» не является истинным. ). Также было высказано предположение, что каждое иррациональное алгебраическое число абсолютно нормально (что означало бы, что √ 2нормально), и контрпримеры не известны ни в одной базе. Однако не было доказано, что иррациональное алгебраическое число является нормальным в какой-либо базе.

Ненормальные числа [ править ]

Никакое рациональное число не является нормальным ни для какой основы, поскольку последовательности цифр рациональных чисел в конечном итоге являются периодическими . ^[13] Однако рациональное число может быть просто нормальным в определенной базе. Например, это просто нормально в базе 10.${\displaystyle {\frac {13{,}717{,}421}{1{,}111{,}111{,}111}}={\frac {123,\!456,\!789}{9,\!999,\!999,\!999}}=0.{\overline {0123456789}}}$

Мартин ( 2001 ) приводит пример абсолютно ненормального иррационального числа. ^[14] Пусть f (2) = 4 и

${\displaystyle f\left(n\right)=n^{\frac {f\left(n-1\right)}{n-1}},\,n\in \mathbb {Z} \cap \left[3,\infty \right)}$

${\displaystyle \alpha =\prod _{m=2}^{\infty }\left({1-{\frac {1}{f\left(m\right)}}}\right)=\left(1-{\frac {1}{4}}\right)\left(1-{\frac {1}{9}}\right)\left(1-{\frac {1}{64}}\right)\left(1-{\frac {1}{152587890625}}\right)\ldots =0.6562499999956991\underbrace {99999\ldots 99999} _{23,747,291,559}8528404201690728\ldots }$

Тогда α - число Лиувилля и абсолютно ненормально.

Свойства [ править ]

Дополнительные свойства нормальных чисел включают:

• Любое ненулевое действительное число можно записать как произведение двух нормальных чисел. Например, если a - любое ненулевое действительное число, а x - ненулевое действительное число, которое выбирается равномерно случайным образом из любого конечного интервала, то почти наверняка x / a и a / x оба нормальны.
• Если x нормально по основанию b и a ≠ 0 - рациональное число, то также нормально по основанию b . ^[15]${\displaystyle x\cdot a}$
• Если это плотная (для каждого и для всех достаточно больших п , ) и являются base- б разложения элементов А , то число , сформированных путем конкатенации элементов А , нормально в базовой б (Copeland и Erdős 1946) . Отсюда следует, что число Шамперноуна нормально по основанию 10 (поскольку множество всех положительных целых чисел, очевидно, плотно) и что константа Коупленда – Эрдеша нормальна по основанию 10 (поскольку из теоремы о простых числах следует, что множество простых чисел плотно ).${\displaystyle A\subseteq \mathbb {N} }$${\displaystyle \alpha <1}$${\displaystyle |A\cap \{1,\ldots ,n\}|\geq n^{\alpha }}$${\displaystyle a_{1},a_{2},a_{3},\ldots }$${\displaystyle 0.a_{1}a_{2}a_{3}\ldots }$
• Последовательность является нормальной тогда и только тогда, когда каждый блок одинаковой длины появляется с одинаковой частотой. (Блок длина к подстроке длиной к появляться в положении , в последовательности , которая является кратной к : например, первый длина- к блоку в S является S [1 .. к ], второй длина- к блоку является S [ K + 1..2 к ], и т.д.) Это подразумевается в работе Зив и Лемпел ( 1978 ) и сделал явным в работе Бурка, Хичкок и Vinodchandran ( 2005 ).
• Число является нормальным по основанию b тогда и только тогда, когда оно просто нормально по основанию b ^k для всех . Это следует из предыдущей блочной характеристики нормальности: поскольку n- ^й блок длины k в его расширении по основанию b соответствует n- ^й цифре в его расширении по основанию b ^k , число просто нормальное в базе b ^k тогда и только тогда, когда блоки длины k появляются в его разложении по основанию b с одинаковой частотой.${\displaystyle k\in \mathbb {Z} ^{+}}$
• Число является нормальным тогда и только тогда, когда оно просто нормально в каждой базе. Это следует из предыдущей характеристики нормальности по основанию b .
• Число является b -нормальным тогда и только тогда, когда существует набор положительных целых чисел, в котором число является просто нормальным по основанию b ^m для всех ^[16] Никакого конечного набора недостаточно, чтобы показать, что число b -нормально.${\displaystyle m_{1}<m_{2}<m_{3}<\cdots }$${\displaystyle m\in \{m_{1},m_{2},\ldots \}.}$
• Все нормальные последовательности замкнуты относительно конечных вариантов : добавление, удаление или изменение конечного числа цифр в любой нормальной последовательности оставляет ее нормальной. Точно так же, если конечное число цифр добавлено, удалено или изменено в любой простой нормальной последовательности, новая последовательность останется просто нормальной.

Подключение к конечным автоматам [ править ]

Агафонов показал раннюю связь между конечными автоматами и нормальными последовательностями: любая бесконечная подпоследовательность, выбранная из нормальной последовательности обычным языком , также является нормальной. Другими словами, если кто-то запускает конечный автомат в нормальной последовательности, где каждое из состояний конечного автомата помечено либо «выход», либо «нет выхода», и машина выводит цифру, которую он считывает следующей после ввода "output" состояние, но не выводит следующую цифру после входа в "no output state", тогда последовательность, которую он выводит, будет нормальной. ^[17]

Более глубокая связь существует с конечными игроками (FSG) и конечными компрессорами без потерь информации (ILFSC).

• Игрок с конечным числом состояний (также известный как мартингал с конечным числом состояний ) - это конечный автомат над конечным алфавитом , каждое из состояний которого помечено процентным соотношением денег, в котором можно делать ставки на каждую цифру . Например, для FSG по двоичному алфавиту текущее состояние q ставит некоторый процент денег игрока на бит 0, а оставшуюся часть денег игрока на бит 1. Денежная ставка на цифру, которая идет следующей в таблице. входные данные (сумма денег, умноженная на процентную ставку) умножаются на , а остальные деньги теряются. После чтения бита FSG переходит в следующее состояние в соответствии с полученными входными данными. FSG d преуспевает${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle \Sigma =\{0,1\}}$${\displaystyle q_{0}\in [0,1]}$${\displaystyle q_{1}=1-q_{0}}$${\displaystyle |\Sigma |}$ на бесконечной последовательности S, если, начиная с 1 доллара, он делает неограниченные денежные ставки на эту последовательность; то есть, если

${\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}$

где - сумма денег, которую имеет игрок d после прочтения первых n цифр S (см. верхний предел ).${\displaystyle d(S\upharpoonright n)}$

• Конечно-компрессор представляет собой конечный автомат с выходными строками маркировки своих переходов между состояниями , в том числе , возможно , пустую строки. (Поскольку одна цифра считывается из входной последовательности для каждого перехода между состояниями, необходимо иметь возможность выводить пустую строку, чтобы вообще достичь любого сжатия). Конечный компрессор без потерь информации - это конечный компрессор, входной сигнал которого может быть однозначно восстановлен из его выхода и конечного состояния. Другими словами, для конечного компрессора C с набором состояний Q , C не имеет потерь информации, если функция , отображающая входную строку C в выходную строку и конечное состояние C , имеет вид${\displaystyle f:\Sigma ^{*}\to \Sigma ^{*}\times Q}$1–1 . Методы сжатия, такие как кодирование Хаффмана или кодирование Шеннона – Фано, могут быть реализованы с помощью ILFSC. ILFSC C сжимает бесконечную последовательность S, если

${\displaystyle \liminf _{n\to \infty }{\frac {|C(S\upharpoonright n)|}{n}}<1,}$

где это количество цифр вывода с помощью C после прочтения первых п цифр S . Степень сжатия ( нижний предел, указанный выше) всегда можно сделать равным 1 с помощью ILFSC с 1 состоянием, который просто копирует свои входные данные в выходные.${\displaystyle |C(S\upharpoonright n)|}$

Шнорр и Стимм показали, что ни один FSG не может быть успешным в любой нормальной последовательности, а Бурк, Хичкок и Винодчандран показали обратное . Следовательно:

Последовательность является нормальной тогда и только тогда, когда нет игрока с конечным числом состояний, который преуспел в ней .

Зив и Лемпель показали:

Последовательность является нормальной тогда и только тогда, когда она несжимаема каким-либо компрессором с конечным состоянием без потерь информации.

(они фактически показали, что оптимальная степень сжатия последовательности по всем ILFSCs - это в точности степень ее энтропии , количественная мера ее отклонения от нормальности, которая равна 1 именно тогда, когда последовательность нормальна). Поскольку алгоритм сжатия LZ сжимает асимптотически так же, как и любой ILFSC, это означает, что алгоритм сжатия LZ может сжимать любую ненормальную последовательность. ^[18]

Эти характеристики нормальных последовательностей можно интерпретировать как означающие, что «нормальный» = «случайный с конечным числом состояний»; т.е. нормальные последовательности - это в точности те, которые кажутся случайными для любого конечного автомата. Сравните это с алгоритмически случайными последовательностями , которые представляют собой те бесконечные последовательности, которые кажутся случайными для любого алгоритма (и фактически имеют аналогичные характеристики игры и сжатия с машинами Тьюринга, заменяющими конечные машины).

Подключение к равнораспределенным последовательностям [ править ]

Ряд х нормален в базовом Ь тогда и только тогда , когда последовательность будет равномерно распределена по модулю 1, ^{[19] [20]} или , что эквивалентно, с использованием критерия Вейля , если и только если${\displaystyle {\left(b^{k}x\right)}_{k=0}^{\infty }}$

${\displaystyle \lim _{n\rightarrow \infty }{\frac {1}{n}}\sum _{k=0}^{n-1}e^{2\pi imb^{k}x}=0\quad {\text{ for all integers }}m\geq 1.}$

Эта связь приводит к терминологии, согласно которой x является нормальным по основанию β для любого действительного числа β тогда и только тогда, когда последовательность равнораспределена по модулю 1. ^[20]${\displaystyle \left({x\beta ^{k}}\right)_{k=0}^{\infty }}$

Заметки [ править ]

См. Также [ править ]

• Постоянная Шамперноуна
• Последовательность де Брюйна
• Теорема о бесконечной обезьяне
• Вавилонская библиотека

Ссылки [ править ]

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

• Мы в Разрядность Pi и жить вечно на Clifford A. Пиковер
• Вайсштейн, Эрик В. «Нормальное число» . MathWorld .