# How are the infinity norm of Fourier transforms of sign vectors distributed?

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!

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
• 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. – Mert Sağlam Jun 24 '15 at 15:56