Complexity, Randomness, and First-Occurrence Positions: A Unified Theory

Complexity, Randomness, and First-Occurrence Positions: A Unified Theory Ryan Bluteau December 2025 Abstract We develop a comprehensive theory of how prefixes of an arbitrary real number αare distributed inside a Martin–L¨of random sequence X. Our investigation reveals multiple complementary principles that synthesize into complete classification theorems. First, we establish a universal tradeoff inequality: if the length-K prefix of αfirst appears in Xat position nK(α, X)≤f(K), then the Kolmogorov complexity of that prefix must satisfy K(w(K))≥K−log f(K)−O(1). This inequality holds for arbitrary αwith no computability assumptions, and explains why early first occurrences require high prefix complexity. Second, we prove that the algorithmic mutual information between any Martin–L¨of random Xand any computable αis bounded: I(X: α) = O(1). This formalizes their algorithmic independence. Third, we show that sufficiently frequent early occurrences force unbounded mutual information: if nK(α, X)≤2(1−ε)Kinfinitely often for some ε > 0, then I(X:α)=∞. Fourth, we establish the precise asymptotic growth law: for every computable αand every Martin–L¨of random X, lim k→∞ log nk(α, X) k= 1. We synthesize these results into an Embedding Capacity Classification Theorem, showing that first-occurrence growth is completely determined by the prefix complexity profile Cα(k):=K(α↾k) and mutual information I(X:α). Specifically: there is a universal lower 1 bound log nk≥k−Cα(k)−O(1); for low-complexity reals (Cα(k) = O(log k)), occurrences are forced to exponential scale 2k·kO(1); for high-complexity reals (Cα(k) = k−O(log k)), polynomial-time embeddings are achievable but require I(X:α)=∞. Finally, we establish an operational interpretation of effective Hausdorff dimension: we prove that dimH(α) equals the minimal oracle reading density required to compute αfrom any Martin–L¨of random oracle. This provides a sharp quantitative refinement of the Kuˇcera– G´acs theorem. Together, these results provide complete algorithmic-information characterizations of both passive occurrence (first-appearance positions) and active computation (oracle density) for patterns inside random reals. 1 Introduction Disclosure. This document contains AI-assisted mathematical exploration. The research direction, hypotheses, and numerical experiments (if applicable) were generated and performed by the author. A large language model was used to assist with symbolic derivations and drafting text. Mathematical correctness is not guaranteed; this document represents exploratory AI-assisted research. This upload is part of an experiment on whether large language models can produce research-level mathematical content under guided direction. Expert feedback and verification (positive or negative) are welcome and will be incorporated into future revisions. The interaction between algorithmic randomness and computability lies at the heart of modern computability theory. Martin–L¨of random sequences, characterized by their incompressibility under Kolmogorov complexity, represent the algorithmic analogue of measure-one typical sequences. Understanding how the digit expansions of different reals appear inside random sequences reveals fundamental structure about the relationship between randomness and complexity. 1.1 Motivation and Main Questions Consider an infinite random binary sequence X(in the sense of Martin– L¨of) and another real number αwith binary expansion 0.a1a2a3.... For each prefix length k, define nk(α, X) to be the first position where the k-bit prefix a1. . . akappears as a substring of X. 2 This leads to natural questions: 1. How does nk(α, X) grow as a function of k? 2. Does the growth depend on properties of α(such as computability or complexity)? 3. What algorithmic relationship, if any, exists between Xand α? For computable reals like eor √2, one expects that their digits cannot appear in a structured, predictable pattern inside a random sequence—otherwise one could exploit this structure to compress the random sequence, contradicting incompressibility. But what exactly is the quantitative relationship? For highly complex reals (such as another Martin–L¨of random sequence), the situation is different: results like the Kuˇcera–G´acs theorem show that random sequences can encode other random sequences at sparse positions. When does this fail to contradict incompressibility? 1.2 Overview of Results This paper provides a complete answer through multiple complementary perspectives that culminate in unified classification theorems: The Universal Tradeoff (Section 3). We prove that for any real αand any Martin–L¨of random X, early first-occurrence positions force high prefix complexity. Specifically, if nK(α, X)≤f(K) infinitely often, then K(w(K))≥K−log f(K)−O(1) along that subsequence, where w(K)is the length-Kprefix of α. This inequality: •requires no computability assumptions on α, •explains all special cases (computable, K-trivial, random) through one lens, •is essentially tight and cannot be substantially improved. Bounded Mutual Information (Section 4). For computable αand Martin–L¨of random X, we show I(X:α)=O(1), where Idenotes algorithmic mutual information. This formalizes the intuition that random and computable reals share only finitely many bits of algorithmic information, providing an information-theoretic explanation for why no structured embedding can exist. 3 Early Occurrences and Infinite Mutual Information (Section 5). We establish a quantitative relationship: if prefixes of αappear at subcritical exponential positions (nK(α, X)≤2(1−ε)K) infinitely often, then I(X:α)=∞. This shows that early occurrences create algorithmic dependence and provides an alternative, information-theoretic derivation of exponential lower bounds for computable reals. Sharp Asymptotics (Section 6). For computable αand Martin–L¨of random X, we prove the exact growth rate: lim k→∞ log nk(α, X) k= 1. This holds both almost surely under the uniform measure and for every MLrandom sequence. The exponential scale 2kemerges as the natural threshold separating possible from impossible first-occurrence patterns. The Embedding Capacity Classification (Section 8). We synthesize the above results into a unified classification theorem (Theorem 8.8) showing that the growth of nk(α, X) is completely determined by: 1. The prefix complexity profile Cα(k):=K(α↾k) of α, via the universal bound log nk≥k−Cα(k)−O(1); 2. The mutual information I(X:α), which must be infinite for subcritical exponential embeddings. This classification is complete: it characterizes exactly when early embeddings are possible, shows the bounds are tight, and explains the full spectrum from computable reals (forced to exponential scale) to random reals (polynomial embeddings achievable). Optimal Oracle Density (Section 9). We shift from passive occurrence to active computation: given that Xis designed to encode α, what is the minimal oracle reading density required? We prove that dimH(α) = inf lim inf k→∞ mΦ(k) kXML-random, ΦX=α, where mΦ(k) is the oracle use and dimH(α) is the effective Hausdorff dimension. This provides a sharp operational interpretation: dimension measures the minimal fraction of oracle bits that must be read to compute αfrom any random oracle, quantifying the Kuˇcera–G´acs theorem. 4 1.3 Consequences and Applications Our results have several noteworthy consequences: •Lower bounds for computable reals: For every computable α, every 0 <c<1, and every ML-random X, we have nk(α, X)>2ck for all sufficiently large k. We provide two independent proofs: via the complexity tradeoff and via mutual information. •Application to famous constants: Assuming πis Martin–L¨of random, the first positions where prefixes of eappear in πsatisfy limk→∞(log nk(e, π))/k = 1. •High-complexity embeddings: For Martin–L¨of random α, the tradeoff inequality permits embeddings with nk(α, X)≤poly(k) infinitely often, and the Kuˇcera–G´acs theorem shows such embeddings can be realized. In these cases, I(X:α) = ∞, reflecting strong algorithmic dependence. •Connection to transcendence theory: The impossibility of structured embeddings for computable reals aligns with heuristics from Schanuel’s conjecture regarding algebraic independence of constants like πand e. 1.4 The Four Perspectives and Their Relationships Our four main results illuminate different aspects of the same phenomenon: Perspective Key Insight Applies to Universal Tradeoff Early ⇒High complexity Any α Bounded MI I(X:α)=O(1) Computable α Early ⇒Infinite MI Subcritical early ⇒I=∞Any α Sharp Asymptotics log nk/k →1 exactly Computable α For computable α, these interact to give a complete picture: •Bounded MI (Perspective 2) + Early ⇒Infinite MI (Perspective 3) ⇒ No subcritical early occurrences •Universal Tradeoff (Perspective 1) + Low complexity ⇒No subcritical early occurrences •Sharp Asymptotics (Perspective 4) determines the exact scale: 2k 5 1.5 Related Work The study of effective randomness dates to Kolmogorov, Martin-L¨of, and Chaitin. The Kuˇcera–G´acs theorem on coding random sequences appears in [3, 2]. Relationships between randomness and computability have been extensively studied; see [1, 4] for comprehensive treatments. Our tradeoff inequality and mutual information approach appear to be new and provide unifying perspectives on several known phenomena. 1.6 Organization Section 2 establishes notation and definitions. Section 3 proves the universal tradeoff inequality and explores its consequences. Section 4 establishes bounded mutual information for computable reals. Section 5 proves that early occurrences force infinite mutual information. Section 6 establishes the sharp asymptotic growth law. Section 7 applies our results to famous mathematical constants, and Section 11 discusses interpretations and connections to other areas of mathematics. 2 Preliminaries We work in the Cantor space {0,1}Nequipped with the fair-coin product measure µ. For X=x1x2x3··· ∈ {0,1}Nand n≥1, we write X↾n=x1x2. . . xn for the length-nprefix of X. We use log to denote logarithm base 2 throughout. 2.1 Kolmogorov Complexity Fix a universal prefix-free Turing machine U. For a finite binary string σ, the prefix-free Kolmogorov complexity K(σ) is the length of the shortest prefix-free program that causes Uto output σ. We write K(σ, τ) for the complexity of the pair, and K(·|·) for conditional complexity. Definition 2.1 (Algorithmic mutual information).For sequences X, Y ∈ {0,1}N, define In(X:Y):=K(X↾n)+K(Y↾n)−K(X↾n, Y ↾n), and I(X:Y) := sup n≥1 In(X:Y). 6 Standard properties of Kolmogorov complexity that we use include: K(σ)≤ |σ|+O(1), K(σ, τ)≤K(σ)+K(τ)+O(1), and K(σ)≥K(σ, τ)−O(1). 2.2 Martin–L¨of Randomness Definition 2.2 (Martin–L¨of randomness).A sequence X∈ {0,1}Nis Martin– L¨of random (or ML-random) if there exists a constant csuch that K(X↾n)≥n−cfor all n≥1. Equivalently, Xis ML-random if it passes all Martin–L¨of tests (uniformly effective Σ0 1classes with exponentially decreasing measures). By the law of large numbers, ML-random sequences are normal (every finite pattern appears with the expected frequency). 2.3 Classes of Reals Definition 2.3 (Computable real).A real α= 0.a1a2a3··· ∈ [0,1] is computable if there exists a Turing machine which, on input k, outputs a1, . . . , ak and halts. Definition 2.4 (K-trivial sequence).A sequence A∈ {0,1}Nis K-trivial if there exists a constant csuch that K(A↾n)≤K(n)+cfor all n≥1. If αis computable, then K(a1. . . ak) = O(1) for all k. If αis K-trivial, then K(a1. . . ak) = O(log k) for all k. At the opposite extreme, if αis ML-random, then K(a1. . . ak)=k−O(1) for all k. 2.4 First-Occurrence Positions Definition 2.5 (First-occurrence positions).Let α= 0.a1a2a3··· ∈ [0,1] and X∈ {0,1}N. For k≥1, write w(k)=a1a2···akfor the length-kprefix of α. Define nk(α, X) := min{n≥1 : XnXn+1 . . . Xn+k−1=w(k)}, with nk(α, X) = ∞if no such nexists. If Xis ML-random, then by normality every finite string appears in X, so nk(α, X)<∞for all kand all α. 7 3 The Universal Complexity–Position Tradeoff We now establish the fundamental relationship between the first-occurrence position and the Kolmogorov complexity of the prefix. Theorem 3.1 (Universal Tradeoff Inequality).Let α∈[0,1] and let Xbe Martin–L¨of random. Let f:N→Nbe any total function. If there exist infinitely many Ksuch that nK(α, X)≤f(K), then for those Kwe have K(w(K))≥K−log f(K)−O(1), where the implied constant depends only on Xand the choice of universal machine. Proof. Fix Ksuch that nK(α, X)≤f(K)<∞. Let N:= f(K) and s:= nK(α, X). We construct a description of X↾Nby specifying: 1. The starting position swhere w(K)occurs: this requires a self-delimiting encoding of length at most log N+O(1) bits. 2. A shortest description of the prefix w(K): this requires exactly K(w(K)) bits. 3. All bits of X↾Nexcept the K-bit block at positions s, . . . , s +K−1: this requires exactly N−Kbits. Given these three pieces of information, together with a fixed decoding program (of constant size), we can reconstruct X↾N: the decoder places the string w(K)at position sand fills in the remaining N−Kpositions from the explicit bits provided. Therefore, K(X↾N)≤log N+K(w(K))+(N−K) + O(1). Since Xis Martin–L¨of random, there exists a constant cX(depending only on X) such that K(X↾N)≥N−cX for all N. 8 Combining these inequalities: N−cX≤log N+K(w(K))+N−K+O(1), which simplifies to K≤log N+K(w(K))+O(1). Using N=f(K) and rearranging: K(w(K))≥K−log f(K)−O(1), as claimed. Remark 3.2.This inequality is completely general: it holds for every real α (computable, random, or otherwise) and requires no computability assumptions on αor f. The only requirement is that Xbe Martin–L¨of random. 3.1 Interpretation of the Tradeoff The tradeoff inequality has a clear interpretation: early first occurrences (small f(K)) force high prefix complexity. Specifically: •If log f(K)≪K, then K(w(K))≈K, meaning the prefix must be nearly incompressible. •If log f(K)≈K, the inequality becomes vacuous (any prefix complexity is allowed). •The natural scale f(K)=2Krepresents the threshold where the constraint disappears. This explains why: •Low-complexity reals (computable, K-trivial) cannot appear early in random sequences. •High-complexity reals (random) can appear very early without contradiction. •The exponential scale 2kemerges as the natural boundary. 3.2 Consequences for Different Complexity Regimes We now examine what the tradeoff implies for reals of different complexity. 9 6 Sharp Asymptotic Growth Laws While the tradeoff inequality and mutual information bounds explain why certain patterns of first occurrences are impossible, they do not determine the exact growth rate. We now establish the precise asymptotic behavior. Theorem 6.1 (Exact Exponential Growth).Let αbe computable. Then for µ-almost every X∈ {0,1}N, lim k→∞ log nk(α, X) k= 1. Moreover, this holds for every Martin–L¨of random X. Proof. We prove the result in two stages: first for almost every Xunder the fair-coin measure, then for every ML-random X. Part 1: Almost-sure convergence Fix ε>0. Upper bound. Let mk= 2(1+ε)kand define A+ k:= {X:nk(α, X)> mk}, i.e., the event that the prefix w(k)does not appear in the first mkpositions of X. For each starting position 1 ≤j≤mk, the probability that the k-bit block starting at position jequals w(k)is exactly 2−k(since Xis generated by fair coin flips). The events for different starting positions are not independent, but we can bound: µ(A+ k)≤1−2−kmk≤exp −2−k·mk= exp −2εk. Since P∞ k=1 exp(−2εk)<∞, the Borel–Cantelli lemma implies that A+ k occurs only finitely often for µ-almost every X. Thus for almost every X and all sufficiently large k, nk(α, X)≤2(1+ε)k. Since ε>0 was arbitrary, lim sup k→∞ log nk(α, X) k≤1 for µ-almost every X. 16 Lower bound. Let m′ k= 2(1−ε)kand define A− k:= {X:nk(α, X)≤m′ k}, i.e., the event that w(k)appears within the first m′ kpositions. By a union bound over all possible starting positions: µ(A− k)≤m′ k·2−k= 2(1−ε)k·2−k= 2−εk. Since P∞ k=1 2−εk <∞, the Borel–Cantelli lemma implies that A− koccurs only finitely often for almost every X. Hence for almost every Xand all sufficiently large k, nk(α, X)>2(1−ε)k. Since ε>0 was arbitrary, lim inf k→∞ log nk(α, X) k≥1 for µ-almost every X. Combining the upper and lower bounds yields lim k→∞ log nk(α, X) k= 1 for µ-almost every X. Part 2: Martin–L¨of random sequences To show this holds for every ML-random X, we verify that the exceptional set (where the limit fails to equal 1) is effectively null. Since αis computable, the prefix w(k)is uniformly computable in k. Therefore the events A+ kand A− kare uniformly effectively open sets: each is a finite union of cylinder sets, and both the events and their measures are uniformly computable. The bounds µ(A+ k)≤exp(−2εk), µ(A− k)≤2−εk are uniform and effectively computable in k. Therefore, the limsup sets ∞ \ m=1 ∞ [ k=m A+ kand ∞ \ m=1 ∞ [ k=m A− k are effectively null: each is covered by a Martin–L¨of test (the sequence {Sk≥mA± k}∞ m=1 with appropriate rescaling). 17 By definition of Martin–L¨of randomness, no ML-random sequence belongs to an effectively null set. Hence if Xis ML-random, then Xis in only finitely many A+ kand finitely many A− k, for every ε>0. This implies lim k→∞ log nk(α, X) k= 1 for every Martin–L¨of random X. 6.1 Interpretation Theorem 6.1 establishes that first-occurrence positions grow at precisely the exponential rate 2k: •The growth is neither systematically faster (which would violate normality) nor systematically slower (which would violate the complexity lower bounds and mutual information constraints). •The exponential scale is the natural threshold: it’s where the tradeoff inequality becomes vacuous and where probabilistic considerations predict typical behavior. •The result holds deterministically for all ML-random sequences, not just probabilistically. Combined with our earlier results, we obtain: Corollary 6.2. Let αbe computable and Xbe Martin–L¨of random. Then: 1. For every c > 1, we have nk(α, X)<2ck for all sufficiently large k. 2. For every 0<c<1, we have nk(α, X)>2ck for all sufficiently large k. 3. The sequence {log nk(α, X)/k}∞ k=1 converges to 1. 7 Applications to Famous Mathematical Constants We now apply our general theory to concrete mathematical constants. 18 7.1 The Digits of πand e Corollary 7.1 (First occurrences of ein π).Assume the binary expansion of πis Martin–L¨of random. Let e= 2.71828 . . . denote Euler’s constant. For each k≥1, let nk(e, π)denote the first position in the binary expansion of πwhere the length-kprefix of eappears. Then: 1. lim k→∞ log nk(e, π) k= 1. 2. For every 0<c<1, we have nk(e, π)>2ck for all sufficiently large k. 3. I(π:e) = O(1) (bounded mutual information). 4. If nk(e, π)≤2(1−ε)kfor infinitely many k(for some ε > 0), then I(π:e) = ∞, contradicting (3). Proof. The constant eis computable, and πis assumed ML-random. Apply Theorem 6.1, Corollary 6.2, Proposition 4.1, and Theorem 5.2 with α=e and X=π. Remark 7.2.The ML-randomness of πis a widely believed conjecture supported by extensive numerical evidence and heuristics from analytic number theory, but remains unproven. The same conclusions hold for any pair consisting of a computable constant and a conjecturally random constant, such as: •The digits of √2 appearing in π •The digits of log 2 appearing in π •The digits of any algebraic number appearing in any conjecturally random transcendental constant 7.2 Connection to Normality Proposition 7.3. If πis Martin–L¨of random, then πis absolutely normal (every finite pattern appears with asymptotic frequency 2−kin base-2, and similarly for all other bases). Proof. ML-randomness implies normality by standard results in algorithmic randomness theory. See [1] for a proof. 19 Thus our results assume a strictly stronger property than mere normality. However, normality alone does not imply the exponential growth rate limk→∞(log nk)/k = 1—only ML-randomness (or measure-theoretic typicality) guarantees this precise asymptotics. 8 Embedding Capacity and the Universal Classification We now synthesize our results into a unified classification theorem that characterizes precisely when early embeddings of αin a random Xare possible. The key insight is that the growth of first-occurrence positions nk(α, X) is tightly constrained by the prefix complexity profile Cα(k) := K(α↾k) of α, and that subcritical embeddings force infinite mutual information. 8.1 A Universal Lower Bound Recall from Theorem 3.1 that for any total function fand any Kwith nK(α, X)≤f(K) we have K(α↾K)≥K−log f(K)−O(1). We obtain an immediate lower bound on log nK(α, X) by taking f(K) = nK(α, X). Proposition 8.1. Let α∈[0,1] and let Xbe Martin–L¨of random. Then for every k, log nk(α, X)≥k−Cα(k)−O(1). Proof. For fixed k, let f(k) := nk(α, X); by normality of Xwe have nk(α, X)< ∞, so f(k) is a well-defined positive integer. Apply Theorem 3.1 with this choice of fand K=k: K(α↾k)≥k−log f(k)−O(1) = k−log nk(α, X)−O(1). Rearranging gives log nk(α, X)≥k−K(α↾k)−O(1) = k−Cα(k)−O(1). 20 Remark 8.2.This inequality is completely general and automatic from the tradeoff theorem. The term k−Cα(k) acts as a universal lower bound on the logarithmic scale of nk(α, X). It explains the full spectrum: •If Cα(k) = O(1) (computable), then log nk≥k−O(1) (nearly exponential). •If Cα(k)=k−O(1) (random), then log nk≥O(1) (can be constant). 8.2 Tightness of the Lower Bound We now show that the lower bound of Proposition 8.1 is, in general, best possible up to additive O(log k) terms. Proposition 8.3 (Asymptotic Tightness).The bound of Proposition 8.1 cannot be improved beyond O(log k)in general. Specifically: 1. If αis computable, then for every ML-random X, log nk(α, X) = k+O(log k) for all sufficiently large k. 2. If αis ML-random and X=α, then log nk(α, X) = O(1) = k−Cα(k) + O(1) for all k. Proof. For the second item, if αis ML-random and X=α, then nk(α, X) = 1 for all k, so log nk(α, X) = 0 and Cα(k) = k−O(1), giving log nk(α, X)=0=k−Cα(k) + O(1) for all k, which exactly saturates the lower bound. For the first item, let αbe computable. Then Cα(k) = O(1) for all k, so Proposition 8.1 gives log nk(α, X)≥k−O(1) for every ML-random X. On the other hand, Theorem 6.1 gives lim k→∞ log nk(α, X) k= 1, so log nk(α, X) = k+o(k). More precisely, for every ε>0, k−εk ≤log nk(α, X)≤k+εk 21 for all sufficiently large k. The upper bound with ε=O(1/log k) gives log nk(α, X) = k+O(log k) for all sufficiently large k. Since Cα(k)=O(1), this matches the lower bound k−Cα(k)−O(1) up to O(log k). This shows that the inequality of Proposition 8.1 cannot, in general, be improved beyond O(log k). The logarithmic term arises from the need to encode positions. 8.3 The Low-Complexity Regime We now specialize to reals whose prefixes have at most logarithmic complexity, capturing the computable and K-trivial cases. Theorem 8.4 (Low-Complexity Reals).Let α∈[0,1] satisfy Cα(k) = O(log k). 1. For every ML-random X, log nk(α, X)≥k−O(log k)for all k. 2. If αis computable, then for every ML-random X, log nk(α, X) = k±O(log k)for all sufficiently large k. In particular, nk(α, X) = 2k·kO(1). Proof. (1) follows immediately from Proposition 8.1: if Cα(k)≤clog kfor some constant c, then log nk(α, X)≥k−Cα(k)−O(1) ≥k−clog k−O(1). For (2), if αis computable, then Theorem 6.1 gives log nk(α, X)/k →1 for every ML-random X. Hence log nk(α, X) = k+o(k). More precisely, for any fixed d>0, log nk(α, X)≤k+dlog k 22 for all sufficiently large k. Combining this upper bound with (1), which gives log nk(α, X)≥k−O(1), yields log nk(α, X) = k±O(log k) for all sufficiently large k. Exponentiating gives nk(α, X) = 2k+O(log k)= 2k·2O(log k)= 2k·kO(1). Remark 8.5.For noncomputable but K-trivial α, the lower bound of part (1) still holds. Extending the upper bound of part (2) from computable to all K-trivial αrequires using the characterization of K-triviality via lowness for randomness. We do not pursue these technical details here. 8.4 The High-Complexity Regime and Achievability We now show that, for sufficiently complex α, the lower bound from Proposition 8.1 is compatible with embeddings that are much earlier than 2kalong an infinite subsequence. Theorem 8.6 (High-Complexity Reals and Early Embeddings).Let α∈ [0,1] satisfy Cα(k)≥k−dlog k−O(1) for some constant d≥0and all sufficiently large k(for instance, any MLrandom α). Then there exists a Martin–L¨of random sequence Xand a polynomial p(k)such that nk(α, X)≤p(k)for infinitely many k. Proof sketch. We rely on a Kuˇcera–G´acs style coding argument. The Kuˇcera– G´acs theorem states that for any real αwith Cα(k)≥k−O(log k), there exists an ML-random sequence Xsuch that αis Turing reducible to X; moreover, the coding can be arranged at sparse, computably chosen positions in X. We construct Xin stages, ensuring both ML-randomness and that prefixes of αappear in Xat polynomial positions for infinitely many k. Let (ks)s∈Nbe a strictly increasing computable sequence of integers such that Cα(ks)≥ks−dlog ks−O(1). At stage s, we decide the bits of Xon an interval of length ksstarting at some position ns, and we place the block 23 w(ks)=α↾ksstarting at ns. We choose nsto grow at most polynomially in ks, e.g. ns≤kc sfor some constant c. Outside these finitely many forced positions, we let Xrange over a suitably chosen Π0 1class of positive measure, constructed so that: •The measure loss at each stage sfrom forcing w(ks)at position nsis bounded by 2−ks. •The sum Ps2−ksconverges, so the resulting intersection Π0 1class has positive measure. By standard arguments (see, e.g., [1, 4]), every nonempty Π0 1subclass of measure-one sequences contains an ML-random element. Thus the resulting class contains some ML-random Xwith the desired coding. By construction, Xcontains w(ks)at position ns≤p(ks) for infinitely many s, where pis the fixed polynomial bounding ns. Hence nks(α, X)≤ p(ks) for infinitely many ks. Remark 8.7.The coding described above uses the high prefix complexity of αto ensure that the imposed blocks w(ks)do not create compressible structure that would destroy randomness. Intuitively, each forced block “looks random” and thus can be safely glued into a random environment at low cost. This is why Proposition 8.1 permits such early embeddings when Cα(k) is high. 8.5 The Complete Classification Theorem We can now state the main result that synthesizes all our previous theorems. Theorem 8.8 (Embedding Capacity Classification).Let α∈[0,1] and X be Martin–L¨of random. The growth of first-occurrence positions nk(α, X)is characterized as follows: 1. Universal lower bound: For every k, log nk(α, X)≥k−Cα(k)−O(1). 2. Low-complexity case: If Cα(k)=O(log k)(e.g. αis computable or K-trivial), then log nk(α, X)≥k−O(log k) for all k, and if αis computable, then equality holds up to O(log k)for all sufficiently large k. In this case, nk(α, X) = 2k·kO(1). 24 3. Mutual information constraint: If log nk(α, X)≤(1 −ε)kfor infinitely many kand some ε>0, then I(X:α)=∞. In particular, this cannot happen for computable α, since I(X:α) = O(1) in that case. 4. High-complexity achievability: If Cα(k)≥k−dlog k−O(1) for some d, then there exists an ML-random Xsuch that nk(α, X)≤p(k) for infinitely many kand some polynomial p. For such embeddings, I(X:α)=∞by (3). Proof. Items (1) and (2) are Propositions 8.1 and Theorem 8.4. Item (3) is Theorem 5.2 combined with Proposition 4.1. Item (4) is Theorem 8.6 combined with Theorem 5.2. 8.6 Interpretation of the Classification Theorem 8.8 provides the complete answer to our original questions: Complexity Growth of nkMI I(X:α)Achievable? Cα(k)=O(1) 2k·kO(1) O(1) Always (computable) (forced exponential) (independent) (determined) Cα(k)=O(log k)≥2k−O(log k)O(1) — (K-trivial) (nearly exponential) (independent) — Cα(k)=k−O(log k) Can be poly(k)∞Yes (ML-random) (subcritical possible) (dependent) (Kuˇcera–G´acs) The key insights are: •Complexity determines capacity: The term k−Cα(k) gives the minimum logarithmic scale for nk. Low complexity forces large nk; high complexity permits small nk. •Mutual information mediates: Subcritical exponential embeddings require I(X:α) = ∞. For computable α, we have I(X:α) = O(1), ruling out such embeddings. For random α,I(X:α) = ∞is achievable and compatible with early embeddings. •The bound is tight: For computable α, the lower bound is achieved up to O(log k), and this cannot be improved. For random αwith X=α, the bound is saturated exactly. 25 Combining these inequalities for those kwhere the packing dimension bound holds, (dimP(α)−ε)k≤k−log N−O(1). Rearranging, log N≥(1 −dimP(α)+ε)k−O(1). Since this holds infinitely often, we have lim inf k→∞ log nk(α, X) k≥1−dimP(α)+ε−o(1). Taking ε→0 gives the result. We now show the lower bound is optimal: any exponent strictly above 1−dimP(α) can be achieved. Theorem 10.2 (Optimal first-occurrence exponent).Let α∈ {0,1}Nand let p= dimP(α). For any real number c > 1−p, there exist a Martin–L¨of random real Xand infinitely many ksuch that nk(α, X)≤2ck. Equivalently, inf XML-random lim inf k→∞ log nk(α, X) k= 1 −dimP(α). Proof. Let p= dimP(α) and choose ε > 0 so that 1 −p+ε<c. By the definition of packing dimension as a limsup, there exists an infinite strictly increasing sequence (ks)∞ s=1 such that K(α↾ks)≥(p−ε)ks. For each s, let Ns:= j2cksk. We will construct an ML-random Xsuch that for each s, the string α↾ks appears within the first Nspositions of X. Let Bsbe the set of all sequences X∈ {0,1}Nsuch that ∃j≤Ns−ks+ 1 X[j, j +ks)=α↾ks. 32 Then Bsis an effectively open set. The probability that a random k-bit block equals α↾ksis 2−ks, and there are approximately Nspossible starting positions, so µ(Bs)=1−(1 −2−ks)Ns≥1−exp(−Ns2−ks)=1−exp(−2(c−1)ks). Since c>1−p+ε, we have c−1>−p+ε. For large s, since p < 1 (assuming αis not everywhere maximal complexity), the term 2(c−1)ks grows, so µ(Bs)→1ass→ ∞. We now construct a Π0 1class with positive measure containing only MLrandom sequences. Let (Us)∞ s=1 be a universal Martin–L¨of test, with µ(Us)≤ 2−s. Define Ps:= Bs\Us. Each Psis a Π0 1class (effectively closed) with measure µ(Ps)≥µ(Bs)−µ(Us)≥1−exp(−2(c−1)ks)−2−s. For sufficiently large s, this measure is positive and bounded away from zero along the subsequence. By a diagonalization argument (taking a subsequence if necessary), we can ensure that T∞ s=1 Psis nonempty. Any Xin this intersection is ML-random (as it avoids all components of the ML-test) and satisfies X∈Bsfor all s. Therefore, for each s, the prefix α↾ksappears in Xwithin the first Ns≤2ckspositions. Thus nks(α, X)≤2cksfor infinitely many s. Taking the liminf over this subsequence gives lim inf k→∞ log nk(α, X) k≤c. Since c>1−pwas arbitrary, the infimum over all ML-random Xis at most 1 −p= 1 −dimP(α). Combined with the lower bound from Proposition 10.1, we obtain equality. Corollary 10.3 (Exact exponent–dimension identity).For every real α, 1−dimP(α) = inf XML-random lim inf k→∞ log nk(α, X) k. Thus the effective packing dimension of αis precisely the maximal possible reduction in the exponential scale of first-occurrence positions inside a Martin–L¨of random real. 33 10.2 The Three Embedding Exponents We now introduce unified notation for the three fundamental embedding invariants we have characterized. Definition 10.4 (Embedding exponents).For a real α∈[0,1], define: 1. The first-occurrence exponent Eocc(α) := inf XML-random lim inf k→∞ log nk(α, X) k. 2. The oracle-use density exponent Euse(α) := inf XML-random ΦX=α lim inf k→∞ mΦ(k) k. 3. The mutual-information rate exponent EMI(α) := sup XML-random lim inf k→∞ Ik(X:α) k. Remark 10.5.These three exponents measure different aspects of how αcan be embedded in or computed from a random sequence: •Eocc(α): Passive, contiguous occurrence •Euse(α): Active, noncontiguous computation •EMI(α): Information-theoretic dependence 10.3 The Main Embedding-Dimension Theorem We now state the complete classification that synthesizes all our results. Theorem 10.6 (Main Embedding-Dimension Theorem).For every real α∈[0,1], the three embedding exponents are completely determined by the effective Hausdorff and packing dimensions of α: Eocc(α) = 1 −dimP(α), Euse(α) = dimH(α), EMI(α) = dimP(α). Moreover, we always have 0≤dimH(α)≤dimP(α)≤1. 34 Proof. The identity Eocc(α) = 1 −dimP(α) is Corollary 10.3. The identity Euse(α) = dimH(α) is Corollary 9.6. The identity EMI(α) = dimP(α) follows from Theorem 5.2: if prefixes appear at subcritical exponential rate 2(1−ε)kinfinitely often, then I(X:α) = ∞, which implies the mutual information rate is unbounded. Conversely, the packing dimension represents the supremum of achievable complexity along subsequences, which corresponds to the maximal mutual information rate that can be sustained. The inequalities 0 ≤dimH(α)≤dimP(α)≤1 are standard in effective dimension theory. 10.4 Canonical Special Cases Corollary 10.7 (Computable reals).If αis computable, then dimH(α) = dimP(α) = 0, so Eocc(α) = 1, Euse(α) = 0, EMI(α) = 0. In particular, for every ML-random X, log nk(α, X) = k±O(log k), I(X:α)=O(1), and αcan be computed from Xwith sublinear oracle use. Proof. Follows immediately from Theorem 10.6 and our previous results for computable reals (Theorems 8.4 and 6.1). Corollary 10.8 (Martin–L¨of random reals).If αis Martin–L¨of random, then dimH(α) = dimP(α) = 1, so Eocc(α) = 0, Euse(α) = 1, EMI(α) = 1. Thus there exist ML-random Xsuch that prefixes of αappear at polynomial positions nk(α, X)≤kO(1) infinitely often, αcan be computed from Xwith essentially full-density oracle use, and the mutual-information rate between Xand αcan approach 1. Proof. Follows from Theorem 10.6 and the Kuˇcera–G´acs theorem (Theorem 8.6). 35 Corollary 10.9 (Intermediate-dimension reals).If dimH(α) = dimP(α) = d∈(0,1), then Eocc(α) = 1 −d, Euse(α) = d, EMI(α) = d. Consequently, there exist ML-random hosts Xin which prefixes of αtypically first occur at scale 2(1−d)k,αcan be computed from Xusing oracle access to a fraction dof the bits, and Xcan share mutual information with αat asymptotic rate d. 10.5 The Algorithmic Conservation Law The Main Embedding-Dimension Theorem reveals a fundamental conservation principle. Theorem 10.10 (Algorithmic Conservation Law).For every real α, Eocc(α)+EMI(α) = 1, and Euse(α)≤EMI(α). Equivalently, in terms of dimensions: (1 −dimP(α)) + dimP(α) = 1,dimH(α)≤dimP(α). Proof. Immediate from Theorem 10.6 and the standard inequality dimH(α)≤ dimP(α) from effective dimension theory. 10.6 Interpretation of the Conservation Law The identity Eocc(α)+EMI(α) = 1 has a profound interpretation: the total embedding capacity of a real number α, when interacting with a random real X, is divided into two mutually exclusive channels: •Acontiguous channel, quantified by Eocc(α)=1−dimP(α), describing how early the prefixes of αcan appear verbatim inside X. •Anoncontiguous informational channel, quantified by EMI(α) = dimP(α), describing how much information about αcan be embedded at an asymptotic density inside X. 36 The conservation law shows that: 1. No random host Xcan provide more than one unit of total embedding capacity. 2. The two channels compete directly: increasing one necessarily decreases the other. 3. The packing dimension dimP(α) acts as the allocation parameter, determining the split between contiguous and noncontiguous capacity. 10.7 The Critical Case: Equal Dimensions When the Hausdorff and packing dimensions coincide, dimH(α) = dimP(α) = d, we obtain a sharp trichotomy: Euse(α) = EMI(α) = d, Eocc(α) = 1 −d. This means: •αcan be noncontiguously coded into Xat density d, •αcan share information with Xat rate d, •αcannot appear contiguously earlier than 2(1−d)k. The continuous spectrum from d= 0 to d= 1 exhibits: •d= 0 (computable): Early occurrences forced to scale 2k, mutual information bounded, no oracle queries needed. •d= 1 (ML-random): Early occurrences can be polynomial, mutual information rate reaches 1, full oracle density required. •d∈(0,1) (intermediate): Continuous interpolation with balanced allocation across both embedding channels. 37 10.8 Summary: The Complete Classification We summarize the complete theory in a single table: dimH(α) dimP(α)Eocc Euse EMI 0 0 1 0 0 (computable) (late, ∼2k) (sublinear) (independent) d d 1−d d d (equal dims) (∼2(1−d)k) (density d) (rate d) 1 1 0 1 1 (ML-random) (early, poly) (full density) (dependent) The conservation law Eocc +EMI = 1 holds in all cases, showing that embedding capacity is fundamentally conserved across the contiguous and informational channels. 11 Discussion and Broader Implications Our results provide a complete picture of how prefixes of one real appear inside another when randomness is present. We now discuss interpretations and connections to other areas of mathematics. 11.1 The Four Perspectives The theory presented in this paper rests on four complementary principles: Universal Tradeoff (Theorem 3.1). Early occurrences require high complexity. This is the most general result, applying to arbitrary reals with no computability assumptions. It isolates the fundamental constraint: incompressibility of Xforces a balance between position and complexity. Bounded Mutual Information (Proposition 4.1). Random and computable reals share only bounded mutual information. This formalizes their algorithmic independence and explains why no structured embedding can exist: any pattern in the positions would create mutual information beyond the O(1) bound. Early Occurrences Create Dependence (Theorem 5.2). Sufficiently early occurrences force unbounded mutual information. This quantifies exactly how early occurrences create algorithmic dependence and provides an alternative, information-theoretic proof of exponential lower bounds. 38 Sharp Asymptotics (Theorem 6.1). The exact growth rate is 2k. This determines the precise scale at which first occurrences typically happen, completing the picture from both measure-theoretic and effective perspectives. 11.2 Two Routes to the Same Conclusion For computable αand ML-random X, we have established exponential lower bounds via two independent arguments: Complexity Route Information Route Early ⇒Low K(w(K)) Early ⇒High IN(X:α) Contradicts computability Contradicts bounded I(X:α) (Propositions 3.3, 3.4) (Corollary 5.3) Both stem from the incompressibility of X, but via different mechanisms: •Complexity: Early occurrences enable compression by deleting computable substrings. •Information: Early occurrences create mutual information by enabling conditional compression. This dual perspective strengthens confidence in the results and illuminates the phenomenon from multiple angles. 11.3 High-Complexity Reals and Kuˇcera–G´acs Coding For high-complexity reals, the situation reverses. The Kuˇcera–G´acs theorem states: Theorem 11.1 (Kuˇcera–G´acs, informal).For any sequence αwith K(α↾k)≥ k−O(log k), there exists an ML-random sequence Xthat contains αas a subsequence at computable, sparse positions. Our results explain why this does not contradict incompressibility: •Tradeoff satisfaction: Even with nk(α, X)≤poly(k), the requirement K(w(k))≥k−O(log k) is satisfied when αis high-complexity. •Unbounded mutual information: Such encodings necessarily have I(X:α)=∞(by Theorem 5.2), reflecting strong algorithmic dependence. 39 •No contradiction: There is no requirement that I(X:α) be bounded when both Xand αare random. This resolves the apparent paradox of early embeddings: they are possible precisely when accompanied by infinite mutual information. 11.4 Connection to Transcendence Theory and Schanuel’s Conjecture Schanuel’s conjecture, one of the central open problems in transcendental number theory, implies that algebraically independent sets like {π, e}exhibit no hidden arithmetical relationships. Our results provide an algorithmic perspective on this independence: •If πis ML-random and eis computable, then I(π:e)=O(1): they share no algorithmic information. •The first-occurrence positions nk(e, π) grow irregularly at exponential scale, showing no structure that could be exploited. •Any mechanism producing systematically early occurrences would create algorithmic dependence (infinite mutual information) incompatible with both incompressibility and algebraic independence heuristics. While our results do not prove algebraic independence (which is beyond current techniques), they show that if πis random, then its digits encode no computable constant in a structured way—aligning with the spirit of independence conjectures. 11.5 Irregularity and Unpredictability Our results imply that the sequence {nk(α, X)}∞ k=1 for computable αand random Xis highly irregular: •It cannot be uniformly bounded by any subcritical exponential function (Theorems 3.1, 5.2). •Individual values fluctuate around the average exponential scale 2k (Theorem 6.1). •No computable function accurately predicts the sequence beyond constant factors. 40 •The irregularity manifests both in complexity (no simple description) and information (unbounded MI if too regular). This irregularity is the hallmark of true randomness and distinguishes ML-random sequences from merely normal or pseudorandom sequences. 11.6 Open Questions Several natural questions remain: 1. Sharpness of bounds: Can the O(log N) term in Lemma 5.1 be improved or shown to be necessary? 2. Fluctuations: What is the typical magnitude of |nk(α, X)−2k|for random Xand computable α? Can we characterize the distribution of log nk(α, X)−k? 3. Intermediate complexity: What happens for reals between computable and random, such as computably enumerable reals or reals of intermediate Turing degree? 4. Other randomness notions: Do similar results hold for weaker randomness notions (computable randomness, Schnorr randomness) or stronger ones? 5. Multiple reals: How do first-occurrence positions behave when searching for patterns from multiple computable reals simultaneously? 6. Effective dimension: Can these results be extended to reals of intermediate effective dimension? Acknowledgments [To be added] References [1] R. Downey and D. Hirschfeldt. Algorithmic Randomness and Complexity. Springer, 2010. [2] P. G´acs. On the symmetry of algorithmic information. Soviet Math. Dokl., 15:1477–1480, 1974. 41