LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge 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.

Bernstein approximation to the square root

Statement

For each integer $d \geq 1$ , the degree- $d$ Bernstein polynomial $B_{d} (x) = \sum_{j = 0}^{d} \sqrt{j / d} (\binom{d}{j}) x^{j} (1 - x)^{d - j}$ satisfies $\sup_{x \in [0, 1]} ∣ B_{d} (x) - \sqrt{x} ∣ \leq (4 d)^{- 1 / 4}$ . Consequently degree $d \geq 1 / (4 η^{4})$ suffices for uniform error at most $η > 0$ .

Facts & Assumptions

Given: An integer $d \geq 1$ and $x \in [0, 1]$ .

[F1]

The binomial theorem over an arbitrary commutative ring: $\sum_{j} (\binom{d}{j}) x^{j} (1 - x)^{d - j} = 1$ .

[F2]

The binomial coefficients count subsets (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ). For $1 \leq j \leq d$ , counting pairs $(S, a)$ with $∣ S ∣ = j$ and $a \in S$ gives $j (\binom{d}{j}) = d (\binom{d - 1}{j - 1})$ . For $d \geq 2$ and $2 \leq j \leq d$ , counting triples $(S, a, b)$ with $∣ S ∣ = j$ and an ordered pair of distinct marked elements gives $j (j - 1) (\binom{d}{j}) = d (d - 1) (\binom{d - 2}{j - 2})$ .

[F3]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: finite weighted sums satisfy Cauchy–Schwarz.

Proof

1.1givenF1F2algebra

Regard the nonnegative weights $p_{j} = (\binom{d}{j}) x^{j} (1 - x)^{d - j}$ as a finite distribution. [F1] gives $\sum_{j} p_{j} = 1$ . Reindexing the first count in [F2] gives $E K = \sum_{j} j p_{j} = d x$ . For $d \geq 2$ , reindexing the second count gives $E [K (K - 1)] = \sum_{j} j (j - 1) p_{j} = d (d - 1) x^{2}$ ; for $d = 1$ this expectation is $0 = d (d - 1) x^{2}$ directly. Since $K^{2} = K (K - 1) + K$ , it follows that $E (K / d - x)^{2} = x (1 - x) / d \leq 1 / (4 d)$ .

2.1F3step 1.1algebra∎

Since $∣ \sqrt{u} - \sqrt{v} ∣ \leq \sqrt{∣ u - v ∣}$ for $u, v \geq 0$ , [F3] gives $E \sqrt{∣ K / d - x ∣} \leq \sqrt{E ∣ K / d - x ∣}$ and $E ∣ K / d - x ∣ \leq \sqrt{E (K / d - x)^{2}}$ . Therefore $∣ B_{d} (x) - \sqrt{x} ∣ \leq (E (K / d - x)^{2})^{1 / 4} \leq (4 d)^{- 1 / 4} .$ The bound is uniform in $x$ , and solving $(4 d)^{- 1 / 4} \leq η$ gives the stated degree choice.

Depends on

Used by

Uniform finite-arity local-energy measurement synthesis Lemma

Dependency tree · two levels

27 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

Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (standard reference, not scraped)