Minimal dispersion of large volume boxes in the cube

Kurt S. MacKay

Abstract

In this note we present a construction which improves the best known bound on the minimal dispersion of large volume boxes in the unit cube. Let $d>1$ . The dispersion of $T\subset[0,1]^{d}$ is defined as the supremum of the volume taken over all axis parallel boxes in the cube which do not intersect $T$ . The minimal dispersion of $n$ points in the cube is defined as the infimum of the dispersion taken over all $T$ such that $|T|=n$ . Define the “large volume” regime as the class of all volumes $\frac{1}{4}<r\leq\frac{1}{2}$ . The inverse of the minimal dispersion is denoted as $N(r,d)$ . When the volume is large, the best known upper bound on $N(r,d)$ is of the order ${(r-\frac{1}{4})}^{-1}.$ The construction presented in this note yields an upper bound given by

N(r,d)\leq\left\lfloor\frac{\pi}{\sqrt{r-\frac{1}{4}}}\right\rfloor-3.

Some of our intermediate estimates are sharp given the condition that $d\geq C_{r}$ , where $C_{r}$ is a positive constant which depends only on the volume $r$ .

1 Introduction

The dispersion of $T\subset[0,1]^{d}$ is defined as the supremum of the volume taken over all axis parallel boxes in the cube which do not intersect $T$ . The minimal dispersion of $n$ points in the cube is defined as the infimum of the dispersion taken over all $T$ such that $|T|=n$ . The inverse of the minimal dispersion, denoted as $N(r,d)$ , is the size of the smallest set of points which intersects any axis parallel box with volume exceeding $r$ . The problem of estimating the minimal dispersion (which was originally defined in [19] as modification of a concept in [6]) has been given considerable attention in recent years. Some contemporary works such as [1], [3], [5], [7], [8] [10], [11], [12], [13], [14], [15], [17], [21], [22], are focused on this problem, or modifications (general $k$ -dispersion, spherical dispersion, etc.) thereof. We will refer to these works when we discuss the known results, and the best known bounds on the minimal dispersion. The dispersion of some particular sets has been studied in [9], [18], [20]. Dispersion is of interest in studying topics in subjects such as Discrete Geometry and Approximation Theory and in studying particular random point configurations as in [15]. Define the “large volume” regime as the class of all volumes $\frac{1}{4}<r\leq\frac{1}{2}$ . When the volume is large, the best known upper bound given in [17], is of the order ${(r-\frac{1}{4})}^{-1}.$ In this note we present a construction which improves the best known bound in this setting. First, consider the situation when $r\geq\frac{1}{2}$ . The minimal dispersion is attained with one point at the center of the cube. Thus, it is clear that in the large volume regime we are interested in estimating the minimal dispersion when $r<\frac{1}{2}$ . Theorem 1.1 improves the best known bound previously given by Sosnovec in [17].

Theorem 1.1.

Let $d>1$ , and let $r\in(\frac{1}{4},\frac{1}{2})$ . Then

N(r,d)\leq\left\lfloor\frac{\pi}{\sqrt{r-\frac{1}{4}}}\right\rfloor-3.

(1)

Let $r\in(\frac{1}{4},\frac{1}{2})$ , and let $\textbf{1}=(1,1,\ldots,1)\in\mathbb{R}^{d}$ . We construct a set of points on the diagonal in the following way. Consider the fractional sequence

\mathfrak{Q}(r)=\bigg{\{}r,\ \frac{r}{1-r},\ \frac{r}{1-\frac{r}{1-r}}\ ,\ \frac{r}{1-\frac{r}{1-\frac{r}{1-r}}},\ \frac{r}{1-\frac{r}{1-\frac{r}{1-\frac{r}{1-r}}}},\ \ldots\bigg{\}}.

Denote the subsequent elements in the sequence as $q_{1},q_{2},\ldots\in\mathfrak{Q}(r)$ . We show that there exists a smallest number $n:=n_{r}\geq 1$ such that

q_{n}\geq 1-r.

Consider the configuration given by

\mathfrak{q}(r)=\{q_{i}\mathbf{1}:1\leq i\leq n\}.

We can see some examples of the configurations when $|\mathfrak{q}(r)|=5,12,19,26$ (respectively). They are given below.
[Uncaptioned image]

Define the function

r\longmapsto|\mathfrak{q}(r)|

(2)

where $|\cdot|$ denotes the cardinality.
It may not be obvious yet, but we can see what the function looks like (a monotone decreasing step function) on some inclusion-ordered intervals in the examples given below.
[Uncaptioned image]

We obtain Theorem 1.1 by showing that this function is an upper bound for the minimal dispersion. Finally, we show that some of our estimates are sharp given that $d\geq C_{r}$ , where $C_{r}$ is a positive constant dependent on $r$ .

2 Previous results

Recall that the inverse of the minimal dispersion, denoted as $N(r,d)$ is defined as the smallest number of points that are needed to intersect any axis parallel box whose volume exceeds $r$ .

In their work [1], Aistleitner, Hinrichs, and Rudolf proved a lower bound for $r<\frac{1}{4}$ given by

(1-4r)\frac{\log_{2}d}{4r}\leq N(r,d).

(3)

This result gives a non-trivial estimate showing that the dispersion asymptotically increases with dimension when the volume is not large. The upper bound given by

N(r,d)\leq\frac{2^{7d+1}}{r}

(4)

was proved by Larcher, and is also presented in [1]. This is an improvement on the bound given by Rote and Tichy in [15]. The upper bound given by

N(r,d)\leq\frac{8d}{r}\log_{2}\bigg{(}\frac{33}{r}\bigg{)}

(5)

is a consequence of a more general result given in [2]. The authors present an argument which uses the $VC-$ dimension of $\mathfrak{B}$ (which is $2d$ ) instead of the ambient dimension $d$ . In the paper [16], Rudolf presented a probabilistic argument which yields the bound in (5). The bound in (5) is an improvement on (4) under the assumption that $r\geq\exp(-C^{d})$ where $C>1$ is an absolute constant. Sosnovec in [17] obtained another upper bound which is better when $d$ grows to infinity, namely

N(r,d)\leq C_{r}\log_{2}d.

(6)

The constant $C_{r}$ obtained in [17] grows extremely fast with $r$ . This constant was improved by Ullrich and Vybìral [21] who showed that

C_{r}=\frac{2^{7}}{r^{2}}\log_{2}^{2}\big{(}\frac{1}{r}\big{)}.

Litvak in [11] gives an improvement on the known bounds when $r\leq\exp(-d)$ , and showed that

N(r,d)\leq\frac{C\ln d}{r}\ln\big{(}\frac{1}{r}\big{)}.

Litvak also established that when $r\geq(\ln^{2}d)/(d\ln\ln(2d))$ that

N(r,d)\leq\frac{C\ln d}{r^{2}}\ln\big{(}\frac{1}{r}\big{)},

which is an improvement on the bound given by Ullrich and Vybìral. Recently, Litvak and Livshyts in [12], proved an upper bound for $d\geq 2$ , and $r\in(0,\frac{1}{2}]$ given by

N(r,d)\leq 12e\frac{4d\log(\log(\frac{8}{r}))+\log(1/r)}{r}.

(7)

They also showed that a random choice of points with respect to the uniform distribution in the cube gives the result with high probability. We mention here that Hinrichs, Krieg, Kunsch, and Rudolph in [7] showed that using a random choice of points uniformly distributed within the cube, one cannot expect to get anything better than

\max\bigg{\{}\frac{c}{r}\log\bigg{(}\frac{1}{r}\bigg{)},\frac{d}{2r}\bigg{\}}.

Thus we can see that in the probabilistic setting, (7) is close to the best possible. Now we turn our attention to the large volume regime $r>\frac{1}{4}$ . Sosnovec in [17] gave a dimension independent upper bound for $N(r,d)$ . In particular, he proved that for $r\in(\frac{1}{4},1)$ , and $d\geq 2$ ,

N(r,d)\leq\left\lfloor{\frac{1}{r-\frac{1}{4}}}\right\rfloor+1.

The goal of this paper is to improve this bound. This is established in Theorem 1.1.

2.1 Definitions and Notation

Let $d\geq 1$ . Denote unit cube as $[0,1]^{d}$ . Let $|\cdot|$ denote the cardinality, let $\textrm{dom}(\cdot)$ denote the domain, and let $\textbf{1}:=(1,1,\ldots,1)\in\mathbb{R}^{d}$ . The set of axis parallel boxes is defined as

\mathfrak{B}:=\bigg{\{}{\prod}_{i=1}^{d}I_{i}:\ I_{i}=[a_{i},b_{i})\subset[0,1]\bigg{\}}.

