OctoInformBeta

OpenAI preprint, September 2026 · §9. Adaptive fingerprints within budget blocks · §9

Theorem 9.8 [Error bounds for the actual estimators]: At every budget, ready row requests get sparse tiles and ready vector requests values in [0,1][0,1], each with error at most bank times allowance

Under its hypotheses the estimator meets its error contract.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The library derandomizes a randomized space-bounded computation presented as a weighted graph: transition weights that lead from smaller to larger nodes, rewards at the nodes, and acceptance probabilities as the values sought. It does so through a hierarchy of stages, and at every stage an estimator answers requests for the entries of the stage’s matrices and vectors.

The estimator’s randomness comes from fingerprints. Random affine lines over a prime field decide which nodes are retained at each level, and an answer is a table or a vector indexed by an environment of three such lines and by retained nodes. The estimator works in budget blocks: at budget MM it answers the requests whose cost is small against MM, from its own answers at smaller budgets, with walks of bounded length on environments in place of averages over all of them. Each request carries an error allowance, and the contract asks, besides sparsity, that every answer lie within the bank, a fixed multiple of its allowance, in a fourth-root norm. The question is whether the answers the estimator actually computes keep this contract at every budget.

Fingerprints and Walks

Let nn be a prime and Vn=(ℤ/n)4V_n=(\mathbb{Z}/n)^4, written as a pair of residue pairs.✦ A rank channel over nn is a pair s=(a,b)s=(a,b) of a direction aa in the punctured frame, the set of nonzero vectors of VnV_n, and an offset b∈Vnb\in V_n✦; its evaluation at a residue yy is the point b+yab+ya of its line.✦ At a level ℓ\ell the box side length is mℓ=⌊(n−1)/2ℓ⌋+1m_\ell=\lfloor(n-1)/2^\ell\rfloor+1✦ and the box is {0,…,mℓ−1}4\{0,\dots,m_\ell-1\}^4, a fraction (mℓ/n)4(m_\ell/n)^4 of VnV_n.✦ A node xx, a natural number read modulo nn, is retained at level ℓ\ell by ss when the hit event occurs: b+xab+xa lies in the box, each coordinate taken by its least nonnegative representative.✦ For a finite domain SS, a finite set of natural numbers, Rℓ(S,s)R_\ell(S,s) is the set of its nodes retained at level ℓ\ell by ss.✦ The rate of level ℓ\ell is 2−4ℓ2^{-4\ell}.✦

An environment is a triple ω=(X,Y,Z)\omega=(X,Y,Z) of rank channels✦, and 𝔼ω\mathbb{E}_\omega is the finite average over all environments, the sum of the values divided by their number.✦ For levels kk, jj and nodes xx, yy, the conditional average at (x,y)(x,y) of a function of environments is its average over the environments whose channel XX retains xx at level kk and whose channel YY retains yy at level jj✦; the conditional average at a node of a function of one channel is its average over the channels that retain the node at a given level.✦

Environments move by walks. A command is a shear, given by a shear choice of two bits, an axial translation, given by a bit, or a cross term, given by two bits✦; a generator is a bit and a command✦, and a generator choice is a generator placed in one of four slots, Γ\Gamma being the set of generator choices.✦ An atom is a bit and a generator choice, 𝒜\mathcal{A} is the set of atoms✦, and a roller index is a letter of the roller alphabet {0,…,10}4\{0,\dots,10\}^4. For levels kk, jj and nodes xx, yy, a path pp of atoms and a path rr of roller indices, words of the same length ll, move an environment by the roller walk wp,rw_{p,r}, one roller step per letter✦; the pair is live at ω\omega when each roller index is the winner for its atom, the roller index selected for that atom at the environment reached so far. The path sampling sum of depth ll of a function ff of environments is Σlf(ω)=∑(p,r)live atω|𝒜|−lf(wp,r(ω)),\Sigma_l f(\omega)=\sum_{(p,r)\ \text{live at}\ \omega}|\mathcal{A}|^{-l}\,f\bigl(w_{p,r}(\omega)\bigr),(1)✦ where 1/|𝒜|1/|\mathcal{A}| is the atom weight.

