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.

Periodic Fourier modes alias modulo the grid size

Statement

Let $N \geq 2$ and $x_{j} = 2 π j / N$ . If integers $k, r$ satisfy $k \equiv r (m o d N)$ , then

e^{i k x_{j}} = e^{i r x_{j}} (0 \leq j < N) .

Consequently, sampling a product of Fourier modes with frequencies $k_{1}, \dots, k_{s}$ gives the same nodal data as the single mode whose frequency is the sum $\sum_{ℓ = 1}^{s} k_{ℓ}$ reduced modulo $N$ .

The frequency space in Periodic Fourier collocation grid and even-grid Nyquist convention is real-valued. For complex data, let $T_{N}^{C}$ be the space obtained by allowing complex coefficients in that same real basis, and extend its cardinal formula by

I_{N}^{C} V (x) : = \sum_{j = 0}^{N - 1} V_{j} L_{j} (x), V \in C^{N} .

Then $I_{N}^{C} V$ is the unique member of $T_{N}^{C}$ with nodal data $V$ . On real data this formula agrees with $I_{N}$ ; in the even case the complex Nyquist samples are interpolated by the real basis function $\cos (N x / 2)$ .

Facts & Assumptions

Given: An integer $N \geq 2$ , its periodic grid, and integers $k, r$ with $k - r = q N$ for some integer $q$ .

[F1]

Periodic Fourier collocation grid and even-grid Nyquist convention: the grid nodes are $x_{j} = 2 π j / N$ , the cardinal functions are $L_{j}$ , and on the grid the complexified basis modes give one complete residue system modulo $N$ (the even-grid Nyquist cosine has the samples of the residue $N / 2$ ); the complexification and its cardinal formula are specified in the Statement.

[F2]

$\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential: $e^{z + w} = e^{z} e^{w}$ ; $\ker (\exp) = 2 π i Z$ , and $\exp z = \exp w$ exactly when $z - w \in 2 π i Z$ : $e^{w} = 1$ when $w \in 2 π i Z$ .

[F3]

Orthogonality of the characters $x \mapsto e^{2 π i k x / N}$ on $Z / N Z$ : the sum over a complete residue system of the characters at $i - j$ is $N$ when $i = j$ and $0$ otherwise.

[F4]

Finite Fourier inversion for the unitary transform on $Z / N Z$ : complex nodal data on $Z / N Z$ have a unique finite Fourier representation.

[F5]

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

[F6]

The derivatives of sine and cosine are cosine and minus sine and Quarter-turn values and shifts by pi/2 and pi: $\sin 0 = 0$ and $\sin (x + π) = - \sin x$ , hence $\sin (m π) = 0$ for every integer $m$ .

Proof

1.1givenF1F2algebra

Since $k - r = q N$ , for every grid index $j$ we have $e^{i (k - r) x_{j}} = e^{2 π i q j} = 1$ by [F2]. Multiplying by $e^{i r x_{j}}$ gives $e^{i k x_{j}} = e^{i r x_{j}}$ .

2.1givenF2step 1.1algebra

For frequencies $k_{1}, \dots, k_{s}$ , multiplication of the sampled modes gives $\prod_{ℓ = 1}^{s} e^{i k_{ℓ} x_{j}} = e^{i (\sum_{ℓ} k_{ℓ}) x_{j}}$ by the exponential addition law in [F2]. Applying step 1.1 to this sum and any congruent representative proves the product aliasing identity.

3.1F1F2F3F4F5F6step 2.1algebra∎

For $Δ = x_{i} - x_{j}$ , Euler's identity [F5] writes the odd-grid kernel as $L_{j} (x_{i}) = N^{- 1} \sum_{k = - K}^{K} e^{i k Δ}$ when $N = 2 K + 1$ . For an even grid $N = 2 K$ , it writes the kernel as $L_{j} (x_{i}) = N^{- 1} \sum_{k = - K + 1}^{K} e^{i k Δ}$ , because $K Δ = π (i - j)$ and [F6] makes the sine term at this Nyquist frequency vanish. In either branch $e^{i N Δ} = 1$ by [F2], so the sum over these complete residue systems equals the sum over $k = 0, \dots, N - 1$ . Character orthogonality [F3] therefore gives $L_{j} (x_{i}) = 1$ for $i = j$ and $0$ otherwise, so the displayed complex-linear cardinal formula interpolates every $V \in C^{N}$ . For uniqueness inside $T_{N}^{C}$ , expand each low-frequency cosine/sine pair by [F5] into its two characters. On an odd grid these are the residues $- K, \dots, K$ ; on an even grid they are $- K + 1, \dots, K - 1$ together with the Nyquist sample $\cos (K x_{j}) = e^{i K x_{j}}$ . The real-basis coefficients map invertibly to these character coefficients (the low modes use the two Euler coefficients and the Nyquist coefficient is unchanged). If a member of $T_{N}^{C}$ has zero samples, inversion [F4] makes every character coefficient zero, hence the member is zero. The product samples from step 2.1 therefore have the unique cardinal interpolant. In the even Nyquist case the interpolant is $\cos (N x / 2)$ , not the complex exponential as a function away from the grid.

Depends on

Used by

Dependency tree · two levels

50 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

Benjamin Seibold, MIT 18.336 Lecture 24: Pseudospectral Methods (standard reference, not scraped)
Lloyd N. Trefethen, Finite Difference and Spectral Methods for Ordinary and Partial Differential Equations, Ch. 7 (standard reference, not scraped)