/- 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 Mathlib.Data.Set.Finite.Basic@[expose] public section

Automatic sequences

A sequence a : ℕ → α is k-automatic if it is the output of a deterministic finite automaton fed the base-k digits of the index. By the kernel criterion of [Eil74] this holds exactly when the k-kernel of a is finite, and that is the definition used here: it needs no automaton, and finiteness of the kernel is what proofs about automatic sequences consume.

For k ≥ 2, IsAutomatic k a already forces the range of a to be finite, by AutomaticSequence.IsAutomatic.finite_range. For k ≤ 1 the k-kernel of a is {a}, so every sequence is k-automatic.

References:

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

    [Eil74] Eilenberg, Samuel. "Automata, Languages, and Machines. Vol. A." Academic Press, 1974. Chapter V, Proposition 3.3.

Main definitions

    AutomaticSequence.kKernel: the k-kernel of a sequence.

    AutomaticSequence.IsAutomatic: k-automaticity, as finiteness of the k-kernel.

namespace AutomaticSequencevariable {α : Type*}

The k-kernel of a sequence a is the set of subsequences $(a_{k^e n + r})_{n \ge 0}$ with $e \ge 0$ and $0 \le r < k^e$.

def kKernel (k : ℕ) (a : ℕ → α) : Set (ℕ → α) := {b | ∃ e r : ℕ, r < k ^ e ∧ b = fun n => a (k ^ e * n + r)}

A sequence is a member of its own k-kernel, via e = r = 0.

theorem self_mem_kKernel (k : ℕ) (a : ℕ → α) : a ∈ kKernel k a := ⟨0, 0, α:Type u_1k:ℕa:ℕ → α⊢ 0 < k ^ 0 All goals completed! 🐙, α:Type u_1k:ℕa:ℕ → α⊢ a = fun n ↦ a (k ^ 0 * n + 0) All goals completed! 🐙⟩

A sequence a is k-automatic if its k-kernel is finite. By [Eil74] this is equivalent to a being generated by a deterministic finite automaton reading the base-k digits of the index.

def IsAutomatic (k : ℕ) (a : ℕ → α) : Prop := (kKernel k a).Finite

A k-automatic sequence with k ≥ 2 takes finitely many values: a m is the value at 0 of the kernel element n ↦ a (k ^ m * n + m).

theorem IsAutomatic.finite_range {k : ℕ} {a : ℕ → α} (hk : 2 ≤ k) (h : IsAutomatic k a) : (Set.range a).Finite := (h.image fun b => b 0).subset <| Set.range_subset_iff.2 fun m => ⟨fun n => a (k ^ m * n + m), ⟨m, m, Nat.lt_pow_self hk, rfl⟩, α:Type u_1k:ℕa:ℕ → αhk:2 ≤ kh:IsAutomatic k am:ℕ⊢ ((fun b ↦ b 0) fun n ↦ a (k ^ m * n + m)) = a m All goals completed! 🐙⟩

The k-kernel of a constant sequence is a singleton.

@[simp] theorem kKernel_const (k : ℕ) (c : α) : kKernel k (fun _ : ℕ => c) = {fun _ => c} := α:Type u_1k:ℕc:α⊢ (kKernel k fun x ↦ c) = {fun x ↦ c} α:Type u_1k:ℕc:αb:ℕ → α⊢ (b ∈ kKernel k fun x ↦ c) ↔ b ∈ {fun x ↦ c} α:Type u_1k:ℕc:αb:ℕ → α⊢ (∃ e, ∃ r < k ^ e, b = fun n ↦ c) ↔ b = fun n ↦ c exact ⟨fun ⟨_, _, _, hb⟩ => hb, fun hb => ⟨0, 0, α:Type u_1k:ℕc:αb:ℕ → αhb:b = fun n ↦ c⊢ 0 < k ^ 0 All goals completed! 🐙, hb⟩⟩

A constant sequence is k-automatic.

α:Type u_1k:ℕc:α⊢ {fun x ↦ c}.Finite All goals completed! 🐙end AutomaticSequence