Towards reflection with relative optimal predictor schemes

[Vanessa Kosoy]

We construct a family or oracles relative to which all estimation problems which have approximate solutions in exponential time are generatable. Relatively to these oracles, we can use the optimal predictor scheme $\Lambda$ for assigning expectation values to arbitrary deterministic computations within time that is superquasipolynomial in the logarithm of the computation time. In particular, this should allow reflection in the sense of Garrabrant once we succeed to derandomize $\Lambda$ relative to the same oracle.

Results

New notation

Given $O\subseteq \{0,1{\}}^{\ast }$ and appropriate sets $X$ and $Y$, $A:X\stackrel{O}{\to }Y$ denotes a pair consisting of $O$ and an oracle machine that, supplied with oracle $O$, halts on every input in $X$ and produces an output in $Y$. In particular, it defines a function from $X$ to $Y$ in the obvious way.

For every $n\in N$, we fix a prefix free universal oracle machine $U{O}_n$ with one program tape, $n$ input tapes and one output tape (we are only going to use a finite number of $n$s). Given $O\subseteq \{0,1{\}}^{\ast }$, $e{v}_{O,n}:N\times {\{0,1{\}}^{\ast }}^{n+1}\stackrel{O}{\to }\{0,1{\}}^{\ast }$ is the following. When $e{v}_{O,n}^k(Q,x_1\dots x_n)$ is computed, $Q$ is interpreted as a program for $U{O}_n$ and $Q(x_1\dots x_n)$ is executed with oracle $O$ for time $k$. The resulting output is produced.

The notation $e{v}_O^k(Q,x_1\dots x_n)$ means $e{v}_{O,n}^k(Q,x_1\dots x_n)$.

Given $A:X\stackrel{O}{\to }Y$ and $X^{\prime }\subseteq X$, $T_A\left(X^{\prime }\right)$ will denote the maximal runtime of $A$ on elements of $X^{\prime }$. $Q_A\left(X^{\prime }\right)$ will denote the set of queries made to the oracle when applying $A$ to elements of $X^{\prime }$.

All the theory of predictors with logarithmic advice can be relativized with respect to an arbitrary oracle. We denote the corresponding concepts using the oracle as a superscript. For example, the relativized version of a $\Delta (poly,log)$-optimal predictor schemes is $\Delta (poly,log{)}^O$-optimal predictor schemes etc.

Given $\mu$ a word ensemble, $\mathrm{supp}\mu$ denotes ${\bigcup }_{k\in N}\mathrm{supp}{\mu }^k$. We previously defined a distributional estimation problem to be a pair $(f,\mu )$ where $\mu$ is a word ensemble and $f$ is a function from $\{0,1{\}}^{\ast }$ to $[0,1]$. From now on, we allow $f$ to be defined only on $\mathrm{supp}\mu$. This doesn’t affect any of the previous results.

Omitting parentheses after an error space will mean zero advice. For example a $\Delta$-sampler is a $\Delta \left(0\right)$-sampler.

---

We start by constructing an exponential time estimation problem which is complete in the class of exponential time estimation problem with samplable word ensembles with respect to $\Delta$-pseudo-invertible reductions (the concept of $\Delta$-pseudo-invertible reductions was previously introduced for unidistributional problems but it is defined in the same day for distributional problems, see Appendix A). Everything is relative to an arbitrary fixed oracle.

Construction 1

Fix $O\subseteq \{0,1{\}}^{\ast }$.

Define ${\mu }_{Samp\left(O\right)}$ to be the following word ensemble. Sampling ${\mu }_{Samp\left(O\right)}^k$ is equivalent to sampling $S$, $F$ and $y$ independently from $U^k$ and producing $(k,S,F,e{v}_O^k(S,k,y\left)\right)$.

Define $f_{EXP\left(O\right)}:\mathrm{supp}{\mu }_{Samp\left(O\right)}\to [0,1]$ by

$$f_{EXP\left(O\right)}(k,S,F,x):=\beta \left(e{v}_O^{2^k}\right(F,x\left)\right)$$

Theorem 1

Fix error spaces ${\Delta }^1$, ${\Delta }^2$ of ranks 1 and 2 respectively. Assume that for any $\delta \in {\Delta }^1$ the function ${\delta }^{\prime }(k,j):=\delta \left(k\right)$ is in ${\Delta }^2$. Consider $(f,\mu )$ a distributional estimation problem. Suppose $q:N\to N$ is a polynomial, $F:\{0,1{\}}^{\ast }\stackrel{O}{\to }[0,1]$ and $\hat{S}=(S,r_S)$ is a $({\Delta }^1{)}^O$-sampler for $\mu$ s.t.

