Introduction and Related Work
Main result and scale
A set S\subseteq V(G) is distance-h dominating if every vertex of G lies within graph distance h of S; its minimum size is denoted \gamma_h(G). For graphs of maximum degree d, one selected vertex can cover at most
B_h=1+d\frac{(d-1)^h-1}{d-2}
vertices, so the elementary volume bound is
\gamma_h(G)\ge \frac{n}{B_h}.
At the other extreme, if every radius-h ball has at least M vertices, independent selection with probability (\log M)/M followed by adding every uncovered vertex gives
\gamma_h(G)\le \frac{n(\log M+1)}{M}.
In the ideal tree-ball geometry M=B_h, this places the natural covering scale at n\log B_h/B_h. The present paper proves that a random d-regular graph cannot beat essentially this scale from below: with high probability,
\gamma_h(G_{n,d})\ge \frac{n}{B_h}\left(\log B_h-2\log\log B_h-\omega(1)\right),
subject to an explicit growth condition. Thus the first-moment lower transition is determined through its first two asymptotic terms, up to the bounded critical window. A matching quenched upper theorem at this precision is not proved here.
The distinction matters at the comparison scale B_h\asymp\sqrt n. There the volume bound alone is of order \sqrt n, whereas the theorem gives an \Omega(\sqrt n\log n) obstruction. This scale is also relevant to pursuit-evasion: Meyniel’s conjecture predicts that O(\sqrt n) cops suffice in every connected n-vertex graph [1,2], and it is known for several random-graph models, including random regular graphs [3,4]. Our conclusion is not a cop-number lower bound. It says that one particular static exhaustive coverage mechanism can require a logarithmic factor more than the Meyniel scale.
Why the first moment is difficult
For an independent random subset of density \alpha, a fixed tree-like radius-h ball is missed with probability approximately (1-\alpha)^{B_h}. Balancing subset entropy against this coupon term predicts the coordinate
\alpha B_h\approx \log B_h-2\log\log B_h.
Turning that heuristic into a theorem is not a product-measure calculation. In the configuration model, coverage events for different vertices overlap heavily, and optimizing over the selected set allows highly organized profiles. A direct bounded-differences argument is also ineffective in the growing-radius regime: changing one pairing can alter the radius-h coverage status of order B_h vertices, so the natural Lipschitz constant grows on exactly the scale that must be resolved.
The key device is to label every vertex by its exact distance to the candidate set. Local consistency of these labels — adjacent labels differ by at most one, and every positive label has a neighbor one level lower — forces them to be genuine graph distances on any graph. This removes the need to approximate neighborhoods by trees and converts the first moment into an exact finite-dimensional method-of-types problem. The price is a nonconcave variational functional whose global optimizer must be identified uniformly as the number of distance levels grows.
Related work
The configuration or pairing model and its transfer to uniformly random simple regular graphs are standard; see Wormald’s survey [5] and Janson’s simplicity theorem [6]. Fixed-radius domination in random regular graphs has been studied algorithmically: Duckworth analyzed randomized greedy algorithms for distance-k dominating sets [7], while Duckworth and Wormald treated independent domination [8]. The broader covering viewpoint is classical in coding theory [9].
The closest message-passing antecedents are statistical-mechanical. Zhao, Habibulla, and Zhou developed a cavity-method and belief-propagation treatment of minimum dominating sets [10]; Habibulla and Qin studied a distance-two version with distance-labeled messages [11]. Those works are replica-symmetric and fixed-radius. The transfer equations below are closely related in spirit; the distinctions here are the exact graph-level type count, the proof of global optimization, and the growing-radius asymptotics.
Cutler and Radcliffe used Shearer entropy to obtain universal extremal bounds for domination polynomials of regular graphs [12]. Such universal bounds cannot by themselves detect the random-covering penalty: structured regular graphs may admit efficient covering codes. In the binomial random graph, Glebov, Liebenau, and Szabó proved two-point concentration at the first-moment threshold in a sufficiently dense regime [13]. That result motivates, but does not supply, the corresponding quenched statement for random regular graphs.
The pursuit application comes from branch-based local coverage. Aigner and Fromme introduced the multiple-cop game in its modern graph-theoretic form [14]; Prałat and Wormald later combined random placement with deterministic pursuit in random graphs [3,4]. The local tube certificate in the branch-tube persistence theorem of [15] motivates a root-independent two-witness covering problem. Section 2.1 states the exact graph-general parameter used here and carefully limits the resulting obstruction.
Proof architecture and contributions
The proof has three acts.
Act I: exact types and a compact functional. Exact distance labels produce a two-sided type estimate
\log \mathbb E N_n=n\Phi_{d,h}(n_\tau/n)+O_d(h\log n).
Optimizing the local profile entropy at fixed tridiagonal edge masses reduces \Phi_{d,h} exactly to a compact functional \mathcal F_{d,h} in 2h+1 variables. The lower side of the type estimate also yields the pointwise entropy anchor
\Psi_{d,h}(\alpha)\le H(\alpha).
Act II: globality without concavity. The compact functional is genuinely nonconcave. Nevertheless, entropy singularities repel every maximizing profile from the boundary. Interior KKT points are equivalent to positive message solutions. An exact reverse transfer reconstructs every positive stationary solution from one terminal parameter, and the associated activity is strictly increasing from 0 to \infty. Hence the grand-canonical optimizer is unique at every activity, and duality gives
\Psi_{d,h}(\alpha)=\Psi_{d,h}^{\mathrm{stat}}(\alpha),\qquad \Psi_{d,h}'(\alpha)=-\log z(\alpha).
Act III: orbit asymptotics and integration. The reverse orbit has exact stable and free outer solutions. In the near-critical slack window they overlap over linearly many levels, allowing uniform shadowing and the activity law
-\log z(\alpha)=\log\frac1\alpha+B_h(1-\alpha)^{B_h}(1+o(1)).
Integrating this identity from a slightly larger density and anchoring with \Psi\le H gives
\Psi_{d,h}(C/B_h)\le -\left(\frac12-o(1)\right)e^{-C}
uniformly up to C=\log B_h-2\log\log B_h-W_h. The coefficient 1/2 is a convenient consequence of the chosen integration interval, not the predicted sharp coefficient; the numerical diagnostics in Section 16 are consistent with a ratio tending to 1 when W_h\to\infty.
The four main contributions are therefore: an exact growing-radius type count with no local-tree assumption; an exact compact reduction; a global solution of a nonconcave annealed variational problem; and a near-critical random-regular lower bound. The bounded critical window, annealed-to-quenched matching, and direct two-branch asymptotics remain separate problems.
Models, Notation, and Main Results
Fix d\ge 3 throughout and put
b=d-1,\qquad D=\frac{b+1}{b-1}=\frac{d}{d-2},
B_h=1+d\frac{b^h-1}{b-1}=Db^h-\frac{2}{b-1}.
For a probability vector r=(r_1,\ldots,r_k), write
H(r)=-\sum_{j=1}^k r_j\log r_j,
with 0\log 0=0; for a scalar a\in[0,1], H(a) denotes the binary entropy H(a,1-a).
| Notation | Meaning |
|---|---|
| B_h | maximum radius-h ball volume at degree d |
| \gamma_h(G) | minimum size of a distance-h dominating set |
| \Phi_{d,h} | full local-profile type functional |
| \mathcal F_{d,h} | compact tridiagonal profile functional |
| \Psi_{d,h}(\alpha) | microcanonical annealed exponent at density \alpha |
| z=e^\theta | grand-canonical activity |
| b=d-1,\ D=d/(d-2) | recurring degree constants |
Definition 1 (Internally two-path (h,2) domination). A set S\subseteq V(G) is internally two-path (h,2) dominating if every vertex v\notin S has two v–S paths of length at most h whose only common vertex is v. In particular, the paths begin through distinct neighbors of v. Let \gamma_{h,2}^{\mathrm{int}}(G) denote the minimum size of such a set.
Every internally two-path (h,2)-dominating set is distance-h dominating, since either witness path alone ends in S within distance h. Therefore
\gamma_{h,2}^{\mathrm{int}}(G)\ge \gamma_h(G).
Connection with static tube coverage
In the tree-ball setting of [15], a length-t tube with residual depth h=R-t depends, after the root is allowed to vary, only on its terminal directed edge. The resulting forward cone excludes one branch at its head. A root-independent set meets every such directed cone exactly when, at every unselected vertex, at least two distinct branches contain a selected vertex within distance h; in a tree-ball these are precisely the two internally disjoint paths of Definition 1. Thus internally two-path domination is a graph-general strengthening of the global exhaustive tube certificate.
Combining the displayed inequality above with the main theorem shows that any such exhaustive static certificate has size \Omega(\sqrt n\log n) at the comparison scale B_h\asymp\sqrt n. Meyniel’s conjecture concerns the existence of a fully adaptive winning strategy with O(\sqrt n) cops, so there is no contradiction: the lower bound applies only to this static exhaustive mechanism. Partial coverage, adaptive reassignment, and epoch-based pursuit remain outside the argument.
The pairing model consists of n labeled buckets of d half-edges paired uniformly at random; conditioning the resulting multigraph on simplicity gives the uniformly random simple d-regular graph G_{n,d}, for dn even. Let Z_{n,d,h}(m) count distance-h dominating m-sets in the pairing model.
For a distance-h dominating set S, assign each vertex its exact label \operatorname{dist}(v,S)\in\{0,\ldots,h\}. The local consistency used below is equivalent to genuine distance: adjacent labels differ by at most one, and every positive label has a neighbor one level lower. The descending condition gives a path to label zero of the displayed length, while the Lipschitz condition gives the reverse inequality. No tree-neighborhood assumption is involved.
The type count developed below gives
\log \mathbb E Z_{n,d,h}(m)\le n\Psi_{d,h}(m/n)+O_d(h\log(n+1)),
uniformly in h. Here \Psi_{d,h} is the exact annealed variational exponent.
Theorem 2 (Near-critical annealed negativity). Fix \eta\in(0,1), put L_h=\log B_h, and let W_h\to\infty. Uniformly for real C satisfying
\eta L_h\le C\le L_h-2\log L_h-W_h,
one has
\Psi_{d,h}(C/B_h)\le -\left(\frac12-o(1)\right)e^{-C}\qquad(h\to\infty),
where the o(1) may depend on d, \eta, and the prescribed sequence W_h, but is uniform over the displayed interval.
Remark 3 (The coefficient 1/2). The coefficient 1/2 is not predicted to be sharp. It comes from the symmetric choice of the upper integration point in Section 15. The activity law and the diagnostics in Section 16 are consistent with the normalized ratio approaching 1-O(e^{-W_h}) deeper in the near-critical window.
Corollary 4 (Fixed-fraction slack). For every fixed 0<c_-\le c_+<1, uniformly for c\in[c_-,c_+],
\Psi_{d,h}\!\left(c\,\frac{\log B_h}{B_h}\right)\le -\left(\frac12-o(1)\right)B_h^{-c}.
Theorem 5 (Random-regular near-critical lower bound). Let h=h(n)\to\infty and W_h\to\infty. Define
C_h^*=L_h-2\log L_h-W_h,
and suppose
\liminf_{n\to\infty}\frac{C_h^*}{L_h}>0,\qquad \frac{ne^{W_h}L_h^2}{B_h}\gg h\log n.
Then, with high probability,
\gamma_h(G_{n,d})\ge \frac{n}{B_h}\left(L_h-2\log L_h-W_h\right).
The same conclusion holds for every parameter whose feasible sets are necessarily distance-h dominating, including internally two-path (h,2) domination.
Corollary 6 (Fixed-fraction random lower bound). For every fixed \varepsilon\in(0,1), if
\frac{n}{B_h^{1-\varepsilon}}\gg h\log n,
then, with high probability,
\gamma_h(G_{n,d})\ge (1-\varepsilon)\frac{n\log B_h}{B_h}.
When B_h\asymp\sqrt n, one has \log B_h=\tfrac12\log n+O(1), and Theorem 5 gives
\gamma_h(G_{n,d})\ge \frac{n}{B_h}\left(\tfrac12\log n-2\log\log n-W_h+O(1)\right)=\Omega(\sqrt n\log n).
The implicit constant in the final order statement depends on the comparison constants in B_h\asymp\sqrt n; no exact prefactor \sqrt n is asserted.
Two-Sided Exact Type Counting and the Entropy Anchor
For completeness, we record the exact local-profile count that underlies both the variational formula and the pointwise entropy bound used later.
Let \mathcal T_{d,h} be the finite set of local profiles
\tau=(i,c),\qquad i\in\{0,\ldots,h\},\qquad c=(c_0,\ldots,c_h),\qquad \sum_j c_j=d,
with
c_j=0 \text{ if } |i-j|>1,\qquad c_{i-1}\ge 1 \text{ if } i>0.
For a probability vector \xi=(\xi_\tau)_{\tau\in\mathcal T_{d,h}}, put
q_{ij}(\xi)=\frac1d\sum_{\tau=(i,c)}\xi_\tau c_j,
and call \xi feasible when q_{ij}=q_{ji}. Its selected density is
\alpha(\xi)=\sum_{\tau:\,i(\tau)=0}\xi_\tau.
Define
\Phi_{d,h}(\xi)=-\sum_\tau \xi_\tau\log\xi_\tau+\sum_\tau \xi_\tau\log\binom{d}{c(\tau)}+\frac d2\sum_{i,j}q_{ij}(\xi)\log q_{ij}(\xi),
with 0\log 0=0. The exact variational exponent is
\Psi_{d,h}(\alpha)=\max\{\Phi_{d,h}(\xi):\xi \text{ feasible},\ \alpha(\xi)=\alpha\}.
Section 4.1 proves the exact reduction from this full profile functional to the compact tridiagonal functional of Proposition 11.
Theorem 7 (Two-sided count for one integer type). There is a constant K_d such that the following holds for every h,n and every admissible integer profile (n_\tau)_{\tau\in\mathcal T_{d,h}}. Put
\xi_\tau=\frac{n_\tau}{n},\qquad H_{ij}=\sum_{\tau=(i,c)} n_\tau c_j=dnq_{ij}(\xi).
Assume \sum_\tau n_\tau=n, H_{ij}=H_{ji}, and every H_{ii} is even; these conditions define admissibility here. Let N_n denote the number of vertex sets whose exact-distance local-profile counts equal n_\tau in the d-regular pairing model. Then
\mathbb E N_n=\frac{n!}{\prod_\tau n_\tau!}\prod_\tau \binom{d}{c(\tau)}^{n_\tau}\cdot \frac{\prod_{0\le i<j\le h} H_{ij}!\ \prod_{i=0}^h (H_{ii}-1)!!}{(dn-1)!!},
and
\bigl|\log \mathbb E N_n-n\Phi_{d,h}(\xi)\bigr|\le K_d(h+1)\log(n+1).
Here (-1)!!=1 when a diagonal mass is zero.
Proof. First assign the n labeled vertices to their local-profile classes, giving n!/\prod_\tau n_\tau! choices. At a vertex of profile (i,c), assign the d labeled half-edges their neighbor labels in \binom{d}{c} ways. There are then H_{ij} half-edges of ordered type (i,j). For i<j, pairing the (i,j) half-edges bijectively with the (j,i) half-edges gives H_{ij}! choices; the H_{ii} diagonal half-edges admit (H_{ii}-1)!! pairings. Division by the total number (dn-1)!! of pairings proves the displayed count.
Every resulting pairing has the prescribed exact distance labels. Indeed, the allowed edge types make the label function 1-Lipschitz, while every positive label has a neighbor one level lower. Following a descending edge reaches label zero in exactly the displayed number of steps, and following any path from label zero cannot increase the label by more than one per edge. Thus the label equals graph distance to its zero set.
Use, uniformly for integers r\ge 0,
\log(r!)=r\log r-r+O(\log(r+1))
and, for even r,
\log((r-1)!!)=\frac r2\log r-\frac r2+O(\log(r+1)).
There are O_d(h+1) profile classes and nonzero tridiagonal edge types. Substitution into the displayed exact count cancels every \log n, \log d, and linear term, leaving exactly n\Phi_{d,h}(\xi) with error O_d(h\log(n+1)). This proves the displayed bound. □
Corollary 8 (Pointwise subset-entropy bound). For every d,h and every \alpha\in[0,1],
\Psi_{d,h}(\alpha)\le H(\alpha).
Proof. First let \xi be a rational feasible profile. Passing to arbitrarily large multiples of a common denominator, and multiplying once more if necessary to make every diagonal half-edge count even, realizes \xi as an integer type. Since N_n counts only subsets of size \alpha n,
\mathbb E N_n\le \binom{n}{\alpha n}.
The lower inequality in Theorem 7, followed by n\to\infty, gives
\Phi_{d,h}(\xi)\le H(\alpha).
The feasible set is a rational polytope, so rational feasible profiles are dense. The functional \Phi_{d,h} is continuous on it under the convention 0\log 0=0. Hence the same inequality holds for every feasible profile. Taking the maximum at fixed selected density proves the corollary. □
Remark 9 (Uniform upper type estimate). Summing Theorem 7 over the at most (n+1)^{O_d(h)} integer profiles gives
\log \mathbb E Z_{n,d,h}(m)\le n\Psi_{d,h}(m/n)+O_d(h\log(n+1)),
uniformly as h varies. Theorem 7 also gives a matching lower estimate along every sequence realizing a prescribed rational profile. No local-tree assumption is involved.
The Exact Compact Variational Problem
Let q_{ij} be the directed-edge distribution of exact distance labels i,j\in\{0,\ldots,h\}. Exact distance consistency makes q symmetric and tridiagonal. Write
x_i=q_{i-1,i}\ (1\le i\le h),\qquad \ell_i=q_{ii}\ (0\le i\le h),
with x_0=x_{h+1}=0. The label masses are
p_i=\ell_i+x_i+x_{i+1},\qquad \sum_{i=0}^h p_i=1.
For i\ge 1, put
y_i=p_i-x_i=\ell_i+x_{i+1},\qquad a_i=\frac{x_i}{p_i}.
Every positive-label vertex has at least one lower-label neighbor, so
a_i\ge \frac1d,\qquad \text{equivalently}\qquad dx_i\ge p_i.
Let s_d(a) be the maximum entropy of a distribution on nonempty subsets of [d] for which each coordinate is present with marginal a. Its dual formula is
s_d(a)=\inf_{\lambda>0}\left\{\log\bigl((1+\lambda)^d-1\bigr)-da\log\lambda\right\},\qquad \frac1d\le a\le 1.
The minimizing parameter is characterized by
a=\frac{\lambda(1+\lambda)^{d-1}}{(1+\lambda)^d-1}.
Exact local entropy reduction
The passage from the full profile functional to \mathcal F_{d,h} is exact.
Lemma 10 (Conditional-product reduction). Fix a symmetric tridiagonal directed-edge distribution q, and write x_i,\ell_i,p_i,y_i,a_i as above, with x_{h+1}=0. Among all feasible local-profile laws inducing q, the maximum of the vertex entropy and arrangement terms is
p_0d\,H\!\left(\frac{\ell_0}{p_0},\frac{x_1}{p_0}\right)+\sum_{i=1}^h\left[p_is_d(a_i)+d(1-a_i)H\!\left(\frac{\ell_i}{y_i},\frac{x_{i+1}}{y_i}\right)\right].
The maximizing law is unique whenever all displayed masses are positive. Conditional on label i\ge 1, the set of lower-label half-edges has the entropy-maximizing tilted nonempty-subset law with coordinate marginal a_i; conditional on that set, every remaining half-edge independently receives label i or i+1 with probabilities \ell_i/y_i and x_{i+1}/y_i.
Proof. Condition on the central label i. Choosing a local count vector and then assigning the d labeled half-edges contributes exactly the entropy of the induced law on words of length d over the allowed neighboring labels.
For i=0, only labels 0 and 1 are allowed and their coordinate marginals are \ell_0/p_0 and x_1/p_0. Subadditivity of entropy is sharp only for independent coordinates, giving the first term above.
Fix i\ge 1. Mark the coordinates whose neighbor label is i-1. Their random subset is nonempty and has common coordinate marginal
a_i=\frac{q_{i,i-1}}{p_i}=\frac{x_i}{p_i}.
By definition, its entropy is at most s_d(a_i), with equality for the exponential tilt \Pr(A)\propto \lambda^{|A|}, \emptyset\ne A\subseteq[d], where \lambda satisfies the marginal characterization above; this also proves the dual formula for s_d. Given the lower-neighbor set, the remaining d-|A| coordinates must split between labels i and i+1. Conditional entropy is maximized by independent splitting with probabilities \ell_i/y_i and x_{i+1}/y_i. Its expectation is
d(1-a_i)H\!\left(\frac{\ell_i}{y_i},\frac{x_{i+1}}{y_i}\right).
The chain rule for entropy proves the displayed reduction; strict entropy concavity gives uniqueness in the positive interior. □
Proposition 11 (Exact compact functional). For every feasible tridiagonal q, maximizing the full profile functional over local-profile laws inducing q gives exactly the compact functional
\mathcal F_{d,h}(x,\ell)=(d-1)p_0\log p_0+\sum_{i=1}^h\left[-p_i\log p_i+p_is_d(a_i)+dy_i\log y_i\right]-\frac d2\sum_{i=0}^h\ell_i\log\ell_i.
Consequently the compact and full variational values agree at every selected density.
Proof. Insert Lemma 10 into the full profile functional \Phi_{d,h}. The edge term is
\frac d2\left(\sum_{i=0}^h \ell_i\log\ell_i+2\sum_{i=1}^h x_i\log x_i\right).
Expanding the two categorical entropies in Lemma 10, the x_i\log x_i terms cancel against the off-diagonal edge terms. The remaining p_i, y_i, and \ell_i terms collect to \mathcal F_{d,h}, including the root contribution (d-1)p_0\log p_0. Since every full feasible profile induces a feasible q and Lemma 10 constructs a maximizing profile for every feasible q, the variational values coincide. □
For activity z=e^\theta>0, the grand-canonical functional is
\mathcal F_{d,h}^{(z)}(x,\ell)=\mathcal F_{d,h}(x,\ell)+p_0\log z.
Define the feasible polytope
\mathcal P_{d,h}=\left\{(x,\ell):x_i,\ell_i\ge0,\ \sum_i p_i=1,\ dx_i\ge p_i\ (1\le i\le h)\right\}.
The exact variational values are
\Psi_{d,h}(\alpha)=\max_{\substack{(x,\ell)\in\mathcal P_{d,h}\\ p_0=\alpha}}\mathcal F_{d,h}(x,\ell),\qquad \phi_{d,h}(z)=\max_{(x,\ell)\in\mathcal P_{d,h}}\mathcal F_{d,h}^{(z)}(x,\ell)=\max_\alpha\{\Psi_{d,h}(\alpha)+\alpha\log z\}.
The polytope is compact, so all maxima exist.
The feasible density interval
The local capacities imply the Moore lower bound. First,
p_1\le dx_1\le dp_0.
For i\ge 2, symmetry and the preceding descent edge give
x_i\le p_{i-1}-x_{i-1}\le \frac{d-1}{d}p_{i-1},
so
p_i\le dx_i\le (d-1)p_{i-1}.
Therefore
1=\sum_{i=0}^h p_i\le B_hp_0,\qquad p_0\ge\frac1{B_h}.
Equality is feasible in the type polytope: take
p_0=\frac1{B_h},\qquad p_i=\frac{d(d-1)^{i-1}}{B_h},\qquad x_i=\frac{(d-1)^{i-1}}{B_h},
with \ell_i=0 for i<h and \ell_h=(d-1)^h/B_h. The upper endpoint p_0=1 is also feasible. Hence the density projection of \mathcal P_{d,h} is exactly [1/B_h,1].
Boundary Repulsion and Full Interiority
The proof that all grand-canonical maximizers are interior rests on the endpoint behavior of s_d.
Lemma 12 (Endpoint expansions). As \delta\downarrow 0,
s_d\!\left(\frac1d+\delta\right)=\log d+d\delta\log\frac1\delta+O_d(\delta),
s_d(1-\delta)=d\delta\log\frac1\delta+O_d(\delta).
Proof. The envelope theorem applied to the dual formula for s_d gives
s_d'(a)=-d\log\lambda(a).
Expanding the marginal characterization at \lambda=0 gives
\lambda(a)=\frac{2d}{d-1}\left(a-\frac1d\right)+O_d\!\left(\left(a-\frac1d\right)^2\right).
At the other endpoint, \lambda(a)=(1-a)^{-1}(1+O_d(1-a)). Integrating s_d' from the known endpoint values s_d(1/d)=\log d and s_d(1)=0 gives the result. □
If p_i=0 at one level, then x_{i+1}=0, and the capacity inequality forces p_{i+1}=0. Thus every feasible profile has an effective horizon k=\max\{i:p_i>0\}, and its positive support is the prefix \{0,\ldots,k\}.
Lemma 13 (Relative boundary repulsion). Fix a finite activity z>0. A maximizer of \mathcal F_{d,h}^{(z)} cannot lie on any proper local face within its effective horizon. More precisely, if its effective horizon is k, then
\ell_i>0\ (0\le i\le k),\qquad a_i>\frac1d\ (1\le i\le k).
In particular, a_k<1.
Proof. For each k\ge 1, a strictly interior feasible profile exists. Choose 1/d<\chi<1/2, 0<r<\chi^{-1}-1, put p_i proportional to r^i, and set x_i=\chi p_i. Then
\ell_0=p_0-x_1>0,\qquad \ell_i=p_i-x_i-x_{i+1}>0\ (1\le i<k),\qquad \ell_k=p_k-x_k>0.
Mix a proposed boundary maximizer with such an interior profile. If a_i=1/d, Lemma 12 contributes a strictly positive multiple of t\log(1/t). If \ell_i=0, the term -\tfrac d2\ell_i\log\ell_i contributes a strictly positive multiple of t\log(1/t). All terms that remain away from their endpoints change by only O(t).
The only apparent negative singularity occurs if a_k=1, equivalently y_k=\ell_k=0. In that case, with y_k(t)=\beta t+O(t^2) for some \beta>0,
p_k(t)s_d\!\left(1-\frac{y_k(t)}{p_k(t)}\right)+dy_k(t)\log y_k(t)=O(t)
by Lemma 12; the two logarithmic singularities cancel. The remaining diagonal-edge term contributes
-\frac d2y_k(t)\log y_k(t)=\frac d2\beta t\log\frac1t+O(t),
which is strictly positive. If several faces are active simultaneously, all leading t\log(1/t) coefficients are nonnegative and at least one is positive. Hence every proper relative boundary point admits an improving inward direction. □
The horizon itself is also repelling.
Lemma 14 (Horizon extension). A maximizer of \mathcal F_{d,h}^{(z)} cannot have effective horizon k<h.
Proof. By Lemma 13, a maximizer is strictly interior on its effective prefix. Choose a^*\in(\max\{1/d,1-2/d\},1). For small \tau>0, introduce a new level of mass p_{k+1}=\tau with
x_{k+1}=a^*\tau,\qquad y_{k+1}=\ell_{k+1}=(1-a^*)\tau.
Keep p_k fixed by reducing \ell_k by a^*\tau, and preserve total mass by reducing \ell_0 by \tau. All old variables remain feasible for sufficiently small \tau. When k=0, take instead
p_0=1-\tau,\qquad x_1=a^*\tau,\qquad \ell_0=1-(1+a^*)\tau.
The new level contributes
\left(1-\frac d2(1-a^*)\right)\tau\log\frac1\tau+O(\tau).
The coefficient is positive by the choice of a^*. All changes to previously positive coordinates are O(\tau). Thus the extension strictly increases the grand functional. □
Theorem 15 (Full interiority). For every d\ge3, h\ge1, and z>0, every maximizer of the exact grand-canonical functional \mathcal F_{d,h}^{(z)} has full effective horizon h and satisfies
x_i>0,\qquad \ell_i>0,\qquad a_i>\frac1d
for all applicable indices.
Stationary Messages and Exact KKT Reconstruction
Recall b=d-1. For 1\le i\le h, let A_i be the cavity weight when the recipient edge already supplies a lower-label neighbor, and let B_i be the weight when it does not. For label zero use B_0, and set A_{h+1}=0. Define
S_0=B_0+A_1,\qquad S_i=B_{i-1}+B_i+A_{i+1}\ (1\le i\le h),
where the terminal convention makes S_h=B_{h-1}+B_h. The positive stationary system is
\kappa B_0=zS_0^b,\qquad \kappa A_i=S_i^b\ (1\le i\le h),\qquad \kappa B_i=S_i^b-(S_i-B_{i-1})^b\ (1\le i\le h).
The following subsection derives this system directly from the compact exact functional and proves the converse reconstruction.
Full KKT-to-message correspondence
Let \lambda_i be the minimizer of s_d(a_i)’s dual formula. Then
s_d'(a_i)=-d\log\lambda_i,\qquad s_d(a_i)-a_is_d'(a_i)=\log((1+\lambda_i)^d-1).
At an interior grand-canonical KKT point, let \mu be the multiplier for \sum_{i=0}^h \ell_i+2\sum_{i=1}^h x_i=1. Since \ell_i enters one layer mass and x_i enters two, the KKT equations are
\frac{\partial \mathcal F^{(z)}}{\partial \ell_i}=\mu,\qquad \frac{\partial \mathcal F^{(z)}}{\partial x_i}=2\mu.
The analytic derivatives used below are, at the root,
g_0=(d-1)(\log p_0+1)+\log z-\frac d2(\log\ell_0+1),
and, for i\ge1,
g_i=-\log p_i-1+s_d(a_i)-a_is_d'(a_i)+d(\log y_i+1)-\frac d2(\log\ell_i+1).
Thus \partial\mathcal F^{(z)}/\partial\ell_i=g_i. The derivative with respect to x_i is the sum of the layer contribution immediately to its left and the x_i-derivative of the layer-i contribution; explicitly, for i\ge2,
\frac{\partial\mathcal F^{(z)}}{\partial x_i}=g_{i-1}+\frac d2(\log\ell_{i-1}+1)+g_i+s_d'(a_i)-d(\log y_i+1)+\frac d2(\log\ell_i+1),
with the same formula at i=1 after replacing the left layer expression by its root analogue.
Define, up to a common positive scale,
B_i=\sqrt{\ell_i},\qquad A_i=\frac{x_i}{B_{i-1}}\ (1\le i\le h),\qquad A_{h+1}=0.
Then y_i=B_i(B_i+A_{i+1}).
Lemma 16 (Edge KKT identifies the local tilt). For every 1\le i\le h,
\lambda_i=\frac{B_{i-1}}{B_i+A_{i+1}}.
Proof. For i\ge2, the derivative of \mathcal F with respect to x_i is the sum of the p_{i-1} and p_i contributions. Subtract the two diagonal equations above, use the dual-formula identities for s_d', and cancel the common constants. The result is
\frac d2\log\ell_{i-1}-d\log\lambda_i\frac{y_i}{\sqrt{\ell_i}}=0.
Thus \lambda_iy_i=\sqrt{\ell_{i-1}\ell_i}, which is the displayed identity. The root contribution at i=1 has the same algebra, with the activity term cancelling through the root diagonal equation. □
Proposition 17 (Compact KKT equals two-message stationarity). Every strict interior KKT point determines positive messages satisfying the stationary system above. Conversely, every positive message solution reconstructs a strict interior KKT point by
q_{ii}=\frac{B_i^2}{Z_e},\qquad q_{i-1,i}=\frac{B_{i-1}A_i}{Z_e}.
Proof. Put T_i=B_i+A_{i+1}, S_i=B_{i-1}+T_i. By Lemma 16, \lambda_i=B_{i-1}/T_i. Exponentiating the diagonal KKT equation and using the entropy dual-formula identities shows that one common constant \kappa>0 satisfies
\kappa=\frac{((1+\lambda_i)^d-1)y_i^d}{p_iB_i^d}=\frac{S_i^d-T_i^d}{p_i}
for every i\ge1. Hence p_i=(S_i^d-T_i^d)/\kappa. The descent marginal formula gives x_i=a_ip_i=B_{i-1}S_i^b/\kappa. Since x_i=B_{i-1}A_i, this is the stationary equation for A_i. Subtracting x_i from p_i gives y_i=T_i(S_i^b-T_i^b)/\kappa. Since y_i=B_iT_i, this is the stationary equation for B_i. At the root, the diagonal KKT equation gives \kappa=zp_0^b/B_0^d. Because p_0=B_0(B_0+A_1)=B_0S_0, this is the stationary equation for B_0.
Conversely, let positive messages satisfy the stationarity equations. Put \sigma=Z_e^{-1/2} and introduce normalized messages \widehat A_i=\sigma A_i, \widehat B_i=\sigma B_i, \widehat\kappa=\sigma^{b-1}\kappa. Then
\widehat\kappa\widehat A_i=\widehat S_i^b,\qquad \widehat\kappa\widehat B_i=\widehat S_i^b-(\widehat S_i-\widehat B_{i-1})^b,\qquad \widehat\kappa\widehat B_0=z\widehat S_0^b.
The reconstructed beliefs are simply \ell_i=\widehat B_i^2, x_i=\widehat B_{i-1}\widehat A_i. They have total mass one by the definition of Z_e. Writing \widehat T_i=\widehat B_i+\widehat A_{i+1}, \lambda_i=\widehat B_{i-1}/\widehat T_i, the message equations give the exact row identities
p_i=\frac{\widehat S_i^d-\widehat T_i^d}{\widehat\kappa},\qquad x_i=\frac{\widehat B_{i-1}\widehat S_i^b}{\widehat\kappa},\qquad y_i=\frac{\widehat T_i(\widehat S_i^b-\widehat T_i^b)}{\widehat\kappa}.
Consequently a_i=x_i/p_i is exactly the tilted conditioned-binomial marginal with parameter \lambda_i, and \lambda_iy_i=\widehat B_{i-1}\widehat B_i=\sqrt{\ell_{i-1}\ell_i}. Substitution into the diagonal derivative gives, for every i\ge1, g_i=\log\widehat\kappa+(d-2)/2. The root equation gives the same value for g_0. Finally, the displayed edge identity and s_d'(a_i)=-d\log\lambda_i make the difference between the x_i derivative and g_{i-1}+g_i vanish exactly. Thus, with \mu=\log\widehat\kappa+(d-2)/2, one has \partial\mathcal F^{(z)}/\partial\ell_i=\mu and \partial\mathcal F^{(z)}/\partial x_i=2\mu. Positivity makes the point strict interior, and common message scaling cancels from the beliefs. □
One-dimensional positive stationary locus
The equations are homogeneous: common message scaling changes \kappa but not z or the reconstructed profile. In the gauge \kappa=1, choosing B_h>0 determines all preceding messages uniquely by
A_i=B_i+(B_i+A_{i+1})^b,\qquad B_{i-1}=A_i^{1/b}-B_i-A_{i+1},
for i=h,h-1,\ldots,1. Positivity is automatic because B_{i-1}=(B_i+A_{i+1})^b+B_i^{1/b}-(B_i+A_{i+1})>0. Thus the positive stationary locus is one dimensional before the activity is imposed.
Exact Reverse Transfer and Monotone Activity Shooting
Normalize A_1=1 and put
\rho_i=\frac{B_i}{A_i},\qquad u_i=\frac{A_{i+1}}{A_i},\qquad v_i=\rho_i+u_i.
At the terminal level, u_h=0, so \rho_h=v_h=:s\in(0,1). Let \mathcal D=\{(\rho,v):0<\rho\le v\le 1\}.
Proposition 18 (Exact reverse map). Given a next-level state (\rho',v')\in\mathcal D, define
w=(1-\rho')^{1/b},\qquad e=1-w,\qquad R=v'\frac{e}{w},\qquad M=\left(e+\frac{w}{v'}\right)^b.
Then its unique positive predecessor is
\rho=\frac{R}{R+M},\qquad v=\frac{1+R}{R+M}.
The remaining coordinates are
u=\frac{1}{R+M},\qquad q=\frac{M-1}{R+M}.
The map sends \mathcal D into itself.
Proof. The forward transfer identities imply \rho/u=v'e/w=R. The next lower-neighbor fraction also gives
e=\frac{\rho(1-\rho)^{1/b}}{u^{1/b}(u+\rho)}.
Substituting \rho=Ru and solving yields u=1/(R+M), which gives the displayed formulas for \rho,v. Uniqueness follows from the algebraic solution. Since e+w/v'\ge e+w=1, we have M\ge1, and therefore 0<\rho<v\le1. □
Proposition 19 (Order preservation). The reverse map is coordinatewise nondecreasing on \mathcal D, and its \rho coordinate is strictly increasing whenever either input coordinate increases. Along the diagonal terminal family (s,s), every earlier \rho_i is strictly increasing in s, and every v_i is nondecreasing.
Proof. The quantity R=v'e/w is strictly increasing in both \rho' and v'. Put N=e+w/v', M=N^b. As v' increases, N strictly decreases. Since w'(\rho')<0 and e'=-w', one has
\frac{\partial N}{\partial \rho'}=w'(\rho')\left(\frac1{v'}-1\right)\le0.
Thus M is nonincreasing in both inputs. The function \rho=R/(R+M) increases with R and decreases with M. Likewise v=(1+R)/(R+M) increases with R when M\ge1 and decreases with M. The asserted monotonicity follows, and strictness of \rho propagates under iteration. □
At the root, write m=\bigl(1-(1-\rho_1)^{1/b}\bigr)/(1-\rho_1)^{1/b}. Then
r_0:=\frac{B_0}{A_1}=v_1m,\qquad \kappa=v_1(1+m)^b,
and the root equation gives
z=v_1^{b+1}m\left(\frac{1+m}{1+v_1m}\right)^b.
Lemma 20 (Strict activity monotonicity). The root activity above is strictly increasing in both v_1 and m. Consequently, the terminal-to-activity map s\mapsto z_h(s) is strictly increasing on (0,1).
Proof. Direct differentiation gives
\frac{\partial}{\partial v}\log z=\frac{b+1+vm}{v(1+vm)}>0,\qquad \frac{\partial}{\partial m}\log z=\frac1m+\frac{b(1-v)}{(1+m)(1+vm)}>0.
The quantity m is strictly increasing in \rho_1, so Proposition 19 completes the proof. □
Lemma 21 (Endpoint activities). For fixed d,h,
\lim_{s\downarrow0}z_h(s)=0,\qquad \lim_{s\uparrow1}z_h(s)=\infty.
Proof. For terminal (\rho',v')=(s,s) with s\downarrow0, one reverse step has R=O(s^2) and M=\Theta(s^{-b}), so the predecessor tends to (0,0). The reverse map is continuous at every interior state and has the displayed boundary limit; induction over the fixed number h-1 of reverse steps therefore sends every earlier state to (0,0). The root equation then gives z\to0.
As s\uparrow1, one has w\to0, R\to\infty, and M\to1, so one reverse step tends to (1,1). The same finite-step induction sends every earlier state to (1,1). Hence m\to\infty, v_1\to1, and the root equation gives z\to\infty. Continuity of the reverse map and of the root equation also makes s\mapsto z_h(s) continuous. □
Theorem 22 (Unique positive stationary point). For every d\ge3, h\ge1, and z>0, the exact grand-canonical stationarity equations have exactly one positive solution up to common message scaling.
Proof. Every positive solution has one terminal parameter s=\rho_h\in(0,1) and is uniquely reconstructed by Proposition 18. Lemma 20 and Lemma 21 show that s\mapsto z_h(s) is a strictly increasing bijection from (0,1) to (0,\infty). □
For a positive stationary message profile whose reconstructed selected density is \alpha, define \Psi_{d,h}^{\mathrm{stat}}(\alpha):=\mathcal F_{d,h}(x,\ell), where (x,\ell) is its normalized compact profile. Theorem 22 shows that this value is single-valued along the positive reverse-transfer branch.
Exact Grand- and Microcanonical Globality
Although \mathcal F_{d,h} is nonconcave, the preceding interiority and uniqueness results determine its global optimizer.
Theorem 23 (Grand-canonical globality). For every d\ge3, h\ge1, and z>0, the exact grand-canonical functional \mathcal F_{d,h}^{(z)} has a unique global maximizer. It is the positive stationary profile corresponding to the unique terminal parameter s satisfying z_h(s)=z.
Proof. A maximizer exists by compactness. Theorem 15 places every maximizer in the strict interior, so every maximizer satisfies the interior stationarity equations. Theorem 22 gives only one such point. □
The microcanonical problem follows by duality.
Theorem 24 (Microcanonical globality). For every density 1/B_h<\alpha<1, the exact microcanonical functional has a unique global maximizer, and it is the positive stationary profile on the reverse-transfer branch with selected density \alpha. Equivalently,
\Psi_{d,h}(\alpha)=\Psi_{d,h}^{\mathrm{stat}}(\alpha)
throughout the interior feasible interval.
Proof. Write \theta=\log z and \phi_{d,h}(\theta)=\max_{(x,\ell)\in\mathcal P_{d,h}}\{\mathcal F_{d,h}(x,\ell)+\theta p_0\}.
By Theorem 23, the maximizer is unique for every \theta. Danskin’s theorem [16] therefore gives \phi_{d,h}'(\theta)=\alpha(\theta), the density of that maximizer. The derivative of a differentiable convex function is continuous here (equivalently, one may use continuity of the unique optimizer). It is also strictly increasing. Indeed, if \theta_1<\theta_2 had the same maximizing density, the two optimality inequalities would force each optimizer to maximize at both activities. Grand-canonical uniqueness would make the profiles equal, but the root equation assigns one activity to an interior stationary profile, a contradiction. To identify the endpoint limits, let \theta_k\to-\infty and pass, by compactness, to a convergent subsequence of optimizers. Comparing with a feasible profile of density 1/B_h shows that any limit must minimize p_0 over the polytope, hence has density 1/B_h. Similarly, along \theta_k\to\infty, comparison with the all-selected profile forces every subsequential limit to have density 1. Therefore
\alpha(\theta)\to\frac1{B_h}\ (\theta\to-\infty),\qquad \alpha(\theta)\to1\ (\theta\to\infty).
Hence every interior density is attained.
Fix \alpha and choose \theta with \alpha(\theta)=\alpha. For every profile P of density \alpha, \mathcal F(P)+\theta\alpha\le \mathcal F(P_\theta)+\theta\alpha, so P_\theta is the microcanonical maximizer. Uniqueness follows from grand-canonical uniqueness. □
Corollary 25 (Concavity and the envelope identity). The exact value function \Psi_{d,h} is strictly concave on (1/B_h,1) and differentiable there. If z(\alpha) is the activity exposing density \alpha, then
\Psi_{d,h}'(\alpha)=-\log z(\alpha).
Proof. This is the standard differentiable Legendre correspondence produced by the unique maximizers in Theorem 23 and Theorem 24. Strict monotonicity of \alpha(\theta) gives strict concavity. □
For later use, we collect the two conclusions as
\Psi_{d,h}(\alpha)=\Psi_{d,h}^{\mathrm{stat}}(\alpha),\qquad \Psi_{d,h}'(\alpha)=-\log z(\alpha).
Explicit positive Hessian directions at stratified profiles do not contradict these theorems: they occur at nonstationary stratified profiles. The compact functional is genuinely nonconcave, but no competing stationary maximum exists.
Corrected Stationary Telescoping and Root Formulas
Define
Z_v=zS_0^d+\sum_{i=1}^h\left[S_i^d-(S_i-B_{i-1})^d\right],\qquad Z_e=\sum_{i=0}^h B_i^2+2\sum_{i=0}^{h-1}B_iA_{i+1}.
The stationary vertex and edge normalizers satisfy the following exact telescoping identity.
Proposition 26 (Corrected telescoping identity). Every positive stationary solution satisfies
Z_v=\kappa Z_e.
Proof. For 1\le i\le h, put V_i=S_i^d-(S_i-B_{i-1})^d. Using the stationary equations for A_i,B_i,
V_i=\kappa\left(B_{i-1}A_i+B_i^2+B_iA_{i+1}\right).
The root contribution is zS_0^d=\kappa(B_0^2+B_0A_1). After summation, every square B_i^2 appears once and every cross term B_iA_{i+1} appears twice: once from each adjacent vertex contribution, with the root supplying the first copy of B_0A_1. This is exactly \kappa Z_e. □
Normalize A_1=1 and write r=B_0. Proposition 26 gives
\alpha=\frac{r(1+r)}{Z_e}.
The pressure is \phi=\log Z_v-\tfrac d2\log Z_e, and the root equation is \log z=\log\kappa+\log r-(d-1)\log(1+r). Eliminating Z_e gives the corrected root-only formulas
\phi=\log z+\frac d2\log\frac{1+r}r+\frac{d-2}2\log\alpha,
\Psi=(1-\alpha)\left(\log\kappa-\frac{d-2}2\right)+\alpha\log r+\frac{d-2}2\log\alpha+\left((d-1)\alpha-\frac{d-2}2\right)\log(1+r).
The corrected formulas are used throughout this paper. Calculations made directly from Z_v and Z_e are unaffected, provided the power differences are evaluated stably as discussed in Section 16.
Terminal Logarithmic Coordinate and Exact Outer Orbits
Retain the normalization A_1=1 and the reverse-transfer coordinates \rho_i=B_i/A_i, u_i=A_{i+1}/A_i, v_i=\rho_i+u_i, q_i=1-v_i. At the terminal wall u_h=0. We write
\rho_h=v_h=s=1-e^{-t},\qquad q_h=e^{-t}.
The exact reverse dynamics are those of Proposition 18.
Two boundary orbits are exact. On the stable boundary \rho=0, the forward map is u\mapsto u^{1/b} and the reverse map is u'\mapsto (u')^b. On the free boundary q=0, the forward map is u\mapsto u^b and the reverse map is u'\mapsto (u')^{1/b}.
For terminal parameter t, define the free density
a_h(t):=1-e^{-t/b^h}.
The exact free orbit with this density is
\bar u_i=e^{-t/b^{h-i}},\qquad \bar\rho_i=1-\bar u_i,\qquad \bar q_i=0.
Uniform One-Step Estimates
The slack theorem requires only terminal parameters linear in h and uniformly below the critical coefficient.
Definition 27 (Subcritical terminal window). Fix constants 0<\tau_-\le\tau_+<\dfrac{4\log b}{3D}. A sequence of terminal parameters is in the subcritical linear window if
\tau_-h\le t\le \tau_+h.
All constants below may depend on d,\tau_-,\tau_+ but not on h or t in this window.
Free-side perturbations
At one reverse step, keep \rho' fixed and write q'=1-v'. The free predecessor with the same \rho' has w=(1-\rho')^{1/b}, \rho_0=1-w, u_0=w, q_0=0.
Lemma 28 (Uniform free-side step). There are \delta_0,C>0 such that, whenever 0\le q'\le\delta_0, the actual predecessor satisfies
1-\rho=w(1+\eta_\rho),\qquad q=bw^2q'(1+\eta_q),
with |\eta_\rho|+|\eta_q|\le Cq'. The estimates are uniform for 0<w\le1.
Proof. Put \delta=q'. Since v'=1-\delta,
R=(1-\delta)\frac{1-w}w,\qquad M=\left(1-w+\frac w{1-\delta}\right)^b=\left(1+\frac{w\delta}{1-\delta}\right)^b.
For \delta\le1/2, the binomial expansion with a uniform remainder gives M=1+bw\delta+O_d(\delta^2). Furthermore,
w(R+M)=(1-\delta)(1-w)+wM=1+O_d(\delta).
Now 1-\rho=u+q=M/(R+M), q=(M-1)/(R+M). Substitution gives the displayed expansions. □
Stable-side perturbations
For a reverse step near the stable manifold, write the next state as v'=V, \rho'=V\delta, u'=V(1-\delta). The stable predecessor with the same V is (\rho_0,u_0)=(0,V^b).
Lemma 29 (Uniform stable-side step). There are \delta_1,C>0 such that, whenever 0\le\delta\le\delta_1, the predecessor satisfies
\log u=b\log V+O_d(V\delta),\qquad \frac\rho v=\frac{V^2}b\delta(1+O_d(\delta)).
Put \widetilde a_i:=\rho_i/(bu_i^D). Then
\frac{\widetilde a_i}{\widetilde a_{i+1}}=1+O_d(\delta).
For sufficiently small \delta_1, the transverse ratios contract backward:
\frac{\rho_i}{v_i}\le\frac{1+o(1)}b\,\frac{\rho_{i+1}}{v_{i+1}}.
Proof. Here w=(1-V\delta)^{1/b}, e=1-w=(V\delta/b)(1+O_d(\delta)), so R=V(e/w)=(V^2\delta/b)(1+O_d(\delta)). Also
e+\frac wV=\frac1V(w+Ve)=\frac1V(1-e(1-V)),
whence M=V^{-b}(1+O_d(V\delta)). Since R/M=O_d(V^{b+2}\delta), the reverse-map formula for u yields the displayed expansion for \log u; moreover \rho/u=R, which gives the displayed expansion for \rho/v.
For the transverse-ratio estimate, use \rho=uR and compute \widetilde a_i/\widetilde a_{i+1}=bRu_i^{1-D}(u')^D/\rho'. The preceding expansions give bR/\rho'=V(1+O_d(\delta)) and u^{1-D}(u')^D=V^{-1}(1+O_d(\delta)), because (b-1)D=b+1. Their product is 1+O_d(\delta). □
Free Shadowing to an Overlap Layer
For t in the terminal window, choose H=\lceil 3Dt/(4\log b)\rceil, m=h-H. Then H,m are both linear in h. Define the formal free transverse sequence, for m\le i\le h, by
\bar q_i=b^{h-i}\exp\!\left(-Dt+\frac{2t}{b-1}b^{i-h}\right).
It satisfies \bar q_h=e^{-t} and \bar q_i=b\bar u_i^2\bar q_{i+1}.
Proposition 30 (Uniform free shadow). There is c_0>0 such that, uniformly in the terminal window,
q_i=\bar q_i(1+O(he^{-c_0h})),\qquad 1-\rho_i=\bar u_i(1+O(e^{-c_0h}))
for every m\le i\le h. In particular,
q_m=b^H\exp\!\left(-Dt+\frac{2t}{b-1}b^{-H}\right)(1+o(1)),\qquad \rho_m=tb^{-H}(1+o(1)),\qquad \frac{\rho_m}{q_m}=o(1).
All errors are exponentially small in h.
Proof. Let E_i=\log((1-\rho_i)/\bar u_i). Lemma 28 gives E_i=\tfrac1bE_{i+1}+O(q_{i+1}), and
\log\frac{q_i}{\bar q_i}=\log\frac{q_{i+1}}{\bar q_{i+1}}+\frac2bE_{i+1}+O(q_{i+1}).
Both errors vanish at i=h.
It remains to verify that the formal transverse sequence is uniformly exponentially small. Write r=h-i. Its logarithm is
f(r)=r\log b-Dt+\frac{2t}{b-1}b^{-r}.
The function f is convex, so its maximum on 0\le r\le H occurs at an endpoint. At r=0, f(0)=-t. At r=H, the definition of H gives f(H)\le -\tfrac14Dt+o(1). Thus \max_iq_i\le e^{-c_0h}.
A standard first-failure bootstrap now closes. As long as q_i\le2\bar q_i, the two displayed recurrences imply \max_i|E_i|=O(e^{-c_0h}), \max_i\log(q_i/\bar q_i)=O(he^{-c_0h}). For large h these estimates prevent the first failure. This proves the displayed uniform estimates.
The formula for q_m follows from 1-e^{-t/b^H}=tb^{-H}(1+o(1)) evaluated at r=H. Finally, \log(\rho_m/q_m)=\log t-2H\log b+Dt+o(h)=-\tfrac12Dt+o(h), which proves the last assertion. □
Stable Shadowing from the Overlap to the Root
Put x=-\log u_1, \widetilde a=\rho_1/(bu_1^D).
Proposition 31 (Uniform stable shadow). Under the terminal-window assumptions and the matching choice of H,m from Section 12,
x=b^{m-1}q_m(1+o(1)),\qquad \widetilde a=\frac{\rho_m}{b^m}(1+o(1)).
If the messages are normalized by A_1=1, then
\log A_m=\frac{b}{b-1}\bigl(1-b^{-(m-1)}\bigr)\log u_1+o(1),
and
B_0=\widetilde aA_m^2(1+o(1)).
All errors are uniform and exponentially small apart from the displayed o(1) generated by q_m.
Proof. Set \delta_i=\rho_i/v_i. Proposition 30 gives \delta_m=o(1), and Lemma 29 implies geometric backward contraction. Hence \sum_{i=2}^m\delta_i=O(\delta_m).
Iteration of the transverse-ratio contraction gives \widetilde a=\rho_m/(b^mu_m^D)(1+O(\delta_m)). Since u_m=1-q_m-\rho_m=1-o(1), this proves the displayed formula for \widetilde a.
The stable-step estimate also gives \log v_i=b\log v_{i+1}+O(\rho_{i+1}). After iteration,
-\log v_1=b^{m-1}[-\log v_m]+O\!\left(\sum_{j=2}^mb^{j-2}\rho_j\right).
Backward transverse contraction bounds the error by O(b^{m-1}\rho_m). Since v_m=1-q_m and \rho_m/q_m=o(1), -\log v_1=b^{m-1}q_m(1+o(1)). The difference between -\log u_1 and -\log v_1 is O(\delta_1), proving the displayed formula for x.
Likewise, the stable-side expansion for \log u and the contraction of \delta_i imply \log u_i=b^{-(i-1)}\log u_1+O(\delta_m) uniformly after summation with the geometric weights. Summing over 1\le i<m gives the displayed formula for \log A_m.
At the root, B_0=v_1\bigl(1-(1-\rho_1)^{1/b}\bigr)/(1-\rho_1)^{1/b}=\widetilde au_1^{D+1}(1+o(1)). Since D+1=2b/(b-1), the displayed formulas for x and \log A_m show
\log\frac{B_0}{\widetilde aA_m^2}=-\frac{2b}{b-1}\frac x{b^{m-1}}+o(1)=o(1),
which proves the last assertion. □
Density and Activity Asymptotics
The free and stable shadows now match without an additional hypothesis.
Theorem 32 (Terminal-window matching). Uniformly for t in every subcritical linear window,
\widetilde a=a_h(t)(1+o(1)),\qquad \frac x{b^{h-1}}=(1-a_h(t))^{B_h}(1+o(1)).
Proof. Proposition 30 and Proposition 31 give \widetilde a=(t/b^h)(1+o(1))=a_h(t)(1+o(1)). Combining the displayed formulas for q_m and x yields
\frac x{b^{h-1}}=\exp\!\left(-Dt+\frac{2t}{b-1}b^{-H}\right)(1+o(1)).
On the other hand, by the definitions of B_h and a_h(t),
(1-a_h(t))^{B_h}=\exp\!\left(-Dt+\frac{2t}{b-1}b^{-h}\right).
Since tb^{-H}=o(1), the two expressions agree relatively. □
To pass from \widetilde a to the actual selected density, reconstruct the edge partition function Z_e=\sum_{i=0}^h B_i^2+2\sum_{i=0}^{h-1}B_iA_{i+1}.
Lemma 33 (Edge-normalizer localization). With the matching index m,
Z_e=A_m^2(1+o(1)).
Consequently,
\alpha=\widetilde a(1+o(1))=a_h(t)(1+o(1)),\qquad B_h|\alpha-a_h(t)|=o(1).
Proof. For i\ge m, B_i^2+2B_iA_{i+1}=(B_i+A_{i+1})^2-A_{i+1}^2. Since B_i+A_{i+1}=A_i(1-q_i), summation gives the exact tail identity
\sum_{i=m}^h(B_i^2+2B_iA_{i+1})=A_m^2(1-q_m)^2-\sum_{i=m+1}^h A_i^2q_i(2-q_i).
Proposition 30 makes the right side A_m^2(1+o(1)).
For the left part, Proposition 31 and the stable invariant give, uniformly for i<m, \rho_i=\widetilde ab^iu_i^D(1+o(1)), while A_i^2u_i^{D+1}/A_m^2=1+o(1). Therefore
\frac1{A_m^2}\sum_{i=1}^{m-1}2B_iA_{i+1}\le C\widetilde a\sum_{i=1}^{m-1}b^i=O(\widetilde ab^m)=O(\rho_m)=o(1).
The square terms are smaller by a factor \rho_i/u_i, and the root term is O(\widetilde aA_m^2). This proves the displayed formula for Z_e.
Finally, the exact root belief is \alpha=B_0(B_0+A_1)/Z_e. Use A_1=1, Proposition 31, the displayed formula for Z_e, and B_0=o(1) to obtain the displayed conclusions. The error estimates above are exponentially small in h, while a_h(t)B_h=\Theta(h), yielding the last assertion. □
The root reconstruction formulas are
B_0=v_1\frac{1-(1-\rho_1)^{1/b}}{(1-\rho_1)^{1/b}},\qquad \kappa=\left(\frac{v_1}{(1-\rho_1)^{1/b}}\right)^b,\qquad z=\frac{B_0\kappa}{(1+B_0)^b}.
Theorem 34 (Uniform activity law). Fix constants 0<c_-<c_+<4/3. Uniformly for densities satisfying
c_-\log B_h\le \alpha B_h\le c_+\log B_h,
one has
-\log z(\alpha)=\log\frac1\alpha+B_h(1-\alpha)^{B_h}(1+o(1)).
In particular, for all sufficiently large h,
-\log z(\alpha)\ge \log\frac1\alpha+\frac12B_h(1-\alpha)^{B_h}
uniformly on the displayed interval.
Proof. First work in a terminal window. At the root, the stable estimates give B_0=\widetilde au_1^{D+1}(1+o(1)), \kappa=u_1^b(1+o(1)). Hence
-\log z=\log\frac1{\widetilde a}+Kx+o(1),\qquad K=b+D+1=bD.
The exact arithmetic identity Kb^{h-1}=Db^h=B_h+2/(b-1) and Theorem 32 give Kx=B_h(1-a_h(t))^{B_h}(1+o(1)).
Lemma 33 permits a_h(t) and \widetilde a to be replaced by \alpha: the relative density error tends to zero and B_h|\alpha-a_h(t)|=o(1), so the exponential term also changes relatively by 1+o(1).
It remains to identify the terminal range corresponding to the displayed density interval. By Lemma 33, uniformly in every terminal window, \alpha B_h=Dt(1+o(1)). Since \log B_h=h\log b+O(1), choose constants \delta_-,\delta_+>0 such that \underline\tau=(c_--\delta_-)\log b/D>0 and \overline\tau=(c_++\delta_+)\log b/D<4\log b/(3D). Uniformly on this broader terminal window, \alpha B_h=Dt(1+o(1)). At t=\underline\tau h the resulting density is below c_-\log B_h/B_h, while at t=\overline\tau h it is above c_+\log B_h/B_h. The terminal parameter increases the activity by Lemma 20, and activity increases the selected density by Theorem 24; hence every density in the displayed interval is exposed by a terminal parameter in the broader window. The preceding estimate is therefore uniform there. □
Near-Critical Integration and the Random-Graph Deduction
We first prove Theorem 2. The pointwise anchor is Corollary 8.
Proof of Theorem 2. Put B=B_h and L=\log B. For a value C in the theorem’s hypothesis, set
\alpha_-=\frac CB,\qquad C^\sharp=\frac{L+C}2,\qquad \alpha_+=\frac{C^\sharp}B.
For large h, the interval [\alpha_-,\alpha_+] lies in a fixed density window \eta L/(2B)\le a\le L/B, so Theorem 34 applies uniformly. Exact globality and the envelope identity of Corollary 25 give
\Psi(\alpha_-)=\Psi(\alpha_+)+\int_{\alpha_-}^{\alpha_+}\log z(a)\,da.
Corollary 8 and Theorem 34’s displayed inequality imply
\Psi(\alpha_-)\le H(\alpha_+)-\int_{\alpha_-}^{\alpha_+}\log\frac1a\,da-\frac12\int_{\alpha_-}^{\alpha_+}B(1-a)^Bda \le H(\alpha_-)-\frac1{2B+1}\left[(1-\alpha_-)^{B+1}-(1-\alpha_+)^{B+1}\right].
The second inequality uses H'(a)=\log(1/a)+\log(1-a).
Write W(C):=L-2\log L-C. By hypothesis W(C)\ge W_h\to\infty. Uniformly over the theorem’s interval,
H(\alpha_-)=O\!\left(\frac{L^2}B\right)=o(e^{-C}),
because e^{-C}=e^{W(C)}L^2/B. Also C=O(L) gives (1-\alpha_-)^{B+1}=e^{-C}(1+o(1)). Finally, C^\sharp-C=(L-C)/2\ge \log L+W_h/2, so
(1-\alpha_+)^{B+1}=e^{-C^\sharp}(1+o(1))=o(e^{-C}).
All estimates are uniform, proving the theorem. □
Proof of Corollary 4. For C=cL with c\in[c_-,c_+], one has L-2\log L-C=(1-c)L-2\log L\to\infty uniformly. Theorem 2 gives e^{-C}=B^{-c}. □
Proof of Theorem 5. Set T_n=nC_h^*/B_h. For large n, C_h^*>0. If T_n\le1, the real-valued lower bound follows from \gamma_h(G)\ge1. Otherwise put m_n=\lceil T_n\rceil-1, C_n=m_nB_h/n. Then m_n<T_n and m_n/T_n\ge1/2. Choose \eta>0 such that C_h^*\ge2\eta L_h eventually. Then, for large h, \eta L_h\le C_n\le C_h^*.
Apply Theorem 2 with this \eta and the same W_h. Since e^{-C_n}\ge e^{-C_h^*}=e^{W_h}L_h^2/B_h and \tfrac12-o(1)\ge\tfrac13 for sufficiently large h,
\log \mathbb E Z_{n,d,h}(m_n)\le -\frac13\frac{ne^{W_h}L_h^2}{B_h}+O_d(h\log n),
which tends to -\infty by the growth hypothesis. Markov’s inequality shows that the configuration model has no dominating set of size exactly m_n with high probability. Any smaller dominating set could be padded to size m_n, so \gamma_h(G)\ge m_n+1=\lceil T_n\rceil\ge T_n. Conditioning on simplicity transfers the conclusion to the uniformly random simple d-regular graph. □
Proof of Corollary 6. Choose W_h=\varepsilon L_h-2\log L_h. Then W_h\to\infty, C_h^*=(1-\varepsilon)L_h, C_h^*/L_h=1-\varepsilon>0, and e^{W_h}L_h^2/B_h=B_h^{-(1-\varepsilon)}. Thus Theorem 5 applies directly. □
Numerical Verification and Conditioning
The proofs above do not use numerical evidence. The accompanying package nevertheless checks every stationary identity, the one-step shadowing expansions, the density targeting, and the activity law with controlled-precision arithmetic.
A cancellation issue discovered during numerical verification is important for reproducibility. Direct evaluation of \phi=\log Z_v-\tfrac d2\log Z_e can be ill-conditioned near criticality: both logarithms are large, and individual vertex terms of the form S_i^d-(S_i-B_{i-1})^d may lose precision. The consolidated solver evaluates these differences as
S_i^d\cdot\bigl(-\operatorname{expm1}(d\log(1-B_{i-1}/S_i))\bigr)
and reports the microcanonical exponent through the corrected root-only formula of Section 9. The direct partition-function route is retained as an independent comparison. A row is rejected unless
\frac{|\Psi_{Z_v}-\Psi_{\mathrm{root}}|}{|\Psi_{\mathrm{root}}|}\le 10^{-6}.
Thus a cross-check residual comparable to the reported quantity gates the record rather than remaining hidden in an internal data structure.
For the diagnostic choice W_h=\log\log B_h, the regenerated cubic values are
| h | C | -\Psi/e^{-C} | activity-law ratio |
|---|---|---|---|
| 20 | 6.8451 | 0.6484 | 0.5873 |
| 30 | 12.6345 | 0.9418 | 0.9520 |
| 40 | 18.7408 | 0.9757 | 0.9956 |
| 52 | 26.2980 | 0.9819 | 0.9997 |
The activity-law ratio is \bigl(-\log z-\log(1/\alpha)\bigr)/\bigl(B_h(1-\alpha)^{B_h}\bigr). The effective onset is slower when C/\log B_h is small, consistent with uniformity only on compact intervals bounded away from zero. Every numerical row records the checker hash, solver hash, precision, stationarity residual, telescoping residual, and the discrepancy between the direct and root-only free-energy routes.
A companion, more narrative account of this same numerical package — including the code itself and the story of the concavity conjecture it killed — is at From Path Tubes to a Near-Critical Domination Bound.
Consequences and Open Problems
Theorem 5 proves the first-moment lower transition up to an arbitrary diverging additive term. Three harder problems remain logically separate.
The bounded critical window
The broad-overlap shadowing argument does not determine the O(1) window. The transfer calculations predict
\alpha_h^{\mathrm{ann}}B_h=\log B_h-2\log\log B_h+o(1),
but proving this requires errors of the same order as the competing entropy and coupon terms.
Quenched matching
The theorem is a first-moment lower bound. A matching upper bound near the annealed zero crossing would require a second moment, small-subgraph conditioning, or an algorithmic construction. In tree-ball geometry, the elementary random-placement-and-patching upper bound is (1+o(1))n\log B_h/B_h. Establishing a matching quenched upper bound in the full random-regular growing-radius regime is separate.
Direct two-branch asymptotics
Internally two-path (h,2) domination is defined in Definition 1 and is stronger than ordinary distance domination. The present theorem transfers as a lower bound but does not identify its own leading constant or critical correction. A direct branch-message analysis is a separate problem.