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

Is the following fact true?

Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k \in \mathbb{R}^2$, $\|w_i\|\leq 1$, such that $v_{\sigma(i)}=w_i-w_{i-1}$? (here, I assume $w_0=w_k$)

Edit. Related (known) facts:
1. The same fact in $\mathbb{R}^1$ is true. (can be easily proven by choosing $w_0=0$ and $\sigma(i)$ such that $\|w_i\|\leq 1$ for $w_i:=w_{i-1}+v_{\sigma(i)}$)
2. For each $\epsilon>0$ there exists a family of vectors $v_i$, such that $\max_i\|w_i\|>1-\epsilon$. See my comment below for the proof.

share|improve this question
1  
In $\mathbb{R}^2$, I see a configuration such that $\max\{\|w_i\|\} > \tfrac1{\sqrt{2}}-\epsilon$, but I do not see anything worse. –  Anton Petrunin Oct 2 '10 at 3:40
3  
There is a configuration with $\max\{\|w_i\|\}>1-\epsilon$ in $\mathbb{R}^n$ for any $n\in N$: in $\mathbb{R}^1$ just take $N−1$ numbers equal to 1 and $N$ numbers equal to $−\frac{N−1}{N}$. In this case $\max\{\|w_i\|\}\geq\frac{N-1}{N}$. If $n>1$ use inclusion $\mathbb{R}^1\hookrightarrow\mathbb{R}^n$. –  Fiktor Oct 2 '10 at 13:25
1  
@fiktor: Your example does not show what you claim it does: its best bound is something like max{$\|w_i\|$} = 1/2. However, in $\mathbb R^n$, by taking the union of all basis vectors and their negatives, one achieves a configuration whose best bound is very close to 1. –  André Henriques Oct 5 '10 at 10:09
2  
@Andre: I disagree. How do you get that best bound of 1/2? If you put two negatively pointing vectors consecutively, they give a max $\geq \frac{N-1}{N}$. By the pigeonhole principle, any arrangement of the vectors fiktor (up to a cyclic permutation which only changes the order, but not the values of $w_i$) must have two consecutive negative pointing "short vectors". –  Willie Wong Oct 5 '10 at 11:34
    
@Willie: You're right. I was talking nonsense. –  André Henriques Oct 5 '10 at 12:52
add comment

3 Answers 3

up vote 8 down vote accepted

I have a counterexample in $\mathbb R^2$. Here's how it goes.

Pick two numbers $n$ and $N$, with $N>>n>>1$.
The collection {$v_i$} consists of:

  • $N(n-1)$ times the vector $(\frac{n-2}{n},\frac{1}{N(2n-3)})$

  • $N(n-2)$ times the vector $(-\frac{n-1}{n},\frac{1}{N(2n-3)})$

  • The vector $(0,-1)$ once.

The smallest ball into which those vectors can be fit back-to-back has diameter $\sqrt{5}-\varepsilon$.

share|improve this answer
    
Andre, are you sure about the number $\sqrt{5} - \epsilon$? This would contradict the theorem Laurent Berger mentioned in his post. Perhaps you dropped a factor of 2? –  Willie Wong Oct 7 '10 at 10:11
    
(Also, do you mean the second component of the second set of vectors to be $-1/N$? the way it looks right now, they do not sum up to 0. ) –  Willie Wong Oct 7 '10 at 10:13
    
Replaced "radius" by "diameter". –  André Henriques Oct 7 '10 at 15:24
    
Replaced 1/N by 1/N(2n-3). Now they add up to zero. –  André Henriques Oct 7 '10 at 15:26
add comment

You can do it with $\|w_i\| \leq \sqrt{5}/2$ and $\sqrt{5}/2 \simeq 1.12$. Indeed, a refinement of the polygonal confinement theorem of Steinitz (see [1]) says that you can reorder your vectors in a way that the partial sums $v_1 + \cdots + v_j$ all satisfy $\| v_1 + \cdots + v_j \| \leq \sqrt{5}/2$. You can now take $w_j = v_1 + \cdots + v_j$.

[1] Banaszczyk, Wojciech.The Steinitz constant of the plane. J. Reine Angew. Math. 373 (1987), 218--220.

Here's the MathSciNet review of that paper:

The Steinitz constant of a finite-dimensional real normed linear space $E$ is the minimum constant $S(E)$ satisfying: For any set of vectors $u_1,\cdots,u_n$ such that $\|u_i\|\leq1$ and $\sum^n_{i=1}u_i=0$, there exists a permutation of $\{1,\cdots,n\}$ such that $\|\sum^k_{i=1}u_{p(i)}\|\leq S(E)$ for $k=1,\cdots,n$. In this article the author proves that $S(E)=\sqrt{5}/2$ if $E$ is the Euclidean plane and that $S(E)\leq\frac32$ for any 2-dimensional space.

share|improve this answer
    
It appears that the $\sqrt{5}/2$ bound may be very much older? zentralblatt-math.org/zmath/en/advanced/… shows a paper by V.Bergström in 1930 deriving this same result. The paper itself is available here: springerlink.com/content/27277w7815v61481 –  Willie Wong Oct 5 '10 at 15:20
    
@Willie: Thank you for the reference! –  Laurent Berger Oct 5 '10 at 15:42
    
Doesn't this qualify as an open problem then? a nice one though –  Piero D'Ancona Oct 5 '10 at 15:49
1  
@Piero: No. Fiktor's question is different. He doesn't insist that $w_0=0$. This is a crucial difference. –  André Henriques Oct 5 '10 at 18:15
    
Indeed, Steinitz' theorem tells you about the radius of a disk centered at $0$ containing the partial sums, while fiktor's question is about the radius of a disk, possibly centered away from $0$, containing the partial sums. –  Laurent Berger Oct 6 '10 at 6:58
show 2 more comments

In $\mathbb R^3$, I have a counterexample:

Pick $n$ big. The vectors $v_1,\ldots,v_{4n}$ are defined as follows:

$v_1=\ldots=v_n=(1-\frac{1}{n},\frac{1}{2n},0)$

$v_{n+1}=\ldots=v_{2n}=(-1+\frac{1}{n},\frac{1}{2n},0)$

$v_{2n+1}=(0,-1,0)$

$v_{2n+2}=\ldots=v_{3n}=(0,0,-1)$

$v_{3n+1}=\ldots=v_{4n}=(0,0,1-\frac{1}{n})$

These vectors can't be put back-to-back inside a unit ball.

share|improve this answer
    
Very nice. It seems that a similar construction will show that the constant goes to $\infty$ as the dimension gets large. –  Peter Shor Oct 8 '10 at 21:41
1  
By adapting the construction in my post about $\mathbb R^2$, I can get the following lower bound for vectors in $\mathbb R^n$. The diameter needs to be at least $\sqrt{n+3}$. That number is the diameter of the box $[0,2] \times [0,1]^{n-1}$. –  André Henriques Oct 8 '10 at 23:21
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.