Submission date: 30 June 2020

Abstract:

The problem of characterizing which automatic sets of integers are stable is here initiated. Given a positive integer d and a subset A\subseteq ℤ^m whose set of representations base d is sparse and recognized by a finite automaton, a necessary condition is found for x+y in A to be a stable formula in Th(ℤ,+,A). Combined with a theorem of Moosa and Scanlon this gives a combinatorial characterization of the d-sparse A ⊆ &ZOpf;^m such that (ℤ,+,A) is stable. This characterization is in terms of what were called “F-sets” by Moosa and Scanlon and “elementary p-nested sets” by Derksen. For A\subseteq ⊆ ℤ d-automatic but not d-sparse, it is shown that if x+y in A is stable then finitely many translates of A cover ℤ. Automata-theoretic methods are also used to produce some NIP expansions of (ℤ,+), in particular the expansion by the monoid (d^ℕ, ×).

Mathematics Subject Classification: 03C45 (Primary) 68Q45, 11B85 (Secondary)

Keywords and phrases: NIP, Automatic sets

Full text arXiv 2007.00070: pdf, ps.