On a Question of Becher and Slaman: For Kurtz Random x the Discrepancy of (2^n x) Is Not O((log N)/N)

In Oberwolfach Report 1/2018, Becher and Slaman ask whether some Martin-Löf random real \(x\) has discrepancy \(D_N((2^nx)_{n\ge1})=O((\log N)/N)\) for all large \(N\). Read as asking for constants \(C\), \(N_0\) with \(ND_N\le C\log N\) for all \(N\ge N_0\), the question has a negative answer, also for Schnorr, computably and Kurtz random \(x\). More precisely, if \(x\) is Kurtz random and \(g\) is computable with \(\limsup_Ng(N)/\sqrt{N\log\log N}<1/\sqrt2\), for instance any computable \(g(N)=o(\sqrt{N\log\log N})\), then \(ND_N>g(N)\) for infinitely many \(N\); in particular \(\limsup_NND_N/\sqrt{N\log\log N}\ge1/\sqrt2\). We give two short proofs of the negative answer. The first combines Koksma's inequality for \(e^{2\pi it}\), the law of the iterated logarithm of Erdős and Gál for lacunary exponential sums, and the fact that a null effectively closed set contains no Kurtz random real; it gives the constant \(1/(2\pi)\) in place of \(1/\sqrt2\). The second replaces these analytic tools by the observation that \(\{2^nx\}<\frac12\) exactly when the \((n+1)\)st binary digit of \(x\) is \(0\), so that \(ND_N\) is at least the deviation from \(N/2\) of a count of zeros; a binomial estimate then gives the negative answer, and Khinchin's law of the iterated logarithm gives the constant \(1/\sqrt2\). For Martin-Löf random \(x\) the negative answer follows at once from this digit count and Vovk's law of the iterated logarithm for Martin-Löf random sequences; the note records a short observation from known results, which may be folklore. The question is due to Becher and Slaman, and the tools are classical. We do not treat the variant with “for infinitely many \(N\)”, nor Korobov's question on the existence of a normal number with discrepancy \(O((\log N)/N)\), which the source connects with the question, nor the other questions of the problem session. This is an unrefereed note.