Функция вопросительного знака Минковского

Эта статья включает список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Апрель 2013 ) ( Узнайте, как и когда удалять это сообщение )

В математике функция Минковского со знаком вопроса , обозначаемая ?( x ) , является функцией с необычными фрактальными свойствами, определенной Германом Минковским в 1904 году ^{. [1]} Она отображает квадратичные иррациональные числа в рациональные числа на единичном интервале с помощью выражения, связывающего разложения квадратичных чисел в непрерывные дроби с двоичными разложениями рациональных чисел, данного Арно Данжуа в 1938 году. ^[2] Она также отображает рациональные числа в двоично-рациональные числа , как можно увидеть из рекурсивного определения, тесно связанного с деревом Штерна–Броко .

Один из способов определения функции вопросительного знака включает соответствие между двумя различными способами представления дробных чисел с использованием конечных или бесконечных двоичных последовательностей . Наиболее привычно, что строка из нулей и единиц с одной точкой ".", например, "11.0010010000111111..." может быть интерпретирована как двоичное представление числа. В этом случае это число есть Однако существует другой способ интерпретации той же последовательности с использованием непрерывных дробей . Интерпретируя дробную часть "0.00100100001111110..." как двоичное число таким же образом, замените каждый последующий блок нулей или единиц на его длину серии (или, для первого блока нулей, его длину серии плюс один), в этом случае генерируя последовательность . Затем используйте эту последовательность в качестве коэффициентов непрерывных дробей: ^{[3] [4]}$${\displaystyle 2+1+{\frac {1}{8}}+{\frac {1}{64}}+\cdots =\pi .}$$${\displaystyle [3;3,1,2,1,4,6,\точки ]}$$${\displaystyle 3+{\frac {1}{\displaystyle 3+{\frac {1}{\displaystyle 1+{\frac {1}{\displaystyle 2+{\frac {1}{\displaystyle 1+{ \frac {1}{\displaystyle 4+{\frac {1}{\displaystyle 6+\dots }}}}}}}}}}}}\approx 3,2676}$$

Функция вопросительного знака обращает этот процесс: она переводит непрерывную дробь заданного действительного числа в двоичную последовательность, закодированную по длине серии, а затем повторно интерпретирует эту последовательность как двоичное число. ^{[3] [4]} Например, для приведенного выше примера, . Чтобы определить это формально, если иррациональное число имеет представление в виде (незавершающейся) непрерывной дроби , то значение функции вопросительного знака на определяется как значение бесконечного ряда Рациональное число имеет представление в виде конечной непрерывной дроби , поэтому значение функции вопросительного знака на сводится к двоично-рациональному числу, определяемому конечной суммой, Квадратичное иррациональное число представлено периодической непрерывной дробью , поэтому значение функции вопросительного знака на является периодической двоичной дробью и, таким образом, недвоично-рациональным числом.${\displaystyle \operatorname {?} (3,2676)\приблизительно \пи }$ ${\displaystyle x}$$${\displaystyle x=a_{0}+{\frac {1}{\displaystyle a_{1}+{\frac {1}{\displaystyle a_{2}+\cdots }}}}=[a_{0};a_{1},a_{2},\dots ]}$$${\displaystyle x}$$${\displaystyle \operatorname {?} (x)=a_{0}+2\sum _{n=1}^{\infty }{\frac {\left(-1\right)^{n+1}}{2^{a_{1}+\cdots +a_{n}}}}.}$$ ${\displaystyle x}$${\displaystyle [a_{0};a_{1},a_{2},\dots ,a_{m}]}$${\displaystyle x}$$${\displaystyle \operatorname {?} (x)=a_{0}+2\sum _{n=1}^{m}{\frac {\left(-1\right)^{n+1}}{2^{a_{1}+\cdots +a_{n}}}}.}$$ ${\displaystyle x}$${\displaystyle x}$

