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.

  • 1
    $\begingroup$ In $\mathbb{R}^2$, I see a configuration such that $\max\{\|w_i\|\} > \tfrac1{\sqrt{2}}-\epsilon$, but I do not see anything worse. $\endgroup$ Oct 2 '10 at 3:40
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Fiktor
    Oct 2 '10 at 13:25
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 5 '10 at 10:09
  • 2
    $\begingroup$ @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". $\endgroup$ Oct 5 '10 at 11:34
  • $\begingroup$ @Willie: You're right. I was talking nonsense. $\endgroup$ Oct 5 '10 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$.

  • $\begingroup$ 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? $\endgroup$ Oct 7 '10 at 10:11
  • $\begingroup$ (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. ) $\endgroup$ Oct 7 '10 at 10:13
  • $\begingroup$ Replaced "radius" by "diameter". $\endgroup$ Oct 7 '10 at 15:24
  • $\begingroup$ Replaced 1/N by 1/N(2n-3). Now they add up to zero. $\endgroup$ Oct 7 '10 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.

  • $\begingroup$ 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 $\endgroup$ Oct 5 '10 at 15:20
  • $\begingroup$ @Willie: Thank you for the reference! $\endgroup$ Oct 5 '10 at 15:42
  • $\begingroup$ Doesn't this qualify as an open problem then? a nice one though $\endgroup$ Oct 5 '10 at 15:49
  • 1
    $\begingroup$ @Piero: No. Fiktor's question is different. He doesn't insist that $w_0=0$. This is a crucial difference. $\endgroup$ Oct 5 '10 at 18:15
  • $\begingroup$ 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. $\endgroup$ Oct 6 '10 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:






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

  • $\begingroup$ Very nice. It seems that a similar construction will show that the constant goes to $\infty$ as the dimension gets large. $\endgroup$
    – Peter Shor
    Oct 8 '10 at 21:41
  • 1
    $\begingroup$ 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}$. $\endgroup$ Oct 8 '10 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.