Changeset - ffbfb3763633
[Not reviewed]
0 1 0
Tom Bannink - 8 years ago 2017-07-11 14:31:19
tom.bannink@cwi.nl
Finish proof of circle lemma
1 file changed with 24 insertions and 20 deletions:
main.tex
24
20
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -601,21 +601,25 @@ Here, I (Tom) tried to set do the same Lemma but for the circle instead of the i
 
    Then
 
    \begin{align*}
 
        \P_{I}(\Z{j})        &= \P_{I'}(\Z{j})        + \mathcal{O}(p^{d(i_*,j) + 1 - |I|}) \\
 
        \P_{I}(\Z{j},\NZ{s}) &= \P_{I'}(\Z{j},\NZ{s}) + \mathcal{O}(p^{\dist{s}(i_*,j) + 1 - |I|}) .
 
        \P_{I}(\Z{j},\NZ{s}) &= \P_{I'}(\Z{j},\NZ{s}) + \mathcal{O}(p^{\min\left( \dist{s}(i_*,j), \dist{j}(i_*,s) \right) + 1 - |I|}) .
 
    \end{align*}
 
\end{lemma}
 
\begin{proof}
 
    We will prove both statements inductively on $|I|$. For $|I|=1$ we have $I=\{i_*\}$ and $I'=\emptyset$, so $\P_{I'}(\Z{j})=0$ and
 
    Without loss of generality, we can assume that $j=0$ and  $0 < i_* < s < n$ (because we can shift $j$ to $0$ and switch the direction to get the correct ordering). Therefore, we have to prove:
 
    \begin{align*}
 
        \P_{I}(\Z{j})       &= \mathcal{O}(p^{d(i_*,j)}) \\
 
        \P_{I}(\Z{j},\NZ{s}) &= \mathcal{O}(p^{\dist{s}(i_*,j)})
 
        \P_{I}(\Z{0})        &= \P_{I'}(\Z{0})        + \mathcal{O}(p^{d(i_*,0) + 1 - |I|}) \\
 
        \P_{I}(\Z{0},\NZ{s}) &= \P_{I'}(\Z{0},\NZ{s}) + \mathcal{O}(p^{\min\left( i_*, s-i_* \right) + 1 - |I|}) .
 
    \end{align*}
 
    simply because a chain of zeroes has to be formed between $i_*$ and $j$, and in the second case this chain can not go through $s$. Now assume both statements hold up to $|I|-1$, then we prove them both for sets of size $|I|$.
 
    We will prove both statements inductively on $|I|$. For $|I|=1$ we have $I=\{i_*\}$ and $I'=\emptyset$, so $\P_{I'}(\Z{0})=0$ and
 
    \begin{align*}
 
        \P_{I}(\Z{0})        &= \mathcal{O}(p^{d(i_*,0)}) \\
 
        \P_{I}(\Z{0},\NZ{s}) &= \mathcal{O}(p^{i_*}) = \mathcal{O}(p^{\min\left( i_*, s-i_* \right)})
 
    \end{align*}
 
    simply because a chain of zeroes has to be formed between $i_*$ and $0$, and in the second case this chain can not go through $s$ so the shortest path has length $i_*$. Now assume both statements hold up to $|I|-1$, then we prove them both for sets of size $|I|$.
 

	
 
    When we refer to an interval $[a,b]$ on the circle we could be referring to two possible intervals because of the periodicity of the circle. Define $[a,b]_j$ as the interval with vertex $j$ on the \emph{inside}. Furthermore by $-a$ we mean the vertex $n-a$, as one would expect modulo $n$.
 
    %If we refer to only $[a,b]$ then we mean $\{a,a+1,...,b\}$ where numbers are considered modulo $n$. So $[a,b]$ and $[b,a]$ are different intervals that cover the circle together.
 

	
 
    Without loss of generality, we can assume that $0=j < i_* < s < n$. We will now consider intervals around vertex 0.
 
 We will now consider intervals around vertex 0.
 
    For $l,r\geq 1$ and $l+r\leq n$, define the event ``zeroes patch'' $\mathrm{ZP}^{[-l,r]_0}$ as the event of getting zeroes inside the interval $[-l,r]_0$ but not on the boundary, i.e.
 
    $$\mathrm{ZP}^{[-l,r]_0} = \NZ{-l} \cap \Z{-l+1} \cap \cdots \cap \Z{0} \cap \cdots \cap \Z{r-1} \cap \NZ{r}$$
 
    Note that there are $r+l-1$ `zeroes' in this event, so $\P_{J}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{r+l-1-|J|})$ for $J\subseteq[-l,r]_0$ is a lower bound on the order of $p$.\\
 
@@ -633,7 +637,7 @@ Here, I (Tom) tried to set do the same Lemma but for the circle instead of the i
 
    \end{center}
 
    Note that by Claim~\ref{claim:eventindependence} we have
 
    \begin{align*}
 
        \P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \P_{I \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) \;\cdot\; \P_{I\setminus [-l,r]_0}(\NZ{a},\NZ{b})
 
        \P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \P_{I \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) \;\cdot\; \P_{I\setminus [-l,r]_0}(\NZ{-l},\NZ{r})
 
    \end{align*}
 
    We have $i_*\in I \setminus[-l,r]_0$, and $I\cap[-l,r]_0 = I' \cap [-l,r]_0$. Define $J=I\setminus[-l,r]_0$ and $J'=I'\setminus[-l,r]_0$. We have $|J|<|I|$ so we can apply the induction hypothesis to $J$:
 
    \begin{align*}
 
@@ -647,7 +651,7 @@ Here, I (Tom) tried to set do the same Lemma but for the circle instead of the i
 
        1
 
        - \P_{J'}(\Z{-l},\NZ{r})
 
        - \P_{J'}(\Z{r}) \\
 
        &\quad + \mathcal{O}(p^{\dist{r}(i_*,-l)+1-|J|})
 
        &\quad + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l), \dist{-l}(i_*,r) \right) +1-|J|})
 
        + \mathcal{O}(p^{d(i_*,r)+1-|J|}) \\
 
        &=
 
        \P_{J'}(\NZ{-l},\NZ{b})
 
@@ -666,7 +670,7 @@ Here, I (Tom) tried to set do the same Lemma but for the circle instead of the i
 
    Where we used Claim~\ref{claim:eventindependence} again.
 
    Case separation shows that
 
    $$\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right) + l +r \geq d(i_*,0) + 1$$
 
    which proves the claim.
 
    for $l,r\geq 1$ which proves the claim.
 

	
 
    The first equality that we have to prove now follows from the fact that the ``zeroes patch'' events are a partition of $\Z{0}$:
 
    \begin{align*}
 
@@ -688,31 +692,31 @@ Here, I (Tom) tried to set do the same Lemma but for the circle instead of the i
 
        \tag{partition of $\Z{0}$}\\
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
 
        \P_{I}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})
 
        +\mathcal{O}(p^{\dist{s}(i_*,0)+1-|I|}) \\
 
        +\mathcal{O}(p^{i_*+1-|I|}) \\
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
 
        \P_{I\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot
 
        \P_{I\setminus [s,r]_0}(\NZ{r},\NZ{s})
 
        +\mathcal{O}(p^{\dist{s}(i_*,0)+1-|I|})
 
        +\mathcal{O}(p^{i_*+1-|I|})
 
        \tag{Claim~\ref{claim:eventindependence}}\\
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
 
        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot
 
        \P_{I\setminus [s,r]_0}(\NZ{r},\NZ{s})
 
        +\mathcal{O}(p^{\dist{s}(i_*,0)+1-|I|})
 
        +\mathcal{O}(p^{i_*+1-|I|})
 
        \tag{$i_*\in I \setminus[s,r]_0$}\\
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
 
        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot
 
        \P_{I'\setminus [s,r]_0}(\NZ{r},\NZ{s}) \\
 
        &\qquad +\mathcal{O}(p^{\min\left( \dist{r}(i_*,s) , d(i_*,r)\right)+l+r-|I|})
 
        +\mathcal{O}(p^{\dist{s}(i_*,0)+1-|I|})
 
        +\mathcal{O}(p^{i_*+1-|I|})
 
        \tag{same argument as before}\\
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
 
        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot
 
        \P_{I'\setminus [s,r]_0}(\NZ{r},\NZ{s}) \\
 
        &\qquad
 
        +\mathcal{O}(p^{\dist{s}(i_*,0)+1-|I|})
 
        \tag{case separation \todo{does not seem to work?}}\\
 
        +\mathcal{O}(p^{\min\left( i_* , s-i_* \right) +1-|I|})
 
        \tag{case separation}\\
 
        &= \P_{I'}(\Z{0} , \NZ{s})
 
        +\mathcal{O}(p^{\dist{s}(i_*,0)+1-|I|})
 
        +\mathcal{O}(p^{\min\left( i_* , s-i_* \right) +1-|I|})
 
    \end{align*}
 
    This finishes the proof.
 
\end{proof}
0 comments (0 inline, 0 general)