Algebro-combinatorial generalizations of the Victoir method for constructing weighted designs

Hiroshi Nozaki, Masanori Sawa · 2025

Read Algebro-combinatorial generalizations of the Victoir method for constructing weighted designs by Hiroshi Nozaki, Masanori Sawa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-12829.txt.

Introduction

Numerical integration over many variables needs sample points that mimic a probability distribution very exactly. Such point sets are called weighted designs, and smaller is better. Nozaki and Sawa extend a classic shrinking trick by Victoir, which used simple combinatorial tables to cut design sizes while keeping the exactness.

Their wider version, built in the framework of Euclidean polynomial spaces, allows tables with any number of levels, not just two. As a payoff, they build equal-weight 5-designs for product measures, including the Gaussian, with a number of points growing like the fourth power of the dimension. They also prove that Gaussian designs exist with even fewer points for any exactness level. The constructions are explicit, with no numerical approximation, and one result sharpens a known theorem about embedding classic function spaces.

Catalog record

CREATORHiroshi Nozaki, Masanori Sawa
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-12829

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Algebro-combinatorial generalizations of the Victoir method for constructing weighted designs Hiroshi Nozaki, Masanori Sawa Abstract A weighted t t -design in ℝ d \mathbb{R}^{d} is a finite weighted set that exactly integrates all polynomials of degree at most t t with respect to a given probability measure. A fundamental problem is to construct weighted t t -designs with as few points as possible. Victoir (2004) proposed a method to reduce the size of weighted t t -designs while preserving the t t -design property by using combinatorial objects such as combinatorial designs or orthogonal arrays with two levels. In this paper, we give an algebro-combinatorial generalization of both Victoir’s method and its variant by the present authors (2014) in the framework of Euclidean polynomial spaces, enabling us to reduce the size of weighted designs obtained from the classical product rule. Our generalization allows the use of orthogonal arrays with arbitrary levels, whereas Victoir only treated the case of two levels. As an application, we present a construction of equi-weighted 5 5 -designs with O ⁡ ( d 4 ) O(d^{4}) points for product measures such as Gaussian measure π − d / 2 e − ∑ i = 1 d x i 2 d x 1 ⋯ d x d \pi^{-d/2}e^{-\sum_{i=1}^{d}x_{i}^{2}}dx_{1}\cdots dx_{d} on ℝ d \mathbb{R}^{d} or equilibrium measure π − d ∏ i = 1 d ( 1 − x i 2 ) − 1 / 2 d x 1 ⋯ d x d \pi^{-d}\prod_{i=1}^{d}(1-x_{i}^{2})^{-1/2}dx_{1}\cdots dx_{d} on ( − 1 , 1 ) d (-1,1)^{d} , where d d is any integer at least 5. The construction is explicit and does not rely on numerical approximations. Moreover, we establish an existence theorem of Gaussian t t -designs with N N points for any t ≥ 2 t\geq 2 , where N < q t ​ d t − 1 = O ⁡ ( d t − 1 ) N<q^{t}d^{t-1}=O(d^{t-1}) for fixed sufficiently large prime power q q . As a corollary of this result, we give an improvement of a famous theorem by Milman (1988) on isometric embeddings of the classical finite-dimensional Banach spaces. 0 0 0 2020 Mathematics Subject Classification: 65D32 (05B15, 05E30) Keywords: Weighted design, Euclidean polynomial space, Product rule, Orthogonal array, Linear code, Gaussian design, Equilibrium design, Isometric embedding, Spherical design, Association scheme 1 Introduction A weighted t -design in \mathbb{R}^{d} with respect to a probability measure \mu is a finite subset X\subset\mathbb{R}^{d} with a positive weight function w:X\to\mathbb{R}_{>0} such that \int_{\mathbb{R}^{d}}f(x)\,d\mu(x)=\sum_{x\in X}w(x)f(x) for all polynomials f\in\mathbb{R}_{t}[x_{1},\ldots,x_{d}] , where \mathbb{R}_{t}[x_{1},\ldots,x_{d}] denotes the space of real polynomials of total degree at most t in d variables; in particular, this is called an (equi-weighted) t -design if w is constant. We refer the reader to Bannai et al. [ 3 ] for a good introduction to the basics on design theory in algebraic combinatorics. On the other hand, a weighted design has long been studied in the context of cubature formula in numerical analysis and related areas, with emphasis on the connection to the theory of orthogonal polynomials. A comprehensive textbook for such analytic aspects of design theory is Dunkl and Xu [ 13 ] . One of the major problems in design theory is to construct a small-sized weighted t -design for given values of d and t . Suppose a measure \mu is expressed in terms of a density function \phi(x) , that is, d\mu(x)=\phi(x)\,dx . The product rule constructs weighted t -designs as Cartesian products of lower-dimensional weighted t -designs, provided that the density function \phi(x) can be written as a Cartesian product of lower-dimensional density functions. This is exemplified by the Gaussian measure \pi^{-d/2}e^{-\sum_{i=1}^{d}x_{i}^{2}}dx_{1}\cdots dx_{d} on \mathbb{R}^{d} and the equilibrium measure \pi^{-d}\prod_{i=1}^{d}(1-x_{i}^{2})^{-1/2}dx_{1}\cdots dx_{d} on (-1,1)^{d} (see Section 4 in this paper). Although the product rule can respond to the preference for simplicity of construction, it has the serious drawback that the size of the resulting weighted design grows exponentially. In this paper, we provide a method for reducing the size of designs obtained through the product rule. A main purpose of this paper is to develop a generalization of both Victoir’s method [ 29 ] and its variant by the present authors [ 27 ] in the framework of Euclidean polynomial spaces; see Definition 2.2 of this paper. The Victoir method reduces the size of a weighted design by replacing specific point-subsets with structured configurations associated with combinatorial objects such as combinatorial designs or orthogonal arrays. Combinatorial designs can be interpreted as designs in Johnson schemes, while orthogonal arrays correspond to designs in Hamming schemes. These designs admit two main types of generalization: one is the design in association schemes, introduced by Delsarte [ 11 ] ; the other is the design in polynomial spaces, proposed by Godsil [ 16 ] . These two notions are slightly different, in the sense that an object satisfying one definition may not satisfy the other. Delsarte’s designs are based on the representation theory of finite groups, whereas Godsil’s designs focus on approximating the average of polynomial functions over the entire set. Since our goal is to reduce the size of weighted designs, Godsil’s framework is quite effective in our context. In design theory, a major recent breakthrough is the explicit construction of spherical t -designs in \mathbb{R}^{d} for arbitrary values of d and t [ 6 , 30 ] . As Xiang [ 30 ] also described, constructing weighted designs on a computer using approximations of real numbers with arbitrary precision is important in numerical analysis, but it cannot be regarded as an explicit construction method. As an application of our generalization, we present an explicit construction of equi-weighted 5 -designs with O(d^{4}) points for Gaussian measure or equilibrium measure, where d is any integer at least 5 (Theorems 4.7 and 4.8 ). We also prove, in a manner not entirely constructive, an existence theorem of Gaussian t -designs with N points for any t\geq 2 , where N<q^{t}d^{t-1}=O(d^{t-1}) for fixed sufficiently large prime power q (Theorem 4.11 ). This paper is organized as follows. In Section 2 , we review the precise definition of designs for polynomial spaces and some fundamental results. We slightly generalize the class of spherical polynomial spaces, which include those arising from association schemes, by introducing the concept of Euclidean polynomial spaces. This generalization extends the range of applicable combinatorial structures, including regular t -wise balanced designs. In Section 3 , we generalize Victoir’s method to designs for polynomial spaces (Theorem 3.6 ). To this end, we extend some known results from [ 15 , 16 ] . This generalization enables the use of orthogonal arrays of arbitrary levels, beyond level 2 which is the only case treated in Victoir [ 29 ] . In Section 4 , we first present an explicit construction of orthogonal arrays of strength t with small run sizes by using the dual codes of certain extended BCH codes. We then apply Theorem 3.6 (and Corollaries 3.8 and 3.9 ) with those orthogonal arrays to large weighted designs obtained via the product rule. This not only leads to an explicit construction of equi-weighted 5 -designs with O(d^{4}) points for Gaussian measure or equilibrium measure, but also establishes

Read the complete text