ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)

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.

The unitary DFT for $N = 1$ and $N = 2$

Example

For $N = 1$ the unitary transform of The unitary discrete Fourier transform on $Z / N Z$ is the identity: the group $Z / 1 Z$ has the single class $[0]_{1}$ , the only term of the defining sum is $1^{- 1 / 2} f ([0]_{1}) e^{0} = f ([0]_{1})$ , and the matrix of $F_{1}$ is the $1 \times 1$ matrix $[1] = I_{1}$ , which is its own inverse.

For $N = 2$ , write $h = (h_{0}, h_{1})$ for $h \in C^{Z / 2}$ with $h_{0} : = h ([0]_{2})$ and $h_{1} : = h ([1]_{2})$ . Since $e^{- π i x k} = (- 1)^{x k}$ for $x, k \in {0, 1}$ ,

$F_{2} (h_{0}, h_{1}) = 2^{- 1 / 2} (h_{0} + h_{1}, h_{0} - h_{1}),$

whose matrix relative to the classes $[0], [1]$ is $\frac{1}{\sqrt{2}} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})$ ; this matrix is real and symmetric and satisfies $A^{2} = I_{2}$ , so it is its own inverse. Since the reflection $x \mapsto - x$ is the identity on $Z / 1 Z$ and on $Z / 2 Z$ , the fourth-power identity of $F_{N}^{2}$ is reflection and $F_{N}^{4}$ is the identity reads $F_{1}^{2} = F_{2}^{2} = i d$ here, consistent with $A^{2} = I_{2}$ and with the inversion theorem Finite Fourier inversion for the unitary transform on $Z / N Z$ ; and $F_{2}$ preserves the counting norm by Finite Parseval and Plancherel identity for the unitary DFT.

Facts & Assumptions

Given: A function $f \in C^{Z / 1}$ with $f_{0} : = f ([0]_{1})$ ; a function $h \in C^{Z / 2}$ with $h_{0} : = h ([0]_{2})$ and $h_{1} : = h ([1]_{2})$ ; and the matrix $A : = \frac{1}{\sqrt{2}} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})$ .

[F1]

$(F_{N} u) (k) = N^{- 1 / 2} \sum_{x = 0}^{N - 1} u ([x]_{N}) e^{- 2 π i k x / N}$ (The unitary discrete Fourier transform on $Z / N Z$ ), with $1^{- 1 / 2} = 1$ and $2^{- 1 / 2} 2^{- 1 / 2} = 2^{- 1}$ (Rational powers $a^{r}$ of a positive base, Laws of rational exponents).

[F2]

$e^{0} = 1$ , $e^{- π i} = - 1$ and $e^{- 2 π i} = 1$ ( $\ker (\exp) = 2 π i Z$ , and $\exp z = \exp w$ exactly when $z - w \in 2 π i Z$ , $\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential, The complex exponential by its power series); in particular $e^{- π i x k} = (- 1)^{x k}$ for $x, k \in {0, 1}$ .

[F3]

