Quantitative Estimates for the Size of an Intersection of Sparse Automatic Sets

Abstract: In 1979, Erdős conjectured that for $k \geq 9$, $2^k$ is not the sum of distinct powers of $3$. That is, the set of powers of two (which is $2$-automatic) and the $3$-automatic set consisting of numbers whose ternary expansions omit $2$ has finite intersection. In the theory of automata, a theorem of Cobham (1969) says that if $k$ and $\ell$ are two multiplicatively independent natural numbers then a subset of the natural numbers that is both $k$- and $\ell$-automatic is eventually periodic. A multidimensional extension was later given by Semenov (1977). Motivated by Erdős' conjecture and in light of Cobham’s theorem, we give a quantitative version of the Cobham-Semenov theorem for sparse automatic sets, showing 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. Moreover, we give effectively computable upper bounds on the size of the intersection in terms of data from the automata that accept these sets.

combinatoricsnumber theory

Audience: researchers in the topic

( paper )

Lethbridge number theory and combinatorics seminar