The Scale Set for the Van Trees Assembly: Eventual Validity of the Copy-Side Constraints, Lower Bounds for the Chernoff Exponents, and Vanishing of the Error Majorants

Data. Let $l\ge2$, $m\ge1$ and $\tilde{l}\ge1$ be natural numbers, and let $B\ge0$, $\tilde{B}\ge0$, $K\ge0$, $\tilde{K}\ge0$, $\underline{b}>0$, $T>0$, $s\in(0,T]$, $\Lambda\ge0$, $\mathsf{M}\ge0$, $\bar\Phi\ge0$, $\mathsf{c}_{0}\ge0$, $c_{Q}\ge0$, $\kappa^{\sharp}\ge1$, $C_{\mathrm{flw}}\ge0$, $C_{\mathrm{ctl}}\ge0$, $\mathsf{P}\ge0$ and $\mathsf{Q}\ge0$ be real numbers (the scalar data). Put

$$\Lambda_{1}=\sqrt{l+m}\,(B+K),\quad \Lambda_{2}=\tfrac32(l+m)K,\quad \Lambda_{3}=3K\sqrt{l(l+m)},\quad \Lambda_{\mathcal{E}}=\sqrt{2}\,l(l-1)\sqrt{l}\,(B+K),\quad \Gamma=\sqrt{l}\,(\tilde{B}+\tilde{K}),\quad C_{\mathrm{Lip}}=l(l-1)(\Lambda_{1}+\Lambda_{3}),\quad \mathsf{c}_{\star}=c_{Q}\kappa^{\sharp},$$ $$C_{A}=\sqrt{2}\,\bigl(1+2l(l-1)\bigr)\exp\bigl(\sqrt{2}\,l(l-1)\Lambda_{1}s\bigr),\qquad C_{M}=2\Lambda_{1}sC_{A}+5,\qquad c_{\mathrm{w}}=\frac{1}{16\,C_{M}},\qquad H=\sqrt{2}\,\bar\Phi^{2}\Lambda_{\mathcal{E}}\,s .$$

Conventions. Natural numbers are regarded as real numbers, real powers $t^{a}=\exp(a\log t)$ of a real $t>0$ are those of Real Power of a Positive Real Number, and $\exp$, $\log$, $\sqrt{\cdot}$, $\lfloor\cdot\rfloor$ and limits of sequences are as in Real Powers Through the Exponential, and Elementary Asymptotic Tools: Monotonicity, Null Sequences of Negative Powers, Exponential Domination, Integer Rounding, and Square-Root and Exponential Inequalities, whose claims are used freely. For a real $t\ge0$ we write $t^{1/2}=\sqrt{t}$ and $t^{1/4}=(t^{1/2})^{1/2}$, consistent with the real powers for $t>0$ by claim 1 of that lemma; in particular $N^{1/2}=\sqrt{N}$, $N^{1/4}=\sqrt{\sqrt{N}}$, $N^{-1/2}=1/\sqrt{N}$, $N^{-1/4}=1/N^{1/4}$ and $N^{-1}=1/N$. Write $a\wedge b$ for the smaller of two real numbers $a,b$. For real numbers $k>0$ and $x\ge0$ let

$$\varpi_{k}(x)=\frac{x^{2}}{4k}\wedge\frac{x}{2}$$

be the Chernoff exponent of that lemma, extended to $x=0$ by the same formula. All objects introduced below are real numbers depending on the scalar data and on a natural number $N$, and "$u_{N}\to u$" refers to the sequence $(u_{N})_{N\in\mathbb{N}}$. Notational cautions: $J_{N}$ (a natural number, the number of cells per clock) and $\mathsf{J}_{N}$ (an information majorant) are distinct, as are $\mathsf{w}_{N}$ and $w_{1,N},w_{2,N}$; $\mathsf{E}^{\star}_{N}$ and $\mathsf{e}^{\star}_{N}$; $\mathsf{m}_{N}$ (a move size) and the control dimension $m$; $\mathsf{M}$ and $M_{N}$; $D_{N}$ and $d_{N}$; $\mathsf{B}_{N}$ and $B$; $\mathsf{k}_{N}$ and $K,\tilde{K}$; $\mathsf{a}_{N}$ and $\alpha_{N}$; and $\mathsf{c}_{0}$, $\mathsf{c}_{\star}$ (scalar data) and $\mathsf{c}_{N}$ (a derived quantity indexed by $N$).

