The following is a joint blog post with Kyle Pratt, a fellow graduate student at UIUC.

Recall a theorem of Fermat, which asserts that a prime ${p}$ is ${\equiv 1 \pmod{4}}$ if and only if it is the sum of two squares. From Dirichlet’s theorem on primes in arithmetic progressions we conclude there are infinitely primes that can be written as the sum of two squares:

$\displaystyle p = m^2+\ell^2 \ \ \ \ \ (1)$

Fouvry and Iwaniec showed this can be strengthened in a strong way, by showing there are infinitely many primes of the form in (1) with ${\ell}$ prime.

Kyle and I, mostly to understand Fouvry and Iwaniec’s proof better, considered (a couple of years ago) the analogous question with

$\displaystyle \ell^2 - N m^2 , \ \ \ N > 0 , \ \ \ \ \ (2)$

replacing ${\ell^2 + m^2}$. We were lead to a rather interesting spacing result of fractions of the form

$\displaystyle \frac{v}{d}, \ \ \ \ \ v^2 - N \equiv 0 \, (\text{mod } d), \ \ \ \ D \leq d \leq 2D,$

which we explain below in the fold, using some basic theory of quadratic forms as well as a Brook’s theorem from graph theory.

We (very) briefly recall the structure of the Fouvry-Iwaniec argument. They look to asymptotically estimate

$\displaystyle \sum_{\ell^2 + m^2 \leq x} \Lambda(\ell) \Lambda(\ell^2 + m^2) ,\ \ \ \ \ (3)$

where ${\Lambda}$ is the Von Mongoldt function. They use Vaughan’s identity on ${\Lambda(\ell^2 + m^2)}$ to decompose (3) into Type I and Type II sums for the sequence

$\displaystyle a_n = \sum_{\ell^2 + m^2 =n} \Lambda(\ell).$

Great complications from the type II sums ensue, but the fundamental idea is to utilize the quadratic form appearing in (3) to factor

$\displaystyle a_{mn} = \sum_{a^2 + b^2 = m} \sum_{c^2 + d^2 = n} b_{m,n}$

where ${b_{m,n}}$ encodes a rather strange looking condition that is eventually managable. In essence, this follows from the Brahmagupta-Fibonacci identity of the form

$\displaystyle (a^2+b^2)(c^2 + d^2) = (ad-bc)^2 + (ac+bd)^2.$

Properties of Gaussian integers underly their analysis.

In this post we are more concerned with the Type I estimates. We look for a bound of the form

$\displaystyle \sum_{d \leq x^{\theta}} \Bigg| \sum_{\substack{n \leq x \\ d | n}} a_n - \frac{1}{d} \sum_{n\leq x} a_n \Bigg| \ll x^{1 - \epsilon}. \ \ \ \ \ (4)$

The largest ${\theta}$ for which (4) holds is the so-called level of distribution. In the analogous Bombieri-Vinogradov theorem, one can take any ${\theta<1/2}$ (thought only saving an arbitrary power of log), while it turns out here we can take the much stronger ${\theta <1}$ here. This is of the same strength as the unproven Elliot-Halberstam conjecture, as we are allowed to take advantage of the structure of the quadratic form ${\ell^2 + m^2}$. In the end, the Bombieri-Vinogradov theorem relies on the spacing of distinct Farey fractions

$\displaystyle \left|\frac{a}{q} - \frac{a'}{q'}\right| \geq \frac{1}{qq'}, \ \ \ (a,q) = (a',q') = 1.$

In a similar manner, a spacing result for the fractions

$\displaystyle \{\frac{v}{d} : D \leq d \leq 2D , \ v^2 + 1 \equiv 0 \ {\rm mod} \ d\},$

for a fixed large ${D}$, can be used to provide a bound for (4).

Thus in our search for primes of the form in (2), we are lead to study the spacing of fractions of the form

$\displaystyle \Big\{\frac{v}{d} : D \leq d \leq 2D , \ v^2 - N \equiv 0 \, (\text{mod }d)\Big\}, \ \ \ \ \ (5)$

where ${N}$ and ${D}$ are fixed (${D}$ large). For simplicity we take ${N}$ to be a discriminant of a quadratic number field, though this is not a significant assumption. The main spacing result looks as follows.

${ \ }$

Proposition 1: The fractions in (5) can be partitioned into sets ${F_1 , \ldots , F_t}$ such that ${t = O_N(1)}$, and for any distinct ${x,y \in F_j}$ we have

$\displaystyle \| x - y \| \gg \frac{1}{D}. \ \ \ \spadesuit$

${ \ }$

We remark this estimate is best possible up to logarithms. Proposition 1 combined with some reductions and the large sieve can be used to establish (4).

${ \ }$

Proof of Proposition 1: Suppose ${v^2 - N \equiv 0 \ (\text{mod }d)}$. Then we have

$\displaystyle d = ar^2 + 2brs + cs^2,\ \ \ \ \ (6)$

for some ${a,b,c,r,s\in \mathbb{Z}}$. Note we can choose the tuples ${(a,b,c)}$ to come from the ${h(N)}$ inequivalent quadratic forms of discriminant ${N}$. One can check that after multiplication by units in the ring of integers of ${\mathbb{Q}(\sqrt{N})}$, we may assume ${r \asymp_N s}$. It follows that ${r , s \asymp_N D^{1/2}}$

We have, as in this paper of Hooley (page 106), that

$\displaystyle \frac{v}{d} = \frac{\overline{r}}{s} - \frac{ar+bs}{sd}, \ \ \ r\overline{r} \equiv 1 \, (\text{mod }s).\ \ \ \ \ (7)$

Now

$\displaystyle \Big|\frac{\overline{r}}{s} - \frac{\overline{r'}}{s'}\Big| =\Big| \frac{r s' - r' s}{ss'}\Big| \gg \frac{1}{D}, \ \ \ r s' - r' s \neq 0. \ \ \ \ \ (8)$

Thus we want to show ${\frac{ar+bs}{sd}}$ is much smaller than ${1/D}$. We have the trivial bound

$\displaystyle \frac{ar+bs}{sd} \ll_N 1/D.\ \ \ \ \ (9)$

This is not good enough to ensure a spacing of ${1/D}$ as the error term can be bigger than the main term by a multiplicative constant. We cannot even ensure such a spacing for all the fractions in (5), but what we are able to do is partition the fractions into sets

$\displaystyle F_1, \ldots , F_t , \ \ \ t = O_N(1),$

such that we can improve (8) for the fractions that lie inside each set. Indeed for each ${a,b,c, r,s}$ there is a unique ${v}$ and ${d}$ that satisfy (6) and (7). Thus there are at most ${O_N(1)}$ choices of ${v,d}$ for a fixed ${r,s}$.

${ \ }$

Lemma 1: Suppose ${(x,y) = 1}$ and ${x,y \asymp_N D^{1/2}}$. Then there are at most ${O(k)}$ choices of coprime ${x',y' \asymp D^{1/2}}$ so that ${xy' - x'y = k}$. ${\spadesuit}$

${ \ }$

Proof of Lemma 1: Note that, by coprimality, ${k=0}$ is impossible. We have ${x' = x_0 + xt}$, ${y' = y_0 + yt}$. By size considerations, there are ${O(1)}$ choices for ${t}$ and thus ${x'}$ and ${y'}$. ${\spadesuit}$

${ \ }$

We choose ${K = K(N)}$ to be a sufficiently large constant. By Lemma 1, for a fixed fraction ${v/d}$ from (5), there are at most ${O_N(1)}$ choices ${v',d'}$ so that

$\displaystyle \Big|\frac{v}{d} - \frac{v'}{d'}\Big| \leq \frac{1}{D}.$

We create a graph ${G}$ with vertex set from (5) and ${v/d \sim v'/d'}$ if ${|r s' - r' s| \leq K}$. Thus ${G}$ has maximum degree ${O_N(1)}$. By Brooks’ theorem, we may find a coloring of ${G}$ with ${O_N(1)}$ color classes ${F_1, \ldots , F_t}$.

Inside a color class, we improve the lower bound in (8) to ${K/D}$ while (9) remains the same and so ${\|v/d - v'/d'\| \gg_N 1/D}$, as desired. ${\spadesuit}$