%% \documentclass[preprint,review,12pt]{elsarticle}
%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
%% for a journal layout.
\documentclass[final,3p,times]{elsarticle}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=true,allcolors=blue}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{microtype}

\theoremstyle{plain}
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Corollary}[Theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Remark}[Theorem]{Remark}

\journal{Hexagon}

\begin{document}

\begin{frontmatter}

\title{Class Numbers of Imaginary Quadratic Orders in the Polynomial Hierarchy}

\author{Frank Vega}

\address{Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA}

\ead{vega.frank@gmail.com}

\begin{abstract}
For $d \geq 3$ with $-d \equiv 0, 1 \pmod 4$, let $h(-d)$ be the number of classes of primitive positive definite binary quadratic forms of discriminant $-d$. We prove that $d \mapsto h(-d)$ is computable in deterministic polynomial time with an oracle for a language in the second level $\Sigma_2^{\text{P}}$ of the polynomial hierarchy. The proof uses only reduction theory of binary quadratic forms, Lagrange's theorem and Hermite normal forms; it does not assume the generalized Riemann hypothesis, does not take a generating set of the class group as input, and uses no randomness. A $\Sigma_2^{\text{P}}$ oracle finds a generating set of $O(\log d)$ forms, and an NP oracle then determines the lattice of relations, whose index is $h(-d)$. Consequently, if $\text{P} = \text{NP}$, class numbers of imaginary quadratic fields are computable in polynomial time. As an application, the number $D_n$ of representations of $n$ by the ternary form $8x^2 + 2y^2 + 16z^2$ in Tunnell's congruent number criterion equals $2h(-4n)$ for square-free $n \equiv 2 \pmod 8$ and vanishes for square-free $n \equiv 6 \pmod 8$; hence $D_n$ lies in $\text{FP}^{\Sigma_2^{\text{P}}}$ on even square-free $n$, and an exact counting reduction from $\#\text{SAT}$ to $D_n$ would collapse the polynomial hierarchy to $\Delta_3^{\text{P}}$.
\end{abstract}

\begin{keyword}
class numbers \sep binary quadratic forms \sep polynomial hierarchy \sep counting complexity \sep Tunnell's theorem \sep congruent numbers \sep Hermite normal form \sep black-box groups
\MSC[2020] 11Y40 \sep 11R29 \sep 68Q15 \sep 11E16 \sep 11E20
\end{keyword}

\end{frontmatter}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

For an integer $d \geq 3$ with $-d \equiv 0, 1 \pmod 4$, let $h(-d)$ be the number of $\text{SL}_2(\mathbb{Z})$-classes of primitive positive definite binary quadratic forms of discriminant $-d$; when $-d$ is a fundamental discriminant, $h(-d)$ is the class number of $\mathbb{Q}(\sqrt{-d})$. Computing $h(-d)$ from the binary encoding of $d$ is a classical problem of computational number theory. Shanks's baby-step giant-step method and its refinements compute it in time exponential in $\log d$ \cite{cohen1993course}; under the generalized Riemann hypothesis (GRH), Hafner and McCurley gave a subexponential algorithm \cite{hafner1989rigorous}; and under GRH the class group is generated by forms of norm $O(\log^2 d)$ \cite{bach1990explicit}, so that Watrous's quantum algorithm for the order of a solvable black-box group \cite{watrous2001quantum} computes $h(-d)$ in quantum polynomial time.

The form class group $\text{Cl}(-d)$ is an abelian group whose elements have unique polynomial-size encodings, the reduced forms, and whose operation is computable in polynomial time. For black-box groups given by a list of generators, Babai and Szemer\'{e}di \cite{babai1984complexity} proved that membership lies in NP, and Babai \cite{babai1992bounded} proved that order verification lies in $\text{AM} \cap \text{coAM}$. These results take a generating set as part of the input. No small generating set of $\text{Cl}(-d)$ is known to be computable without GRH.

In this paper we prove that $d \mapsto h(-d)$ is computable in deterministic polynomial time with an oracle for a language in $\Sigma_2^{\text{P}}$ (Theorem \ref{thm:classnumber_sigma2}). The proof is elementary: it uses only reduction theory of binary quadratic forms, Lagrange's theorem, and Hermite normal forms of integer matrices. It does not assume GRH, does not take a generating set as input, and uses no interactive proofs or randomness. Its consequences are the following.

\begin{enumerate}
\item If $\text{P} = \text{NP}$, then class numbers of imaginary quadratic orders are computable in deterministic polynomial time (Corollary \ref{cor:pnp}).
\item Let $D_n$ be the number of representations of $n$ by the ternary form $8x^2 + 2y^2 + 16z^2$ that appears in Tunnell's congruent number criterion \cite{tunnell1983}. For square-free $n \equiv 2 \pmod 8$ one has $D_n = 2h(-4n)$ (Proposition \ref{prop:classnumber}), and $D_n = 0$ for square-free $n \equiv 6 \pmod 8$ (Lemma \ref{lem:local_vanishing}). Hence $n \mapsto D_n$ on even square-free $n$ lies in $\text{FP}^{\Sigma_2^{\text{P}}}$ (Corollary \ref{cor:tunnellcount}).
\item An exact counting reduction from $\#\text{SAT}$ to $D_n$, computable in polynomial time with an NP oracle, would imply $\#\text{P} \subseteq \text{FP}^{\Sigma_2^{\text{P}}}$ and, by Toda's theorem \cite{toda1991pp}, the collapse of the polynomial hierarchy to $\Delta_3^{\text{P}}$ (Theorem \ref{thm:nogo}). Thus, unless the polynomial hierarchy collapses, Tunnell's count $D_n$ cannot carry $\#\text{P}$-hardness, although it is a $\#\text{P}$ function of $n$.
\end{enumerate}

Section \ref{sec:prelim} fixes notation. Section \ref{sec:main} proves the main theorem and its first consequences. Section \ref{sec:tunnell} applies it to Tunnell's count. Section \ref{sec:related} relates the results to prior work, and Section \ref{sec:conclusion} concludes.

\section{Preliminaries}\label{sec:prelim}

For an integer $m$ we write $|m|$ for its bit length. $\Sigma_2^{\text{P}} = \text{NP}^{\text{NP}}$ and $\Delta_3^{\text{P}} = \text{P}^{\Sigma_2^{\text{P}}}$ are levels of the polynomial hierarchy PH; for a class $\mathcal{C}$ of languages, $\text{FP}^{\mathcal{C}}$ is the class of functions computable in deterministic polynomial time with an oracle for a language in $\mathcal{C}$. If $\text{P} = \text{NP}$, then $\text{PH} = \text{P}$, so $\text{FP}^{\text{NP}} = \text{FP}^{\Sigma_2^{\text{P}}} = \text{FP}$. A function $f: \{0,1\}^* \to \mathbb{N}$ is in $\#\text{P}$ if $f(x)$ is the number of strings $y$ of length $p(|x|)$ accepted by a polynomial-time verifier $V(x,y)$, for some polynomial $p$ \cite{valiant1979complexity,valiant1979enumeration}; $\#\text{SAT}$, the number of satisfying assignments $\#\varphi$ of a Boolean formula $\varphi$, is $\#\text{P}$-complete under parsimonious reductions \cite{arora2009computational}.

$H(d)$ denotes the Hurwitz class number, which counts all, not necessarily primitive, classes of positive definite binary forms of discriminant $-d$, weighted by $1/2$ and $1/3$ for classes of forms equivalent to multiples of $x^2 + y^2$ and $x^2 + xy + y^2$ respectively, and which is zero unless $-d \equiv 0, 1 \pmod 4$ \cite{bringmann2022class}. For a fundamental discriminant $-d < -4$ one has $H(d) = h(-d)$.

\section{Class Numbers in the Polynomial Hierarchy}\label{sec:main}

We use the standard facts \cite[Section 5.4]{cohen1993course} that every class of primitive positive definite forms of discriminant $-d$ contains exactly one reduced form $(a,b,c)$, with $|b| \leq a \leq c$, $b \geq 0$ if $|b| = a$ or $a = c$, and $a \leq \sqrt{d/3}$; that reduced forms have encoding length $O(\log d)$; and that composition followed by reduction, the group operation of the form class group $\text{Cl}(-d)$, is computable in time polynomial in $\log d$. Consequently $\prod_i f_i^{v_i}$ can be computed by repeated squaring in time polynomial in $\log d$ and in the bit lengths of the exponents. We also use the crude bound
\begin{equation}\label{eq:hbound}
h(-d) \;\leq\; \#\{(a,b) : 1 \leq a \leq \sqrt{d/3},\ |b| \leq a\} \;\leq\; \tfrac{d}{3} + 2\sqrt{d/3} \;\leq\; d \qquad (d \geq 3),
\end{equation}
and the polynomial-time computability of Hermite normal forms of integer matrices \cite{kannan1979polynomial}.

