Sums of Two Squares

note

This is Lab 4 from Clint by Hugh Montgomery, edited by Elad Zelingher. All rights reserved to Hugh Montgomery.

Problem 1

Apply the program PolySolv to the polynomial $f(x)=x^{2}+1$. Take the modulus to be a prime number $\equiv 3 (\bmod 4)$, and note that the congruence has no solution as proved in Theorem 2.12 of NZM. Take $p$ to be a prime $\equiv 1(\bmod 4)$. How many solutions are there? How are they related to each other? Try several different primes $\equiv 1(\bmod 4)$. Is the number of solutions always the same? Form a conjecture (This conjecture can be proved by applying Corollary 2.27, or by taking $d=4$ in Corollary 2.30 of NZM.). How many solutions are there when $p=2$ ? Let $N(m)$ denote the number of solutions of the congruence $x^{2}+1 \equiv 0 (\bmod m)$. Use PolySolv to determine the value of $N\left(2^{j}\right), N\left(3^{j}\right)$, and $N\left(5^{j}\right)$ for several small values of $j$. Does a pattern emerge?

Problem 2

The program SumsPwrs will find all representations of $n$ as a sum of $s$ $k$-th powers, by exhaustive searching. If $s$ is large compared with $k$ then the time required for this increases very rapidly with $n$. Use SumsPwrs with input $n=1105$ $s=2$ $k=2$. Let $R(n)$ denote the number of representations of $n$ as a sum of two squares. That is, the number of ordered pairs $(x, y)$ of integers such that $x^{2}+y^{2}=n$. (Note that $x$ and/or $y$ may be negative.) Thus from SumsPwrs we find that $R(1105)=32$. A representation $n=x^{2}+y^{2}$ is called proper if $\gcd(x, y)=1$. Let $r(n)$ denote the number of proper representations of $n$. Using Factor, PolySolv, and SumsPwrs, determine entries for the table below:

$n$	Factorization	$R(n)$	$r(n)$	$N(n)$
5
13
17
65
91
1105

The functions $N(n)$ and $r(n)$ are closely related. Can you spot the connection? (These functions are discussed in $\S 3.6$ of NZM, as an application of the theory of binary quadratic forms.) Theorem 2.15 of NZM asserts that one can determine whether $n$ is a sum of two squares by inspecting the canonical factorization of $n$. Is your data above consistent with this description?

Problem 3

Choose a prime number $p \equiv 1(\bmod 4)$, and set $x=\left(\frac{p-1}{2}\right)!$. Use FctrlTab to find the value of $x(\bmod p)$. Then use WolframAlpha to confirm that $x^{2} \equiv-1(\bmod p)$. This is computationally slow when $p$ is large, because of the large number of multiplications required to evaluate the factorial. A much faster method for finding solutions of this congruence is found at the top of p. 111 of NZM. Once the congruence has been solved, the representation of $p$ as a sum of two squares can be found quickly, either by using the theory of binary quadratic forms (see Example 3 in $\S 3.6$ of NZM), or by using continued fractions (as described in Problem 6. at the end of $\S 7.3$ of NZM).

Problem 4

Let $f(x)=x^{2}+1$. If $p \equiv 1(\bmod 4)$ then $f$ has exactly one root $x$ for which $0<x<$ $p / 2$. Let $p$ run over a collection of such primes. How are the numbers $2 x / p$ distributed in the interval $(0,1)$ ? It has long been conjectured that these quantities approach uniform distribution as $p$ runs over all primes $\equiv 1(\bmod 4), p \leq x$, with $x$ tending to infinity. One could write a program to test how rapidly the distribution approaches uniformity. This conjecture was finally proved in 1994 (see W. Duke, J. B. Friedlander, and H. Iwaniec, Equidistribution of roots of a quadratic congruence to prime moduli, Annals of Math. (2) 141 (1995), 423-441). The proof is quite sophisticated, as it depends on the spectral theory of modular forms.

Problem 5

Let $x=\left(\frac{p-1}{2}\right)!$, as in Problem 3 above. What is $x(\bmod p)$, if $p \equiv 3(\bmod 4)$ ? Use FctrlTab to investigate, and recall Problem 18 on p. 57 of NZM. Of the two possibilities that occur here, it seems not to be known that both occur for infinitely many $p \equiv 3$ $(\bmod 4)$, although one might conjecture that each occurs asymptotically $1 / 2$ the time. One could write a program to generate statistical data. D. H. Lehmer showed that the two possibilities are connected to whether $h(-p) \equiv 1 (\bmod 4)$ or $\equiv 3(\bmod 4)$, where $h(-p)$ is a class number of binary quadratic forms, as defined in Problem 13 on p. 163 of NZM..

In view of the definition of $R(n)$, it is clear that the sum $\sum_{n \leq x} R(n)$ is equal to the number of lattice points $(x, y)$ in the disk of radius $\sqrt{x}$ centered at the origin. As the number $N$ of lattice points within a convex body $\mathcal{C}$ differs from the area $A$ of that body by an amount that is at most proportional to the perimeter $P$ of that body. That is, $N=A+O(P)$. Applying this to the disk, we deduce that

$$\begin{equation*} \sum_{n \leq x} R(n)=\pi x+O(\sqrt{x}) . \end{equation*}$$

Let $B(x)$ denote the number of integers $n \leq x$ that can be expressed as a sum of two squares. One might think that the relation above suggests that $B(x) \sim c x$ as $x$ tends to infinity (i.e., the sums of two squares form a set of positive asymptotic density). However, Landau proved that

$$\begin{equation*} B(x) \sim \frac{b x}{\sqrt{\log x}} \end{equation*}$$

as $x$ tends to infinity. Here $b$ is a certain positive constant. The apparent discrepancy between these results is reconciled by recognizing that $R(n)$ is usually 0 , but if $R(n)>0$ then $R(n)$ is likely to be large. The tools required to prove (2) are similar to those used in the analytic proof of the Prime Number Theorem: Dirichlet series, Euler products, contour integration, etc. For an exposition of this, see W. J. LeVeque, Topics in Number Theory, vol. II, Addison-Wesley, Reading, 1956, pp. 257-263.

It is known that the limiting approximation in (2) is approached only slowly. A more accurate approximation to $B(x)$ could be constructed by introducing a second term on the right hand side of (2), of the form $b_{1} x /(\log x)^{3 / 2}$. Here $b_{1}$ is some appropriate constant. Still greater accuracy would be achieved by introducing a term $b_{2} x /(\log x)^{5 / 2}$, and so on. This is discussed by D. Shanks, The second-order term in the asymptotic expansion of $B(x)$, Math. Comp. 85 (1964), 75-86. It turns out that the constant $b$ in (2) is

$$b=\left(2 \prod_{q \equiv 3 (\bmod 4)}\left(1-\frac{1}{q^{2}}\right)\right)^{-1 / 2}=0.764223654 \ldots$$

where the product is taken over all prime numbers $q \equiv 3(\bmod 4)$.