The dispersion of $T\subset[0,1]^{d}$ is defined as

\textrm{disp}(T):=\sup_{B\in\mathfrak{B},\ B\cap T=\emptyset}\textrm{Vol}(B).

The minimal dispersion is defined as

\textrm{disp}^{*}(n,d):=\inf_{T\subset[0,1]^{d},\ |T|=n}\textrm{disp}(T).

Let $r\in[0,1]$ . The inverse of the minimal dispersion is defined as

N(r,d):=\min\{n\in\mathbb{N}:\textrm{disp}^{*}(n,d)\leq r\}.

Let $k\geq 0$ . Inductively define a sequence of functions $\{f_{k}\}_{k\geq 0}$ in the following way. Let $\beta_{0}=1$ . Define $f_{0}:[0,1]\rightarrow[0,1]$ as the identity $f_{0}(x)=x$ . Given functions $f_{0},f_{1},\ldots f_{k-1}$ , and numbers $\beta_{0},\beta_{1},\ldots,\beta_{k-1}$ , define

\beta_{k}=\inf\{x\geq 0:x\in\textrm{dom}(f_{k-1}),\ f_{k-1}(x)=1\},

(8)

and define $f_{k}:[0,\beta_{k})\rightarrow\mathbb{R}$ by

f_{k}(x)=\frac{x}{1-f_{k-1}(x)}.

(9)

Proposition 3.2 shows that the infimum in (8) is attained for all $k~{}\geq~{}0$ . Let $k\geq 0$ . It is clear that $\textrm{dom}(f_{k})\subset\textrm{dom}(f_{k-1})$ , hence $\beta_{k}<\beta_{k-1}$ . Let $r\in(\frac{1}{4},\frac{1}{2}]$ (we include the the right endpoint here since the intermediate estimates are still valid here). The following definition is a complete description of the step function introduced in (2). Define

\alpha(r):=\inf\{k\geq 0:r\in\textrm{dom}(f_{k}),\ f_{k}(r)\geq 1-r\}+1,

(10)

and define

n_{r}:=\alpha(r)-1.

(11)

In Remark 3.8 we show that the infimum in (10) is attained.

3 Auxiliary tools

Proposition 3.1.

Let $i\geq 0$ . The function $f_{i}$ is strictly increasing on its domain.

Proof.

Employ induction on $i$ . Let $i=0$ . By definition $\mathrm{dom}(f_{0})=[0,1]$ . For all $x\in[0,1]$ , $f_{0}(x)=x$ . The base case is seen to be trivial. Assume that the proposition holds for $i=0,1,2,\ldots,k$ . Let $x_{1},x_{2}\in\textrm{dom}(f_{k+1})$ be such that $x_{1}<x_{2}$ . Then by domain inclusion $x_{1},x_{2}\in\textrm{dom}(f_{k})$ . By the induction hypothesis $f_{k}(x_{1})<f_{k}(x_{2})$ . It follows from the definition of $f_{k+1}$ as in (9) that

f_{k+1}(x_{1})=\frac{x_{1}}{1-f_{k}(x_{1})}<\frac{x_{2}}{1-f_{k}(x_{2})}=f_{k+1}(x_{2}).

This proves the proposition. ∎

In Proposition 3.2 we show that the infimum in (8) is attained.

Proposition 3.2.

Let $r_{0}=1$ . For each $i\geq 1$ there exists a unique number

r_{i}\in\mathrm{dom}(f_{i})=[0,\beta_{i})

with the properties

\beta_{i}=r_{i-1}

(12)

f_{i-1}(r_{i})=1-r_{i}

(13)

f_{i}(r_{i})=1.

(14)

Proof.

Note that $\beta_{1}=1=r_{0}$ . Employ induction on $n$ . For each $n>0$ we produce a number $r_{n}$ with the properties (12), (13), (14).

Let $n=1$ . Recall the definition of $f_{2}$ given in (9), by

f_{2}(x)=\frac{x}{1-f_{1}(x)}.

We will show that there exists $r_{1}\in$ $\mathrm{dom}(f_{1})$ such that

1=f_{1}(r_{1})=\frac{r_{1}}{1-f_{0}(r_{1})}.

Equivalently, we find the solution to the equation $f_{0}(x)-(1-x)=0.$ It is clear that $r_{1}=\frac{1}{2}<1=\beta_{1}$ , and that $\beta_{2}=r_{1}$ . This implies that $\mathrm{dom}(f_{2})=[0,\beta_{2}).$ Hence, $r_{1}$ has properties (12), (13), (14).

Let $n=2$ . Recall the definition of $f_{3}$ given in (9), by

f_{3}(x)=\frac{x}{1-f_{2}(x)}.

We show that there exists $r_{2}\in$ $\mathrm{dom}(f_{2})$ such that

1=f_{2}(r_{2})=\frac{r_{2}}{1-f_{1}(r_{2})}.

Equivalently, we show that there exists a solution to the equation

f_{1}(x)-(1-x)=0.

The function $f_{1}$ is strictly increasing by Proposition 3.1. Note that $f_{1}(0)=0$ , and $f_{1}(r_{1})=1$ . Apply the Intermediate Value Theorem to $f_{1}(x)-(1-x)$ . This yields a unique solution $r_{2}<r_{1}$ such that

f_{1}(r_{2})-(1-r_{2})=0.

It follows that $\beta_{3}=r_{2}$ , and that $\mathrm{dom}(f_{3})=[0,\beta_{3}).$ Hence $r_{2}$ has properties (12), (13), (14).

Let $k>2$ . Assume that there exist numbers $r_{0},r_{1},r_{2},\ldots,r_{k-1}$ with the properties (12), (13), (14). Under the assumption that $\mathrm{dom}(f_{k})=[0,\beta_{k})$ where $\beta_{k}=r_{k-1}$ , and $f_{k-1}(r_{k-1})=1$ . Recall the definition of $f_{k+1}$ given in (9), by

f_{k+1}(x)=\frac{x}{1-f_{k}(x)}.

We show that there exists $r_{k}\in$ $\mathrm{dom}(f_{k})$ , such that

1=f_{k}(r_{k})=\frac{r_{k}}{1-f_{k-1}(r_{k})}.

Equivalently, we show that there exists a solution to the equation

f_{k-1}(x)-(1-x)=0.

The function $f_{k-1}$ is strictly increasing by Proposition 3.1. Note that $f_{k-1}(0)=0,$ and by the induction hypothesis, $f_{k-1}(r_{k-1})=1.$ Apply the Intermediate Value Theorem to $f_{k-1}(x)-(1-x)$ . This yields a unique solution $r_{k}<r_{k-1}$ , such that

f_{k-1}(r_{k})-(1-r_{k})=0.

It follows that $\beta_{k+1}=r_{k}$ , and that $\mathrm{dom}(f_{k+1})=[0,\beta_{k+1}).$ This yields a number $r_{k+1}$ with the properties (12), (13), (14). This proves the proposition. ∎

Remark 3.3.

For each $k\geq 1$ , the infimum in the definition of $\beta_{k}$ is attained at $\beta_{k}=r_{k-1}$ . Proposition 3.2 justifies the assertion following the definition in (8). Fix the sequence

\{r_{m}\}_{m\geq 0}=\{\beta_{m+1}\}_{m\geq 0}.

(15)

Proposition 3.4.

Let $n\geq 1$ . Let $r\in(\frac{1}{4},\frac{1}{2})$ be such that $f_{i}(r)<1$ for all $i\leq n$ . Then for all $i\leq n$ ,

f_{i-1}(r)<f_{i}(r).

Proof.

Fix $n\geq 1$ . Employ induction on $i$ . Let $r\in(\frac{1}{4},\frac{1}{2})$ be such that $f_{i}(r)<1$ for all $i\leq n$ . Let $i=1$ . Recall the definitions of $f_{0},$ $f_{1}$ . Since $r<\frac{1}{2}$ , it follows that

f_{0}(r)=r<\frac{r}{1-r}=f_{1}(r).

Let $1\leq k<n$ . Assume as the induction hypothesis that for all $1\leq i\leq k$ ,

f_{i-1}(r)<f_{i}(r).

By assumption $f_{k-1}(r)<f_{k}(r)$ , then by definition of $f_{k}$ it follows that

f_{k}(r)=\frac{r}{1-f_{k-1}(r)}<\frac{r}{1-f_{k}(r)}=f_{k+1}(r).

This proves the proposition. ∎

Corollary 3.5.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . Let $n\geq 1$ be such that $r<r_{n}$ . Then for all $i\leq n$ ,

f_{i-1}(r)<f_{i}(r).

