lemmaroutine

Latent coloring change probability formula

Latent coloring changes with probability exactly (1−q−3)(1−θ)t(1-q^{-3})(1-\theta)^t
gives the change probability pushed below p∗p_*
Lemma·lem:latent-noise·§3.3 Concatenation and its noise

Statement (paper)

For independent uniform u∈Ptu\in P_t and noise ξt\xi_t, pt:=Pr⁡[Ct(u+ξt)≠Ct(u)]=(1−q−3)(1−θ)t. p_t:=\Pr[C_t(u+\xi_t)\ne C_t(u)] =(1-q^{-3})(1-\theta)^t.

In plain English

For independent uniform u∈Ptu\in P_t and noise ξt\xi_t, the probability that the latent coloring CtC_t changes, Pr⁡[Ct(u+ξt)≠Ct(u)]\Pr[C_t(u+\xi_t)\ne C_t(u)], equals exactly (1−q−3)(1−θ)t(1-q^{-3})(1-\theta)^t.

Why it's here

This gives the exact change probability ptp_t of the concatenated coloring, which is the noise-sensitivity quantity the latent gadget must keep small. It extends the one-block computation, where a nonzero shift flips a block color with probability 1−θ1-\theta, to a factor (1−θ)(1-\theta) per block over tt blocks, and it is what yields the bound ps≤(1−θ)sp_s\le(1-\theta)^s used to get below p∗p_*.
Classified routine:
Direct calculation from the one-block change probability (lem-latent-block-noise): independence across the t blocks of the concatenation gives a factor (1-θ) per block, combined with the probability 1-q^{-3} that the noise shift is nonzero.

Uses

lemBlock coloring changes with probability 1−θ

Used by

lemLatent alphabet gadget with detecting noiseclaimBase gadget change probability at most p_*

Figures

A flow diagram of one level of the latent recursion. Three boxes sit in a top row, separated by ellipses: a left child box ($u_{AJ}\in P_{t-1}$ mapped to $JC_{t-1}(u_{AJ})$), a red-highlighted selected child box ($u_{A_*J_*}+\xi_{t-1}$ mapped to $J_*C_{t-1}(u_{A_*J_*}+\xi_{t-1})$) and a right box of other child inputs. Arrows from all three, the middle one red, point to a summation box reading "Sum over every child $(A,J)\in\mathcal I$" with noisy aggregate $(x',y')=(x,y)+J_*\Delta$. That box points down to a final box, "Noisy parent output $y'+Q(x')\in B$". The figure shows how noise in only one uniformly chosen child propagates through the embedding, summation and quadratic map to the parent output.
Figure 2diagramp. 13
One level of the latent recursion, shown under its additive noise. The input space is a product over all child indices (A,J)(A,J); only one uniformly chosen child is perturbed. Each child output is embedded in UA≤X⊕BU_A\le X\oplus B, all embedded outputs are added, and the quadratic map is applied once at the parent. Here (x,y)(x,y) is the initial aggregate, and Δ\Delta is the selected child's output difference, so the noisy aggregate is (x′,y′)=(x,y)+J∗Δ(x',y')=(x,y)+J_*\Delta. The omitted children obey the same rule. The highlighted perturbation may disappear at the parent.
What it shows
A flow diagram of one level of the latent recursion. Three boxes sit in a top row, separated by ellipses: a left child box (uAJ∈Pt−1u_{AJ}\in P_{t-1} mapped to JCt−1(uAJ)JC_{t-1}(u_{AJ})), a red-highlighted selected child box (uA∗J∗+ξt−1u_{A_*J_*}+\xi_{t-1} mapped to J∗Ct−1(uA∗J∗+ξt−1)J_*C_{t-1}(u_{A_*J_*}+\xi_{t-1})) and a right box of other child inputs. Arrows from all three, the middle one red, point to a summation box reading "Sum over every child (A,J)∈I(A,J)\in\mathcal I" with noisy aggregate (x′,y′)=(x,y)+J∗Δ(x',y')=(x,y)+J_*\Delta. That box points down to a final box, "Noisy parent output y′+Q(x′)∈By'+Q(x')\in B". The figure shows how noise in only one uniformly chosen child propagates through the embedding, summation and quadratic map to the parent output.
Read from the image by claude-opus-5.5 · confidence 80%
SupportslemLatent coloring change probability formulalemLatent alphabet gadget with detecting noiselemBlock coloring changes with probability 1−θ

Sources

PaperOpen
Section
§3.3 Concatenation and its noise
Page
—
Label
lem:latent-noise
Line
sections/02-latent.tex:429
Leannot aligned

Phase 2 aligns this node to a Lean declaration.