betaFeedback

WorksMathematics

Poissonian Pair Correlation and Discrepancy Rates

Abstract

We prove the existence of a sequence in [0,1)[0,1) with Poissonian pair correlation (PPC) and optimal-order star discrepancy DN∗=O((log⁡N)/N)D_N^*=O((\log N)/N), and further give a deterministic construction by applying a conditional-expectation rule to a nested dyadic random model. We also show that PPC imposes no universal discrepancy decay rate: for every positive sequence ρN→0ρ_N\to0, there exists a PPC sequence with DN∗/ρN→∞D_N^*/ρ_N\to\infty. Under suitable regularity and growth assumptions, we realize prescribed discrepancy asymptotics, including DN∗∼cβN−βD_N^*\sim c_βN^{-β} for every 0<β<10<β<1, with cβ>0c_β>0. We further construct a PPC sequence satisfying DN∗≍(log⁡N)/ND_N^*\asymp(\log N)/N for all sufficiently large NN.

Introduction

The theory of uniform distribution modulo one was developed in the work of Weyl [17]. A sequence (xn)n≥1⊂[0,1)(x_n)_{n\ge1}\subset[0,1) is uniformly distributed modulo one if

1N#{1≤n≤N:xn∈[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)

for every 0≤a<b≤10\le a<b\le1. A basic example is the Kronecker sequence {nα}n≥1\{n\alpha\}_{n\ge1} for any irrational α\alpha, where {t}=t−⌊t⌋\{t\}=t-\lfloor t\rfloor denotes the fractional part of tt.

For x=(xn)⊂[0,1)x=(x_n)\subset[0,1), put

ANx(t)=#{1≤n≤N:xn<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),

with A0x(t)=0A_0^x(t)=0. The star discrepancy of the first NN points is

DN∗=DN∗(x):=sup⁡0≤t≤1∣ANx(t)N−t∣.D_N^*=D_N^*(x):=\sup_{0\le t\le1}\left|\frac{A_N^x(t)}{N}-t\right|.

A sequence xx is uniformly distributed modulo one if and only if DN∗(x)→0D_N^*(x)\to0 as N→∞N\to\infty; 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 DN∗=O((log⁡N)/N)D_N^*=O((\log N)/N). This order is optimal for infinite one-dimensional sequences: Schmidt [15] proved that NDN∗≫log⁡NND_N^*\gg\log N for infinitely many NN for every infinite sequence in [0,1)[0,1). Both the Kronecker sequence ({nα})n≥1(\{n\alpha\})_{n\ge1} 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/N1/N. We identify [0,1)[0,1) with T=R/Z\mathbb{T}=\mathbb{R}/\mathbb{Z} and write ∥ ⋅ ∥T=min⁡m∈Z∣⋅−m∣\|\,\cdot\,\|_{\mathbb{T}}=\min_{m\in\mathbb{Z}}|\cdot-m| for the distance to the nearest integer. For a sequence x=(xn)x=(x_n), we define

RN(s)=RNx(s):=1N#{1≤i≠j≤N:∥xi−xj∥T≤sN}(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).

The sequence has Poissonian pair correlation (PPC) if, for every s>0s>0,

RN(s)→2s(N→∞).R_N(s)\to2s\qquad(N\to\infty).

This is the almost-sure limit for independent uniform random points on T\mathbb{T}.

El-Baz, Marklof and Vinogradov [2] proved that ({n})n≥1\left(\{\sqrt{n}\}\right)_{n\ge1} has PPC after the terms with square nn are omitted. Metric examples include ({n2α})n≥1\left(\{n^2\alpha\}\right)_{n\ge1} and ({2nα})n≥1\left(\{2^n\alpha\}\right)_{n\ge1}, 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/Ns/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} 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 DN∗≍(log⁡N)/ND_N^* \asymp(\log N)/N for all sufficiently large NN. More generally, we construct PPC sequences with prescribed discrepancy asymptotics DN∗∼cψψ(N)D_N^* \sim c_\psi\psi(N) under suitable regularity and growth assumptions on ψ\psi, where cψ>0c_\psi> 0. These include every polynomial rate N−βN^{-\beta} with 0<β<10 < \beta< 1. We also show that, for every positive sequence ρN→0\rho_N \to0, there exists a PPC sequence with DN∗/ρN→∞D_N^*/\rho_N \to\infty. Thus PPC imposes no universal discrepancy decay rate.

Throughout the paper, we use Landau and Vinogradov notation interchangeably. For instance, we write aN≪bNa_N \ll b_N, or equivalently aN=O(bN)a_N = O(b_N), if there exists a constant C>0C > 0 such that bN>0b_N > 0 and ∣aN∣≤CbN\lvert a_N\rvert\le Cb_N for all sufficiently large NN; sometimes a subscript on OO or ≪\ll is added to indicate parameters on which the implied constant CC may depend. We write aN≍bNa_N \asymp b_N if both aN≪bNa_N \ll b_N and bN≪aNb_N \ll a_N, and we write aN∼bNa_N \sim b_N if aN/bN→1a_N/b_N \to1 as N→∞N \to\infty. We write aN=o(bN)a_N = o(b_N), or equivalently bN=ω(aN)b_N = \omega(a_N), if aN/bN→0a_N/b_N \to0 as N→∞N \to\infty.

