# Primes written as the sum of two squares

A well known result due to Fermat states that any prime $p \equiv 1 \pmod 4$ can be written as the sum of two squares,$\,$ $p = a^2 + b^2$ .$\,$ We can define a set $\,A\,$ by collecting together all the $a$'s and $b$'s which arise in this way (ignoring multiplicity).$\,$ Examples include:$\;$ $5 = 1^2 + 2^2$,$\;$$13 = 2^2 + 3^2,\;$$17 = 1^2 + 4^2$,$\;$$29 = 2^2 + 5^2,\;and \,$$37 = 1^2 + 6^2$. $\;$From these examples we see that $\,A\,$ begins with $\;A = \,${$\,$$1,2,3,4,5,6, ...$$\,$}$\;$.

Questions: $\;$ 1) Does the set $\,A\,$ coincide with the set of all natural numbers?

$\qquad$$\qquad$$\quad$2) If not or if this is not known, is there at least a good lower bound for the density of$\qquad$$\qquad$$\quad$$\;$$\;$ the set$\,A\,$?

Thanks.

• For (2), the number of elements of $A$ up to $y$ is at least $(1+o(1)) y/\sqrt{2\log y}$. This follows from the fact that all the primes up to $y^2$ that are $1\pmod4$ have to have a representation from $A\cap[1,y]$, if $a(y) = \#(A\cap[1,y])$, then we must have $\binom{a(y)}2 \ge \pi(y^2;4,1) \sim y^2/4\log y$. Oct 28 '15 at 18:35

1) is almost certainly true, though it does not seem to be a known result.

It is equivalent to show that every vertical line in the Gaussian integers contains a Gaussian prime. There are many similar results along these lines, such as Tao's result that the Gaussian primes contain arbitrarily shaped constellations.

In fact, it is likely that every vertical line contains infinitely many primes, but this would imply Landau's fourth problem, and so it's certainly difficult.

Since it is frequently just as difficult to show that a sequence contains one prime as it is to show that it contains infinitely many, I would not be optimistic that this conjecture will be resolved anytime soon.

There may be a way to get a nice answer to 2) using known results. For example, a standard density theorem is that the Gaussian primes are distributed evenly through sectors, which might lead to a lower bound on the density of their $x$-coordinates.

• Nice answer! Interesting that your point "that every vertical line in the Gaussian integers contains a Gaussian prime" remains unresolved, is among the impediments to showing that Gaussian prime spirals always close. Oct 28 '15 at 23:59

2) By looking at this derivation, there are asymptoticaly $2n^2/\log n$ Gaussian primes in the circle $|z|<n$, and so, in the square $0<\Re z,\Im z<n$ there are at least (asymptoticaly) $n^2/2\log n$ Gaussian primes. Hence, by pigeonhole principle, at least $n/2\log n$ abscissas out of first $n$ contain at least one Gaussian prime.

This is a very crude lower bound, but it's better than nothing.