Let $f=(f\_0,\ldots,f\_{n-1})$ be a vector in $V\_n=\{\pm 1\}^n$. Let 
$F=(F\_0,\ldots,F\_{n-1})$ 
be its (discrete) Fourier transform defined by 
$$
F\_k=\sum\_{x=0}^{n-1} f\_x \omega\_n^{x k}
$$
where $\omega\_n=\exp(2 \pi i/n)$. Let 
$$\theta\_n=\min \left( \max\_{0\leq k\leq n-1}|F\_k|: f \in V\_n \right).$$ 
Is anything known about the growth rate of $\theta\_n$ with $n$? I have quickly computed the values corresponding to $n=3,4,\ldots,7$ as
$$
(n,\theta\_n)=[(3,2/\sqrt{3}),(4,1),(5,3/\sqrt{5}),(6,\sqrt{2}),(7,3/\sqrt{7})].
$$
A lower bound on the growth rate would be fantastic, if it is known. 


The question can also be stated as computing the minimal infinity norm of the Fourier transform of the following difference of indicator functions $$\chi(A)-\chi(A^c)$$ where $A^c$ is the complement of $A$, as the set $A$ ranges over all subsets of $[n]$ so has an arithmetic combinatorics flavour.



Growth rate of the infinity norm of Discrete Fourier Transform of +1,-1 vectors
Here is my proposed answer based on what I have found out so far: Since the set $V\_n$ is a subset of the sphere $S\_{n-1}(\sqrt{n})$ in $R^n$ the minimum $\theta\_n$ is lower bounded by the minimum, cal it $\alpha\_n$, on this sphere. A vector $f=(\sqrt{n},0,\ldots,0)$ and all its cyclic shifts achieves equal magnitudes $F\_k=\sqrt{n}$ for all $k$ on its Fourier transform.


The quantity $\theta\_n/\sqrt{n} \rightarrow 1$ from above as $n\rightarrow \infty$ on the subsequence of primes if we consider the Legendre sequences. This also works for the so-called maximal length binary sequences of lengths $n=2^m-1, m\geq 2$ since they have $|F\_k|=\sqrt{n+1}$ for $k \neq 0$ as observed by Golomb in his book "shift register sequences".


Please feel free to edit, if you know any other lengths for which an analytic construction exists achieving optimality or near optimality.


