5
$\begingroup$

This is a follow up to an earlier resolved question. Define the $n$-dimensional discrete Fourier transform via the matrix $$ D_{s,t} := \omega^{st}, $$ where $\omega=\exp(-2\pi i/n)$. Notice that $D$ is $\sqrt{n}$ times a unitary.

Observe that for any $x$, it holds that $\|Dx\|_\infty\geq \|x\|_2$, and in particular if $x\in\{\pm 1\}^n$, $\|Dx\|_\infty\geq \sqrt{n}$.

The earlier question was whether this bound is tight. The answer is a yes: there are explicit $x\in\{\pm1\}^n$ such that $\|Dx\|_\infty =\sqrt{n+1}$ when $n$ is a prime or power of two minus one.

Here is the follow up question. Suppose $x$ is chosen uniformly at random from $\{\pm 1\}^n$. How is $\|Dx\|_\infty$ distributed? An easy martingale Chernoff bound + union bound argument shows that

$$ \Pr_{x}\left[\|Dx\|_\infty \geq (\lambda +1)\sqrt{n}\right]\leq ne^{-2\lambda^2}, $$

which is useful when $\lambda \gg \sqrt{\log n}$ (and seems almost tight in this regime). Is it known, for instance, the probability that $\|Dx\|_\infty\leq 5\sqrt{n}$? We know that this probability is at least $2^{-n}$, but is this the correct estimate? Should it be closer to $n^c /2^n$, higher, or lower?

Many thanks!

$\endgroup$
1
$\begingroup$

Special Case: In the answer to the earlier question you linked to, it is stated that the $m-$sequences of period $n=2^d-1,$ $d\geq 2$ give $\mid\mid D x\mid\mid_{\infty}=\sqrt{n+1}.$ Now these sequences are cyclic, with each cyclic shift distinct. This means, if there are $k(n)$ inequivalent $m-$sequences of period $n=2^d-1$, we know that the probability $$\mathbb{P}(\mid\mid D x\mid\mid_{\infty} \leq \sqrt{n+1}) \geq k(n) n 2^{-n}.$$ Now, $k(n)=\phi(2^d-1)/d=O(\phi(n)/\log(n))$ where $\phi(\cdot)$ is the Euler phi function and the quantity given is the number of distinct primitive polynomials of degree $d.$ If there are infinitely many primes of the form $2^d-1,$ we'd get $k(n)=O(n/\log n)$ or $$\mathbb{P}(\mid\mid D x\mid\mid_{\infty} \leq \sqrt{n+1}) \geq \frac{n^2 2^{-n}}{\log n},$$ infinitely often

In general, if we can find one sequence of low maximum DFT magnitude, all its cyclic shifts (whenever distinct) will also have the same maximum magnitude and yield low DFT sequences.

$\endgroup$
  • $\begingroup$ Thank you very much. I am studying the construction of Golomb to see if it can be generalized to larger max spectral norm sequences by starting from "almost irreducible" polynomials instead of irreducible polynomials. $\endgroup$ – Mert Sağlam Jun 24 '15 at 14:35
  • $\begingroup$ @Msaglam, how would you define almost irreducible? $\endgroup$ – kodlu Jun 24 '15 at 14:37
  • $\begingroup$ Unfortunately, I am not sure yet. I wonder having only few factors may give anything. $\endgroup$ – Mert Sağlam Jun 24 '15 at 14:43
  • $\begingroup$ I might think about it as well. Just so I understand, when you say "generalized to larger max spectral norm sequences" you mean a larger family containing more sequences, I presume. $\endgroup$ – kodlu Jun 24 '15 at 14:46
  • $\begingroup$ Oh, by larger max spectral norm, I meant the set of $x\in\{\pm\}^n$ satisfying $\|Dx\|_\infty \leq c\sqrt{n+1}$ for $c$ not necessarily 1, but potentially larger. $\endgroup$ – Mert Sağlam Jun 24 '15 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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