Stages and Scenes

Matrices and vectors are real and indexed by natural numbers; a product over a finite domain SS sums the middle index over SS✦, and the row weight of a matrix CC at xx is ∑y∈SC(x,y)\sum_{y\in S}C(x,y).✦ A stochastic step matrix on SS at rate ff is a matrix CC whose entries lie in [0,f][0,f], whose row weights are at most 11, and whose positive entries C(x,y)C(x,y) have x,y∈Sx,y\in S and x<yx<y; it is the bounded support matrix on SS with bound 11.✦

Parameter constants are natural numbers k*k_*, KK, JJ and D0D_0, an iteration count, two parameters and a number of copies, with k*>0,(5/A)k*k*!≤11024,128(1+32(k*+1)η(δ))≤K+1,16(k*+1)<D0,64D0(k*+1)2≤δ(J+1),k_*>0,\quad \frac{(5/A)^{k_*}}{k_*!}\le\frac{1}{1024},\quad 128\Bigl(1+\frac{32(k_*+1)}{\eta(\delta)}\Bigr)\le K+1,\quad 16(k_*+1)<D_0,\quad 64D_0(k_*+1)^2\le\delta(J+1),(2)✦ where A=1/4096A=1/4096 is the cutoff scale, δ=A/400\delta=A/400 and η(z)=z/1000\eta(z)=z/1000; k*k_* is called admissible when the first two conditions hold. A stage PP consists of parameter constants, a level, a finite domain SS and a matrix CC✦, and its rate is the rate of its level.✦

A prize triple ℋ=(P,W,v)\mathcal{H}=(P,W,v) is a stage PP with a reward vector WW and a value vector vv, the acceptance probability transported to the nodes.✦ A prize triple ℋ=(P,W,v)\mathcal{H}=(P,W,v) is correct when the matrix CC of PP is a stochastic step matrix on the domain SS of PP at the rate of PP, W≥0W\ge 0, every value of vv lies in [0,1][0,1], and, with CvCv the matrix-vector product over SS, v=W+Cv.v=W+Cv.(3) The iterates ℋ0=ℋ,ℋ1,…\mathcal{H}_0=\mathcal{H},\mathcal{H}_1,\dots of a prize triple ℋ\mathcal{H} are the prize triples obtained from ℋ\mathcal{H} by repeating the prize step, which takes a prize triple to the next one; PiP_i is the stage of ℋi\mathcal{H}_i, with domain SiS_i and matrix CiC_i, and WiW_i is the reward vector of ℋi\mathcal{H}_i.✦

A scene over nn is a prize triple ℋ\mathcal{H} with natural numbers NN, hh, ρ\rho, gg and λ\lambda: a size bound, a height, a roof, a gap and a walk length.✦ The parameter constants of a scene are those of the stage of its prize triple ℋ\mathcal{H}, and the scene hypotheses on a scene over nn are that ℋ\mathcal{H} is correct with its stage at level 00, that D0<nD_0<n and 2ρ≤n2^\rho\le n, that for every i≤hi\le h the domain SiS_i has at most NN nodes and is a legal vertex set, a finite set of natural numbers, its nodes all less than nn, and that the walk length condition holds: 16βλ≤2−72,β=1−116384(10c0|Γ|)2,16\,\beta^{\lambda}\le 2^{-72},\qquad \beta=1-\frac{1}{16384\,(10\,c_0\,|\Gamma|)^2},(4)✦ where β\beta is the ebb factor, 1−β1-\beta is the loss factor of the generator choices at 10c010c_0, c0=6+4/τc_0=6+4/\tau is the gap constant and τ=2(1−cos⁡(π/8))\tau=2(1-\cos(\pi/8)) is the threshold.

Requests, Norms and Budgets

