/- 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.Analysis.SpecialFunctions.Log.ENNRealLog public import Mathlib.Data.EReal.Inv public import Mathlib.Data.Real.ENatENNReal public import Mathlib.Data.Set.Card public import Mathlib.Order.LiminfLimsup

Block complexity and entropy of a sequence

The block complexity $p(n, a)$ of a sequence $a$ is the number of distinct blocks of $n$ consecutive terms of $a$. The entropy of $a$ is the exponential growth rate of $p(n, a)$.

An eventually periodic sequence has bounded block complexity and zero entropy. In particular $p(n, a) \le n$ for some $n \ge 1$. This is the easy direction of the Morse–Hedlund theorem.

References:

    [AS03] Allouche, Jean-Paul, and Jeffrey Shallit. "Automatic sequences: theory, applications, generalizations." Cambridge University Press, 2003. Chapter 10.

    [Bug12] Bugeaud, Yann. "Distribution modulo one and Diophantine approximation." Vol. 193. Cambridge University Press, 2012. Chapter 10.

Main definitions

    SymbolicDynamics.blockComplexity: the number of distinct blocks of length n of a sequence.

    SymbolicDynamics.blockEntropy: the entropy of a sequence.

    SymbolicDynamics.IsEventuallyPeriodic: a sequence is eventually periodic.

@[expose] public sectionopen Filteropen scoped ENNRealnamespace SymbolicDynamics

The block complexity $p(n, a)$ of a sequence $a$, that is, the number of distinct blocks $a_k a_{k+1} \cdots a_{k+n-1}$ of $n$ consecutive terms of $a$. It is ⊤ when $n \ge 1$ and $a$ takes infinitely many values.

noncomputable def blockComplexity {α : Type*} (a : ℕ → α) (n : ℕ) : ℝ≥0∞ := {w : Fin n → α | ∃ k, ∀ i, w i = a (k + i)}.encard

The entropy of a sequence $a$, $$E(a) = \lim_{n \to \infty} \frac{\log p(n, a)}{n}.$$ The limit exists because $n \mapsto \log p(n, a)$ is subadditive, so it agrees with the limsup used here. The value is ⊤ exactly when $a$ takes infinitely many values.

noncomputable def blockEntropy {α : Type*} (a : ℕ → α) : EReal := limsup (fun n : ℕ ↦ (blockComplexity a n).log / (n : EReal)) atTop

A constant sequence has exactly one block of each length.

α:Type u_1c:αn:ℕh:{w | ∃ k, ∀ (i : Fin n), w i = (fun x ↦ c) (k + ↑i)} = {fun x ↦ c}⊢ blockComplexity (fun x ↦ c) n = 1 All goals completed! 🐙

A constant sequence has zero entropy.

theorem blockEntropy_const {α : Type*} (c : α) : blockEntropy (fun _ ↦ c) = 0 := α:Type u_1c:α⊢ (blockEntropy fun x ↦ c) = 0 All goals completed! 🐙

Every sequence has at least one block of each length.

α:Type u_1a:ℕ → αn:ℕthis:{fun i ↦ a (0 + ↑i)} ⊆ {w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)}⊢ 1 ≤ blockComplexity a n All goals completed! 🐙

The block complexity is monotone: every block of length $n$ extends to a block of length $n + 1$.

theorem blockComplexity_mono {α : Type*} (a : ℕ → α) : Monotone (blockComplexity a) := α:Type u_1a:ℕ → α⊢ Monotone (blockComplexity a) α:Type u_1a:ℕ → αn:ℕ⊢ {w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)}.encard ≤ {w | ∃ k, ∀ (i : Fin (n + 1)), w i = a (k + ↑i)}.encard calc _ ≤ ((fun (w : Fin (n + 1) → α) (i : Fin n) ↦ w i.castSucc) '' {w | ∃ k, ∀ i, w i = a (k + i)}).encard := α:Type u_1a:ℕ → αn:ℕ⊢ {w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)}.encard ≤ ((fun w i ↦ w i.castSucc) '' {w | ∃ k, ∀ (i : Fin (n + 1)), w i = a (k + ↑i)}).encard α:Type u_1a:ℕ → αn:ℕ⊢ {w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)} ⊆ (fun w i ↦ w i.castSucc) '' {w | ∃ k, ∀ (i : Fin (n + 1)), w i = a (k + ↑i)} α:Type u_1a:ℕ → αn:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)⊢ w ∈ (fun w i ↦ w i.castSucc) '' {w | ∃ k, ∀ (i : Fin (n + 1)), w i = a (k + ↑i)} All goals completed! 🐙 _ ≤ _ := Set.encard_image_le _ _

