5
$\begingroup$

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$?

Improve this question
$\endgroup$
4
  • $\begingroup$ I think (based on preliminary experiments) that typical behavior of $D_n$ is on the order of $n^{1/2}$. $\endgroup$
    – James Propp
    Commented Sep 2, 2014 at 3:47
  • $\begingroup$ But the context of Schmidt's discrepancy theorem indicates that the question is what happens not for typical sequences but for any sequence, no matter how well distributed. Since there are sequences whose $L^\infty$ discrepancy is $O(\log n)$, the same sequence has $L^2$ discrepancy at worst $O(\sqrt{\log n})$. Conceivably this can be improved further even though for $L^\infty$ it is known that $C\log n$ is best possible. $\endgroup$
    – Noam D. Elkies
    Commented Sep 2, 2014 at 4:34
  • 1
    $\begingroup$ @NoamD.Elkies: Not sure how you deduce an $O(\sqrt{\log n})$ upper bound for $\min \|f_n\|_2$ from an $O(\log n)$ upper bound for $\min \|f_n\|_\infty$ (I do see how to get an $O(\log n)$ upper bound). $\endgroup$
    – Anthony Quas
    Commented Sep 2, 2014 at 5:10
  • $\begingroup$ Sorry my first comment was misleading. What I meant to say was that for the van der Corput sequence, the behavior of $D_n$ appears to be $n^{1/2}$ (albeit with lots of fluctuations), and I suspect that this is best possible, in the sense that for any $c<1/2$, $D_n / n^c$ is unbounded, regardless of what sequence $x_1,x_2,...$ one is looking at. $\endgroup$
    – James Propp
    Commented Sep 2, 2014 at 15:35

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am confused. The Mathematica code Davenport[n_] := Integrate[(Sum[If[t >= Mod[N[k Sqrt[2]], 1], 1, 0], {k, 0, n - 1}] - t n)^2, {t, 0, 1}] gives the values 0.33,0.43,0.19,0.4,0.22,0.77,0.77,0.34,0.52,0.27,0.68,0.53,0.2,0.26,0.18,0.27,0.15,0.58,0.63,0.31,0.49,0.28,0.7,0.6,0.26,0.34,0.18,0.35,0.2,0.84,0.97,0.51 as n goes from 1 to 32 (where I've rounded to two sig figs). This doesn't look like log $n$ times a constant. Am I naive in expecting the asymptotics to kick in by $n=32$? Am I making a basic mathematical or programming error? Or is Mathematica doing something wrong? $\endgroup$
    – James Propp
    Commented Sep 4, 2014 at 4:03
  • $\begingroup$ I've satisfied myself that these numbers are right (by writing completely different Mathematica code that doesn't use potentially buggy Mathematica procedures for integration of discontinuous integrands; see jamespropp.org/davenport.pdf) so I'm guessing that Davenport's $D_n$ must be different from mine (unless the asymptotics are slow to kick in). Has anyone tabulated the exact values of these integrals for values beyond 32? That might shed some light on the situation. $\endgroup$
    – James Propp
    Commented Sep 4, 2014 at 17:36
  • $\begingroup$ A few points: one is that Davenport needs to consider $\{n\alpha\}$ for positive and negative $n$. This is easily fixed by considering $x_{2n} = \{n\sqrt{2}\}$ and $x_{2n+1} = \{-n\sqrt{2}\}$ say. So you could try computing these. Note that only an upper bound is established, and not an asymptotic -- there will be fluctuations. The log arises from rational approximations to $\sqrt{2}$, there are constants involved, and also the denominators of the convergents grow exponentially. Numerical computations up to $32$ may not be very insightful; I recommend reading the (simple) proof. $\endgroup$
    – Lucia
    Commented Sep 4, 2014 at 18:05
  • $\begingroup$ I did the calculations up through 10,000, and it looks much more like a constant times log n (up to fluctuations). I plan to look at the proof, as Lucia suggests. In the meantime, I will approve her answer. (Thanks, Lucia!) $\endgroup$
    – James Propp
    Commented Sep 4, 2014 at 21:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .