/- 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.Dynamics.SymbolicDynamics.BlockComplexity public import FormalConjecturesForMathlib.NumberTheory.NormalNumber public import Mathlib.Algebra.ContinuedFractions.Computation.Basic

Entropy of the expansions of a real number

The entropy of the continued fraction expansion of a real number $\xi$ and of its expansion in an integer base $b$. Both are the entropy SymbolicDynamics.blockEntropy of the sequence of digits.

A real number is rich in base $b$ if and only if its base-$b$ expansion has the maximal block complexity $p(n) = b^n$ for all $n$. Then its entropy is the maximal value $\log b$. In particular, this holds for numbers that are normal in base $b$.

References:

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

Main definitions

    Real.partQuot: the sequence of partial quotients of a real number.

    Real.cfEntropy: the entropy of the continued fraction expansion of a real number.

    Real.baseEntropy: the entropy of the base b expansion of a real number.

Main statements

    NormalNumber.isRichInBase_iff_blockComplexity: a number is rich in base b if and only if its expansion has block complexity b ^ n for all n.

    Real.baseEntropy_le: the entropy of a base b expansion is at most log b.

    NormalNumber.IsRichInBase.baseEntropy_eq, NormalNumber.IsNormalInBase.baseEntropy_eq: rich and normal numbers have entropy log b.

    NormalNumber.IsRichInBase.not_isEventuallyPeriodic: the expansion of a rich number is not eventually periodic.

@[expose] public sectionopen Filter SymbolicDynamicsopen scoped ENNRealnamespace Real

The sequence $(c_n)_{n \ge 1}$ of partial quotients of the continued fraction expansion $\xi = [c_0; c_1, c_2, \ldots]$, indexed from $0$. The integer part $c_0$ is not part of the sequence. The expansion of an irrational number never terminates, so the default value 0 is never used for such $\xi$.

noncomputable def partQuot (ξ : ℝ) (n : ℕ) : ℝ := ((GenContFract.of ξ).partDens.get? n).getD 0

The entropy $E(\xi)$ of the continued fraction expansion of $\xi$.

noncomputable def cfEntropy (ξ : ℝ) : EReal := blockEntropy (partQuot ξ)

The entropy $E(\xi, b)$ of the base $b$ expansion of $\xi$.

noncomputable def baseEntropy (b : ℕ) (ξ : ℝ) : EReal := blockEntropy (NormalNumber.digitSeq b ξ)end Realnamespace NormalNumberprivate theorem blocks_subset {b : ℕ} (hb : 1 ≤ b) (ξ : ℝ) (n : ℕ) : {w : Fin n → ℕ | ∃ k, ∀ i, w i = digitSeq b ξ (k + i)} ⊆ {w | ∀ i, w i < b} := fun _ ⟨_, hk⟩ i => hk i ▸ Nat.mod_lt _ hbb:ℕn:ℕthis:{w | ∀ (i : Fin n), w i < b} = ↑(Fintype.piFinset fun x ↦ Finset.range b)⊢ ↑(∏ i, (Finset.range b).card) = ↑b ^ n All goals completed! 🐙

A base-$b$ expansion has at most $b^n$ distinct blocks of length $n$.

theorem blockComplexity_digitSeq_le {b : ℕ} (hb : 1 ≤ b) (ξ : ℝ) (n : ℕ) : blockComplexity (digitSeq b ξ) n ≤ (b : ℝ≥0∞) ^ n := b:ℕhb:1 ≤ bξ:ℝn:ℕ⊢ blockComplexity (digitSeq b ξ) n ≤ ↑b ^ n All goals completed! 🐙

A real number is rich in base $b$ if and only if its base-$b$ expansion has $b^n$ distinct blocks of length $n$ for every $n$.

b:ℕhb:1 ≤ bξ:ℝh:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n = ↑b ^ nn:ℕw:Fin n → ℕhw:∀ (j : Fin n), w j < bhfin:{w | ∀ (i : Fin n), w i < b}.Finiteheq:{w | ∃ k, ∀ (i : Fin n), w i = digitSeq b ξ (k + ↑i)} = {w | ∀ (i : Fin n), w i < b}⊢ ∃ i, ∀ (j : Fin n), digitSeq b ξ (i + ↑j) = w j b:ℕhb:1 ≤ bξ:ℝh:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n = ↑b ^ nn:ℕw:Fin n → ℕhw:∀ (j : Fin n), w j < bhfin:{w | ∀ (i : Fin n), w i < b}.Finiteheq:{w | ∃ k, ∀ (i : Fin n), w i = digitSeq b ξ (k + ↑i)} = {w | ∀ (i : Fin n), w i < b}k:ℕhk:∀ (i : Fin n), w i = digitSeq b ξ (k + ↑i)⊢ ∃ i, ∀ (j : Fin n), digitSeq b ξ (i + ↑j) = w j All goals completed! 🐙

A number that is normal in base $b$ has $b^n$ distinct blocks of length $n$ in its base-$b$ expansion.

theorem IsNormalInBase.blockComplexity_eq {b : ℕ} (hb : 1 ≤ b) {ξ : ℝ} (h : IsNormalInBase b ξ) (n : ℕ) : blockComplexity (digitSeq b ξ) n = (b : ℝ≥0∞) ^ n := (isRichInBase_iff_blockComplexity hb ξ).1 h.isRichInBase nAll goals completed! 🐙

The entropy of a base-$b$ expansion is at most $\log b$.

b:ℕhb:1 ≤ bξ:ℝn:ℕhn:1 ≤ n⊢ (blockComplexity (digitSeq b ξ) n).log / ↑n ≤ (↑b ^ n).log / ↑n exact EReal.div_le_div_right_of_nonneg (b:ℕhb:1 ≤ bξ:ℝn:ℕhn:1 ≤ n⊢ 0 ≤ ↑n All goals completed! 🐙) (ENNReal.log_le_log (blockComplexity_digitSeq_le hb ξ n))

A number that is rich in base $b$ has base-$b$ entropy $\log b$.

All goals completed! 🐙

A number that is normal in base $b$ has base-$b$ entropy $\log b$.

theorem IsNormalInBase.baseEntropy_eq {b : ℕ} (hb : 1 ≤ b) {ξ : ℝ} (h : IsNormalInBase b ξ) : Real.baseEntropy b ξ = (Real.log b : EReal) := h.isRichInBase.baseEntropy_eq hb

The base-$b$ expansion of a number that is rich in base $b \ge 2$ is not eventually periodic.

b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)C:ℕhC:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n ≤ ↑Cthis:↑b ^ C ≤ ↑C⊢ False exact this.not_gt (b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)C:ℕhC:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n ≤ ↑Cthis:↑b ^ C ≤ ↑C⊢ ↑C < ↑b ^ C exact_mod_cast Nat.lt_pow_self (b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)C:ℕhC:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n ≤ ↑Cthis:↑b ^ C ≤ ↑C⊢ 1 < b All goals completed! 🐙))

The base-$b$ expansion of a number that is normal in base $b \ge 2$ is not eventually periodic.

theorem IsNormalInBase.not_isEventuallyPeriodic {b : ℕ} (hb : 2 ≤ b) {ξ : ℝ} (h : IsNormalInBase b ξ) : ¬ IsEventuallyPeriodic (digitSeq b ξ) := h.isRichInBase.not_isEventuallyPeriodic hbend NormalNumber