# Growth rate of the infinity norm of Discrete Fourier Transform of +1,-1 vectors

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.

-
In telecom this should be related to PAR - peak to average ratio for OFDM system. You ask about "peak". +1 or -1 - symbols transmitteed, OFDM is protocol which makes FT before transmission. As far as I heard PAR is big may be about 9 - but I do not know details... sorry – Alexander Chervov Jul 28 '12 at 5:37
The answer is basically $\sqrt{n}$ for large $n$.When $n$ is prime, an example should be given by the Legendre symbol $f_i = (i | n)$. – Ben Green Jul 28 '12 at 8:46
$\sqrt(n)$ corresponds to "average" power i.e. L^2 norm of any vector of +-1 is exactly $\sqrt(n)$. So if I interpret correctly what I heard from engineers, the answer should be not more $9 \sqrt(n)$. The question is important since if this "peak" value would be great it can "burn out" cell phone's brain :) – Alexander Chervov Jul 28 '12 at 9:27
@ Alexander Chervov: Thanks for your comments. @ Ben Green: Thanks. I'll have a look at what happens in the Legendre case. – kodlu Jul 28 '12 at 11:03
@Alexander: is this related to the $6\sqrt{n}$ that appears in Joel Spencer's "Six standard deviations suffice"? – Nik Weaver Jul 28 '12 at 16:29

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.

-