# Sums of Squares

Every prime $p = 4k + 1$ can be uniquely expressed as sum of two squares, but for which integers $x$ is $x^2 + y^2 =$ some prime $p$? Stated differently, does the square of every positive integer appear as one of the squares in the representation of some prime $p$?

-
Even the case $x=1$, i.e. determining primes of the form $n^2+1$ is an open problem. –  Keivan Karai Mar 14 '13 at 11:01
But it's known that there is at least one n such that n^2 + 1 is prime. So the answer for 1 is yes. –  C. T. Jorgensen Mar 14 '13 at 11:20
I believe is has not been proved that for every $x$ there is a $y$ such that $x^2+y^2$ is prime. –  Gerry Myerson Mar 14 '13 at 11:25
Nice question. I'd like to see an elaboration of Gerry's comment. –  Joël Mar 14 '13 at 11:58
the computational evidence on this is remarkably regular - for p up to about 10**8. say x (or y) represents p if x**2+y**2 = p. if we then examine the primes (of form 4k+1) until all positive integers up to m have been used in a representation, then we will need to examine the first m**2 primes p=4k+1. the regularity is impressive. it is also tempting to conjecture that all squares are used equally often (in some asymptotic sense). –  geoffreyexoo Mar 14 '13 at 13:19

If the square of every positive integer appears as one of the squares in the representation of some prime -- that is, if for each $y$ there is an $x$ such that $x^2 + y^2$ is prime -- then it follows that there are infinitely many primes of the form $X^2 + Y^4$ (by restricting to $y$s that themselves are squares). This corollary happens to be true, but it was a breakthrough result of Friedlander and Iwaniec from about 15 years ago, so it seems unlikely that the much stronger question the OP is asking has been proven.
This is a special case of Bateman–Horn conjecture, which in this case states that for given $y\in\mathbb{N}$ the polynomial $p(x)=x^2+y^2$ assumes prime values for infinitely many $x\in\mathbb{N}$, more specifically, $$\#\{x\leq N: p(x)\text{ is prime}\}\sim\frac{1}{2}\prod_{p\nmid y}\frac{p-1-(-1)^{\frac{p-1}{2}}}{p-1}\cdot\frac{N}{\ln N},$$ thus the asymptotics should depend on $y$, but only by a multiplicative constant.