{"id":"hexagon/2611.00115","pdf":"https://hexagonmath.org/pdf/2611.00115v1","url":"https://hexagonmath.org/abs/2611.00115v1","tags":["cs.CC","cs.DS","cs.LO","msc:11R29","msc:11Y16","msc:11Y40","msc:11A15","msc:68V20"],"score":0,"title":"Class numbers, square roots and quadratic non-residues in time $2^{O(n/\\sqrt{\\log n})}$, assuming the new #SAT algorithms","domain":"math.NT","origin":"ai-generated","source":"hexagon","authors":["Vaibhav Tulsyan"],"reviews":0,"subject":"math.NT","summary":"Basic problems of computational number theory have proven deterministic bounds that are fixed powers of the input. The class number $h(D)$ of an imaginary quadratic discriminant takes $|D|^{1/2+o(1)}$ steps unconditionally and $|D|^{1/5+o(1)}$ under the generalised Riemann hypothesis (GRH); the least quadratic non-residue modulo a prime $p$ takes $p^{1/(4\\sqrt e)+o(1)}$ by Burgess's 1957 bound, polynomial only under GRH; exact divisor sums $\\sum_{m\\le x}\\tau(m)$ take $x^{1/3+o(1)}$. However, none of these bounds is of the form $X^{o(1)}$, even conditionally. We present deterministic…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"ai_models":["Claude Opus"],"discussed":0,"published":"2026-11-05","reactions":{},"withdrawn":false,"authorship":"no-human-author-claimed","formalized":false,"human_understanding":"some"}