# Advanced Number Theory Note #9: Finding the finite Fourier expansion of a periodic arithmetical function

This note (intended mainly as a technical memo for myself) is a detailed study of the important result that every arithmetical function which is periodic mod k can be expressed as a finite Fourier series. I try to give illustrative examples of key points throughout.

An arithmetical function $f$ is periodic with period k, or equivalently ‘periodic mod k’, if

$f(n + k) = f(n)$

for all integers n.

Example: A simple example is the greatest common divisor of two integers n and k, usually denoted $gcd(n, k)$, which can be viewed as a periodic function of n with period k. To see that this is periodic, note that if we let

$d = gcd(n, k)$

and

$h = gcd(n+k, k)$

then saying that d is “a periodic function of n with period k” is simply saying $h = d$.

h divides both $(n+k)$ and $k$, so it must also divide $(n+k) - k = n$, and thus we must have $h \leq d$ since d is the gcd of n and k.

d divides both $n$ and $k$, so it must divide $(n + k)$, and hence we must have $d \leq h$ since h is the gcd of $(n+k)$ and $k$, so we have proved $h = d$.END

Note that one can uniquely specify a periodic arithmetical function with period k by giving the values $f(0)$, $f(1)$, . . . , $f(k-1)$. Then for any n we will have

$f(kn) = f(0)$

$f(kn+1) = f(1)$

$\vdots$

$f(kn + k - 1) = f(k-1)$

Example: For example, to construct a periodic function $f$ with period 4 for which $f(11) = 1$ and $f(22) = 2$, we can specify $f(0) = 3$, $f(1) = 4$, $f(2) = 2$, and $f(3) = 1$. Then $f(11) = f(3) = 1$ and $f(22) = f(2) = 2$ as required.END

The key result which is the focus of this note is that any such periodic function can be expressed as a finite Fourier series of the form

$f(m) = \sum_{n=0}^{k-1}g(n)e^{2\pi imn/k}$

The theorem which proves this, Theorem 4 given at the end of this note, also provides a simple formula for the coefficients $g(n)$.

Note that $e^{2\pi im/k}$ is a kth root of unity and the terms $e^{2\pi imn/k}$ appearing in the expression for the finite Fourier series above are the nth powers of this.

Three theorems are needed to arrive at the proof of the final fourth one. The following result is a crucial first step.

Theorem 1. For fixed $k \ge 1$ let

$g(n) = \sum_{m=0}^{k-1}e^{2\pi imn/k}$

Then $g(n) = 0$ if $k \nmid n$ and $g(n) = k$ if $k \mid n$.

Example: Suppose $k = 2$, $n = 3$. Then $k \nmid n$ and

$g(3) = 1 + e^{2\pi i3/2} = 1 - 1 = 0$

Now suppose $k = 2$, $n = 4$. Then $k \mid n$ and

$g(3) = 1 + e^{2\pi i4/2} = 1 + 1 = 2 = k$ END

Proof of Theorem 1. Letting $x = e^{2\pi in/k}$ we see that $g(n)$ is the sum of a geometric progression,

$g(n) = \sum_{m=0}^{k-1}x^m$

and so

$g(n) = \frac{x^k - 1}{x - 1}$

if $x \neq 1$, whereas $g(n) = k$ if $x = 1$. But since $x$ is a kth root of unity we must have $x^k = 1$ and so $g(n) = 0$ when $x \neq 1$. Furthermore, since $x = 1$ iff $k \mid n$ (because otherwise x is a primitive kth root of unity and thus not itself equal to 1) we must have $g(n) = k$ whenever $k \mid n$ and $g(n) = 0$ whenever $k \nmid n$. Thus, we obtain the result in Theorem 1.QED

The next key step is a theorem which yields a formula for obtaining polynomials taking particular values at specified points (known as Lagrange’s polynomial interpolation formula).

Theorem 2. Lagrange’s interpolation theorem. Let $z_0$, $z_1$, . . ., $z_{k-1}$ be k distinct complex numbers, and let $w_0$, $w_1$, . . ., $w_{k-1}$ be k complex numbers which are not necessarily distinct. Then there is a unique polynomial $P(z)$ of degree $\le k - 1$ such that

$P(z_m) = w_m$ for $m = 0, 1, 2, \dots, k-1$

Proof of Theorem 2. This is a proof by construction, i.e., Lagrange’s interpolation polynomial $P(z)$ is constructed explicitly, as follows. Let

$A(z) = (z - z_0) (z - z_1) \cdots (z - z_{k-1})$

and let

$A_m(z) = \frac{A(z)}{z - z_m}$

(Thus, $A_m(z)$ is obtained by ‘deleting’ the factor $(z - z_m)$ from the product $A(z)$). Then $A_m(z)$ is a polynomial of degree $k - 1$ with the properties that

$A_m(z_m) \neq 0$

and

$A_m(z_j) = 0$ if $j \neq m$

It follows that $A_m(z)/A_m(z_m)$ is a polynomial of degree $k - 1$ which vanishes at each $z_j$ for $j \neq m$, and has the value 1 at $z_m$. Therefore the sum

$P(z) = \sum_{m=0}^{k-1} w_m \frac{A_m(z)}{A_m(z_m)}$

is a polynomial of degree $\le k-1$ with $P(z_j) = w_j$ for each j.

If $Q(z)$ is any other such polynomial then $P(z) - Q(z)$ vanishes at the k distinct points $z_0$, $z_1$, . . ., $z_{k-1}$. Since it cannot be the case that $P(z) - Q(z)$ is a polynomial of degree k with roots $z_0$, $z_1$, . . ., $z_{k-1}$ (because both $P(z)$ and $Q(z)$ have degree $\le k-1$), the only other possibility is that $P(z) - Q(z)$ vanishes everywhere, i.e.,  that $P(z) = Q(z)$, which proves uniqueness. QED

Example: To illustrate how this theorem is applied, suppose we wish to find a polynomial of degree 3 such that

$P(1) = 1 + i$

$P(-1) = 1 - i$

$P(i) = 1 + 2i$

$P(-i) = 1 - 2i$

Then we define

$A(z) = (z - 1)(z + 1)(z - i)(z + i)$

$A_0(z) = (z + 1)(z - i)(z + i)$

$A_1(z) = (z - 1)(z - i)(z + i)$

$A_2(z) = (z - 1)(z + 1)(z + i)$

$A_3(z) = (z - 1)(z + 1)(z - i)$

and we get

$P(z) = (1 + i)\frac{A_0(z)}{A_0(1)} + (1 - i)\frac{A_1(z)}{A_1(-1)} + (1+2i) \frac{A_2(z)}{A_2(i)} + (1 - 2i)\frac{A_3(z)}{A_3(-i)}$

$= \frac{1}{2}(i - 2)z^3 + \frac{1}{2}(i + 2)z + 1$ END

The third result is proved by choosing the numbers $z_0$, $z_1$, . . ., $z_{k-1}$ in Theorem 2 to be the kth roots of unity.

Theorem 3. Given k complex numbers $w_0$, $w_1$, . . ., $w_{k-1}$, there exist k uniquely determined complex numbers $a_0$, $a_1$, . . ., $a_{k-1}$ such that

$w_m = \sum_{n=0}^{k-1}a_ne^{2\pi imn/k}$               (1)

for $m = 0, 1, 2, \ldots, k-1$. Furthermore, the coefficients $a_n$ are given by the formula

$a_n = \frac{1}{k}\sum_{m=0}^{k-1}w_m e^{-2\pi imn/k}$               (2)

for $n = 0, 1, 2, \ldots, k-1$.

Proof of Theorem 3. Let $z_m = e^{2\pi im/k}$. The numbers $z_0$, $z_1$, . . ., $z_{k-1}$ are distinct, so by Theorem 2 there is a unique Lagrange polynomial

$P(z) = \sum_{n=0}^{k-1}a_n z^n$

such that $P(z_m) = w_m$ for each $m = 0, 1, 2, \ldots, k-1$. This proves that there are uniquely determined numbers $a_n$ satisfying (1).

To obtain (2), multiply both sides of (1) by $e^{-2\pi imr/k}$ where m and r are non-negative integers less than k, and sum over m, to get

$\sum_{m=0}^{k-1}w_m e^{-2\pi imr/k} = \sum_{n=0}^{k-1}a_n \sum_{m=0}^{k-1}e^{2\pi i(n-r)m/k}$

By Theorem 1, the sum over m on the right hand side is zero unless $k \mid (n-r)$. But we have $\mid n-r \mid \le k-1$, so $k \mid (n-r)$ iff $n = r$. Therefore the only term that doesn’t vanish on the right occurs when $n = r$, and this proves (2). QED

With these three theorems in hand, it is now straightforward to show that every arithmetical function which is periodic mod k can be expressed as a finite Fourier series.

Theorem 4. Let $f$ be an arithmetical function which is periodic mod k. Then there is a uniquely determined arithmetical function $g$ which is also periodic mod k, such that

$f(m) = \sum_{n=0}^{k-1}g(n) e^{2\pi imn/k}$

where $g$ is given by the formula

$g(n) = \frac{1}{k}\sum_{m=0}^{k-1}f(m) e^{-2\pi imn/k}$

Proof of Theorem 4. Let $w_m = f(m)$ for $m = 0, 1, 2, \ldots, k-1$. We can apply Theorem 3 to get the numbers corresponding to $a_0$, $a_1$, . . ., $a_{k-1}$ in that theorem. With these numbers in hand we can now define the periodic function $g$ by the relations $g(m) = a_m$ for $m = 0, 1, 2, \ldots, k-1$ and (as shown at the start of this note) we can extend the definition of $g(m)$ to all integers m by periodicity mod k. This proves that the equations $f$ and $g$ are related by the equations in Theorem 4. QED

Since both $f$ and $g$ are periodic mod k, we can write the sums in Theorem 4 equivalently as

$f(m) = \sum_{n \hspace{1 mm} mod \hspace{1 mm} k}g(n) e^{2\pi imn/k}$            (3)

and

$g(n) = \frac{1}{k}\sum_{m \hspace{1 mm} mod \hspace{1 mm} k}f(m) e^{-2\pi imn/k}$          (4)

The sum in (3) is the finite Fourier expansion of $f$, and the numbers defined by $g(n)$ in (4) are the Fourier coefficients of $f$.

Example: To illustrate the application of Theorem 4, suppose we want to calculate $g(n)$ when $k = 6$ and $f$ is the non-principal Dirichlet character mod 6. (Dirichlet characters were discussed in Advanced Number Theory Note #7). The residue classes mod 6 are $\{1, 5 \}$ so there are only two Dirichlet characters. One is the principal character taking the value 1 for both 1 and 5. The other is the non-principal character which must have the square roots of unity as its values, so $f(1) = \chi(1) = 1$, $f(5) = \chi(5) = -1$, and $f(m) = 0$ for $m \neq 1,5$. Therefore

$g(n) = \frac{1}{6}f(1)e^{-2\pi in/k} + \frac{1}{6}f(5)e^{-2\pi i5n/k} = \frac{1}{6}( e^{-2\pi in/k} - e^{-2\pi i5n/k})$ END