path_length_log_growth
plain-language theorem explainer
Average path length grows strictly with network size for N > 1 in the recognition model. Network scientists deriving small-world properties from phi-recurrence would cite it to confirm L(N) = log base phi of N. The proof is a short algebraic reduction that unfolds the definition and applies the monotonicity of the logarithm after confirming the positivity of log phi.
Claim. If real numbers satisfy $1 < N < M$, then $L(N) < L(M)$ where $L(x) = log_φ x$ and $φ$ is the golden ratio.
background
The SmallWorldFromSigma module re-derives small-world network properties from the φ-recurrence on the recognition graph. It defines the average path length as $L(N) = log N / log φ$, which equals the logarithm of N to base φ. This scaling is listed in the module documentation alongside the fixed-point derivation of the degree exponent γ = 3 from the equation (γ-1)(γ-2) = 2.
proof idea
The proof unfolds avgPathLength to obtain (log N) / (log φ). It invokes the upstream lemma one_lt_phi to obtain 0 < log φ. The division inequality div_lt_div_iff_of_pos_right then reduces the claim to log N < log M, which follows from Real.log_lt_log applied to the hypotheses 1 < N and N < M.
why it matters
The theorem is referenced inside smallWorldFromSigmaCert, which bundles gamma_eq_3, gamma_fixed_point, gamma_unique, avgPathLength_pos, and this growth result into a single certificate. It supplies the path-length scaling step stated in the module documentation: 'Average path length scales as log_φ N (small-world property)'. Within Recognition Science this supports the emergence of small-world topology from the self-similar fixed point phi.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.