The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model

1 Introduction

In a broadcast process on a tree, each vertex transmits a noisy copy of its spin to its children. The reconstruction problem asks whether the spins far from the root retain information about its initial spin. For the symmetric four-state channel, the linear second-moment threshold has long been expected to be the exact reconstruction threshold in the ferromagnetic regime. We prove the nonreconstruction direction at and below this threshold for all regular and Poisson branching parameters.

1.1 Model and main result

Write [4]=\{1,2,3,4\}. The root spin \sigma_\rho is uniform on [4]. For a parameter \lambda\in[0,1], each edge independently transmits the parent spin through the channel

The parameter \lambda is the nontrivial eigenvalue of the channel; its nonnegativity specifies the ferromagnetic regime.

We consider the rooted d-ary tree, where every vertex has exactly d children, and a Galton–Watson tree with independent Poisson(d) offspring counts. In the latter case the tree is sampled independently of the root spin and the randomness used by the edge channels. The observer is given the entire rooted tree T and the spins \sigma_{L_n} at level L_n=\{v:\operatorname{dist}(v,\rho)=n\}. Let

The tree observation in the Galton–Watson model is unlabelled, the level observation is empty when L_n is empty, and the expectation is not conditioned on survival. Nonreconstruction means that a_n(d,\lambda) tends to zero.

Here d denotes the number of children or its mean, not the total undirected degree. The known Kesten–Stigum reconstruction direction for d\lambda^2>1 makes Theorem 1.1 an exact threshold statement [6, 11, 8]. For Poisson trees, the branching-number reconstruction criterion applies on survival, where the branching number equals d; survival has positive probability when d\lambda^2>1. The theorem is computer assisted: all probabilistic arguments are proved below, and the remaining polynomial inequalities are verified by the complete exact-arithmetic programs in Appendix A.

1.2 History and significance

The Kesten–Stigum criterion originates in the second-moment analysis of multitype branching processes [6]. In tree broadcasting it gives the reconstruction direction above d\lambda^2=1, but the corresponding nonreconstruction assertion depends on the channel. For binary symmetric channels, Bleher, Ruiz, and Zagrebnov established sharpness on regular trees [2]; Evans, Kenyon, Peres, and Schulman developed the general-tree theory [3]. Mossel showed that the spectral criterion need not be necessary for other channels [10]. For Potts channels, this distinction becomes decisive as the number of states increases. Mézard and Montanari proposed threshold coincidence for small alphabets and discussed its extension to all regular degrees [9, Section 8]. Sly proved sharpness for the three-state model on regular trees of sufficiently large degree and established failure of sharpness for q\geq5 [14]. The four-state case lies at the boundary between these behaviors.

Mossel, Sly, and Sohn proved nonreconstruction, including the critical point, for the three- and four-state models on Galton–Watson trees of sufficiently large mean degree under hypotheses that cover both regular and Poisson offspring [12]. Theorem 1.1 removes the large-degree restriction for the ferromagnetic four-state model in these two families. Cavity expansions and numerical investigations by Ricci-Tersenghi, Semerjian, and Zdeborová also support the four-state ferromagnetic threshold [13]; those predictions are distinct from a rigorous all-degree nonreconstruction theorem. The restriction \lambda\geq0 matters: the four-state antiferromagnetic model can reconstruct below the Kesten–Stigum threshold [12].

1.3 The proof mechanism

The key object is the distribution of a posterior probability vector p=(p_1,p_2,p_3,p_4), not an individual vector. Define its quadratic information by

A channel step multiplies \E A by \lambda^2. The problem is to control the nonlinear combination of the observations arriving from different children. We construct a degree-six polynomial H for which the additional constraint \E H(p)\geq0 is preserved by both channel steps and the combination of observations. Two explicit polynomial inequalities then make \E A subadditive under combination, with a strictly positive cubic saving when two informative branches are present.

