Steinitz's polygonal confinement theorem: finitely many vectors of norm at most $1$ summing to $0$ can be ordered so that every partial sum has norm at most $n$

Deleting one entry from a finite sum. Let $b : \mathbb{N} \to \mathbb{R}$, let $r \ge 1$, let $q<r$, and let $b^{\wedge q}$ be the list with $b^{\wedge q}_i := b_i$ for $i<q$ and $b^{\wedge q}_i := b_{i+1}$ for $q \le i < r-1$. Then $\sum_{i<r}b_i = \sum_{i<r-1}b^{\wedge q}_i + b_q$: splitting the left side at $q$ and again at $q+1$ gives $\sum_{i<q}b_i + b_q + \sum_{l<r-1-q}b_{q+1+l}$, and splitting the right side at $q$ gives $\sum_{i<q}b_i + \sum_{l<r-1-q}b_{q+l+1}$, and the two agree.

The easy case $m \le n$. Take $\pi$ to be the identity of $m$, a bijection. For $k \le m$ the finite triangle inequality and $\lVert v_j\rVert_2 \le 1$ give $\lVert\sum_{j<k}v_j\rVert_2 \le \sum_{j<k}\lVert v_j\rVert_2 \le \sum_{j<k}1 = \iota(k) \le \iota(n)$, since $k \le m \le n$ and $\iota$ is increasing. So the theorem holds in this case, and we assume $m>n$ from here on.

Stage data. For $n \le k \le m$ call a pair $(b,\mu)$ admissible at $k$ when $b : k \to m$ is injective, $\mu : \mathbb{N} \to \mathbb{R}$ vanishes at every $j \ge k$, satisfies $0 \le \mu_j \le 1$ for $j<k$, and satisfies $\sum_{j<k}\mu_j v_{b(j)} = 0$ and $\sum_{j<k}\mu_j = \iota(k-n)$.

Stage $m$ is admissible. Take $b^{m} :=$ the identity of $m$ and $\mu^{m}_j := \iota(m-n)/\iota(m)$ for $j<m$, $\mu^m_j := 0$ for $j \ge m$; here $\iota(m) > 0$ because $m > n \ge 1$, and $0 \le \iota(m-n) \le \iota(m)$ gives $0 \le \mu^m_j \le 1$. Then $\sum_{j<m}\mu^m_j v_j = \bigl(\iota(m-n)/\iota(m)\bigr)\sum_{j<m}v_j = 0$ and $\sum_{j<m}\mu^m_j = \iota(m)\cdot\iota(m-n)/\iota(m) = \iota(m-n)$.

The estimate for $k<n$, for an arbitrary ordering. For every bijection $\rho : m \to m$ and every $k<n$, the finite triangle inequality gives $\bigl\lVert\sum_{j<k}v_{\rho(j)}\bigr\rVert_2 \le \sum_{j<k}\lVert v_{\rho(j)}\rVert_2 \le \sum_{j<k}1 = \iota(k) \le \iota(n)$.

The reindexing identity. For every $k \in \mathbb{N}$, every $r \in \mathbb{N}$, every injective $f : r \to k$ and every $c : \mathbb{N} \to \mathbb{R}$ vanishing at every $j<k$ outside the image of $f$, one has $\sum_{j<k}c_j = \sum_{i<r}c_{f(i)}$. This is proved by induction on $k$, with $r$, $f$ and $c$ universally quantified. At $k=0$ the only injective $f : r \to 0$ has $r = 0$ and both sums are empty. At $k+1$, write $\sum_{j<k+1}c_j = \sum_{j<k}c_j + c_k$: if $k$ is not in the image of $f$ then $c_k = 0$ and $f$ maps into $k$, so the inductive hypothesis applies directly; and if $k = f(q)$ for the unique such $q<r$, then $r \ge 1$ and the list $g := f^{\wedge q}$ of step 1.1 is an injective map $r-1 \to k$ off whose image $c$ vanishes on $\{j : j<k\}$, so the inductive hypothesis gives $\sum_{j<k}c_j = \sum_{i<r-1}c_{g(i)}$, while step 1.1 applied to $b_i := c_{f(i)}$ gives $\sum_{i<r}c_{f(i)} = \sum_{i<r-1}c_{g(i)} + c_{f(q)}$; adding $c_k = c_{f(q)}$ to the first identity yields the claim.

The feasible set at $k-1$ is nonempty. Let $(b,\mu)$ be admissible at $k$ with $n<k\le m$, and let $\Lambda$ be the set of all $\mu' : \mathbb{N} \to \mathbb{R}$ vanishing at every $j\ge k$, with $0 \le \mu'_j \le 1$ for $j<k$, $\sum_{j<k}\mu'_j v_{b(j)} = 0$ and $\sum_{j<k}\mu'_j = \iota(k-1-n)$. The scalar $\rho := \iota(k-1-n)/\iota(k-n)$ is defined and lies in $[0,1]$, since $\iota(k-n)>0$ and $0 \le \iota(k-1-n) \le \iota(k-n)$; and $\rho\mu$ lies in $\Lambda$.

Both identities hold verbatim for lists with values in $\mathbb{R}^{n}$, since a vector identity is the conjunction of its $n$ coordinate identities and the coordinates of a vector finite sum are the real finite sums of the coordinates.

The minimal number of fractional coordinates. Call $\mu' \in \Lambda$ $r$-simple when there is an injective $f : r \to k$ with $\mu'_j \in \{0,1\}$ for every $j<k$ outside the image of $f$. The set $R := \{\, r \in \mathbb{N} : \text{some } \mu' \in \Lambda \text{ is } r\text{-simple} \,\}$ contains $k$, taking $f$ to be the identity of $k$, so $R$ is a nonempty set of naturals and has a least element $r_0$; fix $\mu \in \Lambda$ and an injective $f : r_0 \to k$ witnessing it.

Two consequences used repeatedly. Taking $k = r$ and $f$ a bijection of $k$ in step 2.1 gives $\sum_{j<k}c_{f(j)} = \sum_{j<k}c_j$ for every $c$; and taking $c$ to vanish off the image of an injective $f : r \to k$ gives $\sum_{j<k}c_j = \sum_{i<r}c_{f(i)}$, both in $\mathbb{R}$ and in $\mathbb{R}^{n}$.

Every marked coordinate is strictly fractional. For every $i<r_0$ one has $0 < \mu_{f(i)} < 1$: otherwise $\mu_{f(i)} \in \{0,1\}$, and then $f^{\wedge i}$, an injective map $r_0-1 \to k$ off whose image $\mu$ takes values in $\{0,1\}$, would witness that $\mu$ is $(r_0-1)$-simple, contradicting minimality of $r_0$.

Suppose $r_0 \ge n+2$, towards a contradiction. Define $w : r_0 \to \mathbb{R}^{n+1}$ by $w_i(t) := \bigl(v_{b(f(i))}\bigr)(t)$ for $t<n$ and $w_i(n) := 1$.

The list $w$ is linearly dependent: there is $\lambda : r_0 \to \mathbb{R}$, not identically $0$, with $\sum_{i<r_0}\lambda_i w_i = 0$. If $w$ is not injective, say $w_{i_1} = w_{i_2}$ with $i_1 \ne i_2$, take $\lambda_{i_1} := 1$, $\lambda_{i_2} := -1$ and $\lambda_i := 0$ otherwise; the list $i \mapsto \lambda_i w_i$ then vanishes off $\{i_1,i_2\}$ and sums to $w_{i_1} - w_{i_2} = 0$ by step 4.1. If $w$ is injective, its image is a subset of $\mathbb{R}^{n+1}$ equinumerous with $r_0 \ge n+2$, hence not linearly independent by [L6]; so some injective list $h : p \to \operatorname{im}(w)$ is linearly dependent, giving $\nu : p \to \mathbb{R}$ not identically $0$ with $\sum_{l<p}\nu_l h(l) = 0$, and setting $\lambda_{i} := \nu_l$ when $w_i = h(l)$ and $\lambda_i := 0$ otherwise turns that into $\sum_{i<r_0}\lambda_i w_i = 0$ by step 4.1, the list $i \mapsto \lambda_i w_i$ vanishing off the image of the injective map $l \mapsto$ the unique $i$ with $w_i = h(l)$.

The step length. Let $i_0$ be the least $i<r_0$ with $\lambda_i \ne 0$, which exists because $\lambda$ is not identically $0$. Define $s : r_0 \to \mathbb{R}$ by $s_i := (1-\mu_{f(i)})/\lambda_i$ if $\lambda_i>0$, by $s_i := \mu_{f(i)}/(-\lambda_i)$ if $\lambda_i<0$, and by $s_i := s_{i_0}$ if $\lambda_i = 0$; every $s_i$ is a positive real by step 4.2. Put $t^{*} := \min\{s_0,\dots,s_{r_0-1}\}$, a minimum over a nonempty finite set of reals, so $t^{*}>0$ and $t^{*} = s_{i}$ for some $i<r_0$; choosing that $i$ if $\lambda_i \ne 0$ and $i_0$ otherwise, there is $i^{*}<r_0$ with $\lambda_{i^{*}} \ne 0$ and $t^{*} = s_{i^{*}}$.

Reading the coordinates of step 5.1. The coordinate $n$ gives $\sum_{i<r_0}\lambda_i = 0$, and the coordinates $t<n$ give $\sum_{i<r_0}\lambda_i v_{b(f(i))} = 0$ in $\mathbb{R}^{n}$.

The moved point. Define $\mu' : \mathbb{N} \to \mathbb{R}$ by $\mu'_j := \mu_j + t^{*}\lambda_i$ if $j = f(i)$ for the unique $i<r_0$ with that property, and $\mu'_j := \mu_j$ otherwise. Then $0 \le \mu'_j \le 1$ for every $j<k$: outside the image of $f$ nothing changes; at $j = f(i)$ with $\lambda_i>0$ one has $\mu_{f(i)} < \mu'_j \le \mu_{f(i)} + s_i\lambda_i = 1$; with $\lambda_i<0$ one has $0 = \mu_{f(i)} + s_i\lambda_i \le \mu'_j < \mu_{f(i)}$; and with $\lambda_i = 0$ the value is unchanged.

The moved point is feasible. The list $j \mapsto \mu'_j - \mu_j$ vanishes at every $j<k$ off the image of $f$ and takes the value $t^{*}\lambda_i$ at $f(i)$, so step 4.1 gives $\sum_{j<k}(\mu'_j-\mu_j) = \sum_{i<r_0}t^{*}\lambda_i = t^{*}\cdot 0 = 0$; likewise the $\mathbb{R}^{n}$-valued list $j \mapsto (\mu'_j-\mu_j)v_{b(j)}$ vanishes off that image and takes the value $t^{*}\lambda_i v_{b(f(i))}$ at $f(i)$, so $\sum_{j<k}(\mu'_j-\mu_j)v_{b(j)} = t^{*}\sum_{i<r_0}\lambda_i v_{b(f(i))} = 0$. Hence $\sum_{j<k}\mu'_j = \iota(k-1-n)$ and $\sum_{j<k}\mu'_j v_{b(j)} = 0$, so $\mu' \in \Lambda$.

