Constructive and efficiently computable spherical $t$-designs with asymptotically optimal cardinality

A spherical $t$-design on the unit sphere $S^d$ is a finite point set whose equal-weight average reproduces the surface average of every polynomial of degree at most $t$; it is the equal-weight case of optimal quadrature on the sphere. Existence is now known at the asymptotically optimal cardinality: for every $N\ge C_d t^d$ there is a spherical $t$-design on $S^d$ with exactly $N$ points (Bondarenko, Radchenko, Viazovska, Annals of Mathematics 2013), improving the threshold $N\ge c_d t^{2d(d+1)/(d+2)}$ of the source paper (Bondarenko and Viazovska, SIAM J. Discrete Math. 2010) and settling the Korevaar–Meyers conjecture. All known proofs of these existence statements, however, are nonconstructive, resting on the Brouwer fixed point theorem and Brouwer degree theory. The problem is to give an explicit, efficiently computable construction that, for general dimension $d$ and strength $t$, produces a spherical $t$-design with $N=O_d(t^d)$ points (ideally for every prescribed $N\ge C_d t^d$), or otherwise replace the nonconstructive topological argument by a constructive procedure with the same asymptotically optimal guarantees ($N\le C_d t^d$). Present constructive knowledge is confined to fixed small strengths, numerical optimization without general proofs, and interval-arithmetic-certified designs on $S^2$ up to $t=160$ with $N=(t+1)^2$ points; no provably correct general construction is known.

Background

A spherical $t$-design is a finite set $X_N=\{x_1,\dots,x_N\}$ on the unit sphere $S^d=\{x\in\mathbb{R}^{d+1}:\|x\|=1\}$, equipped with its surface measure $\mu_d$ of total mass $|S^d|=\mu_d(S^d)$, such that

$$\frac{1}{|S^d|}\int_{S^d} p(x)\,d\mu_d(x)=\frac{1}{N}\sum_{i=1}^N p(x_i)$$

for every real polynomial $p$ of total degree at most $t$. Equivalently, all Weyl sums $\sum_{i=1}^N Y_{\ell k}(x_i)$ vanish for the spherical harmonics $Y_{\ell k}$ (the standard orthogonal basis of the polynomial space on the sphere, indexed by degree $\ell=1,\dots,t$ and order $k$). The concept was introduced in this form by Delsarte, Goethals and Seidel (1977), growing out of the theory of cubature formulas on the sphere (cubature is the multivariate analogue of quadrature, i.e., of approximating an integral by a weighted sum of finitely many function values); it is exactly an equal-weight (Chebyshev-type) quadrature rule, i.e., one in which every node carries the same weight $1/N$. Designs serve as the benchmark 'perfectly uniform' point sets for numerical integration, interpolation and data processing on spheres.

Two features make the equal-weight condition the hard part. First, a dimension count — the space of polynomials of degree $\le t$ restricted to $S^d$ has dimension of order $t^d$ — forces $N\ge c_d t^d$; point sets meeting this lower bound (so-called tight designs) exist only sporadically, for a short list of small strengths. Second, if the weights are allowed to differ, positive quadrature formulas with the optimal number $C_d t^d$ of nodes are classical (Mhaskar, Narcowich and Ward, 2000); it is exact equal weighting that has resisted construction.

The existence theory developed over four decades. Seymour and Zaslavsky (1984) proved that spherical $t$-designs exist on $S^d$ for all $d$ and $t$, nonconstructively and with no cardinality bound. After successive bounds with large exponents, Korevaar and Meyers (1993) proved $N(d,t)\le C_d t^{(d^2+d)/2}$ for the minimal cardinality $N(d,t)$ and conjectured the optimal bound $N(d,t)\le C_d t^d$. Bondarenko and Viazovska's 'Spherical designs via Brouwer fixed point theorem' (SIAM J. Discrete Math. 24 (2010) 207–217), proved that for each $N\ge c_d\,t^{2d(d+1)/(d+2)}$ there exists a spherical $t$-design on $S^d$ consisting of exactly $N$ points, by combining area-regular partitions of the sphere (partitions into regions of equal surface measure and small diameter), spherical Marcinkiewicz–Zygmund inequalities (sampling inequalities that control the integral of a spherical polynomial by finitely many of its point values at a well-distributed set), and the Brouwer fixed point theorem (every continuous self-map of a convex compact set has a fixed point). Three years later Bondarenko, Radchenko and Viazovska settled the conjecture in a stronger form: for each $N\ge C_d t^d$ there exists a spherical $t$-design on $S^d$ with exactly $N$ points (Annals of Mathematics 178 (2013) 443–452), using Brouwer degree theory (a topological counting invariant for zeros of continuous maps that forces a zero under suitable boundary conditions). This is optimal in order, and it was extended to well-separated designs — designs whose points are pairwise separated by an angle depending only on $d$ — with the same order bound (Constructive Approximation 41 (2015) 93–112).