A row request q=(i,u,a,t,κ,μ)q=(i,u,a,t,\kappa,\mu) names a stage ii, a source level uu, a destination level aa, a second destination level tt, a kind κ\kappa and a main flag μ\mu.✦ A kind is a chip, a slot jj for a copy index jj, an echo (b,k)(b,k) with a pilot bit bb and a round kk, or a score at round kk✦; the echoes are the narrow kinds✦, every kind but a score is paired✦, and qq is paired main when μ\mu is set and κ\kappa is paired.✦ A vector request e=(i,u,k)e=(i,u,k) names a stage ii, a source level uu and an optional round kk✦; a prize request has no round✦, and a detector request has i=ui=u and a round.✦

The axis of qq is (Si,N,u,a)(S_i,N,u,a)✦ and that of ee is (Si,N,u,i)(S_i,N,u,i).✦ A monotone linear meter on a set α\alpha is a monotone linear functional II on the real functions on α\alpha; the fourth moment of ff under II is I(f4)I(f^4)✦, and the fourth-root norm is its fourth root.✦ On an axis (S,N,u,a)(S,N,u,a) the vertex meter multiplies by the meter scale 24u/N2^{4u}/N the average over environments of the sum over the source domain Ru(S,X)R_u(S,X), retained by the channel XX of ω\omega✦, and the table meter follows it along the sums over the destination domain Ra(S,Y)R_a(S,Y), retained by the channel YY.✦ A table family assigns a matrix to each environment✦ and a vertex family a vector✦, and their fourth-root norms under the two meters are the vertex norm and the table norm ∥f∥u=(24uN𝔼ω∑x∈Ru(S,X)f(ω,x)4)1/4,∥F∥u,a=(24uN𝔼ω∑x∈Ru(S,X)∑y∈Ra(S,Y)F(ω,x,y)4)1/4.\|f\|_u=\Bigl(\frac{2^{4u}}{N}\,\mathbb{E}_\omega\!\sum_{x\in R_u(S,X)}\!f(\omega,x)^4\Bigr)^{1/4}, \qquad \|F\|_{u,a}=\Bigl(\frac{2^{4u}}{N}\,\mathbb{E}_\omega\!\sum_{x\in R_u(S,X)}\,\sum_{y\in R_a(S,Y)}\!F(\omega,x,y)^4\Bigr)^{1/4}.(5) The table error of two table families FF and GG is du,a(F,G)=∥F1/4−G1/4∥u,ad_{u,a}(F,G)=\|F^{1/4}-G^{1/4}\|_{u,a}, with fourth roots taken entrywise.✦

At budget MM the row request qq is ready when i≤hi\le h, i≤ui\le u, a≤ta\le t, u+M≤ρu+M\le\rho, t+M≤ρt+M\le\rho and its indices are sane: i≤a+k*+10i\le a+k_*+10 for a chip, the same with j<D0j<D_0 for a slot jj, and i=ai=a with k<k*k<k_* for an echo or a score at round kk✦; here k*+10k_*+10 is the padding.✦ The vector request ee is ready when i≤hi\le h, i≤ui\le u, u+M≤ρu+M\le\rho and, if it has a round kk, i=ui=u and k<k*k<k_*.✦

