Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 9 down vote accepted

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

share|improve this answer
    
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. –  Joël Dec 24 '12 at 14:54
    
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". –  Seva Dec 24 '12 at 15:47
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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