Vadim Kosoy edited The_following_theorem_is_the__.tex  about 8 years ago

Commit id: 724056b536aab7576c365484646f56d1fed3e757

deletions | additions      

       

\begin{proof}  Fix $S: \Words \xrightarrow{\Gamma} \Rats$ with $\R_S \geq \R_P$. Consider any $\sigma: \Nats^2 \rightarrow \{ \pm 1 \}$ and $n: \Nats^2 \rightarrow \Nats$. Define $t(k,j) := \sigma(k,j) 2^{-n(k,j)}$. Choose $h: \Nats^2 \rightarrow \Nats$ a polynomial s.t. $2^{-h} \in \mathcal{E}$. Then, it is easy to see  there is $Q_t: \Words \xrightarrow{\Gamma} \Rats$ s.t. given $k,j \in \Nats$, $x \in \Supp \mu^k$, $y \in \WordsLen{\R_P(k,j)}$ and $z \in \WordsLen{\R_P(k,j) - \R_S(k,j)}$, $\Abs{Q^{kj}(x,yz) \R_S(k,j)}$  $$\Abs{Q^{kj}(x,yz)  - (P^{kj}(x,y) + t(k,j) S^{kj}(x,yz))} \leq 2^{-h(k,j)}$. 2^{-h(k,j)}$$  Specifically, $Q_t$ is computed by computing $P^{kj}(x,y) + t(k,j) S^{kj}(x,yz)$ within $h(k,j)$ digits after the binary point.  $$ E_{\mu^k \times U^{r(k,j)}}[(P^{kj}-f)^2] \leq E_{\mu^k \times U^{r(k,j)} \times U^s}[(R-f)^2] + \tilde{\delta}(k,j,T_R^\mu(k,r(k,j)+s),2^{|R|}) $$