Positive moments forever: Undecidable and decidable cases

Gemma De les Coves; Joshua Graf; Andreas Klingler; Tim Netzer

doi:10.1016/j.laa.2025.05.015

Positive moments forever: Undecidable and decidable cases

Gemma De les Coves
, Joshua Graf
, Andreas Klingler
, Tim Netzer

Department of Mathematics

Publications: Contribution to journal › Article › Peer Reviewed

Abstract

We investigate the generalized moment membership problem for matrices, a formulation equivalent to Skolem's problem for linear recurrence sequences. We show decidability for orthogonal, unitary, and real eigenvalue matrices, and undecidability for matrices over certain commutative and non-commutative polynomial rings. As consequences, we deduce that positivity is decidable for simple unitary linear recurrence sequences and undecidable for linear recurrence sequences over commutative polynomial rings. As a byproduct, we also prove a free version of Pólya's theorem.

Original language	English
Pages (from-to)	255-275
Number of pages	21
Journal	Linear Algebra and Its Applications
Volume	722
DOIs	https://doi.org/10.1016/j.laa.2025.05.015
Publication status	Published - 1 Oct 2025

Austrian Fields of Science 2012

101001 Algebra
101013 Mathematical logic

Keywords

Linear recurrence sequence
Matrix moment sequence
Positivity
Undecidability

Access to Document

10.1016/j.laa.2025.05.015

Cite this

@article{fb78f07b864e4821b9007c6373b66a36,

title = "Positive moments forever: Undecidable and decidable cases",

abstract = "We investigate the generalized moment membership problem for matrices, a formulation equivalent to Skolem's problem for linear recurrence sequences. We show decidability for orthogonal, unitary, and real eigenvalue matrices, and undecidability for matrices over certain commutative and non-commutative polynomial rings. As consequences, we deduce that positivity is decidable for simple unitary linear recurrence sequences and undecidable for linear recurrence sequences over commutative polynomial rings. As a byproduct, we also prove a free version of P{\'o}lya's theorem.",

keywords = "Linear recurrence sequence, Matrix moment sequence, Positivity, Undecidability",

author = "\{De les Coves\}, Gemma and Joshua Graf and Andreas Klingler and Tim Netzer",

note = "Publisher Copyright: {\textcopyright} 2025 Elsevier Inc.",

year = "2025",

month = oct,

day = "1",

doi = "10.1016/j.laa.2025.05.015",

language = "English",

volume = "722",

pages = "255--275",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

}

TY - JOUR

T1 - Positive moments forever

T2 - Undecidable and decidable cases

AU - De les Coves, Gemma

AU - Graf, Joshua

AU - Klingler, Andreas

AU - Netzer, Tim

PY - 2025/10/1

Y1 - 2025/10/1

N2 - We investigate the generalized moment membership problem for matrices, a formulation equivalent to Skolem's problem for linear recurrence sequences. We show decidability for orthogonal, unitary, and real eigenvalue matrices, and undecidability for matrices over certain commutative and non-commutative polynomial rings. As consequences, we deduce that positivity is decidable for simple unitary linear recurrence sequences and undecidable for linear recurrence sequences over commutative polynomial rings. As a byproduct, we also prove a free version of Pólya's theorem.

AB - We investigate the generalized moment membership problem for matrices, a formulation equivalent to Skolem's problem for linear recurrence sequences. We show decidability for orthogonal, unitary, and real eigenvalue matrices, and undecidability for matrices over certain commutative and non-commutative polynomial rings. As consequences, we deduce that positivity is decidable for simple unitary linear recurrence sequences and undecidable for linear recurrence sequences over commutative polynomial rings. As a byproduct, we also prove a free version of Pólya's theorem.

KW - Linear recurrence sequence

KW - Matrix moment sequence

KW - Positivity

KW - Undecidability

UR - https://www.scopus.com/pages/publications/105005939967

U2 - 10.1016/j.laa.2025.05.015

DO - 10.1016/j.laa.2025.05.015

M3 - Article

AN - SCOPUS:105005939967

SN - 0024-3795

VL - 722

SP - 255

EP - 275

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Positive moments forever: Undecidable and decidable cases

Abstract

Austrian Fields of Science 2012

Keywords

Access to Document

Other files and links

Fingerprint

Cite this