OctoInformBeta

OpenAI preprint, September 2026 · Section 3. A polynomial approximation with controlled coefficients

Lemma 3: Asymptotic bounds and an explicit Chebyshev construction

Separating zero with controlled polynomial coefficients.

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

A polynomial filter for an integer count must distinguish zero from a prescribed range of positive values, while controlling the cost of its coefficients. For quantum circuit bounds, let NN denote the total number of qubits, including ancillas.

For a real polynomial p(X)=∑kckXkp(X)=\sum_k c_kX^k and a real weight RR, the weighted coefficient cost WR(p)W_R(p) is the real number given by (1), with the sum taken over the nonzero coefficients: WR(p)=∑k|ck|Rk.W_R(p)=\sum_k |c_k|R^k.(1)✦ For a real number tt, the natural ceiling ⌈t⌉+\lceil t\rceil_+ is the least nonnegative integer at least tt.

The Finite Construction

The integer root polynomial qr∈ℝ[X]q_r\in\mathbb R[X], for a nonnegative integer rr, is the product in (2): qr(X)=∏j=1r(1−Xj).q_r(X)=\prod_{j=1}^{r}\left(1-\frac{X}{j}\right).(2)✦ The affine polynomial in (3) defines the interval rescaling polynomial sr,m∈ℝ[X]s_{r,m}\in\mathbb R[X] for real parameters rr and mm. sr,m(X)=m+rm−r−2Xm−r.s_{r,m}(X)=\frac{m+r}{m-r}-\frac{2X}{m-r}.(3)✦

Write Tk∈ℝ[X]T_k\in\mathbb R[X] for the Chebyshev polynomial of the first kind of degree kk, where kk is a nonnegative integer. The Chebyshev approximant Pr,m,k∈ℝ[X]P_{r,m,k}\in\mathbb R[X] for nonnegative integers r,m,kr,m,k is the real polynomial defined from (2) and (3) by (4). Pr,m,k(X)=[Tk(m+rm−r)]−1qr(X)Tk(sr,m(X)).P_{r,m,k}(X)= \left[T_k\!\left(\frac{m+r}{m-r}\right)\right]^{-1} q_r(X)\,T_k\!\left(s_{r,m}(X)\right).(4)✦

The Claim

Theorem 1 (Uniform polynomial approximation). Let a,b,ua,b,u be real numbers with 0<a<b0<a<b and (a+b)/2<u(a+b)/2<u. For all sufficiently large natural NN, there is a real polynomial pp satisfying (5): deg⁡p≤Nu,WN(p)≤exp⁡(Nu),p(0)=1,|p(x)|≤exp⁡(−Na)for every integer 1≤x≤⌈Nb⌉+.\begin{gathered} \deg p\le N^u,\qquad W_N(p)\le \exp(N^u),\qquad p(0)=1,\\ |p(x)|\le \exp(-N^a) \quad\text{for every integer }1\le x\le\lceil N^b\rceil_+. \end{gathered}(5)✦

Theorem 2 (Approximating polynomial bounds). Let r,m,kr,m,k be nonnegative integers and let R≥0R\ge0 be real. Suppose 1≤r1\le r, 2r≤m2r\le m, and 4rlog⁡m≤kr/m4r\log m\le k\sqrt{r/m}. Then the Chebyshev approximant satisfies (6): deg⁡Pr,m,k≤r+k,WR(Pr,m,k)≤(1+R)r(7+4R)k,Pr,m,k(0)=1,|Pr,m,k(x)|≤2exp⁡(−3rlog⁡m)for every integer 1≤x≤m.\begin{gathered} \deg P_{r,m,k}\le r+k,\qquad W_R(P_{r,m,k})\le (1+R)^r(7+4R)^k,\\ P_{r,m,k}(0)=1,\\ |P_{r,m,k}(x)|\le 2\exp(-3r\log m) \quad\text{for every integer }1\le x\le m. \end{gathered}(6)✦

What Is Checked

The asymptotic assertion concerns real polynomials with the cost (1), real exponents and natural qubit counts; the finite assertion concerns the Chebyshev approximants (4), with natural parameters and nonnegative real weight.

The integer root polynomial qrq_r equals one at zero and vanishes at the first rr positive integers.