OctoInformBeta

The Euclidean Steinitz–Bergström bound

Let v1,…,vNv_1,\dots,v_N be vectors in the Euclidean unit ball of ℝd\mathbb R^d. The signing problem asks for one choice of signs ε1,…,εN∈{−1,1}\varepsilon_1,\dots,\varepsilon_N\in\{-1,1\} for which every signed prefix sum ∑i=1kεivi\sum_{i=1}^k\varepsilon_iv_i, 1≤k≤N1\le k\le N, has norm at most a bound depending only on dd. When ∑i=1Nvi=0\sum_{i=1}^Nv_i=0, the ordering problem keeps the vectors unsigned and asks instead for an order in which every prefix sum is small. For such a zero-sum family, define β(v1,…,vN)=min⁡π∈𝔖Nmax⁡1≤k≤N∥∑i=1kvπ(i)∥2\beta(v_1,\dots,v_N)=\min_{\pi\in\mathfrak S_N}\max_{1\le k\le N}\bigl\|\sum_{i=1}^kv_{\pi(i)}\bigr\|_2, where 𝔖N\mathfrak S_N is the set of permutations of {1,…,N}\{1,\dots,N\}. The Euclidean Steinitz constant S2(d)S_2(d) is the supremum of β\beta over all finite zero-sum families in the unit ball of ℝd\mathbb R^d. The Euclidean Steinitz-Bergström conjecture asks whether S2(d)=O(d)S_2(d)=O(\sqrt d).

The ordering problem goes back to Steinitz’s work on conditionally convergent vector series. Ambrus and Heck give a historical account of it. Grinberg and Sevast’yanov proved that, for an arbitrary norm on ℝd\mathbb R^d, every finite zero-sum family in the unit ball has an order whose partial sums stay within dd times the unit ball. Behrend discussed the expected growth on the smaller scale d\sqrt d in Euclidean space. The modern formulation of the conjecture and its attribution to Bergström are recorded by Ambrus and Heck. For the signing problem, the question of a bound O(d)O(\sqrt d) was stated explicitly by Bansal, Jiang, Meka, Singla and Sinha, following Banaszczyk. Their discussion records the bound O(d+log⁡N)O(\sqrt d+\sqrt{\log N}) of Banaszczyk, which grows with NN. Dutta, Jha and Jiang state an efficient signing bound O(d+d1/4log⁡7/4N)O(\sqrt d+d^{1/4}\log^{7/4}N). Chobanyan’s transference principle relates rearrangements to signed sums.

The preprint proves that there is an absolute constant CC such that, for all d,N≥1d,N\ge1, every sequence v1,…,vNv_1,\dots,v_N in the unit ball of ℝd\mathbb R^d has signs ε1,…,εN∈{−1,1}\varepsilon_1,\dots,\varepsilon_N\in\{-1,1\} with ∥∑i=1kεivi∥2≤Cd\bigl\|\sum_{i=1}^k\varepsilon_iv_i\bigr\|_2\le C\sqrt d for every 1≤k≤N1\le k\le N (Theorem 1.1). With the same constant, every zero-sum family v1,…,vNv_1,\dots,v_N in the unit ball of ℝd\mathbb R^d has a permutation π∈𝔖N\pi\in\mathfrak S_N with ∥∑i=1kvπ(i)∥2≤Cd\bigl\|\sum_{i=1}^kv_{\pi(i)}\bigr\|_2\le C\sqrt d for every 1≤k≤N1\le k\le N (Theorem 1.2). Theorem 1.2 resolves the Euclidean Steinitz-Bergström conjecture. The preprint also exhibits, in a dd-dimensional Euclidean space, d+1d+1 unit vectors with pairwise inner products −1/d-1/d that sum to zero and have, in every order, a prefix sum of norm at least 12d\frac12\sqrt d. The Lean library does not contain this example.

The Lean library Steinitz proves Theorem 1.1 and Theorem 1.2 as the preprint states them, without hypotheses. Lean has checked every result of the Lean library, so the Lean library is the reference. Each result on these pages is stated as the Lean library states it and linked to the Lean declaration behind it, with the preprint’s statement beside it where the two differ. The preprint is a guide only, which gives the results their order and their names. The Lean library proves the Gaussian correlation inequality of Royen for closed centrally symmetric convex sets under a centered Gaussian measure on a finite-dimensional space.

