ON THE COMPLEXITY OF SUBSHIFTS AND INFINITE WORDS

The paper proves Theorem 1.1: for any non-decreasing f with f(n) ≥ n+1 and f(2n) ≤ f(n)^2 there exists a recurrent infinite word w with p_w ∼ f, via an explicit multiscale marker construction with “balanced” indices and three growth regimes, and upgrades bounds along a bounded-ratio subsequence using a monotonicity lemma. This exactly matches the model’s outline, which restates the construction (dictionaries/markers, balanced stages, three regimes), the recurrence argument, and the Lemma 2.2 subsequence-to-all-n step. Minor notational simplifications in the model (e.g., using |W_k| instead of n_k s_k) don’t affect correctness. See Theorem 1.1 and its proof sketch, the balanced-index framework and cases, the recurrence Lemma 4.1, the balanced-index bounds (Corollary 4.3), and the conclusion p_X ∼ f via Lemma 4.4 and Lemma 2.2 in the paper .