Вопросительный знак явно визуально самоподобен. Моноид самоподобий может быть сгенерирован двумя операторами S и R, действующими на единичный квадрат, и определяется следующим образом:$${\displaystyle {\begin{aligned}S(x,y)&=\left({\frac {x}{x+1}},{\frac {y}{2}}\right),\\[5px]R(x,y)&=(1-x,1-y).\end{aligned}}}$$

Визуально S сжимает единичный квадрат до его нижней левой четверти, в то время как R выполняет точечное отражение через его центр.

Точка на графике ? имеет координаты ( x , ?( x ) ) для некоторого x в единичном интервале. Такая точка преобразуется S и R в другую точку графика, поскольку ? удовлетворяет следующим тождествам для всех x ∈ [0, 1] :$${\displaystyle {\begin{aligned}\operatorname {?} \left({\frac {x}{x+1}}\right)&={\frac {\operatorname {?} (x)}{2}},\\[5px]\operatorname {?} (1-x)&=1-\operatorname {?} (x).\end{aligned}}}$$

Эти два оператора могут быть многократно объединены, образуя моноид. Общий элемент моноида тогда$${\displaystyle S^{a_{1}}RS^{a_{2}}RS^{a_{3}}\cdots }$$

для положительных целых чисел a ₁ , a ₂ , a ₃ , … . Каждый такой элемент описывает самоподобие функции вопросительного знака. Этот моноид иногда называют моноидом удвоения периода , и все фрактальные кривые удвоения периода имеют самосимметрию, описываемую им ( кривая де Рама , частным случаем которой является вопросительный знак, является категорией таких кривых). Элементы моноида находятся в соответствии с рациональными числами посредством отождествления a ₁ , a ₂ , a ₃ , … с непрерывной дробью [0; a ₁ , a ₂ , a ₃ ,…] . Поскольку оба и являются дробно-линейными преобразованиями с целыми коэффициентами, моноид можно рассматривать как подмножество модулярной группы PSL(2, Z ) .$${\displaystyle S:x\mapsto {\frac {x}{x+1}}}$$$${\displaystyle T:x\mapsto 1-x}$$

Функция вопросительного знака обеспечивает взаимно-однозначное отображение недвоичных рациональных чисел в квадратичные иррациональные числа , тем самым позволяя явно доказать счетность последних. Фактически, их можно понимать как соответствующие периодическим орбитам для двузначного преобразования . Это можно явно продемонстрировать всего за несколько шагов.

Определим два хода: ход влево и ход вправо, допустимые на единичном интервале как и и и Тогда функция вопросительного знака подчиняется симметрии хода влево и симметрии хода вправо, где обозначает композицию функций . Их можно произвольно конкатенировать. Рассмотрим, например, последовательность ходов влево-вправо. Добавляя индексы C и D и, для ясности, опуская оператор композиции во всех местах, кроме нескольких, получаем: Произвольные строки конечной длины в буквах L и R соответствуют двоичным рациональным числам , в том смысле, что каждое двоичное рациональное число может быть записано как для целых чисел n и m , так и как конечная длина битов с Таким образом, каждое двоичное рациональное число находится во взаимно однозначном соответствии с некоторой самосимметрией функции вопросительного знака.${\displaystyle 0\leq x\leq 1}$$${\displaystyle L_{D}(x)={\frac {x}{2}}}$$${\displaystyle L_{C}(x)={\frac {x}{1+x}}}$$${\displaystyle R_{D}(x)={\frac {1+x}{2}}}$$${\displaystyle R_{C}(x)={\frac {1}{2-x}}}$$${\displaystyle L_{D}\circ {\text{?}}={\text{?}}\circ L_{C}}$$$${\displaystyle R_{D}\circ {\text{?}}={\text{?}}\circ R_{C}}$$${\displaystyle \circ }$${\displaystyle LRLLR.}$${\displaystyle \circ }$$${\displaystyle L_{D}R_{D}L_{D}L_{D}R_{D}\circ {\text{?}}={\text{?}}\circ L_{C}R_{C}L_{C}L_{C}R_{C}}$$${\displaystyle y=n/2^{m}}$${\displaystyle y=0.b_{1}b_{2}b_{3}\cdots b_{m}}$${\displaystyle b_{k}\in \{0,1\}.}$

