WorksMathematics
3-manifold decision problems and Riemann hypotheses
Abstract
Beginning with Kuperberg's work on unknot recognition, several fundamental decision problems in 3-manifold topology have been shown to be in coNP assuming the generalized Riemann hypothesis. In this note, we explain how recent developments around the quasi-Riemann hypothesis yield unconditional versions of these results, leading for example to the first unconditional proof that 3-sphere recognition is in coNP.
Introduction
A decision problem lies in the complexity class NP if given an input for which the answer is yes, there exists a certificate of this fact whose length and verification time are polynomial in the size of the input; it lies in coNP if instead there exists such a certificate when the answer is no. Several fundamental questions in 3-manifold topology are known to lie in NP. These include unknot recognition [7], torus knot recognition [1], satellite knot recognition [5], recognition of any fixed knot [14], and 3-sphere recognition [8, 19], among others.
In [12], Kuperberg gave a beautiful proof that unknot recognition is also in coNP, assuming the generalized Riemann hypothesis (GRH). His certificate of knottedness relies on a deep gauge-theoretic result of Kronheimer and Mrowka [9], which asserts that if a knot is not the unknot, then there exists a representation
with nonabelian image. Using work of Koiran [11], he deduced that there is a nonabelian representation
for some prime , and that by work of Lagarias–Odlyzko [15], GRH allows us to take with at most polynomially many digits in the number of crossings in any planar diagram for (or the number of tetrahedra in any triangulation of ). The certificate of knottedness then consists of matrices , where ranges over generators in a presentation of coming from the input.
The same ideas have been used in combination with additional results from gauge theory [10 Zen18] on a variety of decision problems, which we summarize here.
Theorem 1.1. The following problems are in coNP, assuming GRH:
The input can be either a planar knot diagram in cases (1) and (3), or a triangulation in cases (1), (2), and (4).
In each case, GRH is used to ensure that the certificate has polynomial length in the input, but once we know that a certificate of this length exists, the fact that it can be verified in polynomial time is unconditionally true. (Haraway and Hoffman did not state case (4) in terms of GRH, but they proved that hyperbolicity is in coNP if 3-sphere recognition is.) Several of these problems have since been proved to be in coNP unconditionally by different means, as detailed in Remark 1.4 below, but the proofs relying on GRH are still interesting because the corresponding certificates are arguably much simpler.
While writing our paper [1], we made the unfortunate decision to treat the number-theoretic input as a black box, taking “GRH” as something mysterious but mostly harmless. This is fairly common practice (many of us use “ZFC” in the same way) but not exactly a sign of understanding on our part—for example, it would have been good to know if partial progress toward GRH might actually make the above theorems unconditional, as explicitly suggested in the introduction to [12]. The purpose of this note is to atone for our sins by seeing what exactly we might need from GRH to prove these theorems unconditionally. We do not claim any novelty in our arguments, but we have spelled them out explicitly so that topologists might see how this circle of ideas can be applied.
Our starting point is the following explicit claim, called the quasi-Riemann hypothesis for Dedekind zeta functions. (The earliest reference we could find for this name is [21], but the conjecture itself goes back at least to Hardy and Littlewood [HL23, Hypothesis R].) By way of notation, we write for the ring of integers in a number field , and denotes the norm of an ideal .
Hypothesis 1.2. There is a universal constant such that for every number field , the Dedekind zeta function
has no zeroes with .
The purpose of this note is to explain how the arguments of [12] can also be used to prove the following.
Theorem 1.3. Each of the decision problems in Theorem 1.1 is in coNP, modulo Hypothesis 1.2.
The results of Theorem 1.1 all rely on the existence of a suitably small prime , which Koiran [11] finds (assuming GRH) by appealing to Lagarias and Odlyzko’s effective version of the Chebotarev density theorem [15]. Here the term “effective” means that it describes not only the asymptotic growth of some quantity but also a bound on the error term. Frei, Sofos, and Widmer [3] have recently shown that Hypothesis 1.2 implies an effective version whose error bounds are weaker than the ones implied by GRH (see § 3 for details), but these turn out to be sharp enough to prove the existence of our sought-after prime . This existence is established in Theorem 2.1, which can be used verbatim in place of [12 Theorem 3.2] to prove Theorem 1.3.
Cureton and Thorner [4] have recently communicated a Lean-formalized proof of Hypothesis 1.2 with , building on the formalized proof announced by OpenAI
[17, 18] of the quasi-Riemann hypothesis for Dirichlet -functions. This implies via Theorem 1.3 that the results of Theorem 1.1 no longer rely on any open conjectures: the named decision problems are unconditionally in coNP. However, at the time of writing it is not clear to us that any human has understood the proof given in [4], so following the lead of [3] we will continue to describe these results as being conditional on Hypothesis 1.2.
Remark 1.4. Table 1 summarizes what is known about each of the recognition problems of Theorem 1.1. In the NP column, Baroni and Lackenby have announced forthcoming work proving that hyperbolic knot recognition is in NP. For the unconditionally coNP column, some of these were already known by different methods: this includes unknot recognition, as proved by Lackenby [13], and also by Agol in unpublished work from around 2002; and hyperbolic knot recognition, by Haraway and Hoffman [5 Theorem 2]. As far as we are aware, however, there are no other known strategies in the literature for 3-sphere recognition or hyperbolicity of cusped 3-manifolds.
| Problem | NP | coNP mod GRH | coNP |
| Unknot recognition | [7] | [12] | [13] |
| Torus knot recognition | [1] | [1] | Theorem 1.3 |
| Hyperbolic knot recognition | (forthcoming) | [1] | [5] |
| Hyperbolicity of cusped 3-manifolds | ? | [Zen18]+[HH19] | Theorem 1.3 |
| 3-sphere recognition | [8, 19] | [Zen18] | Theorem 1.3 |
Table 1. References for the complexity of various 3-manifold decision problems. The results attributed to Theorem 1.3 assume only Hypothesis 1.2, a proof of which was claimed in [4].
Remark 1.5. Hypothesis 1.2 also implies nontrivial bounds on the least size of nonabelian finite quotients of many knot and 3-manifold groups, exactly as in [12 Theorem 5.1]. See Theorem 2.3 for a precise statement.
AI statement
No generative AI was used at any point in the writing of this note.
IA statement
As we were writing this note, Ian Agol informed us that he was also aware that Hypothesis 1.2 suffices to prove an unconditional version of Theorem 1.1.
Acknowledgments
JAB was supported by NSF Grant DMS-2506250 and a Simons Fellowship. SS was supported by the Engineering and Physical Sciences Research Council [grant number UKRI1016]. No data were created or analyzed in this work.
Background
The results of Theorem 1.1 all rely on the same technique. Given a decision problem, we construct a group with a modestly-sized presentation—this could be a knot group , or a 3-manifold group —and then the representation variety
is a complex affine algebraic set that can be described by a controlled number of variables and relations. If we want to find a representation with non-abelian image, this can be achieved at minimal extra cost by the Rabinowitsch trick: given polynomials in the input variables, we can impose the condition by adding extra variables and the equation . Applying this trick to the entries of as range over pairs of generators of , we thus get a system of polynomial equations with integral coefficients
with the properties that
the integers , and the coefficients of the are all bounded in terms of the input;
and the system has a solution if and only if the desired representation exists.
If this system has a solution, then Kuperberg [12 Theorem 3.1] asserts that by work of Koiran [11 Theorems 4 and 7], there is an explicit solution in terms of a root of a single irreducible polynomial
whose degree and coefficients are suitably bounded by , , and the degrees and coefficients of the . In particular, if has a solution modulo then so will our original system of equations, so our goal will be to find such a that is not too large. In other words, we just need to prove the following strengthening of [12 Theorem 3.2].
Theorem 2.1. Assume Hypothesis 1.2. Let be an irreducible polynomial of degree , and let denote the maximum absolute value among the coefficients of . Then there is a prime
such that has a root modulo .
We note that Theorem 2.1 will then imply the following corollaries, by exactly the same arguments as for the corresponding theorems in [12].
Theorem 2.2 (cf. [12 Theorem 3.4]). Assume Hypothesis 1.2, and let be an affine algebraic group over . Let be a discrete group with a finite presentation of length . If there is a homomorphism with nonabelian image, then there is also a homomorphism with nonabelian image for some prime with .
Theorem 2.3 (cf. [12 Theorem 5.1]). Assume Hypothesis 1.2. Let be any of the following:
a finite-volume hyperbolic -manifold,
the complement of a nontrivial knot ,
or an integer homology -sphere not homeomorphic to .
Suppose that admits a triangulation with tetrahedra. Then there is a regular nonabelian cover of degree at most .
Proof. There is a homomorphism with nonabelian image, by [2 Proposition 3.1.1], [9], or [Zen18] respectively. Since has a presentation of length , Theorem 2.2 gives a nonabelian
for some prime with . Then surjects onto the image of , which is a nonabelian group of order at most
and the regular cover of corresponding to has degree , which is less than .
Returning to Theorem 2.1, the original version stated in [12], which is attributed to Lagarias–Odlyzko [15] and Weinberger [22], assumed GRH. Our proof follows the same lines, with GRH replaced by Hypothesis 1.2, but we spell out the details much more explicitly here.
The strategy is as follows. It is hard to find an explicit choice of that works. However, many classical results in number theory describe the statistical behavior of prime numbers, such as the prime number theorem: if we define
then the number of primes less than a given is asymptotic to . This guarantees that prime numbers exist, but it doesn’t tell us how far we must search before we can be certain that we will find one. (This is strictly for motivation; we do actually know that are prime.) In order to get effective bounds, we need to estimate the size of the error term, and the Riemann hypothesis tells us that this error should be for any .
In order to prove Theorem 2.1, then, we define a suitable counting function: given a prime , we let
and we want to know that is positive for some not-too-large value of . Equivalently, we want to find some relatively small such that the sum
is strictly positive. If we count roots of mod with multiplicity, then we can think of as actually counting the number of linear factors in the prime factorization of , where is viewed as an element of . (We mostly don’t have to worry about multiplicity: if does not divide the discriminant , then has no repeated factors mod .) We are thus led to the following classical theorem of Dedekind and Kummer.
Theorem 2.4 ([Neu99, Proposition I.8.3]). Let be monic and irreducible. Let be a root of , and let . If does not divide the index , and the mod reduction of has irreducible factorization
then the ideal has prime factorization
where each is a lift of . Each prime has norm .
See also [20 Theorem 8.2] for a slightly more general version.
Theorem 2.4 tells us that for a given monic, irreducible , if we set , then the sum is closely related to the count
of prime ideals of norm not exceeding , and more precisely to the count of those ideals whose norm is a rational prime. We must therefore try to estimate the count (2.1), and then also bound the smaller count of prime ideals whose norms are prime powers for some .
The effective Chebotarev density theorem
In this section we explain the input needed from [3] to prove Theorem 2.1. Strictly speaking, we will only need Corollary 3.3, which is easier to state than the prerequisites that we are about to explain. We encourage the topologists reading this to stick with us and learn about the Chebotarev density theorem anyway, rather than skipping ahead.
Let be a number field, and let be a normal extension of with Galois group
A prime ideal is said to be unramified in if the ideal has prime factorization
without any repeated factors. Then for each ideal , there is a uniquely defined Frobenius automorphism
fixing setwise and satisfying for all . In general depends on our choice of prime lying over , but only up to conjugacy. We use the Artin symbol to denote this conjugacy class in .
Following the notation of Lagarias and Odlyzko [15], we set
The Chebotarev density theorem says that for any conjugacy class in , we have the asymptotic relation
as . The classical version of this theorem says nothing about the error terms, but Lagarias and Odlyzko’s effective Chebotarev density theorem [15 Theorem 1.1] bounds the error from above under the assumption of GRH. Frei, Sofos, and Widmer [3] have shown that the proof applies equally well under the assumption of Hypothesis 1.2:
Theorem 3.1 ([3 Theorem 1.1]). Assume Hypothesis 1.2. There exists a universal constant such that for every , if is a normal extension of the number field with Galois group , then we have
Remark 3.2. The theorem stated in [15] corresponds to the case .
Theorem 3.1 quickly implies an effective version of Landau’s prime ideal theorem, which is what we will actually need to prove Theorem 2.1.
Corollary 3.3. Assume Hypothesis 1.2. Then there exists a universal constant with the following property: if is an irreducible monic polynomial of degree , and , then
for every .
Proof. We take , which is trivially a normal extension of . Then is the trivial group, and we apply Theorem 3.1 to its unique conjugacy class. □
Corollary 3.3 says that the quantity (2.1), which approximates the total number of roots our monic polynomial has modulo the various primes , is at least
Thus we have two remaining goals, at least in the proof of Theorem 2.1 for monic : one is to determine how many of the prime ideals in actually correspond to roots mod , and then the other is to bound error term .
In order to understand the discriminant appearing in this error term, we apply the identity
see e.g. [20 Equation (7.7)]. Here the term denotes the absolute value of the product
where the are the roots of in .
Lemma 3.4 (cf. [12 Equation (3)]). Let be a monic polynomial of degree . The discriminant satisfies
Proof. We can evaluate as the resultant of and , which is defined as the determinant of a certain matrix , the Sylvester matrix of and . The first rows of each contain shifts of the coefficient vector of : there are at most nonzero entries, each bounded in absolute value by , so as row vectors these have length at most . Likewise, the remaining rows are all shifts of the coefficient vector of , which has at most nonzero entries bounded by , so as row vectors these have length at most . Then is at most the product of the lengths of the rows of :
The lemma follows immediately. □
Counting roots mod of monic polynomials
Let be monic and irreducible, of degree , and with some root . Letting as in Theorem 2.4, we now attempt to classify the primes of norm at most . Each such lies over some rational prime , meaning that , and then it is one of the factors in the prime factorization
Since the relative norm of an ideal is multiplicative, we have
so each is a positive power of ; there are at most factors ; and
Thus each prime ideal of norm at most lies over a prime satisfying exactly one of the following:
does not divide , and ;
does not divide , and for some ;
divides .
We consider each of these cases separately, in order to bound case (1) from below as done in the proof of [11 Corollary 1].
In case (1), we recall from (3) that cannot divide , so Theorem 2.4 says that such ideals are in bijection with the roots of mod .
In case (2) we have , so . For any fixed , the relation (4) says that there are at most such primes over , so overall this case contributes at most prime ideals to the total.
Finally, in case (3), there are at most primes dividing , and for each of these the ideal contributes at most prime factors of norm at most , so in total this case contributes at most prime ideals.
Isolating case (1) from the rest, we have shown that
Proposition 4.1. Assuming Hypothesis 1.2, there is a universal constant with the following property. Let be a monic, irreducible polynomial of degree . Then
for all .
Proof. Let be the constant provided by the effective prime ideal theorem, Corollary 3.3, so that
We can replace with , which is at least as large by (3), and combine this with (5) to conclude. □
Proof of Theorem 2.1
In our work towards proving Theorem 2.1, we have assumed until now that the polynomial is monic, but the general case quickly reduces to this one. Suppose that
where . We consider the related polynomial
which is monic and which has integer coefficients as well. Then is a root of if and only if is a root of , and this is true not just over but also over any field as long as is invertible mod . Thus if we want to find a prime such that has a root mod , it suffices to find such that has a root mod .
We now observe that , and also that
Since , the number of primes dividing is at most
and each of them has at most prime ideal factors in where . Thus in this case we can weaken the bound of Proposition 4.1 slightly, by removing all the prime ideals that divide some rational prime divisor of , to get
Applying Lemma 3.4 to the monic polynomial gives us
so collectively we have shown the following.
Proposition 5.1. Assuming Hypothesis 1.2, there is a universal polynomial with the following property. Let be an irreducible polynomial of degree , with leading coefficient . Then
for all , where the discriminant of satisfies (5.1). The polynomial depends on the constant in Hypothesis 1.2 and the resulting universal constant , but we will not make this explicit other than to note that we can certainly take .
Proof of Theorem 2.1. We wish to find , of size polynomial in and , such that the sum on the left side of (5.2) is strictly positive. Proposition 5.1 says that this will apply as long as
and if then the inequality
shows that it will further suffice to take satisfying
There is a constant such that
for all , and for all we have
as desired. □
References
Department of Mathematics, Boston College
Email address: [email protected]
Department of Mathematics, Imperial College London
Email address: [email protected]
References
- [1]J. A. Baldwin and S. Sivek. On the complexity of torus knot recognition. Trans. Amer. Math. Soc., 371(6):3831–3855, 2019. 1, 2, 3
- [2]M. Culler and P. B. Shalen. Varieties of group representations and splittings of 3-manifolds. Ann. of Math. (2), 117(1):109–146, 1983. 4DOI
- [3]C. Frei, E. Sofos, and M. Widmer. Some applications of the quasi-Riemann hypothesis to class groups and small generators of number fields. arXiv:2610.18491, 2026. 2, 3, 6, 7arxiv.org/abs/2610.18491
- [4]A quasi-Riemann hypothesis for Dedekind zeta functions. Hexagon preprint hexagon:2610.00200v2, 2026. Contributors: Dean Cureton; Jesse Thorner. 2, 3
- [5]R. Haraway and N. R. Hoffman. On the complexity of cusped non-hyperbolicity. arXiv:1907.01675, 2019. 1, 3arxiv.org/abs/1907.01675
- [7]J. Hass, J. C. Lagarias, and N. Pippenger. The computational complexity of knot and link problems. J. ACM, 46(2):185–211, 1999. 1, 3
- [8]S. V. Ivanov. The computational complexity of basic decision problems in 3-dimensional topology. Geom. Dedicata, 131:1–26, 2008. 1, 3DOI
- [9]P. B. Kronheimer and T. S. Mrowka. Dehn surgery, the fundamental group and SU(2). Math. Res. Lett., 11(5-6):741–754, 2004. 1, 4DOI
- [10]P. Kronheimer and T. Mrowka. Knots, sutures, and excision. J. Differential Geom., 84(2):301–364, 2010. 1arxiv.org/abs/0807.4891
- [11]P. Koiran. Hilbert’s Nullstellensatz is in the polynomial hierarchy, volume 12, pages 273–286. 1996. Special issue for the Foundations of Computational Mathematics Conference (Rio de Janeiro, 1997). 1, 2, 4, 8
- [12]G. Kuperberg. Knottedness is in NP, modulo GRH. Adv. Math., 256:493–506, 2014. 1, 2, 3, 4, 5, 7
- [13]M. Lackenby. The efficient certification of knottedness and Thurston norm. Adv. Math., 387:Paper No. 107796, 142, 2021. 3arxiv.org/abs/1604.00290
- [14]M. Lackenby. A polynomial upper bound on Reidemeister moves for each link type. arXiv:2602.09923, 2026. 1arxiv.org/abs/2602.09923
- [15]J. C. Lagarias and A. M. Odlyzko. Effective versions of the Chebotarev density theorem. In Algebraic number fields: L-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975), pages 409–464. Academic Press, London–New York, 1977. 1, 2, 5, 6, 7
- [17]OpenAI. The Quasi-Riemann Hypothesis. OpenAI Math Release preprint OAI:The-Quasi-Riemann-Hypothesis-October-5-2026, 2026. 3
- [18]OpenAI. The Quasi-Riemann Hypothesis: A Zero-Free Half-Plane Re(s) > 7/8. OpenAI Math Release preprint OAI:The-Quasi-Riemann-Hypothesis-September-30-2026, 2026. 3
- [19]S. Schleimer. Sphere recognition lies in NP. In Low-dimensional and symplectic topology, volume 82 of Proc. Sympos. Pure Math., pages 183–213. Amer. Math. Soc., Providence, RI, 2011. 1, 3
- [20]P. Stevenhagen. The arithmetic of number rings. In Algorithmic number theory: lattices, number fields, curves and cryptography, volume 44 of Math. Sci. Res. Inst. Publ., pages 209–266. Cambridge Univ. Press, Cambridge, 2008. 6, 7DOI
- [21]P. Turan. On Riemann’s hypothesis. Bull. Acad. Sci. URSS. Sér. Math. [Izvestia Akad. Nauk SSSR], 11:197–262, 1947. 2
- [22]P. J. Weinberger. Finding the number of factors of a polynomial. J. Algorithms, 5(2):180–186, 1984. 5DOI