betaFeedback

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 K⊂S3K \subset S^3 is not the unknot, then there exists a representation

π1(S3∖K)→SL(2,C)\pi_1(S^3 \setminus K) \to\mathrm{SL}(2,\mathbb{C})

with nonabelian image. Using work of Koiran [11], he deduced that there is a nonabelian representation

ρ:π1(S3∖K)→SL(2,Fp)\rho:\pi_1(S^3 \setminus K) \to\mathrm{SL}(2,\mathbb{F}_p)

for some prime pp, and that by work of Lagarias–Odlyzko [15], GRH allows us to take pp with at most polynomially many digits in the number of crossings in any planar diagram for KK (or the number of tetrahedra in any triangulation of S3∖KS^3 \setminus K). The certificate of knottedness then consists of matrices ρ(gi)\rho(g_i), where gig_i ranges over generators in a presentation of π1(S3∖K)\pi_1(S^3 \setminus K) 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:

  1. unknot recognition [12];

  2. 3-sphere recognition [Zen18];

  3. torus knot recognition and hyperbolic knot recognition [1];

  4. hyperbolicity of cusped 3-manifolds [5].

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 OK\mathcal{O}_K for the ring of integers in a number field KK, and NK/Q(I)=[OK:I]N_{K/\mathbb{Q}}(I) = [\mathcal{O}_K : I] denotes the norm of an ideal I⊂OKI \subset\mathcal{O}_K.

Hypothesis 1.2. There is a universal constant ϵ>0\epsilon> 0 such that for every number field KK, the Dedekind zeta function

ζK(s)=∑I⊂OK1NK/Q(I)s=∏p⊂OK prime(1−1NK/Q(p)s)−1\zeta_K(s) = \sum_{I \subset\mathcal{O}_K} \frac{1}{N_{K/\mathbb{Q}}(I)^s} = \prod_{\mathfrak{p} \subset\mathcal{O}_K\ \mathrm{prime}} \left(1 - \frac{1}{N_{K/\mathbb{Q}}(\mathfrak{p})^s}\right)^{-1}

has no zeroes with Re⁡(s)>1−ϵ\operatorname{Re}(s) > 1 - \epsilon.

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 pp, 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 pp. 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 ϵ=132\epsilon= \frac{1}{32}, building on the formalized proof announced by OpenAI

[17, 18] of the quasi-Riemann hypothesis for Dirichlet LL-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.

ProblemNPcoNP mod GRHcoNP
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 GG with a modestly-sized presentation—this could be a knot group π1(S3∖K)\pi_1(S^3 \setminus K), or a 3-manifold group π1(Y)\pi_1(Y)—and then the representation variety

Hom⁡(G,SL(2,C))\operatorname{Hom}(G,\mathrm{SL}(2,\mathbb{C}))

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 ρ\rho with non-abelian image, this can be achieved at minimal extra cost by the Rabinowitsch trick: given polynomials w1,…,wkw_1,\ldots,w_k in the input variables, we can impose the condition (w1,…,wk)≠(0,…,0)(w_1,\ldots,w_k) \ne(0,\ldots,0) by adding kk extra variables tit_i and the equation ∑itiwi=1\sum_i t_iw_i = 1. Applying this trick to the entries of ρ(gigj)−ρ(gjgi)\rho(g_i g_j)-\rho(g_j g_i) as gi,gjg_i,g_j range over pairs of generators of GG, we thus get a system of polynomial equations with integral coefficients

fi(x1,…,xn)=0,1≤i≤m,f_i(x_1,\ldots,x_n)=0,\qquad1\le i\le m,

with the properties that

  1. the integers mm, nn and the coefficients of the fif_i are all bounded in terms of the input;

  2. and the system has a solution if and only if the desired representation ρ\rho 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

f∈Z[x],f\in\mathbb{Z}[x],

whose degree and coefficients are suitably bounded by mm, nn, and the degrees and coefficients of the fif_i. In particular, if f(x)=0f(x)=0 has a solution modulo pp then so will our original system of equations, so our goal will be to find such a pp 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 f∈Z[x]f\in\mathbb{Z}[x] be an irreducible polynomial of degree d≥1d\ge1, and let ∥f∥\lVert f\rVert denote the maximum absolute value among the coefficients of ff. Then there is a prime

p=poly⁡(d,log⁡∥f∥)p=\operatorname{poly}(d,\log\lVert f\rVert)

