Tree reconstruction: sharp thresholds and nonlinear capacity

Source and verification

This article explains family 229 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

Broadcasting asks whether a noisy signal at a tree’s root can still be inferred from distant descendants. Family 229 claims exact three- and four-state thresholds, including equality, and a nonlinear-capacity criterion for four-state broadcasting on irregular trees.

🏷️ Preliminaries: channels and posterior information

Choose the root label uniformly from $q$ states. Each edge independently transmits its parent label through the symmetric channel

$$P_{\lambda }(j\mid i)=\lambda 1_{\{i=j\}}+\frac{1-\lambda }{q}.$$

The parameter $\lambda$ is the nonconstant eigenvalue of this transition matrix. For three states it may range from $-1/2$ to $1$; negative values favor disagreement. The four-state results here concern the ferromagnetic range $\lambda \ge 0$.

Observe the labels at depth $n$, together with the tree when it is random. If $p_n$ is the posterior distribution of the root and $u$ the uniform distribution, the reconstruction advantage is

$$a_n=\mathbb{E}\Vert p_n-u{\Vert }_{\mathrm{TV}}.$$

It decreases with depth by data processing. Reconstruction means its limit is positive. In a Poisson Galton–Watson tree the expectation includes extinction; it is not conditioned on survival.

🏷️ Exact thresholds and their ranges

For the four-state ferromagnetic channel, the first companion claims reconstruction exactly when $d{\lambda }^2>1$, on every regular $d$-ary tree with $d\ge 2$ and every Poisson offspring tree with mean $d>0$. Here $d$ counts children, not undirected degree. (OpenAI, 2026)

For three states, another companion claims the same exact criterion on every regular tree with at least two children and every observed Poisson tree of mean greater than one, including both signs of $\lambda$ and nonreconstruction at equality. Its sparse three-community graph consequence has threshold

$$(a-b{)}^2>3(a+2b),$$

for fixed positive within- and between-community rates $a,b$, assuming mean degree $(a+2b)/3>1$. The graph implication uses the additional tree-to-graph and algorithmic results stated in the manuscript. (OpenAI, 2026a)

The linear scale $d{\lambda }^2$ comes from competition between exponentially many descendants and the squared decay of one transmitted signal. The difficult direction is showing that nonlinear estimators cannot reconstruct below that linear threshold.

🏷️ The critical nonlinear saving

For a four-state posterior $p$, define its quadratic information by $A(p)=4{\sum }_i{p}_i^2-1$. One channel step multiplies its expectation by ${\lambda }^2$. Combining several child observations is nonlinear and can increase information beyond a naive sum.

The four-state paper constructs a polynomial constraint on the law of the posterior that is preserved by both transmission and combination. Within that class, its combination inequality yields a recursion of the form

$$m_{n+1}\le d{\lambda }^2{m}_n-c{m}_n^3,c>0.$$

At equality, the negative cubic term is decisive. If a positive limit $m$ remained, passing to the limit would give $m\le m-c{m}^3$, a contradiction. Below equality, the linear factor already contracts. The polynomial inequalities use an exact-arithmetic certificate; that certificate was not executed for these notes.

The three-state proof uses different posterior functionals, including entropy and higher moments. It excludes nonuniform limiting posterior fixed points, with separate arguments needed for the negative channel. The four-state cubic calculation should not be presented as a proof for every number of states.

🏷️ Nonlinear capacity on an irregular tree

For a bounded-degree deterministic rooted tree and $0<\lambda <1$, assign a nonnegative flow $\theta (e)$ to each edge, conserved at nonroot vertices. Its total outgoing root flow is $|\theta |$. For an infinite ray $\xi$, put

$$V_{\lambda }(\theta ,\xi )=\sum _{e\in \xi }({\lambda }^{-2|e|}\theta (e){)}^2,$$

where $|e|$ is the child endpoint’s depth. The $L^3$ capacity is the supremum of $|\theta |$ over flows for which every ray has potential at most one. The exponent in this path sum is $3-1=2$.

The capacity companion claims that four-state reconstruction occurs exactly when this capacity is positive. It imports the preserved posterior class and moment-saving inequality from the threshold paper. No regular growth assumption on the tree is imposed. (OpenAI, 2026a)

On a $d$-ary tree, the symmetric unit flow has value $d^{-k}$ on depth-$k$ edges. Its ray potential is

$$\sum _{k\ge 1}(d{\lambda }^2{)}^{-2k}.$$

This is finite above the threshold and divergent at equality, matching the regular-tree criterion. On irregular trees, the arrangement of branching bottlenecks matters, and capacity retains information an exponential growth rate can miss. The restriction $\lambda <1$ is essential: a single infinite ray transmits perfectly at $\lambda =1$, although the displayed capacity vanishes.

