Lowness for integer-valued randomness

Theorem 2.1.

If A > T ∅ , then A is not in Low ( IVR ) .

Proof.

We construct from A > T ∅ an integer-valued martingale M that succeeds on a set B ∈ IVR .

The martingale M is very easily constructed. Simply put, it is the martingale that for each n, bets 1 quantum that the nth bit it sees will be the nth bit of A (unless it has run out of capital) and for concreteness starts with initial capital 1. More formally, M ( ⟨ ⟩ ) = 1 and for any σ, if M ( σ ) ⩾ 1 then M ( σ ⌢ A ( | σ | ) ) = M ( σ ) + 1 and M ( σ ⌢ A ‾ ( | σ | ) ) = M ( σ ) − 1 , and otherwise M ( σ ⌢ i ) = 0 for i ∈ { 0 , 1 } . Here and further ⟨ ⟩ denotes the empty string, the smallest element of 2 < ω . It is clear that this M is an integer-valued martingale recursive in A.

The construction of B will be more complicated. We want B to be ‘random enough’ that any recursive integer-valued martingale will fail to win along B, while still including enough bits of A that M can succeed on it. We note that, since the only hypothesis on A is that it is not recursive, A itself could be very far from random. We will build B Turing-below A ⊕ ∅ ′ , at each stage s deciding the next bit of B in trying to defeat one of the integer-valued martingales. We use ( ϕ e ) e ∈ ω as an effective listing of all partial recursive functions from 2 < ω to N . Several of these will not give integer-valued martingales, but these will be identified as the construction progresses and subsequently ignored.

The idea of the construction is to build B such that each ϕ e either loses all its capital or stops betting on any further bits, while ensuring that M’s capital goes to infinity. For clarity we will partition M’s capital, M ( σ ) , for each σ ≺ B , into a Reserve Bank R ( σ ) = 1 and Gamblers G 0 ( σ ) , G 1 ( σ ) , G 2 ( σ ) , … (only finitely many of which will be non-zero for a given σ), each trying to defeat a single partial recursive function. If we ensure that infinitely many G i are eventually at least 1 on a cofinal segment of the set B then M must succeed on B. Each G i will start with value 0, but will eventually be initialized and given capital by the construction. We know that the martingale M bets 1 quantum at each bit, so at each stage at most one G i will change its value, and that by at most 1 quantum. We choose each bit of B in order to defeat some ϕ e and so the gain or loss of 1 quantum worth of capital can be credited or debited to the G e on whose behalf we make this decision. That is, since for any σ, M ( σ ⌢ A ( | σ | ) ) = M ( σ ) + 1 , we will have for any σ there is a single e such that G e ( σ ⌢ A ( | σ | ) ) = G e ( σ ) + 1 and for all other d ≠ e , G d ( σ ⌢ 0 ) = G d ( σ ⌢ 1 ) = G d ( σ ) . Similarly, for any σ, M ( σ ⌢ A ‾ ( | σ | ) ) = M ( σ ) − 1 , so if we extend σ with a bit from A ‾ then exactly one G e will decrease by 1 and all others will remain unchanged.

The strategy for defeating a single ϕ e will be relatively simple. As long as G e ( σ ) is less than ϕ e ( σ ) we choose the next bit of B to be the corresponding bit of A or A ‾ that increases the proportion G e ϕ e as much as possible, using the convention that n 0 = ∞ for any n ⩾ 0 (it is good for us if both ϕ e and the Gambler G e go bankrupt; we can always give G e more capital from the bank). It should be clear that the ratio G e ϕ e can decrease in at most one direction, depending on whether ϕ e ’s bet is greater than or less than 1 G e times ϕ e ’s capital, since G e is wagering exactly 1 G e times G e ’s capital. If ϕ e bets on the bit of A ‾ , then this does not matter and we can increase G e while decreasing ϕ e , otherwise we choose the extension for which the ratio in non-decreasing. In the case that the proportion is the same in both directions, we choose the direction that decreases both G e and ϕ e . Now, A can compute M and ∅ ′ can determine whether ϕ e ( σ ⌢ 1 ) and ϕ e ( σ ⌢ 0 ) will converge (and if they do we can wait for ϕ e to give their values), so A ⊕ ∅ ′ can compute the effect extending B in either direction will have on the proportion G e ϕ e . In the case that one of these does not converge, we extend B as we wish and can henceforward ignore ϕ e . Once G e ( σ ) ⩾ ϕ e ( σ ) we can afford to choose the bit of B that will decrease ϕ e each time that ϕ e bets. So, either it must stop betting or we can reduce its capital to 0 along an initial segment of our B.

