Proof of 1. For a fixed target \(h^\star\in \mathcal{H}\), every training example has the form \[(x,\operatorname{Roll}_\mathtt{halt}(h^\star)(x)).\] This is exactly a realizable multiclass example for the target function \(\operatorname{Roll}_\mathtt{halt}(h^\star)\in\operatorname{Roll}_\mathtt{halt}(\mathcal{H})\). Conversely, every target in \(\operatorname{Roll}_\mathtt{halt}(\mathcal{H})\) is \(\operatorname{Roll}_\mathtt{halt}(h)\) for some \(h\in \mathcal{H}\). The loss in 4 is ordinary zero-one loss against that target function. ◻

Proof sketch of 3. Fix a tuple \(\mathbf{x}=(x_1,\ldots,x_n)\in\mathcal{X}^n\), and consider the one-inclusion hypergraph on the possibly infinite vertex set \(\mathcal{H}|_{\mathbf{x}}\subseteq\mathcal{Y}^{[n]}\). Its hyperedges are the non-singleton fibers of the coordinate-deletion maps \[v\in\mathcal{H}|_{\mathbf{x}} \longmapsto v|_{[n]\setminus\{i\}}, \qquad i\in[n].\] For every finite vertex set \(W\subseteq\mathcal{H}|_{\mathbf{x}}\), choose one representative \(h\in\mathcal{H}\) for each vertex of \(W\). These representatives form a finite subclass \(\mathcal{H}_W\subseteq\mathcal{H}\) with \(\mathcal{H}_W|_{\mathbf{x}}=W\). Hence every finite induced subhypergraph has density at most \(\mu_\mathcal{H}(n)\), because \(\mu_\mathcal{H}(n)\) takes the supremum over all finite subclasses in 7.

The finite one-inclusion orientation theorem, in the density normalization of 7, gives an orientation with maximum outdegree at most \(\lceil\mu_\mathcal{H}(n)\rceil\) on every finite induced subhypergraph; see [9] for the one-inclusion bound and [5] for this density normalization, building on the orientation formulation of [8]. By the standard compactness argument for infinite one-inclusion graphs, these finite orientations extend to an orientation of the full one-inclusion hypergraph; see also [5].

The resulting orientation defines a deterministic transductive leave-one-out rule for the fixed ordered tuple \(\mathbf{x}\), with average leave-one-out error at most \(\lceil\mu_\mathcal{H}(n)\rceil/n\). Finally, averaging this rule over a uniformly random permutation of \([n]\) makes the rule permutation-invariant without increasing its average leave-one-out error. ◻

Proof of 2. By 1 and 7, \[\operatorname{ParDim}(\mathcal{H})\le\operatorname{DSdim}(\mathcal{H})=2.\] Hence 6 gives \[\operatorname{ParDim}(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}))\le2.\] On the other hand, \(\operatorname{DSdim}(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}))\ge3\) by 7. The lower comparison in 1 then gives \[\operatorname{ParDim}(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}))\ge\frac{3}{2}.\] Since \(\operatorname{ParDim}\) is a supremum over integer dimensions and is at most \(2\) here, this forces \[\operatorname{ParDim}(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}))=2.\] ◻

Proof of 1. 5 applied to the rollout class and 6 give \[\mu_{\operatorname{Roll}_\mathtt{halt}(\mathcal{H})}(m) \le \operatorname{ParDim}(\operatorname{Roll}_\mathtt{halt}(\mathcal{H})) \le \operatorname{ParDim}(\mathcal{H}) \qquad\forall m\ge1.\] If \(\operatorname{ParDim}(\mathcal{H})=\infty\), the claimed upper bound is vacuous. Otherwise, \(\operatorname{ParDim}(\mathcal{H})\) is an integer, and \(\mu_{\operatorname{Roll}_\mathtt{halt}(\mathcal{H})}(m)\le\operatorname{ParDim}(\mathcal{H})\) for every \(m\ge1\), so the ceiling in 3 does not change the bound. Apply 3 with \(K=\operatorname{ParDim}(\mathcal{H})\), then apply 4. The DS-dimension version follows from 1. ◻

Proof of 3. Under one-step stopping, \(\operatorname{Roll}_\mathtt{halt}(h)(x)=h(x)\) as a length-one action string. Thus ordinary realizable multiclass learning of \(\mathcal{H}\) embeds into exact-trace learning of \(\operatorname{Roll}_\mathtt{halt}(\mathcal{H})\). The multiclass lower bound in terms of \(\operatorname{DSdim}(\mathcal{H})\) applies to this special case. ◻

Proof of 1. For \(u\in\mathcal{H}|_{D'''}\) and \(\eta\in\mathbb{F}_2^{\mathcal{H}|_{D'}}\), the left-hand side is \[\sum_{\substack{v\in\mathcal{H}|_{D'}:\\ v|_{D'''}=u}}\eta(v).\] The right-hand side first groups each \(v\in\mathcal{H}|_{D'}\) by its restriction to \(D''\), and then sums over exactly those \(D''\)-patterns whose restriction to \(D'''\) is \(u\). It is therefore the same sum. ◻

Proof of 2. For every \(D'\subseteq D\), a function \(f\in J_{D'}^D(\mathcal{H})\) has the form \(f=\phi\circ(u\mapsto u|_{D'})\) for some \(\phi:\mathcal{H}|_{D'}\to\mathbb{F}_2\). Therefore \[\langle\eta,f\rangle = \sum_{w\in\mathcal{H}|_{D'}}\phi(w) \bigl(M_{D'}^D[\mathcal{H}]\eta\bigr)(w).\] Thus \(\eta\) annihilates \(J_{D'}^D(\mathcal{H})\) if and only if \(M_{D'}^D[\mathcal{H}]\eta=0\). Taking the orthogonal complement of the sum defining \(\mathsf L_k^D(\mathcal{H})\) gives the displayed identity. ◻

Proof of 3. If \(0\ne\eta\in \mathsf N_{|D|-1}^D(\mathcal{H})\), then in particular \[M_{D\setminus\{x\}}^D[\mathcal{H}]\eta=0 \qquad\forall x\in D.\] These are precisely the coordinate-deletion marginal conditions in 9, so \(\mathcal{H}|_D\) is an even pseudo-cube on \(D\).

Conversely, suppose \(0\ne\eta\in\mathbb{F}_2^{\mathcal{H}|_D}\) satisfies all coordinate-deletion marginal conditions: \[M_{D\setminus\{x\}}^D[\mathcal{H}]\eta=0 \qquad\forall x\in D.\] For every proper subset \(D''\subsetneq D\), choose \(x\in D\setminus D''\). By 1, \[M_{D''}^D[\mathcal{H}] = M_{D''}^{D\setminus\{x\}}[\mathcal{H}] M_{D\setminus\{x\}}^D[\mathcal{H}]\] shows that \(M_{D''}^D[\mathcal{H}]\eta=0\). Hence \(\eta\in\mathsf N_{|D|-1}^D(\mathcal{H})\), so \(\mathsf N_{|D|-1}^D(\mathcal{H})\ne0\). ◻

Proof of 4. By 2, it suffices to show \(\mathsf N_k^D(\mathcal{H})=0\). Let \(\eta\in \mathsf N_k^D(\mathcal{H})\). If \(\eta=0\), there is nothing to prove. Otherwise, since \(M_D^D[\mathcal{H}]\eta=\eta\ne0\), choose an inclusion-minimal set \(D'\subseteq D\) such that \[\theta:=M_{D'}^D[\mathcal{H}]\eta\ne0.\] For every \(x\in D'\), minimality gives \[M_{D'\setminus\{x\}}^D[\mathcal{H}]\eta=0.\] By 1, \[M_{D'\setminus\{x\}}^{D'}[\mathcal{H}]\theta = M_{D'\setminus\{x\}}^D[\mathcal{H}]\eta =0.\] For every proper subset \(D''\subsetneq D'\), choose \(x\in D'\setminus D''\). By the same factorization argument as in 3, \[M_{D''}^{D'}[\mathcal{H}]\theta = M_{D''}^{D'\setminus\{x\}}[\mathcal{H}] M_{D'\setminus\{x\}}^{D'}[\mathcal{H}]\theta =0.\] Thus \[0\ne\theta\in \mathsf N_{|D'|-1}^{D'}(\mathcal{H}).\] Moreover \(|D'|\ge k+1\), because \(|D'|\le k\) would force \(M_{D'}^D[\mathcal{H}]\eta=0\) from \(\eta\in \mathsf N_k^D(\mathcal{H})\). This contradicts the assumed high-order vanishing. Therefore every \(\eta\in \mathsf N_k^D(\mathcal{H})\) is zero. By 2, \[\bigl(\mathsf L_k^D(\mathcal{H})\bigr)^\perp=0.\] Since \(\mathbb{F}_2^{\mathcal{H}|_D}\) is finite-dimensional, \(\mathsf L_k^D(\mathcal{H})=\mathbb{F}_2^{\mathcal{H}|_D}\). ◻

