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.

Improve this question
$\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$
    – Anton Petrunin
    Commented 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
    Commented 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$
    – André Henriques
    Commented 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$
    – Willie Wong
    Commented Oct 5, 2010 at 11:34
  • $\begingroup$ @Willie: You're right. I was talking nonsense. $\endgroup$
    – André Henriques
    Commented Oct 5, 2010 at 12:52

3 Answers 3

Reset to default
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$.

Improve this answer
$\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$
    – Willie Wong
    Commented 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$
    – Willie Wong
    Commented Oct 7, 2010 at 10:13
  • $\begingroup$ Replaced "radius" by "diameter". $\endgroup$
    – André Henriques
    Commented Oct 7, 2010 at 15:24
  • $\begingroup$ Replaced 1/N by 1/N(2n-3). Now they add up to zero. $\endgroup$
    – André Henriques
    Commented 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.

Improve this answer
$\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$
    – Willie Wong
    Commented Oct 5, 2010 at 15:20
  • $\begingroup$ @Willie: Thank you for the reference! $\endgroup$
    – Laurent Berger
    Commented Oct 5, 2010 at 15:42
  • $\begingroup$ Doesn't this qualify as an open problem then? a nice one though $\endgroup$
    – Piero D'Ancona
    Commented 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$
    – André Henriques
    Commented 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$
    – Laurent Berger
    Commented 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.

Improve this answer
$\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
    Commented 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$
    – André Henriques
    Commented Oct 8, 2010 at 23:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .