Changeset - d3ea27296b0f
[Not reviewed]
0 1 0
András Gilyén - 8 years ago 2017-09-06 06:11:37
gilyen@cwi.nl
cycle lemma
1 file changed with 58 insertions and 0 deletions:
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -826,6 +826,64 @@ Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is
 
    	\item Can we prove the conjectured formula for $a_k^{(3)}$?		
 
    \end{itemize} 
 
    
 
	\begin{lemma}On the infinite chain
 
		$$\P_I(Z^{0}\cap Z^{k})=\P_I(Z^{0})\P_I(Z^{k})+\mathcal{O}(p^{k-|b|+1})$$
 
	\end{lemma}   
 
    Note that using De Morgan's law and the inclusion-exclusion formula we can see that this is equivalent to saying:
 
    $$\P_I(NZ^{0}\cap NZ^{k})=\P_I(NZ^{0})\P_I(NZ^{k})+\mathcal{O}(p^{k-|b|+1})$$
 
    \begin{proof}
 
    We proceed by induction on $|I|$. For $|I|=0,1$ the statement is trivial.
 
    
 
    Now observe that:
 
    $$\P_I(Z^{0})=\sum_{P\text{ patch}\,:\,0\in P}\P_I(P\in\mathcal{P})$$
 
    $$\P_I(Z^{k})=\sum_{P\text{ patch}\,:\,k\in P}\P_I(P\in\mathcal{P})$$
 
    
 
    Suppose $|I|\geq 2$, then we proceed using induction similarly to the above
 
    \begin{align*}
 
    &\P_I(Z^{0}\cap Z^{k})\\
 
    &=\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}
 
    \P_I(P_l,P_r\in\mathcal{P})
 
    +\sum_{P\text{ patch}\,:\,0,k\in P}\P_I(P\in\mathcal{P})\\
 
    &=\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}
 
    \P_I(P_l,P_r\in\mathcal{P})
 
    +\mathcal{O}(p^{k+1})\\
 
    &\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}
 
    \P_{I\cap P_l}(P_l\in\mathcal{P})
 
    \P_{> I <}(NZ^{P_l^{\max}+1}\cap NZ^{P_r^{\min}-1})
 
    \P_{I\cap P_r}(P_r\in\mathcal{P})
 
    +\mathcal{O}(p^{k+1})\\
 
    &\overset{\text{induction}}{=}\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}
 
    \P_{I\cap P_l}(P_l\in\mathcal{P})
 
    \P_{> I <}(NZ^{P_l^{\max}+1})\P_{> I <}(NZ^{P_r^{\min}-1})
 
    \P_{I\cap P_r}(P_r\in\mathcal{P})
 
    +\mathcal{O}(p^{k-|I|+1})\\
 
    &\overset{Lemma~\ref{lemma:probIndep}}{=}\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}
 
    \P_{I\cap P_l}(P_l\in\mathcal{P})
 
    \P_{I\setminus P_l}(NZ^{P_l^{\max}+1})\P_{I\setminus P_r}(NZ^{P_r^{\min}-1})
 
    \P_{I\cap P_r}(P_r\in\mathcal{P})
 
    +\mathcal{O}(p^{k-|I|+1})\\
 
    &\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}
 
    \P_{I}(P_l\in\mathcal{P})
 
    \P_{I}(P_r\in\mathcal{P})
 
    +\mathcal{O}(p^{k-|I|+1})\\
 
    &=\left(\sum_{P_l\text{ patch}\,:\,0\in P_l}
 
    \P_{I}(P_l\in\mathcal{P})\right)\left(\sum_{P_l\text{ patch}\,:\,0\in P_l}
 
    \P_{I}(P_l\in\mathcal{P})\right)
 
    +\mathcal{O}(p^{k-|I|+1})\\
 
    &=\P_I(Z^{0})\P_I(Z^{k})
 
    +\mathcal{O}(p^{k-|I|+1}).	
 
    \end{align*}
 
    \end{proof}
 

	
 
	Final observation: Suppose $S={a,b}$ 
 
	    \begin{align*}
 
	    &\sum_{f_{\overline{P}}\in\{0,1'\}^{2}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\min}-1)}\cap NZ^{(P_{\max}+1)})  \\
 
	    &= \sum_{f_{\overline{P}}\in\{0,1'\}^{2}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\min}-1)}) \mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\max}+1)})   +\mathcal{O}(p^{|\overline{P}|-|S|})\\
 
 	    &= \sum_{f_{\overline{P}}\in\{0,1'\}^{2}}  \rho_{a_f}\mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\min}-1)})  \rho_{b_f}\mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\max}+1)})   +\mathcal{O}(p^{|\overline{P}|-|S|})\\
 
	    \end{align*}
 

	
 

	
 
    
 
\begin{comment}
 
    \subsection{Sketch of the (false) proof of the linear bound \ref{it:const}}
 
    Let us interpret $[n]$ as the vertices of a length-$n$ cycle, and interpret operations on vertices mod $n$ s.t. $n+1\equiv 1$ and $1-1\equiv n$.
0 comments (0 inline, 0 general)