Finite Fourier Analysis and the Fast Fourier Transform

Let $N\ge 1$ and let ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ be the complex vector space of all functions $\mathbb{Z}\mathrm{/}N\mathbb{Z}\to \mathbb{C}$, with pointwise addition and scalar multiplication (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\}$, Vector space over a field). For $f,g\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ define

$⟨f,g⟩:={\sum }_{x\in \mathbb{Z}\mathrm{/}N}f(x)\overline{g(x)},$

the sum being the finite sum over the finite index set $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ in the additive commutative monoid of $\mathbb{C}$ (A finite sum in a commutative monoid indexed by an arbitrary finite set). Enumerating the group by its standard representatives gives the equivalent formula

$⟨f,g⟩={\sum }_{x=0}^{N-1}f([x{]}_N)\overline{g([x{]}_N)},$

where $\bar{\phantom{z}}$ is complex conjugation (Real and imaginary parts, complex conjugation, and modulus). The two displays agree. By For $n\ge 1$, every class in $\mathbb{Z}\mathrm{/}n$ has one representative $r$ with $0\le r<n$, so $\mid \mathbb{Z}\mathrm{/}n\mid =n$; while $\mathbb{Z}\mathrm{/}0$ is in bijection with $\mathbb{Z}$ the map $x\mapsto [x{]}_N$ is a bijection from the von Neumann natural $N=\{0,\dots ,N-1\}$ onto $\mathbb{Z}\mathrm{/}N\mathbb{Z}$, and the summand $f(x)\overline{g(x)}$ depends only on the class $x$; a finite commutative-monoid sum is unchanged by reindexing along a bijection (Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule, part 1), so the second display is a rewrite of the first. No representative of a class is ever selected: every application of $f$ or of $g$ is an evaluation at a class.

The pairing is an inner product in the sense of Real and complex inner product spaces, with the inner product linear in the first argument and Real and complex inner-product spaces and their induced length, with the linear-first convention fixed there. Linearity in the first argument, $⟨a{f}_1+b{f}_2,g⟩=a⟨f_1,g⟩+b⟨f_2,g⟩$ for $a,b\in \mathbb{C}$, follows from the field laws of $\mathbb{C}$ ($\mathbb{C}=\mathbb{R}[x]\mathrm{/}(x^2+1)$ is a field, every element is uniquely $a+bi$, and every nonzero element has inverse $(a-bi)\mathrm{/}(a^2+b^2)$) together with the two elementary laws of a finite sum over a fixed finite index set, ${\sum }_x(u_x+v_x)={\sum }_x{u}_x+{\sum }_x{v}_x$ and ${\sum }_{x}c{u}_x=c{\sum }_x{u}_x$; each of these laws is proved from the recursion clauses of A finite sum in a commutative monoid indexed by an arbitrary finite set by induction on an enumeration of the index set. Conjugate symmetry, $⟨f,g⟩=\overline{⟨g,f⟩}$, follows from the same two laws together with the fact that complex conjugation is an involutive field automorphism, hence $\overline{g(x)\stackrel{‾}{f(x)}}=\overline{g(x)}f(x)$ and conjugation commutes with finite sums (Conjugation is an involutive real-field automorphism, $z\bar{z}=\mathrm{\mid }z{\mathrm{\mid }}^2$, and modulus is definite, multiplicative, and subadditive).

Positive definiteness. Taking $g=f$ gives $⟨f,f⟩={\sum }_x\mathrm{\mid }f(x){\mathrm{\mid }}^2$ by $z\bar{z}=\mathrm{\mid }z{\mathrm{\mid }}^2$ (Conjugation is an involutive real-field automorphism, $z\bar{z}=\mathrm{\mid }z{\mathrm{\mid }}^2$, and modulus is definite, multiplicative, and subadditive), a sum of nonnegative real numbers, so $⟨f,f⟩\ge 0$. For the vanishing clause, reindex by the standard representatives to identify this group sum of the real family $x\mapsto \mathrm{\mid }f(x){\mathrm{\mid }}^2$ with the sequential real sum ${\sum }_{x=0}^{N-1}\mathrm{\mid }f([x{]}_N){\mathrm{\mid }}^2$ (Finite sums and finite products, by recursion, Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule); by claim 4 of Laws of finite sums and finite products a finite sum of nonnegative reals vanishes only if every term vanishes, and $\mathrm{\mid }f([x{]}_N){\mathrm{\mid }}^2=0$ happens exactly when $f([x{]}_N)=0$ (Conjugation is an involutive real-field automorphism, $z\bar{z}=\mathrm{\mid }z{\mathrm{\mid }}^2$, and modulus is definite, multiplicative, and subadditive). Since every class of $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ is $[x{]}_N$ for some $0\le x<N$, this forces $f=0$.

