Decidability of zero hitting by rational matrix powers
In the problem below, rational numbers are given exactly, for instance by numerator and denominator in binary, and there is no bound on $d$, on the entries or on $k$. For $A \in \mathbb{Q}^{d \times d}$ and $u, v \in \mathbb{Q}^d$ the sequence $(u^{\mathsf T} A^k v)_{k \ge 0}$ is a rational linear recurrence sequence of order at most $d$, and every such sequence arises in this way, so the question below is the Skolem problem: whether a linear recurrence sequence, given by rational coefficients and initial values, has a zero term (Bacik et al.). Mignotte, Shorey and Tijdeman, and independently Vereshchagin, showed that it is decidable for sequences of order at most $4$, hence for $d \le 4$. Luca, Ouaknine and Worrell showed that a strengthening of Cramér's conjecture on gaps between primes would imply that it is decidable.
Problem. Is there a single algorithm which, given a positive integer $d$, a matrix $A \in \mathbb{Q}^{d \times d}$ and vectors $u, v \in \mathbb{Q}^d$, always halts and correctly decides whether $$u^{\mathsf T} A^k v = 0 \quad \text{for some integer } k \ge 0?$$
Source: Classical, with no single originator: implicit in Skolem (1934), and first stated explicitly in the 1970s, by Mignotte and by Salomaa and Soittola among others; see Bacik et al. (2026), §5.1.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NT — Number Theory
- Secondary
- LO, NA
- Keywords
- decidability, linear recurrence sequences, OpenProblemsInNLA, Skolem problem
- Literature checked
- Oct. 7, 2026 by clemens-admin
References
@incollection{skolem1934,
author = {Skolem, Thoralf},
title = {Ein {V}erfahren zur {B}ehandlung gewisser exponentialer {G}leichungen und diophantischer {G}leichungen},
booktitle = {Comptes Rendus du Huiti{\`e}me Congr{\`e}s des Math{\'e}maticiens Scandinaves (Stockholm, 1934)},
year = {1934},
pages = {163--188},
}
@misc{bacik2026,
author = {Bacik, Piotr and Karimov, Toghrul and Luca, Florian and Nieuwveld, Joris and Ouaknine, Jo{\"e}l and Purser, David and Worrell, James},
title = {A survey of the {S}kolem and {P}ositivity {P}roblems for linear recurrence sequences},
year = {2026},
howpublished = {Submitted},
url = {https://people.mpi-sws.org/~joel/publications/skolem_and_positivity_survey26.pdf},
note = {Version of 26 July 2026},
}
@article{mignotte1984,
author = {Mignotte, Maurice and Shorey, Tarlok N. and Tijdeman, Robert},
title = {The distance between terms of an algebraic recurrence sequence},
journal = {J. Reine Angew. Math.},
volume = {349},
year = {1984},
pages = {63--76},
doi = {10.1515/crll.1984.349.63},
}
@article{vereshchagin1985,
author = {Vereshchagin, N. K.},
title = {Occurrence of zero in a linear recursive sequence},
journal = {Math. Notes},
volume = {38},
number = {2},
year = {1985},
pages = {609--615},
doi = {10.1007/BF01156238},
}
@misc{luca2026,
author = {Luca, Florian and Ouaknine, Jo{\"e}l and Worrell, James},
title = {Conjectural Decidability of the {S}kolem Problem},
year = {2026},
eprint = {2607.15510},
archivePrefix = {arXiv},
}
@article{mignotte1977,
author = {Mignotte, Maurice},
title = {Calculs sur des suites r{\'e}currentes lin{\'e}aires},
journal = {M{\'e}m. Soc. Math. France},
volume = {49--50},
year = {1977},
pages = {137--140},
doi = {10.24033/msmf.222},
}
@book{salomaa1978,
author = {Salomaa, Arto and Soittola, Matti},
title = {Automata-Theoretic Aspects of Formal Power Series},
publisher = {Springer},
year = {1978},
doi = {10.1007/978-1-4612-6264-0},
}
@misc{openproblemsinnla-mf19,
author = {Townsend, Alex},
title = {{MF-19}: Decidability of zero hitting by rational matrix powers},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/matrix-functions-and-stability/MF-19/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00167, "Decidability of zero hitting by rational matrix powers", clopen.solutions.