MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.

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.

-
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 2010 at 3:40
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 2010 at 13:25
@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 2010 at 10:09
@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 2010 at 11:34
@Willie: You're right. I was talking nonsense. – André Henriques Oct 5 2010 at 12:52

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

-
 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 2010 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 2010 at 10:13 Replaced "radius" by "diameter". – André Henriques Oct 7 2010 at 15:24 Replaced 1/N by 1/N(2n-3). Now they add up to zero. – André Henriques Oct 7 2010 at 15:26

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.

-
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 2010 at 15:20
@Willie: Thank you for the reference! – Laurent Berger Oct 5 2010 at 15:42
Doesn't this qualify as an open problem then? a nice one though – Piero D'Ancona Oct 5 2010 at 15:49
@Piero: No. Fiktor's question is different. He doesn't insist that $w_0=0$. This is a crucial difference. – André Henriques Oct 5 2010 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 2010 at 6:58

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.

-
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 2010 at 21:41
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 2010 at 23:21