Numerical Cauchy products on a root grid with explicit accuracy scale

If $n=0$, return zero; if $M=1$, sum the $n$ nonzero-denominator fractions directly, using $O(n+1)$ operations and space, and use the rounding argument below. Otherwise construct a binary tree on consecutive root indices. Its root covers all roots, with center $0$ and radius $1$. At depth $\mathrm{\ell }\ge 1$, a node contains $m=M\mathrm{/}{2}^{\mathrm{\ell }}$ consecutive roots starting at index $b$; its center is $c=\exp (2\pi i(b+(m-1)\mathrm{/}2)\mathrm{/}M)$ and its covering radius is $R=2\sin (\pi (m-1)\mathrm{/}(2M))\le \pi 2^{-\mathrm{\ell }}$. These disks contain their roots because the largest angular distance from the arc midpoint is $\pi (m-1)\mathrm{/}M$. Singleton leaves have radius zero. For each pole start at the root: at a nonleaf stop at a far node if $\mathrm{\mid }c-{\mu }_j\mathrm{\mid }\ge 3R\mathrm{/}2$, or descend into both children if $\mathrm{\mid }c-{\mu }_j\mathrm{\mid }\le 2R$. In the overlap either choice is valid. A singleton is evaluated directly if reached. Certified interval tests terminate: for $R>0$, the two thresholds have a positive gap $R\mathrm{/}2$, so enclosures of width less than $R\mathrm{/}4$ distinguish at least one admissible choice, even when one threshold is an equality. Squared-distance comparisons implement the same test with a positive gap and finitely accurate supplied coordinates.

At a fixed depth put $J=2^{\mathrm{\ell }}$. The $J$ arc centers are equally spaced on the unit circle and have mutual distance at least $2\sin (\pi \mathrm{/}J)\ge 4\mathrm{/}J$ for $J\ge 2$, by concavity of sine on $[0,\pi \mathrm{/}2]$. Every near center lies within $2\pi \mathrm{/}J$ of its pole. Disks of radius $2\mathrm{/}J$ about these centers have disjoint interiors and lie in the disk of radius $(2\pi +2)\mathrm{/}J$ about that pole. Comparing their areas bounds the number of near centers by $(\pi +1{)}^2<18$. Thus there are fewer than $36$ candidate children per pole at the next depth, including all far stops. The root contributes one candidate. The $q+1$ depths therefore contain $O(n\log (2+M))$ pole/node pairs. Each root follows exactly one stopped or singleton node for each pole, so these pairs partition all pole/root interactions without duplication. Repeated poles obey the same argument separately.

For a stopped pair put $t=-(z-c)\mathrm{/}(c-{\mu }_j)$. Its targets satisfy $\mathrm{\mid }t\mathrm{\mid }\le 2\mathrm{/}3$. The finite geometric identity gives $1\mathrm{/}(z-{\mu }_j)={\sum }_{h=0}^{p-1}(-(z-c){)}^h\mathrm{/}(c-{\mu }_j{)}^{h+1}+t^p\mathrm{/}(z-{\mu }_j)$. Therefore the error in this pair is at most $(2\mathrm{/}3{)}^p\mathrm{\mid }{a}_j\mathrm{\mid }\mathrm{/}\mathrm{\mid }z-{\mu }_j\mathrm{\mid }$. Summing the partition from step 2.1 gives error at each root at most $(2\mathrm{/}3{)}^p{\sum }_j\mathrm{\mid }{a}_j\mathrm{\mid }\mathrm{/}\mathrm{\mid }z-{\mu }_j\mathrm{\mid }\le (2\mathrm{/}3{)}^{p}A\mathrm{/}d$. Choose $p\ge 1$ with $(2\mathrm{/}3{)}^p\le \eta \mathrm{/}2$; then $p=O(\log (1\mathrm{/}\eta ))$ and the truncation error is at most $\eta s\mathrm{/}2$. Direct singleton interactions have zero truncation error.