🏷️ Key steps and proof outlines

The threshold proof needs an invariant class of posterior laws, not a pointwise inequality for every posterior. The irregular-tree theorem additionally needs to convert information into a conserved flow and back. The three-state companion uses a different invariant, with special work near the negative coloring channel.

Bayes’ rule includes a change of observation law

If two observations are conditionally independent given a uniform four-state input, let $p,q$ have their separate marginal posterior laws $\mu ,\nu$. Their actual joint observation law is not $\mu \otimes \nu$. Relative to that independent product it has density

$$z=4\sum _i{p}_i{q}_i,P_i=4p_i{q}_i/z.$$

Indeed, the likelihood of one observation conditional on input $i$ is $4p_i$, so averaging the product of likelihoods over $i$ gives $z$. Its integral is one because both posterior means are uniform. Thus combined expectations are $\int zf(P)d\mu d\nu$. At $z=0$, the chosen value of $P$ is irrelevant.

This weighting is the reason independent branch calculations are legitimate: factor expectations under $\mu \otimes \nu$ before applying $z$. Treating the actual marginal branch observations as independent would give the wrong recursion.

The preserved polynomial constraint supplies the cubic saving

Use coordinates

$$x=(p_1+p_2-p_3-p_4,p_1-p_2+p_3-p_4,p_1-p_2-p_3+p_4).$$

Set $A=|x{|}^2$, $B=x_1{x}_2{x}_3$, $C=x_1^2{x}_2^2+x_1^2{x}_3^2+x_2^2{x}_3^2$, and

$$\begin{array}{rl}H=& B-A^2/10-3C/20+3AB/10\\ & -A^3/50+7AC/100-51B^2/100.\end{array}$$

The invariant class consists of symmetric laws with $\mathbb{E}H\ge 0$. This allows individual negative values: $H(1/2,1/2,0,0)=-3/25$. The informative and uninformative laws belong to the class. A channel scales $x$ by $\lambda$; the source’s inequality $H(\lambda x)\ge {\lambda }^{3}H(x)$ preserves the constraint.

For products, average the weighted posterior expression over all 24 relative permutations of the two inputs. The exact polynomial certificate gives a lower bound for the new $H$ involving the old $H$ times a nonnegative auxiliary polynomial, and an upper bound for the new $A$ with a negative term

$$\frac{A(p)A(q)(A(p)+A(q))}{1000}.$$

After integration, independence factors the auxiliary terms; their signs follow from $\mathbb{E}H\ge 0$, not from pointwise positivity of $H$. Jensen’s inequality then shows that two branch laws of equal mean information $b$ save at least $2b^3/1000$.

At depth $n+1$, combine the first two branches first, then use subadditivity for the remaining branches. If $D$ is the offspring count and $m_n=\mathbb{E}A(p_n)$, the resulting exact bound is

$$m_{n+1}\le d{\lambda }^2{m}_n-\frac{2}{1000}\mathbb{P}(D\ge 2)({\lambda }^2{m}_n{)}^3.$$

The offspring count is an observed random variable independent of the input, so mixing over it preserves the law constraint. At equality, its positive cubic saving forces the decreasing sequence $m_n$ to zero. Finally $\mathbb{E}\Vert p_n-u{\Vert }_{\mathrm{TV}}\le \sqrt{m_n}/2$ transfers moment decay to nonreconstruction (OpenAI, 2026c).

The polynomial step has an exact finite verification interface. Rational midpoint subdivisions cover the product of two ordered posterior simplices; a cell is accepted only when a coefficient certificate proves its sign. The manuscript reports zero unresolved cells in its two checks. These are reported certificate results, not executions performed for this article. Coverage of boundary points and positivity of cleared denominators are part of the certificate argument, so a numerical grid would not replace it.

A cubic change of variables creates loss at one-child vertices

On an irregular tree put $r={\lambda }^2$ and let $m_v$ be the limiting information at $v$. For child contributions $b_w=r{m}_w$, write $S={\sum }_w{b}_w$ and

$$D=\underset{w\ne w^{\prime }}{\max }{b}_w{b}_{w^{\prime }}(b_w+b_{w^{\prime }}),$$

with $D=0$ when there are fewer than two children. Combining the chosen pair first gives $m_v\le S-cD$. If the number of children is bounded by $B_0$, then $S^3\le {\sum }_w{b}_w^3+B_0^{3}D$.

Choose $K{B}_0^3\le c$ and set $y_v=m_v+K{m}_v^3$. The two inequalities imply

$$y_v\le r\sum _w{y}_w-Kr(1-r^2)\sum _w{m}_w^3.$$

