#  Poissonian Correlations of Higher Orders

Manuel Hauke  TU Graz, Austria<EMAIL_ADDRESS>and  Agamemnon
Zafeiropoulos  NTNU Trondheim, Norway<EMAIL_ADDRESS>
###### Abstract.

We show that any sequence $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ that has
Poissonian correlations of $k$ – th order is uniformly distributed, also
providing a quantitative description of this phenomenon. Additionally, we
extend connections between metric correlations and additive energy, already
known for pair correlations, to higher orders. Furthermore, we examine how the
property of Poissonian $k$ – th correlations is reflected in the asymptotic
size of the moments of the function $F(t,s,N)=\\#\\{n\leqslant
N\mathrel{\mathop{\ordinarycolon}}\|x_{n}-t\|\leqslant s/(2N)\\},\,t\in[0,1].$

###### 2010 Mathematics Subject Classification:

Primary 11K06, 11J71; Secondary 11K99

AZ is supported by a postdoctoral fellowship funded by Grant 275113 of the
Research Council of Norway

##  1\. Introduction

###  1.1. The main results

Let $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ be a sequence and $k\geqslant 2$
be an integer. Given a compactly supported test function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{k-1}\to[0,\infty)$ we define
the $k$ – th order correlation function of the sequence
$(x_{n})_{n\in\mathbb{N}}$ with respect to $f$ to be

(1)
$R_{k}(f,N)=\frac{1}{N}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\ \text{
distinct}\end{subarray}}f\left(N(\\!(x_{i_{1}}-x_{i_{2}})\\!),N(\\!(x_{i_{1}}-x_{i_{3}})\\!),\ldots,N(\\!(x_{i_{1}}-x_{i_{k}})\\!)\right).$

Here $(\\!(x)\\!)$ denotes the signed distance of $x$ from the origin modulo
$1$ (see Section 1.4 for a proper definition).

We say that the sequence $(x_{n})_{n\in\mathbb{N}}$ has Poissonian $k$ – th
order correlations if

(2)
$\lim_{N\to\infty}R_{k}(f,N)=\int_{\mathbb{R}^{k-1}}f(x)\,\mathrm{d}x\qquad\text{for
any }f\in C_{c}(\mathbb{R}^{k-1}).$

A discussion on equivalent definitions of Poissonian correlations appearing in
the literature can be found in Appendix A. There we explain that a sequence
has Poissonian $k$ – th order correlations if and only if (2) holds for any
$f$ which is the characteristic function of some rectangle in
$\mathbb{R}^{k-1}.$

Having Poissonian $k$ – th order correlations can be viewed as a pseudo-
randomness property of the sequence $(x_{n})_{n\in\mathbb{N}}$ in the
following sense: when $(Y_{n})_{n\in\mathbb{N}}$ is a sequence of independent,
uniformly distributed random variables in $[0,1]$, then almost surely, the
sequence $(Y_{n}(\omega))_{n\in\mathbb{N}}$ has Poissonian $k$ – th order
correlations (see Appendix B for a proof).

The $k$ – th order correlations of a sequence are a local asymptotic
statistics of the gaps of a sequence. Another closely related statistics is
the asymptotic gap distribution of the sequence [14]. It is known that when a
sequence has Poissonian correlations of all orders $k\geqslant 2,$ then the
asymptotic distribution of its gaps is also Poissonian; a proof can be found
in [14, Appendix A].

The term _Poissonian_ comes from the fact that (2) is in accordance with the
almost sure statistical behavior of gaps between random points coming from a
Poisson process. Originally, the motivation for studying the gap statistics of
point sequences came from theoretical physics, where the Berry – Tabor
conjecture predicts that the spacings of the energy eigenvalues of generic
integrable quantum systems follow the Poissonian model (see [17] for a survey
in mathematical language). For some quantum systems the sequence of energy
eigenvalues follows a simple arithmetic formula, but establishing the
correlations to be Poissonian is usually a very substantial challenge (that
often becomes more and more difficult as the order of the correlations
increases). For some contributions concerning sequences of cognizable physical
origin see for example [10, 18, 25]. However, the subject has also gained
significant interest on a purely mathematical level, where the correlations of
general sequences of arithmetic origin were studied; see for example [2, 3,
21]. Most results only concern the case of correlations of order $k=2$ (known
as _pair correlations_), while correlations of higher order are
combinatorially and analytically more difficult to study and often out of
reach; among the relatively few results in that direction are [23] and [29].

A topic of particular interest has been the connection of Poissonian pair
correlations with uniform distribution properties. Recall that a sequence
$(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ is called uniformly distributed if
for any $0\leqslant a<b\leqslant 1$ we have

$\lim_{N\to\infty}\frac{1}{N}\\#\\{n\leqslant
N\mathrel{\mathop{\ordinarycolon}}a\leqslant x_{n}\leqslant b\\}=b-a.$

To be more specific, it has been shown that when a sequence has Poissonian
pair correlations it is also uniformly distributed.

Theorem A.  Let $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ be a sequence. If
$(x_{n})_{n\in\mathbb{N}}$ has Poissonian pair correlations, then
$(x_{n})_{n\in\mathbb{N}}$ is uniformly distributed.

Theorem A was proved independently by Aistleitner, Lachmann and Pausinger [1]
and by Grepstad and Larcher [9]. Additional proofs were given later by
Steinerberger in [26] and, in a much more general setup, by Marklof [16].
These four proofs are all essentially different.

The authors of [1] also prove a quantitative version of Theorem A that is
interesting in its own right. Before we present this version of Theorem A,
recall that a function $G\mathrel{\mathop{\ordinarycolon}}[0,1]\to\mathbb{R}$
is called an asymptotic distribution function of a sequence
$(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ if there exists a strictly increasing
sequence of integers $(N_{j})_{j\in\mathbb{N}}$ such that

(3) $G(x)=\lim_{j\to\infty}\frac{1}{N_{j}}\\#\\{n\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}0\leqslant x_{n}\leqslant x\\},\qquad
0\leqslant x\leqslant 1.$

By the Helly selection principle, every sequence
$(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ has at least one asymptotic
distribution function (see e.g. [12, Ch. 1, Thm. 7.1]). Whenever
$G\mathrel{\mathop{\ordinarycolon}}[0,1]\to\mathbb{R}$ is the unique
asymptotic distribution function of the sequence $(x_{n})_{n\in\mathbb{N}}$,
that is, whenever

$G(x)=\lim_{N\to\infty}\frac{1}{N}\\#\\{n\leqslant
N\mathrel{\mathop{\ordinarycolon}}0\leqslant x_{n}\leqslant x\\}$

holds for all $x\in[0,1]$, we will simply refer to it as the asymptotic
distribution function of $(x_{n})_{n\in\mathbb{N}}$.

The quantitative version of Theorem A is the following statement.

Theorem B.  Assume that the sequence $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$
has the unique asymptotic distribution function
$G\mathrel{\mathop{\ordinarycolon}}[0,1]\to\mathbb{R}.$ Assume also that there
is a function
$F\mathrel{\mathop{\ordinarycolon}}[0,\infty)\rightarrow[0,\infty]$ such that

$F(s)=\lim_{N\to\infty}\frac{1}{N}\\#\Big{\\{}k\neq\ell\leqslant
N\mathrel{\mathop{\ordinarycolon}}\|x_{k}-x_{\ell}\|\leqslant\frac{s}{N}\Big{\\}},\qquad
s>0.$

Then the following hold:

  * (i)

If $G$ is not absolutely continuous, then $F(s)=\infty$ for all $s>0$.

  * (ii)

If $G$ is absolutely continuous, then

$\limsup_{s\to\infty}\frac{F(s)}{2s}\geqslant\int_{0}^{1}g(x)^{2}\,\mathrm{d}x$

where $g$ is the density function of the corresponding measure (that is,
$g=G^{\prime}$ almost everywhere).

As a main result of this paper, we prove that Theorem A can be generalised to
sequences with Poissonian correlations of order $k\geqslant 2$: having
Poissonian correlations of any order $k\geqslant 2$ is a stronger property
than uniform distribution.

######  Theorem 1.1.

If the sequence $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ has Poissonian $k$ –
correlations for some $k\geqslant 2$, then it is uniformly distributed.

In fact, with a little more effort than in the proof of Theorem 1.1 we are
able to prove a stronger result that can be viewed as a generalisation of
Theorem B in the context of $k$ – th order correlations. In what follows, for
$s>0$ we shall write $R_{k}(s,N)=R_{k}(f_{s},N)$ where $f_{s}$ is the test
function $f_{s}=\mathds{1}_{[-s,s]^{k-1}}$.

######  Theorem 1.2.

Let $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$,
$G\mathrel{\mathop{\ordinarycolon}}[0,1]\to\mathbb{R}$ be an asymptotic
distribution function of $(x_{n})_{n\in\mathbb{N}}$ and
$(N_{j})_{j\in\mathbb{N}}$ be a sequence as in (3). Then the following hold:

  * (i)

If $G$ is not absolutely continuous, then
$\lim\limits_{j\to\infty}R_{k}(s,N_{j})=\infty$ for all $s>0$.

  * (ii)

If $G$ is absolutely continuous, then

(4)
$\limsup_{s\to\infty}\frac{\limsup\limits_{j\to\infty}R_{k}(s,N_{j})}{(2s)^{k-1}}\geqslant\int_{0}^{1}g(x)^{k}\,\mathrm{d}x,$

where $g$ is the density function of the corresponding measure.

To see why Theorem 1.2 is indeed a stronger version of Theorem 1.1, observe
that if $(x_{n})_{n\in\mathbb{N}}$ has Poissonian $k$ – th correlations but is
not uniformly distributed, it will have an asymptotic distribution function
$G$ whose density function $g$ is not constantly equal to $1$ (the existence
of $g$ follows from (i) of Theorem 1.2). Therefore
$\int_{0}^{1}g(x)^{k}\mathrm{d}x>1$ and (4) leads to a contradiction.

The reader might spot two subtle differences between Theorem B and its
generalisation, Theorem 1.2. First, in Theorem 1.2 we assume that $G$ is an
asymptotic distribution function of $(x_{n})_{n\in\mathbb{N}}$, not
necessarily unique as in Theorem B. Second, we do not require that the limit
$\lim_{N\to\infty}R_{k}(s,N)$ exists, but instead, we work with the term
$\limsup_{j\to\infty}R_{k}(s,N_{j})$. The additional assumptions in Theorem B
are not essential, and the proof in [1] can be easily modified under the
slightly weaker hypotheses of Theorem 1.2. These minor modifications also make
Theorem B an actually stronger result than Theorem A.

In the proof of both Theorems 1.1 and 1.2, we shall make use of several
variants of the correlation function $R_{k}(f,N)$ that was defined in (1). To
be more specific, given some scales $s_{1},s_{2},\ldots,s_{k-1}>0$ we define
the correlation function $R_{k}(s_{1},\ldots,s_{k-1},N)$ by

(5)
$R_{k}(s_{1},\ldots,s_{k-1},N)=\frac{1}{N}\\#\left\\{\parbox{70.0001pt}{$i_{1},\ldots,i_{k}\leqslant
N$ \\\ $i_{j}\neq i_{\ell}\,\forall
j\neq\ell$}\mathrel{\mathop{\ordinarycolon}}\,\|x_{i_{1}}-x_{i_{r+1}}\|\leqslant\frac{s_{r}}{N}\,\,\,(1\leqslant
r<k)\right\\}$

(where $\|x\|$ denotes the distance of $x\in\mathbb{R}$ to its nearest
integer). Since we can write $R_{k}(s_{1},\ldots,s_{k-1},N)$ as
$R_{k}(\mathds{1}_{B},N)$ where $B$ is the rectangle
$[-s_{1},s_{1}]\times\ldots\times[-s_{k-1},s_{k-1}],$ it follows from (2) and
an approximation argument that sequences with Poissonian $k$ – th correlations
also satisfy

$\lim_{N\to\infty}R_{k}(s_{1},\ldots,s_{k-1},N)=(2s_{1})\cdots(2s_{k-1})\quad\text{
for all }s_{1},\ldots,s_{k-1}>0$

(see also Appendix A for a discussion).

Furthermore, we define the correlation function
$R_{k}^{*}(s_{1},\ldots,s_{k-1},N)$ by

(6) $\displaystyle
R_{k}^{*}(s_{1},\ldots,s_{k-1},N)=\frac{1}{N}\\#\left\\{i_{1},\ldots,i_{k}\leqslant
N\mathrel{\mathop{\ordinarycolon}}\|x_{i_{1}}-x_{i_{r+1}}\|\leqslant\frac{s_{r}}{N}\,\,(1\leqslant
r<k)\right\\}.$

That is, in the definition of $R_{k}^{*}(s_{1},\ldots,s_{k-1},N)$ we allow
indices to be equal. We will also make use of the appropriate averages of
$R_{k}$ and $R_{k}^{*}$ defined as

$C_{k}(s_{1},\ldots,s_{k-1},N)=\mathop{\iint\ldots\int}_{B(s_{1},\ldots,s_{k-1})}R_{k}(\sigma_{1},\ldots,\sigma_{k-1},N)\,\mathrm{d}\sigma_{1}\mathrm{d}\sigma_{2}\ldots\mathrm{d}\sigma_{k-1}$

and

$C_{k}^{*}(s_{1},\ldots,s_{k-1},N)=\mathop{\iint\ldots\int}_{B(s_{1},\ldots,s_{k-1})}R_{k}^{*}(\sigma_{1},\ldots,\sigma_{k-1},N)\,\mathrm{d}\sigma_{1}\mathrm{d}\sigma_{2}\ldots\mathrm{d}\sigma_{k-1},$

where $B(s_{1},\ldots,s_{k-1})$ denotes the rectangle
$[0,s_{1}]\times[0,s_{2}]\times\ldots\times[0,s_{k-1}].$ Finally, when the
scales $s_{1},\ldots,s_{k-1}$ are all equal to $s>0$ we write for simplicity

$\begin{gathered}R_{k}(s,N)=R_{k}(s,\ldots,s,N),\qquad
R_{k}^{*}(s,N)=R_{k}^{*}(s,\ldots,s,N),\\\
C_{k}(s,N)=C_{k}(s,\ldots,s,N),\qquad
C_{k}^{*}(s,N)=C_{k}^{*}(s,\ldots,s,N).\end{gathered}$

We note that the definition of $R_{k}(s,N)$ here agrees with the definition
given right before Theorem 1.2.

###  1.2. Some consequences of the main results

In the course of the proofs of the stated theorems, we examine the relations
between the correlation functions of different orders for a given sequence.
These relations enable us to prove that when a sequence
$(x_{n})_{n\in\mathbb{N}}$ fails to have Poissonian $k$ – th order
correlations in a very strong sense, then it will also not have Poissonian
correlations of any higher order.

######  Theorem 1.3.

Let $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ be a sequence and assume that for
some scales $s_{1},\ldots,s_{k-1}>0$ the $k$ – th order correlation function
$R_{k}(s_{1},\ldots,s_{k-1},N)$ satisfies

$\limsup_{N\to\infty}R_{k}(s_{1},\ldots,s_{k-1},N)=\infty.$

Then the sequence $(x_{n})_{n\in\mathbb{N}}$ does not have Poissonian $p$ – th
order correlations for any $p\geqslant k.$

Theorem 1.3 is one of the key ingredients we will use to derive new results on
the metric theory of Poissonian correlations: an increasing sequence
$\mathcal{A}=(a_{n})_{n\in\mathbb{N}}\subseteq\mathbb{N}$ is fixed, and we
study the Lebesgue measure of $x\in[0,1]$ such that the sequence
$(a_{n}x)_{n\in\mathbb{N}}$ has Poissonian correlations. As with the
correlations of fixed sequences, most of the metric results to date are
concerned with the $k=2$ case.

In the metric setup, the authors of [2] have established several statements on
the connection of Poissonian correlations with the notion of additive energy.
Recall that the additive energy of a finite set $A$ is defined as

$E(A)=\\#\\{a,b,c,d\in A\mathrel{\mathop{\ordinarycolon}}a+b=c+d\\}$

(see [27, Chapter 2] for more details). Writing
$\mathcal{A}_{N}=(a_{n})_{n\leqslant N}$ for the set of the first $N$ elements
of $\mathcal{A},$ Aistleitner, Larcher & Lewko [2] proved that whenever
$E(\mathcal{A}_{N})=\mathcal{O}(N^{3-\varepsilon}),N\to\infty$ for some
$\varepsilon>0,$ then the sequence $(a_{n}x)_{n\in\mathbb{N}}$ has Poissonian
pair correlations for almost all $x\in[0,1].$ Examining to what extent this
bound on the additive energy is optimal, Bourgain [2, Appendix] showed that if
$E(\mathcal{A}_{N})=\Omega(N^{3}),N\to\infty$ then $(a_{n}x)_{n\in\mathbb{N}}$
does not have Poissonian pair correlations for all $x$ in a subset of $[0,1]$
of positive Lebesgue measure, while on the other hand there exists a sequence
$\mathcal{A}=(a_{n})\subseteq\mathbb{N}$ with
$E(\mathcal{A}_{N})=o(N^{3}),N\to\infty$ such that $(a_{n}x)_{n\in\mathbb{N}}$
does not have Poissonian pair correlations for almost all $x\in[0,1].$