This is the pairing induced by the counting set function on the finite set $\mathbb{Z}\mathrm{/}N\mathbb{Z}$, which weights a finite set by its cardinality and therefore gives weight $1$ to each point (Counting measure on an arbitrary set). No factor $1\mathrm{/}N$ is inserted anywhere in the definition; a normalisation constant is carried by the transform, not by the pairing.

• Why the counting normalisation and not $(1\mathrm{/}N)$-counting. Taylor's (11.5) weights the function space on ${\mathrm{\Gamma }}_n$ by $(1\mathrm{/}n)$-times counting measure and the space on ${\mathbb{Z}}_n$ by counting measure, matching the factor $1\mathrm{/}n$ carried by his forward transform (11.1); this page uses the counting pairing on both sides and puts the constant $N^{-1\mathrm{/}2}$ in the transform. Under the identification ${\omega }^j\leftrightarrow [j{]}_N$ the two conventions are related by $f^{\mathrm{\#}}=N^{-1\mathrm{/}2}{\mathcal{F}}_{N}f$, a relabelling of the same finite sums, not a change of the mathematics.

Let $N\ge 1$ and let ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ be the complex vector space of functions on the finite group $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (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\}$). For $f,g\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ the cyclic convolution of $f$ and $g$, unnormalised, is the function $f\ast g:\mathbb{Z}\mathrm{/}N\mathbb{Z}\to \mathbb{C}$ defined for $x\in \mathbb{Z}\mathrm{/}N\mathbb{Z}$ by

$(f\ast g)(x):={\sum }_{y\in \mathbb{Z}\mathrm{/}N}f(y)g(x-y),$

where $x-y$ is the group operation of $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (For every natural $n$, $(\mathbb{Z}\mathrm{/}n,+)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold) and the sum is the finite sum in the additive commutative monoid of $\mathbb{C}$ over the finite index set $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (A finite sum in a commutative monoid indexed by an arbitrary finite set). No factor $1\mathrm{/}N$ or $1\mathrm{/}\sqrt{N}$ is inserted, and this unnormalised convention is the one used throughout the page.

Well-definedness. The standard-representatives bijection gives $\mathrm{\mid }\mathbb{Z}\mathrm{/}N\mathbb{Z}\mathrm{\mid }=N$ (For $n\ge 1$, every class in $\mathbb{Z}\mathrm{/}n$ has one representative $r$ with $0\le r<n$, so $\mid \mathbb{Z}\mathrm{/}n\mid =n$; while $\mathbb{Z}\mathrm{/}0$ is in bijection with $\mathbb{Z}$). For fixed $x$, $f(y)$ and $g(x-y)$ are values at classes, so the finite sum of the complex family $y\mapsto f(y)g(x-y)$ is a single complex number (A finite sum in a commutative monoid indexed by an arbitrary finite set). Thus $x\mapsto (f\ast g)(x)$ is a well-defined function $\mathbb{Z}\mathrm{/}N\mathbb{Z}\to \mathbb{C}$.

The operation is commutative. Fix $x\in \mathbb{Z}\mathrm{/}N\mathbb{Z}$ and let $h:\mathbb{Z}\mathrm{/}N\mathbb{Z}\to \mathbb{Z}\mathrm{/}N\mathbb{Z}$ be $h(y):=x-y$; then $h(h(y))=x-(x-y)=y$, so $h$ is its own two-sided inverse and hence a bijection (Injection, surjection, bijection, For every natural $n$, $(\mathbb{Z}\mathrm{/}n,+)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold). Reindexing the finite sum along a bijection (Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule, part 1) with the substitution $z:=x-y$ gives

$(f\ast g)(x)={\sum }_{y\in \mathbb{Z}\mathrm{/}N}f(y)g(x-y)={\sum }_{z\in \mathbb{Z}\mathrm{/}N}f(x-z)g(z)={\sum }_{z\in \mathbb{Z}\mathrm{/}N}g(z)f(x-z)=(g\ast f)(x),$

the middle equality being commutativity of multiplication in $\mathbb{C}$ ($\mathbb{C}=\mathbb{R}[x]\mathrm{/}(x^2+1)$ is a field, every element is uniquely $a+bi$, and every nonzero element has inverse $(a-bi)\mathrm{/}(a^2+b^2)$). Hence $f\ast g=g\ast f$.

Attached to the finite set $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ is its counting set function, which gives weight $1$ to each point (Counting measure on an arbitrary set); the displayed sum is the convolution of $f$ and $g$ against that weight on the finite group. This cyclic convolution is a different operation from the linear convolution of finite sequences of coefficients, which agrees with it only after the sequences are padded with enough zeros; the companion page exhibits the wrap that occurs without such padding, and the transform law proved later on this page computes the cyclic, not the linear, convolution.

• The factor that this convention costs. Because no normalisation is built into $\ast$, the unitary transform of this page does not turn $\ast$ into an unadorned pointwise product: the transform law later on this page carries a factor $\sqrt{N}$. That factor is not an artefact of the proof but the exact price of leaving the convolution unnormalised, and it is recorded here once so that no later item silently mixes the two conventions.

• Cyclic convolution as reduction of polynomial products. Writing a function on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ as the coefficient list of a residue-class polynomial identifies $(f\ast g)(x)$ with the coefficient of $z^x$ in the product of the two polynomials taken modulo $z^N-1$: exponents add under the group operation and are reduced modulo $N$. This is the viewpoint of Taylor's (11.30)–(11.33) and of the MIT lecture, and it is what makes the diagonalisation of $\ast$ by the discrete Fourier transform the discrete analogue of the Fourier-multiplier calculus.

Let $N\ge 1$ and let ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ be the complex vector space of all functions $\mathbb{Z}\mathrm{/}N\mathbb{Z}\to \mathbb{C}$ (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\}$, Vector space over a field). For $f\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ define the unitary discrete Fourier transform ${\mathcal{F}}_{N}f:\mathbb{Z}\to \mathbb{C}$ by

$({\mathcal{F}}_{N}f)(k):=N^{-1\mathrm{/}2}{\sum }_{x=0}^{N-1}f([x{]}_N)e^{-2\pi ikx\mathrm{/}N},k\in \mathbb{Z},$

where $[x{]}_N$ is the class of the integer $x$ in $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (The congruence class $[a{]}_n$ and the quotient set $\mathbb{Z}\mathrm{/}n$, Congruence modulo every integer is an equivalence relation on $\mathbb{Z}$), $e^z=\exp z$ is the complex exponential (The complex exponential by its power series), and $N^{-1\mathrm{/}2}$ is the rational power of the positive real $N$ (Rational powers $a^r$ of a positive base, Laws of rational exponents), read in $\mathbb{C}$ through the embedded copy of $\mathbb{R}$ ($\mathbb{C}=\mathbb{R}[x]\mathrm{/}(x^2+1)$ is a field, every element is uniquely $a+bi$, and every nonzero element has inverse $(a-bi)\mathrm{/}(a^2+b^2)$).

