Fourier analysis on finite abelian groups

Lesson HA-LCA-01. This lesson proves finite character duality, Fourier formulas, Poisson summation, uncertainty and Gauss-sum identities. Self-checked by the writing AI.

Written by GPT-6 Astra (OpenAI), Ultra, 4 October 2026. The exposition and proofs below are newly written; the free source readings are identified at the end. Earlier programme proofs retain their own stated licences.

Throughout, $G$ is a finite abelian group, written additively, and $N=|G|$. Its topology is discrete. A character is a homomorphism $\chi:G\to\mathbb T=\{z\in\mathbb C:|z|=1\}$; characters form the group $\widehat G$ under pointwise multiplication. Write $\widehat f(\chi)=\sum_{x\in G}f(x)\overline{\chi(x)},\qquad (f*g)(x)=\sum_{y\in G}f(y)g(x-y). \tag{1}$ Thus the measure on $G$ is counting measure. The inverse transform will put mass $1/N$ at each point of the dual.

Only the elementary real and complex analysis proved in the Banach-algebra prerequisite, Lemmas 1.1–1.3, is imported. In particular, that reading constructs $\exp(it)$, a quarter-period $\alpha=\pi/2$ with $\exp(i\alpha)=i$, and its positive cosine on $[0,\alpha)$. All finite group and polynomial facts required below are proved here.

0. Roots and finite groups

Lemma 0.0. A subgroup's order divides the finite group's order, and the order of each element divides the group's order.

Proof. For a subgroup $H\le G$, its cosets partition $G$: intersecting cosets coincide by subtracting a shared element. Translation is a bijection from $H$ to each coset. Consequently $|G|=|H|\,|G/H|.$ If $x\in G$, some positive multiple is zero because two members of the list $0,x,2x,\ldots$ coincide. The least such positive integer $d$ is its order; division with remainder shows that $kx=0$ exactly when $d\mid k$. Its generated subgroup has $d$ elements, so $d\mid N$. $\square$

Lemma 0.1. Put $E(t)=\exp(2\pi it)$. Then $E(\mathbb R)=\mathbb T$, its kernel is $\mathbb Z$, and every $w\in\mathbb T$ has exactly $n$ distinct $n$-th roots. The $n$-th roots of one form the cyclic group $\mu_n=\{E(k/n):0\le k<n\}$. Every finite subgroup of $\mathbb T$ is cyclic.

Proof. In the earlier construction, $s(t)=\operatorname{Im}\exp(it)$ has derivative $c(t)>0$ on $[0,\alpha)$. The integral of this positive derivative on any nondegenerate subinterval is positive. Thus $s$ increases continuously from zero to one on $[0,\alpha]$. The identity $c^2+s^2=1$ and $c\ge0$ show that this path reaches each point of the closed first quadrant of the circle exactly once. Multiplication by $i$ supplies the other quadrants. The same sign information shows that $\exp(it)=1$ only at $t=0$ in $0\le t<4\alpha$. Periodicity now gives both assertions about $E$.

If $w=E(t)$, the solutions of $z^n=w$ are exactly $E((t+k)/n)$, $0\le k<n$, because every $z$ is an $E(u)$ and $nu-t\in\mathbb Z$. They are distinct by the kernel assertion.

Let $S\le\mathbb T$ have $m$ elements. The coset argument above gives $z^m=1$ for every $z\in S$, so $S\le\mu_m$. Under $k\mapsto E(k/m)$, the inverse image of $S$ in $\mathbb Z$ is a subgroup containing $m\mathbb Z$. Choose its smallest positive element $d$. Division with remainder makes every member a multiple of $d$; in particular $d\mid m$. Thus $S$ is generated by $E(d/m)$. $\square$

1. Extending and counting characters

Theorem 1.1. Every character of $H\le G$ extends to $G$, and it has exactly $|G/H|$ extensions. In particular $|\widehat G|=N$, and characters separate points.

