A note on norms of signed sums of vectors

Abstract

Our starting point is an improved version of a result of D. Hajela related to a question of Komlós: we show that if $f(n)$ is a function such that $\underset{n\to \infty }{\lim }f(n)=\infty$ and $f(n)=o(n)$, there exists $n_0=n_0(f)$ such that for every $n⩾n_0$ and any $S\subseteq \{-1,1{\}}^n$ with cardinality $|S|⩽2^{n/f(n)}$ one can find orthonormal vectors $x_1,\dots ,x_n\in {\mathbb{R}}^n$ that satisfy $$\Vert {\epsilon }_1{x}_1+\cdots +{\epsilon }_n{x}_n{\Vert }_{\infty }⩾c\sqrt{\log f(n)}$$ for all $({\epsilon }_1,\dots ,{\epsilon }_n)\in S$. We obtain analogous results in the case where $x_1,\dots ,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$.

accepted for publication in Advances in Geometry