1 A bilinear statistic

To study the minimal gap, we introduce statistics counting all possible gaps: we start with a smooth, compactly supported window function $f\in C_{c}^{\infty }([-1/2,1/2])$ , which is non-negative: $f\geqslant 0$ , and of unit mass $\int f(x)\,dx=1$ , and define

$$\begin{eqnarray}F_{M}(x)=\mathop{\sum }_{j\in \mathbb{Z}}f(M(x+j)),\end{eqnarray}$$

which is localized on the scale of $1/M$ , and periodic: $F_{M}(x+1)=F_{M}(x)$ . We then set

$$\begin{eqnarray}D_{{\mathcal{A}}}(N,M)(\unicode[STIX]{x1D6FC})=\mathop{\sum }_{\substack{ 1\leqslant m,n\leqslant N \\ m\neq n}}F_{M}(\unicode[STIX]{x1D6FC}a(n)-\unicode[STIX]{x1D6FC}a(m)).\end{eqnarray}$$

The expected value of $D_{{\mathcal{A}}}(N,M)$ is easily seen to equal

(2) $$\begin{eqnarray}\int _{0}^{1}D_{{\mathcal{A}}}(N,M)(\unicode[STIX]{x1D6FC})\,d\unicode[STIX]{x1D6FC}=\frac{N(N-1)}{M}\sim \frac{N^{2}}{M}.\end{eqnarray}$$

This already suffices to show that minimal gaps cannot typically be small (Theorem 1); see §2.

We will bound the variance of $D_{{\mathcal{A}}}(N,M)$ , from which Theorem 2 will follow.

Proposition 3.

$$\begin{eqnarray}\operatorname{Var}D_{{\mathcal{A}}}(N,M)\ll \frac{1}{M}N^{\unicode[STIX]{x1D716}}E({\mathcal{A}},N).\end{eqnarray}$$

The statistic $D_{{\mathcal{A}}}(N,M)(\unicode[STIX]{x1D6FC})$ is related to the pair correlation function of the sequence ${\mathcal{A}}^{\unicode[STIX]{x1D6FC}}$ , which in our notation is $D_{{\mathcal{A}}}(N,N)(\unicode[STIX]{x1D6FC})/N$ . Pair correlation measures gaps on the scale of the mean spacing, assumed here to be $1/N$ , corresponding to $M=N$ , here we are looking at much smaller scales of $M$ close to $N^{2}$ .

The metric theory of the pair correlation function of fractional parts was initiated in [Reference Rudnick and Sarnak11], where the sequences $a(n)=\unicode[STIX]{x1D6FC}n^{d}$ were shown to almost surely have Poissonian pair correlation for $d\geqslant 2$ (see [Reference Heath-Brown7, Reference Marklof and Strömbergsson10] for different proofs of the quadratic case $d=2$ ). The problem has since been studied in several other cases and has recently been revived in an abstract setting [Reference Aistleitner, Larcher and Lewko1, Reference Bloom, Chow, Gafni and Walker4, Reference Lachmann and Technau8, Reference Walker14]. In particular, a convenient criterion for almost sure Poisson pair correlation has been formulated by Aistleitner, Larcher and Lewko [Reference Aistleitner, Larcher and Lewko1] in terms of the additive energy $E({\mathcal{A}},N)$ of the sequence. The proof of Proposition 3 is close to that of the analogous statement for the pair correlation function in [Reference Aistleitner, Larcher and Lewko1], which in turn is based on [Reference Rudnick and Sarnak11, Reference Rudnick and Zaharescu12].

Proof. The Fourier expansion of $F_{M}(x)$ is

(3) $$\begin{eqnarray}F_{M}(x)=\mathop{\sum }_{k\in \mathbb{Z}}\frac{1}{M}\widehat{f}\biggl(\frac{k}{M}\biggr)e(kx),\end{eqnarray}$$

where $\widehat{f}(y)=\int _{-\infty }^{\infty }f(x)\text{e}^{-2\unicode[STIX]{x1D70B}\text{i}xy}dx$ . Inserting into the definition of $D(N,M)$ gives