Proof.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . Let $n\geq 1$ be such that $r<r_{n}$ . The sequence $\{r_{m}\}_{m>0}$ defined in (15) is decreasing. Hence, $r<r_{n}<r_{n-1}<\cdots<r_{1}$ . Property (14) in Proposition 3.2 implies that $f_{k}(r_{k})=1$ for all $k\leq n$ . Since $r<r_{k}$ , it follows by Proposition 3.1 that $f_{k}(r)<f_{k}(r_{k})$ . Hence,

f_{k}(r)<f_{k}(r_{k})=1.

Now apply Proposition 3.4. ∎

Remark 3.6.

Corollary 3.5 gives the property that for all $n<k$ , $f_{n}(r_{k})<1$ . Property (14) in Proposition 3.2 gives that for all $k>0$ , $f_{k}(r_{k})=1$ . Let $r\in(\frac{1}{4},\frac{1}{2}]$ , and recall the definition in (10) given by

\alpha(r):=\inf\{k\geq 0:r\in\mathrm{dom}(f_{k}),\ f_{k}(r)\geq 1-r\}+1.

Then we have that for all $k>0$ ,

\alpha(r_{k})=k=n_{r_{k}}+1.

This gives the integral values of the step function in (2) evaluated at the left endpoints of the interval partition given by

\cdots[r_{3},r_{2}),[r_{2},r_{1}),[r_{1},1).

(16)

The following proposition shows that the function in (10) is constant over any interval in the partition (16).

Proposition 3.7.

Let $i\geq 1$ . Let $r\in(\frac{1}{4},\frac{1}{2}]$ be such that $r_{i}\leq r<r_{i-1}$ . Then

\alpha(r)=i.

Proof.

First, let $i=1$ , and let $r\in(\frac{1}{4},\frac{1}{2}]$ be such that $r_{1}\leq r<1$ . Since $r_{1}=\frac{1}{2}$ , it follows that $r=\frac{1}{2}$ . Hence, $\alpha(r)=1$ .

Let $i\geq 2$ , and let $r\in(\frac{1}{4},\frac{1}{2})$ be such that $r_{i}\leq r<r_{i-1}$ . Since $r<r_{i-1}$ , Corollary 3.5 implies that for all $k\leq i-1$ , $f_{k-1}(r)<f_{k}(r)$ . Apply Proposition 3.1 on $f_{i-2}$ to get $f_{i-2}(r)<f_{i-2}(r_{i-1})$ . By Proposition 3.2,

f_{i-2}(r_{i-1})=1-r_{i-1}.

It follows that

f_{i-2}(r)<f_{i-2}(r_{i-1})=1-r_{i}<1-r.

This means that for all $k\leq i-2$ ,

f_{k-2}(r)<1-r.

It follows that $n_{r}>i-2$ . Since $r_{i}\leq r$ , apply Proposition 3.1 on $f_{i-1}$ to get $f_{i-1}(r_{i})<f_{i-1}(r)$ . Recall that by Proposition 3.2,

f_{i-1}(r_{i})=1-r_{i}.

It follows that

1-r\leq 1-r_{i}=f_{i-1}(r_{i})<f_{i-1}(r).

Thus, $f_{i-1}(r)>1-r$ . It follows that $n_{r}\leq i-1.$ Therefore, $n_{r}=i-1.$ This proves the proposition. ∎

Remark 3.8.

Proposition 3.7 shows that the function in (10) is constant over the intervals in the partition from (16). This shows that for each $r\in(\frac{1}{4},\frac{1}{2}]$ , the infimum in the definition of $n_{r}$ as in (11) is attained.

A brief discussion on Geometric Rational Sequences follows. We use the results herein to obtain explicit values for the numbers $\{r_{k}\}_{k\geq 1}$ as in (15). The paper [4] provides results which can be applied to sequences of the form defined below.

Definition 3.9.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . A Geometric Rational Sequence $\{x_{n}(r)\}_{n\geq 0}$ is defined by setting an initial condition $x_{0}(r)=r$ , and recursively defining

x_{n+1}=\frac{r}{1-x_{n}}.

If $x_{n}=1$ , then define $x_{n+1}=\infty$ , $x_{n+2}=0$ , so that $x_{n+3}=r$ .

Definition 3.10.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . The reduced form of a Geometric Rational Sequence $\{y_{n}(r)\}_{n\geq 0}$ is defined by setting an initial condition

y_{0}(r)=-1+r,

and recursively defining

y_{n+1}(r)=-1-\frac{r}{y_{n}(r)}.

If $y_{n}(r)=0$ , then define $y_{n+1}(r)=\infty$ , $y_{n+2}(r)=-1$ , so that $y_{n+3}(r)=-1+r$ .

Remark 3.11.

Note that if $y_{n+3}(r)=-1+r$ , then $y_{n+2}(r)=-1$ . Hence, $y_{n+1}(r)=\infty$ and $y_{n}(r)=0$ . This occurs if and only if the sequence $\{y_{n}(r)\}_{n\geq 0}$ is cyclical.

Remark 3.12.

Let $i\geq 1$ , and let $r\leq r_{i}$ . Then,

y_{0}(r)=-1+r,

y_{1}(r)=-1+\frac{r}{1-r}=-1+f_{1}(r),

y_{2}(r)=-1+\frac{r}{1-f_{1}(r)}=-1+f_{2}(r).

Continuing in this way, we see that for all $k<i$ and $r\leq r_{i}$ ,

y_{k}(r)=-1+f_{k}(r).

Proposition 3.13.

Let $m>0$ . Then the reduced sequence $\{y_{n}(r_{m})\}_{n\geq 0}$ is cyclical with cycle length $m+3$ .

Proof.

From Remark 3.12, we have that for all $k<m$ ,

y_{k}(r_{m})=-1+f_{k}(r_{m}).

Apply Proposition 3.4 to yield

f_{k-1}(r_{m})<f_{k}(r_{m})

for all $k<m$ . This guarantees no repetition in the first $m-1$ terms of the reduced sequence $\{y_{n}(r_{m})\}_{n\geq 0}$ . By Proposition 3.2, $f_{m}(r_{m})=1$ . It follows that

y_{m}(r_{m})=f_{m}(r_{m})-1=1-1=0.

Recall the reduced sequence given in Definition 3.10. Then by definition

y_{m+1}(r_{m})=\infty

y_{m+2}(r_{m})=-1

y_{m+3}(r_{m})=1-r_{m}.

This shows that $y_{m+3}(r_{m})=1-r_{m}=y_{0}(r_{m})$ . It follows that the sequence is cyclical with cycle length $m+3$ . ∎

The following theorem from [4] will be used. Note that there is a typographical error in the condition $\sigma^{2}<4\gamma$ .

Theorem 3.14.

Let $\sigma$ , $\gamma\in\mathbb{R}$ with $\sigma^{2}<4\gamma$ , and $\theta=\arccos{\frac{\sigma}{2\sqrt{\gamma}}}$ . A sequence satisfying $y_{n+1}=\sigma-\frac{\gamma}{y_{n}}$ , $y_{1}\in\mathbb{R}$ , has a finite or infinite number of cluster points depending on whether or not $\frac{\theta}{\pi}$ is rational. Moreover, when $\frac{\theta}{\pi}=\frac{k}{m}\in\mathbb{Q}$ is irreducible, the sequence takes on $m$ distinct values $y_{1},y_{2},\ldots,y_{m}$ which are thereafter repeated in this order.

Proposition 3.15.

Let $n\geq 1$ . Let

R_{n}=\frac{1}{4}\frac{1}{\cos^{2}(\frac{\pi}{n+3})}.

Then the reduced sequence $\{y_{k}(R_{n})\}_{k\geq 0}$ has cycle length $n+3$ .

Proof.

Let $n\geq 1$ . Let

R_{n}=\frac{1}{4}\frac{1}{\cos^{2}(\frac{\pi}{n+3})}.

In reference to Theorem 3.14, the sequence $\{y_{k}(R_{n})\}_{k\geq 0}$ has the parameters $\sigma=-1$ , and $\gamma=R_{n}$ . Apply Theorem 3.14 with the given parameters, and set

\theta=\arccos{\big{(}\frac{-1}{2\sqrt{R_{n}}}\big{)}}=\arccos{\big{(}-\cos(\frac{\pi}{n+3})\big{)}}=\frac{\pi(n+2)}{n+3}.

Then

\frac{\theta}{\pi}\in\mathbb{Q}.

By Theorem 3.14, it follows that $\{y_{k}(R_{n})\}_{k\geq 0}$ has cycle length $n+3$ . ∎

Remark 3.16.

