# Lower bound for exponential sums.

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-Schwartz 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$.

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}$.
• 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$. – KConrad Nov 30 '13 at 19:46