In the present paper, we are able to deduce an analogue of the first –
mentioned result of Bourgain, proving that when the additive energy of
$\mathcal{A}$ is of maximal order of magnitude, then the sequence
$(a_{n}x)_{n\in\mathbb{N}}$ fails to have Poissonian triple correlations (i.e.
of order $k=3$) for Lebesgue almost all $x$. Further, as mentioned previously,
we use Theorem 1.3 to generalise the second – mentioned result of Bourgain for
$k$ – th order correlations.

######  Theorem 1.4.

(i) There exists a set $\mathcal{A}=(a_{n})_{n=1}^{\infty}\subseteq\mathbb{N}$
with additive energy $E(\mathcal{A}_{N})=o(N^{3}),N\to\infty$ such that for
Lebesgue almost all $x\in[0,1]$ the sequence $(a_{n}x)_{n=1}^{\infty}$ does
not have Poissonian correlations of any order $k\geqslant 2.$

(ii) Let $\mathcal{A}=(a_{n}x)_{n\in\mathbb{N}}\subseteq\mathbb{N}$ be a
sequence such that $E(\mathcal{A}_{N})=\Omega(N^{3})$ as $N\to\infty$. Then
for all $x$ in a set of positive Lebesgue measure, $(a_{n}x)_{n\in\mathbb{N}}$
does not have Poissonian triple correlations.

###  1.3. Poissonian Correlations and the number of points in small intervals

As a final result of this paper, we seek to exhibit a connection of the
property of Poissonian k – th correlations with the number of elements of a
sequence in sufficiently small intervals. More formally, given $s>0$ and
$N\geqslant 1$ we define

(7) $F(t,s,N)=\\#\Big{\\{}n\leqslant
N\mathrel{\mathop{\ordinarycolon}}\|x_{n}-t\|\leqslant\frac{s}{2N}\Big{\\}},\qquad
0\leqslant t\leqslant 1.$

Heuristically, if $t$ is seen as a random variable uniformly distributed in
$[0,1]$, then $F(t)=F(t,s,N)$ can be viewed as the number of points of the
sequence $(x_{n})_{n\in\mathbb{N}}$ in a random interval of length $s/N$.

Our purpose is to establish a link between the property of Poissonian $k$ – th
correlations and the asymptotic size of the $k$ – th moment of $F(t,s,N)$. For
the $k=2$ case, it is already known that a sequence $(x_{n})_{n\in\mathbb{N}}$
has Poissonian pair correlations if and only if

$\lim_{N\to\infty}\int_{0}^{1}F(t,s,N)^{2}\,\mathrm{d}t=s^{2}+s\qquad\text{
for all }s>0.$

This is shown in [15] and also implicitly in [10, Thm 3(i)]. Regarding
correlations of higher orders, some relevant results are shown in [28] for the
triple correlations of sequences of the form $(n^{2}\alpha)_{n\in\mathbb{N}}$
and for values of the length $s>0$ that lie in a range that depends on $N$.

We hereby consider both the $k$ – th moment of $F(t,s,N)$ as well as its $k$ –
th factorial moment. To be more specific, given $s>0,N\geqslant 1$ and
$k\geqslant 2$ we set

(8) $\displaystyle I_{k}(s,N)$
$\displaystyle=\int_{0}^{1}F(t,s,N)(F(t,s,N)-1)\cdots(F(t,s,N)-(k-1))\,\mathrm{d}t,$
$\displaystyle I_{k}^{*}(s,N)$
$\displaystyle=\int_{0}^{1}F(t,s,N)^{k}\,\mathrm{d}t.$

We prove that the property of Poissonian correlations of $k$ – th order is
reflected in the asymptotic behaviour of $I_{k}(s,N)$ and $I_{k}^{*}(s,N).$

######  Theorem 1.5.

Let $k\geqslant 2$ and $I_{k}(s,N),I_{k}^{*}(s,N)$ be as in (8). Assume the
sequence $(x_{n})_{n\in\mathbb{N}}$ has Poissonian $k$ – th correlations. Then
the following statements hold:
(i) $\lim\limits_{N\to\infty}I_{k}(s,N)=s^{k}$ for all $s>0.$
(ii)
$\limsup\limits_{N\to\infty}I_{k}^{*}(s,N)=s^{k}+\mathcal{O}_{k}(s^{k-1}),\quad
s\to\infty$.
(iii) If, in addition, $(x_{n})_{n\in\mathbb{N}}$ has Poissonian $\ell$ –
correlations for all $\ell\leqslant k$, then

(9) $\lim_{N\to\infty}I_{k}^{*}(s,N)=s^{k}+c_{k,k-1}s^{k-1}+\ldots+c_{k,1}s,$

where $c_{k,i},i=1,\ldots,k-1$ denote the Stirling numbers of the second kind.

Theorem 1.5 provides further evidence for the connection between sequences
with Poissonian correlations on the one hand, and random variables that follow
the Poisson distribution on the other. It is known [20] that the $k$ – th
factorial moment of a random variable following the Poisson distribution with
parameter $s>0$ is equal to $s^{k}$, while its $k$ – th moment is equal to the
polynomial on the right – hand side of (9) (this is called the Bell polynomial
of degree $k,$ see also [5]).

###  1.4. Notation

Given two functions
$f,g\mathrel{\mathop{\ordinarycolon}}(0,\infty)\to\mathbb{R},$ we write
$f(t)=\mathcal{O}(g(t)),t\to\infty,$ $f(t)=o(g(t)),t\to\infty$ and
$f(t)=\Omega(g(t)),t\to\infty$ when

$\limsup_{t\to\infty}\frac{|f(t)|}{|g(t)|}<\infty,\quad\quad\lim_{t\to\infty}\frac{f(t)}{g(t)}=0\quad\text{
or }\quad\limsup_{t\to\infty}\frac{f(t)}{g(t)}>0$

respectively. Any dependence of the value of the limsup above on potential
parameters is denoted by the appropriate subscripts in the $\mathcal{O}$ –
symbol. Given a real number $x\in\mathbb{R},$ we write $\\{x\\}$ for the
fractional part of $x$,
$\|x\|=\min\\{|x-k|\mathrel{\mathop{\ordinarycolon}}k\in\mathbb{N}\\}$ for the
distance of $x$ from its nearest integer, and

$(\\!(x)\\!)=\begin{cases}\\{x\\},&\text{ if
}0\leqslant\\{x\\}\leqslant\tfrac{1}{2}\\\ \\{x\\}-1,&\text{ if
}\tfrac{1}{2}<\\{x\\}<1\end{cases}$

for the signed distance of $x$ from the origin modulo $1$. Further, we use the
symbol $\\{\,\cdot\,\\}^{+}$ for the function

$\\{x\\}^{+}=\begin{cases}x,&\text{ if }x\geqslant 0\\\ 0,&\text{ if
}x<0.\end{cases}$

Throughout the paper, we shall implicitly consider the unit interval $[0,1]$
equipped with the topology induced by
$\mathinner{\\!\left\lVert\,\cdot\,\right\rVert}$ because we deal with
distribution of sequences modulo $1$. This is homeomorphic to the interval
$[0,1)$ with the same topology, so for convenience, we will work
interchangingly with $[0,1]$ and $[0,1)$.

We use the standard notation $e(x)=e^{2\pi ix}.$ We also write
$B(x_{0},r)=\\{x\in[0,1]\mathrel{\mathop{\ordinarycolon}}\|x-x_{0}\|\leqslant
r\\}$ for the interval with center $x_{0}$ and length $2r$ modulo $1$. The
characteristic function of a set $A$ is denoted by $\mathds{1}_{A}.$

###  1.5.  Directions for Further Research

We end this introductory part with some interesting questions that would shed
more light on the properties of sequences with Poissonian correlations of $k$
– th order.

$\bullet$ In Theorem 1.1 we proved that when a sequence
$(x_{n})_{n\in\mathbb{N}}$ has Poissonian $k$ – th correlations it is
uniformly distributed, but we do not know whether the correlations of orders
$m<k$ also follow the Poissonian model. Are Poissonian correlations of order
$k+1$ a property stronger than Poissonian correlations of order $k$? In other
words, does any sequence $(x_{n})_{n\in\mathbb{N}}$ with Poissonian $k$ – th
correlations also have Poissonian correlations of all orders $2\leqslant m<k?$

$\bullet$ We would like to know if some partial converse to Theorem 1.5 is
true. Is it true, for example, that whenever (9) holds, the sequence
$(x_{n})_{n\in\mathbb{N}}$ has Poissonian correlations of all orders up to
$k$?

##  2\. Properties of the functions $R_{k},R_{k}^{*}$.

In the present section we prove several properties of the functions $R_{k}$
and $R_{k}^{*}$ defined in the introduction that will be used later in the
proof of the main results.

We start by proving the inequality that will be the key ingredient in the
proof of Proposition 2.2.

######  Lemma 2.1.

Let $m\geqslant 1.$ For any $M\geqslant 1$ and for all non-negative real
numbers $x_{1},x_{2},\ldots,x_{M}\geqslant 0$ we have

(10)
$(x_{1}^{m+1}+x_{2}^{m+1}+\ldots+x_{M}^{m+1})\geqslant\frac{1}{M}(x_{1}+x_{2}+\ldots+x_{M})(x_{1}^{m}+x_{2}^{m}+\ldots+x_{M}^{m}).$

###### Proof.

Applying the Hölder inequality with exponents $p=m+1$ and $q=(m+1)/m$ to the
$M$–tuples $(x_{1},\ldots,x_{M})$ and $(1,\ldots,1)$ we get

(11)
$x_{1}+x_{2}+\ldots+x_{M}\leqslant\left(x_{1}^{m+1}+\ldots+x_{M}^{m+1}\right)^{\frac{1}{m+1}}M^{\frac{m}{m+1}},$

while the Hölder inequality with the same exponents applied to the $M$–tuples
$(1,\ldots,1)$ and $(x_{1}^{m},\ldots,x_{M}^{m})$ yields

(12)
$x_{1}^{m}+x_{2}^{m}+\ldots+x_{M}^{m}\leqslant\left(x_{1}^{m+1}+\ldots+x_{M}^{m+1}\right)^{\frac{m}{m+1}}M^{\frac{1}{m+1}}.$

Multiplying (11) and (12), we obtain (10).∎

The following proposition provides a relation between correlation functions of
different orders. This result will later have a key role in the proof of both
Theorems 1.1 and 1.2, while it straightforwardly implies Theorem 1.3.

######  Proposition 2.2.

Let $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ be a sequence and $m\geqslant 2$.
There exists a constant $s_{m}>0$ such that for any $s>s_{m}$, the inequality

(13) $R_{m}\Big{(}\frac{s}{3},N\Big{)}\leqslant\dfrac{6}{s}R_{m+1}(s,N)$

holds for all $N\geqslant N_{0}(s,m).$ Moreover, the values of the constants
$s_{m}$ and $N_{0}$ are independent of the sequence
$(x_{n})_{n\in\mathbb{N}}$.

###### Proof.

We partition the unit interval into pieces of size approximately $s/N$ and
count points in each interval: we set

$K=K(s,N)=\left\lceil\frac{N}{s}\right\rceil$

and for $0\leqslant\ell\leqslant K-1$ we define

$y_{\ell}=y_{\ell}(s,N)=\\#\Big{\\{}1\leqslant i\leqslant
N\mathrel{\mathop{\ordinarycolon}}x_{i}\in\left[\tfrac{\ell
s}{N},\tfrac{(\ell+1)s}{N}\right)\cap[0,1]\Big{\\}}.$

Observe that

$\displaystyle R_{m+1}(s,N)$ $\displaystyle\geqslant$
$\displaystyle\frac{1}{N}\sum_{\ell=0}^{K-1}y_{\ell}(y_{\ell}-1)\ldots(y_{\ell}-m)$
$\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{\ell=0}^{K-1}\Big{(}y_{\ell}^{m+1}-c_{m}y_{\ell}^{m}+c_{m-1}y_{\ell}^{m-1}-\ldots+(-1)^{m}c_{1}y_{\ell}\Big{)}$

with $c_{i}\in\mathbb{N}$.

First, we consider the case when $m$ is odd. Since
$y_{0}+y_{1}+\ldots+y_{K-1}=N,$ applying inequality (10) to (2) we obtain

$R_{m+1}(s,N)\geqslant\frac{1}{N}\sum_{\ell=0}^{K-1}[(\tfrac{N}{K}-c_{m})y_{\ell}^{m}+(\tfrac{N}{K}c_{m-1}-c_{m-2})y_{\ell}^{m-2}+\ldots+(\tfrac{N}{K}c_{2}-c_{1})y_{\ell}].$

Note that for any $\varepsilon>0$, we find that for $N$ sufficiently large
$\dfrac{N}{K}\geqslant(1-\varepsilon)s$ and therefore

$R_{m+1}(s,N)\geqslant\frac{1}{N}\sum_{\ell=0}^{K-1}[((1-\varepsilon)s-c_{m})y_{\ell}^{m}+((1-\varepsilon)sc_{m-1}-c_{m-2})y_{\ell}^{m-2}+\ldots+((1-\varepsilon)sc_{2}-c_{1})y_{\ell}].$

Similarly, for $m$ even, we have

$R_{m+1}(s,N)\geqslant\frac{1}{N}\sum_{\ell=0}^{K-1}[((1-\varepsilon)s-c_{m})y_{\ell}^{m}+((1-\varepsilon)sc_{m-1}-c_{m-2})y_{\ell}^{m-2}+\ldots+((1-\varepsilon)sc_{3}-c_{2})y_{\ell}^{2}+c_{1}y_{\ell}].$

Now let $\varepsilon>0$ be small enough such that
$s(1-\varepsilon)>s_{m}\mathrel{\mathop{\ordinarycolon}}=2\max\\{c_{i}\mathrel{\mathop{\ordinarycolon}}1\leqslant
i\leqslant m\\}$. Then all non – leading terms are positive and hence we can
estimate

$R_{m+1}(s,N)\geqslant\frac{1}{N}\sum_{\ell=0}^{K-1}((1-\varepsilon)s-c_{m})y_{\ell}^{m}\geqslant\frac{s}{2}\cdot\frac{1}{N}\sum_{\ell=0}^{K-1}y_{\ell}^{m},$

which implies that

(14)
$\frac{1}{N}\sum_{\ell=0}^{K-1}y_{l}^{m}\leqslant\frac{2R_{m+1}(s,N)}{s}\cdot$

We now seek an upper bound for $R_{m}(\frac{s}{3},N)$. For each
$0\leqslant\ell\leqslant K-1$ consider the sets

$A_{\ell}=\left[\frac{s\ell}{N},\frac{s(\ell+1)}{N}\right),\qquad
A_{\ell}^{\prime}=A_{\ell}+\frac{s}{3N},\qquad
A_{\ell}^{\prime\prime}=A_{\ell}+\frac{2s}{3N}\,$

(where we understand the intervals modulo 1). Here we have essentially defined
three different partitions of the unit interval: the partition
$(A_{\ell})_{\ell=0}^{K-1}$ we employed previously, and the partitions
$(A_{\ell}^{\prime})_{\ell=0}^{K-1}$ and
$(A_{\ell}^{\prime\prime})_{\ell=0}^{K-1}$ that we get by shifting the
intervals of the first partition by $s/3N$ and $2s/3N$ respectively. Writing
$y_{\ell}^{\prime},y_{\ell}^{\prime\prime}$ for the number of points $x_{i}$
in $A_{\ell}^{\prime}$ and $A_{\ell}^{\prime\prime}$ respectively, it is
straightforward to show that an analogue of (14) holds for
$(y_{\ell}^{\prime})_{\ell=0}^{K-1}$ and
$(y_{\ell}^{\prime\prime})_{\ell=0}^{K-1}$.

At this point, we need to employ the following Lemma, the proof of which we
postpone for later in the text.

######  Lemma 2.3.

If the $m$ – tuple $(x_{i_{1}},\ldots,x_{i_{m}})$ contributes something to the
sum $R_{m}(\frac{s}{3},N)$, then there exists some $0\leqslant\ell\leqslant
K-1$ such that the points $x_{i_{1}},x_{i_{2}},\ldots,x_{i_{m}}$ belong all to
$A_{\ell}$ or to $A_{\ell}^{\prime}$ or to $A_{\ell}^{\prime\prime}$.

Using Lemma 2.3 we finally obtain