Proof of 5. This is the same touch-counting mechanism as in the polynomial proof of the multiclass density theorem by [5]. There, one chooses a spanning family of low-support monomials in coordinate-value indicator variables; each basis element touches only the coordinates appearing in that monomial. Here the basis elements are low-coordinate functions, and \(D_b\) records the touched coordinate set for a basis vector \(b\).

Because \(\mathsf L_k^D(\mathcal{H})=\mathbb{F}_2^{\mathcal{H}|_D}\), there exists a basis \[\mathcal{B}\subseteq \bigcup_{\substack{D'\subseteq D\\ |D'|\le k}}J_{D'}^D(\mathcal{H})\] of \(\mathbb{F}_2^{\mathcal{H}|_D}\). For every \(b\in\mathcal{B}\), choose a set \(D_b\subseteq D\) such that \[|D_b|\le k, \qquad b\in J_{D_b}^D(\mathcal{H}).\] For every coordinate \(x\in D\), let \[q_x:\mathbb{F}_2^{\mathcal{H}|_D}\to \mathbb{F}_2^{\mathcal{H}|_D}/J_{D\setminus\{x\}}^D(\mathcal{H})\] be the quotient map. If \(x\notin D_b\), then \(D_b\subseteq D\setminus\{x\}\), so \(b\) does not depend on \(x\). Equivalently, \[b\in J_{D\setminus\{x\}}^D(\mathcal{H}) \quad\text{and}\quad q_x(b)=0.\] The vectors \(q_x(b)\), \(b\in\mathcal{B}\), span the quotient. Therefore only basis vectors with \(x\in D_b\) can contribute to the quotient dimension, and \[\operatorname{codim}J_{D\setminus\{x\}}^D(\mathcal{H}) \le |\{b\in\mathcal{B}:x\in D_b\}|.\] Since \(\dim J_{D\setminus\{x\}}^D(\mathcal{H})=\left|\mathcal{H}|_{D\setminus\{x\}}\right|\), the left-hand side is \(\left|\mathcal{H}|_D\right|-\left|\mathcal{H}|_{D\setminus\{x\}}\right|\). Using 7 and summing the displayed quotient bound over \(x\in D\), \[\begin{align} \left|\mathcal{H}|_D\right|\operatorname{dens}_D(\mathcal{H}|_D) &= \sum_{x\in D}\left(\left|\mathcal{H}|_D\right|-\left|\mathcal{H}|_{D\setminus\{x\}}\right|\right) \le \sum_{x\in D}|\{b\in\mathcal{B}:x\in D_b\}|\\ &= \sum_{b\in\mathcal{B}}|D_b| \le k|\mathcal{B}|=k\left|\mathcal{H}|_D\right|. \end{align}\] Dividing by \(\left|\mathcal{H}|_D\right|\) gives \(\operatorname{dens}_D(\mathcal{H}|_D)\le k\). ◻

Proof of 5. Let \(\mathcal{F}\subseteq\mathcal{Y}^\mathcal{X}\) be a function class. If \(\operatorname{ParDim}(\mathcal{F})=\infty\), there is nothing to prove. Otherwise put \[p=\operatorname{ParDim}(\mathcal{F})<\infty.\] Fix \(n\ge1\), a tuple \(\mathbf{x}=(x_1,\ldots,x_n)\in\mathcal{X}^n\), and a finite nonempty subclass \(\mathcal{H}\subseteq\mathcal{F}\). Put \[\mathcal{G}=\mathcal{H}|_{\mathbf{x}} = \{(h(x_1),\ldots,h(x_n)):h\in\mathcal{H}\} \subseteq\mathcal{Y}^{[n]}.\] We will prove \(\operatorname{dens}_{[n]}(\mathcal{G})\le p\). Since \(\mathbf{x}\) and \(\mathcal{H}\) were arbitrary, this proves the theorem by 7.

The tuple \(\mathbf{x}\) may have repeated entries, so we first show that any high-order even certificate must live on distinct original domain points.

For every coordinate subset \(A\subseteq[n]\) with \(|A|\ge p+1\), the following high-order vanishing holds: \[\mathsf N_{|A|-1}^{A}(\mathcal{G})=0.\] Indeed, suppose otherwise. By 3, \(\mathcal{G}|_A\) is an even pseudo-cube on the coordinate set \(A\). Let \(0\ne\eta\in\mathbb{F}_2^{\mathcal{G}|_A}\) be an even certificate.

First, the original points \(x_i\), \(i\in A\), must be distinct. If \(i\ne j\) in \(A\) and \(x_i=x_j\), then every pattern \(v\in\mathcal{G}|_A\) satisfies \(v(i)=v(j)\). Hence the coordinate-deletion map \(\mathcal{G}|_A\to\mathcal{G}|_{A\setminus\{i\}}\) is injective, because \(v(i)\) is recovered from the remaining coordinate \(j\). Its fibers are singletons, so the deletion-marginal condition at coordinate \(i\) forces \(\eta(v)=0\) for every \(v\in\mathcal{G}|_A\), contradicting \(\eta\ne0\).

Thus the map \(i\mapsto x_i\) is injective on \(A\). Let \(D_A=\{x_i:i\in A\}\). Relabeling each coordinate \(i\in A\) by the distinct domain point \(x_i\) turns \(\mathcal{G}|_A\) into \(\mathcal{H}|_{D_A}\), and preserves the coordinate-deletion marginal conditions. Therefore \(\mathcal{H}|_{D_A}\) is an even pseudo-cube on the domain \(D_A\). Since \(|D_A|=|A|>p\) and \(\mathcal{H}\subseteq\mathcal{F}\), this contradicts the definition of \(p=\operatorname{ParDim}(\mathcal{F})\).

Apply 4 to the finite class \(\mathcal{G}\subseteq\mathcal{Y}^{[n]}\) on the domain \([n]\). The high-order vanishing gives \[\mathsf L_p^{[n]}(\mathcal{G})=\mathbb{F}_2^\mathcal{G}.\] Since \(\mathcal{G}\ne\emptyset\), 5 gives \[\operatorname{dens}_{[n]}(\mathcal{G})\le p.\] Taking the supremum over all tuples \(\mathbf{x}\in\mathcal{X}^n\) and all finite nonempty \(\mathcal{H}\subseteq\mathcal{F}\) gives \[\mu_\mathcal{F}(n)\le p=\operatorname{ParDim}(\mathcal{F}) \qquad\forall n\ge1.\] ◻

Proof of 6. Among all descendants \(v\) of \(u_0\), including \(u_0\) itself, whose block has zero mass for every \(\omega\in\Omega\) and on whose block \(\theta\) is not identically zero, choose one with inclusion-minimal block. Among nodes with that same block, choose \(v\) deepest.

The node \(v\) cannot be a leaf. If \(\operatorname{Blk}(v)=\{\ell\}\), then zero mass gives \(\theta(\ell,\omega)=0\) for every \(\omega\in\Omega\), contrary to nonzero restriction. Hence \(v\) is internal.

If the child quotient at \(v\) were zero, every child \(c\in\operatorname{Ch}(v)\) would have zero mass for every \(\omega\). Since the children partition \(\operatorname{Blk}(v)\) and \(\theta\) is nonzero on \(\operatorname{Blk}(v)\times\Omega\), some child \(c_0\) has nonzero restriction. If \(\operatorname{Blk}(c_0)\subsetneq\operatorname{Blk}(v)\), this contradicts inclusion-minimality. If \(\operatorname{Blk}(c_0)=\operatorname{Blk}(v)\), this contradicts the deepest-node tie breaker. Therefore the child quotient at \(v\) is nonzero. Set \(u=v\).

The final displayed identity follows because the child blocks partition \(\operatorname{Blk}(u)\): \[\sum_{c\in\operatorname{Ch}(u)}Q_u(c,\omega) = \sum_{\ell\in\operatorname{Blk}(u)}\theta(\ell,\omega) = 0.\] ◻

Proof of 8. We use block systems in the sense of 14. Start with the singleton block system in each coordinate. The corresponding quotient tensor is \(\eta\), so it is nonzero and line-even. Invariant: after a set \(S\subseteq[d]\) of coordinates has been processed, the quotient tensor over the child-block systems in coordinates \(S\) and singleton systems elsewhere is nonzero and line-even in every coordinate.

Process coordinates one at a time. Suppose the current quotient tensor is nonzero and line-even, and coordinate \(r\) is still represented by singleton leaf blocks. Treat all other current block choices as a finite parameter set \(\Omega\). For \(\ell\in L_r\) and parameter \(\omega\), let \(\theta(\ell,\omega)\) be the current quotient entry obtained by using \(\{\ell\}\) in coordinate \(r\) and the blocks specified by \(\omega\) in all other coordinates.

Nonzeroness of the current quotient says that \(\theta\) is not identically zero. Line-evenness in coordinate \(r\) says that \[\sum_{\ell\in L_r}\theta(\ell,\omega)=0 \qquad\forall\omega\in\Omega.\] Apply 6 to the root of \(\mathcal{T}_r\). It returns an internal node \(u_r\) whose child quotient is nonzero and child-even. Replace the singleton block system in coordinate \(r\) by the child blocks \(\{\operatorname{Blk}(c):c\in\operatorname{Ch}(u_r)\}\). The active subset in coordinate \(r\) becomes \(\operatorname{Blk}(u_r)\); later quotient tensors are taken over the product of the active block systems.

The new quotient is nonzero by the nonzero child quotient. It is line-even in coordinate \(r\) by the child-even conclusion of 6. For a different coordinate \(q\), the new line sum is a finite sum of old line sums, one for each leaf in a child block \(\operatorname{Blk}(c)\). Each old line sum is zero by the induction invariant. Thus line-evenness in all other coordinates is preserved.

After all coordinates are processed, the quotient tensor has the displayed form and is nonzero and line-even. ◻

Proof of 7. Suppose \(u,v\in L_x\) and \(u\) is a proper prefix of \(v\). The rollout that emits exactly \(u\) stops after emitted suffix \(u\), so \(\mathtt{halt}(x,u)=1\). The rollout that emits \(v\) has the same initial state \(x\) and the same emitted prefix \(u\), but must continue beyond \(u\), so \(\mathtt{halt}(x,u)=0\). This is impossible. ◻

Proof of 9. Extend \(\eta\) by zero to a tensor on \(L_1\times\cdots\times L_d\). This extended tensor is nonzero and line-even in every coordinate because each coordinate-deletion marginal of \(\eta\) is zero: for a fixed coordinate direction \(r\), each full line in \(L_1\times\cdots\times L_d\) intersects \(V\) in one fiber of the restriction map \(V\to V|_{[d]\setminus\{r\}}\), and \(\eta\) has zero sum on every such fiber.

By 7, each \(L_r\) is prefix-free, so it has a prefix partition tree. Apply 8. We get internal prefix nodes \(u_r\) such that \[Q(c_1,\ldots,c_d) = \eta[\operatorname{Blk}(c_1),\ldots,\operatorname{Blk}(c_d)], \qquad c_r\in\operatorname{Ch}(u_r),\] is nonzero and line-even.

A child \(c_r\in\operatorname{Ch}(u_r)\) has the form \(u_ra_r\) for a unique action \(a_r\in\mathcal{A}\). Relabel the child quotient by these actions. Since different children of a prefix correspond to different next actions, this relabeling preserves nonzeroness and line-evenness.

If a relabeled entry \((a_1,\ldots,a_d)\) has coefficient \(1\), then \[\sum_{v\in V\cap(\operatorname{Blk}(u_1a_1)\times\cdots\times\operatorname{Blk}(u_da_d))} \eta(v) = 1 .\] In particular, at least one such tuple has \(\eta(v)=1\), and hence at least one representative \(h\in \mathcal{H}'\) realizes it. For that \(h\), the rollout from \(x_r\) passes through prefix \(u_r\) and then appends \(a_r\), so \[h(x_r\cdot u_r)=a_r.\] Let \[V_{\mathrm{base}} = \{(h(x_1\cdot u_1),\ldots,h(x_d\cdot u_d)):h\in\mathcal{H}'\} \subseteq \mathcal{A}^{[d]} .\] Define a vector \(\xi\in\mathbb{F}_2^{V_{\mathrm{base}}}\) by setting \(\xi(a_1,\ldots,a_d)=Q(a_1,\ldots,a_d)\) on base patterns arising from the relabeled child quotient, and \(\xi=0\) on all other base patterns. The preceding paragraph shows that every support point of \(Q\) is realized in \(V_{\mathrm{base}}\), so \(\xi\) is nonzero. Moreover, the line-evenness of \(Q\) implies that every coordinate-deletion marginal of \(\xi\) is zero: if the fixed \((d-1)\)-pattern uses an action outside the corresponding child sets, all coefficients in that fiber are zero; otherwise the marginal is exactly one of the line sums of \(Q\). Hence \(\xi\) is a nonzero even certificate for the indexed base value table. ◻

Proof of 6. Take a finite witness to \(\operatorname{ParDim}(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}))\). Thus there are a finite state set \(D=\{x_1,\ldots,x_d\}\subseteq \mathcal{X}\) with \(|D|=d\), and a finite nonempty subclass \(U\subseteq\operatorname{Roll}_\mathtt{halt}(\mathcal{H})\), such that \(U|_D\subseteq(\mathcal{A}^*)^D\) is a \(d\)-dimensional even pseudo-cube. Equivalently, after enumerating \(D\) as \(x_1,\ldots,x_d\), the trace table \(V=U|_D\), viewed as a finite class on the indexed domain \([d]\), carries a nonzero vector \(0\ne\eta\in\mathbb{F}_2^V\) whose coordinate-deletion marginals vanish: \[M_{[d]\setminus\{r\}}^{[d]}[V]\eta=0 \qquad\forall r\in[d].\] For every rollout function in \(U\), choose one representative hypothesis in \(\mathcal{H}\) that realizes it; these representatives form a finite set \(\mathcal{H}'\subseteq\mathcal{H}\).

Apply 9 to \(\mathcal{H}'\), the states \(x_1,\ldots,x_d\), and the certificate \(\eta\). We obtain prefixes \(u_1,\ldots,u_d\in\mathcal{A}^*\) and a nonzero parity certificate for the base value table of \(\mathcal{H}'\) on the indexed states \[\widetilde{x}_r=x_r\cdot u_r, \qquad r=1,\ldots,d.\] The states \(\widetilde{x}_1,\ldots,\widetilde{x}_d\) are distinct. Indeed, if \(\widetilde{x}_r=\widetilde{x}_s\) for some \(r\ne s\), then every base value pattern has identical coordinates \(r\) and \(s\). The restriction map deleting coordinate \(r\) is then injective on the indexed base table, so \(M_{[d]\setminus\{r\}}^{[d]}\) has zero kernel on that table. This contradicts the existence of a nonzero certificate in all \(d\) indexed coordinate directions.

Thus \(\widetilde{D}=\{\widetilde{x}_1,\ldots,\widetilde{x}_d\}\) is a finite domain set of size \(d\), and \(\mathcal{H}'|_{\widetilde{D}}\) is a \(d\)-dimensional even pseudo-cube. Hence \(\operatorname{ParDim}(\mathcal{H})\ge d\). Taking the supremum over all rollout witnesses proves the theorem. ◻

Proof of 10. Fix \(y_0\in\mathcal{Y}\). Rephrase the full-label problem as an autoregressive rollout. Let \[\mathcal{E}=\mathcal{U}^\star, \qquad \mathcal{A}=\mathcal{Y}, \qquad \mathcal{X}=\mathcal{E}\times\mathcal{Y}^*.\] For \(g\in\mathcal{G}\), define \(h_g:\mathcal{X}\to\mathcal{Y}\) by \[h_g((u_1,\ldots,u_T),w) = \begin{cases} g(u_{|w|+1}), & |w|<T,\\ y_0, & |w|\ge T. \end{cases}\] Let \(\mathcal{H}_\mathcal{G}=\{h_g:g\in\mathcal{G}\}\). Use the stopping predicate \[\mathtt{halt}((U,w),y)=1 \quad\Longleftrightarrow\quad |y|\ge |U|.\] The class \(\mathcal{H}_\mathcal{G}\) is pointwise \(\mathtt{halt}\)-halting, and the rollout from \((U,\epsilon)\) emits exactly \(g^\star(U)\). Hence \(\mathcal{G}^\star\) is the restriction of \(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}_\mathcal{G})\) to the initial-state slice \(\mathcal{U}^\star\times\{\epsilon\}\).

