Finite Abelian Fourier Analysis

Put $n:=\mathrm{ord}(x)\ge 1$. By [F1] and [F3], $\chi (x{)}^n=\chi (nx)=\chi (0)=1$, with $\chi (0)=1$ by [F2].

By [F4], $\chi (x)=\exp (2\pi ik\mathrm{/}n)$ for some $0\le k<n$. Therefore [F5] gives $\mathrm{\mid }\chi (x)\mathrm{\mid }=1$. The argument includes $x=0$, for which $n=1$ and $\chi (0)=1$.

If $\chi \in \widehat{C_n}$ as defined in [F4], then $\chi (g{)}^n=\chi (ng)=\chi (0)=1$ by [F1] and the given relation $ng=0$, so evaluation at $g$ maps this character set into the set in [F3]. Every element is $jg$ by [F2], and [F1] gives $\chi (jg)=\chi (g{)}^j$; thus evaluation at $g$ is injective.

Conversely, for each $n$th root of unity $z$, define ${\chi }_z(jg):=z^j$ for $j\in \mathbb{Z}$. If $jg=kg$, [F2] gives $j-k=qn$ for some integer $q$, so $z^j=z^k(z^n{)}^q=z^k$ by [F3, F5]; hence the value is well defined. Also ${\chi }_z(jg+kg)=z^{j+k}={\chi }_z(jg){\chi }_z(kg)$ by [F5], so ${\chi }_z$ is an additive character in [F4], and ${\chi }_z(g)=z$.

Steps 1.1 and 1.2 make evaluation at $g$ a bijection from the character set [F4] to the $n$ distinct roots in [F3]. This also covers $n=1$: the quotient is trivial and the sole root is $1$. Therefore $\mathrm{\mid }\widehat{C_n}\mathrm{\mid }=n$.

For $\chi \in \widehat{P}$ as defined in [F4], put ${\chi }_i(g_i):=\chi (0,\dots ,0,g_i,0,\dots ,0)$. The coordinate embedding preserves addition by the componentwise operation in [F2], so [F1] shows each ${\chi }_i$ is a character.

For a tuple $({\chi }_i)$, define $\sigma (({\chi }_i))(g_1,\dots ,g_r):={\prod }_i{\chi }_i(g_i)$. The componentwise operation and each homomorphism law give $\sigma (({\chi }_i))(g+h)=\sigma (({\chi }_i))(g)\sigma (({\chi }_i))(h)$, so this is a character of $P$.

Restricting $\sigma (({\chi }_i))$ to the $i$th coordinate gives ${\chi }_i$, because all other coordinates are zero and every character takes the identity to $1$. Thus restriction after $\sigma$ is the identity on the product of duals.

Every $(g_1,\dots ,g_r)$ is the sum of its coordinate vectors. Applying a homomorphism $\chi$ to this sum gives $\chi (g_1,\dots ,g_r)={\prod }_i{\chi }_i(g_i)$, so $\sigma$ after restriction is the identity on $\widehat{P}$. For $r=0$, the sole group element and sole character give the stated singleton bijection.

Steps 2.1 and 2.2 show the two displayed maps are inverse bijections between the character sets in [F4], including the empty-product case.

If the invariant-factor list is empty, [F1] identifies $G$ with the trivial group, which is cyclic of order $1$. By [F3] it has one character and one element, so $\mathrm{\mid }\widehat{G}\mathrm{\mid }=\mathrm{\mid }G\mathrm{\mid }=1$ for the character set in [F8].

Otherwise fix one isomorphism $\phi :G\to P$, where $P=C_{n_1}\times \cdots \times C_{n_r}$ is the finite iterated product. By [F6] and [F7], both $\phi$ and ${\phi }^{-1}$ are group homomorphisms. Thus $\chi \mapsto \chi \circ {\phi }^{-1}$ and $\psi \mapsto \psi \circ \phi$ preserve the character sets in [F8] and are inverse bijections between $\widehat{G}$ and $\widehat{P}$.

