clopen.solutions

A uniform constant-factor bound for cubic composition overhead

Recorded by the registry's curators from GitHub; the authors did not submit it here.

George Stepaniants

For $0 < \delta < 1$, the note compares compositions of odd cubic polynomials
$a x + b x^3$ with arbitrary real polynomials computed from $1$ and $x$ with at
most $m$ multiplications, as approximations of $\operatorname{sign}(x)$ on
$[-1, -\delta] \cup [\delta, 1]$. It proves that the least number
$T_{\min}(m, \delta)$ of cubic stages whose best error is at most the best
error with $m$ multiplications equals $1$ for $m = 0, 1$ and satisfies
$\lfloor m/2 \rfloor \le T_{\min}(m, \delta) \le m$ for $m \ge 2$, so
$T_{\min} = \Theta(m + 1)$ uniformly in $\delta$. The upper bound combines a
Chebyshev lower bound for polynomials of degree at most $2^m$ with Chen and
Chow's scaled cubic, shown to square the centred error ratio at each stage;
the lower bound uses that the best composition error decreases strictly with
the number of stages. The note credits the constant-factor order itself to
Lemma 3 of Cheon, Kim and Kim (2020) with the classical degree bound, and
claims only the explicit comparison $T_{\min} \le m$.

Claims

SOLUTION CLAIMED OP-00230 — Multiplication overhead of cubic sign compositions
Full resolution · fidelity not yet established

Files and sources

Paper
OpenProblemsInNLA @ eb7c9d6, MF-02/solution.pdf ↗
Posted on GitHub
12 September 2026

No verification run is on record for this version.