Séminaires SymPA à venir

Cobham’s theorem states that a set of natural numbers recognizable in two multiplicatively independent bases is ultimately periodic. A related question is how two automatic sets, each recognizable in one of the bases, can intersect. We show that if both sets are sparse, then their intersection is finite, and we give an explicit upper bound for its cardinality in terms of the bases and the automata recognizing these sets. The result also holds for subsets of . Taking the two sets to be equal also yields a quantitative refinement of the sparse case of the Cobham–Semenov theorem. This is joint work with Jason Bell.