Proposition 3.15 gives a decreasing sequence of numbers $\{R_{n}\}_{n>0}\subset(\frac{1}{4},\frac{1}{2}]$ such that as $n$ goes to infinity $R_{n}\to\frac{1}{4}$ . We show that these numbers correspond to the numbers $\{r_{k}\}_{k\geq 1}$ given in (15). These are exactly the values of the endpoints in the partition given in (16).

Proposition 3.17.

Recall the sequence $\{r_{m}\}_{m>0}$ defined in (15). Then for all $n>0$ ,

r_{n}=R_{n}.

Proof.

Apply induction on $n$ . Let $n=1$ . It is easy to check that $r_{1}=\frac{1}{2}=R_{1}.$

Let $n=2$ . Recall that $\{R_{n}\}_{n>0}$ is decreasing. Hence, $R_{2}<R_{1}=\beta_{2}$ . By Proposition 3.2 it follows that $R_{2}\in\mathrm{dom}(f_{2})$ . By Proposition 3.15, the sequence $\{y_{k}(R_{2})\}_{k\geq 0}$ has cycle length $2+3$ . From Remark 3.11, it follows that $y_{2}(R_{2})=0$ . Then

y_{2}(R_{2})=0=1-1=f_{2}(R_{2})-1.

This implies that $f_{2}(R_{2})=1$ . Thus, $r_{2}=R_{2}$ .

Let $n=3$ . Note $R_{3}<R_{2}=\beta_{3}$ . Then by Proposition 3.2, it follows that $R_{3}\in\mathrm{dom}(f_{3})$ . By Proposition 3.15, the sequence $\{y_{k}(R_{3})\}_{k\geq 0}$ has cycle length $3+3$ . From Remark 3.11, it follows that $y_{3}(R_{3})=0$ . Then

y_{3}(R_{3})=0=1-1=f_{3}(R_{3})-1.

This implies that $f_{3}(R_{3})=1$ . Thus $r_{3}=R_{3}$ .

Fix $k>3$ . Assume that $r_{n}=R_{n}$ for $n=1,2,\ldots,k$ . Note $R_{k+1}<R_{k}=\beta_{k+1}$ . Then by Proposition 3.2, it follows that $R_{k+1}\in\mathrm{dom}(f_{k+1})$ . The sequence $\{y_{l}(R_{k+1})\}_{l\geq 0}$ has cycle length $(k+1)+3$ . From Remark 3.11, it follows that $y_{k+1}(R_{k+1})=0$ . Then

y_{k+1}(R_{k+1})=0=1-1=f_{k+1}(R_{k+1})-1.

This implies that $f_{k+1}(R_{k+1})=1$ . Thus, $r_{k+1}=R_{k+1}$ . ∎

4 Main results

In this section we give an upper bound for the minimal dispersion.

4.1 Upper bound

Let $r\in(\frac{1}{4},\frac{1}{2}]$ , and let $n_{r}$ be as in (11). We define the following configurations on the diagonal

\mathfrak{q}(r)=\{f_{k}(r)\textbf{1}:0\leq k\leq n_{r}\}.

(17)

It is clear that $|\mathfrak{q}(r)|=n_{r}+1$ .
We define two fundamental box types (Type 1 and Type 2). The definitions are given below, but first some examples in the plane should be elucidating. One can always think about the $2-$ dimensional projection of a higher dimensional box onto one of its faces.

(Example of Type 1 boxes, $d=2$ )

(Example of Type 2 boxes, $d=2$ )

Definition 4.1.

Let $B=I_{1}\times I_{2}\times\cdots\times I_{d}\in\mathfrak{B}$ . The box $B$ is Type $1$ , if one of the following conditions holds. There exists $1\leq j\leq d$ , such that $I_{j}\subset[0,r]$ , or such that $I_{j}\subset[f_{n_{r}}(r),1]$ . There exists $1\leq j\leq d$ , and $0\leq k\leq n_{r}-1$ , such that $I_{j}\subset[f_{k}(r),f_{k+1}(r)]$ .
The box $B$ is Type $2$ , if there exist $1\leq j,l\leq d$ , and $0\leq k\leq n_{r}-1$ , such that $I_{j}\subset[f_{k}(r),1]$ , and $I_{l}\subset[0,f_{k+1}(r)]$ .

Lemma 4.2.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . Let $B\in\mathfrak{B}$ be a box of Type $1$ or Type $2$ . Then Vol $(B)\leq r$ .

Proof.

Let $B=I_{1}\times I_{2}\times\cdots\times I_{d}\in\mathfrak{B}$ . First assume that $B$ is Type $1$ . Assume that $I_{i}\subset[0,r]$ . Then the lemma trivially holds. Assume that there exists $1\leq i\leq d$ , such that $I_{i}\subset[f_{n_{r}}(r),1]$ . Since $n_{r}$ is the smallest integer such that $f_{n_{r}}(r)\geq 1-r$ , it follows that

\textrm{Vol}(B)\leq|I_{i}|\leq 1-f_{n_{r}}(r)\leq r.

Assume that there exists $1\leq i\leq d$ , and $0\leq k<n_{r}$ such that $I_{i}\subset[f_{k}(r),f_{k+1}(r)]$ . Then

\textrm{ Vol}(B)\leq|I_{i}|\leq f_{k+1}(r)-f_{k}(r)=\frac{r}{1-f_{k}(r)}-f_{k}(r)=\frac{r-(1-f_{k}(r))f_{k}(r)}{1-f_{k}(r)}.

Recall that $n_{r}$ is the smallest integer such that $1-r\leq f_{n_{r}}(r)$ . Since $k<n_{r}$ , it follows that $f_{k}(r)<1-r$ . Then

\textrm{Vol}(B)\leq\frac{r-(1-f_{k}(r))f_{k}(r)}{1-f_{k}(r)}\leq\frac{r-rf_{k}(r)}{1-f_{k}(r)}=r.

Hence, if $B\in\mathfrak{B}$ is Type $1$ , then Vol $(B)\leq r$ .

Let $B\in\mathfrak{B}$ be a Type $2$ box. By definition there exist $1\leq i,j\leq d$ and $0\leq k\leq n_{r}-1$ such that $I_{i}\subset[f_{k}(r),1]$ and $I_{j}\subset[0,f_{k+1}(r)]$ . Recall the definition of $f_{k+1}$ as in (9) given by

f_{k+1}(r)=\frac{r}{1-f_{k}(r)}.

It follows that

\textrm{Vol}(B)\leq|I_{i}||I_{j}|\leq(1-f_{k}(r))\frac{r}{1-f_{k}(r)}=r.

This proves the lemma. ∎

Lemma 4.3.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . Let $B\in\mathfrak{B}$ be such that $\mathfrak{q}(r)\cap B=\emptyset$ . Then $B$ is either Type $1$ or Type $2$ .

Proof.

Let

P(r)=\{p_{i}:p_{i}=f_{i}(r),\ 0\leq i\leq n_{r}\},

(18)

\mathfrak{q}(r)=P(r)\mathbf{1}.

Let $B=I_{1}\times I_{2}\times\cdots\times I_{d}\in\mathfrak{B}$ . Notice that $\mathfrak{q}(r)\not=\emptyset$ for all $r\in(\frac{1}{4},\frac{1}{2}]$ . Then it is clear that there exists $1\leq i\leq d$ such that $I_{i}\neq[0,1]$ . Define

Q:=I_{i}\cap P(r).

If $Q=\emptyset$ , then $B$ is Type $1$ . From here we list the remaining possible cases.

Case 1: In this case $Q=\{p_{n_{r}}\}$ . Then $p_{n_{r}}\in I_{i}$ . It is clear that $I_{i}\subset(p_{{n_{r}}-1},1]$ . Since $B\cap\mathfrak{q}(r)=\emptyset$ , there exists $1\leq j\leq d$ such that $I_{j}\subset(p_{n_{r}},1]$ or $I_{j}\subset[0,p_{n_{r}})$ . If $I_{j}\subset(p_{n_{r}},1]$ , then by definition $B$ is Type $1$ . If $I_{j}\subset[0,p_{n_{r}})$ , then since $I_{i}\subset(p_{n_{r}-1},1]$ , by definition $B$ is Type $2$ .

Case 2: Denote $Q_{0}=Q$ . In the second case let

0<m\leq n_{r},

and define

Q_{0}\subset\{p_{m},p_{m+1},\ldots,p_{n_{r}}\}.

