The Functions R(n), r(n), P(n) and N(n)

# The Functions R(n), r(n), P(n) and N(n)

Definition: For each $n \in \mathbb{N}$, $R(n)$ denotes the Number of Representations $(x, y)$ of $n = x^2 + y^2$. |

Definition: For each $n \in \mathbb{N}$, $r(n)$ denotes the Number of Proper Representations $(x, y)$ of $n = x^2 + y^2$. |

Definition: For each $n \in \mathbb{N}$, $P(n)$ denotes the Number of Proper Representations $(x, y)$ of $n = x^2 + y^2$ such that $x > 0$ and $y \geq 0$. |

Definition: For each $n \in \mathbb{N}$, $N(n)$ denotes the Number of Solutions to the congruence $x^2 \equiv -1 \pmod n$. |

The functions $R$, $r$, $P$, and $N$ are deeply connected. We establish these connections on the following pages:

Theorem 1: Let $n \in \mathbb{N}$. Then:a) $r(n) = 4P(n)$.b) $P(n) = N(n)$.c) $\displaystyle{R(n) = \sum_{d^2 | n} r \left ( \frac{n}{d^2} \right )}$. |

**Proof of b):**Let:

\begin{align} \quad P = \{ (a, b) : n = a^2 + b^2, \: a > 0, \: b \geq 0, \: (a, b) = 1 \} \end{align}

(2)
\begin{align} \quad N = \{ s \pmod n : s^2 \equiv -1 \pmod n \} \end{align}

- Observe that $P$ and $N$ are finite sets and that $P(n) = |P|$, $N(n) = |N|$. Define a function $f : P \to N$ for all $(a, b) \in P$ by:

\begin{align} \quad f((a, b)) = ab^{-1} \end{align}

- Observe that $f$ is a well defined function, for if $(a, b) \in P$ then $f((a, b)) \in N$ since:

\begin{align} \quad [f((a, b))]^2 &= [ab^{-1}]^2 \\ &= a^2 [b^{-1}]^2 \\ &= [n - b^2][b^{-1}]^2 \\ &= n[b^{-1}]^2 - b^2[b^2]^{-1} \\ &\equiv -1 \pmod n \end{align}

- We now show that $f$ is injective. Suppose that $f((a, b)) = f((c, d))$. Then $ab^{-1} \equiv cd^{-1} \pmod n$. So $ad - bc \equiv 0 \pmod n$. Since $a > 0$, and $b \geq 0$, it can be shown that this congruence implies that $ad - bc = 0$. So $ad = bc$.

- Since $a | ad$ we have that $a | bc$. But since $(a, b) = 1$ this implies that $a | c$. Similarly, since $c | bc$ we have that $c | ad$. Since $(c, d) = 1$ this implies that $c | a$. So $a = \pm c$. But $a, c > 0$ so $a = c$. So $b = d$. Thus $(a, b) = (c, d)$, and so $f$ is injective.

- We now show that $f$ is surjective. Let $s \in S$. Then $s^2 \equiv -1 \pmod n$. So $n | s^2 + 1$, and there exists an integer $k \in \mathbb{Z}$ for which $s^2 + 1 = kn$, thus:

\begin{align} \quad s^2 - kn &= -1 \\ \quad 4s^2 - 4kn &= -4 \\ \quad (2s)^2 - 4kn &= -4 \quad (*) \end{align}

- Let:

\begin{align} \quad g(x, y) = nx^2 + (2s)xy + ky^2 \end{align}

- Then the discriminant $d$ of $f$ is $(2s)^2 - 4kn$, which by $(*)$ is $d = -4$. Observe that $H(-4) = 1$. There is only one reduced positive definite binary quadratic form with discriminant $-4$, namely:

\begin{align} \quad f(x, y) = x^2 + y^2 \end{align}

- So we must have that $f \sim g$. So there exists integers $m_{11}, m_{12}, m_{21}, m_{22} \in \mathbb{Z}$ with $m_{11}m_{22} - m_{12}m_{21} = 1$ such that:

\begin{align} \quad g(x, y) = f(m_{11}x + m_{12}y, m_{21}x + m_{22}y) \end{align}

- So we see that:

\begin{align} \quad g(x, y) &= (m_{11}x + m_{12}y)^2 + (m_{21}x + m_{22}y)^2 \\ &= m_{11}^2x^2 + 2m_{11}m_{12}xy + m_{12}^2y^2 + m_{21}^2x^2 + 2m_{21}m_{22}xy + m_{22}^2y^2 \\ &= [m_{11}^2 + m_{21}^2]x^2 + [2m_{11}m_{12} + 2m_{21}m_{22}]xy + [m_{12}^2 + m_{22}^2]y^2 \end{align}

- Hence:

\begin{align} \quad n &= m_{11}^2 + m_{21}^2 &\quad (1) \\ \quad (2s) &= 2[m_{11}m_{12} + m_{21}m_{22}] & \quad (2)\\ \quad k &= m_{12}^2 + m_{22}^2 & \quad (3) \end{align}

- Let $a = m_{21}$ and let $b = m_{11}$. Then observe that $n = a^2 + b^2$ by (1). Suppose that $(a, b) = (m_{21}, m_{11}) = d$. Since $m_{11}m_{22} - m_{12}m_{21} = 1$, we see that $d | 1$. So $d = 1$, hence $(a, b) = 1$.

- Lastly, observe that from (2) and (3) and from $1 = m_{11}m_{22} - m_{12}m_{21}$ we have that:

\begin{align} \quad bs &= m_{11}s \\ & \overset{(2)} = m_{11}[m_{11}m_{12} + m_{21}m_{22}] \\ &= m_{11}^2m_{12} + m_{11}m_{21}m_{22} \\ &=m_{11}^2m_{12} + m_{21}[m_{11}m_{22}]\\ &=m_{11}^2m_{12} + m_{21}[m_{12}m_{21} + 1] \\ &=m_{11}^2m_{12} + m_{21}^2m_{12} + m_{21} \\ &= m_{12}[m_{11}^2 + m_{21}^2] + m_{21} \\ &= m_{12}n + m_{21} \\ & \equiv m_{21} \pmod n \\ & \equiv a \pmod n \end{align}

- Therefore $s \equiv ab^{-1} \pmod n$. Thus $f$ is surjective.

- Since $f : P \to N$ is bijective and $|P|, |N| < \infty$ we have that $|P| = |N|$, and so $P(n) = N(n)$. $\blacksquare$