pith. sign in

arxiv: 2605.23866 · v1 · pith:P5E3NL5Inew · submitted 2026-05-22 · 🧮 math.MG · cs.DM

Optimal Vector Balancing for Zonotopes

Victor Reis This is my paper

Pith reviewed 2026-05-25 02:12 UTC · model grok-4.3

classification 🧮 math.MG cs.DM
keywords zonotopesvector balancingdiscrepancySpencer's theoremsign sumsconvex geometrylinear images
0
0 comments X

The pith

There is a universal constant C such that signed sums of vectors in any zonotope stay within C sqrt(d) times the zonotope.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a balancing result for vectors inside zonotopes using signs. A zonotope in d dimensions is the image of a cube under a linear map. The theorem states that for any such zonotope and any vectors inside it, signs exist making the signed sum lie in C sqrt(d) times the zonotope, for some fixed C. This generalizes the case when the zonotope is the unit cube, recovering Spencer's theorem, and answers an open question posed in 2002. The result matters because it shows that the good balancing properties of the cube persist under linear transformations with a dimension-dependent factor.

Core claim

A zonotope is a linear image of the cube [-1,1]^m for some m. We show that there is a universal constant C such that, for every zonotope Z subset R^d and vectors v1 to vn in Z, there are signs x1 to xn in {-1,1} with sum xi vi in C sqrt(d) Z. This resolves a 2002 question of Schechtman and generalizes Spencer's six standard deviations theorem, which corresponds to the case Z = [-1,1]^d.

What carries the argument

The definition of a zonotope as the linear image of the cube, which transfers the balancing property from the cube to its images.

If this is right

  • The bound holds uniformly for all zonotopes in dimension d.
  • It recovers the classical Spencer theorem for the cube zonotope.
  • It provides an affirmative answer to Schechtman's 2002 question on vector balancing in zonotopes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This suggests that similar sign balancing might apply to other classes of convex bodies with appropriate factors.
  • Algorithmic methods for finding such signs in the cube case might extend to zonotopes via the linear map.
  • The sqrt(d) factor may be improvable or optimal in some cases.

Load-bearing premise

That balancing properties of the cube can be transferred to its linear images without losing the universal constant C.

What would settle it

A counterexample consisting of a specific zonotope in some dimension d, together with vectors in it, for which every signing produces a sum outside every multiple of sqrt(d) times the zonotope, would disprove the existence of such C.

read the original abstract

A zonotope is a linear image of the cube $[-1,1]^m$ for some $m \in \mathbb{N}$. We show that there is a universal constant $C$ such that, for every zonotope $Z\subset \mathbb{R}^d$ and vectors $v_1,\dots,v_n\in Z$, there are signs $x_1,\dots,x_n\in\{-1,1\}$ with \[ \sum_{i=1}^n x_i v_i \in C\sqrt d\, Z. \] This resolves a 2002 question of Schechtman and generalizes Spencer's six standard deviations theorem, which corresponds to the case $Z=[-1,1]^d$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript establishes the existence of a universal constant C such that, for every zonotope Z ⊂ R^d and any vectors v_1, …, v_n ∈ Z, there exist signs x_1, …, x_n ∈ {-1,1} satisfying ∑ x_i v_i ∈ C √d · Z. The result is presented as resolving Schechtman’s 2002 question and as a generalization of Spencer’s theorem (recovered when Z = [-1,1]^d).

Significance. If the central claim holds, the result supplies a dimension-only balancing guarantee for zonotopes that is independent of the number of generators. This would constitute a genuine strengthening of the direct cube-to-zonotope transfer and would be of interest to discrepancy theory and convex geometry.

major comments (2)
  1. [Abstract] Abstract, displayed equation: the claimed bound is C √d · Z with C independent of m. The standard reduction Z = A([-1,1]^m) together with Spencer’s theorem on the cube yields membership in O(√m) · Z; when m ≫ d the factor √m cannot be absorbed into any fixed multiple of √d. The manuscript must therefore contain an additional argument that replaces the ambient cube dimension m by the image dimension d; no such step is visible in the abstract and the central claim is load-bearing on its existence.
  2. [Definition opening the abstract] Definition opening the abstract: every zonotope is declared to be the linear image of some cube [-1,1]^m. The transfer of balancing properties from the cube case is invoked to obtain the stated result, yet the reduction as written produces a bound depending on m rather than d. This step is therefore load-bearing for the universal-constant claim and requires an explicit justification that the effective dimension can be taken to be d.
