On the Diophantine equation $a^2+b^2 = c^2+k$

Given the Diophantine equation,

$$a^2+b^2=c^2+k$$

where k is a constant integer. Let $0 < a \le b$, and $\Delta_k(N)$ be the number of primitive solutions with $0 < c < N$ for some bound N. For example, for k = 0 and $N = 10^5$, there are exactly 15919 primitive Pythagorean triples, hence $\Delta_0(10^5) = 15919$.

"Conjecture:

$$\lim_{N\to\infty}\frac{\Delta_k(N)}{N} = \text{constant}$$

where the constant, for negative k, involves $\frac{1}{\sqrt{-k}}$."

In the table below, the first column gives selected k, subsequent columns give (rounded to 5 decimal places) the ratio $\frac{\Delta_k(N)}{N}$ up to $N = 10^7$, its conjectured limit L as $N \to \infty$, and error difference of L and ratio at $N = 10^7$.

$$\begin{array}{ccccc} k&10^5&10^6&10^7&\infty&\text{Error diff}\\ 0&0.15919&0.15914&0.15916& \to 0.15915 \;=\; \frac{1}{2\pi}&0.00001\\ -1&0.12517&0.12497&0.12499& \to 0.12500 \;=\; \frac{1}{8}&0.00001\\ -2&0.17697&0.17679&0.17680& \to 0.17677 = \frac{1}{4\sqrt{2}}&0.00003\\ -3&0.28871&0.28868&0.28864& \to 0.28867 = \frac{1}{2\sqrt{3}}&0.00003\\ -5&0.22354&0.22367&0.22357& \to 0.22360 = \frac{1}{2\sqrt{5}}&0.00003\\ -7&0.37772&0.37780&0.37799& \to 0.37796 = \frac{1}{\sqrt{7}}&0.00003\\ \end{array}$$

Lehmer (1900) proved the case k = 0. Question: Can you prove the conjectured limits are valid/invalid?

Similar simple limits can be found for other negative k, but not for positive k. Code by Daniel Lichtblau of Wolfram Research to find the number of solutions $\le N$ can be found here, though $N = 10^7$ already takes more than an hour, and beyond that takes MUCH more. Do you know of a faster code?

-
What precisely does primitive mean in this context? – Zander Jul 2 '12 at 14:17
Primitive would be {a,b,c} has no common factor. It becomes relevant when $k=0$, or $k = \pm\,n^2$. – Tito Piezas III Jul 2 '12 at 15:51
For $k=-11$, $N=10^5$, I find $3/(2 \sqrt{11})$. Is it correct ? It takes one minute for $N=10^5$ with my program. The Daniel Lichtblau's code must be faster. How long does it take ? Instantaneous ? – francis-jamet Jul 2 '12 at 19:50
Francis: Yes, for $k = -11$, it's $3/(2\sqrt{11})$. The limit is simple to find, isn't it? (For positive k it is not obvious at all.) Lichtblau's Mathematica code takes about 10 seconds for $N = 10^5$. It's in the link I gave above. If you can tweak it and make it faster, I'll be very grateful. – Tito Piezas III Jul 2 '12 at 21:15
For $k=+1$ it seems to go something like $\Delta_1(N)/N=\log N/\pi+0.325$. – Zander Jul 3 '12 at 4:25

(this is not a proof)
Apparently, for squarefree $k$, the limit is $l(k) = \frac 1 2 \prod_{\text {prime }p} f_k(p)$, where :

