Lethbridge Number Theory and Combinatorics Seminar: Seda Albayrak

In 1979, Erdős conjectured that for k≥9, 2k 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 ℓ are two multiplicatively independent natural numbers then a subset of the natural numbers that is both k- and ℓ-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 ℕd and a sparse ℓ-automatic subset of ℕ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.