Low-discrepancy quasi-uniform digital nets in every dimension: blueprint

14 Open problems

(I) Bounded layers. (1) Growth of the deficit. Let \(K(s)\) be the best first-order deficit \(K\) in \(\delta N^{1/s}=1-K/q+O(q^{-2})\), \(q\to \infty \), over families of digital \((0,sk,s)\)-nets over \(\mathbb {Z}/q\mathbb {Z}\) whose geometric layers have entries bounded independently of \(q\) and no zero diagonal entry. Lower bounds: \(K(s)\ge \sqrt{(s-3)/8}\) (Theorem 89). For designs on the places \(\infty ,0,\dots ,s-2\): \(K(F)\ge s^{1-o(1)}\) (Theorem 94); if moreover the row scalars \(\lambda '_c\) (Proposition 18) take one value on the finite places, \(K(F)\ge \operatorname {lcm}(1,\dots ,s-3)\) (Proposition 92); and the two-axis bound \(K_{\mathrm{pair}}\) is at least \(2\) for \(s\ge 5\) (Theorem 90). Upper bounds: the constructions here achieve \(1\) for \(s=3\), \(2\) for \(s=4\) (Proposition 83), \(5\) and \(10\) for \(s=5,6\) (Table tab:Kdesigns), and a certified deficit at most \(a^*_s\le e^{s\log s+O(s)}\) for every \(s\ge 4\) (Theorem A). Does \(K(s)\) grow polynomially or exponentially? On these places a certified deficit polynomial in \(s\) would need row scalars that differ between the finite places (Proposition 92). Also open: \(K=1\) for \(s=4\); whether layers with zero diagonal do better (Remark 82); and the optimal second-order constant \(C\) in \(\delta N^{1/3}=1-1/p+C/p^2+o(p^{-2})\) in dimension three. For nets with the layer of \(\mathcal P_{k,p}\) it is at most \(4\) for \(k\ge 4\) (after Corollary 80); for other bounded layers Proposition 79(i) bounds it by \(\frac12\bigl((|\tilde M_{ba}|+1)^2+(|\tilde M_{b'a}|+1)^2\bigr)\) for a coordinate \(a\) with \(\tilde M_{aa}=-1\), and for zero diagonals (Remark 82) we have no bound. (2) Small bases. Theorem A needs \(q\ge 5a^*_s+4\), and the designs of Table tab:Kdesigns certify smaller bases only by finite scans; for \(s=4\) the bases \(q\le 15\) have only weaker proved constants, and for \(s\ge 4\) Theorem A excludes even \(q\) (it needs \(\operatorname {lpf}(q)\ge s-1\); for \(q=2\) no \((0,m,s)\)-net with \(s\ge 4\) exists, as \(s\le q+1\)). In dimension three the bases \(2\) and \(3\) are covered for every \(m\) (Theorem 66, computer-assisted); at \(m=3\) the column nets cover every base coprime to \(6\) (Theorem 51), column nets do not exist in even bases (Theorem 97), and the other bases \(q\ge 4\) divisible by \(2\) or \(3\) are open at \(m=3\).

(II) Lattice skeletons. (3) For \(s\ge 5\) the residues \(1\le r\le s-3\) (\(\ell \ge 3\) skeleton coordinates) are open for all \(p\); per-prime nets exist for \(s=5\), \(r=2\) at seven primes (computed, after Corollary 41), and a family for all large \(p\) is open. Lattices with the optimal minimum order \(p^{\ell /s}\) exist by a counting argument (after Lemma 31); explicit ones are known here only for \(\ell =1\), \(\ell =2\) and \(r=1\), and for \(3\le \ell \le s-2\) an explicit family is open (a mixed radix in the ring of integers of a degree-\(\ell \) field is a natural candidate). The bottleneck is to realize such a skeleton with bounded faults: inside the frame orbit Lemma 40 excludes the Korobov skeleton digits of \(\mathcal B^1\) with small faults (Corollary 41); other Korobov vectors, faults growing slowly with \(p\), and completions outside the frame orbit are not excluded, and per prime frame-orbit skeletons with faults \(\pm 1\) work (Proposition 42). For one skeleton coordinate it is open whether the certified Euclidean constants tend to \(\sqrt{\gamma _s}\) (Remark 127) and which explicit \(\kappa \) attain it; for two skeleton coordinates, Euclidean (rather than maximum-norm) bounds are open. (4) In dimension four: \(m\equiv 1\pmod4\) for primes \(p{\gt}83\) (no closed form is known; per-prime nets are known at every prime \(7\le p\le 83\), after Corollary 41 (computed), Proposition 42 works out \(p=13\), and we know of no obstruction for larger \(p\)), \(m=4\), and small primes (\(m\equiv 1\) at \(p=5\), \(m\equiv 2\) at \(p\le 19\), \(m\equiv 3\) at \(p\le 13\)). Also open: an explicit \(p_0(s)\) in Theorem 37 for \(s\ge 9\), and a covering radius uniform in \(p\) for \(\ell \ge 2\). (5) In dimension three: a mesh ratio uniform in \(p\) for \(m\equiv 1\); \(m\in \{ 4,7\} \) for \(p\le 31\) and \(m=5\) for \(p\le 7\); and an explicit family for all large primes with limit \({\gt}1\) at the resolutions \(m\ge 4\) (at \(m=3\) the nets \(\mathcal T_p\) and \(\mathcal W_p\) of Propositions 106 and 107 are such families). At \(m=3\), among constants below \(1\): whether digital \((0,3,3)\)-nets that are not column point sets have smaller deficits than \(\frac13\) and \(\frac23\) (Theorem 97 settles this among column point sets; outside them the drift-and-jitter bookkeeping of Section 11 is only a heuristic).

(III) Large-entry layers. (6) (a) Smaller bases for \(s\ge 5\): Proposition 125 needs \(p\ge 1511\), and at one resolution it is open whether some \((0,5,5)\)-net over \(\mathbb {F}_p\) with \(p\le 31\) has \(\delta N^{1/5}{\gt}1\) (Proposition 121). (b) The drift-and-jitter bookkeeping for half-integer layers at \(k\ge 2\), where the split-frame layers are Cauchy matrices, and for \(s\ge 6\). (c) Split-frame designs with explicit constants of moderate size for \(s=6,7,8\). (d) Half-integer layers at the resolutions \(m\not\equiv 0\pmod s\). (e) Other split-frame layers beyond \(D_s^+\). (7) In dimension three: whether a geometric layer \(\tilde M\approx qA\) with a fixed rational matrix \(A\) can be realized for every \(k\) with \(\delta N^{1/3}\) bounded above \(1\). At \(k=1\), layers whose geometric digits wrap together in two or three coordinates (locked wraps, Section 13.3) give the limits \(\sqrt{66}/8\) (Proposition 106), \(\sqrt{281}/16\) (Proposition 107) and \(\mu ^*=1.0480\ldots \) (Remark 110), the optimum of the layers of rank one with image \(\mathbb {F}_p(2,2,1)\) (Proposition 109); the optimum over the other images of rank one, over layers of rank two and over non-digital point sets is open. At \(k\ge 2\) the geometric digits of any two coordinates are jointly uniformly distributed (Lemma 52, as \(2(k+1)\le 3k\)), so no relation between the geometric digits of two coordinates survives, and neither the two-coordinate lock of \(\mathcal T_p\) nor the three-coordinate lock of \(\mathcal W_p\) extends to \(k\ge 2\). For digital nets the only linear relation among the three geometric digits of one index that this count leaves is one of full support, \(h_xr_x+h_yr_y+h_zr_z\equiv 0\) with all \(h_c\ne 0\); whether such a relation, or a correlation that involves digits of other indices, can raise the constant above \(1\) is open.

The case \(k=1\) and digital shifts. (8) At \(k=1\): whether \(K_1=1\) is possible for \(s=5\), or \(K_1=2\) for \(s=6\) (Proposition 86); frameless layers (\(F_0\) chosen directly, not from a frame, Proposition 86(2)) for \(s\ge 7\); and the choice of the deeper rows, which are free at \(k=1\) apart from \(t=0\) and change the exact separation at small \(q\) (Proposition 85 and the remark after it). (9) In the bases two and three the constants of Theorem 66(3) are certified lower bounds, not exact values; for \(b=3\) and \(m\equiv 2\pmod3\) the infimum over \(m\) and \(\tau \) for these nets lies between \(0.0770\) and \(0.0901\), the latter the exact value at \(m=20\) (computed). Whether other seeds or lift parameters give larger every-shift constants in base three is open.

Sequences. (10) All nets here depend on \(m\); they are not prefixes of one sequence, and the question of [ 11 ] for sequences remains open in dimension \(s\ge 3\).

Beyond digital nets. (11) Can nets that are not digital, for instance permutation nets, exceed the constants of the digital nets here, for instance by avoiding the slip planes that linear offsets force (Corollary 99)?