The following algorithm shows that $B$ is Type $1$ or Type $2$ . Let $I_{m_{0}}=I_{i}$ . Then it is clear that $I_{m_{0}}\subset(p_{m-1},1]$ . Recall that $B\cap\mathfrak{q}(r)=\emptyset$ . Then there exists $I^{\prime}_{m_{0}}$ , such that $I^{\prime}_{m_{0}}\subset[0,p_{m})$ or $I^{\prime}_{m_{0}}\subset(p_{m},1]$ . If $I^{\prime}_{m_{0}}\cap Q_{0}=\emptyset$ , then $B$ is Type $1$ . If $I^{\prime}_{m_{0}}\subset[0,p_{m})$ , then since $I_{m_{0}}\subset(p_{m-1},1]$ , $B$ is Type $2$ . If $I^{\prime}_{m_{0}}\subset(p_{m},1]$ , then denote $I_{m_{1}}:=I^{\prime}_{m_{0}}$ . Let

1<m\leq n_{r},

and define

Q_{1}=Q_{0}\cap I_{m_{1}}\subset\{p_{m},p_{m+1},\ldots,p_{n_{r}}\}.

If $I_{m_{1}}\cap P(r)=\{p_{n_{r}}\}$ , then appeal to Case 1. Since $B\cap\mathfrak{q}(r)=\emptyset$ there exists $I^{\prime}_{m_{1}}$ , such that $I^{\prime}_{m_{1}}\subset[0,p_{m})$ or $I^{\prime}_{m_{1}}\subset(p_{m},1]$ . If $I_{m_{1}}^{\prime}\cap Q_{1}=\emptyset$ , then $B$ is Type $1$ . If $I_{m_{1}}^{\prime}\subset[0,p_{m})$ , then since $I_{m_{1}}\subset(p_{m-1},1]$ $B$ is Type $2$ . If $I_{m_{1}}^{\prime}\cap P(r)=\{p_{n_{r}}\}$ , then appeal to Case $1$ . If $I^{\prime}_{m_{1}}\subset(p_{m},1]$ denote $I_{m_{2}}:=I^{\prime}_{m_{1}}\subset(p_{m},1]$ , and continue the algorithm. At step $\ell$ of the algorithm let

\ell<m\leq n_{r},

and define

Q_{\ell}=Q_{m_{\ell-1}}\cap I_{m_{\ell}}\subset\{p_{m},p_{m+1},\ldots,p_{n_{r}}\}.

If $Q_{\ell}=\emptyset$ , then $B$ is Type $1$ . Assume $Q_{\ell}\not=\emptyset$ . If $I_{m_{\ell}}\cap P(r)=\{p_{n_{r}}\}$ , then appeal to Case $1$ . If there exists an interval $I^{\prime}_{m_{\ell}}$ , such that $I^{\prime}_{m_{\ell}}\subset[0,p_{m})$ , then since $I_{m_{\ell}}\subset(p_{m-1},1]$ by definition $B$ is Type $2$ . The algorithm terminates after at most $n_{r}$ steps.

Case 3: In the last case $p_{0}\in Q$ . Since $B\cap\mathfrak{q}(r)=\emptyset$ there exists $I_{j}\subset[0,p_{0})$ or $I_{j}\subset(p_{0},1]$ . If $I_{j}\subset[0,p_{0})$ , then $B$ is Type $1$ . Finally, if $I_{j}\subset(p_{0},1]$ , then apply the results in Case $1$ and Case $2$ . This proves the lemma. ∎

Corollary 4.4.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . Then

N(r,d)\leq\alpha(r).

Proof.

Let $n\geq 1$ . Let $r\in(\frac{1}{4},\frac{1}{2}]$ be such that $r_{n}\leq r<r_{n-1}$ . Recall the configuration $\mathfrak{q}(r)$ defined as in (17). By Lemma 4.2, and Lemma 4.3 we get that

\mathrm{disp}(\mathfrak{q}(r))=r.

Since $|\mathfrak{q}(r)|=n_{r}+1=n$ , it follows that $N(r,d)\leq n$ . ∎

Corollary 4.4 gives an upper bound for the minimal dispersion.

4.2 Formula derivation

We derive a simple formula for the upper bound given in Corollary 4.4.

Corollary 4.5.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . Then

\alpha(r)=\left\lfloor{\frac{\pi}{\arccos{(\frac{1}{2\sqrt{r}})}}}\right\rfloor-3.

Proof.

Let $k>0$ . By Proposition 3.15 and the conclusion of Remark 3.17 it is clear that

\frac{\pi}{\arccos{(\frac{1}{2\sqrt{r_{k}}})}}-3=\alpha(r_{k})=k.

(19)

Notice that the function is strictly decreasing on $(\frac{1}{4},\frac{1}{2}]$ . Let $r\in(\frac{1}{4},\frac{1}{2}]$ , and let $k>0$ be such that $r_{k}\leq r<r_{k-1}$ . By Proposition 3.7 and (19) it follows that

\alpha(r)=k=\left\lfloor{\frac{\pi}{\arccos{(\frac{1}{2\sqrt{r}})}}}\right\rfloor-3.

∎

Theorem 4.6.

Let $r\in(\frac{1}{4},\frac{1}{2})$ . Then

N(r,d)\leq\left\lfloor\frac{\pi}{\sqrt{r-\frac{1}{4}}}\right\rfloor-3.

Proof.

Let $r\in(\frac{1}{4},\frac{1}{2})$ . Then

{\arccos\big{(}\frac{1}{2\sqrt{r}}\big{)}}\geq{\sqrt{r-\frac{1}{4}}}.

This combined with Corollary 4.4 and Corollary 4.5 gives

N(r,d)\leq\left\lfloor\frac{\pi}{{\arccos\big{(}\frac{1}{2\sqrt{r}}\big{)}}}\right\rfloor-3\leq\left\lfloor\frac{\pi}{\sqrt{r-\frac{1}{4}}}\right\rfloor-3.

This proves the theorem. ∎

5 Sharp estimates

We prove some results about our configurations on the diagonal and diagonal analogues in the cube.

5.1 The diagonal

Proposition 5.1.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ , and let $T\subset[0,1]^{d}$ be on the diagonal such that

\mathrm{disp}(T)=r.

Then

|T|\geq n_{r}+1.

Proof.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . Let $T\subset[0,1]^{d}$ be on the diagonal such that

\mathrm{disp}(T)=r.

Let $n_{r}$ be as in (11), and let $\mathfrak{q}(r)$ be the configuration as defined in (17). Let $P(r)$ be as defined in (18). Let

E=\{e_{i}\in[0,1]:e_{1}<e_{2}<\cdots<e_{m},\ m=|T|\}

such that

T=\{e_{i}\textbf{1}:e_{i}\in E\}.

Assume toward a contradiction that $|T|\leq n_{r}$ . Partition $[0,1]$ into $n_{r}+2$ intervals

[0,p_{0}],(p_{0},p_{1}],(p_{1},p_{2}],\ldots,(p_{n_{r}-1},p_{n_{r}}],(p_{n_{r}},1].

(20)

Since $|T|\leq n_{r}$ , there exist at least two intervals which do not intersect $E$ . Assume $E\cap[0,p_{0}]=\emptyset$ . Then $p_{0}<e_{1}$ . Construct the box

B=[0,e_{1})\times[0,1]^{d-1}.

Then $B\cap T=\emptyset$ . However, Vol $(B)=e_{1}>p_{0}=r$ which contradicts the assumption that disp $(T)=r$ .

Now assume

E\cap[0,p_{0}]\not=\emptyset.

Then $e_{1}\leq p_{0}$ . Remove $[0,p_{0}]$ from the partition in (20). Then two intervals in the partition

(p_{0},p_{1}],(p_{1},p_{2}],\ldots,(p_{n_{r}-1},p_{n_{r}}],(p_{n_{r}},1]

must not intersect $E$ . If there exists $i<n_{r}$ such that $e_{m}<p_{i+1}$ , then construct the box

B=[0,1]\times[p_{i},1]\times[0,1]^{d-2}.

It follows that $B\cap E=\emptyset$ , however,

\mathrm{Vol}(B)=(1-p_{i})>p_{i+1}(1-p_{i})=r.

This contradicts the assumption that disp $(T)=r$ . Let $i<n_{r}$ be the smallest integer such that

E\cap(p_{i},p_{i+1}]=\emptyset.

Assume $0<k\leq m$ is the smallest integer such that $p_{i+1}<e_{k}$ . Construct the box

B=[0,e_{k})\times[p_{i},1]\times[0,1]^{d-2}.

Since $T$ is on the diagonal $B\cap E=\emptyset$ , however,

\mathrm{Vol}(B)=e_{k}(1-p_{i})>p_{i+1}(1-p_{i})=r.

This contradicts the assumption that disp $(T)=r$ .

The proposition follows. ∎