Every one of these existence proofs is nonconstructive: the topological argument certifies that a zero of a map exists without any procedure to locate it. The constructive state of the art is the following. Sloan and Womersley (2009) characterized designs as the global minima of an explicitly computable nonnegative functional $A_{N,t}$ — a fixed positive multiple of the sum of squared Weyl sums $\sum_{\ell=1}^{t}\sum_{k}|\sum_j Y_{\ell k}(x_j)|^2$, so that $A_{N,t}=0$ exactly at designs — and proved that a stationary point set of $A_{N,t}$ whose mesh norm (the covering radius, i.e., the geodesic radius of the largest hole in the point set) is below $1/(t+1)$ is already a design; this underlies numerical minimization approaches (Gräf and Potts, 2011, using fast spherical Fourier transforms, i.e., fast algorithms for expanding data in the spherical-harmonic basis; later Barzilai–Borwein-type solvers, a family of two-step gradient-descent methods with specially chosen step sizes). Computer-assisted existence proofs via interval arithmetic — computation with mathematically guaranteed enclosing intervals — certify designs with $N=(t+1)^2$ points on $S^2$: for $t\le100$ by Chen, Frommer and Lang (2011), for well-conditioned designs up to $t\le60$ by An, Chen, Sloan and Womersley (2010), and, according to the 2026 survey of An and Zhuang, up to $t\le160$; the same survey states that there is currently no theoretical proof of the existence of a $t$-design with $(t+1)^2$ nodes for arbitrary $t$ even on $S^2$. Explicit algebraic constructions exist only for fixed small strength, e.g., Misawa's (2026) explicit 5-designs in every dimension and 7-designs in even dimensions. In particular, no explicit or provably efficient construction is known that produces, for general $d$ and growing $t$, a spherical $t$-design with $N=O_d(t^d)$ points; this is the open target.

Problem Statement

Give a constructive counterpart to the nonconstructive existence theorems for spherical designs — a constructive gap that remains open after the source paper 'Spherical designs via Brouwer fixed point theorem' and the subsequent optimal-order existence theorem.

Base goal (mandatory). For every dimension $d$ and strength $t$, construct a spherical $t$-design on the unit sphere $S^d=\{x\in\mathbb{R}^{d+1}:\|x\|=1\}$, where $\mu_d$ denotes surface measure and $|S^d|=\mu_d(S^d)$ its total mass — that is, a point set $X_N=\{x_1,\dots,x_N\}\subset S^d$ with $\frac{1}{N}\sum_{i=1}^N p(x_i)=\frac{1}{|S^d|}\int_{S^d} p\,d\mu_d$ for all real polynomials $p$ of degree $\le t$ — with asymptotically optimal cardinality $N\le C_d\,t^d$, where $C_d$ depends only on $d$. Strong form (optional strengthening, mirroring the existence theorem): for every prescribed $N\ge C_d t^d$, construct a spherical $t$-design consisting of exactly $N$ points.

Efficiency requirement. The construction must be explicit and efficiently computable, with a proof of correctness.

Equivalently, in the formulation of the limitation stated in Bondarenko–Viazovska (2010): replace the nonconstructive Brouwer fixed-point / topological-degree existence argument by a constructive procedure with the same asymptotically optimal guarantees ($N\le C_d t^d$).

References