It remains to compare the local dimensions. We claim that \(\operatorname{ParDim}(\mathcal{H}_\mathcal{G})=\operatorname{ParDim}(\mathcal{G})\). The inequality \(\operatorname{ParDim}(\mathcal{H}_\mathcal{G})\ge\operatorname{ParDim}(\mathcal{G})\) follows from singleton lists: for every local instance \(u\in\mathcal{U}\), \[h_g((u),\epsilon)=g(u).\] For the reverse inequality, take any finite domain set \(D\subseteq\mathcal{U}^\star\times\mathcal{Y}^*\). A state \(((u_1,\ldots,u_T),w)\in D\) with \(|w|<T\) queries the local coordinate \(u_{|w|+1}\); a state with \(|w|\ge T\) is constant equal to \(y_0\). If an even certificate on \(\mathcal{H}_\mathcal{G}|_D\) used a constant coordinate, then the marginal deleting that coordinate would be injective and would have zero kernel. The certificate would be zero, a contradiction. Likewise, if two coordinates in \(D\) queried the same local instance \(u\), then deleting one of them would leave the other one, so the deletion marginal would again be injective. Therefore every nonzero even certificate on \(\mathcal{H}_\mathcal{G}|_D\) uses distinct nonconstant local coordinates, and the same vector is an even certificate for the restriction of \(\mathcal{G}\) to those local coordinates. Thus \(\operatorname{ParDim}(\mathcal{H}_\mathcal{G})\le\operatorname{ParDim}(\mathcal{G})\).

