Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 5 down vote accepted

(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} $

share|improve this answer
    
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 at 0:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.