such that ff has a root modulo pp.

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 GG be an affine algebraic group over Z\mathbb{Z}. Let Γ\Gamma be a discrete group with a finite presentation of length ℓ\ell. If there is a homomorphism Γ→G(C)\Gamma\to G(\mathbb{C}) with nonabelian image, then there is also a homomorphism Γ→G(Fp)\Gamma\to G(\mathbb{F}_p) with nonabelian image for some prime pp with log⁡(p)=poly⁡(ℓ)\log(p)=\operatorname{poly}(\ell).

Theorem 2.3 (cf. [12 Theorem 5.1]). Assume Hypothesis 1.2. Let YY be any of the following:

  1. a finite-volume hyperbolic 33-manifold,

  2. the complement of a nontrivial knot K⊂S3K\subset S^3,

  3. or an integer homology 33-sphere not homeomorphic to S3S^3.

Suppose that YY admits a triangulation with nn tetrahedra. Then there is a regular nonabelian cover Y~→Y\widetilde{Y}\to Y of degree at most epoly⁡(n)e^{\operatorname{poly}(n)}.

Proof. There is a homomorphism π1(Y)→SL⁡(2,C)\pi_1(Y)\to\operatorname{SL}(2,\mathbb{C}) with nonabelian image, by [2 Proposition 3.1.1], [9], or [Zen18] respectively. Since π1(Y)\pi_1(Y) has a presentation of length poly⁡(n)\operatorname{poly}(n), Theorem 2.2 gives a nonabelian

ρ:π1(Y)→SL⁡(2,Fp)(1)\rho:\pi_1(Y)\to\operatorname{SL}(2,\mathbb{F}_p) \tag*{(1)}

for some prime pp with log⁡(p)=poly⁡(n)\log(p)=\operatorname{poly}(n). Then π1(Y)\pi_1(Y) surjects onto the image of ρ\rho, which is a nonabelian group of order at most

∣SL⁡(2,Fp)∣=p(p2−1)<p3,|\operatorname{SL}(2,\mathbb{F}_p)|=p(p^2-1)<p^3,

and the regular cover of YY corresponding to ker⁡(ρ)\ker(\rho) has degree ∣im⁡(ρ)∣|\operatorname{im}(\rho)|, which is less than p3=(epoly⁡(n))3=epoly⁡(n)p^3=(e^{\operatorname{poly}(n)})^3=e^{\operatorname{poly}(n)}.

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 pp 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

Li⁡(x)=∫2xdtlog⁡t,\operatorname{Li}(x)=\int_2^x\frac{dt}{\log t},

then the number of primes less than a given xx is asymptotic to Li⁡(x)\operatorname{Li}(x). 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 2,3,5,7,…2,3,5,7,\ldots 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 O(x1/2+ϵ)O(x^{1/2+\epsilon}) for any ϵ>0\epsilon>0.

In order to prove Theorem 2.1, then, we define a suitable counting function: given a prime pp, we let

W(p)=#{a∈Fp∣f(a)=0},W(p)=\#\{a\in\mathbb{F}_p\mid f(a)=0\},

and we want to know that W(p)W(p) is positive for some not-too-large value of pp. Equivalently, we want to find some relatively small xx such that the sum

∑p≤xW(p)\sum_{p\leq x}W(p)

is strictly positive. If we count roots of ff mod pp with multiplicity, then we can think of W(p)W(p) as actually counting the number of linear factors in the prime factorization of ff, where ff is viewed as an element of Fp[x]\mathbb{F}_p[x]. (We mostly don’t have to worry about multiplicity: if pp does not divide the discriminant Δf\Delta_f, then ff has no repeated factors mod pp.) We are thus led to the following classical theorem of Dedekind and Kummer.

Theorem 2.4 ([Neu99, Proposition I.8.3]). Let f∈Z[x]f\in\mathbb{Z}[x] be monic and irreducible. Let θ\theta be a root of ff, and let K=Q(θ)≅Q[x]/⟨f⟩K=\mathbb{Q}(\theta)\cong\mathbb{Q}[x]/\langle f\rangle. If pp does not divide the index [OK:Z[θ]][\mathcal{O}_K:\mathbb{Z}[\theta]], and the mod pp reduction fˉ∈Fp[x]\bar{f}\in\mathbb{F}_p[x] of ff has irreducible factorization

