Let \(k\) and \(n\) be natural numbers with \(k \ge 1\). The set \((\mathbb {Z}/k\mathbb {Z})^n\) of \(n\)-tuples with entries in \(\mathbb {Z}/k\mathbb {Z}\) is finite, and its cardinality is

Let \(k\) be a positive integer and set \(\omega _k = e^{2\pi i / k} \in \mathbb {C}\). Then \(\omega _k\) is a primitive \(k\)-th root of unity: \(\omega _k^k = 1\), and no smaller positive power of \(\omega _k\) equals \(1\), so that \(\omega _k^j = 1\) for a natural number \(j\) holds precisely when \(k\) divides \(j\).

Let \(k\) be a positive integer and let \(\omega _k = e^{2\pi i / k}\) be the primitive \(k\)-th root of unity in \(\mathbb {C}\). Then \(\omega _k^k = 1\).

Let \(k \ge 1\) and write \(\omega _k = e^{2\pi i/k}\) for the primitive \(k\)-th root of unity, and for \(a \in \mathbb {Z}/k\mathbb {Z}\) let its image under the homomorphism \((\mathbb {Z}/k\mathbb {Z}, +) \to (\mathbb {C}^\times , \cdot )\) be \(\omega _k^{a}\). Then the additive identity \(0 \in \mathbb {Z}/k\mathbb {Z}\) maps to \(1\); that is, \(\omega _k^{0} = 1\).

Fix an integer \(k \ge 1\) and let \(\omega _k = e^{2\pi i/k}\) be the primitive \(k\)-th root of unity. For \(a \in \mathbb {Z}/k\mathbb {Z}\) write \(\chi (a) = \omega _k^{a}\), where the exponent is the canonical representative of \(a\) in \(\{ 0, 1, \ldots , k-1\} \). Then for all \(a, b \in \mathbb {Z}/k\mathbb {Z}\),

so \(\chi \) is a homomorphism from the additive group \(\mathbb {Z}/k\mathbb {Z}\) to the multiplicative group \(\mathbb {C}^{\times }\).

Let \(k \ge 1\) and let \(\omega _k = e^{2\pi i/k}\) be the primitive \(k\)-th root of unity, and for \(a \in \mathbb {Z}/k\mathbb {Z}\) write \(\omega _k^{a}\) for the value \(\omega _k\) raised to the canonical representative of \(a\) in \(\{ 0,\dots ,k-1\} \). Then for every \(a \in \mathbb {Z}/k\mathbb {Z}\),

that is, replacing \(a\) by its additive inverse conjugates the corresponding character value.

Fix an integer \(k \ge 1\) and write \(\omega _k = e^{2\pi i/k}\) for the primitive \(k\)-th root of unity. For every residue \(a \in \mathbb {Z}/k\mathbb {Z}\), the complex number \(\omega _k^{a}\), obtained by raising \(\omega _k\) to the canonical representative of \(a\) in \(\{ 0,\dots ,k-1\} \), satisfies \(\lVert \omega _k^{a}\rVert = 1\), so it lies on the unit circle.

Fix a positive integer \(k\) and let \(\omega _k = e^{2\pi i / k}\). For \(b \in \mathbb {Z}/k\mathbb {Z}\), write \(\lfloor b\rfloor \in \{ 0,\ldots ,k-1\} \) for its canonical representative and set \(\chi (b) = \omega _k^{\lfloor b\rfloor }\). Then for all \(j, a \in \mathbb {Z}/k\mathbb {Z}\),

Let \(k \ge 1\) and let \(\omega _k = e^{2\pi i/k}\) be the primitive \(k\)-th root of unity. For each \(a \in \mathbb {Z}/k\mathbb {Z}\), write \(\omega _k^{a}\) for \(\omega _k\) raised to the canonical representative of \(a\) in \(\{ 0,\ldots ,k-1\} \). Then for every \(j \in \mathbb {Z}/k\mathbb {Z}\),

Fix an integer \(k \ge 1\) and a dimension \(n\), and let \(s, x, y \in (\mathbb {Z}/k\mathbb {Z})^n\). Writing \(s \cdot x = \sum _{i=0}^{n-1} s_i x_i \in \mathbb {Z}/k\mathbb {Z}\) for the componentwise dot product, the dot product is additive in its right argument:

where \(x + y\) denotes the componentwise sum.

Fix an integer \(k \ge 1\) and let \(x \in (\mathbb {Z}/k\mathbb {Z})^n\) be any vector. Then the dot product of the zero vector with \(x\) is zero: \(0 \cdot x = 0\) in \(\mathbb {Z}/k\mathbb {Z}\).

Fix an integer \(k \ge 1\) and a length \(n \ge 0\), and let \(s \in (\mathbb {Z}/k\mathbb {Z})^n\). Writing \(0\) for the zero vector of \((\mathbb {Z}/k\mathbb {Z})^n\), the dot product of \(s\) with \(0\) equals \(0\) in \(\mathbb {Z}/k\mathbb {Z}\); that is, \(\sum _{i=0}^{n-1} s_i \cdot 0 = 0\).

