Lebesgue constants for the Walsh system and the discrepancy of the van der Corput sequence

1. Problem Statement

The paper addresses a previously unobserved coincidence between two distinct mathematical quantities from different branches of analysis:

1. Lebesgue Constants ($L_n$): Fundamental in approximation theory, specifically regarding the convergence of Fourier series expansions with respect to the Walsh system. These constants measure the worst-case error of the partial sum operator relative to the uniform norm.
2. Star Discrepancy ($D^*_n$): A central concept in uniform distribution theory and quasi-Monte Carlo methods, measuring the irregularity of distribution of a sequence. The paper focuses on the van der Corput sequence, a canonical low-discrepancy sequence.

The Core Problem: While both quantities have been studied extensively and independently for decades, no connection was known between the Lebesgue constants of the Walsh system and the non-normalized star discrepancy of the van der Corput sequence. The authors aim to prove that these two quantities are identical and explore the implications of this equivalence.

2. Methodology

The authors employ a direct analytical approach to establish the equality between the two quantities:

• Definitions:

  • Walsh System: Defined via binary expansions. For $k = \sum k_j 2^j$ and $x = \sum x_j 2^{-j}$, the Walsh function is $wal_k(x) = (-1)^{\sum x_j k_j}$.
  • Lebesgue Function: $L_n(x) = \int_0^1 |D_n(x, u)| du$, where $D_n$ is the Walsh Dirichlet kernel. Fine (1947) proved $L_n(x)$ is constant, denoted $L_n$.
  • van der Corput Sequence ($Y_{vdC}$): Constructed by reversing the binary digits of non-negative integers $k$. The $k$-th term is $y_k = \sum k_j 2^{-(j+1)}$.
  • Non-normalized Discrepancy: $d_n = n D^*_n(Y_{vdC})$.

• Proof Strategy:

  1. Decomposition: The authors decompose the set of the first $n$ terms of the van der Corput sequence based on the binary representation of $n$. If $n = 2^{n_1} + 2^{n_2} + \dots + 2^{n_\nu}$ (with $n_1 > n_2 > \dots$), the set $\{y_0, \dots, y_{n-1}\}$ is partitioned into $\nu$ disjoint intervals.
  2. Integration: They utilize the known property that the star discrepancy of the van der Corput sequence is non-negative and equals twice the $L_1$-norm of the discrepancy function.
  3. Calculation: By explicitly integrating the discrepancy function over the decomposed intervals, they derive a closed-form expression for $d_n$.
  4. Comparison: They compare this derived expression for $d_n$ with the known formula for the Lebesgue constants $L_n$ established by Fine.

3. Key Contributions

The primary contribution is the rigorous proof of the identity:
$$d_n = L_n$$
where $d_n$ is the non-normalized star discrepancy of the first $n$ terms of the van der Corput sequence, and $L_n$ is the $n$-th Lebesgue constant for the Walsh system.

Specific Contributions:

• Unification of Fields: The paper bridges approximation theory (Walsh functions) and uniform distribution theory (discrepancy), showing that results in one domain immediately translate to the other.
• New Representations: The equivalence allows for new integral representations of the star discrepancy using Walsh functions and vice versa.
• Transfer of Theorems: The authors demonstrate how known theorems in discrepancy theory (specifically by B'ejian and Faure) refine existing results on Lebesgue constants, and conversely, how results on Lebesgue constants provide new insights into the distribution properties of the van der Corput sequence.

4. Key Results

The paper establishes several specific consequences of the identity $d_n = L_n$:

• Exact Formula: Both quantities satisfy the formula derived by Fine:
  $$L_n = d_n = \nu - \sum_{1 \le j < i \le \nu} 2^{n_i - n_j}$$
  where $n = \sum_{i=1}^\nu 2^{n_i}$ is the binary expansion of $n$.

• Asymptotic Behavior:

  • Growth Rate: $L_n = O(\log n)$.
  • Average Order: $\frac{1}{n} \sum_{k=1}^n L_k = \frac{\log n}{4 \log 2} + O(1)$.
  • Refined Upper Bound: Using results from discrepancy theory, the paper notes the refined bound $d_n \le \frac{\log n}{3 \log 2} + 1$.

• Maximum Values: The maximum value of $d_n$ (and thus $L_n$) in the interval $[2^{r-1}, 2^r]$ is attained at $n = (2^{r+1} + (-1)^r)/3$ and equals $\frac{r}{3} + \frac{7}{9} + \frac{(-1)^r}{9 \cdot 2^{r-1}}$.

• Generating Function: A new generating function for the star discrepancy is derived:
  $$\sum_{n=1}^\infty d_n z^n = \frac{1}{2} \frac{z}{(1-z)^2} \sum_{k=0}^\infty \frac{1}{2^k} \frac{1-z^{2^k}}{1+z^{2^k}}$$

• Central Limit Theorem (CLT): The paper formulates a CLT for the Lebesgue constants (previously known for discrepancy). As $N \to \infty$:
  $$\frac{1}{N} \# \left\{ n < N : L_n \le \frac{\log n}{4 \log 2} + y \sqrt{\frac{\log n}{3 \log 2}} \right\} \to \Phi(y)$$
  where $\Phi(y)$ is the standard Gaussian cumulative distribution function.

• Limit Behavior for Specific $t$: The paper reformulates a result regarding the limit of $d_{n_t(m)} / \log n_t(m)$ (where $n_t(m) = \lfloor 2^m(1+t) \rfloor$):

  • For almost all $t$, the limit is $\frac{1}{4 \log 2}$.
  • For dyadic rational $t$, the limit is $0$.
  • There exists a dense subset $A$ where the limit inferior is $0$ and the limit superior is $\frac{1}{3 \log 2}$.

5. Significance

The significance of this work lies in its ability to transfer knowledge across mathematical disciplines:

1. For Approximation Theory: It provides new probabilistic insights (CLT) and refined bounds for Walsh system convergence that were previously only known in the context of discrepancy theory.
2. For Uniform Distribution Theory: It offers new integral representations and generating functions for the van der Corput sequence derived from the rich theory of orthogonal polynomials and Fourier analysis.
3. Historical Context: The paper highlights that many deep results (such as the specific asymptotic behavior and maximum values) were discovered independently in both fields, often with one field lagging behind the other. This unification suggests that future research in one area should actively look for analogues in the other.

In summary, the paper reveals a profound structural identity between the error bounds of Walsh series approximation and the distribution irregularity of the van der Corput sequence, effectively merging two previously siloed areas of mathematical research.