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 \[ P_\lambda(j\mid i) =\lambda\mathbf 1_{\{i=j\}}+\frac{1-\lambda}{4}, \qquad i,j\in[4]. \tag{1}\] 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 \[ a_n(d,\lambda)= \mathbb E\left[\frac12\sum_{i=1}^4 \left|\Pr(\sigma_\rho=i\mid T,\sigma_{L_n})-\frac14\right|\right]. \tag{2}\] 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 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 7.

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]. 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 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].

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(p)=4\sum_{i=1}^4p_i^2-1.\] A channel step multiplies \(\mathbb EA\) 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 \(\mathbb EH(p)\geq0\) is preserved by both channel steps and the combination of observations. Two explicit polynomial inequalities then make \(\mathbb EA\) 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 \[m_{n+1}\leq d\lambda^2m_n-cm_n^3, \qquad c=c(d,\lambda)>0.\] 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.

Ordered probabilities and homogeneous coefficients

Let \[\mathcal S=\{p\in\Delta_4:p_1\ge p_2\ge p_3\ge p_4\}, \qquad S_i=\frac{1}{i+1}\sum_{v=1}^{i+1}e_v \quad(0\le i\le3),\] where \(e_v\) is the \(v\)th standard basis vector of \(\mathbb 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 \[ X_i=(i+1)(p_{i+1}-p_{i+2}),\qquad p=\sum_{i=0}^3X_iS_i,\qquad \sum_{i=0}^3X_i=1. \tag{21}\] 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=\boldsymbol u+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 \[\mathcal I_r=\{I\in\mathbb Z_{\ge0}^4:|I|=r\},\qquad X^I=\prod_{i=0}^3X_i^{I_i},\qquad W_r(X)=\left(\sum_{i=0}^3X_i\right)^r.\] 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 \[ [X^I](RS)=\sum_{J+K=I}[X^J]R\,[X^K]S. \tag{22}\] 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)\).

The single-posterior checks

The coordinate forms on \(\mathcal S\) are particularly small: \[ L\sum_{i=0}^3X_iS_i =\left(X_0+X_1+\frac{X_2}{3},\, X_0+\frac{X_2}{3},\, X_0-\frac{X_2}{3}\right). \tag{23}\] 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 \[(e_0,\ldots,e_8)=(0,2,3,4,4,5,6,6,6)\] be their degrees. If \(R=\sum_jc_j\Phi_j\), its degree-\(r\) homogeneous form on \(\mathcal S\) is \[ \widehat R_r(X) =\sum_{j:c_j\ne0}c_j\, \Phi_j\left(L\sum_{i=0}^3X_iS_i\right)W_{r-e_j}(X), \qquad r\ge\max_{c_j\ne0}e_j. \tag{24}\] Together with (23) and (22), this formula specifies every coefficient in the following check.

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\mathfrak S_4\), let \[U^\pi_v=4p_vq_{\pi(v)},\qquad z_\pi=\sum_{v=1}^4U^\pi_v,\qquad P^\pi=U^\pi/z_\pi\quad(z_\pi>0).\] Set \[\begin{align*} K_a&=24\bigl(A(p)+A(q)-H(p)F(q)-F(p)H(q)-D_0(p,q)\bigr),\\ K_b&=-24\bigl(H(p)G(q)+G(p)H(q)\bigr). \tag{25}\end{align*}\] The remaining data are \[ \begin{array}{c|c|c|c} \text{row} & k & N_\pi & m\\ \hline a & 1 & -\displaystyle\sum_{j=1}^3(LU^\pi)_j^2 & 3\\[2mm] b & 5 & z_\pi^6H(U^\pi/z_\pi) & 1/2 \end{array} \tag{26}\] 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 \[ \mathcal R=K+\sum_{\pi\in\mathfrak S_4}\frac{N_\pi}{z_\pi^k}. \tag{27}\] 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 4, 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\Delta_4\) 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 \[p=\sum_{i=0}^3X_ia_i,\qquad q=\sum_{j=0}^3Y_jb_j, \qquad X_i,Y_j\ge0,\quad \sum_iX_i=\sum_jY_j=1.\] 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 \(\Delta_4\). 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.

A Taylor lower bound: Type T

For a positive integer \(k\), define \[t_k(z)=\sum_{i=0}^5\binom{-k}{i}(z-1)^i.\] For every \(z>0\), Taylor’s theorem gives \[ z^{-k}-t_k(z) =\frac{k(k+1)\cdots(k+5)}{6!}\, \xi^{-k-6}(z-1)^6\ge0 \tag{28}\] 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 \(\Delta_4\), because each coordinate of \(LP\) lies in \([-1,1]\). For row \(b\), Lemma 7 gives \(H(P)\ge-1/2\). Consequently, in either row, \[ N_\pi+mz_\pi^{k+1}\ge0. \tag{29}\]

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 \[\frac{N_\pi}{z_\pi^k}\ge J_\pi-c_\pi\] 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 \[ O_\pi=W_2N_\pi-z_\pi^kJ_\pi,\qquad Q_\pi=z_\pi^kW_3, \tag{31}\] 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 \[ c_\pi=\frac1M\max\left( \{0\}\cup \left\{ \left\lceil\frac{-M(O_\pi)_{IJ}}{(Q_\pi)_{IJ}}\right\rceil: (O_\pi)_{IJ}<0 \right\}\right). \tag{32}\] 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 \[\ell_I(X)=\prod_{i=0}^3\binom{3X_i}{I_i},\qquad \binom{t}{j}=\frac{t(t-1)\cdots(t-j+1)}{j!},\qquad \binom{t}{0}=1.\] 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 \[ J_\pi(X,Y)= \sum_{I,J\in\mathcal I_3} \operatorname{trunc}_M\!\left( \frac{N_\pi(I/3,J/3)}{z_\pi(I/3,J/3)^k}\right) \ell_I(X)\ell_J(Y). \tag{34}\] 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 9 does not estimate interpolation error or truncation error: it certifies the remainder of the actual rational polynomial \(J_\pi\) chosen by (34). 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 8 or Lemma 9 applies. We carry out that finite verification next.

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 \[p=\sum_{i=0}^3X_i a_i,\qquad q=\sum_{j=0}^3Y_j b_j, \qquad X,Y\in\Delta_4,\] into the arrays of Section 5.

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

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

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

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=\boldsymbol u\text{ or }c_j=\boldsymbol u,\\ 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 10 shows that successful termination proves the required sign on the entire initial domain.

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 10. The fixed-width quantities used for indices, counters, vertices, and small combinatorial factors remain within their integer ranges. Appendix 7 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 and , printed in full in Appendix 7. 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 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 7, 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 11 completes the proof of Proposition 4.

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 \[ \kappa=12\cdot2^{24}. \tag{36}\] 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 (25). 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 (34). 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 (32), by positive integer division, and retains the largest value. The final test is exactly the coefficient test of Lemma 9.

Finally, sub implements (35) with \(2^r\) cleared. Its integer multiplier is \[ C_t=2^{r-I_i-t}\binom{I_j}{t},\qquad C_{t+1}=\frac{C_t(I_j-t)}{2(t+1)}. \tag{37}\] 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\).

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 \[64\kappa^2 =2\,594\,073\,385\,365\,405\,696<2^{63}\] 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 \(\boldsymbol u\). Thus the test that a stored fourth coordinate is \(\kappa/4\) detects a uniform vertex exactly.

The multipliers in (37), 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.

Rational sign certificates

Scalar coefficients and symmetry