6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$ Jul 28, 2012 at 5:37
  • 3
    $\begingroup$ 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)$. $\endgroup$
    – Ben Green
    Jul 28, 2012 at 8:46
  • $\begingroup$ $\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 :) $\endgroup$ Jul 28, 2012 at 9:27
  • $\begingroup$ @ Alexander Chervov: Thanks for your comments. @ Ben Green: Thanks. I'll have a look at what happens in the Legendre case. $\endgroup$
    – kodlu
    Jul 28, 2012 at 11:03
  • $\begingroup$ @Alexander: is this related to the $6\sqrt{n}$ that appears in Joel Spencer's "Six standard deviations suffice"? $\endgroup$
    – Nik Weaver
    Jul 28, 2012 at 16:29

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.