$\displaystyle R_{m}\Big{(}\frac{s}{3},N\Big{)}\leqslant$
$\displaystyle\frac{1}{N}\sum_{\ell=0}^{K-1}y_{\ell}(y_{\ell}-1)\ldots(y_{\ell}-(m-1))+\frac{1}{N}\sum_{\ell=0}^{K-1}y_{\ell}^{\prime}(y_{\ell}^{\prime}-1)\ldots(y_{\ell}^{\prime}-(m-1))$
$\displaystyle+\frac{1}{N}\sum_{\ell=0}^{K-1}y_{\ell}^{\prime\prime}(y_{\ell}^{\prime\prime}-1)\ldots(y_{\ell}^{\prime\prime}-(m-1))$
$\displaystyle\leqslant$
$\displaystyle\frac{1}{N}\sum_{\ell=0}^{K-1}\big{(}y_{\ell}^{m}+(y_{\ell}^{\prime})^{m}+(y_{\ell}^{\prime\prime})^{m}\big{)}\leqslant\frac{6}{s}R_{m+1}(s,N).$

∎

We now provide the proof of Lemma 2.3.

###### Proof of Lemma 2.3.

Since the $m$ – tuple $(x_{i_{1}},\ldots,x_{i_{m}})$ contributes to
$R_{m}(\frac{s}{3},N)$, we have for all $j,k=1,2,\ldots,m$ that

(15) $\lVert x_{i_{j}}-x_{i_{k}}\rVert\leqslant\lVert
x_{i_{j}}-x_{i_{1}}\rVert+\lVert
x_{i_{1}}-x_{i_{k}}\rVert\leqslant\frac{2s}{3N}\cdot$

For each $0\leqslant\ell\leqslant K-1$ the set $A_{\ell}$ can be written as a
disjoint union

(16) $A_{\ell}=(A_{\ell}\cap A_{\ell-1}^{\prime})\sqcup(A_{\ell}^{\prime}\cap
A_{\ell-1}^{\prime\prime})\sqcup(A_{\ell}\cap A_{\ell}^{\prime\prime})$

where the three disjoint sets $A_{\ell}\cap
A_{\ell-1}^{\prime},A_{\ell}^{\prime}\cap A_{\ell-1}^{\prime\prime}$ and
$A_{\ell}\cap A_{\ell}^{\prime\prime}$ appearing are consecutive disjoint
intervals of length $s/3N.$

We may assume without loss of generality that the points
$x_{i_{2}},x_{i_{3}},\ldots,x_{i_{m}}$ are in increasing order; that is, the
signed distances of differences of consecutive terms are
$(\\!(x_{i_{n+1}}-x_{i_{n}})\\!)\geqslant 0$ for $n=2,\ldots,m-1.$

We consider two different cases regarding the relative position of $x_{i_{1}}$
with respect to $x_{i_{2}}.$ If $(\\!(x_{i_{2}}-x_{i_{1}})\\!)\geqslant 0,$
let $0\leqslant\ell\leqslant K-1$ be such that $x_{i_{1}}\in A_{\ell}.$ Then
$x_{i_{1}}$ lies in one of the three sets in the disjoint union in (16);
assume without loss of generality $x_{i_{1}}\in A_{\ell}\cap
A_{\ell-1}^{\prime}.$ Since $\|x_{i_{1}}-x_{i_{m}}\|\leqslant 2s/(3N)$ by (15)
and the points $x_{i_{1}},x_{i_{2}},\ldots,x_{i_{m}}$ are in increasing order,
they will all lie in $A_{\ell}^{\prime}\cap A_{\ell-1}^{\prime\prime}$ or
$A_{\ell}\cap A_{\ell}^{\prime\prime}$, and therefore they will all lie in
$A_{\ell}.$ Similarly, we see that if $x_{i_{1}}\in A_{\ell}^{\prime}\cap
A_{\ell-1}^{\prime\prime}$ then all points lie in $A_{\ell}^{\prime}$ while if
$x_{i_{1}}\in A_{\ell}\cap A_{\ell}^{\prime\prime}$ then they will all lie
inside $A_{\ell}^{\prime\prime}.$ If $(\\!(x_{i_{1}}-x_{i_{2}})\\!)>0$, we
repeat the same argument with the point $x_{i_{2}}$ in the place of
$x_{i_{1}}.$ The lemma is now proved.

∎

######  Remark.

Proposition 2.2 provides an inequality involving the correlation functions
$R_{k}(\tfrac{s}{3},N)$ and $R_{k+1}(s,N)$ only for values of the scale $s>0$
that are large enough. This is not a restriction that comes from the method of
proof followed, but rather a genuine obstruction, as can be seen by the
following example. Define the sequence $(x_{n})_{n\in\mathbb{N}}$ by

$x_{n}=\frac{1}{2^{m}}\big{(}2\big{\lceil}\tfrac{k}{2}\big{\rceil}-1\big{)}\quad\text{whenever
}n=2^{m}+k,\,m\geqslant 0\text{ and }1\leqslant k\leqslant 2^{m}.$

That is, $x_{1}=x_{2}=0,$ $x_{3}=x_{4}=\frac{1}{2},$
$x_{5}=x_{6}=\frac{1}{4}$, $x_{7}=x_{8}=\frac{3}{4}$ etc. Then for the choice
of the scale $s<2$ and for every integer of the form $N=2^{m}$ we have

$R_{2}(s,N)=1\quad\text{ but }\quad R_{3}(s,N)=0.$

Using similar arguments we can define sequences for which $R_{m}(s,N)=1$ and
$R_{m+1}(s,N)=0$ for some given $s>0$ and for infinitely many $N\geqslant 1.$
The upshot is that we cannot obtain an analogue of (13) that holds for all
values of $s>0.$

The next proposition connects the size of $R_{k}(s_{1},\ldots,s_{k-1},N)$ with
the size of $R_{k}^{*}(s_{1},\ldots,s_{k-1},N)$ when the scales
$s_{1},\ldots,s_{k-1}$ are written in decreasing order.

######  Proposition 2.4.

Let $s_{1}\geqslant s_{2}\geqslant\ldots\geqslant s_{k-1}>0$. Defining
$R_{1}(s,N)=1$ for all $s>0$ and $N\geqslant 1$, we have

$R_{k}^{*}(s_{1},\ldots,s_{k-1},N)\leqslant
R_{k}(s_{1},\ldots,s_{k-1},N)+\sum_{m=1}^{k-1}b_{m}R_{m}(s_{1},\ldots,s_{m-1},N),$

where $b_{1},\ldots,b_{k-1}\in\mathbb{N}$ are constants depending only on $k$.

###### Proof.

Observe that if a $k$ – tuple $(i_{1},i_{2},\ldots,i_{k})$ consists of
distinct indices $i_{1},\ldots,i_{k}\leqslant N$ then its contribution to
$R_{k}^{*}(s_{1},\ldots,s_{k-1},N)$ defined in (6) is the same as its
contribution to $R_{k}(s_{1},\ldots,s_{k-1},N),$ however the situation is
different when the indices $i_{1},\ldots,i_{k}$ are not pairwise distinct.

Any $k$ – tuple $\mathbf{i}=(i_{1},i_{2},\ldots,i_{k})$ gives rise to a
uniquely determined partition
$\mathcal{P}_{\mathbf{i}}=\\{J_{1},J_{2},\ldots,J_{m}\\}$ of
$[k]=\\{1,2,\ldots,k\\}$ (where $m\leqslant k$) such that the following
properties hold:

  1. (i)

$i_{j}=i_{\ell}\Leftrightarrow(j,\ell\in J_{t}\,\text{ for some }t\leqslant
m)$

  2. (ii)

$\min J_{i}<\min J_{i+1},\quad i=1,\ldots,m-1.$

Conversely, given a partition $\mathcal{P}=\\{J_{1},J_{2},\ldots,J_{m}\\}$ of
$[k]$ with the property that $\min J_{t}<\min J_{t+1}$ for $t=1,2,\ldots,m-1$,
we define the correlation counting function
$R_{k}^{\mathcal{P}}=R_{k}^{\mathcal{P}}(s_{1},\ldots,s_{k-1},N)$ by

$R_{k}^{\mathcal{P}}=\\#\frac{1}{N}\left\\{\mathbf{i}\in[N]^{k},\mathcal{P}_{\mathbf{i}}=\mathcal{P}\mathrel{\mathop{\ordinarycolon}}\lVert
x_{i_{1}}-x_{i_{2}}\rVert\leqslant\frac{s_{1}}{N},\ldots,\|x_{i_{1}}-x_{i_{k}}\|\leqslant\frac{s_{k-1}}{N}\right\\}.$

That is, $R_{k}^{\mathcal{P}}$ is the variant of $R_{k}$ that counts
correlations only over indices $i_{1},\ldots,i_{k}\leqslant N$ with partition
$\mathcal{P}_{\mathbf{i}}$ equal to $\mathcal{P}.$

Now if for a fixed partition $\mathcal{P}$ as above we set

$j_{r}=\min J_{r},\qquad r=1,2,\ldots,m$

then we have that $j_{r}\geqslant r$. Write
$J_{r}=\\{t_{1}<t_{2}<\ldots<t_{s}\\}$ for one of the sets comprising
$\mathcal{P}.$ In view of the hypothesis that $s_{1}\geqslant
s_{2}\geqslant\ldots\geqslant s_{k-1}$, the inequalities

$\|x_{i_{1}}-x_{i_{t_{\ell}}}\|\leqslant\frac{s_{t_{\ell}-1}}{N},\qquad\ell=1,\ldots,s$

appearing in the definition of $R_{k}^{\mathcal{P}},$ altogether imply that

$\|x_{i_{1}}-x_{i_{t_{\ell}}}\|\leqslant\frac{s_{t_{\ell}-1}}{N}\leqslant\frac{s_{t_{1}-1}}{N}=\frac{s_{j_{r}-1}}{N}\leqslant\frac{s_{r-1}}{N},\quad\ell=1,\ldots,s.$

Thus for the fixed partition $\mathcal{P}=\\{J_{1},\ldots,J_{m}\\}$ as above,
we have

$\displaystyle R_{k}^{\mathcal{P}}(s_{1},\ldots,s_{k-1},N)$
$\displaystyle\leqslant R_{m}(s_{1},\ldots,s_{m-1},N).$

Finally, for the counting function $R_{k}^{*}$, summing over all possible
partitions $\mathcal{P}$ of $[k]$ we deduce that

$\displaystyle R_{k}^{*}(s_{1},\ldots,s_{k-1},N)$
$\displaystyle=\sum_{\mathcal{P}}R_{k}^{\mathcal{P}}(s_{1},\ldots,s_{k-1},N)$
$\displaystyle=\sum_{\mathcal{P}\mathrel{\mathop{\ordinarycolon}}|\mathcal{P}|=k}R_{k}^{\mathcal{P}}(s_{1},\ldots,s_{k-1},N)+\sum_{\begin{subarray}{c}1\leqslant
m\leqslant k-1\\\
\mathcal{P}\mathrel{\mathop{\ordinarycolon}}|\mathcal{P}|=m\end{subarray}}R_{k}^{\mathcal{P}}(s_{1},\ldots,s_{k-1},N)$
$\displaystyle\leqslant\,R_{k}(s_{1},\ldots,s_{k-1},N)+\sum_{m=1}^{k-1}b_{m}R_{m}(s_{1},\ldots,s_{m-1},N),$

with $b_{m}\in\mathbb{N},\,m=1,\ldots,k-1$. ∎

######  Remark.

(i) Proposition 2.4 uses a combinatorial argument to derive a relation between
the pair correlation function $R_{k}$ and $R_{k}^{*},$ which is the
corresponding sum over not necessarily distinct indices. A similar argument
can be found in [22, Chapter 4].

(ii) The constants $c_{i}=c_{i}(m)$ appearing in the proof of Proposition 2.2
are the unsigned Stirling numbers of the first kind and the numbers
$b_{i}=b_{i}(k)$ from Proposition 2.4 are the Stirling numbers of the second
kind. This can be easily seen from (2) and the definition of the $b_{i}$ as
the number of partitions of $[k]$ into $i$ nonempty subsets, respectively (see
[4] for more details).

######  Corollary 2.5.

Let $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ be an arbitrary sequence. For all
$s>0$ large enough we have

(17) $R_{k}(s,N)\leqslant R_{k}^{*}(s,N)\leqslant
R_{k}(s,N)+\mathcal{O}_{k}\left(\frac{1}{s}R_{k}(3^{k}s,N)\right),\qquad
N\to\infty$

If $(x_{n})_{n\in\mathbb{N}}$ has Poissonian k – th correlations, we have for
$s$ sufficiently large

(18) $R_{k}^{*}(s,N)=(2s)^{k-1}+\mathcal{O}(s^{k-2}),\qquad N\to\infty.$

###### Proof.

(18) follows immediately from (17) under the assumption of Poissonian k – th
correlations. Also, the first inequality of (17) is obvious. For the second
inequality of (17), we use Proposition 2.2 and monotonicity of $R_{k}(s,N)$ in
$s$ to deduce that for $1\leqslant i\leqslant k-1,$

$R_{i}(s,N)\ll_{i,k}\frac{1}{s^{k-i}}R_{k}(3^{k-i}s,N)\leqslant\frac{1}{s}R_{k}(3^{k}s,N),\qquad
N\to\infty$

for all $s>0$ sufficiently large. Using Proposition 2.4, the result follows. ∎

Corollary 2.5 shows us that for $s$ large enough, we can work with $R_{k}^{*}$
instead of $R_{k}$. The function $R_{k}^{*}$ satisfies the following
inequalities that will be used in the proofs of Theorems 1.1 and 1.2.

######  Proposition 2.6.

(i) For any $s>0$ and $N\geqslant 1,$

(19) $R_{2}^{*}(s,N)^{k-1}\leqslant R_{k}^{*}(s,N).$

(ii) Let $s_{1},s_{2},\ldots,s_{k-1}>0$ and $N\geqslant 1$. Then

(20) $R_{k}^{*}(s_{1},\ldots,s_{k-1},N)^{k-1}\leqslant
R_{k}^{*}(s_{1},N)\,R_{k}^{*}(s_{2},N)\cdots R_{k}^{*}(s_{k-1},N).$

###### Proof.

For any $s>0$ and $N\geqslant 1$ we define

$z_{i}(s,N)=\\#\Big{\\{}j\leqslant N\mathrel{\mathop{\ordinarycolon}}\lVert
x_{i}-x_{j}\rVert\leqslant\frac{s}{N}\Big{\\}},\quad i\leqslant N.$

Under this notation, we observe that for $k\geqslant 2$ and
$s_{1},s_{2},\ldots,s_{k-1}>0$ we have

(21) $R_{k}^{*}(s_{1},\ldots,s_{k-1},N)=\frac{1}{N}\sum_{i\leqslant
N}z_{i}(s_{1},N)\cdot\ldots\cdot z_{i}(s_{k-1},N).$

For (19), an application of the Hölder inequality with $p=k-1$ and
$q=(k-1)/(k-2)$ gives

$R_{2}^{*}(s,N)^{k-1}=\Big{(}\frac{1}{N}\sum_{i\leqslant
N}z_{i}(s,N)\Big{)}^{k-1}\leqslant\frac{1}{N}\sum_{i\leqslant
N}z_{i}(s,N)^{k-1}=R_{k}^{*}(s,N).$

Applying the Hölder inequality with exponents $p_{i}=k-1,(1\leqslant
i\leqslant k-1)$ to (21) we obtain (20). ∎

##  3\. Proof of Theorem 1.1

Here we prove that sequences with Poissonian correlations of $k$ – th order
are uniformly distributed. We argue as in the proof of [1, Theorem 2]: if the
sequence $(x_{n})_{n\in\mathbb{N}}$ is not uniformly distributed, then there
exists some $a\in(0,1)$ such that relation
$\lim\limits_{N\to\infty}\frac{1}{N}\\#\\{n\leqslant
N\mathrel{\mathop{\ordinarycolon}}x_{i}\in[0,a]\\}=a$ fails, and by the
Bolzano – Weierstrass theorem there exists a sequence $(N_{j})_{j=1}^{\infty}$
and a number $b\neq a$ such that

$\lim\limits_{j\to\infty}\frac{1}{N_{j}}\\#\\{n\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}x_{i}\in[0,a]\\}=b.$

We need the following lemma, which tells us that under the assumption of
Poissonian correlations of $k$ – th order, the proportion of points in a ball
with sufficiently fast shrinking radius has to be asymptotically zero.

######  Lemma 3.1.

Let $k\geqslant 2.$ If $(x_{n})_{n\in\mathbb{N}}$ is a sequence with
Poissonian $k$ – th correlations and $t\in[0,1],$ then for any $s>0$ we have

$\lim_{N\to\infty}\frac{1}{N}\\#\Big{\\{}n\leqslant
N\mathrel{\mathop{\ordinarycolon}}\|x_{n}-t\|\leqslant\frac{s}{2N}\Big{\\}}=0.$

###### Proof.

Assume for contradicition that there exist $t\in[0,1],s>0$ and $\eta>0$ such
that

$\frac{1}{N}\\#\Big{\\{}n\leqslant
N\mathrel{\mathop{\ordinarycolon}}\|x_{n}-t\|\leqslant\frac{s}{2N}\Big{\\}}\geqslant\eta\quad\text{
for inf. many }N\geqslant 1.$

For such values of $N\geqslant 1$ we have

