approximate uncertainty principle for finite abelian groups

Question

Edit: we cannot find such an example. It would imply a negative solution to the KS${}_2$ conjecture which has now been proven by Marcus, Spielman, and Srivastava in this paper.

In fact, their solution implies that there always exists $S$ such that any $f$ supported on $S$ (or $S^c$) satisfies $\|\frac{1}{2}\hat{f} - \hat{f}|_T\|_2 \leq O(\sqrt{\epsilon})\cdot\|\hat{f}\|_2$.

---

Can we find, for every $\epsilon > 0$, an example of the following?

$\bullet$ a finite abelian group $G$

$\bullet$ a small subset $T$ of the dual group $\hat{G}$ (meaning $|T| \leq \epsilon |\hat{G}|$)

such that for any subset $S$ of $G$, there is a nonzero complex valued function $f$ supported either on $S$ or $S^c$ whose Fourier transform is approximately supported on $T$ (meaning $\|\hat{f} - \hat{f}|_T\|_2 \leq \epsilon \|\hat{f}\|_2$).

It seems unlikely, but I don't know any version of the uncertainty principle that would forbid this.

---

Two comments: (1) This arose out of discussions I had with Chuck Akemann about the Kadison-Singer problem. It wouldn't, as it stands, imply a negative solution to Kadison-Singer, but it would be close and (I believe) could probably be easily converted into a full negative solution. (2) Since either $S$ or $S^c$ has cardinality at least $|G|/2$, one could consider assuming $|S| \geq |G|/2$ and demanding that $f$ be supported on $S$. But I know that this makes the problem too hard. (Given $T$, I can always find an $S$ with $|S^c|/|G| = O(\sqrt{\epsilon})$ such that no nonzero function supported on $S$ has Fourier transform approximately supported on $T$.)

Answer 1

The restricted isometry property, or RIP (formerly known as the uniform uncertainty principle, or UUP, as per your suspicion that uncertainty principles should be relevant) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-4} |G|$; this property was first proven (for $G$ a cyclic group, and with exponent 6 instead of 4) by Candes and myself, and then (for arbitrary abelian $G$, and with exponent 4) by Rudelson and Vershynin. If one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (of sparsity less than $c |G|/\log^4 |G|$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP, and so the situation described in your post will not occur.

If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can obtain an analogous result in the Fourier setting and give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group. But unfortunately this is probably outside of reach of the technology described in the above papers. (But there has been a number of advances in that area since then, which I have not followed as closely. For instance, there has been a slight improvement to the Rudelson-Vershynin bound obtained recently by Cheraghchi, Guruswami, and Velingker, although for the problem at hand, it does not appear to lower the exponent $4$ further.)

ADDED LATER: Actually, on thinking about it a bit more, the RIP is probably too strong a property for this purpose (it creates a set S that becomes a counterexample for all sparse T, whereas for your problem it would suffice to find a different counterexample S for each sparse T). The situation is then a bit closer to my original paper with Candes and Romberg which only needed an oversampling of order $\log |G|$ or so, though we didn't phrase our analysis in an easily portable form and one would have to look through the argument in detail to check if the bounds there indeed give a negative answer to your question for $\varepsilon < c/\log |G|$. I still don't know how to get rid of the final logarithm, though.