A step key is a triple (k1,k2,r)(k_1,k_2,r) of natural numbers✦, and its cost at the gap gg is 2k1+2k2+gr2k_1+2k_2+gr. The step key of qq is (a,u,rq)(a,u,r_q)✦ and that of ee is (i,u,re)(i,u,r_e), with rq=1+(50+8k*)i+depth⁡(κ)+[μ],re=1+(50+8k*)i+{0without a round,12+6kat round k,r_q=1+(50+8k_*)\,i+\operatorname{depth}(\kappa)+[\mu],\qquad r_e=1+(50+8k_*)\,i+\begin{cases}0&\text{without a round},\\ 12+6k&\text{at round }k,\end{cases}(6)✦ where (50+8k*)i(50+8k_*)\,i is the core depth✦, 50+8k*50+8k_* being the lag✦, [μ][\mu] is 11 for a main request and 00 otherwise, and the depth of a kind is 33 for a chip, 20+8k*20+8k_* for a slot, 13+6k13+6k for an echo with pilot at round kk, 16+6k*+2k16+6k_*+2k for an echo without pilot at round kk and 10+6k10+6k for a score at round kk.✦ A request whose step key has cost cc is active at budget MM when c<⌊M/8⌋c<\lfloor M/8\rfloor✦, and its error allowance at budget MM is αM=2c−⌊M/8⌋.\alpha_M=2^{\,c-\lfloor M/8\rfloor}.(7)✦

Targets

The smooth rising ramp from a0a_0 to a1a_1 sends xx to the value at (x−a0)/(a1−a0)(x-a_0)/(a_1-a_0) of the smooth fade function, which sends xx to 12(c(2x)4+1−c(2−2x)4)\tfrac12\bigl(c(2x)^4+1-c(2-2x)^4\bigr) with c(u)=min⁡(1,max⁡(0,u))c(u)=\min(1,\max(0,u)): it vanishes for x≤0x\le 0, equals 8x48x^4 on [0,12][0,\tfrac12] and 1−8(1−x)41-8(1-x)^4 on [12,1][\tfrac12,1], and equals 11 for x≥1x\ge 1; for a0<a1a_0<a_1 the ramp vanishes up to a0a_0, increases, and equals 11 from a1a_1 on. The cutoff γ\gamma is 11 minus the ramp from 1/21/2 to 4/54/5✦, the boost is the ramp from 1/41/4 to 1/21/2✦ and the shutoff is 11 minus it✦, the light ramp rises from δ\delta to 2δ2\delta✦, the preparation ramp at zz rises from z/2z/2 to 3z/43z/4✦, and the gate at zz is 11 minus the ramp from η(z)\eta(z) to 2η(z)2\eta(z).✦ With clip⁡[a0,a1](x)=min⁡(a1,max⁡(a0,x))\operatorname{clip}_{[a_0,a_1]}(x)=\min(a_1,\max(a_0,x))✦, so that clip⁡[0,1]\operatorname{clip}_{[0,1]} is the clamp to [0,1][0,1]✦, the threshold profile is the shoulder function Q(x)=Aclip⁡[0,1]((x−A)/A)4+max⁡(0,x−2A)Q(x)=A\operatorname{clip}_{[0,1]}((x-A)/A)^4+\max(0,x-2A) with threshold and gap AA✦, and the inverse clipped denominator is x↦ζ/clip⁡[ζ/2,ζ](x)x\mapsto\zeta/\operatorname{clip}_{[\zeta/2,\zeta]}(x)✦, where ζ=δ/109\zeta=\delta/10^9 is a thousandth of the small constant δ/106\delta/10^6.✦

The pilot sequence of the stage PiP_i starts from the zero pilot pair and moves by the stage’s update, its kk-th pilot pair holding the probed vector πk\pi_k and the correction matrix EkE_k; the stage correction matrices form the corrected iteration, with F0=0F_0=0 and Fk+1F_{k+1} the entrywise correction at the stage’s rate, with weights γ(πk*(x))\gamma(\pi_{k_*}(x)), of the combined matrix Ci+FkCiC_i+F_kC_i; and F=Fk*F=F_{k_*}. The question of a row request q=(i,u,a,t,κ,μ)q=(i,u,a,t,\kappa,\mu) reads the kind matrix GG of the stage PiP_i: the matrix CiC_i for a chip, the corrected residual D=Ci+FCi−FD=C_i+FC_i-F for a slot, the test matrix Ci+EkCiC_i+E_kC_i for a score at round kk or an echo with pilot at round kk, and the next combined matrix Ci+FkCiC_i+F_kC_i for an echo without pilot at round kk, products being over SiS_i.✦ The kind threshold θ\theta is 1/21/2 for a chip or a slot, AA for an echo and δ\delta for a score, and the scaled entries of qq are d(x,y)=24aG(x,y)d(x,y)=2^{4a}G(x,y).✦

A trio of figures is a triple (φ,ψ,χ)(\varphi,\psi,\chi) of real functions✦, evaluated at three reals as φ(x)ψ(r)χ(z)\varphi(x)\,\psi(r)\,\chi(z).✦ The trio of qq is its main trio (φ,gateθ,χ)(\varphi,\mathrm{gate}_\theta,\chi)✦: the starting figure φ\varphi is the kind’s piece at levels aa and ii when qq is main, a bin fragment for a chip or a slot, the light ramp for a score and QQ of its argument clipped to [0,k*+32][0,k_*+32] for an echo, and otherwise the preparation ramp at θ\theta✦; χ\chi is the inverse clipped denominator when qq is paired main and 11 otherwise. The support trio at θ\theta is the ramp from θ/4\theta/4 to θ/3\theta/3, 11 minus the ramp from θ/200\theta/200 to θ/100\theta/100, and the constant 11.✦ The switch function at level aa is swa(d)=cut(d)hca(d)\mathrm{sw}_a(d)=\mathrm{cut}(d)\,\mathrm{hc}_a(d), where cut\mathrm{cut} is the smooth rising ramp from 1/21/2 to 11, the rising cutoff, and hca(d)\mathrm{hc}_a(d) is the high cutoff, equal to 11 at level 00 and to 1−cut(d/16)1-\mathrm{cut}(d/16) at every other level. The directional share of copy jj at xx is the share of copy jj among the D0D_0 copies, equal to 1−s(x)+s(x)/D01-s(x)+s(x)/D_0 for the primary copy j=0j=0 and to s(x)/D0s(x)/D_0 for every other copy, where ss is the slice function, the smooth rising ramp from 1/1281/128 to 1/641/64, so that the D0D_0 shares sum to 11.

For a finite set S′S', a function ff on it and a natural number K′K', the padded descending rank rk⁡K′(f;S′)\operatorname{rk}_{K'}(f;S') is the (K′+1)(K'+1)-th largest value of ff on S′S', counted with multiplicity, when S′S' has more than K′K' elements and that value is positive, and 00 otherwise.✦ At an environment ω=(X,Y,Z)\omega=(X,Y,Z) the blob of a source xx lists the scaled entries d(x,y)d(x,y) and, for a paired main request, the companion entries ζT(x,y)\zeta\,T(x,y)✦, where the tooth value T(x,y)T(x,y) is the conditional average, over a channel retaining xx at level uu and a channel retaining yy at level tt, of the bath value of (x,y)(x,y) under the two channels.✦ The rank of the blob is rk⁡(x)=rk⁡K(d(x,⋅);Ra(Si,Y))\operatorname{rk}(x)=\operatorname{rk}_K(d(x,\cdot);R_a(S_i,Y)).✦ The target table 𝒯q\mathcal{T}_q of qq vanishes at (ω;x,y)(\omega;x,y) unless x∈Ru(Si,X)x\in R_u(S_i,X), y∈Ra(Si,Y)y\in R_a(S_i,Y) and, when qq is paired main, y∈Rt(Si,Y)y\in R_t(S_i,Y), and there 𝒯q(ω;x,y)=φ(d(x,y))gateθ(rk⁡(x))χ(ζT(x,y))σq(y)𝜚q(y),\mathcal{T}_q(\omega;x,y)=\varphi\bigl(d(x,y)\bigr)\,\mathrm{gate}_\theta\bigl(\operatorname{rk}(x)\bigr)\, \chi\bigl(\zeta\,T(x,y)\bigr)\,\sigma_q(y)\,\varrho_q(y),(8)✦ the first three factors forming the pre-incoming figure. For an echo the incoming gate σq(y)\sigma_q(y) is the shutoff of the incoming rank rk⁡clim(w(⋅,y);Ru(Si,X))\operatorname{rk}_{c_{\lim}}(w(\cdot,y);R_u(S_i,X))✦, where the support witness w(x,y)w(x,y) is the support trio evaluated at the same blob without the condition at level tt✦, and clim=128(1+32(128+4(J+1)))c_{\lim}=128\,(1+32(128+4(J+1))) is the incoming cap limit✦; for a main echo the damping 𝜚q(y)\varrho_q(y) is γ(πm(y))\gamma(\pi_m(y)) for the step count mm, which is k+1k+1 with pilot and k*k_* without.✦ Both factors are 11 in the other cases.

The target νe\nu_e of a vector request e=(i,u,k)e=(i,u,k), its pursued vector, is the same at every environment✦: the rewards WiW_i for a prize request, and for a detector request at round kk the test vector UkU_k of PiP_i.✦ With ℓ\ell the level of PiP_i and Gk=Ci+EkCiG_k=C_i+E_kC_i, the averaged score Uk(y)U_k(y) is the conditional average, over the channels s′s' retaining yy at level ℓ\ell, of the average over all channels ss of the rank score rk⁡J(mark⁡(⋅,y);Rℓ(Si,s))\operatorname{rk}_J(\operatorname{mark}(\cdot,y);R_\ell(S_i,s)).✦ The marked entry weight mark⁡(x,y)\operatorname{mark}(x,y) is the light ramp at 24ℓGk(x,y)2^{4\ell}G_k(x,y) times the throttled gate, the gate at δ\delta of the panel rank rk⁡K(24ℓGk(x,⋅);Rℓ(Si,s′))\operatorname{rk}_K(2^{4\ell}G_k(x,\cdot);R_\ell(S_i,s')) of row xx.✦

