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

기술적 요약: 마틴-뢰프 무작위 실수에서의 S2a-가해성과 미분 가능성

문제 정의
본 논문은 솔로베이 가해성(Solovay reducibility, $\le_S$)을 좌측-c.e. 실수를 넘어 더 넓은 범주인 계산 가능 근사(computably approximable, c.a.) 실수로 확장했을 때의 거동을 다룬다. 솔로베이 가해성은 좌측-c.e. 실수 위에서는 잘 알려져 있으며, 이 경우 근사의 상대적 수렴 속도를 특징짓고 쿠체라-슬라만 정리(Kučera–Slaman Theorem) 및 바르팔리아스-루이스-파이 극한 정리(Barmpalias–Lewis-Pye Limit Theorem)를 통해 마틴-뢰프 무작위성과 일치한다. 그러나 일반적인 실수로의 확장은 덜 안정적이다.

구체적으로, 본 논문은 c.a. 실수를 위해 정(Zheng)과 레팅거(Rettinger)가 도입한 변형인 S2a-가해성($\le_{2a}^S$)을 조사한다. 이 가해성은 번역 함수 구간 $(f, h)$를 통해 기능적으로 특징지어지는데, 여기서 $f$는 하반계산 가능(lower semicomputable)하고 $h$는 상반계산 가능(upper semicomputable)하며, $f \le h$이고 두 함수 모두 소스 실수에서 타겟 실수로 수렴한다.

중심 문제는 티토프(Titov) [16]가 제안한 추측 24(Conjecture 24)의 타당성을 검증하는 것이다. 이 추측은 바르팔리아스-루이스-파이 극한 정리가 S2a-가해성으로도 확장될 수 있다고 가정한다. 즉, 만약 $\beta$가 마틴-뢰프 무작위 c.a. 실수이고 $\alpha \le_{2a}^S \beta$가 함수 구간 $(f, h)$에 의해 성립한다면, $x \to \beta$일 때 비율 $\frac{\alpha - f(x)}{\beta - x}$ (그리고 마찬가지로 $h$에 대해서도)는 극한값 $d$로 수렴해야 한다는 것이다. 또한, $d \neq 0$인 것은 $\alpha$가 마틴-뢰프 무작위일 때와 필요충분조건이라는 것을 추측한다.

방법론
저자들은 반례를 구성함으로써 추측 24를 반박한다. 방법론은 특정 마틴-뢰프 무작위 실수 $\beta$로 수렴하는 계산 가능한 근사와 특정 번역 함수 구간의 정의를 포함하는 단계적 구성을 포함한다.

1. $\beta$의 구성: 저자들은 보편적인 마틴-뢰프 테스트를 피하는 계산 가능한 근사 $b_0, b_1, \dots$를 사용하여 마틴-뢰프 무작위 실수 $\beta$를 구성한다. 결정적으로, 이 근사는 $\beta$ 근처에 "간극(gaps)"을 갖도록 설계된다. 구체적으로, 그들은 구간 $[l_i, r_i]$의 수열이 존재하여 $\beta$가 이 구간들의 끝점에 매우 가깝게 위치하지만, 근사 수열 $b_n$의 어떤 원소도 이 구간 내부에 엄격하게 들어오지 않도록 보장한다. 이 성질은 보조정리 26(Lemma 26)에서 공식화된다.
2. 함수 구간의 구성:
   • 유계이지만 진동하는 경우 (Bounded but Oscillating): $\beta$에서 $0$으로 가는 함수 구간$(-h, h)$를 구성한다. 함수$h(x)$는$x$로부터 근사 수열$b_n$까지의 거리의 하한으로 정의된다. 이 함수는 립시츠 상수(Lipschitz constant) 1을 갖는 립시츠 연속 함수이다. 저자들은 $x \to \beta$일 때 양방향 모두에서 비율 $\frac{|0 - h(x)|}{|\beta - x|}$가 0과 1 사이에서 무한히 진동하며 수렴하지 않는다는 것을 보여준다.
   • 무계 성장 (Unbounded Growth): 하그래프(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|}$가 유계가 아님을 보여준다.

주요 기여 및 결과
주된 기여는 마틴-뢰프 무작위 c.a. 실수 $\beta$와 추측 24를 위반하는 특정 함수 구간의 존재를 확립하는 정리 25(Theorem 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|$$
  이는 근사 비율이 미분 가능한 상수(derivative-like constant)로 수렴하지 않음을 보여주며, 이는 해당 추측을 반박한다.
• 유계성의 실패: $(\tilde{f}, \tilde{h})$의 구성은 무작위성 맥락에서 솔로베이 유형의 가해성과 흔히 연관되는 유계성 요구 조건을 위반하여, $\beta$에서 $\beta$로의 가해성조차도 비율이 무계할 수 있음을 보여준다.
• 속도 가능성에 대한 함의: 저자들은 (주석 27) 이러한 함수 구간의 존재가 기능적 특징화를 기반으로 한 S2a-가해성의 비자명한 "속도 가능성(speedability)" 개념 도입을 배제한다는 점을 언급한다. 이는 수렴 거동이 너무 불규칙하기 때문이다.

의의 및 주장
본 논문은 좌측-c.e. 실수에서의 솔로베이 가해성이 갖는 강한 극한 성질이 모든 c.a. 실수에서의 S2a-가해성으로 확장되는지에 대한 문제를 해결했다고 주장한다. 저자들은 다음과 같이 결론짓는다: 그렇지 않다.

• 미분 가능성과 무작위성: 결과는 유리수 상의 계산 가능한 함수에서 반계산 가능한 함수 구간으로 이동할 때, 마틴-뢰프 무작위성과 함수 구간(또는 함수 구간)의 미분 가능성 사이의 연결 고리가 취약하다는 것을 나타낸다. 티토프의 이전 연구는 유계 변화 함수가 무작위 지점에서 미분 가능하다는 것을 보여주었으나, 함수 구간을 통한 S2a-가해성의 특정한 기능적 특징화는 (무한 진동이나 무계 성장과 같은) 행동을 허용하여 유일한 도함수(derivative)의 정의를 방해한다.
• 열린 문제들: 저자들은 다음과 같은 몇 가지 열린 문제를 제시한다:
  1. 어떤 실수 쌍 $(\alpha, \beta)$가 번역 함수 구간을 허용하는지 정확히 결정하는 것.
  2. 더 약한 형태의 극한 정리(예: 단측 미분 가능성)가 성립하는지 여부.
  3. 마틴-뢰프 무작위성이 함수 구간의 미분 가능성 성질을 통해 특징지어질 수 있는지 여부.
  4. 다른 버전의 솔로베이 가해성과 더 강한 무작위성 개념 사이의 연결 탐구.

저자들은 자신들의 연구가 무계 또는 진동하는 성장을 이용한 무작위성 테스트의 구축에 있어, 계산 가능한 함수와 반계산 가능한 함수 구간의 행동 사이에 존재하는 근본적인 차이를 강조한다는 점을 분명히 한다.