The problem, of course, is getting from G e < ϕ e to G e ⩾ ϕ e . As long as ϕ e bets on the bits of A with wagers exactly proportional to those of G e , then this ratio might remain unchanged and we may be unable to increase M’s capital or be forced to interfere with the actions of other strategies infinitely often. Luckily, this cannot happen. M always bets that the bits we see will be the bits of A, and if the ratio is unchanging then ϕ e must be betting the same way. However, this procedure for choosing bits of B is recursive in e, the finite initial segment σ, and the capitals G e ( σ ) and ϕ e ( σ ) . Thus, if at every step ϕ e bets on the next bit of A we would have a procedure for computing a cofinal segment of the set A. Since A is non-recursive, this procedure must fail at some finite stage. Either ϕ e fails to converge at some level, or it converges but does not bet or bets the bit of A ‾ . In the first case we win easily, and in either of the other cases we gain an absolute advantage. Since this must happen infinitely often, we will eventually get G e ( B ↾ m ) ⩾ ϕ e ( B ↾ m ) , although showing that this slow grind eventually gets us there will be the most complicated part of the proof.

Weaving the strategies for the different ϕ e s together is then a matter of letting the earliest one of the strategies which has G e ( B ↾ s ) > 0 and either ϕ e making a bet or ϕ e not betting but G e ( B ↾ s ) < ϕ e ( B ↾ s ) be the strategy which chooses how to extend B ↾ s . If none of the strategies before the first uninitialized G i are in such a position (so in particular no ϕ e that we are still concerned about is betting), we merely extend B with the next bit of A to get 1 quantum more of capital that we use to initialize this G i . We can think of the Reserve Bank R fronting the capital for this bet and then donating it to G i , since G i itself cannot bet. The construction has some of the flavor of a priority argument.

We now give the formal construction of B, using A ⊕ ∅ ′ .

A partial recursive function ϕ e is active at a stage s of the construction if for every t < s , ϕ e ( B ↾ t ) ↓ , ϕ e ( B ↾ t ) = 1 2 ϕ e ( B ↾ t ⌢ 0 ) + 1 2 ϕ e ( B ↾ t ⌢ 1 ) when these all converge, ϕ e ( B ↾ t ⌢ 0 ) ↓ if and only if ϕ e ( B ↾ t ⌢ 1 ) ↓ , and both ϕ e ( B ↾ t ⌢ 0 ) and ϕ e ( B ↾ t ⌢ 1 ) are in N , if they are defined. In essence, ϕ e is active as long as it looks like at least a partial recursive integer-valued martingale that has converged along the current initial segment of B.

We will say that a number e requires attention at a stage s if any of the following hold:

G e ( B ↾ s − 1 ) = 0 ;

ϕ e is active at that stage and one of the following holds:

For both i ∈ { 0 , 1 } , ϕ e ( B ↾ s − 1 ⌢ i ) ↑ ;

For both i ∈ { 0 , 1 } , ϕ e ( B ↾ s − 1 ⌢ i ) ↓ = ϕ e ( B ↾ s − 1 ) > G e ( B ↾ s − 1 ) ;

For both i ∈ { 0 , 1 } , ϕ e ( B ↾ s − 1 ⌢ i ) ↓ and ϕ e ( B ↾ s − 1 ⌢ i ) ≠ ϕ e ( B ↾ s − 1 ) .

The construction is as follows. Stage 0.

Set B ↾ 0 = ⟨ ⟩ and for all i, set G i ( ⟨ ⟩ ) = 0 .