The Estimator

A tick Φ\Phi assigns to every row request qq a table family Φ(q)\Phi(q) and to every vector request ee a vertex family Φ(e)\Phi(e)✦, and a roll is a sequence of ticks.✦ Given a roll and a budget MM, the current tick at MM is the tick that assigns to every request active at MM its active table, for a row request, or its active vertex table, for a vector request, and assigns 00 to every other request.✦ The forecast ΦM\Phi_M is the current tick at MM given the roll of the forecasts Φ0,…,ΦM−1\Phi_0,\dots,\Phi_{M-1}, followed by empty ticks.✦

Within a block the estimator telescopes along lines. A line is a sequence Λ0,Λ1,…\Lambda_0,\Lambda_1,\dots of table families with an account matrix.✦ At budget MM the pick of a line Λ\Lambda at mm is the walk sample table of the successive difference Λm+1−Λm\Lambda_{m+1}-\Lambda_m, the table whose entry at (ω;x,y)(\omega;x,y) is the path sampling sum (1) of depth λ(M−m−1)\lambda(M-m-1) for the levels uu and aa and the nodes xx and yy of the row request being answered, with M−m−1M-m-1 the remaining slack.✦ The conditional mean table of the difference Λm+1−Λm\Lambda_{m+1}-\Lambda_m is the table whose entry at (x,y)(x,y) is the conditional average of the difference at (x,y)(x,y), and the sampling fluke is the difference of the pick and the conditional mean table. A flame is a finite set of rays, pairs of natural numbers, each carrying a line, together with a lamp matrix and a base matrix.✦ For a request and a budget MM, the additive schedule divides MM into ⌊log⁡2M⌋+1\lfloor\log_2M\rfloor+1 groups, and the prefix sum of a flame at a group is the sum, over the rays of the flame, of the picks of the ray’s line below the start of that group, together with the base matrix from the second group on.

