Improved dispersion bounds for modified Fibonacci lattices (Q1996888)

Consider point sets \(\mathcal P\) in the unit square \([0,1]^2\) consisting of \(N\) not necessarily distinct elements and let \(\mathcal B\) be the set of all axes-parallel boxes in the unit square. The authors study dispersion of \(\mathcal P\) defined as \( \text{disp }(\mathcal P):=\sup_{B\in\mathcal B, B\cap\mathcal P=\emptyset}\lambda(B) \), where \(\lambda(B)\) denotes the area of the box \(B\). Known previous results: \textit{A. Dumitrescu} and \textit{M. Jiang} [Algorithmica 66, No. 2, 225--248 (2013; Zbl 1262.68186)] proved that \( \text{disp }(\mathcal P)\ge\max(1/(N+1),5/(4(N+5))). \) \textit{S. Breneis} and \textit{A. Hinrichs} [Radon Ser. Comput. Appl. Math. 26, 117--132 (2020; Zbl 1471.11050)] constructed points with small dispersion using the Fibonacci numbers \(F_m\). The dispersion of the Fibonacci lattice \( \mathcal F_m=\{(k/F_m,\{kF_{m-2}/F_m\}):k=0,1,2,\dots,F_m-1\} \) is given by \( \text{disp }\mathcal F_m=(2(F_m-1)/F^2_m) \) for \(m\ge8\), where \(\{x\}\) denotes the fractional part of \(x\). Then the limit \(\lim_{m\to\infty}|\mathcal F_m|\text{disp }(\mathcal F_m)=2\). The central result of this paper is replacing the limit 2 by a smaller constant 1.894427\dots for the modified Fibonacci lattice \(\widetilde{\mathcal F}_m\) defined in the following way: \par \(\pi(k)=kF_{m-2}\pmod {F_m}\), \par \(s(i)=(\sqrt{5}+1)/2 \text{ if } \pi(i)<\pi(i+1) \text{ and } 1 \text{ otherwise }\), \par \(L=\sum_{i=0}^{F_m-1}s(i)\), \par \(x_k=\sum_{i=0}^{k-1}, k=0,1,\dots,F_m-1\), \par \(\widetilde{\mathcal F}_m=\{(x_k/L,x_{\pi(k)}/L),k=0,1,\dots,F_m-1\}\). \par\noindent In this case, the authors prove \par \(\lim_{m\to\infty}|\widetilde{\mathcal F}_m|\text{disp }(\widetilde{\mathcal F}_m) =1+\frac{2}{\sqrt{5}}\). For proof they use, e.g., \(F^2_{m-2}+F^2_m-3F_mF_{m-2}=(-1)^m\). Using the theory of uniform distribution of sequences it is also conjectured that the Fibonacci lattice \(\mathcal F_m\) have a smallest possible \(L_2\) discrepancy, since for \(m\le 7\) this is known. Note that in uniform distribution theory the \(s\)-dimensional dispersion is defined as follows: If \(\mathbf x_1,\mathbf x_2,\dots,\mathbf x_N\) belong to \([0,1]^s\) then the dispersion \(d_N\) of \(\mathbf x_n\) is defined by \(d_N(\mathbf x_1,\dots,\mathbf x_N)=\sup_{\mathbf x\in[0,1]^s} \min_{1\le n\le N}|\mathbf x-\mathbf x_n|\), where \(|\mathbf x-\mathbf x_n|\) is the Euclidean distance. Basic results of such dispersion are in [\textit{H. Niederreiter}, Random number generation and quasi-Monte Carlo methods. Philadelphia, PA: SIAM (1992; Zbl 0761.65002)].