CounterexampleConstruction: 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.

Cyclic convolution wraps a high coefficient without zero padding

Statement refuted

False claim: for every $N \geq 1$ and all $f, g \in C^{Z / N}$ with coefficient lists $u_{i} : = f ([i]_{N})$ and $v_{j} : = g ([j]_{N})$ , the cyclic convolution $f * g$ of The unnormalised cyclic convolution on $Z / N Z$ has the linear convolution values $(f * g) ([k]) = \sum_{i + j = k} u_{i} v_{j}$ for every $k = 0, \dots, N - 1$ ; that is, no coefficient of the product ever wraps around.

The false claim fails already for $N = 2$ and $f = g = (1, 1)$ : the coefficient $1$ of $z^{2}$ in the unreduced product $(1 + z)^{2} = 1 + 2 z + z^{2}$ is wrapped into degree $0$ , so $(f * g) ([0]) = 2$ while the linear value listed for $k = 0$ is $u_{0} v_{0} = 1$ . Sufficient zero padding restores the agreement: padded to length $4$ , the same two sequences have cyclic convolution $(1, 2, 1, 0)$ , exactly the unreduced coefficient list.

Facts & Assumptions

Given: The classes of $Z / 2 Z$ and $Z / 4 Z$ ; the functions $f, g \in C^{Z / 2}$ with $f ([0]_{2}) = f ([1]_{2}) = g ([0]_{2}) = g ([1]_{2}) = 1$ ; and the padded functions $f^{'}, g^{'} \in C^{Z / 4}$ with $f^{'} ([0]) = g^{'} ([0]) = f^{'} ([1]) = g^{'} ([1]) = 1$ and $f^{'} = g^{'} = 0$ on $[2], [3]$ .

[F1]

For finite groups the cyclic convolution is $(u * v) (x) = \sum_{y \in Z / N} u (y) v (x - y)$ , a finite sum of complex numbers depending on classes only (The unnormalised cyclic convolution on $Z / N Z$ ).

[F2]

In $Z / N Z$ the operation is the class addition of Addition and multiplication on $Z / n$ by $[a]_{n} + [b]_{n} = [a + b]_{n}$ and $[a]_{n} [b]_{n} = [a b]_{n}$ , is commutative, and $[u]_{N} = [v]_{N}$ exactly when $u \equiv v (m o d N)$ ; the classes $[0]_{N}, \dots, [N - 1]_{N}$ enumerate the group (For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold, The congruence class $[a]_{n}$ and the quotient set $Z / n$ , For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ).

[F3]

Finite sums over these groups split over disjoint unions and are computed from any enumeration (A finite sum in a commutative monoid indexed by an arbitrary finite set); arithmetic of the values is that of the field $C$ ( $C = R [x] / (x^{2} + 1)$ is a field, every element is uniquely $a + b i$ , and every nonzero element has inverse $(a - b i) / (a^{2} + b^{2})$ ); $C^{Z / N}$ consists of functions with pointwise operations (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]

Expanding the finite product by distributivity [F3] gives one term $u_{i} v_{j} z^{i + j}$ for each pair of indices. Reduction modulo $z^{N} - 1$ replaces $z^{i + j}$ by $z^{r}$ with $r \equiv i + j (m o d N)$ . For each class $x$ and each class $i$ , exactly one class $j = x - i$ contributes to its coefficient, giving $\sum_{i} u_{i} v_{x - i}$ , the cyclic convolution of [F1].

[L2]

The false claim of the Statement refuted section, for the pair $(f, g)$ and for the padded pair $(f^{'}, g^{'})$ .

Counterexample

technique · direct

1.1F1F2F3

Computing the cyclic convolution on $Z / 2$ : $- [0] = [0]$ and $- [1] = [1]$ , so $(f * g) ([0]) = f ([0]) g ([0]) + f ([1]) g ([1]) = 1 \cdot 1 + 1 \cdot 1 = 2$ and $(f * g) ([1]) = f ([0]) g ([1]) + f ([1]) g ([0]) = 1 + 1 = 2$ . Hence $f * g = (2, 2)$ .

1.2F3

The linear convolution values $c_{k} = \sum_{i + j = k} u_{i} v_{j}$ for the two coefficient lists $(u_{0}, u_{1}) = (1, 1)$ and $(v_{0}, v_{1}) = (1, 1)$ : $c_{0} = u_{0} v_{0} = 1$ , $c_{1} = u_{0} v_{1} + u_{1} v_{0} = 2$ , $c_{2} = u_{1} v_{1} = 1$ . The unreduced coefficient list is therefore $(c_{0}, c_{1}, c_{2}) = (1, 2, 1)$ .

1.3F1F2F3

Zero padding to length $N^{'} = 4$ : for the padded pair, $(f^{'} * g^{'}) ([x]) = \sum_{y = 0}^{3} f^{'} ([y]) g^{'} ([x - y])$ gives $1, 2, 1, 0$ for $x = [0], [1], [2], [3]$ respectively, since each of the products $u_{0} v_{0}, u_{0} v_{1}, u_{1} v_{0}, u_{1} v_{1}$ occurs exactly once and no product of two nonzero values wraps onto a different degree. This equals the linear coefficient list $(1, 2, 1)$ continued by $0$ .

2.1F2L1step 1.1step 1.2

Reducing degrees modulo $2$ : the coefficient $c_{2} = 1$ of $z^{2}$ contributes to degree $2 - 2 = 0$ , so the reduction of the linear list $(1, 2, 1)$ modulo $z^{2} - 1$ is $(c_{0} + c_{2}, c_{1}) = (1 + 1, 2) = (2, 2)$ , which agrees with the cyclic convolution of step 1.1: the reduction, not the unreduced list, is what the cyclic convolution computes.

3.1step 1.1step 1.2step 1.3L2∎

The false claim [L2] predicts $(f * g) ([0]) = c_{0} = 1$ , whereas step 1.1 gives $(f * g) ([0]) = 2$ , so it fails for $N = 2$ and $f = g = (1, 1)$ . Step 1.2 gives three coefficients in the linear product, and step 1.3 verifies that padding to length $4$ preserves them with a trailing zero.

Remarks

Padding threshold. For nonzero coefficient polynomials $P, Q$ , choosing $N \geq \deg P + \deg Q + 1$ prevents wrap: every exponent in $P Q$ is below $N$ , so [L1] leaves its coefficients unchanged. Here the minimum such length is $3$ ; length $4$ also works and admits the radix-two algorithm. The transform law The DFT turns cyclic convolution into a scaled pointwise product always computes cyclic convolution.
Where the wrap comes from. In the group $Z / 2 Z$ the class $[2]$ is $[0]$ , so the exponent $2$ of $z^{2}$ is the exponent $0$ of the reduced polynomial; nothing is lost or approximated — the degree- $2$ and degree- $0$ coefficients are added in the field, which is exactly what the convolution sum does.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

39 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)