TheoremStatement: AI-adaptedProof: 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.

Fourier transform of unnormalized convolution

Statement

For a finite abelian group $G$ , $f, g : G \to C$ , and $χ \in \hat{G}$ , put $N_{R} : = ι_{R} (∣ G ∣)$ . With the transform and unnormalized convolution defined above, $F_{G} (f * g) (χ) = N_{R}^{1 / 2} (F_{G} f) (χ) (F_{G} g) (χ) .$ Thus the factor is $\sqrt{∣ G ∣}$ , not $1$ or $∣ G ∣$ , for this pair of conventions.

Facts & Assumptions

Given: The finite sum definitions of $F_{G}$ and $f * g$ on the same finite abelian group.

[F1]

$(f * g) (z) = \sum_{x \in G} f (x) g (z - x)$ (Unnormalized convolution on a finite abelian group).

[F2]

$(F_{G} f) (χ) = N_{R}^{- 1 / 2} \sum_{x \in G} f (x) \overline{χ (x)}$ (Normalized Fourier transform on a finite abelian group).

[F3]

A character satisfies $χ (x + y) = χ (x) χ (y)$ (Additive characters of a finite abelian group).

[F4]

Complex conjugation preserves products, $\overline{z w} = \overline{z} \overline{w}$ (Conjugation is an involutive real-field automorphism, $z \overline{z} = ∣ z ∣^{2}$ , and modulus is definite, multiplicative, and subadditive).

[F5]

Finite sums may be reindexed by bijections and factored by the finite Fubini rule (Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule).

[F6]

Positive rational powers satisfy $a^{r} a^{s} = a^{r + s}$ and $a^{0} = 1$ (Laws of rational exponents).

Proof

1.1F1F2F5

Substitute [F1] into [F2] and distribute the finite sums; [F5] permits the iterated sum, giving $F_{G} (f * g) (χ) = N_{R}^{- 1 / 2} \sum_{z \in G} \sum_{x \in G} f (x) g (z - x) \overline{χ (z)}$ .

2.1F3F4F5step 1.1construct

The map $(z, x) \mapsto (x, y)$ with $y = z - x$ is a bijection $G \times G \to G \times G$ , with inverse $(x, y) \mapsto (x + y, x)$ . Reindexing by this bijection and using [F3] and [F4] gives $F_{G} (f * g) (χ) = N_{R}^{- 1 / 2} \sum_{x, y} f (x) g (y) \overline{χ (x)} \overline{χ (y)} = N_{R}^{- 1 / 2} (\sum_{x} f (x) \overline{χ (x)}) (\sum_{y} g (y) \overline{χ (y)})$ .

3.1F2F6step 2.1algebra∎

By [F2], each parenthesized sum in step 2.1 equals $N_{R}^{1 / 2}$ times the corresponding transform value. The coefficient is therefore $N_{R}^{- 1 / 2} N_{R}^{1 / 2} N_{R}^{1 / 2} = N_{R}^{1 / 2}$ by [F6], which proves the formula.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

41 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

Ronald de Wolf, Quantum Computing: Lecture Notes, version 6 (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (standard reference, not scraped)
John Preskill, Quantum Information, Chapter 6: Quantum Algorithms (standard reference, not scraped)