$\displaystyle R_{k}(s,N)$ $\displaystyle\geqslant\frac{1}{N}\eta N\cdot(\eta
N-1)\cdot\ldots\cdot(\eta N-(k-1))$
$\displaystyle=\eta^{k}N^{k-1}+\mathcal{O}(N^{k-2}),\qquad N\to\infty,$

which contradicts the assumption of Poissonian $k$ – th correlations. ∎

We can now apply Lemma 3.1 with $t=a$ and $t=0$ to deduce that for
$\varepsilon>0$ small enough, we have

$\displaystyle\frac{1}{N_{j}}\\#\Big{\\{}n\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}\frac{s}{2N_{j}}\leqslant x_{n}\leqslant
a-\frac{s}{2N_{j}}\Big{\\}}$ $\displaystyle=\frac{1}{N_{j}}\\#\\{n\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}x_{i}\in[0,a]\\}$
$\displaystyle\qquad-\frac{1}{N_{j}}\\#\Big{\\{}n\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}0\leqslant
x_{n}<\frac{s}{2N_{j}}\Big{\\}}$
$\displaystyle\qquad-\frac{1}{N_{j}}\\#\Big{\\{}n\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}a-\frac{s}{2N_{j}}<x_{n}\leqslant
a\Big{\\}}$ $\displaystyle\geqslant b-\varepsilon$

and also

$\displaystyle\frac{1}{N_{j}}\\#\Big{\\{}n\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}a+\frac{s}{2N_{j}}\leqslant
x_{n}\leqslant 1-\frac{s}{2N_{j}}\Big{\\}}$ $\displaystyle\geqslant
1-b-\varepsilon$

for all $j\geqslant 1$ sufficiently large.

For these values of $j,$ if $F(t,s,N)$ is the function defined in (7), we see
that

$\displaystyle\int_{0}^{a}F(t,s,N_{j})\,\mathrm{d}t$
$\displaystyle=\int_{0}^{a}\sum_{n\leqslant
N}\mathds{1}_{B(x_{n},\frac{s}{2N})}(t)\,\mathrm{d}t=\sum_{n\leqslant
N}\lambda\Big{(}B(x_{n},\frac{s}{2N})\cap[0,a]\Big{)}$
$\displaystyle\geqslant\frac{s}{N_{j}}\\#\Big{\\{}n\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}\frac{s}{2N_{j}}\leqslant x_{n}\leqslant
a-\frac{s}{2N_{j}}\Big{\\}}$ $\displaystyle\geqslant s(b-\varepsilon)$

and similarly

$\int_{a}^{1}F(t,s,N_{j})\mathrm{d}t\geqslant s(1-b-\varepsilon).$

Applying the Cauchy – Schwarz inequality we deduce that

$\displaystyle\int_{0}^{1}F(t,s,N_{j})^{2}\,\mathrm{d}t$ $\displaystyle=$
$\displaystyle\int_{0}^{a}F(t,s,N_{j})^{2}\,\mathrm{d}t+\int_{a}^{1}F(t,s,N_{j})^{2}\,\mathrm{d}t$
$\displaystyle\geqslant$
$\displaystyle\frac{1}{a}\left(\int_{0}^{a}F(t,s,N_{j})\,\mathrm{d}t\right)^{2}+\frac{1}{1-a}\left(\int_{a}^{1}F(t,s,N_{j})\,\mathrm{d}t\right)^{2}$
$\displaystyle\geqslant$
$\displaystyle\frac{s^{2}}{a}(b-\varepsilon)^{2}+\frac{s^{2}}{1-a}(1-b-\varepsilon)^{2}.$

Since $a\neq b,$ if we choose $\varepsilon>0$ small enough we have

$\frac{(b-\varepsilon)^{2}}{a}+\frac{(1-b-\varepsilon)^{2}}{1-a}=1+\delta\quad\text{
for some }\delta>0$

and therefore

(22)
$\displaystyle\int_{0}^{1}F(t,s,N_{j})^{2}\,\mathrm{d}t\geqslant(1+\delta)s^{2}$

for all $j\geqslant 1$ large enough. At this point, we present a simple fact
that connects the correlation functions $R_{2}^{*}(s,N)$ with the function
$F(t,s,N)$.

######  Lemma 3.2.

For any $s>0$, we have

(23)
$\int_{0}^{1}F(t,s,N)^{2}\,\mathrm{d}t=\int_{0}^{s}R_{2}^{*}(\sigma,N)\,\mathrm{d}\sigma.$

###### Proof.

By definition of $F(t,s,N)$, we see that

$\int_{0}^{1}F(t,s,N)^{2}\,\mathrm{d}t=\sum_{m,n\leqslant
N}\lambda\Big{(}B(x_{m},\frac{s}{2N})\cap
B(x_{n},\frac{s}{2N})\Big{)}=\sum_{m,n\leqslant
N}\Big{\\{}\frac{s}{N}-\|x_{m}-x_{n}\|\Big{\\}}^{+},$

while the definition of $R_{2}^{*}(s,N)$ gives

$\int_{0}^{s}R_{2}^{*}(\sigma,N)\,\mathrm{d}\sigma=\int_{0}^{s}\frac{1}{N}\sum_{m,n\leqslant
N}\mathds{1}_{[N\|x_{m}-x_{n}\|,\infty)}(\sigma)\,\mathrm{d}\sigma=\frac{1}{N}\sum_{m,n\leqslant
N}\Big{\\{}s-N\|x_{m}-x_{n}\|\Big{\\}}^{+}$

and these two terms on the right – hand sides of the equations above are
clearly equal. ∎

Combining (22) with (23) we get

(24)
$\int_{0}^{s}R_{2}^{*}(\sigma,N_{j})\,\mathrm{d}\sigma\geqslant(1+\delta)s^{2},$

and in turn using (24) with (19) and (18) we see that

$\displaystyle(1+\delta)s^{2}$
$\displaystyle\leqslant\int_{0}^{s}R_{2}^{*}(\sigma,N_{j})\,\mathrm{d}\sigma\leqslant\int_{0}^{s}R_{k}^{*}(\sigma,N_{j})^{\frac{1}{k-1}}\,\mathrm{d}\sigma=s^{2}+\mathcal{O}(s),\quad
j\to\infty$

which is a contradiction for values of $s$ which are sufficiently large.

##  4\.  Proof of Theorem 1.2

In this section we present the proof of Theorem 1.2, which generalises Theorem
B in the context of $k$ – th order correlations. We first present the
properties of the correlation functions $C_{k}(s,N)$ and $C_{k}^{*}(s,N)$ that
we use in the proof and then continue with the proof itself.

###  4.1. The functions $C_{k},C_{k}^{*}$.

For convenience, when $N\geqslant 1$ and $1\leqslant i,j\leqslant N$ we write

(25) $\lambda_{N}(s;i,j)=\lambda\Big{(}B\big{(}x_{i},\frac{s}{2N}\big{)}\cap
B\big{(}x_{j},\frac{s}{2N}\big{)}\Big{)}.$

As shown in the following proposition, the values of $C_{k}$ and $C_{k}^{*}$
can be expressed explicitly in terms of the numbers $\lambda_{N}(s;i,j).$

######  Proposition 4.1.

The functions $C_{k},C_{k}^{*}$ satisfy

$C_{k}(s_{1},\ldots,s_{k-1},N)=N^{k-2}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\
\mathrm{distinct}\end{subarray}}\lambda_{N}(s_{1};i_{1},i_{2})\lambda_{N}(s_{2};i_{1},i_{3})\ldots\lambda_{N}(s_{k-1};i_{1},i_{k})\vspace{-3mm}$

and

$C_{k}^{*}(s_{1},\ldots,s_{k-1},N)=N^{k-2}\sum_{i_{1},\ldots,i_{k}\leqslant
N}\lambda_{N}(s_{1};i_{1},i_{2})\lambda_{N}(s_{2};i_{1},i_{3})\ldots\lambda_{N}(s_{k-1};i_{1},i_{k}).$

###### Proof.

Note that for any $i,j\leqslant N$ and $s>0$,

$\int_{0}^{s}\\!\mathds{1}_{\left[0,\tfrac{\sigma}{N}\right]}\\!\left(\lVert
x_{i}-x_{j}\rVert\right)\mathrm{d}\sigma=\left\\{s-N\lVert
x_{i}-x_{j}\rVert\right\\}^{+}=N\lambda_{N}(s;i,j).$

Therefore,

$\displaystyle C_{k}^{*}(s_{1},\ldots,s_{k-1},N)$
$\displaystyle=\int_{0}^{s_{1}}\\!\\!\int_{0}^{s_{2}}\\!\cdots\\!\int_{0}^{s_{k-1}}R_{k}^{*}(\sigma_{1},\ldots,\sigma_{k-1},N)\,\mathrm{d}\sigma_{1}\mathrm{d}\sigma_{2}\ldots\mathrm{d}\sigma_{k-1}$
$\displaystyle=\frac{1}{N}\sum_{i_{1},\ldots,i_{k}\leqslant
N}\prod_{j=1}^{k-1}\int_{0}^{s_{j}}\mathds{1}_{\left[0,\tfrac{\sigma}{N}\right]}(\lVert
x_{1}-x_{j+1}\rVert)\,\mathrm{d}\sigma$
$\displaystyle=\frac{1}{N}\sum_{i_{1},\ldots,i_{k}\leqslant
N}\prod_{j=1}^{k-1}N\lambda_{N}(s_{j};i_{1},i_{j+1})$
$\displaystyle=N^{k-2}\sum_{i_{1},\ldots,i_{k}\leqslant
N}\lambda_{N}(s_{1};i_{1},i_{2})\lambda_{N}(s_{2};i_{1},i_{3})\ldots\lambda_{N}(s_{k-1};i_{1},i_{k}).$

The proof follows similarly for $C_{k}(s_{1},\ldots,s_{k-1},N)$. ∎

The next proposition gives a lower bound for the size of $C_{k}^{*}$. For
convenience, when we deal with $\lambda_{N}(s;i,j)$ as in (25) and the value
of $s>0$ is clear from the context, we suppress the dependence on $s$ and
simply write $\lambda_{N}(i,j).$

######  Proposition 4.2.

Let $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ be a sequence. For any $s>0$,

$C_{k}^{*}(s,N)\geqslant s^{2(k-1)}\qquad\text{ for all }\,N\geqslant 1.$

###### Proof.

By Proposition 4.1, we have

$\displaystyle C_{k}^{*}(s,N)=N^{k-2}\sum_{i_{1},\ldots,i_{k}\leqslant
N}\lambda_{N}(i_{1},i_{2})\lambda_{N}(i_{1},i_{3})\ldots\lambda_{N}(i_{1},i_{k}).$

Using the Hölder inequality with $p=(k-1)/(k-2)$ and $q=k-1$, we get

$\displaystyle C_{2}^{*}(s,N)^{k-1}$
$\displaystyle=\Bigg{(}\sum_{i_{1},i_{2}\leqslant
N}\lambda_{N}(i_{1},i_{2})\Bigg{)}^{k-1}$ $\displaystyle\leqslant
N^{k-2}\sum_{i_{1}=1}^{N}\Bigg{(}\sum_{i_{2}=1}^{N}\lambda_{N}(i_{1},i_{2})\Bigg{)}^{k-1}=C_{k}^{*}(s,N).$

On the other hand, if $F(t,s,N)$ is the function defined in (7), by Lemma 3.2
we have

$C_{2}^{*}(s,N)=\int_{0}^{s}R_{2}^{*}(\sigma,N)\mathrm{d}\sigma=\int_{0}^{1}F(t,s,N)^{2}\mathrm{d}t\geqslant\left(\int_{0}^{1}F(t,s,N)\mathrm{d}t\right)^{2}=s^{2},$

which implies that for any $N\geqslant 1$ we have $C_{k}^{*}(s,N)\geqslant
s^{2(k-1)}.$ ∎

For the proof of Theorem 1.2, we need to introduce a localised version of the
correlation functions $C_{k}^{*}(s,N)$. For any $s>0$ and any interval
$A\subseteq[0,1)$ we define the quantity

(26)
$C_{k}^{*}(A;s,N)\mathrel{\mathop{\ordinarycolon}}=N^{k-2}\mathop{\sum_{i_{1},\ldots,i_{k}\leqslant
N}}_{x_{i_{1}},\ldots,x_{i_{k}}\in
A}\lambda_{N}(i_{1},i_{2})\lambda_{N}(i_{1},i_{3})\ldots\lambda_{N}(i_{1},i_{k}).$

In view of Proposition 4.1, one can think of $C_{k}^{*}(A;s,N)$ as a
restriction of $C_{k}^{*}(s,N)$ on $A$. We intend to use the obvious fact that
for any partition $(A_{j})_{j=1}^{M}$ of the unit interval we have

(27) $C_{k}^{*}(s,N)\geqslant\sum_{j=1}^{M}C_{k}^{*}(A_{j};s,N).$

The following proposition generalises Proposition 4.2 for the localised
versions of the $C_{k}^{*}(s,N)$ in the context of Theorem 1.2.

######  Proposition 4.3.

Let $G\mathrel{\mathop{\ordinarycolon}}[0,1]\to\mathbb{R}$ be an asymptotic
distribution function of $(x_{n})_{n\in\mathbb{N}}$ and
$(N_{j})_{j\in\mathbb{N}}$ be a sequence as in (3). Let $k\geqslant 2$,
$A\subseteq[0,1]$ be an interval,
$a\mathrel{\mathop{\ordinarycolon}}=\lambda(A)$ be its Lebesgue measure and
$b\mathrel{\mathop{\ordinarycolon}}=\mu_{G}(A)$ be its Riemann – Stieltjes
measure with respect to $G$. Then for all $s>0$ we have

$\liminf_{j\to\infty}C_{k}^{*}(A,s,N_{j})\geqslant\frac{b^{k}}{a^{k-1}}s^{2(k-1)}.$

###### Proof.

Let $s>0$ arbitrary and assume without loss of generality that $A=[0,a]$. Let
$(x_{r_{n}})_{n=1}^{\infty}$ denote the subsequence of
$(x_{n})_{n=1}^{\infty}$ consisting of all terms that lie in $[0,a]$ and
define the sequence $(z_{n})_{n\in\mathbb{N}}$ by

$z_{n}=\frac{1}{a}x_{r_{n}},\qquad n\geqslant 1.$

We wish to establish a relation between $C_{k}^{*}([0,a],s,N)$ defined in (26)
and the correlation counting function $C_{k}^{*}(s,N)$ relevant to the
sequence $(z_{n})_{n\in\mathbb{N}}.$ Since we need to specify to which
sequence the counting function refers to, from now on we write
$C_{k}^{*}((z_{n})_{n\in\mathbb{N}},s,N)$ for the function $C_{k}^{*}$ that
refers to $(z_{n})_{n\in\mathbb{N}}$, and when we do not state which sequence
the correlation function $C_{k}^{*}$ refers to, it will be understood that it
refers to $(x_{n})_{n\in\mathbb{N}}.$

We define

$K_{N}=\\#\\{i\leqslant
N\mathrel{\mathop{\ordinarycolon}}x_{i}\in[0,a]\\},\qquad N\geqslant 1.$

Let $\varepsilon>0$. By the definitions of $a$ and $b$, there exists
$J\geqslant 1$ such that for all $j\geqslant J,$

(28) $(b-\varepsilon)N_{j}\,\,<\,\,\\#\\{i\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}x_{i}\in[0,a]\\}\,\,<\,\,(b+\varepsilon)N_{j}.$

Then for any $s>0$ we have

$\displaystyle C_{k}^{*}\left([0,a],s,N_{j}\right)$
$\displaystyle=N_{j}^{k-2}\mathop{\sum_{i_{1},\ldots,i_{k}\leqslant
N_{j}}}_{x_{i_{1}},\ldots,x_{i_{k}}\leqslant a}\prod_{2\leqslant p\leqslant
k}\lambda\Big{(}B\Big{(}x_{i_{1}},\frac{s}{2N_{j}}\Big{)}\cap
B\Big{(}x_{i_{p}},\frac{s}{2N_{j}}\Big{)}\Big{)}$ (29)
$\displaystyle=N_{j}^{k-2}\sum_{i_{1},\ldots,i_{k}\leqslant
K_{N_{j}}}\prod_{2\leqslant p\leqslant
k}\lambda\Big{(}B\Big{(}az_{i_{1}},\frac{s}{2N_{j}}\Big{)}\cap
B\Big{(}az_{i_{p}},\frac{s}{2N_{j}}\Big{)}\Big{)}.$

At this point, we notice that when $N_{j}$ is sufficiently large, the measure
of the intersections appearing in the right-hand side of (29) is

$\displaystyle\lambda\Big{(}B\Big{(}az_{i_{1}},\frac{s}{2N_{j}}\Big{)}\cap
B\Big{(}az_{i_{p}},\frac{s}{2N_{j}}\Big{)}\Big{)}=a\lambda\Big{(}B\Big{(}z_{i_{1}},\frac{s}{2aN_{j}}\Big{)}\cap
B\Big{(}z_{i_{p}},\frac{s}{2aN_{j}}\Big{)}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eps_close}}}{{\geqslant}}a\lambda\Big{(}B\Big{(}z_{i_{1}},\frac{s(b-\varepsilon)}{2aK_{N_{j}}}\Big{)}\cap
B\Big{(}z_{i_{p}},\frac{s(b-\varepsilon)}{2aK_{N_{j}}}\Big{)}\Big{)}.$