(i) $$E_{{\mu }^k}\left[\right(F\left(x\right)-f\left(x\right){)}^2]\in {\Delta }^1$$

(ii) $$\forall k\in N:T_F\left(\mathrm{supp}{\mu }^k\right)\le 2^{q\left(k\right)}$$

(iii) $$\forall k\in N:|F|\le q\left(k\right)$$

(iv) $$\forall k\in N:T_S\left(\{0,1{\}}^{r_S\left(k\right)}\right)\le q\left(k\right)$$

(v) $$\forall k\in N:|S|\le q\left(k\right)$$

It is possible to choose a polynomial $p:N\to N$ and $\tilde{S}$ a $(poly,0{)}^O$-scheme of signature $1\to \{0,1{\}}^{\ast }$ s.t.

(i) $$\forall k\in N:p\left(k\right)\ge q\left(k\right)$$

(i) $$\forall k\in N,y\in \{0,1{\}}^{p\left(k\right)}:{\tilde{S}}^{p\left(k\right)}\left(y\right)=S^k\left(y_{<r_S\left(k\right)}\right)$$

(ii) $$\forall k\in N:T_{\tilde{S}}\left(\{0,1{\}}^{p\left(k\right)}\right)\le p\left(k\right)$$

Denote ${\hat{\zeta }}_{\tilde{S},F,p}=({\zeta }_{\tilde{S},F,p},r_{\tilde{S},F,p})$ to the $\{0,1{\}}^{\ast }$-valued $(poly,0)$-scheme defined by

$$r_{\tilde{S},F,p}\left(k\right)=2p\left(k\right)-|\tilde{S}|-|F|$$

$$\forall k\in N,x\in \{0,1{\}}^{\ast },y_1\in \{0,1{\}}^{p\left(k\right)-|\tilde{S}|},y_2\in \{0,1{\}}^{p\left(k\right)-|F|}:{\zeta }_{\tilde{S},F,p}^k(x,y_1{y}_2)=\left(p\right(k),\tilde{S}{y}_1,F{y}_2,x)$$

Then, ${\hat{\zeta }}_{\tilde{S},F,p}$ is a ${\Delta }^2$-pseudo-invertible reduction of $(f,\mu )$ to $(f_{EXP\left(O\right)},{\mu }_{Samp\left(O\right)})$.

---

The proofs of this and subsequent results are in Appendix B.

In particular, if $(f_{EXP\left(O\right)},{\mu }_{Samp\left(O\right)})$ has a uniform ${\Delta }^2(poly,log{)}^O$-optimal predictor scheme then we can construct a ${\Delta }^2(poly,log{)}^O$-optimal predictor scheme for any ${\Delta }^1$-samplable distributional estimation problem which has an exponential time approximation with error in ${\Delta }^1$. We don’t expect this to be true for reasonable error spaces and $O=\varnothing$, but as the following construction (drawing heavily from Heller) shows it is true for some oracles.

Construction 2

Consider $O\subseteq \{0,1{\}}^{\ast }$, $p:N\to N$ a polynomial and $\sigma :N\times \{0,1{\}}^{\ast }\stackrel{O}{\to }\{0,1{\}}^{\ast }$. We give a recursive definition of $O_{p,k}^{\sigma }\subseteq \{0,1{\}}^{\ast }$ for $k\in N$.

Recursion base:

$$O_{p,0}^{\sigma }:=\{0x\mid x\in O\}$$

Denote

$$O_{p,k}^{\sigma ,+}:=\{1w\alpha \mid |\alpha |=k\wedge \exists S,F,y\in \{0,1{\}}^k,z\in \{0,1{\}}^{p\left(k\right)}:{\sigma }^k(w)=zSFy\wedge f_{EXP\left(O_{p,k}^{\sigma }\right)}^k(S,F,e{v}_{O_{p,k}^{\sigma }}^k(S,k,y))\ge \beta (\alpha \left)\right\}$$

$$O_{p,k}^{\sigma ,-}:=(\{0,1{\}}^{\ast }\setminus O_{p,k}^{\sigma })\cap \left(Q_{f_{EXP\left(O_{p,k}^{\sigma }\right)}}\right(\mathrm{supp}{\mu }_{Samp\left(O_{p,k}^{\sigma }\right)}^k)\cup Q_{e{v}_{O_{p,k}^{\sigma }}}(\{0,1{\}}^k\times \left\{k\right\}\times \{0,1{\}}^k\left)\right)$$

Recursion step:

$$O_{p,k+1}^{\sigma }:=O_{p,k}^{\sigma }\cup O_{p,k}^{\sigma ,+}\setminus \bigcup _{i\le k}{O}_{p,i}^{\sigma ,-}$$

Finally, we define

$$O_p^{\sigma }:=\bigcup _{k\in N}{O}_{p,k}^{\sigma }$$

Construction 3

Define ${\Delta }_{pow}^1$ to be the set of functions $\delta :N\to R^{\ge 0}$ s.t.

$$\exists ϵ>0:\underset{k\to \infty }{lim}{k}^{ϵ}\delta \left(k\right)=0$$

It is easy to see ${\Delta }_{pow}^1$ is an error space.

Theorem 2

Consider $O\subseteq \{0,1{\}}^{\ast }$ and $\sigma :N\times \{0,1{\}}^{\ast }\stackrel{O}{\to }\{0,1{\}}^{\ast }$ s.t.${\sigma }^k$ is a bijection on $\{0,1{\}}^{3k+p\left(k\right)}$. Then, for any sufficiently large polynomial $p:N\to N$, $(f_{EXP\left(O_p^{\sigma }\right)},{\mu }_{Samp\left(O_p^{\sigma }\right)})$ is $({\Delta }_{pow}^1{)}^{O_p^{\sigma }}$-generatable.

Note 1

For $\sigma$ the identity function, $(f_{EXP\left(O_p^{\sigma }\right)},{\mu }_{Samp\left(O_p^{\sigma }\right)})$ admits a Monte Carlo algorithm. This is too strong for our purposes since it means there is no logical uncertainty in exponential time problems. Such oracles can be regarded as bounded analogues of reflective oracles.

Note 2

It is easy to see that $O_p^{\sigma }\in EX{P}^O$.

---

Theorem 2 is insufficient by itself to enable reflection with optimal predictor schemes relative to $O_p^{\sigma }$ since $\Lambda$ is a random algorithm. Potentially this can be solved by derandomization but at present we don’t know whether under what conditions derandomization with respect to $O_p^{\sigma }$ is possible.

Appendix A

Fix $\Delta$ an error space of rank 2.

Definition A

Consider $(f,\mu )$, $(g,\nu )$ distributional estimation problems, $\hat{\zeta }=(\zeta ,r_{\zeta },a_{\zeta })$ a $\{0,1{\}}^{\ast }$-valued $(poly,log)$-bischeme.$\hat{\zeta }$ is called a $\Delta$-pseudo-invertible reduction of $(f,\mu )$ to $(g,\nu )$ when there is a polynomial $p:N\to N$ s.t. the following conditions hold:

(i) $$E_{{\mu }^k\times U^{r_{\zeta }(k,j)}}\left[\right(g\left({\hat{\zeta }}^{kj}\right(x\left)\right)-f\left(x\right){)}^2]\in \Delta$$

(ii) $$P{r}_{{\mu }^k\times U^{r_{\zeta }(k,j)}}\left[{\nu }^{p\left(k\right)}\right({\hat{\zeta }}^{kj}\left(x\right))=0]\in \Delta$$

(iii) There is $M>0$ and $\hat{R}=(R,r_R,a_R)$ a $Q\cap [0,M]$-valued $(poly,log)$-bischeme s.t.

$$E_{{\nu }^{p\left(k\right)}\times U^{r_R(k,j)}}\left[\right({\hat{R}}^{kj}\left(y\right)-\frac{P{r}_{{\mu }^k\times U^{r_{\zeta }(k,j)}}\left[{\hat{\zeta }}^{kj}\right(x)=y]}{{\nu }^{p\left(k\right)}\left(y\right)}{)}^2]\in \Delta$$

(iv) There is a $\{0,1{\}}^{\ast }$-valued $(poly,log)$-scheme $\hat{\xi }=(\xi ,r_{\xi },a_{\xi })$ s.t.