The active vertex table of a vector request ee is the clamp to [0,1][0,1] of the diagonal of the prefix sum over all groups of its weave, a flame whose lines are built from the roll, taken on the axis of ee with its destination level replaced by 00, at the sources in Ru(Si,X)R_u(S_i,X), and 00 at the other nodes.✦ The active table of a row request qq is built as its target (8) is, with two changes: the blob of each source is the midpoint blob of a buffer run of the request’s compression spray, which compresses its starting flame and its companion flame, and for a main echo the damping 𝜚q(y)\varrho_q(y) gives way to γ\gamma of the running maximum, over the rounds below the step count, of the detector answers in ΦM−1\Phi_{M-1} at the environment with XX and YY exchanged.✦

Tonic Bounds and the Purse

A function ff is cc-Lipschitz when |f(y)−f(x)|≤c|y−x||f(y)-f(x)|\le c\,|y-x| for all reals xx and yy.✦ A real function ff is a bounded fragment with constant cc when c≥1c\ge 1, f≥0f\ge 0, its fourth root f1/4f^{1/4} is at most cc and cc-Lipschitz, and f(sat⁡c(x))=f(x)f(\operatorname{sat}_c(x))=f(x) for every xx, where sat⁡c=clip⁡[−c,c]\operatorname{sat}_c=\operatorname{clip}_{[-c,c]} is the symmetric saturation.✦ A trio (φ,ψ,χ)(\varphi,\psi,\chi) has test shape at threshold zz with constant CC when φ\varphi, ψ\psi and χ\chi are bounded fragments with constant CC, φ\varphi vanishes on (−∞,z/8](-\infty,z/8], and ψ\psi vanishes on [z/40,∞)[z/40,\infty) and equals 11 on (−∞,η(z)](-\infty,\eta(z)].✦

