TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-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.

DCT-II samples extract Chebyshev coefficients at first-kind roots

Statement

Let $p (t) = \sum_{k = 0}^{N - 1} a_{k} T_{k} (t)$ be a polynomial of degree less than $N$ , where $T_{k}$ is the Chebyshev polynomial of the first kind, and sample $x_{j} = p (\cos (π (j + 1 / 2) / N))$ for $0 \leq j < N$ . If $X$ is the DCT-II of $x$ , then $a_{0} = X_{0} / N$ and $a_{k} = 2 X_{k} / N$ for $1 \leq k < N$ .

Facts & Assumptions

Given: $N \geq 1$ , coefficients $a_{0}, \dots, a_{N - 1}$ , Chebyshev polynomials $T_{k}$ , and the DCT-II convention of DCT-II and DST-I with fixed even and odd extension conventions.

[F1]

$T_{k} (\cos θ) = \cos (k θ)$ for every integer $k \geq 0$ , by the recurrence definition together with the addition formulas (Chebyshev polynomials of the first and second kinds by their three-term recurrences, $T_{n} (\cos θ) = \cos (n θ)$ and $U_{n} (\cos θ) \sin θ = \sin ((n + 1) θ)$ for every $n \in N$ ).

[F2]

The DCT-II matrix is $C_{k j} = \cos (π (j + 1 / 2) k / N)$ , and its row-orthogonality factor is $C C^{T} = diag (N, N / 2, \dots, N / 2)$ (DCT-II and DST-I with fixed even and odd extension conventions, DCT-II is orthogonal with the stated endpoint normalization and even extension).

Proof

1.1givenF1F2

Put $θ_{j} = π (j + 1 / 2) / N$ . By [F1], $x_{j} = \sum_{k = 0}^{N - 1} a_{k} \cos (k θ_{j}) = \sum_{k = 0}^{N - 1} C_{k j} a_{k}$ , so in vector form $x = C^{T} a$ .

2.1step 1.1F2algebra∎

The DCT output is $X = C x = C C^{T} a$ . By [F2], $C C^{T}$ is diagonal with entries $N$ at index zero and $N / 2$ at positive indices. Thus $X_{0} = N a_{0}$ and $X_{k} = (N / 2) a_{k}$ for $k \geq 1$ . Dividing by these positive constants gives the claimed coefficients.

Depends on

Used by

Three Chebyshev-root samples recover a quadratic by DCT-II Example

Dependency tree · two levels

22 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

C. Sidney Burrus, Fast Fourier Transforms, Chapter 8 §8.3.2 (standard reference, not scraped)