Writing numbers in multiple bases: the viewpoint of finite automata

Abstract: Although binary and decimal representations of numbers coexist seamlessly in our digital world, these changes of basis conceal profound mysteries. Consider, for example, the following statements, both currently out of reach:
- The date when Trump will leave the US presidency appears in the decimal expansion of every sufficiently large power of 2;
- The real number whose binary expansion is the characteristic sequence of powers of 3 contains the pattern 1312 infinitely often in its decimal expansion.
Both statements rely on the heuristic that expansions in multiplicatively independent bases (such as 2 and 10) should share no common structure. Furstenberg captured this heuristic through a series of results and conjectures concerning the joint behavior of the dynamical systems ×p and ×q on the torus.

In this talk, we approach this question from the perspective pioneered by Turing, Hartmanis, Stearns, and Cobham: that of computational complexity. Powers of 2 are particularly easy to recognize from their base-2 expansion—a task achievable by a finite automaton. Cobham's theorem then implies that no automaton can recognize them from their decimal expansion. Similarly, one can readily construct a finite automaton with output that produces the binary expansion of the real number introduced above. Whether there exists another automaton producing its decimal expansion remained open until recently.

In this talk, we present how this question has been solved using a transcendence method known as Mahler's method. While this approach yields a new proof and an algebraic generalization of Cobham's theorem, its main contribution is the following statement: no irrational real number has expansions in two multiplicatively independent bases that can both be produced by finite automata.

dynamical systemsnumber theory

Audience: researchers in the topic

( paper | 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

---