Abstract

Let I be a finite set of integers and F be a finite set of maps of the form n ↦ k_{i} n + ℓ_{i} with integer coefficients. For an integer base k ≥ 2, we study the k-recognizability of the minimal set X of integers containing I and satisfying φ(X) ⊆ X for all φ ∈ F. We answer an open problem of Garth and Gouge by showing that X is k-recognizable when the multiplicative constants k_{i} are all powers of k and additive constants ℓ_{i} are chosen freely. Moreover, solving a conjecture of Allouche, Shallit and Skordev, we prove under some technical conditions that if two of the constants k_{i} are multiplicatively independent, then X is not k-recognizable for any k ≥ 2.