Proof. If \(\mathbf{d}=\delta(\Pi,H)\), then the restriction of \(H\) to \(\Pi[s]\) realizes \((\mathbf{d}[x,s])_{x\in\Pi[s]}\) and the restriction of \(H\) to the pairs between \(\Pi[s]\) and \(\Pi[t]\) realizes the pair \((\mathbf{d}[x,t])_{x\in\Pi[s]}\), \((\mathbf{d}[y,s])_{y\in\Pi[t]}\). Conversely, given a graph on each \(\Pi[s]\) and a bipartite graph between each \(\Pi[s]\) and \(\Pi[t]\) realizing these sequences, their union \(H\) is a simple graph on \(V\), because the block pairs involve disjoint sets of vertex pairs, and \(\delta(\Pi,H)=\mathbf{d}\) by construction. ◻

Proof. The assertion for \(r=1\) is the hypothesis on \(c\). If it holds for some \(r<k\), then for \(x\in\Pi[s]\), \[\sum_{y\sim_H x}c_r(\mathfrak g)[y] =\sum_{t\in\{0,1\}^k}(-1)^{t[r-1]}\deg^H_{\Pi[t]}x =\sum_{t\in\{0,1\}^k}(-1)^{t[r-1]}\mathbf d[x,t] \ge_{s[r-1]s[r]}0.\] The last relation is the \(r\)th constraint in \(\mathcal I_s(\mathbf d[x,\bullet])\). Together with \(c_r(\mathfrak g)[x]=(-1)^{s[r-1]}\), the tie-breaking rule gives \(c_{r+1}(\mathfrak g)[x]=(-1)^{s[r]}\). This proves the assertion by induction, hence \(\Pi_k(\mathfrak g)=\Pi\) and \(\sigma_k(\mathfrak g)=(\Pi,\mathbf d)\). A realizing graph \(H\) exists because \(\mathbf d\in\mathcal D(\Pi)\), which proves attainability. ◻

Proof. We first explain why the displayed one-step statement, which conditions on the present state only, is equivalent to the Markov property, which conditions on the whole history \((\sigma_1(\mathfrak{g}),\ldots,\sigma_k(\mathfrak{g}))\). The reason is that \(\sigma_k(\mathfrak{g})\) determines the earlier states: for \(r<k\), the block \(\Pi_r(\mathfrak{g})[u]\) is the union of the blocks \(\Pi_k(\mathfrak{g})[s]\) over the strings \(s\) whose first \(r\) bits form \(u\), and \(\delta(\Pi_r(\mathfrak{g}),G)[x,u]\) is the sum of the entries \(\delta(\Pi_k(\mathfrak{g}),G)[x,s]\) over the same strings \(s\). Hence conditioning on \(\sigma_k(\mathfrak{g})\) is the same as conditioning on the whole history, and it suffices to prove the displayed identity.

Once \(\sigma_k(\mathfrak{g})=(\Pi,\mathbf{d})\) is known, the next partition is already determined: it is exactly \(\Phi_k(\sigma)\). The only remaining randomness in \(\sigma_{k+1}(\mathfrak{g})\) is the way the degree-constrained edge sets of the block pairs of \(\Pi\) split across the deterministic refinement \(\Phi_k(\sigma)\).

Condition on \(\sigma_k(\mathfrak{g})=(\Pi,\mathbf{d})\). Since this state has positive probability, \(\Pi\) is compatible with the fixed initial coloring \(c\), in the sense that \(x\in\Pi[s]\) implies \(c[x]=(-1)^{s[0]}\). Conversely, on the event \(\delta(\Pi,G)=\mathbf{d}\), Fact 2.2 gives \(\sigma_k(\mathfrak g)=\sigma\). Thus, for the present state \(\sigma\), the event \(\{\sigma_k(\mathfrak{g})=\sigma\}\) is exactly the event \(\{\delta(\Pi,G)=\mathbf{d}\}\).

The random edge sets of the internal and bipartite block pairs of \(\Pi\) are independent in \(\mathbb{G}(V,p)\), and the constraints recorded by \(\mathbf{d}\) involve these disjoint edge sets separately. Therefore the conditional law is a product over the block pairs of \(\Pi\). Inside \(\Pi[s]\), every simple graph with degree sequence \((\mathbf{d}[x,s])_{x\in\Pi[s]}\) has the same number of edges, and hence the same conditional probability; similarly, between \(\Pi[s]\) and \(\Pi[t]\), every simple bipartite graph with degree sequences \((\mathbf{d}[x,t])_{x\in\Pi[s]}\) and \((\mathbf{d}[y,s])_{y\in\Pi[t]}\) has the same number of edges. Thus the conditional distribution is exactly the product of uniformly random degree-constrained graphs and bipartite graphs used to define \(K_k(\sigma,\cdot)\).

It follows that the conditional law of \(\sigma_{k+1}(\mathfrak{g})\) given \(\sigma_k(\mathfrak{g})=\sigma\) is \(K_k(\sigma,\cdot)\), which depends only on the present state. This is the Markov property. ◻

Proof. Let \(\Pi=\operatorname{part}(y)\) and write \[E_y:=\left\{\rho_k^{(p)}(\sigma_k(\mathfrak{g}))=y\right\},\qquad \widetilde\sigma:=\left(\Pi,\delta(\Pi,G)\right).\] Since \(\mathbb{P}[E_y]>0\), the partition \(\Pi\) is compatible with the fixed coloring \(c\): if \(x\in\Pi[s]\), then \(c[x]=(-1)^{s[0]}\).

We first identify the event \(E_y\). On \(E_y\) we have \(\Pi_k(\mathfrak{g})=\Pi\), hence \(\sigma_k(\mathfrak{g})=(\Pi,\delta(\Pi,G))=\widetilde\sigma\); in particular \(\widetilde\sigma\in\mathcal{S}_k(V)\) and \(\rho_k^{(p)}(\widetilde\sigma)=y\). Conversely, if \(\widetilde\sigma\in\mathcal S_k(V)\) and \(\rho_k^{(p)}(\widetilde\sigma)=y\), the compatibility of \(\Pi\) with \(c\) and Fact 2.2, applied to the graph \(G\), give \(\sigma_k(\mathfrak g)=\widetilde\sigma\). Thus \(\rho_k^{(p)}(\sigma_k(\mathfrak g))=y\), and therefore \[E_y=\left\{\widetilde\sigma\in\mathcal{S}_k(V),\; \rho_k^{(p)}(\widetilde\sigma)=y\right\}.\] In particular, \(y\) is \(p\)-attainable. Since \(\sigma_k(\mathfrak{g})=\widetilde\sigma\) on \(E_y\), conditional on \(E_y\) the state \(\sigma_k(\mathfrak{g})\) has law \(\Lambda_y^{(p)}\), which by definition is the law of \(\widetilde\sigma\) conditioned on the event displayed above.

Let \(A=(\rho_{k+1}^{(p)})^{-1}(B)\). Every state \(\sigma\) in the support of \(\Lambda_y^{(p)}\) satisfies \(\mathbb{P}[\sigma_k(\mathfrak{g})=\sigma]\ge\mathbb{P}[\sigma_k(\mathfrak{g})=\sigma,\,E_y]>0\), so Proposition 2.3 applies to it and gives \[\mathbb{P}\left[\sigma_{k+1}(\mathfrak{g})\in A\mid \sigma_k(\mathfrak{g})=\sigma\right]=K_k(\sigma,A).\] For such \(\sigma\) we also have \(\{\sigma_k(\mathfrak{g})=\sigma\}\subseteq E_y\), because \(\rho_k^{(p)}(\sigma)=y\). Hence, by the law of total probability over the value of \(\sigma_k(\mathfrak{g})\), whose conditional law given \(E_y\) is \(\Lambda_y^{(p)}\), \[\begin{aligned} \mathbb{P}\left[\rho_{k+1}^{(p)}(\sigma_{k+1}(\mathfrak{g}))\in B\mid E_y\right] &=\sum_{\sigma}\mathbb{P}\left[\sigma_k(\mathfrak{g})=\sigma\mid E_y\right]\mathbb{P}\left[\sigma_{k+1}(\mathfrak{g})\in A\mid\sigma_k(\mathfrak{g})=\sigma\right]\\ &=\mathbb{E}_{\sigma\sim\Lambda_y^{(p)}}\left[K_k\left(\sigma,(\rho_{k+1}^{(p)})^{-1}(B)\right)\right], \end{aligned}\] which is \(\overline K_k^{(p)}(y,B)\) by definition. ◻

Proof. The event \(\mathcal{I}_\Pi=\bigcap_{x\in V}\mathcal{I}_{s(x)}(\mathbf{D}[x,\bullet])\), where \(s(x)\) denotes the block index of \(x\), is an intersection of one event per row, each depending on that row alone, and it has positive probability by the hypothesis. Since \(\mathsf{R}_{\Pi,\lambda}\) is a product over rows, for arrays \(\mathbf{d}\in\mathcal{A}(\Pi)\) satisfying \(\mathcal{I}_\Pi(\mathbf{d})\), \[\mathsf{R}_{\Pi,\lambda}\left(\mathbf{d}\mid\mathcal{I}_\Pi\right) =\frac{\prod_{x\in V}\mathbb{P}\left[A_{s(x),\bullet}=\mathbf{d}[x,\bullet]\right]}{\prod_{x\in V}\mathbb{P}\left[\mathcal{I}_{s(x)}(A_{s(x),\bullet})\right]} =\prod_{x\in V}\mathbb{P}\left[A_{s(x),\bullet}=\mathbf{d}[x,\bullet]\ \middle|\ \mathcal{I}_{s(x)}(A_{s(x),\bullet})\right],\] and \(\mathsf{R}_{\Pi,\lambda}(\mathbf{d}\mid\mathcal{I}_\Pi)=0\) when \(\mathcal{I}_\Pi(\mathbf{d})\) fails, which is also the value of the right-hand side. The right-hand side is a product law with the stated factors. ◻

Proof. By definition, \(\Lambda_y^{(p)}\) is obtained by sampling \(G\sim\mathbb{G}(V,p)\), forming \[\widetilde\sigma_y(G)=(\Pi,\delta(\Pi,G)),\] and conditioning on \[\widetilde\sigma_y(G)\in\mathcal{S}_k(V),\qquad \rho_k^{(p)}(\widetilde\sigma_y(G))=y.\] Writing \(\mathbf{D}=\delta(\Pi,G)\), the first condition says exactly that \(\mathbf{D}\in\mathcal{D}(\Pi)\) and \(\mathcal{I}_\Pi(\mathbf{D})\) holds, and the condition \(\mathbf{D}\in\mathcal{D}(\Pi)\) is automatic because \(\mathbf{D}\) is the degree array of the graph \(G\). Since \(y=(\Pi,m,1)\), the second condition imposes \[m(\Pi,\mathbf{D})=m,\qquad \kappa_p(\Pi,\mathbf{D}).\] Thus \(\Lambda_y^{(p)}\) is the law of \((\Pi,\mathbf{D})\) conditioned on the single event \(\{m(\Pi,\mathbf{D})=m\}\cap\mathcal{I}_\Pi\cap\kappa_p(\Pi,\cdot)\). Writing \(\mathcal{B}:=\mathcal{I}_\Pi\cap\kappa_p(\Pi,\cdot)\) and \(\{m\}:=\{\mathbf{d}\in\mathcal{A}(\Pi):m(\Pi,\mathbf{d})=m\}\), we therefore have, for every \(E\subseteq\mathcal{A}(\Pi)\), \[\begin{aligned} \Lambda_y^{(p)}\left(\left\{\sigma:\operatorname{deg}(\sigma)\in E\right\}\right) &=\frac{\mathbb{P}\left[\mathbf{D}\in E\cap\{m\}\cap\mathcal{B}\right]}{\mathbb{P}\left[\mathbf{D}\in\{m\}\cap\mathcal{B}\right]} =\frac{\mathbb{P}\left[\mathbf{D}\in E\cap\mathcal{B}\mid \mathbf{D}\in\{m\}\right]}{\mathbb{P}\left[\mathbf{D}\in\mathcal{B}\mid \mathbf{D}\in\{m\}\right]}\\ &=\frac{\mathsf{G}_{\Pi,m}(E\cap\mathcal{B})}{\mathsf{G}_{\Pi,m}(\mathcal{B})} =\mathsf{G}_{\Pi,m}\left(E\mid\mathcal{B}\right), \end{aligned}\] where the second equality divides numerator and denominator by \(\mathbb{P}[\mathbf{D}\in\{m\}]>0\), and the third is the definition of \(\mathsf{G}_{\Pi,m}\) as the law of \(\mathbf{D}=\delta(\Pi,G)\) conditioned on \(\{m\}\) (Definition 3.5). ◻

Proof. Throughout the proof we abbreviate \(\Gamma:=\Gamma_{C_{B.3}(\theta,k,T,\phi),p}(\Pi,m,\cdot)\), \(\kappa_p:=\kappa_p(\Pi,\cdot)\), and \(\{m\}:=\{\mathbf{D}\in\mathcal{A}(\Pi):m(\Pi,\mathbf{D})=m\}\). By Proposition 3.7, it suffices to prove \[\label{eq:transf-goal} \mathsf{G}_{\Pi,m}\left(E^c\mid \mathcal{I}_\Pi\cap\kappa_p\right)\le e^{-N}+C_{3.8}\,\mathsf{R}_{\Pi,\lambda}\left(E^c\mid\mathcal{I}_\Pi,\{m\}\right)\] for a suitable constant \(C_{3.8}\).

Step 1: restriction to \(\Gamma\). By Lemma B.3, \[\label{eq:transf-gamma} \mathsf{G}_{\Pi,m}\left(\Gamma^c\mid \mathcal{I}_\Pi\cap\kappa_p\right)\le e^{-N}.\] Since \(E^c\subseteq\Gamma^c\cup(E^c\cap\Gamma)\), and since \(\mathsf{G}_{\Pi,m}(\mathcal{I}_\Pi\cap\kappa_p)\ge\mathsf{G}_{\Pi,m}(\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p)\), Bayes’ rule and (3.2) give \[\label{eq:transf-split} \mathsf{G}_{\Pi,m}\left(E^c\mid \mathcal{I}_\Pi\cap\kappa_p\right) \le e^{-N}+\frac{\mathsf{G}_{\Pi,m}\left(E^c\cap\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p\right)}{\mathsf{G}_{\Pi,m}\left(\mathcal{I}_\Pi\cap\kappa_p\right)} \le e^{-N}+\frac{\mathsf{G}_{\Pi,m}\left(E^c\cap\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p\right)}{\mathsf{G}_{\Pi,m}\left(\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p\right)}.\]

Step 2: comparison with the row model. The measure \(\mathsf{G}_{\Pi,m}\) is supported on \(\{m\}\), so the numerator and denominator in (3.3) are sums of \(\mathsf{G}_{\Pi,m}(\mathbf{d})\) over arrays \(\mathbf{d}\in\{m\}\cap\kappa_p\cap\Gamma\). By (LA2), (LA3), and Lemma B.1, every such array is graphical, and the restriction to \(\Gamma\) in Step 1 is exactly what makes the bounded-ratio comparison Lemma B.2(ii) available for every such array (on \(\kappa_p\) alone only the weak comparison (i) with the factor \(\exp\{O((pN)^{2/7})\}\) holds). Write \(C_1:=C'_{B.2}(\theta,k,T,C_{B.3}(\theta,k,T,\phi))\) for the constant of that comparison. Summing the upper bound \(\mathsf{G}_{\Pi,m}(\mathbf{d})\le C_1\mathsf{R}_{\Pi,\lambda}(\mathbf{d}\mid\{m\})\) over the arrays in the numerator and the lower bound \(\mathsf{G}_{\Pi,m}(\mathbf{d})\ge C_1^{-1}\mathsf{R}_{\Pi,\lambda}(\mathbf{d}\mid\{m\})\) over the arrays in the denominator, \[\label{eq:transf-compare} \frac{\mathsf{G}_{\Pi,m}\left(E^c\cap\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p\right)}{\mathsf{G}_{\Pi,m}\left(\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p\right)} \le C_1^2\, \frac{\mathsf{R}_{\Pi,\lambda}\left(E^c\cap\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p\mid\{m\}\right)}{\mathsf{R}_{\Pi,\lambda}\left(\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p\mid\{m\}\right)}.\]

Step 3: Bayes’ rule in the row model. The event \(\mathcal{I}_\Pi\cap\{m\}\) has positive \(\mathsf{R}_{\Pi,\lambda}\)-probability by Lemma B.6, so we may divide the numerator and the denominator of the right-hand side of (3.4) by \(\mathsf{R}_{\Pi,\lambda}(\mathcal{I}_\Pi\mid\{m\})\), which converts both into probabilities conditional on \(\mathcal{I}_\Pi\cap\{m\}\): \[\label{eq:transf-bayes} \frac{\mathsf{R}_{\Pi,\lambda}\left(E^c\cap\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p\mid\{m\}\right)}{\mathsf{R}_{\Pi,\lambda}\left(\Gamma\cap\mathcal{I}_\Pi\cap\kappa_p\mid\{m\}\right)} = \frac{\mathsf{R}_{\Pi,\lambda}\left(E^c\cap\Gamma\cap\kappa_p\mid\mathcal{I}_\Pi,\{m\}\right)}{\mathsf{R}_{\Pi,\lambda}\left(\Gamma\cap\kappa_p\mid\mathcal{I}_\Pi,\{m\}\right)} \le \frac{\mathsf{R}_{\Pi,\lambda}\left(E^c\mid\mathcal{I}_\Pi,\{m\}\right)}{\mathsf{R}_{\Pi,\lambda}\left(\Gamma\cap\kappa_p\mid\mathcal{I}_\Pi,\{m\}\right)}.\] For the denominator, the chain rule together with Lemma B.7 and Lemma B.4 gives \[\label{eq:transf-denominator} \mathsf{R}_{\Pi,\lambda}\left(\Gamma\cap\kappa_p\mid\mathcal{I}_\Pi,\{m\}\right) =\mathsf{R}_{\Pi,\lambda}\left(\kappa_p\mid\mathcal{I}_\Pi,\{m\}\right)\, \mathsf{R}_{\Pi,\lambda}\left(\Gamma\mid\mathcal{I}_\Pi,\kappa_p,\{m\}\right) =(1-o(1))(1-o(1))\ge\frac12\] for all sufficiently large \(N\). Combining (3.3), (3.4), (3.5), and (3.6), \[\mathsf{G}_{\Pi,m}\left(E^c\mid \mathcal{I}_\Pi\cap\kappa_p\right)\le e^{-N}+2C_1^2\,\mathsf{R}_{\Pi,\lambda}\left(E^c\mid\mathcal{I}_\Pi,\{m\}\right),\] which is (3.1) with \(C_{3.8}:=2C_1^2=2\,C'_{B.2}(\theta,k,T,C_{B.3}(\theta,k,T,\phi))^2\); this constant depends only on \(\theta,k,T,\phi\). The final sentence of the statement follows because the bound holds uniformly in \(E\). ◻

Proof. We prove the proposition with \(C_{3.9}:=1\). Let \(\mathcal{E}\) denote the event that (R1), (R2), and (R3) hold. We first prove \[\mathsf{R}_{\Pi,\lambda}\left(\mathcal{E}\mid \mathcal{I}_\Pi,\ m(\Pi,\mathbf{D})=m\right)=1-o(1).\] By (LA7) the hypothesis of Fact 3.6 holds, so under \(\mathsf{R}_{\Pi,\lambda}(\cdot\mid\mathcal{I}_\Pi)\) the rows \(\mathbf{D}[x,\bullet]\) are independent, and if \(x\in\Pi[s]\) then the row has law \[A_{s,\bullet}\mid \mathcal{I}_s(A_{s,\bullet}).\] Conditions (LA7) and (LA6) give \(\mathbb{P}[\mathcal{I}_s(A_{s,\bullet})]\ge\phi\) and \(|\lambda[s,t]-p|\le T p/\sqrt{pN}\). For fixed \(x\in\Pi[s]\) and \(t\), the mean of \(A_{s,t}\) satisfies \[\begin{aligned} \left|\mathbb{E}A_{s,t}-p|\Pi[t]|\right| &=\left|\left(n[t]-\mathbb{1}_{s=t}\right)\lambda[s,t]-p\,n[t]\right| \le n[t]\left|\lambda[s,t]-p\right|+\lambda[s,t]\\ &\le T\sqrt{pN}+2p \le\tfrac12\sqrt{pN}(\log N)^{2/3} \end{aligned}\] for large \(N\), so Chernoff’s inequality gives \[\mathbb{P}\left[\left|A_{s,t}-p|\Pi[t]|\right|> \sqrt{pN}\,(\log N)^{2/3}\right]\le2\exp\left(-\frac{(\log N)^{4/3}}{24}\right)=N^{-\omega(1)}.\] After division by \(\mathbb{P}[\mathcal{I}_s(A_{s,\bullet})]\ge\phi\) and a union bound over the \(2^kN\) pairs \((x,t)\), estimate (R1) fails with probability \(N^{-\omega(1)}\) under \(\mathsf{R}_{\Pi,\lambda}(\cdot\mid\mathcal{I}_\Pi)\).

For fixed \(s\in\{0,1\}^k\) and \(b\in\{0,1\}\), the random variables in the family \(\left(\mathbb{1}_{\mathcal{J}_{sb}(\mathbf{D}[x,\bullet])}\right)_{x\in\Pi[s]}\) are mutually independent under \(\mathsf{R}_{\Pi,\lambda}(\cdot\mid\mathcal{I}_\Pi)\), with common mean \[\mathbb{P}[\mathcal{J}_{sb}(A_{s,\bullet})\mid\mathcal{I}_s(A_{s,\bullet})].\] Therefore \(|W_{\mathbf{D}}[sb]|\) is binomial with \(n[s]\le N\) trials and mean \(n^{\mathrm{loc}}[sb]\) by Definition 3.2, and Chernoff’s inequality gives \[\mathbb{P}\left[\left||W_{\mathbf{D}}[sb]|-n^{\mathrm{loc}}[sb]\right|>\sqrt N\log N\right]\le2\exp\left(-\frac{N\log^2N}{2(N/4+\sqrt N\log N/3)}\right)=N^{-\omega(1)},\] which is estimate (R2) with \(C_{3.9}=1\).

For fixed \(s,t\in\{0,1\}^k\) and \(b\in\{0,1\}\), put \[X_x:=\mathbf{D}[x,t]\mathbb{1}_{\mathcal{J}_{sb}(\mathbf{D}[x,\bullet])},\qquad x\in\Pi[s].\] The random variables in the family \((X_x)_{x\in\Pi[s]}\) are mutually independent under \(\mathsf{R}_{\Pi,\lambda}(\cdot\mid\mathcal{I}_\Pi)\) and have mean \[\mathbb{E}\left[A_{s,t}\mathbb{1}_{\mathcal{J}_{sb}(A_{s,\bullet})}\mid\mathcal{I}_s(A_{s,\bullet})\right]=\frac{\ell^{\mathrm{loc}}[sb,t]}{n[s]},\] where the equality is the definition of \(\ell^{\mathrm{loc}}\) in Definition 3.2. On the high-probability event (R1) already proved, every \(X_x\) is at most \(\mathbf{D}[x,t]\le p|\Pi[t]|+\sqrt{pN}(\log N)^{2/3}\le2pN\), using \(|\Pi[t]|\le N\) and taking \(N\) sufficiently large. Therefore, replacing \(X_x\) by the truncated variable \(X_x':=X_x\mathbb{1}_{X_x\le2pN}\) changes the sum \(\sum_{x\in\Pi[s]}X_x\) with probability \(N^{-\omega(1)}\) only. The truncation also changes the means, but negligibly: since \(0\le X_x\le N\), \[0\le\mathbb{E}[X_x]-\mathbb{E}[X_x']=\mathbb{E}\left[X_x\mathbb{1}_{X_x>2pN}\right]\le N\,\mathbb{P}[X_x>2pN]=N^{-\omega(1)},\] so \(\left|\sum_{x\in\Pi[s]}\mathbb{E}[X_x']-\ell^{\mathrm{loc}}[sb,t]\right|\le n[s]N^{-\omega(1)}=N^{-\omega(1)}\), which is negligible against the error term below. Hoeffding’s inequality applied to the \(n[s]\le N\) independent variables \(X_x'\in[0,2pN]\) gives \[\begin{aligned} \mathbb{P}\left[\left|\sum_{x\in\Pi[s]}X_x'-\sum_{x\in\Pi[s]}\mathbb{E}[X_x']\right|>\frac12\frac{N^2p}{\sqrt N}\log N\right] &\le2\exp\left(-\frac{2\cdot\frac14N^3p^2\log^2N}{N(2pN)^2}\right)\\ &=2\exp\left(-\frac{\log^2N}{8}\right)=N^{-\omega(1)}, \end{aligned}\] and combining the three displays, \[\left|\sum_{x\in\Pi[s]}X_x-\ell^{\mathrm{loc}}[sb,t]\right| \le\frac12\frac{N^2p}{\sqrt N}\log N+N^{-\omega(1)}\le\frac{N^2p}{\sqrt N}\log N\] with failure probability \(N^{-\omega(1)}\); this is estimate (R3) with \(C_{3.9}=1\). A union bound over the at most \(2^{2k+1}\) choices of \(s,t,b\) gives \[\label{eq:E-unconditioned} \mathsf{R}_{\Pi,\lambda}(\mathcal{E}^c\mid\mathcal{I}_\Pi)=N^{-\omega(1)}.\] By Lemma B.6, \[\label{eq:exact-total-poly} \mathsf{R}_{\Pi,\lambda}\left(m(\Pi,\mathbf{D})=m\mid\mathcal{I}_\Pi\right)\ge (N^2p)^{-C_{B.6}(\theta,k,T,\phi)}.\] By Bayes’ rule, (3.8), and (3.7), \[\begin{aligned} \mathsf{R}_{\Pi,\lambda}\left(\mathcal{E}^c\mid\mathcal{I}_\Pi,m(\Pi,\mathbf{D})=m\right) &=\frac{\mathsf{R}_{\Pi,\lambda}\left(\mathcal{E}^c\cap\{m(\Pi,\mathbf{D})=m\}\mid\mathcal{I}_\Pi\right)}{\mathsf{R}_{\Pi,\lambda}\left(m(\Pi,\mathbf{D})=m\mid\mathcal{I}_\Pi\right)}\\ &\le\frac{\mathsf{R}_{\Pi,\lambda}\left(\mathcal{E}^c\mid\mathcal{I}_\Pi\right)}{(N^2p)^{-C_{B.6}(\theta,k,T,\phi)}} \le(N^2p)^{C_{B.6}(\theta,k,T,\phi)}N^{-\omega(1)}=N^{-\omega(1)}. \end{aligned}\] Hence Proposition 3.8, applied to the event \(\mathcal{E}\), gives \[\Lambda_y^{(p)}\left(\sigma:\operatorname{deg}(\sigma)\notin\mathcal{E}\right)\le e^{-N}+C_{3.8}(\theta,k,T,\phi)N^{-\omega(1)}=o(1),\] which is the claim. ◻

Proof. Assertion (S1) is deterministic: by the definition of \(K_k\) we have \(\Pi'=\Phi_k((\Pi,\mathbf{d}))\), and \(\Phi_k((\Pi,\mathbf{d}))[sb]=W_{\mathbf{d}}[sb]\) by the definitions of \(\Phi_k\) and \(W_{\mathbf{d}}\).

We record two consequences of the hypotheses that are used repeatedly below. First, by (LA2), (LA9), and (R2), for all sufficiently large \(N\), \[\label{eq:W-sizes} \frac{\phi}{2T}N\le |W_{\mathbf{d}}[sb]|\le N\qquad\text{for all }s\in\{0,1\}^k\text{ and }b\in\{0,1\},\] since \(|W_{\mathbf{d}}[sb]|\ge n^{\mathrm{loc}}[sb]-C_{3.9}(\theta,k,T,\phi)\sqrt N\log N\ge\phi\,n[s]-C_{3.9}(\theta,k,T,\phi)\sqrt N\log N\) and \(n[s]\ge T^{-1}N\). Second, by (R1) and (LA2), for all sufficiently large \(N\), \[\label{eq:d-window} \left|\mathbf{d}[x,t]-p\,n[t]\right|\le\sqrt{pN}\,(\log N)^{2/3}\le\min_{u\in\{0,1\}^k}\left(p\,n[u]\right)^{4/7}\qquad\text{for all }x\in V\text{ and }t\in\{0,1\}^k,\] where the minimum over \(u\) is what allows the degrees on either side of a bipartite block pair \(\{s,t\}\) to be measured against the size of the other block. Finally, put \[\label{eq:T1} T_1:=\max\left\{T^{5/2},\,\frac{2T}{\phi}\right\},\] which is the value of the constant \(T\) with which Lemma C.1 and Theorem C.2 are applied below: since every block size \(n[u]\) lies in \([T^{-1}N,N]\), their hypothesis \(p\in(T_1^{-1}n^{-\theta},T_1n^{-\theta})\) holds because \(T_1\ge T^{1+\theta}\), the hypothesis \(\ell\in[T_1^{-1}n,T_1n]\) holds because \(T_1\ge T\), the edge-count hypothesis \(|m-p\ell n|\le T_1n^2p/\sqrt{pn}\) (respectively \(|m-pn(n-1)/2|\le T_1n^2p/\sqrt{pn}\)) follows from (LA3) because \(TN^2p/\sqrt{pN}\le T^{5/2}n^2p/\sqrt{pn}\) for \(n\ge T^{-1}N\) (in the internal case, where \(m=m[s,s]/2\), the additional term \(\tfrac12p\,n[s]\) from \(pn(n-1)/2\) versus \(pn^2/2\) is absorbed, since \(pn\le n^{3/2}\sqrt p\)), and the subset-size hypotheses hold by (3.9) because \(T_1\ge2T/\phi\).

We prove (S3). Suppose first that \(s\ne t\). Under \(K_k((\Pi,\mathbf{d}),\cdot)\), the bipartite graph between \(\Pi[s]\) and \(\Pi[t]\) is uniformly random among all bipartite graphs with side-degree sequences \((\mathbf{d}[x,t])_{x\in\Pi[s]}\) and \((\mathbf{d}[y,s])_{y\in\Pi[t]}\); it has exactly \(\sum_{x\in\Pi[s]}\mathbf{d}[x,t]=m(\Pi,\mathbf{d})[s,t]=m[s,t]\) edges. We apply Lemma C.1(iii) to this bipartite graph with \(\ell=n[s]\), \(n=n[t]\), \(U=W_{\mathbf{d}}[sb]\), \(U'=W_{\mathbf{d}}[tc]\), and with the constant \(T\) of that lemma equal to \(T_1\): the hypotheses on \(p\), on \(\ell\), on the edge count \(m[s,t]\), and on the subset sizes hold by the discussion following (3.11), and the degree hypotheses hold by (3.10) with \(u=t\) (the lemma measures the deviations of both degree sequences, of \((\mathbf{d}[x,t])_{x\in\Pi[s]}\) from \(p\,n[t]\) and of \((\mathbf{d}[y,s])_{y\in\Pi[t]}\) from \(p\,n[s]\), in units of \((pn)^{4/7}=(p\,n[t])^{4/7}\)). Since \(\sum_{x\in W_{\mathbf{d}}[sb]}\mathbf{d}[x,t]=L_{\mathbf{d}}[sb,t]\), \(\sum_{y\in W_{\mathbf{d}}[tc]}\mathbf{d}[y,s]=L_{\mathbf{d}}[tc,s]\), and \(m(\Pi',\mathbf{D}')[sb,tc]\) is the number of edges between \(W_{\mathbf{d}}[sb]\) and \(W_{\mathbf{d}}[tc]\), the lemma gives \[\left|m(\Pi',\mathbf{D}')[sb,tc]-\frac{L_{\mathbf{d}}[sb,t]L_{\mathbf{d}}[tc,s]}{m[s,t]}\right| \le C_1 N^2p\sqrt{\frac{(pN)^{1/7}}{N}}\log N\] with probability \(1-o(1)\), where \(C_1:=2T\): the lemma is stated with \(n=n[t]\in[T^{-1}N,N]\), and its error term \(n^2p\sqrt{(pn)^{1/7}/n}\log n\) is at most \(T^{3/7}N^2p\sqrt{(pN)^{1/7}/N}\log N\) because \(n^{-6/7}\le T^{6/7}N^{-6/7}\) (the factor \(2\) in \(C_1\) is not needed here; it is needed in the internal case with \(b=c\) below).

Now suppose \(s=t\). Under \(K_k((\Pi,\mathbf{d}),\cdot)\), the graph on \(\Pi[s]\) is uniformly random among all graphs with degree sequence \((\mathbf{d}[x,s])_{x\in\Pi[s]}\); it has exactly \(m[s,s]/2\) edges. The hypotheses of Lemma C.1(i) and (ii) are verified exactly as above, with \(n=n[s]\), \(U=W_{\mathbf{d}}[sb]\), and the constant \(T\) of the lemma equal to \(T_1\). If \(b=c\), the quantity \(m(\Pi',\mathbf{D}')[sb,sb]\) is twice the number \(X\) of edges inside \(W_{\mathbf{d}}[sb]\), and \(L_{\mathbf{d}}[sb,s]^2/m[s,s]\) is twice the centering \((\sum_{x\in W_{\mathbf{d}}[sb]}\mathbf{d}[x,s])^2/(4\cdot m[s,s]/2)\) of Lemma C.1(i), so that lemma gives \[\left|m(\Pi',\mathbf{D}')[sb,sb]-\frac{L_{\mathbf{d}}[sb,s]^2}{m[s,s]}\right| =2\left|X-\frac{\left(\sum_{x\in W_{\mathbf{d}}[sb]}\mathbf{d}[x,s]\right)^2}{4\cdot m[s,s]/2}\right| \le C_1 N^2p\sqrt{\frac{(pN)^{1/7}}{N}}\log N,\] where the factor \(2\) is absorbed by \(C_1=2T\). If \(b\ne c\), then \(W_{\mathbf{d}}[sc]=\Pi[s]\setminus W_{\mathbf{d}}[sb]\) and \(m(\Pi',\mathbf{D}')[sb,sc]\) is the number of edges between \(W_{\mathbf{d}}[sb]\) and \(W_{\mathbf{d}}[sc]\), so Lemma C.1(ii) gives \[\left|m(\Pi',\mathbf{D}')[sb,sc]-\frac{L_{\mathbf{d}}[sb,s]L_{\mathbf{d}}[sc,s]}{m[s,s]}\right| \le C_1 N^2p\sqrt{\frac{(pN)^{1/7}}{N}}\log N.\] A union bound over the at most \(2^{2k+2}\) choices of \(s,t,b,c\) proves (S3) with \(C_{3.10}:=C_1\).

It remains to prove (S2). Fix a vertex \(x\in\Pi[s]\) and a new part \(\Pi'[tc]=W_{\mathbf{d}}[tc]\). If \(t=s\), then \(\mathbf{D}'[x,tc]\) is the degree of \(x\) into the subset \(W_{\mathbf{d}}[sc]\) of \(\Pi[s]\) in the uniformly random graph on \(\Pi[s]\) with degree sequence \((\mathbf{d}[z,s])_{z\in\Pi[s]}\); if \(t\ne s\), it is the degree of \(x\) into the subset \(W_{\mathbf{d}}[tc]\) of \(\Pi[t]\) in the uniformly random bipartite graph between \(\Pi[s]\) and \(\Pi[t]\) with the side-degree sequences above. We apply Theorem C.2(i) in the first case and Theorem C.2(ii) in the second, with \(n=n[t]\) (and \(\ell=n[s]\) in the bipartite case), \(v=x\), \(S=W_{\mathbf{d}}[tc]\), and the constant \(T\) of that theorem equal to \(T_1\): the hypotheses on \(p\), on \(\ell\), on the edge count, and on the size of \(S\) hold by the discussion following (3.11), and the degree hypotheses \(|\alpha_i|,|\beta_j|\le\log n\) from (R1), because \(n[u]\ge T^{-1}N\) gives \(\sqrt{pN}\,(\log N)^{2/3}\le\sqrt{T}\sqrt{p\,n[u]}\,(\log N)^{2/3}\le\sqrt{p\,n[u]}\log n[t]\) for \(u\in\{s,t\}\) and all sufficiently large \(N\). Now the event that \(\kappa_p(\Pi',\mathbf{D}')\) fails at the entry \((x,tc)\) is the event that \(\mathbf{D}'[x,tc]=t'\) for some integer \(t'\) with \(|t'-p|W_{\mathbf{d}}[tc]||>(pN)^{4/7}\). Writing such a \(t'\) as \(t'=p|W_{\mathbf{d}}[tc]|+\tau\sqrt{p|W_{\mathbf{d}}[tc]|}\), we have \(|\tau|\ge(pN)^{4/7}/\sqrt{pN}=(pN)^{1/14}\ge\log^{100}N\) for all sufficiently large \(N\), so Theorem C.2, whose constant is \(C_{C.2}(\theta,T_1)\) here, bounds the probability of this event by \[\sum_{t'}\exp\left(-C_{C.2}(\theta,T_1)\tau^2\right)\le O(pN)\exp\left(-C_{C.2}(\theta,T_1)(pN)^{1/7}\right)=N^{-\omega(1)}\] for each fixed \(x\) and \(tc\). A union bound over all \(x\in V\) and the \(2^{k+1}\) choices of \(tc\) gives (S2) with probability \(1-o(1)\). ◻

Proof. For \(k=1\) the cone \(\mathcal{C}_s\) is all of \(\mathbb{R}^{\{0,1\}}\), the conditioning is on a sure event, and \(F_{s,\nu}\) is the identity, which is a strong bijection. Let \(k\ge2\), and let \(M_s\in\mathbb{R}^{(k-1)\times2^k}\) be the matrix whose \(r\)th row is the coefficient vector \(\mu_r\) of \(Z_{s,r}\), that is, \(\mu_r[t]=(-1)^{s[r]}(-1)^{t[r-1]}\). Then \(\mathcal{C}_s=\{x:M_sx>0\}\). The rows are nonzero, and they are pairwise orthogonal: for \(r\ne r'\), flipping bit \(r-1\) of \(t\) is a bijection of \(\{0,1\}^k\) that changes the sign of \(\mu_r[t]\mu_{r'}[t]\), so \(\sum_t\mu_r[t]\mu_{r'}[t]=0\). Hence \(M_s\) has rank \(k-1\), and Corollary D.4 with \(d=2^k\), \(M=M_s\), and \(\Sigma=\operatorname{diag}(\nu)\), which is positive definite, shows that \(F_{s,\nu}=F_{\mathcal{C}_s}\) is a strong bijection onto \(\mathcal{C}_s\). ◻

Proof. We prove by induction on \(k\) that the day-\(k\) quantities are defined and satisfy (i)–(iii). For \(k=1\), \(\nu[0]=\nu[1]=1/2\) are positive and sum to \(1\), \(\mu\equiv0\) is symmetric, and (iii) is vacuous because \(\mathcal{C}_s=\mathbb{R}^{\{0,1\}}\); also \(\gamma=0=F_{s,\nu}^{-1}(0)\), since \(F_{s,\nu}\) is the identity for \(k=1\).

Suppose the claims hold for some \(k\ge1\). By (iii), condition (4.1) holds, so \(\gamma[s,\bullet]\) is defined through Proposition 4.2, the day-\(k\) Gaussian row model is defined, and (4.2) holds. All conditional expectations in (4.3) and (4.4) are defined because \(\mathbb{P}[\mathcal{J}_{sb}(W_{s,\bullet})]>0\), as noted after Definition 4.1. We verify the three claims on \(\{0,1\}^{k+1}\).

(i): \(\nu[sb]>0\) because \(\mathbb{P}[\mathcal{J}_{sb}(W_{s,\bullet})\mid\mathcal{I}_s(W_{s,\bullet})]>0\). For a vector \(x\) satisfying \(\mathcal{I}_s(x)\), exactly one of \(\mathcal{J}_{s0}(x)\) and \(\mathcal{J}_{s1}(x)\) holds, since the two differ only in the \(k\)th inequality, which is \(\ge_{s[k-1]0}\) in one and \(\ge_{s[k-1]1}\) in the other, and these two relations are complementary. Hence \[\nu[s0]+\nu[s1]=\nu[s]\left(\mathbb{P}[\mathcal{J}_{s0}(W_{s,\bullet})\mid\mathcal{I}_s(W_{s,\bullet})]+\mathbb{P}[\mathcal{J}_{s1}(W_{s,\bullet})\mid\mathcal{I}_s(W_{s,\bullet})]\right)=\nu[s],\] and summing over \(s\) gives \(\sum_{u\in\{0,1\}^{k+1}}\nu[u]=\sum_{s\in\{0,1\}^k}\nu[s]=1\).

(ii): the right-hand side of (4.4) is invariant under exchanging \((s,b)\) with \((t,c)\), because \(\mu[s,t]=\mu[t,s]\) by the induction hypothesis.

(iii): fix \(s\in\{0,1\}^k\) and \(b\in\{0,1\}\), and let \(x\in\mathbb{R}^{\{0,1\}^{k+1}}\) be the vector \(x[u]:=\nu[u]\mu[sb,u]\). For \(t\in\{0,1\}^k\), (4.4) gives \[\begin{aligned} x[t0]+x[t1]&=\frac{\nu[t0]+\nu[t1]}{\nu[t]}\,\mathbb{E}\left[W_{s,t}\mid\mathcal{J}_{sb}(W_{s,\bullet})\right]\\ &\quad+\frac{1}{\nu[s]}\sum_{c\in\{0,1\}}\nu[tc]\,\mathbb{E}\left[W_{t,s}\mid\mathcal{J}_{tc}(W_{t,\bullet})\right]-\left(\nu[t0]+\nu[t1]\right)\mu[s,t]. \end{aligned}\] The first coefficient is \(1\) by (i). In the second term, \(\nu[tc]=\nu[t]\,\mathbb{P}[\mathcal{J}_{tc}(W_{t,\bullet})\mid\mathcal{I}_t(W_{t,\bullet})]\) by (4.3), and since \(\mathcal{J}_{t0}\) and \(\mathcal{J}_{t1}\) partition \(\mathcal{I}_t\), the law of total expectation gives \(\sum_c\mathbb{P}[\mathcal{J}_{tc}\mid\mathcal{I}_t]\,\mathbb{E}[W_{t,s}\mid\mathcal{J}_{tc}]=\mathbb{E}[W_{t,s}\mid\mathcal{I}_t(W_{t,\bullet})]=\nu[s]\mu[t,s]\) by (4.2); so the second term equals \(\nu[t]\mu[t,s]\). The third term is \(-\nu[t]\mu[s,t]\). By (ii) the last two cancel, and \[\label{eq:children-sum} x[t0]+x[t1]=\mathbb{E}\left[W_{s,t}\mid\mathcal{J}_{sb}(W_{s,\bullet})\right]\qquad(t\in\{0,1\}^k).\] Now let \(1\le r\le k\). For \(u=tc\in\{0,1\}^{k+1}\) we have \(u[r-1]=t[r-1]\), and \((sb)[r]=s[r]\) for \(r\le k-1\) while \((sb)[k]=b\). Hence, by (4.5), \[Z_{sb,r}(x)=(-1)^{(sb)[r]}\sum_{t}(-1)^{t[r-1]}\left(x[t0]+x[t1]\right) =\begin{cases} \mathbb{E}\left[Z_{s,r}(W_{s,\bullet})\mid\mathcal{J}_{sb}\right]&\text{if }1\le r\le k-1,\\[2pt] (-1)^b\,\mathbb{E}\left[Z_{s,k}(W_{s,\bullet})\mid\mathcal{J}_{sb}\right]&\text{if }r=k, \end{cases}\] where \(\mathcal{J}_{sb}\) abbreviates \(\mathcal{J}_{sb}(W_{s,\bullet})\). Conditioning on \(\mathcal{J}_{sb}(W_{s,\bullet})\) is conditioning on the nonempty open convex set \(\mathcal{C}_s\cap\{(-1)^bZ_{s,k}>0\}\), on which the linear forms \(Z_{s,r}\) (\(r\le k-1\)) and \((-1)^bZ_{s,k}\) are positive; by Lemma A.12 the conditional mean of \(W_{s,\bullet}\) lies in this set, so all the displayed quantities are positive. Thus \(x\in\mathcal{C}_{sb}\), which is (4.1) on \(\{0,1\}^{k+1}\). ◻

Proof. Let \(R\colon\mathbb{R}^{\{0,1\}^k}\to\mathbb{R}^{\{0,1\}^k}\) be the reflection \((Rx)[t]:=x[\overline{t}]\), an involution. Substituting \(u=\overline{t}\) and using \((-1)^{\overline{t}[i]}=-(-1)^{t[i]}\), \[\begin{aligned} Z_{\overline{s},r}(Rx)&=(-1)^{1-s[r]}\sum_{u}(-1)^{1-u[r-1]}x[u]=Z_{s,r}(x)\qquad(1\le r\le k-1),\\ Z_{\overline{s},k}(Rx)&=\sum_u(-1)^{1-u[k-1]}x[u]=-Z_{s,k}(x). \end{aligned}\] Consequently \(R\mathcal{C}_s=\mathcal{C}_{\overline{s}}\), and \(R\) maps \(\mathcal{C}_s\cap\{(-1)^bZ_{s,k}>0\}\) onto \(\mathcal{C}_{\overline{s}}\cap\{(-1)^{\overline{b}}Z_{\overline{s},k}>0\}\); in words, \(R\) carries the strict forms of \(\mathcal{I}_s\) and \(\mathcal{J}_{sb}\) to those of \(\mathcal{I}_{\overline{s}}\) and \(\mathcal{J}_{\overline{s}\,\overline{b}}\).

We prove the three identities by induction on \(k\); for \(k=1\) they hold because \(\nu[0]=\nu[1]\) and \(\gamma=\mu=0\). Suppose they hold on \(\{0,1\}^k\). If \(W\) has independent coordinates \(W[t]\sim\mathcal{N}(\gamma[t],\nu[t])\) and \(\nu[\overline{t}]=\nu[t]\), then \(RW\) has independent coordinates \((RW)[t]=W[\overline{t}]\sim\mathcal{N}((R\gamma)[t],\nu[t])\); therefore \[F_{\overline{s},\nu}(R\gamma)=\mathbb{E}\left[RW\mid RW\in\mathcal{C}_{\overline{s}}\right]=R\,\mathbb{E}\left[W\mid W\in\mathcal{C}_s\right]=R\,F_{s,\nu}(\gamma),\] that is, \(F_{\overline{s},\nu}\circ R=R\circ F_{s,\nu}\), and hence \(F_{\overline{s},\nu}^{-1}\circ R=R\circ F_{s,\nu}^{-1}\). The vector \(v_s:=(\nu[t]\mu[s,t])_t\) satisfies \(v_{\overline{s}}[t]=\nu[t]\mu[\overline{s},t]=\nu[\overline{t}]\mu[s,\overline{t}]=v_s[\overline{t}]\) by the induction hypothesis (applied to the pair \((\overline{s},t)\)), so \(v_{\overline{s}}=Rv_s\), and therefore \(\gamma[\overline{s},\bullet]=F^{-1}_{\overline{s},\nu}(Rv_s)=R\,\gamma[s,\bullet]\), which is \(\gamma[\overline{s},\overline{t}]=\gamma[s,t]\). It follows that the day-\(k\) Gaussian row model satisfies \(W_{\overline{s},\bullet}\overset{d}{=}RW_{s,\bullet}\), and by the first paragraph the events \(\mathcal{I}_{\overline{s}}(W_{\overline{s},\bullet})\) and \(\mathcal{J}_{\overline{s}\,\overline{b}}(W_{\overline{s},\bullet})\) correspond, up to null sets, to \(\mathcal{I}_s(W_{s,\bullet})\) and \(\mathcal{J}_{sb}(W_{s,\bullet})\) under this identification. Hence \[\mathbb{P}\left[\mathcal{J}_{\overline{s}\,\overline{b}}(W_{\overline{s},\bullet})\mid\mathcal{I}_{\overline{s}}(W_{\overline{s},\bullet})\right]=\mathbb{P}\left[\mathcal{J}_{sb}(W_{s,\bullet})\mid\mathcal{I}_s(W_{s,\bullet})\right],\qquad \mathbb{E}\left[W_{\overline{s},\overline{t}}\mid\mathcal{J}_{\overline{s}\,\overline{b}}(W_{\overline{s},\bullet})\right]=\mathbb{E}\left[W_{s,t}\mid\mathcal{J}_{sb}(W_{s,\bullet})\right],\] and (4.3), (4.4) give \(\nu[\overline{s}\,\overline{b}]=\nu[sb]\) and \(\mu[\overline{s}\,\overline{b},\overline{t}\,\overline{c}]=\mu[sb,tc]\), completing the induction. Finally, for \(1\le r\le k\), pairing \(t\) with \(\overline{t}\) in \(\sum_t(-1)^{t[r-1]}\nu[t]\) shows that the sum equals its own negative, hence vanishes. ◻

Proof. Conditioning on \(\mathcal{I}_s(W_{s,\bullet})\) is conditioning on the nonempty open convex set \(\mathcal{C}_s\), and \(W_{s,\bullet}\) is Gaussian with the positive definite covariance \(\operatorname{diag}(\nu)\). Lemma A.12 applies. ◻

Proof. (i): by (4.7), (4.3), and Lemma 4.4(i), \[\varepsilon[s0]+\varepsilon[s1]=\nu[s]\sum_{b\in\{0,1\}}\mathbb{P}\left[\mathcal{J}_{sb}(W_{s,\bullet})\mid\mathcal{I}_s(W_{s,\bullet})\right]\mathbb{E}\left[B_s\mid\mathcal{J}_{sb}(W_{s,\bullet})\right]-\nu[s]\,\mathbb{E}\left[B_s\mid\mathcal{I}_s(W_{s,\bullet})\right]=0,\] because \(\mathcal{J}_{s0}\) and \(\mathcal{J}_{s1}\) partition \(\mathcal{I}_s\) and the law of total expectation applies.

(ii): we prove \(\varepsilon[\overline{s}]=-\varepsilon[s]\) by induction on \(k\), deriving the identity for \(\beta\) along the way. For \(k=1\) it is \(\varepsilon[1]=-\varepsilon[0]\). Suppose \(\varepsilon[\overline{t}]=-\varepsilon[t]\) for all \(t\in\{0,1\}^k\). With \(R\) the reflection of the proof of Lemma 4.5, that proof gives \(W_{\overline{s},\bullet}\overset{d}{=}RW_{s,\bullet}\) with corresponding conditioning events, hence \[\Sigma_{\overline{s}}[\overline{t},\overline{t}']=\mathrm{Cov}\left(W_{\overline{s},\overline{t}},W_{\overline{s},\overline{t}'}\mid\mathcal{I}_{\overline{s}}\right)=\mathrm{Cov}\left(W_{s,t},W_{s,t'}\mid\mathcal{I}_s\right)=\Sigma_s[t,t'].\] Define \(\beta'[t]:=-\beta[s,\overline{t}]\). Then for every \(t\), \[\sum_{t'}\beta'[t']\,\Sigma_{\overline{s}}[t',t]=-\sum_{t'}\beta[s,\overline{t}']\,\Sigma_s[\overline{t}',\overline{t}]=-\sum_{u}\beta[s,u]\,\Sigma_s[u,\overline{t}]=-\varepsilon[\overline{t}]=\varepsilon[t],\] by (4.6) for \(s\) and the induction hypothesis. So \(\beta'\) solves (4.6) for \(\overline{s}\), and by uniqueness \(\beta[\overline{s},t]=-\beta[s,\overline{t}]\) for all \(t\), that is, \(\beta[\overline{s},\overline{t}]=-\beta[s,t]\). Consequently, under the identification \(W_{\overline{s},\bullet}=RW_{s,\bullet}\), \[B_{\overline{s}}=\sum_t\beta[\overline{s},t]\,W_{s,\overline{t}}=\sum_u\beta[\overline{s},\overline{u}]\,W_{s,u}=-B_s,\] and since the conditioning events correspond, (4.7) together with \(\nu[\overline{s}\,\overline{b}]=\nu[sb]\) gives \(\varepsilon[\overline{s}\,\overline{b}]=-\varepsilon[sb]\). ◻

Proof. By Lemma 4.8(i) it suffices to prove \(\varepsilon[s0]>0\). We proceed by induction on \(k\), using at day \(k\) the following consequence of the statement for smaller \(k\): \[\label{eq:lead-sum-positive} S_k:=\sum_{t\in\{0,1\}^k}(-1)^{t[k-1]}\varepsilon[t]>0 .\] For \(k=1\), \(S_1=\varepsilon[0]-\varepsilon[1]=2\) by definition; for \(k\ge2\), grouping \(t=t'b\) with \(t'\in\{0,1\}^{k-1}\) gives \(S_k=\sum_{t'}(\varepsilon[t'0]-\varepsilon[t'1])=2\sum_{t'}\varepsilon[t'0]\) by Lemma 4.8(i), which is positive by the statement for \(k-1\). We also use \[\label{eq:history-sum-zero} \sum_{t\in\{0,1\}^k}(-1)^{t[r-1]}\varepsilon[t]=0\qquad(1\le r\le k-1),\] which holds because for \(r\le k-1\) the bit \(t[r-1]\) depends only on \(t'\) when \(t=t'b\), so the sum is \(\sum_{t'}(-1)^{t'[r-1]}(\varepsilon[t'0]+\varepsilon[t'1])=0\).

Fix \(k\ge1\) and \(s\in\{0,1\}^k\), let \(W:=W_{s,\bullet}\) be the day-\(k\) Gaussian row model, and write \(Z_r:=Z_{s,r}(W)\) for \(1\le r\le k\). Up to null sets, \(\mathcal{I}_s(W)\) is the event \(E:=\{Z_1>0,\ldots,Z_{k-1}>0\}\) and \(\mathcal{J}_{s0}(W)\) is \(E\cap\{Z_k>0\}\). Let \(\mathcal{G}\) be the linear span of the centered variables \(W_t-\mathbb{E}W_t\), \(t\in\{0,1\}^k\), a finite-dimensional space of centered jointly Gaussian random variables, with the inner product \(\langle X,Y\rangle:=\mathbb{E}[XY]=\mathrm{Cov}(X,Y)\); in \(\mathcal{G}\), orthogonal families are independent. The centered variables \(\overline{Z}_r:=Z_r-\mathbb{E}Z_r\) and \(\overline{B}:=B_s-\mathbb{E}B_s\) lie in \(\mathcal{G}\). The \(\overline{Z}_r\), \(1\le r\le k\), are linearly independent: their coefficient vectors are nonzero and pairwise orthogonal in \(\mathbb{R}^{\{0,1\}^k}\) (see the proof of Proposition 4.2), and \(a\mapsto\sum_ta[t](W_t-\mathbb{E}W_t)\) is injective because its image has variance \(\sum_ta[t]^2\nu[t]>0\) for \(a\ne0\).

Step 1: the covariances of \(B_s\) with the constraints. By (4.6), \(\mathrm{Cov}(B_s,W_t\mid E)=\varepsilon[t]\) for every \(t\), so by linearity \[\begin{aligned} \mathrm{Cov}(B_s,Z_r\mid E)&=(-1)^{s[r]}\sum_t(-1)^{t[r-1]}\varepsilon[t]=0\qquad(1\le r\le k-1),\\ \mathrm{Cov}(B_s,Z_k\mid E)&=\sum_t(-1)^{t[k-1]}\varepsilon[t]=S_k>0, \end{aligned}\] by (4.9) and (4.8).

Step 2: \(B_s\) is independent of the history constraints. Decompose \(\overline{B}=\sum_{r<k}\alpha_r\overline{Z}_r+X\) with \(X\in\mathcal{G}\) orthogonal to \(\overline{Z}_1,\ldots,\overline{Z}_{k-1}\) (orthogonal projection). Then \(X\) is independent of \((Z_r)_{r<k}\), and since \(E\) is an event of \((Z_r)_{r<k}\), under the law conditioned on \(E\) the variable \(X\) is still independent of \((Z_r)_{r<k}\); hence \(\mathrm{Cov}(X,Z_r\mid E)=0\) for \(r<k\), and Step 1 gives \[0=\mathrm{Cov}(B_s,Z_r\mid E)=\sum_{r'<k}\alpha_{r'}\mathrm{Cov}(Z_{r'},Z_r\mid E)\qquad(1\le r\le k-1).\] The matrix \((\mathrm{Cov}(Z_{r'},Z_r\mid E))_{r',r<k}\) is the covariance of the nondegenerate Gaussian vector \((Z_r)_{r<k}\in\mathbb{R}^{k-1}\) conditioned on the open orthant \(E\), hence positive definite by Lemma A.12. Therefore \(\alpha_r=0\) for all \(r\), and \(\overline{B}=X\): the centered variable \(B_s-\mathbb{E}B_s\) is independent of \((Z_r)_{r<k}\). (For \(k=1\) there is nothing to prove in this step.)

Step 3: the component of \(Z_k\) orthogonal to the constraints. Decompose \(\overline{Z}_k=\sum_{r<k}\delta_r\overline{Z}_r+Y\) with \(Y\in\mathcal{G}\) orthogonal to \(\overline{Z}_1,\ldots,\overline{Z}_{k-1}\). By linear independence \(Y\ne0\), so \(\mathrm{Var}(Y)>0\). The pair \((X,Y)\) is independent of \((Z_r)_{r<k}\), so conditioning on \(E\) does not change its joint law, and using Step 2, \[S_k=\mathrm{Cov}(B_s,Z_k\mid E)=\mathrm{Cov}\Big(X,\sum_{r<k}\delta_rZ_r+Y\ \Big|\ E\Big)=\mathrm{Cov}(X,Y).\] Write \(X=\alpha Y+X'\) with \(\alpha:=\mathrm{Cov}(X,Y)/\mathrm{Var}(Y)=S_k/\mathrm{Var}(Y)>0\) and \(X'\in\mathcal{G}\) orthogonal to \(Y\); then \(X'\) is orthogonal to \(Y\) and to all \(\overline{Z}_r\), \(r<k\), hence independent of \((Y,(Z_r)_{r<k})\).

Step 4: the conditional means. Since \(B_s=\mathbb{E}B_s+X\) and \(X\) is independent of \(E\) with mean \(0\), we have \(\mathbb{E}[B_s\mid E]=\mathbb{E}B_s\), and (4.7) reads \[\varepsilon[s0]=\nu[s0]\,\mathbb{E}\left[X\mid E\cap\{Z_k>0\}\right].\] Put \(U:=-\mathbb{E}Z_k-\sum_{r<k}\delta_r\overline{Z}_r\), a function of \((Z_r)_{r<k}\), so that \(\{Z_k>0\}=\{Y>U\}\). The variable \(X'\) is centered and independent of \((Y,U,\mathbf{1}_E)\), so \(\mathbb{E}[X'\mid E\cap\{Y>U\}]=0\) and \[\mathbb{E}\left[X\mid E\cap\{Z_k>0\}\right]=\alpha\,\mathbb{E}\left[Y\mid E\cap\{Y>U\}\right]=\alpha\,\frac{\mathbb{E}\left[\mathbf{1}_E\,\phi(U)\right]}{\mathbb{P}\left[E\cap\{Y>U\}\right]},\qquad\phi(u):=\mathbb{E}\left[Y\mathbf{1}_{Y>u}\right],\] where we conditioned on \((Z_r)_{r<k}\) and used that \(Y\) is independent of \((U,\mathbf{1}_E)\). For a centered Gaussian \(Y\) with positive variance, \(\phi(u)>0\) for every \(u\in\mathbb{R}\): if \(u\ge0\) then \(Y\mathbf{1}_{Y>u}\ge0\) with positive probability of being positive, and if \(u<0\) then \(\phi(u)=\mathbb{E}Y-\mathbb{E}[Y\mathbf{1}_{Y\le u}]=-\mathbb{E}[Y\mathbf{1}_{Y\le u}]>0\). Since \(\mathbb{P}[E]>0\), we get \(\mathbb{E}[\mathbf{1}_E\phi(U)]>0\), hence \(\mathbb{E}[X\mid E\cap\{Z_k>0\}]>0\), and \(\varepsilon[s0]>0\) because \(\nu[s0]>0\) by Lemma 4.4(i). ◻

Proof. (i): for \(k\ge2\) and \(1\le r\le k-1\), write \(t=t'b\) with \(t'\in\{0,1\}^{k-1}\); the bit \(t[r-1]=t'[r-1]\) does not depend on \(b\), so the sum is \(\sum_{t'}(-1)^{t'[r-1]}(\varepsilon[t'0]+\varepsilon[t'1])=0\) by Lemma 4.8(i). The same grouping without the sign gives \(\sum_t\varepsilon[t]=0\) for \(k\ge2\), and for \(k=1\) it is \(\varepsilon[0]+\varepsilon[1]=0\). (ii): for \(k\ge2\), \((-1)^{t[k-1]}=(-1)^b\) when \(t=t'b\), so the sum is \(\sum_{t'}(\varepsilon[t'0]-\varepsilon[t'1])=2\sum_{t'}\varepsilon[t'0]\) by Lemma 4.8(i), which is positive by Theorem 4.9; for \(k=1\) the sum is \(\varepsilon[0]-\varepsilon[1]=2\). (iii) is the last assertion of Lemma 4.5, and (iv) is Lemma 4.4(iii). ◻

Proof. There are finitely many quantities involved: \(2^k\) probabilities \(\mathbb{P}[\mathcal{I}_s(W_{s,\bullet})]\), \(2^{k+1}\) conditional probabilities \(\mathbb{P}[\mathcal{J}_{sb}(W_{s,\bullet})\mid\mathcal{I}_s(W_{s,\bullet})]\), and \(2^k(k-1)\) numbers \(Z_{s,r}((\nu[t]\mu[s,t])_t)\). Each \(\mathbb{P}[\mathcal{I}_s(W_{s,\bullet})]\) is positive, as noted after Definition 4.1. Each \(\mathbb{P}[\mathcal{J}_{sb}\mid\mathcal{I}_s]\) is positive for the same reason, and is less than \(1\) because \(\mathbb{P}[\mathcal{J}_{s0}\mid\mathcal{I}_s]+\mathbb{P}[\mathcal{J}_{s1}\mid\mathcal{I}_s]=1\) (proof of Lemma 4.4) with both terms positive. Each \(Z_{s,r}((\nu[t]\mu[s,t])_t)\) is positive by Corollary 4.10(iv). Let \(\phi^\ast_k\) be one half of the minimum of all the probabilities \(\mathbb{P}[\mathcal{I}_s]\), \(\mathbb{P}[\mathcal{J}_{sb}\mid\mathcal{I}_s]\), and \(1-\mathbb{P}[\mathcal{J}_{sb}\mid\mathcal{I}_s]\), so that \(\phi^\ast_k\in(0,1/4]\) and the first two displayed inequalities hold; and let \(\varsigma^\ast_k\) be the minimum of the numbers \(Z_{s,r}((\nu[t]\mu[s,t])_t)\) when \(k\ge2\), and \(\varsigma^\ast_1:=1\). ◻

Proof. Let \(y'\in\mathcal{L}^{(p)}_{k+1}(y,\lambda_y)\), and write \(\Pi':=\operatorname{part}(y')\), \(m':=\operatorname{edge}(y')\); by (L2), \(y'=(\Pi',m',1)\). Write \(C:=C_{3.3}(\theta,k,T_1,\phi_1)\) and let \((n^{\mathrm{loc}},\ell^{\mathrm{loc}},m^{\mathrm{loc}})\) be the local template of \((y,\lambda_y)\). For (F1) at day \(k+1\), the triangle inequality, (L3), and Theorem 5.4(c) give, for all \(s\in\{0,1\}^k\) and \(b\in\{0,1\}\), \[\left||\Pi'[sb]|-\widetilde n[sb]-\tau\sqrt N\sqrt{pN}^{\,k}\varepsilon[sb]\right|\le C\sqrt N\log N+T_1\sqrt N\sqrt{pN}^{\,k}N^{-\delta_1}.\] Since \(\delta_2\le\delta_1\), the second term is at most \(T_1\sqrt N\sqrt{pN}^kN^{-\delta_2}\). For the first, because \(k\ge1\) and \(\delta_2\le(1-\theta)/8\), \[\sqrt{pN}^{\,k}N^{-\delta_2}\ge(pN)^{1/2}N^{-\delta_2}\ge T^{-1/2}N^{(1-\theta)/2-\delta_2}\ge T^{-1/2}N^{3(1-\theta)/8},\] so \(C\log N\le T_1\sqrt{pN}^kN^{-\delta_2}\) for large \(N\). Hence the left-hand side is at most \(2T_1\sqrt N\sqrt{pN}^kN^{-\delta_2}=T_2\sqrt N\sqrt{pN}^kN^{-\delta_2}\). For (F2) at day \(k+1\), similarly, by (L4) and Theorem 5.4(c), \[\begin{gathered} \left|m'[sb,tc]-\widetilde m[sb,tc]\left(1+\tau\frac{\sqrt{pN}^{\,k}}{\sqrt N}\left(\frac{\varepsilon[sb]}{\nu[sb]}+\frac{\varepsilon[tc]}{\nu[tc]}\right)\right)\right|\\ \le CN^2p\sqrt{\frac{(pN)^{1/7}}{N}}\log N+T_1\frac{\sqrt{pN}^{\,k}}{\sqrt N}N^{-\delta_1}N^2p . \end{gathered}\] The first term is at most \(T_1\frac{\sqrt{pN}^k}{\sqrt N}N^{-\delta_2}N^2p\) as soon as \(C(pN)^{1/14}\log N\le T_1\sqrt{pN}^kN^{-\delta_2}\), and \(\sqrt{pN}^k/(pN)^{1/14}\ge(pN)^{3/7}\ge T^{-3/7}N^{3(1-\theta)/7}\), while \(\delta_2\le(1-\theta)/8<3(1-\theta)/7\); so this holds for large \(N\). Both conditions of Definition 5.3 therefore hold with the constants \((T_2,\delta_2)\), and \(y'\in\mathcal{G}^{(p)}_{k+1}(T_2,\delta_2,\tau)\). ◻

Proof. Write \(\Pi:=\Pi_1(\mathfrak g)\), \(\mathbf d:=\delta(\Pi,G)\), \(n[s]:=|\Pi[s]|\), and \(y:=\rho_1^{(p)}(\sigma_1(\mathfrak g))=(\Pi,m,\mathbb{1}_{\kappa_p(\Pi,\mathbf d)})\) with \(m[s,t]=\sum_{x\in\Pi[s]}\mathbf d[x,t]\). By definition, \(\Pi[0]=c^{-1}(1)\) and \(\Pi[1]=c^{-1}(-1)\), so \(n[0]=a:=\lfloor N/2\rfloor+\lfloor\tau\sqrt N\rfloor\) and \(n[1]=N-a\). At day \(1\) we have \(\widetilde n[0]=\widetilde n[1]=\lfloor N/2\rfloor\), \(\widetilde m[s,t]=p\widetilde n[s](\widetilde n[t]-\mathbb{1}_{s=t})\), \(\nu[0]=\nu[1]=\frac12\), and \(\varepsilon[0]=1=-\varepsilon[1]\), so \(\varepsilon[s]/\nu[s]=2(-1)^s\) for \(s\in\{0,1\}\).

Sizes. Deterministically, \(|n[0]-\widetilde n[0]-\tau\sqrt N|=|\lfloor\tau\sqrt N\rfloor-\tau\sqrt N|<1\) and \(|n[1]-\widetilde n[1]+\tau\sqrt N|=|N-2\lfloor N/2\rfloor-\lfloor\tau\sqrt N\rfloor+\tau\sqrt N|<2\), while the tolerance in (F1) is \(\sqrt NN^{-\delta_0}\ge2\) for large \(N\).

Edge counts. For \(s\ne t\), \(m[s,t]\) is the number of edges of \(G\) between \(\Pi[s]\) and \(\Pi[t]\), a \(\mathrm{Bin}(n[s]n[t],p)\) variable; and \(m[s,s]\) is twice the number of edges inside \(\Pi[s]\), twice a \(\mathrm{Bin}(\binom{n[s]}{2},p)\) variable. In both cases \(\mathbb E\,m[s,t]=pn[s](n[t]-\mathbb{1}_{s=t})\) and \(\mathrm{Var}\,m[s,t]\le2N^2p\), so by Chernoff’s inequality, with probability \(1-o(1)\), \[\label{eq:day-one-chernoff} \left|m[s,t]-pn[s]\left(n[t]-\mathbb{1}_{s=t}\right)\right|\le2N\sqrt p\log N\qquad\text{for all }s,t\in\{0,1\}.\] Next, \(n[s]=\widetilde n[0]+(-1)^s\lfloor\tau\sqrt N\rfloor+\mathbb{1}_{s=1}(N-2\lfloor N/2\rfloor)\), and since \(\lfloor\tau\sqrt N\rfloor/\widetilde n[0]=2\tau/\sqrt N+O(1/N)\) (recall \(\tau\le T\)), both \(n[s]\) and \(n[s]-1\) equal \((\widetilde n[0]-\mathbb{1})\big(1+(-1)^s\frac{2\tau}{\sqrt N}+O(\frac1N)\big)\) with the corresponding \(\mathbb{1}\in\{0,1\}\). Hence \[\begin{aligned} pn[s]\left(n[t]-\mathbb{1}_{s=t}\right)&=\widetilde m[s,t]\left(1+\frac{2\tau}{\sqrt N}\left((-1)^s+(-1)^t\right)+O\left(\frac1N\right)\right)\\ &=\widetilde m[s,t]\left(1+\frac{\tau}{\sqrt N}\left(\frac{\varepsilon[s]}{\nu[s]}+\frac{\varepsilon[t]}{\nu[t]}\right)\right)+O(Np), \end{aligned}\] the cross term \(4\tau^2/N\) being part of the \(O(1/N)\). Combining with (5.1), the left-hand side of (F2) is at most \(2N\sqrt p\log N+O(Np)\le3N\sqrt p\log N\), while the tolerance is \(N^{-\delta_0}N^{3/2}p\). Since \(\sqrt p\ge T^{-1/2}N^{-\theta/2}\), the ratio of the tolerance to \(N\sqrt p\log N\) is at least \(T^{-1/2}N^{(1-\theta)/2-\delta_0}/\log N=T^{-1/2}N^{(1-\theta)/4}/\log N\), which tends to infinity; so (F2) holds for large \(N\) on the event (5.1).

Regularity. For \(x\in V\) and \(t\in\{0,1\}\), \(\mathbf d[x,t]=\deg^G_{\Pi[t]}x\sim\mathrm{Bin}(n[t]-\mathbb{1}_{x\in\Pi[t]},p)\), whose mean differs from \(pn[t]\) by at most \(p\). By Chernoff’s inequality, \(\mathbb P[|\mathbf d[x,t]-pn[t]|>(pN)^{4/7}]\le2\exp(-c(pN)^{1/7})\) for an absolute constant \(c>0\) and large \(N\), and a union bound over the \(2N\) pairs \((x,t)\) gives \(\mathbb P[\neg\kappa_p(\Pi,\mathbf d)]\le4N\exp(-c(pN)^{1/7})=o(1)\), since \((pN)^{1/7}\ge T^{-1/7}N^{(1-\theta)/7}\). On the intersection of the two events, \(y=(\Pi,m,1)\in\mathcal G^{(p)}_1(1,\delta_0,\tau)\). ◻

Proof. Write \(y_j:=\rho_j^{(p)}(\sigma_j(\mathfrak g))\) for the day-\(j\) coarse state of \(\mathfrak g\), and \(\mathcal G_j(T',\delta'):=\mathcal G^{(p)}_j(T',\delta',\tau)\). Note that \(\mathcal G_j(T',\delta')\subseteq\mathcal G_j(T'',\delta'')\) whenever \(T'\le T''\) and \(\delta'\ge\delta''\), since the tolerances in Definition 5.3 increase.

Constants. Define \((T^\circ_j,\delta^\circ_j)\) for \(1\le j\le K_\theta\) recursively: \(T^\circ_1:=T\) and \(\delta^\circ_1:=\frac{1-\theta}{4}\); and for \(1\le j<K_\theta\) (so that \(j<\frac1{1-\theta}\)), let \((T_2,\delta_2)\) be the constants of Proposition 5.6 for the parameters \((\theta,j,T^\circ_j,\delta^\circ_j)\), and put \(T^\circ_{j+1}:=\max\{T_2,T^\circ_j\}\) and \(\delta^\circ_{j+1}:=\delta_2\). These depend only on \(\theta\) and \(T\); \(T^\circ_j\) is nondecreasing in \(j\), and \(\delta^\circ_j\) is nonincreasing because \(\delta_2\le\delta_1<\delta\) in Proposition 5.6 and Theorem 5.4. Set \(T^\ast:=T^\circ_{K_\theta}\ge T\) and \(\delta^\ast:=\delta^\circ_{K_\theta}\); then \(\mathcal G_j(T^\circ_j,\delta^\circ_j)\subseteq\mathcal G_j(T^\ast,\delta^\ast)\) for every \(j\le K_\theta\).

Induction. We show by induction on \(j\) that \(\mathbb P[y_j\in\mathcal G_j(T^\circ_j,\delta^\circ_j)]=1-o(1)\) for \(1\le j\le K_\theta\). For \(j=1\) this is Proposition 5.7, since \(1\le T^\circ_1\). Let \(1\le j<K_\theta\) and suppose the claim holds for \(j\). Fix \(y\in\mathcal G_j(T^\circ_j,\delta^\circ_j)\) with \(\mathbb P[y_j=y]>0\). By Proposition 2.4, \(y\) is \(p\)-attainable and \(\mathbb P[y_{j+1}\in B\mid y_j=y]=\overline K^{(p)}_j(y,B)\) for every \(B\subseteq\mathcal Y_{j+1}(V)\). Since \(T^\circ_j\ge T\), the ranges \(p\in(T^{-1}N^{-\theta},TN^{-\theta})\) and \(\tau\in[T^{-1},T]\) are contained in those of Theorem 5.4 with the parameters \((\theta,j,T^\circ_j,\delta^\circ_j)\), and that theorem provides the tilt \(\lambda_y\) and constants \(T_1,\phi_1\), depending only on \(\theta,T\), such that \((y,\lambda_y)\) is \((T_1,\phi_1,p)\)-locally admissible. Since \(T_1\ge T^\circ_j\ge T\), the range of \(p\) is also contained in that of Theorem 3.3 with the parameters \((\theta,j,T_1,\phi_1)\), which gives \(\overline K^{(p)}_j(y,\mathcal L^{(p)}_{j+1}(y,\lambda_y))=1-o(1)\), where, by the convention of Section 1.4, the \(o(1)\) is a function of \(N\) alone, uniform over all \(p\) in the range and all admissible \((y,\lambda)\). By Proposition 5.6 with the parameters \((\theta,j,T^\circ_j,\delta^\circ_j)\), \(\mathcal L^{(p)}_{j+1}(y,\lambda_y)\subseteq\mathcal G_{j+1}(T_2,\delta_2)\subseteq\mathcal G_{j+1}(T^\circ_{j+1},\delta^\circ_{j+1})\). Therefore \[\begin{aligned} \mathbb P\left[y_{j+1}\in\mathcal G_{j+1}(T^\circ_{j+1},\delta^\circ_{j+1})\right]&\ge\sum_{\substack{y\in\mathcal G_j(T^\circ_j,\delta^\circ_j)\\ \mathbb P[y_j=y]>0}}\mathbb P[y_j=y]\,\overline K^{(p)}_j\left(y,\mathcal L^{(p)}_{j+1}(y,\lambda_y)\right)\\ &\ge(1-o(1))\,\mathbb P\left[y_j\in\mathcal G_j(T^\circ_j,\delta^\circ_j)\right]=1-o(1), \end{aligned}\] which completes the induction. Since there are finitely many days, a union bound gives (i): with probability \(1-o(1)\), \(y_j\in\mathcal G_j(T^\circ_j,\delta^\circ_j)\subseteq\mathcal G_j(T^\ast,\delta^\ast)\) for all \(1\le j\le K_\theta\).

The integer case. Suppose \(\frac1{1-\theta}=k_0\in\mathbb Z\), so \(K_\theta=k_0\). Fix \(y\in\mathcal G_{k_0}(T^\ast,\delta^\ast)\) with \(\mathbb P[y_{k_0}=y]>0\). Theorem 5.5 with the parameters \((\theta,T^\ast,\delta^\ast)\), whose ranges contain ours since \(T^\ast\ge T\), provides \(\lambda_y\) and constants \(T_1',\phi_1',\zeta\) such that \((y,\lambda_y)\) is \((T_1',\phi_1',p)\)-locally admissible and its local template satisfies \((-1)^b(n^{\mathrm{loc}}[sb]-N\nu[sb])\ge\zeta N\) for all \(s\in\{0,1\}^{k_0}\), \(b\in\{0,1\}\). Since \(T_1'\ge T^\ast\ge T\), the density range is contained in that of Theorem 3.3 with the parameters \((\theta,k_0,T_1',\phi_1')\). By that theorem and Proposition 2.4, conditionally on \(y_{k_0}=y\), with probability \(1-o(1)\) the state \(y_{k_0+1}\) lies in \(\mathcal L^{(p)}_{k_0+1}(y,\lambda_y)\), and then (L3) gives, for every \(s\in\{0,1\}^{k_0}\) and \(b\in\{0,1\}\), \[(-1)^b\left(|\Pi_{k_0+1}(\mathfrak g)[sb]|-N\nu[sb]\right)\ge\zeta N-C_{3.3}(\theta,k_0,T_1',\phi_1')\sqrt N\log N\ge\tfrac{\zeta}{2}N\] for large \(N\), where we used \(\operatorname{part}(y_{k_0+1})=\Pi_{k_0+1}(\mathfrak g)\). Summing over \(y\) as above and combining with (i) at day \(k_0\) gives (ii), since for \(s\in\{0,1\}^{k_0+1}\) the sign \((-1)^{s[k_0]}\) is \((-1)^b\) when \(s\) is written as \(s'b\). ◻

Proof. Let \(T^\ast,\delta^\ast\) be the constants of Theorem 5.8, and let \(E\) be its event of probability \(1-o(1)\). It suffices to show that \(\Delta_K(\mathfrak g)\ge\frac{N}{\sqrt{pN}}\log N\) on \(E\) for large \(N\).

Suppose first that \(\frac1{1-\theta}\notin\mathbb Z\), so that \(K=K_\theta\). On \(E\), condition (F1) at day \(K\) with the constants \((T^\ast,\delta^\ast)\) gives, for every \(s\in\{0,1\}^K\), \[|\Pi_K(\mathfrak g)[s]|=\widetilde n[s]+\tau\sqrt N\sqrt{pN}^{\,K-1}\varepsilon[s]+O\left(\sqrt N\sqrt{pN}^{\,K-1}N^{-\delta^\ast}\right).\] Summing with the signs \((-1)^{s[K-1]}\): the first sum \(\sum_s(-1)^{s[K-1]}\widetilde n[s]\) vanishes, because pairing \(s\) with \(\overline s\) and using \(\widetilde n[\overline s]=\widetilde n[s]\) (Theorem 5.2(iv)) shows that it equals its own negative; the second is \(\tau\sqrt N\sqrt{pN}^{K-1}S_K\) with \(S_K:=\sum_s(-1)^{s[K-1]}\varepsilon[s]=2\sum_{s'\in\{0,1\}^{K-1}}\varepsilon[s'0]>0\) by Corollary 4.10(ii). Hence, for large \(N\), \[\Delta_K(\mathfrak g)\ge\tau S_K\sqrt N\sqrt{pN}^{\,K-1}-O\left(\sqrt N\sqrt{pN}^{\,K-1}N^{-\delta^\ast}\right)\ge\frac{S_K}{2T}\sqrt N\sqrt{pN}^{\,K-1}.\] Finally \(\sqrt N\sqrt{pN}^{K-1}\big/\big(\frac{N}{\sqrt{pN}}\log N\big)=\sqrt{pN}^{\,K}/(\sqrt N\log N)\ge T^{-K/2}N^{(K(1-\theta)-1)/2}/\log N\to\infty\), because \(K=\lfloor\frac1{1-\theta}\rfloor+1>\frac1{1-\theta}\) gives \(K(1-\theta)>1\). So \(\Delta_K(\mathfrak g)\ge\frac{N}{\sqrt{pN}}\log N\) for large \(N\).

Suppose now that \(\frac1{1-\theta}=k_0\in\mathbb Z\), so that \(K=k_0+1\). On \(E\), Theorem 5.8(ii) gives \[(-1)^{s[K-1]}\left(|\Pi_K(\mathfrak g)[s]|-N\nu[s]\right)\ge\tfrac\zeta2N\qquad\text{for every }s\in\{0,1\}^K .\] Sum over the \(2^K\) strings \(s\) and use \(\sum_s(-1)^{s[K-1]}\nu[s]=0\), which is Corollary 4.10(iii) with \(r=K\): \[\Delta_K(\mathfrak g)=\sum_{s\in\{0,1\}^K}(-1)^{s[K-1]}|\Pi_K(\mathfrak g)[s]|\ge N\sum_s(-1)^{s[K-1]}\nu[s]+2^K\frac{\zeta}{2}N=2^{k_0}\zeta N,\] which exceeds \(\frac{N}{\sqrt{pN}}\log N\) for large \(N\). ◻

Proof. The degree of a vertex is a \(\mathrm{Bin}(N-1,p)\) variable with mean \(p(N-1)\ge0.95pN\) for large \(N\), so by Chernoff’s inequality it is less than \(0.9pN\) with probability at most \(\exp(-cpN)\) for an absolute constant \(c>0\); a union bound over the \(N\) vertices gives probability at most \(N\exp(-cpN)=o(1)\), because \(pN\ge T^{-1}N^{1-\theta}\gg\log N\). For jumbledness we use (Chakraborti et al. 2023, Lemma 4.1), restating (Krivelevich and Sudakov 2006, Corollary 2.3), in the range \(\log^2N\le pN\) and \(p\le0.99\): with probability \(1-o(1)\), \(\mathbb{G}(V,p)\) is \((p,\beta)\)-jumbled with \(\beta=O(\sqrt{pN})\). Both restrictions hold uniformly in our density window for large \(N\), since \(pN\ge T^{-1}N^{1-\theta}\gg\log^2N\) and \(p\le TN^{-\theta}=o(1)\). ◻

Proof. Write \(U:=M_{j+1}\), \(x:=|U|\), and \(m:=|M_j|\), so that \(\Delta_j(\mathfrak{g})=N-2m\). A vertex \(v\in U\) has at least as many neighbors in \(M_j\) as in its complement: either strictly more of its neighbors hold \(-1\) on day \(j\), or there is a tie and \(v\) already holds \(-1\). Thus \[\tfrac12\deg^G_Vv\le\deg^G_{M_j}v, \qquad\text{and hence}\qquad \tfrac12 e_G(U,V)\le e_G(U,M_j).\] Both conclusions are immediate if \(x=0\), so assume \(x>0\).

(i): Jumbledness gives \[\tfrac12\bigl(pxN-\beta\sqrt{xN}\bigr) \le\tfrac12 e_G(U,V) \le e_G(U,M_j) \le pxm+\beta\sqrt{xm}.\] Using \(m\le N\) and \(\Delta_j(\mathfrak{g})=N-2m\), we obtain \[10\beta x\le px\,\Delta_j(\mathfrak{g}) \le\beta\sqrt{xN}+2\beta\sqrt{xm} \le3\beta\sqrt{xN}.\] Since \(\beta>0\), squaring and canceling \(x>0\) gives \(100x\le9N\), and therefore \(x\le9N/100\le N/5\).

(ii): The minimum-degree bound and the same majority inequality give \[\frac{9}{20}pNx\le e_G(U,M_j) \le pxm+\beta\sqrt{xm}.\] Since \(m\le N/5\), \[\frac{pN}{4}x \le p\left(\frac{9N}{20}-m\right)x \le\beta\sqrt{xm}.\] Both sides are nonnegative; squaring and canceling \(x>0\) yields \((pN)^2x\le16\beta^2m\), proving the assertion because \(pN>0\). ◻

Proof. Uniformly for \(x\in[-\sqrt{pn}\log n,\sqrt{pn}\log n]\cap(\mathbb{Z}-pn)\), we have \[\begin{aligned} \mathbb{P}[\mathrm{Bin}(n',p') = pn + x] &= \frac{n'!}{(pn+x)!(n'-pn-x)!}p'^{pn+x}(1-p')^{n'-pn-x} \\ &= \frac{n'!}{(pn)!(n'-pn)!}p'^{pn}(1-p')^{n'-pn}\cdot\frac{(n'-pn)!}{(n'-pn-x)!}\frac{(pn)!}{(pn+x)!}\left(\frac{p'}{1-p'}\right)^x \\ &= (1+O(p\log^2 n))\frac{n'!}{(pn)!(n'-pn)!}p'^{pn}(1-p')^{n'-pn}\\ &\qquad\cdot(n'-pn)^x\frac{(pn)!}{(pn+x)!}\left(\frac{p'}{1-p'}\right)^x \\ &= (1+O(p\log^2 n))\mathcal{N}_1\left(\frac{p'(n'-pn)}{(1-p')pn}\right)^x\frac{(pn)!(pn)^x}{(pn+x)!}, \end{aligned}\] for some normalization \(\mathcal{N}_1\) independent of \(x\). This proves the first equality.

For the second equality, we use the fact that \[n! = \sqrt{2\pi n}(n/e)^n(1+O(1/n))\] as \(n\to\infty\). Indeed, uniformly for \(x\in[-\sqrt{pn}\log n,\sqrt{pn}\log n]\cap(\mathbb{Z}-pn)\), we have \[\begin{aligned} \frac{(pn+x)!}{(pn)!(pn)^x} &= (1 + O(1/pn))e^{-x}\left(1 + \frac{x}{pn}\right)^{pn+x+\frac{1}{2}} \\ &= (1 + O(1/pn))e^{-x}\exp\left(\left(pn+x+\frac{1}{2}\right)\left[\frac{x}{pn}-\frac{x^2}{2(pn)^2}+ O\left(\frac{\log^3 n}{(pn)^{3/2}}\right)\right]\right) \\ &= \left(1 + O\left(\frac{\log^3 n}{\sqrt{pn}}\right)\right)\exp\left(\frac{x^2}{2pn}\right), \end{aligned}\] which combined with the previous equality implies the second equality. ◻

Proof. Call a convex region \(\mathcal{C}\) in \(\mathbb{R}^d\) (each boundary can be either open or closed) good if it is bounded by pairwise orthogonal planes with integer normal vectors whose entries are bounded by \(\left\lVert M\right\rVert_\infty\), and distance to the origin bounded by \(\sqrt{pn}\log n\). For such a region, define \[\mathcal{P}_1(\mathcal{C}) := \bigcup_{\substack{x\in \prod_{t\in[d]}(\mathbb{Z}-p\eta_t)\cap[-\sqrt{p\eta_t}\log\eta_t,\sqrt{p\eta_t}\log\eta_t] \\ x\in\mathcal{C}}}\prod_{t\in[d]}[x_t,x_t+1),\] and \[\mathcal{P}_2(\mathcal{C}) := \left\{x\in\prod_{t\in[d]}[-\sqrt{p\eta_t}\log\eta_t,\sqrt{p\eta_t}\log\eta_t] : x\in\mathcal{C}\right\},\] and \[\mathcal{P}_3(\mathcal{C}) := \left\{x\in\mathbb{R}^d : x\in\mathcal{C}\right\}.\]

Note that \(\mathbb{P}[|A_t-p\eta_t| > \sqrt{p\eta_t}\log\eta_t] = O(n^{-\omega(1)})\) by Chernoff’s inequality, so Lemma A.5 gives \[\mathbb{E}[\rho(A-p\eta)\mathbf{1}_{MA\ge'0}] = \frac{\displaystyle\sum_{\substack{x\in\prod_{t\in[d]}(\mathbb{Z}-p\eta_t)\cap[-\sqrt{p\eta_t}\log\eta_t,\sqrt{p\eta_t}\log\eta_t] \\ Mx\ge' -pM\eta}}\rho(x)f(x)}{\displaystyle\sum_{x\in\prod_{t\in[d]}(\mathbb{Z}-p\eta_t)\cap[-\sqrt{p\eta_t}\log\eta_t,\sqrt{p\eta_t}\log\eta_t]}f(x)} + O(\sqrt{pn}^{\deg\rho-1}\log^{3+\deg\rho}n),\] where \[f(x):=\exp\left(-\sum_{t\in[d]}\frac{(x_t-\alpha_t\sqrt{p\eta_t})^2}{2p\eta_t}\right).\] The first step is to turn the summations into integrals over \(\mathcal{P}_1\).

Note that for \(x\in\prod_{t\in[d]}[-\sqrt{p\eta_t}\log\eta_t,\sqrt{p\eta_t}\log\eta_t]\), we have \[f(x+\varepsilon) = f(x) + O(\log n/\sqrt{pn})\] for any \(\varepsilon\in[0,1)^d\). In particular, this implies that \[f(x) = \int_{[0,1)^d}d\varepsilon\, f(x+\varepsilon) + O(\log n/\sqrt{pn})\] and \[\rho(x)f(x) = \int_{[0,1)^d}d\varepsilon\,\rho(x+\varepsilon)f(x+\varepsilon) + O(\sqrt{pn}^{\deg\rho-1}\log^{1+\deg\rho} n)\] for all \(x\in\prod_{t\in[d]}[-\sqrt{p\eta_t}\log\eta_t,\sqrt{p\eta_t}\log\eta_t]\). Thus, letting \(\mathcal{C}_M = \{x\in\mathbb{R}^d : Mx\ge' -pM\eta\}\), we have \[\begin{aligned} \mathbb{E}[\rho(A-p\eta)\mathbf{1}_{MA\ge'0}] &= \frac{\int_{\mathcal{P}_1(\mathcal{C}_M)}dx\,\rho(x)f(x) + O(\sqrt{pn}^{\deg\rho + d-1}\log^{1+\deg\rho + d} n)}{\int_{\mathcal{P}_1(\mathbb{R}^d)}dx\,f(x) + O(\sqrt{pn}^{d-1}\log^{1+d}n)}\\ &\quad+ O(\sqrt{pn}^{\deg\rho-1}\log^{3+\deg\rho}n). \end{aligned}\] There is a constant \(C\) such that for any good \(\mathcal{C}\), \(\mathcal{P}_1\setminus\mathcal{P}_2\) and \(\mathcal{P}_2\setminus\mathcal{P}_1\) are both contained in \(B(\partial\mathcal{P}_2,C)\), and \(\mathrm{vol}\,B(\partial\mathcal{P}_2,C)=O(\sqrt{pn}^{d-1}\log^{d-1}n)\). Therefore, \[\begin{aligned} \mathbb{E}[\rho(A-p\eta)\mathbf{1}_{MA\ge'0}] &= \frac{\int_{\mathcal{P}_2(\mathcal{C}_M)}dx\,\rho(x)f(x) + O(\sqrt{pn}^{\deg\rho + d-1}\log^{1+\deg\rho + d} n)}{\int_{\mathcal{P}_2(\mathbb{R}^d)}dx\,f(x) + O(\sqrt{pn}^{d-1}\log^{1+d}n)}\\ &\quad+ O(\sqrt{pn}^{\deg\rho-1}\log^{3+\deg\rho}n). \end{aligned}\] Note that \(\mathcal{P}_2\subset\mathcal{P}_3\) and \(\mathcal{P}_3\setminus\mathcal{P}_2\subset\{x\in\mathbb{R}^d : \left\lVert x\right\rVert_\infty>C\sqrt{pn}\log n\}\) for some constant \(C\), and \[\begin{aligned} &\int_{\left\lVert x\right\rVert_\infty>C\sqrt{pn}\log n}dx\,f(x) = O(n^{-\omega(1)}) \\ &\int_{\left\lVert x\right\rVert_\infty>C\sqrt{pn}\log n}dx\,\left\lVert\rho(x)\right\rVert_\infty f(x) = O(n^{-\omega(1)}). \end{aligned}\] Therefore, \[\begin{aligned} \mathbb{E}[\rho(A-p\eta)\mathbf{1}_{MA\ge'0}] &= \frac{\int_{\mathcal{P}_3(\mathcal{C}_M)}dx\,\rho(x)f(x) + O(\sqrt{pn}^{\deg\rho + d-1}\log^{1+\deg\rho + d} n)}{\int_{\mathcal{P}_3(\mathbb{R}^d)}dx\,f(x) + O(\sqrt{pn}^{d-1}\log^{1+d}n)}\\ &\quad+ O(\sqrt{pn}^{\deg\rho-1}\log^{3+\deg\rho}n) \\ &= \frac{\int_{x\in\mathcal{C}_M}dx\,\rho(x)f(x)}{\int_{x\in\mathbb{R}^d}dx\, f(x)} + O(\sqrt{pn}^{\deg\rho-1}\log^{3+\deg\rho+d}n), \end{aligned}\] as desired. ◻

Proof. Write \(\widetilde{c}:=p\widetilde{\eta}\) for the common center, \(D:=\deg\rho\), and \[\Lambda:=\prod_{t\in[d]}\left(\mathbb{Z}-\widetilde{c}_t\right)\cap\left[-\sqrt{p\widetilde{\eta}_t}\log\widetilde{\eta}_t,\ \sqrt{p\widetilde{\eta}_t}\log\widetilde{\eta}_t\right]\] for the lattice window around the center, and \(\mathcal{R}:=\{x\in\Lambda:Mx\ge'-M\widetilde{c}\}\). Since \(\widetilde{\eta}_t\in(T^{-1}n,Tn)\) we have \(\sqrt{p\widetilde\eta_t}\log\widetilde\eta_t\asymp\sqrt{pn}\log n\), so on \(\Lambda\) every coordinate satisfies \(|x_t|=O(\sqrt{pn}\log n)\) and \(|\rho(x)|=O(\sqrt{pn}^{D}\log^Dn)\). All implied constants below depend only on \(\theta,d,M,\rho,T\).

Step 1: truncation. The means satisfy \(|\mathbb{E}\widetilde{A}_t-\widetilde{c}_t|\le|\widetilde\eta'_t-\widetilde\eta_t|\widetilde q_t+\widetilde\eta_t|\widetilde q_t-p|\le2T\sqrt{pn}+T^2\sqrt{pn}\) and likewise \(|\mathbb{E}A_t-\widetilde{c}_t|\le2T\sqrt{pn}+T^2\sqrt{pn}\), and the variances are \(O(pn)\), so Chernoff’s inequality gives \(\mathbb{P}[A-\widetilde{c}\notin\Lambda]=O(n^{-\omega(1)})\) and \(\mathbb{P}[\widetilde{A}-\widetilde{c}\notin\Lambda]=O(n^{-\omega(1)})\). For large \(n\), the trial counts \(\eta_t\) and \(\widetilde\eta'_t\) are at most \(2Tn\), so \(|\rho(A-\widetilde c)|\) and \(|\rho(\widetilde A-\widetilde c)|\) are deterministically \(O(n^D)\), while multiplying by one centered coordinate gives \(O(n^{D+1})\); the coefficients of \(\rho\) are absorbed into the implied constants. Consequently the contributions of the complement of \(\Lambda\) to all expectations in the statement are \(O(n^{-\omega(1)})\), and the events \(\{MA\ge'0\}\) and \(\{M\widetilde{A}\ge'0\}\) coincide with \(\{A-\widetilde{c}\in\mathcal{R}\}\) and \(\{\widetilde{A}-\widetilde{c}\in\mathcal{R}\}\) on \(\Lambda\), because \(A=\widetilde{c}+x\) satisfies \(MA\ge'0\) if and only if \(Mx\ge'-M\widetilde{c}\), and likewise for \(\widetilde{A}\).

Step 2: the two point probabilities. Apply the first formula of Lemma A.5, for each \(t\), with its \(n\) equal to \(\widetilde{\eta}_t\) (so that its center is \(p\widetilde\eta_t=\widetilde c_t\) and its window is the \(t\)th factor of \(\Lambda\)), its constant \(T\) replaced by \(T^{3/2+\theta}\), and \((n',p')=(\widetilde\eta'_t,\widetilde q_t)\), respectively \((n',p')=(\eta_t,q_t)\); the hypotheses hold because \(p\in(T^{-1-\theta}\widetilde\eta_t^{-\theta},T^{1+\theta}\widetilde\eta_t^{-\theta})\), \(|q_t-p|,|\widetilde q_t-p|<Tp/\sqrt{pn}\le T^{3/2}p/\sqrt{p\widetilde\eta_t}\), and \(|\eta_t-\widetilde\eta_t|,|\widetilde\eta'_t-\widetilde\eta_t|<Tn/\sqrt{pn}\le T^{3/2}\widetilde\eta_t/\sqrt{p\widetilde\eta_t}\). Writing \[\widetilde\kappa_t:=\frac{\widetilde q_t(\widetilde\eta'_t-\widetilde c_t)}{(1-\widetilde q_t)\widetilde c_t},\qquad\kappa_t:=\frac{q_t(\eta_t-\widetilde c_t)}{(1-q_t)\widetilde c_t},\qquad g_t(x):=\frac{\widetilde c_t!\,\widetilde c_t^{\,x}}{(\widetilde c_t+x)!},\qquad w(x):=\prod_{t\in[d]}\widetilde\kappa_t^{\,x_t}g_t(x_t),\] we obtain, uniformly for \(x\in\Lambda\), \[\mathbb{P}\left[\widetilde{A}=\widetilde{c}+x\right]=\left(1+O(p\log^2n)\right)\widetilde{\mathcal{N}}\,w(x),\qquad\mathbb{P}\left[A=\widetilde{c}+x\right]=\left(1+O(p\log^2n)\right)\mathcal{N}\,e^{\beta\cdot x}\,w(x),\] for normalizations \(\widetilde{\mathcal N},\mathcal N\) not depending on \(x\), where we used that \(\kappa_t/\widetilde\kappa_t=e^{\beta_t}\) by the definition of \(\beta\), and that a product of \(d\) factors \(1+O(p\log^2n)\) is again \(1+O(p\log^2n)\).

Step 3: reduction to averages against \(w\). For a function \(h\) on \(\Lambda\) write \[\langle h\rangle:=\frac{\sum_{x\in\Lambda}h(x)w(x)}{\sum_{x\in\Lambda}w(x)}.\] By Step 1, \(\widetilde{\mathcal N}\sum_{x\in\Lambda}(1+O(p\log^2n))w(x)=\mathbb P[\widetilde A-\widetilde c\in\Lambda]=1-O(n^{-\omega(1)})\), so for every function \(h\) on \(\Lambda\) with \(|h|\le H\), \[\label{eq:tilt-average} \begin{aligned} \mathbb{E}\left[h(\widetilde{A}-\widetilde{c})\mathbf{1}_{\widetilde A-\widetilde c\in\Lambda}\right] &=\mathbb P[\widetilde A-\widetilde c\in\Lambda]\, \frac{\sum_{x\in\Lambda}h(x)\left(1+O(p\log^2n)\right)w(x)}{\sum_{x\in\Lambda}\left(1+O(p\log^2n)\right)w(x)}\\ &=\langle h\rangle+O\left(p\log^2n\cdot H\right). \end{aligned}\] The window-mass factor is \(1-O(n^{-\omega(1)})\) by Step 1; its contribution \(O(Hn^{-\omega(1)})\) is absorbed in the displayed error. The same holds for \(A\) with \(w\) replaced by \(e^{\beta\cdot x}w\) in the definition of the average. Applying (A.1) with \(h=\rho\mathbf 1_{\mathcal R}\), \(h=x_t\rho\mathbf 1_{\mathcal R}\), and \(h=x_t\), and using Step 1, \[\label{eq:tilt-conversion} \begin{aligned} \mathbb{E}\left[\rho(\widetilde{A}-\widetilde{c})\mathbf{1}_{M\widetilde{A}\ge'0}\right]&=\langle\rho\mathbf 1_{\mathcal R}\rangle+O\left(p\sqrt{pn}^{D}\log^{2+D}n\right),\\ \mathbb{E}\left[(\widetilde{A}_t-\widetilde{c}_t)\rho(\widetilde{A}-\widetilde{c})\mathbf{1}_{M\widetilde{A}\ge'0}\right]&=\langle x_t\rho\mathbf 1_{\mathcal R}\rangle+O\left(p\sqrt{pn}^{D+1}\log^{3+D}n\right),\\ \mathbb{E}\left[\widetilde{A}_t-\widetilde{c}_t\right]&=\langle x_t\rangle+O\left(p\sqrt{pn}\log^3n\right), \end{aligned}\] and \[\label{eq:tilt-A-side} \mathbb{E}\left[\rho(A-\widetilde{c})\mathbf{1}_{MA\ge'0}\right]=\frac{\sum_{x\in\mathcal R}\rho(x)e^{\beta\cdot x}w(x)}{\sum_{x\in\Lambda}e^{\beta\cdot x}w(x)}+O\left(p\sqrt{pn}^{D}\log^{2+D}n\right).\]

Step 4: expansion of the tilt. On \(\Lambda\) we have \(|\beta\cdot x|\le d\left\lVert\beta\right\rVert_\infty\max_t|x_t|=O(1/\log n)\), so \(e^{\beta\cdot x}=1+\beta\cdot x+O((\beta\cdot x)^2)=1+\beta\cdot x+O(\delta)\) with \(\delta:=\left\lVert\beta\right\rVert_\infty^2pn\log^2n=O(1/\log^2n)\). Inserting this into (A.3), the numerator becomes \(\langle\rho\mathbf 1_{\mathcal R}\rangle+\sum_t\beta_t\langle x_t\rho\mathbf 1_{\mathcal R}\rangle+O(\delta\sqrt{pn}^{D}\log^Dn)\) times \(\sum_\Lambda w\), and the denominator becomes \(1+u+O(\delta)\) times \(\sum_\Lambda w\), where \(u:=\sum_t\beta_t\langle x_t\rangle\). By (A.2) and Step 1, \(\langle x_t\rangle=\mathbb E[\widetilde A_t-\widetilde c_t]+O(p\sqrt{pn}\log^3n)=O(\sqrt{pn})\), so \(|u|=O(\left\lVert\beta\right\rVert_\infty\sqrt{pn})=O(1/\log^2n)\) and \(u^2\le d^2\left\lVert\beta\right\rVert_\infty^2pn\cdot O(1)\le O(\delta)\); hence \((1+u+O(\delta))^{-1}=1-u+O(\delta)\). Multiplying out, and using \(|\langle x_t\rho\mathbf 1_{\mathcal R}\rangle|=O(\sqrt{pn}^{D+1}\log^{D+1}n)\) so that \(\sum_t\beta_t\langle x_t\rho\mathbf 1_{\mathcal R}\rangle\cdot u=O(\left\lVert\beta\right\rVert_\infty^2pn\log^{D+1}n\sqrt{pn}^{D})=O(\delta\sqrt{pn}^D\log^{D}n)\), \[\frac{\sum_{x\in\mathcal R}\rho(x)e^{\beta\cdot x}w(x)}{\sum_{x\in\Lambda}e^{\beta\cdot x}w(x)}=\langle\rho\mathbf 1_{\mathcal R}\rangle+\sum_{t\in[d]}\beta_t\left(\langle x_t\rho\mathbf 1_{\mathcal R}\rangle-\langle x_t\rangle\langle\rho\mathbf 1_{\mathcal R}\rangle\right)+O\left(\delta\sqrt{pn}^{D}\log^{D}n\right).\]

Step 5: conclusion. Substitute (A.2) into the right-hand side. The zeroth-order term contributes an error \(O(p\sqrt{pn}^D\log^{2+D}n)\). In the first-order terms, each \(\beta_t=O(1/(\sqrt{pn}\log^2n))\) multiplies an error of size \(O(p\sqrt{pn}^{D+1}\log^{3+D}n)\), giving \(O(p\sqrt{pn}^{D}\log^{1+D}n)\). Together with (A.3) and the bound \[\delta\sqrt{pn}^D\log^Dn\le\left\lVert\beta\right\rVert_\infty^2\,pn\log^2n\,\sqrt{pn}^D\log^{2+D}n,\] all errors are \(O(\max\{p,\left\lVert\beta\right\rVert_\infty^2pn\log^2n\}\sqrt{pn}^{D}\log^{2+D}n)\), which is the statement. ◻

Proof. Arrange the sequence in nonincreasing order and write \(L_r:=\sum_{i=1}^r d_i\), so that \(L_r\le r\Delta\). By the Erdős–Gallai theorem, it suffices to prove \(L_r\le r(r-1)+\sum_{i=r+1}^n\min(r,d_i)\) for every \(1\le r\le n\). If \(r\ge\Delta\), then \(\min(r,d_i)=d_i\) for \(i>r\), and \[\begin{aligned} r(r-1)+\sum_{i=r+1}^n\min(r,d_i)&=r(r-1)+S-L_r\ge r(r-1)+\Delta(\Delta+1)-r\Delta\\ &=r\Delta+(r-\Delta)(r-\Delta-1)\ge r\Delta\ge L_r, \end{aligned}\] where the second inequality holds because \((r-\Delta)(r-\Delta-1)\ge0\) for every integer \(r\). If \(r<\Delta\), then \(\min(r,d_i)\ge rd_i/\Delta\) for every \(i\), and \[\sum_{i=r+1}^n\min(r,d_i)\ge\frac r\Delta(S-L_r)\ge\frac r\Delta(S-r\Delta)\ge\frac{r}{\Delta}\left(\Delta(\Delta+1)-r\Delta\right)=r\Delta-r(r-1)\ge L_r-r(r-1).\qedhere\] ◻

Proof. Arrange \(a_1,\ldots,a_\ell\) in nonincreasing order. By Gale–Ryser, it suffices to show \[\sum_{i=1}^r a_i\le\sum_{j=1}^n\min(r,b_j)\] for every \(1\le r\le\ell\). If \(r\ge\Delta_R\), the right side is \(M\), and the inequality is immediate. If \(r<\Delta_R\), then \(\min(r,b_j)\ge r b_j/\Delta_R\) for every \(j\), so the right side is at least \(rM/\Delta_R\ge r\Delta_L\ge\sum_{i=1}^r a_i\). ◻

Proof. We first record a moment generating function bound for a single truncated binomial variable. Let \(Y\sim\mathrm{Bin}(r,p)\), let \(B>0\) with \(B\ge rp\), write \(\overline{Y}:=Y-rp\), and put \(\lambda:=1/(20B)\). Bernstein’s inequality (Theorem 2.8.4 of (Vershynin 2018)), applied to the \(r\) independent centered Bernoulli variables whose sum is \(\overline{Y}\), which are bounded by \(1\) and whose variances sum to \(rp(1-p)\le B\), gives for \(0\le u\le2B\) \[\mathbb{P}\left[|\overline{Y}|>u\right]\le2\exp\left(-\frac{u^2/2}{B+u/3}\right)\le2\exp\left(-\frac{3u^2}{10B}\right).\] For \(X\ge0\), \(b>0\), and an increasing differentiable \(g\) we have \(\mathbb{E}[g(\min(X,b))]=g(0)+\int_0^bg'(u)\mathbb{P}[X>u]\,du\); applying this with \(X=|\overline{Y}|\), \(b=2B\), and \(g(u)=e^{\lambda u^2}\), and using \(e^{\lambda\overline{Y}^2}\mathbf{1}_{|\overline{Y}|\le2B}\le e^{\lambda\min(|\overline{Y}|,2B)^2}\), \[\begin{aligned} \mathbb{E}\left[e^{\lambda\overline{Y}^2}\mathbf{1}_{|\overline{Y}|\le2B}\right]&\le1+\int_0^{2B}2\lambda u\,e^{\lambda u^2}\,\mathbb{P}\left[|\overline{Y}|>u\right]du\\ &\le1+\int_0^\infty4\lambda u\exp\left(-\frac{u^2}{4B}\right)du=1+8\lambda B=\frac75\le e^{1/2}. \end{aligned}\] Consequently, if \(\overline{Y}_1,\ldots,\overline{Y}_q\) are independent, each of the form \(Y_i-r_ip\) with \(Y_i\sim\mathrm{Bin}(r_i,p)\) and \(r_ip\le B\), then for every \(t>0\), by Markov’s inequality applied to \(\exp(\lambda\sum_i\overline{Y}_i^2)\) on the truncation event, \[\label{eq:trunc-mgf} \mathbb{P}\left[\sum_{i=1}^q\overline{Y}_i^2\ge t\text{ and }\max_i|\overline{Y}_i|\le2B\right]\le e^{-\lambda t}\prod_{i=1}^q\mathbb{E}\left[e^{\lambda\overline{Y}_i^2}\mathbf{1}_{|\overline{Y}_i|\le2B}\right]\le\exp\left(-\frac{t}{20B}+\frac q2\right).\]

We prove (i). Since the empirical mean \(d\) minimizes \(a\mapsto\sum_i(d_i-a)^2\), we have \(\sum_i(d_i-d)^2\le\sum_i(d_i-p(n-1))^2\), so it suffices to bound the probability of \(\mathcal{E}\cap\mathcal{K}\), where \(\mathcal{E}\) is the event that \(\sum_{i=1}^n(d_i-p(n-1))^2\ge Cpn^2\) and \(\mathcal{K}\) is the event that \(|d_i-pn|\le pn\) for all \(i\in[n]\).

We first show that \(\mathcal{E}\) is contained in a union of events that involve only independent variables. Let \(S\) be a uniformly random subset of \([n]\), let \(U=[n]\setminus S\), and let \(\mathbb{E}_S\) denote averaging over the randomness of \(S\) only. For \(v\in[n]\) write \[\Delta_S(v):=\deg^G_Sv-p|S\setminus\{v\}|,\qquad\Delta_U(v):=\deg^G_Uv-p|U\setminus\{v\}|,\] so that \(\Delta_S(v)+\Delta_U(v)=d_v-p(n-1)\). Both \(\Delta_S(v)\) and \(\Delta_U(v)\) are determined by \(G\) and by \(S\setminus\{v\}\), and \(\mathbf{1}_{v\in S}\) is independent of \(S\setminus\{v\}\). Hence \[\begin{aligned} \mathbb{E}_S\left[\mathbf{1}_{v\in U}\Delta_S(v)^2 + \mathbf{1}_{v\in S}\Delta_U(v)^2\right] &=\frac{1}{2}\mathbb{E}_S\left[\Delta_S(v)^2 + \Delta_U(v)^2\right]\\ &\ge\frac{1}{4}\mathbb{E}_S\left[\left(\Delta_S(v)+\Delta_U(v)\right)^2\right] = \frac{1}{4}(d_v-p(n-1))^2. \end{aligned}\] Summing over \(v\), on the event \(\mathcal{E}\) we have \[\mathbb{E}_S\left[\sum_{v\in U}\Delta_S(v)^2 + \sum_{v\in S}\Delta_U(v)^2\right]\ge Cpn^2/4,\] so there is some \(S\subseteq[n]\) with \(\sum_{v\in U}\Delta_S(v)^2\ge Cpn^2/8\) or \(\sum_{v\in S}\Delta_U(v)^2\ge Cpn^2/8\). Exchanging the roles of \(S\) and \(U\) in the second case, and noting that \(\Delta_S(v)=\deg^G_Sv-p|S|\) for \(v\in U\), we conclude that \(\mathcal{E}\subseteq\bigcup_{S\subseteq[n]}\mathcal{E}_S\), where \[\mathcal{E}_S:=\left\{\sum_{v\in[n]\setminus S}(\deg^G_Sv-p|S|)^2\ge Cpn^2/8\right\}.\]

Fix \(S\). Over the randomness of \(G\), the variables \(\deg^G_Sv\) for \(v\in[n]\setminus S\) are independent \(\mathrm{Bin}(|S|,p)\) variables, since they are determined by the disjoint edge sets \(\{v\}\times S\). On \(\mathcal{K}\) we have \(0\le\deg^G_Sv\le d_v\le2pn\) and \(0\le p|S|\le pn\), so \(|\deg^G_Sv-p|S||\le2pn\) for every \(v\). Applying (A.4) with \(B=pn\), \(t=Cpn^2/8\), and \(q=n-|S|\le n\), \[\mathbb{P}[\mathcal{E}_S\cap\mathcal{K}]\le\exp\left(-\frac{Cn}{160}+\frac{n}{2}\right).\] A union bound over the \(2^n\) sets \(S\) gives \(\mathbb{P}[\mathcal{E}\cap\mathcal{K}]\le\exp(-(C/160-1/2-\log2)n)\le\exp(-Kn)\) as soon as \(C\ge160(K+2)\).

For (ii) no bisection is needed: the variables \(s_i\), \(i\in[\ell]\), are independent \(\mathrm{Bin}(n,p)\) variables, and the variables \(t_j\), \(j\in[n]\), are independent \(\mathrm{Bin}(\ell,p)\) variables. As before, \(\sum_i(s_i-s)^2\le\sum_i(s_i-pn)^2\) and \(\sum_j(t_j-t)^2\le\sum_j(t_j-p\ell)^2\). Apply (A.4) with \(B=Tpn\), which is at least \(np\) and at least \(\ell p\), with \(t=Cp\ell n\ge Cpn^2/T\), and with \(q=\ell\le Tn\), respectively \(q=n\); the truncation hypotheses \(|s_i-pn|\le pn\) and \(|t_j-p\ell|\le pn\) are stronger than the required \(|\overline{Y}_i|\le2B\). Each of the two events in question therefore has probability at most \(\exp(-Cn/(20T^2)+Tn/2)\) on the truncation event, and their union has probability at most \(2\exp(-Cn/(20T^2)+Tn/2)\le\exp(-Kn)\) as soon as \(C\ge20T^2(K+T)\). Both parts therefore hold with \(C_{A.10}(K):=\max\{160(K+2),\,20T^2(K+T)\}\). ◻

Proof. Write \(n_0:=n-\lceil n^{2/3}\rceil\) and \(J:=[-C\sqrt{np},C\sqrt{np}]\cap\mathbb{Z}\), so that \(|J|\ge C\sqrt{np}\). By Chebyshev’s inequality, at least half of all sequences \((y_1,\ldots,y_{n_0})\in J^{n_0}\) have \(|y_1+\cdots+y_{n_0}|\le2C\sqrt{n}\sqrt{np}\). Each such sequence has at least one continuation \((y_{n_0+1},\ldots,y_n)\in J^{n-n_0}\) making the overall sum \(0\), since the remaining \(\lceil n^{2/3}\rceil\) entries, each ranging over the integer interval \(J\), can contribute any integer of absolute value at most \(\lceil n^{2/3}\rceil\lfloor C\sqrt{np}\rfloor\), and \(\lceil n^{2/3}\rceil\lfloor C\sqrt{np}\rfloor\ge 2C\sqrt n\sqrt{np}\) for large \(n\). Therefore, the number of sequences in question is at least \[\frac{1}{2}|J|^{n_0}\ge\frac12\left(C\sqrt{np}\right)^{n-n^{2/3}-1}\ge\exp(-C_{A.11}(C)\,n)(\sqrt{np})^n\] for a suitable constant \(C_{A.11}(C)>0\) depending only on \(\theta\), \(T\), and \(C\) (the factor \((\sqrt{np})^{-n^{2/3}-1}\ge\exp(-n^{2/3}\log n)\) and the factor \(\frac12C^{\,n-n^{2/3}-1}\) are both \(\ge\exp(-O(n))\)), as desired. ◻

Proof. The density \(\varphi\) of \(X\) is positive on all of \(\mathbb{R}^d\), and \(\mathcal{O}\) is a nonempty open set, hence has positive Lebesgue measure; therefore \(\mathbb{P}[X\in\mathcal{O}]=\int_{\mathcal{O}}\varphi>0\), and the law of \(X\) conditioned on \(\{X\in\mathcal{O}\}\) has the density \(\varphi\mathbb{1}_{\mathcal{O}}/\mathbb{P}[X\in\mathcal{O}]\), which is positive on \(\mathcal{O}\) and vanishes off \(\mathcal{O}\).

Let \(\mu:=\mathbb{E}[X\mid X\in\mathcal{O}]\) and suppose \(\mu\notin\mathcal{O}\). Since \(\mathcal{O}\) is convex and open, the separating hyperplane theorem gives \(u\in\mathbb{R}^d\setminus\{0\}\) with \(u\cdot x\le u\cdot\mu\) for all \(x\in\mathcal{O}\), and the inequality is strict for every \(x\in\mathcal{O}\) because \(\mathcal{O}\) is open. Hence \(u\cdot X<u\cdot\mu\) almost surely under the conditioned law, and taking expectations, \(u\cdot\mu=\mathbb{E}[u\cdot X\mid X\in\mathcal{O}]<u\cdot\mu\), a contradiction. Thus \(\mu\in\mathcal{O}\).

Finally let \(u\in\mathbb{R}^d\setminus\{0\}\). Then \(u^\top\mathrm{Cov}(X\mid X\in\mathcal{O})\,u=\mathrm{Var}(u\cdot X\mid X\in\mathcal{O})\). If this vanished, the conditioned law would be supported on the hyperplane \(\{x:u\cdot x=u\cdot\mu\}\), which has Lebesgue measure zero, whereas the conditioned law has a density that is positive on the open set \(\mathcal{O}\) and therefore gives positive mass to \(\mathcal{O}\) minus any Lebesgue-null set. Hence the variance is positive, and \(\mathrm{Cov}(X\mid X\in\mathcal{O})\) is positive definite. ◻

Proof. By Fact 2.1, it suffices to show that for every internal block pair \(\{s,s\}\) the sequence \((\mathbf{d}[x,s])_{x\in\Pi[s]}\) is the degree sequence of some simple graph on \(\Pi[s]\), and that for every bipartite block pair \(\{s,t\}\) the pair of sequences \((\mathbf{d}[x,t])_{x\in\Pi[s]}\), \((\mathbf{d}[y,s])_{y\in\Pi[t]}\) is the pair of degree sequences of some simple bipartite graph between \(\Pi[s]\) and \(\Pi[t]\).

Fix \(s\). The sequence \((\mathbf{d}[x,s])_{x\in\Pi[s]}\) has even sum \(m[s,s]\), and by the assumptions \(m[s,s]\asymp pN^2\). By \(\kappa_p\), \[\Delta_s:=\max_{x\in\Pi[s]}\mathbf{d}[x,s]\le p|\Pi[s]|+(pN)^{4/7}=O(pN).\] Since \(\Delta_s(\Delta_s+1)=O(p^2N^2)=o(pN^2)\), we have \(m[s,s]\ge\Delta_s(\Delta_s+1)\) for all sufficiently large \(N\), and Lemma A.8 implies that there is a simple graph on \(\Pi[s]\) with degree sequence \((\mathbf{d}[x,s])_{x\in\Pi[s]}\). Now fix \(s\ne t\). The two sequences \((\mathbf{d}[x,t])_{x\in\Pi[s]}\) and \((\mathbf{d}[y,s])_{y\in\Pi[t]}\) have the common sum \(m[s,t]\asymp pN^2\), and by \(\kappa_p\) their maxima \(\Delta_{s,t}\) and \(\Delta_{t,s}\) are \(O(pN)\), so \(m[s,t]\ge\Delta_{s,t}\Delta_{t,s}\) for all sufficiently large \(N\), and Lemma A.9 implies that there is a simple bipartite graph between \(\Pi[s]\) and \(\Pi[t]\) with these two degree sequences. Thus \(\mathbf{d}\in\mathcal{D}(\Pi)\). ◻

Proof. Factorization over block pairs. Write \(\{m\}:=\{\mathbf{d}'\in\mathcal{A}(\Pi):m(\Pi,\mathbf{d}')=m\}\). For \(\mathbf{d}\in\{m\}\) and a block pair \(\{s,t\}\) of \(\Pi\), let \(\mathbf{d}_{s,s}:=(\mathbf{d}[x,s])_{x\in\Pi[s]}\) be the degree sequence of \(\mathbf{d}\) on the internal block pair \(\{s,s\}\), which has sum \(m[s,s]\), and let \(\mathbf{d}_{s,t}:=\big((\mathbf{d}[x,t])_{x\in\Pi[s]},(\mathbf{d}[y,s])_{y\in\Pi[t]}\big)\) be its pair of degree sequences on the bipartite block pair \(\{s,t\}\), which have common sum \(m[s,t]\). The array \(\mathbf{d}\) is the same as the collection of these sequences, and both laws in the statement factor over block pairs, in the notation of Definition A.1 and Definition A.2: \[\label{eq:enum-factor} \begin{aligned} \mathsf{G}_{\Pi,m}(\mathbf{d})&=\prod_{s\in\{0,1\}^k}\mathbb{P}_{G(n[s],m[s,s]/2)}(\mathbf{d}_{s,s})\prod_{\{s,t\}:\,s\ne t}\mathbb{P}_{G(n[s],n[t],m[s,t])}(\mathbf{d}_{s,t}),\\ \mathsf{R}_{\Pi,\lambda}(\mathbf{d}\mid\{m\})&=\prod_{s\in\{0,1\}^k}\mathbb{P}_{B(n[s],m[s,s]/2)}(\mathbf{d}_{s,s})\prod_{\{s,t\}:\,s\ne t}\mathbb{P}_{B(n[s],n[t],m[s,t])}(\mathbf{d}_{s,t}). \end{aligned}\] The first identity is Definition 3.5: under \(\mathsf{G}_{\Pi,m}\), the restrictions of \(G\) to the block pairs are independent uniformly random simple graphs on \(\Pi[s]\) with \(m[s,s]/2\) edges, respectively bipartite graphs between \(\Pi[s]\) and \(\Pi[t]\) with \(m[s,t]\) edges. For the second identity, \(\mathsf{R}_{\Pi,\lambda}\) is a product law and \(\{m\}\) is an intersection of one constraint per block pair, so the block-pair sequences remain independent after conditioning; and for independent binomial variables with a common success probability \(\lambda\), every point probability on the event that their sum equals \(M\) carries the same factor \(\lambda^{M}(1-\lambda)^{\text{trials}-M}\), so the conditional law given the sum does not depend on \(\lambda\) and coincides with the laws \(\mathbb{P}_{B(\cdot)}\), which were defined with success probability \(1/2\). In particular the numerical values of \(\lambda[s,t]\) play no role in this proof.

Hypotheses of the enumeration theorems. Write \(\bar d_{s,t}:=m[s,t]/n[s]\) for the average of the sequence \((\mathbf{d}[x,t])_{x\in\Pi[s]}\). By (LA2), \(n[s]\asymp N\); by (LA2) and (LA3), \(\bar d_{s,t}\asymp pN\) and \[\label{eq:enum-avg} \left|\bar d_{s,t}-p\,n[t]\right|\le\frac{TN^2p}{\sqrt{pN}\,n[s]}\le T^2\sqrt{pN}.\] Hence \(\kappa_p(\Pi,\mathbf{d})\) and (B.2) give, for all \(s,t\in\{0,1\}^k\) and \(x\in\Pi[s]\), \[\label{eq:enum-entry} \left|\mathbf{d}[x,t]-\bar d_{s,t}\right|\le(pN)^{4/7}+T^2\sqrt{pN}\le2(pN)^{4/7}\le\bar d_{s,t}^{\,7/12}\] for large \(N\), which is the maximum-degree hypothesis of Theorem A.3 and Theorem A.4 with \(\alpha=7/12\), applied to each block pair after identifying \(\Pi[s]\) with \([n[s]]\). Their remaining hypotheses hold as well: the densities \(\mu_s\) and \(\mu_{s,t}\) defined below are \(\asymp p\to0\); the average degrees are \(\asymp pN\ge T^{-1}N^{1-\theta}\), so \(\log^KN/N=o(\mu_s)\) and \(N\log^KN=o(m[s,t])\) for every fixed \(K\); and for \(\alpha=7/12\) the condition \((\ell+n)^{5-5\alpha}=o(\ell n\,m^{3-5\alpha})\) of Theorem A.4, with \(\ell=n[s]\), \(n=n[t]\), \(m=m[s,t]\), reads \(N^{25/12}=o(N^{2}(pN^2)^{1/12})\) up to constants, that is, \((pN)^{1/12}\to\infty\). Every \(\mathbf{d}\) in the statement is graphical by Lemma B.1, whose hypotheses are supplied by (LA2) and (LA3); thus each block-pair degree sequence of \(\mathbf{d}\) is realized by a simple graph, respectively bipartite graph, so the left-hand sides in (B.4) below are positive.

The block-pair ratios. Put \(\mu_s:=\bar d_{s,s}/(n[s]-1)\), \(\mu_{s,t}:=m[s,t]/(n[s]n[t])\), both \(\asymp p\), and \[\gamma_2(\mathbf{d}_{s,s}):=\frac{1}{(n[s]-1)^2}\sum_{x\in\Pi[s]}\left(\mathbf{d}[x,s]-\bar d_{s,s}\right)^2,\qquad \sigma^2_{s,t}:=\frac{1}{n[s]}\sum_{x\in\Pi[s]}\left(\mathbf{d}[x,t]-\bar d_{s,t}\right)^2 .\] The error terms of Theorem A.3 and Theorem A.4 are \(o(1)\) in the present ranges: with \(\alpha=7/12\) they are \(O(\log^2N/\sqrt N+(pN)^{-1/12})\), respectively \(O(\log^2N/\sqrt N+(pN)^{-25/12}\cdot p^2N^2)=O(\log^2N/\sqrt N+(pN)^{-1/12})\). The theorems therefore read \[\label{eq:enum-ratios} \begin{aligned} \frac{\mathbb{P}_{G(n[s],m[s,s]/2)}(\mathbf{d}_{s,s})}{\mathbb{P}_{B(n[s],m[s,s]/2)}(\mathbf{d}_{s,s})}&=(1+o(1))\exp\left(\frac14-\frac{\gamma_2(\mathbf{d}_{s,s})^2}{4\mu_s^2(1-\mu_s)^2}\right),\\ \frac{\mathbb{P}_{G(n[s],n[t],m[s,t])}(\mathbf{d}_{s,t})}{\mathbb{P}_{B(n[s],n[t],m[s,t])}(\mathbf{d}_{s,t})}&=(1+o(1))H_{s,t}, \end{aligned}\] where \[H_{s,t}:=\exp\left(-\frac12\left(1-\frac{\sigma^2_{s,t}}{\bar d_{s,t}(1-\mu_{s,t})}\right)\left(1-\frac{\sigma^2_{t,s}}{\bar d_{t,s}(1-\mu_{s,t})}\right)\right).\] Taking logarithms in (B.1) and substituting (B.4), \[\label{eq:enum-log} \log\frac{\mathsf{G}_{\Pi,m}(\mathbf{d})}{\mathsf{R}_{\Pi,\lambda}(\mathbf{d}\mid\{m\})} =\sum_{s\in\{0,1\}^k}\left(\frac14-\frac{\gamma_2(\mathbf{d}_{s,s})^2}{4\mu_s^2(1-\mu_s)^2}\right)+\sum_{\{s,t\}:\,s\ne t}\log H_{s,t}+o(1).\]

Proof of (i). By (B.3), \[\gamma_2(\mathbf{d}_{s,s})\le\frac{4n[s](pN)^{8/7}}{(n[s]-1)^2}=O\left(p(pN)^{1/7}\right),\qquad \frac{\gamma_2(\mathbf{d}_{s,s})^2}{4\mu_s^2(1-\mu_s)^2}=O\left(\frac{p^2(pN)^{2/7}}{p^2}\right)=O\left((pN)^{2/7}\right),\] and \[\sigma^2_{s,t}\le4(pN)^{8/7},\qquad \frac{\sigma^2_{s,t}}{\bar d_{s,t}(1-\mu_{s,t})}=O\left((pN)^{1/7}\right),\] so that \(|\log H_{s,t}|\le\frac12\left(1+O\left((pN)^{1/7}\right)\right)^2=O\left((pN)^{2/7}\right)\). Each of the \(2^k+\binom{2^k}{2}\) terms in (B.5) is therefore \(O((pN)^{2/7})\) in absolute value, with implied constants depending only on \(\theta,k,T\); this is (i).

Proof of (ii). If \(\Gamma_{C_\Gamma,p}(\Pi,m,\mathbf{d})\) holds, then \(\sum_{x\in\Pi[s]}(\mathbf{d}[x,t]-\bar d_{s,t})^2\le C_\Gamma pN^2\) for all \(s,t\), so in place of the bounds above, \[\begin{aligned} \gamma_2(\mathbf{d}_{s,s})&\le\frac{C_\Gamma pN^2}{(n[s]-1)^2}=O(C_\Gamma p),& \frac{\gamma_2(\mathbf{d}_{s,s})^2}{4\mu_s^2(1-\mu_s)^2}&=O\left(C_\Gamma^2\right),\\ \sigma^2_{s,t}&\le\frac{C_\Gamma pN^2}{n[s]}=O(C_\Gamma pN),& |\log H_{s,t}|&=O\left((1+C_\Gamma)^2\right), \end{aligned}\] and every term in (B.5) is bounded in absolute value by a constant depending only on \(\theta,k,T,C_\Gamma\); this is (ii). ◻

Proof. Let \(P_{\Pi,p}\) denote the law of \(\delta(\Pi,G)\) for \(G\sim\mathbb{G}(V,p)\), with the partition \(\Pi\) fixed, and abbreviate \(\{m\}:=\{\mathbf{D}\in\mathcal{A}(\Pi):m(\Pi,\mathbf{D})=m\}\), \(\kappa_p:=\kappa_p(\Pi,\cdot)\), and \(\Gamma_C:=\Gamma_{C,p}(\Pi,m,\cdot)\) for \(C>0\). By Definition 3.5, \(\mathsf{G}_{\Pi,m}=P_{\Pi,p}[\,\cdot\mid\{m\}]\), so for every event \(E\subseteq\mathcal{A}(\Pi)\), \[\label{eq:G-as-conditional} \mathsf{G}_{\Pi,m}(E)=\frac{P_{\Pi,p}\left[E\cap\{m\}\right]}{P_{\Pi,p}\left[\{m\}\right]}.\] Applying (B.6) to numerator and denominator, the quantity to be bounded is \[\label{eq:gamma-goal} \mathsf{G}_{\Pi,m}\left(\Gamma_{C_{B.3}}^c\mid\mathcal{I}_\Pi\cap\kappa_p\right) =\frac{\mathsf{G}_{\Pi,m}\left(\Gamma_{C_{B.3}}^c\cap\mathcal{I}_\Pi\cap\kappa_p\right)}{\mathsf{G}_{\Pi,m}\left(\mathcal{I}_\Pi\cap\kappa_p\right)} =\frac{P_{\Pi,p}\left[\Gamma_{C_{B.3}}^c\cap\mathcal{I}_\Pi\cap\kappa_p\cap\{m\}\right]}{P_{\Pi,p}\left[\mathcal{I}_\Pi\cap\kappa_p\cap\{m\}\right]}.\] We will exhibit a constant \(C_5\), depending only on \(\theta,k,T,\phi\) and not on \(C_{B.3}\), such that the denominator is at least \(e^{-C_5N}\) (Steps 1–3), and then choose \(C_{B.3}\) so that the numerator is at most \(e^{-(C_5+1)N}\) (Step 4). The constants \(C_0,\ldots,C_5\) and \(C_\ast\) below are internal to this proof and depend only on \(\theta,k,T,\phi\).

Step 1: lower bound for \(P_{\Pi,p}[\{m\}]\). Under \(P_{\Pi,p}\), the edge counts of the block pairs of \(\Pi\) are independent, so \(P_{\Pi,p}[\{m\}]\) is the product, over the block pairs of \(\Pi\), of the probabilities that the edge count of the internal block pair \(\{s,s\}\) equals \(m[s,s]/2\), respectively that the edge count of the bipartite block pair \(\{s,t\}\) equals \(m[s,t]\). Each such edge count is a binomial variable \(\mathrm{Bin}(R,p)\) with \(R=\binom{n[s]}{2}\), respectively \(R=n[s]n[t]\), so that \(Rp\asymp N^2p\) by (LA2), and by (LA3) the target value \(j\) (\(=m[s,s]/2\), respectively \(m[s,t]\)) satisfies \(|j-Rp|=O(N^2p/\sqrt{pN})\). We use the following elementary lower bound for binomial point probabilities. For an integer \(0<j<R\), put \(q:=j/R\). The term \(\binom Rj q^j(1-q)^{R-j}\) is the largest of the \(R+1\) terms of the binomial distribution \(\mathrm{Bin}(R,q)\), whose mode is at \(\lfloor(R+1)q\rfloor=j\), and these terms sum to \(1\), so \(\binom Rj q^j(1-q)^{R-j}\ge(R+1)^{-1}\). Therefore \[\begin{aligned} \mathbb P[\mathrm{Bin}(R,p)=j]=\binom Rj p^j(1-p)^{R-j} &\ge\frac{1}{R+1}\left(\frac pq\right)^{j}\left(\frac{1-p}{1-q}\right)^{R-j} =\frac{1}{R+1}\exp\left(-R\,D(q\,\|\,p)\right)\\ &\ge\frac{1}{R+1}\exp\left(-\frac{(j-Rp)^2}{Rp(1-p)}\right), \end{aligned}\] where \(D(q\|p)=q\log\frac qp+(1-q)\log\frac{1-q}{1-p}\), and the last step uses \(\log u\le u-1\) twice: \(q\log\frac qp\le\frac{q(q-p)}{p}\) and \((1-q)\log\frac{1-q}{1-p}\le\frac{(1-q)(p-q)}{1-p}\), whose sum is \(\frac{(q-p)^2}{p(1-p)}\). In our situation \((j-Rp)^2/(Rp)=O\left(N^4p^2/(pN\cdot N^2p)\right)=O(N)\) and \(\log(R+1)=O(\log N)\), so each of the \(2^k+\binom{2^k}{2}\) probabilities is at least \(\exp(-C_0N)\) for a constant \(C_0=C_0(\theta,k,T)\), and hence, with \(C_1:=(2^k+\binom{2^k}{2})C_0\), \[\label{eq:m-lower} P_{\Pi,p}\left[\{m\}\right]\ge \exp(-C_1N).\]

Step 2: a large set \(\mathcal{E}_0\) of good arrays. Let \(\mathcal E_0\) be the set of arrays \(\mathbf d\in\mathcal{A}(\Pi)\) with \(m(\Pi,\mathbf d)=m\) and \[\label{eq:E0-window} \left|\mathbf d[x,t]-\frac{m[s,t]}{n[s]}\right|\le \frac{0.01}{T2^k}\sqrt{pN} \qquad\text{for every }s,t\in\{0,1\}^k\text{ and }x\in\Pi[s].\] Every array in \(\mathcal E_0\) satisfies \(\mathcal{I}_\Pi\). Indeed, fix \(s\in\{0,1\}^k\), \(x\in\Pi[s]\), and \(1\le r\le k-1\). Summing (B.9) over the \(2^k\) values of \(t\), \[\left|\sum_{t\in\{0,1\}^k}(-1)^{t[r-1]}\mathbf d[x,t]-\frac{1}{n[s]}\sum_{t\in\{0,1\}^k}(-1)^{t[r-1]}m[s,t]\right|\le\frac{0.01}{T}\sqrt{pN},\] while (LA5) together with \(n[s]\le N\) gives \[\left|\frac{1}{n[s]}\sum_{t\in\{0,1\}^k}(-1)^{t[r-1]}m[s,t]\right|\ge\frac{1}{n[s]}\cdot T^{-1}\frac{N^2p}{\sqrt{pN}}\ge T^{-1}\sqrt{pN},\] with the sign of the sum equal to \((-1)^{s[r]}\). Hence \(\sum_{t}(-1)^{t[r-1]}\mathbf d[x,t]\) is nonzero with sign \((-1)^{s[r]}\), which is exactly the \(r\)th inequality in \(\mathcal{I}_s(\mathbf d[x,\bullet])\) (both the weak and the strict form). Every array in \(\mathcal E_0\) also satisfies \(\kappa_p\): by (LA2) and (LA3), \(|m[s,t]/n[s]-p\,n[t]|\le TN^2p/(\sqrt{pN}\,n[s])\le T^2\sqrt{pN}\), so (B.9) gives \(|\mathbf d[x,t]-p\,n[t]|\le(T^2+0.01)\sqrt{pN}\le(pN)^{4/7}\) for all sufficiently large \(N\). Finally, squaring and summing (B.9) over \(x\in\Pi[s]\) gives \(\sum_{x\in\Pi[s]}(\mathbf d[x,t]-m[s,t]/n[s])^2\le 10^{-4}pN^2\), so every array in \(\mathcal E_0\) satisfies \(\Gamma_1\), and hence \(\Gamma_{C}\) for every \(C\ge1\). In summary, \[\label{eq:E0-inclusion} \mathcal{E}_0\subseteq\{m\}\cap\mathcal{I}_\Pi\cap\kappa_p\cap\Gamma_1\subseteq\{m\}\cap\mathcal{I}_\Pi\cap\kappa_p\cap\Gamma_{C}\qquad(C\ge1),\] and by Lemma B.1 every array in \(\mathcal{E}_0\) is graphical.

Step 3: lower bound for the denominator of (B.7). We first lower bound \(\mathsf{G}_{\Pi,m}(\mathcal{E}_0)\) by summing pointwise bounds over \(\mathcal{E}_0\). We claim that, under the law \(\mathsf{R}_{\Pi,\lambda}(\cdot\mid\{m\})\), each array in \(\mathcal E_0\) has probability at least \[\label{eq:E0-point} \mathsf{R}_{\Pi,\lambda}\left(\mathbf{d}\mid\{m\}\right)\ge(pN)^{-2^kN/2}\exp(-C_2N)\qquad\text{for every }\mathbf{d}\in\mathcal{E}_0,\] with \(C_2\) depending only on \(\theta,k,T\). To see this, fix \(\mathbf{d}\in\mathcal{E}_0\). Since \(\mathbf{d}\in\{m\}\), conditioning can only increase its probability, \(\mathsf{R}_{\Pi,\lambda}(\mathbf{d}\mid\{m\})\ge\mathsf{R}_{\Pi,\lambda}(\mathbf{d})\), and by the product structure of \(\mathsf{R}_{\Pi,\lambda}\), \[\mathsf{R}_{\Pi,\lambda}(\mathbf{d})=\prod_{s\in\{0,1\}^k}\prod_{x\in\Pi[s]}\prod_{t\in\{0,1\}^k}\mathbb{P}\left[\mathrm{Bin}\left(n[t]-\mathbb{1}_{s=t},\lambda[s,t]\right)=\mathbf{d}[x,t]\right],\] a product of \(2^kN\) binomial point probabilities. Each of them is a point probability at a bounded number of standard deviations from the mean: by (B.9), (LA2), (LA3), and (LA6), \[\left|\mathbf{d}[x,t]-p\,n[t]\right|\le\left|\mathbf{d}[x,t]-\frac{m[s,t]}{n[s]}\right|+\left|\frac{m[s,t]}{n[s]}-p\,n[t]\right|\le(0.01+T^2)\sqrt{pN},\] while the parameters \(n':=n[t]-\mathbb{1}_{s=t}\) and \(p':=\lambda[s,t]\) of the binomial satisfy \(|n'-n[t]|\le1\) and \(|p'-p|\le Tp/\sqrt{pN}\). We may therefore apply Lemma A.5 with its \(n\) equal to \(n[t]\) (note \(p\in(T'^{-1}n[t]^{-\theta},T'n[t]^{-\theta})\) for \(T':=T^{1+\theta}\), by (LA2)), its \((n',p')\) as above, and \(\xi:=\mathbf{d}[x,t]-p\,n[t]\) in the role of the variable \(x\) of the lemma; by the previous display, \(\xi\) lies in the window \(|\xi|\le\sqrt{p\,n[t]}\log n[t]\) of the lemma. In its second formula the parameter \(\alpha=\sqrt{pn}\log\left(p'(n'-pn)/((1-p')pn)\right)\) is bounded by a constant depending only on \(T\), because \(p'/p=1+O(1/\sqrt{pN})\) and \((n'-pn)/((1-p')n)=1+O(p+1/n)\); and the normalization satisfies \(\mathcal{N}_2=(1+o(1))(2\pi p\,n[t])^{-1/2}\), as one sees by summing the formula over the window (which carries all but \(N^{-\omega(1)}\) of the mass, by Chernoff’s inequality). Hence \[\begin{aligned} \mathbb{P}\left[\mathrm{Bin}\left(n[t]-\mathbb{1}_{s=t},\lambda[s,t]\right)=\mathbf{d}[x,t]\right] &\ge\frac{1+o(1)}{\sqrt{2\pi p\,n[t]}}\exp\left(-\frac{\left((0.01+T^2)\sqrt{pN}+|\alpha|\sqrt{p\,n[t]}\right)^2}{2p\,n[t]}\right)\\ &\ge\frac{c}{\sqrt{pN}} \end{aligned}\] for a constant \(c=c(\theta,k,T)>0\), where we used \(T^{-1}N\le n[t]\le N\) in the last step. Taking the product over the \(2^kN\) entries gives (B.11) with \(C_2:=2^k\log(1/c)\).

Next we count \(\mathcal{E}_0\). An array \(\mathbf{d}\) with \(m(\Pi,\mathbf{d})=m\) is specified by choosing, for each of the \(2^{2k}\) ordered pairs \((s,t)\), the integer sequence \((\mathbf{d}[x,t])_{x\in\Pi[s]}\) with sum \(m[s,t]\). Fix \((s,t)\), write \(w:=0.01\sqrt{pN}/(T2^k)\), and write \(m[s,t]=q\,n[s]+r\) with \(q\in\mathbb{Z}\) and \(0\le r<n[s]\). Let \(\mathbf{b}\) be the sequence taking the value \(q+1\) on \(r\) fixed elements of \(\Pi[s]\) and \(q\) on the remaining \(n[s]-r\); then \(\sum_x\mathbf{b}[x]=m[s,t]\) and \(|\mathbf{b}[x]-m[s,t]/n[s]|\le1\) for every \(x\). For every integer sequence \((y_x)_{x\in\Pi[s]}\) with \(\sum_xy_x=0\) and \(|y_x|\le w-1\), the sequence \(\mathbf{b}+y\) has sum \(m[s,t]\) and satisfies (B.9); its entries lie in \([0,n[t]-\mathbb{1}_{s=t}]\) for all sufficiently large \(N\), because they are within \(w\) of \(m[s,t]/n[s]=p\,n[t]+O(\sqrt{pN})\), so the resulting arrays lie in \(\mathcal{A}(\Pi)\) and hence in \(\mathcal{E}_0\). By Lemma A.11, applied with \(n=n[s]\), with its constant \(T\) equal to \(T^{1+\theta}\) (so that its hypothesis on \(p\) holds, because \(n[s]\in[T^{-1}N,N]\) by (LA2)), and with its parameter \(C\) equal to \(c_0:=0.005/(T2^k)\) (so that \(c_0\sqrt{n[s]p}\le w-1\) for large \(N\)), the number of such sequences \(y\) is at least \[\exp\left(-C_{A.11}(\theta,T^{1+\theta},c_0)\,n[s]\right)\left(\sqrt{n[s]p}\right)^{n[s]}\ge\exp\left(-\left(C_{A.11}(\theta,T^{1+\theta},c_0)+\tfrac12\log T\right)N\right)(pN)^{n[s]/2},\] using \(T^{-1}N\le n[s]\le N\). Multiplying over the \(2^{2k}\) ordered pairs \((s,t)\), and using \(\sum_{s,t}n[s]=2^kN\), we obtain, with \(C_3:=2^{2k}(C_{A.11}(\theta,T^{1+\theta},c_0)+\tfrac12\log T)\), \[\label{eq:E0-count} |\mathcal{E}_0|\ge(pN)^{2^kN/2}\exp(-C_3N).\] Now, by (B.10), every \(\mathbf{d}\in\mathcal{E}_0\) is a graphical array satisfying \(m(\Pi,\mathbf{d})=m\), \(\kappa_p\), and \(\Gamma_1\), so Lemma B.2(ii), applied with its parameter \(C_\Gamma\) equal to \(1\), gives \(\mathsf{G}_{\Pi,m}(\mathbf{d})\ge C_\ast^{-1}\mathsf{R}_{\Pi,\lambda}(\mathbf{d}\mid\{m\})\) for every \(\mathbf{d}\in\mathcal{E}_0\), where \(C_\ast:=C'_{B.2}(\theta,k,T,1)\). Summing this over \(\mathbf{d}\in\mathcal{E}_0\) and using (B.11) and (B.12), \[\label{eq:G-E0} \begin{aligned} \mathsf{G}_{\Pi,m}(\mathcal{E}_0)=\sum_{\mathbf{d}\in\mathcal{E}_0}\mathsf{G}_{\Pi,m}(\mathbf{d}) &\ge C_\ast^{-1}\,|\mathcal{E}_0|\,(pN)^{-2^kN/2}e^{-C_2N}\\ &\ge C_\ast^{-1}e^{-(C_2+C_3)N} \ge e^{-C_4N},\qquad C_4:=C_2+C_3+\log C_\ast. \end{aligned}\] Unwinding the definition of \(\mathsf{G}_{\Pi,m}\) through (B.6) and using (B.8), \[\label{eq:P-E0} P_{\Pi,p}\left[\mathcal{E}_0\right]=P_{\Pi,p}\left[\mathcal{E}_0\cap\{m\}\right]=\mathsf{G}_{\Pi,m}(\mathcal{E}_0)\,P_{\Pi,p}\left[\{m\}\right]\ge e^{-C_4N}e^{-C_1N}=:e^{-C_5N}.\] Finally, by (B.10) the denominator of (B.7) satisfies \[\label{eq:gamma-denominator} P_{\Pi,p}\left[\mathcal{I}_\Pi\cap\kappa_p\cap\{m\}\right]\ge P_{\Pi,p}\left[\mathcal{E}_0\right]\ge e^{-C_5N}.\] The constant \(C_5=C_1+C_4\) depends only on \(\theta,k,T,\phi\); in particular it does not depend on \(C_{B.3}\).

Step 4: upper bound for the numerator of (B.7), and choice of \(C_{B.3}\). For \(C>0\), on the event \(\{m\}\) the assertions \(\Gamma_{C}(\mathbf{D})=\Gamma_{C,p}(\Pi,m,\mathbf{D})\) and \(\Gamma_{C,p}(\Pi,m(\Pi,\mathbf{D}),\mathbf{D})\) coincide, and the latter is the assertion that, for every internal block pair \(\{s,s\}\) and every bipartite block pair \(\{s,t\}\), the corresponding block-pair degree sequences of \(G\) have sum of squared deviations from their means at most \(CpN^2\). We retain the event \(\kappa_p\) in the numerator because it supplies the truncation hypothesis of Lemma A.10: \(\kappa_p\) asserts that \(|\mathbf{D}[x,t]-p\,n[t]|\le(pN)^{4/7}\) for all \(x\in V\) and \(t\in\{0,1\}^k\), and \((pN)^{4/7}\le p\,n[t]\) for all sufficiently large \(N\) because \(n[t]\ge T^{-1}N\) by (LA2). Under \(P_{\Pi,p}\), the graph induced on \(\Pi[s]\) is distributed as \(\mathbb{G}(n[s],p)\) and the bipartite graph between \(\Pi[s]\) and \(\Pi[t]\) as \(\mathbb{G}(n[s],n[t],p)\). Apply Lemma A.10(i) to each internal block pair, with \(n=n[s]\), and Lemma A.10(ii) to each bipartite block pair, with \(n=n[t]\) and \(\ell=n[s]\), in both cases with the constant \(T\) of the lemma replaced by \(T^{1+\theta}\) (so that its hypotheses on \(p\) and on \(\ell\) hold) and with \(K:=T(2C_5+2)\), and put \(C_{B.3}:=\max\{1,C_{A.10}(\theta,T^{1+\theta},K)\}\), which depends only on \(\theta,k,T,\phi\). On \(\kappa_p\) the truncation hypotheses of the lemma hold, by the previous paragraph. Since \(n[s],n[t]\ge T^{-1}N\), each application has failure probability at most \(e^{-KN/T}=e^{-(2C_5+2)N}\), and \(C_{B.3}pn[s]^2\le C_{B.3}pN^2\) (respectively \(C_{B.3}pn[s]n[t]\le C_{B.3}pN^2\)), so a union bound over the \(2^k+\binom{2^k}{2}\le2^{2k}\) blocks and block pairs gives \[\label{eq:gamma-numerator} P_{\Pi,p}\left[\Gamma_{C_{B.3}}^c\cap\mathcal{I}_\Pi\cap\kappa_p\cap\{m\}\right] \le P_{\Pi,p}\left[\Gamma_{C_{B.3},p}(\Pi,m(\Pi,\mathbf{D}),\mathbf{D})^c\cap\kappa_p\right] \le2^{2k}e^{-(2C_5+2)N}\le e^{-(C_5+1)N}\] for all sufficiently large \(N\). Inserting (B.15) and (B.16) into (B.7), \[\mathsf{G}_{\Pi,m}\left(\Gamma_{C_{B.3}}^c\mid\mathcal{I}_\Pi\cap\kappa_p\right) =\frac{P_{\Pi,p}\left[\Gamma_{C_{B.3}}^c\cap\mathcal{I}_\Pi\cap\kappa_p\cap\{m\}\right]}{P_{\Pi,p}\left[\mathcal{I}_\Pi\cap\kappa_p\cap\{m\}\right]} \le\frac{e^{-(C_5+1)N}}{e^{-C_5N}}=e^{-N}.\] ◻

Proof. Abbreviate \(\Gamma:=\Gamma_{C_{B.3}(\theta,k,T,\phi),p}(\Pi,m,\cdot)\), \(\kappa_p:=\kappa_p(\Pi,\cdot)\), and \(\{m\}:=\{\mathbf{D}\in\mathcal{A}(\Pi):m(\Pi,\mathbf{D})=m\}\), and write \(C_0:=C_{B.2}(\theta,k,T)\) for the constant of the weak comparison Lemma B.2(i). By Bayes’ rule, \[\mathsf{R}_{\Pi,\lambda}\left(\Gamma^c\mid \mathcal{I}_\Pi,\kappa_p,\{m\}\right) =\frac{\mathsf{R}_{\Pi,\lambda}\left(\Gamma^c\cap\mathcal{I}_\Pi\cap\kappa_p\mid\{m\}\right)}{\mathsf{R}_{\Pi,\lambda}\left(\mathcal{I}_\Pi\cap\kappa_p\mid\{m\}\right)}.\] Both the numerator and the denominator are sums of \(\mathsf{R}_{\Pi,\lambda}(\mathbf{d}\mid\{m\})\) over arrays \(\mathbf{d}\in\{m\}\cap\kappa_p\), and for every such array the weak comparison gives \[\exp\{-C_0(pN)^{2/7}\}\,\mathsf{G}_{\Pi,m}(\mathbf{d})\le\mathsf{R}_{\Pi,\lambda}(\mathbf{d}\mid\{m\})\le\exp\{C_0(pN)^{2/7}\}\,\mathsf{G}_{\Pi,m}(\mathbf{d}).\] Summing the upper bound over the arrays in the numerator and the lower bound over the arrays in the denominator, and then applying Bayes’ rule for \(\mathsf{G}_{\Pi,m}\) and Lemma B.3, \[\begin{aligned} \mathsf{R}_{\Pi,\lambda}\left(\Gamma^c\mid \mathcal{I}_\Pi,\kappa_p,\{m\}\right) &\le\exp\{2C_0(pN)^{2/7}\}\,\frac{\mathsf{G}_{\Pi,m}\left(\Gamma^c\cap\mathcal{I}_\Pi\cap\kappa_p\right)}{\mathsf{G}_{\Pi,m}\left(\mathcal{I}_\Pi\cap\kappa_p\right)}\\ &=\exp\{2C_0(pN)^{2/7}\}\,\mathsf{G}_{\Pi,m}\left(\Gamma^c\mid \mathcal{I}_\Pi\cap\kappa_p\right) \le\exp\{2C_0(pN)^{2/7}-N\}, \end{aligned}\] which is \(o(1)\) because \((pN)^{2/7}=o(N)\). ◻

Proof. By (LA7) and Fact 3.6, under \(\mathsf{R}_{\Pi,\lambda}(\cdot\mid\mathcal{I}_\Pi)\) the rows in a fixed part \(\Pi[s]\) are independent copies of \(A_{s,\bullet}\mid\mathcal{I}_s(A_{s,\bullet})\), and rows in different parts are independent. By (LA8), \[n[s]\,\mathbb E[A_{s,t}\mid\mathcal I_s(A_{s,\bullet})]=m[s,t]\] for every \(s,t\in\{0,1\}^k\). Hence the event \(m(\Pi,\mathbf D)=m\) is the intersection, over \(s\in\{0,1\}^k\), of the independent events \[\label{eq:exact-total-s} \sum_{x\in\Pi[s]}\mathbf D[x,\bullet]=m[s,\bullet],\] each of which asks that the sum of \(n[s]\) independent copies of the conditioned row vector \(A_{s,\bullet}\mid\mathcal I_s(A_{s,\bullet})\) equal its mean \(n[s]\,\mathbb E[A_{s,\bullet}\mid\mathcal I_s(A_{s,\bullet})]=m[s,\bullet]\), an integer vector. It therefore suffices to show that each event (B.17) has probability at least \((N^2p)^{-C_s}\) under \(\mathsf R_{\Pi,\lambda}(\cdot\mid\mathcal I_\Pi)\) with \(C_s:=2^{k-1}+1\), and then to multiply over the \(2^k\) values of \(s\).

Fix \(s\in\{0,1\}^k\) and put \(d:=2^k\). A nondegenerate \(d\)-dimensional lattice sum with fluctuation scale \(\sqrt{N^2p}\) suggests mass of order \((N^2p)^{-d/2}\) at its integral mean. Theorem B.5 gives this bound for the conditioned binomial rows; we verify its hypotheses below. We apply Theorem B.5 with \(d=2^k\), with its \(n\) equal to \(N\), its \(m\) equal to \(n[s]\), and with \(\eta_t:=n[t]-\mathbb{1}_{s=t}\) and \(q_t:=\lambda[s,t]\) for \(t\in\{0,1\}^k\), so that its \(A_t\sim\mathrm{Bin}(\eta_t,q_t)\) is exactly \(A_{s,t}\). The \(k-1\) inequalities defining \(\mathcal I_s(A_{s,\bullet})\) are of the form \(\mu_r\cdot A_{s,\bullet}\ge'_r0\) for \(1\le r\le k-1\), where \(\mu_r\in\{\pm1\}^{\{0,1\}^k}\) has entries \(\mu_r[t]=(-1)^{s[r]}(-1)^{t[r-1]}\) and \(\ge'_r\in\{\ge,>\}\) is determined by the pair \(s[r-1]s[r]\); let \(M\) be the matrix with rows \(\mu_1,\ldots,\mu_{k-1}\). Distinct rows of \(M\) are orthogonal: for \(r\ne r'\), flipping bit \(r-1\) of \(t\) is a bijection of \(\{0,1\}^k\) that negates \(\mu_r[t]\mu_{r'}[t]\), so \(\sum_t\mu_r[t]\mu_{r'}[t]=0\). We now verify the remaining hypotheses of Theorem B.5, with its constant \(T\) replaced by \(2T\). By (LA2), we have \(\eta_t\in((2T)^{-1}N,2TN)\) and \(n[s]\in((2T)^{-1}N,2TN)\), and, for each \(1\le r\le k-1\), \[\left|(M\eta)_r\right|=\left|\sum_{t\in\{0,1\}^k}(-1)^{t[r-1]}n[t]-(-1)^{s[r-1]}\right|\le T\frac{N}{\sqrt{pN}}+1<2T\frac{N}{\sqrt{pN}},\] where the term \((-1)^{s[r-1]}\) comes from the indicator \(\mathbb{1}_{s=t}\) in \(\eta_t\). By (LA6), \(q_t=\lambda[s,t]\in(p-Tp/\sqrt{pN},p+Tp/\sqrt{pN})\). Finally, the integrality hypothesis \(n[s]\,\mathbb E[A_{s,\bullet}\mid MA_{s,\bullet}\ge'0]\in\mathbb Z^{d}\) of Theorem B.5 is exactly (LA8): the event \(MA_{s,\bullet}\ge'0\) is \(\mathcal I_s(A_{s,\bullet})\), and \(n[s]\,\mathbb E[A_{s,t}\mid\mathcal I_s(A_{s,\bullet})]=m[s,t]\in\mathbb Z\). Therefore Theorem B.5 gives, with \(d=2^k\), \[\begin{aligned} \mathbb P\left[\sum_{x\in\Pi[s]}\mathbf D[x,\bullet]=m[s,\bullet]\ \middle|\ \mathcal I_s(\mathbf D[x,\bullet])\text{ for all }x\in\Pi[s]\right] &=\Omega\left((N^2p)^{-2^{k-1}}\right)\\ &\ge (N^2p)^{-2^{k-1}-1}=(N^2p)^{-C_s} \end{aligned}\] for all sufficiently large \(N\), where the implied constant in \(\Omega(\cdot)\) depends only on \(\theta,k,T,\phi\) and is absorbed by the extra factor \((N^2p)^{-1}\). Multiplying over the \(2^k\) values of \(s\) gives the result with \(C_{B.6}:=\sum_sC_s=2^k(2^{k-1}+1)\). ◻

Proof. For fixed \(x\in\Pi[s]\) and \(t\in\{0,1\}^k\), the tilt bound (LA6) gives \(|\mathbb{E}A_{s,t}-p|\Pi[t]||\le|\Pi[t]|\cdot Tp/\sqrt{pN}+\lambda[s,t]\le T\sqrt{pN}+2p\), so Chernoff’s inequality gives \[\mathbb P\left[\left|A_{s,t}-p|\Pi[t]|\right|>(pN)^{4/7}\right]=O(N^{-\omega(1)}).\] By (LA7) and Fact 3.6, under \(\mathsf{R}_{\Pi,\lambda}(\cdot\mid\mathcal{I}_\Pi)\) the row \(\mathbf{D}[x,\bullet]\) has the law of \(A_{s,\bullet}\) conditioned on \(\mathcal{I}_s(A_{s,\bullet})\). Hence, by Bayes’ rule and (LA7), \[\begin{aligned} \mathsf{R}_{\Pi,\lambda}\left(\left|\mathbf{D}[x,t]-p|\Pi[t]|\right|>(pN)^{4/7}\ \middle|\ \mathcal{I}_\Pi\right) &=\frac{\mathbb P\left[\left|A_{s,t}-p|\Pi[t]|\right|>(pN)^{4/7},\ \mathcal I_s(A_{s,\bullet})\right]}{\mathbb P\left[\mathcal I_s(A_{s,\bullet})\right]}\\ &\le\frac{\mathbb P\left[\left|A_{s,t}-p|\Pi[t]|\right|>(pN)^{4/7}\right]}{\phi} =O(N^{-\omega(1)}). \end{aligned}\] A union bound over the \(2^kN\) pairs \((x,t)\in V\times\{0,1\}^k\) gives \[\mathsf{R}_{\Pi,\lambda}\left(\kappa_p(\Pi,\mathbf{D})^c\mid\mathcal{I}_\Pi\right)\le2^kN\cdot O(N^{-\omega(1)})=O(N^{-\omega(1)}),\] which is the first estimate. For the second, Bayes’ rule and Lemma B.6 give \[\begin{aligned} \mathsf{R}_{\Pi,\lambda}\left(\kappa_p(\Pi,\mathbf{D})^c\mid\mathcal{I}_\Pi,m(\Pi,\mathbf{D})=m\right) &=\frac{\mathsf{R}_{\Pi,\lambda}\left(\kappa_p(\Pi,\mathbf{D})^c\cap\{m(\Pi,\mathbf{D})=m\}\mid\mathcal{I}_\Pi\right)}{\mathsf{R}_{\Pi,\lambda}\left(m(\Pi,\mathbf{D})=m\mid\mathcal{I}_\Pi\right)}\\ &\le\frac{\mathsf{R}_{\Pi,\lambda}\left(\kappa_p(\Pi,\mathbf{D})^c\mid\mathcal{I}_\Pi\right)}{(N^2p)^{-C_{B.6}(\theta,k,T,\phi)}}\\ &=O\left((N^2p)^{C_{B.6}(\theta,k,T,\phi)}N^{-\omega(1)}\right)=O(N^{-\omega(1)}). \end{aligned}\] ◻

Proof. We prove (i); the proof of (ii) is similar and simpler. (For (ii), the ratio equals \(\frac{(\ell n)!}{(\ell n-n)!}\cdot\frac{(m-s_v)!}{m!}\cdot\frac{(\ell n-m-(n-s_v))!}{(\ell n-m)!}\), whose three logarithms are \(n\log(\ell n)-\frac{n}{2\ell}+O(1/\ell)\), \(-s_v\log m+O(p)\), and \(-(n-s_v)\log(\ell n-m)+\frac{n}{2\ell}+O(p)\) by the same expansions as below; summing them and expanding \(\frac{m}{p\ell n}=1+O(1/\sqrt{pn})\) exactly as in the last step below gives \(-s_v\log p+pn+O(\log n)\).)

Note that \[\begin{aligned} \frac{\binom{(n-1)(n-2)/2}{m-d_v}}{\binom{n(n-1)/2}{m}} &= \left[\frac{\left[\frac{n(n-1)}{2}\right]!}{\left[\frac{n(n-1)}{2}-(n-1)\right]!}\right]^{-1}\left[\frac{m!}{(m-d_v)!}\right]\left[\frac{\left[\frac{n(n-1)}{2}-m\right]!}{\left[\frac{n(n-1)}{2}-m-(n-1-d_v)\right]!}\right]. \end{aligned}\] We find that \[\begin{aligned} \log\left[\frac{\left[\frac{n(n-1)}{2}\right]!}{\left[\frac{n(n-1)}{2}-(n-1)\right]!}\right] &= \sum_{i=0}^{n-2}\log\left(\frac{n(n-1)}{2}-i\right) \\ &= (n-1)\log\left(\frac{n(n-1)}{2}\right) + \sum_{i=0}^{n-2}\log\left(1-\frac{i}{\frac{n(n-1)}{2}}\right) \\ &= (n-1)\log\left(\frac{n(n-1)}{2}\right) - \sum_{i=0}^{n-2}\frac{i}{\frac{n(n-1)}{2}} + O(1/n) \\ &= (n-1)\log\left(\frac{n(n-1)}{2}\right) - 1 + O(1/n) \end{aligned}\] and \[\begin{aligned} \log\left[\frac{m!}{(m-d_v)!}\right] &= d_v\log m + \sum_{i=0}^{d_v-1}\log\left(1-\frac{i}{m}\right) \\ &= d_v\log m + O(d_v^2/m) \\ &= d_v\log m + O(p) \end{aligned}\] and \[\begin{aligned} &\log\left[\frac{\left[\frac{n(n-1)}{2}-m\right]!}{\left[\frac{n(n-1)}{2}-m-(n-1-d_v)\right]!}\right] \\ &\quad= \sum_{i=0}^{n-2-d_v}\log\left(\frac{n(n-1)}{2}-m-i\right) \\ &\quad= (n-1-d_v)\log\left(\frac{n(n-1)}{2}-m\right) + \sum_{i=0}^{n-2-d_v}\log\left(1-\frac{i}{\frac{n(n-1)}{2}-m}\right) \\ &\quad= (n-1-d_v)\log\left(\frac{n(n-1)}{2}-m\right) - \sum_{i=0}^{n-2-d_v}\frac{i}{\frac{n(n-1)}{2}-m} + O(1/n) \\ &\quad= (n-1-d_v)\log\left(\frac{n(n-1)}{2}-m\right) - 1 + O(p), \end{aligned}\] so \[\frac{\binom{(n-1)(n-2)/2}{m-d_v}}{\binom{n(n-1)/2}{m}} = (1+O(p))\left(\frac{n(n-1)}{2}\right)^{1-n}m^{d_v}\left(\frac{n(n-1)}{2}-m\right)^{n-1-d_v}.\] We similarly derive \[\frac{\binom{(n-1)(n-2)}{2m-2d_v}}{\binom{n(n-1)}{2m}} = (1+O(p))\left(n(n-1)\right)^{3-2n}(2m)^{2d_v}\left(n(n-1)-2m\right)^{2n-3-2d_v}.\] Thus, \[\frac{\binom{(n-1)(n-2)/2}{m-d_v}\binom{(n-1)(n-2)}{2m-2d_v}^{-1}}{\binom{n(n-1)/2}{m}\binom{n(n-1)}{2m}^{-1}} = (1+O(p))\left[\frac{n(n-1)}{2m}\right]^{d_v}\left[\frac{\frac{n(n-1)}{2}}{\frac{n(n-1)}{2}-m}\right]^{n-2-d_v}.\] We see that \[\begin{aligned} \log\left(\left[\frac{n(n-1)}{2m}\right]^{d_v}\right) &= d_v\log\left(\frac{n^2}{2m}\right) + O(p) \\ &= -d_v\log p - d_v\log\left(\frac{2m}{pn^2}\right) + O(p) \\ &= -d_v\log p - d_v\left[\frac{2m}{pn^2}-1\right] + O(1) \\ &= -d_v\log p - \frac{2m}{n} + pn + O(\log n), \end{aligned}\] where in the third line we used \(\frac{2m}{pn^2}-1=O(1/\sqrt{pn})\), so that \(d_v\left(\frac{2m}{pn^2}-1\right)^2=O(1)\), and in the last line we wrote \(d_v=pn+\beta_v\sqrt{pn}\) with \(\beta_v:=(d_v-pn)/\sqrt{pn}\), so that \(|\beta_v|\le\log n\) by hypothesis and \(\beta_v\sqrt{pn}\left(\frac{2m}{pn^2}-1\right)=O(\log n)\); and \[\begin{aligned} \log\left(\left[\frac{\frac{n(n-1)}{2}}{\frac{n(n-1)}{2}-m}\right]^{n-2-d_v}\right) &= (n-2-d_v)\log\left[\frac{1}{1-\frac{2m}{n(n-1)}}\right] \\ &= \frac{2m}{n} + O(np^2). \end{aligned}\] Adding these two directly implies the desired result. ◻

Proof. We prove only (i); the proof of (ii) is similar but uses Theorem A.4 instead of Theorem A.3, and Lemma C.3(ii) instead of Lemma C.3(i).

Let \(\mathbb{P}_{\mathbf{d}}\) denote the uniform distribution on graphs with degree sequence \(\mathbf{d}\). Given \(R\subset[n]\setminus\{v\}\) of size \(d_v\), we begin by computing \(\mathbb{P}_{G\sim\mathbb{P}_{\mathbf{d}}}[N_G(v) = R]\). To this end, define \[\mathbf{d}_R = (d_w - \mathbf{1}_{w\in R})_{w\in[n]\setminus\{v\}}.\] Note that \(2m = \sum_{i\in[n]}d_i\) and let \(m_R = m-d_v\), and let \(d=2m/n\) and \(d_R = 2m_R/(n-1)\). Note that by Bayes’ theorem, \[\mathbb{P}_{G\sim\mathbb{P}_\mathbf{d}}[N_G(v) = R] = \mathbb{P}_{G\sim G(n,m)}[N_G(v)=R]\frac{\mathbb{P}_{G(n-1,m_R)}[\mathbf{d}_R]}{\mathbb{P}_{G(n,m)}[\mathbf{d}]} = \frac{\binom{(n-1)(n-2)/2}{m-d_v}}{\binom{n(n-1)/2}{m}}\frac{\mathbb{P}_{G(n-1,m_R)}[\mathbf{d}_R]}{\mathbb{P}_{G(n,m)}[\mathbf{d}]},\] where \(\mathbb{P}_{G(n,m)}\) and \(\mathbb{P}_{G(n-1,m_R)}\) are the degree-sequence laws of Definition A.1: the graphs with degree sequence \(\mathbf{d}\) and \(N_G(v)=R\) correspond bijectively to the graphs on \([n]\setminus\{v\}\) with degree sequence \(\mathbf{d}_R\), and the latter number \(\binom{(n-1)(n-2)/2}{m-d_v}\mathbb{P}_{G(n-1,m_R)}[\mathbf{d}_R]\), while the former are \(\binom{n(n-1)/2}{m}\mathbb{P}_{G(n,m)}[\mathbf{d}]\) in total. We compute the remaining two probabilities by appealing to Theorem A.3. Indeed, note that \(\mu = \frac{d}{n-1} = p + O(p/\sqrt{pn})\), and \(\gamma_2(\mathbf{d}) = O(p\log^2 n)\), and similarly \(\mu_R = \frac{d_R}{n-2} = p + O(p/\sqrt{pn})\) and \(\gamma_2(\mathbf{d}_R) = O(p\log^2 n)\). Thus, by Theorem A.3, we have \[\begin{aligned} \mathbb{P}_{G\sim\mathbb{P}_\mathbf{d}}[N_G(v) = R] &= \exp\left(O(\log^4 n)\right)\frac{\binom{(n-1)(n-2)/2}{m-d_v}}{\binom{n(n-1)/2}{m}}\frac{\frac{\prod_{w\in [n]\setminus\{v\}}\binom{n-2}{d_w-\mathbf{1}_{w\in R}}}{\binom{(n-1)(n-2)}{2m-2d_v}}}{\frac{\prod_{w\in[n]}\binom{n-1}{d_w}}{\binom{n(n-1)}{2m}}} \\ &= \exp\left(O(\log^4 n)\right)\frac{\binom{(n-1)(n-2)/2}{m-d_v}\binom{(n-1)(n-2)}{2m-2d_v}^{-1}}{\binom{n(n-1)/2}{m}\binom{n(n-1)}{2m}^{-1}}\frac{\prod_{w\in [n]\setminus\{v\}}\binom{n-2}{d_w-\mathbf{1}_{w\in R}}}{\prod_{w\in[n]}\binom{n-1}{d_w}}. \end{aligned}\] Note that \[\begin{aligned} \frac{\prod_{w\in [n]\setminus\{v\}}\binom{n-2}{d_w-\mathbf{1}_{w\in R}}}{\prod_{w\in[n]}\binom{n-1}{d_w}} &= \frac{1}{\binom{n-1}{d_v}}\prod_{i\in R}\frac{d_i}{n-1}\prod_{i\in[n]\setminus(\{v\}\cup R)}\frac{n-1-d_i}{n-1} \\ &= \frac{\exp(O(1))}{\binom{n-1}{d_v}}p^{d_v}(1-p)^{n-1-d_v}\prod_{i\in R}\left[1 + \frac{\beta_i}{\sqrt{pn}}\right]\prod_{i\in [n]\setminus(\{v\}\cup R)}\left[1 - \frac{\sqrt{pn}}{n}\beta_i\right] \\ &= \frac{\exp(O(\log^2 n))}{\binom{n-1}{d_v}}p^{d_v}e^{-np}\exp\left[\sum_{i\in R}\frac{\beta_i}{\sqrt{pn}} - \sum_{i\in [n]\setminus(\{v\}\cup R)}\frac{\sqrt{pn}}{n}\beta_i\right], \end{aligned}\] so by Lemma C.3(i), we have \[\mathbb{P}_{G\sim\mathbb{P}_\mathbf{d}}[N_G(v) = R] = \exp\left(O(\log^4 n)\right)\frac{\exp(\Lambda_R)}{\binom{n-1}{d_v}}.\] Now pick \(R_1\) uniformly from \(\binom{S\setminus\{v\}}{t}\) and \(R_2\) uniformly from \(\binom{[n]\setminus(\{v\}\cup S)}{d_v-t}\), and let \(R=R_1\cup R_2\). Under this setup, we have \[\mathbb{P}_{G\sim\mathbb{P}_{\mathbf{d}}}[\deg^G_Sv=t] = \binom{h-\mathbf{1}_S(v)}{t}\binom{n-h-\mathbf{1}_{[n]\setminus S}(v)}{d_v-t}\mathbb{E}_R[\mathbb{P}_{G\sim\mathbb{P}_\mathbf{d}}[N_G(v) = R]],\] so \[\mathbb{P}[\deg^G_Sv=t] = \exp\left(O(\log^4 n)\right)\frac{\binom{h-\mathbf{1}_S(v)}{t}\binom{n-h-\mathbf{1}_{[n]\setminus S}(v)}{d_v-t}}{\binom{n-1}{d_v}}\mathbb{E}_R[\exp(\Lambda_R)],\] as desired. ◻

Proof. Let \(q=s/n\), and let \(Y = \sum_i \zeta_i a_i\), where the \(\zeta_i\) are independent \(\mathrm{Ber}(q)\) random variables. Since \(q\asymp p\), \[\mathbb{E}\left[e^Y\right] \ge \mathbb{P}[\mathrm{Bin}(n,q)=s]\mathbb{E}\left[e^X\right] \ge \Omega(1/\sqrt{pn})\mathbb{E}\left[e^X\right].\] Also, \[\log\mathbb{E}\left[e^Y\right] =\sum_{i=1}^n\log\left(1+q(e^{a_i}-1)\right) =q\sum_{i=1}^n a_i+O\left(q\sum_{i=1}^n a_i^2\right) =\mathbb{E}[X]+O(\log^2 n),\] using \(|a_i|\le T\log n/\sqrt{pn}\). Combining the two displays proves the claim. ◻

Proof. We first record that a smooth map \(h\colon W\to\mathbb{R}^d\) on an open set \(W\subseteq\mathbb{R}^d\) is Lipschitz on every compact \(K\subseteq W\). For \(K=\emptyset\) this is immediate, so assume \(K\ne\emptyset\). Since \(K\) is compact and \(W\) is open there is \(\rho>0\) such that the closed \(\rho\)-neighborhood \(K_\rho:=\{x:\operatorname{dist}(x,K)\le\rho\}\) is contained in \(W\); the derivative \(Dh\) is continuous, hence bounded by some \(L_1\) on the compact set \(K_\rho\). If \(y,z\in K\) and \(|y-z|\le\rho\), the segment from \(y\) to \(z\) lies in \(K_\rho\), and the mean value inequality gives \(|h(y)-h(z)|\le L_1|y-z|\). If \(|y-z|>\rho\), then \(|h(y)-h(z)|\le2\sup_K|h|\le(2\sup_K|h|/\rho)\,|y-z|\). So \(h\) is Lipschitz on \(K\) with constant \(\max\{L_1,2\sup_K|h|/\rho\}\).

Applying this to \(h=f^{-1}\) on \(W=B\) gives the upper bound with some constant \(L'\). For the lower bound, the set \(K':=f^{-1}(K)\) is compact, being the image of a compact set under the continuous map \(f^{-1}\); applying the fact to \(h=f\) on \(W=\mathbb{R}^d\) gives \(L''\) with \(|f(a)-f(b)|\le L''|a-b|\) for \(a,b\in K'\), and taking \(a=f^{-1}(y)\), \(b=f^{-1}(z)\) yields \(|y-z|\le L''|f^{-1}(y)-f^{-1}(z)|\). Take \(L:=\max\{L',L'',1\}\). ◻

Proof. That \(F_{\mathcal{O}}\) is well defined with values in \(\mathcal{O}\) is Lemma A.12. Define \[\Phi\colon\mathbb{R}^d\to\mathbb{R},\qquad\Phi(\vartheta):=\log\int_{\mathcal{O}}\exp\left(\vartheta\cdot x-\tfrac12x^\top\Sigma^{-1}x\right)dx .\] The integrand is bounded by \(\exp(|\vartheta||x|-\frac12\lambda_{\min}|x|^2)\), where \(\lambda_{\min}>0\) is the smallest eigenvalue of \(\Sigma^{-1}\), so the integral converges for every \(\vartheta\), and differentiation under the integral sign (justified by the same Gaussian domination, locally uniformly in \(\vartheta\)) shows that \(\Phi\) is smooth with \[\nabla\Phi(\vartheta)=\mathbb{E}_\vartheta[X],\qquad\nabla^2\Phi(\vartheta)=\mathrm{Cov}_\vartheta(X),\] where \(\mathbb{P}_\vartheta\) denotes the probability measure on \(\mathcal{O}\) with density proportional to \(\exp(\vartheta\cdot x-\frac12x^\top\Sigma^{-1}x)\). Since \[-\tfrac12(x-\gamma)^\top\Sigma^{-1}(x-\gamma)=x\cdot\Sigma^{-1}\gamma-\tfrac12x^\top\Sigma^{-1}x-\tfrac12\gamma^\top\Sigma^{-1}\gamma,\] the law of \(X^\gamma\) conditioned on \(\{X^\gamma\in\mathcal{O}\}\) is \(\mathbb{P}_{\Sigma^{-1}\gamma}\). Hence \[\label{eq:F-gradient} F_{\mathcal{O}}(\gamma)=\nabla\Phi(\Sigma^{-1}\gamma)\qquad\text{and}\qquad DF_{\mathcal{O}}(\gamma)=\nabla^2\Phi(\Sigma^{-1}\gamma)\,\Sigma^{-1}=\mathrm{Cov}(X^\gamma\mid X^\gamma\in\mathcal{O})\,\Sigma^{-1},\] so \(F_{\mathcal{O}}\) is smooth, and its Jacobian is invertible because \(\mathrm{Cov}(X^\gamma\mid X^\gamma\in\mathcal{O})\) is positive definite by Lemma A.12.

Injectivity. By (D.1) and Lemma A.12, \(\nabla^2\Phi\) is positive definite everywhere, so \(\Phi\) is strictly convex. If \(\nabla\Phi(\vartheta)=\nabla\Phi(\vartheta')\) with \(\vartheta\ne\vartheta'\), then the strictly convex function \(t\mapsto\Phi(\vartheta+t(\vartheta'-\vartheta))\) would have equal derivatives at \(t=0\) and \(t=1\), which is impossible. Hence \(\nabla\Phi\) is injective, and so is \(F_{\mathcal{O}}=\nabla\Phi\circ\Sigma^{-1}\).

Surjectivity. Fix \(y\in\mathcal{O}\) and consider the smooth function \(\Psi(\vartheta):=\Phi(\vartheta)-\vartheta\cdot y\). We show that \(\Psi(\vartheta)\to\infty\) as \(|\vartheta|\to\infty\). Since \(\mathcal{O}\) is open there is \(\eta>0\) with \(B(y,2\eta)\subseteq\mathcal{O}\). For a unit vector \(e\) and \(t>0\), the ball \(B(y+\frac32\eta e,\frac12\eta)\) is contained in \(B(y,2\eta)\subseteq\mathcal{O}\) and in the half-space \(\{x:(x-y)\cdot e>\eta\}\), so \[\Psi(te)=\log\int_{\mathcal{O}}\exp\left(t(x-y)\cdot e-\tfrac12x^\top\Sigma^{-1}x\right)dx \ge\log\left(e^{t\eta}\,m_0\right)=t\eta+\log m_0,\] where \[m_0:=\mathrm{vol}\left(B(0,\tfrac12\eta)\right)\inf_{|x-y|\le2\eta}e^{-\frac12x^\top\Sigma^{-1}x}>0\] does not depend on \(e\). Hence \(\Psi\ge t\eta+\log m_0\) on the sphere of radius \(t\), which exceeds \(\Psi(0)\) for \(t\) large. A continuous function on a closed ball attains its minimum; as \(\Psi\) is larger on the boundary of a large ball than at its center, the minimum over the ball is attained at an interior point \(\vartheta^\ast\), where \(\nabla\Psi(\vartheta^\ast)=0\), that is, \(\nabla\Phi(\vartheta^\ast)=y\). Thus \(F_{\mathcal{O}}(\Sigma\vartheta^\ast)=y\).

Smoothness of the inverse. \(F_{\mathcal{O}}\) is a smooth bijection \(\mathbb{R}^d\to\mathcal{O}\) whose Jacobian is everywhere invertible, so by the inverse function theorem it is a local diffeomorphism around every point; hence its inverse is smooth on \(\mathcal{O}\). ◻

Proof. \(\mathcal{C}_M\) is the intersection of \(r\) open half-spaces, hence open and convex. It is nonempty: since \(M\) has rank \(r\), the map \(x\mapsto Mx\) is onto \(\mathbb{R}^r\), so some \(x\) has \(Mx=(1,\ldots,1)\). Apply Theorem D.3 with \(\mathcal{O}=\mathcal{C}_M\). ◻

Proof. If \(\mathcal{K}=\emptyset\), the conclusion is vacuous, so take \(\varepsilon_0=C=1\). Assume henceforth that \(\mathcal{K}\ne\emptyset\). Since \(\mathcal{K}\) is compact and \(B\) is open, \(r_0:=\frac12\operatorname{dist}(\mathcal{K},\mathbb{R}^d\setminus B)\) is positive (with \(r_0:=1\) if \(B=\mathbb{R}^d\)), and \(\mathcal{K}':=\{z:\operatorname{dist}(z,\mathcal{K})\le r_0\}\) is a compact subset of \(B\). Let \(L:=L(f,\mathcal{K}')\) be the constant of Lemma D.2, and put \[\varepsilon_0:=\min\left\{\frac{r_0}{C_0},\ \frac{1}{L\,C_0}\right\},\qquad C:=L\,C_0.\] Fix \(\varepsilon\in(0,\varepsilon_0)\), a map \(g\) as in the statement, and \(y\in\mathcal{K}\), and let \(x_0:=f^{-1}(y)\), so that \(|x_0|\le R_0-1\). For \(x\) in the closed ball \(\overline{B}(x_0,1)\) we have \(|x|\le R_0\), hence \(|f(x)-g(x)|\le C_0\varepsilon<r_0\), so the point \[z(x):=y+f(x)-g(x)\] lies in \(\mathcal{K}'\subseteq B\), and \(h(x):=f^{-1}(z(x))\) is defined. The map \(h\colon\overline{B}(x_0,1)\to\mathbb{R}^d\) is continuous, being a composition of continuous maps, and by Lemma D.2 on \(\mathcal{K}'\), \[|h(x)-x_0|=\left|f^{-1}(z(x))-f^{-1}(y)\right|\le L\,|z(x)-y|\le L\,C_0\,\varepsilon\le1 .\] Thus \(h\) maps \(\overline{B}(x_0,1)\) into itself, and by Brouwer’s fixed point theorem (Hatcher 2002, Corollary 2.15) it has a fixed point \(x^\ast\). Then \(f(x^\ast)=z(x^\ast)=y+f(x^\ast)-g(x^\ast)\), that is, \(g(x^\ast)=y\), and the displayed inequality with \(x=x^\ast\) gives \(|x^\ast-f^{-1}(y)|\le L\,C_0\,\varepsilon=C\varepsilon\).

For the last assertion, \(\mathcal{K}_T\) is closed and bounded, hence compact, and it is contained in \(\mathcal{C}_M\); the constants then depend on \(\mathcal{K}_T\) only through \(d\), \(M\), and \(T\). ◻

Proof. Every point \(a\) of the box \(\prod_t\{0,\ldots,\eta_t\}\) has \(\mathbb{P}[A^q=a]=\prod_t\binom{\eta_t}{a_t}q_t^{a_t}(1-q_t)^{\eta_t-a_t}>0\), and \(S\) is nonempty (a set contained in no affine hyperplane contains \(d+1\) affinely independent points), so \(\mathbb{P}[MA^q\ge'0]=\mathbb{P}[A^q\in S]>0\). Write \(\vartheta_t:=\log\frac{q_t}{1-q_t}\), which is a bijection \((0,1)^d\to\mathbb{R}^d\), and \(\binom{\eta}{a}:=\prod_t\binom{\eta_t}{a_t}\). Since \(q_t^{a_t}(1-q_t)^{\eta_t-a_t}=e^{\vartheta_ta_t}(1-q_t)^{\eta_t}\), \[\mathbb{P}\left[A^q=a\mid A^q\in S\right]=\binom{\eta}{a}\exp\left(\vartheta\cdot a-\psi(\vartheta)\right)\quad(a\in S),\qquad\psi(\vartheta):=\log\sum_{a\in S}\binom{\eta}{a}e^{\vartheta\cdot a}.\] The function \(\psi\) is smooth on \(\mathbb{R}^d\) (a logarithm of a finite positive sum of exponentials), and differentiating gives \(\nabla\psi(\vartheta)=\mathbb{E}[A^q\mid A^q\in S]\) and \(\nabla^2\psi(\vartheta)=\mathrm{Cov}(A^q\mid A^q\in S)\). For \(u\in\mathbb{R}^d\setminus\{0\}\), \(u^\top\nabla^2\psi(\vartheta)u=\mathrm{Var}(u\cdot A^q\mid A^q\in S)\), and this vanishes only if \(u\cdot a\) is constant over \(S\) (all points of \(S\) have positive conditional probability), that is, only if \(S\) lies in an affine hyperplane, which is excluded. Hence \(\psi\) is strictly convex, so \(\nabla\psi\) is injective (if \(\nabla\psi(\vartheta)=\nabla\psi(\vartheta')\) with \(\vartheta\ne\vartheta'\), the strictly convex function \(t\mapsto\psi(\vartheta+t(\vartheta'-\vartheta))\) would have equal derivatives at \(0\) and \(1\)), and so is \(q\mapsto\nabla\psi(\vartheta(q))\). ◻

Proof. Since \(M\) has rank \(r\), the linear map \(x\mapsto Mx\) is onto \(\mathbb{R}^r\), so \(\mathcal{E}_u\), the preimage of the closed orthant \(\{z\ge-u\}\), has nonempty interior, and \(\mathbb{P}[X\in\mathcal{E}_u]>0\). The functions in the statement are continuous in \((m,v,u)\): in \((m,v)\) by dominated convergence, and in \(u\) because the boundary of \(\mathcal{E}_u\) is a finite union of hyperplanes, which is Lebesgue-null. A positive continuous function on the compact set \(\mathcal{P}\) is bounded below, which gives \(c_{\mathcal{P}}\).

For the Lipschitz bounds, enlarge \(\mathcal P\) to a compact rectangular box in \(\mathbb R^d\times\mathbb R_{>0}^d\times\mathbb R^r\). All variances on this box remain bounded away from zero, and the box contains the line segments used in the mean value inequality below. Proving the bounds on this box suffices for the original set. Write \(\varphi_{m,v}\) for the density of \(X\) and let \(h\) be one of the functions \(1\), \(x_t\), \(x_tx_{t'}\). The partial derivatives \(\partial_{m_t}\varphi_{m,v}=\frac{x_t-m_t}{v_t}\varphi_{m,v}\) and \(\partial_{v_t}\varphi_{m,v}=\big(\frac{(x_t-m_t)^2}{2v_t^2}-\frac{1}{2v_t}\big)\varphi_{m,v}\) are bounded in absolute value by \(C(1+|x|^2)\varphi_{m,v}(x)\) for a constant \(C\) depending on \(\mathcal{P}\), and \((1+|x|^2)|h(x)|\varphi_{m,v}(x)\) is integrable uniformly over \(\mathcal{P}\); hence \((m,v)\mapsto\int_{\mathcal{E}_u}h\,\varphi_{m,v}\) is continuously differentiable with derivatives bounded on \(\mathcal{P}\), uniformly in \(u\), and therefore Lipschitz in \((m,v)\). For the dependence on \(u\), let \(u,u'\in\mathbb{R}^r\) and write \(Z:=MX\). The symmetric difference \(\mathcal{E}_u\,\triangle\,\mathcal{E}_{u'}\) is contained in \(\bigcup_{i\le r}\{x:-\max(u_i,u_i')\le(Mx)_i<-\min(u_i,u'_i)\}\), so \[\left|\int_{\mathcal{E}_u}h\varphi_{m,v}-\int_{\mathcal{E}_{u'}}h\varphi_{m,v}\right|\le\sum_{i\le r}\mathbb{E}\left[|h(X)|\,\mathbf{1}\{Z_i\in J_i\}\right],\qquad J_i:=\left[-\max(u_i,u'_i),-\min(u_i,u'_i)\right].\] Each \(Z_i\) is a nondegenerate Gaussian variable whose variance is bounded below on \(\mathcal{P}\), so its density is bounded by a constant \(C'\); and given \(Z_i=z\), the vector \(X\) is Gaussian with mean affine in \(z\) and bounded covariance, so \(\mathbb{E}[|h(X)|\mid Z_i=z]\le C''(1+z^2)\). Integrating over \(z\in J_i\) gives \(\mathbb{E}[|h(X)|\mathbf 1\{Z_i\in J_i\}]\le C'C''\sup_{z\in J_i}(1+z^2)\,|u_i-u'_i|\), which is at most a constant times \(|u-u'|\) on the compact set \(\mathcal{P}\). The conditional quantities are quotients of Lipschitz functions by the function \(\mathbb{P}[X\in\mathcal{E}_u]\), which is Lipschitz and bounded below by \(c_{\mathcal{P}}\); hence they are Lipschitz. ◻

Proof. Write \(d:=2^k\), \(\eta'_t:=\eta[t]-\mathbb{1}_{s=t}\), and let \(N\) be large enough that \(\eta'_t\in(\frac12N\nu[t],2N\nu[t])\) for all \(t\). Put \[\alpha_t:=\frac{\sigma[t]}{\nu[t]}\sqrt{\frac{\eta'_t}{N}},\qquad\text{so that}\qquad\Lambda_{N,p}(\sigma[t],\nu[t])=\frac{\frac{p}{1-p}e^{\alpha_t/\sqrt{p\eta'_t}}}{1+\frac{p}{1-p}e^{\alpha_t/\sqrt{p\eta'_t}}},\] and \(|\alpha_t|\le R\sqrt{2/\nu[t]}\). Let \(T_1\) be a constant, depending on \(\theta,k,T,R\), exceeding \(2T\), \(2/\min_t\nu[t]\), and \(\max_t R\sqrt{2/\nu[t]}\). We apply Theorem A.6 with \(d\), \(n=N\), the constant \(T_1\), \(\eta=\eta'\), \(\alpha\) as above, and \(\rho\in\{1,x_t,x_tx_{t'}\}\), once with \((M,\ge')=(M_s,\ge'_s)\) and once with \((M,\ge')=(M_{sb},\ge'_{sb})\); its hypotheses hold because \(\eta'_t\in(T_1^{-1}N,T_1N)\), \(|\alpha_t|<T_1\), \(p\in(T_1^{-1}N^{-\theta},T_1N^{-\theta})\), and \(\left\lVert M_s\eta'\right\rVert_\infty\le\left\lVert M_s\eta\right\rVert_\infty+1\le TN/\sqrt{pN}+1<T_1N/\sqrt{pN}\), while \(\left\lVert M_{sb}\eta'\right\rVert_\infty=\max\{\left\lVert M_s\eta'\right\rVert_\infty,|Z_{s,k}(\eta')|\}\le\max\{\left\lVert M_s\eta\right\rVert_\infty,|Z_{s,k}(\eta)|\}+1<T_1N/\sqrt{pN}\). Its conclusion is, for each admissible \(\rho\) and \(M\), \[\label{eq:gl-gpc} \mathbb{E}\left[\rho(A^\sigma-p\eta')\mathbf{1}_{MA^\sigma\ge'0}\right]=\mathbb{E}\left[\rho(X)\mathbf{1}_{MX\ge-pM\eta'}\right]+O\left(\sqrt{pN}^{\deg\rho-1}\log^{5+d}N\right),\] where \(X\) has independent coordinates \(X_t\sim\mathcal{N}(\sqrt{p\eta'_t}\,\alpha_t,\,p\eta'_t)\), and the events \(\{MA^\sigma\ge'0\}\) are \(\mathcal{I}_s(A^\sigma)\) and \(\mathcal{J}_{sb}(A^\sigma)\) respectively.

Normalization. Put \(\hat X:=X/\sqrt{pN}\), which has independent coordinates \(\hat X_t\sim\mathcal{N}(\hat m_t,\hat v_t)\) with \[\hat m_t=\frac{\sigma[t]\,\eta'_t}{N\nu[t]},\qquad\hat v_t=\frac{\eta'_t}{N},\qquad|\hat m_t-\sigma[t]|\le\frac{R}{\nu[t]}\left(\frac{\log^\ell N}{\sqrt{pN}}+\frac1N\right),\qquad|\hat v_t-\nu[t]|\le\frac{\log^\ell N}{\sqrt{pN}}+\frac1N,\] and the event \(\{MX\ge-pM\eta'\}\) is \(\{M\hat X\ge-u\}\) with \(u:=pM\eta'/\sqrt{pN}\). For \(M=M_s\), \(\left\lVert u\right\rVert_\infty\le\xi+p/\sqrt{pN}\le2\epsilon\). For \(M=M_{sb}\), the first \(k-1\) coordinates of \(u\) are those of the previous case and the last is \((-1)^bpZ_{s,k}(\eta')/\sqrt{pN}=(-1)^b(u_\eta+O(p/\sqrt{pN}))\), so that \(\{M_{sb}\hat X\ge-u\}\) is, up to a shift of the first \(k-1\) thresholds by \(O(\epsilon)\) and of the last by \(O(p/\sqrt{pN})\le O(\epsilon)\), the event \(\mathcal{J}^{u_\eta}_{sb}(\hat X)\). Dividing (E.1) by \(\sqrt{pN}^{\deg\rho}\), \[\label{eq:gl-normalized} \mathbb{E}\left[\rho\left(\frac{A^\sigma-p\eta'}{\sqrt{pN}}\right)\mathbf{1}_{MA^\sigma\ge'0}\right]=\mathbb{E}\left[\rho(\hat X)\mathbf{1}_{M\hat X\ge-u}\right]+O\left(\frac{\log^{5+d}N}{\sqrt{pN}}\right).\]

Comparison of the Gaussian functionals. Apply Lemma E.2 with \(M\in\{M_s,M_{sb}\}\) and the compact parameter set \(\mathcal{P}\) of all \((m,v,u)\) with \(\left\lVert m\right\rVert_\infty\le2R/\min_t\nu[t]\), \(\frac12\nu[t]\le v_t\le2\nu[t]\), and \(\left\lVert u\right\rVert_\infty\le2T+1\). For large \(N\) the triple \((\hat m,\hat v,u)\) lies in \(\mathcal{P}\), and so does the triple \((\sigma,\nu,0)\) for \(M=M_s\), respectively \((\sigma,\nu,(0,\ldots,0,(-1)^bu_\eta))\) for \(M=M_{sb}\); the two triples are at distance \(O(\log^\ell N/\sqrt{pN}+\xi+p/\sqrt{pN})=O(\epsilon)\) from each other. Hence the right-hand side of (E.2) differs by \(O(\epsilon)\) from \(\mathbb{E}[\rho(W^\sigma)\mathbf{1}_{\mathcal{I}_s(W^\sigma)}]\) for \(M=M_s\), respectively from \(\mathbb{E}[\rho(W^\sigma)\mathbf{1}_{\mathcal{J}^{u_\eta}_{sb}(W^\sigma)}]\) for \(M=M_{sb}\), where we used that \(\{M_sW^\sigma\ge0\}\) and \(\{M_{sb}W^\sigma\ge-(0,\ldots,0,(-1)^bu_\eta)\}\) coincide with \(\mathcal{I}_s(W^\sigma)\) and \(\mathcal{J}^{u_\eta}_{sb}(W^\sigma)\) up to null sets. Taking \(\ell':=5+d+\ell\), we conclude that for \(\rho\in\{1,x_t,x_tx_{t'}\}\), \[\label{eq:gl-final} \mathbb{E}\left[\rho\left(\frac{A^\sigma-p\eta'}{\sqrt{pN}}\right)\mathbf{1}_{\mathcal{I}_s(A^\sigma)}\right]=\mathbb{E}\left[\rho(W^\sigma)\mathbf{1}_{\mathcal{I}_s(W^\sigma)}\right]+O(\epsilon),\] and the same with \(\mathcal{J}_{sb}(A^\sigma)\) and \(\mathcal{J}^{u_\eta}_{sb}(W^\sigma)\) in place of \(\mathcal{I}_s(A^\sigma)\) and \(\mathcal{I}_s(W^\sigma)\).

Uniform denominator bounds. The lower probability bound in Lemma E.2 applies also at the actual parameters \((\hat m,\hat v,u)\in\mathcal{P}\). Choose \(c_0>0\) as the minimum of these compact-family lower bounds over the finitely many matrices \(M_s\) and \(M_{sb}\) with \(s\in\{0,1\}^k\) and \(b\in\{0,1\}\). Equation (E.2) with \(\rho=1\) gives, for each of these matrices, \[\mathbb{P}[MA^\sigma\ge'0]\ge c_0-O\left(\frac{\log^{5+d}N}{\sqrt{pN}}\right)\ge\frac{c_0}{2}\] uniformly for sufficiently large \(N\). The error tends to zero uniformly in the density window, regardless of \(\xi\in(0,T]\); the later error \(O(\epsilon)\) need not tend to zero. Thus both the binomial history and child-event probabilities are bounded away from zero before we divide the raw-moment comparisons.

Conclusion. The lower bounds \(\mathbb{P}[\mathcal{I}_s(W^\sigma)]\ge c_0\) and \(\mathbb{P}[\mathcal{J}^{u_\eta}_{sb}(W^\sigma)]\ge c_0\) follow from the choice of \(c_0\) and Lemma E.2 at the parameters \((\sigma,\nu,0)\) and \((\sigma,\nu,(0,\ldots,0,(-1)^bu_\eta))\). The two approximation bounds of (i) are (E.3) with \(\rho=1\), the second after dividing the \(\mathcal{J}\) version by the \(\mathcal{I}\) version and using the Gaussian lower bound \(c_0\) and the binomial lower bound \(c_0/2\) just proved. For (ii), (E.3) with \(\rho=x_t\) and \(\rho=1\) gives \[\frac{\mathbb{E}[A^\sigma_t\mid\mathcal{I}_s(A^\sigma)]-p\eta'_t}{\sqrt{pN}}=\frac{\mathbb{E}[W^\sigma_t\mathbf{1}_{\mathcal{I}_s(W^\sigma)}]+O(\epsilon)}{\mathbb{P}[\mathcal{I}_s(W^\sigma)]+O(\epsilon)}=\mathbb{E}[W^\sigma_t\mid\mathcal{I}_s(W^\sigma)]+O(\epsilon),\] and \(p\eta'_t\) differs from \(p\eta[t]\) by at most \(p\le\sqrt{pN}\,\epsilon\); the \(\mathcal{J}\) version is identical. For (iii), use \(\rho=x_tx_{t'}\), \(x_t\), \(x_{t'}\), and \(1\) in the same way. Finally, if \(|Z_{s,k}(\eta)|\le\xi N/\sqrt{pN}\) then \(|u_\eta|\le\xi\le\epsilon\), and by Lemma E.2 the Gaussian quantities with the event \(\mathcal{J}^{u_\eta}_{sb}(W^\sigma)\) differ from those with \(\mathcal{J}_{sb}(W^\sigma)\) by \(O(\epsilon)\). Smoothness in \(\sigma\): each binomial quantity is a rational function, with positive denominator, of the finitely many values \(\Lambda_{N,p}(\sigma[t],\nu[t])^{a}(1-\Lambda_{N,p}(\sigma[t],\nu[t]))^{\eta'_t-a}\), which are smooth in \(\sigma\). ◻

Proof. Write \(d:=2^k\) and \(c_t:=p\,\widetilde n[t]\). Since \(k(1-\theta)<1\), the number \(c_1:=\frac12(1-k(1-\theta))\) is positive and \[\label{eq:beta0-small} \beta_0\sqrt{pN}=\frac{\sqrt{pN}^{\,k}}{\sqrt N}\le T^{k/2}N^{-c_1},\] so \(\beta_0\sqrt{pN}\log^{O(1)}N\to0\). We use Theorem 5.2(v) throughout; in particular \(\widetilde n[t]\asymp N\), \(\widetilde m[s,t]/\widetilde n[s]-c_t=c_t\mu[s,t]/\sqrt{pN}+O(\log^\ell N)=O(\sqrt{pN})\), and \(|\widetilde\lambda[s,t]-p|=O(p/\sqrt{pN})\) (because \(\Lambda_{N,p}(\gamma,\nu)-p=O(p/\sqrt{pN})\) and \(\log^\ell N/N\le p/\sqrt{pN}\) for large \(N\)).

The tilt. By definition, \(\operatorname{logit}q^\sigma[t]=\operatorname{logit}\widetilde\lambda[s,t]+\log\frac{\widetilde n[t]-\mathbb{1}_{s=t}-c_t}{n[t]-\mathbb{1}_{s=t}-c_t}+\tau\beta_0\sigma[t]\), and the middle term is \(O(|n[t]-\widetilde n[t]|/N)=O(\beta_0)\) by the hypothesis on \(n\). Hence \(|\operatorname{logit}q^\sigma[t]-\operatorname{logit}\widetilde\lambda[s,t]|=O(\beta_0)\), so \(|q^\sigma[t]-\widetilde\lambda[s,t]|=O(p\beta_0)\) and \(|q^\sigma[t]-p|=O(p/\sqrt{pN})\); smoothness in \(\sigma\) is clear. Now apply Theorem A.7 with \(d\), \(n=N\), a sufficiently large constant \(T_1=T_1(\theta,k,T,R)\ge T\) in place of \(T\), reference sizes \(\widetilde\eta_t:=\widetilde n[t]\), trial counts \(\widetilde\eta'_t:=\widetilde n[t]-\mathbb{1}_{s=t}\) and \(\eta_t:=n[t]-\mathbb{1}_{s=t}\), success probabilities \(\widetilde q:=\widetilde\lambda[s,\bullet]\) and \(q:=q^\sigma\), and \(\rho\in\{1,x_t\}\), once with \((M_s,\ge'_s)\) and once with \((M_{sb},\ge'_{sb})\). Its hypotheses hold for large \(N\): \(p\in(T_1^{-1}N^{-\theta},T_1N^{-\theta})\); \(\widetilde\eta_t\asymp N\); \(|\widetilde\eta'_t-\widetilde\eta_t|\le1\); \(|\eta_t-\widetilde\eta_t|\le T\sqrt N\sqrt{pN}^{k-1}+1\le T^{1+k/2}N/\sqrt{pN}\) by (E.4); \(|\widetilde q_t-p|,|q_t-p|=O(p/\sqrt{pN})\); and its tilt vector is exactly \(\beta_t=\tau\beta_0\sigma[t]\), by the definition of \(q^\sigma\), so \(\left\lVert\beta\right\rVert_\infty\le TR\beta_0<T_1/(\sqrt{pN}\log^2N)\) by (E.4). Writing \(E_1:=\max\{p,\left\lVert\beta\right\rVert_\infty^2pN\log^2N\}\), the conclusions are, for the event \(\mathcal{I}_s\) (and identically for \(\mathcal{J}_{sb}\)), \[\begin{aligned} \mathbb{P}[\mathcal{I}_s(A^\sigma)]&=\widetilde P+\sum_{t'}\beta_{t'}J_{t'}+O(E_1\log^2N),\label{eq:lr-prob}\\ \mathbb{E}\left[(A^\sigma_t-c_t)\mathbf{1}_{\mathcal{I}_s(A^\sigma)}\right]&=\widetilde E_t\widetilde P+\sum_{t'}\beta_{t'}K_{t't}+O(E_1\sqrt{pN}\log^3N),\label{eq:lr-mean} \end{aligned}\] where \(\widetilde P:=\mathbb{P}[\mathcal{I}_s(\widetilde A)]\), \(\widetilde E_t:=\mathbb{E}[\widetilde A_t-c_t\mid\mathcal{I}_s(\widetilde A)]\), \(J_{t'}:=\mathrm{Cov}(\widetilde A_{t'},\mathbf{1}_{\mathcal{I}_s(\widetilde A)})\), and \(K_{t't}:=\mathbb{E}[(\widetilde A_{t'}-c_{t'})(\widetilde A_t-c_t)\mathbf{1}_{\mathcal{I}_s(\widetilde A)}]-\mathbb{E}[\widetilde A_{t'}-c_{t'}]\,\widetilde E_t\widetilde P\); here \(\widetilde A:=\widetilde A_{s,\bullet}\). By Theorem 5.2(ii), \(\widetilde E_t=\widetilde m[s,t]/\widetilde n[s]-c_t=O(\sqrt{pN})\). By Lemma E.3 applied with \(\eta=\widetilde n_k\) (so \(\left\lVert M_s\eta\right\rVert_\infty=0\) by Theorem 5.2(iv) and Corollary 4.10(iii), and we may take \(\xi=\sqrt{pN}/N\)) and with \(\sigma\) the vector \(\widetilde\sigma\) defined by \(\Lambda_{N,p}(\widetilde\sigma[t],\nu[t])=\widetilde\lambda[s,t]\), which satisfies \(\left\lVert\widetilde\sigma-\gamma[s,\bullet]\right\rVert_\infty=O(\log^\ell N/\sqrt{pN})\) by (v) and is therefore bounded, we have \(\widetilde P\ge\phi^\ast_k/2\), \(\mathbb{P}[\mathcal{J}_{sb}(\widetilde A)\mid\mathcal{I}_s(\widetilde A)]=\nu[sb]/\nu[s]+O(\epsilon_0)\), and \[\label{eq:lr-cov-limit} \frac{K_{t't}-J_{t'}\widetilde E_t}{\widetilde P}=\mathrm{Cov}\left(\widetilde A_{t'},\widetilde A_t\mid\mathcal{I}_s(\widetilde A)\right)=pN\,\Sigma_s[t',t]+O(pN\epsilon_0),\qquad\epsilon_0:=\frac{\log^{\ell'}N}{\sqrt{pN}}+\frac{\sqrt{pN}}{N},\] where the first equality is a direct expansion of the definitions. The second is Lemma E.3(iii) together with the Lipschitz dependence of the Gaussian conditional covariance on the mean (Lemma E.2), which converts the covariance of \(W^{\widetilde\sigma}\) given \(\mathcal{I}_s\) into \(\Sigma_s\) at the cost of \(O(\log^\ell N/\sqrt{pN})\). Also \(|J_{t'}|\le\sqrt{\mathrm{Var}(\widetilde A_{t'})}\), which is \(O(\sqrt{pN})\), and \(|K_{t't}|=O(pN)\).

Proof of (i). Dividing (E.6) by (E.5), with \(u:=\sum_{t'}\beta_{t'}J_{t'}/\widetilde P=O(\left\lVert\beta\right\rVert_\infty\sqrt{pN})=O(\beta_0\sqrt{pN})\), \[\begin{aligned} \mathbb{E}[A^\sigma_t\mid\mathcal{I}_s(A^\sigma)]-c_t&=\frac{\widetilde E_t\widetilde P+\sum_{t'}\beta_{t'}K_{t't}+O(E_1\sqrt{pN}\log^3N)}{\widetilde P\left(1+u+O(E_1\log^2N)\right)}\\ &=\widetilde E_t+\sum_{t'}\beta_{t'}\frac{K_{t't}-J_{t'}\widetilde E_t}{\widetilde P}+O\left(E_1\sqrt{pN}\log^3N+\beta_0^2\,pN\sqrt{pN}\right), \end{aligned}\] where the last error collects the second-order terms \(u^2\widetilde E_t\) and \(u\sum\beta K/\widetilde P\), both \(O(\beta_0^2pN\sqrt{pN})\), and \(\widetilde E_t\cdot O(E_1\log^2N)=O(E_1\sqrt{pN}\log^2N)\). Substituting \(\widetilde E_t=\widetilde m[s,t]/\widetilde n[s]-c_t\) and (E.7), and dividing by \(\tau\beta_0pN\), the main term becomes \((\Sigma_s\sigma)[t]+O(\epsilon_0)\) and the error terms become \[O\left(\frac{p\sqrt{pN}\log^3N}{\beta_0pN}+\frac{\beta_0^2pN\log^2N\sqrt{pN}\log^3N}{\beta_0pN}+\beta_0\sqrt{pN}\right) =O\left(\frac{\sqrt p\log^3N}{\sqrt{pN}^{\,k-1}}+\beta_0\sqrt{pN}\log^5N\right),\] using \(\left\lVert\beta\right\rVert_\infty\le TR\beta_0\) and \(\beta_0=\sqrt{pN}^{k-1}/\sqrt N\). The first term is at most \(\sqrt p\log^3N\) and the second is \(O(N^{-c_1}\log^5N)\) by (E.4); together with \(\epsilon_0=O(\log^{\ell'}N/\sqrt{pN})\), all are \(O(N^{-\kappa})\) for \(\kappa:=\frac12\min\{c_1,\theta/2,(1-\theta)/2\}\) and large \(N\).

Proof of (ii). Write \(\widetilde P_J:=\mathbb{P}[\mathcal{J}_{sb}(\widetilde A)]\) and \(J^{(b)}_{t'}:=\mathrm{Cov}(\widetilde A_{t'},\mathbf{1}_{\mathcal{J}_{sb}(\widetilde A)})\). Dividing the \(\mathcal{J}_{sb}\) version of (E.5) by the \(\mathcal{I}_s\) version, \[\mathbb{P}[\mathcal{J}_{sb}(A^\sigma)\mid\mathcal{I}_s(A^\sigma)]=\frac{\widetilde P_J}{\widetilde P}+\sum_{t'}\beta_{t'}\left(\frac{J^{(b)}_{t'}}{\widetilde P}-\frac{\widetilde P_J\,J_{t'}}{\widetilde P^2}\right)+O\left(E_1\log^2N+\beta_0^2pN\right),\] and a direct expansion gives \(\frac{J^{(b)}_{t'}}{\widetilde P}-\frac{\widetilde P_JJ_{t'}}{\widetilde P^2}=\frac{\widetilde P_J}{\widetilde P}\left(\mathbb{E}[\widetilde A_{t'}\mid\mathcal{J}_{sb}(\widetilde A)]-\mathbb{E}[\widetilde A_{t'}\mid\mathcal{I}_s(\widetilde A)]\right)\). By Lemma E.3(i) and (ii) at \(\widetilde\sigma\), together with the Lipschitz dependence on the mean of Lemma E.2, this equals \(\sqrt{pN}\,\frac{\nu[sb]}{\nu[s]}\left(\mathbb{E}[W_{s,t'}\mid\mathcal{J}_{sb}(W_{s,\bullet})]-\mathbb{E}[W_{s,t'}\mid\mathcal{I}_s(W_{s,\bullet})]\right)+O(\sqrt{pN}\epsilon_0)\). Dividing by \(\tau\beta_0\sqrt{pN}\) and using \(\beta_{t'}=\tau\beta_0\sigma[t']\) gives the main term of (ii); the errors are \(O(\epsilon_0)\) from the main term and \[O\left(\frac{p\log^2N}{\beta_0\sqrt{pN}}+\frac{\beta_0^2pN\log^4N}{\beta_0\sqrt{pN}}+\frac{\beta_0^2pN}{\beta_0\sqrt{pN}}\right)=O\left(\frac{\sqrt p\log^2N}{\sqrt{pN}^{\,k-1}}+\beta_0\sqrt{pN}\log^4N\right)=O(N^{-\kappa}).\]

Proof of (iii). Dividing the \(\mathcal{J}_{sb}\) versions of (E.6) and (E.5), exactly as in the proof of (i) but with \(\mathcal{J}_{sb}\) in place of \(\mathcal{I}_s\) and with the lower bound \(\widetilde P_J\ge\widetilde P\,\phi^\ast_k/4\), the difference \(\mathbb{E}[A^\sigma_t\mid\mathcal{J}_{sb}(A^\sigma)]-\mathbb{E}[\widetilde A_t\mid\mathcal{J}_{sb}(\widetilde A)]\) equals \(\sum_{t'}\beta_{t'}\mathrm{Cov}(\widetilde A_{t'},\widetilde A_t\mid\mathcal{J}_{sb}(\widetilde A))\) plus the error \(O(E_1\sqrt{pN}\log^3N+\beta_0^2pN\sqrt{pN})\); the sum is \(O(\left\lVert\beta\right\rVert_\infty pN)=O(\tau\beta_0pN)\) and the error is smaller, by the computation in the proof of (i).

Proof of (iv). By (E.5), \(\mathbb{P}[\mathcal{I}_s(A^\sigma)]=\widetilde P+O(\beta_0\sqrt{pN}+E_1\log^2N)\), and \(\widetilde P\ge\phi^\ast_k/2\), so the first bound holds for large \(N\) by (E.4). By (ii), \(\mathbb{P}[\mathcal{J}_{sb}(A^\sigma)\mid\mathcal{I}_s(A^\sigma)]=\mathbb{P}[\mathcal{J}_{sb}(\widetilde A)\mid\mathcal{I}_s(\widetilde A)]+O(\beta_0\sqrt{pN})=\nu[sb]/\nu[s]+O(\epsilon_0+\beta_0\sqrt{pN})\), and \(\nu[sb]/\nu[s]=\mathbb{P}[\mathcal{J}_{sb}(W_{s,\bullet})\mid\mathcal{I}_s(W_{s,\bullet})]\in[\phi^\ast_k,1-\phi^\ast_k]\) by (4.3) and Lemma 4.11. ◻