We can sums over multiplicative Dirichlet characters $\sum\limits_{N<n<M}\chi(n)$ using the Polya Vinogradov inequality by $\ll \sqrt{p}\log\,p .$ Is there a similar estimate when we sum over primitive roots modulo q, where q is a fixed integer: $$\sum\limits_{\substack{N<n<M\\ (n,q)=1}}e^{2\pi i \frac{n}{q}}$$

  • 3
    $\begingroup$ No; consider what happens with $N=1$ and $M=q/100$. $\endgroup$
    – Lucia
    Commented Mar 8, 2018 at 3:04
  • $\begingroup$ Hi, I do not understand what you mean. $\endgroup$
    – Claus
    Commented Mar 8, 2018 at 3:25
  • $\begingroup$ You say "primitive roots", but your sum is over all reduced residue classes; is that what you mean? $\endgroup$ Commented Mar 8, 2018 at 7:42
  • 1
    $\begingroup$ Lucia meant that for $0<\frac{n}{q}<1/100$ we have $\mathrm{Re}\,e^{\frac{2\pi i n}{q}}=\cos\left(\frac{2\pi i n}{q}\right)>\cos\left(\frac{\pi}{50}\right)$ and thus for $M=q/100, N=1$ the real part of your sum is at least $\cos\left(\frac{\pi}{50}\right)\#\{N<n<M: (n,q)=1\}$, i.e. you don't have any nontrivial estimate (up to some constant). $\endgroup$ Commented Mar 8, 2018 at 8:02
  • 1
    $\begingroup$ Also, unlike in the case of Dirichlet characters, your sum may be not bounded uniformly in $M$ and $N$, because the "complete" sum (with $N=0, M=q$) equals $\mu(q)$, which can be nonzero $\endgroup$ Commented Mar 8, 2018 at 8:43

1 Answer 1


The standard approach would use the Möbius function: \begin{align*} \sum_{\substack{N<n<M\\ (n,q)=1}}e^{2\pi i n/q} &= \sum_{N<n<M}e^{2\pi i n/q} \sum_{d\mid(n,q)} \mu(d) \\ &= \sum_{d\mid q} \mu(d) \sum_{\substack{N<n<M \\ d\mid n}}e^{2\pi i n/q} \\ &= \sum_{d\mid q} \mu(d) \sum_{N/d<m<M/d}e^{2\pi i m/(q/d)}. \end{align*} The inner sum is now a geometric series which can be evaluated exactly or approximated in standard ways....


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.