Process depths successively, keeping the bounded near list per pole for the next depth and the bounded far list for the current depth. At a fixed depth, store $v_{j,I}=1\mathrm{/}(c_I-{\mu }_j)$ and initially $w_{j,I}=a_j{v}_{j,I}$ for each far pair. Initialize one target power $t_k=1$ per root. For degrees $h=0,\dots ,p-1$, clear one coefficient $g_I$ per current-depth node, add every current $w_{j,I}$ to its node's $g_I$, and add $g_{I(k)}{t}_k$ to each target accumulator, where $I(k)$ is its unique ancestor at this depth. Update $w_{j,I}\leftarrow w_{j,I}{v}_{j,I}$ and $t_k\leftarrow -(z_k-c_{I(k)})t_k$. A node without stopped pairs has coefficient zero. Discard the depth's arrays before advancing; at leaves add all direct pairs. The sums are exactly the polynomials in step 3.1. Each depth/degree uses $O(n+M)$ operations and words by step 2.1; the near/far lists, current coefficients, powers and output arrays occupy $O(n+M)$ words. No array of $p$ moments and no list across all depths is stored. The binary root tree has fewer than $2M$ nodes, so its supplied constants and routing data also occupy $O(M)$ words. Routing costs $O(n\log (2+M)+M)$ operations; fixed-width certified interval arithmetic for each overlapping test has constant scalar cost at its supplied sufficient precision. Total cost is $O((n+M)\log (2+M)p)$, with $O(n+M)$ words independently of $p$.

Fix the certified routing and the exact truncated rational circuit just constructed. Nonleaf far denominators are nonzero by their distance test; leaf denominators are nonzero by [A1]. Its finite exact intermediates and denominators admit the stated $V,D$. Suppose all already formed operands have error at most $e\le \min (1,D\mathrm{/}2)$. Addition or subtraction increases error by at most $2e+u$. Multiplication increases it by at most $(2V+1)e+u$. For division, writing exact operands as $x,y$, approximate operands as $x^{\mathrm{\prime }},y^{\mathrm{\prime }}$, and $\mathrm{\mid }y\mathrm{\mid }\ge D$, gives $\mathrm{\mid }{y}^{\mathrm{\prime }}\mathrm{\mid }\ge D\mathrm{/}2$ and $\mathrm{\mid }{x}^{\mathrm{\prime }}\mathrm{/}{y}^{\mathrm{\prime }}-x\mathrm{/}y\mathrm{\mid }\le 2e\mathrm{/}D+2Ve\mathrm{/}{D}^2$; the final rounding adds $u$. Conjugation and changing signs do not increase error. All these bounds are at most $Ke+u$ for the stated $K\ge 2$. Input constant error is at most $u$. Induction over the $T$ gates bounds every operand error by $2u{K}^{T+1}$: more precisely after $t$ gates the maximum error is at most $u(1+K+\cdots +K^t)\le 2u{K}^t$. The stated choice of $u$ keeps this within $\min (1,D\mathrm{/}2,\tau )$, so every division remains defined and the output rounding error is at most $\tau$. Root and pole approximation errors are included as input errors in this recurrence. The certified routing uses exact admissible inequalities, so rounding cannot route a pair outside its valid geometric estimate; the positive overlapping gap in step 1.1 permits finite enclosures, whose sufficient precision can be selected together with this $u$.

Combine the truncation and rounding errors to obtain ${\max }_k\mathrm{\mid }{\widehat{y}}_k-y_k\mathrm{\mid }\le \eta s$. For absolute error $\delta$ apply the construction with $\eta =\delta \mathrm{/}s\le 1\mathrm{/}2$, obtaining $p=O(\log (s\mathrm{/}\delta ))$. These substitutions do not change the memory argument. The elementary example $y=1\mathrm{/}(z-\mu )$ changes by $h\mathrm{/}((z-\mu )(z-\mu -h))$ when $\mu$ changes to $\mu +h$, showing why separation-dependent precision cannot be omitted from an absolute-error statement. The count in step 4.1 measures scalar words and operations at the required precision and supplies no bound on their bit lengths or bit cost.