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

Igor Rivin · 2026

Read Monte-Carlo Irreducibility and Imprimitivity Detection of Polynomials over ℚ \mathbb{Q} by Igor Rivin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-00944.txt.

Description

Igor Rivin gives an explicit Monte-Carlo method detecting imprimitivity via subfield extraction, yielding constructive algebraic proofs, the first such high-degree algorithm. He studies Monte-Carlo methods testing irreducibility and spotting imprimitivity of polynomials. Building on the Pemantle-Peres-Rivin subset-sum criterion, he develops a random test with expected time log in degree for generic inputs. His method, unlike the standard modular test, pools modular factorization information rather than dropping failed trials. Test failure plus a modular proof strongly signals non-generic structure, often pointing to Galois imprimitivity.

Catalog record

CREATORIgor Rivin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE8885
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602.00944

Browse the full library · About the Tower of Babel