S2a-reducibility and differentiation in Martin-Löf random reals

テクニカル・サマリー：マーチン＝レーフ乱数におけるS2a-還元可能性と微分

問題提起
本論文は、左c.e.実数のクラスを超えて、より広いクラスである計算可能近似（c.a.）実数へと拡張された際のソロヴェイ還元可能性（$\le_S$）の振る舞いを取り上げている。ソロヴェイ還元可能性は、左c.e.実数においては、近似の相対的な収束速度を特徴付け、クチェラ–スラムンの定理やバンプリアス–ルイス–パイの極限定理を通じてマーチン＝レーフ乱数と一致することがよく知られているが、一般的な実数への拡張においては、その安定性が低い。

具体的には、本論文は、c.a.実数のためにゼンガーとレッテリによって導入された変種であるS2a-還元可能性（$\le_{2a}^S$）を調査している。この還元可能性は、翻訳関数区間 $(f, h)$ を通じて機能的に特徴付けられる。ここで、$f$ は下半可算、$h$ は上半可算であり、$f \le h$ であり、かつ両者がソースの実数に対してターゲットとなる実数へと収束する。

中心となる問題は、ティトス[16]によって提案された予想24の妥当性である。この予想は、バンプリアス–ルイス–パイの極限定理がS2a-還元可能性にも拡張されるというものである。この予想は、もし $\beta$ がマーチン＝レーフ乱数であるc.a.実数であり、$\alpha \le_{2a}^S \beta$ が関数区間 $(f, h)$ によってなされるならば、比率 $\frac{\alpha - f(x)}{\beta - x}$ （および $h$ についても同様）は $x \to \beta$ のとき極限 $d$ に収束しなければならないと主張している。さらに、この予想は、$d \neq 0$ であることと $\alpha$ がマーチン＝レーフ乱数であることが同値であると述べている。

手法
著者らは、反例を構成することによって予想24を論破する。その手法は、特定のマーチン＝レーフ乱数 $\beta$ に収束する計算可能近似のステップごとの構成と、特定の翻訳関数区間の定義を含む。

1. $\beta$ の構成： 著者らは、ユニバーサル・マーチン＝レーフ・テストを回避する計算可能近似 $b_0, b_1, \dots$ を用いて、マーチン＝レーフ乱数 $\beta$ を構成する。決定的なのは、この近似が $\beta$ の近くに「隙間」を持つように設計されている点である。具体的には、区間 $[l_i, r_i]$ の列が存在し、$\beta$ がこれらの区間の端点に極めて近いものの、近似列 $b_n$ の要素がこれらの区間の内部に決して入らないことを保証する。この性質は補題26において定式化されている。
2. 関数区間の構成：
   • ケース1（有界だが振動する）： $\beta$ から $0$への関数区間$(-h, h)$を構成する。関数$h(x)$は、近似列$b_n$からの距離のインフィマムとして定義される。この関数は定数1のリプシッツ連続関数である。著者らは、比率$\frac{|0 - h(x)|}{|\beta - x|}$は有界であるものの、$x \to \beta$ のとき両側から無限に0と1の間で振動し、収束しないことを示す。
   • ケース2（非有界な成長）： 近似列によって定義される下グラフ（hypograph）と上グラフ（epigraph）を用いて、$\beta$ から $\beta$ への関数区間 $(\tilde{f}, \tilde{h})$ を構成する。これらの関数は単調増加であり、半可算である。著者らは、比率 $\frac{|\beta - \tilde{f}(x)|}{|\beta - x|}$ および $\frac{|\beta - \tilde{h}(x)|}{|\beta - x|}$ が $x \to \beta$ のとき非有界であることを示す。

主要な貢献と結果
主要な貢献は、特定のマーチン＝レーフ乱数 $\beta$ と特定の関数区間の存在を確立する定理25の証明である。

• 極限定理の論破： 本論文は、バンプリアス–ルイス–パイの極限定理がS2a-還元可能性においては成立しないことを証明している。具体的には、構成された $\beta$ と $\beta$ から $0$への関数区間$(-h, h)$ について：
  $$\liminf_{x \to \beta} \left| \frac{0 - h(x)}{\beta - x} \right| = 0 < 1 = \limsup_{x \to \beta} \left| \frac{0 - h(x)}{\beta - x} \right|$$
  これは、近似比が微分のような定数に収束しないことを示しており、予想に矛盾する。
• 有界性の失敗： $(\tilde{f}, \tilde{h})$ の構成は、ランダムな実数から自身への還元であっても、比率が非有界になり得ることを示しており、これはランダムネスの文脈においてソロヴェイ型の還元可能性に関連してしばしば想定される有界性の要件に違反している。
• 速度可能性への含意： 著者らは（注釈27）、このような関数区間の存在は、機能的な特徴付けに基づくS2a-還元可能性の非自明な「速度可能性（speedability）」の概念を導入することを排除すると指摘している。なぜなら、収束の振る舞いがあまりにも不規則だからである。

意義と主張
本論文は、左c.e.実数上のソロヴェイ還元可能性の強い極限特性が、すべてのc.a.実数上のS2a-還元可能性の機能的特徴付けへと拡張されるかという問いに決着をつけるものである。著者らは、それは拡張されないと結論付けている。

• 微分とランダムネス： これらの結果は、有理数上の計算可能関数から半可算な関数区間へと移行する際、マーチン＝レーフ乱数と翻訳関数（または関数区間）の微分可能性との関係がいかに脆弱であるかを示している。ティトスの先行研究では、有界変動関数はランダムな点において微分可能であることが示されていたが、関数区間によるS2a-還元可能性の特定の機能的特徴付けは、一意の微分を定義することを妨げる挙動（無限の振動や非有界な成長）を許容している。
• 未解決問題： 著者らは控えめにいくつかの未解決問題を挙げている：
  1. どの実数のペア $(\alpha, \beta)$ が翻訳関数区間を許容するかを正確に決定すること。
  2. より弱い形式の極限定理（例：片側微分可能性）が成立するかどうか。
  3. マーチン＝レーフ乱数が、関数区間の微分可能性の性質を通じて特徴付けられ得るか。
  4. 他のバージョンのソロヴェイ還元可能性と、より強いランダムネス概念との接続の探求。

著者らは、彼らの研究が、非有界または振動する成長からランダムネス・テストを構築することに関する、計算可能関数と半可算な関数区間の振る舞いの根本的な違いを浮き彫りにしていることを強調している。