Let $D$ be a subset of $\mathbb Z/n \mathbb Z$ containing $0$. For $m$ an integer, set $$\alpha(m,D)=\sum_{d \in D} e\left (\frac{m d }{n}\right ),$$ where as usual $e(x) = e^{2 i \pi x}$ This is an exponential sum (or if you like: character sum). Obviously $|\alpha(m,D)| \leq |D|$.

Now consider $$\sigma(D) = \frac{1}{n} \sum_{m=0}^{n-1} |\alpha(m,D)|.$$

A simple upper bound using Cauchy-Schwarz for $\sigma(D)$ is $\sigma(D) \leq \sqrt{ |D|}$, which is better than the trivial bound $\sigma(D) \leq |D|$. But here I am interested in a lower bound:

is it true that $\sigma(D) \geq 1$, with equality only if $D$ is a subgroup of $\mathbb Z/n \mathbb Z$ ?

This seems true on some numerical tests I have done, and this seems a very elementary question , but I don't see how to prove it at this time (I might be missing something trivial). More generally, I am interested in any information or reference on this number $\sigma(D)$. It appears in the error term in the formula for the number of primes $p \leq x$ which residues modulo $n$ is in $D$.


1 Answer 1


This seems easier than you might have expected. Up to normalization, your quantities $\alpha(m,D)$ are Fourier coefficients of the indicator function of $D$ (for which reason many people would rather use the notation $\hat 1_D(m)$). As such, they satisfy the Parseval identity $$ \sum_m |\alpha(m,D)|^2 = n|D|. $$ In view of $|\alpha(m,D)|\le|D|$, this yields $$ n|D| \le \sum_m |D| |\alpha(m,D)|, $$ whence $$ \sigma = \frac1n \sum_m |\alpha(m,D)| \ge 1. $$ Moreover, for equality to hold, one needs all $|\alpha(m,D)|$ to be equal to either $0$ or $|D|$, which is only possible if $D$ is a coset of a subgroup of ${\mathbb Z}/n{\mathbb Z}$.

  • $\begingroup$ That was easy indeed! Thank you very much. I am still interested in any reference talking of these numbers, for example, better upper bounds in special cases, etc. $\endgroup$
    – Joël
    Commented Dec 24, 2012 at 14:54
  • $\begingroup$ As far as references are concerned, you can check "On the Littlewood problem modulo a prime" by Green and Konyagin, or the joint papers of Konyagin and myself "Character sums in complex half-planes" and "On the distribution of exponential sums". $\endgroup$
    – Seva
    Commented Dec 24, 2012 at 15:47
  • $\begingroup$ For what it's worth, the same inequality can be proved with any finite abelian group $G$ in place of ${\mathbf Z}/(n)$: for any nonempty subset $D$ of $G$ and character $\chi$ of $G$, let $\alpha_G(\chi,D) = \sum_{g \in D} \chi(g)$. Then $\alpha(m,D)$ in the original problem is $\alpha_{{\mathbf Z}/(n)}(\chi,D)$ where $\chi(d) = e^{2\pi imd/n}$. We have $(1/|G|)\sum_{\chi} |\alpha_G(\chi,D)| \geq 1$, with equality if and only if $D$ is a coset of a subgroup of $G$. The last step, as in the case of ${\mathbf Z}/(n)$, depends on the uncertainty principle for $G$. $\endgroup$
    – KConrad
    Commented Nov 30, 2013 at 19:46

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.