Inserting this into (29) gives

$\displaystyle C_{k}^{*}\left([0,a],s,N_{j}\right)$ $\displaystyle\geqslant
N_{j}^{k-2}\sum_{i_{1},\ldots,i_{k}\leqslant
K_{N_{j}}}a^{k-1}\prod_{2\leqslant p\leqslant
k}\lambda\Big{(}B\Big{(}z_{i_{1}},\frac{s(b-\varepsilon)}{2aK_{N_{j}}}\Big{)}\cap
B\Big{(}z_{i_{p}},\frac{s(b-\varepsilon)}{2aK_{N_{j}}}\Big{)}\Big{)}$
$\displaystyle=a^{k-1}\frac{N_{j}^{k-2}}{K_{N_{j}}^{k-2}}\cdot
C_{k}^{*}\big{(}(z_{n})_{n\in\mathbb{N}};s(b-\varepsilon)a^{-1},K_{N_{j}}\big{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eps_close}}}{{\geqslant}}\frac{a^{k-1}}{(b+\varepsilon)^{k-2}}C_{k}^{*}\big{(}(z_{n})_{n\in\mathbb{N}};s(b-\varepsilon)a^{-1},K_{N_{j}}\big{)}.$

We now use Proposition 4.2 for
$C_{k}^{*}\big{(}(z_{n})_{n\in\mathbb{N}};(b-\varepsilon)sa^{-1},K_{N_{j}}\big{)}$
to deduce that

$C_{k}^{*}\left([0,a],s,N_{j}\right)\geqslant\frac{a^{k-1}}{(b+\varepsilon)^{k-2}}\cdot\frac{(b-\varepsilon)^{2(k-1)}}{a^{2(k-1)}}\,s^{2(k-1)}$

for all $j\geqslant J$. Since $\varepsilon>0$ can be chosen arbitrarily small,
this finally implies

$\liminf_{j\to\infty}C_{k}^{*}\left([0,a],s,N_{j}\right)\geqslant\frac{b^{k}}{a^{k-1}}s^{2(k-1)}.$

∎

###  4.2. Proof of Theorem 1.2

For each $r\geqslant 1$ we define the intervals

(30) $B_{r,i}=\Big{[}\frac{i}{2^{r}},\frac{i+1}{2^{r}}\Big{)},\qquad
0\leqslant i\leqslant 2^{r}-1.$

Applying Proposition 4.3 and (27) to the partition
$(B_{r,i})_{i=0}^{2^{r}-1},$ we deduce that for any $s>0$

(31) $\displaystyle\frac{\liminf_{j\to\infty}C_{k}^{*}(s,N_{j})}{s^{2(k-1)}}$
$\displaystyle\geqslant\sum_{i=0}^{2^{r}-1}2^{r(k-1)}\left(G\Big{(}\frac{i+1}{2^{r}}\Big{)}-G\Big{(}\frac{i}{2^{r}}\Big{)}\right)^{k}.$

We now consider two cases regarding the function $G.$
(i) If $G$ is not absolutely continuous, there exists a fixed $\varepsilon>0$
such that for any $\delta>0$, there exist $M=M_{\delta}\in\mathbb{N}$ many
pairwise disjoint intervals $I_{1},\ldots,I_{M}\subseteq(0,1)$ with
$I_{j}=(a_{j},b_{j}),j=1,\ldots,M$ such that

$\sum_{j=1}^{M}(b_{j}-a_{j})<\frac{\delta}{2},\qquad\sum_{j=1}^{M}(G(b_{j})-G(a_{j}))>\varepsilon.$

For $r\in\mathbb{N}$, we define

$a_{j,r}=\frac{\lfloor 2^{r}a_{j}\rfloor}{2^{r}},\qquad b_{j,r}=\frac{\lceil
2^{r}b_{j}\rceil}{2^{r}},\qquad I_{j,r}=(a_{j,r},b_{j,r}).$

In other words, $I_{j,r}$ is the smallest interval of the form
$(\frac{m}{2^{r}},\frac{n}{2^{r}})$ with $m,n\in\mathbb{N}$ that contains
$I_{j}$. We choose $r=r(\delta)\geqslant 1$ large enough so that the intervals
$I_{j,r},\,j=1,\ldots,M$ are still pairwise disjoint, contained in $(0,1)$ and
also $2^{r}>4M/\delta$. We then have

(32)
$\sum_{j=1}^{M}(b_{j,r}-a_{j,r})\leqslant\sum_{j=1}^{M}\left(b_{j}-a_{j}+\frac{2}{2^{r}}\right)<\frac{\delta}{2}+\frac{\delta}{2}=\delta.$

Let $J_{r,\delta}\subseteq\\{0,\ldots,2^{r}-1\\}$ be the index set such that

$\bigcup_{i\in J_{r,\delta}}B_{r,i}=\bigcup_{j=1}^{M}I_{j,r}.$

Using (32), we see that

(33) $\lvert J_{r,\delta}\rvert<2^{r}\delta.$

Additionally, since $G$ is non-decreasing, we still have

(34) $\sum_{i\in
J_{r,\delta}}\left(G\Big{(}\frac{i+1}{2^{r}}\Big{)}-G\Big{(}\frac{i}{2^{r}}\Big{)}\right)>\varepsilon.$

Combining (31) with (34), applying the Hölder inequality in the form
$\left(\sum_{i\in J}x_{i}\right)^{k}\leqslant\lvert J\rvert^{k-1}\sum_{i\in
J}x_{i}^{k}$ and using (33) we obtain

$\displaystyle\frac{\liminf_{j\to\infty}C_{k}^{*}(s,N_{j})}{s^{2(k-1)}}$
$\displaystyle\geqslant 2^{r(k-1)}\sum_{i\in
J_{r,\delta}}\\!\left(\\!G\Big{(}\frac{i+1}{2^{r}}\Big{)}-G\Big{(}\frac{i}{2^{r}}\Big{)}\\!\right)^{k}$
$\displaystyle\geqslant\frac{2^{r(k-1)}}{\lvert
J_{r,\delta}\rvert^{k-1}}\Bigg{(}\sum_{i\in
J_{r,\delta}}\\!\\!\Big{(}\\!G\Big{(}\frac{i+1}{2^{r}}\Big{)}-G\Big{(}\frac{i}{2^{r}}\Big{)}\\!\Big{)}\Bigg{)}^{k}\geqslant\frac{\varepsilon^{k}}{\delta^{k-1}}\cdot$

As $\varepsilon>0$ is fixed and $\delta>0$ can be chosen arbitrarily small, we
obtain that for any $s>0,$ $\liminf_{j\to\infty}C_{k}^{*}(s,N_{j})=\infty,$ or
equivalently $\lim_{j\to\infty}C_{k}^{*}(s,N_{j})=\infty.$ By monotonicity of
$R_{k}^{*},$ this immediately implies that also
$\lim_{j\to\infty}R_{k}^{*}(s,N_{j})=\infty.$

We will now show that $\lim_{j\to\infty}R_{k}(s,N)=\infty.$ Letting
$z_{i}=z_{i}(s,N)$ be as in the proof of Proposition 2.6, for all $m<k$ and
$N\geqslant 1$ we have

$\displaystyle R_{m}(s,N)$ $\displaystyle=\frac{1}{N}\sum_{i\leqslant
N}(z_{i}-1)(z_{i}-2)\cdot\ldots\cdot(z_{i}-(m-1))$
$\displaystyle=\frac{1}{N}\mathop{\sum_{i\leqslant N,z_{i}\geqslant
k}}(z_{i}-1)\cdot\ldots\cdot(z_{i}-(m-1))+\frac{1}{N}\mathop{\sum_{i\leqslant
N,z_{i}<k}}(z_{i}-1)\cdot\ldots\cdot(z_{i}-(m-1))$
$\displaystyle\leqslant\frac{1}{N}\mathop{\sum_{i\leqslant N,z_{i}\geqslant
k}}(z_{i}-1)\cdot\ldots\cdot(z_{i}-(m-1))+k^{m}$ $\displaystyle\leqslant
R_{k}(s,N)+k^{m}.$

Together with Proposition 2.4, this gives

(35)
$R_{k}^{*}(s,N)\leqslant(1+b_{k-1}+\ldots+b_{1})R_{k}(s,N)+\sum_{m=1}^{k-1}b_{m}k^{m}.$

Since $\lim_{j\to\infty}R_{k}^{*}(s,N_{j})=\infty,$ (35) immediately shows
that also

$\lim_{j\to\infty}R_{k}(s,N_{j})=\infty,$

as required.
(ii) We now consider the case when $G$ is absolutely continuous, and write $g$
for the function as in the hypothesis of Theorem 1.2. We follow the method
used in [1] to prove Theorem B. We first assume that $g^{k}$ is integrable.
For each $r\geqslant 1,$ let $\mathcal{F}_{r}$ be the $\sigma$ – algebra
generated by the intervals $B_{r,i},\;0\leqslant i\leqslant 2^{r}-1$ defined
in (30). By the hypothesis, for any $r\geqslant 1$ and $i=0,1,\ldots,2^{r}-1$
we have

$\lim_{j\to\infty}\frac{1}{N_{j}}\\#\\{n\leqslant
N_{j}\mathrel{\mathop{\ordinarycolon}}x_{n}\in
B_{r,i}\\}=G\Big{(}\frac{i+1}{2^{r}}\Big{)}-G\Big{(}\frac{i}{2^{r}}\Big{)}=\int_{B_{r,i}}g(x)\mathrm{d}x.$

Inequality (31) implies that for any $s>0$

$\frac{\liminf_{j\to\infty}C_{k}^{*}(s,N_{j})}{s^{2(k-1)}}\geqslant\sum_{i=0}^{2^{r}-1}2^{r(k-1)}\left(\int_{B_{r,i}}g(x)\mathrm{d}x\right)^{k}=\int_{0}^{1}\mathbb{E}\\!\left[g|\mathcal{F}_{r}\right]\\!(x)^{k}\mathrm{d}x.$

(Here the function $\mathbb{E}\left[g|\mathcal{F}_{r}\right]$ is the
conditional expectation of $g$ with respect to the $\sigma$ – algebra
$\mathcal{F}_{r},$ for the definition we refer to [6, p. 121].) At this point,
we observe that $\mathcal{F}_{r}\subseteq\mathcal{F}_{r+1}$ for all
$r\geqslant 1$ and the $\sigma$ – algebra generated by
$\bigcup\limits_{r=1}^{\infty}\mathcal{F}_{r}$ is the Borel $\sigma$ – algebra
on $[0,1].$ Since $g$ has a finite $k$ – th moment, we can apply the
martingale convergence theorem [6, Thm 5.5] to deduce

$\lim_{r\to\infty}\int_{0}^{1}\mathbb{E}\\!\left[g|\mathcal{F}_{r}\right]\\!(x)^{k}\mathrm{d}x=\int_{0}^{1}g(x)^{k}\,\mathrm{d}x,$

so we obtain

(36)
$\frac{\liminf_{j\to\infty}C_{k}^{*}(s,N_{j})}{s^{2(k-1)}}\geqslant\int_{0}^{1}g(x)^{k}\,\mathrm{d}x.$

Applying Proposition 2.6, we see that

$\displaystyle\liminf_{j\to\infty}C_{k}^{*}(s,N_{j})$
$\displaystyle\leqslant\limsup_{j\to\infty}\int_{[0,s]^{k-1}}R_{k}^{*}(t_{1},\ldots,t_{k-1},N_{j})\,\mathrm{d}t_{1}\ldots\mathrm{d}t_{k-1}$
(37)
$\displaystyle\leqslant\limsup_{j\to\infty}\int_{[0,s]^{k-1}}R_{k}^{*}(t_{1},N_{j})^{\frac{1}{k-1}}\cdots
R_{k}^{*}(t_{k-1},N_{j})^{\frac{1}{k-1}}\,\mathrm{d}t_{1}\ldots\mathrm{d}t_{k-1}$
$\displaystyle=\limsup_{j\to\infty}\left(\int_{0}^{s}R_{k}^{*}(t,N_{j})^{1/(k-1)}\,\mathrm{d}t\right)^{k-1}.$

We will first prove that

(38)
$\limsup_{s\to\infty}\frac{\limsup_{j\to\infty}R_{k}^{*}(s,N_{j})}{(2s)^{k-1}}\geqslant\int_{0}^{1}g(x)^{k}\,\mathrm{d}x$

and prove the same with $R_{k}$ in place of $R_{k}^{*}$ later. Assume for
contradiction that there exists an $\varepsilon>0$ and some
$S_{0}=S_{0}(\varepsilon)\in\mathbb{N}$ such that for all $s>S_{0},$

(39)
$\limsup_{j\to\infty}R_{k}^{*}(s,N_{j})<{(2s)^{k-1}}\left(\int_{0}^{1}g(x)^{k}\,\mathrm{d}x-\varepsilon\right).$

Raising both sides in (39) to the power of $1/(k-1)$ and integrating, we see
that for all $s>S_{0}$ we have

$\displaystyle\int_{0}^{s}\\!\\!\limsup_{j\to\infty}R_{k}^{*}(\sigma,N_{j})^{\frac{1}{k-1}}\mathrm{d}\sigma$
$\displaystyle=\int_{S_{0}}^{s}\limsup_{j\to\infty}R_{k}^{*}(\sigma,N_{j})^{\frac{1}{k-1}}\mathrm{d}\sigma+\mathcal{O}(1)$
(40) $\displaystyle\leqslant
s^{2}\left(\int_{0}^{1}g(x)^{k}\,\mathrm{d}x-\varepsilon\right)^{\frac{1}{k-1}}+\mathcal{O}(1).$

The $\mathcal{O}(1)$ term here comes from the fact that
$\limsup_{j\to\infty}R_{k}^{*}(\sigma,N_{j})$ is bounded in the range
$(0,S_{0}].$ Combining (36), (37) and (40) and applying the reverse Fatou
Lemma, we obtain

$\displaystyle
s^{2}\left(\int_{0}^{1}g(x)^{k}\,\mathrm{d}x\right)^{\frac{1}{k-1}}$
$\displaystyle\leqslant\liminf_{j\to\infty}C_{k}^{*}(s,N_{j})^{\frac{1}{k-1}}$
$\displaystyle\leqslant\limsup_{j\to\infty}\int_{0}^{s}R_{k}^{*}(\sigma,N_{j})^{1/(k-1)}\,\mathrm{d}\sigma$
$\displaystyle\leqslant\int_{0}^{s}\limsup_{j\to\infty}R_{k}^{*}(\sigma,N_{j})^{1/(k-1)}\,\mathrm{d}\sigma$
$\displaystyle\leqslant
s^{2}\left(\int_{0}^{1}g(x)^{k}\,\mathrm{d}x-\varepsilon\right)^{\frac{1}{k-1}}+\mathcal{O}(1),$

a contradiction when $s\to\infty$.

To prove (38) with $R_{k}$ instead of $R_{k}^{*}$, we argue as follows: assume
for contradiction that

(41)
$\limsup_{s\to\infty}\frac{\limsup_{j\to\infty}R_{k}(s,N_{j})}{(2s)^{k-1}}<\int_{0}^{1}g(x)^{k}\,\mathrm{d}x.$

Combining (38) with (41), we deduce that there exists some $\delta>0$ such
that

$\limsup_{s\to\infty}\frac{\limsup_{j\to\infty}(R_{k}^{*}(s,N_{j})-R_{k}(s,N))}{(2s)^{k-1}}\geqslant\delta\int_{0}^{1}g(x)^{k}\,\mathrm{d}x.$

In view of (17), this implies that

$\limsup_{s\to\infty}\frac{1}{s}\frac{\limsup_{j\to\infty}R_{k}(3^{k}s,N_{j})}{(2s)^{k-1}}\geqslant
M\,\int_{0}^{1}g(x)^{k}\,\mathrm{d}x,$

where the constant $M>0$ depends on $k$; a contradiction to (41).

If $g$ does not have a finite $k$ – th moment, we approximate $g$ by
truncations

$g_{\ell}(x)\mathrel{\mathop{\ordinarycolon}}=\begin{cases}g(x),&\text{ if
}g(x)\leqslant\ell\\\ 0,&\text{ if }g(x)>\ell.\end{cases}$

We can apply the arguments from above to show that for any
$\ell\in\mathbb{N},$

$\limsup_{s\to\infty}\frac{\limsup_{j\to\infty}R_{k}(s,N_{j})}{(2s)^{k-1}}\geqslant\int_{0}^{1}g_{\ell}(x)^{k}\,\mathrm{d}x.$

Since $\int_{0}^{1}g_{\ell}(x)^{k}\,\mathrm{d}x$ can be made arbitrarily
large, the result follows.

##  5\. Proof of Theorems 1.3 and 1.4

