The claim
Notation, from LIT-239 Appendix B:
- For a total recursive p, l_x(p) = min{|d| : p(d) = x}.
- Its randomness deficiency is δ(x | p) = l_x(p) − K(x | p).
- β_x(α) = min{δ(x | S) : S ∋ x, K(S) ≤ α}, over finite sets.
- β^tot_x(α) = min{δ(x | p) : x ∈ range p, K(p) ≤ α}, over total recursive functions. This one is the record’s notation.
For x of length n and every α:
β^tot_x(α + O(1)) ≤ β_x(α) + O(1) and β_x(α + O(log n)) ≤ β^tot_x(α) + O(log n).
Hence the strings of Corollary IV.9 keep their shape under total recursive models. Take k = α₀ = n − √n. There are strings x of length n and complexity n − √n ± O(log n) such that:
- every total recursive model of complexity at most n − √n − O(log n) leaves deficiency at least √n − O(log n);
- some total recursive model of complexity n − √n + O(log n) has deficiency O(log n).
Their simplest model with logarithmic deficiency has complexity near n.
The argument
-
From sets to functions. Proposition B.1(b) turns any finite S ∋ x into a total p with K(p) = K(S) + O(1), l_x(p) ≤ log |S| and δ(x | p) ≤ δ(x | S) + O(1). This gives the first inequality.
-
From functions to sets. Proposition B.2(b) turns a total p into a set S ∋ x with K(S) ≤ K(p) + K(l_x(p)) + c and δ(x | S) ≤ δ(x | p) + 2 log K(p) + K(l_x(p)) + 2 log K(l_x(p)) + c.
- These terms are O(log n) once K(p) ≤ n + O(log n) and l_x(p) ≤ n + O(1).
- Remark B.3 makes that restriction free. For every p there is p′ with K(p′) ≤ min{K(p), n} + O(log n), δ(x | p′) ≤ δ(x | p) + O(log n) and l_x(p′) ≤ min{l_x(p), n} + 1.
- Composing the two gives the second inequality.
-
Non-stochastic strings. Corollary IV.9 with k = α₀ = n − √n, as the paper applies it in §VI-D, gives the following for the finite-set functions:
- β_x(i) > √n − C log n for i ≤ n − √n − C log n;
- β_x(i) < C log n for i ≥ n − √n + C log n.
Substituting through steps 1 and 2 moves each threshold, and each bound, by O(log n). That gives the claim.
The record checked steps 1 and 2 against the text of Appendix B (NOTE-787). The record’s own contribution is the substitution in step 3.
A correction it carries
LIT-239 §VI-D says the deficiency is about √n “with respect to … every other finite set of complexity less than n − O(log n)”. Corollary IV.9 gives this only below n − √n − O(log n). It cannot hold above K(x), since the singleton {x} has complexity K(x) + O(1) ≈ n − √n and deficiency O(1). NOTE-787 repeats the paper’s phrase. The statement above uses the corollary’s bound.
Where it is used
- THEORY-260, promoted at version 2, whose second clause asks for strings whose sophistication is near their length. LIT-229 proves this directly for total functions at constant precision (Theorem 6.5(iv)). This claim is the independent route through LIT-239. It meets the clause at logarithmic precision, which is the precision THEORY-260 claims for the agreement of the classes.
What it does not say
- Nothing at constant precision. LIT-229’s sophistication counts f as sufficient when K(f) + l_x(f) =⁺ K(x). Converting a deficiency of O(log n) into that condition costs further logarithmic terms, and this claim does not argue it.
- Nothing about how many strings are non-stochastic. Corollary IV.9 gives existence, not frequency.