Некоторые перестановки обозначений могут сделать вышеизложенное немного более простым для выражения. Пусть и обозначают L и R. Композиция функций расширяет это до моноида , в том смысле, что можно записать и в общем случае для некоторых двоичных строк цифр A , B , где AB — это просто обычная конкатенация таких строк. Тогда диадический моноид M является моноидом всех таких конечной длины лево-правых движений. Записывая как общий элемент моноида, мы получаем соответствующую самосимметрию функции вопросительного знака:${\displaystyle g_{0}}$${\displaystyle g_{1}}$${\displaystyle g_{010}=g_{0}g_{1}g_{0}}$${\displaystyle g_{A}g_{B}=g_{AB}}$${\displaystyle \gamma \in M}$$${\displaystyle \gamma _{D}\circ {\text{?}}={\text{?}}\circ \gamma _{C}}$$

Явное отображение между рациональными и двоично-рациональными числами может быть получено с помощью оператора отражения и отметив, что и так как и является тождеством , произвольная строка ходов влево-вправо может быть переписана как строка только ходов влево, за которыми следует отражение, за которым следуют еще ходы влево, отражение и так далее, то есть как , которая явно изоморфна сверху. Оценка некоторой явной последовательности в аргументе функции дает двоично-рациональное число; явно, оно равно где каждый является двоичным битом, ноль соответствует левому ходу, а единица соответствует правому ходу. Эквивалентная последовательность ходов, оцененная в дает рациональное число Это явно то, что предоставляется непрерывной дробью, имея в виду, что это рациональное число, поскольку последовательность имела конечную длину. Это устанавливает взаимно-однозначное соответствие между двоично-рациональными и рациональными числами.$${\displaystyle r(x)=1-x}$$$${\displaystyle r\circ R_{D}\circ r=L_{D}}$$${\displaystyle r\circ R_{C}\circ r=L_{C}}$${\displaystyle r^{2}=1}$${\displaystyle L^{a_{1}}rL^{a_{2}}rL^{a_{3}}\cdots }$${\displaystyle S^{a_{1}}TS^{a_{2}}TS^{a_{3}}\cdots }$${\displaystyle L_{D},R_{D}}$${\displaystyle x=1}$${\displaystyle y=0.b_{1}b_{2}b_{3}\cdots b_{m}}$${\displaystyle b_{k}\in \{0,1\}}$${\displaystyle L_{C},R_{C}}$${\displaystyle x=1}$${\displaystyle p/q.}$${\displaystyle p/q=[a_{1},a_{2},a_{3},\ldots ,a_{j}]}$${\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{j})}$

Рассмотрим теперь периодические орбиты диадического преобразования . Они соответствуют битовым последовательностям, состоящим из конечной начальной «хаотической» последовательности бит , за которой следует повторяющаяся строка длины . Такие повторяющиеся строки соответствуют рациональному числу. Это легко сделать явным. Запишите одно, тогда ясно, что Прикрепляя к начальной неповторяющейся последовательности, ясно, что имеем рациональное число. Фактически, каждое рациональное число можно выразить таким образом: начальная «случайная» последовательность, за которой следует циклическое повторение. То есть периодические орбиты отображения находятся во взаимно-однозначном соответствии с рациональными числами.${\displaystyle b_{0},b_{1},b_{2},\ldots ,b_{k-1}}$${\displaystyle b_{k},b_{k+1},b_{k+2},\ldots ,b_{k+m-1}}$${\displaystyle m}$$${\displaystyle y=\sum _{j=0}^{m-1}b_{k+j}2^{-j-1}}$$$${\displaystyle \sum _{j=0}^{\infty }b_{k+j}2^{-j-1}=y\sum _{j=0}^{\infty }2^{-jm}={\frac {y}{1-2^{m}}}}$$