The proof of Theorem 1.3 follows straightforwardly from Proposition 2.2.
Assume $s_{1},\ldots,s_{k-1}>0$ are such that

$\limsup_{N\to\infty}R_{k}(s_{1},\ldots,s_{k-1},N)=\infty.$

If $p>k$, then by (13) for any $s$ large enough with respect to $k$ and
$s_{1},\ldots,s_{k-1}$ we have $\limsup_{N\to\infty}R_{p}(s,N)=\infty.$
Therefore the sequence $(x_{n})_{n\in\mathbb{N}}$ cannot have Poissonian
correlations of order $p$.

Turning to Theorem 1.4, statement (i) follows by Bourgain’s construction in
[2, Appendix] of a subset $\mathcal{A}=(a_{n})_{n\in\mathbb{N}}$ of the
positive integers such that $E(\mathcal{A}_{N})=o(N^{3}),N\to\infty$ and for
almost all $x\in[0,1]$ the sequence $(a_{n}x)_{n\in\mathbb{N}}$ satisfies

$\limsup_{N\to\infty}R_{2}(1,N)=\infty.$

By Theorem 1.3, for almost all $x\in[0,1]$ the sequence
$(a_{n}x)_{n=1}^{\infty}$ does not have Poissonian correlations of any order
$k\geqslant 2.$

For statement (ii), within the context of Theorem 1.4 we write $R_{k}(s,N,x)$
for the $k$ – th correlation function $R_{k}(s,N)$ of the sequence
$(a_{n}x)_{n\in\mathbb{N}}.$ Also given any finite set $A$, we write

$T(A)\mathrel{\mathop{\ordinarycolon}}=\\#\\{(a,b,c)\in
A^{3}\mathrel{\mathop{\ordinarycolon}}a-b=b-c\neq 0\\}.$

We shall make use of a result in additive combinatorics, which states that
whenever the additive energy of a set $A$ is $E(A)\geqslant\kappa_{1}|A|^{3}$
then $T(A)\geqslant\kappa_{2}|A|^{2}$; the constant $\kappa_{2}>0$ only
depends on $\kappa_{1}>0.$ (see e.g. [19, Theorem 6.1]).

Therefore the assumption of Theorem 1.4 implies that

$T(\mathcal{A}_{N})\geqslant cN^{2}\qquad\text{ for infinitely many
}N\geqslant 1,$

where $c>0$ is a constant.

Let $(i,j,k)\in\mathcal{A}_{N}^{3}$ be a 3 – term arithmetic progression with
distance $d\geqslant 1$. Then we have $\lVert
j\alpha-i\alpha\rVert\leqslant\frac{s}{N}$ and $\lVert
k\alpha-j\alpha\rVert\leqslant\frac{s}{N}$ if and only if $\lVert
d\alpha\rVert\leqslant\frac{s}{N}$, which happens for $\alpha$ on a set of
measure $2s/N,$ independent of the value of $d\geqslant 1.$ Observe that for
infinitely many values of $N\geqslant 1$, we have

$\displaystyle\int_{0}^{1}R_{3}(s,N,\alpha)\,\mathrm{d}\alpha$
$\displaystyle=\sum_{\begin{subarray}{c}i,j,k\in\mathcal{A}_{N}\\\
\text{distinct}\end{subarray}}\int_{0}^{1}\frac{1}{N}\mathds{1}_{[\lVert
j\alpha-i\alpha\rVert\leqslant\frac{s}{N},\lVert
k\alpha-j\alpha\rVert\leqslant\frac{s}{N}]}(\alpha)\,\mathrm{d}\alpha$
$\displaystyle\geqslant\frac{1}{N}\sum_{\begin{subarray}{c}(i,j,k)\text{ is
a}\\\ \text{non-trivial
3-AP}\end{subarray}}\frac{2s}{N}\,\,=\,\,2s\frac{T(\mathcal{A}_{N})}{N^{2}}\,\,\geqslant\,\,2sc.$

For $s$ sufficiently small, we have $2sc>4s^{2},$ so

$\limsup_{N\to\infty}\int_{0}^{1}R_{3}(s,N,\alpha)\,\mathrm{d}\alpha>4s^{2}.$

By the reverse Fatou Lemma,

$\limsup_{N\to\infty}\int_{0}^{1}R_{3}(s,N,\alpha)\,\mathrm{d}\alpha\leqslant\int_{0}^{1}\limsup_{N\to\infty}R_{3}(s,N,\alpha)\,\mathrm{d}\alpha$

which implies that there must be a set $\Omega\subseteq[0,1]$ with positive
Lebesgue measure such that for $\alpha\in\Omega,$

$\limsup_{N\to\infty}R_{3}(s,N,\alpha)>4s^{2}.$

##  6\. Proof of Theorem 1.5

In the proof of Theorem 1.5 we make use of the test functions
$g^{(k)}_{s}\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{k-1}\to\mathbb{R}$
defined for every $k\geqslant 2$ and $s>0$ by

$g^{(k)}_{s}(y_{1},\ldots,y_{k-1})\mathrel{\mathop{\ordinarycolon}}=\Big{\\{}s-\max_{1\leqslant
i<k}\\{y_{i}\\}^{+}-\max_{1\leqslant i<k}\\{-y_{i}\\}^{+}\Big{\\}}^{+}.$

Then $g^{(k)}_{s}\in C_{c}(\mathbb{R}^{k-1})$. The importance of the test
functions $g_{s}^{(k)}$ is seen from the following lemma. For convenience,
when $s>0$ and $N\geqslant 1$ are fixed, given an index $i\leqslant N$ we
write $B_{i}=B\big{(}x_{i},\dfrac{s}{2N}\big{)}.$

######  Lemma 6.1.

Let $s>0,N\geqslant 4s$ be fixed. Consider the points
$x_{1},x_{2},\ldots,x_{k}\in[0,1]$, where $2\leqslant k\leqslant N.$ Then

(42)
$\lambda\Big{(}\bigcap_{j=1}^{k}B_{{j}}\Big{)}=g_{s}^{(k)}\left(N(\\!(x_{1}-x_{2})\\!),\ldots,N(\\!(x_{1}-x_{k})\\!)\right).$

###### Proof.

Let $x_{i_{1}}$ and $x_{i_{2}}$ be the first and last point modulo $1$, that
is, $(\\!(x_{i}-x_{i_{1}})\\!)\geqslant 0$ and
$(\\!(x_{i_{2}}-x_{i})\\!)\geqslant 0$ for all $1\leqslant i\leqslant k,i\neq
i_{1},i_{2}.$ Then

$\displaystyle\lambda\Big{(}\bigcap_{j=1}^{k}B_{{j}}\Big{)}$
$\displaystyle=\lambda(B_{i_{1}}\cap
B_{i_{2}})=\Big{\\{}\frac{s}{N}-\|x_{i_{1}}-x_{i_{2}}\|\Big{\\}}^{+}$
$\displaystyle=\left\\{\frac{s}{N}-\max_{1\leqslant m,n\leqslant
k}(\\!(x_{m}-x_{n})\\!)\right\\}^{+}$

and it remains to prove that

(43) $\left\\{\frac{s}{N}-\max_{1\leqslant m,n\leqslant
k}(\\!(x_{m}-x_{n})\\!)\right\\}^{+}=g_{s}^{(k)}\left(N(\\!(x_{1}-x_{2})\\!),\ldots,N(\\!(x_{1}-x_{k})\\!)\right).$

We only need to show this for points $x_{1},\ldots,x_{k}$ such that
$\|x_{1}-x_{\ell}\|\leqslant\frac{s}{N}\leqslant\frac{1}{4}$ for all
$2\leqslant\ell\leqslant k$ – otherwise both sides of (43) are zero. For such
points we have

(44)
$(\\!(x_{\ell}-x_{j})\\!)=(\\!(x_{\ell}-x_{1})\\!)+(\\!(x_{1}-x_{j})\\!)\qquad\text{for
all }1\leqslant\ell,j\leqslant k.$

We further assume without loss of generality that the points
$x_{2},\ldots,x_{k}$ are in increasing order, that is,
$(\\!(x_{n+1}-x_{n})\\!)\geqslant 0$ for $n=2,\ldots,k-1.$ We first consider
the case in which $x_{1}$ is between $x_{2}$ and $x_{k},$ i.e.
$(\\!(x_{1}-x_{2})\\!)>0$ and $(\\!(x_{k}-x_{1})\\!)>0.$ Then

$\displaystyle\max_{1\leqslant m,n\leqslant k}(\\!(x_{m}-x_{n})\\!)$
$\displaystyle=(\\!(x_{k}-x_{2})\\!)\stackrel{{\scriptstyle(\ref{sum_of_norms})}}{{=}}(\\!(x_{k}-x_{1})\\!)+(\\!(x_{1}-x_{2})\\!)$
$\displaystyle=\max_{2\leqslant n\leqslant
k}\\{-(\\!(x_{1}-x_{n})\\!)\\}^{+}+\max_{2\leqslant n\leqslant
k}\\{(\\!(x_{1}-x_{n})\\!)\\}^{+},$

which proves (43). The proof is similar in all other cases regarding the
relative position of $x_{1}$ with respect to $x_{2},\ldots,x_{k}.$ ∎

In order to employ the test functions $g_{s}^{(k)}$ to deduce information for
Poissonian $k$ – th order correlations, we first need to determine their
integrals.

######  Lemma 6.2.

For any $k\geqslant 2$ and $s>0,$ we have

(45)
$\int_{\mathbb{R}^{k-1}}g^{(k)}_{s}(y_{1},\ldots,y_{k-1})\,\mathrm{d}y_{1}\ldots\mathrm{d}y_{k-1}=s^{k}.$

###### Proof.

Clearly $\mathrm{supp}(g_{s}^{(k)})\subseteq[-s,s]^{k-1}.$ We partition the
set $[-s,s]^{k-1}$ as follows: for each $\ell=0,1,\ldots,k-1$ and each subset
$A\subseteq[k-1]$ with $|A|=\ell$ we define

$D_{\ell}(A)=\\{(y_{1},\ldots,y_{k-1})\in[-s,s]^{k-1}\mathrel{\mathop{\ordinarycolon}}y_{i}\geqslant
0\iff i\in A\\}.$

Then

$\int
g_{s}^{(k)}(y_{1},\ldots,y_{k-1})\,\mathrm{d}y_{1}\ldots\mathrm{d}y_{k-1}=\sum_{\ell=0}^{k-1}\sum_{\begin{subarray}{c}A\subseteq[k-1]\\\
|A|=\ell\end{subarray}}\int_{D_{\ell}(A)}g_{s}^{(k)}(y_{1},\ldots,y_{k-1})\,\mathrm{d}y_{1}\ldots\mathrm{d}y_{k-1}.$

Consider first the set $A_{0}=\\{1,\ldots,\ell\\}.$ Then we can write

$D_{\ell}(A_{0})=\bigcup_{\begin{subarray}{c}1\leqslant i\leqslant\ell\\\
\ell<j<k\end{subarray}}D_{\ell}(A_{0},i,j)$

where for each $1\leqslant i\leqslant\ell$ and $\ell<j<k$ we define

$D_{\ell}(A_{0},i,j)=\left\\{(y_{1},\ldots,y_{k-1})\in
D_{\ell}(A_{0})\mathrel{\mathop{\ordinarycolon}}y_{i}=\max_{1\leqslant
r\leqslant\ell}y_{r},\,y_{j}=\min_{\ell<r<k}y_{r}\right\\}.$

The sets $D_{\ell}(A_{0},i,j)$ are almost pairwise disjoint (their
intersections are sets of zero $(k-1)$ – dimensional Lebesgue measure). On the
set $D_{\ell}(A_{0},1,k-1)$ we have for $1\leqslant\ell<k-1$ that

$g_{s}^{(k-1)}(y_{1},\ldots,y_{k-1})=s-y_{1}+y_{k-1}.$

Thus

$\displaystyle\int\limits_{D_{\ell}(A_{0},1,k-1)}g_{s}^{(k)}$
$\displaystyle=\int_{0}^{s}\int_{-(s-y_{1})}^{0}\iint_{[0,y_{1}]^{\ell-1}\times[y_{k-1},0]^{k-\ell-2}}(s-y_{1}+y_{k-1})\,\mathrm{d}y_{2}\ldots\mathrm{d}y_{k-2}\mathrm{d}y_{k-1}\mathrm{d}y_{1}$
$\displaystyle=\int_{0}^{s}\int_{-(s-y_{1})}^{0}(-1)^{k-\ell-2}y_{1}^{\ell-1}y_{k-1}^{k-\ell-2}(s-y_{1}+y_{k-1})\,\mathrm{d}y_{k-1}\mathrm{d}y_{1}$
$\displaystyle=\int_{0}^{s}(-1)^{k-\ell-2}x^{\ell-1}(s-x)\int_{-(s-x)}^{0}y^{k-\ell-2}\,\mathrm{d}y\mathrm{d}x$
$\displaystyle\qquad+\int_{0}^{s}(-1)^{k-\ell-2}x^{\ell-1}\int_{-(s-x)}^{0}y^{k-\ell-1}\,\mathrm{d}y$
$\displaystyle=\Big{(}\frac{1}{k-\ell-1}-\frac{1}{k-\ell}\Big{)}\int_{0}^{s}x^{\ell-1}(s-x)^{k-\ell}\,\mathrm{d}x.$

We now make use of the identity

$\int_{0}^{1}x^{n-1}(1-x)^{m-1}\,\mathrm{d}x=\frac{1}{m}\binom{m+n-1}{n-1}^{-1},\qquad
m,n\geqslant 1$

(see for example [8, p. 908, 910]) to deduce that

$\int\limits_{D_{\ell}(A_{0},1,k-1)}g_{s}^{(k)}=\frac{1}{(k-\ell)(k-\ell-1)\ell}\binom{k}{k-\ell}^{-1}s^{k}.$

Using a symmetry argument, one sees that the integral of $g_{s}^{(k)}$ has the
same value on any of the sets of the form $D_{\ell}(A_{0},i,j)$. Since there
exist $\ell(k-\ell-1)$ such sets, we have

(46)
$\int_{D_{\ell}(A_{0})}g_{s}^{(k)}\,=\,\frac{1}{k-\ell}\binom{k}{k-\ell}^{-1}=\,\,\frac{1}{k}\binom{k-1}{\ell}^{-1}s^{k}.$

Another symmetry argument now shows that the value of the integral on any set
$D_{\ell}(A)$ where $A\subset[k-1]$ has $\ell$ elements is the same as on the
right hand side of (46). We have proved this for $\ell=1,\ldots,k-2$, but the
same result also holds when $\ell=0$ or $k-1.$ Since there exist precisely
$\binom{k-1}{\ell}$ such subsets of $[k-1],$ we have

$\int_{D_{\ell}}g_{s}^{(k)}=\frac{s^{k}}{k}\cdot$

Finally, summing over the $k$ possible values of the index $\ell$ we deduce
(45). ∎

Armed with Lemma 6.1, we can proceed to the proof of Theorem 1.5.

###### Proof of Theorem 1.5.

(i) Fix some $s>0$ and $N\geqslant 1$. A counting argument gives that for any
$0\leqslant t\leqslant 1$ such that $F(t,s,N)\geqslant k,$

(47)
$F(t,s,N)(F(t,s,N)-1)\ldots(F(t,s,N)-(k-1))=\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\ {\rm
distinct}\end{subarray}}\mathds{1}_{\left(\bigcap\limits_{j=1}^{k}B_{i_{j}}\right)}(t).$

Note that this equality also holds when $F(t,s,N)<k$: since $F$ is integer –
valued, both sides of (47) are then equal to $0$. Integrating with respect to
$t$ we get

$\displaystyle I_{k}(s,N)$
$\displaystyle=\\!\\!\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant N\\\
\mathrm{distinct}\end{subarray}}\lambda\Big{(}\bigcap_{j=1}^{k}B_{{i_{j}}}\Big{)}\stackrel{{\scriptstyle\eqref{measure_of_intersection}}}{{=}}\frac{1}{N}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\
\mathrm{distinct}\end{subarray}}\\!\\!g_{s}^{(k)}\left(N(\\!(x_{i_{1}}-x_{i_{2}})\\!),\ldots,N(\\!(x_{i_{1}}-x_{i_{k}})\\!)\right)$

Since we assumed that $(x_{n})_{n\in\mathbb{N}}$ has Poissonian $k$ – th
correlations, it follows from Lemma 6.2 that
$\lim\limits_{N\to\infty}I_{k}(s,N)=s^{k}.$

(ii) Using the well-known formula for Stirling numbers of the second kind

$\sum_{j=1}^{k}c_{k,j}x(x-1)\cdots(x-(j-1))=x^{k}$

(see e.g. [4, Chap. 5.3]), we can write

