# Counting the Number of Integral Solutions to $x^2+dy^2 = n$

It is a well known result that the number of integer solutions $(x,y), x>0, y\ge 0$ to $x^2+y^2 = n$ is $\sum_{d|n}\chi(d)$, where $\chi$ is the nontrivial Dirichlet character modulo $4$ such that $\chi(d)=1$ if $d\equiv 1\pmod{4}$, $\chi(d)=-1$ if $d\equiv 3\pmod{4}$, and $\chi(2k)=0$.

My question: Can we extend this to the integers of other imaginary quadratic fields? How many integer solutions are there to $x^2+2y^2 = n$ and $x^2+3y^2 = n$? Can this be generalized?

To derive the result for $x^2+y^2=n$, one extends the notion of a Euler product to the Gaussian integers $\mathbf{Z}[i]$. Suppose $a_n$ is the number of solutions, so $a_n$ is the number of ideals $(\alpha)\in\mathbf{Z}[i]$ such that $N(\alpha)=n$. Using well known characterization of irreducibles in $\mathbf{Z}[i]$, we get $$\sum_{n=1}^{\infty}\frac{a_n}{n^s}=\prod_{(\pi)}\frac{1}{1-N(\pi)^{-s}}=\left(\frac{1}{1-2^{-s}}\right)\prod_{p\equiv 1\pmod{4}}\left(\frac{1}{1-p^{-s}}\right)^2\prod_{q\equiv 3\pmod{4}}\left(\frac{1}{1-q^{-2s}}\right).$$ After algebraic manipulation followed by introducing the zeta function, we can write the RHS as $$\zeta(s)\left(\prod_{p\equiv 1\pmod{4}}\frac{1}{1-p^{-s}}\right)\left(\prod_{q\equiv 3\pmod{4}}\frac{1}{1+q^{-s}}\right)=\zeta(s)\prod_{p}\frac{1}{1-\chi(p)p^{-s}}=\zeta(s)\sum_{n=1}^{\infty}\frac{\chi(n)}{n^s}$$ due to standard results on multiplicativity. Finally, due to Dirichlet convolution, we can match up coefficients to what we originally started with to get the desired $a_n = \sum_{d|n}\chi(d)$.

In the case of $x^2+3y^2=n$, we would work over $\mathbf{Z}[\omega]$. The irreducibles here are precisely $1-\omega$, $q\equiv 2\pmod{3}$ where $q$ is a rational prime, and $\pi$ such that $p = \pi\bar\pi$ where $p\equiv 1\pmod{3}$ is a rational prime. Similarly in $\mathbf{Z}[\sqrt{-2}]$, the conditions for irreducibility depend on the residue class of the norm modulo $8$. Thus, using a Dirichlet character modulo $3$ or modulo $8$, could we also extend the Euler product to these rings - thus allowing to answer such questions?

Finally, can this be generalized to the integers of $\mathbf{Q}(\sqrt{-d})$ in general so as to give a way to count the number of solutions to $x^2+dy^2=n$ in terms of Dirichlet characters? Would this work differently in quadratic extensions with different class numbers? Moreover, there are $\varphi(m)$ characters modulo $m$, so which one would we use?

I hope the jumble of thoughts and questions above are not completely ignorant, naive, and/or trivial (or completely bogus). Any ideas/thoughts/answers are greatly appreciated.

EDIT: Lemma 3.25 in David Cox's Primes of the form $x^2+ny^2$ actually gives a formula for this sort of computation: Let $m$ be a positive odd number relatively prime to $n>1$. Then, the number of ways that $m$ is properly represented by a reduced form of discriminant $-4n$ is $2\displaystyle\prod_{p|n}\left(1+\left(\frac{-n}{p}\right)\right).$ While Cox states that he doesn't deal with number of representations by forms in his book, the proof of this is dealt with in the exercises.