The scale set. For $N\in\mathbb{N}$ put

$$\mathsf{m}_{N}=\lfloor N^{1/16}\rfloor+1,\qquad D_{N}=N^{3/64},\qquad A_{N}=\sqrt{2}\,\bigl(\mathsf{m}_{N}+l(l-1)(D_{N}+\mathsf{m}_{N})\bigr)\exp\bigl(\sqrt{2}\,l(l-1)\Lambda_{1}s\bigr),\qquad L_{N}=\Lambda_{1}sA_{N}+1,\qquad M_{N}=\lfloor L_{N}\rfloor+1,$$ $$R_{N}=\lfloor N(Bs+1)\rfloor+1,\qquad J_{N}=\lfloor R_{N}N^{-3/4}\rfloor+1,\qquad \mu_{N}=\frac{R_{N}}{J_{N}},\qquad d_{N}=l(l-1)J_{N},$$ $$\eta_{N}=N^{-3/8},\qquad \delta_{N}=N^{-1/8},\qquad \zeta_{N}=N^{-1/2},\qquad \theta_{N}=\lfloor N^{1/4}\rfloor+1,\qquad x_{N}=\mu_{N}^{1/2}N^{1/32},$$ $$\varepsilon_{S,N}=(C_{\mathrm{flw}}+1)N^{-1/4},\qquad \varepsilon_{\mathrm{ctl},N}=C_{\mathrm{Lip}}(TC_{\mathrm{ctl}})^{1/2}N^{-1/4},\qquad w_{1,N}=N\bigl(\Lambda_{1}s\,\varepsilon_{S,N}+\varepsilon_{\mathrm{ctl},N}\bigr),\qquad w_{2,N}=\mu_{N}.$$

Derived quantities. For $N\in\mathbb{N}$ put

$$\varepsilon_{0,N}=\frac{\Gamma A_{N}}{N\underline{b}},\qquad \bar{E}_{N}=\frac{\tilde{l}\,s\,\Gamma^{2}A_{N}^{2}}{N\underline{b}},\qquad \mathsf{c}_{N}=\exp(\bar{E}_{N})-1,\qquad \mathsf{E}^{\star}_{N}=\tilde{l}\,s\,N\tilde{B}\,\varepsilon_{0,N}^{2},\qquad \mathsf{e}^{\star}_{N}=\tfrac12(\mathsf{E}^{\star}_{N})^{2}\exp(\mathsf{E}^{\star}_{N})+\mathsf{E}^{\star}_{N}\bigl(\exp(9\mathsf{E}^{\star}_{N})-1\bigr)^{1/2},$$ $$\mathsf{E}^{\mathrm{ch}}_{N}=8\,\tilde{l}\,s\,N\tilde{B}\,\theta_{N}^{2}\varepsilon_{0,N}^{2},\qquad \bar\Pi_{N}=d_{N}\Bigl(\exp\bigl(-\varpi_{\mu_{N}}(x_{N})\bigr)+\exp\bigl(-\theta_{N}\delta_{N}/2+\mathsf{E}^{\mathrm{ch}}_{N}\bigr)\Bigr),$$ $$\mathsf{g}_{N}=d_{N}\exp\bigl(-\varpi_{\mu_{N}}(\mu_{N}-\mathsf{m}_{N})\bigr)+2\,l(l-1)\,(R_{N}+1)(M_{N}+3)\exp\bigl(-\varpi_{M_{N}+2}(D_{N}-2)\bigr)$$

(the formula for $\mathsf{g}_{N}$ is read for those $N$ for which $\mu_{N}-\mathsf{m}_{N}\ge0$ and $D_{N}-2\ge0$; for the remaining $N$ put $\mathsf{g}_{N}=0$; the formula for $\bar\Pi_{N}$ is read for every $N$),

