A strong version of Cobham's theorem

Abstract: Let $k,l>1$ be two multiplicatively independent integers. A subset $X$ of $\mathbb{N}^n$ is $k$-recognizable if the set of $k$-ary representations of $X$ is recognized by some finite automaton. Cobham’s famous theorem states that a subset of the natural numbers is both $k$-recognizable and $l$-recognizable if and only if it is Presburger-definable (or equivalently: semilinear). We show the following strengthening. Let $X$ be $k$-recognizable, let $Y$ be $l$-recognizable such that both $X$ and $Y$ are not Presburger-definable. Then the first-order logical theory of $(\mathbb{N},+,X,Y)$ is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of $(\mathbb{N},+,X)$ is decidable. Our work strengthens and depends on earlier work of Villemaire and Bès.

The essence of Cobham's theorem is that recognizability depends strongly on the choice of the base $k$. Our results strengthens this: two non-Presburger definable sets that are recognizable in multiplicatively independent bases, are not only distinct, but together computationally intractable over Presburger arithmetic.

This is joint work with Christian Schulz.

dynamical systemsnumber theory

Audience: researchers in the topic

( slides )

---

One World Numeration seminar

Series comments: Description: Online seminar on numeration systems and related topics

For questions or subscribing to the mailing list, contact the organisers at numeration@irif.fr

---