\begin{Theorem}[Class numbers in $\text{FP}^{\Sigma_2^{\text{P}}}$]\label{thm:classnumber_sigma2}
The function $d \mapsto h(-d)$, defined for $d \geq 3$ with $-d \equiv 0,1 \pmod 4$, lies in $\text{FP}^{\Sigma_2^{\text{P}}}$. In particular, if $\text{P} = \text{NP}$, then $d \mapsto h(-d)$ is computable in deterministic polynomial time.
\end{Theorem}

\begin{proof}
Let $G = \text{Cl}(-d)$, write $1_G$ for the class of the principal form, and put $h = |G| \leq d$ by \eqref{eq:hbound}. If $h = 1$ the procedure below terminates immediately with the empty generating set and outputs $1$.

\emph{Step 1: a small generating set.} For a list $S = (s_1, \ldots, s_t)$ of reduced forms, every element of $\langle S \rangle$ has the form $\prod_i s_i^{v_i}$ with $0 \leq v_i < h \leq d$. Hence the language
\[
L_1 = \bigl\{(d, S, w) : \exists f \text{ reduced, with prefix } w,\ \forall v \in \{0, \ldots, d\}^t : \textstyle\prod_i s_i^{v_i} \neq f \bigr\}
\]
is in $\Sigma_2^{\text{P}}$, because $t$ never exceeds $\log_2 d + 1$ and all quantified objects have polynomial length. Starting from $S = ()$, we use $L_1$ with prefix search to find a reduced form $f \notin \langle S \rangle$, append it to $S$, and repeat until no such $f$ exists. Each step at least doubles $|\langle S \rangle|$ by Lagrange's theorem, so the loop stops after $t \leq \log_2 h \leq \log_2 d$ steps with $\langle S \rangle = G$.

\emph{Step 2: the relation lattice.} Let $\varphi: \mathbb{Z}^t \to G$, $\varphi(v) = \prod_i s_i^{v_i}$, and $\Lambda = \ker \varphi$. Since $\varphi$ is surjective, $[\mathbb{Z}^t : \Lambda] = h$, and $h\mathbb{Z}^t \subseteq \Lambda$. The Hermite normal form basis of $\Lambda$ is triangular with positive diagonal entries whose product is $h$ and with off-diagonal entries bounded by the diagonal ones; hence all its entries lie in $[0, h] \subseteq [0, d]$.

\emph{Step 3: lattice completion.} For a finite list $B$ of integer vectors, membership in the lattice $\mathcal{L}(B)$ spanned by $B$ is decidable in polynomial time via Hermite normal forms \cite{kannan1979polynomial}. Hence
\[
L_2 = \bigl\{(d, S, B, w) : \exists v \in [-d, d]^t \text{ with prefix } w,\ \varphi(v) = 1_G,\ v \notin \mathcal{L}(B) \bigr\}
\]
is in NP. Starting from $B = ()$, we use $L_2$ with prefix search to find such $v$, append it to $B$, and repeat until none exists. Each appended vector strictly enlarges $\mathcal{L}(B) \subseteq \Lambda$. At most $t$ additions increase the rank. Between two rank increases, while $\mathcal{L}(B)$ has rank $r$ and spans the rational subspace $V$, the index $[\Lambda \cap V : \mathcal{L}(B)]$ is a positive integer bounded by the determinant of $\mathcal{L}(B)$, which is at most $(d\sqrt{t})^r$ by Hadamard's inequality applied to $r$ independent vectors of $B$; each addition that does not increase the rank replaces this index by a proper divisor. Hence the loop stops after at most $t + t^2\log_2(d\sqrt{t}) = O(\log^3 d)$ additions. Full rank is reached because the vectors $h e_i \in \Lambda \cap [-d,d]^t$ are available to the search. When the loop stops, every vector of $\Lambda \cap [-d,d]^t$, in particular every vector of the Hermite normal form basis of $\Lambda$, lies in $\mathcal{L}(B)$, so $\mathcal{L}(B) = \Lambda$. We output $|\det H|$, where $H$ is the Hermite normal form basis of $\mathcal{L}(B)$; this equals $[\mathbb{Z}^t : \Lambda] = h$.