Writing m_n for the expected quadratic information at depth n, this gives, for \lambda>0, a recursion of the form

The cubic term is essential at equality: it forces m_n\to0 even when the linear coefficient equals one. The constraint on the posterior law is linear, so it also survives mixtures over the observed offspring count. This is what allows the same pairwise inequalities to treat the Poisson and regular models.

Expected functionals of posterior distributions are central to earlier entropy and stochastic Lyapunov methods, including the work of Formentin and Külske [4]. Rigorous computational methods for nonreconstruction include Bhatnagar and Maneva’s survey method [1] and Gu’s population-dynamics method for binary Poisson hypertrees [5]. The additional ingredient here is the explicit polynomial constraint that remains valid during each pairwise combination of observations. Its pairing with the two combination inequalities gives a strict moment saving for every parameter in the two branching families when \lambda>0.

The required inequalities are certified on products of probability simplices by nonnegative homogeneous coefficients, using Taylor lower bounds and interpolation with explicitly certified remainders. The interpolation itself is never assumed to approximate the target accurately. Thus the computation verifies fixed polynomial inequalities on all posterior vectors; the preserved constraint on their laws then supplies the tree argument.

Section 2 gives the posterior operations, and Section 3 states the explicit polynomial inequalities and derives their consequences for posterior laws. Section 4 completes the probabilistic argument. Sections 5 and 6 prove the inequalities through a finite exact-arithmetic calculation.

2 Symmetric posterior experiments

The observations below are experiments about an input that is uniform on [4]. A tree combines such experiments in two ways: an observation passes through one broadcast edge, and observations from different branches are combined. We record the exact posterior laws for these operations, keeping separate the independent laws used in a calculation and the actual law of a combined observation. The normalized posterior update and its change of observation law are standard in broadcasting recursions; see [9, Sections 2.2–2.4].

Write

and let \Sym be the group of permutations of [4]. An experiment consists of a uniform input I\in[4] and an observation Y. Write \kappa_i for the conditional law of Y given I=i, and \kappa=\frac14\sum_i\kappa_i for its marginal law. Since each \kappa_i is absolutely continuous with respect to \kappa, its posterior vector p(Y)\in\Deltafour satisfies

These identities also define the posterior on a general observation space, up to a \kappa-null set. Denote by \mu the law of p(Y) under \kappa. In particular,

Conversely, any probability law \mu with this barycenter is realized by taking the observation space to be \Deltafour and its conditional laws to be 4p_i\,\mathrm d\mu(p). We call the experiment symmetric if \mu is invariant under all permutations of its four coordinates. This is a condition on the law of the posterior, not on an individual posterior vector.

The following coordinates remove the constant direction:

Since L^{\mathsf T}L=4\operatorname{Id}-\boldsymbol{1} \boldsymbol{1}^{\mathsf T}, where \boldsymbol{1}=(1,1,1,1)^{\mathsf T},

Thus decay of the mean of A will imply nonreconstruction.

In (2.4), p and q are independent under \mu\otimes\nu. They generally are not independent under the actual observation law z\,\mathrm d\mu\,\mathrm d\nu. All factorizations of expectations below use the former measure, before the factor z is applied. The choice of P at z=0 never affects a combined expectation.

We will also use observed mixtures of experiments. Suppose an index S is independent of the input and, conditional on S=s, the observation has posterior law \mu_s. If S itself is observed, the resulting posterior law is \int\mu_s\,\mathrm d\Pr_S(s). Hence symmetry and any linear inequality on posterior laws are preserved under such mixtures. In the tree application, S will be the offspring count. The uninformative experiment has posterior law concentrated at \unif; the experiment that reveals the input has posterior law assigning mass 1/4 to each of the four coordinate vectors.

3 A preserved constraint on posterior laws

The second moment \E A(p) measures information about the input, but the estimate we need for products also involves one higher-order statistic. We now give this statistic explicitly. Its expectation will remain nonnegative throughout the recursion, allowing a strict improvement on second-moment subadditivity.

