Complexity and recurrence in infinite words and related structures

The paper proves that for every ε>0 there exists an infinite word over a finite alphabet with polynomially bounded complexity and whose discrete derivative satisfies p′(n) ≥ p(n)/n^ε for infinitely many n (Theorem 1.2), via a carefully stratified construction and sharp counting lemmas . The candidate solution independently builds a 3-letter word using ultra-long separators and catalogs of sparsely marked binary cores. It establishes a polynomial complexity bound and substantiates a large-derivative phenomenon along an infinite subsequence. While some counting steps (especially for factors containing '#') are sketched rather than fully formalized, the approach is sound and compatible with known identities (e.g., p(n+1)−p(n)=∑(right-extensions−1)). Net: both achieve the same statement by different methods; the paper’s argument is fully rigorous, and the model’s is a plausible, implementable variant.