An explicit formula for the \(L_2\)-discrepancy of \((n\alpha)\)-sequences
type: Item
instance of: scholarly article
title: An explicit formula for the \(L_2\)-discrepancy of \((n\alpha)\)-sequences
zbMATH Open document ID: 1099.11038
published in: Computing
publication date: 2006-03-21T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 11K38
Mathematics Subject Classification ID: 11K31
Mathematics Subject Classification ID: 11K50
Mathematics Subject Classification ID: 11J70
Mathematics Subject Classification ID: 11J71
zbMATH DE Number: 5014078
zbMATH Keywords: discrepancy
zbMATH Keywords: Weyl sequence
zbMATH Keywords: distribution mod\,1
zbMATH Keywords: continued fractions
author: Luís Roçadas
author: Johannes Schoissengeier
MaRDI profile type: Publication
full work available at URL: s00607-005-0143-1
OpenAlex ID: W2044021661
cites work: Calculation of improper integrals using \((n\alpha)\)-sequences
cites work: Efficient algorithms for computing the $L_2$-discrepancy
cites work: Continued fractions and density results for Dedekind sums.
cites work: Another proof of a theorem of J. Beck
DOI: 10.1007/S00607-005-0143-1
description: scientific article; zbMATH DE number 5014078