ExampleConstruction: AI-generatedVerification: 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.

Two-point circular convolution aliases the linear endpoint term

Example

Let $a = b = (1, 1)$ . The exact length-two cyclic convolution is $(2, 2)$ , while the linear convolution is $(1, 2, 1)$ . Padding both inputs to length four makes the first three cyclic outputs equal the linear convolution and leaves the last output zero. The length-two circular result has wrapped the final linear coefficient into its index-zero output. This compares exact convolution operations and does not assert an output for the computed routine.

Facts & Assumptions

Given: The exact cyclic and linear convolution operations, $a_{0} = a_{1} = b_{0} = b_{1} = 1$ , and zeros outside the stated two-entry supports.

[F1]

$(a *_{2} b)_{k} = \sum_{j = 0}^{1} a_{j} b_{[k - j]_{2}}$ (The unnormalised cyclic convolution on $Z / N Z$ ).

[F2]

Zero padding to any $M \geq n + m - 1$ gives the full linear convolution in the first $n + m - 1$ cyclic outputs and zero thereafter (Zero padding embeds linear convolution in cyclic convolution without aliasing).

Verification

1.1givenF1algebra

From [F1], $(a *_{2} b)_{0} = a_{0} b_{0} + a_{1} b_{1} = 2$ and $(a *_{2} b)_{1} = a_{0} b_{1} + a_{1} b_{0} = 2$ . Direct linear convolution has coefficients $c_{0} = a_{0} b_{0} = 1$ , $c_{1} = a_{0} b_{1} + a_{1} b_{0} = 2$ , and $c_{2} = a_{1} b_{1} = 1$ .

2.1givenF2step 1.1∎

Here $n = m = 2$ , so $n + m - 1 = 3$ . Choose $M = 4 \geq 3$ . By [F2], the exact length-four cyclic operation on the padded inputs has outputs $(c_{0}, c_{1}, c_{2}, 0) = (1, 2, 1, 0)$ . Since its index-zero value is $1$ rather than the unpadded circular value $2$ , the latter contains the wrapped endpoint term $c_{2}$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 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 13 §13.1 (standard reference, not scraped)