fˉ=fˉ1e1⋯fˉkek,fˉi∈Fp[x],\bar{f}=\bar{f}_1^{e_1}\cdots\bar{f}_k^{e_k},\qquad\bar{f}_i\in\mathbb{F}_p[x],

then the ideal ⟨p⟩⊂OK\langle p\rangle\subset\mathcal{O}_K has prime factorization

pOK=∏i=1kqiei,qi=⟨p,fi(θ)⟩p\mathcal{O}_K=\prod_{i=1}^{k}\mathfrak{q}_i^{e_i},\qquad\mathfrak{q}_i=\langle p,f_i(\theta)\rangle

where each fi∈Z[x]f_i\in\mathbb{Z}[x] is a lift of fˉi∈Fp[x]\bar{f}_i\in\mathbb{F}_p[x]. Each prime qi\mathfrak{q}_i has norm NK/Q(qi)=pdeg⁡fˉiN_{K/\mathbb{Q}}(\mathfrak{q}_i)=p^{\deg\bar{f}_i}.

See also [20 Theorem 8.2] for a slightly more general version.

Theorem 2.4 tells us that for a given monic, irreducible ff, if we set K=Q[x]/⟨f(x)⟩K = \mathbb{Q}[x]/\langle f(x)\rangle, then the sum ∑p≤xW(p)\sum_{p\leq x} W(p) is closely related to the count

#{q⊂OK∣NK/Q(q)≤x}(2)\#\{\mathfrak{q} \subset\mathcal{O}_K \mid N_{K/\mathbb{Q}}(\mathfrak{q}) \leq x\} \tag*{(2)}

of prime ideals of norm not exceeding xx, 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 pep^e for some e≥2e \geq2.

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 KK be a number field, and let LL be a normal extension of KK with Galois group

G=Gal⁡(L/K).G = \operatorname{Gal}(L/K).

A prime ideal p⊂OK\mathfrak{p} \subset\mathcal{O}_K is said to be unramified in LL if the ideal pOL⊂OL\mathfrak{p}\mathcal{O}_L \subset\mathcal{O}_L has prime factorization

pOL=q1q2⋯qk\mathfrak{p}\mathcal{O}_L = \mathfrak{q}_1\mathfrak{q}_2 \cdots\mathfrak{q}_k

without any repeated factors. Then for each ideal q=qi\mathfrak{q} = \mathfrak{q}_i, there is a uniquely defined Frobenius automorphism

Frob⁡q∈Gal⁡(L/K)\operatorname{Frob}_{\mathfrak{q}} \in\operatorname{Gal}(L/K)

fixing q\mathfrak{q} setwise and satisfying Frob⁡q(t)≡t#(OK/p)(modq)\operatorname{Frob}_{\mathfrak{q}}(t) \equiv t^{\#(\mathcal{O}_K/\mathfrak{p})} \pmod{\mathfrak{q}} for all t∈OLt \in\mathcal{O}_L. In general Frob⁡q\operatorname{Frob}_{\mathfrak{q}} depends on our choice of prime q\mathfrak{q} lying over p\mathfrak{p}, but only up to conjugacy. We use the Artin symbol [L/Kp]\left[\frac{L/K}{\mathfrak{p}}\right] to denote this conjugacy class in Gal⁡(L/K)\operatorname{Gal}(L/K).

Following the notation of Lagarias and Odlyzko [15], we set

πC(x,L/K)=#{p⊂OK | p unramified in L[L/Kp]=CNK/Q(p)≤x}.\pi_C(x,L/K) = \#\left\{\mathfrak{p} \subset\mathcal{O}_K \ \middle|\ \begin{array}{l} \mathfrak{p}\text{ unramified in }L\\ \left[\frac{L/K}{\mathfrak{p}}\right] = C\\ N_{K/\mathbb{Q}}(\mathfrak{p}) \leq x \end{array} \right\}.

The Chebotarev density theorem says that for any conjugacy class CC in G=Gal⁡(L/K)G = \operatorname{Gal}(L/K), we have the asymptotic relation

πC(x,L/K)∼#C#GLi⁡(x)\pi_C(x,L/K) \sim\frac{\#C}{\#G}\operatorname{Li}(x)

as x→∞x \to\infty. 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 c>0c > 0 such that for every x>2x > 2, if LL is a normal extension of the number field KK with Galois group G=Gal⁡(L/K)G = \operatorname{Gal}(L/K), then we have

