Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 23 / 1

A primitive Dirichlet character modulo $q$ is a Dirichlet character which is not induced from a character of a proper divisor of $q$. To determine the inducing primitive Dirichlet character, use the Chinese remainder theorem to decomposeOn each factor choose the least exponent $c_p\in \{0,\dots ,k\}$ through whose reduction the restricted character factors. Exponent zero means the trivial unit group modulo one. Put $q_0={\prod }_p{p}^{c_p}$ and define ${\chi }_0$ on the units modulo $q_0$ by these descended factors, extending by zero off the units. Every reduction of unit groups is surjective, so the descended character is unique. Its local exponents cannot be decreased, hence it is primitive. The original character is $\chi (n)={\chi }_0(n)$ when $(n,q)=1$, and zero otherwise.

Any other inducing modulus must have exponent at least $c_p$ at every prime, by restriction to the corresponding local factor. Therefore $q_0$ is the unique minimal modulus, the conductor of a Dirichlet character, and ${\chi }_0$ is the unique primitive Dirichlet character inducing $\chi$. The argument also explains why removing extra prime factors can change values at integers that were nonunits for $q$.

Use the unitary discrete Fourier transform, with $e(x)=\exp (2\pi ix)$:For a unit $a$, substitute $m=an$ in the sum. The multiplicativity of the Dirichlet character gives $\chi (a^{-1}m)=\overline{\chi (a)}\chi (m)$, henceThe complex conjugation is present in the original PDF and lost in the converted TeX. It matters for nonreal characters.

Now let $q=p^k$ and let $\chi$ be primitive. Since it does not descend to $p^{k-1}$, there is a unit $u\equiv 1(\mathrm{mod}{p}^{k-1})$ with $\chi (u)\ne 1$. For $k=1$, reduction is to the unit group modulo one. If $p\mid a$, then $a(u-1)\equiv 0(\mathrm{mod}q)$, so multiplication of the summation variable by $u$ leaves its exponential factor unchanged. It follows that $\hat{\chi }(a)=\chi (u)\hat{\chi }(a)$, and therefore $\hat{\chi }(a)=0$. Also $\chi (a)=0$. This proves the formula at every nonunit as well as every unit, including $a=0$.

For a primitive Dirichlet character the previous formula gives $|\hat{\chi }(a)|=|\chi (a)||\hat{\chi }(1)|$. The Plancherel theorem for the unitary finite transform yieldsThus $|\hat{\chi }(1)|=1$, the normalized Gauss sum of a Dirichlet character magnitude.

For an imprimitive character modulo $p^k$ with $k\ge 2$, its values on residues are periodic modulo $p^{k-1}$: descent preserves the values on units, and divisibility by $p$ is unchanged by that shift. Splitting the sum into these residue classes gives a factor ${\sum }_{j=0}^{p-1}e(-j/p)=0$. Hence $\hat{\chi }(1)=0$. If $k=1$, the only imprimitive character is principal, and its Gauss sum is ${\sum }_{n=1}^{p-1}e(-n/p)=-1$, giving $|\hat{\chi }(1)|=p^{-1/2}$. All cases satisfy the required bound.

Every nonprincipal Dirichlet character modulo the prime $q$ is primitive, so its finite Fourier coefficients have modulus one off zero; the coefficient at zero is zero by character orthogonality. Fourier inversion theorem givesThe finite geometric series givesThe printed hint omits $n$ from the exponential; its literal constant summand would not obey the bound for arbitrary $N$. The geometric-series calculation proves the needed estimate independently. Pairing $a$ with $q-a$ givesThe last sum is a harmonic number. This proves the Pólya–Vinogradov inequality uniformly in $M$ and $N$; complete blocks of length $q$ also vanish by Orthogonality of Dirichlet characters.

Let $\chi$ be the quadratic character, equivalently the Legendre symbol. Zero is included among the square residue classes. For every integer $n$ its square-class indicator isFor a nonzero quadratic residue the right side is one, for a nonresidue it is zero, and for a multiple of $q$ it is one. Summing over the interval, the character contribution is $O(\sqrt{q}\log q)$ by the previous part, while the number of multiples of $q$ is $N/q+O(1)$. Thus the required count isThis counts the integers in the interval whose residue classes are squares. When the interval exceeds one period, repeated appearances are counted; the displayed main term could not describe a count of distinct residue classes for arbitrary $N$.