• It appears that an exact answer doesn't exist in all cases: media.wix.com/ugd/18f425_e232d911fd80a6f74278b5df2a36ab3b.pdf seems like a pretty solid introduction to the issue. – Steven Stadnicki Jan 20 '14 at 17:49
• I could be mistaken, but after some hasty scratch work it appears that the Dirichlet character modulo $8$ such that $\chi(d) = 1$ if $d\equiv 1,3\pmod{8}$, $\chi(d) = -1$ if $d\equiv 5,7\pmod{8}$, and $\chi(2k)=0$ works for the $\mathbf{Z}[\sqrt{-2}]$ case. – tc1729 Jan 20 '14 at 19:50
• @Steven Stadnicki ; My dear Steven Stadnicki, your link does not still works. – Davood Khajehpour Sep 16 '17 at 15:39
• @Famke, I see the bounty got awarded. I tend to agree that the excerpt from Cox does not give a final answer to the problem. That would be Siegel's approach, giving a weighted average number of representations of a number by a genus. For positive forms, this is an actual average; for indefinite forms, we switch to counting orbits of solutions under the modular group; I have answered many problems on this site that display orbits, seems to me I had a recent one with target 44 math.stackexchange.com/questions/2424587/… – Will Jagy Sep 24 '17 at 0:07
• @Will Jagy ; thank you my dear Will Jagy. – Davood Khajehpour Sep 24 '17 at 18:41

## 3 Answers

It's been a while since I've looked at this, and at the time I didn't fully understand everything, so the details are going to be a little fuzzy, but here goes. We can give an answer in the case where there is one quadratic form per genus, which includes the class number one case.

For some of the general theory needed see Section 4.3 Modular Forms and Algebraic Number Theory, in the lectures on Elliptic Modular Forms and Their Applications by D. Zagier, in the book The 1-2-3 of Modular Forms.

Take a discriminant $D$ such that there is one quadratic form per genus. One form per genus is equivalent to the class group being isomorphic to $(\mathbb{Z}/2\mathbb{Z})^m$ for some $m$. The discriminants for which this is the case are given by $-4n$, where $n$ is one of Euler's convenient numbers. In this case we can derive explicit formula for the rep numbers $r_{Q}(n)$ for each quadratic form $Q$ of discriminant $D$ as follows.

Take the quadratic forms $Q_i$ of discriminant $D$, and look at their theta series $$\Theta_{Q_i} = \sum r_{Q_i}(n) q^n \, .$$ For each character $\chi$ of the class group, we can consider the following sum of theta series $$f_\chi = \frac{1}{w} \sum_{Q_i} \chi(Q_i) \Theta_{Q_i} \, ,$$ ($w$ the number of roots of unity in the relevant quadratic field). We also have the associated $L$-series $L(f_\chi, s)$.

For the trivial character $\chi_0$, it's know that $$L(f_{\chi_0}, s) = \zeta(s) L(\varepsilon_D, s) \, ,$$ where $\varepsilon_D(n) = (\tfrac{D}{n})$ is the Kronecker symbol. For a character of order 2 (as all other characters will be in this case), it's know that the $L$-series factors as $$L(f_{\chi}, s) = L(\varepsilon_{D_1}, s) L(\varepsilon_{D_2}, s)$$ for some other discriminants $D_1 D_2 = D$.

From this we can explicitly find the coefficients of each $f_{\chi}$. By solving the resulting system for $\Theta_{Q_i}$, we get a formula for $r_{Q_i}(n)$.

This might be more understandable in the context of an example. For discriminant $D = -20$, the two quadratic forms are $$Q_0(x,y) = x^2 + 5y^2 \\ Q_1(x,y) = 2x^2 + 2xy + 3y^2 \, ,$$ and there is one form per genus since the class group is exactly $\mathbb{Z}/2\mathbb{Z}$. Write $\Theta_0$ and $\Theta_1$ for the theta series of $Q_0$ and $Q_1$ respectively.

