15
$\begingroup$

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.

$\endgroup$
5
  • 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, 2010 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, 2010 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, 2010 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, 2010 at 11:34
  • $\begingroup$ @Willie: You're right. I was talking nonsense. $\endgroup$ Oct 5, 2010 at 12:52

3 Answers 3

8
$\begingroup$

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

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

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.

$\endgroup$
7
  • $\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, 2010 at 15:20
  • $\begingroup$ @Willie: Thank you for the reference! $\endgroup$ Oct 5, 2010 at 15:42
  • $\begingroup$ Doesn't this qualify as an open problem then? a nice one though $\endgroup$ Oct 5, 2010 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, 2010 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, 2010 at 6:58
4
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2010 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, 2010 at 23: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.