Vadim Kosoy edited The_following_theorem_is_the__.tex  about 8 years ago

Commit id: f04022e4feaaff3cd6a84673ffe1047b65a8e75f

deletions | additions      

       

\begin{proof}  Fix $S: \Words \xrightarrow{\Gamma} \Rats$ with $\R_S \geq \R_P$. Consider $t := \sigma 2^{-a}$ where $\sigma \in any $\sigma: \Nats^2 \rightarrow  \{ \pm 1 \}$ and $a \in $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}$. Define $Q: Then, 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) - (P^{kj}(x,y) + t t(k,j)  S^{kj}(x,yz))} \leq 2^{-h(k,j)}$. $$ 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|}) $$