The trivial character $\chi_0$ sends $Q_0, Q_1 \mapsto 1$, while the non-trivial character $\chi_1$ sends $Q_0 \mapsto 1$ and $Q_1 \mapsto -1$. This means we need to consider the following combinations of theta series $$f_{\chi_0} = \tfrac{1}{2} ( \Theta_0 + \Theta_1 ) \\ f_{\chi_1} = \tfrac{1}{2} ( \Theta_0 - \Theta_1 ) \, .$$ Then it turns out that $$L(f_{\chi_0},s) = \zeta(s) L(\varepsilon_{-20}, s) \\ L(f_{\chi_1},s) = L(\varepsilon_{-4}, s) L(\varepsilon_{5}, s)$$

(At the moment I don't recall the full details. But one can get the last line by first saying $$L(f_{\chi_1}, s) = \prod_p (1 - a_p p^{-s} + (\tfrac{-20}{p}) p^{-2s})^{-1} \, ,$$ using the fact that $f_{\chi_1}$ is a Hecke eigenform on $S_1(\Gamma_0(20), (\tfrac{-20}{\cdot}))$. Then work out that $$a_p = \begin{cases} 1 & \text{if  p = 5 } \\ 0 & \text{if  (\tfrac{-20}{p}) = -1 } \\ 2 & \text{if  (\tfrac{-20}{p}) = -1  and  Q_0  represents  p } \\ -2 & \text{if  (\tfrac{-20}{p}) = -1  and  Q_1  represents  p } \end{cases}$$ Finally check that $a_p$ agrees with $(\tfrac{5}{p}) + (\tfrac{-4}{p})$.)

Multiplying two $L$-series means taking the convolution of their coefficients. Doing this and translating back to the $f_{\chi_i}$ gives $$f_{\chi_0} = \tfrac{1}{2} (\Theta_0 + \Theta_1) = 1 + \sum_{n=1}^\infty \left( \sum_{d \mid n} (\tfrac{-20}{d}) \right) q^n \\ f_{\chi_0} = \tfrac{1}{2} (\Theta_0 - \Theta_1) = 0 + \sum_{n=1}^\infty \left( \sum_{d \mid n} (\tfrac{-4}{d}) (\tfrac{5}{n/d} ) \right) q^n$$

Then, solving for $\Theta_0$ and $\Theta_1$ gives $$\Theta_0 = 1 + \sum_{n=1}^\infty \left( \sum_{d \mid n} (\tfrac{-20}{d}) + (\tfrac{-4}{d}) (\tfrac{5}{n/d} ) \right) q^n \\ \Theta_0 = 1 + \sum_{n=1}^\infty \left( \sum_{d \mid n} (\tfrac{-20}{d}) - (\tfrac{-4}{d}) (\tfrac{5}{n/d} ) \right) q^n \, .$$ Finally we can read off the following formulae for the rep numbers of $Q_0$ and $Q_1$: $$r_{Q_0}(n) = r_{x^2 + 5y^2}(n) = \sum_{d \mid n} (\tfrac{-20}{d}) + (\tfrac{-4}{d}) (\tfrac{5}{n/d} ) \\ r_{Q_1}(n) = r_{2x^2 + 2xy + 3y^2}(n) = \sum_{d \mid n} (\tfrac{-20}{d}) - (\tfrac{-4}{d}) (\tfrac{5}{n/d} )$$

This method should generalise to any discrimiant $D = -4n$, where $n$ is a convenient (or idoneal) numbers. For example $n = 21$ leads to the following formulae \begin{align*} r_{x^2+21y^2}(n) &= \frac{1}{2} \sum_{d \mid n } (\tfrac{-84}{d}) + (\tfrac{-3}{d})(\tfrac{28}{n/d}) + (\tfrac{-4}{d})(\tfrac{21}{n/d}) + (\tfrac{-7}{d})(\tfrac{12}{n/d}) \\ r_{3x^2+7y^2}(n) &= \frac{1}{2} \sum_{d \mid n } (\tfrac{-84}{d}) + (\tfrac{-3}{d})(\tfrac{28}{n/d}) - (\tfrac{-4}{d})(\tfrac{21}{n/d}) - (\tfrac{-7}{d})(\tfrac{12}{n/d}) \\ r_{2x^2+2xy+11y^2}(n) &= \frac{1}{2} \sum_{d \mid n } (\tfrac{-84}{d}) - (\tfrac{-3}{d})(\tfrac{28}{n/d}) - (\tfrac{-4}{d})(\tfrac{21}{n/d}) + (\tfrac{-7}{d})(\tfrac{12}{n/d}) \\ r_{5x^2+4xy+5y^2}(n) &= \frac{1}{2} \sum_{d \mid n } (\tfrac{-84}{d}) - (\tfrac{-3}{d})(\tfrac{28}{n/d}) + (\tfrac{-4}{d})(\tfrac{21}{n/d}) - (\tfrac{-7}{d})(\tfrac{12}{n/d}) \end{align*}

So there will be 65 (or possibly 66) different discriminants where this works, starting $D = -4n$ for $n = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 21, 22, \ldots, 1848$. Moreover we get one such formula for each of the equivalence classes of quadratic forms for the these discriminants; there are a total of 331 such quadratic forms (add up the class numbers for these discriminants), and so 331 such formulae (not counting those which would from the possible 66th value of $n$, if it exists).

• Could you generalize this method to another quadratic form rather than $x^2+5y^2, 2x^2+2xy+3y^2$. If the answer is positive; do you belive the number of such quadratic forms are more than $50$? – Davood Khajehpour Oct 8 '17 at 10:40
• @accursed This method should work whenever the discriminant is $-4n$, for $n$ one of Euler's convenient (idoneal) numbers. I've added an example for the case $n = 21$. – Steven Charlton Oct 8 '17 at 14:16
• I'm studying Artin and Hecke L-functions, do you have an intuitive explanation of what is the genus of a binary quadratic form $Q$ in this framework ? (I start from $\sum_{n \in \mathbb{Z}^2} e^{2i \pi z Q(n,n)} = \sum_{a \in \Lambda} e^{2i \pi N(a)}$ where $\Lambda = u\mathbb{Z}+v \mathbb{Z}$ is a lattice in some $\mathbb{Q}(\sqrt{d})$) – reuns Oct 8 '17 at 22:07
• @accursed For binary quadratic forms (2 variables) of a fixed discrimination $D$, the number of forms per genus is constant, so I cannot give your an example in this case. For higher arity (say 3 variables), I think one can find such examples though I would need to consult the literature first. – Steven Charlton Oct 9 '17 at 5:58
• @accursed Indeed, the reference is Corollary 3.14 in Primes of the form $x^2 + ny^2$, 2013, 2nd Ed, David A Cox. It says: Let $D < 0$ be a discriminant. Then i) All genera of forms of discriminant $D$ consist of the same number of classes, and ii) The number of genera of forms of discriminant $D$ is a power of 2. – Steven Charlton Oct 10 '17 at 1:28

We can extend the argument to any imaginary quadratic field with class number one, and use the Jacobi triple product identity to provide Lambert series for the representation function: $$r(n)=|\{(x,y)\in\mathbb{Z}\times\mathbb{Z}:x^2+dy^2=n\}|.$$ For such cases, it is also true that the representation function is an hypomultiplicative function, i.e. $$r(n) = K\cdot f(n)$$ where $f$ is a multiplicative function and $K$ is the number of units in the ring $\mathbb{Z}[\sqrt{-d}]$.

However, there are just a finite number of imaginary quadratic field with class number one.

For the whole topic, the book of Cox "Primes of the form $n^2+ny^2$" is an excellent reference.

Here are two pages from Leonard Eugene Dickson, Introduction to the Theory of Numbers. You may need to adjust to get your results with some inequalities on the variables. later he does a few forms such as $x^2 + 5 y^2$ and $2 x^2 + 2 x y + 3 y^2$ with one form per genus. 