The summands depend only on classes, and the transform is periodic in $k$. Each summand $f([x{]}_N)e^{-2\pi ikx\mathrm{/}N}$ is a complex number determined by the class $[x{]}_N$ and the integer $k$, and the classes $[0{]}_N,\dots ,[N-1{]}_N$ are pairwise distinct and exhaust $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (For $n\ge 1$, every class in $\mathbb{Z}\mathrm{/}n$ has one representative $r$ with $0\le r<n$, so $\mid \mathbb{Z}\mathrm{/}n\mid =n$; while $\mathbb{Z}\mathrm{/}0$ is in bijection with $\mathbb{Z}$); so the display is the finite sum, over the finite group, of the family $x\mapsto f(x)N^{-1\mathrm{/}2}{e}^{-2\pi ikx\mathrm{/}N}$, and reindexing by any other representative list leaves it unchanged (Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule, part 1). Reindexing by the transition $x\mapsto x+N$ uses $e^{-2\pi ik(x+N)\mathrm{/}N}=e^{-2\pi ikx\mathrm{/}N}{e}^{-2\pi ik}$ and $e^{-2\pi ik}=1$ for every integer $k$, because $-2\pi k\in 2\pi \mathbb{Z}$ ($\exp (z+w)=\exp z\exp w$, and the complex exponential extends the real exponential, $\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$). For periodicity in $k$, the same two facts give $e^{-2\pi i(k+N)x\mathrm{/}N}=e^{-2\pi ikx\mathrm{/}N}{e}^{-2\pi ix}=e^{-2\pi ikx\mathrm{/}N}$ for every integer $x$, so $({\mathcal{F}}_{N}f)(k+N)=({\mathcal{F}}_{N}f)(k)$ for every $k\in \mathbb{Z}$ ($\exp (z+w)=\exp z\exp w$, and the complex exponential extends the real exponential, $\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$). Consequently ${\mathcal{F}}_{N}f$ factors through the quotient $\mathbb{Z}\to \mathbb{Z}\mathrm{/}N\mathbb{Z}$ and is a well-defined function on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$, and ${\mathcal{F}}_N$ is a map ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}\to {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$.

Form in terms of characters. Define ${\chi }_k([m]):=\exp (2\pi ikm\mathrm{/}N)$ for $k,m\in \mathbb{Z}$. The assignment is well defined on classes because replacing $m$ by $m+N$ multiplies the exponential by $e^{2\pi ik}=1$ ($\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$); it is multiplicative, ${\chi }_k(x+y)={\chi }_k(x){\chi }_k(y)$, by the addition law ($\exp (z+w)=\exp z\exp w$, and the complex exponential extends the real exponential); and it takes values of modulus $1$, since $\mathrm{\mid }\exp (i\theta )\mathrm{\mid }=1$ ($\exp (x+iy)=e^x(\cos y+i\sin y)$, $\mathrm{\mid }\exp (x+iy)\mathrm{\mid }=e^x$, and $e^{i\pi }+1=0$). Thus the ${\chi }_k$ are characters of the finite group $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (homomorphisms into the unit circle; no continuity is required on a discrete group), and the definition reads

$({\mathcal{F}}_{N}f)(k)=N^{-1\mathrm{/}2}{\sum }_{x\in \mathbb{Z}\mathrm{/}N}f(x){\chi }_{-k}(x),$

with the positive-sign transform obtained by replacing $k$ with $-k$. This fixes the negative-sign, $N^{-1\mathrm{/}2}$-normalised convention of the whole page: the forward transform carries the minus sign in the exponent and the factor $N^{-1\mathrm{/}2}$, and the inverse transform of the inversion theorem carries the plus sign with the same factor. A different, unnormalised convention is introduced later on this page for the algorithmic part; the two are related by a single explicit rescaling recorded there.

Linearity, recorded for later use. For $a,b\in \mathbb{C}$ and $f,g\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ one has ${\mathcal{F}}_N(af+bg)=a{\mathcal{F}}_{N}f+b{\mathcal{F}}_{N}g$: the identity holds at each $k$ by distributivity in $\mathbb{C}$ ($\mathbb{C}=\mathbb{R}[x]\mathrm{/}(x^2+1)$ is a field, every element is uniquely $a+bi$, and every nonzero element has inverse $(a-bi)\mathrm{/}(a^2+b^2)$) and the elementary laws of finite sums over a fixed finite index set, which follow from the recursion clauses of A finite sum in a commutative monoid indexed by an arbitrary finite set by induction on an enumeration. Nothing else about ${\mathcal{F}}_N$ — unitarity, invertibility, the convolution law — is asserted here; those are proved in the items that follow.

• Why the normalisation is split as $N^{-1\mathrm{/}2}$. The factor $N^{-1\mathrm{/}2}$ is exactly what makes the transform an isometry for the counting inner product, and is the finite analogue of the $1\mathrm{/}\sqrt{2\pi }$ convention in the $L^2$ Fourier transform. Taylor writes the finite transform (11.1) with the factor $1\mathrm{/}n$ in the forward direction and weights $L^2({\mathrm{\Gamma }}_n)$ by $(1\mathrm{/}n)$-counting measure; the two descriptions differ by relabelling the sides, not by mathematics, and the translation used here sends ${\omega }^j$ to $[j{]}_N$ and $f^{\mathrm{\#}}$ to $N^{-1\mathrm{/}2}{\mathcal{F}}_{N}f$.

• No convergence hypothesis is needed or used. The index set is finite, so the definition involves no limit, no summability condition and no auxiliary topology; it applies to every function in ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$, including the zero function, and it is total at $N=1$, where the single summand is $f([0{]}_1)e^0=f([0{]}_1)$ with coefficient $1^{-1\mathrm{/}2}=1$.

Let $N\ge 1$ and let $k,\mathrm{\ell }\in \mathbb{Z}$. Then

${\sum }_{x=0}^{N-1}{e}^{2\pi i(k-\mathrm{\ell })x\mathrm{/}N}=\{\begin{array}{ll}N,& k\equiv \mathrm{\ell }(\mathrm{m}\mathrm{o}\mathrm{d}N),\\ \\ 0,& k\equiv ̸\mathrm{\ell }(\mathrm{m}\mathrm{o}\mathrm{d}N)\mathrm{.}\end{array}$

At $N=1$ the congruence holds for all $k,\mathrm{\ell }$ and the sum is $1$. The sum is the finite sum of the complex family $x\mapsto e^{2\pi i(k-\mathrm{\ell })x\mathrm{/}N}$ over the von Neumann natural $N=\{0,\dots ,N-1\}$ (A finite sum in a commutative monoid indexed by an arbitrary finite set), and $N$ on the right is the natural number $N$ read in $\mathbb{C}$ as the additive multiple $N\cdot 1_{\mathbb{C}}$, that is, the value at $N$ of the canonical embedding $\mathbb{N}\to \mathbb{C}$ (The canonical natural $\iota (n)=n\cdot 1_F$ of a field, In a field, the additive multiple $n\cdot 1_F$ is the canonical natural $\iota (n)$: the additive power of the group-power definition and the canonical natural are the same function, both being the unique one given by the recursion $\iota (0)=0_F$, $\iota (\sigma (n))=\iota (n)+1_F$).

• The case ${\omega }^m=1$ is exactly the case split used by Taylor. In Taylor's proof of Proposition 11.2 the sum $S_m$ of the powers of $\omega$ satisfies $S_m={\omega }^m{S}_m$, so it vanishes whenever ${\omega }^m\mathrm{\ne }1$; the coincident case ${\omega }^m=1$ is separated first. Here the split is made on $k\equiv \mathrm{\ell }(\mathrm{m}\mathrm{o}\mathrm{d}N)$ and the noncoincident case is settled by the geometric identity, which is the same computation in explicit finite-sum form.

• No dependence on the representation-theoretic orthogonality. The published orthogonality lemma for finite abelian groups and the real-variable factorisation lemma for $b^n-a^n$ are stated outside the complex-sum setting used here, so this lemma proves the complex geometric identity directly from the recursion instead of importing them. They are independent cross-checks, not prerequisites.

Let $N\ge 1$ and $f\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$. Define the reflection $Rf$ by $(Rf)(x):=f(-x)$ for $x\in \mathbb{Z}\mathrm{/}N\mathbb{Z}$. Then ${\mathcal{F}}_N^{2}f=Rf$ and ${\mathcal{F}}_N^4=\mathrm{i}\mathrm{d}$, the identity map of ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$; consequently ${\mathcal{F}}_N^2$ is an involution and ${\mathcal{F}}_N^3={\mathcal{F}}_N^{-1}$. At $N=1$ and $N=2$ the reflection is the identity, so ${\mathcal{F}}_N^2=\mathrm{i}\mathrm{d}$ there. No convergence or regularity hypothesis is involved: the transform is a finite sum (The unitary discrete Fourier transform on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$).

• The two involution cases. At $N=1$ the group $\mathbb{Z}\mathrm{/}1$ has one element, so $-x=x$ and the reflection is the identity. At $N=2$ the element $[1]$ satisfies $[1]+[1]=[0]$, so $-[1]=[1]$ and $-[0]=[0]$; the reflection is the identity there too and ${\mathcal{F}}_2^2=\mathrm{i}\mathrm{d}$, consistent with the fact that the $N=2$ matrix $\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ \\ 1& -1\end{array}\right)$ is its own inverse. Both claims use only the group law of For every natural $n$, $(\mathbb{Z}\mathrm{/}n,+)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold.

• What this identity is not. It is a statement about the finite transform and its exponent bookkeeping only. In particular it does not assert that ${\mathcal{F}}_N$ has order four in general, and it does not identify the reflection with the identity for $N\ge 3$: for $N=3$ the reflection exchanges the classes $[1]$ and $[2]$ and is not the identity, while it still satisfies $R^2=\mathrm{i}\mathrm{d}$.

Let $N\ge 1$ and $f,g\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$. Then for every $k\in \mathbb{Z}$

$({\mathcal{F}}_N(f\ast g))(k)=\sqrt{N}({\mathcal{F}}_{N}f)(k)({\mathcal{F}}_{N}g)(k),$

where $\ast$ is the unnormalised cyclic convolution of The unnormalised cyclic convolution on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ and $\sqrt{N}=N^{1\mathrm{/}2}$ is the rational power of Rational powers $a^r$ of a positive base. The factor $\sqrt{N}$ is the price of leaving the convolution unnormalised; it is not an artefact of the proof, and the same factor appears for every pair $(f,g)$.