we-solve (beta)

Math-2922 · mathematics · Probability

The exact three-state reconstruction threshold including equality

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Statement recorded in the supplied source.
For the symmetric three-state broadcast channel with admissible $-$1/2$\leq$lambda$\leq$1, is reconstruction on every b-ary tree $b\geq 2$ and observed Poisson(d) offspring tree $d>1$ equivalent to d $\lambda ^2>1$, including antiferromagnetic parameters and nonreconstruction at equality?

Short English statement

For the symmetric three-state broadcast channel with admissible $-$1/2$\leq$lambda$\leq$1, is reconstruction on every b-ary tree $b\geq 2$ and observed Poisson(d) offspring tree $d>1$ equivalent to d $\lambda ^2>1$, including antiferromagnetic parameters and nonreconstruction at equality?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-2922-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-2922

Three-state symmetric broadcasting is claimed reconstructible precisely when $d\lambda^2>1$ on regular and observed Poisson trees, for both signs of the channel parameter. The question retains these same parameters and conventions. Within these assumptions, this is a claimed affirmative answer to the stated question.

The exact three-state reconstruction threshold including equality

OpenAI's claim

OpenAI presents a proof in the selected manuscript. Three-state symmetric broadcasting is claimed reconstructible precisely when $d\lambda^2>1$ on regular and observed Poisson trees, for both signs of the channel parameter.

Mathematical statement of the claimed result

Result 1.
The tree channel has three equally likely states and transition matrix with diagonal $(1+2\lambda)/3$ and off-diagonal $(1-\lambda)/3$, so $-1/2\le\lambda\le1$. On a regular tree with branching $b\ge2$, or a Poisson Galton--Watson tree of mean $d>1$, the claim gives \[ \text{reconstruction}\quad\Longleftrightarrow\quad d\lambda^2>1, \qquad d=b\text{ in the regular case}, \] with nonreconstruction at admissible equality. The SBM corollary fixes $a,b>0$, $(a+2b)/3>1$, assigns independent uniform labels in $\{1,2,3\}$, and uses edge probabilities $a/n$ within a label and $b/n$ across labels. For overlap maximized over label permutations, it claims \[ (a-b)^2\le3(a+2b)\ \Longrightarrow\ \mathbb E\operatorname{ov}(\sigma,\widehat\sigma_n)\to1/3 \] for every estimator from the graph and independent randomness. Under the strict reverse inequality, some $O(n\log n)$ algorithm achieves overlap at least $1/3+\varepsilon$ with probability tending to one. These SBM statements retain the mean-degree assumption. Reconstruction means $\lim_{\ell\to\infty}a_\ell>0$, where \[ a_\ell=\mathbb E\left\|\mathbb P(\sigma_{\varnothing}\in\cdot\mid T_{\le\ell},\sigma_{\partial T_\ell})-\operatorname{Unif}\{1,2,3\}\right\|_{\mathrm{TV}}. \] The tree shape in the conditioning is unlabelled. In the Galton--Watson case the expectation includes extinct trees; it is not conditioned on survival.

Outline of the argument

The posterior is represented by a complex mean and two invariant statistics. Fixed-point inequalities separately exclude positive and negative threshold reconstruction, and an exact finite certificate treats the coloring boundary; known transfer theorems then give the corresponding three-community graph recovery threshold.

Formal verification

For family 229, the three-state Comparator entries only establish reconstruction when $d\lambda^2>1$. They omit threshold nonreconstruction, the graph recovery corollary, and the four-state companions. The listed Comparator files are ThreeStateSupercritical.lean, ThreeStateTreeClauses.lean. The inventory does not supply a named declaration for these Comparator entries. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources

Go to contribution →