Proposition 5.2.

Let $i>0$ . Let $r_{i}$ be as defined in (15). The configuration given by $\mathfrak{q}(r_{i})$ in (17) are symmetric on the diagonal. That is, if $0\leq j\leq i-1$ , then

1-f_{j}(r_{i})=f_{(i-1)-j}(r_{i}).

Proof.

Let $i>0$ . Let $r_{i}$ be as defined in (15). Employ an inductive argument on $j$ . Let $j=0$ . Then by Proposition 3.2 it follows that

1-f_{0}(r_{i})=1-r_{i}=f_{i-1}(r_{i}).

Let $j=1$ . Then by definition of the functions, and by Proposition 3.2

f_{i-1}(r_{i})(1-f_{i-2}(r_{i}))=\frac{r_{i}}{(1-f_{i-2}(r_{i}))}(1-f_{i-2}(r_{i}))=r_{i}.

By Proposition 3.2, $f_{i-1}(r_{i})=1-r_{i}$ . It follows that

(1-r_{i})(1-f_{i-2}(r_{i}))=r_{i}.

Then

1-f_{i-2}(r_{i})=\frac{r_{i}}{1-r_{i}}=f_{1}(r_{i}),

in particular

1-f_{1}(r_{i})=f_{i-2}(r_{i})=f_{(i-1)-1}(r_{i}).

Fix $0\leq j<i-1$ , and assume the induction hypothesis, for all $0\leq k\leq j$ . Namely that

1-f_{k}(r_{i})=f_{(i-1)-k}(r_{i}).

We show that

1-f_{j+1}(r_{i})=f_{(i-1)-({j+1})}(r_{i}).

By the induction hypothesis

1-f_{j}(r_{i})=f_{(i-1)-j}(r_{i}).

By construction of the functions, we have that

f_{(i-1)-{j}}(r_{i})(1-f_{(i-1)-j-1}(r_{i}))=\frac{r_{i}}{(1-f_{(i-1)-j-1}(r_{i}))}(1-f_{(i-1)-j-1}(r_{i}))=r_{i}.

Therefore,

1-f_{(i-1)-j-1}(r_{i})=\frac{r_{i}}{(1-f_{j}(r_{i}))}=f_{j+1}(r_{1}).

It follows that

1-f_{j+1}(r_{1})=f_{(i-1)-(j+1)}(r_{i}).

The proposition follows. ∎

5.2 Extended diagonal

Definition 5.3.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ , and $d>1$ . Let $P(r)$ be given by (18), and denoted as $P(r)=\{p_{i}:p_{i}=f_{i}(r),0\leq i\leq n_{r}\}$ . Define the Extended Diagonal as

\mathfrak{D}(r,d)=[0,p_{0}]^{d}\cup(p_{0},p_{1}]^{d}\cup\cdots\cup(p_{n_{r}},1]^{d}.

Definition 5.4.

Let $d>1$ . Let $x=(x_{1},x_{2},\ldots,x_{d})\in[0,1]^{d}$ . Define

s(x)=\min\{x_{i}:1\leq i\leq d\}.

Proposition 5.5.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ , and $d>1$ . Let $A\subset\mathfrak{D}(r,d)$ be such that

\mathrm{disp}(A)=r.

Then

|A|\geq n_{r}+1.

Proof.

Assume that the hypothesis holds. Let $n_{r}$ be as in (11), and let $\mathfrak{q}(r)$ be the configuration as in (17). Define

C_{0}=[0,p_{0}]^{d},\ C_{n_{r}+1}=(p_{n_{r}},1]^{d}.

For $0<i\leq n_{r}$ define

C_{i}=(p_{i-1},p_{i}]^{d}.

Assume toward a contradiction that $|A|\leq n_{r}$ . The $n_{r}$ points contained in $A$ must lie in the $n_{r}+2$ disjoint sets in $\{C_{i}:0\leq i\leq n_{r}+1\}$ composing $\mathfrak{D}(r,d)$ . There exist at least two integers $i\leq n_{r}$ , such that $A\cap C_{i}=\emptyset$ .

First assume that $A\cap C_{0}=\emptyset$ . Since $A\subset\mathfrak{D}$ , it follows that $s(p)>p_{0}$ for each $p\in A$ . Let

t=\min\{s(p):p\in A\}.

Construct the box $B=[0,t)\times[0,1]^{d-1}$ . The magnitude of the components of each $p\in A$ is bounded below by $t$ . It follows that $A\cap B=\emptyset$ , however, Vol $(B)=t>p_{0}=r$ . This contradicts the assumption that $\mathrm{disp}(A)=r$ .

Now assume that $A\cap C_{0}\not=\emptyset$ . Let $1\leq i\leq n_{r}$ be the smallest number such that $A\cap C_{i}=\emptyset.$ Assume that for all $j>i$ , $A\cap C_{j}=\emptyset$ . Then set $t=1.$ Construct a box

B=[0,t]\times(p_{i-1},1]\times[0,1]^{d-2}.

Since $A\subset\mathfrak{D}$ , it follows that $B\cap A=\emptyset$ , however,

\textrm{Vol}(B)=(1-p_{i-1})>p_{i}(1-p_{i-1})=r.

This contradicts the assumption that $\mathrm{disp}(A)=r$ . Assume that $A\cap C_{j}\not=\emptyset$ for some smallest $j>i$ . Then set

t=\min\{s(p):p\in A\cap C_{j}\}.

Construct a box

B=[0,t)\times(p_{i-1},1]\times[0,1]^{d-2}.

Since $A\subset\mathfrak{D}$ , it follows that $A\cap B=\emptyset$ , however,

\textrm{Vol}(B)=t(1-p_{i-1})>p_{i}(1-p_{i-1})=r.

This contradicts the assumption that $\mathrm{disp}(A)=r$ . It follows that

n_{r}+1\leq|A|.

∎

Remark 5.6.

The condition $d>1$ in Proposition 5.5 is required. Let $r=\frac{1}{3}$ and $d=1$ . Note $\mathfrak{q}(r)=\{\frac{1}{3},\frac{1}{2},\frac{2}{3}\}$ . Define

U_{0}=[0,r],U_{1}=(r,f(r)],U_{2}=(f(r),1-r],U_{3}=(1-r,1].

Then by definition

\mathfrak{D}(r,1)=U_{0}\cup U_{1}\cup U_{2}\cup U_{3}.

Let $A\subset\mathfrak{D}(r,1)$ be the set $\{\frac{1}{3},\frac{2}{3}\}$ . Then

\mathrm{disp}(A)=\frac{1}{3}.

Since $|A|=2,$ and

n_{r}+1=|\mathfrak{q}(r)|=3

the proposition fails. This example shows that Proposition 5.5 only holds when $d>1$ .

Proposition 5.7.

Let $d\geq 2$ . Let $r_{n}$ be as in (15) and let $\mathfrak{q}(r_{n})$ be as in (17). Let $A\subset\mathfrak{D}(r_{n},d)$ , be such that $|A|=n$ , and

\mathrm{disp}(A)=r_{n}.

(21)

Then

A=\mathfrak{q}(r_{n}).

Proof.

Assume the hypothesis. Note $A\not=\emptyset$ . For all $0\leq i\leq n$ define $C_{i}$ to be as in the proof of Proposition 5.5. Assume that for all $0\leq i\leq n$ , $A\cap C_{i}\not=\emptyset$ . Then it follows that for all $0\leq i\leq n-1$ , $A\cap C_{i}=\{p_{i}\mathbf{1}\}$ . Hence, $A=\mathfrak{q}(r_{n})$ . We state here that for all $0\leq i\leq n-1$ , $A\cap C_{i}\not=\emptyset$ . This follows directly from the proof of Proposition 5.5: thus we shall omit the details to avoid repetition. Then for all $0\leq i\leq n-1$ , $|A\cap C_{i}|=1$ . Now apply induction on $i$ to show that for all $1\leq i\leq n$ , $A\cap C_{n-i}=\{p_{n-i}\mathbf{1}\}$ .

Let $i=1$ . Assume toward a contradiction that

A\cap C_{n-1}\not=\{p_{n-1}\mathbf{1}\}.

Let $p\in A\cap C_{n-1}\setminus\{p_{n-1}\mathbf{1}\}$ . There exists a maximum component of $p$ which is less than $p_{n-1}$ . Without loss of generality, assume that this is the first component. Denote the magnitude of this component as $b(p)<p_{n-1}$ . Construct the box

B=(b(p),1]\times[0,1]^{d-1}.

Since $A\subset\mathfrak{D}$ , it follows that $A\cap B=\emptyset$ . However,

