SFU NTAG Seminar: Seda Albayrak

In this talk, I will talk about use of automata theory in answering problems in number theory. In 1844, Catalan conjectured that the set consisting of natural numbers of the form $2^n+1$, $n \ge 0$ and the set consisting of powers of $3$ has finite intersection. In fact, we can answer such question in more generality, that is, instead of $2$ and $3$, we can show this for $k$ and $\ell$ that are multiplicatively independent (meaning if $k^a=\ell^b$, then $a=b=0$). In automata-theoretic terms, these sets described above are sparse $2$-automatic and sparse $3$-automatic sets, respectively. In fact, a sparse $k$-automatic set can be more complicated than having elements that are of the form $k^n$ or $k^n+1$, and hence, we are answering an even more general question. Moreover, we also prove our result in a multidimensional setting in line with the existing results in the theory of formal languages and finite automata. We show that the intersection of a sparse $k$-automatic subset of $\mathbb{N}^d$ and a sparse $\ell$-automatic subset of $\mathbb{N}^d$ is finite and we give effectively computable upper bounds on the size of the intersection in terms of data from the automata that accept these sets. We will also see how all of this is related to a conjecture of Erdös.