/-
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 sectionAutomatic 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