By [F2], $\widehat{P}$ is in bijection with ${\prod }_i\widehat{C_{n_i}}$. Each factor has $n_i$ elements by [F3], and repeated application of [F5] to the finite Cartesian products gives $\mathrm{\mid }\widehat{P}\mathrm{\mid }={\prod }_i{n}_i$.

The same repeated product-order formula gives $\mathrm{\mid }P\mathrm{\mid }={\prod }_i{n}_i$ by [F4]; the isomorphism in step 1.2 preserves finite cardinality by [F6]. Hence $\mathrm{\mid }G\mathrm{\mid }={\prod }_i{n}_i=\mathrm{\mid }\widehat{G}\mathrm{\mid }$.

For $\chi ,\psi \in \widehat{G}$, $x,y\in G$, and pointwise product as in [F1], $(\chi \psi )(x+y)=\chi (x)\chi (y)\psi (x)\psi (y)=\chi (x)\psi (x)\chi (y)\psi (y)$ by commutativity in [F2]. Thus $\chi \psi$ is again a homomorphism. The constant-one function is a homomorphism because it sends every sum to $1\cdot 1=1$; [F3] also confirms each character takes the identity to $1$.

The pointwise inverse is a homomorphism because $(\chi (x+y){)}^{-1}=(\chi (x)\chi (y){)}^{-1}=\chi (x{)}^{-1}\chi (y{)}^{-1}$ in the abelian group ${\mathbb{C}}^{\times }$. Associativity and commutativity of pointwise product, its identity law, and the inverse laws follow by evaluating at each $x$ and using the corresponding laws in [F2]. Hence $\widehat{G}$ is an abelian group.

The dual is finite by [F4], and its order is $\mathrm{\mid }G\mathrm{\mid }$ by the same result. Thus it is a finite abelian group of the asserted order.

If $G$ is trivial, every additive character sends its identity to $1$ by [F7], so [F10] makes the character set a singleton; the sum is $1=\mathrm{\mid }G\mathrm{\mid }$ and the formula holds. Otherwise fix an invariant-factor isomorphism $\phi :G\to P={\prod }_i{C}_{n_i}$ from [F1]. By [F8] and [F9], composition with $\phi$ and ${\phi }^{-1}$ gives inverse bijections of the character sets [F10], taking $x,y$ to $a=\phi (x),b=\phi (y)$. Thus it suffices to compute the sum for $P$.

In each cyclic factor write $a_i=r_i{g}_i$ and $b_i=s_i{g}_i$, with $0\le r_i,s_i<n_i$. By [F3] and [F7], a character whose value on $g_i$ is ${\omega }_{n_i}^k$ has values ${\omega }_{n_i}^{k{r}_i}$ and ${\omega }_{n_i}^{k{s}_i}$ on $a_i$ and $b_i$. By [F4], $\mathrm{\mid }{\omega }_{n_i}\mathrm{\mid }=1$, so $\overline{{\omega }_{n_i}^{k{s}_i}}={\omega }_{n_i}^{-k{s}_i}$. The character-indexed sum in this coordinate is therefore ${\sum }_{k=0}^{n_i-1}{\omega }_{n_i}^{k(r_i-s_i)}$. If $r_i=s_i$ modulo $n_i$, this equals $n_i$. Otherwise $q:={\omega }_{n_i}^{r_i-s_i}\mathrm{\ne }1$ by distinctness of the roots in [F3], and $q^{n_i}=1$, so ${\sum }_{k=0}^{n_i-1}{q}^k=(1-q^{n_i})\mathrm{/}(1-q)=0$ by the geometric-sum identity. For $n_i=1$ the first case applies and the sum is $1$.

Under the product-character bijection, finite-sum factorization [F5] makes the sum over $\widehat{P}$ the product of these cyclic sums. It is therefore ${\prod }_i{n}_i$ exactly when every coordinate of $a$ equals the corresponding coordinate of $b$, and is zero otherwise.

