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

Type-1, type-2, and type-3 nonuniform Fourier transforms

Definition

Fix an integer dimension $d \geq 1$ . Let $T^{d} = [0, 1)^{d}$ be the chosen representatives for period-one coordinates; all coordinates in a type-1 or type-2 transform are interpreted modulo integer shifts. Here $π$ is the real constant defined in Real elementary functions and their domains. For $x \in R^{d}$ and $k \in Z^{d}$ , write $k \cdot x = \sum_{r = 1}^{d} k_{r} x_{r}$ . Let $N, J \geq 0$ be finite integers, let $x_{0}, \dots, x_{N - 1} \in T^{d}$ , let $c = (c_{j})_{j < N} \in C^{N}$ , and choose integers $K_{r} \geq 0$ . The rectangular mode set is

$K = \prod_{r = 1}^{d} {- K_{r}, - K_{r} + 1, \dots, K_{r}} .$

The type-1 nonuniform discrete Fourier transform maps source coefficients to integer-mode samples:

$F_{k} = \sum_{j = 0}^{N - 1} c_{j} e^{- 2 π i k \cdot x_{j}}, k \in K .$

The type-2 nonuniform discrete Fourier transform maps a coefficient array $(f_{k})_{k \in K}$ to values at the same point list:

$g_{j} = \sum_{k \in K} f_{k} e^{+ 2 π i k \cdot x_{j}}, 0 \leq j < N .$

For the type-1 matrix $A = (e^{- 2 π i k \cdot x_{j}})_{k \in K, j < N}$ , define its conjugate transpose by $(A^{*})_{j k} = \overline{A_{k j}}$ . Use the finite counting inner products from Finite complex-array norms used by the NUFFT certificates; the type-2 matrix is $A^{*}$ as proved below.

The type-3 nonuniform discrete Fourier transform takes a finite source list $x_{0}, \dots, x_{N - 1} \in R^{d}$ , coefficients $c_{j} \in C$ , and a separately specified finite frequency list $ξ_{0}, \dots, ξ_{J - 1} \in R^{d}$ , and returns

$G_{ℓ} = \sum_{j = 0}^{N - 1} c_{j} e^{- 2 π i ξ_{ℓ} \cdot x_{j}}, 0 \leq ℓ < J .$

Type 3 has no integer-mode restriction or implicit coordinate wrapping. No frequency normalization, axis scaling, or frequency-space product is implicit; any such scaling is separate input data whose cost must be analyzed separately. Each displayed map is a finite sum of defined complex exponentials; the zero-source case has the empty-sum value zero and the zero-output case returns the empty array. No fast algorithm or complexity claim for type 3 is part of this definition.

Facts & Assumptions

Given: The finite source and mode lists, arrays $c, f$ , and the displayed type-1/type-2 conventions.

[F1]

$\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ : for real $t$ , $e^{i t} = \cos t + i \sin t$ .

[F2]

Pythagorean and parity identities for all six trigonometric functions on their natural domains: cosine is even and sine is odd.

[F3]

Real and imaginary parts, complex conjugation, and modulus: $\overline{a + i b} = a - i b$ for real $a, b$ .

[F4]

A finite sum in a commutative monoid indexed by an arbitrary finite set, Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either, $C = R [x] / (x^{2} + 1)$ is a field, every element is uniquely $a + b i$ , and every nonzero element has inverse $(a - b i) / (a^{2} + b^{2})$ , and Conjugation is an involutive real-field automorphism, $z \overline{z} = ∣ z ∣^{2}$ , and modulus is definite, multiplicative, and subadditive: finite complex sums may be expanded and reordered, multiplication is commutative/distributive, and conjugation preserves products and sums.

Proof

1.1givenF1F2F3algebra

Fix $j < N$ and $k \in K$ , and put $t = 2 π k \cdot x_{j} \in R$ . By [F1]–[F2], $e^{- i t} = \cos (- t) + i \sin (- t) = \cos t - i \sin t$ . Applying [F3] gives $\overline{e^{- i t}} = \cos t + i \sin t = e^{i t}$ . Thus $(A^{*})_{j k} = \overline{A_{k j}} = e^{+ 2 π i k \cdot x_{j}}$ .

2.1F4step 1.1algebra∎

For any $c \in C^{N}$ and $f \in C^{K}$ , expand the finite sums: $⟨ A c, f ⟩_{K} = \sum_{k \in K} \sum_{j < N} c_{j} e^{- 2 π i k \cdot x_{j}} \overline{f_{k}} = \sum_{j < N} c_{j} \overline{\sum_{k \in K} f_{k} e^{+ 2 π i k \cdot x_{j}}} = ⟨ c, A^{*} f ⟩_{{j < N}} .$ The first equality uses finite distributivity/reordering from [F4]; the second uses step 1.1 and the stated inner-product convention. Thus the type-2 sum is exactly the conjugate-transpose action under matching finite inner products.

Depends on

Used by

Dependency tree · two levels

54 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

Jens Keiner, Stefan Kunis, and Antje Vollrath, The Nonequispaced FFT and its Applications, Part I, slides 40 and 69 (standard reference, not scraped)
Leslie Greengard and June-Yub Lee, Accelerating the Nonuniform Fast Fourier Transform (standard reference, not scraped)
Leslie Greengard and June-Yub Lee, NUFFT User's Guide, Version 1.2 (standard reference, not scraped)