(4) $$\begin{eqnarray}D(N,M)(\unicode[STIX]{x1D6FC})=\mathop{\sum }_{k\in \mathbb{Z}}\frac{1}{M}\widehat{f}\biggl(\frac{k}{M}\biggr)\mathop{\sum }_{\substack{ 1\leqslant m,n\leqslant N \\ m\neq n}}e(k\unicode[STIX]{x1D6FC}(a(m)-a(n))).\end{eqnarray}$$

Integrating over $\unicode[STIX]{x1D6FC}$ gives the expected value (we assume $a(m)\neq a(n)$ if $n\neq m$ )

$$\begin{eqnarray}\int _{0}^{1}D(N,M)(\unicode[STIX]{x1D6FC})\,d\unicode[STIX]{x1D6FC}=\widehat{f}(0)\frac{1}{M}N(N-1)=\frac{N(N-1)}{M}.\end{eqnarray}$$

The variance is the second moment of the sum over non-zero frequencies:

$$\begin{eqnarray}\operatorname{Var}D(N,M)=\int _{0}^{1}\Bigg|\mathop{\sum }_{0\neq k\in Z}\frac{1}{M}\widehat{f}\biggl(\frac{k}{M}\biggr)\mathop{\sum }_{\substack{ 1\leqslant m,n\leqslant N \\ m\neq n}}e(k\unicode[STIX]{x1D6FC}(a(m)-a(n)))\Bigg|^{2}\,d\unicode[STIX]{x1D6FC}.\end{eqnarray}$$

Squaring out and integrating gives

$$\begin{eqnarray}\displaystyle & & \displaystyle \operatorname{Var}D(N,M)=\mathop{\sum }_{k_{1},k_{2}\neq 0}\frac{1}{M^{2}}\widehat{f}\biggl(\frac{k_{1}}{M}\biggr)\widehat{f}\biggl(\frac{k_{2}}{M}\biggr)\nonumber\\ \displaystyle & & \displaystyle \qquad \qquad \times \,\#\{m_{1}\neq n_{1},m_{2}\neq n_{2}:k_{1}(a(m_{1})-a(n_{1}))=k_{2}(a(m_{2})-a(n_{2}))\}.\nonumber\end{eqnarray}$$

We now follow [Reference Aistleitner, Larcher and Lewko1, Lemma 3] to convert this to “greatest common divisor (GCD) sums”. Let

$$\begin{eqnarray}R(v)=\#\{1\leqslant m\neq n\leqslant N:a(m)-a(n)=v\}.\end{eqnarray}$$

Then

$$\begin{eqnarray}\operatorname{Var}D(N,M)=\mathop{\sum }_{v_{1},v_{2}\neq 0}\mathop{\sum }_{k_{1},k_{2}\neq 0}c(k_{1})c(k_{2})R(v_{1})R(v_{2})\unicode[STIX]{x1D6FF}(k_{1}v_{1}=k_{2}v_{2}),\end{eqnarray}$$

where we set

$$\begin{eqnarray}c(k):=\frac{1}{M}\widehat{f}\biggl(\frac{k}{M}\biggr).\end{eqnarray}$$

Lemma 4. Let $f\in C_{c}^{\infty }(\mathbb{R})$ . For any non-zero integers $v_{1},v_{2}\neq 0$ ,

(5) $$\begin{eqnarray}\mathop{\sum }_{k_{1},k_{2}\neq 0}c(k_{1})c(k_{2})\unicode[STIX]{x1D6FF}(k_{1}v_{1}=k_{2}v_{2})\ll _{f}\frac{1}{M}\frac{\gcd (v_{1},v_{2})}{\sqrt{|v_{1}v_{2}|}}.\end{eqnarray}$$

Proof. For $k_{1},k_{2}\neq 0$ , we have $k_{1}v_{1}=k_{2}v_{2}$ if and only if

$$\begin{eqnarray}(k_{1},k_{2})=\ell \biggl(\frac{v_{2}}{\gcd (v_{1},v_{2})},\frac{v_{1}}{\gcd (v_{1},v_{2})}\biggr)\end{eqnarray}$$