Since \(\mathcal{G}^\star\) is the restriction of \(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}_\mathcal{G})\) to the initial-state slice \(\mathcal{U}^\star\times\{\epsilon\}\), any learner for \(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}_\mathcal{G})\) gives a learner for \(\mathcal{G}^\star\). By 1 and \(\operatorname{ParDim}(\mathcal{G})\le\operatorname{DSdim}(\mathcal{G})\), \[n_{\operatorname{PAC}}^{\varepsilon,\delta}(\mathcal{G}^\star) \le O\!\left( \frac{\operatorname{DSdim}(\mathcal{G})+\log(1/\delta)}{\varepsilon} \right).\] The lower bound is the singleton-list embedding. Any local example \((u,g(u))\) is the full-label example \(((u),(g(u)))\), so learning \(\mathcal{G}^\star\) is at least as hard as learning this fixed local class \(\mathcal{G}\). The lower-bound half of the standard sharp realizable multiclass PAC theorem, due to [9], [13], and [5], gives \[n_{\operatorname{PAC}}^{\varepsilon,\delta}(\mathcal{G}) \ge \Omega\!\left( \frac{\operatorname{DSdim}(\mathcal{G})+\log(1/\delta)}{\varepsilon} \right)\] whenever \(\operatorname{DSdim}(\mathcal{G})\ge1\). Together with the preceding upper bound, this gives the displayed \(\Theta\)-rate.

If \(\operatorname{DSdim}(\mathcal{G})=0\), then no one-point domain is DS-shattered. Hence all functions in \(\mathcal{G}\) agree on every \(u\in\mathcal{U}\), so all functions in \(\mathcal{G}^\star\) agree on every finite list \(U\in\mathcal{U}^\star\). The realizable problem has no label uncertainty, and \(n_{\operatorname{PAC}}^{\varepsilon,\delta} (\mathcal{G}^\star)=0\). ◻

Proof of 11. See 10. ◻

Proof of 1. The upper density bound \[\sup_{n\ge1}\mu_\mathcal{H}(n) \le \operatorname{ParDim}(\mathcal{H})\] is exactly 5.

Next, \(\operatorname{ParDim}(\mathcal{H})\le\operatorname{DSdim}(\mathcal{H})\) follows directly from the definitions. Suppose \(D\subseteq\mathcal{X}\) is finite, \(\mathcal{H}'\subseteq\mathcal{H}\) is finite and nonempty, and \(\mathcal{H}'|_D\) is an even pseudo-cube on \(D\). Let \(0\ne\eta\in\mathbb{F}_2^{\mathcal{H}'|_D}\) be an even certificate, and let \[Q=\operatorname{supp}(\eta)\subseteq\mathcal{H}'|_D.\] For every \(q\in Q\) and every \(x\in D\), the coordinate-deletion fiber of \(\mathcal{H}'|_D\to\mathcal{H}'|_{D\setminus\{x\}}\) containing \(q\) has zero \(\eta\)-sum. Since \(\eta(q)=1\), that fiber contains another point \(q'\in Q\). Then \(q'\) agrees with \(q\) on \(D\setminus\{x\}\) and differs at \(x\). Thus \(Q\) is a pseudo-cube on \(D\).

It remains to prove the lower density comparison \[\frac{1}{2}\operatorname{DSdim}(\mathcal{H})\le \sup_{n\ge1}\mu_\mathcal{H}(n).\] This comparison is recalled in [5]; we give the elementary proof in the present normalization. Let \(D\subseteq\mathcal{X}\) have size \(d\ge1\), and let \(Q\subseteq\mathcal{H}|_D\) be a finite pseudo-cube on \(D\). Choose a finite subclass \(\mathcal{H}'\subseteq\mathcal{H}\) with \(\mathcal{H}'|_D=Q\). Order \(D\) as \(D=\{x_1,\ldots,x_d\}\) and put \(\mathbf{x}=(x_1,\ldots,x_d)\). Then \(\mathcal{H}'|_{\mathbf{x}}\subseteq\mathcal{Y}^{[d]}\) is obtained from \(Q\subseteq\mathcal{Y}^D\) by relabeling the coordinate \(x_i\) as \(i\), so \[\mu_\mathcal{H}(d)\ge \operatorname{dens}_{[d]}(\mathcal{H}'|_{\mathbf{x}})=\operatorname{dens}_D(Q).\] It suffices to prove \[\operatorname{dens}_D(Q)\ge \frac{d}{2}.\] Fix \(x\in D\). Every fiber of the restriction map \[Q\to Q|_{D\setminus\{x\}}\] has size at least \(2\), because the pseudo-cube property supplies, for every point in the fiber, another point with the same \(D\setminus\{x\}\)-restriction and a different value at \(x\). Hence \[\left|Q|_{D\setminus\{x\}}\right| \le \frac{|Q|}{2}.\] Using 7, \[\operatorname{dens}_D(Q) = \frac{1}{|Q|}\sum_{x\in D} \left(|Q|-\left|Q|_{D\setminus\{x\}}\right|\right) \ge \frac{d}{2}.\] Taking the supremum over all positive-dimensional DS witnesses gives the lower density comparison.

For binary classes, \(\operatorname{DSdim}(\mathcal{H})=\operatorname{VCdim}(\mathcal{H})\) by the usual equivalence between binary pseudo-cubes and VC-shattered sets. Conversely, if \(D\) is VC-shattered by a binary class, then the full binary cube \(\{0,1\}^D\) has the all-one vector as an even certificate: every coordinate-deletion fiber has exactly two points, so its \(\mathbb{F}_2\)-sum is zero. Hence \(\operatorname{ParDim}(\mathcal{H})\ge\operatorname{VCdim}(\mathcal{H})\), while the already proved inequality \(\operatorname{ParDim}(\mathcal{H})\le\operatorname{DSdim}(\mathcal{H})=\operatorname{VCdim}(\mathcal{H})\) gives equality. ◻

Proof of 11. Let \(q=\lfloor\log_2 T_{\max}\rfloor\), so \(q\ge1\), and let \[\mathcal{U}=\{\star\}\sqcup\{(j,\sigma):j\in[d],\;\sigma\in\{0,1\}^q\}.\] For \[a=(a_1,\ldots,a_d)\in(\{0,1\}^q\cup\{\bot\})^d,\] define \(g_a:\mathcal{U}\to\{0,1\}\) by \[g_a(j,\sigma)=1 \quad\Longleftrightarrow\quad a_j=\sigma, \qquad g_a(\star)=0.\] Let \[\mathcal{G}=\{g_a:a\in(\{0,1\}^q\cup\{\bot\})^d\}.\] The all-zero target is \(g_\bot=g_{(\bot,\ldots,\bot)}\).

We first check the dimension. The class \(\mathcal{G}\) shatters the \(d\)-point set \[\{(1,0^q),\ldots,(d,0^q)\},\] because coordinate \(j\) is labeled one by setting \(a_j=0^q\) and labeled zero by setting \(a_j=\bot\). Conversely, no set of size \(d+1\) is VC-shattered. If the set contains \(\star\), then \(\star\) is always labeled zero. Otherwise, by the pigeonhole principle, two selected points have the same block index \(j\). For a fixed \(j\), every \(g_a\) labels at most one point \((j,\sigma)\) by one, so the all-ones labeling on those two points is impossible. Thus \(\operatorname{VCdim}(\mathcal{G})=d\), and \(\operatorname{DSdim}(\mathcal{G})=d\) because the class is binary.

For every \(j\in[d]\) and \(r\in[q]\), define the rare list \[U_{j,r}=((j,\sigma):\sigma_r=1),\] with an arbitrary fixed ordering. Its length is \(2^{q-1}\le T_{\max}\). Also define the dummy list \(U_0=(\star)\). All labels below are generated by the target \(g_\bot\), so every observed full-label list is all zero.

Let \(N=dq\) and put \(\rho=8\varepsilon\). Define a realizable distribution \(\mathcal{D}\) by \[\Pr_{\mathcal{D}}[U=U_{j,r}]=\frac{\rho}{N} \quad (j\in[d],\;r\in[q]), \qquad \Pr_{\mathcal{D}}[U=U_0]=1-\rho,\] with labels \(g_\bot^\star(U)\). Since \(\varepsilon\le1/16\), this is a probability distribution.

Let \(S\sim\mathcal{D}^n\), and let \(\widehat g\) be drawn uniformly from the proper version space \(V_\mathcal{G}(S)\). The target \(g_\bot\) is always in the version space, so the version space is nonempty. Conditional on \(S\), consider a rare list \(U_{j,r}\) that did not appear in the sample. Let \(B_j(S)\subseteq[q]\) be the set of rare-list indices \(s\) for which \(U_{j,s}\) did appear in \(S\). A spike \(a_j\in\{0,1\}^q\) is consistent with the observed all-zero lists in block \(j\) if and only if \[(a_j)_s=0 \qquad\forall s\in B_j(S).\] Among the consistent choices for the \(j\)-th component, there is also the zero choice \(a_j=\bot\). Since \(r\notin B_j(S)\), if \[u=q-|B_j(S)|\ge1\] is the number of unobserved bit coordinates in block \(j\), then the number of consistent spike choices is \(2^u\), and exactly \(2^{u-1}\) of them have \((a_j)_r=1\). Such choices put a one somewhere in \(U_{j,r}\), and therefore make a full-label mistake on \(U_{j,r}\). Hence, conditional on \(S\), \[\Pr_{\widehat g\sim V_\mathcal{G}(S)} [\widehat g^\star(U_{j,r})\ne g_\bot^\star(U_{j,r})] = \frac{2^{u-1}}{1+2^u} \ge \frac{1}{3} .\]