∣πC(x,L/K)−#C#GLi⁡(x)∣≤c⋅#C#Gx1−εlog⁡(ΔL1/εx[L:Q]).\left|\pi_C(x,L/K)-\frac{\#C}{\#G}\operatorname{Li}(x)\right| \leq c\cdot\frac{\#C}{\#G}x^{1-\varepsilon}\log\left(\Delta_L^{1/\varepsilon}x^{[L:\mathbb{Q}]}\right).

Remark 3.2. The theorem stated in [15] corresponds to the case ε=12\varepsilon= \frac{1}{2}.

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 c>0c > 0 with the following property: if f∈Z[x]f \in\mathbb{Z}[x] is an irreducible monic polynomial of degree d≥1d \geq1, and K=Q[x]/⟨f(x)⟩K = \mathbb{Q}[x]/\langle f(x)\rangle, then

∣#{q⊂OK∣NK/Q(q)≤x}−Li⁡(x)∣≤c⋅x1−εlog⁡(ΔK1/εxd)\left|\#\left\{\mathfrak{q} \subset\mathcal{O}_K \mid N_{K/\mathbb{Q}}(\mathfrak{q}) \leq x\right\}-\operatorname{Li}(x)\right| \leq c\cdot x^{1-\varepsilon}\log\left(\Delta_K^{1/\varepsilon}x^d\right)

for every x>2x > 2.

Proof. We take L=KL = K, which is trivially a normal extension of KK. Then Gal⁡(L/K)\operatorname{Gal}(L/K) 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 ff has modulo the various primes p≤xp \leq x, is at least

Li⁡(x)−c⋅x1−εlog⁡(ΔK1/εxd).\operatorname{Li}(x)-c\cdot x^{1-\varepsilon}\log\left(\Delta_K^{1/\varepsilon}x^d\right).

Thus we have two remaining goals, at least in the proof of Theorem 2.1 for monic ff: one is to determine how many of the prime ideals in OK\mathcal{O}_K actually correspond to roots mod pp, and then the other is to bound error term x1−εlog⁡(ΔK1/εxd)x^{1-\varepsilon}\log\left(\Delta_K^{1/\varepsilon}x^d\right).

In order to understand the discriminant ΔK\Delta_K appearing in this error term, we apply the identity

Δf=[OK:Z[θ]]2⋅ΔK,(3)\Delta_f = [\mathcal{O}_K:\mathbb{Z}[\theta]]^2\cdot\Delta_K, \tag*{(3)}

see e.g. [20 Equation (7.7)]. Here the term Δf\Delta_f denotes the absolute value of the product

∏1≤i<j≤d(θi−θj)2,\prod_{1\leq i<j\leq d}(\theta_i-\theta_j)^2,

where the θi\theta_i are the roots of ff in C\mathbb{C}.

Lemma 3.4 (cf. [12 Equation (3)]). Let f∈Z[x]f \in\mathbb{Z}[x] be a monic polynomial of degree d≥1d \geq1. The discriminant Δf\Delta_f satisfies

log⁡Δf<2d(log⁡(d+1)+log⁡∥f∥).\log\Delta_f < 2d\left(\log(d+1)+\log\lVert f\rVert\right).

Proof. We can evaluate Δf\Delta_f as the resultant of ff and f′f', which is defined as the determinant of a certain (2d−1)×(2d−1)(2d-1)\times(2d-1) matrix MM, the Sylvester matrix of ff and f′f'. The first d−1d-1 rows of MM each contain shifts of the coefficient vector of ff: there are at most d+1d+1 nonzero entries, each bounded in absolute value by ∥f∥\lVert f\rVert, so as row vectors these have length at most ∥f∥d+1\lVert f\rVert\sqrt{d+1}. Likewise, the remaining dd rows are all shifts of the coefficient vector of f′f', which has at most dd nonzero entries bounded by d∥f∥d\lVert f\rVert, so as row vectors these have length at most d∥f∥⋅dd\lVert f\rVert\cdot\sqrt{d}. Then Δf=∣det⁡(M)∣\Delta_f = |\det(M)| is at most the product of the lengths of the rows of MM:

Δf≤(∥f∥d+1)d−1⋅(∥f∥d3/2)d<∥f∥2d−1(d+1)2d−1/2.\Delta_f \le\left(\lVert f\rVert\sqrt{d}+1\right)^{d-1}\cdot\left(\lVert f\rVert d^{3/2}\right)^d < \lVert f\rVert^{2d-1}(d+1)^{2d-1/2}.

