Lower bounds on the minimal dispersion of point sets via cover-free families 0 0 footnotetext: The work of the first and the third author has been supported by the grant P202/23/04720S of the Grant Agency of the Czech Republic. The work of the second author has been supported by the grant 23-06815M
M. Trödler, J. Volec, and J. Vybíral · 2025
Read Lower bounds on the minimal dispersion of point sets via cover-free families 0 0 footnotetext: The work of the first and the third author has been supported by the grant P202/23/04720S of the Grant Agency of the Czech Republic. The work of the second author has been supported by the grant 23-06815M by M. Trödler, J. Volec, and J. Vybíral (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-2504-00715.txt.
Introduction
Matěj Trödler, Jan Volec, and Jan Vybíral sharpen, in a 2025 preprint, lower bounds on how well a finite point set can fill a box. The measure is dispersion: the volume of the largest aligned box that dodges every point. Small dispersion means the points probe the space evenly. The authors build on a link they found between dispersion and cover-free families, a topic from extremal set theory. A result by Michel and Scott feeds that link. Out comes a shelf of lower bounds on the point count needed to cap dispersion at a given level.
No single bound rules them all. For each bound on the shelf, some mix of dimension and target accuracy makes it the strongest. The picture tells designers of sampling schemes that the cheapest point budget depends on the regime. The paper is a step in quasi-Monte Carlo theory.
Catalog record
| CREATOR | M. Trödler, J. Volec, and J. Vybíral |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-00715
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lower bounds on the minimal dispersion of point sets via cover-free families 0 0 footnotetext: The work of the first and the third author has been supported by the grant P202/23/04720S of the Grant Agency of the Czech Republic. The work of the second author has been supported by the grant 23-06815M of the Grant Agency of the Czech Republic. M. Trödler, J. Volec, and J. Vybíral Abstract We elaborate on the intimate connection between the largest volume of an empty axis-parallel box in a set of n n points from [ 0 , 1 ] d [0,1]^{d} and cover-free families from the extremal set theory. This connection was discovered in a recent paper of the authors. In this work, we apply a very recent result of Michel and Scott to obtain a whole range of new lower bounds on the number of points needed so that the largest volume of such a box is bounded by a given ε \varepsilon . Surprisingly, it turns out that for each of the new bounds, there is a choice of the parameters d d and ε \varepsilon such that the bound outperforms the others. 1 Introduction Let X\subset[0,1]^{d} be a (finite) set of points. There are several ways of how to measure whether the points of X are well spread. One way, which has recently attracted the attention of many researchers, is the so-called dispersion . The dispersion of X is the volume of the largest axis-parallel box in [0,1]^{d} that contains no point of X , i.e., \disp(X):=\sup_{B:B\cap X=\emptyset}|B|. (1) Here, the supremum is taken over all the boxes B=\prod_{i=1}^{d}(a_{i},b_{i}) , where 0\leq a_{i}<b_{i}\leq 1 for all i\in[d], and |B| stands for the (Lebesgue) volume of B . The study of this notion goes back to [ 13 , 22 ] and [ 23 ] . A very natural extremal problem is to determine the smallest possible dispersion for a given number of points in [0,1]^{d} . For fixed integers d and n , we denote the minimum dispersion of an n -point set X\subseteq[0,1]^{d} by \disp^{*}(n,d):=\inf_{\begin{subarray}{c}X\subset[0,1]^{d}\\ |X|=n\end{subarray}}\disp(X). (2) It is sometimes convenient to study this problem in the inverse setting: given an integer d and \varepsilon\in(0,1) , how many points do we need to place into the d -dimensional unit cube (and how?) so that their dispersion is at most \varepsilon ? The extremal problem is reflected by the quantity \displaystyle N(\varepsilon,d) \displaystyle:=\min\{n\in\mathbb{N}:\disp^{*}(n,d)\leq\varepsilon\} (3) \displaystyle=\min\{n\in\mathbb{N}:\exists X\subset[0,1]^{d}\ \text{with}\ |X|=n\ \text{and}\ \disp(X)\leq\varepsilon\}. As mentioned above, a number of upper and lower bounds on the quantities \disp^{*}(n,d) and N(\varepsilon,d) have been established. The elementary lower bound \disp^{*}(n,d)\geq\frac{1}{n+1} was improved in [ 7 ] to \disp^{*}(n,d)\geq\frac{5}{4(n+5)} . As the next step, for d\geq 2 and \varepsilon\in(0,1/4) , it was shown in [ 2 ] that N(\varepsilon,d)\geq\frac{\log_{2}d}{8\varepsilon}, (4) which seems to be the first lower bound on N(\varepsilon,d) that grows with d . A further improvement was obtained by Bukh and Chao [ 6 ] , who proved \disp^{*}(n,d)\geq\frac{1}{e}\cdot\frac{2d}{n}\left(1-\frac{4d}{n^{1/d}}\right). (5) This can be translated into the following lower bound on the inverse problem: N(\varepsilon,d)\geq\frac{1}{e}\cdot\frac{d}{\varepsilon}\quad\text{ for every $\varepsilon\leq(8d)^{-d}$}. (6) The bounds ( 5 ) and ( 6 ) are nearly optimal when d is fixed, and we study the limiting behavior for n (or 1/\varepsilon ) tending to infinity. However, note that ( 5 ) yields ( 6 ) only for very small values of \varepsilon . Regarding upper bounds on N(\varepsilon,d) , a series of recent papers [ 18 , 26 , 31 ] have shown that N(\varepsilon,d)\leq\frac{C\log d\cdot\log\frac{1}{\varepsilon}}{\varepsilon^{2}}\,. (7) In [ 29 ] we have shown that this bound is nearly optimal for \varepsilon being large: Theorem 1 ( [ 29 ] ) . There is an absolute constant c>0 such that for any integer d\geq 2 and any real \varepsilon\in\left(\frac{1}{4\sqrt{d}},\frac{1}{4}\right) , it holds that N(\varepsilon,d)>\frac{c\,\log d}{\varepsilon^{2}\cdot\log{\frac{1}{\varepsilon}}}\,. (8) On one hand, ( 8 ) matches ( 7 ) up to a polylogarithmic factor in 1/\varepsilon . On the other hand, ( 8 ) holds only for \varepsilon of the order at least 1/\sqrt{d} . Some further bounds for different regimes of \varepsilon and d were obtained in [ 4 , 18 , 19 , 20 , 24 ] , and the dispersion of certain specific sets was studied also in [ 5 , 12 , 15 , 16 , 17 , 28 , 30 ] . The aim of this work is to establish lower bounds on N(\varepsilon,d) that are valid when \varepsilon<1/\sqrt{d} . Our main result is the following. Theorem 2 . Fix a positive integer k . There exists a constant c_{k} such that if d is a positive integer satisfying d\geq d^{\frac{k}{k+1}}+k and \varepsilon\in\left(0,2^{-k-2}\right) , then the following is true. (i) If \varepsilon\geq d^{-\frac{k^{2}}{k+1}} then N(\varepsilon,d)\geq c_{k}\cdot\varepsilon^{-\frac{k+1}{k}} . (ii) If \varepsilon<d^{-\frac{k^{2}}{k+1}} then N(\varepsilon,d)\geq c_{k}\cdot d^{\frac{k}{k+1}}\,\varepsilon^{-1} . The proof of part (i) of Theorem 2 is given in Section 2 and the second part of Theorem 2 is demonstrated in Section 3 . We postpone the comparison of the bounds given in Theorem 2 to other bounds available in the literature to Section 4 . 1.1 Notation For a finite set X , we denote its size by |X| . With a slight abuse of notation, we also write |A| for A\subseteq[0,1]^{d} to denote the Lebesgue measure of A . It will be, however, always clear from the context whether the argument of |\cdot| is a finite set or not. For a positive integer d , we denote by [d] the set \{1,2,\ldots,d\} . Additionally, for a non-negative integer k , we write \binom{[d]}{k} to denote the collection of all the k -element subsets of [d] . Given a point x\in[0,1]^{d} and an integer i\in[d] , we denote by (x)_{i} the i -th coordinate of x . 2 Part (i) of Theorem 2 and cover-free families We utilize a strong connection between lower bounds on N(\varepsilon,d) and a certain problem in extremal set theory. The following is a generalization of the notion of an r -cover-free family , a crucial notion in the proof of ( 8 ) in [ 29 ] . Definition 1 . Let \mathcal{F} be a family of subsets of a ground set X . We say that \mathcal{F} is (k,r) -cover-free if no intersection of any k sets of \mathcal{F} is contained in the union of any other r sets from \mathcal{F} , i.e., if for all A_{1},\dots,A_{k}\in\mathcal{F} and all B_{1},\dots,B_{r}\in\mathcal{F}\setminus\{A_{1},\dots,A_{k}\} it holds that \bigcap_{i=1}^{k}A_{i}\not\subset\bigcup_{j=1}^{r}B_{j}. Let C(k,r,d) be the smallest size of the ground set such that a d -element (k,r) -cover-free family exists, i.e., C(k,r,d):=\min\{n\in\mathbb{N}\colon\exists(k,r)\text{-cover-free family }\mathcal{F}_{n}\text{ on }[n]\text{ with }|\mathcal{F}_{n}|=d\}. Note that the case k=1 corresponds to r -cover-free families introduced in 1964 by Kautz and Singleton [ 14 ] and then intensively studied since the 1980s in various contexts [ 1 , 3 , 8 , 9 , 10 , 11 , 25 , 27 ] . The following very recent result of Michel and Scott [ 21 ] plays a crucial role for us. Theorem 3 ( [ 21 , Lemma 2.2] ) . If k,s,t and d are positive integers satisfying d\geq k+t , then C(k,s+t,d)\geq\frac{1}{2k^{k}}\cdot\min\bigl\{d^{k},\ s(k+t)^{k}\bigr\} . The connection between lower bounds on N(\varepsilon,d) and cover-free families was first discovered in