We denote the indicator of a set AA by 1A\mathbf{1}_A. The notation B(S)\mathcal{B}(S) denotes the Borel σ\sigma-algebra of SS. The symbols P\mathbb{P} and E\mathbb{E} denote probability and expectation for the random construction under consideration. Let λ\lambda denote normalized Lebesgue measure on T\mathbb{T}. All integrals on T\mathbb{T} are taken with respect to this measure.

Our main results read as follows.

Theorem 1.1. There exists a deterministic sequence (yn)n≥1⊂[0,1)(y_n)_{n\ge1} \subset[0,1) such that

RNy(s)→2s(N→∞)for every s>0R_N^y(s) \to2s \qquad(N \to\infty) \qquad\text{for every } s>0

and

NDN∗(y1,…,yN)≤52log⁡2log⁡N(N≥2).(1)N D_N^*(y_1,\ldots,y_N) \le\frac{5}{2\log2}\log N \qquad(N \ge2). \tag*{(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 (xn)n≥1⊂T(x_n)_{n\ge1} \subset\mathbb{T} with PPC such that

DN∗≍log⁡NND_N^* \asymp\frac{\log N}{N}

for all sufficiently large NN.

Theorem 1.3. Let ψ:N→(0,∞)\psi:\mathbb{N}\to(0,\infty), and put hN=Nψ(N)h_N=N\psi(N) with h0=0h_0=0. Assume that, for some L>0L>0,

0≤hN−hN−1≤L(N≥1).(2)0 \le h_N-h_{N-1}\le L \qquad(N\ge1). \tag*{(2)}
hN=ω(log⁡N)(N→∞)(3)h_N=\omega(\log N)\qquad(N\to\infty) \tag*{(3)}

and

hN≪Nlog⁡N.(4)h_N\ll\sqrt{N}\log N. \tag*{(4)}

Then there exist a sequence (xn)n≥1⊂T(x_n)_{n\ge1}\subset\mathbb{T} and a constant cψ>0c_\psi>0 such that:

  1. the sequence (xn)(x_n) has PPC;

  2. its star discrepancy satisfies

NDN∗=cψhN+O(log⁡N+hNlog⁡hN)ND_N^*=c_\psi h_N+O\left(\log N+\sqrt{h_N\log h_N}\right)

for all sufficiently large NN. In particular,

DN∗∼cψψ(N)(N→∞).D_N^*\sim c_\psi\psi(N)\qquad(N\to\infty).

:::

References

  1. [1]C. Aistleitner, T. Lachmann, and F. Pausinger, Pair correlations and equidistribution, Journal of Number Theory 182 (2018), 206–220.
  2. [2]D. El-Baz, J. Marklof, and I. Vinogradov, The two-point correlation function of the fractional parts of √n is Poisson, Proceedings of the American Mathematical Society 143 (2015), no. 7, 2815–2828.
  3. [3]S. Grepstad and G. Larcher, On pair correlation and discrepancy, Archiv der Mathematik 109 (2017), no. 2, 143–149.arxiv.org/abs/1612.08008
  4. [4]W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963), no. 301, 13–30.
  5. [5]L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, Wiley-Interscience, New York, 1974.
  6. [6]G. Larcher and F. Puchhammer, An improved bound for the star discrepancy of sequences in the unit interval, Uniform Distribution Theory 11 (2016), no. 1, 1–14.
  7. [7]G. Larcher and W. Stockinger, Some negative results related to Poissonian pair correlation problems, Discrete Mathematics 343 (2020), no. 2, 111656.
  8. [8]M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90, Cambridge University Press, Cambridge, 2002.DOI
  9. [9]P. Massart, The tight constant in the Dvoretzky–Kiefer–Wolfowitz inequality, The Annals of Probability 18 (1990), no. 3, 1269–1283.
  10. [10]C. McDiarmid, On the method of bounded differences, in Surveys in Combinatorics, 1989 (J. Siemons, ed.), London Mathematical Society Lecture Note Series, vol. 141, Cambridge University Press, 1989, pp. 148–188.
  11. [11]V. Ostromoukhov, Recent progress in improvement of extreme discrepancy and star discrepancy of one-dimensional sequences, in Monte Carlo and Quasi-Monte Carlo Methods 2008 (P. L’Ecuyer and A. B. Owen, eds.), Springer, Berlin, 2009, pp. 561–572.
  12. [12]P. Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences 37 (1988), no. 2, 130–143.
  13. [13]Z. Rudnick and P. Sarnak, The pair correlation function of fractional parts of polynomials, Communications in Mathematical Physics 194 (1998), no. 1, 61–70.
  14. [14]Z. Rudnick and A. Zaharescu, A metric result on the pair correlation of fractional parts of sequences, Acta Arithmetica 89 (1999), no. 3, 283–293.
  15. [15]W. M. Schmidt, Irregularities of distribution, VII, Acta Arithmetica 21 (1972), no. 1, 45–50.
  16. [16]S. Steinberger, Poissonian pair correlation and discrepancy, Indagationes Mathematicae 29 (2018), no. 5, 1167–1178.
  17. [17]H. Weyl, Über die Gleichverteilung von Zahlen mod. Eins, Mathematische Annalen 77 (1916), no. 3, 313–352.

Paper details

vlnc:W_3fbtpuzv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents