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 is periodic with period k, or equivalently ‘periodic mod k’, if

for all integers n.

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

and

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

h divides both and , so it must also divide , and thus we must have since d is the gcd of n and k.

d divides both and , so it must divide , and hence we must have since h is the gcd of and , so we have proved .END

Note that one can uniquely specify a periodic arithmetical function with period k by giving the values , , . . . , . Then for any n we will have

* Example*: For example, to construct a periodic function with period 4 for which and , we can specify , , , and . Then and 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

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

Note that is a kth root of unity and the terms 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 let

Then if and if .

* Example*: Suppose , . Then and

Now suppose , . Then and

END

* Proof of Theorem 1*. Letting we see that is the sum of a geometric progression,

and so

if , whereas if . But since is a kth root of unity we must have and so when . Furthermore, since iff (because otherwise x is a primitive kth root of unity and thus not itself equal to 1) we must have whenever and whenever . 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 , , . . ., be k distinct complex numbers, and let , , . . ., be k complex numbers which are not necessarily distinct. Then there is a unique polynomial of degree such that

for

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

and let

(Thus, is obtained by ‘deleting’ the factor from the product ). Then is a polynomial of degree with the properties that

and

if

It follows that is a polynomial of degree which vanishes at each for , and has the value 1 at . Therefore the sum

is a polynomial of degree with for each j.

If is any other such polynomial then vanishes at the k distinct points , , . . ., . Since it cannot be the case that is a polynomial of degree k with roots , , . . ., (because both and have degree ), the only other possibility is that vanishes everywhere, i.e., that , which proves uniqueness. QED

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

Then we define

and we get

END

The third result is proved by choosing the numbers , , . . ., in Theorem 2 to be the kth roots of unity.

* Theorem 3*. Given k complex numbers , , . . ., , there exist k uniquely determined complex numbers , , . . ., such that

(1)

for . Furthermore, the coefficients are given by the formula

(2)

for .

* Proof of Theorem 3*. Let . The numbers , , . . ., are distinct, so by Theorem 2 there is a unique Lagrange polynomial

such that for each . This proves that there are uniquely determined numbers satisfying (1).

To obtain (2), multiply both sides of (1) by where m and r are non-negative integers less than k, and sum over m, to get

By Theorem 1, the sum over m on the right hand side is zero unless . But we have , so iff . Therefore the only term that doesn’t vanish on the right occurs when , 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 be an arithmetical function which is periodic mod k. Then there is a uniquely determined arithmetical function which is also periodic mod k, such that

where is given by the formula

* Proof of Theorem 4*. Let for . We can apply Theorem 3 to get the numbers corresponding to , , . . ., in that theorem. With these numbers in hand we can now define the periodic function by the relations for and (as shown at the start of this note) we can extend the definition of to all integers m by periodicity mod k. This proves that the equations and are related by the equations in Theorem 4. QED

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

(3)

and

(4)

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

* Example*: To illustrate the application of Theorem 4, suppose we want to calculate when and is the non-principal Dirichlet character mod 6. (Dirichlet characters were discussed in Advanced Number Theory Note #7). The residue classes mod 6 are 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 , , and for . Therefore

END