Maximum of finitely many Rademacher linear forms ($\mathrm{Pr}({\max }_i|u_i^T\xi |\le \alpha )>1-2m{e}^{-{\alpha }^2/2}$)

For independent Rademacher random variables and $\Vert u_i{\Vert }_2\le 1$, this bound holds for $\alpha >0$. The moment-generating function satisfies ${\prod }_j\cosh (t{u}_{ij})\le e^{t^2/2}$, with strict inequality for a nonzero vector and $t>0$. Applying the exponential Markov bound to both tails and then the union bound proves a strict failure bound; a zero vector has failure probability zero. At $\alpha =\sqrt{2\log (2m)}$, the success probability is strictly positive, ensuring a sign vector with all linear forms below that threshold.