Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy (Q6540045)

Let \(\mathcal{F} \subseteq (F, \| \cdot \|)\), where \((F, \| \cdot \|)\) is a normed space of real-valued functions. For \(\ell, u \in F\), the bracket \([\ell,u]\) is defined as \([\ell, u]:= \{f\in\mathcal{F}\colon \ell \le f\le u\}\). Such a bracket is an \(\varepsilon\)-bracket, if \(\| u - \ell \|\le \varepsilon\). The bracketing number \(N_{[]}(\varepsilon, \mathcal{F}, \|\cdot\|)\) is the minimum number of \(\varepsilon\)-brackets to cover \(\mathcal{F}\), i.e., \(\mathcal{F}\) is contained in the union of the \(\varepsilon\)-brackets.\N\NThe paper studies a special case of this general setting, namely when \((F, \| \cdot \|)\) is the space \(L^1 ([0,1)^d, \lambda^d)\) of \(\lambda^d\)-integrable real-valued functions on \([0,1)^d\), where \(\lambda^d\) is the \(d\)-dimensional Lebesgue measure, and when \(\mathcal{F}\) is the set of characteristic functions of half-open, axes-parallel boxes in \([0,1)^d\). For \(\boldsymbol{x}, \boldsymbol{y} \in [0,1)^d\), write \([\boldsymbol{x},\boldsymbol{y}):=[x_1,y_1)\times \cdots \times [x_d,y_d)\), where the \(x_j\) and \(y_j\), \(1\le j \le d\), are the components of \(\boldsymbol{x}\) and \(\boldsymbol{y}\), respectively. Moreover, let\N\[\N\mathcal{C}_d:=\{[\boldsymbol{0},\boldsymbol{x})\colon \boldsymbol{x}\in [0,1)^d\}.\N\]\NWith \(\mathcal{C}_d\), we identify the set of characteristic functions \(1_C\) for all \(C\in \mathcal{C}_d\). In a paper from 2001, Thiémard provided a special \(\varepsilon\)-bracketing cover \(\mathcal{P}_\varepsilon^d\) of \(\mathcal{C}_d\), which he used for obtaining an algorithm to effectively compute bounds on the star discrepancy of points in \([0,1)^d\). For \(d\ge 3\), a slightly simplified bound on the cardinality of \(\mathcal{P}_\varepsilon^d\) is\N\[\N| \mathcal{P}_\varepsilon^d | \le \frac{d^d}{d!} \left(\frac{\ln (\varepsilon^{-1})}{\varepsilon} +1\right)^d.\N\]\NThe author of the present paper improves Thiémard's bound to\N\[\N| \mathcal{P}_\varepsilon^d | \le \frac{d^d}{d!} \frac{1}{\varepsilon^d},\N\]\Nand gives further, related, remarks and improvements.