🔢 mathematics

A tight lower bound on the minimal dispersion

Original authors: Matěj Trödler, Jan Volec, Jan Vybíral

Published 2026-06-12

📖 5 min read🧠 Deep dive

Original authors: Matěj Trödler, Jan Volec, Jan Vybíral

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to scatter a handful of marbles across a giant, multi-dimensional room. The goal is to place these marbles so that no matter where you look, you can't find a large empty space between them. In mathematics, this "room" is a unit cube (a box where every side is length 1), and the "empty space" is a smaller box that doesn't touch any of your marbles.

The size of the largest empty box you can find is called the dispersion. If the dispersion is small, your marbles are spread out very evenly. If it's large, there are big gaps where you could easily hide a whole other box.

The big question the paper tackles is: How many marbles (points) do you need to guarantee that there are no "big" empty boxes left?

The Setup: The "Empty Room" Problem

Mathematicians have been trying to figure out the relationship between:

$d$ : The number of dimensions (how "wide" the room is).
$\epsilon$ : The maximum size of an empty box you are willing to tolerate.
$n$ : The number of points (marbles) you need to place to ensure no empty box is bigger than $\epsilon$ .

Previous research had found some rules of thumb. One rule suggested that if you want to shrink the empty boxes, you might need a number of points that grows with the square of $1/\epsilon$ (meaning if you want the empty space to be half as big, you might need four times as many points). However, there was a nagging doubt: Is that "square" rule actually necessary, or is it just a flaw in the way we were calculating it? Maybe we could get away with fewer points?

The New Discovery: The "Square" Rule is Real

The authors of this paper, Trödler, Volec, and Vybíral, say: Stop hoping for a shortcut. The square rule is real.

They proved that for high-dimensional rooms, if you want to shrink the empty space significantly, you genuinely need a number of points proportional to $1/\epsilon^2$ . You cannot do it with fewer. This was surprising because usually, in high dimensions, things get messy, but here, the "cost" of precision is exactly as high as the most pessimistic estimates suggested.

How They Proved It: The "Trap" Strategy

Instead of trying to check every possible empty box in the room (which would be impossible), the authors used a clever trick. They decided to only look at a very specific, tiny class of "test boxes."

Think of it like a game of hide-and-seek:

The Old Way: Try to hide from a seeker who can look in any direction, in any shape of hiding spot.
The New Way: The authors said, "Let's only care if the seeker can hide in these specific, weirdly shaped boxes."

They constructed these test boxes so that they were very hard to hit with a random point. To ensure a point set hits all of these specific boxes, the points had to be arranged in a very specific, complex pattern.

The Secret Weapon: Cover-Free Families

This is where the paper gets into "extremal set theory" (a branch of math about organizing groups).

The authors realized that if your points are to hit all these specific test boxes, the points must form a structure called an $r$ -cover-free family.

The Analogy: Imagine you have a group of people (the points). You want to make sure that no single person can be "covered" or "explained away" by a group of $r$ other people.
If you have a group that is cover-free, it means everyone is unique and essential; you can't remove anyone without losing the ability to cover a specific spot.

The authors used a known mathematical limit on how small these "unique" groups can be. They showed that to satisfy the condition of hitting all their specific test boxes, you need a massive number of points. Because these test boxes were just a subset of all possible boxes, if you need this many points to hit the test boxes, you definitely need at least that many to hit all boxes.

The Bottom Line

The paper proves that in high-dimensional spaces, the effort required to eliminate large empty gaps grows quadratically with the precision you want.

The Metaphor: If you want to pave a floor so perfectly that no gap is larger than a coin, and you are working in a room with hundreds of dimensions, you can't just sprinkle a few more tiles. You need a number of tiles that explodes as you try to make the gaps smaller.
The Result: The "expensive" formula (involving $1/\epsilon^2$ ) isn't a mistake in the math; it's a fundamental law of how points can be distributed in high-dimensional space.

The authors also note that they didn't try to find the perfect constant number (the exact multiplier), but they proved the relationship holds true. They left it as an open question whether this method can be tweaked to work for even smaller gaps, but for the range they studied, the "square law" is tight.

Technical Summary of "A tight lower bound on the minimal dispersion"

Problem Statement
The paper addresses the problem of minimal dispersion for point sets in the $d$ -dimensional unit cube $[0, 1]^d$ . The dispersion of a set $X$ , denoted $\text{disp}(X)$ , is defined as the volume of the largest axis-parallel box in $[0, 1]^d$ that does not intersect $X$ . The authors investigate the minimal dispersion $\text{disp}^*(n, d)$ for a set of cardinality $n$ , and its inverse function $N(\varepsilon, d)$ , which represents the minimum number of points required to ensure a dispersion of at most $\varepsilon$ .

