LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite-grid Markov derivative inequality

Statement

Let $N \geq 1$ and let $q$ be a real polynomial with no supported monomial of degree greater than $d \in N_{0}$ . Put $h = \max_{[0, N]} q - \min_{[0, N]} q$ and $D = \max_{[0, N]} ∣ q^{'} ∣$ . If $0 \leq q (k) \leq 1$ for every integer $k = 0, \dots, N$ , then $D \leq \frac{d^{2}}{N} h .$

Facts & Assumptions

Given: An integer $N \geq 1$ , a real polynomial $q$ of degree at most $d$ , and the bounds $0 \leq q (k) \leq 1$ on the integer grid.

[F1]

Continuous Markov derivative bound on an interval: for a polynomial $p$ of degree at most $d$ on $[- 1, 1]$ , its maximum derivative magnitude is at most $d^{2} / 2$ times its range height.

[F2]

Bounded integer-grid values control excursions by the derivative: under the stated integer-grid bounds, $D \geq \max {0, h - 1}$ ; in particular $h \leq 1 + D$ .

[F3]

For a natural $n \geq 1$ the function $x \mapsto x^{n}$ is differentiable everywhere with derivative $ι (n) x^{n - 1}$ ; for $n = 0$ it is the constant $1$ , with derivative $0$ ; for a natural $n \geq 1$ the function $x \mapsto x^{- n}$ is differentiable at every $x \neq 0$ with derivative $- ι (n) x^{- n - 1}$ ; consequently every polynomial function is differentiable at every real, with the derivative computed term by term, The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ , Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function, and Extreme value theorem: a continuous real function on a nonempty compact subset of $R$ attains a greatest and a least value: polynomial functions are differentiable with polynomial derivative, compositions obey the chain rule, and continuous functions on $[0, N]$ attain their extrema.

Proof

1.1givenF1F3algebra

The polynomial functions $q, q^{'}$ are continuous and attain extrema on $[0, N]$ by [F3], so $h, D$ are defined. Put $p (u) : = q (N (u + 1) / 2)$ for $u \in [- 1, 1]$ . It has no supported monomial above degree $d$ and the same range height $h$ as $q$ on $[0, N]$ . By the chain rule in [F3], $p^{'} (u) = (N / 2) q^{'} (N (u + 1) / 2)$ , hence $\max ∣ p^{'} ∣ = (N / 2) D$ . Applying [F1] gives $(N / 2) D \leq (d^{2} / 2) h$ .

2.1step 1.1F2algebra∎

Since $N > 0$ , multiplying the inequality of step 1.1 by $2 / N$ yields $D \leq d^{2} h / N$ . The grid-return estimate [F2] is compatible with this bound and gives the additional consequence $h \leq 1 + D$ that will be used in the OR lower-bound proof.

Depends on

Used by

OR has a square-root approximate-degree lower bound and corresponding query lower bounds Theorem

Dependency tree · two levels

57 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

N. L. Carothers, A Short Course on Approximation Theory (1998), Chapter 5, Theorem 5.22 (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (2025), §21.6 (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes (arXiv:1907.09415), §11.2 (standard reference, not scraped)