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
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
Proof of Theorem 1. Letting we see that is the sum of a geometric progression,
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
Proof of Theorem 2. This is a proof by construction, i.e., Lagrange’s interpolation polynomial is constructed explicitly, as follows. Let
(Thus, is obtained by ‘deleting’ the factor from the product ). Then is a polynomial of degree with the properties that
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
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
for . Furthermore, the coefficients are given by the formula
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
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