While the trivial lower bound $N(\varepsilon, d) \ge 1/\varepsilon - 1$ is well-known, the dependence on the dimension $d$ has been a subject of recent research. Previous work established upper bounds such as $N(\varepsilon, d) \le C \cdot d^2 \log d / \varepsilon$ and, more recently, $N(\varepsilon, d) \le C \cdot \log d \cdot \log(1/\varepsilon) / \varepsilon^2$ (Litvak [11], refined in [21]). A central open question was whether the $\varepsilon^{-2}$ factor in the latter bound is an artifact of the proof method or a necessary feature of the problem.

Methodology
The authors resolve this question by constructing a specific, restricted class of test boxes rather than considering all possible axis-parallel boxes. The core methodology involves:

Reduction to Extremal Set Theory: The authors translate the geometric problem of bounding dispersion into a combinatorial problem concerning $r$ -cover-free families. A family $\mathcal{F}$ of subsets is $r$ -cover-free if no set in $\mathcal{F}$ is contained in the union of any $r$ other sets from $\mathcal{F}$ .
Construction of Test Boxes: For a fixed $\varepsilon$ , they define a collection $\mathcal{B}$ of axis-parallel boxes. Each box $B_{A,j}$ is constructed such that one coordinate interval is small (near 0) and a specific set of $2k-2$ other coordinates are bounded away from zero (near 1), where $k$ is chosen such that $2^{-(k+1)} < \varepsilon \le 2^{-k}$ .
Cover-Free Mapping: They associate any point set $X$ that intersects every box in $\mathcal{B}$ with a family of sets $\{F_1, \dots, F_d\}$ , where $F_j$ contains points with a small $j$ -th coordinate. They prove that if $X$ intersects all boxes in $\mathcal{B}$ , the family $\{F_j\}$ must be $r$ -cover-free with $r = 2k-2$ .
Application of Combinatorial Bounds: The authors utilize a lower bound on the size of the ground set for $r$ -cover-free families established by Alon and Asodi [2] (based on Ruszinkó [17]). This bound relates the size of the ground set (which corresponds to the number of points $|X|$ ) to the parameters $d$ and $r$ .

Key Contributions and Results
The primary contribution is the proof that the $\varepsilon^{-2}$ dependence in the upper bound is optimal for sufficiently large $\varepsilon$ , contradicting the intuition that the quadratic term might be an artifact of probabilistic proof methods.

Theorem 1: The authors prove the existence of an absolute constant $c > 0$ such that for any integer $d \ge 2$ and real $\varepsilon$ satisfying $\frac{1}{4\sqrt{d}} \le \varepsilon \le \frac{1}{4}$ , the following lower bound holds:
$N(\varepsilon, d) > \frac{c \log d}{\varepsilon^2 \cdot \log(1/\varepsilon)}$
This result matches the recently obtained upper bound (Litvak [11], [21]) up to logarithmic terms, confirming the optimality of the $\varepsilon^{-2}$ factor in this regime.
Corollary 2: Reformulated in terms of minimal dispersion, for positive integers $d$ and $n$ with $2 \log d \le n \le c_1 d$ , the minimal dispersion satisfies:
$\text{disp}^*(n, d) \ge c_2 \left(\frac{\log d}{n}\right)^{1/2} \cdot \left(\log\left(\frac{n}{\log d}\right)\right)^{-1/2}$

Significance and Claims
The paper claims that the result is "surprising" because it demonstrates that a linear dependence on $1/\varepsilon$ and a logarithmic dependence on $d$ cannot coexist; the quadratic dependence on $1/\varepsilon$ is necessary. The authors emphasize that this strong lower bound is achieved by considering only a "very small class" of test boxes compared to the total number of axis-parallel boxes.

The work relies on the insight that boxes with a large number of coordinates bounded away from zero are the most difficult to "hit" with randomly generated points, a phenomenon observed in the analysis of Litvak [11] and [21]. By focusing on these specific difficult cases, the authors reduce the problem to a known combinatorial structure ( $r$ -cover-free systems), allowing them to derive a tight lower bound. The authors note that the constant $c$ in their proof can be chosen as $1/1920$ , though they did not attempt to optimize it. They leave as an open problem whether this method can be extended to smaller values of $\varepsilon$ .