A zonotope is a Minkowski sum of finitely many line segments. Bourgain and Lindenstrauss (1993) proved that the Euclidean ball Bn⊂RnB_n\subset\mathbb{R}^n can be approximated within Hausdorff distance ε\varepsilon by a zonotope with NN summands all of the same length, with N≤c(n)(ε−2∣log⁡ε∣)(n−1)/(n+2)N\le c(n)(\varepsilon^{-2}|\log\varepsilon|)^{(n-1)/(n+2)}, matching the general lower bound of Bourgain–Lindenstrauss–Milman (1989), N≥c1(n)ε−2(n−1)/(n+2)N\ge c_1(n)\varepsilon^{-2(n-1)/(n+2)}, only up to a logarithmic factor; they also noted that their equal-length proof is tied to the sphere's geometry and does not extend obviously to general zonoids. The subsequent literature resolved most of this: Matoušek (1996) achieved the optimal logarithm-free bound for arbitrary zonoids in ambient dimensions at least 5, with equal-length summands, and Siegel (2025) removed the logarithmic factor for arbitrary zonoids in ambient dimensions 3 and 4 — but only with summands of unequal length, explicitly leaving open whether equal lengths suffice there, even for the ball. The open problem is: in ambient dimensions 3 and 4, determine whether the optimal rate is attainable with equal-length summands for the ball (and, at least at the logarithmic level, for general zonoids), or whether the equal-length constraint provably costs a logarithmic factor. Equivalently: construct (or rule out) optimal equal-weight quadrature for the cosine transform (the spherical integral u↦∫Sn−1∣⟨u,y⟩∣ dτ(y)u\mapsto\int_{S^{n-1}}|\langle u,y\rangle|\,d\tau(y) of a measure τ\tau on the sphere) on the 2-sphere and the 3-sphere.

Background

A zonotope in Rn\mathbb{R}^n is a Minkowski sum (elementwise set addition) of finitely many line segments Z=∑j=1N[−xj,xj]Z=\sum_{j=1}^{N}[-x_j,x_j]; a zonoid is a Hausdorff limit of zonotopes. The Hausdorff distance between convex bodies containing the origin equals the supremum norm of the difference of their support functions, where the support function of a body KK is hK(u)=max⁡y∈K⟨u,y⟩h_K(u)=\max_{y\in K}\langle u,y\rangle. A foundational fact (going back to the projection formulas of Cauchy, and central to Betke and McMullen's 1983 study of estimating sizes of convex bodies from projections) is that a symmetric convex body is a zonoid exactly when its support function is the cosine transform hK(u)=∫Sn−1∣⟨u,y⟩∣ dτ(y)h_K(u)=\int_{S^{n-1}}|\langle u,y\rangle|\,d\tau(y) of a positive measure τ\tau on the unit sphere Sn−1S^{n-1}, called the generating measure; KK is a zonotope with NN summands exactly when τ\tau is supported on NN points, the weights being the segment half-lengths. Thus approximating a zonoid within Hausdorff distance ε\varepsilon by an NN-summand zonotope is equivalent to approximating the cosine transform of τ\tau in the uniform norm over u∈Sn−1u\in S^{n-1} by an NN-point discrete measure, and requiring all summands to have equal length is exactly requiring the approximating measure to have equal weights 1/N1/N — an equal-weight quadrature rule on the sphere.

For the Euclidean ball BnB_n (whose generating measure is uniform on Sn−1S^{n-1}), Bourgain, Lindenstrauss and Milman (1989), using spherical harmonics (the expansions of functions on the sphere in the eigenfunctions of the spherical Laplacian), proved the lower bound: any zonotope within Hausdorff distance ε\varepsilon of BnB_n must have N≥c1(n)ε−2(n−1)/(n+2)N\ge c_1(n)\varepsilon^{-2(n-1)/(n+2)} summands. Bourgain and Lindenstrauss (1988) constructed approximating zonotopes with N≤c2(n)(ε−2∣log⁡ε∣)(n−1)/(n+2)N\le c_2(n)(\varepsilon^{-2}|\log\varepsilon|)^{(n-1)/(n+2)}, so the exponent is optimal up to a possible logarithmic factor. In the 1989 paper they asked what changes if all summands must have the same length. Linhart (1989) and Wagner (1993) obtained equal-length bounds for the ball (Wagner via quadrature formulas with equal weights, for n<6n<6, and his method also covered zonoids sufficiently close to balls), and Bourgain–Lindenstrauss (1993) established the equal-length bound N≤c2(n)(ε−2∣log⁡ε∣)(n−1)/(n+2)N\le c_2(n)(\varepsilon^{-2}|\log\varepsilon|)^{(n-1)/(n+2)} in all dimensions n≥2n\ge 2, by partitioning the sphere into 'good spherical parallelepipeds' and replacing, on each piece, the normalized surface measure by an equal-weight average of Dirac masses with the same barycenter. Their proof, however, depends strongly on the coordinate structure of the sphere and, as the authors state, does not generalize in an obvious way to other zonoids; and the paper leaves open whether the logarithmic factor is necessary.

Two later developments nearly completed the picture (using the equivalent relative-error formulation K⊂P⊂(1+ε)KK\subset P\subset(1+\varepsilon)K, and writing d=n−1d=n-1 for the dimension of the sphere, in which the optimal error with NN summands is of order N−1/2−3/(2d)N^{-1/2-3/(2d)}). Matoušek (1996), adapting combinatorial discrepancy techniques (the study of two-colorings of point sets under which every set of a given family is nearly color-balanced, applied here via partial-coloring and halfspace-discrepancy arguments), improved the upper bounds for arbitrary zonoids: he attained the optimal logarithm-free rate in ambient dimensions n≥5n\ge 5 (d≥4d\ge 4) — and, as reported in later literature, with summands of equal length for all zonoids — and the rate with a log⁡\sqrt{\log} loss in ambient dimensions 3 and 4. Siegel (2025) closed the remaining logarithmic gap for arbitrary zonoids in ambient dimensions 3 and 4 (a result equivalent to optimal uniform approximation rates for shallow ReLU neural networks — single-hidden-layer networks built from the rectified-linear activation max⁡(0,x)\max(0,x) — on their variation spaces, i.e. function classes whose norm is the total variation of the representing measure; this equivalence is the source of recent interest in the problem); however, his entropy-based construction produces summands of unequal length, and the published paper states explicitly that it is unknown whether the optimal rate can be achieved with equal-length summands — even for the ball — in ambient dimensions below 5. This leaves precisely one coherent open case of the classical problem: the cost of the equal-length constraint in ambient dimensions 3 and 4.

Problem Statement

Let BnB_n be the Euclidean unit ball in Rn\mathbb{R}^n and let δH\delta_H denote Hausdorff distance. A zonotope Z=∑j=1N[−xj,xj]Z=\sum_{j=1}^{N}[-x_j,x_j] (Minkowski sum of segments) has equal-length summands if ∣x1∣=⋯=∣xN∣|x_1|=\cdots=|x_N|. Writing xj=αjzjx_j=\alpha_j z_j with zj∈Sn−1z_j\in S^{n-1} and αj>0\alpha_j>0, the generating measure of ZZ is τ′=∑j=1Nαjδzj\tau'=\sum_{j=1}^{N}\alpha_j\delta_{z_j}, whose cosine transform u↦∫Sn−1∣⟨u,y⟩∣ dτ′(y)=∑j=1Nαj∣⟨u,zj⟩∣u\mapsto\int_{S^{n-1}}|\langle u,y\rangle|\,d\tau'(y)=\sum_{j=1}^{N}\alpha_j|\langle u,z_j\rangle| is exactly the support function hZh_Z, so equal-length summands are equal-weight atoms of τ′\tau'. The generating measure of the ball is a fixed dimension-dependent multiple of the normalized surface measure μ\mu on Sn−1S^{n-1} (Cauchy's projection formula), and by rotation invariance the cosine transform of μ\mu is the constant κn:=∫Sn−1∣⟨u,y⟩∣ dμ(y)\kappa_n:=\int_{S^{n-1}}|\langle u,y\rangle|\,d\mu(y), independent of u∈Sn−1u\in S^{n-1}. It follows that equal-length zonotope approximation of BnB_n is equivalent, up to constants depending only on nn, to the equal-weight quadrature problem of making sup⁡u∈Sn−1∣1N∑j=1N∣⟨u,zj⟩∣−κn∣\sup_{u\in S^{n-1}}\bigl|\frac{1}{N}\sum_{j=1}^{N}|\langle u,z_j\rangle|-\kappa_n\bigr| small.

