Cardinality of the K-cones below a non infinitely often K-trivial
Abstract
Given a real x∈ 2ω, how many reals are there that are simpler (or equally simple) to describe than x. With ``simpler to describe" characterized by K-complexity of initial segments (hence we call such y with y≤K x a solution to x), if x is infinitely often K-trivial (hence i.o. K-trivial), then a simple counting argument shows that the number of solutions to x is countable. If x is non i.o. K-trivial, then must it admit uncountably many solutions? Motivated by this question, we show that: (1) There is a non i.o. K-trivial x such that most of its solution is i.o. K-trivial. i.e., Only countably many solution to x are non i.o. K-trivial. In particular, the cardinality of K-degree of x is countable. (2) There is a minimal pair of K-degree (meaning their common solutions are all K-trivial) so that each of the pair is non i.o. K-trivial, generalizing a result of Csima and Montalbán (where the pair is not required to be non i.o. K-trivial but non K-trivial). (3) There is a non i.o. K-trivial x whose ΔK complexity grows arbitrarily slow (in a weak sense: infm≥ nΔK(xupharpoonright m)≤ h(n) with h a given unbounded and nondecreasing function) such that x admits uncountably many solutions. (4) An ample excess lemma holds for non i.o. K-trivial. Namely: ∑n 2−(K(xupharpoonright n)− log2 n)<∞. for all non i.o. K-trivial x. Actually, this even holds for non i.o. b-K-trivial with b only depends on the universal prefix free machine. The same argument also gives a constant complexity return phenomenon for K-trivial where this constant only depends on the universal prefix free machine.
Related
- Below what training size do deep tabular generators stop beating trivial baselines? A preregistered benchmark on a size ladder of clinical and standard datasets
- Consistency: A Critical but Often Overlooked Requirement for Causal Inference in Psychological Research
- An equality condition for the Dobrushin bound on attention rollout and how often it holds in trained transformers
- An Exact Noise Floor for Contingency-Table Effect Sizes: A Per-Table Reporting Gate, and How Often It Would Change Reported Magnitudes
- Hard unknots are often easy from a different perspective
BibTeX
@misc{barmpalias2026cardinality,
title = {{Cardinality of the K-cones below a non infinitely often $K$-trivial}},
author = {George Barmpalias and Lu Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39172},
eprint = {2610.39172},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39172},
}
RIS
TY - UNPB
TI - Cardinality of the K-cones below a non infinitely often K-trivial
AU - George Barmpalias
AU - Lu Liu
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39172
UR - https://arxiv.org/abs/2610.39172
AB - Given a real x∈ 2^ω, how many reals are there that are simpler (or equally simple) to describe than x. With ``simpler to describe" characterized by K-complexity of initial segments (hence we call such y with y≤_K x a solution to x), if x is infinitely often K-trivial (hence i.o. K-trivial), then a simple counting argument shows that the number of solutions to x is countable. If x is non i.o. K-trivial, then must it admit uncountably many solutions? Motivated by this question, we show that: (1) There is a non i.o. K-trivial x such that most of its solution is i.o. K-trivial. i.e., Only countably many solution to x are non i.o. K-trivial. In particular, the cardinality of K-degree of x is countable. (2) There is a minimal pair of K-degree (meaning their common solutions are all K-trivial) so that each of the pair is non i.o. K-trivial, generalizing a result of Csima and Montalbán (where the pair is not required to be non i.o. K-trivial but non K-trivial). (3) There is a non i.o. K-trivial x whose Δ_K complexity grows arbitrarily slow (in a weak sense: inf_m≥ nΔ_K(xupharpoonright m)≤ h(n) with h a given unbounded and nondecreasing function) such that x admits uncountably many solutions. (4) An ample excess lemma holds for non i.o. K-trivial. Namely: ∑_n 2^−(K(xupharpoonright n)− log_2 n)<∞. for all non i.o. K-trivial x. Actually, this even holds for non i.o. b-K-trivial with b only depends on the universal prefix free machine. The same argument also gives a constant complexity return phenomenon for K-trivial where this constant only depends on the universal prefix free machine.
ER -