For x=Lp, with L as in Section 2, set

Together with A(p)=x_1^2+x_2^2+x_3^2, these polynomials are invariant under permuting the four entries of p. Indeed, such a permutation acts on x by a permutation of its coordinates and an even number of sign changes. Define H,F,G by the following coefficient table, whose entries are divided by 1000:

Thus, for example, H=B-A^2/10-3C/20+3AB/10-A^3/50 +7AC/100-51B^2/100. We also write H(x) when its three coordinate arguments, rather than the probability vector, are supplied.

For p,q\in\Deltafour and \pi\in\Sym, put

For a continuous function \phi on \Deltafour, use the notation

with each summand set to zero when z_\pi=0. Finally, define

Sections 5 and 6 prove this proposition using exact polynomial sign certificates. We first show how it controls posterior laws; this identifies the purpose of each inequality before the coefficient calculation begins.

Let \mathcal C be the class of symmetric posterior laws \mu for which

The condition is linear in the law. It does not require H(p)\geq0 at every posterior: for example, p=(1/2,1/2,0,0) has H(p)=-3/25. The completely informative experiment and the uninformative experiment belong to \mathcal C, because

Here the informative experiment has posterior law uniform on the four point masses e_i.

4 Decay on the tree

We now apply Proposition 3.2 to the observations in successive generations. The saving from just two branches will suffice; the remaining branches need only satisfy subadditivity.

For the calculation, supply an ordering of the children at every vertex. In the Galton–Watson model, one may construct this ordered tree by giving each vertex an independent offspring count and numbering its children from 1 to that count. Erasing the numbering gives the unlabelled tree in the theorem. Write \widehat T for the ordered tree and \widehat T_{\le n} for its truncation at depth n. Define

Every finite-depth truncation is finite almost surely. Let \mu_n be the law of p^{(n)}, and put

In the random-tree case this integral averages over the tree as well as the spins, without conditioning on survival.

There are two information comparisons to check. First, conditional on \widehat T_{\le n}, the part of \widehat T below depth n is independent of the root and all spins used in Y_n. This follows from the independence of the tree construction and the channel randomness. Consequently, supplying the entire ordered tree leaves the posterior unchanged:

Second, forgetting the ordering cannot increase expected total variation from the prior. Indeed, for observation sigma-fields \mathcal F\subseteq\mathcal G, the posterior given \mathcal F is the conditional expectation of the posterior given \mathcal G; convexity of the total-variation norm gives the assertion. Combining this observation with (2.3) and Jensen’s inequality, the advantage defined in Theorem 1.1 satisfies

It therefore remains to prove that m_n tends to zero.

5 Exact polynomial certificates

We now prove the polynomial inequalities in Proposition 3.1. The single-posterior inequalities follow from small homogeneous coefficient calculations. For the two-posterior inequalities, we give two sufficient tests on a product of simplices. Section 6 applies those tests to a finite subdivision and completes the proof.

5.1 Ordered probabilities and homogeneous coefficients

Let

where e_v is the vth standard basis vector of \R^4. The set \mathcal S is the simplex with vertices S_0,S_1,S_2,S_3. Indeed, on setting p_5=0, its barycentric coordinates are

All X_i are nonnegative. Conversely, each such convex combination lies in \mathcal S.

A permutation of the four probabilities acts on x=Lp by permuting its three coordinates and changing an even number of their signs. One way to check this is to note that, on the hyperplane \sum_vp_v=1, p=\unif+L^{\mathsf T}x/4. For a permutation matrix \Pi, the induced matrix is L\Pi L^{\mathsf T}/4; it is a signed permutation matrix whose three nonzero entries have product 1. Consequently A,B,C, and hence H,F,G, are invariant. It is therefore enough to check the single-posterior inequalities on \mathcal S. The permutation-averaged two-posterior expressions are invariant under separate permutations of p and q: a permutation of q reindexes the average, and a permutation of p can be moved to q by simultaneous permutation of the output coordinates. We may thus restrict both inputs to \mathcal S.

We use ordinary monomial coefficients throughout. For r\ge0, put

The coefficient of X^I in W_r is the multinomial coefficient \binom rI=r!/\prod_iI_i!. A polynomial of degree at most r can be homogenized to degree r by multiplying each degree-s monomial by W_{r-s}. This does not change its values when \sum_iX_i=1. If all coefficients of a homogeneous polynomial are nonnegative, then the polynomial is nonnegative on the simplex. No converse is required. The coefficients in the simplicial Bernstein basis differ from these ordinary homogeneous coefficients by positive multinomial factors, so their signs agree. This is the coefficient-positivity principle behind simplicial Bernstein bounds and their refinement by subdivision; see [7].

The calculations below use only coefficient addition and the product rule

For two sets of variables, write W_r(X,Y)=W_r(X)W_r(Y). A bihomogeneous polynomial of bidegree (r,r), meaning homogeneous of degree r in each set of variables, is stored as the matrix of its coefficients [X^IY^J], with I,J\in\mathcal I_r. Multiplication is convolution in both indices; multiplication by W_s(X,Y) raises both homogeneous degrees by s. A monomial of degree s in X and degree t in Y is homogenized to bidegree (r,r) by multiplying it by W_{r-s}(X)W_{r-t}(Y).

5.2 The single-posterior checks

The coordinate forms on \mathcal S are particularly small:

Let \Phi_0,\ldots,\Phi_8 be the polynomials 1,A,B,A^2,C,AB,A^3,AC,B^2 in the three coordinates, and let

be their degrees. If R=\sum_jc_j\Phi_j, its degree-r homogeneous form on \mathcal S is

Together with (5.3) and (5.2), this formula specifies every coefficient in the following check.

5.3 The two rational inequalities

It remains to prove the two-posterior inequalities. We express each as the nonnegativity of a rational function on \mathcal S\times\mathcal S. For \pi\in\Sym, let

Set

The remaining data are

In row b, the expression for N_\pi is a polynomial: each degree-s term of H becomes the corresponding term in LU^\pi multiplied by z_\pi^{6-s}. For either row define

In row a, the summand is -z_\pi A(P^\pi); in row b, it is z_\pi H(P^\pi). Thus \mathcal R\ge0 is exactly the corresponding inequality of Proposition 3.1, multiplied by 24.

These rational functions have continuous extensions to their apparent singularities. All coordinates of U^\pi are nonnegative, so z_\pi=0 implies U^\pi=0. Since P^\pi\in\Deltafour whenever z_\pi>0, both A(P^\pi) and H(P^\pi) are bounded independently of p,q. Hence the corresponding weighted summand tends to 0 as z_\pi\to0. We assign it that value on the boundary.

Now take any two nondegenerate subsimplices of \mathcal S, with vertex lists a=(a_0,\ldots,a_3) and b=(b_0,\ldots,b_3), and write

The ordinary bidegree-(1,1) coefficient of U^\pi_v at X_iY_j is 4a_{iv}b_{j,\pi(v)}. In particular, the coefficients of z_\pi are nonnegative. Both p and q are strictly positive on the relative interior of their subsimplices: a full-dimensional simplex cannot lie in a coordinate face of \Deltafour. Thus every z_\pi is strictly positive there. We represent K homogeneously with bidegree (6,6) and N_\pi with bidegree (k+1,k+1).

The next two tests certify \mathcal R\ge0 on such a product of simplices. They establish lower bounds on the entire region, not just at the points used to construct the polynomials.

5.4 A Taylor lower bound: Type T

For a positive integer k, define

For every z>0, Taylor’s theorem gives

for some \xi between 1 and z; at z=1 the identity is immediate. The bound holds for the full positive half-line, with no restriction such as |z-1|<1.

For row a, A(P)\le3 on \Deltafour, because each coordinate of LP lies in [-1,1]. For row b, Lemma 5.1 gives H(P)\ge-1/2. Consequently, in either row,

5.5 A polynomial lower bound with a certified remainder: Type P

The second test constructs a lower bound for each rational summand separately. Start with any bihomogeneous polynomial J_\pi of bidegree (3,3). The way it is chosen affects the strength of the test, but not its validity. We seek a constant c_\pi\ge0 such that

throughout the product simplex. On the relative interior, clearing the positive denominator reduces this to nonnegativity of N_\pi-z_\pi^kJ_\pi+c_\pi z_\pi^k. To test that remainder by homogeneous coefficients, form in bidegree (k+3,k+3) the arrays

where the arguments (X,Y) of W_2,W_3 are suppressed. Every coefficient of Q_\pi is nonnegative.

Fix M=2^{32}. If an entry (O_\pi)_{IJ} is negative and the corresponding entry (Q_\pi)_{IJ} is zero, the test is not applicable. Otherwise define

By construction, O_\pi+c_\pi Q_\pi is coefficientwise nonnegative.

For reproducibility, we specify the polynomials J_\pi used in the finite check. For I\in\mathcal I_3, define the cardinal polynomial

At a lattice point J/3, with J\in\mathcal I_3, its value is \prod_i\binom{J_i}{I_i}=\mathbf 1_{\{I=J\}}. Indeed, if I\ne J then some J_i<I_i, since |I|=|J|=3. These 20 cardinal polynomials therefore give interpolation of degree at most three on the three-dimensional simplex. In coefficient arrays we use their homogeneous degree-three forms, obtained by replacing each factor 3X_i-h by 3X_i-h\sum_jX_j.

Let \operatorname{trunc}_M(t) denote truncation toward zero to a multiple of 1/M. Evaluate the continuous rational summand N_\pi/z_\pi^k at the 20^2 node pairs (I/3,J/3), assigning zero when z_\pi=0, and put

The convention at vanishing denominators is understood in this formula. For the rational vertex lists used in Section 6, all these node values are rational. Their evaluation, truncation, and interpolation can therefore be performed in exact rational arithmetic. Lemma 5.3 does not estimate interpolation error or truncation error: it certifies the remainder of the actual rational polynomial J_\pi chosen by (5.14). Thus the verification remains exact despite the finite interpolation grid and truncation.

The single-posterior inequalities are now proved. For the two remaining inequalities, the proof has been reduced to finding a finite cover of \mathcal S\times\mathcal S by products of simplices on each of which either Lemma 5.2 or Lemma 5.3 applies. We carry out that finite verification next.

6 Finite verification

The certificates in Section 5 reduce the two product inequalities to signs of rational coefficient arrays. We now specify a finite subdivision of \mathcal S\times\mathcal S on which those signs can be checked. The subdivision and all coefficient operations are exact. The complete verifier is printed in Appendix A.

6.1 Subdivision and coverage

A cell is specified by two affinely independent lists of four rational vertices a=(a_0,a_1,a_2,a_3) and b=(b_0,b_1,b_2,b_3) in \mathcal S; its domain is \operatorname{conv}(a)\times\operatorname{conv}(b). Initially both lists are (S_0,S_1,S_2,S_3). On a cell we substitute

into the arrays of Section 5.

Here is the entire decision rule for one row of (5.6). Start at depth zero. At each cell:

1. 1.

   Try the Type T coefficient test of Lemma 5.2. Accept the cell if every coefficient is nonnegative.

2. 2.

   If neither vertex list contains \unif, try the Type P test of Lemma 5.3, with M=2^{32}. If the correction (5.12) is undefined, report failure immediately. Otherwise accept the cell if its coefficient test succeeds.

3. 3.

   If neither test has accepted the cell and its depth is 24, report failure. Otherwise select an edge as follows. For y\in\{0,1\}, put c=a when y=0 and c=b when y=1. Among all i>j, maximize lexicographically the tuple

   (w,y,i,j),\qquad w=\|c_i-c_j\|_2^2 \begin{cases} 16,&c_i=\unif\text{ or }c_j=\unif,\\ 1,&\text{otherwise}. \end{cases}

   Replace vertex j by the midpoint and recursively check that child; then replace vertex i by the midpoint and check the other child. Both children have depth one greater than their parent.

Skipping Type P on cells having a uniform vertex is part of this specified rule; no claim about the success or failure of that test on such cells is needed. Lemma 6.1 shows that successful termination proves the required sign on the entire initial domain.

6.2 The completed verification

The verifier represents every coefficient matrix by integer numerators and a common positive denominator, using arbitrary-precision integers for both. Its polynomial arithmetic consists of convolution, degree elevation, rational addition, and the exact substitutions of Lemma 6.1. The fixed-width quantities used for indices, counters, vertices, and small combinatorial factors remain within their integer ranges. Appendix A proves these bounds and identifies the implementation routines with the mathematical certificates. Thus a successful run verifies exact coefficient signs, without a numerical tolerance.

done 4479 19 lp=2074 lt=166
done 1935 20 lp=871 lt=97

For reproduction, the paper directory contains verification/checks/certificate.cpp and verification/checks/small_polynomials.py, printed in full in Appendix A. The first requires a C++17 compiler with GCC-compatible standard-library headers and the Boost multiprecision headers; the second uses only the Python 3 standard library. For example, from the paper’s verification/ directory run

mkdir -p artifacts
g++ -std=c++17 -O3 -UNDEBUG checks/certificate.cpp \
    -o artifacts/certificate
./artifacts/certificate
./artifacts/certificate b
python3 checks/small_polynomials.py

The C++ program writes progress and its final result to standard error. Its no-argument mode checks row (a); any argument selects row (b). The Python program independently computes the four scalar coefficient minima of Lemma 5.1, using rational convolution, and checks all 24 coordinate actions. Assertions must remain enabled in both programs: do not define NDEBUG or run Python with -O. Together with the scalar checks, Proposition 6.2 completes the proof of Proposition 3.1.

A Exact implementation and complete verifiers

This appendix identifies the array operations with the certificates of Section 5 and bounds the auxiliary fixed-width arithmetic. The complete source listings follow these implementation details. The command lines and expected C++ output are given in Section 6.

A.1 Exact coefficient arithmetic

The C++ type P represents a rational coefficient matrix of bidegree (r,r) by an integer array and a common positive denominator. Its entries are indexed by \mathcal I_r in descending lexicographic order. Integer numerators and denominators use boost::multiprecision::cpp_int. The routine ones(r) constructs W_r; multiplication is ordinary coefficient convolution, and lift raises both degrees by multiplying by W_1. Addition first lifts to a common degree and then uses a common denominator. Thus signs are tested on integer numerators, without a floating-point tolerance.

We explain the correspondence between the remaining routines and the mathematical certificates; this also fixes the normalizations in the listing. Initially the coordinates of every vertex are stored as integers at scale

Removing the factor 2^{24} leaves the denominator 12 for the individual coordinates. The coefficients of U_v are 4(a_i)_v(b_j)_{\pi(v)}; their initialization removes 2^{48} and uses denominator 144. The routine inv forms the nine invariant polynomials in their stated order. The routine dot forms a linear combination divided by 1000 and homogenizes lower-degree terms with its third argument. With that argument equal to the homogeneous one it gives H(p), F(p), or G(p); with that argument equal to z it gives z^6H(U/z).

There is one useful economy in constructing K. A polynomial depending only on X is nevertheless stored with both degrees equal, so it has the form f(X)(\sum_jY_j)^r. Its column indexed by (r,0,0,0) contains exactly the coefficients of f. Taking this column and the analogous row of a polynomial depending only on Y gives the outer product used by tensor. The factor 24 in make then gives exactly the K of (5.5). The array t is the Type T polynomial; it is constructed once and thereafter restricted by midpoint substitution. The arrays N and D store N_\pi and z_\pi, respectively, for the 24 permutations in lexicographic order.

The Type P interpolation uses ordinary matrix multiplication. The matrix ev(r,3) has entries I^J, where I\in\mathcal I_3 indexes a node and J\in\mathcal I_r indexes a monomial. Consequently the two-sided evaluation act must be divided by 3^{2r}. The listing includes this factor explicitly, using 9 when r=1. The routine inverse constructs, rather than numerically inverts, the cardinal polynomials in (5.14). It expands their homogeneous linear factors 3X_h-m\sum_iX_i, stores their coefficients multiplied by 960, and divides by the factorial denominators. Two-sided interpolation therefore requires division by 960^2.

After the node values of N_\pi/z_\pi^k have been truncated toward zero in multiples of M^{-1}, testP constructs the interpolant J_\pi. Its subtraction o=b-o implicitly lifts N_\pi by W_2, and hence constructs precisely O_\pi=W_2N_\pi-z_\pi^kJ_\pi. The array w is Q_\pi=z_\pi^kW_3. For each negative coefficient of O_\pi, the program asserts that the corresponding coefficient of Q_\pi is positive. A violation aborts the verification rather than merely rejecting that cell; no such violation occurs in the completed runs. It then computes the integer ceiling in (5.12), by positive integer division, and retains the largest value. The final test is exactly the coefficient test of Lemma 5.3.

Finally, sub implements (6.1) with 2^r cleared. Its integer multiplier is

Here r-I_i-t\ge0 for every used term, so the indicated division is exact. The resulting matrix denominator is multiplied by 2^r.

A.2 Bounds for fixed-width arithmetic

Only indices, counters, vertex coordinates, and small combinatorial factors use fixed-width integer types. Take int to have at least 32 bits and long long to have at least 64 bits. The following bounds cover every such operation in the listing.

All polynomial matrices in the C++ verifier have bidegree at most 11. Thus there are at most \binom{14}{3}=364 indices in one dimension and 132\,496 entries in a matrix. The depth limit 24 allows at most 2^{25}-1 visited cells, so the counters for visited cells and terminal cells also fit a 32-bit signed integer. The largest factorial initialized is 19!=121\,645\,100\,408\,832\,000<2^{63}, and products of factorials appearing in a multinomial denominator do not exceed this bound. The largest multinomial coefficient through degree 11 is 92\,400, whose square is 8\,537\,760\,000<2^{63}.

Each scaled vertex coordinate belongs to [0,\kappa]. Initial products are bounded by 4\kappa^2, and even the conservative bound

covers the weighted squared edge distances. The initial coordinates are multiples of 2^{24}, so all midpoint coordinates are integers through depth 24. A point of \mathcal S has fourth coordinate at most 1/4, with equality only at \unif. Thus the test that a stored fourth coordinate is \kappa/4 detects a uniform vertex exactly.

The multipliers in (A.2), including the intermediate numerator of the recurrence, are bounded by 11\cdot2^{11}\binom{11}{5}<2^{24}. The evaluation matrices contain integers at most 3^6, and the cardinal-polynomial construction uses only three linear factors starting from 960. Even bounding the sum of absolute coefficients at each multiplication by a factor 8 gives 960\cdot8^3<2^{19}. All products with polynomial coefficients are already operations on unlimited integers. These bounds exclude fixed-width overflow; in particular, the exact sign tests do not rely on floating-point arithmetic or machine rounding.

A.3 Rational sign certificates

[language=C++,basicstyle=, columns=fullflexible,keepspaces=true,breaklines=true, showstringspaces=false,numbers=left,numberstyle=, numbersep=6pt,tabsize=4]../verification/checks/certificate.cpp

A.4 Scalar coefficients and symmetry