TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generated

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.

Certified phase output encloses the exact unit-circle value

Statement

Whenever Certified dyadic enclosures for unit-circle phases returns certified(\widehat w,\epsilon) on rational input $q$ , its output satisfies $∣ \hat{w} - e^{π i q} ∣ \leq ϵ \leq τ$ .

Facts & Assumptions

Given: Rational $q$ , target $0 < τ \leq 1 / 4$ , finite precision and evaluation budgets, and a successful output certified(\widehat w,\epsilon).

[F1]

On a finite return, the real interval $C$ contains $\cos (π q)$ and $S$ contains $\sin (π q)$ , and Euler's identity identifies their pair with $e^{π i q}$ ; the interval and Fourier definitions use the same $π$ (Certified real elementary-function evaluations enclose their ranges, Real intervals, complex rectangles and ball enclosures, $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ , The interval evaluator's arctangent definition uses the canonical Fourier pi).

[F2]

The returned lower endpoints are the lower endpoints of $C, S$ , and $ϵ$ is an upward-rounded dyadic at least $(c_{+} - c_{-}) + (s_{+} - s_{-})$ ; directed interval arithmetic encloses these exact widths (Certified dyadic enclosures for unit-circle phases, Outward-rounded operations are inclusion-isotone and enclose DAG evaluations).

[F3]

For real $a, b$ , $∣ a + i b ∣ \leq ∣ a ∣ + ∣ b ∣$ by the complex modulus triangle inequality (Conjugation is an involutive real-field automorphism, $z \overline{z} = ∣ z ∣^{2}$ , and modulus is definite, multiplicative, and subadditive).

Proof

1.1givenF1F2

By [F1], the real coordinate of $w = e^{π i q}$ lies in $[c_{-}, c_{+}]$ and its imaginary coordinate lies in $[s_{-}, s_{+}]$ . Since $\hat{w} = c_{-} + i s_{-}$ by [F2], the coordinate differences satisfy $∣ ℜ (w - \hat{w}) ∣ \leq c_{+} - c_{-}$ and $∣ ℑ (w - \hat{w}) ∣ \leq s_{+} - s_{-}$ .

2.1step 1.1F2F3algebra∎

Applying [F3] to these two coordinate differences gives $∣ w - \hat{w} ∣ \leq (c_{+} - c_{-}) + (s_{+} - s_{-}) \leq ϵ$ . The algorithm returns only when $ϵ \leq τ$ , proving the claim.

Depends on

Used by

Dependency tree · two levels

35 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

Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., Chapter 24, pp. 452–454 (standard reference, not scraped)
C. Sidney Burrus, Fast Fourier Transforms, Chapter 11 §11.7 (standard reference, not scraped)