Algorithmic and Provable Precision of Monotone Approximations
Version 1 / Nov 18, 2026 / CC BY 4.0
Abstract
We study how much information is needed to approximate a monotone limit and when arithmetic can prove that a finite approximation is accurate. For an eventually constant computable descending approximation in an effective partial order, we identify the minimum description length of an adequate stage bound with the one-sided algorithmic rate-distortion complexity of its limit, up to a uniform additive constant. For integer limits, this is also the complexity of a coarse quotient. Finite proof maxima give normal forms for bounded reflection and refutation completeness, and determine every provably sufficient budget. Under soundness for the positive and negative threshold families and refutation completeness at the chosen rank, the least provable error is the difference between the true threshold and its greatest provable lower bound. This difference retains the joint information in two opposing monotone limits. Chaitin counts give matching precision and Busy Beaver bounds, including a maximum law for finitely many fixed reference machines. We also obtain sharp advice bounds for variable certificate presentations, fixed-rank refutations over a finite arithmetic base, an elementary verified selector for bounded positive reflection under explicit proof-presentation assumptions, and resource bounds for proof translation.
Provenance statement
Tools used
- OpenAI
- Codex
References
- M. Andreev. Busy beavers and Kolmogorov complexity. arXiv:1703.05170, 2017. https://arxiv.org/abs/1703.05170v1.arXiv
- L. Antunes, B. Bauwens, A. Souto, and A. Teixeira. Sophistication vs Logical Depth. Theory of Computing Systems 60(2) (2017), 280--298. https://doi.org/10.1007/s00224-016-9672-6. Preprint: https://arxiv.org/abs/1304.8046v3.DOI
- S. Artemov. Serial properties, selector proofs and the provability of consistency. Journal of Logic and Computation 35(3) (2025), exae034; published online 26 July 2024. https://doi.org/10.1093/logcom/exae034. Preprint: https://arxiv.org/abs/2403.12272v1.DOI
- L. D. Beklemishev. Reflection principles and provability algebras in formal arithmetic. Russian Mathematical Surveys 60(2) (2005), 197--268. https://doi.org/10.1070/RM2005v060n02ABEH000823.DOI
- R. Blanck. Hierarchical incompleteness results for arithmetically definable extensions of fragments of arithmetic. The Review of Symbolic Logic 14(3) (2021), 624--644. https://doi.org/10.1017/S1755020321000307.DOI
- C.-L. Chang, Y.-D. Lyuu, Y.-W. Ti, and A. Shen. Sets of k-independent strings. Author manuscript. https://www.lirmm.fr/~ashen/nafit/2009-indep.pdf.link
- E. Gadsby. Properties of Selector Proofs. arXiv:2509.19373, 2025. https://arxiv.org/abs/2509.19373v1.arXiv
- I. Hasuo. Introduction to Logic and Computability . Author's textbook, version 20 April 2022, §5.1. https://group-mmm.org/~ichiro/papers/textbook_inflogic_pub_202204.pdf.link
- J. J. Joosten. Characterizations of interpretability in bounded arithmetic. arXiv:1602.00555, 2016. https://arxiv.org/abs/1602.00555v1.arXiv
- M. Koucký. A Brief Introduction to Kolmogorov Complexity. Lecture notes, 4 May 2006. https://iuuk.mff.cuni.cz/~koucky/papers/kolmcomp.pdf.link
Show all 15 referencesShow fewer references
- E. Nelson. Elements. Manuscript dated 12 March 2013; published posthumously with an afterword by S. Buss and T. Tao, 2015. https://arxiv.org/abs/1510.00369v1.link
- P. Pudlák. The Lengths of Proofs. In S. R. Buss (ed.), Handbook of Proof Theory , Elsevier, 1998. https://users.math.cas.cz/~pudlak/length.pdf.link
- A. S. Troelstra and H. Schwichtenberg. Basic Proof Theory , second edition. Cambridge University Press, 2000, Chapter 4. https://doi.org/10.1017/CBO9781139168717.DOI
- N. K. Vereshchagin and P. M. B. Vitányi. Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity. IEEE Transactions on Information Theory 56(7) (2010), 3438--3454. https://doi.org/10.1109/TIT.2010.2048491.DOI
- A. Visser. Friedman-reflexivity: interpreters as consistoids. arXiv:2111.14413, version 2, 2022. https://arxiv.org/abs/2111.14413v2.arXiv
Version history
- v1 · 42 pagesSubmitted by Zhenyu SunInitial depositCurrentNov 17, 2026