O31 — Order of a polynomial's Galois group

Definitions and mathematical statement

Let $f\in\mathbb Q[X]$ be a nonzero polynomial, given densely with each rational coefficient written as a reduced fraction of binary integers. Fix an algebraic closure $\overline{\mathbb Q}$, and let $K$ be the smallest subfield containing $\mathbb Q$ and every root of $f$. This field is the splitting field of $f$ over $\mathbb Q$.

Since the characteristic is zero, $K/\mathbb Q$ is finite and Galois. Its Galois group consists of all field automorphisms of $K$ fixing every rational number, and its order is $[K:\mathbb Q]$. Repeated factors of $f$ do not change $K$; a nonzero constant polynomial has $K=\mathbb Q$ and output one.

Can a deterministic classical algorithm compute the exact integer $[K:\mathbb Q]$, in binary, in time polynomial in the total dense input length? Both polynomial degree and coefficient bit sizes are variable parameters. The algorithm is not given defining equations for the entire splitting field or a list of its automorphisms.

Only the order is requested. Constructing the full field, listing all group elements, or describing their action individually would impose stronger output requirements. Although the field degree can be as large as $d!$ for a degree-$d$ polynomial, its binary length is only $O(d\log(d+1))$; an efficient order computation is therefore not excluded merely by the number of automorphisms.

Short English statement

Can the order of the Galois group of an arbitrary rational polynomial be computed deterministically in polynomial time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400035 (AMR-083-0035), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O31, p21 / LNCS p311. Original source indexed by AMR-083-0035. https://mccurley.org/papers/open.ps.gz.