Introduction
The theory of uniform distribution modulo one was developed in the work of Weyl [17 ] . A sequence ( x n ) n ≥ 1 ⊂ [ 0 , 1 ) (x_n)_{n\ge1}\subset[0,1) ( x n ) n ≥ 1 ⊂ [ 0 , 1 ) is uniformly distributed modulo one if
1 N # { 1 ≤ n ≤ N : x n ∈ [ a , b ) } → b − a ( N → ∞ ) \frac{1}{N}\#\{1\le n\le N:x_n\in[a,b)\}\to b-a\qquad(N\to\infty) N 1 # { 1 ≤ n ≤ N : x n ∈ [ a , b )} → b − a ( N → ∞ )
for every 0 ≤ a < b ≤ 1 0\le a<b\le1 0 ≤ a < b ≤ 1 . A basic example is the Kronecker sequence { n α } n ≥ 1 \{n\alpha\}_{n\ge1} { n α } n ≥ 1 for any irrational α \alpha α , where { t } = t − ⌊ t ⌋ \{t\}=t-\lfloor t\rfloor { t } = t − ⌊ t ⌋ denotes the fractional part of t t t .
For x = ( x n ) ⊂ [ 0 , 1 ) x=(x_n)\subset[0,1) x = ( x n ) ⊂ [ 0 , 1 ) , put
A N x ( t ) = # { 1 ≤ n ≤ N : x n < t } ( N ≥ 1 , 0 ≤ t ≤ 1 ) , A_N^x(t)=\#\{1\le n\le N:x_n<t\}\qquad(N\ge1,\ 0\le t\le1), A N x ( t ) = # { 1 ≤ n ≤ N : x n < t } ( N ≥ 1 , 0 ≤ t ≤ 1 ) ,
with A 0 x ( t ) = 0 A_0^x(t)=0 A 0 x ( t ) = 0 . The star discrepancy of the first N N N points is
D N ∗ = D N ∗ ( x ) : = sup 0 ≤ t ≤ 1 ∣ A N x ( t ) N − t ∣ . D_N^*=D_N^*(x):=\sup_{0\le t\le1}\left|\frac{A_N^x(t)}{N}-t\right|. D N ∗ = D N ∗ ( x ) := 0 ≤ t ≤ 1 sup N A N x ( t ) − t .
A sequence x x x is uniformly distributed modulo one if and only if D N ∗ ( x ) → 0 D_N^*(x)\to0 D N ∗ ( x ) → 0 as N → ∞ N\to\infty N → ∞ ; see Kuipers and Niederreiter [5 Chapter 2, Corollary 1.1] . Thus star discrepancy measures the rate of convergence to uniform distribution. A sequence is called a low-discrepancy sequence if D N ∗ = O ( ( log N ) / N ) D_N^*=O((\log N)/N) D N ∗ = O (( log N ) / N ) . This order is optimal for infinite one-dimensional sequences: Schmidt [15 ] proved that N D N ∗ ≫ log N ND_N^*\gg\log N N D N ∗ ≫ log N for infinitely many N N N for every infinite sequence in [ 0 , 1 ) [0,1) [ 0 , 1 ) . Both the Kronecker sequence ( { n α } ) n ≥ 1 (\{n\alpha\})_{n\ge1} ({ n α } ) n ≥ 1 with α \alpha α having bounded partial quotients in its continued fraction expansion, and the van der Corput sequence, attain this order; see Kuipers and Niederreiter [5 Chapter 2, Theorems 3.4 & 3.5] . We also refer the reader to this book for further background and history, as well as for more information.
Pair correlation concerns distances between pairs of points at the scale 1 / N 1/N 1/ N . We identify [ 0 , 1 ) [0,1) [ 0 , 1 ) with T = R / Z \mathbb{T}=\mathbb{R}/\mathbb{Z} T = R / Z and write ∥ ⋅ ∥ T = min m ∈ Z ∣ ⋅ − m ∣ \|\,\cdot\,\|_{\mathbb{T}}=\min_{m\in\mathbb{Z}}|\cdot-m| ∥ ⋅ ∥ T = min m ∈ Z ∣ ⋅ − m ∣ for the distance to the nearest integer. For a sequence x = ( x n ) x=(x_n) x = ( x n ) , we define
R N ( s ) = R N x ( s ) : = 1 N # { 1 ≤ i ≠ j ≤ N : ∥ x i − x j ∥ T ≤ s N } ( s > 0 ) . R_N(s)=R_N^x(s):=\frac{1}{N}\#\left\{1\le i\ne j\le N:\|x_i-x_j\|_{\mathbb{T}}\le\frac{s}{N}\right\}\qquad(s>0). R N ( s ) = R N x ( s ) := N 1 # { 1 ≤ i = j ≤ N : ∥ x i − x j ∥ T ≤ N s } ( s > 0 ) .
The sequence has Poissonian pair correlation (PPC) if, for every s > 0 s>0 s > 0 ,
R N ( s ) → 2 s ( N → ∞ ) . R_N(s)\to2s\qquad(N\to\infty). R N ( s ) → 2 s ( N → ∞ ) .
This is the almost-sure limit for independent uniform random points on T \mathbb{T} T .
El-Baz, Marklof and Vinogradov [2 ] proved that ( { n } ) n ≥ 1 \left(\{\sqrt{n}\}\right)_{n\ge1} ( { n } ) n ≥ 1 has PPC after the terms with square n n n are omitted. Metric examples include ( { n 2 α } ) n ≥ 1 \left(\{n^2\alpha\}\right)_{n\ge1} ( { n 2 α } ) n ≥ 1 and ( { 2 n α } ) n ≥ 1 \left(\{2^n\alpha\}\right)_{n\ge1} ( { 2 n α } ) n ≥ 1 , which have PPC for Lebesgue-almost every α \alpha α , by results of Rudnick and Sarnak [13 ] and Rudnick and Zaharescu [14 ] , respectively.
Uniform distribution concerns frequencies in fixed intervals, whereas PPC concerns pair counts at the shrinking scale s / N s/N s / N . PPC implies uniform distribution, as proved independently by Aistleitner, Lachmann and Pausinger [1 ] and by Grepstad and Larcher [3 ] . The converse fails: for irrational α \alpha α , the Kronecker sequence ( { n α } ) n ≥ 1 \left(\{n\alpha\}\right)_{n\ge1} ( { n α } ) n ≥ 1 is uniformly distributed but does not have PPC. Even low discrepancy does not imply PPC, as the van der Corput sequence shows; both examples are covered by the results of Larcher and Stockinger [7 ] .
The relation between PPC and discrepancy also has a quantitative form. Grepstad and Larcher [3 ] and Steinerberger [16 ] obtained discrepancy bounds from quantitative estimates for pair-correlation statistics.
We study which discrepancy rates are compatible with PPC. We first construct a sequence with PPC and optimal-order star discrepancy2 . The construction yields a random sequence with low discrepancy for every realization and PPC almost surely, together with a deterministic conditional-expectation rule that selects one such realization. We also obtain a PPC sequence satisfying D N ∗ ≍ ( log N ) / N D_N^* \asymp(\log N)/N D N ∗ ≍ ( log N ) / N for all sufficiently large N N N . More generally, we construct PPC sequences with prescribed discrepancy asymptotics D N ∗ ∼ c ψ ψ ( N ) D_N^* \sim c_\psi\psi(N) D N ∗ ∼ c ψ ψ ( N ) under suitable regularity and growth assumptions on ψ \psi ψ , where c ψ > 0 c_\psi> 0 c ψ > 0 . These include every polynomial rate N − β N^{-\beta} N − β with 0 < β < 1 0 < \beta< 1 0 < β < 1 . We also show that, for every positive sequence ρ N → 0 \rho_N \to0 ρ N → 0 , there exists a PPC sequence with D N ∗ / ρ N → ∞ D_N^*/\rho_N \to\infty D N ∗ / ρ N → ∞ . Thus PPC imposes no universal discrepancy decay rate.
Throughout the paper, we use Landau and Vinogradov notation interchangeably. For instance, we write a N ≪ b N a_N \ll b_N a N ≪ b N , or equivalently a N = O ( b N ) a_N = O(b_N) a N = O ( b N ) , if there exists a constant C > 0 C > 0 C > 0 such that b N > 0 b_N > 0 b N > 0 and ∣ a N ∣ ≤ C b N \lvert a_N\rvert\le Cb_N ∣ a N ∣ ≤ C b N for all sufficiently large N N N ; sometimes a subscript on O O O or ≪ \ll ≪ is added to indicate parameters on which the implied constant C C C may depend. We write a N ≍ b N a_N \asymp b_N a N ≍ b N if both a N ≪ b N a_N \ll b_N a N ≪ b N and b N ≪ a N b_N \ll a_N b N ≪ a N , and we write a N ∼ b N a_N \sim b_N a N ∼ b N if a N / b N → 1 a_N/b_N \to1 a N / b N → 1 as N → ∞ N \to\infty N → ∞ . We write a N = o ( b N ) a_N = o(b_N) a N = o ( b N ) , or equivalently b N = ω ( a N ) b_N = \omega(a_N) b N = ω ( a N ) , if a N / b N → 0 a_N/b_N \to0 a N / b N → 0 as N → ∞ N \to\infty N → ∞ .
We denote the indicator of a set A A A by 1 A \mathbf{1}_A 1 A . The notation B ( S ) \mathcal{B}(S) B ( S ) denotes the Borel σ \sigma σ -algebra of S S S . The symbols P \mathbb{P} P and E \mathbb{E} E denote probability and expectation for the random construction under consideration. Let λ \lambda λ denote normalized Lebesgue measure on T \mathbb{T} T . All integrals on T \mathbb{T} T are taken with respect to this measure.
Our main results read as follows.
Theorem 1.1. There exists a deterministic sequence ( y n ) n ≥ 1 ⊂ [ 0 , 1 ) (y_n)_{n\ge1} \subset[0,1) ( y n ) n ≥ 1 ⊂ [ 0 , 1 ) such that
R N y ( s ) → 2 s ( N → ∞ ) for every s > 0 R_N^y(s) \to2s \qquad(N \to\infty) \qquad\text{for every } s>0 R N y ( s ) → 2 s ( N → ∞ ) for every s > 0 and
N D N ∗ ( y 1 , … , y N ) ≤ 5 2 log 2 log N ( N ≥ 2 ) . (1) N D_N^*(y_1,\ldots,y_N) \le\frac{5}{2\log2}\log N \qquad(N \ge2). \tag*{(1)} N D N ∗ ( y 1 , … , y N ) ≤ 2 log 2 5 log N ( N ≥ 2 ) . (1) A deterministic conditional-expectation rule selects such a sequence as a realization of a random sequence satisfying both properties almost surely.
Theorem 1.2. There exists a sequence ( x n ) n ≥ 1 ⊂ T (x_n)_{n\ge1} \subset\mathbb{T} ( x n ) n ≥ 1 ⊂ T with PPC such that
D N ∗ ≍ log N N D_N^* \asymp\frac{\log N}{N} D N ∗ ≍ N log N for all sufficiently large N N N .
Theorem 1.3. Let ψ : N → ( 0 , ∞ ) \psi:\mathbb{N}\to(0,\infty) ψ : N → ( 0 , ∞ ) , and put h N = N ψ ( N ) h_N=N\psi(N) h N = N ψ ( N ) with h 0 = 0 h_0=0 h 0 = 0 . Assume that, for some L > 0 L>0 L > 0 ,
0 ≤ h N − h N − 1 ≤ L ( N ≥ 1 ) . (2) 0 \le h_N-h_{N-1}\le L \qquad(N\ge1). \tag*{(2)} 0 ≤ h N − h N − 1 ≤ L ( N ≥ 1 ) . (2)
h N = ω ( log N ) ( N → ∞ ) (3) h_N=\omega(\log N)\qquad(N\to\infty) \tag*{(3)} h N = ω ( log N ) ( N → ∞ ) (3)
and
h N ≪ N log N . (4) h_N\ll\sqrt{N}\log N. \tag*{(4)} h N ≪ N log N . (4)
Then there exist a sequence ( x n ) n ≥ 1 ⊂ T (x_n)_{n\ge1}\subset\mathbb{T} ( x n ) n ≥ 1 ⊂ T and a constant c ψ > 0 c_\psi>0 c ψ > 0 such that:
the sequence ( x n ) (x_n) ( x n ) has PPC;
its star discrepancy satisfies
N D N ∗ = c ψ h N + O ( log N + h N log h N ) ND_N^*=c_\psi h_N+O\left(\log N+\sqrt{h_N\log h_N}\right) N D N ∗ = c ψ h N + O ( log N + h N log h N )
for all sufficiently large N N N . In particular,
D N ∗ ∼ c ψ ψ ( N ) ( N → ∞ ) . D_N^*\sim c_\psi\psi(N)\qquad(N\to\infty). D N ∗ ∼ c ψ ψ ( N ) ( N → ∞ ) .
:::
Theorem 1.4. Let ψ : N → ( 0 , ∞ ) \psi:\mathbb{N}\to(0,\infty) ψ : N → ( 0 , ∞ ) , and put h N = N ψ ( N ) h_N=N\psi(N) h N = N ψ ( N ) with h 0 = 0 h_0=0 h 0 = 0 . Assume that, for some L > 0 L>0 L > 0 ,
0 ≤ h N − h N − 1 ≤ L ( N ≥ 1 ) , 0\le h_N-h_{N-1}\le L\qquad(N\ge1), 0 ≤ h N − h N − 1 ≤ L ( N ≥ 1 ) , and that
h N = ω ( N log N ) ( N → ∞ ) (5) h_N=\omega(\sqrt{N\log N})\qquad(N\to\infty) \tag*{(5)} h N = ω ( N log N ) ( N → ∞ ) (5) and
h N = o ( N ) ( N → ∞ ) . h_N=o(N)\qquad(N\to\infty). h N = o ( N ) ( N → ∞ ) . Then there exist a sequence ( x n ) n ≥ 1 ⊂ T (x_n)_{n\ge1}\subset\mathbb{T} ( x n ) n ≥ 1 ⊂ T and a constant c ψ > 0 c_\psi>0 c ψ > 0 such that:
the sequence ( x n ) (x_n) ( x n ) has PPC;
its star discrepancy satisfies
N D N ∗ = c ψ h N + O ( N log N ) ND_N^*=c_\psi h_N+O\left(\sqrt{N\log N}\right) N D N ∗ = c ψ h N + O ( N log N ) for all sufficiently large N N N . In particular,
D N ∗ ∼ c ψ ψ ( N ) ( N → ∞ ) . D_N^*\sim c_\psi\psi(N)\qquad(N\to\infty). D N ∗ ∼ c ψ ψ ( N ) ( N → ∞ ) .
We record several immediate consequences of the main theorems, with proofs that assume the theorems.
Corollary 1.5. For every 0 < β < 1 0<\beta<1 0 < β < 1 , there exist a PPC sequence and a constant c β > 0 c_\beta>0 c β > 0 such that D N ∗ ∼ c β N − β D_N^*\sim c_\beta N^{-\beta} D N ∗ ∼ c β N − β as N → ∞ N\to\infty N → ∞ .
Proof. Apply Theorem 1.3 for 1 / 2 ≤ β < 1 1/2\le\beta<1 1/2 ≤ β < 1 and Theorem 1.4 for 0 < β < 1 / 2 0<\beta<1/2 0 < β < 1/2 , in both cases with ψ ( N ) = N − β \psi(N)=N^{-\beta} ψ ( N ) = N − β . □
Corollary 1.6. For every positive sequence ( ρ N ) N ≥ 1 (\rho_N)_{N\ge1} ( ρ N ) N ≥ 1 with ρ N → 0 \rho_N\to0 ρ N → 0 , there exists a PPC sequence such that
D N ∗ ρ N → ∞ ( N → ∞ ) . \frac{D_N^*}{\rho_N}\to\infty\qquad(N\to\infty). ρ N D N ∗ → ∞ ( N → ∞ ) . Thus there is no positive sequence ρ N → 0 \rho_N\to0 ρ N → 0 such that D N ∗ = O ( ρ N ) D_N^*=O(\rho_N) D N ∗ = O ( ρ N ) for every PPC sequence.
Proof. Put
u n = sup m ≥ n ρ m + n − 1 / 4 , ψ ( N ) = 1 N ∑ n = 1 N u n . u_n=\sup_{m\ge n}\sqrt{\rho_m}+n^{-1/4},\qquad
\psi(N)=\frac{1}{N}\sum_{n=1}^{N}u_n. u n = m ≥ n sup ρ m + n − 1/4 , ψ ( N ) = N 1 n = 1 ∑ N u n . Since u n ↓ 0 u_n\downarrow0 u n ↓ 0 , we have ψ ( N ) → 0 \psi(N)\to0 ψ ( N ) → 0 and ψ ( N ) ≥ u N \psi(N)\ge u_N ψ ( N ) ≥ u N . With h N = N ψ ( N ) h_N=N\psi(N) h N = N ψ ( N ) , h 0 = 0 h_0=0 h 0 = 0 ,
0 < h N − h N − 1 = u N ≤ u 1 . 0<h_N-h_{N-1}=u_N\le u_1. 0 < h N − h N − 1 = u N ≤ u 1 . Moreover,
ρ N ψ ( N ) ≤ ρ N → 0 , ( log N ) / N ψ ( N ) ≤ N − 1 / 4 log N → 0. \frac{\rho_N}{\psi(N)}\le\sqrt{\rho_N}\to0,\qquad
\frac{\sqrt{(\log N)/N}}{\psi(N)}
\le N^{-1/4}\sqrt{\log N}\to0. ψ ( N ) ρ N ≤ ρ N → 0 , ψ ( N ) ( log N ) / N ≤ N − 1/4 log N → 0. Theorem 1.4 provides a PPC sequence with D N ∗ ∼ c ψ ψ ( N ) D_N^*\sim c_\psi\psi(N) D N ∗ ∼ c ψ ψ ( N ) , and hence D N ∗ / ρ N → ∞ D_N^*/\rho_N\to\infty D N ∗ / ρ N → ∞ . □
In the proof of the main theorems, the low-discrepancy construction uses nested random point sets with equal numbers of points in dyadic cells at each completed stage. An ordering of the newly added points controls discrepancy for every N N N , while conditional pair-correlation estimates give PPC almost surely. A conditional-expectation argument, based on the method of Raghavan [12 ] , selects one realization deterministically. To obtain other discrepancy rates, we either insert sparse additional points into a fixed sequence satisfying Theorem 1.1, or sample independently from suitable nonidentical distributions.
Sections 2–5 prove Theorems 1.1–1.4, respectively. Section 6 discusses optimal discrepancy constants.
Construction of a low-discrepancy PPC sequence
We prove Theorem 1.1 in two stages. First, we construct a random sequence every realization of which has low discrepancy, and establish summable bounds on the probability that its pair-correlation estimates deviate from their expected values. Second, we convert this randomized construction into a deterministic one by means of a conditional-expectation rule, thereby producing the deterministic sequence required for Theorem 1.1.
Nested random point sets
We describe a recursive scheme that generates a sequence of increasingly refined random point sets on T \mathbb{T} T .
For k ≥ 1 k \ge1 k ≥ 1 , a dyadic interval of order k k k , or a level-k k k cell, takes the form
I k , r = [ r 2 k , r + 1 2 k ) ( 0 ≤ r < 2 k ) . I_{k,r} = \left[\frac{r}{2^k},\frac{r+1}{2^k}\right) \qquad(0 \le r < 2^k). I k , r = [ 2 k r , 2 k r + 1 ) ( 0 ≤ r < 2 k ) .
To each such interval we assign k k k labels ( k , r , j ) (k,r,j) ( k , r , j ) , 1 ≤ j ≤ k 1 \le j \le k 1 ≤ j ≤ k . Ordering all these labels lexicographically defines a bijection
τ : { ( k , r , j ) : k ≥ 1 , 0 ≤ r < 2 k , 1 ≤ j ≤ k } → N , \tau: \{(k,r,j): k \ge1,\ 0 \le r < 2^k,\ 1 \le j \le k\} \to\mathbb{N}, τ : {( k , r , j ) : k ≥ 1 , 0 ≤ r < 2 k , 1 ≤ j ≤ k } → N ,
where τ ( k , r , j ) = n \tau(k,r,j)=n τ ( k , r , j ) = n means that ( k , r , j ) (k,r,j) ( k , r , j ) is the n n n -th label in this order.
We work on the product probability space
( Ω , F , P ) = ( [ 0 , 1 ) N , B ( [ 0 , 1 ) ) ⊗ N , λ ⊗ N ) . (\Omega,\mathcal{F},\mathbb{P}) = ([0,1)^{\mathbb{N}},\mathcal{B}([0,1))^{\otimes\mathbb{N}},\lambda^{\otimes\mathbb{N}}). ( Ω , F , P ) = ([ 0 , 1 ) N , B ([ 0 , 1 ) ) ⊗ N , λ ⊗ N ) .
Define a sequence of random variables ( U n ) (U_n) ( U n ) by
U n ( ω ) = ω n , ω = ( ω j ) j ≥ 1 ∈ Ω . U_n(\omega)=\omega_n,\qquad\omega=(\omega_j)_{j\ge1}\in\Omega. U n ( ω ) = ω n , ω = ( ω j ) j ≥ 1 ∈ Ω.
Then the U n U_n U n are independent and uniform on [ 0 , 1 ) [0,1) [ 0 , 1 ) . With the n n n -th label ( k , r , j ) (k,r,j) ( k , r , j ) , where n = τ ( k , r , j ) n=\tau(k,r,j) n = τ ( k , r , j ) , we associate the candidate
Z n = r + U n 2 k , Z_n=\frac{r+U_n}{2^k}, Z n = 2 k r + U n ,
which is uniform on its assigned cell I k , r I_{k,r} I k , r . Since U n U_n U n are independent, the candidates Z n Z_n Z n are independent as well.
For each ω ∈ Ω \omega\in\Omega ω ∈ Ω , we now construct P k ( ω ) P_k(\omega) P k ( ω ) recursively. In our construction, all point counts are taken with multiplicity. We start with
P 1 ( ω ) = { Z 1 ( ω ) , Z 2 ( ω ) } . P_1(\omega)=\{Z_1(\omega),Z_2(\omega)\}. P 1 ( ω ) = { Z 1 ( ω ) , Z 2 ( ω )} .
Assume that P k ( ω ) P_k(\omega) P k ( ω ) has been defined and contains exactly k k k points in each I k , r I_{k,r} I k , r . For 0 ≤ r < 2 k + 1 0\le r<2^{k+1} 0 ≤ r < 2 k + 1 , put
p r ( ω ) = # ( P k ( ω ) ∩ I k + 1 , r ) , q r ( ω ) = k + 1 − p r ( ω ) . p_r(\omega)=\#(P_k(\omega)\cap I_{k+1,r}),\qquad q_r(\omega)=k+1-p_r(\omega). p r ( ω ) = # ( P k ( ω ) ∩ I k + 1 , r ) , q r ( ω ) = k + 1 − p r ( ω ) .
Since p r ( ω ) ∈ { 0 , … , k } p_r(\omega)\in\{0,\ldots,k\} p r ( ω ) ∈ { 0 , … , k } , we have q r ( ω ) ∈ { 1 , … , k + 1 } q_r(\omega)\in\{1,\ldots,k+1\} q r ( ω ) ∈ { 1 , … , k + 1 } . In each ( k + 1 ) (k+1) ( k + 1 ) -cell I k + 1 , r I_{k+1,r} I k + 1 , r , we retain the first q r ( ω ) q_r(\omega) q r ( ω ) of the k + 1 k+1 k + 1 candidates, namely
Z τ ( k + 1 , r , j ) ( ω ) , 1 ≤ j ≤ q r ( ω ) . Z_{\tau(k+1,r,j)}(\omega),\qquad1\le j\le q_r(\omega). Z τ ( k + 1 , r , j ) ( ω ) , 1 ≤ j ≤ q r ( ω ) .
Adjoining these retained points to P k ( ω ) P_k(\omega) P k ( ω ) , we obtain P k + 1 ( ω ) P_{k+1}(\omega) P k + 1 ( ω ) , which contains exactly k + 1 k+1 k + 1 points in each I k + 1 , r I_{k+1,r} I k + 1 , r . Thus
N k : = # P k ( ω ) = k 2 k , Q k : = N k + 1 − N k = ∑ r = 0 2 k + 1 − 1 q r ( ω ) = ( k + 2 ) 2 k . N_k := \#P_k(\omega) = k2^k,\qquad Q_k := N_{k+1}-N_k = \sum_{r=0}^{2^{k+1}-1} q_r(\omega) = (k+2)2^k. N k := # P k ( ω ) = k 2 k , Q k := N k + 1 − N k = r = 0 ∑ 2 k + 1 − 1 q r ( ω ) = ( k + 2 ) 2 k .
Whether a candidate is retained is determined by the preceding point counts. Each point count is a finite sum of indicators of the event that a candidate is retained and belongs to a given set; induction therefore shows that all retention events and point counts are measurable. Following the usual convention, we henceforth suppress the dependence on ω \omega ω .
Lemma 2.1. In terms of point counts, the random point set P k P_k P k is distributionally equivalent to the model in which k k k independent uniform points are sampled in each level-k k k cell, independently across cells. More precisely, for every finite family of Borel subsets of [ 0 , 1 ) [0,1) [ 0 , 1 ) , the counts of P k P_k P k in these sets have the same joint distribution as the corresponding counts obtained by sampling k k k independent uniform points in each I k , r I_{k,r} I k , r , independently across cells.
Proof. For this proof, we list the points in each cell as follows. For k = 1 k=1 k = 1 , each level-1 list consists of its single point. At each transition k → k + 1 k\to k+1 k → k + 1 , the old points in each ( k + 1 ) (k+1) ( k + 1 ) -cell inherit their relative order from the list in its parent node, and the retained candidates are then appended in increasing order of their indices.
We prove by induction on k k k that all entries in the level-k k k lists are mutually independent and uniform on their respective cells.
The base case k = 1 k=1 k = 1 follows from the independence of the initial samples.
Assume the assertion at level k k k . To pass to level k + 1 k+1 k + 1 , we condition on the half containing every old point in every level-k k k cell. More precisely, for each cell I k , j I_{k,j} I k , j , let X j , 1 , … , X j , k X_{j,1},\ldots,X_{j,k} X j , 1 , … , X j , k denote the old points in this cell. Splitting I k , j I_{k,j} I k , j into its two offspring I k + 1 , 2 j I_{k+1,2j} I k + 1 , 2 j and I k + 1 , 2 j + 1 I_{k+1,2j+1} I k + 1 , 2 j + 1 , we condition on the joint event that each X j , i X_{j,i} X j , i lies in a prescribed half, i.e., on the entire vector of membership indicators 1 { X j , i ∈ I k + 1 , 2 j } 0 ≤ j < 2 k , 1 ≤ i ≤ k \boldsymbol{1}_{\{X_{j,i}\in I_{k+1,2j}\}}{}_{0\le j<2^k,\ 1\le i\le k} 1 { X j , i ∈ I k + 1 , 2 j } 0 ≤ j < 2 k , 1 ≤ i ≤ k . By the induction hypothesis, the old points remain conditionally independent and uniform on their specified halves.
Under this conditioning, the counts p r p_r p r and q r q_r q r are fixed. The list in each I k + 1 , r I_{k+1,r} I k + 1 , r contains p r p_r p r old points followed by the first q r q_r q r new candidates. The new candidates remain independent of one another and of the old points. All entries in the completed lists are therefore conditionally independent and uniform on their respective cells.
For arbitrary Borel sets H r , i ⊆ I k + 1 , r H_{r,i}\subseteq I_{k+1,r} H r , i ⊆ I k + 1 , r , 0 ≤ r < 2 k + 1 0\le r<2^{k+1} 0 ≤ r < 2 k + 1 , 1 ≤ i ≤ k + 1 1\le i\le k+1 1 ≤ i ≤ k + 1 , the conditional probability that the i i i -th point in I k + 1 , r I_{k+1,r} I k + 1 , r belongs to H r , i H_{r,i} H r , i for every r , i r,i r , i is ∏ r , i λ ( H r , i ) / λ ( I k + 1 , r ) \prod_{r,i}\lambda(H_{r,i})/\lambda(I_{k+1,r}) ∏ r , i λ ( H r , i ) / λ ( I k + 1 , r ) . This expression does not depend on the specified halves. By the law of total probability, the same formula holds without conditioning. This completes the induction and hence establishes the asserted equality of joint count distributions. □ \square □
Ordering the random points
The construction described above produces the point sets P k P_k P k but does not specify the order in which their points are arranged. To obtain a low-discrepancy sequence Y 1 , Y 2 , Y 3 , … Y_1,Y_2,Y_3,\ldots Y 1 , Y 2 , Y 3 , … , we order these points recursively.
We set Y 1 = Z 1 Y_1=Z_1 Y 1 = Z 1 and Y 2 = Z 2 Y_2=Z_2 Y 2 = Z 2 to be the two points in P 1 P_1 P 1 . Suppose that the points of P k P_k P k have been ordered as Y 1 , … , Y N k Y_1,\ldots,Y_{N_k} Y 1 , … , Y N k . We retain this order and specify the order in which the Q k Q_k Q k new points are appended.
Consider the dyadic tree with root I 0 , 0 = [ 0 , 1 ) I_{0,0}=[0,1) I 0 , 0 = [ 0 , 1 ) , and leaves I k + 1 , 0 , … , I k + 1 , 2 k + 1 − 1 I_{k+1,0},\ldots,I_{k+1,2^{k+1}-1} I k + 1 , 0 , … , I k + 1 , 2 k + 1 − 1 at depth k + 1 k+1 k + 1 . For each node J J J , we define its quota by q ( J ) = ∑ I k + 1 , r ⊆ J q r q(J)=\sum_{I_{k+1,r}\subseteq J}q_r q ( J ) = ∑ I k + 1 , r ⊆ J q r , and thus q ( J ) q(J) q ( J ) is the total number of new points added to J J J during the current transition. In particular, q ( I k + 1 , r ) = q r q(I_{k+1,r})=q_r q ( I k + 1 , r ) = q r and q ( [ 0 , 1 ) ) = Q k q([0,1))=Q_k q ([ 0 , 1 )) = Q k .
At an internal node J J J , we write J L J_L J L and J R J_R J R for its left and right offspring, respectively. We associate with J J J the (upper) mechanical word χ J = ( χ J ( 1 ) , … , χ J ( q ( J ) ) ) ∈ { 0 , 1 } q ( J ) \chi_J=(\chi_J(1),\ldots,\chi_J(q(J)))\in\{0,1\}^{q(J)} χ J = ( χ J ( 1 ) , … , χ J ( q ( J ))) ∈ { 0 , 1 } q ( J ) of slope q ( J R ) / q ( J ) q(J_R)/q(J) q ( J R ) / q ( J ) , characterized by
χ J ( n ) = ⌈ n q ( J R ) q ( J ) ⌉ − ⌈ ( n − 1 ) q ( J R ) q ( J ) ⌉ ( 1 ≤ n ≤ q ( J ) ) . \chi_J(n)=\left\lceil\frac{nq(J_R)}{q(J)}\right\rceil-\left\lceil\frac{(n-1)q(J_R)}{q(J)}\right\rceil\qquad(1\le n\le q(J)). χ J ( n ) = ⌈ q ( J ) n q ( J R ) ⌉ − ⌈ q ( J ) ( n − 1 ) q ( J R ) ⌉ ( 1 ≤ n ≤ q ( J )) .
In the following, we issue Q k Q_k Q k requests in total; each request starts at the root, descends along the tree, and eventually lands in some leaf. Exactly q r q_r q r requests land in I k + 1 , r I_{k+1,r} I k + 1 , r . The order in which the requests reach the leaves will determine the order in which the new points are placed.
Every request starts at the root. The v v v -th request reads the v v v -th symbol χ I 0 , 0 ( v ) \chi_{I_{0,0}}(v) χ I 0 , 0 ( v ) of the mechanical word χ I 0 , 0 \chi_{I_{0,0}} χ I 0 , 0 : if it is 0, the request descends into the left subtree; if it is 1, into the right subtree. Suppose a request reaches a node J ′ J' J ′ . That node records that it has now been visited v ′ v' v ′ times, and the v ′ v' v ′ -th symbol of χ J ′ \chi_{J'} χ J ′ determines whether the request descends into the left or the right offspring of J ′ J' J ′ . The descent is repeated at every level until the request reaches some leaf I k + 1 , r I_{k+1,r} I k + 1 , r , whence the request is assigned the label r r r .
Reading the labels in the order 1 , 2 , … , Q k 1,2,\ldots,Q_k 1 , 2 , … , Q k of the requests yields
W k = ( ℓ 1 , ℓ 2 , … , ℓ Q k ) ( ℓ n ∈ { 0 , … , 2 k + 1 − 1 } ) . W_k=(\ell_1,\ell_2,\ldots,\ell_{Q_k})\qquad(\ell_n\in\{0,\ldots,2^{k+1}-1\}). W k = ( ℓ 1 , ℓ 2 , … , ℓ Q k ) ( ℓ n ∈ { 0 , … , 2 k + 1 − 1 }) .
The quota of the leaf I k + 1 , r I_{k+1,r} I k + 1 , r is q r q_r q r , meaning that q r q_r q r requests should land in I k + 1 , r I_{k+1,r} I k + 1 , r . This is guaranteed by the mechanical word at each node: in χ J \chi_J χ J , the number of zeros equals the left quota q ( J L ) q(J_L) q ( J L ) and the number of ones equals the right quota q ( J R ) q(J_R) q ( J R ) , so among the requests entering J J J , exactly q ( J L ) q(J_L) q ( J L ) descend left and q ( J R ) q(J_R) q ( J R ) descend right. Applying this level by level, the number of requests reaching each leaf equals the quota of that leaf. Hence
# { n : ℓ n = r } = q r , ∑ r = 0 2 k + 1 − 1 q r = Q k . \#\{n:\ell_n=r\}=q_r,\qquad\sum_{r=0}^{2^{k+1}-1}q_r=Q_k. # { n : ℓ n = r } = q r , r = 0 ∑ 2 k + 1 − 1 q r = Q k .
To determine the order in which the points are finally appended, we need to impose a definite order on the q r q_r q r points that the leaf I k + 1 , r I_{k+1,r} I k + 1 , r contributes to P k + 1 P_{k+1} P k + 1 . Since these q r q_r q r points arise by retaining the first q r q_r q r elements of a larger sample, they already carry a natural order, namely the index order of the sample. The internal ordering of a leaf I k + 1 , r I_{k+1,r} I k + 1 , r is taken to be precisely this index order.
We are ready to append the Q k Q_k Q k new points to the existing sequence Y 1 , … , Y N k Y_1,\ldots,Y_{N_k} Y 1 , … , Y N k . Scan W k W_k W k in the order n = 1 , 2 , … , Q k n=1,2,\ldots,Q_k n = 1 , 2 , … , Q k . Suppose ℓ n = r \ell_n=r ℓ n = r , and suppose this is the w w w -th occurrence of the label r r r in W k W_k W k . Then the w w w -th point of the ordered list carried by I k + 1 , r ∩ ( P k + 1 ∖ P k ) I_{k+1,r}\cap(P_{k+1}\setminus P_k) I k + 1 , r ∩ ( P k + 1 ∖ P k ) is appended to the sequence.
We have thus defined the order of the points in P k + 1 P_{k+1} P k + 1 , which yields the sequence
Y 1 , Y 2 , … , Y N k + 1 . Y_1,Y_2,\ldots,Y_{N_{k+1}}. Y 1 , Y 2 , … , Y N k + 1 .
We remark that each Y n Y_n Y n depends on only finitely many of the candidates Z m Z_m Z m , and is therefore a measurable function of those candidates. The random variables Y n Y_n Y n need not be independent.
Lemma 2.2. For every internal node J J J and an integer 0 ≤ v ≤ q ( J ) 0\leq v\leq q(J) 0 ≤ v ≤ q ( J ) ,
# { 1 ≤ n ≤ v : χ J ( n ) = 0 } = ⌊ v q ( J L ) q ( J ) ⌋ . \#\{1\leq n\leq v:\chi_J(n)=0\}=\left\lfloor\frac{v q(J_L)}{q(J)}\right\rfloor. # { 1 ≤ n ≤ v : χ J ( n ) = 0 } = ⌊ q ( J ) v q ( J L ) ⌋ . Consequently,
∣ # { 1 ≤ n ≤ v : χ J ( n ) = 0 } − v q ( J L ) q ( J ) ∣ < 1. \left|\#\{1\leq n\leq v:\chi_J(n)=0\}-\frac{v q(J_L)}{q(J)}\right|<1. # { 1 ≤ n ≤ v : χ J ( n ) = 0 } − q ( J ) v q ( J L ) < 1. The corresponding errors for the two offspring are negatives of each other.
Proof. This is the balance property of mechanical words; we refer the reader to [8 ] for further details. For the reader’s convenience, we include a short proof.
We readily check that 1 − χ J ( n ) = ⌊ n q ( J L ) / q ( J ) ⌋ − ⌊ ( n − 1 ) q ( J L ) / q ( J ) ⌋ 1-\chi_J(n)=\lfloor nq(J_L)/q(J)\rfloor-\lfloor(n-1)q(J_L)/q(J)\rfloor 1 − χ J ( n ) = ⌊ n q ( J L ) / q ( J )⌋ − ⌊( n − 1 ) q ( J L ) / q ( J )⌋ , and thus
# { 1 ≤ n ≤ v : χ J ( n ) = 0 } = ∑ n = 1 v ( ⌊ n q ( J L ) q ( J ) ⌋ − ⌊ ( n − 1 ) q ( J L ) q ( J ) ⌋ ) = ⌊ v q ( J L ) q ( J ) ⌋ . \#\{1\leq n\leq v:\chi_J(n)=0\}=\sum_{n=1}^{v}\left(\left\lfloor\frac{nq(J_L)}{q(J)}\right\rfloor-\left\lfloor\frac{(n-1)q(J_L)}{q(J)}\right\rfloor\right)=\left\lfloor\frac{vq(J_L)}{q(J)}\right\rfloor. # { 1 ≤ n ≤ v : χ J ( n ) = 0 } = n = 1 ∑ v ( ⌊ q ( J ) n q ( J L ) ⌋ − ⌊ q ( J ) ( n − 1 ) q ( J L ) ⌋ ) = ⌊ q ( J ) v q ( J L ) ⌋ . The remaining assertions follow from the floor bound and the fact that the counts for the two offspring sum to v v v .
When no confusion can arise, we identify a label r ∈ { 0 , … , 2 k + 1 − 1 } r \in\{0,\ldots,2^{k+1}-1\} r ∈ { 0 , … , 2 k + 1 − 1 } with the leaf I k + 1 , r I_{k+1,r} I k + 1 , r it represents, and a set S S S of labels with the union ⋃ r ∈ S I k + 1 , r \bigcup_{r\in S} I_{k+1,r} ⋃ r ∈ S I k + 1 , r of the corresponding leaves. Thus q ( S ) = ∑ r ∈ S q r q(S)=\sum_{r\in S}q_r q ( S ) = ∑ r ∈ S q r ; we also write p ( S ) = ∑ r ∈ S p r p(S)=\sum_{r\in S}p_r p ( S ) = ∑ r ∈ S p r . For 0 ≤ m ≤ Q k 0\le m\le Q_k 0 ≤ m ≤ Q k and 0 ≤ r < 2 k + 1 0\le r<2^{k+1} 0 ≤ r < 2 k + 1 , we put
x r ( m ) = # { 1 ≤ n ≤ m : ℓ n = r } , E r ( m ) = x r ( m ) − m q r Q k . x_r(m)=\#\{1\le n\le m:\ell_n=r\},\qquad E_r(m)=x_r(m)-m\frac{q_r}{Q_k}. x r ( m ) = # { 1 ≤ n ≤ m : ℓ n = r } , E r ( m ) = x r ( m ) − m Q k q r .
Lemma 2.3. For integers m , b m,b m , b with 0 ≤ m ≤ Q k 0\le m\le Q_k 0 ≤ m ≤ Q k and 0 < b ≤ 2 k + 1 0<b\le2^{k+1} 0 < b ≤ 2 k + 1 , we have
∣ ∑ r = 0 b − 1 E r ( m ) ∣ ≤ k + 1. \left|\sum_{r=0}^{b-1}E_r(m)\right|\le k+1. r = 0 ∑ b − 1 E r ( m ) ≤ k + 1. Consequently, for 0 ≤ b 1 < b 2 ≤ 2 k + 1 0\le b_1<b_2\le2^{k+1} 0 ≤ b 1 < b 2 ≤ 2 k + 1 ,
∣ ∑ r = b 1 b 2 − 1 E r ( m ) ∣ ≤ 2 ( k + 1 ) . \left|\sum_{r=b_1}^{b_2-1}E_r(m)\right|\le2(k+1). r = b 1 ∑ b 2 − 1 E r ( m ) ≤ 2 ( k + 1 ) .
Proof. Throughout, requests are those issued during the current transition k → k + 1 k\to k+1 k → k + 1 .
For a node J J J of the dyadic tree introduced earlier, let h ( J ) h(J) h ( J ) be the height of J J J , that is, the number of edges on a path from J J J to a leaf, so that h ( J ) = 0 h(J)=0 h ( J ) = 0 at a leaf and h ( I 0 , 0 ) = k + 1 h(I_{0,0})=k+1 h ( I 0 , 0 ) = k + 1 .
We consider only the requests reaching J J J . Let S S S be an initial segment of the leaf labels below J J J ; thus S S S is either empty, or all labels below J J J , or a set of the form { 0 , … , b − 1 } \{0,\ldots,b-1\} { 0 , … , b − 1 } intersected with the labels below J J J . For 0 ≤ v ≤ q ( J ) 0\le v\le q(J) 0 ≤ v ≤ q ( J ) , let F J ( v , S ) F_J(v,S) F J ( v , S ) be the number of the first v v v such requests that end in a leaf labeled by S S S , minus the ideal count v q ( S ) / q ( J ) v q(S)/q(J) v q ( S ) / q ( J ) :
F J ( v , S ) = # { 1 ≤ n ≤ v : the n -th request reaching J ends in a leaf of S } − v q ( S ) q ( J ) . F_J(v,S)=\#\{1\le n\le v:\text{ the }n\text{-th request reaching }J\text{ ends in a leaf of }S\}-v\frac{q(S)}{q(J)}. F J ( v , S ) = # { 1 ≤ n ≤ v : the n -th request reaching J ends in a leaf of S } − v q ( J ) q ( S ) .
We claim that, for every node J J J , every 0 ≤ v ≤ q ( J ) 0\le v\le q(J) 0 ≤ v ≤ q ( J ) , and every initial segment S S S of the labels below J J J ,
∣ F J ( v , S ) ∣ ≤ h ( J ) . |F_J(v,S)|\le h(J). ∣ F J ( v , S ) ∣ ≤ h ( J ) .
We argue by induction on h ( J ) h(J) h ( J ) . When h ( J ) = 0 h(J)=0 h ( J ) = 0 , i.e., J J J is a leaf, the set S S S is either empty or consists of the single label of J J J . In either case, F J ( v , S ) = 0 F_J(v,S)=0 F J ( v , S ) = 0 .
Let J J J be a node with offspring J L J_L J L and J R J_R J R . Let v 0 v_0 v 0 and v 1 v_1 v 1 be the numbers of the first v v v requests reaching J J J that descend into J L J_L J L and J R J_R J R , respectively, so v 0 + v 1 = v v_0+v_1=v v 0 + v 1 = v . Set δ = v 0 − v q ( J L ) / q ( J ) \delta=v_0-vq(J_L)/q(J) δ = v 0 − v q ( J L ) / q ( J ) . By the balance property established in Lemma 2.2, we have ∣ δ ∣ < 1 |\delta|<1 ∣ δ ∣ < 1 . We distinguish two cases, according to the position of S S S .
Case 1: all leaves labelled by S S S lie below J L J_L J L . Then a request reaching J J J ends in S S S if and only if it descends into J L J_L J L and ends in S S S there. So
F J ( v , S ) = F J L ( v 0 , S ) + v 0 q ( S ) q ( J L ) − v q ( S ) q ( J ) = F J L ( v 0 , S ) + δ q ( S ) q ( J L ) . F_J(v,S)=F_{J_L}(v_0,S)+v_0\frac{q(S)}{q(J_L)}-v\frac{q(S)}{q(J)}
=F_{J_L}(v_0,S)+\delta\frac{q(S)}{q(J_L)}. F J ( v , S ) = F J L ( v 0 , S ) + v 0 q ( J L ) q ( S ) − v q ( J ) q ( S ) = F J L ( v 0 , S ) + δ q ( J L ) q ( S ) .
Case 2: S S S contains all leaves below J L J_L J L . Write S = J L ∪ S 1 S=J_L\cup S_1 S = J L ∪ S 1 , where S 1 S_1 S 1 is an initial segment of the labels below J R J_R J R . A request reaching J J J ends in S S S if and only if it either descends into J L J_L J L , or descends into J R J_R J R and ends in S 1 S_1 S 1 . Hence
F J ( v , S ) = v 0 + F J R ( v 1 , S 1 ) + v 1 q ( S 1 ) q ( J R ) − v q ( J L ) + q ( S 1 ) q ( J ) . F_J(v,S)=v_0+F_{J_R}(v_1,S_1)+v_1\frac{q(S_1)}{q(J_R)}-v\frac{q(J_L)+q(S_1)}{q(J)}. F J ( v , S ) = v 0 + F J R ( v 1 , S 1 ) + v 1 q ( J R ) q ( S 1 ) − v q ( J ) q ( J L ) + q ( S 1 ) .
Using v 1 = v − v 0 v_1=v-v_0 v 1 = v − v 0 and the definition of δ \delta δ , this simplifies to
F J ( v , S ) = F J R ( v 1 , S 1 ) + δ ( 1 − q ( S 1 ) q ( J R ) ) . F_J(v,S)=F_{J_R}(v_1,S_1)+\delta\left(1-\frac{q(S_1)}{q(J_R)}\right). F J ( v , S ) = F J R ( v 1 , S 1 ) + δ ( 1 − q ( J R ) q ( S 1 ) ) .
In both cases, the induction hypothesis applied to the offspring gives
∣ F J ( v , S ) ∣ ≤ ( h ( J ) − 1 ) + ∣ δ ∣ ≤ h ( J ) , |F_J(v,S)|\le(h(J)-1)+|\delta|\le h(J), ∣ F J ( v , S ) ∣ ≤ ( h ( J ) − 1 ) + ∣ δ ∣ ≤ h ( J ) ,
which proves the claim at J J J .
Now taking S = { 0 , 1 , … , b − 1 } S=\{0,1,\ldots,b-1\} S = { 0 , 1 , … , b − 1 } , the labels below the root I 0 , 0 I_{0,0} I 0 , 0 are all leaf labels, so
F I 0 , 0 ( m , S ) = ∑ r = 0 b − 1 x r ( m ) − m ∑ r = 0 b − 1 q r Q k = ∑ r = 0 b − 1 E r ( m ) . F_{I_{0,0}}(m,S)=\sum_{r=0}^{b-1}x_r(m)-m\frac{\sum_{r=0}^{b-1}q_r}{Q_k}
=\sum_{r=0}^{b-1}E_r(m). F I 0 , 0 ( m , S ) = r = 0 ∑ b − 1 x r ( m ) − m Q k ∑ r = 0 b − 1 q r = r = 0 ∑ b − 1 E r ( m ) .
The claim at the root therefore yields
∣ ∑ r = 0 b − 1 E r ( m ) ∣ ≤ h ( I 0 , 0 ) = k + 1 , \left|\sum_{r=0}^{b-1} E_r(m)\right| \le h(I_{0,0}) = k+1, r = 0 ∑ b − 1 E r ( m ) ≤ h ( I 0 , 0 ) = k + 1 ,
which is the first estimate. The second then follows from the triangle inequality.
Discrepancy of every prefix
We calculate the discrepancy of the sequence. To this end, we fix a transition from level k k k to level k + 1 k+1 k + 1 . Recall that N k = k 2 k N_k=k2^k N k = k 2 k and Q k = ( k + 2 ) 2 k Q_k=(k+2)2^k Q k = ( k + 2 ) 2 k are the numbers of old points and new points in the transition, respectively.
Lemma 2.4. For an integer b b b with 0 ≤ b ≤ 2 k + 1 0\le b\le2^{k+1} 0 ≤ b ≤ 2 k + 1 , writing S b = { 0 , … , b − 1 } S_b=\{0,\ldots,b-1\} S b = { 0 , … , b − 1 } , we have
∣ p ( S b ) − N k b 2 k + 1 ∣ ≤ k 2 , (6) \left|p(S_b)-N_k\frac{b}{2^{k+1}}\right|\le\frac{k}{2}, \tag*{(6)} p ( S b ) − N k 2 k + 1 b ≤ 2 k , (6) and
q ( S b ) − Q k b 2 k + 1 = − ( p ( S b ) − N k b 2 k + 1 ) . (7) q(S_b)-Q_k\frac{b}{2^{k+1}}=-\left(p(S_b)-N_k\frac{b}{2^{k+1}}\right). \tag*{(7)} q ( S b ) − Q k 2 k + 1 b = − ( p ( S b ) − N k 2 k + 1 b ) . (7) Proof. Each level-k k k cell contains k k k old points, so
p ( S b ) − N k b 2 k + 1 = { 0 , b = 2 j , p 2 j − k / 2 , b = 2 j + 1. p(S_b)-N_k\frac{b}{2^{k+1}}=
\begin{cases}
0, & b=2j,\\
p_{2j}-k/2, & b=2j+1.
\end{cases} p ( S b ) − N k 2 k + 1 b = { 0 , p 2 j − k /2 , b = 2 j , b = 2 j + 1. Since 0 ≤ p 2 j ≤ k 0\le p_{2j}\le k 0 ≤ p 2 j ≤ k , this yields (2.1); (2.2) is equivalent to the identity p ( S b ) + q ( S b ) = ( k + 1 ) b p(S_b)+q(S_b)=(k+1)b p ( S b ) + q ( S b ) = ( k + 1 ) b .
Proposition 2.5. The sequence Y 1 , Y 2 , … Y_1,Y_2,\ldots Y 1 , Y 2 , … constructed above satisfies
N D N ∗ ≤ 5 2 log 2 log N ( N ≥ 2 ) . ND_N^* \le\frac{5}{2\log2}\log N \qquad(N\ge2). N D N ∗ ≤ 2 log 2 5 log N ( N ≥ 2 ) . Proof. Write N = N k + m N=N_k+m N = N k + m with k ≥ 1 k\ge1 k ≥ 1 and 0 ≤ m ≤ Q k 0\le m\le Q_k 0 ≤ m ≤ Q k . Throughout this section, every integer N N N is assumed to take this form, so that N N N and the pair ( k , m ) (k,m) ( k , m ) determine each other.
For an integer b b b with 0 ≤ b ≤ 2 k + 1 0\le b\le2^{k+1} 0 ≤ b ≤ 2 k + 1 , (2.2) yields
# { 1 ≤ n ≤ N : Y n < b 2 k + 1 } − N b 2 k + 1 = p ( S b ) + ∑ r = 0 b − 1 x r ( m ) − N b 2 k + 1 \#\{1\le n\le N:Y_n<\frac{b}{2^{k+1}}\}-N\frac{b}{2^{k+1}}
=p(S_b)+\sum_{r=0}^{b-1}x_r(m)-N\frac{b}{2^{k+1}} # { 1 ≤ n ≤ N : Y n < 2 k + 1 b } − N 2 k + 1 b = p ( S b ) + r = 0 ∑ b − 1 x r ( m ) − N 2 k + 1 b = ( 1 − m Q k ) ( p ( S b ) − N k b 2 k + 1 ) + ∑ r = 0 b − 1 E r ( m ) . =\left(1-\frac{m}{Q_k}\right)\left(p(S_b)-N_k\frac{b}{2^{k+1}}\right)+\sum_{r=0}^{b-1}E_r(m). = ( 1 − Q k m ) ( p ( S b ) − N k 2 k + 1 b ) + r = 0 ∑ b − 1 E r ( m ) . By Lemma 2.3 and (2.1),
∣ # { 1 ≤ n ≤ N : Y n < b 2 k + 1 } − N b 2 k + 1 ∣ ≤ ( 1 − m Q k ) k 2 + k + 1 ≤ 3 k 2 + 1. (8) \left|\#\{1\le n\le N:Y_n<\frac{b}{2^{k+1}}\}-N\frac{b}{2^{k+1}}\right|
\le\left(1-\frac{m}{Q_k}\right)\frac{k}{2}+k+1
\le\frac{3k}{2}+1. \tag*{(8)} # { 1 ≤ n ≤ N : Y n < 2 k + 1 b } − N 2 k + 1 b ≤ ( 1 − Q k m ) 2 k + k + 1 ≤ 2 3 k + 1. (8) For 0 ≤ t < 1 0\le t<1 0 ≤ t < 1 , choose an integer b b b so that b / 2 k + 1 ≤ t < ( b + 1 ) / 2 k + 1 b/2^{k+1}\le t<(b+1)/2^{k+1} b / 2 k + 1 ≤ t < ( b + 1 ) / 2 k + 1 . Since each level-( k + 1 ) (k+1) ( k + 1 ) cell contains at most k + 1 k+1 k + 1 of the first N N N points, and N ≤ ( k + 1 ) 2 k + 1 N\le(k+1)2^{k+1} N ≤ ( k + 1 ) 2 k + 1 , both # { 1 ≤ n ≤ N : b / 2 k + 1 ≤ Y n < t } \#\{1\le n\le N:b/2^{k+1}\le Y_n<t\} # { 1 ≤ n ≤ N : b / 2 k + 1 ≤ Y n < t } and N ( t − b / 2 k + 1 ) N(t-b/2^{k+1}) N ( t − b / 2 k + 1 ) lie in [ 0 , k + 1 ] [0,k+1] [ 0 , k + 1 ] , so their difference has absolute value at most k + 1 k+1 k + 1 . Together with (2.3) and the exact count at t = 1 t=1 t = 1 , this yields N D N ∗ ≤ 5 k / 2 + 2 ND_N^*\le5k/2+2 N D N ∗ ≤ 5 k /2 + 2 .
For N ≥ 8 N\ge8 N ≥ 8 , we have k ≥ 2 k\ge2 k ≥ 2 and N ≥ k 2 k N\ge k2^k N ≥ k 2 k , and thus
5 k 2 + 2 ≤ 5 k 2 + 5 k 2 log 2 = 5 log k 2 log 2 + 5 2 log 2 = 5 2 log 2 log ( k 2 k ) ≤ 5 2 log 2 log N . \frac{5k}{2}+2\le\frac{5k}{2}+\frac{5k}{2\log2}
=\frac{5\log k}{2\log2}+\frac{5}{2\log2}
=\frac{5}{2\log2}\log(k2^k)\le\frac{5}{2\log2}\log N. 2 5 k + 2 ≤ 2 5 k + 2 log 2 5 k = 2 log 2 5 log k + 2 log 2 5 = 2 log 2 5 log ( k 2 k ) ≤ 2 log 2 5 log N . For 2 ≤ N ≤ 7 2\le N\le7 2 ≤ N ≤ 7 , the bound N D N ∗ ≤ N ≤ 5 log N / ( 2 log 2 ) ND_N^*\le N\le5\log N/(2\log2) N D N ∗ ≤ N ≤ 5 log N / ( 2 log 2 ) completes the proof.
Conditional pair-correlation estimates
We estimate the conditional expectation of N R N ( s ) NR_N(s) N R N ( s ) .
Lemma 2.6. For k ≥ 1 k \ge1 k ≥ 1 and 0 ≤ m ≤ Q k 0 \le m \le Q_k 0 ≤ m ≤ Q k , we have
∑ r = 0 2 k + 1 − 1 E r ( m ) 2 ≤ 5 ⋅ 2 k . \sum_{r=0}^{2^{k+1}-1} E_r(m)^2 \le5 \cdot2^k. r = 0 ∑ 2 k + 1 − 1 E r ( m ) 2 ≤ 5 ⋅ 2 k . Proof. For 0 ≤ j < 2 k 0 \le j < 2^k 0 ≤ j < 2 k , let v j ( m ) v_j(m) v j ( m ) be the number of visits to I k , j I_{k,j} I k , j among the first m m m requests. Since q 2 j + q 2 j + 1 = k + 2 q_{2j}+q_{2j+1}=k+2 q 2 j + q 2 j + 1 = k + 2 for every j j j , requests alternate between the two offspring at each node of level less than k k k , giving
v j ( m ) ∈ { ⌊ m 2 k ⌋ , ⌈ m 2 k ⌉ } , ∣ v j ( m ) − m 2 k ∣ < 1. v_j(m) \in\left\{\left\lfloor\frac{m}{2^k}\right\rfloor,\left\lceil\frac{m}{2^k}\right\rceil\right\}, \qquad\left|v_j(m)-\frac{m}{2^k}\right|<1. v j ( m ) ∈ { ⌊ 2 k m ⌋ , ⌈ 2 k m ⌉ } , v j ( m ) − 2 k m < 1. By Lemma 2.2, for r ∈ { 2 j , 2 j + 1 } r\in\{2j,2j+1\} r ∈ { 2 j , 2 j + 1 } , we have that ∣ x r ( m ) − v j ( m ) q r / ( k + 2 ) ∣ < 1 \left|x_r(m)-v_j(m)q_r/(k+2)\right|<1 ∣ x r ( m ) − v j ( m ) q r / ( k + 2 ) ∣ < 1 , and thus
∣ E r ( m ) ∣ ≤ ∣ x r ( m ) − q r k + 2 v j ( m ) ∣ + q r k + 2 ∣ v j ( m ) − m 2 k ∣ < 1 + q r k + 2 . |E_r(m)|\le\left|x_r(m)-\frac{q_r}{k+2}v_j(m)\right|+\frac{q_r}{k+2}\left|v_j(m)-\frac{m}{2^k}\right|<1+\frac{q_r}{k+2}. ∣ E r ( m ) ∣ ≤ x r ( m ) − k + 2 q r v j ( m ) + k + 2 q r v j ( m ) − 2 k m < 1 + k + 2 q r . Hence
E 2 j ( m ) 2 + E 2 j + 1 ( m ) 2 < ( 1 + q 2 j k + 2 ) 2 + ( 1 + q 2 j + 1 k + 2 ) 2 ≤ 5. E_{2j}(m)^2+E_{2j+1}(m)^2<\left(1+\frac{q_{2j}}{k+2}\right)^2+\left(1+\frac{q_{2j+1}}{k+2}\right)^2\le5. E 2 j ( m ) 2 + E 2 j + 1 ( m ) 2 < ( 1 + k + 2 q 2 j ) 2 + ( 1 + k + 2 q 2 j + 1 ) 2 ≤ 5. Summing over the 2 k 2^k 2 k pairs completes the proof.
By Lemma 2.1, the variables p 2 j p_{2j} p 2 j , 0 ≤ j < 2 k 0\le j<2^k 0 ≤ j < 2 k , are independent, with
p 2 j ∼ Binomial ( k , 1 / 2 ) , p 2 j + 1 = k − p 2 j . p_{2j}\sim\operatorname{Binomial}(k,1/2),\qquad p_{2j+1}=k-p_{2j}. p 2 j ∼ Binomial ( k , 1/2 ) , p 2 j + 1 = k − p 2 j . For 0 ≤ m ≤ Q k 0\le m\le Q_k 0 ≤ m ≤ Q k , recalling N = N k + m N=N_k+m N = N k + m , we define, for 0 ≤ r < 2 k + 1 0\le r<2^{k+1} 0 ≤ r < 2 k + 1 ,
C r ( m ) = p r + x r ( m ) , e r ( m ) = C r ( m ) − N 2 k + 1 , C_r(m)=p_r+x_r(m),\qquad e_r(m)=C_r(m)-\frac{N}{2^{k+1}}, C r ( m ) = p r + x r ( m ) , e r ( m ) = C r ( m ) − 2 k + 1 N , where C r ( m ) C_r(m) C r ( m ) is the number of points in I k + 1 , r I_{k+1,r} I k + 1 , r among the first N N N terms and e r ( m ) e_r(m) e r ( m ) is its deviation from N / 2 k + 1 N/2^{k+1} N / 2 k + 1 . Define the event
A k = { ∑ r = 0 2 k + 1 − 1 ( p r − k 2 ) 2 ≤ k 2 k + 1 } . \mathcal{A}_k=\left\{\sum_{r=0}^{2^{k+1}-1}\left(p_r-\frac{k}{2}\right)^2\le k2^{k+1}\right\}. A k = ⎩ ⎨ ⎧ r = 0 ∑ 2 k + 1 − 1 ( p r − 2 k ) 2 ≤ k 2 k + 1 ⎭ ⎬ ⎫ . Lemma 2.7. For k ≥ 1 k\ge1 k ≥ 1 , we have
P ( A k c ) ≤ 1 9 ⋅ 2 k − 1 . (9) \mathbb{P}(\mathcal{A}_k^c)\le\frac{1}{9\cdot2^{k-1}}. \tag*{(9)} P ( A k c ) ≤ 9 ⋅ 2 k − 1 1 . (9) On A k \mathcal{A}_k A k , we have, uniformly in 0 ≤ m ≤ Q k 0\le m\le Q_k 0 ≤ m ≤ Q k ,
∑ r = 0 2 k + 1 − 1 e r ( m ) 2 ≤ k 2 k + 4 . \sum_{r=0}^{2^{k+1}-1}e_r(m)^2\le k2^{k+4}. r = 0 ∑ 2 k + 1 − 1 e r ( m ) 2 ≤ k 2 k + 4 . Proof. Set
X = ∑ j = 0 2 k − 1 ( p 2 j − k 2 ) 2 . X=\sum_{j=0}^{2^k-1}\left(p_{2j}-\frac{k}{2}\right)^2. X = j = 0 ∑ 2 k − 1 ( p 2 j − 2 k ) 2 . Since p 2 j ∼ Binomial ( k , 1 / 2 ) p_{2j}\sim\operatorname{Binomial}(k,1/2) p 2 j ∼ Binomial ( k , 1/2 ) , a direct calculation yields
E [ ( p 2 j − k 2 ) 2 ] = k 4 , E [ ( p 2 j − k 2 ) 4 ] = 3 k 2 16 − k 8 , \mathbb{E}\left[\left(p_{2j}-\frac{k}{2}\right)^2\right]=\frac{k}{4},\qquad\mathbb{E}\left[\left(p_{2j}-\frac{k}{2}\right)^4\right]=\frac{3k^2}{16}-\frac{k}{8}, E [ ( p 2 j − 2 k ) 2 ] = 4 k , E [ ( p 2 j − 2 k ) 4 ] = 16 3 k 2 − 8 k , and hence
Var ( ( p 2 j − k 2 ) 2 ) = k ( k − 1 ) 8 ≤ k 2 8 . \operatorname{Var}\left(\left(p_{2j}-\frac{k}{2}\right)^2\right)=\frac{k(k-1)}{8}\le\frac{k^2}{8}. Var ( ( p 2 j − 2 k ) 2 ) = 8 k ( k − 1 ) ≤ 8 k 2 .
The independence property then gives E X = k 2 k − 2 \mathbb{E}X=k2^{k-2} E X = k 2 k − 2 and Var ( X ) ≤ k 2 k − 3 \operatorname{Var}(X)\le k2^{k-3} Var ( X ) ≤ k 2 k − 3 . Since p 2 j + 1 = k − p 2 j p_{2j+1}=k-p_{2j} p 2 j + 1 = k − p 2 j , we see that ∑ r = 0 2 k + 1 − 1 ( p r − k / 2 ) 2 = 2 X \sum_{r=0}^{2^{k+1}-1}(p_r-k/2)^2=2X ∑ r = 0 2 k + 1 − 1 ( p r − k /2 ) 2 = 2 X , and thus X − E X > 3 k 2 k − 2 X-\mathbb{E}X>3k2^{k-2} X − E X > 3 k 2 k − 2 on A k c A_k^c A k c . Chebyshev’s inequality then yields
P ( A k c ) ≤ k 2 k − 3 ( 3 k 2 k − 2 ) 2 = 1 9 ⋅ 2 k − 1 . \mathbb{P}(A_k^c)\le\frac{k2^{k-3}}{(3k2^{k-2})^2}=\frac{1}{9\cdot2^{k-1}}. P ( A k c ) ≤ ( 3 k 2 k − 2 ) 2 k 2 k − 3 = 9 ⋅ 2 k − 1 1 .
As in Lemma 2.4, we have q r − Q k / 2 k + 1 = − ( p r − k / 2 ) q_r-Q_k/2^{k+1}=-(p_r-k/2) q r − Q k / 2 k + 1 = − ( p r − k /2 ) . Therefore, by the definitions of e r ( m ) e_r(m) e r ( m ) and E r ( m ) E_r(m) E r ( m ) , we obtain
e r ( m ) = ( 1 − m Q k ) ( p r − k 2 ) + E r ( m ) . e_r(m)=\left(1-\frac{m}{Q_k}\right)\left(p_r-\frac{k}{2}\right)+E_r(m). e r ( m ) = ( 1 − Q k m ) ( p r − 2 k ) + E r ( m ) .
For 0 ≤ m ≤ Q k 0\le m\le Q_k 0 ≤ m ≤ Q k , Lemma 2.6 and the elementary inequality ( a + b ) 2 ≤ 2 ( a 2 + b 2 ) (a+b)^2\le2(a^2+b^2) ( a + b ) 2 ≤ 2 ( a 2 + b 2 ) imply, on A k A_k A k ,
∑ r = 0 2 k + 1 − 1 e r ( m ) 2 ≤ 2 ( k 2 k + 1 + 5 ⋅ 2 k ) < k 2 k + 4 . \sum_{r=0}^{2^{k+1}-1}e_r(m)^2\le2(k2^{k+1}+5\cdot2^k)<k2^{k+4}. r = 0 ∑ 2 k + 1 − 1 e r ( m ) 2 ≤ 2 ( k 2 k + 1 + 5 ⋅ 2 k ) < k 2 k + 4 .
Let G k = σ ( p 0 , … , p 2 k + 1 − 1 ) ⊆ F \mathcal{G}_k=\sigma(p_0,\ldots,p_{2^{k+1}-1})\subseteq\mathcal{F} G k = σ ( p 0 , … , p 2 k + 1 − 1 ) ⊆ F be the σ \sigma σ -algebra generated by the old-point counts in I k + 1 , 0 , … , I k + 1 , 2 k + 1 − 1 I_{k+1,0},\ldots,I_{k+1,2^{k+1}-1} I k + 1 , 0 , … , I k + 1 , 2 k + 1 − 1 . These counts determine q r = k + 1 − p r q_r=k+1-p_r q r = k + 1 − p r and the order of the new points. For each integer 0 ≤ m ≤ Q k 0\le m\le Q_k 0 ≤ m ≤ Q k , conditioning on G k \mathcal{G}_k G k therefore fixes, for each of the first m m m new points, both the cell containing it and its candidate index, and hence the counts x r ( m ) x_r(m) x r ( m ) and C r ( m ) C_r(m) C r ( m ) .
Lemma 2.8. Fix 0 ≤ m ≤ Q k 0\le m\le Q_k 0 ≤ m ≤ Q k , and N = N k + m N=N_k+m N = N k + m . Conditional on G k \mathcal{G}_k G k , the counts of Y 1 , … , Y N Y_1,\ldots,Y_N Y 1 , … , Y N in any finite family of Borel subsets of [ 0 , 1 ) [0,1) [ 0 , 1 ) have the same joint distribution as the corresponding counts obtained by sampling C r ( m ) C_r(m) C r ( m ) independent uniform points in each I k + 1 , r I_{k+1,r} I k + 1 , r , independently across cells.
Proof. By Lemma 2.1 and the conditioning argument in its proof, conditional on G k \mathcal{G}_k G k , the joint count distribution of the old points is that obtained from p r p_r p r independent uniform points in each I k + 1 , r I_{k+1,r} I k + 1 , r , independently across cells.
The new candidates are independent of all old points. Given G k \mathcal{G}_k G k , the first m m m new points include the first x r ( m ) x_r(m) x r ( m ) candidates in I k + 1 , r I_{k+1,r} I k + 1 , r , with x r ( m ) x_r(m) x r ( m ) fixed. Adjoining these candidates proves the assertion, since p r + x r ( m ) = C r ( m ) p_r+x_r(m)=C_r(m) p r + x r ( m ) = C r ( m ) .
Fix s > 0 s>0 s > 0 . Since N = N k + m ≥ k 2 k N=N_k+m\ge k2^k N = N k + m ≥ k 2 k ,
a : = s / N 1 / 2 k + 1 ≤ 2 s k ⟶ 0 ( N ⟶ ∞ ) . a:=\frac{s/N}{1/2^{k+1}}\le\frac{2s}{k}\longrightarrow0\qquad(N\longrightarrow\infty). a := 1/ 2 k + 1 s / N ≤ k 2 s ⟶ 0 ( N ⟶ ∞ ) .
Hence, for all sufficiently large N N N , every pair counted by R N ( s ) R_N(s) R N ( s ) lies either in the same cell or in two adjacent cells on T \mathbb{T} T . In the latter case we say that the pair crosses a boundary, by which we mean the common endpoint shared by two adjacent cells on T \mathbb{T} T ; there are 2 k + 1 2^{k+1} 2 k + 1 such boundaries.
Lemma 2.9. Whenever a < 1 a<1 a < 1 , we have
E [ N R N ( s ) ∣ G k ] = ( 2 a − a 2 ) ∑ r = 0 2 k + 1 − 1 C r ( m ) ( C r ( m ) − 1 ) + a 2 ∑ r = 0 2 k + 1 − 1 C r ( m ) C r + 1 ( m ) . (10) \mathbb{E}\left[N R_N(s)\mid\mathcal{G}_k\right]=(2a-a^2)\sum_{r=0}^{2^{k+1}-1}C_r(m)(C_r(m)-1)
+a^2\sum_{r=0}^{2^{k+1}-1}C_r(m)C_{r+1}(m). \tag*{(10)} E [ N R N ( s ) ∣ G k ] = ( 2 a − a 2 ) r = 0 ∑ 2 k + 1 − 1 C r ( m ) ( C r ( m ) − 1 ) + a 2 r = 0 ∑ 2 k + 1 − 1 C r ( m ) C r + 1 ( m ) . (10) where the cell indices are interpreted modulo 2 k + 1 2^{k+1} 2 k + 1 .
Proof. Since N R N ( s ) N R_N(s) N R N ( s ) is unchanged by permuting the first N N N points, Lemma 2.8 allows us to compute its conditional expectation using independent uniform samples, with C r ( m ) C_r(m) C r ( m ) points in each I k + 1 , r I_{k+1,r} I k + 1 , r .
For two independent uniform points in the same cell, rescaling the cell to [ 0 , 1 ) [0,1) [ 0 , 1 ) gives the probability 2 a − a 2 2a-a^2 2 a − a 2 . There are C r ( m ) ( C r ( m ) − 1 ) C_r(m)(C_r(m)-1) C r ( m ) ( C r ( m ) − 1 ) ordered pairs of terms in I k + 1 , r I_{k+1,r} I k + 1 , r with different indices, giving the first term on the right-hand side of (2.5). For an ordered pair that crosses a boundary, we interchange the two points if necessary, so that the first lies in the left cell and the second in the right cell, and then rescale the two adjacent cells to [ 0 , 1 ) [0,1) [ 0 , 1 ) and [ 1 , 2 ) [1,2) [ 1 , 2 ) . We thus see that the probability that the pair satisfies the distance condition is a 2 / 2 a^2/2 a 2 /2 . There are 2 C r ( m ) C r + 1 ( m ) 2C_r(m)C_{r+1}(m) 2 C r ( m ) C r + 1 ( m ) ordered pairs across a boundary, so their conditional expected contribution is
2 C r ( m ) C r + 1 ( m ) a 2 2 = a 2 C r ( m ) C r + 1 ( m ) . 2C_r(m)C_{r+1}(m)\frac{a^2}{2}=a^2C_r(m)C_{r+1}(m). 2 C r ( m ) C r + 1 ( m ) 2 a 2 = a 2 C r ( m ) C r + 1 ( m ) .
Summing over the 2 k + 1 2^{k+1} 2 k + 1 boundaries gives the second term. □ \square □
Almost-sure Poissonian pair correlation
We prove that ( Y n ( ω ) ) n ≥ 1 (Y_n(\omega))_{n\geq1} ( Y n ( ω ) ) n ≥ 1 has PPC for P \mathbb{P} P -almost every ω ∈ Ω \omega\in\Omega ω ∈ Ω .
Lemma 2.8 identifies the conditional distribution of the first N N N points given G k \mathcal{G}_k G k with the distribution obtained by sampling C r ( m ) C_r(m) C r ( m ) independent uniform points in each I k + 1 , r I_{k+1,r} I k + 1 , r , independently across cells. Since s / N ≤ 2 − ( k + 2 ) s/N\leq2^{-(k+2)} s / N ≤ 2 − ( k + 2 ) , moving one point within its cell can affect only pairs containing that point and another point in the same cell or an adjacent cell. Each cell contains at most k + 1 k+1 k + 1 points, so at most 6 ( k + 1 ) 6(k+1) 6 ( k + 1 ) ordered-pair indicators can change. Thus changing one point changes R N ( s ) R_N(s) R N ( s ) by at most 6 ( k + 1 ) / N 6(k+1)/N 6 ( k + 1 ) / N . Applying McDiarmid’s inequality [10 ] to these independent samples and using the equality of conditional distributions gives, for every ε > 0 \varepsilon>0 ε > 0 ,
P ( ∣ R N ( s ) − E [ R N ( s ) ∣ G k ] ∣ > ε ∣ G k ) ≤ 2 exp ( − ε 2 N 18 ( k + 1 ) 2 ) . (11) \mathbb{P}\left(\left|R_N(s)-\mathbb{E}[R_N(s)\mid\mathcal{G}_k]\right|>\varepsilon\mid\mathcal{G}_k\right)\leq2\exp\left(-\frac{\varepsilon^2N}{18(k+1)^2}\right). \tag*{(11)} P ( ∣ R N ( s ) − E [ R N ( s ) ∣ G k ] ∣ > ε ∣ G k ) ≤ 2 exp ( − 18 ( k + 1 ) 2 ε 2 N ) . (11)
Taking expectations gives the same bound for the unconditional probability. Therefore
∑ k ≥ 4 s ∑ N = N k N k + 1 P ( ∣ R N ( s ) − E [ R N ( s ) ∣ G k ] ∣ > ε ) ≤ 2 ∑ k ≥ 4 s ( Q k + 1 ) exp ( − ε 2 N k 18 ( k + 1 ) 2 ) < ∞ . \sum_{k\geq4s}\sum_{N=N_k}^{N_{k+1}}\mathbb{P}\left(\left|R_N(s)-\mathbb{E}[R_N(s)\mid\mathcal{G}_k]\right|>\varepsilon\right)
\leq2\sum_{k\geq4s}(Q_k+1)\exp\left(-\frac{\varepsilon^2N_k}{18(k+1)^2}\right)<\infty. k ≥ 4 s ∑ N = N k ∑ N k + 1 P ( ∣ R N ( s ) − E [ R N ( s ) ∣ G k ] ∣ > ε ) ≤ 2 k ≥ 4 s ∑ ( Q k + 1 ) exp ( − 18 ( k + 1 ) 2 ε 2 N k ) < ∞.
By the Borel–Cantelli lemma, we deduce that
R N ( s ) − E [ R N ( s ) ∣ G k ] → 0 almost surely as N → ∞ , (12) R_N(s)-\mathbb{E}[R_N(s)\mid\mathcal{G}_k]\to0\quad\text{almost surely as }N\to\infty, \tag*{(12)} R N ( s ) − E [ R N ( s ) ∣ G k ] → 0 almost surely as N → ∞ , (12)
where k = k ( N ) k=k(N) k = k ( N ) is the unique integer with N k ≤ N < N k + 1 N_k\leq N<N_{k+1} N k ≤ N < N k + 1 . Moreover, (9) gives ∑ k P ( A k c ) < ∞ \sum_k\mathbb{P}(A_k^c)<\infty ∑ k P ( A k c ) < ∞ . Applying the Borel–Cantelli lemma once more, we obtain that A k A_k A k holds for all sufficiently large k k k , almost surely.
Substituting C r ( m ) = N / 2 k + 1 + e r ( m ) C_r(m)=N/2^{k+1}+e_r(m) C r ( m ) = N / 2 k + 1 + e r ( m ) into (10) , and using ∑ r e r ( m ) = 0 \sum_r e_r(m)=0 ∑ r e r ( m ) = 0 and the Cauchy–Schwarz inequality ∣ ∑ r e r ( m ) e r + 1 ( m ) ∣ ≤ ∑ r e r ( m ) 2 \left|\sum_r e_r(m)e_{r+1}(m)\right|\leq\sum_r e_r(m)^2 ∣ ∑ r e r ( m ) e r + 1 ( m ) ∣ ≤ ∑ r e r ( m ) 2 , we obtain that, on A k A_k A k ,
∣ E [ R N ( s ) ∣ G k ] − 2 s ∣ ≤ 2 a ( 1 + 1 N ∑ r e r ( m ) 2 ) ≤ 34 a ≤ 68 s k . (13) \left|\mathbb{E}[R_N(s)\mid\mathcal{G}_k]-2s\right|\leq2a\left(1+\frac{1}{N}\sum_r e_r(m)^2\right)\leq34a\leq\frac{68s}{k}. \tag*{(13)} ∣ E [ R N ( s ) ∣ G k ] − 2 s ∣ ≤ 2 a ( 1 + N 1 r ∑ e r ( m ) 2 ) ≤ 34 a ≤ k 68 s . (13)
The above estimate uses 0 < a ≤ 2 s / k ≤ 1 / 2 0<a\leq2s/k\leq1/2 0 < a ≤ 2 s / k ≤ 1/2 and N − 1 ∑ r e r ( m ) 2 ≤ 16 N^{-1}\sum_r e_r(m)^2\leq16 N − 1 ∑ r e r ( m ) 2 ≤ 16 . The second bound follows from Lemma 2.7 together with N ≥ N k N\geq N_k N ≥ N k .
Since A k A_k A k holds almost surely for all sufficiently large k k k , and since (13) holds on A k A_k A k , we conclude that almost surely,
∣ E [ R N ( s ) ∣ G k ] − 2 s ∣ ≤ 68 s k → 0. \left|\mathbb{E}[R_N(s)\mid\mathcal{G}_k]-2s\right|\leq\frac{68s}{k}\to0. ∣ E [ R N ( s ) ∣ G k ] − 2 s ∣ ≤ k 68 s → 0.
Combining this with (12) yields R N ( s ) → 2 s R_N(s)\to2s R N ( s ) → 2 s almost surely. Intersecting the corresponding probability-one events over the countable set s ∈ Q > 0 s\in\mathbb{Q}_{>0} s ∈ Q > 0 , and using the monotonicity of R N R_N R N in s s s to pass from rational to real s s s , we obtain PPC almost surely.
Deterministic selection
We select the candidate points by a deterministic conditional-expectation rule; see Raghavan [12 ] for the method behind it.
For k ≥ 1 k \ge1 k ≥ 1 , put
L k = ⌊ log 2 k ⌋ , S k = { p q : 1 ≤ p , q ≤ L k , p , q ∈ N } , η k = k − 1 / 4 , L_k = \lfloor\log_2 k \rfloor,\qquad S_k = \left\{\frac{p}{q}:1 \le p,q \le L_k,\ p,q \in\mathbb{N}\right\},\qquad\eta_k = k^{-1/4}, L k = ⌊ log 2 k ⌋ , S k = { q p : 1 ≤ p , q ≤ L k , p , q ∈ N } , η k = k − 1/4 ,
and define
D k = ⋃ N k ≤ N < N k + 1 ⋃ s ∈ S k { ∣ R N ( s ) − 2 s ∣ > η k } . D_k = \bigcup_{N_k \le N < N_{k+1}} \bigcup_{s \in S_k} \left\{\lvert R_N(s)-2s\rvert> \eta_k\right\}. D k = N k ≤ N < N k + 1 ⋃ s ∈ S k ⋃ { ∣ R N ( s ) − 2 s ∣ > η k } .
Take k k k sufficiently large, say k ≥ K 0 k \ge K_0 k ≥ K 0 , that L k ≤ k / 4 L_k \le k/4 L k ≤ k /4 and 68 L k / k ≤ η k / 2 68L_k/k \le\eta_k/2 68 L k / k ≤ η k /2 . Then, by (13) , for N k ≤ N < N k + 1 N_k \le N < N_{k+1} N k ≤ N < N k + 1 and s ∈ S k s \in S_k s ∈ S k , we have, on A k A_k A k ,
∣ E [ R N ( s ) ∣ G k ] − 2 s ∣ ≤ η k 2 . \left\lvert\mathbb{E}[R_N(s)\mid\mathcal{G}_k]-2s\right\rvert\le\frac{\eta_k}{2}. ∣ E [ R N ( s ) ∣ G k ] − 2 s ∣ ≤ 2 η k .
Since A k ∈ G k A_k \in\mathcal{G}_k A k ∈ G k , applying (11) with ϵ = η k / 2 \epsilon=\eta_k/2 ϵ = η k /2 , multiplying by 1 A k \mathbf{1}_{A_k} 1 A k , and taking expectations, we obtain
P ( A k ∩ { ∣ R N ( s ) − 2 s ∣ > η k } ) ≤ 2 exp ( − η k 2 N 72 ( k + 1 ) 2 ) . \mathbb{P}\left(A_k \cap\{\lvert R_N(s)-2s\rvert>\eta_k\}\right) \le2\exp\left(-\frac{\eta_k^2N}{72(k+1)^2}\right). P ( A k ∩ {∣ R N ( s ) − 2 s ∣ > η k } ) ≤ 2 exp ( − 72 ( k + 1 ) 2 η k 2 N ) .
Splitting according to A k A_k A k and using the union bound, we obtain
P ( D k ) ≤ P ( A k c ) + ∑ N = N k N k + 1 − 1 ∑ s ∈ S k P ( A k ∩ { ∣ R N ( s ) − 2 s ∣ > η k } ) ≤ 4 9 ⋅ 2 k + 1 + 2 L k 2 Q k exp ( − η k 2 N k 72 ( k + 1 ) 2 ) . \begin{aligned}
\mathbb{P}(D_k)
&\le\mathbb{P}(A_k^{\mathrm{c}})+\sum_{N=N_k}^{N_{k+1}-1}\sum_{s\in S_k}\mathbb{P}\left(A_k\cap\{\lvert R_N(s)-2s\rvert>\eta_k\}\right)\\
&\le\frac{4}{9\cdot2^{k+1}}+2L_k^2Q_k\exp\left(-\frac{\eta_k^2N_k}{72(k+1)^2}\right).
\end{aligned} P ( D k ) ≤ P ( A k c ) + N = N k ∑ N k + 1 − 1 s ∈ S k ∑ P ( A k ∩ {∣ R N ( s ) − 2 s ∣ > η k } ) ≤ 9 ⋅ 2 k + 1 4 + 2 L k 2 Q k exp ( − 72 ( k + 1 ) 2 η k 2 N k ) .
Since η k 2 N k / ( k + 1 ) 2 ≍ 2 k / k 3 / 2 \eta_k^2N_k/(k+1)^2 \asymp2^k/k^{3/2} η k 2 N k / ( k + 1 ) 2 ≍ 2 k / k 3/2 , the bound is summable in k k k . Let K 1 ≥ K 0 K_1 \ge K_0 K 1 ≥ K 0 be the least positive integer such that
∑ k ≥ K 1 P ( D k ) < 1 / 2. \sum_{k\ge K_1}\mathbb{P}(D_k)<1/2. k ≥ K 1 ∑ P ( D k ) < 1/2.
For the candidate Z ν Z_\nu Z ν assigned to I b ν , r ν I_{b_\nu,r_\nu} I b ν , r ν , write
Z ν = 2 − b ν ( r ν + ∑ j ≥ 1 ξ ν , j 2 − j ) . Z_\nu=2^{-b_\nu}\left(r_\nu+\sum_{j\ge1}\xi_{\nu,j}2^{-j}\right). Z ν = 2 − b ν ( r ν + j ≥ 1 ∑ ξ ν , j 2 − j ) .
The first b ν b_\nu b ν binary digits are fixed by the assigned cell, and ξ ν , j \xi_{\nu,j} ξ ν , j is the j j j -th subsequent binary digit. We refer to all the ξ ν , j \xi_{\nu,j} ξ ν , j as the free binary digits of Z ν Z_\nu Z ν . Under P \mathbb{P} P , all the free digits ( ξ ν , j ) ν , j ≥ 1 (\xi_{\nu,j})_{\nu,j\ge1} ( ξ ν , j ) ν , j ≥ 1 are independent and take the values 0 0 0 and 1 1 1 with equal probability. Arrange these digits ( ξ ν , j ) ν , j ≥ 1 (\xi_{\nu,j})_{\nu,j\ge1} ( ξ ν , j ) ν , j ≥ 1 in one sequence ( ζ m ) m ≥ 1 (\zeta_m)_{m\ge1} ( ζ m ) m ≥ 1 , here we order the pairs ( ν , j ) (\nu,j) ( ν , j ) by increasing ν + j \nu+j ν + j and then increasing ν \nu ν :
( ζ 1 , ζ 2 , … ) = ( ξ 1 , 1 , ξ 1 , 2 , ξ 2 , 1 , ξ 1 , 3 , ξ 2 , 2 , ξ 3 , 1 , … ) . (\zeta_1,\zeta_2,\ldots)=(\xi_{1,1},\xi_{1,2},\xi_{2,1},\xi_{1,3},\xi_{2,2},\xi_{3,1},\ldots). ( ζ 1 , ζ 2 , … ) = ( ξ 1 , 1 , ξ 1 , 2 , ξ 2 , 1 , ξ 1 , 3 , ξ 2 , 2 , ξ 3 , 1 , … ) .
For ν , j ≥ 1 \nu,j\ge1 ν , j ≥ 1 , define
C ν , j = { ξ ν , j = ξ ν , j + 1 = ⋯ = ξ ν , 2 j + ν + 1 } . C_{\nu,j}=\{\xi_{\nu,j}=\xi_{\nu,j+1}=\cdots=\xi_{\nu,2j+\nu+1}\}. C ν , j = { ξ ν , j = ξ ν , j + 1 = ⋯ = ξ ν , 2 j + ν + 1 } .
From the independence we obtain that P ( C ν , j ) = 2 − 1 − ν − j \mathbb{P}(C_{\nu,j})=2^{-1-\nu-j} P ( C ν , j ) = 2 − 1 − ν − j and ∑ ν , j ≥ 1 P ( C ν , j ) = 1 / 2 \sum_{\nu,j\ge1}\mathbb{P}(C_{\nu,j})=1/2 ∑ ν , j ≥ 1 P ( C ν , j ) = 1/2 . Define
Φ = ∑ k ≥ K 1 1 D k + ∑ ν , j ≥ 1 1 C ν , j . \Phi=\sum_{k\ge K_1}\mathbf{1}_{D_k}+\sum_{\nu,j\ge1}\mathbf{1}_{C_{\nu,j}}. Φ = k ≥ K 1 ∑ 1 D k + ν , j ≥ 1 ∑ 1 C ν , j .
The preceding estimates yield E Φ < 1 \mathbb{E}\Phi<1 E Φ < 1 .
For a finite binary word σ \sigma σ of length n n n , let
[ σ ] = { ( ζ 1 , … , ζ n ) = σ } , [ ∅ ] = Ω . [\sigma]=\{(\zeta_1,\ldots,\zeta_n)=\sigma\},\qquad[\varnothing]=\Omega. [ σ ] = {( ζ 1 , … , ζ n ) = σ } , [ ∅ ] = Ω.
Then V ( σ ) : = E ( Φ ∣ [ σ ] ) = 2 n E [ Φ 1 [ σ ] ] V(\sigma):=\mathbb{E}(\Phi\mid[\sigma])=2^n\mathbb{E}[\Phi\mathbf{1}_{[\sigma]}] V ( σ ) := E ( Φ ∣ [ σ ]) = 2 n E [ Φ 1 [ σ ] ] , since P ( σ ) = 2 − n \mathbb{P}(\sigma)=2^{-n} P ( σ ) = 2 − n . These conditional expectations are finite and satisfy V ( σ ) = ( V ( σ 0 ) + V ( σ 1 ) ) / 2 V(\sigma)=(V(\sigma0)+V(\sigma1))/2 V ( σ ) = ( V ( σ 0 ) + V ( σ 1 )) /2 .
Starting with σ 0 = ∅ \sigma_0=\varnothing σ 0 = ∅ , we define recursively
σ n = { σ n − 1 0 , V ( σ n − 1 0 ) ≤ V ( σ n − 1 1 ) , σ n − 1 1 , V ( σ n − 1 1 ) < V ( σ n − 1 0 ) . \sigma_n=
\begin{cases}
\sigma_{n-1}0, & V(\sigma_{n-1}0)\le V(\sigma_{n-1}1),\\
\sigma_{n-1}1, & V(\sigma_{n-1}1)<V(\sigma_{n-1}0).
\end{cases} σ n = { σ n − 1 0 , σ n − 1 1 , V ( σ n − 1 0 ) ≤ V ( σ n − 1 1 ) , V ( σ n − 1 1 ) < V ( σ n − 1 0 ) .
We then obtain a nested sequence of words ( σ n ) (\sigma_n) ( σ n ) , and
V ( σ n ) ≤ V ( σ n − 1 ) ≤ V ( ∅ ) < 1 ( n ≥ 1 ) . V(\sigma_n) \le V(\sigma_{n-1}) \le V(\varnothing) < 1 \qquad(n \ge1). V ( σ n ) ≤ V ( σ n − 1 ) ≤ V ( ∅ ) < 1 ( n ≥ 1 ) .
These words ( σ n ) (\sigma_n) ( σ n ) determine a unique infinite digit sequence, and the corresponding selected values of U ν U_\nu U ν thereby determine a point ω ∗ ∈ Ω \omega^* \in\Omega ω ∗ ∈ Ω .
None of the events C ν , j C_{\nu,j} C ν , j can occur for the selected digit sequence; otherwise, for n n n sufficiently large, we would have Φ ≥ 1 \Phi\ge1 Φ ≥ 1 on [ σ n ] [\sigma_n] [ σ n ] , and hence V ( σ n ) ≥ 1 V(\sigma_n) \ge1 V ( σ n ) ≥ 1 . Therefore no candidate’s free digits are eventually constant, and the corresponding candidates are not dyadic rationals and lie in the interiors of their assigned cells.
Set y n = Y n ( ω ∗ ) y_n=Y_n(\omega^*) y n = Y n ( ω ∗ ) . We show that ( y n ) (y_n) ( y n ) has PPC by bounding R N y ( s ) = R N ( s ) ( ω ∗ ) R_N^y(s)=R_N(s)(\omega^*) R N y ( s ) = R N ( s ) ( ω ∗ ) .
Fix s > 0 s>0 s > 0 and choose rational numbers s − , s + s^-,s^+ s − , s + with 0 < s − < s < s + 0<s^-<s<s^+ 0 < s − < s < s + . Choose K 2 ≥ K 1 K_2\ge K_1 K 2 ≥ K 1 such that s − , s + ∈ S k s^-,s^+\in S_k s − , s + ∈ S k for k ≥ K 1 k\ge K_1 k ≥ K 1 . Fix k ≥ K 1 k\ge K_1 k ≥ K 1 and N N N satisfying N k ≤ N < N k + 1 N_k\le N<N_{k+1} N k ≤ N < N k + 1 . Let ω ∈ [ σ n ] \omega\in[\sigma_n] ω ∈ [ σ n ] , where σ n \sigma_n σ n is a selected prefix whose length will be chosen below. We compare
R N ( s − ) ( ω ) , R N ( s ) ( ω ∗ ) , R N ( s + ) ( ω ) . R_N(s^-)(\omega), \qquad R_N(s)(\omega^*), \qquad R_N(s^+)(\omega). R N ( s − ) ( ω ) , R N ( s ) ( ω ∗ ) , R N ( s + ) ( ω ) .
These quantities depend only on Y 1 ( ω ) , Y 2 ( ω ) , … , Y N ( ω ) Y_1(\omega),Y_2(\omega),\ldots,Y_N(\omega) Y 1 ( ω ) , Y 2 ( ω ) , … , Y N ( ω ) and Y 1 ( ω ∗ ) , Y 2 ( ω ∗ ) , … , Y N ( ω ∗ ) Y_1(\omega^*),Y_2(\omega^*),\ldots,Y_N(\omega^*) Y 1 ( ω ∗ ) , Y 2 ( ω ∗ ) , … , Y N ( ω ∗ ) . The selection and ordering of the first N k + 1 N_{k+1} N k + 1 terms involve only finitely many candidates, namely those up to level k + 1 k+1 k + 1 .
At ω ∗ \omega^* ω ∗ , every candidate lies in the interior of its dyadic cell. Let δ > 0 \delta>0 δ > 0 be the minimum distance of their values from the dyadic boundaries at level k + 1 k+1 k + 1 . For a sufficiently long selected prefix σ n \sigma_n σ n , we have ∣ Z ν ( ω ) − Z ν ( ω ∗ ) ∣ < δ / 2 \lvert Z_\nu(\omega)-Z_\nu(\omega^*)\rvert<\delta/2 ∣ Z ν ( ω ) − Z ν ( ω ∗ )∣ < δ /2 for any ω ∈ [ σ n ] \omega\in[\sigma_n] ω ∈ [ σ n ] . Hence Z ν ( ω ) Z_\nu(\omega) Z ν ( ω ) and Z ν ( ω ∗ ) Z_\nu(\omega^*) Z ν ( ω ∗ ) lie in the same cell at each level up to k + 1 k+1 k + 1 . Thus, for every ω ∈ [ σ n ] \omega\in[\sigma_n] ω ∈ [ σ n ] , the first N N N terms use the same candidate indices as at ω ∗ \omega^* ω ∗ .
Extending the selected prefix σ n \sigma_n σ n further if necessary, we obtain
∥ Y i ( ω ) − y i ∥ T < min { s − s − , s + − s } 2 N ( 1 ≤ i ≤ N , ω ∈ [ σ n ] ) . \lVert Y_i(\omega)-y_i\rVert_{\mathbb{T}}<
\frac{\min\{s-s^-,s^+-s\}}{2N}
\qquad(1\le i\le N,\ \omega\in[\sigma_n]). ∥ Y i ( ω ) − y i ∥ T < 2 N min { s − s − , s + − s } ( 1 ≤ i ≤ N , ω ∈ [ σ n ]) .
Consequently, every indexed pair at distance at most s − / N s^-/N s − / N for ω \omega ω is at distance at most s / N s/N s / N for ω ∗ \omega^* ω ∗ , and every indexed pair at distance at most s / N s/N s / N for ω ∗ \omega^* ω ∗ is at distance at most s + / N s^+/N s + / N for ω \omega ω . Therefore
R N ( s − ) ( ω ) ≤ R N ( s ) ( ω ∗ ) ≤ R N ( s + ) ( ω ) ( ω ∈ [ σ n ] ) . R_N(s^-)(\omega)\le R_N(s)(\omega^*)\le R_N(s^+)(\omega)
\qquad(\omega\in[\sigma_n]). R N ( s − ) ( ω ) ≤ R N ( s ) ( ω ∗ ) ≤ R N ( s + ) ( ω ) ( ω ∈ [ σ n ]) .
We claim that
2 s − − η k ≤ R N ( s ) ( ω ∗ ) ≤ 2 s + + η k . 2s^- - \eta_k\le R_N(s)(\omega^*)\le2s^+ + \eta_k. 2 s − − η k ≤ R N ( s ) ( ω ∗ ) ≤ 2 s + + η k .
Indeed, if R N ( s ) ( ω ∗ ) > 2 s + + η k R_N(s)(\omega^*)>2s^+ +\eta_k R N ( s ) ( ω ∗ ) > 2 s + + η k , then R N ( s + ) ( ω ) > 2 s + + η k R_N(s^+)(\omega)>2s^+ +\eta_k R N ( s + ) ( ω ) > 2 s + + η k for every ω ∈ [ σ n ] \omega\in[\sigma_n] ω ∈ [ σ n ] , implying [ σ n ] ⊆ D k [\sigma_n]\subseteq D_k [ σ n ] ⊆ D k and hence V ( σ m ) ≥ 1 V(\sigma_m)\ge1 V ( σ m ) ≥ 1 , a contradiction. The lower bound R N ( s ) ( ω ∗ ) ≥ 2 s − − η k R_N(s)(\omega^*)\ge2s^- -\eta_k R N ( s ) ( ω ∗ ) ≥ 2 s − − η k follows in the same way.
Letting N → ∞ N\to\infty N → ∞ , and hence k → ∞ k\to\infty k → ∞ , we obtain
2 s − ≤ lim inf N → ∞ R N ( s ) ( ω ∗ ) ≤ lim sup N → ∞ R N ( s ) ( ω ∗ ) ≤ 2 s + . 2s^-\le\liminf_{N\to\infty}R_N(s)(\omega^*)\le\limsup_{N\to\infty}R_N(s)(\omega^*)\le2s^+. 2 s − ≤ N → ∞ lim inf R N ( s ) ( ω ∗ ) ≤ N → ∞ lim sup R N ( s ) ( ω ∗ ) ≤ 2 s + .
Letting s − , s + → s s^-,s^+\to s s − , s + → s , we conclude that lim N → ∞ R N ( s ) ( ω ∗ ) = 2 s \lim_{N\to\infty}R_N(s)(\omega^*)=2s lim N → ∞ R N ( s ) ( ω ∗ ) = 2 s , which proves that ( y n ) (y_n) ( y n ) has PPC. Proposition 2.5 yields (1.1). This completes the proof of Theorem 1.1.
PPC sequences with discrepancy of order (log N)/N
Let ( y n ) n ≥ 1 (y_n)_{n\ge1} ( y n ) n ≥ 1 be a sequence satisfying the conclusions of Theorem 1.1. Given such a sequence, we prove Theorem 1.2 by inserting zeros so as to obtain a matching lower discrepancy bound for every sufficiently large N N N , while preserving PPC.
Set
H 0 = 0 , H N = ⌊ log N ⌋ , M N = N − H N ( N ≥ 1 ) . H_0=0,\qquad H_N=\lfloor\log N\rfloor,\qquad M_N=N-H_N\qquad(N\ge1). H 0 = 0 , H N = ⌊ log N ⌋ , M N = N − H N ( N ≥ 1 ) .
Then H N − H N − 1 ∈ { 0 , 1 } H_N-H_{N-1}\in\{0,1\} H N − H N − 1 ∈ { 0 , 1 } for every N ≥ 1 N\ge1 N ≥ 1 . Retaining the original order of ( y n ) (y_n) ( y n ) , define
x N = { 0 , H N − H N − 1 = 1 , y M N , H N − H N − 1 = 0. x_N=
\begin{cases}
0, & H_N-H_{N-1}=1,\\
y_{M_N}, & H_N-H_{N-1}=0.
\end{cases} x N = { 0 , y M N , H N − H N − 1 = 1 , H N − H N − 1 = 0.
The first N N N terms thus consist of y 1 , … , y M N y_1,\ldots,y_{M_N} y 1 , … , y M N and H N H_N H N copies of 0.
Proposition 3.1. The sequence ( x N ) (x_N) ( x N ) has Poissonian pair correlation and satisfies
log N − 1 ≤ N D N ∗ ≤ ( 1 + 5 2 log 2 ) log N ( N ≥ 2 ) . (14) \log N - 1 \le ND_N^* \le\left(1+\frac{5}{2\log2}\right)\log N \qquad(N \ge2). \tag*{(14)} log N − 1 ≤ N D N ∗ ≤ ( 1 + 2 log 2 5 ) log N ( N ≥ 2 ) . (14) In particular, D N ∗ ≍ ( log N ) / N D_N^* \asymp(\log N)/N D N ∗ ≍ ( log N ) / N .
Proof. For 0 < t ≤ 1 0<t\le1 0 < t ≤ 1 , the construction gives
A N x ( t ) − N t = ( A M N y ( t ) − M N t ) + H N ( 1 − t ) . A_N^x(t)-Nt=\left(A_{M_N}^y(t)-M_Nt\right)+H_N(1-t). A N x ( t ) − N t = ( A M N y ( t ) − M N t ) + H N ( 1 − t ) .
Since M N ≥ 2 M_N\ge2 M N ≥ 2 for N ≥ 2 N\ge2 N ≥ 2 , we apply (1) and obtain
N D N ∗ ≤ H N + 5 2 log 2 log M N ≤ ( 1 + 5 2 log 2 ) log N . ND_N^*\le H_N+\frac{5}{2\log2}\log M_N\le\left(1+\frac{5}{2\log2}\right)\log N. N D N ∗ ≤ H N + 2 log 2 5 log M N ≤ ( 1 + 2 log 2 5 ) log N .
For the lower bound, the first N N N terms contain at least H N H_N H N zeros. Letting t ↓ 0 t\downarrow0 t ↓ 0 in the definition of star discrepancy, we get
N D N ∗ ≥ # { 1 ≤ n ≤ N : x n = 0 } ≥ H N ≥ log N − 1. ND_N^*\ge\#\{1\le n\le N:x_n=0\}\ge H_N\ge\log N-1. N D N ∗ ≥ # { 1 ≤ n ≤ N : x n = 0 } ≥ H N ≥ log N − 1.
This proves (14) .
To verify PPC, fix s > 0 s>0 s > 0 . Splitting the ordered pairs according to whether their entries are background points or inserted zeros, we obtain
R N x ( s ) = M N N R M N y ( s M N N ) + H N ( H N − 1 ) N + 2 H N N # { 1 ≤ m ≤ M N : ∥ y m ∥ T ≤ s N } . R_N^x(s)=\frac{M_N}{N}R_{M_N}^y\left(s\frac{M_N}{N}\right)+\frac{H_N(H_N-1)}{N}+\frac{2H_N}{N}\#\left\{1\le m\le M_N:\|y_m\|_{\mathbb{T}}\le\frac{s}{N}\right\}. R N x ( s ) = N M N R M N y ( s N M N ) + N H N ( H N − 1 ) + N 2 H N # { 1 ≤ m ≤ M N : ∥ y m ∥ T ≤ N s } .
The first term tends to 2 s 2s 2 s as N → ∞ N\to\infty N → ∞ , by the PPC of ( y m ) (y_m) ( y m ) , monotonicity in the window parameter, and M N / N → 1 M_N/N\to1 M N / N → 1 . Applying (1) to the two intervals adjacent to 0 0 0 , we obtain that, for all sufficiently large N N N ,
# { 1 ≤ m ≤ M N : ∥ y m ∥ T ≤ s N } ≤ 2 s M N N + 5 log 2 log M N ≪ s log N . \#\left\{1\le m\le M_N:\|y_m\|_{\mathbb{T}}\le\frac{s}{N}\right\}\le\frac{2sM_N}{N}+\frac{5}{\log2}\log M_N\ll_s\log N. # { 1 ≤ m ≤ M N : ∥ y m ∥ T ≤ N s } ≤ N 2 s M N + log 2 5 log M N ≪ s log N .
Since H N ≤ log N H_N\le\log N H N ≤ log N , the remaining two terms are O s ( ( log N ) 2 / N ) O_s((\log N)^2/N) O s (( log N ) 2 / N ) and tend to 0 0 0 . Thus R N x ( s ) → 2 s R_N^x(s)\to2s R N x ( s ) → 2 s for every s > 0 s>0 s > 0 .
:::
Prescribed discrepancy by inserting random points
We prove Theorem 1.3 by inserting independent uniform points in [ 0 , 1 / 2 ) [0,1/2) [ 0 , 1/2 ) into a sequence satisfying Theorem 1.1. Their number determines the discrepancy asymptotic, while estimates for pairs involving the inserted points yield PPC almost surely.
Construction of the sequence
Let ψ \psi ψ satisfy the assumptions of Theorem 1.3, and put h N = N ψ ( N ) h_N=N\psi(N) h N = N ψ ( N ) , with h 0 = 0 h_0=0 h 0 = 0 . Choose κ > 0 \kappa>0 κ > 0 such that κ L ≤ 1 / 2 \kappa L\le1/2 κ L ≤ 1/2 , where L L L is the increment bound in (2) . Set
H 0 = 0 , H N = ⌊ κ h N ⌋ , M N = N − H N ( N ≥ 1 ) . H_0=0,\qquad H_N=\lfloor\kappa h_N\rfloor,\qquad M_N=N-H_N\qquad(N\ge1). H 0 = 0 , H N = ⌊ κ h N ⌋ , M N = N − H N ( N ≥ 1 ) .
From (2) we then obtain
H N − H N − 1 ∈ { 0 , 1 } , 0 ≤ H N ≤ N / 2 ( N ≥ 1 ) . H_N-H_{N-1}\in\{0,1\},\qquad0\le H_N\le N/2\qquad(N\ge1). H N − H N − 1 ∈ { 0 , 1 } , 0 ≤ H N ≤ N /2 ( N ≥ 1 ) .
Since H N = κ h N + O ( 1 ) H_N=\kappa h_N+O(1) H N = κ h N + O ( 1 ) , we deduce from (3) and (4) that
H N ≪ N log N , H N log N → ∞ , M N N → 1. H_N\ll\sqrt{N\log N},\qquad\frac{H_N}{\log N}\to\infty,\qquad\frac{M_N}{N}\to1. H N ≪ N log N , log N H N → ∞ , N M N → 1.
Consider the probability space ( Ω , F , P ) (\Omega,\mathcal{F},\mathbb{P}) ( Ω , F , P ) , where
Ω = [ 0 , 1 / 2 ) N , F = B ( [ 0 , 1 / 2 ) ) ⊗ N , P = ( 2 λ ∣ [ 0 , 1 / 2 ) ) ⊗ N . \Omega=[0,1/2)^{\mathbb{N}},\qquad\mathcal{F}=\mathcal{B}([0,1/2))^{\otimes\mathbb{N}},\qquad\mathbb{P}=(2\lambda|_{[0,1/2)})^{\otimes\mathbb{N}}. Ω = [ 0 , 1/2 ) N , F = B ([ 0 , 1/2 ) ) ⊗ N , P = ( 2 λ ∣ [ 0 , 1/2 ) ) ⊗ N .
For ω = ( z 1 , z 2 , … ) ∈ Ω \omega=(z_1,z_2,\ldots)\in\Omega ω = ( z 1 , z 2 , … ) ∈ Ω , we define
W n ( ω ) = z n ( n ≥ 1 ) . W_n(\omega)=z_n\qquad(n\ge1). W n ( ω ) = z n ( n ≥ 1 ) .
Then W 1 , W 2 , … W_1,W_2,\ldots W 1 , W 2 , … are independent and uniform on [ 0 , 1 / 2 ) [0,1/2) [ 0 , 1/2 ) . Fix a sequence ( y m ) m ≥ 1 (y_m)_{m\ge1} ( y m ) m ≥ 1 satisfying the conclusions of Theorem 1.1. We insert W 1 , W 2 , … W_1,W_2,\ldots W 1 , W 2 , … into this sequence, retaining all its terms in their original order. More precisely, we define
X N = { W H N , H N − H N − 1 = 1 , y M N , H N − H N − 1 = 0. X_N =
\begin{cases}
W_{H_N}, & H_N-H_{N-1}=1,\\
y_{M_N}, & H_N-H_{N-1}=0.
\end{cases} X N = { W H N , y M N , H N − H N − 1 = 1 , H N − H N − 1 = 0.
The first N N N terms thus consist of y 1 , … , y M N y_1,\ldots,y_{M_N} y 1 , … , y M N and W 1 , … , W H N W_1,\ldots,W_{H_N} W 1 , … , W H N .
Discrepancy
The distribution function of W 1 W_1 W 1 is
F W ( t ) = min { 2 t , 1 } ( 0 ≤ t ≤ 1 ) . F_W(t)=\min\{2t,1\}\qquad(0\le t\le1). F W ( t ) = min { 2 t , 1 } ( 0 ≤ t ≤ 1 ) .
For 0 ≤ t ≤ 1 0\le t\le1 0 ≤ t ≤ 1 , from the construction we see
A N X ( t ) − N t = ( A M N y ( t ) − M N t ) + ( A H N W ( t ) − H N F W ( t ) ) + H N min { t , 1 − t } . A_N^X(t)-Nt=(A_{M_N}^y(t)-M_Nt)+(A_{H_N}^W(t)-H_NF_W(t))+H_N\min\{t,1-t\}. A N X ( t ) − N t = ( A M N y ( t ) − M N t ) + ( A H N W ( t ) − H N F W ( t )) + H N min { t , 1 − t } .
The Dvoretzky–Kiefer–Wolfowitz inequality in Massart’s sharp form [9 ] gives, for every integer H ≥ 2 H\ge2 H ≥ 2 ,
P ( sup 0 ≤ t ≤ 1 ∣ A H W ( t ) − H F W ( t ) ∣ > H log H ) ≤ 2 H 2 . \mathbb{P}\left(\sup_{0\le t\le1}\left|A_H^W(t)-HF_W(t)\right|>\sqrt{H\log H}\right)\le\frac{2}{H^2}. P ( 0 ≤ t ≤ 1 sup A H W ( t ) − H F W ( t ) > H log H ) ≤ H 2 2 .
By the Borel–Cantelli lemma, we have, almost surely,
sup 0 ≤ t ≤ 1 ∣ A H W ( t ) − H F W ( t ) ∣ = O ( H log H ) ( H → ∞ ) . (15) \sup_{0\le t\le1}\left|A_H^W(t)-HF_W(t)\right|=O\left(\sqrt{H\log H}\right)\qquad(H\to\infty). \tag*{(15)} 0 ≤ t ≤ 1 sup A H W ( t ) − H F W ( t ) = O ( H log H ) ( H → ∞ ) . (15)
Since sup 0 ≤ t ≤ 1 min { t , 1 − t } = 1 / 2 \sup_{0\le t\le1}\min\{t,1-t\}=1/2 sup 0 ≤ t ≤ 1 min { t , 1 − t } = 1/2 , we deduce from the reverse triangle inequality, (1) and (15) that, almost surely,
∣ N D N ∗ − H N 2 ∣ ≤ sup 0 ≤ t ≤ 1 ∣ A M N y ( t ) − M N t ∣ + sup 0 ≤ t ≤ 1 ∣ A H N W ( t ) − H N F W ( t ) ∣ ≪ log N + H N log H N . \begin{aligned}
\left|ND_N^*-\frac{H_N}{2}\right|
\le\sup_{0\le t\le1}\left|A_{M_N}^y(t)-M_Nt\right|+\sup_{0\le t\le1}\left|A_{H_N}^W(t)-H_NF_W(t)\right| \\
&\ll\log N+\sqrt{H_N\log H_N}.
\end{aligned} N D N ∗ − 2 H N ≤ 0 ≤ t ≤ 1 sup A M N y ( t ) − M N t + 0 ≤ t ≤ 1 sup A H N W ( t ) − H N F W ( t ) ≪ log N + H N log H N .
Using H N = κ h N + O ( 1 ) H_N=\kappa h_N+O(1) H N = κ h N + O ( 1 ) , we then obtain, almost surely,
N D N ∗ = κ 2 h N + O ( log N + h N log h N ) . ND_N^*=\frac{\kappa}{2}h_N+O\left(\log N+\sqrt{h_N\log h_N}\right). N D N ∗ = 2 κ h N + O ( log N + h N log h N ) .
By (3) , the error is o ( h N ) o(h_N) o ( h N ) , so we conclude that D N ∗ ∼ ( κ / 2 ) ψ ( N ) D_N^*\sim(\kappa/2)\psi(N) D N ∗ ∼ ( κ /2 ) ψ ( N ) .
Poissonian pair correlation
Fix s > 0 s>0 s > 0 . The following argument applies to every realization satisfying (15) . Splitting the ordered pairs according to their origins, we obtain
R N X ( s ) = M N N R M N y ( s M N N ) + 2 N ∑ j = 1 H N # { 1 ≤ m ≤ M N : ∥ y m − W j ∥ T ≤ s N } + 1 N # { 1 ≤ i ≠ j ≤ H N : ∥ W i − W j ∥ T ≤ s N } . \begin{aligned}
R_N^X(s)=\frac{M_N}{N}R_{M_N}^y\left(\frac{sM_N}{N}\right)+\frac{2}{N}\sum_{j=1}^{H_N}\#\left\{1\le m\le M_N:\|y_m-W_j\|_{\mathbb T}\le\frac{s}{N}\right\} \\
&+\frac{1}{N}\#\left\{1\le i\ne j\le H_N:\|W_i-W_j\|_{\mathbb T}\le\frac{s}{N}\right\}.
\end{aligned} R N X ( s ) = N M N R M N y ( N s M N ) + N 2 j = 1 ∑ H N # { 1 ≤ m ≤ M N : ∥ y m − W j ∥ T ≤ N s } + N 1 # { 1 ≤ i = j ≤ H N : ∥ W i − W j ∥ T ≤ N s } .
The first term tends to 2 s 2s 2 s , by the PPC of ( y m ) (y_m) ( y m ) , monotonicity in the window parameter, and M N / N → 1 M_N/N\to1 M N / N → 1 . Applying (1) and (15) to circular intervals of radius s / N s/N s / N , we obtain, uniformly in z ∈ T z\in\mathbb T z ∈ T ,
# { 1 ≤ m ≤ M N : ∥ y m − z ∥ T ≤ s N } ≪ s log N , \#\left\{1\le m\le M_N:\|y_m-z\|_{\mathbb T}\le\frac{s}{N}\right\}\ll_s\log N, # { 1 ≤ m ≤ M N : ∥ y m − z ∥ T ≤ N s } ≪ s log N ,
# { 1 ≤ j ≤ H N : ∥ W j − z ∥ T ≤ s N } ≪ s H N log H N . \#\left\{1\le j\le H_N:\|W_j-z\|_{\mathbb T}\le\frac{s}{N}\right\}\ll_s\sqrt{H_N\log H_N}. # { 1 ≤ j ≤ H N : ∥ W j − z ∥ T ≤ N s } ≪ s H N log H N .
Since H N ≪ N log N H_N\ll\sqrt{N\log N} H N ≪ N log N , we deduce that
0 ≤ R N X ( s ) − M N N R M N y ( s M N N ) ≪ s H N log N N + H N 3 / 2 log H N N → 0. 0\le R_N^X(s)-\frac{M_N}{N}R_{M_N}^y\left(\frac{sM_N}{N}\right)\ll_s\frac{H_N\log N}{N}+\frac{H_N^{3/2}\sqrt{\log H_N}}{N}\to0. 0 ≤ R N X ( s ) − N M N R M N y ( N s M N ) ≪ s N H N log N + N H N 3/2 log H N → 0.
Thus ( X n ) (X_n) ( X n ) has PPC on the same probability-one event.
Prescribed discrepancy by independent sampling
We prove Theorem 1.4 using independent random variables with nonidentical distributions. We control discrepancy through their average density and prove PPC almost surely by estimating the expectation and variance of R N ( s ) R_N(s) R N ( s ) .
Construction of the sequence
Construction of the sequence. Let ψ \psi ψ satisfy the assumptions of Theorem 1.4. Put h N = N ψ ( N ) h_N=N\psi(N) h N = N ψ ( N ) , with h 0 = 0 h_0=0 h 0 = 0 . Choose κ > 0 \kappa>0 κ > 0 such that κ L ≤ 1 / 2 \kappa L\le1/2 κ L ≤ 1/2 . Define a n = κ ( h n − h n − 1 ) a_n=\kappa(h_n-h_{n-1}) a n = κ ( h n − h n − 1 ) . Then 0 ≤ a n ≤ 1 / 2 0\le a_n\le1/2 0 ≤ a n ≤ 1/2 , and
∑ n = 1 N a n = κ h N = κ N ψ ( N ) . (16) \sum_{n=1}^{N}a_n=\kappa h_N=\kappa N\psi(N). \tag*{(16)} n = 1 ∑ N a n = κ h N = κ N ψ ( N ) . (16)
Define g ( x ) = 1 [ 0 , 1 / 2 ) ( x ) − 1 [ 1 / 2 , 1 ) ( x ) g(x)=\mathbf{1}_{[0,1/2)}(x)-\mathbf{1}_{[1/2,1)}(x) g ( x ) = 1 [ 0 , 1/2 ) ( x ) − 1 [ 1/2 , 1 ) ( x ) , and, for n ≥ 1 n\ge1 n ≥ 1 , define f n ( x ) = 1 + a n g ( x ) f_n(x)=1+a_ng(x) f n ( x ) = 1 + a n g ( x ) . We see that 1 / 2 ≤ f n ( x ) ≤ 3 / 2 1/2\le f_n(x)\le3/2 1/2 ≤ f n ( x ) ≤ 3/2 , and since ∫ T g ( x ) d x = 0 \int_{\mathbb{T}}g(x)\,\mathrm{d}x=0 ∫ T g ( x ) d x = 0 , each f n f_n f n is a probability density. Consider the probability space ( Ω , F , P ) (\Omega,\mathcal{F},\mathbb{P}) ( Ω , F , P ) , where
Ω = T N , F = B ( T ) ⊗ N , P = ⨂ n ≥ 1 ( f n ( x ) d x ) . \Omega=\mathbb{T}^{\mathbb{N}},\qquad\mathcal{F}=\mathcal{B}(\mathbb{T})^{\otimes\mathbb{N}},\qquad\mathbb{P}=\bigotimes_{n\ge1}(f_n(x)\,\mathrm{d}x). Ω = T N , F = B ( T ) ⊗ N , P = n ≥ 1 ⨂ ( f n ( x ) d x ) .
For ω = ( x 1 , x 2 , … ) ∈ Ω \omega=(x_1,x_2,\ldots)\in\Omega ω = ( x 1 , x 2 , … ) ∈ Ω , we define
X n ( ω ) = x n ( n ≥ 1 ) . X_n(\omega)=x_n\qquad(n\ge1). X n ( ω ) = x n ( n ≥ 1 ) .
Then X 1 , X 2 , … X_1,X_2,\ldots X 1 , X 2 , … are independent random variables with respective densities f 1 , f 2 , … f_1,f_2,\ldots f 1 , f 2 , … . Their average density is
f ‾ N ( x ) = 1 N ∑ n = 1 N f n ( x ) = 1 + κ ψ ( N ) g ( x ) . (17) \overline{f}_N(x)=\frac{1}{N}\sum_{n=1}^{N}f_n(x)=1+\kappa\psi(N)g(x). \tag*{(17)} f N ( x ) = N 1 n = 1 ∑ N f n ( x ) = 1 + κ ψ ( N ) g ( x ) . (17)
Discrepancy
Discrepancy. For 0 ≤ t ≤ 1 0\le t\le1 0 ≤ t ≤ 1 , write
G N ( t ) = 1 N ∑ n = 1 N 1 [ 0 , t ) ( X n ) , F N ( t ) = E G N ( t ) = ∫ 0 t f ‾ N ( x ) d x . G_N(t)=\frac{1}{N}\sum_{n=1}^{N}\mathbf{1}_{[0,t)}(X_n),\qquad F_N(t)=\mathbb{E}G_N(t)=\int_0^t\overline{f}_N(x)\,\mathrm{d}x. G N ( t ) = N 1 n = 1 ∑ N 1 [ 0 , t ) ( X n ) , F N ( t ) = E G N ( t ) = ∫ 0 t f N ( x ) d x .
Since 0 ≤ f ‾ N ≤ 3 / 2 0\le\overline{f}_N\le3/2 0 ≤ f N ≤ 3/2 , the monotonicity of G N G_N G N yields
sup 0 ≤ t ≤ 1 ∣ G N ( t ) − F N ( t ) ∣ ≤ max 0 ≤ j ≤ N ∣ G N ( j / N ) − F N ( j / N ) ∣ + 3 2 N . \sup_{0\le t\le1}|G_N(t)-F_N(t)|\le\max_{0\le j\le N}|G_N(j/N)-F_N(j/N)|+\frac{3}{2N}. 0 ≤ t ≤ 1 sup ∣ G N ( t ) − F N ( t ) ∣ ≤ 0 ≤ j ≤ N max ∣ G N ( j / N ) − F N ( j / N ) ∣ + 2 N 3 .
We combine Hoeffding’s inequality [4 Theorem 1] with a union bound to obtain, for every ε > 0 \varepsilon>0 ε > 0 ,
P ( max 0 ≤ j ≤ N ∣ G N ( j / N ) − F N ( j / N ) ∣ > ε ) ≤ 2 ( N + 1 ) e − 2 N ε 2 . \mathbb{P}\left(\max_{0\le j\le N}|G_N(j/N)-F_N(j/N)|>\varepsilon\right)\le2(N+1)e^{-2N\varepsilon^2}. P ( 0 ≤ j ≤ N max ∣ G N ( j / N ) − F N ( j / N ) ∣ > ε ) ≤ 2 ( N + 1 ) e − 2 N ε 2 .
Taking ε = 2 ( log N ) / N \varepsilon=2\sqrt{(\log N)/N} ε = 2 ( log N ) / N and applying the Borel–Cantelli lemma, we obtain that, almost surely,
sup 0 ≤ t ≤ 1 ∣ G N ( t ) − F N ( t ) ∣ = O ( log N N ) . (18) \sup_{0\le t\le1}|G_N(t)-F_N(t)|=O\left(\sqrt{\frac{\log N}{N}}\right). \tag*{(18)} 0 ≤ t ≤ 1 sup ∣ G N ( t ) − F N ( t ) ∣ = O ( N log N ) . (18)
By (5.2),
F N ( t ) − t = κ ψ ( N ) ∫ 0 t g ( x ) d x = κ ψ ( N ) min { t , 1 − t } ( 0 ≤ t ≤ 1 ) . F_N(t)-t=\kappa\psi(N)\int_0^t g(x)\,\mathrm{d}x=\kappa\psi(N)\min\{t,1-t\}\qquad(0\le t\le1). F N ( t ) − t = κ ψ ( N ) ∫ 0 t g ( x ) d x = κ ψ ( N ) min { t , 1 − t } ( 0 ≤ t ≤ 1 ) .
Hence
sup 0 ≤ t ≤ 1 ∣ F N ( t ) − t ∣ = κ 2 ψ ( N ) . \sup_{0\le t\le1}|F_N(t)-t|=\frac{\kappa}{2}\psi(N). 0 ≤ t ≤ 1 sup ∣ F N ( t ) − t ∣ = 2 κ ψ ( N ) .
The reverse triangle inequality for the supremum norm yields
∣ D N ∗ − κ 2 ψ ( N ) ∣ ≤ sup 0 ≤ t ≤ 1 ∣ G N ( t ) − F N ( t ) ∣ . \left|D_N^*-\frac{\kappa}{2}\psi(N)\right|\le\sup_{0\le t\le1}|G_N(t)-F_N(t)|. D N ∗ − 2 κ ψ ( N ) ≤ 0 ≤ t ≤ 1 sup ∣ G N ( t ) − F N ( t ) ∣.
(18) therefore implies that, almost surely,
N D N ∗ = κ 2 h N + O ( N log N ) . ND_N^*=\frac{\kappa}{2}h_N+O\left(\sqrt{N\log N}\right). N D N ∗ = 2 κ h N + O ( N log N ) .
By (1.5), the error is o ( h N ) o(h_N) o ( h N ) , so we conclude that D N ∗ ∼ ( κ / 2 ) ψ ( N ) D_N^* \sim(\kappa/2)\psi(N) D N ∗ ∼ ( κ /2 ) ψ ( N ) .
Poissonian pair correlation
Fix s > 0 s>0 s > 0 . For N > 2 s N>2s N > 2 s and 1 ≤ i ≠ j ≤ N 1\le i\ne j\le N 1 ≤ i = j ≤ N , put
B i j = 1 { ∥ X i − X j ∥ T ≤ s / N } . B_{ij}=\mathbf{1}_{\{\lVert X_i-X_j\rVert_{\mathbb{T}}\le s/N\}}. B ij = 1 {∥ X i − X j ∥ T ≤ s / N } .
Then
R N ( s ) = 1 N ∑ 1 ≤ i ≠ j ≤ N B i j = 2 N ∑ 1 ≤ i < j ≤ N B i j . R_N(s)=\frac{1}{N}\sum_{1\le i\ne j\le N}B_{ij}=\frac{2}{N}\sum_{1\le i<j\le N}B_{ij}. R N ( s ) = N 1 1 ≤ i = j ≤ N ∑ B ij = N 2 1 ≤ i < j ≤ N ∑ B ij .
By the independence, expanding f i ( x ) f j ( y ) f_i(x)f_j(y) f i ( x ) f j ( y ) and using ∫ T g ( x ) d x = 0 \int_{\mathbb{T}}g(x)\,\mathrm{d}x=0 ∫ T g ( x ) d x = 0 , we obtain
E B i j − 2 s N = a i a j ∫ T ∫ ∥ x − y ∥ T ≤ s / N g ( x ) g ( y ) d y d x . \mathbb{E}B_{ij}-\frac{2s}{N}=a_i a_j\int_{\mathbb{T}}\int_{\lVert x-y\rVert_{\mathbb{T}}\le s/N}g(x)g(y)\,\mathrm{d}y\,\mathrm{d}x. E B ij − N 2 s = a i a j ∫ T ∫ ∥ x − y ∥ T ≤ s / N g ( x ) g ( y ) d y d x .
Since ∣ g ∣ ≤ 1 |g|\le1 ∣ g ∣ ≤ 1 and a i , a j ≥ 0 a_i,a_j\ge0 a i , a j ≥ 0 ,
∣ E B i j − 2 s N ∣ ≤ 2 s N a i a j . \left|\mathbb{E}B_{ij}-\frac{2s}{N}\right|\le\frac{2s}{N}a_i a_j. E B ij − N 2 s ≤ N 2 s a i a j .
Summing over i ≠ j i\ne j i = j and using (5.1) we obtain
∣ E ( R N ( s ) − 2 s ) ∣ ≤ 2 s N + 2 s N 2 ∑ 1 ≤ i < j ≤ N a i a j ≤ 2 s N + 2 s κ 2 ψ ( N ) 2 → 0. \left|\mathbb{E}(R_N(s)-2s)\right|\le\frac{2s}{N}+\frac{2s}{N^2}\sum_{1\le i<j\le N}a_i a_j\le\frac{2s}{N}+2s\kappa^2\psi(N)^2\to0. ∣ E ( R N ( s ) − 2 s ) ∣ ≤ N 2 s + N 2 2 s 1 ≤ i < j ≤ N ∑ a i a j ≤ N 2 s + 2 s κ 2 ψ ( N ) 2 → 0.
For pairwise distinct indices i , j , k i,j,k i , j , k , conditioning on X i X_i X i , using the independence and f n ≤ 3 / 2 f_n\le3/2 f n ≤ 3/2 , and then taking expectations, we have
E B i j ≤ 3 s N , E ( B i j B i k ) ≤ 9 s 2 N 2 . \mathbb{E}B_{ij}\le\frac{3s}{N},\qquad\mathbb{E}(B_{ij}B_{ik})\le\frac{9s^2}{N^2}. E B ij ≤ N 3 s , E ( B ij B ik ) ≤ N 2 9 s 2 .
Indicators corresponding to disjoint index sets are independent. Using Var ( B i j ) ≤ E B i j \operatorname{Var}(B_{ij})\le\mathbb{E}B_{ij} Var ( B ij ) ≤ E B ij and Cov ( B i j , B i k ) ≤ E ( B i j B i k ) \operatorname{Cov}(B_{ij},B_{ik})\le\mathbb{E}(B_{ij}B_{ik}) Cov ( B ij , B ik ) ≤ E ( B ij B ik ) , we obtain
Var ( R N ( s ) ) = 4 N 2 Var ( ∑ 1 ≤ i < j ≤ N B i j ) ≤ 4 N 2 ( ( N 2 ) 3 s N + N ( N − 1 ) ( N − 2 ) 9 s 2 N 2 ) ≤ 6 s + 36 s 2 N . \begin{aligned}
\operatorname{Var}(R_N(s))=\frac{4}{N^2}\operatorname{Var}\left(\sum_{1\le i<j\le N}B_{ij}\right) \\
&\le\frac{4}{N^2}\left(\binom{N}{2}\frac{3s}{N}+N(N-1)(N-2)\frac{9s^2}{N^2}\right)\le\frac{6s+36s^2}{N}.
\end{aligned} Var ( R N ( s )) = N 2 4 Var 1 ≤ i < j ≤ N ∑ B ij ≤ N 2 4 ( ( 2 N ) N 3 s + N ( N − 1 ) ( N − 2 ) N 2 9 s 2 ) ≤ N 6 s + 36 s 2 .
The standard subsequence argument now shows that ( X n ) (X_n) ( X n ) has PPC almost surely.
Optimal discrepancy constants
Theorem 1.1 shows that PPC is compatible with the optimal discrepancy order ( log N ) / N (\log N)/N ( log N ) / N . We now consider the optimal limsup constant. Set
c ∗ : = inf x lim sup N → ∞ N D N ∗ ( x ) log N , c^*:=\inf_x\limsup_{N\to\infty}\frac{ND_N^*(x)}{\log N}, c ∗ := x inf N → ∞ lim sup log N N D N ∗ ( x ) ,
where the infimum is over all infinite sequences x = ( x n ) n ≥ 1 x=(x_n)_{n\ge1} x = ( x n ) n ≥ 1 in [ 0 , 1 ) [0,1) [ 0 , 1 ) . Define
c P P C ∗ : = inf x h a s P P C lim sup N → ∞ N D N ∗ ( x ) log N . c_{\mathrm{PPC}}^*:=\inf_{x\ \mathrm{has\ PPC}}\limsup_{N\to\infty}\frac{ND_N^*(x)}{\log N}. c PPC ∗ := x has PPC inf N → ∞ lim sup log N N D N ∗ ( x ) .
Since PPC sequences form a subclass of all sequences,
c ∗ ≤ c P P C ∗ . c^*\le c_{\mathrm{PPC}}^*. c ∗ ≤ c PPC ∗ .
The exact value of c ∗ c^* c ∗ is unknown; for bounds, we refer to Larcher and Puchhammer [6 ] and Ostromoukhov [11 ] .
Open Problem 6.1. Is c P P C ∗ = c ∗ c_{\mathrm{PPC}}^*=c^* c PPC ∗ = c ∗ ?
Statements and Declarations
Funds. This work is supported by National Key R&D Program of China (No. 2024YFA1013700) and NSFC (Nos. 12671113 and 12331005), and the Fundamental Research Funds for the Central Universities.
Competing Interests. The authors declare that they have no financial or non-financial interests relevant to the content of this article.
Data Availability. This article is theoretical. No research datasets were generated or analysed.
References
School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan 430074, China.
Email address: tanbo@hust.edu.cn
School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan 430074, China.
Email address: zhangzhen_@hust.edu.cn
School of Mathematics and Statistics, Wuhan University of Technology, Wuhan 430070, China. Email address: zhouql@whut.edu.cn