Такие периодические орбиты имеют эквивалентную периодическую непрерывную дробь, согласно изоморфизму, установленному выше. Существует начальная «хаотическая» орбита некоторой конечной длины, за которой следует повторяющаяся последовательность. Повторяющаяся последовательность порождает периодическую непрерывную дробь, удовлетворяющую Эта непрерывная дробь имеет вид ^[5] с являющимися целыми числами, и удовлетворяющая Явные значения могут быть получены путем записи для сдвига, так что в то время как отражение задается так что . Обе эти матрицы унимодулярны , произвольные произведения остаются унимодулярными и приводят к матрице формы, дающей точное значение непрерывная дробь. Поскольку все элементы матрицы являются целыми числами, эта матрица принадлежит проективной модулярной группе${\displaystyle x=[a_{n},a_{n+1},a_{n+2},\ldots ,a_{n+r},x].}$$${\displaystyle x={\frac {\alpha x+\beta }{\gamma x+\delta }}}$$${\displaystyle \alpha ,\beta ,\gamma ,\delta }$${\displaystyle \alpha \delta -\beta \gamma =\pm 1.}$$${\displaystyle S\mapsto {\begin{pmatrix}1&0\\1&1\end{pmatrix}}}$$$${\displaystyle S^{n}\mapsto {\begin{pmatrix}1&0\\n&1\end{pmatrix}}}$$$${\displaystyle T\mapsto {\begin{pmatrix}-1&1\\0&1\end{pmatrix}}}$$${\displaystyle T^{2}=I}$$${\displaystyle S^{a_{n}}TS^{a_{n+1}}T\cdots TS^{a_{n+r}}={\begin{pmatrix}\alpha &\beta \\\gamma &\delta \end{pmatrix}}}$$ ${\displaystyle PSL(2,\mathbb {Z} ).}$

Решая явно, получаем, что Нетрудно проверить, что решения этого уравнения соответствуют определению квадратичных иррациональностей. Фактически, каждое квадратичное иррациональное число может быть выражено таким образом. Таким образом, квадратичные иррациональные числа находятся во взаимно однозначном соответствии с периодическими орбитами двоичного преобразования, которые находятся во взаимно однозначном соответствии с (недвоичными) рациональными числами, которые находятся во взаимно однозначном соответствии с двоичными рациональными числами. Функция вопросительного знака обеспечивает соответствие в каждом случае.${\displaystyle \gamma x^{2}+(\delta -\alpha )x-\beta =0.}$

Функция вопросительного знака является строго возрастающей и непрерывной, ^[6] но не абсолютно непрерывной функцией. Производная определена почти всюду и может принимать только два значения: 0 (ее значение почти всюду, включая все рациональные числа ) и . ^[7] Существует несколько конструкций для меры , которая при интегрировании дает функцию вопросительного знака. Одна из таких конструкций получается путем измерения плотности чисел Фарея на числовой прямой. Мера вопросительного знака является прототипическим примером того, что иногда называют мультифрактальными мерами .${\displaystyle +\infty }$

Функция вопросительного знака отображает рациональные числа в двоичные рациональные числа , то есть те, чье представление с основанием два заканчивается, что может быть доказано индукцией из рекурсивной конструкции, описанной выше. Она отображает квадратичные иррациональные числа в недвоичные рациональные числа. В обоих случаях она обеспечивает изоморфизм порядков между этими множествами, ^[8] конкретизируя теорему Кантора об изоморфизме, согласно которой любые два неограниченных счетных плотных линейных порядка являются изоморфными по порядку. ^[9] Это нечетная функция и удовлетворяет функциональному уравнению ?( x + 1) = ?( x ) + 1 ; следовательно, x ↦ ?( x ) − x является нечетной периодической функцией с периодом один. Если ?( x ) иррационально, то x является либо алгебраической степени больше двух, либо трансцендентной .

Функция вопросительного знака имеет неподвижные точки в 0, ⁠1/2⁠ и 1, и по крайней мере еще два, симметричные относительно средней точки. Один приблизительно равен 0,42037. ^[6] Мощевитин предположил, что это были единственные 5 неподвижных точек. ^[10]