$\displaystyle I_{k}^{*}(s,N)=\int_{0}^{1}F(t,s,N)^{k}\,\mathrm{d}t=$
$\displaystyle\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant N\\\ {\rm
distinct}\end{subarray}}\lambda\Big{(}\bigcap_{j=1}^{k}B_{x_{i_{j}}}\Big{)}+$
$\displaystyle+c_{k,k-1}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k-1}\leqslant
N\\\ {\rm
distinct}\end{subarray}}\lambda\Big{(}\bigcap_{j=1}^{k-1}B_{x_{i_{j}}}\Big{)}+\ldots$
$\displaystyle+c_{k,1}\sum_{i_{1}\leqslant N}\lambda(B_{x_{i_{1}}}).$

In view of (42), this implies that

(48) $\displaystyle I_{k}^{*}(s,N)$
$\displaystyle=R_{k}(g_{s}^{(k)},N)+c_{k,k-1}R_{k-1}(g_{s}^{(k-1)},N)+\ldots$
$\displaystyle\qquad+c_{k,1}R_{2}(g_{s}^{(2)},N).$

The main term in (48) is $R_{k}(g_{s}^{(k)},N)=I_{k}(s,N),$ and we have shown
in (i) that $I_{k}(s,N)\to s^{k},N\to\infty.$ For $\ell<k$, we see that
$g_{s}^{(\ell)}\leqslant s\mathds{1}_{[-s,s]^{\ell-1}}$ which implies by
monotonicity of $R_{\ell}(\cdot,N)$ that

$R_{\ell}(g_{s}^{(\ell)},N)\leqslant sR_{\ell}(s,N).$

By Proposition 2.2, since $(x_{n})_{n\in\mathbb{N}}$ has Poissonian $k$ – th
correlations we have

$\limsup_{N\to\infty}R_{\ell}(s,N)=\mathcal{O}_{k}(s^{\ell-1}),\qquad
s\to\infty.$

Combining (48) with these remarks, we see that

$\limsup\limits_{N\to\infty}I_{k}^{*}(s,N)=s^{k}+\mathcal{O}_{k}(s^{k-1}),\quad
s\to\infty.$

(iii) Since $(x_{n})_{n\in\mathbb{N}}$ has Poissonian $\ell$ – correlations
for all $2\leqslant\ell\leqslant k$, by definition
$\lim\limits_{N\to\infty}R_{\ell}(g_{s}^{(\ell)},N)=s^{\ell}.$ Therefore in
that case, (48) implies that

$\lim_{N\to\infty}I_{k}^{*}(s,N)=s^{k}+c_{k,k-1}s^{k-1}+\ldots+c_{k,1}s.$

∎

## Appendix A: Equivalent Definitions of Poissonian Correlations

We discuss the different definitions of Poissonian $k$ – th order correlations
appearing in the literature.

The reader who is already familiar with the notion of Poissonian correlations
might compare the definition given in (2) with another common definition,
where in the correlation function $R_{k}(g,N)$ the differences
$(\\!(x_{i_{1}}-x_{i_{2}})\\!),(\\!(x_{i_{2}}-x_{i_{3}})\\!),\ldots,(\\!(x_{i_{k-1}}-x_{i_{k}})\\!)$
appear instead of the differences
$(\\!(x_{i_{1}}-x_{i_{2}})\\!),(\\!(x_{i_{1}}-x_{i_{3}})\\!)\ldots(\\!(x_{i_{1}}-x_{i_{k}})\\!)$
as in (1). This is the definition used, for example, in the papers [13, 14]
that deal with the $k$ – th level correlations of quadratic residues modulo
some integer $Q\geqslant 1$.

Here we explain that these two definitions are equivalent.

Proposition A.  Let $(x_{n})_{n\in\mathbb{N}}\subseteq[0,1]$ be a sequence.
The following are equivalent:
(i) The sequence $(x_{n})_{n\in\mathbb{N}}$ has Poissonian $k$ – th order
correlations.
(ii) For all test functions $g\in C_{c}(\mathbb{R}^{k-1})$ we have

$\lim_{N\to\infty}\frac{1}{N}\\!\\!\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\
\mathrm{distinct}\end{subarray}}g\left(N(\\!(x_{i_{1}}-x_{i_{2}})\\!),N(\\!(x_{i_{2}}-x_{i_{3}})\\!),\ldots,N(\\!(x_{i_{k-1}}-x_{i_{k}})\\!)\right)=\int\limits_{\mathbb{R}^{k-1}}g(x)\,\mathrm{d}x.$

(iii) For all rectangles
$B=[a_{1},b_{1}]\times[a_{2},b_{2}]\times\ldots\times[a_{k-1},b_{k-1}],\;b_{i}>a_{i},\;1\leqslant
i\leqslant k-1,$ we have

$\lim_{N\to\infty}R_{k}(\mathds{1}_{B},N)=\lambda(B)$

where $\lambda$ denotes the $(k-1)$ – dimensional Lebesgue measure.

###### Proof.

The proof of the equivalence of (i) and (iii) uses a standard approximation
argument from analysis and is omitted. We show (i) $\Rightarrow$ (ii), the
direction (ii) $\Rightarrow$ (i) can be proven in a similar fashion. Let $g\in
C_{c}(\mathbb{R}^{k-1})$ be an arbitrary test function, and define
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{k-1}\to\mathbb{R}$ via

$f(x_{1},x_{2},\ldots,x_{k-1})=g(x_{1},x_{2}-x_{1},x_{3}-x_{2},\ldots,x_{k-1}-x_{k-2}).$

This definition implies that $f\in C_{c}(\mathbb{R}^{k-1})$,

(49)
$\int_{\mathbb{R}^{k-1}}f(x)\,\mathrm{d}x=\int_{\mathbb{R}^{k-1}}g(x)\,\mathrm{d}x,$

and furthermore

(50)
$g(x_{1},x_{2},\ldots,x_{k-1})=f\left(x_{1},x_{1}+x_{2},\ldots,x_{1}+x_{2}+\ldots+x_{k-1}\right).$

Now when $N\geqslant 1$ is so large that
$\mathrm{supp}(f)\subseteq\left[\frac{-N}{2k},\frac{N}{2k}\right]^{k-1}$ and
in addition

$f\left(N(\\!(x_{i_{1}}-x_{i_{2}})\\!),N(\\!(x_{i_{2}}-x_{i_{3}})\\!),\ldots,N(\\!(x_{i_{k-1}}-x_{i_{k}})\\!)\right)\neq
0,$

then for all $\ell\leqslant k$ we have $\lVert
x_{i_{\ell-1}}-x_{i_{\ell}}\rVert\leqslant\dfrac{1}{2k}.$ Hence

$\lVert x_{i_{1}}-x_{i_{2}}\rVert+\lVert
x_{i_{2}}-x_{i_{3}}\rVert+\ldots+\lVert
x_{i_{\ell-1}}-x_{i_{\ell}}\rVert\leqslant\frac{1}{2}$

and thus

(51)
$(\\!(x_{i_{1}}-x_{i_{2}})\\!)+(\\!(x_{i_{2}}-x_{i_{3}})\\!)+\ldots+(\\!(x_{i_{\ell-1}}-x_{i_{\ell}})\\!)=(\\!(x_{i_{1}}-x_{i_{\ell}})\\!).$

Using these considerations, we get

$\displaystyle\frac{1}{N}$
$\displaystyle\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant N\\\ \text{
distinct}\end{subarray}}g\left(N(\\!(x_{i_{1}}-x_{i_{2}})\\!),N(\\!(x_{i_{2}}-x_{i_{3}})\\!),\ldots,N(\\!(x_{i_{k-1}}-x_{i_{k}})\\!)\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{g_f_translate}}}{{=}}\frac{1}{N}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\ \text{
distinct}\end{subarray}}f\big{(}N(\\!(x_{i_{1}}-x_{i_{2}})\\!),N\\!\left((\\!(x_{i_{1}}-x_{i_{2}})\\!)+(\\!(x_{i_{2}}-x_{i_{3}})\\!)\right),\ldots\big{)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{signed_distance_cond}}}{{=}}\frac{1}{N}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\ \text{
distinct}\end{subarray}}f\left(N(\\!(x_{i_{1}}-x_{i_{2}})\\!),N(\\!(x_{i_{1}}-x_{i_{3}})\\!),\ldots,N(\\!(x_{i_{1}}-x_{i_{k}})\\!)\right)=R_{k}(f,N).$

Combining this with (49), we see that under the hypothesis that the sequence
has Poissonian $k$ – th correlations, statement (ii) is true. As noted, the
implication
(ii) $\Rightarrow$ (i) can be shown in a similar way. ∎

At this point, we should also mention that for the specific case $k=2$,
sequences are usually defined to have Poissonian pair correlations when

(52) $\lim_{N\to\infty}R_{2}(s,N)=2s\qquad\text{ for all }s>0,$

where $R_{2}(s,N)$ is the correlation function as in (5). We have already
explained why a sequence with Poissonian pair correlations automatically
satisfies (52), but it turns out that condition (52) is actually equivalent to
(2) when $k=2$. Indeed, assume $(x_{n})_{n\in\mathbb{N}}$ is a sequence such
that (52) holds. For the test function $\mathds{1}_{[0,s]}$ (that is, the
characteristic function of the interval $[0,s]$) we have

(53) $\displaystyle R_{2}(\mathds{1}_{[0,s]},N)$
$\displaystyle=\frac{1}{2}R_{2}(s,N)+\frac{1}{N}\\#\big{\\{}i\neq j\leqslant
N\mathrel{\mathop{\ordinarycolon}}x_{i}=x_{j}\big{\\}}.$

Since

$0\leqslant\frac{1}{N}\\#\\{i\neq j\leqslant
N\mathrel{\mathop{\ordinarycolon}}x_{i}=x_{j}\\}\leqslant
R_{2}(\varepsilon,N)\qquad\text{ for any }\varepsilon>0,$

the assumption on $(x_{n})_{n\in\mathbb{N}}$ implies that the rightmost term
in (53) tends to $0$. By this, we deduce that
$\lim_{N\to\infty}R_{2}(\mathds{1}_{[0,s]},N)=s\text{ for all }s>0$ and it
follows that for any $b>a$ we have
$\lim_{N\to\infty}R_{2}(\mathds{1}_{[a,b]},N)=b-a.$ In view of Proposition A
(iii), relation (2) holds for $k=2$.

We also note that this equivalence cannot be generalized for correlations of
higher orders. The reason is that when $k\geqslant 3$, we cannot employ the
symmetry argument to deduce a generalization of (53), i.e. for the rectangle
$B=[0,s_{1}]\times\ldots\times[0,s_{k-1}]$, it does not hold in general that

$R_{k}(\mathds{1}_{B},N)=\Big{(}\frac{1}{2}\Big{)}^{k-1}R_{k}(s_{1},\ldots,s_{k-1},N).$

## Appendix B: The $k$ – th order correlations of random sequences are almost
surely Poissonian

We establish a fact that was alluded to in the introduction: whenever
$(Y_{n})_{n\in\mathbb{N}}$ is a sequence of independent and uniformly
distributed random variables in $[0,1]$, then for all $k\geqslant 2$ the
sequence $(Y_{n}(\omega))_{n\in\mathbb{N}}$ almost surely has Poissonian
correlations of $k$ – th order. The method of proof we use is a standard mean
– variance argument that appears very often in the relevant literature. We
refer the reader to [11] for a proof in higher dimensions when $k=2$.

Indeed, given such a sequence $(Y_{n})_{n\in\mathbb{N}}$ and
$a_{r}<b_{r}\,\,(1\leqslant r<k)$, let

$R_{k}(\omega,N)=\frac{1}{N}\\#\left\\{\parbox{70.0001pt}{$i_{1},\ldots,i_{k}\leqslant
N$ \\\ $i_{j}\neq i_{\ell}\,\forall
j\neq\ell$}\mathrel{\mathop{\ordinarycolon}}\frac{a_{r}}{N}\leqslant
Y_{i_{1}}(\omega)-Y_{i_{r+1}}(\omega)\leqslant\frac{b_{r}}{N}\quad(1\leqslant
r<k)\right\\}.$

According to Proposition A it suffices to show that
$R_{k}(\omega,N)\to(b_{1}-a_{1})\cdots(b_{k-1}-a_{k-1})$ as $N\to\infty$
almost surely.

We proceed to the calculation of the expectation and variance of
$R_{k}(\cdot,N)$ viewed as a random variable on $[0,1].$ This will be done in
several steps. In the estimates that follow, the implicit constants in the
asymptotic notations depend on the scales $a_{1},\ldots,b_{k-1}.$
Step 1: We claim that for any $m\geqslant 1$ and for any distinct indices
$i_{1},i_{2},\ldots,i_{m},\geqslant 1$ the differences

$\Delta_{1}=Y_{i_{1}}-Y_{i_{2}},\quad\Delta_{2}=Y_{i_{1}}-Y_{i_{3}},\quad\ldots\quad\Delta_{m+1}=Y_{i_{1}}-Y_{i_{m+2}}$

are independent. For convenience, we only show this when $m=1$ and for the
random variables

$\Delta_{1}=Y_{1}-Y_{2}\quad\text{ and }\quad\Delta_{2}=Y_{1}-Y_{3}$

(the proof is similar for any other choice of indices and for any $m\geqslant
2$). Writing $f_{X}$ for the probability density function of a random variable
$X\mathrel{\mathop{\ordinarycolon}}[0,1]\to\mathbb{R}$, we need to show that

(54)
$f_{\Delta_{1},\Delta_{2}}(x_{1},x_{2})=f_{\Delta_{1}}(x_{1})f_{\Delta_{2}}(x_{2})\quad\text{
for all }x_{1},x_{2}\in[0,1].$

Note that in our context, addition and subtraction of the random variables is
always understood modulo $1$. Thus for all $i\in\mathbb{N}$ we have
$f_{Y_{i}}(y)=1,$ $0\leqslant y\leqslant 1$ and the density functions of the
differences $\Delta_{1},\Delta_{2}$ are

$f_{\Delta_{1}}(\delta)=\int_{0}^{1}f_{Y_{1}}(y)f_{Y_{2}}(\delta+y)\mathrm{d}y=1$

and similarly $f_{\Delta_{2}}(\delta)=1,$ for all $\delta\in[0,1].$ We start
from the left – hand side of (54): the theorem of total probability and the
independence of $\\{Y_{1},Y_{2},Y_{3}\\}$ imply that

$\displaystyle f_{\Delta_{1},\Delta_{2}}(x_{1},x_{2})$
$\displaystyle=\int_{0}^{1}f_{\Delta_{1},\Delta_{2}|Y_{1}}(x_{1},x_{2}|y)\mathrm{d}y=\int_{0}^{1}\frac{f_{\Delta_{1},\Delta_{2},Y_{1}}(x_{1},x_{2},y)}{f_{Y_{1}}(y)}\mathrm{d}y$
$\displaystyle=\int_{0}^{1}f_{\Delta_{1},\Delta_{2},Y_{1}}(x_{1},x_{2},y)\mathrm{d}y=\int_{0}^{1}f_{y-Y_{2}}(x_{1})f_{y-Y_{3}}(x_{2})\mathrm{d}y=1.$

Step 2: We now claim that whenever each of the sets
$I=\\{i_{1},\ldots,i_{m}\\}$ and $J=\\{j_{1},\ldots,j_{n}\\}$ consists of
pairwise distinct indices and $\\#(I\cap J)\leqslant 1$, then the differences
$Y_{i_{1}}-Y_{i_{2}},Y_{i_{1}}-Y_{i_{3}},\ldots,Y_{i_{1}}-Y_{i_{m}},Y_{j_{1}}-Y_{j_{2}},\ldots,Y_{j_{1}}-Y_{j_{n}}$
are independent random variables. It follows by the previous step that the
random variables
$Y_{i_{1}}-Y_{i_{2}},Y_{i_{1}}-Y_{i_{3}},\ldots,Y_{i_{1}}-Y_{i_{m}}$ are
independent, and so are $Y_{j_{1}}-Y_{j_{2}},\ldots,Y_{j_{1}}-Y_{j_{n}}$ . If
the sets $I,J$ are disjoint, all of these random variables are immediately
independent, so we deal with the case when $\\#(I\cap J)=1.$ We need to
distinguish the following cases:
Case 1: $i_{1}=j_{1}$. In this case, independence follows immediately from
Step $1$.
Case 2: $i_{1}=j_{\ell}$ or $j_{1}=i_{\ell}$ with $\ell\geqslant 2$: Then we
can assume without loss of generality that $i_{1}=j_{2}$. The random variables
we are looking at are

$Y_{j_{1}}-Y_{j_{n}},Y_{j_{1}}-Y_{j_{n-1}},\ldots,Y_{j_{1}}-Y_{j_{2}}=Y_{j_{1}}-Y_{i_{1}},Y_{i_{1}}-Y_{i_{2}},\ldots,Y_{i_{1}}-Y_{i_{m}},$

and these are independent by an argument similar to the one used in Step $1.$
Case 3: $i_{r}=j_{\ell}$ with $r,\ell\geqslant 2$: Then we assume without loss
of generality $i_{2}=j_{2}$ and we are in a similar situation as in Case 2.
Step 3: Given $k$ distinct indices $i_{1},\ldots,i_{k}\leqslant N,$ we write

