The Exercise

A complex function $f$ on the integers is periodic with period $r$ , a positive integer, when $f(x + r) = f(x)$ for every integer $x$ . Let $N$ be a positive multiple of $r$ , so that the points $x = 0, 1, \dots, N-1$ hold $N/r$ whole periods of $f$ . The exercise asks for the discrete Fourier transform of $f$ over these $N$ points: at which frequencies $\ell$ it vanishes, and what it is at the rest.

The Fourier Transform

For a complex function $f$ on the integers, the normalized discrete Fourier transform $\hat f_n$ of $f$ over $n$ points is the complex function on the integers given by $\hat f_n(\ell) = \frac{1}{\sqrt{n}} \sum_{x=0}^{n-1} e^{-2\pi i \ell x / n} f(x).$ (1)^✦

When $f(0), \dots, f(N-1)$ are the amplitudes of a state $\sum_x f(x)\,|x\rangle$ of a register with $N$ basis states, $\hat f_N(\ell)$ is the amplitude of $|\ell\rangle$ after the inverse quantum Fourier transform, as in period finding.

The Claim

The claim compares the transform over the $N$ points with the transform $\hat f_r$ over a single period, $x = 0, \dots, r-1$ .

Theorem 1. Let $r$ and $N$ be positive integers with $r$ dividing $N$ , and let $f$ be a complex function on the integers, periodic with period $r$ . For every integer $\ell$ that is not a multiple of $N/r$ , $\hat f_N(\ell) = 0,$ (2)^✦ and for every integer $k$ , $\hat f_N\!\left(k \, \frac{N}{r}\right) = \sqrt{\frac{N}{r}}\; \hat f_r(k).$ (3)^✦

What Is Checked

The claim is stated over the normalized transform (1) of the function $f$ . What the library proves about this transform is the theorem above, for every function of period $r$ whatever its values on a period.