for some non-zero integer $0\neq \ell \in \mathbb{Z}$ . Abbreviating $a_{i}=v_{i}/(M\gcd (v_{1},v_{2}))$ , we find

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{k_{1},k_{2}\neq 0}c(k_{1})c(k_{2})\unicode[STIX]{x1D6FF}(k_{1}v_{1}=k_{2}v_{2}) & = & \displaystyle \mathop{\sum }_{0\neq \ell \in \mathbb{Z}}c\biggl(\ell \frac{v_{2}}{\gcd (v_{1},v_{2})}\biggr)c\biggl(\ell \frac{v_{1}}{\gcd (v_{1},v_{2})}\biggr)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{M^{2}}\mathop{\sum }_{0\neq \ell \in \mathbb{Z}}\widehat{f}(a_{2}\ell )\widehat{f}(a_{1}\ell )\nonumber\end{eqnarray}$$

so that it suffices to show that

(6) $$\begin{eqnarray}\mathop{\sum }_{0\neq \ell \in \mathbb{Z}}\widehat{f}(a_{1}\ell )\widehat{f}(a_{2}\ell )\ll _{f}\frac{1}{\sqrt{|a_{1}a_{2}|}}=\frac{M\gcd (v_{1},v_{2})}{\sqrt{|v_{1}v_{2}|}}.\end{eqnarray}$$

Applying Cauchy–Schwarz we get

$$\begin{eqnarray}\mathop{\sum }_{0\neq \ell \in \mathbb{Z}}\widehat{f}(\ell a_{1})\widehat{f}(\ell a_{2})\leqslant \biggl(\mathop{\sum }_{\ell \neq 0}\widehat{f}(a_{1}\ell )^{2}\biggr)^{1/2}\biggl(\mathop{\sum }_{\ell \neq 0}\widehat{f}(a_{2}\ell )^{2}\biggr)^{1/2}.\end{eqnarray}$$

We will obtain (6) if we show that for any $a>0$ ,

$$\begin{eqnarray}\mathop{\sum }_{\ell \neq 0}\widehat{f}(a\ell )^{2}\ll _{f}\frac{1}{a}.\end{eqnarray}$$

Indeed, if $0<a\ll 1$ then we get a Riemann sum for $(\widehat{f}\;)^{2}$ :

$$\begin{eqnarray}\mathop{\sum }_{\ell \neq 0}\widehat{f}(a\ell )^{2}\sim \frac{1}{a}\int _{-\infty }^{\infty }\widehat{f}(y)^{2}\,dy=\frac{1}{a}\int _{-\infty }^{\infty }f(x)^{2}\,dx.\end{eqnarray}$$

If $a\gg 1$ then use the decay rate of the Fourier transform: for $y\neq 0$ ,

$$\begin{eqnarray}|\widehat{f}(y)|\leqslant \frac{1}{2\unicode[STIX]{x1D70B}|y|}\int _{-\infty }^{\infty }|f^{\prime }(x)|\,dx,\end{eqnarray}$$

to obtain

$$\begin{eqnarray}\mathop{\sum }_{\ell \neq 0}\widehat{f}(a\ell )^{2}\ll \mathop{\sum }_{\ell \neq 0}\biggl(\frac{\int _{-\infty }^{\infty }|f^{\prime }(x)|\,dx}{|a\ell |}\biggr)^{2}\ll _{f}\frac{1}{a^{2}},\end{eqnarray}$$

which for $a\gg 1$ is $\ll 1/a$ .

Hence,

$$\begin{eqnarray}\operatorname{Var}D(N,M)\ll \frac{1}{M}\mathop{\sum }_{v_{1},v_{2}\neq 0}R(v_{1})R(v_{2})\frac{\gcd (v_{1},v_{2})}{\sqrt{|v_{1}v_{2}|}}.\end{eqnarray}$$

According to the GCD bounds of [Reference Dyer and Harman6],

$$\begin{eqnarray}\mathop{\sum }_{v_{1},v_{2}\neq 0}R(v_{1})R(v_{2})\frac{\gcd (v_{1},v_{2})}{\sqrt{|v_{1}v_{2}|}}\ll \exp \biggl(\frac{10\log N}{\log \log N}\biggr)\mathop{\sum }_{v}R(v)^{2}\end{eqnarray}$$

