HEXAGONbeta

Class Numbers of Imaginary Quadratic Orders in the Polynomial Hierarchy

Primarily AI-generated textHuman understanding: all partscs.CC — Computational Complexitymath.NT — Number Theory

Contributed by Frank Vega ↗

Version 1 / Nov 04, 2026 / CC BY 4.0

Abstract

For d≥3d \geq 3 with −d≡0,1(mod4)-d \equiv 0, 1 \pmod 4, let h(−d)h(-d) be the number of classes of primitive positive definite binary quadratic forms of discriminant −d-d. We prove that d↦h(−d)d \mapsto h(-d) is computable in deterministic polynomial time with an oracle for a language in the second level Σ2P\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 Σ2P\Sigma_2^{\text{P}} oracle finds a generating set of O(log⁡d)O(\log d) forms, and an NP oracle then determines the lattice of relations, whose index is h(−d)h(-d). Consequently, if P=NP\text{P} = \text{NP}, class numbers of imaginary quadratic fields are computable in polynomial time. As an application, the number DnD_n of representations of nn by the ternary form 8x2+2y2+16z28x^2 + 2y^2 + 16z^2 in Tunnell's congruent number criterion equals 2h(−4n)2h(-4n) for square-free n≡2(mod8)n \equiv 2 \pmod 8 and vanishes for square-free n≡6(mod8)n \equiv 6 \pmod 8; hence DnD_n lies in FPΣ2P\text{FP}^{\Sigma_2^{\text{P}}} on even square-free nn, and an exact counting reduction from #SAT\#\text{SAT} to DnD_n would collapse the polynomial hierarchy to Δ3P\Delta_3^{\text{P}}.

Provenance statement

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.

Tools used

Anthropic
Claude OpusVersion 5.5

References

  1. Henri Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, vol. 138. 1993DOI
  2. James L. Hafner; Kevin S. McCurley. A rigorous subexponential algorithm for computation of class groups. Journal of the American Mathematical Society, vol. 2, no. 4, pp. 837–850. 1989DOI
  3. Eric Bach. Explicit bounds for primality testing and related problems. Mathematics of Computation, vol. 55, no. 191, pp. 355–380. 1990DOI
  4. John Watrous. Quantum algorithms for solvable groups. Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 60–67. 2001DOI
  5. László Babai; Endre Szemerédi. On the complexity of matrix group problems I. 25th Annual Symposium on Foundations of Computer Science, pp. 229–240. 1984DOI
  6. László Babai. Bounded round interactive proofs in finite groups. SIAM Journal on Discrete Mathematics, vol. 5, no. 1, pp. 88–111. 1992DOI
  7. Jerrold Bruce Tunnell. A classical Diophantine problem and modular forms of weight 3/23/2. Inventiones Mathematicae, vol. 72, no. 2, pp. 323–334. 1983DOI
  8. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, vol. 20, no. 5, pp. 865–877. 1991DOI
  9. Leslie Gabriel Valiant. The complexity of computing the permanent. Theoretical Computer Science, vol. 8, no. 2, pp. 189–201. 1979DOI
  10. Leslie Gabriel Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, vol. 8, no. 3, pp. 410–421. 1979DOI
Show all 15 referencesShow fewer references
  1. Sanjeev Arora; Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press. 2009DOI
  2. Kathrin Bringmann; Ben Kane. Class numbers and representations by ternary quadratic forms with congruence conditions. Mathematics of Computation, vol. 91, no. 333, pp. 295–329. 2022DOI
  3. Ravindran Kannan; Achim Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM Journal on Computing, vol. 8, no. 4, pp. 499–507. 1979DOI
  4. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, vol. 26, no. 5, pp. 1484–1509. 1997DOI
  5. William B. Hart; Gonzalo Tornaría; Mark Watkins. Congruent number theta coefficients to 101210^{12}. Algorithmic Number Theory (ANTS-IX), vol. 6197, pp. 186–200. 2010DOI

Version history

  1. v1Submitted by Frank VegaInitial depositCurrentNov 04, 2026