It is known (Bourgain–Lindenstrauss–Milman 1989) that every zonotope Z=∑j=1N[−xj,xj]Z=\sum_{j=1}^{N}[-x_j,x_j] with δH(Z,Bn)≤ε\delta_H(Z,B_n)\le\varepsilon satisfies N≥c1(n) ε−2(n−1)/(n+2)N\ge c_1(n)\,\varepsilon^{-2(n-1)/(n+2)}, and (Bourgain–Lindenstrauss 1993) that for every n≥2n\ge2 there are equal-length zonotopes ZZ with δH(Z,Bn)≤ε\delta_H(Z,B_n)\le\varepsilon and N≤c2(n)(ε−2∣log⁡ε∣)(n−1)/(n+2)N\le c_2(n)(\varepsilon^{-2}|\log\varepsilon|)^{(n-1)/(n+2)}. In ambient dimensions n≥5n\ge5 the logarithmic factor has been removed even with equal-length summands and for arbitrary zonoids (Matoušek 1996), and for arbitrary zonoids in ambient dimensions 3 and 4 it has been removed with summands of unequal length (Siegel 2025, where the same result reads: error at most C(d)N−1/2−3/(2d)C(d)N^{-1/2-3/(2d)} with d=n−1d=n-1). In ambient dimension n=2n=2 the question is closed by a classical construction: the regular 2N2N-gon, which is a zonotope with NN equal-length summands, approximates the disk with Hausdorff error of order N−2N^{-2}, matching the lower bound. The equal-length question therefore survives precisely in ambient dimensions 3 and 4.

The open problem is to settle, in ambient dimensions n=3n=3 and n=4n=4, the cost of the equal-length constraint:

  1. (Achievability) Does there exist, for n=3n=3 or n=4n=4 (or both), a constant C(n)C(n) and ε0(n)>0\varepsilon_0(n)>0 such that for every 0<ε<ε0(n)0<\varepsilon<\varepsilon_0(n) the ball BnB_n admits a zonotopic approximation δH(Z,Bn)≤ε\delta_H(Z,B_n)\le\varepsilon with equal-length summands and N≤C(n) ε−2(n−1)/(n+2)N\le C(n)\,\varepsilon^{-2(n-1)/(n+2)}, i.e. with no logarithmic factor? Equivalently, in the equal-weight quadrature formulation on Sn−1S^{n-1}: are there points z1,…,zN∈Sn−1z_1,\dots,z_N\in S^{n-1} (not necessarily distinct) with sup⁡u∈Sn−1∣1N∑j=1N∣⟨u,zj⟩∣−κn∣≤C(n)N−1/2−3/(2(n−1))\sup_{u\in S^{n-1}}\bigl|\frac{1}{N}\sum_{j=1}^{N}|\langle u,z_j\rangle|-\kappa_n\bigr|\le C(n)N^{-1/2-3/(2(n-1))}?

  2. (Lower bound / necessity) Or is there, for n=3n=3 or n=4n=4 (or both), an exponent γ(n)>0\gamma(n)>0 such that every equal-length zonotope with δH(Z,Bn)≤ε\delta_H(Z,B_n)\le\varepsilon must have N≥c(n) ε−2(n−1)/(n+2)(log⁡(1/ε))γ(n)N\ge c(n)\,\varepsilon^{-2(n-1)/(n+2)}(\log(1/\varepsilon))^{\gamma(n)} for all sufficiently small ε\varepsilon — proving that the equal-length constraint genuinely costs a logarithmic factor? The known spherical-harmonics lower bound applies to all zonotopes and therefore cannot by itself separate the equal-length case.

  3. (Zonoid extension) The same question for zonoids beyond the ball in ambient dimensions 3 and 4: for an origin-symmetric zonoid K⊂RnK\subset\mathbb{R}^n (n=3,4n=3,4) with generating measure τ\tau (at least for non-atomic τ\tau), can the optimal rate — or at least the logarithmic-level rate currently available only for balls (Bourgain–Lindenstrauss 1993) and zonoids sufficiently close to balls (Wagner 1993) — be achieved by equal-weight discrete measures τ′=1N∑jδzj\tau'=\frac{1}{N}\sum_j\delta_{z_j} in the cosine-transform norm?

