Range of discrete Fourier transform for binary strings $\DeclareMathOperator\C{\mathbb{C}}$Let X be the set of all $n$-bit binary strings, $x=(x_1,\ldots x_n)$ where where $x_i\in\{-1,1\}$. Now consider the discrete fourier transform $F$, which maps elements of X into $\C^n$ (n complex numbers).  What is the range of $F$ over $X$,
$$FX = \{c\in \C^n\mid \exists x\in X: c=Fx\},$$
as a subset of $\C^n$?  It is clearly a discrete subset and must satisfy various symmetries (such as a rotation like symmetry from "rotations" of a binary string), as well as certain bounds on its size (from Parseval's theorem), but is there a nice characterization of it?
 A: First, separate real and imaginary parts of each column of the DFT matrix, write them side-by-side, thus form a $2n\times n$ real matrix $L^{*}$, where $^*$ denotes the  transpose. Thus, $L^{*}x(2k) = real(Fx(k))$ and $L^{*}x(2k+1) = imag(Fx(k))$ for $k=0,1,\dots,n-1$.
Consider $x_i$ as i.i.d. Rademacher random variables. Form a new random vector by $\xi := L^{*}x\in\mathbb{R}^{2n}$. Let $\mu_{\xi}$ be the probability distribution measure, and $\Phi_{\xi}:\mathbb{R}^{2n}\to\mathbb{C}$ be the characteristic function (i.e., the Fourier transform of $\mu_{\xi}$) of $\xi$.
\begin{eqnarray}
\Phi_{\xi}(\gamma) = Exp(e^{-2\pi i\langle\gamma,\xi\rangle})
= Exp(e^{-2\pi i\langle L\gamma, x\rangle})
= Exp(e^{-2\pi i\sum_{k=0}^{n-1}\langle\gamma,e_k\rangle x_k})
= \prod_{k=0}^{n-1} Exp(e^{-2\pi i\langle\gamma,e_k\rangle x_k})
\end{eqnarray}
where $e_k$ is the $k$th row of $L$. The last ($=$) is due to independence of $x_k$'s. Since $x_k$ is a Rademacher r.v., then $Exp(e^{-2\pi i\langle\gamma,e_k\rangle x_k})=\cos(2\pi \langle\gamma,e_k\rangle)$. Finally, if $B\subseteq\mathbb{R}^{2n}$, then
$$
Prob(\xi\in B) = \int_{\mathbb{R}^{2n}} 1_B \ d\mu_{\xi}
= \int_{\mathbb{R}^{2n}} \overline{\hat{1}_B(\gamma)} \Phi_{\xi}(\gamma) d\gamma 
= \int_{\mathbb{R}^{2n}} \overline{\hat{1}_B(\gamma)} \prod_{k=0}^{n-1} \cos(2\pi \langle\gamma,e_k\rangle)d\gamma
$$
where $1_B(x) = 1 \Leftrightarrow x\in B$ and $1_B(x) = 0 \Leftrightarrow x\notin B$. $\hat{f}$ denotes the Fourier transform of $f$.
We may interpret $Prob(\xi\in B) = 2^{-n}|B\cap L^{*}X|$, the ratio of elements of $L^{*}X$ that is in the set $B$.
Note: Clearly, $L$ could be chosen above any $N\times d$ real matrix in order to give a similar description for the set $L^{*}X =\{L^{*}x = \sum_{k=0}^{N-1} x_k e_k : x_k\in\{-1,1\}\} $
