ミンコフスキーの疑問符関数

数学において、ミンコフスキー疑問符関数（英: Minkowski question-mark function）は、Hermann Minkowski (1904, pages 171–172) によって定義された ?(x) と表される関数であり、さまざまな奇妙なフラクタル特性を持つ。この関数は、二次無理数（英語版）を有理数の二進展開に連分数展開する関係式を介して、二次無理数を単位区間内の有理数に写す。この関係式は1938年にアルノー・ダンジョワ（英語版）(Arnaud Denjoy)によって与えられた。 また、スターン・ブロコット木（英語版）(Stern–Brocot tree)に密接に関連する再帰的な定義でわかるように、この関数は有理数を二進有理数（英語版）に写す。 x が無理数の場合、x の連分数表現を [a0; a1, a2, …] とすると、疑問符関数は次のように定義される。 ? ⁡ ( x ) = a 0 + 2 ∑ n = 1 ∞ ( − 1 ) n + 1 2 a 1 + ⋯ + a n {\displaystyle \operatorname {?} (x)=a_{0}+2\sum _{n=1}^{\infty }{\frac {\left(-1\right)^{n+1}}{2^{a_{1}+\cdots +a_{n}}}}} x が有理数の場合、x の連分数表現を [a0; a1, a2, …, am] とすると、次のようになる。 ? ⁡ ( x ) = a 0 + 2 ∑ n = 1 m ( − 1 ) n + 1 2 a 1 + ⋯ + a n {\displaystyle \operatorname {?} (x)=a_{0}+2\sum _{n=1}^{m}{\frac {\left(-1\right)^{n+1}}{2^{a_{1}+\cdots +a_{n}}}}} 上記の定義を直感的に理解するために、0で始まる無限ビット列を [0, 1] 内の実数と解釈する、2つの相異なる解釈方法を考える。 まず明白な方法は、最初の0の後に2進小数点を置き、二進小数として読む方法である。たとえば、ビット列 001001001001001001001001... は、2進数 0.010010010010... すなわち 2/7 を表す。 別の方法は、ビット列を連分数 [0; a1, a2, …] とみなす方法である。ここで整数 ai は、ビット列を連長圧縮したときの連続回数である。この場合、先ほどと同じビット列 001001001001001001001001...は [0; 2, 1, 2, 1, 2, 1, …] = √3 − 1/2 に対応する。もしビット列で同じビットが無限に続いて終わる場合、それを無視して連分数表現を終了する。この操作の妥当性は以下の恒等式に基づく。 [0; a1, …, an, ∞] = [0; a1, …, an + 1/∞] = [0; a1, …, an + 0] = [0; a1, …, an]. [0, 1] に対する疑問符関数は、カントール関数が三進法表現を二進法表現に写すのと同様に、先程のビット列の2つ目の解釈方法を同じ列の1つ目の解釈方法に写すものと理解できる。先程のビット列を例に挙げると、以下の等式が成り立つ。 ? ⁡ ( 3 − 1 2 ) = 2 7 {\displaystyle \operatorname {?} \left({\frac {{\sqrt {3}}-1}{2}}\right)={\frac {2}{7}}} 単位区間内の有理数の場合、関数を再帰的に定義することもできる。 p/q と r/s が |ps − rq| = 1 を満たす（ファレイ数列の隣接する項である）既約分数である場合、次のようになる。 ? ⁡ ( p + r q + s ) = 1 2 [ ? ⁡ ( p q ) + ? ⁡ ( r s ) ] {\displaystyle \operatorname {?} \left({\frac {p+r}{q+s}}\right)={\frac {1}{2}}\left[\operatorname {?} \left({\frac {p}{q}}\right)+\operatorname {?} \left({\frac {r}{s}}\right)\right]} 初期条件を次のように与えると ? ⁡ ( 0 1 ) = 0  and  ? ⁡ ( 1 1 ) = 1 {\displaystyle \operatorname {?} \left({\frac {0}{1}}\right)=0\quad {\text{ and }}\quad \operatorname {?} \left({\frac {1}{1}}\right)=1} ファレイ数列を F2、F3と順に求めることで、任意の有理数 x に対して ?(x) を計算することが可能になる。 pn−1/qn−1 と pn/qn が同じ連分数をそれぞれ n - 1 段、n 段で打ち切ったものとすると、行列 ( p n − 1 p n q n − 1 q n ) {\displaystyle {\begin{pmatrix}p_{n-1}&p_{n}\\q_{n-1}&q_{n}\end{pmatrix}}} の行列式は ±1 となる。このような行列は、2 × 2 行列で行列式が ±1 となる群 SL(2, Z) の元である。 この群は、モジュラー群に関係する。 この再帰的な定義は、次のC言語関数が示すように、任意の実数に対して任意の精度で関数値を計算するアルゴリズムに適している。 このアルゴリズムは、入力 x を探してスターン・ブロコット木（英語版）を下降する途中で、y = ?(x) の二進展開の項を合計していく。 ループ不変量 qr − ps = 1が満たされる限り、分数 m/n = p + r/q + s を約分する必要はない。 別の不変量は p/q ≤ x < r/s である。このプログラムのforループは、 whileループのように扱われており、最初の3行の条件付きbreak構文が終了条件となる。 ループ内で不変条件に影響を与えるのは最後の2行のみであり、最初の3行がループから抜け出すことなく正常に実行されている限り、両方の不変条件が真であると示すことができる。ループ内部の第三の不変量（浮動小数点精度）は y ≤ ?(x) < y + d であるが、どの条件もテストされる前に、ループの初めに d が半分にされるため、結果的にループの終了時でしか y ≤ ?(x) < y + 2d は担保されない。 プログラムの停止を証明する（英語版）には、ループの反復ごとに合計 q + s が少なくとも1ずつ増加し、この合計がC言語のプリミティブ型 long で表現するには大きすぎる場合にループが終了することに注意すれば十分である。 ただし実際には、 y + d == y の条件付き break があるため、短時間でループが終了する。 /* Minkowski's question-mark function */ double minkowski(double x) { long p = x; if ((double)p > x) --p; /* p=floor(x) */ long q = 1, r = p + 1, s = 1, m, n; double d = 1, y = p; if (x < (double)p || (p < 0)