Skip to main content
2 of 2
edited title
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126

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

H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126