Taking expectation over the sample and the random ERM draw gives \[\mathbb{E}[ \operatorname{err}_{\mathcal{D}}(\widehat g^\star)] \ge \frac{\rho}{3} \left(1-\frac{\rho}{N}\right)^n.\] Indeed, each rare list has mass \(\rho/N\), and the probability that a fixed rare list is absent from \(n\) iid samples is \((1-\rho/N)^n\).

If \[n\le \frac{N}{4\rho},\] then \[\left(1-\frac{\rho}{N}\right)^n \ge 1-\frac{\rho n}{N} \ge \frac{3}{4},\] and therefore \[\mathbb{E}[ \operatorname{err}_{\mathcal{D}}(\widehat g^\star)] \ge \frac{\rho}{4} = 2\varepsilon.\] The error of \(\widehat g^\star\) is supported only on the rare lists, whose total mass is \(\rho=8\varepsilon\). Hence \[2\varepsilon \le \mathbb{E}[ \operatorname{err}_{\mathcal{D}}(\widehat g^\star)] \le \varepsilon\, \Pr[\operatorname{err}_{\mathcal{D}}(\widehat g^\star)\le\varepsilon] + 8\varepsilon\, \Pr[\operatorname{err}_{\mathcal{D}}(\widehat g^\star)>\varepsilon].\] Thus \[\Pr[\operatorname{err}_{\mathcal{D}}(\widehat g^\star)>\varepsilon] \ge \frac{1}{7} \ge \frac{1}{8}.\] Since \(N=dq\), the implication holds with \(c=1/32\). This proves the theorem. ◻

Proof of 12. Let \(\mathsf{Alg}\) be an online learning rule for the local class \(\mathcal{H}\) with mistake bound \(M\). After the current local history, let \(\widehat h:\mathcal{X}\to\mathcal{A}\) denote the current prediction map induced by \(\mathsf{Alg}\): on a local instance \(v\in\mathcal{X}\), \(\widehat h(v)\) is the label that \(\mathsf{Alg}\) would currently predict at \(v\).

On a trace-level round with start state \(x\in\mathcal{X}\), use a halting oracle to decide whether the deterministic rollout of \(\widehat h\) from \(x\) under \(\mathtt{halt}\) terminates. If it terminates, simulate it until termination and predict the finite trace \[\widehat y=\operatorname{Roll}_\mathtt{halt}(\widehat h)(x).\] If it does not terminate, predict \(\widehat y=\epsilon\).

After the true trace \(y=\operatorname{Roll}_\mathtt{halt}(h^\star)(x)\) is revealed, do nothing if \(\widehat y=y\). Suppose first that the oracle said that \(\widehat h\) terminates and the finite prediction \(\widehat y\) is wrong. Then \(\widehat y\) and \(y\) are both terminal traces from the same start state \(x\). They cannot be strict prefixes of each other: if the shorter string has already halted, then the same deterministic stopping predicate would also stop the other rollout at the same emitted suffix. Hence there is a first position at which the two action strings differ. Let \(u\in\mathcal{A}^*\) be their common prefix before that first disagreement. The current local predictor makes a local mistake at the aligned state \(x\cdot u\): \[\widehat h(x\cdot u)\ne h^\star(x\cdot u).\] Feed the labeled local example \((x\cdot u,h^\star(x\cdot u))\) to \(\mathsf{Alg}\).

It remains to handle the case where the oracle said that \(\widehat h\) does not terminate, so the trace learner predicted \(\epsilon\), and this prediction is wrong. Then \(y\ne\epsilon\): if \(y=\epsilon\), then \(\mathtt{halt}(x,\epsilon)=1\), so every rollout from \(x\), including the rollout of \(\widehat h\), would terminate immediately. Write the nonempty true trace as \(y=a_1\cdots a_T\). For \(t\in[T]\), let \(u_t=a_1\cdots a_{t-1}\) be the prefix before the \(t\)-th true action. There must be a first \(t\) such that \[\widehat h(x\cdot u_t)\ne h^\star(x\cdot u_t).\] Indeed, if \(\widehat h\) agreed with \(h^\star\) at all prefix states \(x\cdot u_t\) along the true trace, then \(\widehat h\) would emit the entire string \(y\). Since \(\mathtt{halt}(x,y)=1\), it would then terminate after \(y\), contradicting the halting oracle’s nontermination answer. Feed the labeled local example \((x\cdot u_t,h^\star(x\cdot u_t))\) to \(\mathsf{Alg}\).

Every complete-trace online mistake causes exactly one genuine local online mistake update by the current local prediction map. Therefore the halting-oracle-assisted complete-trace online learner makes at most \(M\) mistakes on every realizable online stream, proving the claim. ◻

Proof of 8. For (i), fix \(u=q|_B\in Q|_B\) and a coordinate \(x\in B\). Since \(Q\) is a pseudo-cube, there exists \(q'\in Q\) such that \(q'(x)\ne q(x)\) and \(q'\) agrees with \(q\) on \(D\setminus\{x\}\). Then \(q'|_B\) differs from \(u\) at \(x\) and agrees with \(u\) on \(B\setminus\{x\}\).

For (ii), fix \((r,c)\in Q_\alpha\). Since \(Q\) is a \(3\)-pseudo-cube, the point \((\alpha,r,c)\) has a flip in the \(R\)-coordinate and a flip in the \(C\)-coordinate while the \(L\)-coordinate remains \(\alpha\). Thus \(Q_\alpha\) has a row flip and a column flip at \((r,c)\). This is exactly the \(2\)-pseudo-cube condition on \(R\times C\).

For (iii), a \(2\)-pseudo-cube \(Q\subseteq S\) would be a nonempty edge set such that every edge has another edge sharing its row and another edge sharing its column. Hence every vertex incident to an edge of \(Q\) has degree at least two in the subgraph induced by \(Q\). A finite graph with minimum degree at least two contains a cycle, contradicting that the ambient row–column graph is a forest. ◻

Proof of 7. Construction. Let \[\begin{align} \mathcal{A}_{\mathrm{sgn}}&=\{\mathsf P,\mathsf N\},& \mathcal{A}_{\mathsf P}&=\{\mathsf P_1,\mathsf P_2\},& \mathcal{A}_{\mathsf N}&=\{\mathsf N_1,\mathsf N_2\},\\ \mathcal{A}_{\mathrm{row}}&=\{R_0,R_1,R_2\},& \mathcal{A}_{\mathrm{col}}&=\{C_0,C_1,C_2,C_3\},& \mathcal{A}_{\mathrm{off}}&=\{\bot\}. \end{align}\] The action alphabet is the disjoint union \[\mathcal{A}= \mathcal{A}_{\mathrm{sgn}}\sqcup\mathcal{A}_{\mathsf P}\sqcup\mathcal{A}_{\mathsf N} \sqcup\mathcal{A}_{\mathrm{row}}\sqcup\mathcal{A}_{\mathrm{col}} \sqcup\mathcal{A}_{\mathrm{off}}.\] The action \(\bot\) is an ordinary off-branch action. It is not a stopping token, and the root rollouts used below never emit it. Let \(\mathcal{E}=\{1,2,3\}\), let \(\mathcal{X}=\mathcal{E}\times\mathcal{A}^*\), and use the stopping predicate \[\begin{align} \mathtt{halt}((e,w),y)=0 \quad\Longleftrightarrow\quad& \bigl(w=\epsilon,\;e=1,\;|y|<2\bigr)\\ &\text{or } \bigl(w=\epsilon,\;e\in\{2,3\},\;|y|<1\bigr). \end{align}\] Thus only rollouts started from root states \(w=\epsilon\) emit new actions; non-root start states halt immediately. Define a sign map \[\beta(\mathsf P_1)=\beta(\mathsf P_2)=\mathsf P, \qquad \beta(\mathsf N_1)=\beta(\mathsf N_2)=\mathsf N.\]