The open problem splits into the two alternatives above (items 1 and 2) for the ball in ambient dimensions 3 and 4; the remaining dimension and item 3 are extensions of the same objective of characterizing the cost of the equal-length constraint for zonoid approximation in low ambient dimensions.

References

  1. Jean Bourgain and Joram Lindenstrauss, Approximating the ball by a Minkowski sum of segments with equal length, Discrete & Computational Geometry 9 (1993), no. 2, 131–144. DOI: 10.1007/BF02189313, https://doi.org/10.1007/BF02189313
  2. J. Bourgain and J. Lindenstrauss, Distribution of points on spheres and approximation by zonotopes, Israel Journal of Mathematics 64 (1988), no. 1, 25–31. DOI: 10.1007/BF02767366, https://doi.org/10.1007/BF02767366
  3. J. Bourgain, J. Lindenstrauss, and V. Milman, Approximation of zonoids by zonotopes, Acta Mathematica 162 (1989), no. 1, 73–141. DOI: 10.1007/BF02392835, https://doi.org/10.1007/BF02392835
  4. Gerold Wagner, On a new method for constructing good point sets on spheres, Discrete & Computational Geometry 9 (1993), no. 2, 111–129. DOI: 10.1007/BF02189312, https://doi.org/10.1007/BF02189312
  5. Jiří Matoušek, Improved upper bounds for approximation by zonotopes, Acta Mathematica 177 (1996), no. 1, 55–73. DOI: 10.1007/BF02392598, https://doi.org/10.1007/BF02392598
  6. Jonathan W. Siegel, Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks, Constructive Approximation 62 (2025), no. 2, 441–469. DOI: 10.1007/s00365-025-09712-9, https://doi.org/10.1007/s00365-025-09712-9 (preprint: arXiv:2307.15285, https://arxiv.org/abs/2307.15285)
  7. J. Linhart, Approximation of a ball by zonotopes using uniform distribution on the sphere, Archiv der Mathematik 53 (1989), no. 1, 82–86. DOI: 10.1007/BF01194876, https://doi.org/10.1007/BF01194876
  8. Richard J. Gardner, Markus Kiderlen, and Peyman Milanfar, Convergence of algorithms for reconstructing convex bodies and directional measures, The Annals of Statistics 34 (2006), no. 3, 1331–1374. DOI: 10.1214/009053606000000335, https://doi.org/10.1214/009053606000000335 (preprint: arXiv:math/0608011, https://arxiv.org/abs/math/0608011)
  9. U. Betke and P. McMullen, Estimating the sizes of convex bodies from projections, Journal of the London Mathematical Society (2) 27 (1983), no. 3, 525–538. DOI: 10.1112/jlms/s2-27.3.525, https://doi.org/10.1112/jlms/s2-27.3.525
  10. Zhengjie Sun, Wenwu Gao, and Xingping Sun, Spherical quasi-interpolation using scaled zonal kernels, preprint (2024), arXiv:2408.14803, https://arxiv.org/abs/2408.14803
  11. Yi Li, Optimal Embeddings of Constant-Dimensional Subspaces of LpL^p into ℓpN\ell_p^N, preprint (2026), arXiv:2607.11747, https://arxiv.org/abs/2607.11747
  12. Eliza O'Reilly and Venkat Chandrasekaran, Operatopes, Operanoids, and Noncommutative Zonoids, preprint (2026), arXiv:2602.08103, https://arxiv.org/abs/2602.08103