Variability of DFT coefficient with length

15 Views Asked by At

This was asked on mathoverflow 15 months ago with no answers but some upvotes

Consider the unnormalized Fourier coefficients of subsets $D_g$ of $\mathbb Z/n \mathbb Z$, denoted by $$ \hat1_{D_g}(m,n)=\sum_{d \in {D_g}} e\left (\frac{m d }{n}\right ), $$ where $e(x) = e^{2 i \pi x}$ and the $D_g$ which are arithmetic series dilated by a geometric series, $$ D_g=2^g\{1,2,\ldots,s\},\quad g=1,\ldots,v. $$

Let $n$ be odd, fix an $m$ and a $g$ and say that a certain $n$ is very bad because it gives a very small (nearly zero) magnitude for $|\hat1_{D_g}(m,n)|.$

I am looking for a result of the form below, given $m,g,n$ there is some $n'$ in $[n,un]$ such that $$|\hat1_{D_g}(m,n')|=\left|\sum_{k=1}^s e\left (\frac{m k ~2^g }{n'}\right )\right|>c s,$$ for some constant $c$. How large should $u$ be?