Tonic bounds for parameter constants are a real R≥1R\ge 1 such that the fourth roots of the boost, of γ\gamma and of the shutoff are RR-Lipschitz, the support trio of every kind has test shape at the kind threshold θ\theta with constant RR, and so does every main trio (φ,gateθ,χ)(\varphi,\mathrm{gate}_\theta,\chi) of a kind, with φ\varphi its piece at levels kk and i′i' for i′≤k+k*+10i'\le k+k_*+10 or the preparation ramp at θ\theta, and χ\chi the inverse clipped denominator or 11.✦ Tonic bounds RR have the size R3R^3, the natural size 4R94R^9✦, the bank b=4+2R3(w+1)b=4+2R^3(w+1)✦, the ticket bt=b22(k*+10)b_{\mathrm t}=b\,2^{2(k_*+10)}✦ and the clergy bc=Rk*btb_{\mathrm c}=Rk_*b_{\mathrm t}✦, where w=K+climw=K+c_{\lim} is the width.✦

A budget purse for tonic bounds is a triple of reals, a ceiling c1c_1, a slip c2c_2 and a toll c3c_3, with c1≥max⁡{R3,(w+1)R6,1+2k*/A},c2≥max⁡{bt,4R3(w+1)bt,bt+R3(w+1)bc},c3≥max⁡{20,8D02,2D0,4(k*+1),64c14c2,4ζR9bt,4R9bt,bt+4bc,8wR9bt+(w+1)2R12bt+4wR12bc}.\begin{aligned} c_1&\ge\max\{R^3,\ (w+1)R^6,\ 1+2k_*/A\},\\ c_2&\ge\max\{b_{\mathrm t},\ 4R^3(w+1)\,b_{\mathrm t},\ b_{\mathrm t}+R^3(w+1)\,b_{\mathrm c}\},\\ c_3&\ge\max\{20,\ 8D_0^2,\ 2D_0,\ 4(k_*+1),\ 64c_1^4c_2,\ 4\zeta R^9b_{\mathrm t},\ 4R^9b_{\mathrm t},\ b_{\mathrm t}+4b_{\mathrm c},\\ &\qquad\qquad 8wR^9b_{\mathrm t}+(w+1)^2R^{12}b_{\mathrm t}+4wR^{12}b_{\mathrm c}\}. \end{aligned}(9)✦ The purse meets the purse requirement at a gap gg when the following holds, with the purse prize Π\Pi, the purse venture Υ\Upsilon, the run charge 16R3(1+4(R+12))16R^3(1+4(R+12)), the spray price in the last factor of Π\Pi and the droplet count 72⋅106/δ72\cdot10^6/\delta: 2−gmax⁡{Π,Υ,24c32}≤b,Π=8c32(1+2K)⋅16R3(1+4(R+12))⋅(2⋅72⋅106δ+4096(k*+1)+386),Υ=Π+R3(1+2clim)(4R10Π+4bc).\begin{aligned} &2^{-g}\max\{\Pi,\ \Upsilon,\ 24c_3^2\}\le b,\\ &\Pi=8c_3^2\,(1+2K)\cdot16R^3\bigl(1+4(R+12)\bigr)\cdot\Bigl(2\cdot\frac{72\cdot10^6}{\delta}+4096(k_*+1)+386\Bigr),\\ &\Upsilon=\Pi+R^3(1+2c_{\lim})\bigl(4R^{10}\,\Pi+4b_{\mathrm c}\bigr). \end{aligned}(10)✦

