Rich sequences and decidability of logical theories

We develop a new framework for proving the undecidability of first-order theories of structures of the form ⟨ℕ; +, P⟩, ⟨ℕ; <, f⟩, and ⟨ℕ; +, f⟩, where P ⊆ ℕ and f : ℕ → ℕ. It is based on the recent proof of Hieronymi and Schulz that the first-order theory of ⟨ℕ; +, {2ⁿ : n ∈ ℕ}, {3ⁿ : n ∈ ℕ}⟩ is undecidable, and capable of transforming various randomness results about integer sequences into undecidability proofs. We apply our method to a large class of integer linear recurrence sequences, as well as various special functions, in particular showing that the first-order theories of ⟨ℕ; +, {u_n : n ∈ ℕ} ∩ ℕ⟩, ⟨ℕ; <, n ↦ max{0, u_n}⟩, and ⟨ℕ; <, φ⟩ are undecidable, where (u_n)_{n ∈ ℕ} is any integer LRS with exactly two non-repeated dominant roots satisfying a non-degeneracy assumption, and φ is Euler’s totient function.

Submitted, 2026. 41 pages.

PDF © 2026 Toghrul Karimov, Joris Nieuwveld, and Joël Ouaknine.