13
$\begingroup$

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

Improve this question
$\endgroup$
10
  • $\begingroup$ 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$. $\endgroup$
    – H A Helfgott
    Commented Dec 2, 2013 at 17:13
  • 1
    $\begingroup$ Reminds me a bit of the uncertainty principle of Donoho and Stark. $\endgroup$
    – Dirk
    Commented Dec 2, 2013 at 18:34
  • $\begingroup$ 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)}$.) $\endgroup$
    – Seva
    Commented Dec 2, 2013 at 19:32
  • $\begingroup$ @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. $\endgroup$
    – Eric Naslund
    Commented Dec 3, 2013 at 2:19
  • $\begingroup$ @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? $\endgroup$
    – Seva
    Commented Dec 3, 2013 at 6:31

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .