A Negative Answer to a Question of Novak on Randomly Shifted Lattices and the Expected p-th Power of the L_p Discrepancy

In an Oberwolfach report of 2004, E. Novak (joint work with A. Hinrichs) considered the generalized lattices with shift \(M_n^{z,\Delta}\)\({}=\{jz\)\({}+\Delta \bmod 1\)\({}:\ 0\)\({}\le j\)\({}<n\}\), with \(z\) and \(\Delta\) independent and uniformly distributed in \([0,1]^d\), and asked whether, for even \(p\), the expectation of \(\operatorname{disc}_p^p(M_n^{z,\Delta})\), the \(p\)-th power of the \(L_p\) discrepancy, is at most the corresponding expectation for \(n\) independent uniformly distributed points. We show that the answer is negative. Equality holds for \(p=2\), because the lattice points are pairwise independent (in substance a known fact, which underlies random Weyl sampling), and for \(n\le2\). For \(n=3\) and \(p=4\) the difference of the two expectations is \(\frac89\,2^{-d}\bigl((\frac25)^d\)\({}-(\frac{19}{48})^d\bigr)\)\({}>0\) in every dimension \(d\); for \(d=1\) the two values are \(19/1620\) and \(16/1620\). A closed formula shows that \(n=4\), \(p=4\) fails in every dimension as well. For every \(d\) and every even \(p\ge4\) the inequality fails for all \(n\ge N(d,p)\), with \(N(d,p)\) explicit: with probability of order \(1/n\) the points form a short arithmetic progression, which gives \(\mathbb{E}\operatorname{disc}_p^p\)\({}\ge 4\)\(/((p\)\({}+1)^d(p\)\({}+2)(p\)\({}+3)(n\)\({}-1))\) for the lattices, against order \(n^{-p/2}\) for independent points. For thirteen pairs \((p,d)\), among them \(p=4\) with \(d\le4\), the inequality fails for every \(n\ge3\); this part is computer-assisted (exact rational arithmetic and a certified polynomial inequality). We conjecture failure for all \(n\ge3\), \(d\ge1\) and even \(p\ge4\). The answer concerns the \(p\)-th power, as in the source; for the expectation of \(\operatorname{disc}_p\) itself, which the wording of the corpus record also allows, all computed cases go the other way. The results are asymptotic in \(n\) for fixed \(d\) and \(p\) and do not exclude bounds of the i.i.d. type when \(n\) grows polynomially with \(d\). The question is Novak's; no answer to it was found in the literature accessible to us. This is an unrefereed note.