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

I have $n$ unit-length vectors $v_i$ in $\mathbb{R}^3$, whose sum is zero: $$ v_1 + v_2 + \cdots + v_n = 0 \; .$$ Now I form the closed polygon $P$ in space by placing them head to tail. So the vertices of $P$ are $$ 0, v_1, (v_1+v_2), \ldots (v_1+\cdots v_{n-1}), 0 \; .$$ My question is:

What is the minimum excursion from the origin achievable by shuffling the vectors by a permutation of $(1,2,\ldots,n)$?

For example, the $12$ red vectors below wander $\sqrt{10}$ from the (purple) origin, but the light blue vectors—the same in a different order—stay within $\sqrt{3}$.
           Vector Sum
(These particular vectors derive from the vertices of a cuboctahedron, so some are negations of others.)

Is there some constant $r_{\min}$ independent of $n$ such that the sum can always be arranged to be at most $r_{\min}$, i.e., lie within an origin-centered ball of that radius? Or must $r_{\min}$ depend on $n$? Is there some natural algorithm for minimizing the excursion, or must I (in the worst case) try all $n!$ permutations?

Of course the same question can be asked in any dimension $\mathbb{R}^d$, but my focus is $\mathbb{R}^3$. Thanks for ideas and/or pointers!

Update1. The suggestion (in the comments) that $r_{\min} = \sqrt{d}$ in $\mathbb{R}^d$, based on an answer to the previous MO question, "Bounding a signed sum of complex numbers," is intriguing, and may be true. But I do not see that it is proved by that answer.

Update2. With key phrases suggested by Nik Weaver, I found a 1981 paper by Imre Bárány, "A Vector-Sum Theorem and its Application to Improving Flow Shop Guarantees" (Math. Oper. Res. link), which shows that $r_{\min} < \frac{3}{2} d$.

share|improve this question
    
I think the version in the plane has appeared as an olympiad problem, and that the number sqrt(2) appears in the answer. (Or I could be remembering something else.) It might have appeared on MathOverflow too. Gerhard "Ask Me About System Design" Paseman, 2012.08.19 –  Gerhard Paseman Aug 20 '12 at 1:33
    
@Gerhard: If you are correct, then perhaps the appearance of $\sqrt{3}$ in my example is not a coincidence... –  Joseph O'Rourke Aug 20 '12 at 1:40
2  
@Gerhard is correct. This was a MO question a few months ago; the proof generalizes to $d$ dimensions, $\sqrt{d}$ is the magic constant, but I am having trouble finding the right keyword to search on. –  Igor Rivin Aug 20 '12 at 2:24
1  
I think Igor is thinking about this: mathoverflow.net/questions/98288/… . Either that or one of the linked questions in the answer. Gerhard "Ask Me About System Design" Paseman, 2012.08.20 –  Gerhard Paseman Aug 20 '12 at 16:42
1  
@Gerhard: There once was a fellow named Henschel Whose limericks were self-referential My limericks, said he Refer NOT to me But to themselves, THAT's essential! –  Igor Rivin Aug 20 '12 at 17:59
show 6 more comments

1 Answer 1

This is a famous open problem, $r_{min}\le d$ is known as the Steinitz-lemma. It is conjectured that $r_{min}= O(\sqrt d)$ but even $r_{min}= o(d)$ is open. See also http://www.renyi.hu/~barany/cikkek/steinitz.pdf , section 3.

share|improve this answer
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.