Finite-budget weighted rational Remez exchange with defect status

Inputs. A nondegenerate interval $I=[a,b]$, degrees $m,n\ge 0$, continuous real target $f$, strictly positive continuous weight $w$, a finite exchange integer budget $B\in {\mathbb{N}}_0$, an initial reference $X=(x_0,\dots ,x_{m+n+1})$ satisfying $a\le x_0<\cdots <x_{m+n+1}\le b$, an exact rational alternation-solver procedure, and an exact weighted-extrema oracle.

The alternation solver is an explicit input procedure. On a reference $X=(x_0,\dots ,x_{m+n+1})$, it solves the nonlinear equations $w(x_i)(f(x_i)-p(x_i)\mathrm{/}q(x_i))=(-1{)}^i\lambda$ with $p,q$ coprime, $\mathrm{deg}p\le m$, $\mathrm{deg}q\le n$, $q>0$ on $I$, and $\mathrm{\parallel }q{\mathrm{\parallel }}_{\mathrm{c}\mathrm{o}\mathrm{e}\mathrm{f},2}=1$. It reports one of: a unique candidate with defect $d=0$ and its solved level $\lambda$; an exact defective candidate with its computed $d>0$ and solved level $\lambda$; singular or nonunique system; no normal solution; or inconclusive. The procedure does not assume that this nonlinear solve always succeeds.

The weighted-extrema oracle for a returned candidate $r=p\mathrm{/}q$ reports one of:

• alternation$(E,Y)$ only when $E=\mathrm{\parallel }w(f-r){\mathrm{\parallel }}_{\mathrm{\infty },I}$ and $Y$ consists of $N_{m,n}(r)+2$ ordered distinct points in $I$ with weighted residuals $\sigma (-1{)}^{i}E$;
• maximum$(E,x)$ only when $x\in I$, $E=\mathrm{\parallel }w(f-r){\mathrm{\parallel }}_{\mathrm{\infty },I}$ and $\mathrm{\mid }w(x)(f(x)-r(x))\mathrm{\mid }=E$; or
• inconclusive.

Procedure. For $k=0,\dots ,B$, call the alternation solver on the current reference. Return its singular, no-normal-solution, or inconclusive status unchanged. If it returns a defective candidate, return defective$(d,N_{m,n}(r))$ immediately; do not apply the normal $m+n+2$-point count. For a normal candidate $(r,\lambda )$, query the weighted-extrema oracle. If it returns inconclusive, return oracle-inconclusive. A response alternation$(0,Y)$ or maximum$(0,x)$ returns exact$(r)$, since either certifies zero weighted error. An alternation response with $E>0$ returns certified$(r,E,Y)$, with optimality supplied by Weighted rational minimizers satisfy the defect-sensitive alternation criterion. For maximum$(E,x)$ with $E=\mathrm{\mid }\lambda \mathrm{\mid }$, the current reference itself is an exact global alternation certificate, so return certified$(r,E,X)$. If $\lambda =0<E$, return zero-level-no-exchange. If $k=B$, return budget-exhausted before attempting an exchange. Otherwise $E>\mathrm{\mid }\lambda \mathrm{\mid }$; exchange the returned maximum point $x$ for the smallest reference node $x_i$ whose expected sign $\mathrm{sgn}(\lambda )(-1{)}^i$ matches the sign of $w(x)(f(x)-r(x))$ and for which replacing $x_i$ by $x$ preserves strict ordering. If no such index exists, return no-valid-exchange. After an exchange, continue to the next iteration.

Outputs. The procedure returns an exact minimax certificate, an exact zero-error candidate, or an explicit defect, singularity, no-solution, oracle, exchange, or budget status. It claims no existence of a successful nonlinear solve and no iterative convergence.