most recent 30 from http://mathoverflow.net 2013-05-19T06:45:53Z http://mathoverflow.net/feeds/question/103364 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103364/growth-rate-of-the-infinity-norm-of-discrete-fourier-transform-of-1-1-vectors kodlu 2012-07-28T05:14:07Z 2012-08-14T01:22:01Z

<p>Let $f=(f_0,\ldots,f_{n-1})$ be a vector with entries drawn from $V_n=${$\pm 1$}. 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. </p> <p>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.</p>

http://mathoverflow.net/questions/103364/growth-rate-of-the-infinity-norm-of-discrete-fourier-transform-of-1-1-vectors/103555#103555 kodlu 2012-07-30T21:34:40Z 2012-07-31T01:04:32Z

<p>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.</p> <p>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".</p> <p>Please feel free to edit, if you know any other lengths for which an analytic construction exists achieving optimality or near optimality.</p>