(see [Reference Bondarenko and Seip5] for an essentially optimal refinement). Now

$$\begin{eqnarray}\!\sum \!R(v)^{2}=\#\{m_{i},n_{j}\leqslant N,m_{1}\neq n_{1},m_{2}\neq m_{2}:a(m_{1})-a(n_{1})=a(m_{2})-a(n_{2})\}\end{eqnarray}$$

is at most the additive energy $E({\mathcal{A}},N)$ . Thus,

$$\begin{eqnarray}\operatorname{Var}D(N,M)\ll \frac{1}{M}N^{\unicode[STIX]{x1D716}}E({\mathcal{A}},N)\end{eqnarray}$$

as claimed. ◻

Corollary 5. Assume that the additive energy satisfies $E({\mathcal{A}},N)<N^{2+o(1)}$ . If $M<N^{2-\unicode[STIX]{x1D702}}$ , then for almost all $\unicode[STIX]{x1D6FC}$ ,

$$\begin{eqnarray}D_{{\mathcal{A}}}(N,M)(\unicode[STIX]{x1D6FC})\sim \frac{N^{2}}{M}.\end{eqnarray}$$

Proof. Take $N_{k}=\lfloor k^{4/\unicode[STIX]{x1D702}}\rfloor$ , so that $\sum _{k}N_{k}^{-\unicode[STIX]{x1D702}/2}<\infty$ , and pick any $M_{k}<N_{k}^{2-\unicode[STIX]{x1D702}}$ , then we find from Proposition 3,

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{k}\int _{0}^{1}\Bigg|\frac{D(N_{k},M_{k})(\unicode[STIX]{x1D6FC})}{N_{k}(N_{k}-1)/M_{k}}-1\Bigg|^{2}\,d\unicode[STIX]{x1D6FC} & = & \displaystyle \mathop{\sum }_{k}\frac{\operatorname{Var}D(N_{k},M_{k})}{(N_{k}(N_{k}-1)/M_{k})^{2}}\nonumber\\ \displaystyle & {<} & \displaystyle \mathop{\sum }_{k}N_{k}^{o(1)}\frac{E(N_{k})M_{k}}{N_{k}^{4}}\ll \mathop{\sum }_{k}\frac{1}{N_{k}^{\unicode[STIX]{x1D702}/2}}<\infty ,\nonumber\end{eqnarray}$$

and so for almost all $\unicode[STIX]{x1D6FC}$ ,

(7) $$\begin{eqnarray}D(N_{k},M_{k})(\unicode[STIX]{x1D6FC})\sim \frac{N_{k}^{2}}{M_{k}}\quad \text{for all }k>k_{0}(\unicode[STIX]{x1D6FC}).\end{eqnarray}$$

A priori the set depends on the test function $f$ , but that can be taken care of by a standard diagonalization procedure; for our purposes we only need one test function.

Given $N\gg 1$ , there is a unique value of $k$ so that $N_{k}\leqslant N<N_{k+1}$ . Note that $N/N_{k}=1+O(N^{-\unicode[STIX]{x1D702}/4})$ . Since $M<N^{2-\unicode[STIX]{x1D702}}\sim N_{k}^{2-\unicode[STIX]{x1D702}}<N_{k+1}^{2-\unicode[STIX]{x1D702}}$ , we know from (7) that almost surely $D(N_{k},M)/(N_{k}^{2}/M)\rightarrow 1$ .

Note that

$$\begin{eqnarray}D(N_{k},M)\leqslant D(N,M)\leqslant D(N_{k+1},M).\end{eqnarray}$$

This is because the sums $D(N,M)$ consist of non-negative terms, and hence,

$$\begin{eqnarray}\displaystyle D(N,M) & = & \displaystyle \mathop{\sum }_{1\leqslant m\neq n\leqslant N}F_{M}(\unicode[STIX]{x1D6FC}(a(m)-a(n)))\nonumber\\ \displaystyle & {\geqslant} & \displaystyle \mathop{\sum }_{1\leqslant m\neq n\leqslant N_{k}}F_{M}(\unicode[STIX]{x1D6FC}(a(m)-a(n)))=D(N_{k},M)\nonumber\end{eqnarray}$$

