Changeset - 0d0911198b0d
[Not reviewed]
0 1 0
Tom Bannink - 8 years ago 2017-07-07 17:29:12
tom.bannink@cwi.nl
Update circle proof
1 file changed with 38 insertions and 13 deletions:
main.tex
38
13
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -618,16 +618,15 @@ Here, I (Tom) tried to set do the same Lemma but for the circle instead of the i
 
    Without loss of generality, we can assume that $0=j < i_* < s < n$. 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$.
 
    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$.\\
 
    Claim:
 
    \begin{align*}
 
        \P_{I}(\mathrm{ZP}^{[-l,r]_0}) &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})
 
        + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|})
 
        + \mathcal{O}(p^{d(i_*,0)+1-|I|})
 
    \end{align*}
 
    \todo{These special cases.}
 
    If $r\geq i_*$ or $l\geq n-i_*$ then $\P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$.
 
    If $-l\in I$ or $r\in I$ then the left hand side is zero so the claim holds.
 
    If $[-l,r]_0$ has no overlap with $I$ then both sides of the above expression are zero so it also holds. We are left with the case where, $-l,r,\notin I$ and $[-l,r]_0 \cap I \neq \emptyset$ and $i_*\notin[-l,r]_0$.
 
    If $r\geq i_*$ or $l\geq n-i_*$ then $\P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$ and also $\P_{I'}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$ so then the claim holds.
 
    If $-l\in I$ or $r\in I$ (and $-l,r$ are both not $i_*$ because of the previous point) then the probability of $\mathrm{ZP}^{[-l,r]_0}$ is zero for both $I$ and $I'$ so the claim holds.
 
    If $[-l,r]_0$ has no overlap with $I$ then both sides are also zero so it also holds. We are left with the case where: $-l,r,\notin I$ and $[-l,r]_0 \cap I \neq \emptyset$ and $i_*\notin[-l,r]_0$.
 
    The following diagram illustrates the situation
 
    \begin{center}
 
        \includegraphics{diagram_circle_lemma.pdf}
 
@@ -664,9 +663,12 @@ Here, I (Tom) tried to set do the same Lemma but for the circle instead of the i
 
        &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})
 
        + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|})
 
    \end{align*}
 
    Case separation shows that $\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right) \geq d(i_*,0) + 1$ \todo{prove.}
 
    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.
 

	
 
    Now we can prove the required equalities:
 
    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*}
 
        \P_{I}(\Z{0})
 
        &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}
 
@@ -674,7 +676,8 @@ Here, I (Tom) tried to set do the same Lemma but for the circle instead of the i
 
        \tag{the events are a partition of $\Z{0}$}\\
 
        &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}
 
        \P_{I'}(\mathrm{ZP}^{[-l,r]_0})
 
        + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|}) \\
 
        + \mathcal{O}(p^{d(i_*,0)+1-|I|})
 
        \tag{by claim} \\
 
        &= \P_{I'}(\Z{0}) + \mathcal{O}(p^{d(i_*,0)+1-|I|})
 
    \end{align*}
 
    Similarly, we have
 
@@ -683,13 +686,35 @@ Here, I (Tom) tried to set do the same Lemma but for the circle instead of the i
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
 
        \P_{I}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})
 
        \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|}) \\
 
        &=\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|})
 
        \tag{Claim~\ref{claim:eventindependence}}\\
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
 
        \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|})
 
        \tag{$i_*\in I \setminus[s,r]_0$}\\
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
 
        \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|})
 
        \tag{same argument as before}\\
 
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
 
        \P_{I'}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})
 
        + \mathcal{O}(p^{something}) \\
 
        \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?}}\\
 
        &= \P_{I'}(\Z{0} , \NZ{s})
 
        + \sum_{l=1}^{n-s}\sum_{r=1}^{s} + \mathcal{O}(p^{something})
 
        +\mathcal{O}(p^{\dist{s}(i_*,0)+1-|I|})
 
    \end{align*}
 
    \todo{finish details}
 
    This finishes the proof.
 
\end{proof}
 

	
 
\begin{definition}[Connected patches]
0 comments (0 inline, 0 general)