Let $p$ be a large prime. I would like to say that the multi-set $[1,p^{1-\varepsilon}]^2 = \{ab \mod p: a, b \in [1,p^{1-\varepsilon}]\}$ is close to uniformly distributed, i.e. that every nonzero residue class mod $p$ occurs with almost equal frequency.

Quantitatively, is it true that (almost?) every nonzero residue class appears at most $O(p^{1-2\varepsilon})$ times?

  • 6
    $\begingroup$ True for each $\epsilon < 1/4$ by the bound on Kloosterman sums. Probably true for each $\epsilon < 1/2$ but I don't think we know how to prove this. $\endgroup$ Commented Sep 7, 2015 at 15:58

2 Answers 2


Here is a more explicit version of Noam Elkies's comment.

Theorem. Let $p>2$ be a prime number. Let $\mathcal{U},\mathcal{V}\subseteq\{1,2,\dots,p-1\}$ be two intervals, and let $r\in\{1,2,\dots,p-1\}$ be a nonzero residue modulo $p$. Then $$\Biggl|\sum_{\substack{u\in\mathcal{U},\ v\in\mathcal{V} \\ uv\equiv r \pmod{p}}} 1-\frac{|\mathcal{U}||\mathcal{V}|}{p-1}\Biggr|<2p^{1/2}(\log p)^2.$$

You can find a proof from scratch here (see Theorem 9).


If you're OK with "almost every", we can use a $L^2$ method and multiplicative character sum bounds to do better.

Let's estimate $$ \sum_{c \in \mathbb F_p^\times} \left( \left[\sum_{a,b \in I | ab=c } 1\right] - p^{1-2\epsilon}\right)^2 $$

by Plancherel $$= \frac{1}{p-1} \sum_{\chi \in \left( \mathbb F_p^{\times} \right)^{\vee}, \chi \neq 1} \left | \sum_{a,b \in I} \chi(ab) \right|^2 $$

and multiplicativity$$= \frac{1}{p-1} \sum_{\chi \in \left( \mathbb F_p^{\times} \right)^{\vee}, \chi \neq 1} \left | \sum_{a\in I} \chi(a) \right|^4 $$

Now assume we have a nontrivial character sum bound $\left| \sum_{a \in I} \chi(a) \right| \leq N$ for all nontrivial characters $\chi$. Then we continue:

$$ \leq \frac{1}{p-1} \sum_{\chi \in \left( \mathbb F_p^{\times} \right)^{\vee}, \chi \neq 1} N^2 \left | \sum_{a\in I} \chi(a) \right|^2 \leq \frac{1}{p-1} \sum_{\chi \in \left( \mathbb F_p^{\times} \right)^{\vee} } N^2 \left | \sum_{a\in I} \chi(a) \right|^2 = N^2 p^{1-\epsilon} $$

Then we see that

$$\left[\sum_{a,b \in I | ab=c } 1\right] \leq 2 p^{1-2\epsilon} $$

for all but

$$\frac{ N^2 p^{1-\epsilon}}{ p^{2-4 \epsilon} } = N^2 p^{3\epsilon-1}$$

This is $\ll p$ as long as $N \ll p^{1 - 3\epsilon/2}$. Using the Pólya-Vinagradov bound where $N \approx p^{1/2}$, this works for $\epsilon <1/3$. Using the Burgess bound we can do slightly better, but not get all the way to $\epsilon = 1/2$, which would require $N= p^{1/4}$ - full square root cancellation, outside of reach.

  • $\begingroup$ Should it be $1/p$ in front of Plancherel instead of $1/(p-1)$? $\endgroup$
    – Xiaoyu He
    Commented Sep 9, 2015 at 1:58
  • $\begingroup$ @alkjash I don't think so, because I'm doing it on a group of size $p-1$, the multiplicative group. $\endgroup$
    – Will Sawin
    Commented Sep 9, 2015 at 2:01
  • $\begingroup$ Yea, sorry. I just realized that the true mean should be $|I|^2/(p-1)$, not $|I|^2/p$. $\endgroup$
    – Xiaoyu He
    Commented Sep 9, 2015 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.