Monte-Carlo Irreducibility and Imprimitivity Detection of Polynomials over $\mathbb{Q}$

Technical Summary: Monte-Carlo Irreducibility and Imprimitivity Detection of Polynomials Over $\mathbb{Q}$

Problem Statement
The paper addresses three central problems in computational algebra and number theory: factoring polynomials over the rational numbers $\mathbb{Q}$, testing polynomial irreducibility, and determining the structure of Galois groups. While deterministic algorithms exist with polynomial-time theoretical bounds, they often become impractical at modest degrees. Conversely, standard modular methods scale well but typically discard information from "unsuccessful" trials (where a polynomial factors modulo $p$) rather than aggregating it. Furthermore, detecting arithmetic imprimitivity (the existence of nontrivial block systems in the Galois action) in high degrees has lacked practical algorithms.

Methodology
The proposed approach relies on Monte-Carlo methods that aggregate information from modular factorizations across multiple primes, rather than stopping at the first irreducible reduction.

1. The PPR Subset-Sum Criterion: Building on the work of Pemantle, Peres, and Rivin (PPR), the method utilizes the factor degrees $(d_i)$ of a polynomial $f$ modulo a prime $p$. It constructs a subset-sum set $S_p$ containing all possible sums $\sum_{i \in I} d_i$. The core theoretical premise is that if $f$ possesses a rational factor of degree $d$, then $d$ must belong to $S_p$ for all "good" primes.
2. Probabilistic Irreducibility Test: The algorithm intersects the subset-sum sets $S_p$ across a sequence of sampled primes. If the intersection contains no proper degrees (degrees strictly between 1 and $n$), the polynomial is declared irreducible.
3. Hybrid Strategy: The algorithm runs the PPR-based test for an expected $O(\log n)$ primes. If the test is inconclusive, it falls back to standard modular irreducibility tests.
4. Imprimitivity Detection: The method treats the "failure" of the subset-sum test (where the intersection remains non-empty despite the polynomial being certified irreducible) as a structural flag. This signals potential arithmetic imprimitivity. The algorithm then performs a search for nontrivial subfields within the root field $K = \mathbb{Q}(\alpha)$, yielding constructive certificates.
5. Warm-Start for Factorization: When the subset-sum intersection does not collapse, the surviving degrees provide a restricted candidate set $D$ for rational factor degrees. This set is used to accelerate subsequent Hensel lifting and recombination procedures.

Key Contributions and Results

• Efficient Probabilistic Irreducibility Test: For generic inputs, the expected running time (measured in the number of primes examined) is logarithmic in the degree, $O(\log n)$. Unlike standard tests that discard unsuccessful modular factorizations, this method aggregates information from all trials.
• Detection of Arithmetic Imprimitivity: The paper presents the first practical Monte-Carlo algorithm for detecting arithmetic imprimitivity in high-degree polynomials over $\mathbb{Q}$. It identifies imprimitivity not merely through heuristic statistics but by producing explicit algebraic certificates: nontrivial intermediate subfields and relative equations defining the root field over these subfields.
• Acceleration of Factorization: The subset-sum data generated during irreducibility testing serves as a "warm start" for factorization. By sharply restricting the possible degrees of rational factors, the method significantly reduces the combinatorial complexity of lifting and recombination, avoiding the need for new modular computations.
• Adversarial Robustness: The authors demonstrate that while local modular data is informative when aggregated, it is insufficient to certify global structure on its own. They construct "evil twin" polynomials that preserve reductions modulo small primes but restore generic global Galois behavior, illustrating the necessity of combining probabilistic heuristics with explicit field-theoretic constructions.

Significance and Claims
The paper claims that these methods are orders of magnitude faster in practice than known deterministic algorithms and remain effective in degrees far beyond the reach of current deterministic techniques.

• Practicality: The algorithms are described as practical, implemented, and successfully applied to high-degree polynomials.
• Pareto Optimality: The hybrid approach is claimed to be Pareto-optimal; it is never asymptotically worse than existing Monte-Carlo methods and is often significantly faster.
• Constructive Output: In the case of imprimitivity, the method moves beyond detection to provide constructive certificates (subfields and relative equations), distinguishing it from purely heuristic approaches.
• Scalability: The reliance on modular computation, small primes, and information aggregation makes the methods particularly well-suited for large-scale and parallel computation.

The paper concludes that while local modular data is highly informative when aggregated, efficient certification of global algebraic structure requires the combination of probabilistic heuristics with explicit field-theoretic constructions.