Proof. Choose $y\notin H$, and let $d$ be the order of $y+H$ in $G/H$. Every element of $H+\mathbb Zy$ is $h+ky$. Choose $z\in\mathbb T$ with $z^d=\chi(dy)$, and set $\widetilde\chi(h+ky)=\chi(h)z^k.$ If $h+ky=h'+k'y$, then $k-k'=qd$ for an integer $q$, and $h'-h=qdy$. Hence $\chi(h')z^{k'}=\chi(h)\chi(dy)^qz^{k'}=\chi(h)z^k$. The definition is independent of the expression, and addition of two expressions proves its homomorphism law. Every extension must have this form, determined by its value $z$ at $y$. Lemma 0.1 gives exactly $d$ choices.

Adjoin elements until reaching $G$. The process stops because the subgroup size strictly increases. The product of the successive indices telescopes to $|G/H|$, and each extension at one stage has exactly the next index many extensions. This proves the count and existence. Taking $H=\{0\}$ proves $|\widehat G|=N$.

For $x\ne0$ of order $d>1$, the character $kx\mapsto E(k/d)$ of $\langle x\rangle$ extends to $G$ and is nontrivial at $x$. Apply this to $x-y$ to separate any two distinct points. $\square$

Theorem 1.2. Every finite abelian group is a product of cyclic groups. Its dual is isomorphic to it, with the isomorphism depending on the chosen cyclic coordinates.

Proof. Suppose $G\ne\{0\}$, and choose $a$ of largest possible order $m$. Extend the character $ka\mapsto E(k/m)$ to a character $\chi$ of $G$, using Theorem 1.1. Its finite image is cyclic by Lemma 0.1 and contains $\mu_m$. Choose $b\in G$ whose character value generates that image. The order of $\chi(b)$ is at most the order of $b$, hence at most $m$, while the image already has at least $m$ elements. Thus its image is exactly $\mu_m$.

Let $K=\ker\chi$. The intersection $K\cap\langle a\rangle$ is zero. For any $x$, choose $j$ with $\chi(x)=\chi(ja)$; then $x-ja\in K$. Consequently $(k,ja)\mapsto k+ja$ is a bijective homomorphism $K\times\langle a\rangle\to G$. Since $|K|=N/m<N$, induction on group size gives the cyclic decomposition, including the empty product for the trivial group.

For $\mathbb Z/n\mathbb Z$, the characters are exactly $\chi_k(x)=E(kx/n)$: their value at $1$ is an $n$-th root of one and determines all values. The rule $k\mapsto\chi_k$ is a bijective homomorphism. For $A\times B$, restriction to the two axes gives a bijection $\widehat{A\times B}\longrightarrow\widehat A\times\widehat B, \quad \chi\longmapsto(\chi|_A,\chi|_B);$ its inverse sends $(\eta,\theta)$ to $(a,b)\mapsto\eta(a)\theta(b)$. Both maps preserve multiplication. Applying these maps to the chosen decomposition proves $\widehat G\cong G$. $\square$

Theorem 1.3. Evaluation gives a canonical isomorphism $\alpha_G:G\longrightarrow\widehat{\widehat G},\qquad \alpha_G(x)(\chi)=\chi(x).$

Proof. Pointwise multiplication shows that each evaluation is a character, and the character law shows that $\alpha_G$ is a homomorphism. Its kernel is zero by separation. Theorem 1.1 applied twice gives $|\widehat{\widehat G}|=|G|$, so the injection is surjective. No choices enter its definition. More precisely, if $u:G\to K$ is a homomorphism and $\widehat u(\eta)=\eta\circ u$, then $\alpha_G(x)(\widehat u(\eta))=\eta(u(x))=\alpha_K(u(x))(\eta)$. This is the naturality assertion. $\square$

2. Orthogonality and exact transform formulas

Theorem 2.1. The characters form an orthonormal basis for functions on $G$, with inner product $N^{-1}\sum_x f(x)\overline{g(x)}$. Explicitly, $\sum_x\chi(x)\overline{\psi(x)}=N\,1_{\{\chi=\psi\}},\qquad \sum_\chi\chi(x)\overline{\chi(y)}=N\,1_{\{x=y\}}. \tag{2}$

Proof. If a character $\theta$ is nontrivial, choose $a$ with $\theta(a)\ne1$. Translating the sum gives $\sum_x\theta(x)=\theta(a)\sum_x\theta(x)$, so it is zero. For the trivial character the sum is $N$. Taking $\theta=\chi\overline\psi$ proves the first formula. If $x\ne y$, separation gives $\eta(x-y)\ne1$. Multiplying each dual index by $\eta$ shows that the second sum equals $\eta(x-y)$ times itself, so is zero; at $x=y$ it has $N$ terms equal to one.

The second formula gives $\delta_y(x)=N^{-1}\sum_\chi\overline{\chi(y)}\chi(x)$. Every function is $\sum_y f(y)\delta_y$, so characters span. The first formula proves orthonormality and linear independence: inner product with each character recovers its coefficient. $\square$

Theorem 2.2. With convention (1), $f(x)=\frac1N\sum_\chi\widehat f(\chi)\chi(x),\qquad \sum_x f(x)\overline{g(x)} =\frac1N\sum_\chi\widehat f(\chi)\overline{\widehat g(\chi)}, \tag{3}$ and $\widehat{f*g}=\widehat f\,\widehat g$. In particular $\sum_x|f(x)|^2=N^{-1}\sum_\chi|\widehat f(\chi)|^2$.

Proof. Substitute the delta expansion from Theorem 2.1 in $f=\sum_y f(y)\delta_y$, interchange the finite sums, and obtain inversion. Substitute inversion for $f,g$ into their inner product; (2) eliminates unequal characters and gives the second identity. Finally set $z=x-y$ to obtain $\widehat{f*g}(\chi) =\sum_{y,z} f(y)g(z)\overline{\chi(y+z)} =\left(\sum_y f(y)\overline{\chi(y)}\right) \left(\sum_z g(z)\overline{\chi(z)}\right).$ Every interchange is finite. Formula (3) identifies the dual Haar measure here: each dual point has mass $1/N$. This is the finite case of the dual normalization constructed later for general LCA groups. $\square$

Proposition 2.3. Let $\tau_a f(x)=f(x-a)$, $M_\eta f(x)=\eta(x)f(x)$, and $f^*(x)=\overline{f(-x)}$. Then $\widehat{\tau_a f}(\chi)=\overline{\chi(a)}\widehat f(\chi), \qquad \widehat{M_\eta f}(\chi)=\widehat f(\chi\eta^{-1}), \qquad \widehat{f^*}(\chi)=\overline{\widehat f(\chi)}. \tag{4}$

Proof. In the first sum put $y=x-a$, extracting $\overline{\chi(a)}$. In the second combine $\eta(x)\overline{\chi(x)}=\overline{(\chi\eta^{-1})(x)}$. In the third put $y=-x$ and conjugate the finite sum. These substitutions give precisely (4). $\square$

Example 2.4. On $\mathbb Z/4$, the transform and its inverse, in order $0,1,2,3$, are $F=\begin{pmatrix} 1&1&1&1\\ 1&-i&-1&i\\ 1&-1&1&-1\\ 1&i&-1&-i \end{pmatrix}, \qquad F^{-1}=\tfrac14\overline F. \tag{5}$

Verification. The entry in row $k$, column $x$ is $E(-kx/4)$, giving the matrix. The geometric sums in (2) give $\overline F F=4I$. For $f=1_{\{0,2\}}$, the vector $(1,0,1,0)$ has transform $(2,0,2,0)$; multiplication by $\overline F/4$ returns $f$. Plancherel is $2=(4+4)/4$. Direct overlap gives $f*f=2f$, whose transform $(4,0,4,0)$ is the square of $\widehat f$. Translation by $1$ gives transform $(2,0,-2,0)$; modulation by $\chi_1$ gives transform $(0,2,0,2)$, checking both signs in (4).

This example also checks the subgroup formulas below directly. For $H=\{0,2\}$, trivial restriction means $\chi_k(2)=(-1)^k=1$, so $H^\perp=\{\chi_0,\chi_2\}$; its annihilator consists of the even points again. Reduction modulo two identifies $G/H$ with $\mathbb Z/2$, while restriction of $\chi_k$ to $H$ depends exactly on $k\bmod2$. For the same $f$, the two sides of Poisson summation are $2\,1_H(x)$ and $\tfrac12(2+2(-1)^x)$, respectively, and agree at all four points. Its two support sizes give equality $2\cdot2=4$ in uncertainty. $\square$

Example 2.5. On $G=(\mathbb Z/2)^n$, the characters are $\chi_a(x)=(-1)^{a\cdot x}$, where $a\cdot x=\sum_j a_jx_j$ is computed modulo two. Its transform is the Walsh–Hadamard transform.

Verification. The cyclic formula and product restriction in Theorem 1.2 give these characters, one for each $a$. Thus $\widehat f(a)=\sum_x(-1)^{a\cdot x}f(x)$, with inverse $2^{-n}$ times the same matrix. For $n=0$ this is the one-by-one identity. Exercise 6.2 verifies the matrix square directly. $\square$

3. Subgroups, quotients and periodization

Define the annihilator $H^\perp=\{\chi\in\widehat G:\chi(h)=1\text{ for all }h\in H\}$.

Theorem 3.1. There are canonical isomorphisms $\widehat{G/H}\cong H^\perp,\qquad \widehat G/H^\perp\cong\widehat H,\qquad (H^\perp)^\perp=H, \tag{6}$ where the last identity uses evaluation to identify the double dual with $G$. In particular $|H^\perp|=N/|H|$.

Proof. Composition with the quotient map embeds $\widehat{G/H}$ into $\widehat G$ with image $H^\perp$. Indeed a character trivial on $H$ defines $\eta(x+H)=\chi(x)$, independently of the representative, giving the inverse. Restriction $\widehat G\to\widehat H$ is onto by Theorem 1.1 and has kernel $H^\perp$. Its fibers are precisely the cosets of that kernel: two characters have the same restriction exactly when their quotient lies in $H^\perp$. Thus it gives the second bijective homomorphism.

Every $h\in H$ is annihilated by $H^\perp$. If $x\notin H$, Theorem 1.1 applied to $G/H$ gives a character nontrivial at $x+H$; its pullback is in $H^\perp$ and is nontrivial at $x$. This proves the last identity. The cardinality follows from the first isomorphism and Theorem 1.1. $\square$

Theorem 3.2 (finite Poisson summation). For every $x\in G$, $\sum_{h\in H}f(x+h) =\frac{|H|}{N}\sum_{\chi\in H^\perp}\widehat f(\chi)\chi(x). \tag{7}$

Proof. Insert inversion for each summand on the left. The inner sum $\sum_{h\in H}\chi(h)$ is $|H|$ when $\chi\in H^\perp$, and zero otherwise by (2) on $H$. This gives (7).

It is also inversion on the quotient: the function $P f(x+H)=\sum_{h\in H}f(x+h)$ is well-defined, and for a quotient character $\eta$ its transform is $\widehat f(\eta\circ q)$, because the cosets partition $G$. The quotient has $N/|H|$ elements, so its inversion factor is exactly $|H|/N$. $\square$

Example 3.3. In $\mathbb Z/6$, take $H=\{0,3\}$. Then $H^\perp=\{\chi_0,\chi_2,\chi_4\}$, and $G/H\cong\mathbb Z/3$.

Verification. Since $\chi_k(3)=(-1)^k$, trivial restriction is equivalent to even $k$. Reduction modulo three has kernel $H$, and its fibers are exactly the three cosets. For $f=\delta_0$, all Fourier coefficients are one, so the right side of (7) is $\frac13\left(1+E(x/3)+E(2x/3)\right).$ It is one for $x\in\{0,3\}$ and zero otherwise by the finite geometric sum; these are exactly the values of $\delta_0(x)+\delta_0(x+3)$. $\square$

For a function on a finite set, its support is the set where it is nonzero.

Theorem 4.1. If $f\ne0$, then $|\operatorname{supp}f|\,|\operatorname{supp}\widehat f|\ge N. \tag{8}$ Subgroup indicators attain equality.

Proof. Put $s=|\operatorname{supp}f|$, $t=|\operatorname{supp}\widehat f|$ and $M=\max_x|f(x)|>0$. For nonnegative numbers $b_1,\ldots,b_t$, $t\sum_jb_j^2-\left(\sum_jb_j\right)^2 =\sum_{i<j}(b_i-b_j)^2\ge0.$ Using this inequality, inversion and Plancherel gives $M\le\frac1N\sum_\chi|\widehat f(\chi)| \le\frac{\sqrt t}{N}\left(\sum_\chi|\widehat f(\chi)|^2\right)^{1/2} =\sqrt{\frac tN}\left(\sum_x|f(x)|^2\right)^{1/2} \le\sqrt{\frac{st}{N}}\,M.$ Cancel $M$. For $f=1_H$, orthogonality on $H$ gives $\widehat f=|H|1_{H^\perp}$; the support sizes have product $|H|(N/|H|)=N$. Exercise 6.3 proves the full equality characterization. $\square$

The stronger prime-order theorem requires an algebraic fact about roots of unity. We supply its algebraic prerequisites here.

Lemma 4.2 (polynomial and determinant tools). For a prime $p$, the ring $\mathbb F_p=\mathbb Z/p\mathbb Z$ is a field, and $\Phi_p(X)=1+X+\cdots+X^{p-1}$ is irreducible over $\mathbb Q$. If $P$ is an integer polynomial in finitely many variables and $\omega_j^p=1$, then $P(\omega_1,\ldots,\omega_n)=0 \quad\Longrightarrow\quad p\mid P(1,\ldots,1). \tag{9}$ Polynomial division, the root bound, the Vandermonde identity and inversion of a matrix with nonzero determinant all hold over any field.

Proof. We give the elementary algebra used in this statement. For integers $a,b$ not both zero, choose the smallest positive integer $d=ua+vb$ among their positive integer linear combinations. Division with remainder of $a,b$ by $d$ shows that both remainders are zero, by minimality. Thus $d$ divides both $a,b$, and every common divisor divides $d$. If $p$ is prime and $p\nmid a$, this gcd is one, so $ua+vp=1$. Reduction modulo $p$ gives an inverse to every nonzero residue. This proves the field assertion and also that a prime dividing a product of integers divides one factor.

Division of a polynomial by one with invertible leading coefficient is performed by canceling its leading term repeatedly; the degree strictly decreases, so the procedure terminates with a unique lower-degree remainder. Division by $X-a$ has remainder equal to evaluation at $a$. A nonzero polynomial of degree $d$ over a field has at most $d$ roots: factor out $X-a$ at a root and use induction, since a different root remains a root of the quotient. The same division algorithm gives a polynomial gcd and a linear-combination expression for it: apply successive divisions until the nonzero remainders end and substitute backward.

An integer polynomial is primitive when the gcd of its coefficients is one. The product of two primitive integer polynomials is primitive. Otherwise some prime divides every product coefficient; reducing modulo that prime would multiply two nonzero polynomials to zero over a field. That is impossible because the product's leading coefficient is the product of the two nonzero leading coefficients. A prime divisor exists for every integer greater than one by choosing its smallest divisor greater than one.

Every rational polynomial is a rational constant times a primitive integer polynomial, by clearing denominators and dividing the coefficient gcd. Therefore a factorization of a primitive integer polynomial over $\mathbb Q$ yields a factorization over $\mathbb Z$, up to signs: write it as $qAB$ with $A,B$ primitive and $q=u/v$ in lowest terms. The integrality of all coefficients forces $v$ to divide their gcd, which is one, and primitivity then forces $|u|=1$. For a monic polynomial its integer factors have leading coefficients with product one and can both be chosen monic.

Consider $\Phi_p(X+1)=\frac{(X+1)^p-1}{X}.$ Its leading coefficient is one, every other coefficient is divisible by $p$, and its constant coefficient is $p$, not divisible by $p^2$. Indeed the intermediate binomial coefficients $\binom pj$, $0<j<p$, are divisible by $p$: multiply by $j!$, whose residue is invertible modulo $p$, and use the falling product beginning with $p$. If this polynomial had two monic integer factors of positive degree, reduction modulo $p$ would make their product $X^{p-1}$. Each reduced factor must be a power of $X$: its least nonzero degree and its greatest degree add under multiplication, and for their product those two degrees are equal. Both factors' constant coefficients would consequently be divisible by $p$, contrary to the constant coefficient $p$ of their product. The preceding primitive-polynomial argument rules out a rational factorization too. Substitution $X\mapsto X-1$ proves the irreducibility of $\Phi_p$.

Set $\zeta=E(1/p)$. It is not one and satisfies $\Phi_p(\zeta)=0$, by the geometric sum. If a rational polynomial $Q$ vanishes at $\zeta$, divide it by $\Phi_p$. A nonzero remainder of smaller degree would have gcd one with the irreducible $\Phi_p$; the polynomial gcd identity evaluated at $\zeta$ would give $1=0$. Thus the remainder is zero. If $Q$ has integer coefficients, division by the monic $\Phi_p$ has integer quotient. For (9), write $\omega_j=\zeta^{k_j}$, $0\le k_j<p$, and apply this to $Q(X)=P(X^{k_1},\ldots,X^{k_n})$. Since $Q(1)=\Phi_p(1)A(1)=pA(1)$ for an integer polynomial $A$, (9) follows.

For clarity, the matrix facts used below also follow from finite algebra. Define the determinant by its signed sum over permutations. This formula is multilinear in the rows or columns and changes sign when two of them are interchanged; paired permutations make it zero when two rows coincide. Expansion along a row groups the same permutation terms by the chosen column. Consequently the cofactor matrix transposed, $\operatorname{adj}(M)$, satisfies $M\operatorname{adj}(M)=\operatorname{adj}(M)M=(\det M)I$: diagonal entries are row expansions, and off-diagonal entries are determinants with a repeated row or column. Thus $(\det M)^{-1}\operatorname{adj}(M)$ is an inverse whenever $\det M\ne0$.

Finally, $\det(z_i^{j-1})_{i,j=1}^n=\prod_{i<j}(z_j-z_i). \tag{10}$ Here is a polynomial proof which works over the integers and hence every field. The determinant vanishes when $z_i=z_j$, so division by the monic linear polynomial $z_j-z_i$ shows divisibility by that factor. Divide out the factors one at a time. On a new diagonal, the product of previously removed, different factors remains a nonzero polynomial, so the quotient still vanishes there and can be divided again. Polynomial rings over an integral domain are integral domains, by induction on variables and comparison of leading coefficients in the last variable. This justifies that cancellation on each diagonal. The determinant and the product both have degree $n(n-1)/2$, so their quotient is constant. The coefficient of $z_1^0z_2^1\cdots z_n^{n-1}$ is one in each: in the determinant it is the identity permutation, and in the product it is forced successively by the required powers of $z_1,z_2,\ldots$. This proves (10). $\square$

Lemma 4.3 (prime Fourier minors). If $x_1,\ldots,x_n$ and $r_1,\ldots,r_n$ are distinct residues modulo a prime $p$, where $1\le n\le p$, then $\det\bigl(E(x_i r_j/p)\bigr)_{i,j=1}^n\ne0. \tag{11}$

Proof. Choose the representatives $0\le r_j<p$. In the integer polynomial ring put $D(z)=\det(z_i^{r_j}),\qquad V(z)=\prod_{i<j}(z_j-z_i).$ The diagonal-division argument in Lemma 4.2 applies to the alternating polynomial $D$, giving $D=VP$ with $P$ an integer polynomial. We compute $P(1,\ldots,1)$ by setting $z_i=1+u_i$. The product $V(1+u)=V(u)$ is homogeneous of degree $d=n(n-1)/2$, with coefficient one at $u_1^0u_2^1\cdots u_n^{n-1}$. Therefore that coefficient in $D(1+u)$ equals $P(1,\ldots,1)$. Expansion of each row by the binomial formula gives $P(1,\ldots,1)=\det\left(\binom{r_j}{i-1}\right)_{i,j=1}^n.$ The polynomial $\binom Xk=X(X-1)\cdots(X-k+1)/k!$ has degree $k$ and leading coefficient $1/k!$. Replacing each row by its monomial leading term using the preceding lower-degree rows is a triangular row change with these diagonal coefficients. Multilinearity, and vanishing when two rows coincide, therefore gives $\left(\prod_{k=0}^{n-1}k!\right)P(1,\ldots,1) =\prod_{j<\ell}(r_\ell-r_j). \tag{12}$ This is (10) applied to the transposed power matrix; transposition preserves the permutation formula for a determinant.

No factor on the right of (12) vanishes modulo $p$, since the $r_j$'s are distinct. No factorial on the left vanishes modulo $p$, since $n-1<p$. Thus $p\nmid P(1,\ldots,1)$. By (9), $P(E(x_1/p),\ldots,E(x_n/p))\ne0$. The corresponding $V$ is nonzero because its arguments are distinct. Hence $D$ is nonzero there, proving (11). $\square$

Theorem 4.4 (sharp prime uncertainty). On $\mathbb Z/p$, for $p$ prime and $f\ne0$, $|\operatorname{supp}f|+|\operatorname{supp}\widehat f|\ge p+1. \tag{13}$ Conversely, any nonempty sets $A,B\subseteq\mathbb Z/p$ with $|A|+|B|\ge p+1$ are the exact supports of some $f,\widehat f$.

Proof. If (13) failed and $s=|\operatorname{supp}f|$, at least $s$ frequencies would have zero transform. Restrict to any $s$ of them. The resulting homogeneous system in the $s$ nonzero-position values of $f$ has a nonzero determinant by Lemma 4.3, using $-x_i$ to match the sign in (1). Lemma 4.2 makes the matrix invertible, forcing $f=0$, a contradiction.

First suppose $|A|+|B|=p+1$. Choose $b\in B$ and let $C=B^c\cup\{b\}$, so $|C|=|A|$. The matrix carrying a function supported in $A$ to its transform restricted to $C$ is invertible. Prescribe value one at $b$ and zero on $B^c$; it has a unique solution. Its supports are contained in $A,B$, it is nonzero, and (13) forces equality with both sets.

If $|A|+|B|>p+1$, set $a'=p+1-|B|\ge1$. For each $x\in A$, choose $A_x\subset A$ of size $a'$ containing $x$, and use the just-proved case to obtain $f_x$ with exact supports $A_x,B$. Enumerate these functions as $f_0,\ldots,f_{m-1}$ and form $F_t=\sum_{j=0}^{m-1}t^j f_j$. At any point of $A$, $F_t$ is a nonzero polynomial in $t$, since at least one coefficient is nonzero. At any frequency of $B$, its transform is also a nonzero polynomial, while both functions vanish outside the intended sets. Each of the finitely many nonzero polynomials has finitely many roots by Lemma 4.2. Choose $t\in\mathbb C$ outside their union. Then $F_t,\widehat F_t$ have exactly the desired supports. $\square$

Corollary 4.5 (Cauchy–Davenport). For nonempty $A,B\subseteq\mathbb Z/p$, $|A+B|\ge\min(|A|+|B|-1,p). \tag{14}$

Proof. Put $a=p+1-|A|$, $b=p+1-|B|$, and $r=\max(a+b-p,1)$. These integers satisfy $1\le r\le\min(a,b)$. Choose sets $X,Y$ of sizes $a,b$ with intersection of size $r$; for example use the integer intervals $X=\{0,\ldots,a-1\}$ and $Y=\{a-r,\ldots,a-r+b-1\}$ inside $\{0,\ldots,p-1\}$. Theorem 4.4 supplies functions with exact support pairs $(A,X)$ and $(B,Y)$. Their convolution is supported in $A+B$, and its Fourier support is exactly $X\cap Y$, by multiplication of the two transforms. This intersection is nonempty, so inversion makes the convolution nonzero. Applying (13) to it yields $|A+B|\ge p+1-r =p+1-\max(p+2-|A|-|B|,1) =\min(|A|+|B|-1,p).$ This proves (14). $\square$

Example 4.6. On $\mathbb Z/5$, $f=\delta_0-\delta_1$ has support sizes $2,4$, attaining (13). On $\mathbb Z/4$, the function $1_{\{0,2\}}$ has support sizes $2,2$, so the prime conclusion fails.

Verification. In the first case $\widehat f(k)=1-E(-k/5)$, which vanishes only at $k=0$ by Lemma 0.1. The second calculation is Example 2.4. Its Fourier submatrix with both row and column sets $\{0,2\}$ consists of ones, so even the nonzero-minor assertion fails in that composite group. $\square$

5. Multiplicative characters and Gauss sums

A Dirichlet character modulo $m\ge2$ means a character of the finite abelian unit group $(\mathbb Z/m)^\times$, extended by zero on nonunits. This extension is multiplicative: a product is a unit exactly when both factors are units. Indeed an inverse to $ab$ gives an inverse to $a$ and to $b$ in this commutative ring, and conversely their inverses multiply. Additive characters of $\mathbb Z/m$, such as $a\mapsto E(a/m)$, are different functions on a different group.

Lemma 5.1. For an odd prime $p$, the nonzero squares form a subgroup $Q$ of $\mathbb F_p^\times$ of index two. The function $\lambda(a)= \begin{cases} 0,&a=0,\\ 1,&a\in Q,\\ -1,&a\in\mathbb F_p^\times\setminus Q \end{cases}$ restricts to a nontrivial character of $\mathbb F_p^\times$, called the quadratic character.

Proof. Lemma 4.2 proves that $\mathbb F_p$ is a field. Squaring is a homomorphism on its abelian unit group, so its image $Q$ is a subgroup. The kernel is $\{1,-1\}$, because $x^2-1=(x-1)(x+1)$, a field has no zero divisors, and $p$ odd makes these two elements distinct. Each fiber of a homomorphism is a coset of its kernel, as in Theorem 3.1, so $|Q|=(p-1)/2$. The quotient has two elements and is cyclic; sending its identity to $1$ and its other element to $-1$ is an isomorphism with $\{1,-1\}$. Composing with the quotient map gives exactly the stated character. $\square$

Proposition 5.2. Let $p$ be prime, $\zeta=E(1/p)$, and $\chi$ a nontrivial character of $\mathbb F_p^\times$. Then $g(\chi)=\sum_{a\ne0}\chi(a)\zeta^a \quad\hbox{satisfies}\quad |g(\chi)|^2=p. \tag{15}$ For $p$ odd, $g(\lambda)^2=\lambda(-1)p$. For the trivial character on the unit group, the sum is $-1$.

Proof. Because multiplication by a nonzero residue is a bijection, substitute $a=tb$ in the expanded square: $|g(\chi)|^2 =\sum_{t\ne0}\chi(t)\sum_{b\ne0}\zeta^{b(t-1)}.$ For $t=1$, the inner sum is $p-1$. For $t\ne1$, its version including $b=0$ is zero by additive character orthogonality, so it is $-1$. Multiplicative character orthogonality gives $\sum_{t\ne0}\chi(t)=0$. Hence the square is $(p-1)-\sum_{t\ne0,1}\chi(t)=(p-1)-(0-1)=p$.

For the real character $\lambda$, conjugation and the substitution $a=-b$ give $\overline{g(\lambda)} =\sum_{a\ne0}\lambda(a)\zeta^{-a} =\lambda(-1)\sum_{b\ne0}\lambda(b)\zeta^b =\lambda(-1)g(\lambda).$ Multiply by $g(\lambda)$ and use (15); since $\lambda(-1)^2=1$, the asserted square follows. Finally $\sum_{a\ne0}\zeta^a=-1$, because the full geometric sum is zero. This last value explains why (15) requires a nontrivial multiplicative character. $\square$

Example 5.3. For $p=5$, the quadratic Gauss sum is $+\sqrt5$.

Verification. The quadratic character, in order $0,1,2,3,4$, is $(0,1,-1,-1,1)$. Put $\zeta=E(1/5)$ and $u=\zeta+\zeta^{-1}$. The geometric identity gives $u^2+u-1=0$. Also $u=2\cos(2\pi/5)>0$: the angle lies strictly between zero and $\pi/2$, where the earlier exponential construction proved positive cosine. Therefore $g(\lambda)=\zeta+\zeta^4-\zeta^2-\zeta^3=2u+1>0, \qquad (2u+1)^2=5.$ The positive real square root is unique, so this is $+\sqrt5$, fixing the sign left open by (15). $\square$

6. Exercises with complete solutions

Exercise 6.1. List all characters of $\mathbb Z/2\times\mathbb Z/4$ and give an isomorphism with its dual.

Solution. For $a=0,1$ and $b=0,1,2,3$, set $\chi_{a,b}(x,y)=(-1)^{ax}i^{by}$. These eight characters are distinguished by their values at $(1,0)$ and $(0,1)$. Every character must send those generators to a square root of one and a fourth root of one, respectively; the homomorphism law therefore forces exactly one displayed formula. Multiplication adds $a$ modulo two and $b$ modulo four. Thus $(a,b)\mapsto\chi_{a,b}$ is the required isomorphism. $\square$

Exercise 6.2. For $H_n=((-1)^{a\cdot x})_{a,x\in(\mathbb Z/2)^n}$, prove $H_n^2=2^nI$.

Solution. Its $(a,b)$-entry after squaring is $\sum_x(-1)^{a\cdot x+x\cdot b} =\prod_{j=1}^n\left(1+(-1)^{a_j+b_j}\right).$ Distributing the product yields the sum over all binary coordinates, justifying the factorization. Each factor is two when the corresponding coordinates agree and zero otherwise. The product is $2^n$ exactly when $a=b$; for $n=0$ the empty product is one. $\square$

Exercise 6.3. Prove that equality in (8) holds exactly for $f(x)=c\,\chi_0(x)1_{a+H}(x), \qquad c\ne0,\quad a\in G,\quad H\le G,\quad\chi_0\in\widehat G. \tag{16}$ Equivalently, these are nonzero scalar multiples of translates of modulated subgroup indicators.

Solution. Write $S=\operatorname{supp}f$, $T=\operatorname{supp}\widehat f$, $s=|S|$, $t=|T|$, and suppose $st=N$. The chain in Theorem 4.1 begins and ends with the same positive number $M$, so every inequality in it is an equality. The last inequality implies $|f(x)|=M$ on $S$, because the nonnegative defects $M^2-|f(x)|^2$ sum to zero. The preceding finite-square identity implies that $|\widehat f(\chi)|$ is constant, say $b>0$, on $T$.

For any $x\in S$, the triangle inequality in inversion is also an equality. Its nonzero summands $\widehat f(\chi)\chi(x)$ consequently all have the same phase. To verify this equality condition, rotate their nonzero sum to the positive real axis. For each summand, its real part is at most its modulus, and the sum of these nonnegative differences is zero. Every real part equals the corresponding modulus, so every summand is a positive real number after the rotation. Since their moduli all equal $b$, inversion gives $\widehat f(\chi)\chi(x)=\frac Nt f(x)\qquad(\chi\in T,\ x\in S).$ Fix $a\in S$ and $\chi_0\in T$. Dividing the identity at $x$ by the one at $a$ shows that $(\chi\chi_0^{-1})(x-a)=1$ for every $x\in S,\chi\in T$. Let $H$ be the subgroup generated by $S-a$. Multiplicativity extends this equality to all of $H$. Hence $S\subseteq a+H,\qquad T\subseteq\chi_0H^\perp.$ Theorem 3.1 gives $t\le N/|H|$, while $s\le|H|$. Since $st=N$, both inequalities are equalities; thus $S=a+H$ and $T=\chi_0H^\perp$. The same divided identity, now at $\chi=\chi_0$, yields $f(x)=f(a)\chi_0(x-a)$ on $S$, which is (16) with $c=f(a)/\chi_0(a)$.

Conversely $1_H$ attains equality by Theorem 4.1. Translation permutes its support and multiplies its transform by nonzero phases; modulation preserves its support and translates its Fourier support, by (4). A nonzero scalar changes neither support. All functions (16) therefore attain equality. $\square$

Exercise 6.4. For $p$ odd, show that $x^2=a$ in $\mathbb F_p$ has $1+\lambda(a)$ solutions. Deduce $\sum_{x\in\mathbb F_p}E(x^2/p)=g(\lambda).$

Solution. At $a=0$, the field property gives the unique root zero, and $1+\lambda(0)=1$. A nonsquare has no roots by definition. If $a=y^2\ne0$, its roots are $y,-y$, which are distinct because $p$ is odd; any other root $x$ would satisfy $(x-y)(x+y)=0$ and thus coincide with one of them. This proves the count in all cases. Grouping the displayed sum by $a=x^2$ gives $\sum_x E(x^2/p)=\sum_a(1+\lambda(a))E(a/p) =0+\sum_{a\ne0}\lambda(a)E(a/p).$ The zero is additive character orthogonality, and the last sum is $g(\lambda)$. For $p=5$, Example 5.3 gives the explicit value $\sqrt5$. $\square$

Exercise 6.5. Let $A\subseteq\mathbb Z/p$ with $|A|=\alpha p$. Prove that the number of ordered triples $(a,b,c)\in A^3$ with $a+b=c$ is $\alpha^3p^2+E$, where $|E|\le\alpha p\max_{\chi\ne1}|\widehat{1_A}(\chi)|.$

Solution. Put $f=1_A$. The count is $T=\sum_c(f*f)(c)f(c)$. The inner-product and convolution identities (3) give $T=\frac1p\sum_\chi \widehat f(\chi)^2 \overline{\widehat f(\chi)}.$ At the trivial character $\widehat f(1)=|A|=\alpha p$, giving the term $\alpha^3p^2$. If $M=\max_{\chi\ne1}|\widehat f(\chi)|$, the other terms satisfy $|E|\le\frac Mp\sum_{\chi\ne1}|\widehat f(\chi)|^2 =\frac Mp\bigl(p|A|-|A|^2\bigr) =M\alpha(1-\alpha)p\le M\alpha p.$ Plancherel justifies the equality in the middle. Empty $A$ and full $A$ are included. $\square$

Reading and continuation

The free readings for this reconstruction are Keith Conrad's Characters of finite abelian groups (short version), §§3–5, and Gauss and Jacobi sums on finite fields and $\mathbb Z/m\mathbb Z$, Theorem 2.2 and Corollary 2.3; and Terence Tao's An uncertainty principle for cyclic groups of prime order, arXiv version 6, §1. These references provide mathematical reading material. They do not replace any proof in this programme.

All the stated results and five exercises are proved above, with elementary exponential facts supplied by the exact earlier reading. The next lesson develops the topology of characters on general locally compact abelian groups.