HEXAGONbeta

Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence

Primarily AI-generated textHuman understanding: all partsmath.NT — Number Theorycs.CC — Computational Complexity

Contributed by Joseph Shunia ↗

Version 1 / Oct 31, 2026 / CC BY 4.0

Abstract

We give a deterministic polynomial-time primality test whose main verification is the congruence (1+X)n=1+Xn(1+X)^n=1+X^n in Cn[X]/(Xr−b(Y))C_n[X]/(X^r-b(Y)), where Cn=(Z/nZ)[Y]/(Φr(Y))C_n=(\mathbb{Z}/n\mathbb{Z})[Y]/(\Phi_r(Y)). Two identities in the coefficient ring normalize bb and ensure compatibility with the main congruence. A finite-field root count and a lattice bound show that an accepted input is a prime power; elementary preprocessing excludes nontrivial perfect powers. We construct bb deterministically using Jacobi sums and the uniform Dedekind-zeta zero-free theorem of Cureton and Thorner, which extends OpenAI's Hecke zero-free theorem. The total bit complexity is L32+o(1)L^{32+o(1)}, where L=⌈log⁡2n⌉L=\lceil\log_2 n\rceil, and verification after constructing bb costs L6+o(1)L^{6+o(1)}. More generally, for a fixed real algebraic 1/2≤θ<11/2\le\theta<1, a common zero-free boundary ℜs>θ\Re s>\theta for the relevant Dedekind zeta functions gives Lmax⁡{6,(1−θ)−1}+o(1)L^{\max\{6,(1-\theta)^{-1}\}+o(1)}. This bound reaches L6+o(1)L^{6+o(1)} at θ=5/6\theta=5/6, and hence under GRH. We state a fixed-base modification of Agrawal's conjecture for odd integers passing the base-22 Fermat test, using the modulus Xr−2X^r-2 with rr the least positive integer not dividing n(n−1)n(n-1).

Provenance statement

OpenAI's GPT-6 Astra developed and wrote the proofs, including the deterministic parameter construction and complexity analysis, through an extended mathematical dialogue with the author. The author supplied the fixed-base test, conjectural framework, research notes, and references; proposed applying OpenAI's recent analytic number-theoretic results to deterministic parameter selection; and directed the investigation of Jacobi sums, power nonresidues, composite degrees, multivariate quotient rings, and finite-field root counting.

Tools used

OpenAI
ChatGPTVersion 6

References

  1. L. M. Adleman, C. Pomerance, and R. S. Rumely, On distinguishing prime numbers from composite numbers , Annals of Mathematics 117 (1983), 173--206. Theorem 3 records the Odlyzko--Pomerance parameter construction. https://math.dartmouth.edu/~carlp/PDF/paper37.pdf.link
  2. M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P , Annals of Mathematics 160 (2004), 781--793. doi:10.4007/annals.2004.160.781 (https://doi.org/10.4007/annals.2004.160.781). Agrawal's conjecture is stated in Section 6; see also the authors' version at https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf.DOI
  3. Axiom Math, D. Cureton, and J. Thorner, Dedekind Zeta Zero-Free Region , Lean 4 formalization, October 2026. The declaration DedekindZetaZeroFree.main in Solution/DedekindZetaSolution.lean proves the Dedekind-zeta statement; the repository reports verification using only Lean's standard axioms. https://github.com/AxiomMath/DedekindZetaZeroFree.link
  4. D. J. Bernstein, Proving primality in essentially quartic random time , Mathematics of Computation 76 (2007), 389--403. doi:10.1090/S0025-5718-06-01786-8 (https://doi.org/10.1090/S0025-5718-06-01786-8). Section references are to the December 3, 2004 draft: https://cr.yp.to/papers/quartic-20041203.pdf.DOI
  5. D. J. Bernstein, N. Heninger, and T. Lange, FactHacks: Remainder tree . https://facthacks.cr.yp.to/remainder.html.link
  6. P. Berrizbeitia, Sharpening ``PRIMES is in P'' for a large family of numbers , Mathematics of Computation 74 (2005), 2043--2059. doi:10.1090/S0025-5718-05-01727-8 (https://doi.org/10.1090/S0025-5718-05-01727-8).DOI
  7. Q. Cheng, Primality proving via one round in ECPP and one iteration in AKS , preprint, 2003. https://arxiv.org/abs/math/0301179.link
  8. K. Conrad, Gauss and Jacobi sums on finite fields and Z/mZ\Z/m\Z , expository notes. https://kconrad.math.uconn.edu/blurbs/gradnumthy/Gauss-Jacobi-sums.pdf.link
  9. D. Cureton and J. Thorner, A quasi-Riemann hypothesis for Dedekind zeta functions , Hexagon preprint 2610.00200, version 2, October 12, 2026. Theorem 1.1 and Section 15. https://hexagonmath.org/2610.00200v2.hexagon
  10. H. W. Lenstra, Jr., and C. Pomerance, Primality testing with Gaussian periods , Journal of the European Mathematical Society 21 (2019), 1229--1269. doi:10.4171/JEMS/861 (https://doi.org/10.4171/JEMS/861).DOI
Show all 11 referencesShow fewer references
  1. OpenAI, Primitive roots for every admissible integer base , preprint, October 4, 2026. Theorem 1.2 and Section 9. https://github.com/openai/math/blob/main/preprints/Primitive-roots-for-every-admissible-integer-base-October-4-2026/primitive-roots-all-integer-bases.pdf.link

Version history

  1. v1Submitted by Joseph ShuniaInitial depositCurrentOct 31, 2026