minor comments (1)
  1. The abstract supplies no proof outline, lemmas, or reference to the key reduction step; a one-sentence indication of the argument that achieves independence from m would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the central technical point regarding dimension reduction. The manuscript develops a new argument that achieves the claimed bound in terms of d rather than m; we address the comments below and will revise the abstract and introduction for clarity.

read point-by-point responses

  1. Referee: [Abstract] Abstract, displayed equation: the claimed bound is C √d · Z with C independent of m. The standard reduction Z = A([-1,1]^m) together with Spencer’s theorem on the cube yields membership in O(√m) · Z; when m ≫ d the factor √m cannot be absorbed into any fixed multiple of √d. The manuscript must therefore contain an additional argument that replaces the ambient cube dimension m by the image dimension d; no such step is visible in the abstract and the central claim is load-bearing on its existence.

    Authors: The abstract summarizes the result without detailing the proof. The full manuscript (Theorem 1.1 and Sections 3–4) contains an argument that directly controls the discrepancy using the rank-d structure of the zonotope, without passing through an m-dimensional Spencer bound. The proof employs an iterative signing procedure whose potential depends only on the ambient dimension d. We will add a sentence to the abstract indicating that the argument replaces m by d via the intrinsic dimension of Z. revision: yes

  2. Referee: [Definition opening the abstract] Definition opening the abstract: every zonotope is declared to be the linear image of some cube [-1,1]^m. The transfer of balancing properties from the cube case is invoked to obtain the stated result, yet the reduction as written produces a bound depending on m rather than d. This step is therefore load-bearing for the universal-constant claim and requires an explicit justification that the effective dimension can be taken to be d.

    Authors: The definition is the standard one, but the manuscript does not invoke a direct transfer from the cube that would retain the m-dependence. Instead, the proof exploits that any generating matrix A has rank at most d and constructs signs whose partial sums remain controlled in the image space, yielding the √d factor. We will insert a brief clarifying paragraph in the introduction (and a parenthetical remark in the abstract) that makes this dimension reduction explicit. revision: yes

Circularity Check

0 steps flagged

No circularity; pure existence proof generalizing known theorem

full rationale

The manuscript states an existence theorem for a universal constant C in a vector balancing result for zonotopes, explicitly generalizing Spencer's theorem (the cube case). No equations define a quantity in terms of itself, no parameters are fitted to data and then relabeled as predictions, and no load-bearing steps reduce to self-citations or ansatzes imported from prior author work. The derivation relies on the structural fact that zonotopes are linear images of cubes, which is definitional and external to the claimed bound. The result is self-contained as a mathematical existence statement without reduction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The theorem rests on the standard definition of zonotopes as linear images of cubes and on the background theory of vector balancing for the cube; no new free parameters or postulated entities are introduced in the abstract.

axioms (1)
  • domain assumption A zonotope is a linear image of the cube [-1,1]^m for some m
    This definition is used to state the theorem and to connect it to the cube case.

pith-pipeline@v0.9.0 · 5637 in / 1284 out tokens · 29299 ms · 2026-05-25T02:12:35.210299+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 1 internal anchor

  1. [1]

    K. M. Ball. Volume ratios and a reverse isoperimetric inequality. J. London Math. Soc. (2), 44(2):351--359, 1991

    work page 1991

  2. [2]

    Bourgain and V

    J. Bourgain and V. D. Milman. New volume ratio properties for convex symmetric bodies in R^n . Invent. Math., 88(2):319--340, 1987

    work page 1987

  3. [3]

    Nearly-Tight Bounds for Zonotope Containment and Beyond

    F. Eisenbrand, T. Rothvoss, M. Russo, and R. Skorupinski. Nearly-tight bounds for zonotope containment and beyond. arXiv:2605.04183, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  4. [4]

    L. Heck, V. Reis, and T. Rothvoss. The vector balancing constant for zonotopes. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1292--1300. IEEE, 2023. arXiv:2210.16460

    work page arXiv 2023

  5. [5]

    V. Reis. Vector Balancing and Integer Programming. PhD thesis, University of Washington, 2023. Available at https://tinyurl.com/vbandip

    work page 2023

  6. [6]

    Beck and T

    J. Beck and T. Fiala. ``Integer-making'' theorems. Discrete Appl. Math., 3(1):1--8, 1981

    work page 1981

  7. [7]

    Dadush, A

    D. Dadush, A. Nikolov, K. Talwar, and N. Tomczak-Jaegermann. Balancing vectors in any norm. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 1--10. IEEE, 2018

    work page 2018

  8. [8]

    Bansal and H

    N. Bansal and H. Jiang. Decoupling via affine spectral-independence: Beck--Fiala and Koml\'os bounds beyond Banaszczyk. arXiv:2508.03961, 2025

    work page arXiv 2025

  9. [9]

    B. Bukh. An improvement of the Beck--Fiala theorem. Combin. Probab. Comput., 25(3):380--398, 2016

    work page 2016

  10. [10]

    A. Zouzias. A matrix hyperbolic cosine algorithm and applications. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), Part I, Lecture Notes in Computer Science, vol. 7391, pages 846--858. Springer, 2012

    work page 2012

  11. [11]

    R. Meka. Discrepancy and beating the union bound. Windows on Theory, a research blog, 2014. https://windowsontheory.org/2014/02/07/discrepancy-and-beating-the-union-bound/

    work page 2014

  12. [12]

    Dadush, H

    D. Dadush, H. Jiang, and V. Reis. A new framework for matrix discrepancy: Partial coloring bounds via mirror descent. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 649--658. ACM, 2022

    work page 2022

  13. [13]

    Bansal, H

    N. Bansal, H. Jiang, and R. Meka. Resolving Matrix Spencer conjecture up to poly-logarithmic rank. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 1814--1819. ACM, 2023. arXiv:2208.11286

    work page arXiv 2023

  14. [14]

    B. Carl. Entropy numbers, s -numbers, and eigenvalue problems. J. Funct. Anal., 41(3):290--306, 1981

    work page 1981

  15. [15]

    Carl and A

    B. Carl and A. Pajor. Gelfand numbers of operators with values in a Hilbert space. Invent. Math., 94(3):479--504, 1988

    work page 1988

  16. [16]

    M. B. Cohen and R. Peng. _p row sampling by Lewis weights. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 183--192. ACM, 2015

    work page 2015

  17. [17]

    W. J. Davis, V. D. Milman, and N. Tomczak-Jaegermann. The distance between certain n -dimensional Banach spaces. Israel J. Math., 39(1--2):1--15, 1981

    work page 1981

  18. [18]

    Y. Gordon. On Milman's inequality and random subspaces which escape through a mesh in R^n . In Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, vol. 1317, pages 84--106. Springer, Berlin, 1988

    work page 1988

  19. [19]

    Vershynin

    R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018

    work page 2018

  20. [20]

    F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, pages 187--204. Interscience, New York, 1948

    work page 1948

  21. [21]

    D. R. Lewis. Finite dimensional subspaces of L_p . Studia Math., 63(2):207--212, 1978

    work page 1978

  22. [22]

    Ledoux and M

    M. Ledoux and M. Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 23. Springer-Verlag, Berlin, 1991

    work page 1991

  23. [23]

    Matou s ek and A

    J. Matou s ek and A. Naor, editors. Open problems on embeddings of finite metric spaces. Problem 2.1, ``Subspaces of _1 into _1^n '' (G. Schechtman, 2002), 2003. Revised version available at http://kam.mff.cuni.cz/ matousek/metrop.ps.gz

    work page 2002

  24. [24]

    A. Pietsch. Operator Ideals. VEB Deutscher Verlag der Wissenschaften, Berlin, 1979; North-Holland, Amsterdam, 1980

    work page 1979

  25. [25]

    G. Pisier. The Volume of Convex Bodies and Banach Space Geometry. Cambridge Tracts in Mathematics, vol. 94. Cambridge University Press, Cambridge, 1999

    work page 1999

  26. [26]

    Reis and T

    V. Reis and T. Rothvoss. Vector balancing in Lebesgue spaces. Random Structures & Algorithms, 62(3):667--688, 2023

    work page 2023

  27. [27]

    Schechtman

    G. Schechtman. More on embedding subspaces of L_p in _r^n . Compositio Mathematica, 61(2):159--169, 1987

    work page 1987

  28. [28]

    Fourier analytic methods in convex geometry

    American Institute of Mathematics. Fourier analytic methods in convex geometry. Problem list from the AIM workshop, 2007. https://aimath.org/WWN/fourierconvex/fourierconvex.pdf

    work page 2007

  29. [29]

    J. Spencer. Six standard deviations suffice. Trans. Amer. Math. Soc., 289(2):679--706, 1985

    work page 1985

  30. [30]

    Talagrand

    M. Talagrand. Embedding subspaces of L_1 into _1^N . Proc. Amer. Math. Soc., 108(2):363--369, 1990

    work page 1990