Class numbers, square roots and quadratic non-residues in time $2^{O(n/\sqrt{\log n})}$, assuming the new #SAT algorithms
Source: hexagonmath.org/abs/2611.00115v1
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00115
curl -X POST /api/v1/records/hexagon/2611.00115/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00115/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'