(we dropped all pairs $(m,n)$ where $\max (m,n)>N_{k}$ ).

Since $N/N_{k}=1+O(N^{-\unicode[STIX]{x1D702}/4})$ , we have

$$\begin{eqnarray}\frac{D(N_{k},M)}{N_{k}^{2}/M}\leqslant \frac{D(N,M)}{N^{2}/M(1+O(N^{-\unicode[STIX]{x1D702}/4}))}=\frac{D(N,M)}{N^{2}/M}(1+O(N^{-\unicode[STIX]{x1D702}/4}))\end{eqnarray}$$

and likewise

$$\begin{eqnarray}\frac{D(N,M)}{N^{2}/M}\leqslant \frac{D(N_{k+1},M)}{N_{k+1}^{2}/M}(1+O(N^{-\unicode[STIX]{x1D702}/4})).\end{eqnarray}$$

Since we know that almost surely $D(N_{k},M)/(N_{k}^{2}/M)\rightarrow 1$ , we deduce that almost surely also $D(N,M)/(N^{2}/M)\rightarrow 1$ .◻

2 Lower bounds: proof of Theorem 1

We take any sequence of integers ${\mathcal{A}}=\{a(n)\}$ with distinct elements. We want to show that for any $\unicode[STIX]{x1D702}>0$ , almost surely,

$$\begin{eqnarray}\unicode[STIX]{x1D6FF}^{\unicode[STIX]{x1D6FC}}(N)>1/N^{2+\unicode[STIX]{x1D702}}\quad \text{for all }N>N_{0}(\unicode[STIX]{x1D6FC}).\end{eqnarray}$$

Let $N_{k}=\lfloor k\rfloor ^{2/\unicode[STIX]{x1D702}}$ . We claim that it suffices to show that, for almost all $\unicode[STIX]{x1D6FC}$ ,

(8) $$\begin{eqnarray}\unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N_{k})>2/N_{k}^{2+\unicode[STIX]{x1D702}}\quad \text{for all }k>k_{0}(\unicode[STIX]{x1D6FC}).\end{eqnarray}$$

Indeed, note that if $N_{k}\leqslant N<N_{k+1}$ then $\unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N)\geqslant \unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N_{k+1})$ . Since $N_{k+1}\sim N$ , by (8) we have, for almost all $\unicode[STIX]{x1D6FC}$

$$\begin{eqnarray}\unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N)\geqslant \unicode[STIX]{x1D6FF}_{ min}^{\unicode[STIX]{x1D6FC}}(N_{k+1})>2/N_{k+1}^{2+\unicode[STIX]{x1D702}}>1/N^{2+\unicode[STIX]{x1D702}}\end{eqnarray}$$

for $N>N_{0}(\unicode[STIX]{x1D6FC})$ .

To prove (8), it suffices, by the Borel–Cantelli lemma, to show that

(9) $$\begin{eqnarray}\mathop{\sum }_{k}\operatorname{Prob}(\unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N_{k})\leqslant 2/N_{k}^{2+\unicode[STIX]{x1D702}})<\infty .\end{eqnarray}$$

In the definition of $D(N,M)=D_{f}(N,M)$ , choose $f$ so that $f(x)\geqslant 1$ if $|x|\leqslant 1/4$ (and in addition, $f\geqslant 0$ is non-negative, $\int _{-\infty }^{\infty }f(x)\,dx=1$ , $f$ is smooth and supported in $[-1/2,1/2]$ ). Now note that for such $f$ , if $D_{f}(N,M)<1$ then $\unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N)>1/(4M)$ . This is because $D_{f}(N,M)$ is a sum of non-negative terms, and if there is one gap of size ${\leqslant}1/(4M)$ then the corresponding term $F_{M}(\unicode[STIX]{x1D6FC}(a(m)-a(n)))=\sum _{j}f(M(\unicode[STIX]{x1D6FC}(a(m)-a(n))+j))\geqslant 1$ by the choice of $f$ , so that $D_{f}(N,M)\geqslant 1$ . Thus, we find that