Fix an integer \(k \ge 1\) and a dimension \(n\), and work in the module \(\mathbb {Z}_k^n = (\mathbb {Z}/k\mathbb {Z})^n\) with dot product \(s \cdot x = \sum _{i=0}^{n-1} s_i x_i \in \mathbb {Z}/k\mathbb {Z}\). Then for all \(s, x \in \mathbb {Z}_k^n\),

For any three vectors \(s, t, x \in \mathbb {Z}_k^n\), the dot product is additive in its left argument under subtraction:

where the subtraction on the left is taken componentwise and both sides are elements of \(\mathbb {Z}/k\mathbb {Z}\).

Fix integers \(k \ge 1\) and \(n \ge 0\), let \(\omega _k = e^{2\pi i/k}\), and for \(s \in (\mathbb {Z}/k\mathbb {Z})^n\) let \(\chi _s : (\mathbb {Z}/k\mathbb {Z})^n \to \mathbb {C}\) be the character \(\chi _s(x) = \omega _k^{\, s\cdot x}\), where \(s\cdot x = \sum _{i=1}^{n} s_i x_i \in \mathbb {Z}/k\mathbb {Z}\) is the componentwise dot product. Then for all \(x, y \in (\mathbb {Z}/k\mathbb {Z})^n\),

Fix an integer \(k \ge 1\) and let \(\omega _k = e^{2\pi i/k}\). For any \(s \in \mathbb {Z}_k^n\), the Fourier character \(\chi _s(x) = \omega _k^{s \cdot x}\) satisfies \(\chi _s(0) = 1\), where \(0\) denotes the zero vector of \(\mathbb {Z}_k^n\).

Fix an integer \(k \ge 1\) and a dimension \(n\), and let \(\chi _s(x) = \omega _k^{s \cdot x}\) denote the Fourier character on \(\mathbb {Z}_k^n\) indexed by \(s \in \mathbb {Z}_k^n\), where \(\omega _k = e^{2\pi i/k}\) and \(s \cdot x = \sum _{i} s_i x_i\) is the dot product modulo \(k\). Then the character indexed by the zero vector is the constant function \(1\): for every \(x \in \mathbb {Z}_k^n\),

Fix an integer \(k \ge 1\) and let \(\omega _k = e^{2\pi i/k}\) be the primitive \(k\)-th root of unity. For \(s \in \mathbb {Z}_k^n\), let \(\chi _s \colon \mathbb {Z}_k^n \to \mathbb {C}\) be the Fourier character \(\chi _s(x) = \omega _k^{\, s\cdot x}\), where \(s \cdot x = \sum _{i} s_i x_i \in \mathbb {Z}/k\mathbb {Z}\) is the componentwise dot product. Then for every \(s, x \in \mathbb {Z}_k^n\) one has \(\left\lvert \chi _s(x)\right\rvert = 1\).

Fix \(k \geq 1\) and \(n \in \mathbb {N}\), and let \(s \in \mathbb {Z}_k^n\). Then the Fourier character \(\chi _s(x) = \omega _k^{s \cdot x}\) is nonzero for every \(x \in \mathbb {Z}_k^n\).

Fix an integer \(k \ge 1\), and for \(s \in \mathbb {Z}_k^n\) let \(\chi _s(x) = \omega _k^{s \cdot x}\) be the Fourier character on \(\mathbb {Z}_k^n\) indexed by \(s\), where \(\omega _k = e^{2\pi i/k}\) and \(s \cdot x = \sum _{i} s_i x_i \in \mathbb {Z}/k\mathbb {Z}\). Then for every \(s, x \in \mathbb {Z}_k^n\),

that is, complex conjugation of a character amounts to negating its index.

Fix an integer \(k \ge 1\) and let \(\omega _k = e^{2\pi i/k}\). For a frequency vector \(s \in \mathbb {Z}_k^n\), let \(\chi _s \colon \mathbb {Z}_k^n \to \mathbb {C}\) be the Fourier character \(\chi _s(x) = \omega _k^{\, s \cdot x}\), where \(s \cdot x = \sum _{i} s_i x_i\) is the dot product in \(\mathbb {Z}/k\mathbb {Z}\). Then for all \(s, t, x \in \mathbb {Z}_k^n\),

so that pointwise multiplication of characters corresponds to addition of their frequency indices.

Fix a modulus \(k \ge 1\) and a dimension \(n\), and let \(\omega _k = e^{2\pi i/k}\). For a frequency \(s \in \mathbb {Z}_k^n\), let \(\chi _s(x) = \omega _k^{s\cdot x}\) be the associated Fourier character on \(\mathbb {Z}_k^n\). If \(s \neq 0\), then the character has vanishing mean:

Fix an integer \(k \ge 1\) and let \(\omega _k = e^{2\pi i/k}\) be the associated primitive \(k\)-th root of unity. For a natural number \(n\) and an index \(s \in (\mathbb {Z}/k\mathbb {Z})^n\), let \(\chi _s \colon (\mathbb {Z}/k\mathbb {Z})^n \to \mathbb {C}\) be the Fourier character \(\chi _s(x) = \omega _k^{\, s \cdot x}\), and write \(\mathbb {E}[f] = k^{-n}\sum _{x} f(x)\) for the uniform average of a complex-valued function \(f\) over \((\mathbb {Z}/k\mathbb {Z})^n\). Then the trivial character \(\chi _0\), indexed by the zero vector, has expectation \(\mathbb {E}[\chi _0] = 1\).

Fix an integer \(k \ge 1\) and a dimension \(n \ge 0\), and let \(\omega _k = e^{2\pi i/k}\). For \(s \in \mathbb {Z}_k^n\), let \(\chi _s(x) = \omega _k^{\, s\cdot x}\) be the Fourier character indexed by \(s\), and equip functions on \(\mathbb {Z}_k^n\) with the Hermitian inner product \(\langle f,g\rangle = \frac{1}{k^n}\sum _{x\in \mathbb {Z}_k^n} f(x)\, \overline{g(x)}\). Then every character has unit norm: for all \(s \in \mathbb {Z}_k^n\),

Let \(k \ge 1\) and \(n \ge 0\), and let \(\omega _k = e^{2\pi i/k}\). For \(s, t \in \mathbb {Z}_k^n\) with \(s \ne t\), the Fourier characters \(\chi _s(x) = \omega _k^{s\cdot x}\) and \(\chi _t(x) = \omega _k^{t\cdot x}\) are orthogonal with respect to the Hermitian inner product \(\langle f, g\rangle = \frac{1}{k^n}\sum _{x \in \mathbb {Z}_k^n} f(x)\, \overline{g(x)}\); that is, \(\langle \chi _s, \chi _t\rangle = 0\).

Fix an integer \(k \ge 1\) and a dimension \(n\), and let \(\chi _s(x) = \omega _k^{s \cdot x}\) denote the Fourier character on \(\mathbb {Z}_k^n\) indexed by a frequency \(s \in \mathbb {Z}_k^n\), where \(\omega _k = e^{2\pi i / k}\). Then for every \(s \in \mathbb {Z}_k^n\), the Fourier coefficient of \(\chi _s\) at its own frequency equals \(1\); equivalently, \(\widehat{\chi _s}(s) = \langle \chi _s, \chi _s \rangle = 1\).

Fix an integer \(k \ge 1\) and a dimension \(n\), and let \(\omega _k = e^{2\pi i / k}\). For a frequency \(s \in \mathbb {Z}_k^n\), write \(\chi _s(x) = \omega _k^{\, s \cdot x}\) for the associated Fourier character on \(\mathbb {Z}_k^n\), where \(s \cdot x = \sum _{i} s_i x_i\) is computed in \(\mathbb {Z}/k\mathbb {Z}\). Then for any two distinct frequencies \(s \ne t\) in \(\mathbb {Z}_k^n\), the Fourier coefficient of the character \(\chi _s\) at \(t\) vanishes:

Fix integers \(k \ge 1\) and \(n\), and let \(\omega _k = e^{2\pi i/k}\). For a frequency \(s \in \mathbb {Z}_k^n\), let \(\chi _s(x) = \omega _k^{\, s\cdot x}\) be the corresponding Fourier character, where \(s\cdot x = \sum _{i} s_i x_i \in \mathbb {Z}/k\mathbb {Z}\), and let \(\hat f(s) = \tfrac {1}{k^n}\sum _{x \in \mathbb {Z}_k^n} f(x)\, \overline{\chi _s(x)}\) be the Fourier coefficient of \(f\) at \(s\). Then every function \(f : \mathbb {Z}_k^n \to \mathbb {C}\) is recovered from its Fourier coefficients by

Let \(k \ge 1\) and \(n\) be natural numbers, and let \(f : \mathbb {Z}_k^n \to \mathbb {C}\) be a complex-valued function on \(\mathbb {Z}_k^n\). Then the sum of the squared magnitudes of its Fourier coefficients equals its squared \(L^2\) norm:

where \(\hat{f}(s) = \mathbb {E}_{x}\! \left[f(x)\, \overline{\omega _k^{\, s \cdot x}}\right]\) is the Fourier coefficient at frequency \(s\) and \(\| f\| _2^2 = \tfrac {1}{k^n}\sum _{x \in \mathbb {Z}_k^n} |f(x)|^2\).

Fix an integer \(k \ge 1\) and let \(f, g : \mathbb {Z}_k^n \to \mathbb {C}\) be complex-valued functions on \(\mathbb {Z}_k^n\), with convolution \((f * g)(x) = \mathbb {E}_y\! \left[f(y)\, g(x - y)\right]\) and Fourier coefficients \(\hat{f}(s) = \langle f, \chi _s\rangle \) taken at any frequency \(s \in \mathbb {Z}_k^n\). Then the Fourier transform carries convolution to pointwise multiplication: