Potts Model: OpenAI’s Proof Pinpoints Where Four-State Information Disappears

Imagine a telephone game where every player hears one of four colors and passes a noisy copy to several children. You see every color in the last row. As that row gets farther away, can you still tell what the first player heard? For the ferromagnetic four-state Potts model, OpenAI’s proof locates the exact cutoff on regular and Poisson branching trees. If dd measures branching and λ\lambda measures the signal retained by one transmission, root information survives precisely when dλ2>1d\lambda^2>1. At equality, the linear signal budget balances exactly, but a cubic loss makes the evidence fade.

1. What Is the Potts Model?

The qq-state Potts model assigns one of qq discrete spins to each vertex of a graph. Ferromagnetic interactions favor neighbors with matching spins. With two labels, this is the Ising model after reparameterizing the interaction.

On a tree, each child samples from a distribution that favors its parent’s color. This turns a question about the influence of a distant boundary into a question about inference from noisy copies.

Key facts about the four-state broadcast model and its threshold.
FeatureWhat the Paper Studies
Root stateOne of four equally probable colors.
Edge parameterλ∈[0,1]\lambda\in[0,1] measures how strongly a child’s color depends on its parent’s.
Tree familiesRegular trees with d≥2d\ge 2 children per vertex and Poisson Galton–Watson trees with mean d>0d>0.
Exact cutoffReconstruction for dλ2>1d\lambda^2>1. Nonreconstruction for dλ2≤1d\lambda^2\le 1.

2. The Four-Color Telephone Tree and the Reconstruction Problem

A four-color Potts model tree with a hidden root and eight observed leaves at depth three.
A four-color Potts model tree with a hidden root and eight observed leaves at depth three.

A simple way to implement the channel is to copy the parent with probability λ\lambda and otherwise draw a color uniformly, allowing the draw to match the parent by chance. For colors i,j∈{1,2,3,4}i,j\in\{1,2,3,4\}, with ii the parent’s color and jj the child’s, the transition law is

𝑷𝝀(𝒋|𝒊)=𝝀𝟏{𝒊=𝒋}+1−𝝀4.\boldsymbol{P_\lambda(j\mid i)=\lambda\,\mathbf{1}_{\{i=j\}}+\frac{1-\lambda}{4}.}

For λ=1/2\lambda=1/2, a red parent produces a red child with probability 5/85/8 and each other color with probability 1/81/8. On a tree with two children per vertex, suppose you observe two red children. By Bayes’ rule, the probability of a red root becomes 25/(25+1+1+1)=25/2825/(25+1+1+1)=25/28. With one red and one blue child, red and blue instead tie at 5/125/12 each.

At depth nn, the observer sees the colors exactly nn edges from the root, along with the tree. Random guessing succeeds one quarter of the time. To express what the full observation tells us, the paper measures the expected total variation distance between the root’s posterior and the uniform prior. That distance is half the sum of the four absolute probability shifts. If it tends to zero, the advantage of even the best root guess also tends to zero.

3. The Kesten–Stigum Threshold and the Longstanding Puzzle

The channel has eigenvalue one on constant functions and eigenvalue λ\lambda on every mean-zero color contrast. For example, give red score one, blue score minus one and the other colors zero. The expected score after a transmission is λ\lambda times the parent’s score. A second-moment calculation therefore picks up λ2\lambda^2 for signal strength and a factor of dd for branching. Above dλ2=1d\lambda^2=1, the classical Kesten–Stigum direction gives reconstruction.

The reverse direction has to bound the entire posterior. A linear calculation predicts what happens to weak signals, while the process starts with an exactly observed spin at depth zero. Combining several weak or strong observations can produce effects invisible to a calculation that tracks individual color contrasts.

The binary symmetric case was already understood, and Allan Sly showed that the spectral criterion can fail for larger Potts alphabets, including ferromagnetic models with at least five colors at sufficiently large degree. Elchanan Mossel, Sly and Youngtak Sohn proved four-state nonreconstruction up to and including the critical point in a sufficiently large mean-degree regime. The paper’s new target is the full range of branching parameters in the two specified families.

4. What OpenAI’s New Proof Establishes

	Potts model threshold chart showing root information vanishing at and below dλ² = 1.
Potts model threshold chart showing root information vanishing at and below dλ² = 1.

Theorem 1.1 of the October 5, 2026 manuscript gives nonreconstruction whenever dλ2≤1d\lambda^2\le 1 and 0≤λ≤10\le\lambda\le 1, for every regular dd-ary tree with integer d≥2d\ge 2 and every Poisson Galton–Watson tree of real mean d>0d>0. Here dd counts children or their mean. Paired with the known supercritical result, it makes the threshold exact in both families.

In the Poisson model, the tree is sampled independently of the spins, and the entire unlabelled tree is available to the observer. The expectation includes extinct trees. When level nn is empty, its observation contains no colors and the tree alone leaves the root uniform. Above threshold, the known reconstruction result applies on survival, which has positive probability in the supercritical range, and so yields a positive advantage after averaging over all trees.

5. The Complete Proof Strategy in Six Stages

OpenAI attributes the release’s results to an internal frontier model. The sequence below reconstructs the manuscript’s argument from its mathematical dependencies. The supplied sources leave open how the model arrived at the particular polynomial.

  1. Replace the boundary with four probabilities. Each observed boundary induces a posterior over the root colors. Track how those posteriors vary across observations.
  2. Measure the departure from uniform. Squared distance from the uniform distribution contracts exactly across one edge. Its decay would settle reconstruction.
  3. Account for how branches agree. Multiply color-by-color evidence and normalize it. The normalization also reweights which observation pairs occur, so the proof must control the update and its averaging together.
  4. Keep one more statistic. A degree-six polynomial defines a constraint on the distribution of posteriors. The constraint starts out true and remains true after an edge, a branch merger or an observed mixture.
  5. Find a loss at each branching step. Inside that class of posterior laws, the first two branches yield a strict saving in expected information. At criticality, that saving rules out a positive limit.
  6. Certify the inequalities on whole regions. Use symmetry, exact coefficients and a finite subdivision of two probability simplices to prove the needed signs. The certificates apply to every allowable posterior pair, including those far from uniform.

6. Measuring Information in Posterior Probability Distributions

The posterior p=(p1,p2,p3,p4)p=(p_1,p_2,p_3,p_4) has four nonnegative coordinates that sum to one. Its probability simplex therefore has three independent dimensions. Write u=(1/4,1/4,1/4,1/4)u=(1/4,1/4,1/4,1/4) for the uniform point. The paper’s quadratic information is

𝑨(𝒑)=4∑𝒊=14𝒑𝒊2−1=4∑𝒊=14(𝒑𝒊−14)2.\boldsymbol{\begin{aligned}A(p)&=4\sum_{i=1}^4 p_i^2-1\\&=4\sum_{i=1}^4\left(p_i-\frac14\right)^2.\end{aligned}}

It is zero at uu and three at a vertex where one color is certain. Across an edge, a posterior pp about the child becomes Cλ(p)=u+λ(p−u)C_\lambda(p)=u+\lambda(p-u) about the parent. Every centered coordinate is multiplied by λ\lambda, so A(Cλ(p))=λ2A(p)A(C_\lambda(p))=\lambda^2 A(p) for each posterior, and the same relation holds in expectation.

For example, p=(5/8,1/8,1/8,1/8)p=(5/8,1/8,1/8,1/8) has A(p)=3/4A(p)=3/4. Passing the evidence through another edge with λ=1/2\lambda=1/2 gives (7/16,3/16,3/16,3/16)(7/16,3/16,3/16,3/16) and A=3/16A=3/16. The expected value of AA gives depth-wise progress. Controlling a merger takes more because the size of a deviation alone leaves out which colors the two observations favor.

7. Why Combining Multiple Branches Is Mathematically Difficult

Two child subtrees produce independent observations conditional on the root color. Marginally, both depend on the same unknown color. For instance, with the two children in the red example, the probability both are red is 7/647/64, while the product of their individual red probabilities is 1/161/16.

Let pp and qq be the two individual posteriors about the root after their edge steps. With a uniform prior, their joint posterior PP is obtained by multiplying corresponding coordinates. Let zz denote the weight that converts the independent product of the marginal observation laws into the true joint law.

𝒛(𝒑,𝒒)=4∑𝒊=14𝒑𝒊𝒒𝒊,𝑷𝒊(𝒑,𝒒)=4𝒑𝒊𝒒𝒊𝒛(𝒑,𝒒)(𝒛>0).\boldsymbol{\begin{gathered}z(p,q)=4\sum_{i=1}^4 p_iq_i,\\P_i(p,q)=\frac{4p_iq_i}{z(p,q)}\quad(z>0).\end{gathered}}

For an expected statistic of PP, the proof can sample pp and qq independently from their respective marginal posterior laws and weight the statistic by zz. Pairs with z=0z=0 have zero weight. Aligned evidence may receive more weight and also move the combined posterior farther from uniform. The denominator and the change of measure explain why a spectral calculation for a single edge leaves the merger unresolved.

8. The Degree-Six Polynomial Behind the Breakthrough