Stage s + 1.

For the smallest e that requires attention:

If e requires attention due to clause 1, 2a or 2b, then:

Let B ( s ) = A ( s ) ;

Then G e ( B ↾ s + 1 ) = G e ( B ↾ s ) + 1 and all other G d ( B ↾ s + 1 ) = G d ( B ↾ s ) .

If e requires attention due to clause 2c, then:

Compute the ratios [ G e ( B ↾ s ) + 1 ] / ϕ e ( B ↾ s ⌢ A ( s ) ) and [ G e ( B ↾ s ) − 1 ] / ϕ e ( B ↾ s ⌢ A ‾ ( s ) ) , using n 0 = ∞ for any n ⩾ 0 ;

If [ G e ( B ↾ s ) + 1 ] / ϕ e ( B ↾ s ⌢ A ( s ) ) > [ G e ( B ↾ s ) − 1 ] / ϕ e ( B ↾ s ⌢ A ‾ ( s ) ) , then let B ( s ) = A ( s ) , G e ( B ↾ s + 1 ) = G e ( B ↾ s ) + 1 and all other G d ( B ↾ s + 1 ) = G d ( B ↾ s ) ;

Otherwise, let B ( s ) = A ‾ ( s ) , G e ( B ↾ s + 1 ) = G e ( B ↾ s ) − 1 and all other G d ( B ↾ s + 1 ) = G d ( B ↾ s ) .

This ends the construction. It remains to verify that B is in IVR but not in IVR A . To show that no integer-valued martingale succeeds on B, we show that each e will require attention only finitely often in the construction. Since every time ϕ e bets on a bit e requires attention, this will ensure that ϕ e bets only finitely often, and so cannot win infinitely much capital. Lemma 2.2.

For any e ∈ N , the number e requires attention at only finitely many stages of the construction.

Proof.

We take an e ∈ N and assume that the statement in the lemma holds for all d < e . Then we may assume we are at some stage s such that no d < e will ever require attention at a stage later than s. Thus, if e requires attention at a stage t > s we will act on e’s behalf at that stage. If ϕ e ever ceases to be active, it will remain inactive for the rest of the construction, and so e will only require attention due to clause 1, and that only once.

If at any stage t > s the number e requires attention due to clause 2a, then ϕ e is partial along B and will not be active after stage t. Acting on e’s behalf at this stage t will increase G e to at least 1, so e will never require attention again.

If at a stage t > s the number e requires attention due to clause 1, then B ( t ) = A ( t ) and G e ( B ↾ t ) = 1 , so in general e will not require attention for this reason again. There is only one possible exception: at some later stage r > t , e requires attention due to clause 2c (in any of the other cases G e increases) and G e ( B ↾ r ) = 1 and ϕ e ( B ↾ r ⌢ A ‾ ( r ) ) = 0 . In this case, the ratio G e ( B ↾ r ) − 1 / ϕ e ( B ↾ r ⌢ A ‾ ( r ) ) = ∞ will be the largest possible, and so the construction will set B ( r ) = A ‾ ( r ) and both G e and ϕ e will lose all their capital. Then at stage r + 1 the number e will require attention due to clause 1 again and G e will be given its new 1 quantum of capital. However, since ϕ e ( B ↾ r ) = 0 , as long as ϕ e obeys the martingale property it can no longer bet, so it will no longer cause e to require attention, either through becoming inactive or through never betting.

Thus, if e requires attention at infinitely many stages it must be the case that at infinitely many of these stages e requires attention due to clauses 2b and 2c. We make a small sublemma about how the size of ϕ e ’s bet in clause 2c effects our action at a given stage. Sublemma 1.

Let r be a stage when e is the least number that requires attention and for which there is an n > 0 such that ϕ e ( B ↾ r − 1 ⌢ A ( r − 1 ) ) = ϕ e ( B ↾ r − 1 ) + n . Then B ( r − 1 ) = A ( r − 1 ) if and only if G e ( B ↾ r − 1 ) / ϕ e ( B ↾ r − 1 ) < 1 n .

Proof.