The lemma follows immediately. □

Counting roots mod pp of monic polynomials

Let f∈Z[x]f \in\mathbb{Z}[x] be monic and irreducible, of degree d≥1d \ge1, and with some root θ∈C\theta\in\mathbb{C}. Letting K=Q(θ)K = \mathbb{Q}(\theta) as in Theorem 2.4, we now attempt to classify the primes q⊂OK\mathfrak{q} \subset\mathcal{O}_K of norm at most xx. Each such q\mathfrak{q} lies over some rational prime pp, meaning that q∩Z=pZ\mathfrak{q} \cap\mathbb{Z} = p\mathbb{Z}, and then it is one of the factors in the prime factorization

pOK=q1⋯qk.p\mathcal{O}_K=\mathfrak{q}_1\cdots\mathfrak{q}_k.

Since the relative norm of an ideal is multiplicative, we have

∏i=1kNK/Q(qi)=NK/Q(pOK)=pd.(4)\prod_{i=1}^{k}N_{K/\mathbb{Q}}(\mathfrak{q}_i)=N_{K/\mathbb{Q}}(p\mathcal{O}_K)=p^d. \tag*{(4)}

so each NK/Q(qi)N_{K/\mathbb{Q}}(\mathfrak{q}_i) is a positive power of pp; there are at most dd factors qi\mathfrak{q}_i; and

p≤NK/Q(q)≤x.p \le N_{K/\mathbb{Q}}(\mathfrak{q}) \le x.

Thus each prime ideal q⊂OK\mathfrak{q} \subset\mathcal{O}_K of norm at most xx lies over a prime p≤xp \le x satisfying exactly one of the following:

  1. pp does not divide Δf\Delta_f, and NK/Q(q)=pN_{K/\mathbb{Q}}(\mathfrak{q})=p;

  2. pp does not divide Δf\Delta_f, and NK/Q(q)=peN_{K/\mathbb{Q}}(\mathfrak{q})=p^e for some e≥2e \ge2;

  3. pp divides Δf\Delta_f.

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 pp cannot divide [OK:Z[θ]][\mathcal{O}_K:\mathbb{Z}[\theta]], so Theorem 2.4 says that such ideals q\mathfrak{q} are in bijection with the roots of ff mod pp.

In case (2) we have p2≤NK/Q(q)≤xp^2 \le N_{K/\mathbb{Q}}(\mathfrak{q}) \le x, so p≤xp \le\sqrt{x}. For any fixed pp, the relation (4) says that there are at most d/2d/2 such primes q\mathfrak{q} over pp, so overall this case contributes at most dx/2d\sqrt{x}/2 prime ideals to the total.

Finally, in case (3), there are at most log⁡2Δf<2log⁡Δf\log_2\Delta_f < 2\log\Delta_f primes pp dividing Δf\Delta_f, and for each of these the ideal pOKp\mathcal{O}_K contributes at most dd prime factors q\mathfrak{q} of norm at most xx, so in total this case contributes at most 2d⋅log⁡Δf2d\cdot\log\Delta_f prime ideals.

Isolating case (1) from the rest, we have shown that

∑p≤xp∤ΔfW(p)≥#{q⊂OK∣NK/Q(q)≤x}−12dx1/2−2dlog⁡Δf.(5)\sum_{\substack{p\le x\\p\nmid\Delta_f}}W(p)\ge\#\{\mathfrak{q}\subset\mathcal{O}_K\mid N_{K/\mathbb{Q}}(\mathfrak{q})\le x\}-\frac{1}{2}d x^{1/2}-2d\log\Delta_f. \tag*{(5)}

Proposition 4.1. Assuming Hypothesis 1.2, there is a universal constant c>0c > 0 with the following property. Let f∈Z[x]f \in\mathbb{Z}[x] be a monic, irreducible polynomial of degree d≥1d \ge1. Then

∑p≤xp∤ΔfW(p)≥Li⁡(x)−cx1−ϵlog⁡(Δf1/ϵxd)−d(12x1/2+2log⁡Δf)\sum_{\substack{p \le x \\ p \nmid\Delta_f}} W(p) \ge\operatorname{Li}(x) - c x^{1-\epsilon}\log\left(\Delta_f^{1/\epsilon}x^d\right) - d\left(\frac{1}{2}x^{1/2} + 2\log\Delta_f\right)

