Prove a stronger formula for the discrepancy of a sequence

Question

I am reading famous book about uniform distribution of sequences by Kuipers and Niederreiter and have questions about solving below exercise from that book. Before going to main exercise I will write here some definitions that are needed for problem.

DEFINITION The sequence $w = (x_n), n = 1, 2, ... ,$ of real numbers is said to be uniformly distributed modulo $1$ (abbreviated u.d. $\text{mod }1$) if for every pair $(a, b)$ of real numbers with $0 < a < b < 1$ we have

$$\lim_{N \to \infty} \frac{A([a,b);N;w)}{N} = b-a$$

where for a positive integer $N$ and a subset $E$ of $[0,1]$, let the counting function $A(E; N; w)$ be defined as the number of terms $x_n, 1 \leq n \leq N$, for which the fractional part of $x_n \in E.$

Let $x_1,\cdots x_N$ be a finite sequence of real numbers.

The number $$D_N = D_N(x_1,\cdots x_N)= \sup_{0 \leq \alpha < \beta \leq 1}\Bigg|\frac{A([\alpha,\beta);N)}{N}-(\beta - \alpha)\Bigg|$$

is called the discrepancy of the given sequence.

Now main problem.

Prove that $$D_N(x_1,\cdots, x_N)= \sup_{0 \leq \alpha \leq \beta \leq 1} \Bigg|\frac{A([\alpha,\beta];N)}{N} - (\beta - \alpha)\Bigg|$$

So two points needs to be proven, the interval could be just one point and closed interval instead of partial closed interval.

For first case why we can write $\alpha = \beta $ below sup.

Let $\alpha = \beta $ and let all fractional parts of ${x_n}$ be $\alpha$.Second $D_N$ will be equal to $1$. For first one let $\beta = \alpha + \epsilon$

Then $D_N = \lim_{\epsilon \to 0} 1 - \epsilon = 1$

Same thing we can do with replacing partially closed interval to closed interval. We will look $[\alpha, \beta + \epsilon)$ intervals.

Seems trivial work from my side don't think solution would be this trivial. Anything I am doing wrong?

Answer 1

Some notations.

Without loss of relevance or generality, assume $N$ is fixed and all $x_i$ are in $[0,1)$.

Let $$D_N(\alpha,\beta)=\left|\frac{A([\alpha,\beta);N)}{N} - (\beta - \alpha)\right|.$$ So $D_N=\displaystyle\sup_{0 \leq \alpha \leq \beta \leq 1} D_N(\alpha, \beta).$

Similarly, let $$\Delta_N(\alpha,\beta)=\left|\frac{A([\alpha,\beta];N)}{N} - (\beta - \alpha)\right|,$$ and $\Delta_N=\displaystyle\sup_{0 \leq \alpha \leq \beta \leq 1} \Delta_N(\alpha, \beta).$

We are asked to show $D_N=\Delta_N$.

Remarks on the approach in the question

Call $\Delta_N$ "the stronger formula" is misleading. While the extra case when $\alpha=\beta$ may help make $\Delta_N$ larger than $D_N$, the fact that $A([\alpha,\beta];N)$ may be strictly larger than $A([\alpha,\beta);N)$ does not necessarily help make $\Delta_N$ larger because of the absolute value. Although $0.36>0.2$, we have $|0.36-0.3| < |0.2-0.3|$.

It looks your (idea of) proof is insufficient or lacking the details.

• When $\alpha=\beta$, it is unclear why there is no loss of generality to assume all $x_n$ is $\alpha$. Also the missing special case $\beta=1$ deserves a mention even if it is trivial.
• The argument above against "the stronger formula" indicates that it is specious that "same thing we can do …" will demonstrate correctly what happens when "replacing partially closed interval to closed interval".

A complete proof

We will prove each of $D_N$ and $\Delta_N$ is $\le$ the other.

Prove $\Delta_N \le D_N$

Consider $\Delta_N(\alpha, \beta)$, where $0\le\alpha\le\beta\le1$. There are two cases.

• $\beta =1$.
  Since all $x_i<1$, $\ A([\alpha, 1];N)=A([\alpha, 1);N)$. Hence $\Delta_N(\alpha,\beta)=D_N(\alpha,\beta)\le D_N$
• $\beta <1$.
  Since $$\left|D_N(\alpha, \gamma)-\Delta_N(\alpha,\beta)\right| \le\left|\frac{A([\alpha, \gamma);N)-A([\alpha, \beta];N)}N\right|+\left|\beta-\gamma\right|$$ for all $\beta<\gamma\le 1$ and $$\lim_{\gamma\to\beta^+}A([\alpha, \gamma);N)=A([\alpha, \beta];N)$$ We have $$\lim_{\gamma\to\beta^+}\left|D_N(\alpha, \gamma)-\Delta_N(\alpha,\beta)\right|=0 $$ Hence $\Delta_N(\alpha,\beta)\le D_N$.

So in all cases, $\Delta_N(\alpha,\beta)\le D_N$. Since $\alpha,\beta$ are arbitrary, $\Delta_N\le D_N$.

Prove $D_N \le \Delta_N$

Consider $D_N(\alpha, \beta)$, where $0\le\alpha<\beta\le1$. Since $$\left|\Delta_N(\alpha, \gamma)-D_N(\alpha,\beta)\right| \le\left|\frac{A([\alpha, \gamma];N)-A([\alpha, \beta);N)}N\right|+\left|\beta-\gamma\right|$$ for all $\alpha\le\gamma\le 1$ and $$\lim_{\gamma\to\beta^-}A([\alpha, \gamma];N)=A([\alpha, \beta);N)$$ We have $$\lim_{\gamma\to\beta^-}\left|\Delta_N(\alpha, \gamma)-D_N(\alpha,\beta)\right|=0 $$ Hence $D_N(\alpha,\beta)\le \Delta_N$. Since $\alpha,\beta$ are arbitrary, $D_N\le\Delta_N$.