Use three contrasts x1=p1+p2−p3−p4x_1=p_1+p_2-p_3-p_4, x2=p1−p2+p3−p4x_2=p_1-p_2+p_3-p_4 and x3=p1−p2−p3+p4x_3=p_1-p_2-p_3+p_4. Permuting the four colors permutes these contrasts and changes an even number of their signs. This makes A=x12+x22+x32A=x_1^2+x_2^2+x_3^2, B=x1x2x3B=x_1x_2x_3 and C=x12x22+x12x32+x22x32C=x_1^2x_2^2+x_1^2x_3^2+x_2^2x_3^2 invariant under relabeling. In particular, BB and CC capture aspects of the contrasts that their total squared size leaves undetermined.

𝑯=𝑩−𝑨210−3𝑪20+3𝑨𝑩10−𝑨350+7𝑨𝑪100−51𝑩2100.\boldsymbol{\begin{aligned}H&=B-\frac{A^2}{10}-\frac{3C}{20}+\frac{3AB}{10}\\&\quad-\frac{A^3}{50}+\frac{7AC}{100}-\frac{51B^2}{100}.\end{aligned}}

The manuscript specifies HH, FF and GG as linear combinations of the same nine monomials in AA, BB and CC. The degree-six terms appear in HH, while FF and GG have degree five. The signs of FF and GG connect the constraint to each merger. The key condition is 𝔼[H]≥0\mathbb{E}[H]\ge 0 for a symmetric posterior law. For an exactly revealed color, H=13/100H=13/100. At uniformity it is zero. Individual posteriors can have negative values, such as H=−3/25H=-3/25 when two colors each have probability one half. The edge inequality H(λx)≥λ3H(x)H(\lambda x)\ge\lambda^3 H(x) propagates the expectation constraint.

For mergers, the proof averages the weighted update over the 24 possible relative color permutations. Because each marginal law is symmetric, this averaging preserves the desired expectation. The lower bound for the averaged zH(P)zH(P) contains the paired terms H(p)G(q)+G(p)H(q)H(p)G(q)+G(p)H(q), where G≥0G\ge 0. Under independent marginal sampling, their expectations factor and the result is nonnegative. In the upper bound for zA(P)zA(P), analogous terms with a nonnegative polynomial FF can be subtracted. The bound also subtracts A(p)A(q)(A(p)+A(q))/1000A(p)A(q)(A(p)+A(q))/1000. If both branches have mean information bb, Jensen’s inequality turns this last term into a saving of at least 2b3/10002b^3/1000.

9. The Cubic Correction That Forces Information to Disappear

	Potts model proof diagram showing why a cubic loss forces mean information to zero at the threshold.
Potts model proof diagram showing why a cubic loss forces mean information to zero at the threshold.

Let mnm_n be the mean of AA for the depth-nn experiment on the ordered tree truncated at that depth. Each branch supplies b=λ2mnb=\lambda^2m_n. Use the saving on the first two branches when they exist, then add at most bb for each further branch. An observed offspring count DD is independent of the root, so averaging these bounds over DD preserves the constraint and gives

𝒎𝒏+1≤𝒅𝝀2𝒎𝒏−𝒄𝒎𝒏3,𝒄=2𝝀61000Pr⁡(𝑫≥2).\boldsymbol{\begin{gathered}m_{n+1}\le d\lambda^2m_n-cm_n^3,\\c=\frac{2\lambda^6}{1000}\Pr(D\ge 2).\end{gathered}}

For regular branching the probability is one. For Poisson branching it is 1−(1+d)e−d1-(1+d)e^{-d}, positive for every d>0d>0. At λ=0\lambda=0 the first transmission erases all information. Below threshold, dropping the cubic term already gives geometric decay. At equality, mnm_n decreases toward a nonnegative limit ℓ\ell. The inequality forces ℓ≤ℓ−cℓ3\ell\le\ell-c\ell^3, hence ℓ=0\ell=0. Above threshold, reconstruction comes from the separate Kesten–Stigum result.

Toy cubic recursion below, at and above the threshold Twelve steps from a common initial value of 0.5. The below-threshold curve falls fastest. The threshold curve falls slowly. The above-threshold curve rises toward a positive fixed point. The curves illustrate a toy recursion. 0 0.25 0.50 0.75 1.00 0 3 6 9 12 Step Toy information Below At Above
Illustrative cubic recursion with linear multipliers 0.8 (below), 1 (at) and 1.2 (above). Each starts at 0.5 and subtracts one quarter of the current value cubed. The plotted values are computed examples. The manuscript gives an inequality for the actual tree information.

