Given a binary quadratic form with negative discriminant, such as $3x^{2} + y^{2} = k$, is there an efficient algorithm to compute a value $k$ (or all the values) for which the form has exactly $n$ integer solutions?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
You should clarify what you mean by "efficient algorithm" and "to compute". In general you can express the number of representations as a linear combination of Dirichlet coefficients of certain Hecke $L$-functions. The Hecke characters are the unramified Hecke characters of $\mathbb{Q}(\sqrt{-d})$, where $-d$ is the discriminant of the quadratic form (there are complications when $-d$ is not a fundamental discriminant). The Dirichlet coefficients are multiplicative and can be described explicitly in terms of the Hecke characters. In the end you will have a formula in terms of the prime ideal decomposition of $(k)$ in $\mathbb{Q}(\sqrt{-d})$, and the values of the Hecke characters at the prime ideals participating in the decomposition. So yes, there is an algorithm, but it might not be efficient for your taste because you need to decompose into prime ideals in $\mathbb{Q}(\sqrt{-d})$ and consider about $\sqrt{|d|}$ Hecke characters (imposing "generalized congruence restrictions" on the prime ideals).
A good introduction into these things is Cox: Primes of the form $x^2+ny^2$.
answered Aug 27, 2012 at 15:15
-
$\begingroup$ Is it obvious that there will be ANY $k$ with exactly $n$ solutions? $\endgroup$ Aug 27, 2012 at 15:24
-
$\begingroup$ Are the Hecke characters involved all finite order characters, coming from the fact that we are counting ways to write $k$ as the norm of an integer, not as the norm of an ideal, or is there another source? $\endgroup$ Aug 27, 2012 at 15:28
-
$\begingroup$ @Igor Rivin: Certainly not if $k$ is an odd number other than $1$. $\endgroup$ Aug 27, 2012 at 15:28
-
$\begingroup$ @Will: The Hecke characters are the characters of the ideal class group of $\mathbb{Q}(-d)$, by class field theory, hence they are finite order characters (with no ramification). They serve to detect the principal ideals in $\mathbb{Q}(-d)$, as you say. $\endgroup$ Aug 27, 2012 at 15:48
$\begingroup$
$\endgroup$
If there is one value of $k$ where the form has exactly $n$ solutions, there are infinitely many values of $k$. This is because, if $ax^2+bxy+cx^2=k$ has $n$ solutions, and $p$ is a prime which is inert in $\mathbb Q(\sqrt{b^2-4ac})$ and does not divide $k$, then $ax^2+bxy+cy^2=kp^{2}$ has $n$ solutions as well, because $ax^2+bxy+cy^2\equiv 0$ mod $p$ has just the trivial solution, so $x$ and $y$ must be multiples of $p$.
Since there are infinitely many inert primes, one can get infinitely many different values of $k$.
answered Aug 27, 2012 at 15:37