В 1943 году Рафаэль Салем поднял вопрос о том, исчезают ли коэффициенты Фурье–Стилтьеса функции вопросительного знака на бесконечности. ^[11] Другими словами, он хотел узнать,$${\displaystyle \lim _{n\to \infty }\int _{0}^{1}e^{2\pi inx}\,\operatorname {d?} (x)=0.}$$

На этот вопрос Джордан и Сальстен ответили утвердительно, как на частный случай результата по мерам Гиббса . ^[12]

График функции вопросительного знака Минковского является частным случаем фрактальных кривых, известных как кривые де Рама .

Рекурсивное определение естественным образом поддается алгоритму вычисления функции с любой желаемой степенью точности для любого действительного числа, как демонстрирует следующая функция C. Алгоритм спускается по дереву Штерна–Броко в поисках входных данных  x и суммирует члены двоичного разложения y = ?( x ) по пути. Пока инвариант цикла qr − ps = 1 остается удовлетворенным, нет необходимости сокращать дробь ⁠м/н⁠ = ⁠п + р/д + с⁠ , так как он уже в самых низких терминах. Другой инвариант ⁠п/д⁠ ≤ х < ⁠г/с⁠ .forЦикл в этой программе можно проанализировать какwhileцикл, с условными операторами break в первых трех строках, определяющими условие. Единственные операторы в цикле, которые могут повлиять на инварианты, находятся в последних двух строках, и можно показать, что они сохраняют истинность обоих инвариантов, пока первые три строки выполнены успешно, не прерывая цикл. Третий инвариант для тела цикла (до точности с плавающей точкой) — y ≤ ?( x ) < y + d , но поскольку d делится пополам в начале цикла до проверки каких-либо условий, наш вывод заключается только в том, что y ≤ ?( x ) < y + 2 d в конце цикла.

Для доказательства завершения достаточно отметить, что сумма q + sувеличивается как минимум на 1 с каждой итерацией цикла, и что цикл завершится, когда эта сумма станет слишком большой для представления в примитивном типе данных C. longОднако на практике условный break when y + d == y— это то, что гарантирует завершение цикла за разумное время.

/* Функция Минковского со знаком вопроса */ double minkowski ( double x ) { long p = x ; long q = 1 , r = p + 1 , s = 1 , m , n ; double d = 1 , y = p ; if ( x < p || ( p < 0 ) ^ ( r <= 0 )) return x ; /* вне диапазона ?(x) =~ x */ while ( true ) { /* инварианты: q * r - p * s == 1 && p / q <= x && x < r / s */ d /= 2 ; if ( y + d == y ) break ; /* достигнута максимально возможная точность */ m = p + r ; if (( m < 0 ) ^ ( p < 0 )) break ; /* сумма переполнена */ n = q + s ; если ( n < 0 ) break ; /* сумма переполнена */                                                                                     если ( x < ( double ) m / n ) { r = m ; s = n ; } else { y += d ; p = m ; q = n ; } } return y + d ; /* окончательное округление */ }                               

Ограничивая функцию вопросительного знака Минковского до ?:[0,1] → [0,1], ее можно использовать как кумулятивную функцию распределения сингулярного распределения на единичном интервале. Это распределение симметрично относительно своей средней точки, с сырыми моментами около m ₁  = 0,5, m ₂  = 0,290926, m ₃  = 0,186389 и m ₄  = 0,126992, ^[13] и, таким образом, среднее значение и медиана 0,5, стандартное отклонение около 0,2023, асимметрия 0 и избыточный эксцесс около −1,147.

• Функция Кантора , которую можно понимать как переосмысление троичных чисел как двоичных чисел, аналогично тому, как функция со знаком вопроса переосмысливает непрерывные дроби как двоичные числа.
• Проблема Эрмита , к которой один из подходов использует обобщение функции вопросительного знака Минковского. ^[14]
• производная Помпея

• Обширный библиографический список
• Вайсштейн, Эрик В. , «Функция вопросительного знака Минковского», MathWorld
• Простая реализация IEEE 754 на C++