Automata theory and algebraicity

Automata theory has given some interesting results to characterize algebraicity. I mention two of them, with references. It is by no way exhaustive.

1. An algebraic closure of $\mathbb F_q(t)$

Let $\mathbb F_q(t)$ be the rational function field over the finite field with $q$ elements, where $q=p^s$ for some prime $p$ and integer $s$. Let $\mathbb F_q[[t]]$ be the ring of formal power series over $\mathbb F_q$.

One can characterize the power series which are algebraic over $\mathbb F_q(t)$, that is roots of a monic polynomial with coefficients in $\mathbb F_q(t)$, using an automata-theoretic description.

Theorem (Christol [1]). A formal power series $\sum_{i=0}^{\infty} a_i t^i$ is algebraic over $\mathbb F_q(t)$ if and only if the sequence $\{a_i\}_{i=0}^\infty$ is $p$-automatic.

Actually, this method allows to give a description of an algebraic closure of $\mathbb F_q(t)$. It is known that the field of generalized power series of the form $$\sum_{i\in I} x_i t^i\text,$$ where $I$ is a well-ordered subset of $\mathbb Q$, contains an algebraic closure of $\mathbb F_q(t)$. Again, the generalized power series which are algebraic can be characterized using an automata-theoretic description.

Theorem (Kedlaya [2]). A generalized power series $\sum_{i\in I} a_i t^i$ is algebraic over $\mathbb F_q(t)$ if and only if the sequence $\{a_i\}_{i\in I}$ is $p$-quasi-automatic.

###2. Transcendental numbers

Automatic sequences are also used to characterize transcendental numbers. For instance,

Theorem (Adamczewski & Bugeaud [3]). Let $b$ be an integer $\ge 2$. Let $x\in\mathbb R$ and let $\mathbf x=\{x_i\}_{i=0}^\infty$ be the sequence of digits of its base-$b$ representation.

1. If $\mathbf x$ is ultimately periodic, then $x$ is rational;
2. If $\mathbf x$ is $b$-automatic (but not ultimately periodic), then $x$ is transcendental;
3. Else, $x$ is an algebraic irrational number.

Of course, the first item is a very classic result!

References.

[1] Gilles Christol. Ensembles presque périodiques k-reconnaissables. In Theoretical Computer Science 9(1), pp 141-145, 1979.

[2] Kiran S. Kedlaya. Finite automata and algebraic extensions of function fields. In Journal de théorie des nombres de Bordeaux 18, pp 379-420, 2006. arXiv:math/0410375.

[3] Boris Adamcweski, Yann Bugeaud. On the complexity of algebraic numbers I. Expansions in integer bases. In Annals of Mathematics 165(2), pp 547-565, 2007.

Automata theory and algebraicity

Automata theory has given some interesting results to characterize algebraicity. I mention two of them, with references. It is by no way exhaustive.

1. An algebraic closure of $\mathbb F_q(t)$

Let $\mathbb F_q(t)$ be the rational function field over the finite field with $q$ elements, where $q=p^s$ for some prime $p$ and integer $s$. Let $\mathbb F_q[[t]]$ be the ring of formal power series over $\mathbb F_q$.

One can characterize the power series which are algebraic over $\mathbb F_q(t)$, that is roots of a monic polynomial with coefficients in $\mathbb F_q(t)$, using an automata-theoretic description.

Theorem (Christol [1]). A formal power series $\sum_{i=0}^{\infty} a_i t^i$ is algebraic over $\mathbb F_q(t)$ if and only if the sequence $\{a_i\}_{i=0}^\infty$ is $p$-automatic.

Actually, this method allows to give a description of an algebraic closure of $\mathbb F_q(t)$. It is known that the field of generalized power series of the form $$\sum_{i\in I} x_i t^i\text,$$ where $I$ is a well-ordered subset of $\mathbb Q$, contains an algebraic closure of $\mathbb F_q(t)$. Again, the generalized power series which are algebraic can be characterized using an automata-theoretic description.

Theorem (Kedlaya [2]). A generalized power series $\sum_{i\in I} a_i t^i$ is algebraic over $\mathbb F_q(t)$ if and only if the sequence $\{a_i\}_{i\in I}$ is $p$-quasi-automatic.

2. Transcendental numbers

Automatic sequences are also used to characterize transcendental numbers. For instance,

Theorem (Adamczewski & Bugeaud [3]). Let $b$ be an integer $\ge 2$. Let $x\in\mathbb R$ and let $\mathbf x=\{x_i\}_{i=0}^\infty$ be the sequence of digits of its base-$b$ representation.

1. If $\mathbf x$ is ultimately periodic, then $x$ is rational;
2. If $\mathbf x$ is $b$-automatic (but not ultimately periodic), then $x$ is transcendental;
3. Else, $x$ is an algebraic irrational number.

Of course, the first item is a very classic result!

References.

[1] Gilles Christol. Ensembles presque périodiques k-reconnaissables. In Theoretical Computer Science 9(1), pp 141-145, 1979.

[2] Kiran S. Kedlaya. Finite automata and algebraic extensions of function fields. In Journal de théorie des nombres de Bordeaux 18, pp 379-420, 2006. arXiv:math/0410375.

[3] Boris Adamcweski, Yann Bugeaud. On the complexity of algebraic numbers I. Expansions in integer bases. In Annals of Mathematics 165(2), pp 547-565, 2007.