$$E_{{\mu }^k\times U^{r_{\zeta }(k,j)}}\left[\sum _{x^{\prime }\in \{0,1{\}}^{\ast }}|P{r}_{U^{r_{\xi }(k,j)}}\right[{\hat{\xi }}^{kj}\left({\hat{\zeta }}^{kj}\right(x,z),w)=x^{\prime }]-P{r}_{{\mu }^k\times U^{r_{\zeta }(k,j)}}[x^{\prime \prime }=x^{\prime }\mid {\hat{\zeta }}^{kj}(x^{\prime \prime },z^{\prime })={\hat{\zeta }}^{kj}(x,z)\left]|\right]\in \Delta$$

Such $\hat{\xi }$ is called a $\Delta$-pseudo-inverse of $\hat{\zeta }$.

$\hat{\zeta }=(\zeta ,r_{\zeta },a_{\zeta })$ a $\{0,1{\}}^{\ast }$-valued $(poly,log)$-scheme is called a $\Delta$-pseudo-invertible reduction of $(f,\mu )$ to $(g,\nu )$ when it becomes such when adding trivial dependence on $j$.

Theorem A

Suppose there is a polynomial $h:N^2\to N$ s.t. $h^{-1}\in \Delta$. Consider $(f,\mu )$, $(g,\nu )$ distributional estimation problems, $\hat{\zeta }$ a $\Delta$-pseudo-invertible reduction of $(f,\mu )$ to $(g,\nu )$ and ${\hat{P}}_g$ a $\Delta (poly,log)$-optimal predictor scheme for $(g,\nu )$. Define ${\hat{P}}_f$ by ${\hat{P}}_f^{kj}\left(x\right):={\hat{P}}_g^{kj}\left({\hat{\zeta }}^{kj}\right(x\left)\right)$. Then, ${\hat{P}}_f$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$.

---

Theorem A.1 is proved exactly the same way as Theorem 8 for unidistributional problems and we leave out the details.

Appendix B

Proof of Theorem 1

We need to show the 4 defining conditions of ${\Delta }^2$-pseudo-invertible reductions.

(i) $$E_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[\right(f_{EXP\left(O\right)}\left({\hat{\zeta }}_{\tilde{S},F,p}^k\right(x\left)\right)-f\left(x\right){)}^2]=E_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}[\left(f_{EXP\left(O\right)}^{p\left(k\right)}\right(\tilde{S}{y}_1,F{y}_2,x)-f(x\left){)}^2\right]$$

$$E_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[\right(f_{EXP\left(O\right)}\left({\hat{\zeta }}_{\tilde{S},F,p}^k\right(x\left)\right)-f\left(x\right){)}^2]=E_{{\mu }^k}[\left(\beta \right(e{v}_O^{2^{p\left(k\right)}}(F,x))-f(x\left){)}^2\right]$$

$$E_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[\right(f_{EXP\left(O\right)}\left({\hat{\zeta }}_{\tilde{S},F,p}^k\right(x\left)\right)-f\left(x\right){)}^2]=E_{{\mu }^k}[\left(F\right(x)-f(x\left){)}^2\right]$$

Using assumption (i), we get the required result.

(ii) $$P{r}_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[{\mu }_{Samp\left(O\right)}^{p\left(k\right)}\right({\hat{\zeta }}_{\tilde{S},F,p}^k\left(x\right))=0]=P{r}_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[{\mu }_{Samp\left(O\right)}^{p\left(k\right)}\right(p\left(k\right),\tilde{S}{y}_1,F{y}_2,x)=0]$$

$$P{r}_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[{\mu }_{Samp\left(O\right)}^{p\left(k\right)}\right({\hat{\zeta }}_{\tilde{S},F,p}^k\left(x\right))=0]=P{r}_{{\mu }^k}[x\notin S^k(\{0,1{\}}^{r_S\left(k\right)}\left)\right]$$

$$P{r}_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[{\mu }_{Samp\left(O\right)}^{p\left(k\right)}\right({\hat{\zeta }}_{\tilde{S},F,p}^k\left(x\right))=0]=\sum _{x\in \{0,1{\}}^{\ast }\setminus S^k\left(\{0,1{\}}^{r_S\left(k\right)}\right)}{\mu }^k\left(x\right)$$

$$P{r}_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[{\mu }_{Samp\left(O\right)}^{p\left(k\right)}\right({\hat{\zeta }}_{\tilde{S},F,p}^k\left(x\right))=0]=\sum _{x\in \{0,1{\}}^{\ast }\setminus S^k\left(\{0,1{\}}^{r_S\left(k\right)}\right)}|{\mu }^k\left(x\right)-P{r}_{\{0,1{\}}^{r_S\left(k\right)}}\left[S^k\right(y)=x]|$$

