From: Gerhard Woeginger Subject: Re: Steinitz lemma Date: 28 Apr 1999 15:33:56 +0200 Newsgroups: sci.math.research Keywords: Unit vectors which sum to zero can be ordered to partial sums small In article gerry@mpce.mq.edu.au (Gerry Myerson) writes: >From: gerry@mpce.mq.edu.au (Gerry Myerson) >Subject: Re: Steinitz lemma >Date: Wed, 28 Apr 1999 09:34:41 +1100 >In article <37263D55.49BC@club-internet.fr>, pbornszt@club-internet.fr wrote: >=> I'm looking for references on Steinitz lemma: >=> >=> There exists a constant K(d)=< 5^(d-1)/2 such that: >=> >=> If we have n unit vectors ( a variation : n vectors with norms =< 1) >=> in R^d , we can always find a way of to order these vectors >=> V1,V2,...,Vn so as to have : >=> for every i in {1,2,...,n} : || V1+V2+...Vi|| =< K >=> (where ||..|| denotes the norm...) >Is there a missing hypothesis here? If the vectors all point in the same >direction, the conclusion can't hold for i > K. Maybe the vectors are >supposed to add up to zero? >Gerry Myerson (gerry@mpce.mq.edu.au) Yes, the vectors are supposed to add up to zero. Steinitz proved this result in 1913, a long time ago. In the mean time, much stronger results have been derived and the value 5^(d-1)/2 has been improved to d. This is also the strongest possible result that holds true for arbitrary norms. The reference is V.S. Grinberg and S.V. Sevastianov: "Value of the Steinitz constant". Functional Anal. Appl. 14 (1980), 125-126. (this is the English translation of the Russian journal paper "O velicine konstanty Steinica" in Funkcional. Anal. i Prilozen. 14/2 (1980), 56-57) For specific norms, improvements over d are possible. E.g. for the Euclidean norm in R^2, the best possible value is sqrt(5)/2. This has been proved by W. Banaszczyk: "The Steinitz constant of the plane". Journal fuer Reine und Angewandte Mathematik 373 (1987), 218-220. MR 88e: 52016. Gerhard Woeginger