🔢 mathematics

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

This paper refutes Titov's conjecture by proving that the analogue of the Barmpalias-Lewis-Pye Limit Theorem, which establishes the convergence of approximation ratios for Solovay reducibility, does not hold for S2a-reducibility in the context of Martin-Löf random reals.

Original authors: Georgii Sirotenko, Ivan Titov

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Georgii Sirotenko, Ivan Titov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quiet, abstract world of mathematical logic, researchers study the nature of numbers not just as quantities, but as objects that can be built up step by step by a machine. Imagine a number that is not written down all at once, but approached slowly, like a hiker climbing a mountain toward a peak they can never quite touch. Some of these numbers are "computable," meaning a machine can get arbitrarily close to them with perfect precision. Others are "random," meaning they possess a chaotic, unpredictable quality that no machine can ever fully compress or predict. For decades, mathematicians have tried to measure how close these random numbers come to being computable, and how they relate to one another. They developed a system to compare these numbers, asking whether one random number can be "reduced" to another, essentially asking if the first is simpler or more accessible than the second. This comparison relies on how fast the machine's approximation gets closer to the true value. If the machine gets close to one number just as quickly as it gets close to another, the two are considered to be of similar complexity. This field is crucial because it helps define the very boundary between order and chaos in mathematics, revealing which patterns are deep and which are merely accidental.

Recently, a team of researchers in Germany and France set out to test the limits of this comparison system when applied to a broader class of numbers. They were investigating a specific method called S2a-reducibility, which was designed to extend the rules of comparison to all numbers that can be approximated by a machine, not just the simplest ones. A prominent idea in the field suggested that if you take a truly random number and try to approximate it using this new method, the speed at which you get closer would settle down into a steady, predictable rhythm. It was thought that no matter how you chose your path toward the number, the ratio of your progress would eventually smooth out and converge to a single, fixed value. This idea was so compelling that it was proposed as a fundamental law for these complex numbers, much like a law of physics governing how a falling object behaves.

The researchers, Georgii Sirotenko and Ivan Titov, decided to put this idea to the test. They constructed a specific, highly complex random number and then built two different "paths" or functions to approach it. One path was designed to be very smooth and well-behaved, while the other was allowed to be more erratic. Their goal was to see if the ratio of progress along these paths would indeed settle down to a single number, as the prevailing theory predicted. Instead of finding a steady rhythm, they discovered something far more chaotic. They proved that for certain random numbers, the speed of approximation does not settle down at all. Instead, it oscillates wildly, jumping back and forth between different values without ever finding a stable average. In some cases, the ratio of progress would swing from being very slow to being very fast, and then back again, forever.

This finding was a direct refutation of the conjecture that had guided the field. The team demonstrated that the mathematical "law" which promised a smooth, predictable limit for these approximations simply does not hold when you move beyond the simplest types of numbers. They showed that you can have a perfectly random number where the way you approach it from the left is fundamentally different from the way you approach it from the right, and that the speed of your approach can fluctuate infinitely without ever calming down. They also showed that for some pairs of numbers, the speed of approach can become infinitely fast, breaking any notion of a bounded limit. This means that the intuitive idea that randomness implies a certain uniformity in how we approach these numbers is false in this broader context.

The implications of this discovery are significant for the way mathematicians understand the structure of randomness. It suggests that the tools we use to measure the complexity of numbers are more fragile than previously thought. While the old rules worked perfectly for the simplest, most orderly random numbers, they fail when applied to the wider, messier universe of all computable numbers. The researchers did not just find a single exception; they proved that the entire framework of expecting a smooth, convergent limit is incorrect for this specific type of mathematical relationship. Their work does not destroy the field, but it forces a re-evaluation of what we can expect when dealing with complex, random numbers. It reveals that the landscape of mathematical randomness is more rugged and unpredictable than the smooth, steady paths that earlier theories had imagined.

In the end, the paper stands as a correction to a hopeful but incorrect assumption. It shows that in the realm of algorithmic randomness, not every journey toward a number follows a predictable curve. Sometimes, the path is a wild oscillation, and the speed of arrival is a variable that refuses to settle. This result leaves mathematicians with new questions: if the speed of approximation cannot be relied upon to be steady, what other properties can we use to distinguish between different levels of randomness? The search for a better way to measure these elusive numbers continues, now guided by the knowledge that the answer is not always a simple, smooth limit.

Technical Summary: S2a-reducibility and Differentiation in Martin-Löf Random Reals

Problem Statement
The paper addresses the behavior of Solovay reducibility when extended beyond the class of left-c.e. reals to the broader class of computably approximable (c.a.) reals. While Solovay reducibility ( $\le_S$ ) is well-understood on left-c.e. reals—where it characterizes the relative rate of convergence of approximations and aligns with Martin-Löf randomness via the Kučera–Slaman Theorem and the Barmpalias–Lewis-Pye Limit Theorem—its extension to general reals is less stable.

Specifically, the paper investigates S2a-reducibility ( $\le_{2a}^S$ ), a variant introduced by Zheng and Rettinger for c.a. reals. This reducibility is characterized functionally via translation function intervals $(f, h)$ , where $f$ is lower semicomputable, $h$ is upper semicomputable, $f \le h$ , and both converge to the target real at the source real.

The central problem is the validity of Conjecture 24 (proposed by Titov [16]), which posits that the Barmpalias–Lewis-Pye Limit Theorem extends to S2a-reducibility. The conjecture asserts that if $\beta$ is a Martin-Löf random c.a. real and $\alpha \le_{2a}^S \beta$ via a function interval $(f, h)$ , then the ratio $\frac{\alpha - f(x)}{\beta - x}$ (and similarly for $h$ ) must converge to a limit $d$ as $x \to \beta$ . Furthermore, it conjectures that $d \neq 0$ if and only if $\alpha$ is Martin-Löf random.

Methodology
The authors refute Conjecture 24 by constructing a counterexample. The methodology involves a step-wise construction of a computable approximation converging to a specific Martin-Löf random real $\beta$ , alongside the definition of specific translation function intervals.

Construction of $\beta$ : The authors construct a Martin-Löf random real $\beta$ using a computable approximation $b_0, b_1, \dots$ that avoids a universal Martin-Löf test. Crucially, this approximation is designed to have "gaps" near $\beta$ . Specifically, they ensure the existence of a sequence of intervals $[l_i, r_i]$ such that $\beta$ lies arbitrarily close to the endpoints of these intervals, but no element of the approximation sequence $b_n$ falls strictly inside these intervals. This property is formalized in Lemma 26.
Construction of Function Intervals:
- Case 1 (Bounded but Oscillating): A function interval $(-h, h)$ from $\beta$ to $0$ is constructed. The function $h(x)$ is defined as the infimum of distances from $x$ to the approximation sequence $b_n$ . This function is Lipschitz continuous with constant 1. The authors demonstrate that while the ratio $\frac{|0 - h(x)|}{|\beta - x|}$ is bounded, it oscillates infinitely between 0 and 1 as $x \to \beta$ from both sides, failing to converge.
- Case 2 (Unbounded Growth): A function interval $(\tilde{f}, \tilde{h})$ from $\beta$ to $\beta$ is constructed using hypographs and epigraphs defined by the approximation sequence. These functions are nondecreasing and semicomputable. The authors show that the ratios $\frac{|\beta - \tilde{f}(x)|}{|\beta - x|}$ and $\frac{|\beta - \tilde{h}(x)|}{|\beta - x|}$ are unbounded as $x \to \beta$ .

Key Contributions and Results
The primary contribution is the proof of Theorem 25, which establishes the existence of a c.a. Martin-Löf random real $\beta$ and specific function intervals that violate the conditions of Conjecture 24.

Refutation of the Limit Theorem: The paper proves that the Barmpalias–Lewis-Pye Limit Theorem does not hold for S2a-reducibility. Specifically, for the constructed $\beta$ and the function interval $(-h, h)$ from $\beta$ to $0$:
$\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|$
This demonstrates that the approximation ratio does not converge, contradicting the conjecture that it must converge to a derivative-like constant.
Failure of Boundedness: The construction of $(\tilde{f}, \tilde{h})$ shows that even for a reduction from a random real to itself, the ratio can be unbounded, violating the boundedness requirement often associated with Solovay-type reducibilities in the context of randomness.
Implication for Speedability: The authors note (Remark 27) that the existence of such function intervals excludes the possibility of introducing a nontrivial "speedability" notion for S2a-reducibility based on functional characterizations, as the convergence behavior is too erratic.

Significance and Claims
The paper claims to settle the question of whether the strong limit properties of Solovay reducibility on left-c.e. reals extend to the functional characterization of S2a-reducibility on all c.a. reals. The authors conclude that it does not.

Differentiation vs. Randomness: The results indicate that the connection between Martin-Löf randomness and the differentiability of translation functions (or function intervals) is fragile when moving from computable functions on rationals to semicomputable function intervals. While Titov's previous work showed that bounded variation functions are differentiable at random points, the specific functional characterization of S2a-reducibility via function intervals allows for behaviors (infinite oscillation and unbounded growth) that prevent the definition of a unique derivative.
Open Questions: The paper modestly identifies several open problems:
1. Determining exactly which pairs of reals $(\alpha, \beta)$ admit a translation function interval.
2. Whether a weaker form of the limit theorem holds (e.g., one-sided differentiability).
3. Whether Martin-Löf randomness can be characterized via differentiability properties of function intervals.
4. Exploring connections between other versions of Solovay reducibility and stronger randomness notions.

The authors emphasize that their work highlights a fundamental difference between the behavior of computable functions and semicomputable function intervals regarding the construction of randomness tests from unbounded or oscillating growth.

Technical Summary: S2a-reducibility and Differentiation in Martin-Löf Random Reals

More like this