$$\kappa_{0,N}=1+\frac{\mathsf{m}_{N}^{2}}{2\mu_{N}}\exp\Bigl(\frac{\mathsf{m}_{N}^{2}}{\mu_{N}}\Bigr),\qquad \bar{\mathsf{j}}_{N}=\frac{\kappa_{0,N}\mathsf{m}_{N}^{2}}{\mu_{N}},\qquad \mathsf{j}^{\star}_{N}=\bigl((1+\bar{\mathsf{j}}_{N})^{1/2}+1\bigr)\bar{\mathsf{j}}_{N}^{1/2},$$ $$\mathsf{B}_{N}=\bar\Pi_{N}+d_{N}(1+\bar{\mathsf{j}}_{N})^{1/2}\Bigl((d_{N}\bar\Pi_{N})^{1/2}+(\mathsf{c}_{N}\bar\Pi_{N})^{1/2}\Bigr)+\mathsf{g}_{N}+\mathsf{g}_{N}^{1/2}\,d_{N}(1+\bar{\mathsf{j}}_{N})^{1/2},$$ $$\mathsf{w}_{N}=\frac{\sqrt{2}\,\Lambda\,l(l-1)\,R_{N}}{\mathsf{m}_{N}},\qquad \kappa^{\mathrm{mv}}_{N}=\frac{\mathsf{m}_{N}^{2}}{N\eta_{N}},\qquad \alpha_{N}=\sqrt{2d_{N}}\,\mathsf{c}_{0}\bar\Phi^{2},\qquad \mathsf{k}_{N}=\alpha_{N}\bigl(3\mu_{N}^{2}+\mu_{N}\bigr)^{1/4},$$ $$\mathsf{e}_{F,N}=2\Lambda\,l(l-1)\bigl(\Lambda_{1}s\,\varepsilon_{S,N}+\varepsilon_{\mathrm{ctl},N}\bigr)+\frac{2\Lambda\,l(l-1)\,\mu_{N}}{N}\Bigl(3+\frac{2(\Lambda_{1}sA_{N}+\mu_{N})}{\mu_{N}}\Bigr),$$ $$\epsilon_{\psi,N}=\Bigl(\mathsf{e}_{F,N}+\frac{\sqrt{2}\,l(l-1)\,\mathsf{w}_{N}}{N}\Bigl(D_{N}+\frac{\Lambda_{2}sA_{N}^{2}}{N}\Bigr)+\sqrt{2}\,\mathsf{M}\bigl(l(l-1)\Lambda_{3}s\,\varepsilon_{S,N}+\varepsilon_{\mathrm{ctl},N}\bigr)\Bigr)\exp(\Lambda_{\mathcal{E}}s),$$ $$\kappa_{N}=\frac{\Gamma\,(2\mathsf{M}+\epsilon_{\psi,N})\bigl(3l\tilde{K}\,\varepsilon_{S,N}\,(\mathsf{M}+\epsilon_{\psi,N})+\Gamma\,\epsilon_{\psi,N}\bigr)}{\underline{b}}+\frac{\Gamma^{3}\mathsf{M}^{2}\,\varepsilon_{S,N}}{\underline{b}^{2}},$$ $$\mathsf{Q}_{N}=(1+\zeta_{N})\bigl(\mathsf{Q}+\tilde{l}\,s\,\kappa_{N}\bigr)+\Bigl(1+\frac{1}{\zeta_{N}}\Bigr)\frac{9\,\tilde{l}\,l^{2}\tilde{K}^{2}\,s\,\mathsf{w}_{N}^{2}A_{N}^{4}}{4N^{4}\underline{b}},$$ $$\mathsf{J}_{N}=(1+\delta_{N})\Bigl[\kappa_{0,N}\mathsf{P}+\mathsf{Q}_{N}+\frac{\mathsf{w}_{N}^{2}}{N}\Bigl(\mathsf{e}^{\star}_{N}+\bar{E}_{N}\bigl(N^{-1/2}+\mathsf{c}_{\star}N^{-1}\bigr)+\mathsf{c}_{N}\mathsf{j}^{\star}_{N}\Bigr)\Bigr]+\frac{2d_{N}\mathsf{w}_{N}^{2}\mathsf{B}_{N}}{N},\qquad \mathcal{I}_{N}=\Bigl(\mathsf{J}_{N}^{1/2}+\sqrt{2}\,\mathsf{w}_{N}\bigl(\exp(\kappa^{\mathrm{mv}}_{N})-1-\kappa^{\mathrm{mv}}_{N}\bigr)^{1/2}N^{-1/2}\Bigr)^{2},$$

