We show that for a large class of integer linear recurrence sequences (un)n∈N, the first-order theories of 〈N; <, n ↦ max{0, un}〉 and 〈N; +, {un : n ∈N} ∩ N〉 are undecidable. Our approach is to show that (un)n∈N contains, in a specific sense, all finite sequences over N, an idea that we borrow from the proof of Hieronymi and Schulz that the first-order theory of 〈N; +, {2n : n ∈N}, {3n : n ∈N}〉 is undecidable. In a similar way, we harness a contemporary result about quasi-randomness in the values of the Ramanujan tau function to show that the first-order theory of 〈N; <, n ↦ |τ(n)|〉 is undecidable.
Submitted, 2026. 15 pages.
PDF
© 2026 Toghrul Karimov, Joris Nieuwveld, and Joël Ouaknine.