All steps run in time polynomial in $\log d$ with queries to $L_1 \in \Sigma_2^{\text{P}}$ and $L_2 \in \text{NP} \subseteq \Sigma_2^{\text{P}}$. Under $\text{P} = \text{NP}$ both languages are in P.
\end{proof}

\begin{Corollary}[Class numbers under P = NP]\label{cor:pnp}
If $\text{P} = \text{NP}$, then $d \mapsto h(-d)$ is computable in deterministic polynomial time; in particular, the class number of every imaginary quadratic field $\mathbb{Q}(\sqrt{-d})$ is computable in time polynomial in $\log d$.
\end{Corollary}

\begin{proof}
Under $\text{P} = \text{NP}$, $\Sigma_2^{\text{P}} = \text{P}$, and Theorem \ref{thm:classnumber_sigma2} applies.
\end{proof}

\begin{Remark}[The oracle queries]\label{rem:queries}
Step 1 of the proof makes $O(\log^2 d)$ queries to the $\Sigma_2^{\text{P}}$ language $L_1$, and Step 3 makes $O(\log^5 d)$ queries to the NP language $L_2$, since each of its $O(\log^3 d)$ prefix searches determines a vector of $O(\log^2 d)$ bits. The only $\Sigma_2^{\text{P}}$ queries are those that certify that a list of reduced forms generates $\text{Cl}(-d)$. Given a generating set of $O(\log d)$ forms, for instance the one provided under GRH by \cite{bach1990explicit}, Steps 2 and 3 alone compute $h(-d)$ in $\text{FP}^{\text{NP}}$.
\end{Remark}

