PreprintarXiv licencearXiv
Trinomial containment in polynomial ideals is undecidable
Abstract
We prove that deciding whether an ideal in a polynomial ring contains a trinomial is impossible on a Turing machine. More precisely, from an integer polynomial P we compute generators of an ideal IP in a polynomial ring over ℚ such that IP contains a trinomial if and only if P has an integral zero. By the MRDP theorem this problem is undecidable. A universal halting polynomial gives a computable family of ideals in one fixed polynomial ring, with uniform bounds on colength, generator count, and generator degree, for which the containment of a trinomial encodes the halting problem.
Related
- Lyapunov stability of polynomial vector fields is undecidable
- Controllability of polynomial systems is undecidable and not recursively enumerable
- Global asymptotic stability of homogeneous polynomial vector fields is undecidable
- Prime Ideals and Projective Closure in the Boolean Polynomial Semiring
- Stacked-bases Properties, maximal ideals and polynomial closures of Rings of Integer-Valued Polynomials
BibTeX
@misc{boege2026trinomial,
title = {{Trinomial containment in polynomial ideals is undecidable}},
author = {Tobias Boege and Anna Hofer and Thomas Kahle},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.31162},
eprint = {2608.31162},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.31162},
}
RIS
TY - UNPB
TI - Trinomial containment in polynomial ideals is undecidable
AU - Tobias Boege
AU - Anna Hofer
AU - Thomas Kahle
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.31162
UR - https://arxiv.org/abs/2608.31162
AB - We prove that deciding whether an ideal in a polynomial ring contains a trinomial is impossible on a Turing machine. More precisely, from an integer polynomial P we compute generators of an ideal I_P in a polynomial ring over ℚ such that I_P contains a trinomial if and only if P has an integral zero. By the MRDP theorem this problem is undecidable. A universal halting polynomial gives a computable family of ideals in one fixed polynomial ring, with uniform bounds on colength, generator count, and generator degree, for which the containment of a trinomial encodes the halting problem.
ER -