← Back to arXiv
arXivLogicarXiv:2608.15750

S2a-reducibility and differentiation in Martin-L\"of random reals

The paper deals with a technical area of mathematics that sits at the intersection of computability theory and the study of randomness. At the heart of it is a concept called Solovay reducibility, which is a way of comparing two real numbers by asking how well one can be approximated given information about how the other is being approximated. Specifically, if you have two numbers that can each be approached from below by computable sequences of rational numbers, one number is Solovay reducible to the other if the gaps between each number and its approximation stay in a bounded ratio. A landmark result connects this to Martin-Lof randomness, which is the standard mathematical definition of what it means for a real number to be "truly random." The Kucera-Slaman theorem says that if one number is random in this sense, then any other number of the relevant type is Solovay reducible to it. A later strengthening by Barmpalias and Lewis-Pye showed something even more precise: not only are those approximation ratios bounded, they actually converge to a definite limit, and that limit does not depend on which particular approximating sequences you chose.

Researchers have been trying to extend these ideas beyond the original setting to larger classes of real numbers. Solovay reducibility works naturally for a restricted class called left-c.e. reals, but many numbers fall outside this class. Two proposed extensions are called S2a-reducibility and monotone Solovay reducibility. Recent work showed that monotone Solovay reducibility behaves very nicely: both the Kucera-Slaman theorem and the Barmpalias-Lewis-Pye convergence result carry over to it cleanly. This naturally led researchers to wonder whether S2a-reducibility enjoys the same good properties, and a specific conjecture was put forward saying that it should, based on a known functional characterization of S2a-reducibility.

The main contribution of this paper is to prove that conjecture wrong. The authors show that the analogue of the Barmpalias-Lewis-Pye limit theorem fails for S2a-reducibility. In other words, when you use S2a-reducibility instead of Solovay or monotone Solovay reducibility, those approximation ratios need not converge to a limit, even when one of the numbers involved is Martin-Lof random. This result draws a meaningful boundary between the two proposed extensions, showing that S2a-reducibility behaves more poorly in this respect and is therefore a less natural generalization of the original theory.

Read original →