$$\begin{eqnarray}\unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N)\leqslant \frac{1}{4M}\quad \Rightarrow \quad D_{f}(N,M)\geqslant 1,\end{eqnarray}$$

and hence,

(10) $$\begin{eqnarray}\operatorname{Prob}\biggl(\unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N)\leqslant \frac{1}{4M}\biggr)\leqslant \operatorname{Prob}(D_{f}(N,M)\geqslant 1).\end{eqnarray}$$

Now since $D_{f}\geqslant 0$ ,

$$\begin{eqnarray}\operatorname{Prob}(D_{f}(N,M)\geqslant 1)\leqslant \int _{0}^{1}D_{f}(N,M)(\unicode[STIX]{x1D6FC})\,d\unicode[STIX]{x1D6FC}\end{eqnarray}$$

so that by (2), for $M_{k}=\frac{1}{8}N_{k}^{2+\unicode[STIX]{x1D702}}$ ,

$$\begin{eqnarray}\int _{0}^{1}D(N_{k},M_{k})(\unicode[STIX]{x1D6FC})\,d\unicode[STIX]{x1D6FC}\sim 8N_{k}^{-\unicode[STIX]{x1D702}}\ll \frac{1}{k^{2}},\end{eqnarray}$$

which together with (10) proves (9), and hence, (8). This proves Theorem 1.

3 Minimal gaps for the primes

Let $a(n)=p_{n}$ , the $n$ th prime. By Khinchin’s theorem, for all $\unicode[STIX]{x1D700}>0$ there is a set of full measure of the $\unicode[STIX]{x1D6FC}$ so that $\Vert q\unicode[STIX]{x1D6FC}\Vert \geqslant 1/(q(\log q)^{1+\unicode[STIX]{x1D700}})$ for any integer $q\geqslant q_{0}(\unicode[STIX]{x1D6FC})$ . In particular, for such $\unicode[STIX]{x1D6FC}$ , the gap between fractional parts of $\unicode[STIX]{x1D6FC}p_{n}\hspace{0.2em}{\rm mod}\hspace{0.2em}1$ are

$$\begin{eqnarray}\Vert \unicode[STIX]{x1D6FC}(p_{m}-p_{n})\Vert \gg \frac{1}{|p_{m}-p_{n}|(\log |p_{m}-p_{n}|)^{1+\unicode[STIX]{x1D700}}}\geqslant \frac{1}{N(\log N)^{2+\unicode[STIX]{x1D700}}},\end{eqnarray}$$

since $|p_{m}-p_{n}|\leqslant p_{N}\sim N\log N$ for $m<n\leqslant N$ . Hence, for such $\unicode[STIX]{x1D6FC}$ , the minimal gap satisfies $\unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N)>1/N(\log N)^{2+\unicode[STIX]{x1D700}}$ .

A similar argument applies to other dense cases, such as the sequence of square-free integers. An extreme case is that when ${\mathcal{A}}=\mathbb{N}$ is the sequence of all natural numbers. The argument above gives the minimal gap here is, for almost all $\unicode[STIX]{x1D6FC}$ , at least $\unicode[STIX]{x1D6FF}_{\min }^{\unicode[STIX]{x1D6FC}}(N)\gg 1/(N(\log N)^{1+\unicode[STIX]{x1D700}})$ . Note that in this case the “three-gap” theorem shows that there are at most three distinct gaps between the fractional parts $\{\unicode[STIX]{x1D6FC}n\hspace{0.2em}{\rm mod}\hspace{0.2em}1:n\leqslant N\}$ . Concerning other “dense” sequences, it is known that for any sequence of integers ${\mathcal{A}}\subset [1,M]$ , the fractional parts $\unicode[STIX]{x1D6FC}a(m)\hspace{0.2em}{\rm mod}\hspace{0.2em}1$ have at most $O(\sqrt{M})$ distinct gaps [Reference Balog, Granville and Solymosi2, Reference Vâjâitu and Zaharescu13].