Source-linked AI summary
An optimal constant for vector balancing with permutations
Jonathan Niles-Weed, Shay Sadovsky, Jacob Shkrob
TL;DR
The paper studies bounds for balancing vectors when signs and coordinate permutations may be chosen, a variant of a fundamental convex-geometric problem. The proof of Theorem 1 uses a tight bound for vectors in 1⊥ and decomposes each vector into its 1⊥ and 1 components. The sign-and-permutation variant has explicit bounds for vector and prefix discrepancy, with asymptotically optimal dimension dependence in the stated settings.
Problem
The paper studies bounds for balancing vectors when signs and coordinate permutations may be chosen, a variant of a fundamental convex-geometric problem.
Source: §1 · p. 1Method
The proof of Theorem 1 uses a tight bound for vectors in 1⊥ and decomposes each vector into its 1⊥ and 1 components.
Source: §1 · p. 3Results
The sign-and-permutation variant has explicit bounds for vector and prefix discrepancy, with asymptotically optimal dimension dependence in the stated settings.
Source: §1 · p. 2Takeaways & Limitations
Allowing coordinate permutations yields improved ℓp-to-ℓq bounds, including a sharp O(n^(1/q)) bound when p = ∞.
Source: §1 · p. 2Obtaining the sharp constant for p = q = ∞ remains open.
Source: §1 · p. 3
Abstract
from arXiv · showhide
We present a version of the vector balancing problem in which each vector may be given a sign and a permutation of its coordinates. We prove that this vector balancing problem and its corresponding prefix problem admit an explicit bound, and we further show that it is asymptotically optimal in the dimension. Our method of proof is purely geometric.
1 Introduction
The paper studies vector balancing when each vector can be signed and its coordinates permuted, including control of all partial sums. It gives explicit dimension-dependent bounds and shows their asymptotic optimality in the stated settings.
1 Introduction
- The sign-and-permutation variant admits an explicit bound for all partial sums, yielding a prefix-discrepancy bound with an asymptotically optimal dimension dependence.The paper also gives an explicit upper bound and determines its tight asymptotic leading constant.Source: §1 · pp. 1–2
- The signs and permutations can be chosen online, using only vectors seen so far; the Theorem 1 bound is asymptotically optimal and exactly tight in dimension 2.The construction decomposes each vector into its component parallel to the all-ones vector and its orthogonal component.Source: §1 · pp. 2–4
- The sign-and-permutation choice can be viewed as choosing one vector at each step from the set of signed coordinate permutations.This connects the theorem to colorful vector balancing.Source: §1 · p. 2
- For ℓp-to-ℓq balancing, permutations improve the prior bound by a factor of n^(1/2−1/p)+, with a sharp O(n^(1/q)) bound when p = ∞.For q = ∞ and p < ∞, the paper obtains the tight leading constant.Source: §1 · p. 2
- The sharp constant for p = q = ∞ remains an open problem.The paper also gives an example showing that the constant is at least 2.Source: §1 · p. 3
- The proof uses a tight balancing bound in the subspace orthogonal to the all-ones vector, where permutations alone can balance vectors.The construction greedily chooses permutations so partial sums remain in the regular permutahedron.Source: §1 · p. 3
2 The tight bound in 1⊥
The proof uses majorization and the geometry of a centered regular permutahedron to control partial sums. An induction chooses permutations so the sums remain inside a suitable permutahedron.
2 The tight bound in 1⊥
- Rado's theorem identifies vectors majorized by y with the convex hull of all coordinate permutations of y [18].The proof uses majorization to characterize ordered vectors in the permutahedron.Source: §2 · pp. 4–5
- They scale a permutahedron containing P1⊥Bn and use its closure property to keep partial sums inside it.The closure property combines increasing and decreasing rearrangements while remaining in P.Source: §2 · p. 4
- The centered regular permutahedron P is the convex hull of coordinate permutations of w and is closed under sums of increasing and decreasing rearrangements.Here w = (n −1, n −3, . . . , 3 −n, 1 −n).Source: §2 · p. 4
- The inductive construction chooses permutations so every partial sum remains in the permutahedron P.The proof proceeds by induction on the prefix, reusing the permutations already chosen at each step.Source: §2 · pp. 4, 7
3 Extensions for ℓp-to-ℓq permutation vector balancing
The section extends permutation vector balancing to ℓp-to-ℓq norms using greedy signs and permutations. It gives explicit bounds and reports asymptotic constants for the ℓ∞ output norm.
3 Extensions for ℓp-to-ℓq permutation vector balancing
- The proof greedily chooses signs for the 1-direction component and uses permutations to keep partial sums in a rescaled permutahedron.The permutahedron contains the projected ℓp unit ball.Source: §3 · pp. 8–10
- Theorem 9 gives an explicit version of Theorem 2 for vectors in Bn across 1 ≤ q ≤ ∞.The statement uses Rn,q and Cn,p as its quantities.Source: §3 · p. 8
- For Rn,∞Cn,p, the stated asymptotic value is 1 + on(1) when p < ∞, whereas for Rn,∞Cn,∞ it is 2 + on(1).Source: §3 · p. 8
- The method may also be applied to permutation balancing for any two origin-symmetric sets K and L.The remark describes vectors v1, . . . , vm drawn from L.Source: §3 · p. 10