We first assume that G e ( B ↾ r − 1 ) / ϕ e ( B ↾ r − 1 ) < 1 n . This inequality gives us that n · G e ( B ↾ r − 1 ) < ϕ e ( B ↾ r − 1 ) , so either G e ( B ↾ r − 1 ) = 0 or n < ϕ e ( B ↾ r − 1 ) . If G e ( B ↾ r − 1 ) = 0 , then e requires attention at stage r due to clause 1, and so we will extend B by setting B ( r − 1 ) = A ( r − 1 ) , so the implication holds in this case. Otherwise, we may assume n < ϕ e ( B ↾ r − 1 ) . Multiplying the previous inequality by − 1 gives us − ϕ e ( B ↾ r − 1 ) < − n · G e ( B ↾ r − 1 ) . We add these two inequalities to get that n · G e ( B ↾ r − 1 ) − ϕ e ( B ↾ r − 1 ) < ϕ e ( B ↾ r − 1 ) − n · G e ( B ↾ r − 1 ) . We now add term G e ( B ↾ r − 1 ) · ϕ e ( B ↾ r − 1 ) − n to both sides, yielding G e ( B ↾ r − 1 ) · ϕ e ( B ↾ r − 1 ) + n · G e ( B ↾ r − 1 ) − ϕ e ( B ↾ r − 1 ) − n < G e ( B ↾ r − 1 ) · ϕ e ( B ↾ r − 1 ) + ϕ e ( B ↾ r − 1 ) − n · G e ( B ↾ r − 1 ) − n . This factors to [ G e ( B ↾ r − 1 ) − 1 ] [ ϕ e ( B ↾ r − 1 ) + n ] < [ G e ( B ↾ r − 1 ) + 1 ] [ ϕ e ( B ↾ r − 1 ) − n ] , which gives us the inequality G e ( B ↾ r − 1 ) − 1 ϕ e ( B ↾ r − 1 ) − n < G e ( B ↾ r − 1 ) + 1 ϕ e ( B ↾ r − 1 ) + n . Since we choose the next bit of B depending on which of these two ratios is larger, in this case we extend by B ( r − 1 ) = A ( r − 1 ) .

We can similarly show that if G e ( B ↾ r − 1 ) / ϕ e ( B ↾ r − 1 ) ⩾ 1 n , then the inequality G e ( B ↾ r − 1 ) − 1 ϕ e ( B ↾ r − 1 ) − n ⩾ G e ( B ↾ r − 1 ) + 1 ϕ e ( B ↾ r − 1 ) + n holds, and so we would extend B with B ( r − 1 ) = A ‾ ( r − 1 ) .

We note that in either case a similar argument shows that [ G e ( B ↾ r ) / ϕ e ( B ↾ r ) ] ⩾ [ G e ( B ↾ r − 1 ) / ϕ e ( B ↾ r − 1 ) ] . □

To return to the proof of Lemma 2.2, we note that if we are ever at a stage r > s when G e ( B ↾ r − 1 ) ⩾ ϕ e ( B ↾ r − 1 ) , then, since no other d will affect these quantities, e will never again require attention due to clause 2b, and every time it requires attention due to clause 2c, we will achieve ϕ e ( B ↾ r ) < ϕ e ( B ↾ r − 1 ) . Either ϕ e will bet that the next bit will be A ‾ ( r ) , in which case we will extend B ( r ) = A ( r ) and reduce ϕ e by its bet and increase G e by 1, which increases the ratio of these quantities, or ϕ e will bet that the next bit is A ( r ) , in which case by the sublemma, since G e ( B ↾ r − 1 ) / ϕ e ( B ↾ r − 1 ) ⩾ 1 it is not less than 1 n for ϕ e ’s bet n and so we will extend by B ( r ) = A ‾ ( r ) and ϕ e will lose its bet. Since this is a strict decrease, e can only require attention finitely many more times after this inequality is achieved.

