% !TeX program = pdflatex % Layout adapted from the public TeX source of arXiv:2611.18218v1. \documentclass[12pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage[top=2cm,bottom=2cm,left=2.5cm,right=2cm]{geometry} \usepackage{microtype,enumitem,xcolor} \usepackage[bottom]{footmisc} \usepackage[colorlinks=true,allcolors=blue]{hyperref} \hypersetup{pdftitle={Algorithmic and Provable Precision of Monotone Approximations},pdfauthor={Zhenyu Sun},pdfsubject={Kolmogorov complexity, bounded reflection, and provable precision}} \emergencystretch=2em \pagestyle{plain} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\EA}{\mathsf{EA}} \newcommand{\PA}{\mathsf{PA}} \newcommand{\Q}{\mathsf Q} \newcommand{\Con}{\operatorname{Con}} \newcommand{\Prf}{\operatorname{Prf}} \newcommand{\Prov}{\operatorname{Prov}} \newcommand{\RFN}{\operatorname{RFN}} \newcommand{\BC}{\mathsf{BC}} \newcommand{\Adeq}{\mathsf A} \newcommand{\DW}{\mathsf{DW}} \newcommand{\qr}{\operatorname{qr}} \newcommand{\rk}{\operatorname{rk}} \newcommand{\BB}{\mathsf B} \newcommand{\BT}{\mathsf T} \newcommand{\RD}{\mathcal R} \newcommand{\bd}[1]{\overline{#1}} \newcommand{\code}[1]{\ulcorner #1\urcorner} \newcommand{\seq}{\Rightarrow} \newcommand{\dm}{\mathbin{\dot{-}}} \newcommand{\ceil}[1]{\left\lceil #1\right\rceil} \newcommand{\floor}[1]{\left\lfloor #1\right\rfloor} \title{Algorithmic and Provable Precision\\of Monotone Approximations} \author{Zhenyu Sun} \date{} \begin{document} \maketitle \begin{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. \end{abstract} \noindent\textbf{Keywords.} Kolmogorov complexity; monotone approximation; algorithmic rate distortion; bounded reflection; proof selectors; arithmetical interpretability. \tableofcontents \section{Introduction} \label{sec:introduction} A computable nonincreasing sequence of natural numbers eventually stabilizes, but its values need not reveal when a prescribed accuracy has been reached. A proof search raises a second question: even when a finite search has reached that accuracy, can the underlying theory prove that it has done so? We study these questions through computable descending approximations and downward-closed assertions about their limits. Let $a(n,t)$ be a computable nonincreasing sequence of natural numbers, with eventual value $a_n$, and put \[ \mu_a(n,r)=\min\{t:a(n,t)-a_n\le r\}. \] We measure a sufficient resource bound by \[ \kappa(t\mid z)=\min_{s\ge t}C(s\mid z), \] where $C$ is plain conditional Kolmogorov complexity. The first principal result is the uniform correspondence \begin{equation}\label{eq:intro-duality} \kappa(\mu_a(n,r)\mid n,r) =\min_{|y-a_n|\le r}C(y\mid n,r)+O(1). \end{equation} Theorem~\ref{thm:duality} proves the corresponding statement for effective partial orders and interval-hereditary error relations. The integer form, Theorem~\ref{thm:scalar}, further identifies both sides with $C(\floor{a_n/(2r+1)}\mid n,r)+O(1)$. The proof converts an adequate approximation into a sufficiently late stage by search, and converts a stage bound into an approximation by evaluation. Neither conversion requires a lower bound on the complexity of the limit. Certificate searches give further presentations of the same limit. If certificates recognize exactly the false thresholds in a known finite range, both the largest unrefuted threshold and the number of unrefuted positive thresholds decrease to $a_n$. Their completion moduli therefore have the same inverse Busy Beaver complexity as the original approximation. When the presentation varies with $n$, Theorem~\ref{thm:advice} bounds the joint information in its parameter and its resource budget. A matching construction places a coarse quotient of $a_n$ in the presentation parameter and achieves the specified precision at budget zero. For the arithmetical results, fix a threshold formula $\Theta(n,d)$ whose downward closure and zero instance are provable in elementary arithmetic. Two elementary functions summarize finite proof searches: $P_T$ is the largest threshold with a bounded positive proof, and $H_T$ is the largest threshold with no bounded refutation, with $0$ adjoined in both definitions. Theorem~\ref{thm:normal} reduces bounded positive reflection and bounded refutation completeness, with error $e$, to \[ \Theta(n,P_T\dm e) \quad\text{and}\quad \Theta(n,H_T\dm e), \] respectively, where $d\dm e=\max\{d-e,0\}$. A single cut relates the separation $P_T\le H_T$ to finite consistency, with explicit length and quantifier-rank bounds. Let $L_T(n)$ be the greatest threshold that $T$ proves. For every standard tuple of parameters, Theorem~\ref{thm:pointwise} gives \[ T\vdash\BC_T^{[\bd e]}(\bd n;\bd b,\bd v) \quad\Longleftrightarrow\quad H_T(n,b,v)\le L_T(n)+e. \] Consequently, the least error for which some concrete completion budget is provably sufficient is determined exactly. Under soundness for both positive and negative threshold instances and refutation completeness at the selected rank, this error is \begin{equation}\label{eq:intro-gap} E_T(n)=a_n-L_T(n). \end{equation} For elementary approximations with bounds and monotonicity provable in $\EA$, the same quantity governs provable adequacy of finite computational windows for $G(n,d)=\forall t\,[a(n,t)\ge d]$. Here consistency of $T\supseteq\EA$ suffices, because every false $G$-instance has a finite counterexample verifiable in $\EA$. The error in~\eqref{eq:intro-gap} also carries information about both thresholds. For computable approximations $A(n,s)\searrow a_n$ and $L(n,s)\nearrow l_n\le a_n$, Theorem~\ref{thm:gapjoint} proves \[ C(a_n-l_n\mid n)=C(a_n,l_n\mid n)+O(1). \] Knowing the exact difference allows one to search for a stage at which both nonnegative approximation errors vanish. At positive error, the completion modulus satisfies an exact error-allocation identity. Applied to proof enumeration, this gives information and numerical lower bounds for $E_T$. Chaitin counts supply instances with $n+O(1)$ bits of information. For a fixed computable $k(n)\in\{0,\ldots,n+1\}$, their error-$2^{k(n)}-1$ completion bounds have inverse Busy Beaver complexity $n-k(n)+O(1)$. Under the stated soundness assumptions, the same bounds hold for refutation length at every fixed quantifier rank above the refutation-completeness threshold. For a fixed finite collection of optimal machines, Theorem~\ref{thm:jointmax} shows that the joint approximation cost is determined by the smallest coordinate tolerance. Quantizing the sum of the monotone counting approximations bounds the total error and hence every coordinate error. \paragraph{Relation to earlier work.} Vereshchagin and Vit\'anyi~\cite[Section~II]{VV} develop algorithmic rate distortion for individual data. Andreev~\cite{Andreev} compares maximum-output Busy Beaver functions defined from different versions of Kolmogorov complexity. The minimum description length of an upper bound also occurs in the inverse Busy Beaver treatment of logical depth~\cite[Definitions~2--3]{ABST}. Here monotonicity provides constant-overhead conversions between a distortion center and an adequate stage bound. For integer limits, coarse quotients describe the resulting precision profile. The exact-count argument is classical~\cite[p.~3]{Koucky}; the conditional lower bound uses the deficiency-coding method of~\cite[Proposition~1]{CLTS}. We give the details needed for the uniform constants used below. The arithmetization of reflection and the treatment of proof resources use the settings of Beklemishev~\cite{Beklemishev} and Pudl\'ak~\cite{Pudlak}. The finite extrema here yield threshold normal forms and the exact set of provable budgets. Selector proofs of reflection instances have established precedents: see Beklemishev~\cite[Lemma~2.2]{Beklemishev}, Artemov~\cite[Section~5.1]{Artemov}, and Gadsby~\cite[Example~3.5]{Gadsby}. Our selector is an explicit elementary construction from the bounded positive-proof maximum, with correctness proved in elementary arithmetic under the stated presentation assumptions. The interpretation results specify the formula comparisons, proof translations, and witness-descent principles needed to transfer bounded reflection and completion. Joosten~\cite{Joosten} and Visser~\cite{Visser} provide the related interpretability setting. Nelson's restricted Chaitin arguments in \emph{Elements}~\cite{Nelson} motivate the final discussion of changing proof bounds and interpretation domains. \section{Complexity, arithmetic, and proof encodings} \label{sec:preliminaries} \subsection{Description lengths and resource bounds} Fix an optimal plain machine $U$ and an optimal conditional plain machine $V$. We use $U$ for unconditional complexity and write $C(x\mid z)=\min\{|p|:V(p,z)=x\}$. Finite tuples have fixed computable encodings; integers of either sign are represented by a fixed computable bijection with $\N$. The notation $K$ is reserved for prefix complexity. All logarithms are to base two, and $\N$ contains zero. Constants in $O(1)$ may depend on fixed machines, algorithms, formula templates, and theory presentations. Dependence on a parameter allowed to vary is displayed explicitly. For $t\in\N$ and $m\in\Z$, set \[ \kappa(t\mid z)=\min_{s\ge t}C(s\mid z), \qquad \BB(m;z)=\max\bigl(\{-1\}\cup \{V(p,z)\in\N:|p|\le m,\ V(p,z)\downarrow\}\bigr). \] The program set is empty when $m<0$. This convention gives the exact relation \begin{equation}\label{eq:inverse} \kappa(t\mid z)\le m \quad\Longleftrightarrow\quad t\le\BB(m;z). \end{equation} Thus $\BB$ measures maximum output value. Comparisons with the running time of a particular machine are obtained by specifying the corresponding simulation. \begin{lemma}[Cofinal changes of resource scale]\label{lem:rescaling} Let $f:\N^2\to\N$ be a total computable function such that, for each $n$, the map $t\mapsto f(n,t)$ is nondecreasing and unbounded. Uniformly in $n,t$, \[ \kappa(f(n,t)\mid n)=\kappa(t\mid n)+O_f(1). \] The same assertion holds with additional side information on both sides. \end{lemma} \begin{proof} From any $s\ge t$ one computes $f(n,s)\ge f(n,t)$, which proves one inequality. Given $u\ge f(n,t)$, search for the first $s$ such that $f(n,s)>u$. Unboundedness makes the search terminate, and monotonicity implies $s>t$. These two fixed program transformations prove the assertion. \end{proof} For $x,r\in\N$, define \begin{align*} \RD^\pm(x,r\mid z) &=\min\{C(y\mid z):y\in\N,\ |y-x|\le r\},\\ \RD^+(x,r\mid z) &=\min\{C(u\mid z):x\le u\le x+r\}. \end{align*} When $r$ varies independently, it is included in the side information. If $r=r(n)$ is a fixed total computable function, it can be recovered from $n$ at a constant description cost. We repeatedly use the following elementary coding convention. A plain program can be followed by a suffix whose length is computable from the condition: the decoder removes that suffix before simulating the program. This permits constant-overhead indexing into a finite set with a known cardinality bound. To concatenate two descriptions of independently variable lengths, we use a prefix description for the first one. These conventions account for the different appearances of $C$ and $K$ below. \subsection{Elementary arithmetic and complete proof objects} Computability and standard truth are considered in the usual mathematical metatheory. Internal assertions are explicitly prefixed by $\EA\vdash$ or $T\vdash$, where $\EA=I\Delta_0+\exp$. We allow a fixed finite elementary definitional extension, with its definitions and verification proofs specified. The arithmetic sections use elementary functions for finite bounds, finite computation, and bounded proof search. Quotation with numerical parameters, such as $\code{\varphi(\bd{\vec x})}$, denotes the elementary function assigning the code of the corresponding closed instance. Free variables in an internal assertion are universally closed. The proof calculus is classical tree-like LK with cut, weakening, contraction, and identity initial sequents for arbitrary formulas. Contexts are finite multisets represented by lists; the verifier treats exchange implicitly. Formulas are identified up to $\alpha$-equivalence and stored as explicit named-variable prefix strings over a fixed finite alphabet. The checker compares capture-free instances by canonical indexing of bound variables, an elementary syntactic operation. Length always counts the stored representative. Binary variable indices, numeral terms, eigenvariable annotations, and instantiating terms are all included in the symbol count, including annotations on vacuous quantifier inferences. Efficient binary numeral terms satisfy $|\bd n|=O(\log(n+2))$. The rank $\rk(p)$ of a proof is the maximum quantifier nesting depth of any formula occurring in it, after bounded-quantifier abbreviations are expanded. An empty list has length $1$, and a list cell containing $A$ and a tail $\Gamma$ has length $1+|A|+|\Gamma|$. A sequent consists of one tag and its two context lists, so \[ |\seq|=3, \qquad |\seq A|=|A\seq|=|A|+4. \] An identity proof consists of a tag and its concluding sequent. A cut node is encoded as $\mathtt c\,A\,S\,p\,q$, and a weakening node as $\mathtt w\,S\,p$. In particular, the length of a cut with cut formula $A$ and conclusion $S$ is \begin{equation}\label{eq:cutsize} |p|+|q|+|A|+|S|+1. \end{equation} A left-negation node records the underlying formula $A$ when introducing $\neg A$. The exact additive constants in the finite consistency and proof-composition results refer to these conventions. For a computably enumerable axiom set, a nonlogical axiom leaf concludes $\seq\gamma$ and carries a complete finite computation witnessing the enumeration of $\gamma$. Its cost is part of the proof length. Checking such a trace, checking each inference, and computing the rank are elementary operations on the complete proof object. Hence a bounded proof class is effectively exhaustible, with an elementary bound on its numerical codes. This also applies when the enumeration of the axioms itself has no elementary time bound. In $\Prf_T(p,S)$ the sequent argument denotes its code; when a formula code is supplied, the notation abbreviates verification of the conclusion $\seq\varphi$. Whenever an internal uniform construction requires $T\supseteq\EA$, the presentation includes an elementary embedding of $\EA$ proofs into $T$ proofs, with correctness provable in $\EA$. This is a condition on the chosen presentation. Statements requiring only external computability will be formulated separately. The distinction between symbol length and the numerical value of a proof code is retained in the discussion of arithmetic cuts. \section{Monotone approximation and algorithmic distortion} An adequate upper approximation determines a late enough stage by a computable search. Conversely, evaluating the sequence at any late enough stage gives an adequate approximation. The order-interval condition below makes both conversions uniform in the error parameter. \subsection{A correspondence on finite partially ordered sets} Let $(P_n,\preceq_n)$ be a uniformly computable family of nonempty finite partially ordered sets. This means that an algorithm, on input $n$, returns a complete finite list of the elements of $P_n$, together with its order relation. The availability of this complete list will matter for the covering arguments below. Let $x(n,t)\in P_n$ be a total computable approximation satisfying \begin{equation}\label{eq:descending-poset} x(n,t+1)\preceq_n x(n,t). \end{equation} Each row is eventually constant. Write $x_n$ for its eventual value; in particular, $x_n\preceq_n x(n,t)$ for every $t$. No computable bound on the stabilization stage is assumed. \begin{definition}[Distortion hereditary on order intervals]\label{def:order-distortion} An error parameter $\eta$ is a finite object. A uniformly decidable relation $A_\eta(x,u)$ on $P_n$ is an admissible distortion relation if \begin{equation}\label{eq:order-distortion} A_\eta(x,u)\Longrightarrow x\preceq_n u, \qquad A_\eta(x,x), \end{equation} and \begin{equation}\label{eq:interval-heredity} x\preceq_n v\preceq_n u\ \text{ and }\ A_\eta(x,u) \quad\Longrightarrow\quad A_\eta(x,v). \end{equation} Define the completion modulus and the one-sided distortion complexity by \begin{align} \mu_A(n,\eta) &=\min\{t:A_\eta(x_n,x(n,t))\},\label{eq:mu-order}\\ \RD_A^+(x_n,\eta\mid n,\eta) &=\min\{C(u\mid n,\eta):u\in P_n,\ A_\eta(x_n,u)\}. \label{eq:rd-order} \end{align} \end{definition} Reflexivity ensures that both minima exist. Interval heredity makes the adequate stages exactly the final interval $[\mu_A(n,\eta),\infty)$. We condition every complexity on $\eta$, so the decoder can use the error parameter. When $\eta$ varies independently of $n$, omitting it can change the information available to the decoder. \begin{theorem}[Distortion and the complexity of an adequate bound]\label{thm:duality} For a fixed approximation and distortion relation, there is a constant $c$ independent of $n$ and $\eta$ such that \begin{equation}\label{eq:duality} \kappa(\mu_A(n,\eta)\mid n,\eta) =\RD_A^+(x_n,\eta\mid n,\eta)+O(1). \end{equation} Writing $R=\RD_A^+(x_n,\eta\mid n,\eta)$ and increasing $c$ if necessary, one also has \begin{equation}\label{eq:bbgeneral} \BB(R-c;n,\eta)<\mu_A(n,\eta) \le\BB(R+c;n,\eta). \end{equation} \end{theorem} \begin{proof} Set $z=(n,\eta)$ and $\mu=\mu_A(n,\eta)$. If $s\ge\mu$, then \[ x_n\preceq_n x(n,s)\preceq_n x(n,\mu). \] Consequently $A_\eta(x_n,x(n,s))$ holds. A fixed machine first computes $s$ from a description conditional on $z$ and then computes $x(n,s)$. Its overhead is independent of $z$ and $s$. Hence \[ R\le C(s\mid z)+c_1\qquad(s\ge\mu). \] Taking the minimum over the entire adequate tail gives $R\le\kappa(\mu\mid z)+c_1$. For the converse, let $p$ be a shortest conditional description of an admissible upper approximation $u$. After computing $u$, a fixed machine searches for the least stage $s$ such that $x(n,s)\preceq_n u$. This search terminates: eventually $x(n,s)=x_n$, and admissibility gives $x_n\preceq_n u$. At the returned stage, \[ x_n\preceq_n x(n,s)\preceq_n u, \] so interval heredity implies $A_\eta(x_n,x(n,s))$. Thus $s\ge\mu$, and \[ \kappa(\mu\mid z)\le C(s\mid z)\le |p|+c_2=R+c_2. \] No test of the unknown assertion $A_\eta(x_n,u)$ is used by the decoder; that assertion guarantees termination for the particular description under consideration. The two inequalities prove \eqref{eq:duality}. Choose $c\ge\max(c_1+1,c_2)$. Every program of length at most $R-c$ has output strictly below $\mu$, whereas some program of length at most $R+c$ outputs an integer at least $\mu$. The convention $\max\varnothing=-1$ in the definition of $\BB$ covers the small-index cases and gives \eqref{eq:bbgeneral}. \end{proof} The same argument applies to an infinite effective partially ordered set if eventual constancy of every row is imposed explicitly. Finiteness is used here to obtain eventual constancy from descent, and later to compute complete covers. The theorem concerns the complexity of an adequate bound, rather than the complexity of the first adequate stage itself; Example~\ref{ex:first} shows that the latter can be arbitrarily larger. \begin{proposition}[Volume and covering bounds]\label{prop:cover} For $u\in P_n$, put \[ B_A(n,\eta,u)=\{x\in P_n:A_\eta(x,u)\}, \qquad V_A(n,\eta)=\max_{u\in P_n}|B_A(n,\eta,u)|. \] Let $K_A(n,\eta)$ be the least cardinality of a family of these sets covering $P_n$. Then \begin{align} C(x_n\mid n,\eta)-\ceil{\log V_A(n,\eta)}-O(1) &\le\RD_A^+(x_n,\eta\mid n,\eta),\label{eq:volume}\\ \RD_A^+(x_n,\eta\mid n,\eta) &\le\ceil{\log K_A(n,\eta)}+O(1). \label{eq:cover} \end{align} The constants depend only on the effective family and the distortion relation. \end{proposition} \begin{proof} The complete finite presentation of $P_n$ permits one to compute all the sets $B_A(n,\eta,u)$, their maximum cardinality, and a canonical smallest cover. Reflexivity gives $V_A,K_A\ge1$. For the lower bound, let $p$ describe an admissible center $u$, and append a $k$-bit index of $x_n$ in the canonically ordered set $B_A(n,\eta,u)$, where $k=\ceil{\log V_A(n,\eta)}$. Conditional on $(n,\eta)$, the decoder first computes $k$ and removes exactly the last $k$ bits. It runs the remaining plain program to recover $u$, computes the corresponding finite set, and selects the indicated element. Thus \[ C(x_n\mid n,\eta)\le |p|+k+O(1). \] This fixed-tail parsing also covers $k=0$ and requires no self-delimiting description of $|p|$. For the upper bound, encode the index of an appropriate center in the canonical smallest cover using $\ceil{\log K_A(n,\eta)}$ bits. The conditional decoder recomputes the cover and returns that center. The computation may be expensive; its running time does not enter ordinary Kolmogorov complexity. \end{proof} These bounds are the finite covering form of the usual description argument in algorithmic rate-distortion theory \cite{VV}. If \[ C(x_n\mid n,\eta)\ge\log|P_n|-\delta, \qquad K_A(n,\eta)V_A(n,\eta)\le c|P_n|, \] the two bounds differ by at most $\delta+\log c+O(1)$. The relevant entropy is the joint complexity of $x_n$; separate lower bounds for its coordinates do not imply a lower bound equal to their sum. \subsection{Integer precision and coarse quotients} \begin{theorem}[The scalar correspondence]\label{thm:scalar} Let $a(n,t)\in\N$ be total computable and nonincreasing in $t$, with eventual value $a_n$. Define \[ \mu_a(n,r)=\min\{t:a(n,t)-a_n\le r\}. \] Uniformly for all $n,r\in\N$, \begin{align} \kappa(\mu_a(n,r)\mid n,r) &=\RD^+(a_n,r\mid n,r)+O_a(1)\notag\\ &=\RD^\pm(a_n,r\mid n,r)+O_a(1)\label{eq:scalar}\\ &=C\left(\floor{\frac{a_n}{2r+1}}\ \middle|\ n,r\right)+O_a(1). \notag \end{align} There is also the one-sided quotient formula \begin{equation}\label{eq:onesided-quotient} \RD^+(a_n,r\mid n,r) =C\left(\floor{\frac{a_n}{r+1}}\ \middle|\ n,r\right)+O(1). \end{equation} For exact convergence, the first adequate stage itself satisfies \begin{equation}\label{eq:exacttimecomplex} C(\mu_a(n,0)\mid n)=C(a_n\mid n)+O_a(1). \end{equation} \end{theorem} \begin{proof} Use $P_n=\{0,\ldots,a(n,0)\}$ with its usual order and the distortion relation $0\le u-x\le r$. Theorem~\ref{thm:duality} gives the first equality with centers in $P_n$. Allowing arbitrary natural-number centers changes the minimum by at most a constant: an admissible center can be truncated to $a(n,0)$, a bound computable from $n$, without increasing its error. Every one-sided approximation is a two-sided approximation. Conversely, let $y$ satisfy $|y-a_n|\le r$. One additional bit selects \[ u=y\quad\text{if }a_n\le y, \qquad u=y+r\quad\text{if }a_n>y. \] In both cases $a_n\le u\le a_n+r$. A decoder removes the final direction bit from a plain description of $y$ and performs the indicated computation. This proves that the one-sided and two-sided distortion complexities differ by a uniform constant. For the two-sided quotient formula, set $W=2r+1$ and $q=\floor{a_n/W}$. From $q$ one computes the midpoint $qW+r$, which is within distance $r$ of every integer in that bucket. Conversely, the interval $[y-r,y+r]\cap\N$ associated with any valid approximation meets at most two buckets of width $W$. Their indices can be computed from $y,r$, and one extra bit selects the correct quotient. This proves the last equality in \eqref{eq:scalar}. For \eqref{eq:onesided-quotient}, use buckets of width $w=r+1$. The index $j=\floor{a_n/w}$ yields the upper endpoint $(j+1)w-1$, an admissible one-sided approximation. Conversely, an admissible upper bound $u$ places $a_n$ in $[u-r,u]$, an interval meeting at most two $w$-buckets. A single bit again recovers the correct index. If centers are restricted to a known finite interval, truncate the upper endpoint at its maximum; admissibility is preserved. Finally, $a_n$ is obtained from $(n,\mu_a(n,0))$ by evaluating the approximation. Given $(n,a_n)$, searching for the first equality $a(n,t)=a_n$ returns exactly $\mu_a(n,0)$. These two fixed partial computations prove \eqref{eq:exacttimecomplex}. \end{proof} \begin{corollary}[Bounds from the information in the limit]\label{cor:scalarvolume} Suppose $0\le a_n\le N(n)$ for a total computable $N$. Then \begin{equation}\label{eq:scalar-volume-bounds} \begin{split} C(a_n\mid n,r)-\ceil{\log(r+1)}-O(1) &\le\RD^+(a_n,r\mid n,r)\\ &\le\ceil{\log\ceil{\frac{N(n)+1}{r+1}}}+O(1). \end{split} \end{equation} These inequalities and Theorem~\ref{thm:duality} give corresponding Busy Beaver bounds for $\mu_a(n,r)$. If $r=r(n)$ is a fixed total computable function, $r$ may be removed from the condition at constant cost. \end{corollary} \begin{proof} An admissible upper center leaves at most $r+1$ candidate integers. The interval $[0,N(n)]$ is covered by $\ceil{(N(n)+1)/(r+1)}$ consecutive buckets whose upper endpoints are admissible centers. Apply Proposition~\ref{prop:cover}; alternatively use the quotient construction in the preceding proof. If $r(n)$ is fixed and computable, programs conditional on $(n,r(n))$ and on $n$ simulate one another with fixed overhead. \end{proof} \subsection{Rectangular precision and dimension} Let $d=d(n)\ge1$ be computable, and let $\mathbf x(n,t)\in\N^{d(n)}$ be a uniformly computable coordinatewise nonincreasing approximation with limit $\mathbf x_n$. Its initial vector provides a computable finite product bound. For a tolerance vector $\mathbf r=(r_1,\ldots,r_d)$, put \[ \mu_{\mathbf r}(n) =\min\{t:x_i(n,t)-x_{n,i}\le r_i\text{ for every }i\}, \] and define \[ \RD^\pm_{\mathbf r}(\mathbf x\mid z) =\min\{C(\mathbf y\mid z):|y_i-x_i|\le r_i\text{ for every }i\}. \] The one-sided version requires $0\le y_i-x_i\le r_i$ for every coordinate. \begin{proposition}[Coordinatewise distortion]\label{prop:rectangular} With all distortion complexities conditioned on $(n,\mathbf r)$, \begin{equation}\label{eq:rect} \RD^\pm_{\mathbf r}(\mathbf x_n\mid n,\mathbf r)-O(1) \le\kappa(\mu_{\mathbf r}(n)\mid n,\mathbf r) \le\RD^\pm_{\mathbf r}(\mathbf x_n\mid n,\mathbf r)+d(n)+O(1). \end{equation} There is also the dimension-independent comparison \begin{equation}\label{eq:rect-double} \begin{split} \kappa(\mu_{2\mathbf r}(n)\mid n,\mathbf r) &\le\RD^\pm_{\mathbf r}(\mathbf x_n\mid n,\mathbf r)+O(1)\\ &\le\kappa(\mu_{\mathbf r}(n)\mid n,\mathbf r)+O(1). \end{split} \end{equation} \end{proposition} \begin{proof} The one-sided relation is hereditary on intervals of the product order, so Theorem~\ref{thm:duality} applies exactly to one-sided distortion. To turn a two-sided center into a one-sided center, select $y_i$ or $y_i+r_i$ according to whether $x_{n,i}\le y_i$ or $x_{n,i}>y_i$. The direction vector has $d(n)$ bits. Its length is known from $n$, so it can be appended to a plain program and parsed without further length information. This proves \eqref{eq:rect}. For \eqref{eq:rect-double}, the center $\mathbf y+\mathbf r$ always lies coordinatewise above $\mathbf x_n$ and has one-sided error at most $2\mathbf r$. Searching until the descending approximation lies below this center returns an adequate bound for tolerance $2\mathbf r$, using only a description of $\mathbf y$ and fixed overhead. The other inequality follows by evaluating the approximation at any stage adequate for $\mathbf r$. \end{proof} For $P_n=\prod_i\{0,\ldots,N_i-1\}$ and one-sided rectangular tolerances, the exact volume and covering parameters are \begin{equation}\label{eq:rect-cover} V_A=\prod_i\min(N_i,r_i+1), \qquad K_A=\prod_i\ceil{\frac{N_i}{r_i+1}}. \end{equation} The product partition gives the covering upper bound. For the reverse inequality, take in coordinate $i$ the points $0,r_i+1,2(r_i+1),\ldots$ that remain in its range. An admissible rectangle contains at most one point of the resulting product packing, whose cardinality is the displayed covering number. In particular, dyadic ranges and dyadic bucket widths give $K_AV_A=|P_n|$ whenever each bucket width divides the corresponding range size. For fixed dimension, the loss $d(n)$ in \eqref{eq:rect} is absorbed into the additive constant; the displayed estimate is uniform when the dimension varies. \section{Presentations, completion, and advice} The preceding complexity profile depends on the limit and the allowed error. The numerical stage at which that error is reached also depends on the presentation. We first compare fixed presentations, then account for the information in a presentation parameter that varies with the input. \subsection{Changing a monotone presentation} \begin{theorem}[Effective transfer without loss of precision]\label{thm:change} Let $a(n,t)$ and $b(n,s)$ be total computable nonincreasing approximations to the same integer sequence $a_n$. The function \begin{equation}\label{eq:transfer-function} F_{a\to b}(n,t)=\min\{s:b(n,s)\le a(n,t)\} \end{equation} is total computable and satisfies, for every $r$, \begin{equation}\label{eq:change} \mu_b(n,r)\le F_{a\to b}(n,\mu_a(n,r)). \end{equation} For exact convergence, \begin{equation}\label{eq:exact-change} \mu_b(n,0)=F_{a\to b}(n,\mu_a(n,0)). \end{equation} Interchanging the two presentations gives the reverse transfer. \end{theorem} \begin{proof} For every $n,t$, one has $a(n,t)\ge a_n$, and $b(n,s)$ eventually equals $a_n$. Thus the search defining $F_{a\to b}$ terminates on every input. At $t=\mu_a(n,r)$, \[ a_n\le b(n,F_{a\to b}(n,t))\le a(n,t)\le a_n+r, \] which proves \eqref{eq:change}. If $r=0$, then $a(n,t)=a_n$, and the search condition is precisely $b(n,s)\le a_n$. Since every value of $b$ is at least $a_n$, its first occurrence is the exact stabilization stage of $b$. \end{proof} The proof also gives the corresponding assertion for two descending presentations in the same effective partially ordered set, with interval-hereditary distortion: replace $\le$ in \eqref{eq:transfer-function} by the order relation. Totality follows from their common eventual value. These are statements in the external computability theory. Their use inside a weak arithmetical theory requires a separate proof of totality and of any proposed internal resource bound. \begin{proposition}[Combining presentations in a meet semilattice]\label{prop:meet-combination} Suppose each $P_n$ is a finite meet semilattice, presented effectively as above. Let $m(n)\ge1$ be computable, and suppose that $x_i(n,t)$, $1\le i\le m(n)$, are uniformly computable descending presentations of a common limit $x_n$. Then \begin{equation}\label{eq:meet-presentation} y(n,t)=\bigwedge_{i=1}^{m(n)}x_i(n,t) \end{equation} is a computable descending presentation of $x_n$. For every interval-hereditary distortion relation, \begin{equation}\label{eq:meet-modulus} \mu_y(n,\eta)\le\min_{1\le i\le m(n)}\mu_{x_i}(n,\eta), \end{equation} and \[ \kappa(\mu_y(n,\eta)\mid n,\eta) =\RD_A^+(x_n,\eta\mid n,\eta)+O(1). \] The constant is uniform even when $m(n)$ grows, provided the family is given by one fixed algorithm. \end{proposition} \begin{proof} The complete finite order computes its meet operation. Monotonicity of meet shows that $y(n,t)$ descends. Since $x_n$ is a lower bound for all its factors, \[ x_n\preceq_n y(n,t)\preceq_n x_i(n,t) \] for every $i$. For fixed $n$, all finitely many factors eventually equal $x_n$, so their meet has the same limit. If any factor is adequate at stage $t$, interval heredity makes the meet adequate at that stage as well, proving \eqref{eq:meet-modulus}. The last statement is Theorem~\ref{thm:duality} applied to the single uniform algorithm computing the meet. \end{proof} \subsection{Counterexample certificates as monotone presentations} Let $N(n)$ be a total computable bound and let $a_n\in\{0,\ldots,N(n)\}$ be the true threshold. A certificate presentation consists of a uniformly decidable relation $R(n,d,q)$, with binary-string certificates $q$, satisfying \begin{equation}\label{eq:certsound} \exists q\,R(n,d,q)\quad\Longleftrightarrow\quad d>a_n \qquad(1\le d\le N(n)). \end{equation} Every certificate of length at most a given budget must be effectively inspectable. With the present string-length convention, this follows by enumerating all strings of length at most the budget and running the total verifier on each of them. For more general cost functions, effective exhaustive access to the bounded-cost certificates is an additional hypothesis. For a budget $b$, define the set of marked labels by \[ M_R(n,b)=\{d\in\{1,\ldots,N(n)\}:\exists |q|\le b\ R(n,d,q)\}. \] There are two natural numerical presentations: \begin{align} H_R(n,b) &=\max\bigl(\{0\}\cup(\{1,\ldots,N(n)\}\setminus M_R(n,b))\bigr), \label{eq:Hcert}\\ J_R(n,b)&=N(n)-|M_R(n,b)|. \label{eq:Jcert} \end{align} They are computable and nonincreasing in $b$. Soundness in \eqref{eq:certsound} leaves every label $1,\ldots,a_n$ unmarked; completeness eventually marks every label above $a_n$. Therefore \begin{equation}\label{eq:certificate-frontiers} a_n\le J_R(n,b)\le H_R(n,b), \qquad H_R(n,b),J_R(n,b)\longrightarrow a_n. \end{equation} For the middle inequality, a set of $J_R$ distinct positive integers has maximum at least $J_R$; the empty-set convention gives the same inequality when $J_R=0$. The two errors express different requirements. The condition $H_R-a_n\le r$ says that every label $d>a_n+r$ is marked. The condition $J_R-a_n\le r$ says that at most $r$ false labels remain unmarked. A single unmarked label far above $a_n$ can separate these conditions substantially. \begin{corollary}[The distortion profile of certificate completion]\label{cor:certificate} Let $\mu_{R,H}$ and $\mu_{R,J}$ denote the completion moduli of $H_R$ and $J_R$. For either choice $\mu_R$, \begin{equation}\label{eq:certificate-duality} \kappa(\mu_R(n,r)\mid n,r) =\RD^\pm(a_n,r\mid n,r)+O_R(1). \end{equation} Consequently any two effective certificate presentations satisfying \eqref{eq:certsound} determine the same precision profile in inverse Busy Beaver complexity, up to a constant depending on the presentations. \end{corollary} \begin{proof} Equation \eqref{eq:certificate-frontiers} places each presentation under Theorem~\ref{thm:scalar}. The common limit is $a_n$, so the right-hand side is independent of the certificate presentation and of the choice between the two completion criteria. \end{proof} More direct resource comparisons are available when a certificate transformation preserves labels. If every $R$-certificate of budget at most $b$ is transformed into an $S$-certificate of budget at most $F(n,b)$, then \begin{equation}\label{eq:certificate-transfer} M_R(n,b)\subseteq M_S(n,F(n,b)), \qquad H_S(n,F(n,b))\le H_R(n,b), \end{equation} and the same inequality holds with $J$ in place of $H$. Substituting an adequate $R$-budget gives the corresponding inequality between completion moduli. Even without a supplied transformation, extensional equivalence yields a total computable budget transfer: \begin{equation}\label{eq:certificate-extensional-transfer} F(n,b)=\min\{c:M_R(n,b)\subseteq M_S(n,c)\}. \end{equation} To see termination, first compute the finite set $M_R(n,b)$. Every one of its labels is false by $R$-soundness, and therefore has some $S$-certificate by $S$-completeness. Finitely many such certificates have a common finite budget. This argument proves external totality, without imposing an elementary or polynomial bound on $F$. \subsection{Parameter-dependent presentations and sharp advice bounds} Consider a fixed uniformly decidable verifier $R(z,n,d,q)$ whose presentation parameter $z$ may depend on $n$. Let $M_z(n,b)$ denote its marked labels. For a particular tuple $(n,z,b)$, assume soundness of the selected presentation and suppose that at most $r$ false labels remain unmarked. Completeness at other budgets is not needed for the following lower bounds. The finite computation \[ u_z(n,b)=N(n)-|M_z(n,b)| \] then satisfies $a_n\le u_z(n,b)\le a_n+r$. \begin{theorem}[The joint information in a presentation and its budget]\label{thm:advice} Under these assumptions, uniformly for all successful tuples, \begin{align} C(z,b\mid n,r) &\ge\RD^+(a_n,r\mid n,r)-O(1),\label{eq:adviceRD}\\ C(z,b\mid n,r)+\ceil{\log(r+1)} &\ge C(a_n\mid n,r)-O(1),\label{eq:advicejoint}\\ K(z\mid n,r)+C(b\mid n,r,z)+\ceil{\log(r+1)} &\ge C(a_n\mid n,r)-O(1). \label{eq:advicesplit} \end{align} The constants depend on the fixed verifier and coding, not on the chosen parameter or budget. If $b=F(n,z)$ for a fixed computable function defined on the tuples in question, $C(z,b\mid n,r)$ in the first two inequalities may be replaced by $C(z\mid n,r)$. \end{theorem} \begin{proof} From $n,z,b$, the decoder computes the finite marked set and hence $u_z(n,b)$. This proves \eqref{eq:adviceRD}. To recover the exact threshold, append the offset $u_z-a_n\in\{0,\ldots,r\}$ in exactly $k=\ceil{\log(r+1)}$ bits. The condition supplies $r$, so the decoder knows $k$ before reading the preceding plain description. This proves \eqref{eq:advicejoint} with constant rather than logarithmic parsing overhead. For the split bound, use a shortest prefix description of $z$ conditional on $(n,r)$, followed by a plain description of $b$ conditional on $(n,r,z)$, followed by the $k$ offset bits. The prefix code determines the first boundary and the known tail length determines the second. Running the preceding finite computation recovers $a_n$, giving \eqref{eq:advicesplit}. When $b=F(n,z)$, the same decoder obtains the budget directly after reconstructing $z$. \end{proof} The prefix complexity in \eqref{eq:advicesplit} accounts for one boundary between variable-length descriptions. An unqualified replacement of both terms by ordinary complexities would require an additional parsing argument or a length allowance. \begin{proposition}[Attainment by an informative presentation]\label{prop:advice-attainment} Fix a certificate presentation $R_0$ satisfying \eqref{eq:certsound}. There is a uniformly decidable parameterized presentation $R$ with the following property. For every $n,r$, one can choose a parameter $z_{n,r}$ such that $R(z_{n,r},n,\cdot,\cdot)$ is sound and complete at input $n$, budget $0$ leaves at most $r$ false labels unmarked at that input, and \begin{equation}\label{eq:advice-attainment} C(z_{n,r}\mid n,r) =\RD^+(a_n,r\mid n,r)+O(1). \end{equation} \end{proposition} \begin{proof} Put $w=r+1$, $j=\floor{a_n/w}$, and choose $z_{n,r}=(r,j)$. Given any syntactically valid parameter $z=(r,j)$, let \[ u=\min\{N(n),(j+1)w-1\}. \] The empty certificate is accepted exactly for labels $d>u$. A nonempty certificate of the form $1q$ is accepted exactly when $R_0(n,d,q)$ holds; all other strings are rejected. Prefixing the original certificates ensures that none of them is inadvertently counted at budget $0$. For the selected parameter, $a_n\le u\le a_n+r$. Hence every directly accepted label is false, and the original certificates provide completeness for all remaining false labels. At budget $0$, the marked set is precisely $\{u+1,\ldots,N(n)\}$, so both numerical presentations equal $u$. Finally, \[ C(z_{n,r}\mid n,r)=C(j\mid n,r)+O(1) =\RD^+(a_n,r\mid n,r)+O(1) \] by \eqref{eq:onesided-quotient}. The inclusion of $r$ in $z$ gives the verifier the tolerance it needs; its inclusion in the complexity condition makes that component computable at constant additional description cost. \end{proof} The construction achieves budget zero by placing the required precision information in the presentation parameter. The joint lower bound in Theorem~\ref{thm:advice} still applies. A uniform comparison of varying interpretations or proof systems must therefore include their descriptions among the parameters whose information is counted. \section{Threshold normal forms for bounded reflection} \label{sec:frontiers} Downward closure reduces a finite family of threshold assertions to a single extremal assertion. Applying this observation to positive proofs and to absent refutations gives normal forms that can be proved inside elementary arithmetic. \subsection{Finite proof extrema} Fix an arithmetic formula $\Theta(n,d)$ and an elementary function $N(n)\ge1$. We assume that $\EA$ proves the following sentences, with all displayed parameters universally quantified: \begin{equation}\label{eq:arithmono} \Theta(n,0),\qquad d\le e\le N(n)\;\land\;\Theta(n,e) \ \longrightarrow\ \Theta(n,d). \end{equation} Thus the threshold family is downward closed provably in the base theory. For the semantic applications, we also fix integers $a_n\in[0,N(n)]$ such that, for $0\le d\le N(n)$, \[ \N\models\Theta(n,d)\quad\Longleftrightarrow\quad d\le a_n. \] The internal results of this section use \eqref{eq:arithmono} independently of this standard-model description. Let $T\supseteq\EA$ have the proof presentation specified in the preliminaries. Write $M_T^+(n,d;L,u)$ for the elementary assertion that there is a $T$-proof of $\seq\Theta(\bd n,\bd d)$ of length at most $L$ and rank at most $u$. Write $M_T^-(n,d;b,v)$ for the analogous assertion concerning a refutation $\Theta(\bd n,\bd d)\seq$. These are bounded proof predicates: for the fixed finite-alphabet coding there is an elementary function $J$ such that $\EA$ proves that every proof of length at most $L$ has numerical code below $J(L)$. The existential quantifier over proofs can therefore be bounded by $J(L)$. The complete axiom certificates are part of the object being bounded. Define the elementary functions \begin{align*} P_T(n,L,u)&=\max\bigl(\{0\}\cup \{d\le N(n):M_T^+(n,d;L,u)\}\bigr),\\ H_T(n,b,v)&=\max\bigl(\{0\}\cup \{d\le N(n):\neg M_T^-(n,d;b,v)\}\bigr). \end{align*} Bounded maximization supplies these functions and their defining properties in $\EA$. The function $P_T$ is nondecreasing in either proof budget, whereas $H_T$ is nonincreasing in either refutation budget. We abbreviate them by $P$ and $H$ when the parameters are fixed. The adjoined value $0$ ensures that the definitions remain meaningful even when all the bounded proof tests fail, or all the bounded refutation tests succeed. For $d,e\in\N$, put $d\dm e=\max\{d-e,0\}$. Define bounded reflection with error $e$ by \[ \RFN_T^{[e]}(n;L,u) =\forall d\le N(n)\, \bigl[M_T^+(n,d;L,u)\to\Theta(n,d\dm e)\bigr], \] and bounded refutation completeness with error $e$ by \[ \BC_T^{[e]}(n;b,v) =\forall d\le N(n)\, \bigl[\neg\Theta(n,d\dm e)\to M_T^-(n,d;b,v)\bigr]. \] The case $e=0$ gives the exact versions. Under the threshold semantics, the latter assertion requires refutations of every $d>a_n+e$. \begin{theorem}[Threshold normal forms]\label{thm:normal} For every theory presentation under consideration, $\EA$ proves \begin{align} \RFN_T^{[e]}(n;L,u) &\longleftrightarrow \Theta\bigl(n,P_T(n,L,u)\dm e\bigr),\label{eq:normalP}\\ \BC_T^{[e]}(n;b,v) &\longleftrightarrow \Theta\bigl(n,H_T(n,b,v)\dm e\bigr).\label{eq:normalH} \end{align} These equivalences require neither consistency nor soundness of $T$. \end{theorem} \begin{proof} Work in $\EA$. If $P>0$, the defining property of the bounded maximum gives $M_T^+(n,P;L,u)$. Applying bounded reflection to this threshold yields $\Theta(n,P\dm e)$. If $P=0$, the same conclusion is the base case $\Theta(n,0)$ from \eqref{eq:arithmono}. Conversely, every $d$ satisfying $M_T^+(n,d;L,u)$ satisfies $d\le P$. Consequently $d\dm e\le P\dm e\le N(n)$, and downward closure transfers $\Theta(n,P\dm e)$ to the required conclusion at $d\dm e$. This proves \eqref{eq:normalP}. If $H>0$, then $\neg M_T^-(n,H;b,v)$ holds. The instance of bounded refutation completeness at $d=H$, followed by contraposition, yields $\Theta(n,H\dm e)$. When $H=0$, use $\Theta(n,0)$. For the converse, fix $d\le N(n)$. If $d\le H$, downward closure yields $\Theta(n,d\dm e)$, so the antecedent of the required implication is false. If $d>H$, the maximality of $H$ gives $M_T^-(n,d;b,v)$. Both cases establish the implication in the definition of $\BC_T^{[e]}$. \end{proof} In the standard model, these normal forms reduce the two assertions to the numerical conditions \[ P_T(n,L,u)\le a_n+e, \qquad H_T(n,b,v)\le a_n+e, \] respectively. The internal proof, however, rests on the provable closure property \eqref{eq:arithmono}. For a general certificate relation $R$, this property can be arranged by setting \[ \Theta_R(n,d) =\neg\exists j\,\exists q\, \bigl(1\le j\le d\land R(n,j,q)\bigr). \] If $\exists q\,R(n,j,q)$ holds precisely when $j>a_n$, this formula has the required standard truth set, and its downward closure follows by logic and arithmetic alone. \subsection{Finite separation and local consistency} Let \[ \ell_n=\max_{d\le N(n)}|\Theta(\bd n,\bd d)|, \qquad q_\Theta=\max_{n,d}\qr\bigl(\Theta(\bd n,\bd d)\bigr). \] The second quantity is a constant because numeral substitution changes terms rather than quantifier nesting. Both maxima refer to the fixed formula and numeral coding. Let $\Con_T(L,u)$ assert that there is no $T$-proof of the empty sequent of length at most $L$ and rank at most $u$. \begin{theorem}[Finite separation]\label{thm:separation} The following implication is provable in $\EA$: \begin{equation}\label{eq:sepforward} \Con_T\bigl(L+b+\ell_n+4,\max\{u,v\}\bigr) \ \longrightarrow\ P_T(n,L,u)\le H_T(n,b,v). \end{equation} Conversely, put $K=m+\ell_n+5$ and $R=\max\{s,q_\Theta\}$. Then $\EA$ proves \begin{equation}\label{eq:sepbackward} P_T(n,K,R)\le H_T(n,K,R) \ \longrightarrow\ \Con_T(m,s). \end{equation} \end{theorem} \begin{proof} Suppose that $P>H$. Since $P>0$, the definition of $P$ supplies a positive proof $p$ at threshold $P$, of length at most $L$ and rank at most $u$. Since $P>H$, the definition of $H$ supplies a refutation $q$ of the same instance, of length at most $b$ and rank at most $v$. Their cut on $\Theta(\bd n,\bd P)$ concludes the empty sequent. By \eqref{eq:cutsize}, its length is \[ |p|+|q|+|\Theta(\bd n,\bd P)|+4 \le L+b+\ell_n+4. \] The cut formula already occurs in both input proofs, so the rank is at most $\max\{u,v\}$. These explicit proof operations and their bounds are verifiable in $\EA$, proving \eqref{eq:sepforward}. For the converse, suppose there is an empty-sequent proof $p$ of length at most $m$ and rank at most $s$. One right weakening yields a proof of $\Theta(\bd n,\bd d)$, and one left weakening yields its refutation, for every $d\le N(n)$. Each operation adds \[ 1+|\Theta(\bd n,\bd d)|+4\le\ell_n+5 \] symbols. Each output has rank at most $R$. Thus the indicated budgets establish $P_T(n,K,R)=N(n)$ and $H_T(n,K,R)=0$. Since $N(n)\ge1$, this contradicts their separation. \end{proof} \begin{corollary}[Reflection transfer at a prescribed error]\label{cor:rfntransfer} The theory $\EA$ proves \begin{align} &\Con_T\bigl(L+b+\ell_n+4,\max\{u,v\}\bigr) \land\BC_T^{[e]}(n;b,v)\notag\\ &\hspace{32mm}\longrightarrow\RFN_T^{[e]}(n;L,u). \label{eq:rfnBC} \end{align} \end{corollary} \begin{proof} Finite separation gives $P\le H$. By \eqref{eq:normalH}, the completeness premise gives $\Theta(n,H\dm e)$. Since $P\dm e\le H\dm e$, downward closure gives $\Theta(n,P\dm e)$. Apply \eqref{eq:normalP}. \end{proof} Write $\Prov_T^{L,r}(\code\theta)$ for the assertion that a $T$-proof of $\seq\theta$ exists with length at most $L$ and rank at most $r$. For a fixed refutation $d:\theta\seq$, the same encoding proves in $\EA$ that \[ \Con_T\bigl(L+|d|+|\theta|+4,\max\{r,\rk(d)\}\bigr) \to\bigl(\Prov_T^{L,r}(\code\theta)\to\theta\bigr). \] In $\EA+\neg\theta$, one right weakening also proves \[ \bigl(\Prov_T^{L+|\theta|+5,\max\{r,\qr(\theta)\}}(\code\theta) \to\theta\bigr) \to\Con_T(L,r). \] The refutation-completeness premise in \eqref{eq:rfnBC} accounts for all thresholds simultaneously. Its information and proof-theoretic content will be measured by the next section. \section{The exact spectrum of provable precision} \label{sec:precision} The normal form for bounded refutation completeness separates two quantities: the threshold left unrefuted by the finite search, and the largest threshold the theory proves at any proof length. Comparing them determines both the feasible errors and the full set of provable budgets. \subsection{Provable errors and complete sets of budgets} For each standard $n$, define \[ L_T(n)=\max\bigl(\{0\}\cup \{d\le N(n):T\vdash\Theta(\bd n,\bd d)\}\bigr). \] This is an external maximum of a finite set of thresholds; no computability of the maximum is asserted. Downward closure gives, for standard $0\le d\le N(n)$, \begin{equation}\label{eq:provablethreshold} T\vdash\Theta(\bd n,\bd d) \quad\Longleftrightarrow\quad d\le L_T(n). \end{equation} Indeed, the maximum is itself provable when positive, while the zero case is supplied by \eqref{eq:arithmono}. \begin{theorem}[Criterion for a concrete budget]\label{thm:pointwise} For all standard $n,b,v,e$, \begin{equation}\label{eq:pointwise} T\vdash\BC_T^{[\bd e]}(\bd n;\bd b,\bd v) \quad\Longleftrightarrow\quad H_T(n,b,v)\le L_T(n)+e. \end{equation} \end{theorem} \begin{proof} Let $h=H_T(n,b,v)$. The closed elementary computation giving this value has an $\EA$-proof, so $T$ proves its numeral instance. Using \eqref{eq:normalH} and substituting that equality, the assertion on the left is equivalent to $T\vdash\Theta(\bd n,\bd{h\dm e})$. By \eqref{eq:provablethreshold}, this holds precisely when $h\dm e\le L_T(n)$, or equivalently when $h\le L_T(n)+e$. \end{proof} The finite-valued sequence $b\mapsto H_T(n,b,v)$ is nonincreasing. Write \[ a_{T,v}(n)=\lim_b H_T(n,b,v) \] and define \[ \rho_{T,v}(n) =\min\left\{e:\exists b\in\N\; T\vdash\BC_T^{[\bd e]}(\bd n;\bd b,\bd v)\right\}. \] The minimum exists: taking $e\ge N(n)$ reduces every antecedent in the completeness assertion to the negation of $\Theta(n,0)$. \begin{theorem}[Provable precision spectrum]\label{thm:spectrum} Without a soundness assumption, \begin{equation}\label{eq:spectrumgeneral} \rho_{T,v}(n)=a_{T,v}(n)\dm L_T(n). \end{equation} If every $T$-provable positive or negative instance of the threshold family has its correct standard truth value, then \begin{equation}\label{eq:spectrumrank} \rho_{T,v}(n) =a_{T,v}(n)-L_T(n) =(a_n-L_T(n))+(a_{T,v}(n)-a_n). \end{equation} If, in addition, every false threshold has a refutation of rank at most $v$, then \begin{equation}\label{eq:spectrum} \rho_{T,v}(n)=E_T(n):=a_n-L_T(n). \end{equation} \end{theorem} \begin{proof} An integer-valued nonincreasing sequence with values in $[0,N(n)]$ attains its limit. Consequently there is a budget $b$ satisfying $H_T(n,b,v)\le L_T(n)+e$ exactly when $a_{T,v}(n)\le L_T(n)+e$. The least such nonnegative $e$ is the truncated difference in \eqref{eq:spectrumgeneral}. Positive-family soundness gives $L_T(n)\le a_n$. Negative-family soundness ensures that none of the thresholds $d\le a_n$ can be refuted, whence $H_T(n,b,v)\ge a_n$ for every $b$, and therefore $a_{T,v}(n)\ge a_n$. This removes the truncation and proves \eqref{eq:spectrumrank}. Under rank-$v$ refutation completeness, every $d>a_n$ is eventually refuted. There are finitely many such $d$, so $H_T(n,b,v)$ eventually equals $a_n$, proving \eqref{eq:spectrum}. \end{proof} Consistency and soundness for negative instances play different roles in the applications. \begin{lemma}[Family soundness]\label{lem:familysoundness} Suppose $T$ proves the negation of every false $\Theta$-instance. If $T$ is consistent, every positive $\Theta$-instance provable in $T$ is true. Conversely, soundness of $T$ for the negative instances alone implies consistency of $T$. Hence negative-family soundness together with refutation completeness implies both family soundness conditions in Theorem~\ref{thm:spectrum}. \end{lemma} \begin{proof} A false positive theorem would have its negation provable by the assumed refutation completeness, contrary to consistency. For the converse, an inconsistent theory proves $\neg\Theta(\bd n,0)$ for any standard $n$, whereas $\Theta(n,0)$ is true. This contradicts soundness for negative instances. \end{proof} The entire set of provable budgets admits an exact description. For arbitrary $T,n,v,e$, put \[ \mathcal B_{T,v}(n,e) =\{b\in\N:T\vdash\BC_T^{[\bd e]}(\bd n;\bd b,\bd v)\}. \] Whenever this set is nonempty, let $\nu_{T,v}(n,e)$ denote its least element. Theorem~\ref{thm:pointwise} shows that the set is then the final interval beginning at $\nu_{T,v}(n,e)$. Under both family soundness conditions and rank-$v$ refutation completeness, also put \[ \beta_{T,v}(n,r) =\min\{b:H_T(n,b,v)-a_n\le r\}. \] \begin{proposition}[The set of provable budgets]\label{prop:budgetset} Suppose both families are sound and rank-$v$ refutations are complete. For every standard $n,e$, \begin{equation}\label{eq:budgetset} \mathcal B_{T,v}(n,e)= \begin{cases} \varnothing,&eN(n)$. This formulation compares a finite observation with the unrestricted threshold assertion. \begin{theorem}[Witness adequacy and provable precision]\label{thm:adequacy} The theory $\EA$ proves \begin{equation}\label{eq:adeqnormal} \Adeq_r(n,s) \longleftrightarrow G\bigl(n,a(n,s)\dm r\bigr). \end{equation} In the standard model, this is equivalent to $a(n,s)-a_n\le r$. For consistent computably enumerable $T\supseteq\EA$ and standard $n,r$, \begin{equation}\label{eq:adeqspectrum} \exists s\in\N\,[T\vdash\Adeq_{\bd r}(\bd n,\bd s)] \quad\Longleftrightarrow\quad E_T(n)\le r. \end{equation} More precisely, the set $\{s\in\N:T\vdash\Adeq_{\bd r}(\bd n,\bd s)\}$ is empty when $ra_n$. Finitely many thresholds are involved for each $n$, so a finite length budget includes all of these refutations. Hence the limit of $H_T$ is $a_n$. Lemma~\ref{lem:familysoundness} supplies positive-family soundness, and Theorem~\ref{thm:spectrum} gives the precision identity. Apply Theorem~\ref{thm:scalar} to the computable decreasing sequence $b\mapsto H_T(n,b,v)$ to obtain \eqref{eq:rankBB}. Enlarging the rank budget enlarges the set of refutations, proving the final monotonicity assertions. \end{proof} Thus a constant quantifier-rank bound can coexist with Busy Beaver growth of the length needed to complete the false threshold family. In this argument the unrestricted resource is the size and term structure of the cut-free proof. The rank is the full quantifier nesting specified in the preliminaries. \subsection{Elementary verification of ground computations} \begin{lemma}[Ground verification for a fixed bounded formula]\label{lem:ground} For every fixed $\Delta_0(\exp)$ formula $\varphi(\vec x)$, allowing the fixed elementary definitional extensions, there are elementary functions $v^+_\varphi,v^-_\varphi$ such that $\EA$ proves \[ \varphi(\vec x)\to \Prf_{\EA}\bigl(v^+_\varphi(\vec x), \code{\varphi(\bd{\vec x})}\bigr) \] and \[ \neg\varphi(\vec x)\to \Prf_{\EA}\bigl(v^-_\varphi(\vec x), \code{\neg\varphi(\bd{\vec x})}\bigr). \] Their running times, output lengths, and numerical output codes admit elementary bounds depending on the fixed formula and coding. \end{lemma} \begin{proof} First replace the auxiliary function symbols by their fixed bounded graph definitions and elementary value bounds. This is a fixed syntactic translation with $\EA$-provable correctness. It suffices to work with $\Delta_0(\exp)$ formulas. For a fixed term, its value at numeral arguments can be computed together with an arithmetic derivation of the corresponding ground equality. The usual defining equations for addition, multiplication, and exponentiation give such derivations by finite iteration. Because the term is fixed, its values and these derivations have elementary bounds in the input values. Ground equalities and inequalities are decided using these evaluations, and the resulting positive or negative atomic proofs are assembled by fixed logical proof operations. Proceed by induction on the fixed formula structure. Boolean connectives are handled by their corresponding finite proof constructors. For a bounded quantifier, evaluate its bound $m$ and process the instances with indices $0,\ldots,m$. An existential truth or a universal falsehood uses the first successful instance as a witness or counterexample. A universal truth or an existential falsehood combines all the relevant instance proofs with the elementary arithmetic finite-case derivation \[ z\le\bd m\ \longrightarrow\ (z=0\lor z=1\lor\cdots\lor z=\bd m). \] The nesting depth of these evaluation loops is bounded by the fixed formula depth. The loops, their values, and the lengths of their proof outputs consequently have a fixed-height exponential bound. Encoding a bounded-length proof contributes one further exponential and remains elementary. The same construction is verified in $\EA$. At each loop, the induction invariant states that the partial output is a correct derivation of the corresponding finite conjunction, disjunction, or implication. Once the displayed elementary bounds are fixed, this is a bounded arithmetic assertion. Bounded induction verifies the loop, and the finitely many structural steps prove the two implications in the statement. For the corresponding fixed-formula proof bound in formalized $\Sigma_1$-completeness, see~\cite[Proposition~1.2 and the following paragraph]{Beklemishev}. \end{proof} In particular, if $f$ is one of the fixed elementary functions, the lemma gives a computation-proof constructor for $f(\bd{\vec x})=\bd{f(\vec x)}$, with correctness provable in $\EA$. The formula is fixed throughout this assertion; the construction does not quantify over formulas of unrestricted complexity. \subsection{Uniform selectors for bounded positive reflection} \begin{theorem}[An elementary verified selector]\label{thm:selector} For the explicit theory presentations of the preliminaries, there is an elementary function $S_T(n,L,u,e)$ such that \begin{equation}\label{eq:selector} \EA\vdash\forall n,L,u,e\; \Prf_T\left(S_T(n,L,u,e), \code{\RFN_T^{[\bd e]}(\bd n;\bd L,\bd u)}\right). \end{equation} Consistency and soundness of $T$ are not hypotheses. The selected output proof is not required to satisfy the input resource bounds $L,u$. \end{theorem} \begin{proof} Compute $d=P_T(n,L,u)$ by the bounded proof search. If $d>0$, retain a proof $p$ witnessing the maximum. This bounded choice is elementary, and $\EA$ verifies that the retained object proves $\Theta(\bd n,\bd d)$. If $d=0$, use a numeral instance of the fixed base theorem $\Theta(n,0)$. Apply Lemma~\ref{lem:ground} to the graph of $P_T$ to construct an $\EA$-proof of \[ P_T(\bd n,\bd L,\bd u)=\bd d. \] Use the stipulated elementary, $\EA$-verified embedding to regard this as a $T$-proof. Ground arithmetic and the fixed downward-closure proof now transform the chosen proof of $\Theta(\bd n,\bd d)$ into a proof of \[ \Theta\bigl(\bd n,P_T(\bd n,\bd L,\bd u)\dm\bd e\bigr). \] Finally instantiate the right-to-left direction of \eqref{eq:normalP} and combine the proofs to obtain the indicated numeral instance of bounded reflection. The proof search has the elementary bounds $N(n)$ and $J(L)$; the checker, maximum computation, numeral substitutions, ground-verification constructor, and proof compositions are elementary. All the proof-preservation assertions for these operations are available in $\EA$. In the $d>0$ branch, the only use of the selected $T$-proof is its verified syntactic correctness; its arithmetic conclusion is not reflected into the metatheory. These facts establish \eqref{eq:selector} by bounded arithmetic verification of the construction. \end{proof} In particular, fixed integers $h,c$ can be chosen so that the running time and output length of the selector are bounded by \[ 2_h\bigl((n+L+u+e+c)^c\bigr), \qquad 2_0(x)=x,\quad 2_{j+1}(x)=2^{2_j(x)}. \] The integers depend on the fixed formula, proof checker, and proof embeddings. For a computably enumerable presentation containing $\EA$ only extensionally, the same argument gives an external total computable selector by searching for the required $T$-proofs of elementary facts; the stronger elementary and internally verified conclusion uses the presentation assumption in the theorem. Equation~\eqref{eq:selector} verifies a selected sequence of proofs of numeral instances. The universal closure of their conclusions is a different reflection assertion. This distinction is discussed in~\cite[Section~5.1]{Artemov}; selector provability for reflection instances appears in~\cite[Example~3.5]{Gadsby}, and the classical explicit-reflection construction is given in~\cite[Lemma~2.2]{Beklemishev}. Here the bounded maximum yields an elementary verified selector with the specified presentation. Under both family soundness conditions, Theorem~\ref{thm:spectrum} excludes concrete bounded-completion proofs at errors below $E_T(n)$. Refutation completeness at the chosen rank makes this bound attainable. Proposition~\ref{prop:partialselector} identifies exactly where a proof-selecting procedure for completion can terminate. \section{Chaitin counts: sharp precision bounds and joint counting} The count of incompressible strings has enough information to make the general precision bounds match. We first prove its complexity to within a constant, then apply the scalar and finite-coordinate correspondences. \subsection{Information in the exact count} For the fixed optimal plain machine $U$, set \begin{equation}\label{eq:chaitin-counts} X_n=\{0,1\}^{n+1},\qquad N_n=2^{n+1},\qquad D_n=\#\{x\in X_n:C_U(x)>n\}. \end{equation} There are $N_n-1$ binary programs of length at most $n$, so \[ 1\le D_n\le N_n. \] Let $D_n(t)$ be the number of target strings that have not occurred as completed outputs after every program of length at most $n$ has been simulated for $t$ steps. Only completed outputs in $X_n$ are counted, and duplicate outputs are removed. Then $D_n(t)\searrow D_n$. With a fixed ordinary machine representation, these finite simulations and duplicate checks admit elementary arithmetizations. Thus the associated threshold formula \[ G(n,d)=\forall t\,[D_n(t)\ge d] \] falls under the preceding arithmetical results. \begin{theorem}[Constant-precision complexity of the count]\label{thm:count} With the unconditional and conditional machines fixed as in Section~2, \begin{equation}\label{eq:chaitin-exact-information} C(D_n\mid n)=C(D_n)=C(n,D_n)=n+O(1). \end{equation} Each expression in \eqref{eq:chaitin-exact-information} is individually equal to $n$ up to an additive constant. \end{theorem} \begin{proof} First define a fixed partial computation $E(n,d)$. Dovetail all $U$-programs of length at most $n$, recording distinct completed outputs in $X_n$. Once $N_n-d$ such outputs have appeared, return the lexicographically least unrecorded element of $X_n$. For $d=D_n$, all compressible target strings eventually appear, so the computation terminates and returns a string $x$ with $C_U(x)>n$. When $D_n=N_n$, it terminates immediately. No correctness claim is made for an incorrect parameter $d$. Let $q$ be a shortest conditional program with $V(q,n)=D_n$, and put $\ell=|q|$. The required lower bound is immediate if $\ell\ge n$. Otherwise write $h=n-\ell>0$, and encode $h$ by its Elias gamma code $\gamma(h)$, whose length is \[ \lambda(h)=2\floor{\log h}+1. \] A fixed unconditional decoder reads $\gamma(h)$, treats the remaining input as $q$, determines its length $\ell$, and reconstructs $n=\ell+h$. It then computes $V(q,n)$ and applies $E$. Optimality of $U$ gives a constant $c$ such that \[ nn\}, \qquad \mathbf D_n=(D_n^{(1)},\ldots,D_n^{(m)}). \] The machines, their number, and the algorithms specifying the tolerances are fixed throughout this subsection. Thus their descriptions may contribute to constants, but do not grow with $n$. \begin{theorem}[The maximum law for joint counts]\label{thm:jointmax} For fixed total computable functions $r_1(n),\ldots,r_m(n)$, the one-sided and two-sided rectangular distortion complexities both satisfy \begin{equation}\label{eq:jointmax} \RD_{\mathbf r}(\mathbf D_n\mid n) =\max_{1\le i\le m}\max\{0,n-\log(2r_i(n)+1)\}+O(1). \end{equation} In particular, \begin{equation}\label{eq:joint-exact-information} C(\mathbf D_n\mid n)=n+O(1). \end{equation} For the coordinatewise counting approximation and its simultaneous completion modulus $\mu_{\mathbf D}$, \begin{equation}\label{eq:joint-completion} \kappa(\mu_{\mathbf D}(n,\mathbf r(n))\mid n) =\max_{1\le i\le m}\max\{0,n-\log(2r_i(n)+1)\}+O(1). \end{equation} \end{theorem} \begin{proof} Let $r_* =\min_i r_i(n)$ and $w=r_*+1$. Consider the sum of the counting approximations and its limit, \[ S_n(t)=\sum_{i=1}^m D_n^{(i)}(t), \qquad S_n=\sum_{i=1}^m D_n^{(i)}. \] The sequence $S_n(t)$ is computable and nonincreasing, and \[ m\le S_n\le m2^{n+1}. \] Corollary~\ref{cor:weightedsum} shows that its exact limit retains the joint information of the individual counts. For the approximation bound, encode only the quotient $j=\floor{S_n/w}$. Its range is computable from $n$, and its description requires at most \begin{equation}\label{eq:joint-code-length} \ceil{\log\left(\floor{\frac{m2^{n+1}}{w}}+1\right)} =\max\{0,n-\log w\}+O_m(1) \end{equation} bits, in addition to fixed decoder overhead. From this index, the decoder computes the upper endpoint \[ u=\min\{m2^{n+1},(j+1)w-1\}, \] which satisfies $S_n\le u\le S_n+r_*$. It searches for the first stage $t$ with $S_n(t)\le u$. Since $S_n(t)$ eventually equals $S_n$, the search terminates. At the returned stage, \[ \sum_{i=1}^m\bigl(D_n^{(i)}(t)-D_n^{(i)}\bigr) =S_n(t)-S_n\le r_*. \] Every summand is nonnegative. Consequently the output vector $\widehat D_n^{(i)}=D_n^{(i)}(t)$ satisfies \[ 0\le\widehat D_n^{(i)}-D_n^{(i)}\le r_*\le r_i(n) \qquad(1\le i\le m). \] This is a joint one-sided approximation. Equation \eqref{eq:joint-code-length} gives an upper bound of $\max\{0,n-\log(r_*+1)\}+O(1)$, which differs by at most a constant from the right-hand side of \eqref{eq:jointmax}. For the lower bound, compute from $n$ the first coordinate attaining $r_*$. Projecting any joint approximation onto that coordinate gives a valid approximation to its Chaitin count. Apply the lower bound \eqref{eq:chaitin-explicit-lower} for that machine. Since there are only finitely many fixed machines, their individual constants have a common maximum. This proves \eqref{eq:jointmax} for two-sided distortion and hence, with the preceding one-sided upper bound, for both conventions. Setting all tolerances to zero gives \eqref{eq:joint-exact-information}. Finally, the vector counting approximation descends in a finite product order, and one-sided rectangular distortion is hereditary on its order intervals. Apply Theorem~\ref{thm:duality} and omit the fixed computable tolerance vector from the condition. This proves \eqref{eq:joint-completion}. \end{proof} The joint complexity is $n+O(1)$, the same as that of each coordinate. Quantizing the sum controls the total nonnegative error and hence every coordinate error. The maximum law applies this weighted-sum argument to finitely many fixed monotone counts. When the machine family or its presentation varies, its description must be supplied as side information or counted as in Theorem~\ref{thm:advice}. \subsection{Boundary examples for the information--resource correspondence} \begin{example}[The first adequate stage can contain additional information]\label{ex:first} Let $N_n=2^{n+1}$ and define \[ A(n,t)=\max\{3N_n-t,D_n(t)\},\qquad r=N_n, \] where subtraction in the first entry is interpreted over the integers; the maximum is always a nonnegative integer. This is a computable nonincreasing approximation to $D_n$. Since \[ D_n(t)\le N_n\le D_n+N_n, \] the condition $A(n,t)-D_n\le N_n$ is determined exactly by the linear term. Its first occurrence is \begin{equation}\label{eq:first-stage-example} \mu_A(n,N_n)=2N_n-D_n. \end{equation} Both directions of this identity are computable conditional on $n$, and $N_n$ is itself computable from $n$. Hence \[ C(\mu_A(n,N_n)\mid n,N_n)=n+O(1). \] On the other hand, outputting $0$ approximates $D_n$ within $N_n$, and $2N_n$ is a computable upper bound on the first adequate stage. Therefore \[ \RD^\pm(D_n,N_n\mid n,N_n)=O(1), \qquad \kappa(\mu_A(n,N_n)\mid n,N_n)=O(1). \] The gap between the complexity of the first adequate stage and the complexity of an adequate bound is thus unbounded. The replacement of $\kappa$ by pointwise complexity in Theorem~\ref{thm:duality} fails even for scalar monotone approximations. \end{example} \begin{example}[Failure without monotonicity]\label{ex:nonmono} Let $f(n,t)=1$ if some $U$-program of length at most $n$ halts at exactly step $t$, and let $f(n,t)=0$ otherwise. The predicate is decidable by finite simulation, and every row is eventually zero. Its limit therefore has constant distortion complexity at error zero. For all sufficiently large $n$, there is at least one halting program in the finite family. Let $\BT_U(n)$ be its maximum halting time. The genuine eventual stabilization threshold is \[ \nu(n)=\min\{t:\forall s\ge t\ f(n,s)=0\}=\BT_U(n)+1. \] For the finitely many possible empty families, set $\nu(n)=0$. Given any $s\ge\nu(n)$, simulating all the relevant programs for $s$ steps determines every completed output, and hence computes $D_n$. Thus, uniformly for all sufficiently large $n$, \[ C(s\mid n)\ge n-O(1)\qquad(s\ge\nu(n)), \] and consequently \[ \kappa(\nu(n)\mid n)\ge n-O(1). \] The limit still has a constant-length description. Monotonicity in the correspondence theorem supplies the effective search that turns an approximation to the limit into an adequate resource bound; general convergent sequences need not admit that search. \end{example} \section{Proof translation and witness descent}\label{sec:transport} \subsection{Verified proof translations} To compare completion and reflection across theories, we specify both a proof translation and a comparison between its conclusions. Throughout this section the formula families are fixed, so their instances can be compared directly without a uniform truth predicate. Let $\theta(n,d)$ and $\psi(n,d)$ be formulas of a common arithmetical language, and put $\theta_{n,d}=\theta(\bd n,\bd d)$ and $\psi_{n,d}=\psi(\bd n,\bd d)$. The theories $T$ and $S$ may have larger languages. All formula codes below are obtained by the fixed numeral-substitution functions. Write $\RFN_{T,\theta}(n;L,r)$ for reflection over $d\le N(n)$ with proof length at most $L$ and quantifier rank at most $r$. \begin{proposition}[Transport of bounded reflection]\label{prop:reflection-transport} Suppose that $f$ is an elementary proof transformation and that $F,R$ are elementary functions for which $\EA$ proves, uniformly in $d\le N(n)$, \begin{align*} &\Prf_T(p,\seq\theta_{n,d})\land |p|\le L\land\rk(p)\le r\\ &\qquad\longrightarrow \Prf_S(f(n,d,p),\seq\psi_{n,d}) \land |f(n,d,p)|\le F(n,L,r) \land\rk(f(n,d,p))\le R(n,L,r). \end{align*} If, in addition, \[ \EA\vdash\forall n\,\forall d\le N(n)\, \bigl(\psi(n,d)\to\theta(n,d)\bigr), \] then \begin{equation}\label{eq:transport} \EA\vdash \RFN_{S,\psi}(n;F(n,L,r),R(n,L,r)) \to\RFN_{T,\theta}(n;L,r). \end{equation} \end{proposition} \begin{proof} Reason in $\EA$. Fix $d\le N(n)$ and a source proof satisfying the stated bounds. The verified transformation supplies an $S$-proof of $\psi_{n,d}$ within the target bounds. Target reflection yields $\psi(n,d)$, and the stipulated implication yields $\theta(n,d)$. Existential quantification over the source proof, followed by bounded universal quantification over $d$, gives \eqref{eq:transport}. \end{proof} There is a useful syntactic alternative to the semantic implication in Proposition~\ref{prop:reflection-transport}. Suppose that an elementary function $e(n,d)$ supplies $S$-proofs \[ e(n,d):\psi_{n,d}\seq\theta_{n,d}, \] whose correctness and bounds $|e(n,d)|\le B(n)$ and $\rk(e(n,d))\le\rho(n)$ are verified in $\EA$. Let $\ell_\theta(n)$ and $\ell_\psi(n)$ bound the lengths of the corresponding instances for $d\le N(n)$. A cut between $f(n,d,p)$ and $e(n,d)$ gives an $S$-proof of $\theta_{n,d}$ with bounds \begin{align*} F^+(n,L,r)&=F(n,L,r)+B(n)+\ell_\psi(n)+\ell_\theta(n)+5,\\ R^+(n,L,r)&=\max\{R(n,L,r),\rho(n)\}. \end{align*} Indeed, the conclusion of this cut is $\seq\theta_{n,d}$, whose encoded length is $|\theta_{n,d}|+4$. Formula~\eqref{eq:cutsize} accounts for the displayed additive cost. Consequently, \[ \EA\vdash \RFN_{S,\theta}(n;F^+(n,L,r),R^+(n,L,r)) \to\RFN_{T,\theta}(n;L,r). \] The comparison proof is used as an actual proof subtree, and reflection is applied to its resulting conclusion. For a transformation that takes every bounded $T$-proof of the empty sequent to an $S$-proof of the empty sequent, the same argument yields \begin{equation}\label{eq:consistency-transport} \EA\vdash \Con_S(F_\bot(n,L,r),R_\bot(n,L,r)) \to\Con_T(L,r). \end{equation} Here correctness and the bounds of the empty-sequent transformation are separate hypotheses. If a translation first produces a proof of a formula $\bot^J$, one includes a fixed target proof of $\bot^J\seq$ and the final cut in $F_\bot$ and $R_\bot$. Positive proofs and counterproofs require different comparison directions. Suppose that $J$ translates a fixed family $\theta$ into $\theta^J$. To return a positive translated proof to the original family, the required target sequent is \[ \theta^J\seq\theta. \] To return a translated counterproof $\theta^J\seq$, the required sequent is \[ \theta\seq\theta^J. \] Cutting in the latter direction gives a counterproof of $\theta$. More precisely, suppose an elementary transformation takes each $T$-counterproof of $\theta_{n,d}$ to an $S$-counterproof of the same instance, with correctness and bounds $F^-(n,b,v),R^-(n,b,v)$ verified in $\EA$. The transformation may first pass through $\theta^J$ and then use the displayed comparison. For the error-indexed completeness assertions of Section~\ref{sec:frontiers}, direct substitution in their definition gives \begin{equation}\label{eq:completion-transport} \EA\vdash \BC_{T,\theta}^{[e]}(n;b,v) \to \BC_{S,\theta}^{[e]}(n;F^-(n,b,v),R^-(n,b,v)). \end{equation} Indeed, the unchanged antecedent $\neg\theta(n,d\dm e)$ supplies the source counterproof, which is then transformed. Thus the common formula family and the comparison direction are explicit in the transfer. The comparison of certificate maxima in Section~4 applies with these same bounds. For a fixed finite source axiom set, the domain and axiom-translation certificates can be incorporated into a fixed compiler. Appendix~\ref{app:compiler} gives such a construction for one-dimensional domain relativization. When the source axiom set varies, its translation certificates are additional input data whose existence, correctness, and resource bounds must be supplied uniformly. This is the quantitative aspect of the distinction between pointwise axiom interpretations and the smooth forms of interpretability studied in \cite[Section~3]{Joosten}. \subsection{Composition of comparisons in a common target theory} The cost of comparing several interpretations can be calculated without reapplying their full proof translators. Once all comparisons are given in one target calculus, they compose by cuts. \begin{theorem}[Exact cost of a chain of comparisons]\label{thm:chainglue} In the same target LK calculus, let \[ \pi:\seq A_0,\qquad \nu:\seq\neg A_m,\qquad e_i:A_{i-1}\seq A_i\quad(1\le i\le m), \qquad m\ge1. \] There is an elementary construction of an empty-sequent proof $g$ such that \begin{align} |g|={}&|\pi|+|\nu|+\sum_{i=1}^m|e_i| +|A_0|+2\sum_{i=1}^{m-1}|A_i|\notag\\ &\qquad+9|A_m|+5m+23,\label{eq:chain} \end{align} and \[ \rk(g)\le \max\{\rk(\pi),\rk(\nu),\rk(e_1),\ldots,\rk(e_m)\}. \] The exact count uses the identity, cut, and negation-node encodings fixed in Section~2. In particular, a $\neg L$ node introducing $\neg A$ records $A$. \end{theorem} \begin{proof} Set $\pi_0=\pi$. For $1\le i\le m$, cut $\pi_{i-1}:\seq A_{i-1}$ against $e_i:A_{i-1}\seq A_i$. The resulting proof $\pi_i:\seq A_i$ has length \[ |\pi_i|=|\pi_{i-1}|+|e_i|+|A_{i-1}|+|A_i|+5. \] Therefore \[ |\pi_m| =|\pi|+\sum_{i=1}^m|e_i| +|A_0|+2\sum_{i=1}^{m-1}|A_i|+|A_m|+5m. \] Put $a=|A_m|$. The identity proof $A_m\seq A_m$ has length $2a+6$. Applying $\neg L$ gives $\neg A_m,A_m\seq$. The conclusion sequent has length $2a+6$, so the negation node and its identity premise together have length \[ (2a+6)+(1+a+2a+6)=5a+13. \] Cut this proof against $\nu:\seq\neg A_m$. The cut formula has length $a+1$ and the conclusion $A_m\seq$ has length $a+4$. Thus the resulting counterproof has length $|\nu|+7a+19$. Its final cut with $\pi_m$ adds $a+4$, because the empty sequent has length $3$. Hence \[ |g|=|\pi_m|+|\nu|+8a+23, \] which is \eqref{eq:chain}. Every cut formula is one of the $A_i$ or $\neg A_m$, and all other newly introduced formulas already occur in the displayed end-sequents. Negation does not increase quantifier rank. This proves the rank bound. Each input proof is inserted once, so the construction is a tree-proof construction. Its verification consists of checking the indicated rule instances and is formalizable in $\EA$. \end{proof} Local consistency at the bounds in Theorem~\ref{thm:chainglue} excludes the simultaneous existence of all the displayed proofs. In contrast, composing full proof translators with length bounds $c_i(s+1)^{d_i}$ produces the composed bound $F_m\circ\cdots\circ F_1(s)$, whose polynomial degree for a fixed chain can be taken to be $\prod_i d_i$. These are two different constructions: additive composition of supplied comparisons and composition of the underlying translators. \subsection{Witness descent on arithmetical cuts} Let $M$ be an arithmetical structure, and let $I\subseteq J$ be initial substructures closed under the function symbols occurring in the formulas under consideration. Relations on both domains are induced from $M$. For parameters in $I$, every $\Delta_0$ formula is absolute between $I$ and $J$. To see this, first use function closure to establish that all terms have the same values in the two structures. In the bounded-quantifier step, the bound is an element of $I$, and initiality identifies the two domains below that bound. Induction on formulas completes the proof. For a $\Sigma_1$ formula $H(\bar a)=\exists w\,R(\bar a,w)$ with $R\in\Delta_0$ and $\bar a\in I$, absoluteness gives \[ H^I(\bar a)\to H^J(\bar a). \] The reverse implication is the witness-descent assertion \[ \DW_{I,J}(H):\quad \exists w\in J\,R(\bar a,w) \to\exists w\in I\,R(\bar a,w). \] If $G=\neg H$, classical contraposition gives the exact equivalence \begin{equation}\label{eq:cut-adequacy-descent} G^I(\bar a)\to G^J(\bar a) \quad\longleftrightarrow\quad \DW_{I,J}(H). \end{equation} Thus, for a $\Pi_1$ threshold family, the comparison direction that returns reflected truth from the smaller domain to the larger domain is precisely counterexample-witness descent. Theorem~\ref{thm:adequacy} gives the finite-window, finite-error counterpart of this assertion. There is a particularly direct instance for consistency. Fix the ambient proof predicate \[ P_T(p)=\Prf_T(p,\seq),\qquad H_T=\exists p\,P_T(p). \] For an arbitrary unary predicate $I$, define \[ \Con_{T,P}^I=\neg\exists p\,(I(p)\land P_T(p)), \] \[ \DW_I(H_T)= (\exists p\,P_T(p))\to\exists p\,(I(p)\land P_T(p)). \] Pure first-order logic proves \begin{equation}\label{eq:cutcon} \Con(T)\longleftrightarrow \bigl(\Con_{T,P}^I\land\DW_I(H_T)\bigr). \end{equation} Indeed, global consistency gives both conjuncts, the second vacuously. Conversely, a global contradiction proof would descend to an $I$-proof and contradict the first conjunct. This equivalence keeps the proof predicate fixed. Identifying $\Con_{T,P}^I$ with a relativization of the entire consistency formula additionally requires absoluteness of the chosen proof predicate, including the functions used to check its certificates. \subsection{Closure under numerical proof codes} The numerical size of a code must be distinguished from the symbol length of the encoded proof. For the fixed-width alphabet coding, with an initial marker preventing leading-zero ambiguity, a proof object $p$ satisfies \[ \log_2(\code p+1)=\Theta(|p|+1). \] The construction in Theorem~\ref{thm:chainglue} has output length bounded by a constant multiple of the length of its entire encoded input list. It therefore has a fixed polynomial bound in the numerical code of that list. If the whole input-list code lies in an initial segment closed under multiplication, this polynomial bound places the output code in the same segment. The premise concerns the code of the list, including all its entries, rather than separate membership assertions for its entries. For a proof compiler with symbol-length bound $K(s+1)^d$, the corresponding numerical-code bound has the form \begin{equation}\label{eq:compiler-code-bound} \code{p^J}\le 2^{K'\left(\log_2(\code p+2)\right)^d} \end{equation} after increasing the fixed constant $K'$. When $d>1$, multiplicative closure alone does not yield closure under this function. A sufficient condition for every fixed $d$ is closure under multiplication and \[ \omega_1(x)=2^{\ell_2(x)^2},\qquad \ell_2(x)=\lceil\log_2(x+1)\rceil. \] Choose a fixed $k$ with $2^k\ge d$. A sufficiently large fixed power of $\code p+2$, followed by $k$ iterations of $\omega_1$, bounds the right-hand side of \eqref{eq:compiler-code-bound}. Initiality then places the compiler output in the cut. For completeness, the distinction between multiplication and $\omega_1$ closure already occurs in elementary model-theoretic examples. Let $a$ be a nonstandard element of a model of $\PA$, and consider the externally specified cut \[ I=\{x:xa^k$ for every standard $k$, so $\omega_1(a)\notin I$. This example concerns closure properties; it does not assert that $I$ is definable in the original arithmetical language. For the relation between substitution, smooth interpretability, and collection, see~\cite[Sections~2--3]{Joosten}. Related cut-based $\Sigma_1$-soundness results for consistent restricted sequential theories appear in~\cite[Appendix~A, Theorem~A.2]{Visser}. \section{Restricted Chaitin arguments} \label{sec:applications} The results distinguish the information in an adequate resource bound, the provability of its adequacy, and the construction of proofs of bounded reflection. The normal forms in Theorem~\ref{thm:normal} connect these questions through finite threshold maxima. Applying them to a restricted arithmetic requires an effective proof presentation and a verified comparison of the relevant formulas. \begin{example}[The cost of axiom evidence]\label{ex:axiomcost} Consider a presentation containing every true $\Sigma_1$ sentence as an axiom. If the cost of an axiom instance records only its formula and omits the evidence that it has been enumerated, every false computational threshold has a one-axiom refutation. The valid axiom formulas within a given symbol bound then have no uniform effective finite listing. Indeed, such listings would decide membership in the set of true $\Sigma_1$ sentences. Including the enumeration evidence makes the bounded classes decidable. The resulting presentation satisfies the effectiveness convention of Section~\ref{sec:preliminaries}, and Corollary~\ref{cor:certificate} applies with the full proof cost. \end{example} For the threshold family associated with $D_n$, a varying presentation and a finite search budget must jointly supply the information required by the desired precision. Proposition~\ref{prop:advice-attainment} places this information in the presentation parameter. Provability of the resulting search's adequacy is then determined by the normal form at its remaining threshold. Thus the presentation parameter and the numerical budget must both be specified before the bounds can be applied to a restricted Chaitin argument. In the setting of Nelson's \emph{Elements}~\cite{Nelson}, such an application requires the program coding and counting formula, the proof transformation used for the relevant finite fragment, and the comparison between interpretation domains. The fixed-rank theorem of Section~\ref{sec:rankselectors} concerns ordinary formula quantifier depth. A treatment of a calculus with special constants and its own rank or level functions requires a translation from those resources to the proof quantities fixed here. Once that translation and its internal verification are given, the reflection-transfer theorem and the proof-composition estimates provide the corresponding finite consistency bounds. For a $\Pi_1$ threshold on nested initial substructures, the required smaller-to-larger-domain implication is equivalent to descent of counterexample witnesses, provided the bounded matrix is absolute. For contradiction search with a fixed proof predicate, equation~\eqref{eq:cutcon} expresses full consistency as restricted consistency together with witness descent. These are the formula comparisons that a transfer of the finite precision bounds must supply. \appendix \section{Length and rank bounds for fixed-domain relativization}\label{app:compiler} This appendix supplies a concrete compiler satisfying the hypotheses of Section~\ref{sec:transport}. The source language $\mathcal L$ is finite and contains a constant $0$. Its function and relation symbols retain their interpretations in the target language. Fix a target formula $\delta(u)$ whose only possible free variable is $u$, and put $d=\qr(\delta)$. Let $\Gamma$ be a fixed finite set of closed source axioms. For a term $t$, write $\delta(t)$ for capture-free substitution of $t$ for the free occurrences of $u$ in $\delta(u)$. Define formula translation by preserving atomic formulas, commuting with propositional connectives, and setting \[ (\forall x\,A)^\delta =\forall x\,(\delta(x)\to A^\delta),\qquad (\exists x\,A)^\delta =\exists x\,(\delta(x)\land A^\delta). \] The expressions $\delta(x)$ are chosen capture-free copies of the fixed template. Domain assumptions for free variables will be placed in sequent antecedents rather than built into the translation of atomic formulas. \begin{lemma}[Substitution and formula size]\label{lem:domain-translation} For every formula $A$ and every capture-free term substitution, \[ (\neg A)^\delta=\neg A^\delta, \qquad (A[t/x])^\delta\equiv_\alpha A^\delta[t/x], \] and \[ \qr(A^\delta)\le\qr(A)+d. \] There is an effectively determined constant $c_\delta$ such that \[ |A^\delta|\le c_\delta(|A|+1),\qquad |\delta(t)|\le c_\delta(|t|+1). \] Here the lengths of binary variable indices are included in the formula and term lengths. \end{lemma} \begin{proof} The identities and the rank bound follow by induction on $A$. The atomic and propositional steps are immediate. Before a quantifier step, rename its bound variable away from the free variables of $t$. The inserted domain template has no free parameter other than its displayed variable, so the same capture-free renaming makes both sides agree up to $\alpha$-equivalence. For example, \[ \qr\bigl(\forall x(\delta(x)\to B^\delta)\bigr) =1+\max\{d,\qr(B^\delta)\} \le 1+\qr(B)+d. \] The existential case is identical at the level of quantifier depth. To bound the size of an inserted template $\delta(x)$, apply the permutation exchanging the variable names $u$ and $x$ to a fixed copy of $\delta(u)$. Bound occurrences are permuted together with their binders. The resulting formula has $x$ as its only possible free variable and is an $\alpha$-variant of the required instance. Its size is at most a fixed constant times $1+|x|$. Each insertion occurs at a quantifier of the source formula, where the name of the bound variable is already charged to $|A|$. Summing these costs gives the formula-size bound. For $\delta(t)$, first rename the finitely many bound variables of the template away from the free variables of $t$. Fresh names can be selected from the first $O_\delta(|t|+1)$ indices, so their total additional size is $O_\delta(\log(|t|+2))$. The number of occurrences of the placeholder $u$ is fixed. Substituting $t$ therefore has size $O_\delta(|t|+1)$, as asserted. \end{proof} As fixed in Section~2, formulas are taken modulo $\alpha$-equivalence and represented by explicit named-variable prefix strings. The rule checker compares bound-variable structure by canonical bound-variable indexing, an elementary operation. Actual representative strings, including all variable indices, still determine proof length. Thus the identities modulo $\alpha$ in the lemma are precisely the syntactic identities used by the checker; no unrecorded logical conversion is invoked. All subsequent substitutions use this capture-free convention. \subsection{Domain certificates and proofs for terms} Assume that the target theory $S$ comes with the following fixed proof trees: \begin{enumerate} \item a proof of $\seq\delta(c)$ for each source constant $c$, including $0$; \item for each $k$-ary source function symbol $f$, with $k\ge1$, a proof of \[ \seq\forall x_1\cdots\forall x_k\, \bigl((\delta(x_1)\land\cdots\land\delta(x_k)) \to\delta(f(x_1,\ldots,x_k))\bigr); \] \item a proof of $\seq\gamma^\delta$ for every $\gamma\in\Gamma$. \end{enumerate} For unary functions the antecedent conjunction is simply $\delta(x_1)$. Let $R_{\rm cert}$ be the maximum quantifier rank of all these proof trees. Each occurrence of a certificate in the output is an actual copy of its proof tree, and its full length is charged. For a term $t$, let $\Delta_t$ be the multiset containing one occurrence of $\delta(x)$ for each variable leaf $x$ of the term tree. Repeated occurrences of a variable give repeated assumptions. Constants contribute no assumptions. \begin{lemma}[Term-domain derivations]\label{lem:term-domain} There is an effective construction of $S$-proofs \[ D_t:\Delta_t\seq\delta(t) \] such that, for a fixed constant $K_0$, \[ |D_t|\le K_0(|t|+1)^2, \qquad \rk(D_t)\le\max\{d,R_{\rm cert}\}. \] Every immediate subterm proof is used once in the construction of the proof for its parent term. \end{lemma} \begin{proof} For a variable $x$, use the identity sequent $\delta(x)\seq\delta(x)$. For a constant, use its fixed domain certificate. Suppose $t=f(t_1,\ldots,t_k)$. Instantiate the universal closure certificate for $f$ at $t_1,\ldots,t_k$, and use propositional rules to obtain \[ \delta(t_1),\ldots,\delta(t_k)\seq\delta(t). \] This derivation uses one copy of the fixed certificate. The number of instantiations and propositional steps is bounded by a constant depending on the fixed arity of $f$. Its length is $O(|t|+1)$ by Lemma~\ref{lem:domain-translation}. Cut into it the proofs $D_{t_i}$, one for each argument, obtaining $D_t$. Multiset cut concatenates their leaf assumptions, so the final antecedent is exactly $\Delta_t$. At a term node with subtree $v$, all newly displayed formulas and contexts have total length $O(|v|+1)$. The domain assumptions have that size because each variable leaf contributes a fixed template whose length is linear in the encoded length of the variable name. There are only a fixed number of new rule nodes at each function node. Hence the total length is bounded by a fixed multiple of \[ \sum_{v\text{ a term subtree of }t}(|v|+1) \le (|t|+1)^2. \] This estimate counts the tree representation: each immediate subterm derivation is inserted once, without sharing or duplication. Universal instantiation and term substitution do not increase quantifier depth. Every other new formula is a domain instance or a propositional combination of domain instances, proving the rank bound. \end{proof} \subsection{Scoped eigenvariable regularization} A proof is called regular here if its strong quantifier inferences, $\forall R$ and $\exists L$, have pairwise distinct eigenvariables, each eigenvariable occurs freely only within the premise subtree governed by its inference, and every free variable occurrence in the proof is governed by one of these inferences. Eigenvariable annotations and instantiation terms are part of the proof code, including in vacuous rule instances. The end-sequent under consideration is closed. For a node $v$ of a regular proof, let $E_v$ be the set of eigenvariables whose governing premise subtrees contain $v$. These are the \emph{active eigenvariables} at $v$. Every free variable of the sequent, and every variable in an instantiation term at $v$, belongs to $E_v$; the eigenvariable annotation of a strong inference is a binder for its premise subtree. An active variable can remain absent from the displayed sequent. This occurs, for example, when it appears only in a cut formula above that node. The domain context used below is \[ \mathcal D_v=\{\delta(x):x\in E_v\}, \] with one listed occurrence for each active variable. It is essential to retain this entire context until the governing strong quantifier inference discharges its corresponding assumption. Every source proof with a closed end-sequent can be converted to this form. Traverse the proof tree from its end-sequent towards its leaves while maintaining an environment for free variables. Initially, replace unmanaged free variables by $0$. At a strong quantifier inference with eigenvariable $y$, allocate a fresh variable and, within its premise subtree, map the free occurrences governed by that inference to the fresh variable. A nested inference that reuses the old name receives its own fresh variable and its own local environment. Source formula binders are respected throughout. The eigenvariable condition ensures that changing the local environment leaves the conclusion of the strong inference unchanged. All other inference rules are preserved by capture-free substitution. The axioms in $\Gamma$ are closed and are therefore unchanged. If the original length is $s$, there are at most $s$ strong inferences and at most $s$ variable names occurring in the source code. Choosing fresh names from an initial set of $O(s+1)$ indices, disjoint from those source names and any fixed reserved names, gives encoded fresh names of length $O(\log(s+2))$. The resulting regular proof has length \begin{equation}\label{eq:regularization-size} s'\le K_1(s+1)\log(s+2). \end{equation} Its quantifier rank is unchanged. The traversal is a scoped renaming and substitution operation on an already given proof tree; it neither unfolds a proof DAG nor duplicates a subtree. \subsection{The proof compiler} \begin{theorem}[Fixed-domain proof translation]\label{thm:domain-compiler} Let the language, finite closed axiom set, domain formula, and target certificates be as above. If $p$ is a regular source proof from $\Gamma$ of a closed sequent, of length $s$ and rank $r$, then an $S$-proof $p^\delta$ of its translated end-sequent can be constructed with \begin{equation}\label{eq:compilerpoly} |p^\delta|\le K(s+1)^3, \qquad \rk(p^\delta)\le\max\{r+d,R_{\rm cert}\}. \end{equation} For an arbitrary source proof with a closed end-sequent, the same rank bound and a length bound $K'(s+1)^4$ hold. The constants are effectively determined by the fixed language, domain formula, axiom set, rule encodings, and supplied target certificates. \end{theorem} \begin{proof} First suppose that $p$ is regular. At each source node $v$ with sequent $\Sigma\seq\Pi$, construct a target proof of \begin{equation}\label{eq:guarded-node} \mathcal D_v,\Sigma^\delta\seq\Pi^\delta. \end{equation} We proceed inductively from leaves to the end-sequent. A logical identity becomes the identity for its translated formula, followed by weakening to add $\mathcal D_v$. A nonlogical axiom leaf uses the supplied proof of $\gamma^\delta$, followed by the same weakening. Structural and propositional rules commute with formula translation. In binary rules, the two premise contexts have the same active variables; any duplicate domain assumptions are removed by contraction after the rule has been applied. These contractions retain one copy of every member of $\mathcal D_v$. Contexts are multisets, as fixed in Section~2, so no exchange nodes are required. For a cut, both premise translations contain the domain context of the conclusion node. Cutting on the translated cut formula produces two copies of this context, which are contracted to one. The use of active eigenvariables ensures that guards for variables occurring only in the cut formula are already present in the conclusion context of \eqref{eq:guarded-node}. No assumption has to be removed by an inadmissible reversal of weakening. It remains to describe the four quantifier rules. Consider first a source $\forall R$ inference with eigenvariable $y$. Its translated premise contains $\mathcal D_v,\delta(y)$ in its antecedent and the translated instance $A^\delta[y/x]$ in its succedent. Apply $\to R$ to discharge the distinguished occurrence of $\delta(y)$, and then apply $\forall R$ to obtain \[ \forall x\,(\delta(x)\to A^\delta). \] The variable $y$ is absent from the free variables of the other conclusion formulas and from $\mathcal D_v$. The latter assertion uses the fact that $\delta(x)$ has no free variable other than $x$. Thus the target eigenvariable condition holds. For $\exists L$, first combine the distinguished assumptions $\delta(y)$ and $A^\delta[y/x]$ by $\land L$, and then use $\exists L$ with the same eigenvariable. Lemma~\ref{lem:domain-translation} identifies the required substitution instances. For a source $\forall L$ inference with instantiation term $t$, combine its translated premise with $D_t:\Delta_t\seq\delta(t)$ by $\to L$. This introduces $\delta(t)\to A^\delta[t/x]$ on the left; a subsequent $\forall L$ introduces $\forall x(\delta(x)\to A^\delta)$. Every variable of $t$ is active at the source node. Hence every assumption in $\Delta_t$ is a duplicate of an assumption already present in $\mathcal D_v$, and contraction restores \eqref{eq:guarded-node}. For $\exists R$, combine the translated premise with $D_t$ by $\land R$, using weakening to align the contexts if required by the chosen rule presentation. Apply $\exists R$ to $\delta(t)\land A^\delta[t/x]$, and contract the duplicate domain assumptions. Each translated premise and each term-domain derivation occurs once in these constructions. If equality is treated by its usual substitution rules, their translation is justified by the substitution identity in Lemma~\ref{lem:domain-translation}. We now bound the size. Every displayed source formula and every rule annotation has length at most $s$. The total encoded lengths of the distinct active eigenvariables at any node are at most $s$, because their governing annotations occur in the source proof. It follows that each domain context and each translated source sequent has length $O(s+1)$. A term-domain derivation has length $O((s+1)^2)$ by Lemma~\ref{lem:term-domain}. At a given source node, reconciling contexts requires at most $O(s+1)$ weakenings or contractions, each with a sequent of length $O(s+1)$. The translated inference therefore adds at most $O((s+1)^2)$ symbols beyond its translated premises. The number of source nodes is at most $s$, and no translated premise is duplicated. Summing the local contributions proves the cubic bound. The translated source formulas have quantifier rank at most $r+d$. The auxiliary domain formulas have rank $d$, and the fixed certificate subtrees have rank at most $R_{\rm cert}$. Universal instantiation, propositional rules, and structural rules introduce no larger rank. This proves the rank bound. Since the source end-sequent is closed, its active-variable set is empty; the final sequent \eqref{eq:guarded-node} is therefore exactly the desired translated end-sequent. For an arbitrary proof, first apply the scoped regularization above. By \eqref{eq:regularization-size}, the cubic bound becomes \[ O\bigl((s+1)^3\log^3(s+2)\bigr). \] The inequality $\log^3(s+2)=O(s+1)$ gives the stated quartic bound after adjusting the constant. Regularization does not change quantifier rank. \end{proof} For the fixed data of Theorem~\ref{thm:domain-compiler}, the transformations are elementary on numerical codes. Their correctness is established by bounded induction over the explicitly encoded proof tree, with the displayed elementary output bounds. The chosen proof checker can therefore be used to formalize these transformations in $\EA$. The theorem supplies a uniform compiler for the fixed finite source axiom set; a parameter-dependent collection of source axioms additionally requires the corresponding uniform translation certificates. \clearpage \begingroup \small \linespread{1.0}\selectfont \begin{thebibliography}{ABST17} \setlength{\itemsep}{4pt} \setlength{\parskip}{0pt} \raggedright \bibitem[And17]{Andreev} M. Andreev. Busy beavers and Kolmogorov complexity. arXiv:1703.05170, 2017. \url{https://arxiv.org/abs/1703.05170v1}. \bibitem[ABST17]{ABST} L. Antunes, B. Bauwens, A. Souto, and A. Teixeira. Sophistication vs Logical Depth. \emph{Theory of Computing Systems} 60(2) (2017), 280--298. \url{https://doi.org/10.1007/s00224-016-9672-6}. Preprint: \url{https://arxiv.org/abs/1304.8046v3}. \bibitem[Art25]{Artemov} S. Artemov. Serial properties, selector proofs and the provability of consistency. \emph{Journal of Logic and Computation} 35(3) (2025), exae034; published online 26 July 2024. \url{https://doi.org/10.1093/logcom/exae034}. Preprint: \url{https://arxiv.org/abs/2403.12272v1}. \bibitem[Bek05]{Beklemishev} L. D. Beklemishev. Reflection principles and provability algebras in formal arithmetic. \emph{Russian Mathematical Surveys} 60(2) (2005), 197--268. \url{https://doi.org/10.1070/RM2005v060n02ABEH000823}. \bibitem[Bla21]{Blanck} R. Blanck. Hierarchical incompleteness results for arithmetically definable extensions of fragments of arithmetic. \emph{The Review of Symbolic Logic} 14(3) (2021), 624--644. \url{https://doi.org/10.1017/S1755020321000307}. \bibitem[CLTS]{CLTS} C.-L. Chang, Y.-D. Lyuu, Y.-W. Ti, and A. Shen. Sets of k-independent strings. Author manuscript. \url{https://www.lirmm.fr/~ashen/nafit/2009-indep.pdf}. \bibitem[Gad25]{Gadsby} E. Gadsby. Properties of Selector Proofs. arXiv:2509.19373, 2025. \url{https://arxiv.org/abs/2509.19373v1}. \bibitem[Has22]{Hasuo} I. Hasuo. \emph{Introduction to Logic and Computability}. Author's textbook, version 20 April 2022, \S5.1. \url{https://group-mmm.org/~ichiro/papers/textbook_inflogic_pub_202204.pdf}. \bibitem[Joo16]{Joosten} J. J. Joosten. Characterizations of interpretability in bounded arithmetic. arXiv:1602.00555, 2016. \url{https://arxiv.org/abs/1602.00555v1}. \bibitem[Kou06]{Koucky} M. Kouck\'y. A Brief Introduction to Kolmogorov Complexity. Lecture notes, 4 May 2006. \url{https://iuuk.mff.cuni.cz/~koucky/papers/kolmcomp.pdf}. \bibitem[Nel15]{Nelson} E. Nelson. Elements. Manuscript dated 12 March 2013; published posthumously with an afterword by S. Buss and T. Tao, 2015. \url{https://arxiv.org/abs/1510.00369v1}. \bibitem[Pud98]{Pudlak} P. Pudl\'ak. The Lengths of Proofs. In S. R. Buss (ed.), \emph{Handbook of Proof Theory}, Elsevier, 1998. \url{https://users.math.cas.cz/~pudlak/length.pdf}. \bibitem[TS00]{Troelstra} A. S. Troelstra and H. Schwichtenberg. \emph{Basic Proof Theory}, second edition. Cambridge University Press, 2000, Chapter~4. \url{https://doi.org/10.1017/CBO9781139168717}. \bibitem[VV10]{VV} N. K. Vereshchagin and P. M. B. Vit\'anyi. Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity. \emph{IEEE Transactions on Information Theory} 56(7) (2010), 3438--3454. \url{https://doi.org/10.1109/TIT.2010.2048491}. \bibitem[Vis22]{Visser} A. Visser. Friedman-reflexivity: interpreters as consistoids. arXiv:2111.14413, version 2, 2022. \url{https://arxiv.org/abs/2111.14413v2}. \end{thebibliography} \endgroup \end{document}