The Claim

Theorem 1 (Error bounds for the actual estimators). Let nn be a prime and take a scene over nn that satisfies the scene hypotheses, with gap gg. Let RR be tonic bounds for its parameter constants, with width ww and bank bb, and let (c1,c2,c3)(c_1,c_2,c_3) be a budget purse for them that meets the purse requirement (10) at gg. Then for every budget MM the forecast ΦM\Phi_M is a trusted tick, a tick whose answers to ready requests satisfy the conditions stated next. For every row request q=(i,u,a,t,κ,μ)q=(i,u,a,t,\kappa,\mu) ready at budget MM, the table family ΦM(q)\Phi_M(q) is a tile: its entries are nonnegative with fourth roots at most R3R^3, the root cap, they are nonzero only at sources in Ru(Si,X)R_u(S_i,X) and destinations in Ra(Si,Y)R_a(S_i,Y), and each row has at most ww nonzero entries. For an echo each column of ΦM(q)\Phi_M(q) also has at most ww nonzero entries, a sparse shelf, and for a paired main request ΦM(q)\Phi_M(q) is pinned at level tt, unchanged by the terminal mask that clears the destinations outside Rt(Si,Y)R_t(S_i,Y). For every vector request e=(i,u,k)e=(i,u,k) ready at budget MM, every value of ΦM(e)\Phi_M(e) lies in [0,1][0,1].✦ Finally, in the norms of the axes of qq and ee and with the allowances (7) of their step keys, du,a(𝒯q,ΦM(q))≤bαM(q),∥νe−ΦM(e)∥u≤bαM(e).d_{u,a}\bigl(\mathcal{T}_q,\Phi_M(q)\bigr)\le b\,\alpha_M(q), \qquad \bigl\|\nu_e-\Phi_M(e)\bigr\|_u\le b\,\alpha_M(e).(11)✦

In the paper, in its own symbols, the result reads: for every allowed task with precision pp, the actual row outputs, pre-incoming scores and support witnesses H‾\bar H satisfy du,a(H‾,H)≤Cb2−pd_{u,a}(\bar H,H)\le C_b\,2^{-p}, the clipped vectors have the corresponding ordinary bound, and every allowed reward query satisfies 1N𝔼σ∑x(Xu(x)/u)|W‾ℓ(x)−Wℓ(x)|s≤Cbs2−sp\frac{1}{N}\,\mathbb{E}_\sigma\sum_x(X_u(x)/u)\,|\bar W_\ell(x)-W_\ell(x)|^s\le C_b^s\,2^{-sp} with s=8s=8, uniformly in the task parameters and the stage, with constants independent of the input and of the budget BB.

What Is Checked

The claim is stated over a scene over a prime nn with the scene hypotheses, tonic bounds for its parameter constants, a budget purse meeting the purse requirement at the gap, and the forecasts of the estimator, set against the target tables and pursued vectors in the norms of the table and vertex meters, with the error allowances of the step keys. The finite average 𝔼\mathbb{E} over a finite set is linear and monotone: for functions f1f_1, f2f_2 on the set and a real number ξ\xi, 𝔼(f1+f2)=𝔼f1+𝔼f2,𝔼(ξf1)=ξ𝔼f1,f1≤f2⇒𝔼f1≤𝔼f2.\mathbb{E}(f_1+f_2)=\mathbb{E}f_1+\mathbb{E}f_2,\qquad \mathbb{E}(\xi f_1)=\xi\,\mathbb{E}f_1,\qquad f_1\le f_2\ \Longrightarrow\ \mathbb{E}f_1\le\mathbb{E}f_2.(12)