$X_{i_{1},\ldots,i_{k}}=\mathds{1}_{[\frac{a_{1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N}]}\cdots\mathds{1}_{[\frac{a_{k-1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}}{N}]}.$

We calculate the covariance
$\text{Cov}(X_{i_{1},\ldots,i_{k}},X_{j_{1},\ldots,j_{k}}),$ where
$i_{1},\ldots,i_{k}\leqslant N$ and $j_{1},\ldots,j_{k}\leqslant N$ both
consist of distinct indices. As seen above, when
$\\#\\{i_{1},\ldots,i_{k}\\}\cap\\{j_{1},\ldots,j_{k}\\}\leqslant 1$ the
variables $X_{i_{1},\ldots,i_{k}}$ and $X_{j_{1},\ldots,j_{k}}$ are
independent and thus the covariance in question is $0$. We need to bound the
covariance of $X_{i_{1},\ldots,i_{k}},X_{j_{1},\ldots,j_{k}}$ when

(55) $\\#\\{i_{1},\ldots,i_{k}\\}\cap\\{j_{1},\ldots,j_{k}\\}=\ell\geqslant
2.$

If $(i_{1},\ldots,i_{k}),(j_{1},\ldots,j_{k})$ fulfill (55), then

$\displaystyle\text{Cov}(X_{i_{1},\ldots,i_{k}},X_{j_{1},\ldots,j_{k}})$
$\displaystyle=\mathbb{E}\big{[}\big{(}X_{i_{1},\ldots,i_{k}}-\mathbb{E}[X_{i_{1},\ldots,i_{k}}]\big{)}\big{(}X_{j_{1},\ldots,j_{k}}-\mathbb{E}[X_{j_{1},\ldots,j_{k}}]\big{)}\big{]}$
$\displaystyle\leqslant\mathbb{E}\big{[}X_{i_{1},\ldots,i_{k}}\cdot
X_{j_{1},\ldots,j_{k}}\big{]}$ (56)
$\displaystyle=\mathbb{E}\Big{[}\mathds{1}_{[\frac{a_{1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N}]}\cdots\mathds{1}_{[\frac{a_{k-1}}{N}\leqslant
Y_{j_{1}}-Y_{j_{k}}\leqslant\frac{b_{k-1}}{N}]}\Big{]}.$

To find an upper bound for the right – hand side, we take a maximal subset
$\tilde{J}\subset\\{j_{2},\ldots,j_{k}\\}$ such that
$\\#\\{i_{1},\ldots,i_{k}\\}\cap(\\{j_{1}\\}\cup\tilde{J})\leqslant 1$. By the
discussion in Step $2$, this gives rise to $2(k-1)-(\ell-1)$ independent
random variables among the factors in the integral in (56), each of them
having expectation $\mathcal{O}\left(\frac{1}{N}\right)$. The remaining
differences appearing in (56) might not be independent, but can be trivially
bounded from above by $1$ since they are characteristic functions. We
therefore conclude that

$\text{Cov}(X_{i_{1},\ldots,i_{k}},X_{j_{1},\ldots,j_{k}})=\mathcal{O}\Big{(}\frac{1}{N^{2(k-1)-(\ell-1)}}\Big{)}\cdot$

Step 4: We fix a value of $\ell\geqslant 2$ and we estimate

$\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant N\\\
j_{1},\ldots,j_{k}\leqslant N\\\ \mathrm{distinct}\\\
\\#\\{i_{1},\ldots,i_{k}\\}\cap\\{j_{1},\ldots,j_{k}\\}=\ell\end{subarray}}\text{Cov}(X_{i_{1},...,i_{k}},X_{j_{1},...,j_{k}}).$

We count how many choices of the sets $\\{i_{1},\ldots,i_{k}\\}$ and
$\\{j_{1},\ldots,j_{k}\\}$ there exist such that (55) holds. From a fixed set
$\\{i_{1},\ldots,i_{k}\\}$ we can chose $\ell$ elements that will be in the
intersection with $\\{j_{1},\ldots,j_{k}\\}$ in $\binom{k}{\ell}$ ways. The
remaining $k-\ell$ elements of $\\{j_{1},\ldots,j_{k}\\}$ can be chosen in
$\mathcal{O}(N^{k-\ell})$ ways. Since the set $\\{i_{1},\ldots,i_{k}\\}$ can
be chosen in $\mathcal{O}_{k}(N^{k})$ ways, we deduce that the different
choices of the sets $\\{i_{1},\ldots,i_{k}\\}$ and $\\{j_{1},\ldots,j_{k}\\}$
with precisely $\ell$ common elements is $\mathcal{O}_{k,\ell}(N^{2k-\ell})$.
Combining with Step $3$, we obtain

(57) $\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant N\\\
j_{1},\ldots,j_{k}\leqslant N\\\ \mathrm{distinct}\\\
\\#\\{i_{1},\ldots,i_{k}\\}\cap\\{j_{1},\ldots,j_{k}\\}=\ell\end{subarray}}\text{Cov}(X_{i_{1},...,i_{k}},X_{j_{1},...,j_{k}})=\mathcal{O}_{k,\ell}\big{(}N^{2k-\ell}\frac{1}{N^{2(k-1)-(\ell-1)}}\big{)}=\mathcal{O}_{k,\ell}(N).$

Step 5:  We are finally in place to calculate the expectation and variance of
$R_{k}(\cdot,N).$ The expectation is

$\displaystyle\mathbb{E}[R_{k}(\cdot,N)]$
$\displaystyle=\frac{1}{N}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\
\mathrm{distinct}\end{subarray}}\mathbb{E}\big{[}\mathds{1}_{[\frac{a_{1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N}]}\cdots\mathds{1}_{[\frac{a_{k-1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}}{N}]}\big{]}$
$\displaystyle=\frac{1}{N}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\
\mathrm{distinct}\end{subarray}}\mathbb{E}\big{[}\mathds{1}_{[\frac{a_{1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N}]}\big{]}\cdots\mathbb{E}\big{[}\mathds{1}_{[\frac{a_{k-1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}}{N}]}\big{]}$
$\displaystyle=(a_{1}-b_{1})\cdots(a_{k-1}-b_{k-1})+\mathcal{O}\Big{(}\frac{1}{N}\Big{)},\qquad
N\to\infty$

because $(Y_{n})_{n\in\mathbb{N}}$ are independent (here we used the result
from Step $1$). For the variance we have

$\displaystyle\text{Var}[R_{k}(\cdot,N)]$
$\displaystyle=\frac{1}{N^{2}}\sum_{\ell=0}^{k}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\ j_{1},\ldots,j_{k}\leqslant N\\\
\mathrm{distinct},\;\,(i_{1},...,i_{k})\neq(j_{1},...,j_{k})\\\
\\#\\{i_{1},\ldots,i_{k}\\}\cap\\{j_{1},\ldots,j_{k}\\}=\ell\end{subarray}}\text{Cov}(X_{i_{1},...,i_{k}},X_{j_{1},...,j_{k}})$
(58) $\displaystyle+$
$\displaystyle\frac{1}{N^{2}}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\
\mathrm{distinct}\end{subarray}}\mathrm{Var}[\mathds{1}_{[\frac{a_{1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N}]}\cdots\mathds{1}_{[\frac{a_{k-1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}}{N}]}].$

In the first sum appearing in (Appendix B: The $k$ – th order correlations of
random sequences are almost surely Poissonian), the terms corresponding to
$\ell=0$ or $1$ are equal to $0.$ Applying (57) for the terms corresponding to
$2\leqslant\ell\leqslant k$ in (Appendix B: The $k$ – th order correlations of
random sequences are almost surely Poissonian), we obtain

$\displaystyle\text{Var}[R_{k}(\cdot,N)]=$
$\displaystyle\frac{1}{N^{2}}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\
\mathrm{distinct}\end{subarray}}\mathrm{Var}[\mathds{1}_{[\frac{a_{1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N}]}\cdots\mathds{1}_{[\frac{a_{k-1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}}{N}]}]+\mathcal{O}(\frac{1}{N}).$

Since

$\displaystyle\frac{1}{N^{2}}$
$\displaystyle\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant N\\\
\mathrm{distinct}\end{subarray}}\mathrm{Var}[\mathds{1}_{[\frac{a_{1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N}]}\cdots\mathds{1}_{[\frac{a_{k-1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}}{N}]}]$
$\displaystyle=\frac{1}{N^{2}}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\
\mathrm{distinct}\end{subarray}}\Big{(}\mathbb{E}[\mathds{1}_{[\frac{a_{1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N}]}\cdots\mathds{1}_{[\frac{a_{k-1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}}{N}]}]-$
$\displaystyle\qquad\qquad\qquad\qquad\mathbb{E}[\mathds{1}_{[\frac{a_{1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N}]}\cdots\mathds{1}_{[\frac{a_{k-1}}{N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}}{N}]}]^{2}\Big{)}$
$\displaystyle=\frac{1}{N^{2}}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N\\\
\mathrm{distinct}\end{subarray}}\Big{(}\frac{a_{1}-b_{1}}{N}\cdot\ldots\cdot\frac{a_{k-1}-b_{k-1}}{N}-\prod_{r=1}^{k-1}\Big{(}\frac{a_{r}-b_{r}}{N}\Big{)}^{2}\Big{)}$
$\displaystyle=\mathcal{O}_{k}\big{(}\frac{1}{N}\big{)},$

we deduce that

$\text{Var}[R_{k}(\cdot,N)]=\mathcal{O}_{k}\big{(}\frac{1}{N}\big{)},\qquad
N\to\infty.$

Consider now the sequence $N_{m}=\lfloor m^{1+\gamma}\rfloor,m\geqslant 1$
where $\gamma>0$. Fix $\varepsilon>0$ and let
$A_{N}=\\{\omega\in[0,1]\mathrel{\mathop{\ordinarycolon}}|R_{k}(\omega,N)-\mathbb{E}[R_{k}(\cdot,N)]|\geqslant\varepsilon\\},N\geqslant
1.$ By Chebyshev’s inequality, the Lebesgue measure of $A_{N}$ satisfies
$\lambda(A_{N})=\mathcal{O}(1/N),N\to\infty.$ Then the Borel – Cantelli lemma
implies that

$\lambda\big{(}\limsup\limits_{m\to\infty}A_{N_{m}}\big{)}=0,$

and since $\varepsilon>0$ was arbitrarily chosen, we conclude that for almost
all $\omega\in[0,1]$ we have
$\lim\limits_{m\to\infty}R_{k}(\omega,N_{m})=(b_{1}-a_{1})\cdots(b_{k-1}-a_{k-1}).$
The fact that $R_{k}(\cdot,N_{m})$ converges almost surely to this limit for
any choice of the scalars follows by an intersection over a countable dense
set of $(a_{1},\ldots,b_{k-1}).$

It remains to prove that for the same values of $\omega$, $R_{k}(\omega,N)$
will converge to the value $(b_{1}-a_{1})\cdots(b_{k-1}-a_{k-1})$ for any
choice of $a_{1},\ldots,b_{k-1}$. This will follow from the fact that when
$N_{m}\leqslant N<N_{m+1}$ we have

$\displaystyle\frac{1}{N}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N_{m}\\\
\mathrm{distinct}\end{subarray}}\mathds{1}_{[\frac{a_{1}}{N_{m}}\frac{N_{m}}{N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}}{N_{m}}\frac{N_{m}}{N}]}(\omega)\cdots\mathds{1}_{[\frac{a_{k-1}}{N_{m}}\frac{N_{m}}{N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}}{N_{m}}\frac{N_{m}}{N}]}(\omega)\leqslant
R_{k}(\omega,N)$
$\displaystyle\leqslant\frac{1}{N}\\!\\!\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\leqslant
N_{m+1}\\\
\mathrm{distinct}\end{subarray}}\mathds{1}_{[\frac{a_{1}N_{m+1}}{N_{m+1}N}\leqslant
Y_{i_{1}}-Y_{i_{2}}\leqslant\frac{b_{1}N_{m+1}}{N_{m+1}N}]}(\omega)\cdots\mathds{1}_{[\frac{a_{k-1}N_{m+1}}{N_{m+1}N}\leqslant
Y_{i_{1}}-Y_{i_{k}}\leqslant\frac{b_{k-1}N_{m+1}}{N_{m+1}N}]}(\omega)$

and the fact that $N_{m}/N_{m+1}\to 1$ as $m\to\infty$.

### Acknowledgements

We would like to thank Professor C. Aistleitner for suggesting this direction
of research. We also thank the anonymous referee for many valuable remarks.

## References

  * [1] C. Aistleitner, T. Lachmann and F. Pausinger, Pair correlations and equidistribution, J. Number Theory 182, 206–220 (2018).
  * [2] C. Aistleitner, G. Larcher, M. Lewko, Additive Energy and the Hausdorff dimension of the exceptional set in metric pair correlation problems. With an appendix by Jean Bourgain, Isr. J. Math. 222, 463 – 485 (2017).
  * [3] T. Bloom, A. Walker, GCD sums and sum-product estimates, Israel J. Math. 235, no. 1, 1–11 (2020).
  * [4] P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press (1994).
  * [5] L. Carlitz, Arithmetic properties of the Bell polynomials, Journal of Mathematical Analysis and Applications No. 1, vol. 15, 33 – 52 (1966).
  * [6] M. Einsiedler, T. Ward, Ergodic Theory: with a view towards Number Theory, Springer Verlag, London (2011).
  * [7] W. T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geom. Funct. Analysis 8, 529 – 551 (1998).
  * [8] I. S. Gradshteyn, I. M. Ryzhik, Table of Series, Integrals and Products, Seventh Edition, Academic Press (2007).
  * [9] S. Grepstad, G. Larcher, On Pair Correlation and Discrepancy, Arch. Math. (Basel) 109, no. 2, 143 – 149 (2017).
  * [10] D. R. Heath-Brown, Pair correlation for fractional parts of $\alpha n^{2}$, Math. Proc. Cambridge Philos. Soc. 148, 385–407 (2010).
  * [11] A. Hinrichs, L. Kaltenböck, G. Larcher, W. Stockinger, M. Ullrich, On a multi-dimensional Poissonian pair correlation concept and uniform distribution, Monatsh. Math. 190, 333 – 352 (2019).
  * [12] L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences, Wiley (1974).
  * [13] P. Kurlberg, The distribution of spacings between quadratic residues II, Israel J. Math. 120, 205 – 224 (2000).
  * [14] P. Kurlberg, Z. Rudnick, The distribution of spacings between quadratic residues,  Duke J. Math., 100: 211 – 242 (1999).
  * [15] J. Marklof, Distribution modulo one and Ratner’s theorem, appearing in Equidistribution in Number Theory, an Introduction, edited by Andrew Granville and Zeèv Rudnick, NATO Science Series, Springer (2005).
  * [16] J. Marklof, _Pair correlation and equidistribution on manifolds,_ Monatsh. Math. 191, 279 – 294 (2020).
  * [17] J. Marklof, The Berry-Tabor conjecture. European Congress of Mathematics, Vol. II (Barcelona, 2000), 421–427, Progr. Math., 202, Birkhäuser, Basel, (2001).
  * [18] J. Marklof, N. Yesha, Pair correlation for quadratic polynomials mod 1, Compos. Math. 154 (2018), no. 5, 960–983.
  * [19] C. Pohoata and O. Roche-Newton, Four-term progression free sets with three – term progressions in all large subsets, (to appear in Random Structures and Algorithms), preprint: arXiv:1905.08457
  * [20] J. Riordan, Moment Recurrence Relations for Binomial, Poisson and Hypergeometric Frequency Distributions, The Annals of Mathematical Statistics No. 2, vol. 8,103 – 111 (1937).
  * [21] Z. Rudnick, P. Sarnak, The pair correlation function of fractional parts of polynomials, Comm. Math. Phys., 194 (1) 61 – 70, (1998).
  * [22] Z. Rudnick, P. Sarnak, Zeros of principal $L$ – functions and random matrix theory, Duke Math. J. 81(2) 269 – 322 (1996)
  * [23] Z. Rudnick, A. Zaharescu, _The distribution of spacings between fractional parts of lacunary sequences_ , Forum Math., 14 (5) 691 – 712, (2002).
  * [24] Z. Rudnick, A. Zaharescu, _A metric result on the pair correlation of fractional parts of sequences,_ Acta Arith., 89 (3) 283–293, (1999).
  * [25] P. Sarnak, Values at integers of binary quadratic forms, Harmonic analysis and number theory (Montreal, PQ, 1996), 181–203, CMS Conf. Proc., 21, Amer. Math. Soc., Providence, RI, (1997).
  * [26] S. Steinerberger, Poissonian Pair Correlation in Higher Dimensions, J. Number Theory, 208: 47 – 58, (2020).
  * [27] T. Tao, V. Vu, Additive combinatorics, volume 105 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, (2006).
  * [28] N. Technau, A. Walker, On the triple correlations of fractional parts of $n^{2}\alpha$, pre-print: arXiv:2005.01490
  * [29] N. Technau, N. Yesha, On the correlations of $n^{\alpha}$ mod 1, arXiv:2006.16629 (2020).