The contradiction. By step 5.2, $\mu'_{f(i^{*})} = \mu_{f(i^{*})} + t^{*}\lambda_{i^{*}} \in \{0,1\}$. So $f^{\wedge i^{*}}$, an injective map $r_0-1 \to k$, witnesses that $\mu'$ is $(r_0-1)$-simple: off the image of $f$ the value $\mu'_j = \mu_j$ lies in $\{0,1\}$, and at $f(i^{*})$ it lies in $\{0,1\}$ as just shown. This contradicts the minimality of $r_0$, so the supposition of step 4.3 is untenable and $r_0 \le n+1$.

The support bound. There is $j_0<k$ with $\mu_{j_0} = 0$. Suppose instead that $\mu_j>0$ for every $j<k$; then off the image of $f$ the value $\mu_j$ lies in $\{0,1\}$ and is positive, hence equals $1$. Put $\nu_j := 1-\mu_j$ for $j<k$ and $\nu_j := 0$ for $j \ge k$, so $\nu$ vanishes at every $j<k$ off the image of $f$ and satisfies $0<\nu_{f(i)}<1$ for $i<r_0$ by step 4.2, while $\sum_{j<k}\nu_j = \iota(k)-\iota(k-1-n) = \iota(n+1)$ by [L7].

By step 4.1, $\sum_{j<k}\nu_j = \sum_{i<r_0}\nu_{f(i)}$. If $r_0 = 0$ this is the empty sum $0$, contradicting $\iota(n+1)>0$. If $r_0 \ge 1$ then every term of $\sum_{i<r_0}(1-\nu_{f(i)})$ is positive, so that sum is at least its term at index $0$ and hence positive, whence $\sum_{i<r_0}\nu_{f(i)} = \iota(r_0) - \sum_{i<r_0}(1-\nu_{f(i)}) < \iota(r_0) \le \iota(n+1)$ using step 8.1. Either way $\iota(n+1) < \iota(n+1)$ or $\iota(n+1) = 0$, both impossible; so some $\mu_{j_0}$ is $0$.

