Lethbridge Number Theory and Combinatorics Seminar: Seda Albayrak

  • Date: 09/26/2023
  • Time: 14:00
Seda Albayrak, University of Calgary

University of Lethbridge


Quantitative estimates for the size of an intersection of sparse automatic sets


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.

Other Information: 

Time: 1pm Pacific/ 2pm Mountain


Location: M1060 (Markin Hall) 


Online Via ZoomRegister for link