/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesForMathlib.Computability.AutomaticSequence public import FormalConjecturesForMathlib.NumberTheory.NormalNumber@[expose] public section

Automatic numbers

A real number is automatic in base b if its base-b digit sequence is generated by a finite automaton. Two readings of this are in use, and they differ:

    the classical one, that the digit sequence is b-automatic;

    the broad one, that the digit sequence is k-automatic for some k ≥ 2, which need not be b.

The broad reading is the weaker hypothesis on the number, so a theorem that rules out automatic numbers is stronger when stated with it. Adamczewski and Faverjon prove their two-base rigidity results in the broad form.

Only the digits after the radix point are used, as in NormalNumber.digitSeq. The integer part of a real number contributes finitely many digits, so it does not affect automaticity.

References:

    AF20 Adamczewski, Boris, and Colin Faverjon. "Mahler's method in several variables and finite automata." arXiv:2012.08283 (2020). Appendix A.

    [AS03] Allouche, Jean-Paul, and Jeffrey Shallit. "Automatic Sequences: Theory, Applications, Generalizations." Cambridge University Press, 2003.

Main definitions

    AutomaticSequence.IsAutomaticInBase: the classical reading.

    AutomaticSequence.IsBroadlyAutomaticInBase: the broad reading.

namespace AutomaticSequence

The base-b expansion of ξ is generated by a finite automaton, in the classical sense: its digit sequence is b-automatic.

def IsAutomaticInBase (b : ℕ) (ξ : ℝ) : Prop := IsAutomatic b (NormalNumber.digitSeq b ξ)

The base-b expansion of ξ is generated by a finite automaton, in the broad sense: its digit sequence is k-automatic for some k ≥ 2, not necessarily for k = b.

def IsBroadlyAutomaticInBase (b : ℕ) (ξ : ℝ) : Prop := ∃ k, 2 ≤ k ∧ IsAutomatic k (NormalNumber.digitSeq b ξ)

The classical reading implies the broad one, by taking k = b.

theorem IsAutomaticInBase.broad {b : ℕ} {ξ : ℝ} (hb : 2 ≤ b) (h : IsAutomaticInBase b ξ) : IsBroadlyAutomaticInBase b ξ := ⟨b, hb, h⟩end AutomaticSequence