The Lean library: Steinitz

Steinitz is a Lean library: 26 items, in five groups. Each has a page written by OctoInform, listed below.

§1. Introduction 4 items
  1. §1 (setting): signed prefixes and orderings Signed and reordered prefix sums in the Euclidean unit ball. §1
  2. Theorem 1.1 [Prescribed-order signed prefixes] Signing unit-ball vectors in order with prefix sums O(d)O(\sqrt{d}). §1
  3. Theorem 1.2 [Euclidean Steinitz-Bergström bound] Signed prefix bounds give ordering bounds with the same constant. §1
  4. §1.1 (proof of Theorem 1.2): positive-forward, negative-reverse order Reordering a zero-sum sequence by sign averages its prefix bounds. §1.1
§2. Constructing the signed walk 9 items
  1. §2.1 (setting): diagonal Dirichlet energy, eq. (dirichlet-energy), and the bound (all-diagonal-energy) Convex bodies that diagonal heat flow drains slowly. §2.1
  2. Proposition 2.1 [Signs with adaptive shifts] Signs bring walks with small adaptive shifts into good domains. §2
  3. Proposition 2.2 [Energy of a filtered path body] Dilated filtered path bodies satisfy the diagonal heat bound. §2
  4. Lemma 2.3 [Adding slabs] Slabs cost the Gaussian autoregressive chain little survival. §2
  5. §2.2 (setting): symmetric contractions (symmetric-filter) and predictor rows (predictor-rows) Symmetric filter steps and their predictor rows. §2.2
  6. §2.2 (displayed): predictor columns (predictor-columns) Symmetric steps keep fresh predictor columns within the mass bound. §2.2
  7. §2.2 (displayed): absolute parameters and the application body (application-body) to (absolute-parameters) The body scale that makes the application body good. §2.2
  8. §2.2 (displayed): unclipped coordinates (unclipped-coordinates) and cancellation (feedback-cancellation) Feedback signs in good bodies and prefix cancellation. §2.2
  9. Lemma 2.5 [Gaussian correlation for path constraints] Gaussian correlation for symmetric convex sets in finite dimensions. §2
§3. From low energy to shifted signs 3 items
  1. Lemma 3.1 [One function for all coordinate energies] Diagonal heat bounds give one function for all coordinate energies. §3
  2. Lemma 3.2 [Convexity under Minkowski averages] The compressed heat norm is log-concave under Minkowski averages. §3
  3. Lemma 3.3 [A section that permits shifted signed steps] Shifted sections of good bodies stay good and admit signed steps. §3
§4. Matrix variation along the filter 6 items
  1. §4.1 (setting): cutoff, potentials, scales and the energy E_θ (scalar-potentials), (energy-definition) Weights, potentials and the energy of a run of moves. §4.1
  2. §4.1 (displayed): the scale energy (scale-energy) A trace bound for dyadic energy sums of admissible runs. §4.1
  3. Lemma 4.1 [Weighted increment estimate] Small energy cost bounds the change of the cutoff matrix. §4
  4. Lemma 4.2 [Scalar comparison] The scalar remainder dominates the squared change of the cutoff. §4
  5. Lemma 4.3 [Endpoint comparison] Bounding the change of the cutoff by potential differences. §4
  6. Lemma 4.4 [Controlling the accumulated gain] Small energy bounds the accumulated gain and the potential’s rise. §4
§5. Uniform Gaussian survival 4 items
  1. §5.1 (setting): the stationary Ornstein-Uhlenbeck process The stationary Gaussian autoregressive chain and its covariance. §5.1
  2. Lemma 5.1 [Stationary survival and Dirichlet energy] Stationary survival bounds the compressed Gaussian kernel from below. §5
  3. Lemma 5.2 [One energy interval at one spectral scale] Survival bounds for a Gaussian chain seen through contractions. §5
  4. §5.3 (proof of Proposition 2.2): combining the constraints Dyadic scales and the survival of filtered Gaussian states. §5.3

No item matches.