/-
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.BasicEntropy 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 0The 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
simp 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 := by b:ℕhb:1 ≤ bξ:ℝn:ℕ⊢ blockComplexity (digitSeq b ξ) n ≤ ↑b ^ n
simpa [blockComplexity, encard_digits] using
ENat.toENNReal_le.2 (Set.encard_le_encard (blocks_subset hb ξ 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$.
theorem isRichInBase_iff_blockComplexity {b : ℕ} (hb : 1 ≤ b) (ξ : ℝ) :
IsRichInBase b ξ ↔ ∀ n, blockComplexity (digitSeq b ξ) n = (b : ℝ≥0∞) ^ n := by b:ℕhb:1 ≤ bξ:ℝ⊢ IsRichInBase b ξ ↔ ∀ (n : ℕ), blockComplexity (digitSeq b ξ) n = ↑b ^ n
refine ⟨fun h n => ?_, fun h n w hw => ?_⟩ refine_1 b:ℕhb:1 ≤ bξ:ℝh:IsRichInBase b ξn:ℕ⊢ blockComplexity (digitSeq b ξ) n = ↑b ^ nrefine_2 b:ℕhb:1 ≤ bξ:ℝh:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n = ↑b ^ nn:ℕw:Fin n → ℕhw:∀ (j : Fin n), w j < b⊢ ∃ i, ∀ (j : Fin n), digitSeq b ξ (i + ↑j) = w j
· refine_1 b:ℕhb:1 ≤ bξ:ℝh:IsRichInBase b ξn:ℕ⊢ blockComplexity (digitSeq b ξ) n = ↑b ^ n have : {w : Fin n → ℕ | ∃ k, ∀ i, w i = digitSeq b ξ (k + i)} = {w | ∀ i, w i < b} :=
(blocks_subset hb ξ n).antisymm fun w hw => (h n w hw).imp fun k hk i => (hk i).symm refine_1 b:ℕhb:1 ≤ bξ:ℝh:IsRichInBase b ξn:ℕthis:{w | ∃ k, ∀ (i : Fin n), w i = digitSeq b ξ (k + ↑i)} = {w | ∀ (i : Fin n), w i < b}⊢ blockComplexity (digitSeq b ξ) n = ↑b ^ n
simp [blockComplexity, this, encard_digits] All goals completed! 🐙
· refine_2 b:ℕhb:1 ≤ bξ:ℝh:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n = ↑b ^ nn:ℕw:Fin n → ℕhw:∀ (j : Fin n), w j < b⊢ ∃ i, ∀ (j : Fin n), digitSeq b ξ (i + ↑j) = w j have hfin : {w : Fin n → ℕ | ∀ i, w i < b}.Finite :=
Set.finite_of_encard_eq_coe (encard_digits b n) refine_2 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}.Finite⊢ ∃ i, ∀ (j : Fin n), digitSeq b ξ (i + ↑j) = w j
have heq := (hfin.subset (blocks_subset hb ξ n)).eq_of_subset_of_encard_le
(blocks_subset hb ξ n)
(ENat.toENNReal_le.1 (by 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}.Finite⊢ ↑{w | ∀ (i : Fin n), w i < b}.encard ≤ ↑{w | ∃ k, ∀ (i : Fin n), w i = digitSeq b ξ (k + ↑i)}.encard refine_2 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 simpa [blockComplexity, encard_digits] using (h n).ge All goals completed! 🐙 refine_2 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))refine_2 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
obtain ⟨k, hk⟩ := (Set.ext_iff.1 heq w).2 hw refine_2 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
exact ⟨k, fun i => (hk i).symm⟩ 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 n
private theorem log_pow_div {b : ℕ} (hb : 1 ≤ b) {n : ℕ} (hn : n ≠ 0) :
((b : ℝ≥0∞) ^ n).log / (n : EReal) = (Real.log b : EReal) := by b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0⊢ (↑b ^ n).log / ↑n = ↑(Real.log ↑b)
have : (b : ℝ≥0∞) ^ n = ENNReal.ofReal ((b : ℝ) ^ n) := by
rw [ENNReal.ofReal_pow (by b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0⊢ 0 ≤ ↑b b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0⊢ ↑b ^ n = ENNReal.ofReal ↑b ^ n b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ (↑b ^ n).log / ↑n = ↑(Real.log ↑b) positivity All goals completed! 🐙 b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0⊢ ↑b ^ n = ENNReal.ofReal ↑b ^ n b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ (↑b ^ n).log / ↑n = ↑(Real.log ↑b))] b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0⊢ ↑b ^ n = ENNReal.ofReal ↑b ^ n b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ (↑b ^ n).log / ↑n = ↑(Real.log ↑b)
simp b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ (↑b ^ n).log / ↑n = ↑(Real.log ↑b) b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ (↑b ^ n).log / ↑n = ↑(Real.log ↑b)
rw [this, b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ (ENNReal.ofReal (↑b ^ n)).log / ↑n = ↑(Real.log ↑b) All goals completed! 🐙 ENNReal.log_ofReal_of_pos (by b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ 0 < ↑b ^ n All goals completed! 🐙 positivity All goals completed! 🐙 All goals completed! 🐙), Real.log_pow, b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ ↑(↑n * Real.log ↑b) / ↑n = ↑(Real.log ↑b) All goals completed! 🐙 ← EReal.coe_coe_eq_natCast, b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ ↑(↑n * Real.log ↑b) / ↑↑n = ↑(Real.log ↑b) All goals completed! 🐙
← EReal.coe_div, b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ ↑(↑n * Real.log ↑b / ↑n) = ↑(Real.log ↑b) All goals completed! 🐙 mul_div_cancel_left₀ _ (by b:ℕhb:1 ≤ bn:ℕhn:n ≠ 0this:↑b ^ n = ENNReal.ofReal (↑b ^ n)⊢ ↑n ≠ 0 All goals completed! 🐙 exact_mod_cast hn All goals completed! 🐙 All goals completed! 🐙)] All goals completed! 🐙The entropy of a base-$b$ expansion is at most $\log b$.
theorem _root_.Real.baseEntropy_le {b : ℕ} (hb : 1 ≤ b) (ξ : ℝ) :
Real.baseEntropy b ξ ≤ (Real.log b : EReal) := by b:ℕhb:1 ≤ bξ:ℝ⊢ Real.baseEntropy b ξ ≤ ↑(Real.log ↑b)
refine limsup_le_of_le (by b:ℕhb:1 ≤ bξ:ℝ⊢ IsCoboundedUnder (fun x1 x2 ↦ x1 ≤ x2) atTop fun n ↦ (blockComplexity (digitSeq b ξ) n).log / ↑n isBoundedDefault All goals completed! 🐙) (eventually_atTop.2 ⟨1, fun n hn => ?_⟩)
rw [← log_pow_div hb (n := n) (by b:ℕhb:1 ≤ bξ:ℝn:ℕhn:1 ≤ n⊢ n ≠ 0 b:ℕhb:1 ≤ bξ:ℝn:ℕhn:1 ≤ n⊢ (blockComplexity (digitSeq b ξ) n).log / ↑n ≤ (↑b ^ n).log / ↑n omega All goals completed! 🐙 b:ℕhb:1 ≤ bξ:ℝn:ℕhn:1 ≤ n⊢ (blockComplexity (digitSeq b ξ) n).log / ↑n ≤ (↑b ^ n).log / ↑n)] 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 (by b:ℕhb:1 ≤ bξ:ℝn:ℕhn:1 ≤ n⊢ 0 ≤ ↑n positivity 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$.
theorem IsRichInBase.baseEntropy_eq {b : ℕ} (hb : 1 ≤ b) {ξ : ℝ} (h : IsRichInBase b ξ) :
Real.baseEntropy b ξ = (Real.log b : EReal) := by b:ℕhb:1 ≤ bξ:ℝh:IsRichInBase b ξ⊢ Real.baseEntropy b ξ = ↑(Real.log ↑b)
refine Tendsto.limsup_eq (tendsto_atTop_of_eventually_const (i₀ := 1) fun n hn => ?_) b:ℕhb:1 ≤ bξ:ℝh:IsRichInBase b ξn:ℕhn:n ≥ 1⊢ (blockComplexity (digitSeq b ξ) n).log / ↑n = ↑(Real.log ↑b)
rw [(isRichInBase_iff_blockComplexity hb ξ).1 h n, b:ℕhb:1 ≤ bξ:ℝh:IsRichInBase b ξn:ℕhn:n ≥ 1⊢ (↑b ^ n).log / ↑n = ↑(Real.log ↑b) All goals completed! 🐙 log_pow_div hb (by b:ℕhb:1 ≤ bξ:ℝh:IsRichInBase b ξn:ℕhn:n ≥ 1⊢ n ≠ 0 All goals completed! 🐙 omega All goals completed! 🐙 All goals completed! 🐙)] 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 hbThe base-$b$ expansion of a number that is rich in base $b \ge 2$ is not eventually periodic.
theorem IsRichInBase.not_isEventuallyPeriodic {b : ℕ} (hb : 2 ≤ b) {ξ : ℝ}
(h : IsRichInBase b ξ) : ¬ IsEventuallyPeriodic (digitSeq b ξ) := fun hp ↦ by b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)⊢ False
obtain ⟨C, -, hC⟩ := hp.blockComplexity_le b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)C:ℕhC:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n ≤ ↑C⊢ False
have := hC C b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)C:ℕhC:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n ≤ ↑Cthis:blockComplexity (digitSeq b ξ) C ≤ ↑C⊢ False
rw [(isRichInBase_iff_blockComplexity (by b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)C:ℕhC:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n ≤ ↑Cthis:blockComplexity (digitSeq b ξ) C ≤ ↑C⊢ 1 ≤ b b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)C:ℕhC:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n ≤ ↑Cthis:↑b ^ C ≤ ↑C⊢ False omega All goals completed! 🐙 b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)C:ℕhC:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n ≤ ↑Cthis:↑b ^ C ≤ ↑C⊢ False) ξ).1 h C] at this 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 (by 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 (by b:ℕhb:2 ≤ bξ:ℝh:IsRichInBase b ξhp:IsEventuallyPeriodic (digitSeq b ξ)C:ℕhC:∀ (n : ℕ), blockComplexity (digitSeq b ξ) n ≤ ↑Cthis:↑b ^ C ≤ ↑C⊢ 1 < b omega 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