# Correlation of Fourier transforms of characteristic functions

Let $A$ and $B$ ($A\subset B$) be subsets of a finite abelian group $G$. (For the sake of argument, you can take $G$ to be $\mathbb{Z}/p\mathbb{Z}$ for large $p$, say.) Write $1_S$ for the characteristic function of any subset $S\subset G$. Put the counting measure on $G$ and $\widehat{G}$, so that, for instance, $|1_S| = |S|$, where $|S|$ is the number of elements of $S$. Normalize the Fourier transform on $G$ so that it is an isometry: $|\widehat{f}|_2 = |f|_2$.

What upper bounds can be given for the size of $|\widehat{1_A} \widehat{1_B}|_1$?

To be precise: Cauchy-Schwarz gives $|\widehat{1_A} \widehat{1_B}|_1\leq |\widehat{1_A}|_2 |\widehat{1_B}|_2 = |1_A|_2 |1_B|_2 = \sqrt{|A| |B|}$. On the other hand, $\left|\sum_x \widehat{1_A}(x) \widehat{1_B}(x)\right| = \left|\sum_g 1_A(g) 1_B(g)\right| = \left|\sum_g 1_A(g)\right| = |A|$, suggesting there might be some room for improvement.

So, the question could be made more pointed, as follows: if $|\widehat{1_A} \widehat{1_B}|_1$ is closer to $\sqrt{|A| |B|}$ than to $|A|$, what follows about $|A|$ and $|B|$? What are necessary and sufficient conditions for $|\widehat{1_A} \widehat{1_B}|_1$ to be bounded by a constant times $|A|$?

• I should add that $|\widehat{1_A} \widehat{1_B}| = |A|$ holds for the extreme cases $B=A$ and $B=G$, as well as for any shift $B=A+g$. – H A Helfgott Dec 2 '13 at 17:13
• Reminds me a bit of the uncertainty principle of Donoho and Stark. – Dirk Dec 2 '13 at 18:34
• It seems that the subscript $1$ is missing in $|1_S|$ and in $|\widehat{1_A}\widehat{1_B}|$ in your comment. Also, are you sure you are interested in the norm $|\widehat{1_A}\widehat{1_B}|_1$ and not in $|\widehat{1_A}\overline{\widehat{1_B}}|_1$? (For $\langle \hat f,\hat g\rangle=\langle f,g\rangle$ to hold, the scalar product is to be defined as $\sum_\chi \hat f(\chi)\overline{\hat g(\chi)}$.) – Seva Dec 2 '13 at 19:32
• @Seva: In this case the $\ell^k$ norm of $\hat{f}$ is defined to be $(\sum_t |f(t)|^k)^{1/k}$, so it doesn't matter whether or not we include the complex conjugate - it will be removed by the absolute value. – Eric Naslund Dec 3 '13 at 2:19
• @Eric Naslund: this is not my point. What I mean is that $\sum_x\widehat{1_A}(x)\widehat{1_B}(x)$ is not equal to $\sum_g 1_A(g)1_B(g)$, but to $\sum_g 1_A(g)1_{-B}(g)$. Therefore, I suspect that in the original question should refer to $\widehat{1_A}\overline{\widehat{1_B}}$ instead of $\widehat{1_A}\widehat{1_B}$. Agreed? – Seva Dec 3 '13 at 6:31