\mathrm{Vol}(B)=1-b(p)>1-p_{n-1}=r_{n}.

This contradicts (21). Therefore, $A\cap C_{n-1}=\{p_{n-1}\mathbf{1}\}$ .

Fix $0<m\leq n-1$ . As an induction hypothesis assume that for all $m\leq k\leq n-1$ , $A\cap C_{k}=\{p_{k}\mathbf{1}\}$ . Assume toward a contradiction that $A\cap C_{m-1}\not=\{p_{m-1}\mathbf{1}\}$ . Let $p\in A\cap C_{m-1}\setminus\{p_{m-1}\mathbf{1}\}$ . There exists a maximum component of $p$ which is less than $p_{m-1}$ . Without loss of generality, assume that this is the first component. Denote the magnitude of this component as $b(p)<p_{m-1}$ . Construct the box

B=(b(p),1]\times[0,p_{m})\times[0,1]^{d-1}.

Since $A\subset\mathfrak{D}$ , it follows that $A\cap B=\emptyset$ . Then

\mathrm{Vol}(B)=p_{m}(1-b(p))>p_{m}(1-p_{m-1})=r_{n}.

This contradicts (21). Therefore, it follows that $A\cap C_{m-1}=\{p_{m-1}\mathbf{1}\}$ . Hence, for all $0\leq k\leq n-1$ , $A\cap C_{k}=\{p_{k}\mathbf{1}\}$ . It follows that $A=\mathfrak{q}(r_{n})$ . ∎

Now we show that the bound in Corollary 4.5 is sharp, given that $d$ is large enough. Recall that for each $r\in(\frac{1}{4},\frac{1}{2}]$ , there exists $n>0$ such that $r_{n}\leq r<r_{n-1}$ , and

n_{r}+1=\alpha(r)=n.

Theorem 5.8.

Let $r\in(\frac{1}{4},\frac{1}{2}]$ . Then

N(r,d)=n_{r}+1,

given that $d\geq{n}^{n-1}+1$ , where $n=\alpha(r)$ .

Proof.

Let $r=\frac{1}{2}=r_{1}$ , then for all $d\geq 2$ ,

N(r,d)=1=n_{r_{1}}+1.

Let $r\in(\frac{1}{4},\frac{1}{2})$ be such that $r_{2}\leq r<r_{1}$ . Let $d\geq 3$ . Define $U_{0}=[0,r_{1}]$ , $U_{1}=(r_{1},1]$ , and denote ${[0,1]}^{d}=(U_{0}\cup U_{1})^{d}$ . Assume toward a contradiction that there exists $q_{1}\in[0,1]^{d}$ such that

\mathrm{disp}(\{q_{1}\})=r.

Then either $q_{1}\in[0,1]^{d-1}\times U_{0}$ or $q_{1}\not\in[0,1]^{d-1}\times U_{0}$ . Assume $q_{1}\in[0,1]^{d-1}\times U_{0}$ . Construct the box $B=[0,1]^{d-1}\times U_{1}$ . Then $q_{1}\not\in B$ , and

\mathrm{Vol}(B)=r_{1}=\frac{1}{2}>r.

This contradicts the assumption that $\mathrm{disp}(\{q_{1}\})=r.$ Assume $q_{1}\not\in[0,1]^{d-1}\times U_{0}$ . Construct the box $B=[0,1]^{d-1}\times U_{0}$ . Then $q_{1}\not\in B$ , however,

\mathrm{Vol}(B)=r_{1}>r.

This contradicts the assumption that $\mathrm{disp}(\{q_{1}\})=r.$ Then $1<N(r,d),$ and by Corollary 4.4, $N(r,d)\leq 2.$ It follows that

N(r,d)=2.

Let $r$ be such that $r_{3}\leq r<r_{2}$ . Since $\alpha(r)=3$ , $d\geq 10$ . Define $U_{0}=[0,r_{2}]$ , $U_{1}=(r_{2},1-r_{2}]$ , $U_{2}=(1-r_{2},1]$ . Select two points $q_{1},q_{2}\in[0,1]^{d}$ . Assume toward a contradiction that $\mathrm{disp}(\{q_{1},q_{2}\})=r$ . The components of $q_{1}$ and $q_{2}$ are contained in the intervals $U_{0},U_{1},U_{2}$ . Denote the components of $q_{1},q_{2}$ as $\{q_{1,i}\}_{1\leq i\leq d}$ , $\{q_{2,i}\}_{1\leq i\leq d}$ . Let $M_{1}\geq 4$ denote the largest number of components of $\{q_{1,i}\}_{1\leq i\leq d}$ contained in a single interval, denoted as $U_{m_{1}}$ . Denote the corresponding indices as $\{a_{i}\}_{1\leq i\leq{M_{1}}}:=\{a_{i}:a_{1}<a_{2}<\cdots~{}<~{}a_{M_{1}}~{}\}.$ Let $M_{2}\geq 2$ denote the largest number of components of $\{q_{2,a_{i}}\}_{1\leq i\leq{M_{1}}}$ contained in a single interval, denoted as $U_{m_{2}}$ . Denote the corresponding indices as $\{b_{i}:1\leq i\leq M_{2}\}\subset\{a_{i}\}_{1\leq i\leq M_{1}}$ . It follows that

q_{1,b_{1}},q_{1,b_{2}}\in U_{m_{1}},

q_{2,b_{1}},q_{2,b_{2}}\in U_{m_{2}}.

Project onto the components,

q_{1}\to(0,0,\ldots,0,q_{1,b_{1}},0,0,\ldots,0,q_{1,b_{2}},0,0,\ldots,0)=q_{1}^{\prime},

and

q_{2}\to(0,0,\ldots,0,q_{2,b_{1}},0,0,\ldots,0,q_{2,b_{2}},0,0,\ldots,0)=q_{2}^{\prime}.

The points are projected onto a $2$ -dimensional face of $[0,1]^{d}$ , given by

\{0\}^{b_{1}-1}\times[0,1]\times\{0\}^{b_{2}-(1+b_{1})}\times[0,1]\times\{0\}^{d-b_{2}}.

Note that

q_{1}^{\prime}\in\{0\}^{b_{1}-1}\times U_{m_{1}}\times\{0\}^{b_{2}-(1+b_{1})}\times U_{m_{1}}\times\{0\}^{d-b_{2}},

and

q_{2}^{\prime}\in\{0\}^{b_{1}-1}\times U_{m_{2}}\times\{0\}^{b_{2}-(1+b_{1})}\times U_{m_{2}}\times\{0\}^{d-b_{2}}.

The components $q_{1}^{\prime},q_{2}^{\prime}$ are contained in $\mathfrak{D}(r_{2},2)$ . By Proposition 5.7 there exists $B^{\prime}\in\mathfrak{B}$ such that

B^{\prime}=\{0\}^{b_{1}-1}\times I_{1}\times\{0\}^{b_{2}-(1+b_{1})}\times I_{2}\times\{0\}^{d-b_{2}},

where $q_{1}^{\prime},q_{2}^{\prime}\not\in B^{\prime}$ . However, $\mathrm{Vol}(I_{1}\times I_{2})\geq r_{2}$ . Let

B=[0,1]^{b_{1}-1}\times I_{1}\times[0,1]^{b_{2}-(1+b_{1})}\times I_{2}\times[0,1]^{d-b_{2}}.

It is clear that $q_{1},q_{2}\not\in B$ . However, $\mathrm{Vol}(B)\geq r_{2}>r$ . This contradicts the assumption that $\mathrm{disp}(\{q_{1},q_{2}\})=r$ . Then $N(r,d)>2$ , and by Corollary 4.4, $N(r,d)\leq 3.$ It follows that

N(r,d)=3.

Fix $n>3$ , and let $r_{n+1}\leq r<r_{n}$ . Since $\alpha(r)=n+1$ ,

d\geq{({n}+1)}^{{n}}+1.

Let $q_{1},q_{2},\ldots,q_{n}$ be arbitrary points in the cube. Assume toward a contradiction that $\mathrm{disp(\{q_{1},q_{2},\ldots,q_{n}\})}=r.$ Define the partition

U_{0}=[0,r_{n}],U_{1}=(r_{n},f_{1}(r_{n})],\ldots,U_{n+1}=(1-r_{n},1].

For all $1\leq i\leq n$ , denote the components of $q_{i}$ as $(q_{i,1},q_{i,2},\ldots,q_{i,d})$ . Denote $d_{1}:={({n}+1)}^{{n}}+1$ . Let

M_{1}\geq d_{2}:=\frac{d_{1}-1}{({n}+1)}+1