Descending one stage. With $j_0$ as in step 9.1, put $b' := b^{\wedge j_0} : k-1 \to m$ and $\mu'' := \mu^{\wedge j_0}$, extended by $0$ beyond $k-1$. Then $b'$ is injective with image $\operatorname{im}(b)\setminus\{b(j_0)\}$, $0 \le \mu''_j \le 1$ for $j<k-1$, and by step 1.1 in both its real and its vector form, $\sum_{j<k-1}\mu''_j = \sum_{j<k}\mu_j - \mu_{j_0} = \iota(k-1-n)$ and $\sum_{j<k-1}\mu''_j v_{b'(j)} = \sum_{j<k}\mu_j v_{b(j)} - \mu_{j_0}v_{b(j_0)} = 0$. So $(b',\mu'')$ is admissible at $k-1$.

Iterating. Starting from the admissible pair of step 1.4 at $k = m$ and applying step 11.1 once for each $k$ from $m$ down to $n+1$, one obtains admissible pairs $(b^{k},\mu^{k})$ for every $k$ with $n \le k \le m$, with $\operatorname{im}(b^{k-1}) \subseteq \operatorname{im}(b^{k})$ and $\operatorname{im}(b^{k})\setminus\operatorname{im}(b^{k-1})$ a single element. This is a recursion of length $m-n$, each stage determined by the previous one together with finitely many determinations (a least natural, a minimum of a finite set of reals), so no choice principle is involved.

The ordering. Define $\pi : m \to m$ by $\pi(j) := b^{n}(j)$ for $j<n$ and, for each $k$ with $n<k\le m$, $\pi(k-1) :=$ the unique element of $\operatorname{im}(b^{k})\setminus\operatorname{im}(b^{k-1})$. The images $\operatorname{im}(b^{k})$ increase from $\operatorname{im}(b^{n})$, of size $n$, to $\operatorname{im}(b^{m}) = m$, gaining exactly one element at each stage, so $\pi$ is injective with image $m$, that is a bijection, and for every $k$ with $n \le k \le m$ the set $\{\pi(j) : j<k\}$ is exactly $\operatorname{im}(b^{k})$.

Both enumerations give the same partial sum. Fix $k$ with $n \le k \le m$ and let $c : \mathbb{N} \to \mathbb{R}^{n}$ be $c_i := v_i$ for $i \in \operatorname{im}(b^{k})$ and $c_i := 0$ otherwise. Then $c$ vanishes at every $i<m$ off the image of the injective list $j \mapsto \pi(j)$ on $k$, and also off the image of $b^{k}$, so step 4.1 applied twice gives $\sum_{j<k}v_{\pi(j)} = \sum_{i<m}c_i = \sum_{j<k}v_{b^{k}(j)}$.

The estimate for $n \le k \le m$. Since $\sum_{j<k}\mu^{k}_j v_{b^{k}(j)} = 0$, additivity gives $\sum_{j<k}v_{b^{k}(j)} = \sum_{j<k}\bigl(1-\mu^{k}_j\bigr)v_{b^{k}(j)}$; each coefficient $1-\mu^{k}_j$ is nonnegative, so the finite triangle inequality and $\lVert v_i\rVert_2 \le 1$ give $\bigl\lVert\sum_{j<k}v_{b^{k}(j)}\bigr\rVert_2 \le \sum_{j<k}\bigl(1-\mu^{k}_j\bigr)\lVert v_{b^{k}(j)}\rVert_2 \le \sum_{j<k}\bigl(1-\mu^{k}_j\bigr) = \iota(k)-\iota(k-n) = \iota(n)$.

By steps 14.1 and 15.1 the bound $\lVert\sum_{j<k}v_{\pi(j)}\rVert_2 \le \iota(n)$ holds for $n \le k \le m$, and by step 1.5 it holds for $k<n$; together with the case $m \le n$ of step 1.2, the required bijection $\pi$ has been exhibited in every case.