1. P. Delsarte, J. M. Goethals, and J. J. Seidel (1977), 'Spherical codes and designs', Geometriae Dedicata 6(3), 363–388. DOI: 10.1007/BF03187604, https://doi.org/10.1007/bf03187604
2. P. D. Seymour and T. Zaslavsky (1984), 'Averaging sets: A generalization of mean values and spherical designs', Advances in Mathematics 52(3), 213–240. DOI: 10.1016/0001-8708(84)90022-7, https://doi.org/10.1016/0001-8708(84)90022-7
3. G. Wagner and B. Volkmann (1991), 'On averaging sets', Monatshefte für Mathematik 111(1), 69–78. DOI: 10.1007/BF01299278, https://doi.org/10.1007/bf01299278
4. B. Bajnok (1992), 'Construction of spherical t-designs', Geometriae Dedicata 43(2), 167–179. DOI: 10.1007/BF00147866, https://doi.org/10.1007/bf00147866
5. J. Korevaar and J. L. H. Meyers (1993), 'Spherical Faraday cage for the case of equal point charges and Chebyshev-type quadrature on the sphere', Integral Transforms and Special Functions 1(2), 105–117. DOI: 10.1080/10652469308819013, https://doi.org/10.1080/10652469308819013
6. R. H. Hardin and N. J. A. Sloane (1996), 'McLaren's improved snub cube and other new spherical designs in three dimensions', Discrete & Computational Geometry 15(4), 429–441. DOI: 10.1007/BF02711518, https://doi.org/10.1007/BF02711518
7. H. N. Mhaskar, F. J. Narcowich, and J. D. Ward (2000), 'Spherical Marcinkiewicz–Zygmund inequalities and positive quadrature', Mathematics of Computation 70(235), 1113–1130. DOI: 10.1090/S0025-5718-00-01240-0, https://doi.org/10.1090/S0025-5718-00-01240-0
8. A. V. Bondarenko and M. S. Viazovska (2010), 'Spherical designs via Brouwer fixed point theorem', SIAM Journal on Discrete Mathematics 24(1), 207–217. DOI: 10.1137/080738313; arXiv:0811.1416, https://arxiv.org/abs/0811.1416
9. A. Bondarenko, D. Radchenko, and M. Viazovska (2013), 'Optimal asymptotic bounds for spherical designs', Annals of Mathematics 178(2), 443–452. DOI: 10.4007/annals.2013.178.2.2; arXiv:1009.4407, https://arxiv.org/abs/1009.4407
10. A. Bondarenko, D. Radchenko, and M. Viazovska (2015), 'Well separated spherical designs', Constructive Approximation 41(1), 93–112. DOI: 10.1007/s00365-014-9238-2; arXiv:1303.5991, https://arxiv.org/abs/1303.5991
11. I. H. Sloan and R. S. Womersley (2009), 'A variational characterisation of spherical designs', Journal of Approximation Theory 159(2), 308–318. DOI: 10.1016/j.jat.2009.02.014, https://doi.org/10.1016/j.jat.2009.02.014
12. C. An, X. Chen, I. H. Sloan, and R. S. Womersley (2010), 'Well conditioned spherical designs for integration and interpolation on the two-sphere', SIAM Journal on Numerical Analysis 48(6), 2135–2157. DOI: 10.1137/100795140, https://doi.org/10.1137/100795140
13. X. Chen, A. Frommer, and B. Lang (2011), 'Computational existence proofs for spherical t-designs', Numerische Mathematik 117(2), 289–305. DOI: 10.1007/s00211-010-0332-5, https://doi.org/10.1007/s00211-010-0332-5
14. M. Gräf and D. Potts (2011), 'On the computation of spherical designs by a new optimization approach based on fast spherical Fourier transforms', Numerische Mathematik 119(4), 699–724. DOI: 10.1007/s00211-011-0399-7, https://doi.org/10.1007/s00211-011-0399-7
15. R. S. Womersley (2018), 'Efficient Spherical Designs with Good Geometric Properties', in Contemporary Computational Mathematics — A Celebration of the 80th Birthday of Ian Sloan, Springer, 1243–1285. DOI: 10.1007/978-3-319-72456-0_57, https://doi.org/10.1007/978-3-319-72456-0_57
16. R. Zheng and X. Zhuang (2024), 'On the existence and estimates of nested spherical designs', Applied and Computational Harmonic Analysis 73, article 101672; arXiv:2405.10607. DOI: 10.1016/j.acha.2024.101672, https://arxiv.org/abs/2405.10607
17. M. Ehler, K. Gröchenig, and C. Karner (2025), 'Geodesic cycles on the Sphere: t-designs and Marcinkiewicz–Zygmund Inequalities', arXiv:2501.06120, https://arxiv.org/abs/2501.06120
18. R. Misawa (2026), 'Explicit construction of spherical 5- and 7-designs', arXiv:2602.19757, https://arxiv.org/abs/2602.19757
19. C. An and X. Zhuang (2026), 'A Survey on Spherical Designs: Existence, Numerical Constructions, and Applications', arXiv:2601.11963, https://arxiv.org/abs/2601.11963