denote the largest number of components of $\{q_{1,i}\}_{0<i\leq d}$ which are contained in a single interval, denoted as $U_{m_{1}}$ . Denote the corresponding indices as

\{a_{1,i}\}_{1\leq i\leq M_{1}}.

Let

M_{2}\geq d_{3}:=\frac{d_{2}-1}{({n}+1)}+1

denote the largest number of components of $\{q_{2,a_{1,i}}\}_{1\leq i\leq M_{1}}$ which are contained in a single interval, denoted as $U_{m_{2}}$ . Denote the corresponding indices as $\{a_{2,i}\}_{1\leq i\leq M_{2}}$ .

For all $1\leq k\leq{n}$ let

M_{k}\geq d_{k+1}:=\frac{d_{k}-1}{({n}+1)}+1

denote the largest number of components of $\{q_{k,a_{{k-1},i}}\}_{1\leq i\leq M_{k-1}}$ which are contained in $U_{m_{k}}$ . Denote the corresponding indices as $\{a_{k,i}\}_{1\leq i\leq M_{k}}$ . This guarantees that $M_{n}\geq 2$ . Define a projection on $1\leq j\leq n$ , such that

q_{j}\to q_{j,a_{n,1}},q_{j,a_{n,2}}\in U_{m_{j}}.

This embeds into $\mathfrak{D}(r_{n},2)$ . Then by Proposition 5.7, there exists a box $B^{\prime}$ such that $q_{j}^{\prime}\not\in B^{\prime}$ with $I_{1},I_{2}$ , such that

\mathrm{Vol}(I_{1}\times I_{2})\geq r_{n}.

This can be extended to a box

B=[0,1]^{a_{n,1}-1}\times I_{1}\times[0,1]^{a_{n,2}-(1+a_{n,1})}\times I_{2}\times[0,1]^{d_{1}-a_{n,2}}.

It is clear that $q_{1},q_{2},\ldots,q_{n}\not\in B$ and that $\mathrm{Vol}(B)\geq r_{n}>r$ . This contradicts the assumption that $\mathrm{disp}(\{q_{1},q_{2},\ldots,q_{n}\})=r$ . Then $n<N(r,d)$ , and by Corollary 4.4, $N(r,d)\leq n+1.$ It follows that

N(r,d)=n+1.

∎

6 Concluding remarks

When $r=\frac{1}{4}$ , and $d$ is small the following configurations are better than the best known bound which asymptotically is $\log(d)$ . We present a configuration which is easy to describe and visualize.

Proposition 6.1.

Let $r\geq\frac{1}{4}$ . Then $N(r,d)\leq 2d$ .

Proof.

Let $d=2$ let

K=\big{\{}(\frac{1}{2},\frac{1}{4}),(\frac{1}{2},\frac{3}{4}),(\frac{1}{4},\frac{1}{2}),(\frac{3}{4},\frac{1}{2})\big{\}}.

Every box $B\cap K=\emptyset$ inside $[0,1]^{2}$ is contained in one of the following

\begin{matrix}[0,\frac{1}{2})\times[0,\frac{1}{2}),&[0,\frac{1}{2})\times(\frac{1}{2},1],&(\frac{1}{2},1]\times[0,\frac{1}{2}),&(\frac{1}{2},1]\times(\frac{1}{2},1]\\ (\frac{1}{4},\frac{3}{4})\times(\frac{1}{4},\frac{3}{4}),&[0,\frac{1}{4})\times[0,1],&(\frac{3}{4},1]\times[0,1],&[0,1]\times(\frac{3}{4},1]\\ [0,1]\times[0,\frac{1}{4})&(\frac{1}{4},\frac{1}{2})\times[0,1]&[0,1]\times(\frac{1}{4},\frac{1}{2})&(\frac{1}{2},\frac{3}{4})\times[0,1]\\ [0,1]\times(\frac{1}{2},\frac{3}{4})\par\end{matrix}

(22)

This gives the result in the $2$ dimensional case. Let $d>2$ . Let

K_{1}=\bigg{\{}\bigg{(}\frac{1}{2},\frac{1}{2},\ldots,\frac{1}{2},M_{i},\frac{1}{2},\ldots,\frac{1}{2}\bigg{)}:M_{i}=\frac{1}{4},\ 1\leq i\leq d\bigg{\}}

K_{2}=\bigg{\{}\bigg{(}\frac{1}{2},\frac{1}{2},\ldots,\frac{1}{2},M_{i},\frac{1}{2},\ldots,\frac{1}{2}\bigg{)}:M_{i}=\frac{3}{4},\ 1\leq i\leq d\bigg{\}}.

Let $K=K_{1}\cup K_{2}$ . Then each box in $B\in[0,1]^{d}$ such that $B\cap K=\emptyset$ is contained in a product of $d-2$ intervals $[0,1]$ with one of the boxes in (22). Each of the boxes have volume $\frac{1}{4}$ . Therefore,

\mathrm{disp}(K)=\frac{1}{4},

and $|K|=2d.$ ∎

6.1 Acknowledgments

The author would like to thank his supervisor A.E. Litvak for introducing him to the dispersion problem, for his valuable expertise, and helpful comments while the author was working on this note. The author would also like to thank the reviewers for their comments and suggestions.

References

[1] C. Aistleitner, A. Hinrichs, D. Rudolf, On the size of the largest empty box amidst a point set, Discrete Appl. Math. 230 (2017), 146-150.
[2] A. Blumer, A. Ehrenfeucht, D. Haussler, M. Warmuth, Learnability and the Vapnik–Chervonenkis dimension, J. Assoc. Comput. Mach. 36 (1989), 929-965.
[3] S. Breneis, A. Hinrichs Fibonacci lattices have minimal dispersion on the two-dimensional torus preprint, (2019), arXiv:1905.03856
[4] L. Brand, A Sequence Defined by a Difference Equation, The American Mathematical Monthly. 62 (7) (1955), pp. 489-492.
[5] A. Dumitrescu, M. Jiang, On the largest empty axis-parallel box amidst n points, Algorithmica. 66 (2013), 225-248.
[6] E. Hlawka, Abschatzung von trigonometrischen Summen mittels diophantischer Approximationen, Osterreich. Akad. Wiss. Math.- Naturwiss. Kl. S.-B. II, 185 (1976), 43–50.
[7] A. Hinrichs, D. Krieg, R.J. Kunsch, D. Rudolf, Expected dispersion of uniformly distributed points, J. Complexity, to appear.
[8] A. Hinrichs, J. Prochno, M. Ullrich, J. Vybìral, The minimal k-dispersion of point sets in high dimensions, J. Complexity 53 (2019), 68-78.
[9] D. Krieg, On the dispersion of sparse grids, J. Complexity 45 (2018), 115–119.
[10] D. Krieg, D. Rudolf, Recovery algorithms for high-dimensional rank one tensors, Journal of Approximation Theory 237 (2019): 17-29.
[11] A.E. Litvak, A remark on the minimal dispersion, Communications in Contemporary Mathematics, to appear.
[12] A.E. Litvak, G. V. Livshyts, New bounds on the minimal dispersion, J. Complexity, to appear.
[13] E. Novak, D. Rudolf, Tractability of the approximation of high- dimensional rank one tensors Constructive Approximation 43.1 (2016): 1-13.
[14] J. Prochno, D. Rudolph, The minimal spherical dispersion preprint, (2021), arXiv:2103.11701
[15] G. Rote, R.F. Tichy, Quasi-Monte Carlo methods and the dispersion of point sequences, Math. Comput. Modelling. 23 (1996), 9–23.
[16] D. Rudolf, An upper bound of the minimal dispersion via delta covers, Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan, Springer-Verlag. (2018), 1099-1108.
[17] J. Sosnovec, A note on the minimal dispersion of point sets in the unit cube, European J. of Comb. 69 (2018), 255–259.
[18] V.N. Temlyakov, Dispersion of the Fibonacci and the Frolov point sets, preprint, (2017), arXiv:1709.08158.
[19] M. Ullrich, A lower bound for the dispersion on the torus, Mathematics and Computers in Simulation, 143 (2018), 186–190.
[20] M. Ullrich, A note on the dispersion of admissible lattices, Discrete Appl.Math, 257 (2019), 385–387.
[21] M. Ullrich, J. Vybìral, An upper bound on the minimal dispersion, Jour- nal of Complexity. 45 (2018), 120–126.
[22] M. Ullrich, J. Vybìral, Deterministic constructions of high-dimensional sets with small dispersion, Preprint, (2019), arXiv:1901.06702

Kurt S. MacKay
Dept. of Math. and Stat. Sciences,
University of Alberta,
Edmonton, AB, Canada, T6G 2G1.
e-mail: [email protected]