LemmaStatement: 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.

A computed unitary radix-two butterfly has error at most (10u + εtw) times its input norm

Statement

Let $u \leq 1 / 16$ , let $∣ w ∣ = 1$ , and let $∣ \hat{w} - w ∣ \leq ϵ \leq 1 / 4$ . For $a, b \in C$ , perform the successful butterfly of Computed unitary radix-two FFT with certified twiddle phases using $\hat{w}$ . If each exact nonzero real intermediate is normal and every operation succeeds under the operationwise model, then its computed pair $({\hat{y}}_{+}, {\hat{y}}_{-})$ satisfies

{∥ ({\hat{y}}_{+}, {\hat{y}}_{-}) - 2^{- 1 / 2} (a + w b, a - w b) ∥}_{2} \leq (10 u + ϵ) {∥ (a, b) ∥}_{2} .

Facts & Assumptions

Given: $a, b, w, \hat{w}, u, ϵ$ with the stated bounds, and a successful rounded butterfly.

[F5]

For a pair $(z_{1}, z_{2}) \in C^{2}$ , $∥ (z_{1}, z_{2}) ∥_{2} = (∣ z_{1} ∣^{2} + ∣ z_{2} ∣^{2})^{1 / 2}$ (The counting inner product on $C^{Z / N Z}$ ).

[F1]

Six-operation complex multiplication obeys $∣ {fl}_{C} (z w) - z w ∣ \leq 3 u ∣ z ∣ ∣ w ∣$ when its six operations succeed (Six-operation complex multiplication has a normwise roundoff bound).

[F2]

$∣ w ∣ = 1$ and $∣ \hat{w} - w ∣ \leq ϵ$ ; hence $∣ \hat{w} ∣ \leq 1 + ϵ$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ , Certified phase output encloses the exact unit-circle value, Conjugation is an involutive real-field automorphism, $z \overline{z} = ∣ z ∣^{2}$ , and modulus is definite, multiplicative, and subadditive).

[F3]

Each real rounded addition, multiplication, or positive in-range square root has relative error at most $u$ ; complex addition and real scaling round their two components separately (The standard relative floating-point model and unit roundoff, Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add).

[F4]

The complex modulus is subadditive; Cauchy–Schwarz bounds the Euclidean norm of two coordinatewise error bounds (Conjugation is an involutive real-field automorphism, $z \overline{z} = ∣ z ∣^{2}$ , and modulus is definite, multiplicative, and subadditive, Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors).

Proof

1.1givenF1F2algebra

Let $t = {fl}_{C} (\hat{w} b)$ . By [F1] and [F2], $∣ t - w b ∣ \leq 3 u ∣ \hat{w} ∣ ∣ b ∣ + ϵ ∣ b ∣ \leq (15 u / 4 + ϵ) ∣ b ∣$ . Thus $∣ t ∣ \leq (1 + 15 u / 4 + ϵ) ∣ b ∣ \leq 95 ∣ b ∣ / 64$ .

1.2givenF3F4algebra

For $q_{\pm} = {fl}_{C} (a \pm t)$ , [F3] gives $∣ q_{\pm} - (a \pm t) ∣ \leq u (∣ a ∣ + ∣ t ∣)$ by [F4]. If $c = 1 / \sqrt{2}$ and $\hat{c} = fl (\sqrt{1 / 2})$ , then correct rounding gives $∣ \hat{c} - c ∣ \leq u c$ . The componentwise rounded scaling therefore satisfies $∣ {fl}_{C} (\hat{c} q_{\pm}) - c q_{\pm} ∣ \leq (2 u + u^{2}) c ∣ q_{\pm} ∣$ , and $∣ q_{\pm} ∣ \leq (1 + u) (∣ a ∣ + ∣ t ∣)$ .

2.1step 1.1step 1.2algebra

Combining steps 1.1–1.2 and using $\sqrt{2} c = 1$ , the two-output error norm is at most $(15 u / 4 + ϵ) ∣ b ∣ + α (∣ a ∣ + 95 ∣ b ∣ / 64)$ , where $α = u + (2 u + u^{2}) (1 + u) = 3 u + 3 u^{2} + u^{3} \leq 817 u / 256$ . Since $15 / 4 + (817 / 256) (95 / 64) < 9$ , this is at most $(817 u / 256) ∣ a ∣ + (9 u + ϵ) ∣ b ∣$ .

3.1step 2.1F4F5algebra∎

By [F4], $\sqrt{(817 / 256)^{2} + 9^{2}} < 10$ , so $(817 u / 256) ∣ a ∣ + 9 u ∣ b ∣ \leq 10 u \sqrt{∣ a ∣^{2} + ∣ b ∣^{2}}$ ; [F5] identifies the square-root factor as $∥ (a, b) ∥_{2}$ . Also $ϵ ∣ b ∣ \leq ϵ \sqrt{∣ a ∣^{2} + ∣ b ∣^{2}}$ . Adding the bounds proves the claim.

Depends on

Used by

Computed unitary radix-two FFT has the multiplicative stage error bound Theorem

Dependency tree · two levels

43 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, Theorem 24.2, pp. 453–454 (standard reference, not scraped)
C. Sidney Burrus, Fast Fourier Transforms, Chapter 11 §11.7 (standard reference, not scraped)