for all x>2x > 2.

Proof. Let cc be the constant provided by the effective prime ideal theorem, Corollary 3.3, so that

#{q⊂OK∣NK/Q(q)≤x}≥Li⁡(x)−c⋅x1−ϵlog⁡(ΔK1/ϵxd).\#\left\{\mathfrak{q} \subset\mathcal{O}_K \mid N_{K/\mathbb{Q}}(\mathfrak{q}) \le x\right\} \ge\operatorname{Li}(x) - c \cdot x^{1-\epsilon}\log\left(\Delta_K^{1/\epsilon}x^d\right).

We can replace ΔK\Delta_K with Δf\Delta_f, 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 f∈Z[x]f \in\mathbb{Z}[x] is monic, but the general case quickly reduces to this one. Suppose that

f(x)=adxd+ad−1xd−1+⋯+a0,f(x) = a_d x^d + a_{d-1}x^{d-1} + \cdots+ a_0,

where ad≠0a_d \ne0. We consider the related polynomial

g(x)=add−1f(xad)=xd+∑i=0d−1add−1−iaixi,g(x) = a_d^{d-1}f\left(\frac{x}{a_d}\right) = x^d + \sum_{i=0}^{d-1}a_d^{d-1-i}a_i x^i,

which is monic and which has integer coefficients as well. Then θ\theta is a root of f(x)f(x) if and only if adθa_d\theta is a root of g(x)g(x), and this is true not just over C\mathbb{C} but also over any field Fp\mathbb{F}_p as long as ada_d is invertible mod pp. Thus if we want to find a prime pp such that ff has a root mod pp, it suffices to find p∤adp \nmid a_d such that gg has a root mod pp.

We now observe that deg⁡g=deg⁡f=d\deg g = \deg f = d, and also that

∥g∥≤∣ad∣d−1∥f∥≤∥f∥d⟹log⁡∥g∥≤d⋅log⁡∥f∥.\lVert g\rVert\le|a_d|^{d-1}\lVert f\rVert\le\lVert f\rVert^d \qquad\Longrightarrow\qquad\log\lVert g\rVert\le d\cdot\log\lVert f\rVert.

Since ∣ad∣≤∥f∥|a_d| \le\lVert f\rVert, the number of primes dividing ada_d is at most

log⁡2∣ad∣≤2log⁡∣ad∣≤2log⁡∥f∥,\log_2 |a_d| \le2\log|a_d| \le2\log\lVert f\rVert,

and each of them has at most dd prime ideal factors in OK\mathcal{O}_K where K=Q[x]/⟨g⟩K = \mathbb{Q}[x]/\langle g\rangle. 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 ada_d, to get

∑p≤xp∤Δgp∤adW(p)≥Li⁡(x)−cx1−ϵlog⁡(Δg1/ϵxd)−d(12x1/2+2log⁡Δg+2log⁡∥f∥).\sum_{\substack{p \le x \\ p \nmid\Delta_g \\ p \nmid a_d}} W(p) \ge\operatorname{Li}(x) - c x^{1-\epsilon}\log\left(\Delta_g^{1/\epsilon}x^d\right) - d\left(\frac{1}{2}x^{1/2} + 2\log\Delta_g + 2\log\lVert f\rVert\right).

Applying Lemma 3.4 to the monic polynomial gg gives us

log⁡Δg<2d(log⁡(d+1)+log⁡∥g∥)(6)\log\Delta_g < 2d\left(\log(d+1) + \log\lVert g\rVert\right) \tag*{(6)}
≤2d(log⁡(d+1)+dlog⁡∥f∥),\le2d\left(\log(d+1) + d\log\lVert f\rVert\right),

so collectively we have shown the following.

Proposition 5.1. Assuming Hypothesis 1.2, there is a universal polynomial h(x,y)h(x,y) with the following property. Let f∈Z[x]f \in\mathbb{Z}[x] be an irreducible polynomial of degree d≥1d \ge1, with leading coefficient ad≠0a_d \ne0. Then

∑p≤xp∤ad, p∤ΔgW(p)≥Li⁡(x)−h(d,log⁡∥f∥)⋅x1−ϵlog⁡x(7)\sum_{\substack{p \le x \\ p\nmid a_d,\ p\nmid\Delta_g}} W(p) \ge\operatorname{Li}(x)-h(d,\log\lVert f\rVert)\cdot x^{1-\epsilon}\log x \tag*{(7)}

