Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.)

share|improve this question
add comment

2 Answers

up vote 10 down vote accepted

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

share|improve this answer
    
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). –  Andrea Apr 8 '12 at 18:29
add comment

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.

share|improve this answer
    
Thanks for mentioning Littlewood-Offord problems (en.wikipedia.org/wiki/Littlewood%E2%80%93Offord_problem), it might be useful to me in the future. –  Andrea Apr 8 '12 at 18:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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