Positive primes represented by indefinite binary quadratic form

Question

Neil Sloane asked me about commands in computer languages to find the (positive) primes represented by indefinite binary quadratic forms. So I wrote something in C++ that works. This is for the OEIS, these primes go into sequences... Note that, within a few hours, another guy had run the tables much higher with a one-line Maple command. Some days it does not pay to get up.

I thought of one I really do not understand. Discriminant $205$ has four classes of forms, $$ \langle 1, 13, -9 \rangle, \; \langle -1, 13, 9 \rangle, \; \langle 3, 13, -3 \rangle, \; \langle -3, 13, 3 \rangle. $$

The third and fourth are opposites so in the same genus, although distinct. The first two are in the principal genus, but they are not opposites, one is $-1$ times the other; in particular, they get diffeent positive primes, although both do residues $\pmod 5$ and $\pmod {41}.$ For $\langle 1, 13, -9 \rangle$ we get $$ 1,5,59,131,139,241,269,271,359,409, \ldots, $$ while for $\langle -1, 13, 9 \rangle$ we get $$ 31,41,61,251,349,379,389,401,419,431, \ldots. $$

For positive forms, low class number, there are polynomials, such as in Cox's book, such that primes represented by the principal form are those for which the polynomial factors a certain way. For a prime $p \equiv 1 \pmod 3,$ Gauss showed that $2$ is a cubic residue if an only if $p = u^2 + 27 v^2.$ Jacobi showed that $3$ is a cubic residue if an only if $p = u^2 + uv + 61 v^2.$ All I found in Henri Cohen's tables was the fact that $\mathbb Q(\sqrt {205})$ has class number $2$ and $L_K = \mathbb Q(\sqrt 5),$ appendix 12C on pages 533 and 534. See related information at IT'S A LINK.

Let's see, $34$ is the smallest number where it is a surprise that there is no solution to $x^2 - 34 y^2 = -1.$ The smallest such odd number is $205,$ as there is no solution to $x^2 - 205 y^2 = -1.$ For prime $p \equiv 1 \pmod 4,$ there is always a solution to $x^2 - p y^2 = -1.$ Proof in Mordell's book. Anyway, this is why $\langle 1, 13, -9 \rangle, \; \langle -1, 13, 9 \rangle$ are distinct classes.

So, that is the question, can I distinguish the represented (positive) primes by factoring some polynomial mod these primes?

Answer 1

Class field theory promises such a polynomial (more properly, such a number field $H$, since a polynomial generating $H$ might have to err on the first few primes, though in our case it turns out there's a polynomial with no exceptional primes). The proof is effective, though the recipe is often hard to carry out. So I attempted an end run by asking this database for number fields of degree $8$ and discriminant $205^4$, and was rewarded with $$ x^8 + 15 x^6 + 48 x^4 + 15 x^2 + 1, $$ which generates an unramified normal extension $H \, / \, {\bf Q}(\sqrt{205})$ with the right Galois group. This polynomial matches your list exactly: the gp code

{
forprime(p=1,1000,
   f = factormod(x^8+15*x^6+48*x^4+15*x^2+1, p)[,1];
   if(vecmax(vector(#f,n,poldegree(f[n])))==1,print(p))
)
}

returns your 5, 59, 131, 139, 241, 269, 271, 359, 409, and then continues 541, 569, 599, 661, 701, 761, 859, 881, 911, 941, still in exact agreement with the list of primes represented by $u^2 + 13uv - 9v^2$.

[added later] That gp code checks whether all factors of $P_8(x) := x^8 + 15 x^6 + 48 x^4 + 15 x^2 + 1 \bmod p$ have degree $1$. Since the polynomial is Galois, it would have been sufficient to check that one factor is linear:

{
forprime(p=3,1000,
   if(poldegree(factormod(x^8+15*x^6+48*x^4+15*x^2+1, p)[1,1])==1, print(p))
)
}

(I "cheated" a tad by excluding $p=2$, which is a factor of the discriminant of $P_8$ but not of the number field.) The Galois group of $P_8$ is dihedral, so one can find a quartic polynomial $P_4$ with the same Galois closure that factors completely mod $p$ iff $P_8$ does; such a polynomial was exhibited by NAME_IN_CAPS answering the follow-up Question 171846. Alternatively, we know already that $p$ is (either $5$ or) a quadratic residue of both $5$ and $41$, so by Quadratic Reciprocity $5$ and $41$ have square roots mod $p$, which means that $p$ factors completely in ${\bf Q}(\sqrt{5},\sqrt{41})$. And indeed $x^2$ generates that field and equals (some conjugate of) $$ -\frac14 (15 + 3 \sqrt{5} + \sqrt{41} + \sqrt{205}); $$ so you can also test whether $p$ is represented by $u^2 + 13uv - 9v^2$ by computing $\sqrt{5} \bmod p$ and $\sqrt{41} \bmod p$ (if they don't exist then there's no representation), and then testing whether $-(15 + 3 \sqrt{5} + \sqrt{41} + \sqrt{205})$ is a square mod $p$.

Answer 2

Consider the quadratic number field $K$ with discriminant $D = pq$, where $p$ and $q$ are primes $\equiv 1 \bmod 4$ (all results below hold after a suitable modification also for $p = 2$). By results due to Dirichlet and Scholz, The fundamental unit of this field has norm

• $-1$ if $(p/q) = -1$
• $+1$ if $(p/q) = +1$ and $(p/q)_4 (q/p)_4 = -1$
• $-1$ if $(p/q) = +1$ and $(p/q)_4 = (q/p)_4 = -1$

Here $(q/2)_4$ is $+1$ or $-1$ according as $p$ is congruent to $1$ or $9$ modulo $16$.

In the case $(p/q) = -1$, the Hilbert $2$-class field coincides with the genus field $K^* = Q(\sqrt{p},\sqrt{q}\,)$. This is also the Hilbert $2$-class field in the usual sense if $(p/q) = +1$ and $(p/q)_4 (q/p)_4 = -1$; in this case, however, there is a quadratic extension of the genus field unramified at finite primes, which can be constructed explicitly by solving the diophantine equation $x^2 - 4py^2 = q$ and setting $K = K^*(\sqrt{\mu})$ for $\mu = x + 2y\sqrt{p}$, where the sign of $x$ is chosen in such a way that $\mu$ is congruent to a square mod $4$, i.e., such that $x + 2y \equiv 1 \bmod 4$. In this case this means that $x$ is negative.

For the smallest discriminants, the corresponding elements are

• $D = 2 \cdot 17$: $\mu = -5 + 2 \sqrt{2}$;
• $D = 5 \cdot 41$: $\mu = -11 + 4 \sqrt{5}$;
• $D = 13 \cdot 17$: $\mu = -9 + 2 \sqrt{17}$;
• $D = 5 \cdot 61$: $\mu = -9 + 2 \sqrt{5}$.

Noam's generator in the case $D = 205$, by the way, is $\sqrt{\varepsilon_{205}} \cdot \omega$, where $\sqrt{\varepsilon_{205}} = \frac12(3\sqrt{5} + \sqrt{41})$ and $\omega = \frac12(1+\sqrt{5})$.

It is possible to construct the corresponding polynomials, but for your purpose it is better to work with the generators, as already Noam has pointed out.