Complete r-ary marks: Assumptions (S) and (C) (Lemmas lem:S_rary and lem:C_rary) #
Section 6.2 of the paper, source lines 2623–2792 (inventory L6.2 (i),(ii), L6.3, P19, P21).
Marks: G_k(T) = 1{H_{r,k} ≺ T} (Embeds (completeTree r k)) and its declumping
Ghat_k(T) = 1{k_∅(T) ≠ r} 1{∃ u ∈ Γ_∅(T), G_k(T_u) = 1}
(declumpedMark {d | d ≠ r} (Embeds (completeTree r k))). π_k = P(H_{r,k} ≺ 𝒯).
Main statements #
structuralMicroscopic_embeds: for any sequence of patternsP_jwiths(P_{k_n}) + ℓ(P_{k_n}) = n^{o(1)}(internal vertices plus leaves), the marksP_j ≺ ·satisfy Assumption (S) with respect toM_n = max 1 ⌊n^{1-η}⌋₊,η ∈ (0, 1 - 1/α). Its specializationlem_S_rary_iis Lemmalem:S_rary(i);lem_S_rary_i_one(r = 1,k_n = n^{o(1)}) andlem_S_rary_i_of_two_le(r ≥ 2,r^{k_n} = n^{o(1)}) restate the hypothesis through U07.pairSum_completeTree_le(P19): one constantKsuch that for allk,M,∑_{ℓ=1}^{M} P(|𝒯| ≥ ℓ+1, G_k(𝒯) = 1, G_k(𝒯_{u_{ℓ+1}}) = 1) ≤ K π_k + M π_k².lem_S_rary_ii(Lemmalem:S_rary(ii)): ifn π_{k_n} → ∞andM_n = o(n), then Assumption (C) holds;lem_S_rarypackages (i) and (ii) with the paper's hypotheses.pair_declumped_completeTree_le(P21) andlem_C_rary(Lemmalem:C_rary): the declumped marks satisfyA_n(ℓ) ≤ π̂_{k_n}²for everyℓ ≥ 1, hence Assumption (C) for every level sequence and every cutoff withM_n = o(n).
Proof of P19 (departure from the paper's bookkeeping) #
The paper splits the descendants u_{ℓ+1} of a root occurrence into the vertices of the displayed
skeleton and those of the grafted forest, and bounds the forest part by a union bound over DFS
positions of an infinite forest. Here both parts are handled by the cut-and-graft decomposition
T = Cut_ℓ(T)[T_{u_{ℓ+1}}] at each fixed position ℓ: every position has a class j ≤ k
(exists_replaceClass; j = 0 for forest vertices and skeleton leaves, j = k - a for internal
skeleton vertices at depth a), and the cut-and-graft factorization gives exactly
P(ℓ < |𝒯|, class j, G_k(𝒯_{u_{ℓ+1}})) = (π_k / π_j) P(ℓ < |𝒯|, G_k(𝒯), class j). The class 0
terms give M π_k² (the paper's forest bound M_n π_{k_n} · π_{k_n}; the "fresh increment"
property at a fixed forest position is the factorization 𝐏(A[S]) = w(A) 𝐏(S)), and the classes
j ≥ 1 give at most r^{k-j} positions each (classCount_le). With a = k - j this is the
paper's skeleton sum π_k ∑_{a} r^a π_k / π_{k-a}; using π_k / π_{k-a} ≤ μ_r^{s_{r,a}}
(superadditivity of s_{r,·}) it is bounded by K π_k with the k-independent convergent series
K = ∑_a r^a μ_r^{s_{r,a}} (μ_r < 1). For r = 1 this is the paper's geometric continuation
∑_a μ_1^a; for r ≥ 2 the paper uses instead the bound k r^k μ_r^{r^{k-1}} + r^k π_k (its
leaf term r^k π_k is part of our class 0). No forest DFS bookkeeping is needed.
Assumption (S) #
Under the decomposition embedsSkeletonLaw μ T' (U06), C = s(T') and L = ℓ(T') are
deterministic, so E[C + L] ≤ s(T') + ℓ(T').
Assumption (S) for non-fringe pattern marks G_j = 1{P_j ≺ ·} whose skeleton size
s(P_{k_n}) + ℓ(P_{k_n}) (internal vertices plus leaves) is n^{o(1)}, with respect to the
polynomial cutoff M_n = max 1 ⌊n^{1-η}⌋₊ (= ⌊n^{1-η}⌋ for n ≥ 1), η ∈ (0, 1 - 1/α):
Lemma lem:critM applied to the decomposition of U06 (source lines 2655–2668).
Lemma lem:S_rary(i) (source lines 2644–2668): if
s_{r,k_n} + ℓ_{r,k_n} = n^{o(1)} (s_{r,k} = number of internal vertices and ℓ_{r,k} =
number of leaves of H_{r,k}, identified with k, 1 resp. (r^k - 1)/(r - 1), r^k by U07),
then G_k = 1{H_{r,k} ≺ ·} satisfies Assumption (S) along (k_n) with respect to
M_n = max 1 ⌊n^{1-η}⌋₊, for every η ∈ (0, 1 - 1/α). The n^{o(1)} hypothesis is used only
through its upper half ≤ n^δ (for every δ > 0, eventually along admissible sizes).
Lemma lem:S_rary(i), r = 1: the hypothesis s_{1,k_n} + ℓ_{1,k_n} = k_n + 1 = n^{o(1)}
is k_n = n^{o(1)}.
Lemma lem:S_rary(i), r ≥ 2: the hypothesis
s_{r,k_n} + ℓ_{r,k_n} = (r^{k_n} - 1)/(r - 1) + r^{k_n} = n^{o(1)} is r^{k_n} = n^{o(1)}.
P19: the summed pair bound for the raw marks #
The cut-and-graft factorization for one class (P19):
P(ℓ < |𝒯|, class j, 𝒯_{u_{ℓ+1}} ∈ G_k) π_j = P(ℓ < |𝒯|, class j, 𝒯_{u_{ℓ+1}} ∈ G_j) π_k.
The event {ℓ < |𝒯|, G_k(𝒯) = 1, position ℓ of class j}.
Equations
- One or more equations did not get rendered due to their size.
Instances For
π_j = P(H_{r,j} ≺ 𝒯) = μ_r^{s_{r,j}} as a real number (U07).
P19, one position. A(ℓ) ≤ ∑_{j ≤ k} (π_k / π_j) P(ℓ < |𝒯|, G_k(𝒯) = 1, class j).
P19, count of skeleton positions. For j ≥ 1,
∑_{ℓ=1}^{M} P(ℓ < |𝒯|, G_k(𝒯) = 1, class j) ≤ r^{k-j} π_k.
s_{r,c} + s_{r,a} ≤ s_{r,a+c} (r ≥ 1), where s_{r,a} is the number of internal
vertices of H_{r,a}.
The weights g_a = r^a μ_r^{s_{r,a}} of the skeleton contribution are summable (μ_r < 1):
for r = 1 this is the geometric series ∑ μ_1^a, for r ≥ 2 the ratio r μ_r^{r^a} tends
to 0.
P19 (source lines 2670–2750): for r ≥ 1 with μ_r > 0 there is one constant K such
that, for every level k and every M,
∑_{ℓ=1}^{M} P(|𝒯| ≥ ℓ+1, G_k(𝒯) = 1, G_k(𝒯_{u_{ℓ+1}(𝒯)}) = 1) ≤ K π_k + M π_k².
Lemma lem:S_rary(ii) (source lines 2670–2753), for an arbitrary cutoff with
M_n = o(n) (the paper takes M_n = ⌊n^{1-η}⌋, see lem_S_rary): if μ_r > 0 (r ≥ 1) and
n π_{k_n} → ∞ along admissible sizes, the raw marks G_k = 1{H_{r,k} ≺ ·} satisfy
Assumption (C) along (k_n) with respect to (M_n). The hypothesis
s_{r,k_n} + ℓ_{r,k_n} = n^{o(1)} of the lemma is not needed for this part.
Lemma lem:S_rary(i) and (ii) with the paper's hypotheses (source lines 2644–2753):
r ≥ 1, μ_r > 0, s_{r,k_n} + ℓ_{r,k_n} = n^{o(1)}, η ∈ (0, 1 - 1/α) and
M_n = max 1 ⌊n^{1-η}⌋₊ (= ⌊n^{1-η}⌋ for n ≥ 1). Part (iii) (E[N_{k_n}(𝒯^n)] ∼ n π_{k_n})
is Corollary cor:SM(ii) and is not included.
Lemma lem:C_rary: the declumped marks #
P21 (source lines 2768–2786): for every r, k and ℓ ≥ 1,
P(|𝒯| ≥ ℓ+1, Ghat_k(𝒯) = 1, Ghat_k(𝒯_{u_{ℓ+1}(𝒯)}) = 1) ≤ π̂_k², by Lemma lem:cut_graft with
𝓠_0 the whole tree space and 𝓡 the cut trees all of whose re-graftings are in {Ghat_k = 1}.
Lemma lem:C_rary (source lines 2762–2791): for every r, every level sequence (k_n)
and every cutoff sequence with M_n = o(n), the declumped complete r-ary marks
Ghat_k = 1{k_∅ ≠ r} 1{∃ child c, H_{r,k} ≺ 𝒯_c} satisfy Assumption (C):
∑_{ℓ=1}^{M_n} Â_n(ℓ) ≤ M_n π̂_{k_n}² = o(n π̂_{k_n}²).
Lemma lem:C_rary for every cutoff sequence (IsCutoff M).