All that remains to be shown is that e cannot require attention infinitely often without achieving G e ( B ↾ r − 1 ) ⩾ ϕ e ( B ↾ r − 1 ) . If there is ever a stage t > s when e does not require attention, then, since clause 2c does not hold, ϕ e must not be betting, and since clause 2b does not hold, we must have that G e ( B ↾ t − 1 ) ⩾ ϕ e ( B ↾ t − 1 ) . Thus, if e requires attention infinitely often it must moreover require attention for a cofinal segment of the stages. We appeal to A’s non-recursiveness to show this cannot happen.

If one has an initial segment B ↾ r − 1 of B, the finite values G e ( B ↾ r − 1 ) and ϕ e ( B ↾ r − 1 ) , and the knowledge that e is the least number that requires attention at stage r and that ϕ e bets that the next bit will be A ( r ) , then according to the sublemma one can compute (obviously) the bit A ( r ) , but also the bit B ( r ) and the values G e ( B ↾ r ) and ϕ e ( B ↾ r ) . If one knows that these hypotheses hold for r + 1 , one could then repeat this process. Thus, if we were in the hypotheses of the sublemma for all r in the interval [ t , ∞ ) , that is, if for all these r, e is the least number that requires attention at stage r and ϕ e is betting that the next bit will be A ( r ) , then we could compute A ( r ) for all r > t , using only a finite amount of information. Since A is not recursive, this cannot happen, so it must be the case that we are only ever in the hypotheses of the sublemma for finite intervals. That is, if e requires attention infinitely often, it must be the case that at infinitely many of these stages it either does so due to clause 2b, or it does so due to clause 2c, but bets that the next bit is A ‾ ( r ) . Importantly, this means that if e requires attention infinitely often, then infinitely often we get an r such that G e ( B ↾ r ) = G e ( B ↾ r − 1 ) + 1 while ϕ e ( B ↾ r ) ⩽ ϕ e ( B ↾ r − 1 ) .

We now show that we must eventually achieve G e ( B ↾ r − 1 ) ⩾ ϕ e ( B ↾ r − 1 ) . If we ever reach a stage r such that ϕ e never bets at any stage t > r , then for finitely many stages e will require attention due to clause 2b and eventually the inequality G e ( B ↾ r − 1 ) ⩾ ϕ e ( B ↾ r − 1 ) will be satisfied. In the other case, ϕ e must bet infinitely often. We show that even in this case there is eventually an r such that G e ( B ↾ r ) ⩾ ϕ e ( B ↾ r ) . First, fix some stage t > s , and let a = G e ( B ↾ t ) and b = ϕ e ( B ↾ t ) . Let n be largest such that a b < 1 n . We want to show that at some later stage t ′ , G e ( B ↾ t ′ ) / ϕ e ( B ↾ t ′ ) ⩾ 1 n . For any later stage t ′ let w ( t ′ ) be the number of stages between t and t ′ at which both G e and ϕ e increased, l ( t ′ ) be the number of stages between t and t ′ where both quantities decreased, and k ( t ′ ) be the number of stages between t and t ′ where G e increased and ϕ e did not. Note that until G e ( B ↾ t ′ ) ⩾ ϕ e ( B ↾ t ′ ) we have w ( t ′ ) + l ( t ′ ) + k ( t ′ ) = t ′ − t , since in our construction it is impossible for ϕ e to increase while G e does not (if ϕ e bets on the next bit being from A ‾ , then we always extend B by adding the bit from A, which increases G e and decreases ϕ e ). We recall that according to our strategy (and as mentioned at the end of the proof of Sublemma 1) the ratio G e ( B ↾ t ′ ) / ϕ e ( B ↾ t ′ ) is non-decreasing, so if G e ( B ↾ t ′ ) = 0 then so does ϕ e ( B ↾ t ′ ) . Now, at any stage t ′ > t such that G e ( B ↾ t ′ ) / ϕ e ( B ↾ t ′ ) is still less than 1 n , if G e and ϕ e both increase, then by Sublemma 1 ϕ e cannot have bet more than n on the next bit being from A at stage t ′ , while if G e and ϕ e both decrease, then ϕ e must have bet more than n. Thus, until G e ( B ↾ t ′ ) / ϕ e ( B ↾ t ′ ) > 1 n , at any stage t ′ > t , G e ( B ↾ t ′ ) = a + w ( t ′ ) − l ( t ′ ) + k ( t ′ ) and ϕ e ( B ↾ t ′ ) ⩽ b + n · w ( t ′ ) − ( n + 1 ) · l ( t ′ ) . Since, as above, we must infinitely often get stages where only G e increases, we eventually have a t ′ such that n · ( a + k ( t ′ ) ) ⩾ b . For this t ′ , the ratio G e ( B ↾ t ′ ) / ϕ e ( B ↾ t ′ ) will be at least a + k ( t ′ ) + w ( t ′ ) − l ( t ′ ) b + n · w ( t ′ ) − ( n + 1 ) · l ( t ′ ) ⩾ b / n + w ( t ′ ) − l ( t ′ ) b + n · w ( t ′ ) − ( n + 1 ) · l ( t ′ ) ⩾ 1 n . Thus, eventually the ratio increases past 1 n . We can now repeat this argument to show it eventually grows larger than 1 n − 1 , and so on, and so it is eventually larger than 1.

