Gapped pseudoinverse polynomial degree and error

Put ${\kappa }_0=2\mathrm{/}\delta$, $u=e\mathrm{/}(100\delta )$ and $f_b(x)=(1-(1-x^2{)}^b)\mathrm{/}x$, with its polynomial value at zero. For $\mathrm{\mid }x\mathrm{\mid }\ge 1\mathrm{/}{\kappa }_0$, $\mathrm{\mid }{f}_b(x)-1\mathrm{/}x\mathrm{\mid }\le {\kappa }_0\exp (-b\mathrm{/}{\kappa }_0^2)\le u$. To identify its Chebyshev coefficients, expand ${\sin }^{2b}\theta =2^{-2b}\left(\genfrac{}{}{0px}{}{2b}{b}\right)+2^{1-2b}{\sum }_{r=1}^b(-1{)}^r\left(\genfrac{}{}{0px}{}{2b}{b+r}\right)\cos (2r\theta )$, obtained by expanding $(e^{i\theta }-e^{-i\theta }{)}^{2b}$. Multiplying ${\sum }_{j=0}^{b-1}{a}_j{T}_{2j+1}(x)$ by $x$ and using $2x{T}_n=T_{n+1}+T_{n-1}$ telescopes the binomial tails to $1-(1-x^2{)}^b$. This proves the stated coefficient formula.

Write $H(z)=\mathrm{erf}(\beta z)$, $h=g\mathrm{/}2$, $q=h+\sqrt{1+h^2}$ and $L=\ln (16\mathrm{/}v)$. The defining erf series is entire by the ratio test, and [F3] gives $\mathrm{\mid }H(x)\mathrm{\mid }\le 1$ on the real line. On the ellipse of parameter $q$, $\mathrm{\mid }\mathrm{Im}z\mathrm{\mid }\le h$. Integrating vertically from the real axis gives $\mathrm{\mid }H(z)\mathrm{\mid }\le 1+2\beta h\exp ({\beta }^2{h}^2)=C$. The Laurent expansion of $H((w+w^{-1})\mathrm{/}2)$ and [F4] give Chebyshev coefficients bounded by $2C{q}^{-l}$. Put $N=n+1$ and ${\theta }_j=(j+1\mathrm{/}2)\pi \mathrm{/}N$. At these nodes, $\cos ((l+2N){\theta }_j)=-\cos (l{\theta }_j)$, $\cos ((2N-l){\theta }_j)=-\cos (l{\theta }_j)$, and $\cos (N{\theta }_j)=0$. Repeated reduction therefore interpolates every unresolved $T_l$ as $\pm T_r$ for $0\le r<N$, or as zero; each folded mode has sup norm at most one. Subtracting the original mode costs at most twice its coefficient, so summing the omitted modes bounds interpolation error by $4C{q}^{-n}\mathrm{/}(q-1)$, at most $v\mathrm{/}32$ under OP1A's stopping condition. Odd symmetrization cannot increase this error because $H$ is odd. The declared aggregate evaluation and rounding errors contribute at most $v\mathrm{/}32$ more, so the pre-rescaled interpolant differs uniformly from $H$ by at most $v\mathrm{/}16$. After division by $1+v\mathrm{/}4$, its output $S$ satisfies $\mathrm{\mid }S\mathrm{\mid }<1$, and differs from $H\mathrm{/}(1+v\mathrm{/}4)$ by at most $v\mathrm{/}16$. The Gaussian tail inequality $1-\mathrm{erf}(z)\le e^{-z^2}$ for $z\ge 0$ follows, for $0\le z\le 1\mathrm{/}\sqrt{\pi }$, by differentiation of $e^{-z^2}-\mathrm{erfc}(z)$, and thereafter by the integral bound $\mathrm{erfc}(z)\le e^{-z^2}\mathrm{/}(\sqrt{\pi }z)$. Hence $\mathrm{\mid }S(x)-\mathrm{sign}x\mathrm{\mid }<v\mathrm{/}2$ when $\mathrm{\mid }x\mathrm{\mid }\ge g$.

For completeness, if $X$ is a sum of $2b$ independent fair bits, $\mathbb{E}\exp (s(X-b))=\cosh (s\mathrm{/}2{)}^{2b}\le \exp (b{s}^2\mathrm{/}4)$: the last inequality follows by integrating $\tanh z\le z$ for $z\ge 0$. Markov's inequality and minimization at $s=2r\mathrm{/}b$ yield $\mathrm{Pr}[X-b\ge r]\le \exp (-r^2\mathrm{/}b)$. Consequently the omitted coefficient sum beyond $J$ is at most $4b\exp (-J^2\mathrm{/}b)\le u$, and $\mathrm{\mid }{T}_n(x)\mathrm{\mid }\le 1$ on $[-1,1]$ proves uniform truncation error at most $u$. Thus $P=(\delta \mathrm{/}2)g$ differs from $\delta \mathrm{/}(2x)$ by at most $\delta u=e\mathrm{/}100$ on $\mathrm{\mid }x\mathrm{\mid }\ge \delta \mathrm{/}2$, and $\mathrm{\mid }P\mathrm{\mid }\le 2\delta (J+1)<P_{\max }$ globally.