$$P{r}_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[{\mu }_{Samp\left(O\right)}^{p\left(k\right)}\right({\hat{\zeta }}_{\tilde{S},F,p}^k\left(x\right))=0]\le \sum _{x\in \{0,1{\}}^{\ast }}|{\mu }^k\left(x\right)-P{r}_{\{0,1{\}}^{r_S\left(k\right)}}\left[S^k\right(y)=x]|$$

Since $S$ is a $({\Delta }^1{)}^O$-sampler for $\mu$, we get

$$P{r}_{{\mu }^k\times U^{r_{\tilde{S},F,p}\left(k\right)}}\left[{\mu }_{Samp\left(O\right)}^{p\left(k\right)}\right({\hat{\zeta }}_{\tilde{S},F,p}^k\left(x\right))=0]\in {\Delta }^1$$

(iii) Define $\hat{R}$ by

$${\hat{R}}^{kj}(i,S^{\prime },F^{\prime },x)=\{\begin{array}{c}0\text{if}i\ne p\left(k\right)\\ 0\text{if}\tilde{S}\text{is not a prefix of}{S}^{\prime }\\ 2^{|\tilde{S}|+|F|}\text{in other cases}\end{array}$$

Consider $k\in N$, $x^{\prime }\in \{0,1{\}}^{\ast }$, $y_1\in \{0,1{\}}^{p\left(k\right)-|\tilde{S}|}$, $y_2\in \{0,1{\}}^{p\left(k\right)-|F|}$.

$$\frac{P{r}_{{\mu }^k\times U^{r_{\zeta }(k,j)}}\left[{\hat{\zeta }}_{\tilde{S},F,p}^k\right(x)=(p\left(k\right),\tilde{S}{y}_1,F{y}_2,x^{\prime }\left)\right]}{{\mu }_{Samp\left(O\right)}^{p\left(k\right)}\left(p\right(k),\tilde{S}{y}_1,F{y}_2,x^{\prime })}=\frac{2^{-p\left(k\right)+|\tilde{S}|}{2}^{-p\left(k\right)+|F|}P{r}_{U^{r_S\left(k\right)}}\left[S^k\right(y)=x]}{2^{-p\left(k\right)}{2}^{-p\left(k\right)}P{r}_{U^{r_S\left(k\right)}}\left[S^k\right(y)=x]}=2^{|\tilde{S}|+|F|}$$

(iv) Define $\hat{\xi }$ by

$${\hat{\xi }}^{kj}(i,S^{\prime },F^{\prime },x)=x$$

Proposition B

Consider $O\subseteq \{0,1{\}}^{\ast }$, $p:N\to N$ a polynomial and $\sigma :N\times \{0,1{\}}^{\ast }\stackrel{O}{\to }\{0,1{\}}^{\ast }$. Then

(i) $$\forall k\in N,i>k,x\in \{0,1{\}}^{\ast }:x\in O_{p,k}^{\sigma }⟹x\in O_{p,i}^{\sigma }\wedge x\in O_p^{\sigma }$$

(ii) $$\forall x\in \{0,1{\}}^{\ast }:0x\in O_p^{\sigma }⟺x\in O$$

(iii) $$\forall k\in N,\forall x\in \{0,1{\}}^{4k+p\left(k\right)}:1x\in O_p^{\sigma }⟺1x\in O_{p,k}^{\sigma ,+}\setminus \bigcup _{i\le k}{O}_{p,i}^{\sigma ,-}$$

(iv) $$\forall k\in N,S\in \{0,1{\}}^k,y\in \{0,1{\}}^k:e{v}_{O_p^{\sigma }}^k(S,y)=e{v}_{O_{p,k}^{\sigma }}^k(S,y)$$

(v) $$\forall k\in N,F\in \{0,1{\}}^k,x\in \mathrm{supp}{\mu }_{Samp\left(O_p^{\sigma }\right)}^k:e{v}_{O_p^{\sigma }}^{2^k}(F,x)=e{v}_{O_{p,k}^{\sigma }}^{2^k}(F,x)$$

Proof of Proposition B

(i) By induction: $x\in O_{p,k+1}^{\sigma ,-}$ implies $x\notin O_{p,k}^{\sigma }$.

(ii) If $0x\notin O$ then $0x\notin O_p^{\sigma }$ since all words in $O_{p,k}^{\sigma ,+}$ begin with $1$. If $0x\in O$ then $0x\in O_p^{\sigma }$ by (i).

(iii) If $1x\in O_{p,k}^{\sigma ,+}\setminus {\bigcup }_{i\le k}{O}_{p,i}^{\sigma ,-}$ then $1x\in O_{p,k+1}^{\sigma }$ and by (i) $1x\in O_p^{\sigma }$. If $1x\in O_p^{\sigma }$ then there is $n\in N$ s.t.$1x\in O_{p,n}^{\sigma ,+}\setminus {\bigcup }_{i\le n}{O}_{p,i}^{\sigma ,-}$ and $n=k$ because any word in $O_{p,n}^{\sigma ,+}$ has length $4n+p\left(n\right)+1$.

(iv) All oracle queries made in $e{v}_{O_{p,k}^{\sigma }}^k(S,y)$ return the same values when addressed to $O_{p,i}^{\sigma }$ for $i>k$: queries that return $0$ keep returning $0$ since they are included in $O_{p,k}^{\sigma ,-}$ and queries that return $1$ keep returning $1$ by (i).

(v) Note that (iv) implies $\mathrm{supp}{\mu }_{Samp\left(O_p^{\sigma }\right)}^k=\mathrm{supp}{\mu }_{Samp\left(O_{p,k}^{\sigma }\right)}^k$ and apply the same argument as in (iv) to $e{v}_{O_{p,i}^{\sigma }}^{2^k}(F,x)$.

Proof of Theorem 2

We describe $\hat{G}$ the $({\Delta }_{pow}^1{)}^{O_p^{\sigma }}$-generator for $(f_{EXP\left(O_p^{\sigma }\right)},{\mu }_{Samp\left(O_p^{\sigma }\right)})$. $\hat{G}=(G,3k+p(k\left)\right)$ is the $(poly,0{)}^{O_p^{\sigma }}$-scheme of signature $1\to \{0,1{\}}^{\ast }\times [0,1]$ defined as follows. Consider the computation of $G^k\left(w\right)$.

$zSFy:={\sigma }^k\left(w\right)$ is computed, where $|S|=|F|=|y|=k$. $x:=e{v}_{O_p^{\sigma }}^k(S,k,y)$ is computed. For each $i\in \{0,1\dots k\}$, we compute ${\alpha }_i$ defined as $\frac{i}{k}$ rounded to $k$ binary digits.$\alpha :=\frac{1}{k+1}|\{i\in \{0,1\dots k\}\mid 1w{\alpha }_i\in O_p^{\sigma }\}|$ is computed within $k$ binary digits. The output is $\left(\right(k,S,F,x),\alpha )$.

${\hat{G}}_1$ reproduces ${\mu }_{Samp\left(O_p^{\sigma }\right)}$ precisely since ${\sigma }^k$ preserves $U^{3k+p\left(k\right)}$.

It is easy to see that there is a polynomial $q$ s.t. for any $p$ we have $|{\bigcup }_{i\le k}{O}_{p,i}^{\sigma ,-}|\le 2^{q\left(k\right)}$. Take any polynomial $p$ s.t. ${lim}_{k\to \infty }(3k+p(k)-q(k\left)\right)=+\infty$. By Lemma C, (iii) we have

$$\alpha =\frac{1}{k+1}\left(|\right\{i\in \{0,1\dots k\}\mid 1w{\alpha }_i\in O_{p,k}^{\sigma ,+}\}|-|\{i\in \{0,1\dots k\}\mid 1w{\alpha }_i\in O_{p,k}^{\sigma ,+}\cap \bigcup _{n\le k}{O}_{p,n}^{\sigma ,-}\left\}|\right)$$

The first term approximates $e{v}_{O_{p,k}^{\sigma }}^{2^k}(F,x)$ within error $\frac{1}{k+1}\in {\Delta }_{pow}^1$ by the construction of $O_{p,k}^{\sigma ,+}$. By Lemma C, (v) it approximates $f_{EXP\left(O_p^{\sigma }\right)}(k,S,F,x)=e{v}_{O_p^{\sigma }}^{2^k}(F,x)$ within the same error. The second terms vanishes for all but a negligible fraction of the $w$-s by the properties of $p$ and $q$.