The coordinate map $\phi$ is injective, so all coordinates agree exactly when $x=y$; and [F1] gives $\mathrm{\mid }G\mathrm{\mid }=\mathrm{\mid }P\mathrm{\mid }={\prod }_i{n}_i$. The empty product case was handled in step 1.1. This proves the formula.

By [F1] the quotient is defined; [F2] gives its group law, and [F3] makes $Q:=G\mathrm{/}H$ finite abelian. Finiteness also follows from the finite coset partition in [F6].

Let $\pi :G\to Q$ be $\pi (g)=g+H$. The quotient law in [F2] gives $\pi (g+g^{\mathrm{\prime }})=(g+H)+(g^{\mathrm{\prime }}+H)=\pi (g)+\pi (g^{\mathrm{\prime }})$, so $\pi$ is a homomorphism. For $h\in H$, $\pi (h)=H$, the identity coset; every character sends the identity to $1$. Thus for $\psi \in \widehat{Q}$, $\psi \circ \pi$ is a character by [F8] and is trivial on $H$, so [F9] shows inflation maps $\widehat{Q}$ into $H^{\perp }$.

For $\chi \in H^{\perp }$, define $\tilde{\chi }(g+H):=\chi (g)$. If $g+H=g^{\mathrm{\prime }}+H$, [F4] gives $g^{\mathrm{\prime }}-g\in H$, hence $\chi (g^{\mathrm{\prime }})=\chi (g)\chi (g^{\mathrm{\prime }}-g)=\chi (g)$; so $\tilde{\chi }$ is well defined. For cosets $g+H,g^{\mathrm{\prime }}+H$, the quotient law [F2] gives $\tilde{\chi }((g+H)+(g^{\mathrm{\prime }}+H))=\chi (g+g^{\mathrm{\prime }})=\chi (g)\chi (g^{\mathrm{\prime }})$, so $\tilde{\chi }$ is a character of $Q$.

For every $g\in G$, $(\tilde{\chi }\circ \pi )(g)=\tilde{\chi }(g+H)=\chi (g)$; for every $\psi \in \widehat{Q}$ and coset $g+H$, descent of its inflation returns $\widetilde{(\psi \circ \pi )}(g+H)=(\psi \circ \pi )(g)=\psi (g+H)$. Thus inflation and descent are inverse bijections. Since $Q$ is finite abelian by step 1.1, [F10] supplies an invariant-factor decomposition of $Q$, with the empty list allowed when $Q$ is trivial. Applying [F5] to this decomposition gives $\mathrm{\mid }{H}^{\perp }\mathrm{\mid }=\mathrm{\mid }\widehat{Q}\mathrm{\mid }=\mathrm{\mid }Q\mathrm{\mid }$, and by [F2], $\mathrm{\mid }Q\mathrm{\mid }=[G:H]$.

Lagrange [F6] gives $\mathrm{\mid }G\mathrm{\mid }=[G:H]\mathrm{\mid }H\mathrm{\mid }$. Combining with step 2.1 gives $\mathrm{\mid }{H}^{\perp }\mathrm{\mid }\mathrm{\mid }H\mathrm{\mid }=\mathrm{\mid }G\mathrm{\mid }$, and division by the positive integer $\mathrm{\mid }H\mathrm{\mid }$ from [F7] gives $\mathrm{\mid }{H}^{\perp }\mathrm{\mid }=\mathrm{\mid }G\mathrm{\mid }\mathrm{/}\mathrm{\mid }H\mathrm{\mid }$.

The trivial character is in $H^{\perp }$. If $\chi ,\psi \in H^{\perp }$ and $h\in H$, then $(\chi \psi )(h)=\chi (h)\psi (h)=1$, and ${\chi }^{-1}(h)=\chi (h{)}^{-1}=1$. Thus $H^{\perp }$ contains the identity and is closed under pointwise product and inverse in the group $\widehat{G}$.

