Our starting point is an improved version of a result of D. Hajela related to a question of Koml{o}s: we show that if $f(n)$ is a function such that $limlimits_{ntoinfty }f(n)=infty $ and $f(n)=o(n)$, there exists $n_0=n_0(f)$ such that for every $ngeqslant n_0$ and any $Ssubseteq {-1,1}^n$ with cardinality $|S|leqslant 2^{n/f(n)}$ one can find orthonormal vectors $x_1,ldots ,x_nin {mathbb R}^n$ that satisfy $$|epsilon_1x_1+cdots +epsilon_nx_n|_{infty }geqslant csqrt{log f(n)}$$ for all $(epsilon_1,ldots ,epsilon_n)in S$. We obtain analogous results in the case where $x_1,ldots ,x_n$ are independent random points uniformly distributed in the Euclidean unit ball $B_2^n$ or any symmetric convex body, and the $ell_{infty }^n$-norm is replaced by an arbitrary norm on ${mathbb R}^n$.
Download