For $t=3\delta \mathrm{/}4$, $a=1+t$, monotonicity of $H$ gives $0\le C_{\mathrm{c}\mathrm{u}\mathrm{t}}(x)\le 1+v\mathrm{/}16$ on $[-1,1]$: nonnegativity uses $\mathrm{\mid }S\mathrm{\mid }\le 1$, and the upper bound uses $x-t<x+t$ in step 1.2. If $\mathrm{\mid }x\mathrm{\mid }\le \delta \mathrm{/}2$, the two shifted arguments have opposite signs and magnitude at least $g$, so $C_{\mathrm{c}\mathrm{u}\mathrm{t}}(x)\le v\mathrm{/}2$. If $\mathrm{\mid }x\mathrm{\mid }\ge \delta$, their signs agree and $\mathrm{\mid }{C}_{\mathrm{c}\mathrm{u}\mathrm{t}}(x)-1\mathrm{\mid }\le v\mathrm{/}2$. Therefore inside $[-\delta \mathrm{/}2,\delta \mathrm{/}2]$, $\mathrm{\mid }P{C}_{\mathrm{c}\mathrm{u}\mathrm{t}}\mathrm{\mid }\le P_{\max }v\mathrm{/}2\le e\mathrm{/}2000$; outside it, $\mathrm{\mid }P{C}_{\mathrm{c}\mathrm{u}\mathrm{t}}\mathrm{\mid }\le (1+e\mathrm{/}100)(1+v\mathrm{/}16)$. Division by $1+e\mathrm{/}10$ gives a strict global bound below $1-e\mathrm{/}20$. The total coefficient error $e\mathrm{/}1000$ preserves a strict range margin. On $[\delta ,1]$, the unrounded reciprocal error after division is at most $e\mathrm{/}100+P_{\max }v\mathrm{/}2+e\mathrm{/}20<e\mathrm{/}8$; rounding retains error below $e\mathrm{/}4$. Both reciprocal certificate polynomials are therefore strictly positive, by at least $3e\delta \mathrm{/}4$. Parity-preserving coefficient rounding leaves $p$ odd, hence $p(0)=0$.

All generation loops terminate. The binomial and Chebyshev sums are finite; $q>1$ makes the interpolation tail test terminate; and the explicit entire-function Taylor remainder tends to zero by the ratio test. Certified arithmetic refines positive strict inequalities finitely. For any fixed certificate polynomial $r$ of degree $D$ and a cell $[a,a+w]$, its Bernstein coefficient is $r(a)+{\sum }_{k=1}^j{r}^{(k)}(a)w^k\left(\genfrac{}{}{0px}{}{j}{k}\right)\mathrm{/}(k!\left(\genfrac{}{}{0px}{}{D}{k}\right))$. On the compact interval, the absolute difference from $r(a)$ tends uniformly to zero as $w\to 0$. Thus the positive margin in step 3.1 guarantees a finite dyadic level with every coefficient positive. The exact critical-point test succeeds by the strict global margin, and no actual failed-certificate regeneration is needed at adequate precision. This proves deterministic termination in the uncapped mode; a declared finite cap retains its timeout branch.

Since $e\le \delta$, $b=O({\delta }^{-2}\ln (1\mathrm{/}e))$, $J=O({\delta }^{-1}\ln (1\mathrm{/}e))$, and $\ln P_{\max }=O(\ln (1\mathrm{/}e))$. Also $g=\mathrm{\Theta }(\delta )$, $\ln q=\mathrm{\Theta }(g)$, $\ln C=O(\ln (1\mathrm{/}v))$ and $\ln (1\mathrm{/}v)=O(\ln (1\mathrm{/}e))$; therefore the least interpolation degree is $O({\delta }^{-1}\ln (1\mathrm{/}e))$. Multiplication adds degrees and rounding does not increase them, proving the stated degree bound. This does not assign a bit-time or gate bound to the coefficient generation or Bernstein refinement. On each supported singular vector, apply [F2] to this odd polynomial; the finite SVD then turns the uniform scalar error into operator error at most $e$. Finally ${\bar{A}}^{+}=\alpha A^{+}$ gives $(\delta \mathrm{/}2){\bar{A}}^{+}=(\gamma \mathrm{/}2)A^{+}$.

It remains to link the phase list emitted by the QA23 peeling procedure to the exact completed pair. At each nonconstant peel, its unit scalar ${\omega }_n$ is chosen with ${\omega }_n^2=a_{\mathrm{\ell }}\mathrm{/}{b}_{\mathrm{\ell }-1}$; the explicit square-root formula and coefficient checks give this identity exactly. The simultaneous updates in that procedure are the coefficients of right multiplication of the current source-convention matrix by $Z(-{\psi }_n)W_S^{\ast }$. Therefore the saved peel is reversed by multiplication by $W_{S}Z({\psi }_n)$. At the terminal constant pair, the stored base phase gives its exact diagonal matrix; each degree-padding block is the exact identity. Induction over the finite peel list, followed by reversing its stored order, reconstructs the original source-convention matrix. The stated convention conversion then gives the exact reflected QSP product with upper-left entry $p_0+iB$ and the other three entries of the returned completed pair. Thus the coefficientwise product check in [F1] passes for every uncapped promised construction. It uses finitely many coefficient-array operations, all charged to the phase-generation/certificate arithmetic coordinate; exact arithmetic failures still return PHASE_PRODUCT_ERROR before execution. Numerical angle and compiler certificates concern later implementations and are not part of this exact identity.