An explicit formula for the \(L_2\)-discrepancy of \((n\alpha)\)-sequences (Q818850)

Assume that \(\alpha\) is an irrational number with continued fraction expansion \([a_0;a_1,\dots]\) and convergents, \(n=0,1,\dots\). Every positive integer \(N\) has a unique expansion \(N=b_0q_0+b_1q_1+\cdots +b_mq_m\), where the digits \(b_i\) are nonnegative integers with \(b_0<a_1\), \(b_i\leq a_{i+1}\) and such that \(b_i=a_{i+1}\) implies \(b_{i-1}=0\), the so-called Ostrowski expansion of \(N\) to base \(\alpha\). On the other hand let \(c_{[0,x)}\) be the characteristic function of the half-open interval \([0,x)\) and let \[ D^{*(2)}_N(\alpha):=\sqrt{\int^1_0\left(\sum^N_{n=1}c_{[0,x]}(\{n\alpha\})-Nx\right)^2\,dx} \] be the \(L_2\)-discrepancy of the sequence \((n\alpha)\bmod 1\), where \(\{y\}\) denotes the fractional part of the real number \(y\). In this paper, we give an explicit formula for \(D^{*(2)}_N(\alpha)\) entirely in terms of the digits \(b_0,\dots ,b_m\). This formula enables one to compute the \(L_2\)-discrepancy in at most \(O(\log^4N)\) steps, where the \(O\)-constant does not depend on \(\alpha\), while in the classical formulae for the \(L_2\)-discrepancy \(N^2/2\) calculation steps are necessary. The fastest algorithm so far was found by \textit{S. Heinrich} [Math. Comput. 65, No. 216, 1621--1633 (1996; Zbl 0853.65004)] and works (for all sequences) in \(O(N \log N)\) steps. Let \(\alpha\) be an irrational number, \(\alpha\in(0,1)\) and for any \(x\in [0,1]\) \(N_x(n)=\sum_{\{m\alpha\}<x}1\) with \(m\leq n\), \(\{.\}\) being the fractional part. The paper gives a closed formula for the square-integral (*) \(\int^1_0(N_x(n)-nx)^2\). The formula expresses (*) in terms of the regular continued fraction expansion of \(\alpha\).