The last term is positive even with a single child, because $r<1$. Since $m_w\le 3$, rescaling $y$ gives labels $z_v$ satisfying

$$z_v\le \sum _w\frac{r{z}_w}{\sqrt{1+z_w^2}}.$$

Choose coefficients $0\le d_{vw}\le r/\sqrt{1+z_w^2}$ with $z_v={\sum }_w{d}_{vw}{z}_w$. Starting from ${\ell }_{\rho }=1$, put ${\ell }_w={\ell }_v{d}_{vw}$ and $\theta (v,w)={\ell }_w{z}_w$. This is a conserved flow. For $g_v=r^{-|v|}{\ell }_v$,

$$(r^{-|w|}\theta (v,w){)}^2\le g_v^2-g_w^2.$$

Summing along each ray telescopes to at most one. Positive root information therefore constructs positive capacity, including through long stretches without branching.

A flow controls the loss of information in the converse

Scale an admissible flow down. At each observed terminal vertex add independent channel noise calibrated so its information equals the depth-weighted incoming flow. This gives a uniform upper envelope for information propagated toward the root. To bound losses, track the signed third moment $\tau =\mathbb{E}(x_1{x}_2{x}_3)$ as well as $m$.

At each combination, at least one input law has passed through the $\lambda$-channel. Its posterior coordinates are at least $(1-\lambda )/4$, so the product normalizer satisfies $1+x\cdot y\ge 1-\lambda >0$. For the independent marginal vectors $x,y$, the combined coordinates are $(x+y+R)/(1+x\cdot y)$, with $R_i=x_j{y}_k+x_k{y}_j$. Symmetry gives

$$\mathbb{E}|R{|}^2=2m_x{m}_y/3,\mathbb{E}(x\cdot y{)}^2=m_x{m}_y/3.$$

These terms cancel in the quadratic expansion. The remaining loss is bounded by $7(|{\tau }_x|m_y+m_x|{\tau }_y|)$, while the third-moment magnitude grows by at most a constant times $m_x{m}_y$ beyond its additive terms. Along edges, $m$ scales by ${\lambda }^2$ and $\tau$ by ${\lambda }^3$. Sampling a ray according to the flow turns cumulative losses into a path sum with summable kernel ${\lambda }^{j-i}$. The capacity bound controls that quadratic sum, and sufficiently small fixed degradation leaves positive root information uniformly in the observation depth. This explains both the converse and its dependence on $\lambda <1$ (OpenAI, 2026a).

The negative three-state endpoint needs another functional

For a normalized three-state likelihood vector $m=1+v$, let $G=(m_0{m}_1{m}_2{)}^{1/3}$, $u_i=\log m_i-\frac{1}{3}{\sum }_j\log m_j$, and define $T=1-G$, $W=G\frac{1}{3}{\sum }_i{u}_i^2$, $Y=G\frac{1}{3}{\sum }_i{u}_i^3$. These weighted functions extend continuously to the boundary.

In a branch product, the observation-density normalizer cancels the denominator in the geometric mean, and centered logs add. Permutation symmetry gives $\mathbb{E}(G{u}_i)=0$, so cross terms in the square and cube vanish under the independent branch law. This yields exact fixed-point identities involving the offspring generating function and the edge versions of $T,W,Y$.

The source combines those identities into a zero-mean expression, adjusts coefficients to cancel its low-order terms near the uniform posterior, and proves a strictly positive pointwise lower bound in the stated parameter ranges by rational interval certificates. This contradicts a nonuniform fixed point. Near the coloring endpoint, a separate finite domination calculation takes over; a local small-information exclusion connects the two regimes. The positive-channel argument is separate as well. The proof therefore covers the negative equality case through a specified union of analytic and certified ranges, rather than extrapolating the four-state cubic recursion (OpenAI, 2026b).

See Also

• Family 236 connects the binary reconstruction threshold with root-free sampling of a tree Ising state.
• Family 231 introduces factor-of-IID sampling, a different question from estimating a root from distant observations.

🏷️ Manuscripts and verification scope

• The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model — pinned manuscript and companion source.
• A Capacity Criterion for Four-State Potts Reconstruction on Trees — pinned manuscript and companion source.
• The exact reconstruction threshold for the three-state symmetric channel — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The documented selection covers only the supercritical reconstruction direction for the three-state channel. It does not cover nonreconstruction at or below equality, the graph-recovery consequence, the four-state threshold, or the irregular-tree capacity theorem. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A Capacity Criterion for Four-State Potts Reconstruction on Trees.

🐻  OpenAI 2026b. The exact reconstruction threshold for the three-state symmetric channel.

🐻  OpenAI 2026c. The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model.