The Fibonacci path counts dominate all powers of the golden ratio:
ProvedSubmultiplicativeSearchEntropy.gold_pow_le_fibaether-catalogbridges
The Fibonacci path counts dominate all powers of the golden ratio:
φ ^ n ≤ Fₙ₊₃, obtained here from Fekete's lemma applied to the automaton.
theorem SubmultiplicativeSearchEntropy.gold_pow_le_fib(n : ℕ) : Real.goldenRatio ^ n ≤ (Nat.fib (n + 3) : ℝ) := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Bridges/SubmultiplicativeSearchEntropy.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Bridges/SubmultiplicativeSearchEntropy.lean
import Mathlib
import Definitions.Def_Bridges_SubmultiplicativeSearchEntropy
/-! # Submultiplicative search entropy and the Perron root
A bridge between three areas:
* **Combinatorics of proof search** — counting the successful prefixes of a search language;
* **Real analysis (Fekete's subadditive lemma)** — existence of the normalized logarithmic
growth rate and its identification with the infimum of the finite-scale rates;
* **Linear algebra of nonnegative matrices (Perron theory)** — the growth rate of a
finite-state pruned search equals `log ρ`, where `ρ` is the Perron eigenvalue of the
automaton's transition matrix.
-/
open Filter Topology Set
open SubmultiplicativeSearchEntropy
/-! ## Part 1 — Submultiplicative counting functions and Fekete's lemma -/
open SearchProfile
variable (P : SearchProfile)
/-! ## Part 2 — Nonnegative matrices: path counts of a finite-state pruning automaton -/
variable {k : ℕ} {A : Matrix (Fin k) (Fin k) ℝ}
/-! ### Perron eigenvectors control path counts -/
variable {r : ℝ}
/-! ## Part 3 — The growth rate of a Perron-controlled search equals `log r` -/
/-! ## Part 4 — The bridge theorem: Perron root = entropy = dimension -/
variable {k : ℕ} {A : Matrix (Fin k) (Fin k) ℝ} {r : ℝ}
/-! ## Part 5 — Worked instances
### 5a. Uniform self-similar search: the classical similarity dimension
A `1 × 1` transition matrix `!![s]` models a uniformly self-similar problem in which exactly `s`
of the branches at each node extend to a proof; the bridge recovers the classical similarity
dimension `log s / log b` of the earlier scalar theory. -/
variable {s : ℝ}
/-! ### 5b. The Fibonacci pruning automaton and the golden ratio
Inside the binary search tree, prune every branch that would use two "expensive" inference steps
in a row. The accepted paths are counted by the transition matrix `!![1,1;1,0]`, whose path
counts are Fibonacci numbers and whose Perron root is the golden ratio; the resulting
proof-search dimension is `log φ / log 2 ≈ 0.6942`. -/Formal statement
theorem SubmultiplicativeSearchEntropy.gold_pow_le_fib(n : ℕ) : Real.goldenRatio ^ n ≤ (Nat.fib (n + 3) : ℝ) := by sorry
Source