and the error majorants

$$\mathsf{e}_{2,N}=\mathsf{c}_{0}\bar\Phi^{2}\Bigl(\sqrt{2}\,l(l-1)\Lambda_{2}s\,\mathsf{c}_{\star}^{1/2}N^{-1/2}+\sqrt{2}\,l(l-1)\Lambda_{3}s\bigl(\varepsilon_{S,N}\mathsf{c}_{\star}^{1/4}+\mathsf{c}_{\star}^{1/2}N^{-1/2}\bigr)+\sqrt{2}\,\varepsilon_{\mathrm{ctl},N}\,\mathsf{c}_{\star}^{1/4}\Bigr),$$ $$\Xi_{N}=\Bigl((w_{1,N}+3)^{1/2}+(w_{2,N}+3)^{1/2}\Bigr)N^{1/32}+4+\bigl(8(4096+17R_{N}^{4})\bigr)^{1/4}\exp\bigl(-N^{1/32}/16\bigr)\Bigl[\bigl(2(R_{N}+1)(w_{1,N}+4)\bigr)^{1/4}+\bigl(2(R_{N}+1)(w_{2,N}+4)\bigr)^{1/4}\Bigr],\qquad \mathsf{e}_{3,N}=\frac{\mathsf{c}_{0}}{\sqrt{N}}\,l(l-1)\,(\sqrt{2}+H)\,\Xi_{N},$$ $$\mathsf{e}_{4,N}=\eta_{N}^{1/2}\alpha_{N},\qquad \mathsf{e}_{5,N}=\sqrt{2}\Bigl(\mathsf{g}_{N}^{1/4}+\bigl(N^{-1/2}+\mathsf{c}_{\star}N^{-1}\bigr)^{1/4}\Bigr)\Bigl(\mathsf{c}_{0}\mathsf{c}_{\star}^{1/4}+\frac{\mathsf{k}_{N}}{\sqrt{N}}\Bigr),$$ $$\mathsf{e}_{\mathrm{inj},N}=2\,l(l-1)\,\mathsf{c}_{0}\Lambda\bar\Phi^{2}(\Lambda_{\mathcal{E}}s+1)\frac{\mu_{N}}{N},\qquad \mathsf{a}_{N}=\frac{\sqrt{2}\,\mathsf{c}_{0}\bar\Phi^{2}\mathsf{m}_{N}}{\sqrt{N}} .$$

Then the following hold.

1. (Eventual validity of the constraints.) There is a natural number $N_{\mathrm{c}}$ such that for every natural number $N\ge N_{\mathrm{c}}$: (i) $\mathsf{m}_{N}\in\mathbb{N}$ and $N^{1/16}<\mathsf{m}_{N}\le2N^{1/16}$; (ii) $R_{N}\in\mathbb{N}$ and $NBs<R_{N}$, $N\le R_{N}\le(Bs+2)N$; (iii) $J_{N}\in\mathbb{N}$, $\tfrac12N^{3/4}\le\mu_{N}\le N^{3/4}$, $\mu_{N}\ge2$, and $N^{1/4}\le d_{N}\le l(l-1)(Bs+3)N^{1/4}$; (iv) $D_{N}\le N^{1/16}<\mathsf{m}_{N}$, $A_{N}\le C_{A}\mathsf{m}_{N}\le2C_{A}N^{1/16}$, $0\le\Lambda_{1}sA_{N}<L_{N}$, $M_{N}\in\mathbb{N}$, $L_{N}<M_{N}\le L_{N}+1$ and $M_{N}+2\le M_{N}+3\le C_{M}N^{1/16}$; (v) $D_{N}\ge4$, $0<\eta_{N}\le1$, $0<\delta_{N}\le1$, $\zeta_{N}>0$, $\theta_{N}\in\mathbb{N}$ and $N^{1/4}<\theta_{N}\le2N^{1/4}$; (vi) $\mathsf{m}_{N}<\mu_{N}/2$; (vii) $\varepsilon_{0,N}\le\tfrac12$, $2\theta_{N}\varepsilon_{0,N}\le1$, $\bar{E}_{N}\le1$, $\mathsf{E}^{\star}_{N}\le1$, $\mathsf{E}^{\mathrm{ch}}_{N}\le1$, $\bar{\mathsf{j}}_{N}\le1$ and $\kappa^{\mathrm{mv}}_{N}\le1$; (viii) $\mathsf{m}_{N}(x_{N}+\mathsf{m}_{N})\le\delta_{N}\mu_{N}/2$. Such an $N_{\mathrm{c}}$ is fixed for the remainder of the statement.

2. (Chernoff exponents.) For all real $k>0$ the map $x\mapsto\varpi_{k}(x)$ is nondecreasing on $[0,\infty)$, and for every real $n\ge0$ and every $N\in\mathbb{N}$, the number $y=(n+2)^{1/2}N^{1/32}$ satisfies $\varpi_{n+2}(y)\ge N^{1/32}/4$. Moreover, for every $N\ge N_{\mathrm{c}}$,

$$\varpi_{\mu_{N}}(x_{N})\ge\frac{N^{1/32}}{4},\qquad \varpi_{\mu_{N}}(\mu_{N}-\mathsf{m}_{N})\ge\frac{\mu_{N}}{16}\ge\frac{N^{3/4}}{32},\qquad \varpi_{M_{N}+2}(D_{N}-2)\ge c_{\mathrm{w}}N^{1/32}.$$

3. (Limits.) (a) $\varepsilon_{S,N}\to0$, $\varepsilon_{\mathrm{ctl},N}\to0$, $\varepsilon_{0,N}\to0$, $\bar{E}_{N}\to0$, $\mathsf{c}_{N}\to0$, $\mathsf{e}^{\star}_{N}\to0$, $\kappa_{0,N}\to1$, $\bar{\mathsf{j}}_{N}\to0$, $\mathsf{j}^{\star}_{N}\to0$, $\bar\Pi_{N}\to0$, $\mathsf{g}_{N}\to0$, $\mathsf{e}_{F,N}\to0$, $\epsilon_{\psi,N}\to0$, $\kappa_{N}\to0$, $\mathsf{Q}_{N}\to\mathsf{Q}$, $\frac{2d_{N}\mathsf{w}_{N}^{2}\mathsf{B}_{N}}{N}\to0$ and $\mathsf{J}_{N}\to\mathsf{P}+\mathsf{Q}$. (b) $\mathsf{e}_{2,N}\to0$, $\mathsf{e}_{3,N}\to0$, $\mathsf{e}_{4,N}\to0$, $\mathsf{e}_{5,N}\to0$, $\mathsf{e}_{\mathrm{inj},N}\to0$ and $\mathsf{a}_{N}\to0$. (c) $\mathcal{I}_{N}\to\mathsf{P}+\mathsf{Q}$.

4. (Eventual smallness.) For every real $\epsilon>0$ there is a natural number $N_{\mathrm{sc}}\ge N_{\mathrm{c}}$ such that for every natural number $N\ge N_{\mathrm{sc}}$,

$$\mathsf{e}_{2,N}+\mathsf{e}_{3,N}+\mathsf{e}_{4,N}+\mathsf{e}_{5,N}\le\epsilon,\qquad \mathsf{e}_{\mathrm{inj},N}\le\epsilon,\qquad \mathsf{a}_{N}\le\epsilon,\qquad \mathcal{I}_{N}\le\mathsf{P}+\mathsf{Q}+\epsilon,\qquad \mathsf{g}_{N}\le\epsilon .$$