\section{Application to Tunnell's Count}\label{sec:tunnell}

For a positive integer $n$ let
\[
C_n = \#\{(x,y,z) \in \mathbb{Z}^3 : n = 8x^2 + 2y^2 + 64z^2\}, \qquad D_n = \#\{(x,y,z) \in \mathbb{Z}^3 : n = 8x^2 + 2y^2 + 16z^2\}.
\]
Tunnell \cite{tunnell1983} proved that if an even square-free $n$ is congruent, then $2C_n = D_n$, and that the converse holds if the Birch--Swinnerton-Dyer conjecture holds for the curve $y^2 = x^3 - n^2x$. Both counts are $\#\text{P}$ functions of $n$: a witness is a triple $(x,y,z)$ of bit length $O(|n|)$, checked in polynomial time. Let $\mathcal{N} = \{n \in \mathbb{N} : n \text{ square-free},\ n \equiv 2 \pmod 8\}$.

\begin{Lemma}[Local vanishing]\label{lem:local_vanishing}
Let $n$ be an even square-free positive integer. If $n \equiv 6 \pmod 8$, then $C_n = D_n = 0$; in particular Tunnell's identity $2C_n = D_n$ holds trivially.
\end{Lemma}

\begin{proof}
Write $n = 2m$ with $m$ odd; $n \equiv 6 \pmod 8$ means $m \equiv 3 \pmod 4$. A representation $n = 8x^2 + 2y^2 + 16z^2$ gives $m = 4x^2 + y^2 + 8z^2 \equiv y^2 \pmod 4$, while $y^2 \equiv 0$ or $1 \pmod 4$, a contradiction. The same argument applies to $m = 4x^2 + y^2 + 32z^2$.
\end{proof}

\begin{Proposition}[Class-number formula]\label{prop:classnumber}
For every $n \in \mathcal{N}$,
\[
D_n = 2h(-4n),
\]
where $h(-4n)$ is the class number of $\mathbb{Q}(\sqrt{-n})$. Consequently $D_n > 0$, $D_n = O(\sqrt{n}\log n)$, and for $n \in \mathcal{N}$ Tunnell's identity $2C_n = D_n$ is equivalent to $C_n = h(-4n)$.
\end{Proposition}

\begin{proof}
Write $n = 2m$, so $m \equiv 1 \pmod 4$ is odd and square-free. Dividing $n = 8x^2 + 2y^2 + 16z^2$ by $2$ shows that $D_n = r_{(1,4,8)}(m)$, the number of representations of $m$ by $Q(y,x,z) = y^2 + 4x^2 + 8z^2$. The form $X^2 + 4Y^2 + 8Z^2$ has class number one (its genus consists of a single class), and for such forms the Siegel--Weil average collapses to the representation number itself; on this basis Bringmann and Kane proved \cite[Lemma 4.2]{bringmann2022class} that, for every $m \geq 1$,
\[
r_{(1,4,8)}(m) = c_{(1,4,8)}(m)\bigl(H(8m) - 2H(2m)\bigr),
\]
with the constant $c_{(1,4,8)}(m)$ tabulated in \cite[Appendix B]{bringmann2022class}: it equals $2$ for $m \equiv 1 \pmod 4$, $4$ for $m \equiv 4 \pmod 8$, $12$ for $m \equiv 0 \pmod 8$, and $0$ in the remaining classes. The proof in \cite{bringmann2022class} is unconditional: both sides are modular forms of weight $3/2$ on an explicit congruence subgroup, and the identity is verified on the number of coefficients prescribed by the valence formula. For our $m \equiv 1 \pmod 4$ we obtain $r_{(1,4,8)}(m) = 2(H(8m) - 2H(2m))$. Since $m$ is odd, $-2m \equiv 2 \pmod 4$ is not a discriminant, so $H(2m) = 0$. Since $m$ is odd and square-free, $-8m = -4n$ is a fundamental discriminant, and it is smaller than $-4$, so $H(8m) = h(-4n)$. Hence $D_n = 2h(-4n)$. Dirichlet's class number formula $h(-4n) = \pi^{-1}\sqrt{4n}\,L(1,\chi_{-4n})$ and the elementary bound $L(1,\chi_{-4n}) = O(\log n)$ give $D_n = O(\sqrt{n}\log n)$, and $h(-4n) \geq 1$ gives $D_n > 0$. The last assertion is immediate.
\end{proof}

\begin{Corollary}[Complexity of Tunnell's count]\label{cor:tunnellcount}
The function $n \mapsto D_n$ on even square-free $n$ lies in $\text{FP}^{\Sigma_2^{\text{P}}}$. If $\text{P} = \text{NP}$, it is computable in deterministic polynomial time.
\end{Corollary}

\begin{proof}
An even square-free $n$ satisfies $n \equiv 2$ or $6 \pmod 8$, and square-freeness and $n \bmod 8$ are decidable in $\text{FP}^{\text{NP}}$, since integer factorization is: the predicate ``$m$ has a divisor in $[2, k]$'' is in $\text{NP} \cap \text{coNP}$, and prime factors are found by binary search. If $n \equiv 6 \pmod 8$ output $0$ (Lemma \ref{lem:local_vanishing}); if $n \equiv 2 \pmod 8$ output $2h(-4n)$ (Proposition \ref{prop:classnumber}), computed by Theorem \ref{thm:classnumber_sigma2}.
\end{proof}

\begin{Theorem}[No exact counting reduction to $D_n$]\label{thm:nogo}
Suppose there are functions $R$, $\alpha$, $\beta$, computable in polynomial time with an NP oracle, such that for every Boolean formula $\varphi$, $R(\varphi)$ is an even square-free integer, $\alpha(\varphi) \geq 1$ and $\beta(\varphi)$ are integers, and $D_{R(\varphi)} = \alpha(\varphi)\,\#\varphi + \beta(\varphi)$. Then $\#\text{P} \subseteq \text{FP}^{\Sigma_2^{\text{P}}}$ and $\text{PH} = \Delta_3^{\text{P}}$.
\end{Theorem}

\begin{proof}
On input $\varphi$, compute $n = R(\varphi)$, $\alpha(\varphi)$ and $\beta(\varphi)$ with the NP oracle, compute $D_n$ by Corollary \ref{cor:tunnellcount}, and output $(D_n - \beta(\varphi))/\alpha(\varphi) = \#\varphi$. Every oracle used is in $\Sigma_2^{\text{P}}$, so $\#\text{SAT} \in \text{FP}^{\Sigma_2^{\text{P}}}$. Every $f \in \#\text{P}$ reduces parsimoniously to $\#\text{SAT}$, so $\#\text{P} \subseteq \text{FP}^{\Sigma_2^{\text{P}}}$, and hence $\text{P}^{\#\text{P}} \subseteq \text{P}^{\Sigma_2^{\text{P}}} = \Delta_3^{\text{P}}$. By Toda's theorem \cite{toda1991pp}, $\text{PH} \subseteq \text{P}^{\#\text{P}} \subseteq \Delta_3^{\text{P}} \subseteq \text{PH}$.
\end{proof}

\begin{Corollary}[Quantum computation of Tunnell's count]\label{cor:quantum}
Assume GRH. Then $n \mapsto D_n$ on even square-free $n$ is computable with bounded error in quantum polynomial time.
\end{Corollary}

\begin{proof}
Under GRH, $\text{Cl}(-d)$ is generated by the classes of prime forms of norm less than $6\log^2 d$ \cite{bach1990explicit}, which can be listed in polynomial time. Reduced forms give a unique encoding of group elements and the group operation is polynomial-time, so Watrous's quantum algorithm for the order of a solvable black-box group \cite{watrous2001quantum} computes $h(-d)$ with bounded error in polynomial time. Square-freeness and $n \bmod 8$ are decided with Shor's factoring algorithm \cite{shor1997polynomial}, and Lemma \ref{lem:local_vanishing} and Proposition \ref{prop:classnumber} give $D_n$.
\end{proof}

The identity of Proposition \ref{prop:classnumber} has also been confirmed by exhaustive computation for all $n \in \mathcal{N}$ with $n \leq 3 \cdot 10^4$ and for $1500$ random $n \in \mathcal{N}$ with $n \leq 2 \cdot 10^5$, in exact integer arithmetic by enumeration of representations and of reduced binary quadratic forms; for every square-free $n \equiv 6 \pmod 8$ with $n \leq 2 \cdot 10^5$ ($20267$ integers), $D_n = 0$.

\section{Relationship to Prior Work}\label{sec:related}

The theory of black-box groups gives complexity bounds for problems on finite groups whose elements have unique encodings and whose operations are computable in polynomial time, when a generating set is part of the input: membership is in NP \cite{babai1984complexity}, and order verification is in $\text{AM} \cap \text{coAM}$ \cite{babai1992bounded}. Theorem \ref{thm:classnumber_sigma2} concerns the class group of a single discriminant, given only $d$; Step 1 of its proof finds a generating set of $O(\log d)$ forms with a $\Sigma_2^{\text{P}}$ oracle, and Steps 2 and 3 compute the order of the group they generate with an NP oracle, deterministically. Under GRH, a generating set of polynomial size is available directly \cite{bach1990explicit}, and the order can be computed in subexponential classical time \cite{hafner1989rigorous} or in quantum polynomial time \cite{watrous2001quantum}. Tunnell's criterion has been studied computationally on a large scale \cite{hart2010congruent}. The class-number formula for $D_n$ is an instance of the theory of ternary forms with one class in their genus \cite{bringmann2022class}.

\section{Conclusion}\label{sec:conclusion}

The class number $h(-d)$ of every imaginary quadratic order is computable in $\text{FP}^{\Sigma_2^{\text{P}}}$, without GRH and without a given generating set, and hence in polynomial time if $\text{P} = \text{NP}$. For square-free $n \equiv 2 \pmod 8$, Tunnell's count $D_n$ equals $2h(-4n)$, so it lies in $\text{FP}^{\Sigma_2^{\text{P}}}$ on all even square-free $n$, and an exact counting reduction from $\#\text{SAT}$ to $D_n$ would collapse the polynomial hierarchy to $\Delta_3^{\text{P}}$. Two questions remain open: whether $h(-d)$ is computable in $\text{FP}^{\text{NP}}$ without GRH, which by Remark \ref{rem:queries} reduces to certifying a generating set of $\text{Cl}(-d)$ with an NP oracle; and whether the other Tunnell count $C_n$, which differs from $h(-4n)$ by a coefficient of a weight-$3/2$ cusp form, lies in the polynomial hierarchy.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Acknowledgements}

The author would like to thank Iris, Marilin, Sonia, Yoselin, and Arelis for their support.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Statements and Declarations}

\subsection*{Declaration of interests}

The author declares no competing interests.

\subsection*{Funding sources}

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

\subsection*{Declaration of generative AI in scientific writing}

The author designed the results of this article, and used Claude Opus 5.5 to improve the readability of this manuscript; the author ran all the computations. After using this tool, the author reviewed and edited the content as needed and takes full responsibility for the content of the publication.

\subsection*{Data availability}

All numerical data used in this article are reported in Section~\ref{sec:tunnell}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{elsarticle-num}
\bibliography{biblio}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}