A sequence $a$ is eventually periodic if there is a period $p > 0$ with $a(n + p) = a(n)$ for all sufficiently large $n$.

def IsEventuallyPeriodic {α : Type*} (a : ℕ → α) : Prop := ∃ p > 0, ∀ᶠ n in atTop, a (n + p) = a n

An eventually periodic sequence has bounded block complexity.

α:Type u_1a:ℕ → αp:ℕhp:p > 0hN✝:∀ᶠ (n : ℕ) in atTop, a (n + p) = a nN:ℕhN:∀ (b : ℕ), N ≤ b → a (b + p) = a bhper:∀ (m n : ℕ), N ≤ n → a (n + m * p) = a nn:ℕthis✝:{w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)} ⊆ (fun k i ↦ a (k + ↑i)) '' ↑(Finset.range (N + p))this:{w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)}.encard ≤ ↑(Finset.range (N + p)).card⊢ blockComplexity a n ≤ ↑(N + p) All goals completed! 🐙

An eventually periodic sequence satisfies $p(n, a) \le n$ for some $n \ge 1$. This is the easy direction of the Morse–Hedlund theorem.

theorem IsEventuallyPeriodic.exists_blockComplexity_le {α : Type*} {a : ℕ → α} (h : IsEventuallyPeriodic a) : ∃ n, 0 < n ∧ blockComplexity a n ≤ n := α:Type u_1a:ℕ → αh:IsEventuallyPeriodic a⊢ ∃ n, 0 < n ∧ blockComplexity a n ≤ ↑n α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑C⊢ ∃ n, 0 < n ∧ blockComplexity a n ≤ ↑n All goals completed! 🐙

An eventually periodic sequence has zero entropy.

α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑Chlim:Tendsto (fun n ↦ ↑(Real.log ↑C / ↑n)) atTop (nhds 0)n:ℕ⊢ (blockComplexity a n).log / ↑n ≤ (↑C).log / ↑n exact EReal.div_le_div_right_of_nonneg (α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑Chlim:Tendsto (fun n ↦ ↑(Real.log ↑C / ↑n)) atTop (nhds 0)n:ℕ⊢ 0 ≤ ↑n All goals completed! 🐙) (ENNReal.log_le_log (hle n)) α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑Chlim:Tendsto (fun n ↦ ↑(Real.log ↑C / ↑n)) atTop (nhds 0)x:ERealhx:∀ᶠ (n : ℕ) in atTop, (blockComplexity a n).log / ↑n ≤ x⊢ 0 ≤ x α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑Chlim:Tendsto (fun n ↦ ↑(Real.log ↑C / ↑n)) atTop (nhds 0)x:ERealhx:∀ᶠ (n : ℕ) in atTop, (blockComplexity a n).log / ↑n ≤ xn:ℕhn:(blockComplexity a n).log / ↑n ≤ x⊢ 0 ≤ x refine le_trans (EReal.div_nonneg ?_ (α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑Chlim:Tendsto (fun n ↦ ↑(Real.log ↑C / ↑n)) atTop (nhds 0)x:ERealhx:∀ᶠ (n : ℕ) in atTop, (blockComplexity a n).log / ↑n ≤ xn:ℕhn:(blockComplexity a n).log / ↑n ≤ x⊢ 0 ≤ ↑n All goals completed! 🐙)) hn All goals completed! 🐙end SymbolicDynamics