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!