$$f_k(p) = \left\{ \begin{array}{ll} \lim_{m \to \infty} E[ \#\{c \in \mathbb Z/p^m\mathbb Z, a^2+b^2 = c^2+k \}]_{(a,b)\in \mathbb (Z/p^m\mathbb Z)^2} & \text {for } p=2 \\ \lim_{m \to \infty} E[1+v_p(c^2+k)]_{c \in \mathbb Z/p^m\mathbb Z} & \text {for } p\equiv 1 \mod 4\\ \lim_{m \to \infty} E[\frac 1 2 (1 + (-1)^{v_p(c^2+k)})]_{c \in \mathbb Z/p^m\mathbb Z} & \text {for } p\equiv 3 \mod 4 \end{array} \right.$$

The argument for this formula is the following : the number of ways to write an integer $n$ as a sum of two squares is the number of elements of norm $n$ in $\mathbb Z[i]$. Modulo the units of $\mathbb Z[i]$, it is the product of the $(1+v_p(n))$ for $n \equiv 1 \mod 4$ and of the $\frac 1 2 (1 + (-1)^{v_p(n)})$ for $n \equiv 3 \mod 4$ (it is a direct consequence of the ideal group structure of $\mathbb Z[i]$). So the factors with $p>2$ express the expected value of the number of elements whose norm is a "randomly chosen" integer. The factor for $p=2$ is there to correct the conspiracy of $a^2+b^2$ not hitting things uniformly in $\mathbb Z_{(2)}$ (for example it never hits things of the form $4q+3$). Finally, the $\frac 1 2$ in front of the product is there because we are counting elements of norm $c^2+k$ not only up to units, but also up to conjugation.

Let $\chi(p) = 1$ if $p \equiv 1 \mod 4$ and $\chi(p) = -1$ if $p \equiv 3 \mod 4$, and I will suppose that $k$ is squarefree.

If $p$ is an odd prime dividing $k$, then $v_p(c^2+k) = \min (v_p(c^2,1)) = 1$ if $p$ divides $c$, $= 0$ otherwise. In this case, $f_k(p) = \frac{p-1}p + \frac 2 p = \frac {p+1} p$ when $\chi(p)=1$ ; and $f(p) = \frac{p-1}p$ when $\chi(p)=-1$ : $f_k(p) = \frac{p+\chi(p)}p$

If $p$ is an odd prime not dividing $k$ and if $-k$ is a square mod $p$, then $-k$ has two distinct square roots in $\mathbb Z_{(p)}$ and we have $v_p(c^2+k) = v_p(c+\sqrt{-k}) + v_p(c- \sqrt{-k})$, so that the "probability" of $v_p(c^2+k) \ge l$ is $2/p^l$. Thus, we get $f_k(p) = 1 + 2\chi(p)/p + 2/p^2 + 2\chi(p)/p^3 + \ldots = 2/(1- \chi(p)\frac 1p)-1 = \frac{p+\chi(p)}{p-\chi(p)}$

If $p$ is an odd prime not dividing $k$ and if $-k$ is not a square mod $p$, then $c^2+k$ can never be a multiple of $p$, so $v_p(c^2+k) = 0$, and $f_k(p) = 1$.

Let $\chi_d(p) = 1$ if $d$ is a square mod $p$, $-1$ if it is not, and $0$ if $p$ divides $d$. We see that we always have $$f_k(p) = \frac{p+\chi(p)}{p-\chi_{-k}(p)\chi(p)} = \frac{p+\chi(p)}{p-\chi_k(p)} = \frac{p^2-1}{(p-\chi_k(p))(p-\chi(p))}$$

Then we recognize an Euler product, which converges (except when $k = 1$, where $\chi_k$ is the trivial character) and which we can compute thanks to the class number formula (be careful because so far we implicitly want to have $2$ in the conductor of $\chi_k$) $$\prod f_k(p) = \frac{f_k(2) L(\chi_k,1)L(\chi,1)}{\frac 34 \zeta(2)} = \frac{f_k(2) h(k) R(k) \phi_2(k) }{(w_k/2) \sqrt{|k|} \phi_\infty(k)}$$

where $h(k)$ is the class number of $\mathbb Q(\sqrt{k})$, $R(k)$ is its regulator,$w_k$ its number of roots of unity, $\phi_2(k) = 3$ if $k \equiv 5 \mod 8$, $1$ otherwise, $\phi_\infty(k) = \frac \pi 2$ if $k>0$, $1$ otherwise.

Now, $f_k(2)$ is not difficult to compute, because the expectation of the number of solutions stabilizes very quickly. The formula agrees with the results presented so far and also works for positive $k$ :

$\begin{array}{ccccccccccccc} k & -13 & -11 & -10 & -7 & -6 & -5 & -3 & -2 & -1 & +2 & +3 & +5 \\ f_k(2) & 1/2 & 1 & 1/2 & 2 & 1/2 & 1/2 & 1 & 1/2 & 1/2 & 1/2 & 1/2 & 1 \\ l(k) & \frac 1 {2 \sqrt{13}} & \frac 3 {2 \sqrt {11}} & \frac 1 {2 \sqrt{10}} & \frac 1 {\sqrt 7} & \frac 1 {2 \sqrt{6}} & \frac 1 {2 \sqrt{5}} & \frac 1 {2 \sqrt{3}} & \frac 1 {4 \sqrt{2}} & \frac 18 & \frac {\log(1+\sqrt 2)}{2 \pi \sqrt 2} & \frac {\log(2+\sqrt 3)}{2 \pi \sqrt 3} & \frac {3 \log(\frac {1+\sqrt 5}2)}{\pi \sqrt 5}\end{array}$

-
Beautiful! I first came across this problem around 6 years ago, forgot about it, then thought of putting it here. For k = 2 and $N = 10^6$, Lichtblau's code gives the ratio as $99211/10^6 = 0.09921$ which approaches your $\frac{\log(1+\sqrt{2})}{2\pi\sqrt{2}} = 0.09919$. It is so good to finally know the limits for positive k. Thanks! – Tito Piezas III Jul 8 '12 at 7:19
Seeing the connection between this equation and class numbers prompted me to consider the case k = -163. Remarkably (given the fairly high proportion of integers that are sums of two squares), $a^2 + b^2 = c^2- 163$ (where obviously c must be > 12) has no solutions with c = 13 to 41 inclusive, the smallest being $1^2 + 40^2 = 42^2 - 163$. – Adam Bailey Jul 9 '12 at 8:45
@ Adam Bailey, after seeing that $c$ has to be odd and that one of $a$ or $b$ has to be odd and the other even, this equation reduces to $a'^2+a'+41 = (c'-b')(c'+b')$, and numbers represented by $x^2+x+41$ have all their prime factors $\ge 41$. So this explains why there is no solution with small $c$. But nevertheless, there are enough of them afterwards to reach the conjectured limit $3/2\sqrt{163}$ – mercio Jul 9 '12 at 10:50
@mercio, thank you for this explanation (I assume you meant c has to be even) ... and similar reasoning shows that k = +163 has many small solutions, specifically there is a solution if c is in the range 1 to 79 and is congruent 1 or 7 mod 8 (the latter condition ensuring that reduction to $x^2 + x + 41$ yields a prime of the form 4n+1 and therefore a sum of two squares). – Adam Bailey Jul 12 '12 at 11:53
Is there a reference for a rigorous proof? (Is it known?) – Holden Lee Mar 19 '14 at 0:08