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 is 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:

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 prime.

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

replacing . We were lead to a rather interesting spacing result of fractions of the form

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

where is the Von Mongoldt function. They use Vaughan’s identity on to decompose (3) into Type I and Type II sums for the sequence

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

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

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

The largest for which (4) holds is the so-called level of distribution. In the analogous Bombieri-Vinogradov theorem, one can take any (thought only saving an arbitrary power of log), while it turns out here we can take the much stronger 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 . In the end, the Bombieri-Vinogradov theorem relies on the spacing of distinct Farey fractions

In a similar manner, a spacing result for the fractions

for a fixed large , 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

where and are fixed ( large). For simplicity we take 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 such that , and for any distinct we have

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 . Then we have

for some . Note we can choose the tuples to come from the inequivalent quadratic forms of discriminant . One can check that after multiplication by units in the ring of integers of , we may assume . It follows that

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

Thus we want to show is much smaller than . We have the trivial bound

This is not good enough to ensure a spacing of 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

such that we can improve (8) for the fractions that lie inside each set. Indeed for each there is a unique and that satisfy (6) and (7). Thus there are at most choices of for a fixed .

**Lemma 1:** Suppose and . Then there are at most choices of coprime so that .

**Proof of Lemma 1:** Note that, by coprimality, is impossible. We have , . By size considerations, there are choices for and thus and .

We choose to be a sufficiently large constant. By Lemma 1, for a fixed fraction from (5), there are at most choices so that

We create a graph with vertex set from (5) and if . Thus has maximum degree . By Brooks’ theorem, we may find a coloring of with color classes .

Inside a color class, we improve the lower bound in (8) to while (9) remains the same and so , as desired.