16
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ 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 $\endgroup$ Aug 20, 2012 at 1:33
  • $\begingroup$ @Gerhard: If you are correct, then perhaps the appearance of $\sqrt{3}$ in my example is not a coincidence... $\endgroup$ Aug 20, 2012 at 1:40
  • 2
    $\begingroup$ @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. $\endgroup$
    – Igor Rivin
    Aug 20, 2012 at 2:24
  • 1
    $\begingroup$ 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 $\endgroup$ Aug 20, 2012 at 16:42
  • 1
    $\begingroup$ @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! $\endgroup$
    – Igor Rivin
    Aug 20, 2012 at 17:59

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I think that $r_{\text{min}} \le d$ is often attributed to Lévy as well as Steinitz (Wiki). $\endgroup$
    – LSpice
    Apr 2, 2019 at 2:21

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.