7
$\begingroup$

I have proved a simple Lemma that I need for a larger result, and I was wondering whether it is actually another more famous result in disguise.

The lemma says that for any set of vectors in $\mathbb{R}^n$, it is possible to choose a set of coefficients in ${-1,+1}$ such that the weighted sum of the vectors is close to the origin. The interesting thing (to me, non-mathematician) is that how close depends on the dimensionality of the space and not on the number of vectors.

Lemma Consider a set of $m\geq1$ vectors $\{v_{i}\}_{i=1}^{m}$ in $\mathbb{R}^{n}$, $n\geq1$, such that $||v_{i}||_{\infty}\leq c$. Then there exists a vector of coefficients $\{x_{i}\}_{i=1}^{m}$ , $x_{i}\in\{-1,+1\}$ , such that $\left\Vert \sum_{i=1}^{m}x_{i}v_{i}\right\Vert \leq nc$.

(Note that the bound depends on the dimension $n$, but not the number of vectors $m$.)

$\endgroup$
0

2 Answers 2

10
$\begingroup$

I don't have access right now to search tools, but the result is is due to Steinitz and might be described in

Kadets, Mikhail I.; Kadets, Vladimir M. (1997). "Chapter 2.1 Steinitz's theorem on the sum range of a series, Chapter 7 The Steinitz theorem and B-convexity". Series in Banach spaces: Conditional and unconditional convergence. Operator Theory: Advances and Applications. 94.

Anyway, the right book by V. Kadets contains the result and best known estimates for the constant in terms of the dimension.

EDIT: I asked Gideon Schechtman for a good reference, and he provided

this

$\endgroup$
1
  • $\begingroup$ Thanks! It seems that the book contains exactly this result (as much as I can see from the Google Books preview; I will order it for our library). $\endgroup$
    – Andrea
    Apr 8, 2012 at 18:29
1
$\begingroup$

It sounds like a Littlewood-Offord-type result to me, but I'll have to leave it to the experts to weigh in on this.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.