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_i^{\wedge q}:=b_i$ for $i<q$ and $b_i^{\wedge q}:=b_{i+1}$ for $q\le i<r-1$. Then ${\sum }_{i<r}{b}_i={\sum }_{i<r-1}{b}_i^{\wedge q}+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 $\parallel v_j{\parallel }_2\le 1$ give $\parallel {\sum }_{j<k}{v}_j{\parallel }_2\le {\sum }_{j<k}\parallel v_j{\parallel }_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 }_j^m:=\iota (m-n)\mathrm{/}\iota (m)$ for $j<m$, ${\mu }_j^m:=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 }_j^m\le 1$. Then ${\sum }_{j<m}{\mu }_j^m{v}_j=(\iota (m-n)\mathrm{/}\iota (m)){\sum }_{j<m}{v}_j=0$ and ${\sum }_{j<m}{\mu }_j^m=\iota (m)\cdot \iota (m-n)\mathrm{/}\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 $\parallel {\sum }_{j<k}{v}_{\rho (j)}{\parallel }_2\le {\sum }_{j<k}\parallel v_{\rho (j)}{\parallel }_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 $\mathrm{\Lambda }$ be the set of all ${\mu }^{\mathrm{\prime }}:\mathbb{N}\to \mathbb{R}$ vanishing at every $j\ge k$, with $0\le {\mu }_j^{\mathrm{\prime }}\le 1$ for $j<k$, ${\sum }_{j<k}{\mu }_j^{\mathrm{\prime }}{v}_{b(j)}=0$ and ${\sum }_{j<k}{\mu }_j^{\mathrm{\prime }}=\iota (k-1-n)$. The scalar $\rho :=\iota (k-1-n)\mathrm{/}\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 $\mathrm{\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 }^{\mathrm{\prime }}\in \mathrm{\Lambda }$ $r$-simple when there is an injective $f:r\to k$ with ${\mu }_j^{\mathrm{\prime }}\in \{0,1\}$ for every $j<k$ outside the image of $f$. The set $R:=\{r\in \mathbb{N}:\text{some }{\mu }^{\mathrm{\prime }}\in \mathrm{\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 \mathrm{\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):=\left(v_{b(f(i))}\right)(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\mathrm{\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 \mathrm{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\mathrm{\ne }0$, which exists because $\lambda$ is not identically $0$. Define $s:r_0\to \mathbb{R}$ by $s_i:=(1-{\mu }_{f(i)})\mathrm{/}{\lambda }_i$ if ${\lambda }_i>0$, by $s_i:={\mu }_{f(i)}\mathrm{/}(-{\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^{\ast }:=\min \{s_0,\dots ,s_{r_0-1}\}$, a minimum over a nonempty finite set of reals, so $t^{\ast }>0$ and $t^{\ast }=s_i$ for some $i<r_0$; choosing that $i$ if ${\lambda }_i\mathrm{\ne }0$ and $i_0$ otherwise, there is $i^{\ast }<r_0$ with ${\lambda }_{i^{\ast }}\mathrm{\ne }0$ and $t^{\ast }=s_{i^{\ast }}$.

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 }^{\mathrm{\prime }}:\mathbb{N}\to \mathbb{R}$ by ${\mu }_j^{\mathrm{\prime }}:={\mu }_j+t^{\ast }{\lambda }_i$ if $j=f(i)$ for the unique $i<r_0$ with that property, and ${\mu }_j^{\mathrm{\prime }}:={\mu }_j$ otherwise. Then $0\le {\mu }_j^{\mathrm{\prime }}\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^{\mathrm{\prime }}\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^{\mathrm{\prime }}<{\mu }_{f(i)}$; and with ${\lambda }_i=0$ the value is unchanged.

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

The contradiction. By step 5.2, ${\mu }_{f(i^{\ast })}^{\mathrm{\prime }}={\mu }_{f(i^{\ast })}+t^{\ast }{\lambda }_{i^{\ast }}\in \{0,1\}$. So $f^{\wedge i^{\ast }}$, an injective map $r_0-1\to k$, witnesses that ${\mu }^{\mathrm{\prime }}$ is $(r_0-1)$-simple: off the image of $f$ the value ${\mu }_j^{\mathrm{\prime }}={\mu }_j$ lies in $\{0,1\}$, and at $f(i^{\ast })$ 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^{\mathrm{\prime }}:=b^{\wedge j_0}:k-1\to m$ and ${\mu }^{\mathrm{\prime }\mathrm{\prime }}:={\mu }^{\wedge j_0}$, extended by $0$ beyond $k-1$. Then $b^{\mathrm{\prime }}$ is injective with image $\mathrm{im}(b)\setminus \{b(j_0)\}$, $0\le {\mu }_j^{\mathrm{\prime }\mathrm{\prime }}\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^{\mathrm{\prime }\mathrm{\prime }}={\sum }_{j<k}{\mu }_j-{\mu }_{j_0}=\iota (k-1-n)$ and ${\sum }_{j<k-1}{\mu }_j^{\mathrm{\prime }\mathrm{\prime }}{v}_{b^{\mathrm{\prime }}(j)}={\sum }_{j<k}{\mu }_j{v}_{b(j)}-{\mu }_{j_0}{v}_{b(j_0)}=0$. So $(b^{\mathrm{\prime }},{\mu }^{\mathrm{\prime }\mathrm{\prime }})$ 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 $\mathrm{im}(b^{k-1})\subseteq \mathrm{im}(b^k)$ and $\mathrm{im}(b^k)\setminus \mathrm{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 $\mathrm{im}(b^k)\setminus \mathrm{im}(b^{k-1})$. The images $\mathrm{im}(b^k)$ increase from $\mathrm{im}(b^n)$, of size $n$, to $\mathrm{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 $\mathrm{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 \mathrm{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 }_j^k{v}_{b^k(j)}=0$, additivity gives ${\sum }_{j<k}{v}_{b^k(j)}={\sum }_{j<k}(1-{\mu }_j^k)v_{b^k(j)}$; each coefficient $1-{\mu }_j^k$ is nonnegative, so the finite triangle inequality and $\parallel v_i{\parallel }_2\le 1$ give $\parallel {\sum }_{j<k}{v}_{b^k(j)}{\parallel }_2\le {\sum }_{j<k}(1-{\mu }_j^k)\parallel v_{b^k(j)}{\parallel }_2\le {\sum }_{j<k}(1-{\mu }_j^k)=\iota (k)-\iota (k-n)=\iota (n)$.

By steps 14.1 and 15.1 the bound $\parallel {\sum }_{j<k}{v}_{\pi (j)}{\parallel }_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.