/-
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.LiminfLimsupBlock 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)) atTopA 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
simp only [blockComplexity, h, Set.encard_singleton, ENat.toENNReal_one] All goals completed! 🐙A constant sequence has zero entropy.
theorem blockEntropy_const {α : Type*} (c : α) : blockEntropy (fun _ ↦ c) = 0 := by α:Type u_1c:α⊢ (blockEntropy fun x ↦ c) = 0
simp [blockEntropy, blockComplexity_const] All goals completed! 🐙Every sequence has at least one block of each length.
theorem one_le_blockComplexity {α : Type*} (a : ℕ → α) (n : ℕ) : 1 ≤ blockComplexity a n := by α:Type u_1a:ℕ → αn:ℕ⊢ 1 ≤ blockComplexity a n
have : ({fun i : Fin n ↦ a (0 + i)} : Set _) ⊆ {w : Fin n → α | ∃ k, ∀ i, w i = a (k + i)} := by
rintro w rfl α:Type u_1a:ℕ → αn:ℕ⊢ (fun i ↦ a (0 + ↑i)) ∈ {w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)} α:Type u_1a:ℕ → αn:ℕthis:{fun i ↦ a (0 + ↑i)} ⊆ {w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)}⊢ 1 ≤ blockComplexity a n
exact ⟨0, fun i ↦ rfl⟩ α:Type u_1a:ℕ → αn:ℕthis:{fun i ↦ a (0 + ↑i)} ⊆ {w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)}⊢ 1 ≤ blockComplexity a n α:Type u_1a:ℕ → αn:ℕthis:{fun i ↦ a (0 + ↑i)} ⊆ {w | ∃ k, ∀ (i : Fin n), w i = a (k + ↑i)}⊢ 1 ≤ blockComplexity a n
simpa [blockComplexity] using ENat.toENNReal_le.2 (Set.encard_le_encard this) 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) := by α:Type u_1a:ℕ → α⊢ Monotone (blockComplexity a)
refine monotone_nat_of_le_succ fun n ↦ ENat.toENNReal_le.2 ?_ α: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 := by α: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
refine Set.encard_le_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)}
rintro w ⟨k, hk⟩ α: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)}
exact ⟨fun i ↦ a (k + i), ⟨k, fun i ↦ rfl⟩, funext fun i ↦ (hk i).symm⟩ 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 nAn eventually periodic sequence has bounded block complexity.
theorem IsEventuallyPeriodic.blockComplexity_le {α : Type*} {a : ℕ → α}
(h : IsEventuallyPeriodic a) : ∃ C : ℕ, 0 < C ∧ ∀ n, blockComplexity a n ≤ C := by α:Type u_1a:ℕ → αh:IsEventuallyPeriodic a⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C
obtain ⟨p, hp, hN⟩ := h α:Type u_1a:ℕ → αp:ℕhp:p > 0hN:∀ᶠ (n : ℕ) in atTop, a (n + p) = a n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C
obtain ⟨N, hN⟩ := eventually_atTop.1 hN α:Type u_1a:ℕ → αp:ℕhp:p > 0hN✝:∀ᶠ (n : ℕ) in atTop, a (n + p) = a nN:ℕhN:∀ (b : ℕ), N ≤ b → a (b + p) = a b⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C
have hper (m n : ℕ) (hn : N ≤ n) : a (n + m * p) = a n := by
induction m with
| zero => zero α:Type u_1a:ℕ → αp:ℕhp:p > 0hN✝:∀ᶠ (n : ℕ) in atTop, a (n + p) = a nN:ℕhN:∀ (b : ℕ), N ≤ b → a (b + p) = a bn:ℕhn:N ≤ n⊢ a (n + 0 * p) = a n α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C simp All goals completed! 🐙 α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C
| succ m ih => succ α:Type u_1a:ℕ → αp:ℕhp:p > 0hN✝:∀ᶠ (n : ℕ) in atTop, a (n + p) = a nN:ℕhN:∀ (b : ℕ), N ≤ b → a (b + p) = a bn:ℕhn:N ≤ nm:ℕih:a (n + m * p) = a n⊢ a (n + (m + 1) * p) = a n α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C rw [add_mul, succ α:Type u_1a:ℕ → αp:ℕhp:p > 0hN✝:∀ᶠ (n : ℕ) in atTop, a (n + p) = a nN:ℕhN:∀ (b : ℕ), N ≤ b → a (b + p) = a bn:ℕhn:N ≤ nm:ℕih:a (n + m * p) = a n⊢ a (n + (m * p + 1 * p)) = a n α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C one_mul, succ α:Type u_1a:ℕ → αp:ℕhp:p > 0hN✝:∀ᶠ (n : ℕ) in atTop, a (n + p) = a nN:ℕhN:∀ (b : ℕ), N ≤ b → a (b + p) = a bn:ℕhn:N ≤ nm:ℕih:a (n + m * p) = a n⊢ a (n + (m * p + p)) = a n α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C ← add_assoc, succ α:Type u_1a:ℕ → αp:ℕhp:p > 0hN✝:∀ᶠ (n : ℕ) in atTop, a (n + p) = a nN:ℕhN:∀ (b : ℕ), N ≤ b → a (b + p) = a bn:ℕhn:N ≤ nm:ℕih:a (n + m * p) = a n⊢ a (n + m * p + p) = a n α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C hN _ (by α:Type u_1a:ℕ → αp:ℕhp:p > 0hN✝:∀ᶠ (n : ℕ) in atTop, a (n + p) = a nN:ℕhN:∀ (b : ℕ), N ≤ b → a (b + p) = a bn:ℕhn:N ≤ nm:ℕih:a (n + m * p) = a n⊢ N ≤ n + m * p α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C nlinarith All goals completed! 🐙 α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C), ih succ α:Type u_1a:ℕ → αp:ℕhp:p > 0hN✝:∀ᶠ (n : ℕ) in atTop, a (n + p) = a nN:ℕhN:∀ (b : ℕ), N ≤ b → a (b + p) = a bn:ℕhn:N ≤ nm:ℕih:a (n + m * p) = a n⊢ a n = a n α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C] α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C α: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 n⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C
refine ⟨N + p, by α: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 n⊢ 0 < N + p omega All goals completed! 🐙, fun n ↦ ?_⟩
have : {w : Fin n → α | ∃ k, ∀ i, w i = a (k + i)} ⊆
(fun k (i : Fin n) ↦ a (k + i)) '' ↑(Finset.range (N + p)) := by α:Type u_1a:ℕ → αh:IsEventuallyPeriodic a⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ), blockComplexity a n ≤ ↑C α: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))⊢ blockComplexity a n ≤ ↑(N + p)
rintro w ⟨k, hk⟩ α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)⊢ w ∈ (fun k i ↦ a (k + ↑i)) '' ↑(Finset.range (N + p)) α: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))⊢ blockComplexity a n ≤ ↑(N + p)
by_cases hk' : k < N + p pos α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':k < N + p⊢ w ∈ (fun k i ↦ a (k + ↑i)) '' ↑(Finset.range (N + p))neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + p⊢ w ∈ (fun k i ↦ a (k + ↑i)) '' ↑(Finset.range (N + p)) α: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))⊢ blockComplexity a n ≤ ↑(N + p)
· pos α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':k < N + p⊢ w ∈ (fun k i ↦ a (k + ↑i)) '' ↑(Finset.range (N + p)) α: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))⊢ blockComplexity a n ≤ ↑(N + p) exact ⟨k, by α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':k < N + p⊢ k ∈ ↑(Finset.range (N + p)) α: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))⊢ blockComplexity a n ≤ ↑(N + p) simpa using hk' All goals completed! 🐙 α: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))⊢ blockComplexity a n ≤ ↑(N + p), funext fun i ↦ (hk i).symm⟩
· neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + p⊢ w ∈ (fun k i ↦ a (k + ↑i)) '' ↑(Finset.range (N + p)) α: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))⊢ blockComplexity a n ≤ ↑(N + p) have h1 := Nat.mod_add_div' (k - N) p neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - N⊢ w ∈ (fun k i ↦ a (k + ↑i)) '' ↑(Finset.range (N + p)) α: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))⊢ blockComplexity a n ≤ ↑(N + p)
have h2 := Nat.mod_lt (k - N) hp neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < p⊢ w ∈ (fun k i ↦ a (k + ↑i)) '' ↑(Finset.range (N + p)) α: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))⊢ blockComplexity a n ≤ ↑(N + p)
refine ⟨N + (k - N) % p, Finset.mem_coe.2 (Finset.mem_range.2 (by α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < p⊢ N + (k - N) % p < N + p α: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))⊢ blockComplexity a n ≤ ↑(N + p) omega All goals completed! 🐙 α: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))⊢ blockComplexity a n ≤ ↑(N + p))),
funext fun i ↦ ?_⟩
dsimp only neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < pi:Fin n⊢ a (N + (k - N) % p + ↑i) = w i α: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))⊢ blockComplexity a n ≤ ↑(N + p)
rw [hk, neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < pi:Fin n⊢ a (N + (k - N) % p + ↑i) = a (k + ↑i) neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < pi:Fin n⊢ a (N + (k - N) % p + ↑i + (k - N) / p * p) = a (k + ↑i) α: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))⊢ blockComplexity a n ≤ ↑(N + p) ← hper ((k - N) / p) (N + (k - N) % p + i) (by α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < pi:Fin n⊢ N ≤ N + (k - N) % p + ↑ineg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < pi:Fin n⊢ a (N + (k - N) % p + ↑i + (k - N) / p * p) = a (k + ↑i) α: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))⊢ blockComplexity a n ≤ ↑(N + p) omega All goals completed! 🐙neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < pi:Fin n⊢ a (N + (k - N) % p + ↑i + (k - N) / p * p) = a (k + ↑i) α: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))⊢ blockComplexity a n ≤ ↑(N + p))]neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < pi:Fin n⊢ a (N + (k - N) % p + ↑i + (k - N) / p * p) = a (k + ↑i) α: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))⊢ blockComplexity a n ≤ ↑(N + p)
congr 1 neg α: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:ℕw:Fin n → αk:ℕhk:∀ (i : Fin n), w i = a (k + ↑i)hk':¬k < N + ph1:(k - N) % p + (k - N) / p * p = k - Nh2:(k - N) % p < pi:Fin n⊢ N + (k - N) % p + ↑i + (k - N) / p * p = k + ↑i α: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))⊢ blockComplexity a n ≤ ↑(N + p)
omega α: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))⊢ blockComplexity a n ≤ ↑(N + p) α: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))⊢ blockComplexity a n ≤ ↑(N + p)
have := (Set.encard_le_encard this).trans (Set.encard_image_le _ _) α: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))).encard⊢ blockComplexity a n ≤ ↑(N + p)
rw [Set.encard_coe_eq_coe_finsetCard α: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) α: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)] at this α: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)
simpa [blockComplexity] using ENat.toENNReal_le.2 this 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 := by α:Type u_1a:ℕ → αh:IsEventuallyPeriodic a⊢ ∃ n, 0 < n ∧ blockComplexity a n ≤ ↑n
obtain ⟨C, hC, hle⟩ := h.blockComplexity_le α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑C⊢ ∃ n, 0 < n ∧ blockComplexity a n ≤ ↑n
exact ⟨C, hC, hle C⟩ All goals completed! 🐙An eventually periodic sequence has zero entropy.
theorem IsEventuallyPeriodic.blockEntropy_eq_zero {α : Type*} {a : ℕ → α}
(h : IsEventuallyPeriodic a) : blockEntropy a = 0 := by α:Type u_1a:ℕ → αh:IsEventuallyPeriodic a⊢ blockEntropy a = 0
obtain ⟨C, hC, hle⟩ := h.blockComplexity_le α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑C⊢ blockEntropy a = 0
have hlim : Tendsto (fun n : ℕ ↦ ((Real.log C / n : ℝ) : EReal)) atTop (nhds 0) :=
(continuous_coe_real_ereal.tendsto 0).comp (tendsto_const_div_atTop_nhds_zero_nat _) α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑Chlim:Tendsto (fun n ↦ ↑(Real.log ↑C / ↑n)) atTop (nhds 0)⊢ blockEntropy a = 0
refine le_antisymm ((limsup_le_limsup (Eventually.of_forall fun n ↦ ?_)).trans_eq
hlim.limsup_eq) (le_limsup_of_le (by α:Type u_1a:ℕ → αh:IsEventuallyPeriodic aC:ℕhC:0 < Chle:∀ (n : ℕ), blockComplexity a n ≤ ↑Chlim:Tendsto (fun n ↦ ↑(Real.log ↑C / ↑n)) atTop (nhds 0)⊢ IsBoundedUnder (fun x1 x2 ↦ x1 ≤ x2) atTop fun n ↦ (blockComplexity a n).log / ↑n isBoundedDefault All goals completed! 🐙) fun x hx ↦ ?_)
· refine_1 α: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 ≤ ↑(Real.log ↑C / ↑n) rw [EReal.coe_div, refine_1 α: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 ≤ ↑(Real.log ↑C) / ↑↑n refine_1 α: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 EReal.coe_coe_eq_natCast, refine_1 α: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 ≤ ↑(Real.log ↑C) / ↑n refine_1 α: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 ← ENNReal.log_ofReal_of_pos (by α: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 < ↑Crefine_1 α: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 positivity All goals completed! 🐙refine_1 α: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),
ENNReal.ofReal_natCast refine_1 α: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 / ↑nrefine_1 α: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]refine_1 α: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 (by α: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 positivity All goals completed! 🐙) (ENNReal.log_le_log (hle n))
· refine_2 α: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 obtain ⟨n, hn⟩ := hx.exists refine_2 α: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 ?_ (by α: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 positivity All goals completed! 🐙)) hn
simpa using ENNReal.log_le_log (one_le_blockComplexity a n) All goals completed! 🐙end SymbolicDynamics