The rest of an ordered tree below depth nn adds no spin information once its truncation is known. Forgetting the ordering can only reduce the expected total variation distance, by convexity. The paper bounds the resulting advantage by mn/2\sqrt{m_n}/2. This even covers the noiseless Poisson case d=λ=1d=\lambda=1, where a nonempty level reveals the root perfectly but has probability tending to zero.

10. Inside the Computer-Assisted Mathematical Proof

The verifier sorts each posterior’s coordinates using color symmetry. The sorted vectors form a simplex. In barycentric coordinates, the proof writes polynomials in homogeneous form by multiplying lower-degree terms by powers of the sum of the coordinates, which equals one. Every monomial is nonnegative there. If all coefficients are nonnegative, the polynomial is nonnegative throughout the region.

The two merger inequalities contain denominators from Bayes’ rule. Type T bounds each inverse power of the normalizer from below using a fifth-degree Taylor polynomial about one. The sixth-order remainder is nonnegative, and the proof first shifts the numerator so multiplication preserves the inequality. Type P interpolates each rational term on a grid with 20 lattice nodes in each simplex. It subtracts an explicit correction certified by coefficient signs after clearing the positive denominator. The checked remainder guarantees the bound between grid points as well. The weighted terms extend continuously by zero where the normalizer vanishes.

When neither test accepts a cell, the verifier splits one simplex at an edge midpoint and checks both children, whose union covers the parent. The manuscript reports the following exact traversal totals.

Manuscript Table 2. Counts of cells visited include both terminal cells and cells split during the verification.
Verification MetricInformation BoundConstraint Bound
Cells visited4,4791,935
Maximum depth1920
Type T leaves16697
Type P leaves2,074871
Unresolved cells00

Appendix A gives C++ and Python verifiers. The reproduction notes distinguish rerunning the full traversals from checking the retained traversal records. Exact arithmetic settles the polynomial signs, while the manuscript supplies the probabilistic argument. The linked Lean scope document covers supercritical reconstruction for a three-state channel. This four-state theorem is established by the manuscript’s computer-assisted argument.

11. Why the Four-State Reconstruction Threshold Matters

This Potts model phase transition identifies when distant leaf evidence can retain a lasting statistical advantage about the root. In statistical mechanics, it isolates a transition in what the boundary reveals about a hidden spin. Other notions of ordering, and graphs with cycles, pose separate mathematical questions. A percolation threshold, for example, asks when an infinite connected cluster can exist. The observable here is the information in the posterior of a single hidden color.

The ferromagnetic assumption matters. Four-state antiferromagnetic examples can reconstruct below the Kesten–Stigum threshold, and the theorem treats regular and Poisson offspring. A natural question is which other offspring distributions admit a comparable threshold proof and whether their branch mergers preserve a useful polynomial constraint. The cubic bound establishes disappearance of information at the threshold. Pinning down the exact rate at which the optimal guessing advantage vanishes is a finer question.

At exact linear balance in the four-state Potts model, the loss from combining branches survives averaging and compounds with depth. Follow Binary Verse AI for more research explainers that work from the theorem back to the idea that makes the proof succeed.

What is the Potts model?

The Potts model assigns each vertex of a graph one of several discrete spin states. In the ferromagnetic version, neighbors favor matching states. In the paper’s tree broadcast model, each child receives a noisy copy of its parent’s state.

What is the difference between the Potts model and the Ising model?

The Ising model has two spin states. The qq-state Potts model allows qq states and reduces to the Ising model at q=2q=2 after reparameterizing the coupling. OpenAI’s paper studies the ferromagnetic case with q=4q=4.

What is the Kesten–Stigum threshold for the Potts model?

The Kesten–Stigum threshold is dλ2=1d\lambda^2=1, where dd is the number of children or mean offspring count and λ\lambda measures the correlation transmitted across an edge. For the two four-state ferromagnetic tree models in the paper, reconstruction is possible exactly when dλ2>1d\lambda^2>1.

What did OpenAI prove about the four-state Potts model?

OpenAI proved nonreconstruction for dλ2≤1d\lambda^2\le 1 in the ferromagnetic model on every regular dd-ary tree with integer d≥2d\ge 2 and every observed Poisson Galton–Watson tree with mean d>0d>0. The Poisson result averages over all trees, including those that die out.

What happens exactly at the reconstruction threshold?

The root posterior converges to the uniform prior in expected total variation as depth grows. The linear coefficient in the quadratic information bound equals one, and a strictly negative cubic correction when information is positive forces its mean to zero.

Is OpenAI’s Potts model proof formally verified?

The four-state result is established by a computer-assisted proof. The paper supplies the probabilistic argument and exact-arithmetic certificates checked by C++ and Python programs. The associated Lean scope document describes a formalization of above-threshold reconstruction for the related three-state channel.

Leave a Comment