for all x>2x>2, where the discriminant Δg\Delta_g of g(x)=add−1f(x/ad)g(x)=a_d^{d-1}f(x/a_d) satisfies (5.1). The polynomial h(x,y)h(x,y) depends on the constant ϵ\epsilon in Hypothesis 1.2 and the resulting universal constant cc, but we will not make this explicit other than to note that we can certainly take h(x,y)=O(x3y)h(x,y)=O(x^3y).

Proof of Theorem 2.1. We wish to find xx, of size polynomial in dd and log⁡∥f∥\log\lVert f\rVert, 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

Li⁡(x)>h(d,log⁡∥f∥)⋅x1−ϵlog⁡x,\operatorname{Li}(x)>h(d,\log\lVert f\rVert)\cdot x^{1-\epsilon}\log x,

and if x≥4x\ge4 then the inequality

Li⁡(x)=∫2xdtlog⁡t≥∫2xdtlog⁡x=x−2log⁡x≥x/2log⁡x\operatorname{Li}(x)=\int_{2}^{x}\frac{\mathrm{d}t}{\log t}\ge\int_{2}^{x}\frac{\mathrm{d}t}{\log x}=\frac{x-2}{\log x}\ge\frac{x/2}{\log x}

shows that it will further suffice to take xx satisfying

xϵ>2h(d,log⁡∥f∥)⋅(log⁡x)2.x^\epsilon>2h(d,\log\lVert f\rVert)\cdot(\log x)^2.

There is a constant k>4k>4 such that

xϵ/3>log⁡xx^{\epsilon/3}>\log x

for all x≥kx\ge k, and for all x≥(2h(d,log⁡∥f∥))3/ϵ+kx\ge\left(2h(d,\log\lVert f\rVert)\right)^{3/\epsilon}+k we have

xϵ>xϵ/3(log⁡x)2>2h(d,log⁡∥f∥)⋅(log⁡x)2x^\epsilon>x^{\epsilon/3}(\log x)^2>2h(d,\log\lVert f\rVert)\cdot(\log x)^2

as desired. □

References

Department of Mathematics, Boston College

Email address: [email protected]

Department of Mathematics, Imperial College London

Email address: [email protected]

References

  1. [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. [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. [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. [4]A quasi-Riemann hypothesis for Dedekind zeta functions. Hexagon preprint hexagon:2610.00200v2, 2026. Contributors: Dean Cureton; Jesse Thorner. 2, 3
  5. [5]R. Haraway and N. R. Hoffman. On the complexity of cusped non-hyperbolicity. arXiv:1907.01675, 2019. 1, 3arxiv.org/abs/1907.01675
  6. [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
  7. [8]S. V. Ivanov. The computational complexity of basic decision problems in 3-dimensional topology. Geom. Dedicata, 131:1–26, 2008. 1, 3DOI
  8. [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
  9. [10]P. Kronheimer and T. Mrowka. Knots, sutures, and excision. J. Differential Geom., 84(2):301–364, 2010. 1arxiv.org/abs/0807.4891
  10. [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
  11. [12]G. Kuperberg. Knottedness is in NP, modulo GRH. Adv. Math., 256:493–506, 2014. 1, 2, 3, 4, 5, 7
  12. [13]M. Lackenby. The efficient certification of knottedness and Thurston norm. Adv. Math., 387:Paper No. 107796, 142, 2021. 3arxiv.org/abs/1604.00290
  13. [14]M. Lackenby. A polynomial upper bound on Reidemeister moves for each link type. arXiv:2602.09923, 2026. 1arxiv.org/abs/2602.09923
  14. [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
  15. [17]OpenAI. The Quasi-Riemann Hypothesis. OpenAI Math Release preprint OAI:The-Quasi-Riemann-Hypothesis-October-5-2026, 2026. 3
  16. [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
  17. [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
  18. [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
  19. [21]P. Turan. On Riemann’s hypothesis. Bull. Acad. Sci. URSS. Sér. Math. [Izvestia Akad. Nauk SSSR], 11:197–262, 1947. 2
  20. [22]P. J. Weinberger. Finding the number of factors of a polynomial. J. Algorithms, 5(2):180–186, 1984. 5DOI

Paper details

vlnc:W_uprcsp3n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents