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

技术摘要：Martin-Löf 随机实数中的 S2a-可约性与微分性

问题陈述
本文探讨了当 Solovay 可约性（$\le_S$）从左 c.e. 实数扩展到更广泛的计算可近似（c.a.）实数类时所表现出的行为。虽然 Solovay 可约性在左 c.e. 实数上已被充分研究——它刻画了近似过程的相对收敛速率，并通过 Kučera–Slaman 定理以及 Barmpalias–Lewis-Pye 极限定理与 Martin-Löf 随机性保持一致——但其向一般实数的扩展却并不稳定。

具体而言，本文研究了由 Zheng 和 Rettinger 为 c.a. 实数引入的 S2a-可约性（$\le_{2a}^S$）。这种可约性通过平移函数区间 $(f, h)$ 进行函数化刻画，其中 $f$ 是下半可计算的，$h$ 是上半可计算的，且满足 $f \le h$，两者在源实数处均收敛于目标实数。

核心问题在于 Conjecture 24（由 Titov [16] 提出）的有效性，该猜想认为 Barmpalias–Lewis-Pye 极限定理可以扩展到 S2a-可约性。该猜想断言，如果 $\beta$ 是一个 Martin-Löf 随机的 c.a. 实数，且 $\alpha \le_{2a}^S \beta$ 通过一个函数区间 $(f, h)$ 实现，那么当 $x \to \beta$ 时，比率 $\frac{\alpha - f(x)}{\beta - x}$（以及类似的对于 $h$）必须收敛于一个极限 $d$。此外，它还猜想当且仅当 $\alpha$ 是 Martin-Löf 随机时，$d \neq 0$。

方法论
作者通过构造一个反例来驳斥 Conjecture 24。其方法涉及构造一个收敛于特定 Martin-Löf 随机实数 $\beta$ 的可计算近似过程，并定义特定的平移函数区间。

1. $\beta$ 的构造： 作者使用一个旨在避开通用 Martin-Löf 测试的计算近似序列 $b_0, b_1, \dots$ 来构造一个 Martin-Löf 随机实数 $\beta$。至关重要的是，该近似过程被设计为在 $\beta$ 附近存在“间隙”。具体来说，他们确保存在一个区间序列 $[l_i, r_i]$，使得 $\beta$ 任意接近这些区间的端点，但近似序列中的任何元素都不会严格落在这些区间内部。这一性质在 Lemma 26 中得到了形式化描述。
2. 函数区间的构造：
   • 情况 1（有界但振荡）： 构造了一个从 $\beta$ 到 $0$的函数区间$(-h, h)$。函数$h(x)$被定义为$x$到近似序列$b_n$ 的距离的下确界。该函数是 Lipschitz 连续的，常数为 1。作者证明，虽然比率 $\frac{|0 - h(x)|}{|\beta - x|}$ 是有界的，但当 $x \to \beta$ 时，它从两侧在 0 和 1 之间无限次振荡，未能收敛。
   • 情况 2（无界增长）： 利用由近似序列定义的下图（hypographs）和上图（epigraphs），构造了一个从 $\beta$ 到 $\beta$ 的函数区间 $(\tilde{f}, \tilde{h})$。这些函数是非减且半可计算的。作者表明，当 $x \to \beta$ 时，比率 $\frac{|\beta - \tilde{f}(x)|}{|\beta - x|}$ 和 $\frac{|\beta - \tilde{h}(x)|}{|\beta - x|}$ 是无界的。

主要贡献与结果
本文的主要贡献是证明了 Theorem 25，该定理确立了存在一个 c.a. Martin-Löf 随机实数 $\beta$ 以及特定的函数区间，从而违反了 Conjecture 24 的条件。

• 对极限定理的驳斥： 本文证明了 Barmpalias–Lewis-Pye 极限定理在 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|$$
  这表明近似比率并不收敛，从而反驳了该比率必须收敛于一个类似导数常数的猜想。
• 有界性的失效： 对于从 $\beta$ 到自身的还原 $(\tilde{f}, \tilde{h})$ 的构造表明，即使是针对自身，该比率也可能是无界的，这违反了在随机性语境下通常与 Solovay 型可约性相关的有界性要求。
• 对可加速性的启示： 作者指出（Remark 27），这类函数区间的使用排除了基于函数刻画为 S2a-可约性引入非平凡“可加速性”（speedability）概念的可能性，因为其收敛行为过于紊乱。

意义与主张
本文声称解决了关于 Solovay 可约性在左 c.e. 实数上的强极限性质是否能扩展到所有 c.a. 实数的 S2a-可约性的函数刻画这一问题。作者得出结论：它并不能扩展。

• 微分性与随机性： 结果表明，当从有理数上的可计算函数转向半可计算函数区间时，Martin-Löf 随机性与平移函数（或函数区间）的可微性之间的联系是非常脆弱的。虽然 Titov 先前的研究表明有界变差函数在随机点处是可微的，但 S2a-可助于通过函数区间进行的特定函数化刻画允许了（无限振荡和无界增长等）行为，从而阻碍了唯一导数的定义。
• 开放问题： 作者谦逊地提出了几个开放问题：
  1. 确定确切哪些实数对 $(\alpha, \beta)$ 允许一个平移函数区间。
  2. 是否存在一种较弱形式的极限定理（例如，单侧可微性）。
  3. 是否可以通过函数区间的微分性质来刻画 Martin-Löf 随机性。
  4. 探索其他版本的 Solovay 可约性与其他更强随机性概念之间的联系。

作者强调，他们的工作凸显了关于构建来自无界或振荡增长的随机性测试时，可计算函数与半可计算函数区间之间存在根本性的行为差异。