Show that $Z < \sqrt p$ if $\left( \frac{m - n}p \right) = 1, m \in \mathcal N, n \in \mathcal N, m \ne n$.

Question

Would you please help me solve Exercise 4.2(b) on page 20 of the online document Characters. I repeat that exercise here:

Let $p$ be a prime, $p \equiv 1$ (mod $4$), and let $\mathcal N$ be a set of $Z$ residue classes modulo $p$. Suppose that $\left( \frac{m - n}p \right) = 1$ whenever $m \in \mathcal N, n \in \mathcal N$, and $m \ne n$. Show that $Z < \sqrt p$.

$\left( \frac \cdot p \right)$ is the Legendre symbol.

The document is a supplement to An Introduction to the Theory of Numbers by Niven, Zuckerman, and Montgomery.

I am trying to use the result of the previous part of the exercise: $$\sum_{m \in \mathcal N} \sum_{n \in \mathcal N} \left( \frac{m - n}p \right) = \frac1{\sqrt p} \sum_{a=1}^p \left( \frac a p \right) \left| \sum_{n \in \mathcal N} e^{2\pi ian/p} \right| ^2. \tag a$$ The left side simplifies to $$\sum_{m \in \mathcal N} \sum_{n \in \mathcal N} \left( \frac{m - n}p \right) = \sum_{\substack{m, n \in \mathcal N \\ m \ne n}} 1 = Z^2 - Z = Z(Z - 1)$$ because there are $Z$ ways to choose $m$, and $Z$ ways to choose $n$, which gives $Z^2$ total ordered pairs $(m, n)$ less the $Z$ pairs for which $m = n$. The right side, with more work, simplifies to the same expression. In other words, all I did was to verify (a) for the special case of Exercise 4.2(b), but that does not help me prove that $Z < \sqrt p$.

If I can prove that the right side of (a) is less than either $p - Z$, $(Z - 1) \sqrt p$, or $Z\sqrt p - Z^2/\sqrt p$, I am done.

Answer 1

I credit reuns for this answer although he may have a more obvious one. If you can provide it, I will accept it over mine. When I tried what I thought reuns suggested in his comments, I got $Z < \sqrt p + 1$. I had to work a little harder, namely by playing with the upper limit of the outer sum's index, to get the tighter, desired result $Z < \sqrt p$.

Introduce the function $$f(n) = \begin{cases} 1 & \text{if } n \in \mathcal N, \text{ or}\\ 0 & \text{otherwise.} \end{cases}$$ $f(n)$ is arithmetic with period $p$, so we can use equation (2) on page 2 of the same online document Characters. Substitution into equation (4) on page 3 gives the starting point for the following work: \begin{align} p \sum_{n=1}^p |f(n)|^2 & = \sum_{a=1}^p \left| \sum_{n=1}^p f(n) e^{-2 \pi ian/p} \right|^2\\ p \sum_{n \in \mathcal N} 1^2 & = \sum_{a=1}^p \left| \sum_{n \in \mathcal N} e^{-2 \pi ian/p} \right|^2\\ pZ & = \sum_{a=1}^{p-1} \left| \sum_{n \in \mathcal N} e^{-2 \pi ian/p} \right|^2 + \left| \sum_{n \in \mathcal N} e^0 \right|^2\\ & = \sum_{a=1}^{p-1} \left| \sum_{n \in \mathcal N} e^{-2 \pi ian/p} \right|^2 + Z^2\\ & \ge \sum_{a=1}^{p-1} \left( \frac ap \right) \left| \sum_{n \in \mathcal N} e^{-2 \pi ian/p} \right|^2 + Z^2 \end{align} because a sum of non-negative terms is at least equal to the same sum but with some of the terms having opposite signs due to the insertion of the Legendre symbol.

Let us now work with equation (a) in my question. As I explained there, the left side is $Z(Z - 1)$. On the right side, we can change the upper limit of the outer sum's index from $p$ to $p - 1$ because $\left( \frac pp \right) = 0$. Then into the right side we can substitute the above inequality (because $\left| e^{-i\theta} \right| = \left| e^{i\theta} \right|$, it does not matter that the exponents are of opposite sign) to get $$Z(Z - 1) < \frac1{\sqrt p} \left( pZ - Z^2 \right),$$ which simplifies to $Z < \sqrt p$.