In $Z / 2 Z$ the classes $[0]$ , $[1]$ are distinct and $[1] + [1] = [0]$ ; in $Z / 1 Z$ there is only $[0]$ , and $- [0] = [0]$ (The congruence class $[a]_{n}$ and the quotient set $Z / n$ , For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

[F4]

Matrix product and identity: $(A B)_{i k} = \sum_{j \in n} a_{i j} b_{j k}$ and $I_{n}$ has entries $1$ on the diagonal and $0$ elsewhere (Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes); $C^{Z / 2}$ is the vector space of functions on the two-element group (The vector space $F^{X}$ of all functions $X \to F$ with pointwise operations, and $F^{n}$ as the case $X = n = {0, 1, \dots, n - 1}$ ).

[L1]

$F_{N}^{2} = R$ with $R$ the reflection $x \mapsto - x$ , and $F_{N}^{4} = i d$ ; at $N = 1, 2$ the reflection is the identity ( $F_{N}^{2}$ is reflection and $F_{N}^{4}$ is the identity).

[L2]

$⟨ F_{N} u, F_{N} u ⟩ = ⟨ u, u ⟩$ for the counting inner product (Finite Parseval and Plancherel identity for the unitary DFT, Conjugation is an involutive real-field automorphism, $z \overline{z} = ∣ z ∣^{2}$ , and modulus is definite, multiplicative, and subadditive).

[L3]

The inverse transform is the positive-sign transform $N^{- 1 / 2} \sum_{k} (F_{N} u) (k) e^{2 π i k x / N}$ (Finite Fourier inversion for the unitary transform on $Z / N Z$ ).

Verification

technique · direct

1.1F1F2F3

At $N = 1$ : $(F_{1} f) (0) = 1^{- 1 / 2} f_{0} e^{0} = f_{0}$ , so $F_{1} = i d$ and its matrix is $I_{1} = [1]$ .

1.2F1F2F3

At $N = 2$ : for $k = 0$ both summands have factor $e^{0} = 1$ , giving $(F_{2} h) (0) = 2^{- 1 / 2} (h_{0} + h_{1})$ ; for $k = 1$ the factors are $e^{0} = 1$ at $x = 0$ and $e^{- π i} = - 1$ at $x = 1$ , giving $(F_{2} h) (1) = 2^{- 1 / 2} (h_{0} - h_{1})$ . These are the two entries of $A (h_{0}, h_{1})^{T}$ .

1.3F4

The matrix $A$ satisfies $A^{2} = \frac{1}{2} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array}) (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array}) = \frac{1}{2} (\begin{array}{cc} 1 + 1 & 1 - 1 \\ 1 - 1 & 1 + 1 \end{array}) = \frac{1}{2} (\begin{array}{cc} 2 & 0 \\ 0 & 2 \end{array}) = I_{2}$ , by the entry formula of [F4]; hence $A = A^{- 1}$ , and $A$ is real and symmetric.

2.1F3L1L2step 1.3

The reflection is the identity on $Z / 1 Z$ and on $Z / 2 Z$ by [F3], so [L1] gives $F_{1}^{2} = i d$ and $F_{2}^{2} = i d$ ; this is consistent with $[1]^{2} = [1]$ and with step 1.3, and by [L2] the transforms preserve the counting norm at both lengths (for $N = 2$ , the norm identity reads $∣ h_{0} + h_{1} ∣^{2} + ∣ h_{0} - h_{1} ∣^{2} = 2 ∣ h_{0} ∣^{2} + 2 ∣ h_{1} ∣^{2}$ , which is the displayed matrix computation after multiplying by $\frac{1}{2}$ ).

3.1L3step 1.1step 1.2step 1.3step 2.1∎

Steps 1.1 and 1.2 compute the two transforms and their matrices, step 1.3 verifies that the $N = 2$ matrix is its own inverse, and step 2.1 reconciles both with inversion and the fourth-power identity; the example is verified.

Remarks

The degenerate length is not an exception. $N = 1$ is a genuine case of every statement on this page: the transform is the identity, the orthogonality sum has its single coincident term, and the radix-two recursion later on this page terminates at this case as its base. Nothing in the definitions excludes it, and no separate convention is introduced for it.
At $N = 2$ the transform is its own inverse. This is the smallest length at which the transform is not the identity while still being involutive; for $N \geq 3$ the reflection is not the identity, so the square of the transform is not the identity either, although the fourth power always is.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

68 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

Michael E. Taylor, Fourier Analysis, Distributions, and Constant-Coefficient Linear PDE (author PDF) (standard reference, not scraped)
MIT 18.310 lecture 23, The Finite Fourier Transform and the Fast Fourier Transform Algorithm (course page) (standard reference, not scraped)

The unitary DFT for N=1N=1 and N=2N=2