Given a sequence $x\_1,x\_2,\dots$, let $D\_n$ be the $L^2$-norm of the function $f\_n$ whose value at $t \in [0,1)$ is $nt$ minus the number of $1 \leq i \leq n$ with $x\_i \leq t$. What can be said about the rate at which $D\_n$ must go to infinity, regardless of the choice of $x\_1,x\_2,\dots$?


That is, what theorem lower-bounds the $L^2$ norm of $f\_n$ in analogy with the way Schmidt’s discrepancy theorem (see <http://mathworld.wolfram.com/DiscrepancyTheorem.html>) lower-bounds the $L^\infty$ norm of $f\_n$?



$L^2$ discrepancy bound for sequences in $[0,1)$
This problem has been addressed in work of Roth and Davenport. Roth showed that for any sequence there must be $n$ with $D\_n$ larger than a constant times $\sqrt{\log n}$, and Davenport constructed sequences for which $D\_n$ grows like at most a constant times $\sqrt{\log n}$. 


More precisely, for any set ${\mathcal P}$of $N$ points in $[0,1)^2$, Roth showed that 
$$ 
\int\_{\alpha,\beta=0}^{1} \Big| |{\mathcal P}\cap [0,\alpha)\times [0,\beta)| - N\alpha\beta \Big|^2 d\alpha d\beta \gg \log N. 
$$ 
Apply this to the points $(n/N,x\_n)$ with $n=1$, $\ldots$, $N$. It then follows that 
$$ 
\frac{1}{N} \sum\_{n=1}^{N} D\_n^2 \gg \log N,
$$ 
which proves the lower bound for $D\_n$. 


As for the upper bound, Davenport showed that Roth's result above is best possible by looking at the set $(n/N,\{n \alpha\})$ where $\alpha$ is an irrational number with bounded partial quotients (e.g. $\alpha=\sqrt{2}$). If you look at Davenport's argument (see page 133 of the paper), he really shows that for this sequence (i.e. $x\_n=\{n\sqrt{2}\}$), the $L^2$ discrepancy is of size $\sqrt{\log n}$. 


Roth's paper is in Mathematika vol 1, 1954, and Davenport's in Mathematika vol 3, 1956. 