The identity $0$ of $G$ lies in $K^{\perp }$ by [F3]. If $g,h\in K^{\perp }$, then for every $\chi \in K$, $\chi (g+h)=\chi (g)\chi (h)=1$ and $\chi (-g)=\chi (g{)}^{-1}=1$. Therefore $K^{\perp }$ is closed under addition and inverses in $G$.

By the subgroup criterion in [F2], steps 1.1 and 1.2 show respectively that $H^{\perp }\le \widehat{G}$ and $K^{\perp }\le G$.

By [F1], the transform acts on a function $f$ by the coefficient formula defining $U$. By [F2], its row and column index sets have equal finite cardinality, so $U$ is square.

For $x,y\in G$, the $(x,y)$ entry of $U^{\ast }U$ is $N_{\mathbb{R}}^{-1}{\sum }_{\chi \in \widehat{G}}\chi (x)\overline{\chi (y)}$, because [F6] gives $(N_{\mathbb{R}}^{-1\mathrm{/}2}{)}^2=N_{\mathbb{R}}^{-1}$. By [F4], this is $1$ when $x=y$ and $0$ otherwise, exactly the entry of $I_G$. Hence $U^{\ast }U=I_G$.

For $\chi ,\psi \in \widehat{G}$, the $(\chi ,\psi )$ entry of $U{U}^{\ast }$ is $N_{\mathbb{R}}^{-1}{\sum }_{x\in G}\overline{\chi (x)}\psi (x)$. By [F6] and [F3], this is $1$ when $\chi =\psi$ and $0$ otherwise, exactly the entry of $I_{\widehat{G}}$. Hence $U{U}^{\ast }=I_{\widehat{G}}$.

By [F1], the action of this coefficient matrix on the function values of any $f\in {\mathbb{C}}^G$ is exactly $F_{G}f$. The two identities in steps 1.2 and 1.3 therefore prove the asserted unitarity of the transform as defined here.

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

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\ast g)(\chi )=N_{\mathbb{R}}^{-1\mathrm{/}2}{\sum }_{x,y}f(x)g(y)\overline{\chi (x)}\overline{\chi (y)}=N_{\mathbb{R}}^{-1\mathrm{/}2}({\sum }_{x}f(x)\overline{\chi (x)})({\sum }_{y}g(y)\overline{\chi (y)})$.

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

For each $g\in G$, evaluation on the dual group [F7] is a character: if $\chi ,\psi \in \widehat{G}$, then $\mathrm{ev}(g)(\chi \psi )=\chi (g)\psi (g)=\mathrm{ev}(g)(\chi )\mathrm{ev}(g)(\psi )$. Thus $\mathrm{ev}(g)\in \widehat{\widehat{G}}$.

If $G$ is nontrivial, fix the isomorphism $\phi :G\to {\prod }_i{C}_{n_i}$ from [F3]. For any nonzero $g$, some coordinate is $\phi (g{)}_j=[m]$ with $1\le m<n_j$. In the product, the character trivial on every coordinate except $j$, with generator value ${\omega }_{n_j}$ on that factor, exists by [F4]. Its composite $\chi$ with $\phi$ is a character of $G$ and satisfies $\chi (g)={\omega }_{n_j}^m\mathrm{\ne }1$, because the listed $n_j$ roots are distinct and $m$ is nonzero modulo $n_j$. Thus every nonzero element is detected by a character. The trivial-group case has no nonzero element and satisfies this statement vacuously.

Evaluation is a homomorphism from $G$ to the pointwise group $\widehat{\widehat{G}}$, since for every $\chi$, $\mathrm{ev}(g+h)(\chi )=\chi (g+h)=\chi (g)\chi (h)=(\mathrm{ev}(g)\mathrm{ev}(h))(\chi )$.