We first define the index set of hypotheses. For \(r\in\{0,1,2\}\) and \(s\in\{0,1,2,3\}\), let \(T_{r,s}\subseteq\{\mathsf P_1,\mathsf P_2,\mathsf N_1,\mathsf N_2\}\) be given by \[\begin{array}{c|cccc} & s=0&s=1&s=2&s=3\\ \hline r=0&\mathsf N_1\mathsf N_2& \mathsf P_1\mathsf P_2\mathsf N_1\mathsf N_2& \mathsf P_1\mathsf P_2& \mathsf P_2\mathsf N_2\\ r=1&\mathsf P_1\mathsf P_2& \mathsf N_1\mathsf N_2& \mathsf P_1\mathsf N_2& \mathsf P_2\mathsf N_1\\ r=2&\mathsf P_1\mathsf P_2\mathsf N_1\mathsf N_2& \mathsf P_1\mathsf P_2& \mathsf P_2\mathsf N_2& \mathsf N_1\mathsf N_2. \end{array}\] For every triple \((\ell,r,s)\) with \(\ell\in T_{r,s}\), define a next-action rule \[h_{\ell,r,s}:\mathcal{X}\to\mathcal{A}.\] The class is \[\mathcal{H}=\{h_{\ell,r,s}:\ell\in T_{r,s}\}.\] Thus \(\mathcal{H}\) has \(28\) hypotheses.

The rule \(h_{\ell,r,s}\) is defined as follows. In environment \(1\), it first emits the block \(\beta(\ell)\), then emits \(\ell\), and then the stopping predicate halts: \[h_{\ell,r,s}(1,\epsilon)=\beta(\ell),\] \[h_{\ell,r,s}(1,\mathsf P)= \begin{cases} \ell,&\beta(\ell)=\mathsf P,\\ \bot,&\beta(\ell)=\mathsf N, \end{cases} \qquad h_{\ell,r,s}(1,\mathsf N)= \begin{cases} \bot,&\beta(\ell)=\mathsf P,\\ \ell,&\beta(\ell)=\mathsf N. \end{cases}\] In environments \(2\) and \(3\), it emits the row and column labels: \[h_{\ell,r,s}(2,\epsilon)=R_r,\] \[h_{\ell,r,s}(3,\epsilon)=C_s.\] All unspecified states output \(\bot\). The stopping rule above ensures pointwise halting, and the root rollouts used below never query a state whose returned action is \(\bot\). Therefore \[\operatorname{Roll}_\mathtt{halt}(h_{\ell,r,s})(1,\epsilon)=\beta(\ell)\ell, \qquad \operatorname{Roll}_\mathtt{halt}(h_{\ell,r,s})(2,\epsilon)=R_r, \qquad \operatorname{Roll}_\mathtt{halt}(h_{\ell,r,s})(3,\epsilon)=C_s.\] The construction separates what a rollout can see from what a single base query can see. In environment \(1\), the rollout sees both the sign \(\beta(\ell)\) and then the refined token \(\ell\); a base query can ask only one of the states \((1,\epsilon),(1,\mathsf P),(1,\mathsf N)\) at a time. Environments \(2\) and \(3\) reveal the row \(r\) and column \(s\).

The intended reading is a two-level sign code. The symbols \(\mathsf P,\mathsf N\) are coarse signs: \[\mathsf P\text{-block}=\{\mathsf P_1,\mathsf P_2\}, \qquad \mathsf N\text{-block}=\{\mathsf N_1,\mathsf N_2\}.\] The state \((1,\epsilon)\) reveals only the coarse sign. The state \((1,\mathsf P)\) reveals the refined token only inside the \(\mathsf P\)-block and returns the off-branch action \(\bot\) on the \(\mathsf N\)-block; the state \((1,\mathsf N)\) does the symmetric thing. Thus a single base query sees only one layer of this two-level code, while a rollout from environment \(1\) first sees the sign and then follows the matching branch to recover the refined token.

The table \(T_{r,s}\) is chosen to have two opposite behaviors. For the rollout lower bound, the full table \[P=\{(\ell,r,s):\ell\in T_{r,s}\}\] has enough local redundancy: every cell contains at least two refined tokens, and for each fixed refined token \(\ell\), its row-column support has no row or column leaf. This gives flips in the refined-token, row, and column coordinates. For the base upper bound, every possible single-layer view is acyclic. More precisely, the mixed-sign cells, the cells containing both \(\mathsf P_1,\mathsf P_2\), and the cells containing both \(\mathsf N_1,\mathsf N_2\) are all forests as row-column graphs. Any hypothetical base \(3\)-pseudo-cube must place one first-coordinate slice inside one of these forests, where a row-column \(2\)-pseudo-cube cannot live. The table is therefore a masking gadget: rollout unmasks a \(3\)-dimensional pseudo-cube, but every base view remains only \(2\)-dimensional.

The rollout class has a \(3\)-pseudo-cube. We prove first that \(\operatorname{DSdim}(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}))\ge3\). Let \[x_1=(1,\epsilon), \qquad x_2=(2,\epsilon), \qquad x_3=(3,\epsilon).\] The restriction of the rollout class to \(\{x_1,x_2,x_3\}\) contains, after injectively relabeling the three coordinates, the set \[P=\{(\ell,r,s):\ell\in T_{r,s}\} \subseteq \{\mathsf P_1,\mathsf P_2,\mathsf N_1,\mathsf N_2\}\times\{0,1,2\}\times\{0,1,2,3\}.\] We claim that \(P\) is a \(3\)-pseudo-cube. Every cell \(T_{r,s}\) has size at least two, so every point \((\ell,r,s)\in P\) has a flip in the refined-token coordinate. For flips in the other two coordinates, write \[G_\ell=\{(r,s):\ell\in T_{r,s}\}.\] From the displayed table, \[\begin{align} G_{\mathsf P_1}&=\{(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)\},\\ G_{\mathsf P_2}&=\{(0,1),(0,2),(0,3),(1,0),(1,3),(2,0),(2,1),(2,2)\},\\ G_{\mathsf N_1}&=\{(0,0),(0,1),(1,1),(1,3),(2,0),(2,3)\},\\ G_{\mathsf N_2}&=\{(0,0),(0,1),(0,3),(1,1),(1,2),(2,0),(2,2),(2,3)\}. \end{align}\] In each \(G_\ell\), every row that appears has degree at least two and every column that appears has degree at least two. Hence each \((\ell,r,s)\in P\) has an \(r\)-coordinate flip and an \(s\)-coordinate flip. Thus \(P\) is a \(3\)-pseudo-cube, and \[\operatorname{DSdim}(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}))\ge3.\]

The base class has a \(2\)-pseudo-cube. Next we show \(\operatorname{DSdim}(\mathcal{H})=2\). For the lower bound, restrict \(\mathcal{H}\) to the two base states \[x_0=(1,\epsilon), \qquad x_R=(2,\epsilon).\] The four hypotheses \[h_{\mathsf P_1,0,1},\quad h_{\mathsf P_1,1,0},\quad h_{\mathsf N_1,0,0},\quad h_{\mathsf N_1,1,1}\] realize the four value pairs \[(\mathsf P,R_0),\quad (\mathsf P,R_1),\quad (\mathsf N,R_0),\quad (\mathsf N,R_1).\] These form a \(2\)-pseudo-cube, so \(\operatorname{DSdim}(\mathcal{H})\ge2\).

No base \(3\)-pseudo-cube. It remains to prove \(\operatorname{DSdim}(\mathcal{H})\le2\). The only nonconstant base states are \[x_0=(1,\epsilon), \qquad x_{\mathsf P}=(1,\mathsf P), \qquad x_{\mathsf N}=(1,\mathsf N), \qquad x_R=(2,\epsilon), \qquad x_C=(3,\epsilon).\] A positive-dimensional pseudo-cube cannot use a constant coordinate, so every three-dimensional base witness would have to use three states among these five. Moreover, by 8(i), any base pseudo-cube of dimension at least \(3\) restricts to a \(3\)-pseudo-cube on any three of its coordinates, so ruling out three-state witnesses also rules out every witness of dimension greater than three. It therefore suffices to show that no three of these five states carry a \(3\)-pseudo-cube.

The row-column obstruction used below is the following. After relabeling the two row-column coordinates \(x_R,x_C\) by \((r,s)\), let \(E\) be the mixed-sign cells, let \(F_{\mathsf P}\) be the cells containing both \(\mathsf P_1\) and \(\mathsf P_2\), and let \(F_{\mathsf N}\) be the cells containing both \(\mathsf N_1\) and \(\mathsf N_2\). Explicitly, \[\begin{align} E&=\{(0,1),(0,3),(1,2),(1,3),(2,0),(2,2)\},\\ F_{\mathsf P}&=\{(0,1),(0,2),(1,0),(2,0),(2,1)\},\\ F_{\mathsf N}&=\{(0,0),(0,1),(1,1),(2,0),(2,3)\}. \end{align}\] Equivalently, the three projections have the following row-column tables, where a bullet marks an included cell:

The row-column graphs in [tab:counterexample-mixed-sign,tab:counterexample-p-block,tab:counterexample-n-block] are forests: \(E\) is the path \[s=1\;--\;r=0\;--\;s=3\;--\;r=1\;--\;s=2\;--\;r=2\;--\;s=0,\] \(F_{\mathsf P}\) is the path \[s=2\;--\;r=0\;--\;s=1\;--\;r=2\;--\;s=0\;--\;r=1,\] and \(F_{\mathsf N}\) is the path \[r=1\;--\;s=1\;--\;r=0\;--\;s=0\;--\;r=2\;--\;s=3.\] By 8, none of the three obstruction graphs in [tab:counterexample-mixed-sign,tab:counterexample-p-block,tab:counterexample-n-block] contains a \(2\)-pseudo-cube. The remaining proof only uses this fact.

First, no such witness can use two of \(x_0,x_{\mathsf P},x_{\mathsf N}\). Indeed, the projections to the three pairs \[(x_0,x_{\mathsf P}),\qquad (x_0,x_{\mathsf N}),\qquad (x_{\mathsf P},x_{\mathsf N})\] are respectively \[\{(\mathsf P,\mathsf P_1),(\mathsf P,\mathsf P_2),(\mathsf N,\bot)\},\] \[\{(\mathsf P,\bot),(\mathsf N,\mathsf N_1),(\mathsf N,\mathsf N_2)\},\] and \[\{(\mathsf P_1,\bot),(\mathsf P_2,\bot),(\bot,\mathsf N_1),(\bot,\mathsf N_2)\}.\] Each of these three row–column graphs is a forest, so by 8 none contains a \(2\)-pseudo-cube. Since projections of pseudo-cubes are pseudo-cubes by 8, no \(3\)-pseudo-cube can use two of \(x_0,x_{\mathsf P},x_{\mathsf N}\). Hence a three-dimensional base witness must use one of \[\{x_0,x_R,x_C\}, \qquad \{x_{\mathsf P},x_R,x_C\}, \qquad \{x_{\mathsf N},x_R,x_C\}.\] We rule out these three cases.

For \(\{x_0,x_R,x_C\}\), the first coordinate is the sign value \(\mathsf P\) or \(\mathsf N\). Let \(Q\) be a hypothetical \(3\)-pseudo-cube on these three states, and take a first-coordinate value \(\alpha\in\{\mathsf P,\mathsf N\}\) that appears in \(Q\). By 8, the \(\alpha\)-slice of \(Q\), viewed on the row-column coordinates \(x_R,x_C\), is a \(2\)-pseudo-cube. But every point in this slice must also be able to flip the \(x_0\)-coordinate while keeping \((r,s)\) fixed. Thus each row-column pair in the slice must be a mixed-sign cell, so the slice is contained in the forest in 2, impossible.

For \(\{x_{\mathsf P},x_R,x_C\}\), the first coordinate takes values \(\mathsf P_1,\mathsf P_2,\bot\). Let \(Q\) be a hypothetical \(3\)-pseudo-cube. If the \(\bot\)-slice is nonempty, then it is a row-column \(2\)-pseudo-cube by 8. A \(\bot\)-value at \(x_{\mathsf P}\) comes from an \(\mathsf N\)-token, and flipping the \(x_{\mathsf P}\)-coordinate requires a \(\mathsf P\)-token in the same cell. Hence the \(\bot\)-slice is contained in the mixed-sign forest in 2, impossible.

Therefore \(Q\) has no \(\bot\)-points. Choose a surviving value \(v\in\{\mathsf P_1,\mathsf P_2\}\). The \(v\)-slice is again a row-column \(2\)-pseudo-cube. To see where this slice lives, take any point in it, say with row-column pair \((r,s)\). This point has the form \((v,R_r,C_s)\). Since \(Q\) is a \(3\)-pseudo-cube, this point must have an \(x_{\mathsf P}\)-coordinate flip while the \(x_R\)- and \(x_C\)-coordinates stay equal to \(R_r\) and \(C_s\). The flipped value cannot be \(\bot\), because \(Q\) has no \(\bot\)-points. Thus the same cell \(T_{r,s}\) must contain both \(\mathsf P_1\) and \(\mathsf P_2\). Hence the \(v\)-slice is contained in the within-\(\mathsf P\) forest in 3, impossible.

The case \(\{x_{\mathsf N},x_R,x_C\}\) is symmetric. A nonempty \(\bot\)-slice would be a row-column \(2\)-pseudo-cube contained in the mixed-sign forest in 2: here the \(\bot\)-value at \(x_{\mathsf N}\) comes from a \(\mathsf P\)-token, and the \(x_{\mathsf N}\)-coordinate flip requires an \(\mathsf N\)-token in the same cell. Thus no \(\bot\)-point remains. For any surviving value \(v\in\{\mathsf N_1,\mathsf N_2\}\), each point \((v,R_r,C_s)\) in the \(v\)-slice must flip its \(x_{\mathsf N}\)-coordinate without changing \(R_r,C_s\). Since \(\bot\)-points are absent, that flip must use the other \(\mathsf N\)-token in the same cell. Hence the \(v\)-slice is contained in the within-\(\mathsf N\) forest in 4, again impossible.

We have ruled out every possible three-state base witness. Therefore \(\operatorname{DSdim}(\mathcal{H})\le2\). Together with the lower bound, \(\operatorname{DSdim}(\mathcal{H})=2\), while \(\operatorname{DSdim}(\operatorname{Roll}_\mathtt{halt}(\mathcal{H}))\ge3\). ◻