This completes the proof of Lemma 2.2. Each e will require attention only finitely often. □

Using Lemma 2.2 it is easy to see that B will satisfy the required properties. Every time a ϕ e makes a bet the number e requires attention. Since any e requires attention only finitely often, each ϕ e must eventually stop betting along B, either because its capital is reduced to 0 or because it simply never makes another bet. Since one cannot win if one does not play, if ϕ e bets only finitely often it is clear that sup s → ∞ ϕ e ( B ↾ s ) < ∞ .

One the other hand, each G e is eventually greater than 0, since having G e = 0 makes e require attention. Since M ( B ↾ s ) = 1 + ∑ e G e ( B ↾ s ) , it is clear that M ( B ) = sup s → ∞ M ( B ↾ s ) = ∞ . Thus, B ∈ IVR while B ∉ IVR A , and so A is not in Low ( IVR ) . This completes the proof of Theorem 2.1. □

We note that in the proof of Theorem 2.1 the martingale M that we constructed relative to A was in fact a single-valued martingale while the set B we constructed defeated every partial integer-valued martingale, so we get the following corollary. Corollary 2.3.

The classes Low ( FVR ) , Low ( SVR ) and Low ( PIVR ) all consist of only the recursive sets.

3. Further directions

In the study of lowness for various notions of randomness, one may more generally study also lowness for pairs of notions of randomness. This generalized idea was first studied by Kjos-Hanssen, Nies and Stephan in [5]. For randomness classes Q ⊆ R , we define the class Low ( Q , R ) to be the class of all sets A such that Q ⊆ R A . That is, Low ( Q , R ) is the collection of sets such that every set that is random in the sense of Q is, relative to A, at least still random in the sense of R. These sets are ‘too weak’ computationally to make up the difference between Q and R. If Q = R this is just Low ( R ) , but otherwise this class can have some interesting properties. For instance, Kjos-Hanssen, Nies and Stephan proved that Low ( MLR , SR ) is the class of c.e. traceable sets, where SR is the class of Schnorr-random sets. By the same argument that gave us Corollary 2.3, it follows from Theorem 2.1 that the for any Q ⊆ R where Q and R are taken from the classes PIVR , IVR , FVR and SVR we have that Low ( Q , R ) consists of only the recursive sets. However, since integer-valued randomness is a natural weakening of computable randomness, it is reasonable to examine the class Low ( CR , IVR ) . Now, by Theorem 2.1, Low ( IVR ) consists of only recursive sets, and by results of Nies and Bedregal [2,6] the same is true of Low ( CR ) . This means that any non-recursive set A will compute a recursive martingale that succeeds on a computably random set and an integer-valued martingale that succeeds on an integer-valued random set. This may suggest that Low ( CR , IVR ) also contains only recursive sets, but a priori there may be room for an A that is non-recursive but weak enough in terms of computational power that its succeeding against these computable randoms depends in some essential way on the full power of a betting strategy with no minimum bet. We leave the nature of Low ( CR , IVR ) as an open question.