author = {Georg Regensburger and Clemens Hofstadler and Peter Krug},
title = {{Refuting noncommutative ideal memberschip via matrix certificates}},
booktitle = {{Proceedings of ISSAC 2026}},
language = {english},
abstract = {The ideal membership problem in free algebras is undecidable in general. More precisely, while membership can always be verified in finite time (e.g., via noncommutative Gröbner bases), non-membership is undecidable in general. In this work, we introduce matrix certificates for refuting ideal membership of (commutative and) noncommutative polynomials. Such certificates are matrix evaluations that vanish on the generators of an ideal but not on a given candidate polynomial. For commutative polynomials, a perfect Nullstellensatz guarantees the existence of such certificates with commuting square matrices. For noncommutative polynomials, certificates may require non-square matrices or may not exist at all. To handle evaluations on non-square matrices, we use quivers and their matrix representations. We have implemented an approach for finding matrix certificates by ansatz in SageMath and demonstrate its effectiveness on different examples. Our method relies on the ability to efficiently find one (simple) solution to a system of commutative polynomial equations, which we do by combining SAT solving with Hensel lifting. Our experiments suggest that, in practice, ideal (non-)membership can be efficiently decided and certified.},
pages = {209--218},
isbn_issn = {979-8-4007-2595-1},
year = {2026},
editor = {Christoph Koutschan and Alin Bostan and Clement pernet and Thi Xuan Vu},
refereed = {yes},
length = {10},
url = {https://dl.acm.org/doi/10.1145/3815436.3815447}