%% LyX 1.6.10 created this file. For more info, see http://www.lyx.org/. %% Do not edit unless you really know what you are doing. \documentclass[english]{IEEEtran} \usepackage[T1]{fontenc} \usepackage[latin9]{inputenc} \usepackage{amsthm} \usepackage{graphicx} \usepackage{amssymb} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. \theoremstyle{plain} \newtheorem{thm}{Theorem} \theoremstyle{definition} \newtheorem{defn}[thm]{Definition} \theoremstyle{remark} \newtheorem{rem}[thm]{Remark} \theoremstyle{plain} \newtheorem{lem}[thm]{Lemma} \theoremstyle{plain} \newtheorem{cor}[thm]{Corollary} \makeatother \usepackage{babel} \begin{document} \title{A Good Family of Quantum Low-Density Parity-Check Codes} \author{Reina Riemann% \thanks{Reina Riemann. Computer Science and Artificial Intelligence Laboratory. Massachusetts Institute of Technology. Cambridge, MA 02139, USA. e-mail: riemann@mit.edu% } and Peter Shor% \thanks{Peter Shor. Department of Mathematics. Massachusetts Institute of Technology. Cambridge, MA 02139, USA. e-mail: shor@math.mit.edu% }} \maketitle ~ \begin{abstract} We present a good family of quantum low-density parity-check error-correcting codes. This family is derived from regular Platonic surfaces. We present a logarithmic lower bound on their shortest noncontractible cycle and therefore on the distance of the family of codes. We show the asymptotical low-density of their matrices, and show their asymptotical nonzero rate. We simulate their good decoding performance. This family answers a conjecture proposed by MacKay about the existence of families of quantum low-density parity-check (LDPC) codes with nonzero rate, growing minimum distance and a practical decoder. ~ Index Terms---Low-density parity-check codes, message passing decoding, quantum codes. ~ \end{abstract} \section{Introduction} ~ From a theoretical perspective a good family of error-correcting codes corrects errors in proportion to the block length of the codes and has a practical decoder \cite{mackaygoodcodes}. For example classical low-density parity-check codes (LDPC), first introduced by Gallager \cite{gallager}, approach the Gilbert-Varshamov bound and have a practical decoder. LDCP codes have reemerged as one of the most influential coding schemes. Their sparse local parity-check dependencies imply low decoding complexity when using local iterative message-passing decoding algorithms. Classical LDPC and LDPC-like codes decoded with message-passing decoders are used in practice such as in internet and mobile media broadcast, optical networking and other applications. The development of quantum information theory paves the way to the development of quantum computers extending the notion of classical channels and error-correcting codes \cite{QuantumInformationTheory}. The existence of good quantum error-correcting codes was shown non-constructively by Calderbank and Shor \cite{shorgood}. In 2003, MacKay \cite{mackayquantum} introduced some promising individual examples of quantum LDPC codes. MacKay's codes are dual-containing stabilizer codes whose matrix representation is sparse. Several theoretical questions were raised by this work including a conjecture about the existence of good families of sparse-graph quantum error-correcting codes with nonzero rate, growing minimum distance and a practical decoder. We answer this conjecture by presenting one such family here. We present a family of good sparse quantum error-correcting codes with asymptotic logarithmic distance.We show their asymptotical sparsity, non-zero rate, and their decoding performance with belief propagation. These codes are derived from sparse graphs, induced by tessellations of topological surfaces, and are therefore a type of low-density parity-check (LDPC) code. Note that while most known LDPC codes are derived from regular graphs, there are known classical LDPC codes derived from irregular graphs \cite{mackaryirregular}. The low-density parity-check families of quantum codes that we present are generalizations of Kitaev's codes \cite{kitaevquantum} to surfaces of genus $g$ that encode $2g$ qubits, as explained in section III. Kitaev's topological codes are a class of stabilizer codes derived from lattices on surfaces of single genus, or tori, with asymptotical zero rate. In section II we give definitions, background and notation used in this paper. In section III we review stabilizer quantum error-correcting codes, topological quantum error-correcting codes and their generalization to tessellations on 2-manifolds. In section IV we describe the family of Platonic graphs and surfaces. We present a quantum code derived from $\pi_{7}$ and a good family of Platonic quantum low-density parity-check codes. We derive the asymptotical low-density of their matrices and their rate. In section V we provide a logarithmic lower bound on their distance. In section VI we present decoding simulations using belief propagation. In section VII we provide our insights and conclusions. ~ \section{\label{sec:Definitions}Definitions} ~ In this section we introduce the topological graph-theoretical definitions used in the quantum error-correcting codes families of codes that we present in this paper. Let $G=(V,\, E)$ ~be a graph, where $V$ is a set of vertices, and $E$, a set of edges. $\:$ \begin{defn} If a graph $G$ can be drawn on a $2-dimensional$ $manifold$ or surface $M$ without edge crossing, then it is said to be $embedded$ on this manifold. \end{defn} $\,$ The family of quantum error-correcting codes that we present is derived from embeddings of graphs on 2-dimensional surfaces. ~ \begin{defn} An embedding of a graph is a $tessellation$ of a surface. \end{defn} ~ \begin{defn} The $genus$ of a graph $G$ is the smallest genus of a $2-dimensional$ manifold $M$ in which the graph can be embedded. \end{defn} $\,$ The genus of the surfaces on which these graphs are embedded is related to the number of qubits that can be encoded as explained in the next section, topological quantum error-correcting codes. ~ \begin{defn} A $planar$ graph is a graph that can be embedded in a surface of genus $0,$ that is the plane. \end{defn} $\,$ \begin{defn} The $girth$ of a graph is the length of its shortest cycle. \end{defn} $\:$ \begin{defn} The $shortest$ $noncontractible$ $cycle$ of a graph of genus $g$ is the length of the shortest cycle or closed path that is not a face of the induced tessellation. A face is one of the open discs derived from the difference between the two dimensional manifold $M$ and the embedded graph. \end{defn} $\,$ Furthermore the shortest noncontractible cycle of a graph is related to the number of errors that the code can correct as we explain in the next section. ~ \section{\label{sec:Topological-Quantum-Error-correcting}Topological Quantum Error-correcting Codes} ~ Topological codes are a class of stabilizer codes associated with tessellations of manifolds. Stabilizer codes can be described in terms of group theory or of binary vector spaces. In terms of group theory a codeword is the $+1$ eigenstate of the group generated by a stabilizer set. In terms of binary vector spaces, a stabilizer code is described by a pair of binary matrices whose rows represent generators, and whose columns represent different qubits. One matrix is associated with \begin{eqnarray*} X & = & \left[\begin{array}{cc} 0 & 1\\ 1 & 0\end{array}\right]\end{eqnarray*} and the other matrix with \begin{eqnarray*} Z & = & \left[\begin{array}{cc} 1 & 0\\ 0 & -1\end{array}\right]\end{eqnarray*} Simultaneous entries in both matrices are associated with \begin{eqnarray*} Y & = & \left[\begin{array}{cc} 0 & -i\\ i & 0\end{array}\right]\end{eqnarray*} Multiplication of generators is equivalent to vector addition $mod$ 2. Elements of the stabilizer group have to commute with each other, otherwise they stabilize the trivial space. Using MacKay's notation \cite{mackayquantum}, let $a_{i}|b_{i}$ denote a binary vector, where $a_{i}$ is in row $i$ of the matrix of a stabilizer parity check matrix associated with $X$ errors and $b_{i}$ is in the matrix associated with $Z$ errors. Let $a_{j}|b_{j}$ be another such vector, then the condition that two stabilizer generators commute is equivalent to the following product: \begin{eqnarray*} a_{i}\centerdot b_{j} & +a_{j}\centerdot b_{i}\equiv & 0\; mod\;2\end{eqnarray*} The binary vector view of stabilizer codes emphasizes connections between classical and quantum error correcting codes. Kitaev's toric codes are defined by an $L\times L$ lattice on the torus. The encoding qubits are associated with edges of this lattice. The related stabilizer quantum error-correcting code check operators are associated with faces and vertices as follows: \begin{eqnarray*} Z^{face} & = & \prod_{e\in face}Z_{e}\\ X^{vertex} & = & \prod_{e\in vertex}X_{e}\end{eqnarray*} The vertex and face operators commute because they either act on disjoint qubits or on an even number of qubits in common. Let $e$ be the number of edges, $v$ the number of vertices and $f$ the number of faces of a given grid. By Euler's equation, these toric codes encode $2$ qubits. Since the number of logical qubits remains constant as the number of encoding qubits increases, their asymptotic rate is zero. In order to generalize toric codes to higher genus surfaces, we study tessellations of an orientable 2-manifold of genus $g$. Furthermore a noncontractible cycle in the tessellation or dual tessellation commutes with the stabilizer group of the code because it is a cycle. Nevertheless it is not contained in the stabilizer group. Therefore the distance of the code is the length of the shortest non-contractible cycle in the tessellation. We decode the family of topological codes using belief propagation by simulating the 4-ary symmetric channel as two independent binary symmetric channels in the belief propagation section. Therefore we calculate the independent asymptotical rate of $X^{vertex}$ and $Z^{facce}$ in the next section. ~ The rate for the $Z^{face}$ is \[ \frac{e-(f-1)}{e}\] The rate for the $X^{vertex}$ is \[ \frac{e-(v-1)}{e}\] And the topological rate for the respective code is \[ \frac{e-(f-1)-(v-1)}{e}\] ~ \section{\label{sec:Platonic-Surfaces-and}Platonic Quantum Low-Density Parity-Check Codes} ~ \subsection{Platonic Graph And Surfaces} ~ $Platonic$ $Graphs$ $\pi_{n}$ are generalizations of the Platonic solids \cite{spectralgeometry}. They are characterized by regular tessellations of Riemann surfaces or 2-manifolds, which are called $Platonic$ $Surfaces$ $S_{n}$. ~ \begin{defn} $Platonic\; Graphs$ $\pi_{n}$ are determined by vertices and edges. A vertex of $\pi_{n}$ is defined by a pair of integers $\left({a\atop b}\right)$ such that $\left({a\atop b}\right)\sim\left({-a\atop -b}\right).$ The pair is taken projectively, that is, $gcd(a,b)=1.$ An edge joins two vertices, $\left({a\atop b}\right)$ and $\left({c\atop d}\right)$ iff $det\left[\begin{array}{cc} a & c\\ b & d\end{array}\right]=\pm1$ $mod$ $n.$ \end{defn} ~ Furthermore any two vertices have two paths of length two note that the $Platonic$ $Graphs$ have the two-step property \cite{spectralgeometry}, that is, any two vertices have exactly two paths of length two, associating $\pi_{n}$ to a unique triangulated topological 2-manifold. Also note that $n$ does not have to be a prime number. When $n\geqslant6,$ we obtain a tessellation of a surface of $genus\geqslant1.$ The first few Platonic graphs are the tetrahedron $\pi_{3},$ the octahedron $\pi_{4},$ and the icosahedron $\pi_{5}.$ The Dual Platonic graphs, $\pi'_{n}$, have a vertex for each triangular face in $\pi_{n},$ and an edge between two vertices iff the respective $\pi_{n}$ faces are adjacent. The first few dual Platonic Graphs are the tetrahedron $\pi'_{3}$ (self-dual), the cube $\pi'_{4}$, and the dodecahedron $\pi'_{5}$. ~ \begin{rem} For $p$ odd prime, the graph $\pi_{p}$ has $\frac{p^{2}-1}{2}$ vertices. Let $v_{p}$ be the number of vertices of $\pi_{p}$, then there are $\frac{v_{p}.p}{2}$ edges $e_{p},$ and $\frac{v_{p}.p}{3}$ faces $f_{p}$. For $\pi'_{n}$, there are $v'_{p}=f_{p}$, $e'_{p}=e_{p},$ and $f'_{p}=v_{p}.$ \end{rem} ~ \subsection{\label{sec:Platonic-Surface-Quantum-LDPC}Platonic Quantum Low-Density Parity-Check Codes } ~ In this section we give a specific example of a quantum LDPC code derived from $\pi_{7}$, and an infinite family of good LDPC codes derived from Platonic Surfaces. We calculate their asymptotic rate, analyze their sparsity and provide a lower bound on their distance, the length of its shortest non-contractible cycle ~ \subsubsection*{Example} ~ The Platonic quantum code derived from $\pi_{7}$ has $\frac{p^{2}-1}{2}=24$ vertices $v_{p}$, $\frac{v_{p}.p}{3}=56$ faces, and $\frac{v_{p.}p}{2}=84$ edges, and that it follows that $g=3$ is the genus of the surface. It has quantum rate 1/14. For $\pi'_{7},$ there are $56$ vertices, $24$ faces, and $84$ edges, and its shortest non-contractible cycle is of length $8$. ~ \subsection{Family of Platonic Quantum Low-Density Parity-Check Codes} $\,$ In general we derive a family of quantum LDPC codes from the dual Platonic graphs $\pi'_{p},$ analyze their rate and the next section we provide a bound on their distance of the length of the shortest non-contractible cycle. ~ \subsection{Asymptotic nonzero classical rate for the platonic family of quantum error-correcting codes} $\:$ \begin{rem} \label{thm:TheZfacecheck}The $Z^{face}$ check operator of a dual Platonic quantum LDPC error-correcting code has rate approaching $1$ for $p$ odd prime. \end{rem} ~ \begin{eqnarray*} lim_{p\rightarrow\infty} & \frac{e'_{p}-(f'_{p}-1)}{e'_{p}} & =\\ lim_{p\rightarrow\infty} & \frac{\frac{p^{3}-p}{4}-\left(\frac{p^{2}-1}{2}-1\right)}{\frac{p^{3}-p}{4}} & =\\ & 1\end{eqnarray*} $\,$ \begin{rem} \label{thm:TheXvertexcheck}The $X^{vertex}$ check operator of a dual Platonic quantum LDPC error-correcting code has rate approaching $\frac{1}{3}$, for $p$ odd prime. \end{rem} ~ \begin{eqnarray*} lim_{p\rightarrow\infty} & \frac{e'_{p}-(v'_{p}-1)}{e'_{p}} & =\\ lim_{p\rightarrow\infty} & \frac{\frac{p^{3}-p}{4}-\left(\frac{p^{3}-p}{6}-1\right)}{\frac{p^{3}-p}{4}} & =\\ & \frac{1}{3}\end{eqnarray*} $\,$ \begin{rem} \label{thm:The-average-combined}The average combined rate of the $X^{vertex}$ and $Z^{face}$ operators approaches $\frac{2}{3}$, for $p$ odd prime. \end{rem} ~ \begin{eqnarray*} lim_{p\rightarrow\infty} & \frac{2e'_{p}-(f'_{p}+v'_{p}-2)}{2e'} & =\\ lim_{p\rightarrow\infty} & 1-\frac{f'_{p}+v'_{p}+-2}{2e'_{p}} & =\\ lim_{p\rightarrow\infty} & 1-\frac{1}{p}-\frac{1}{3}+\frac{1}{p^{3}-p} & =\\ & \frac{2}{3}\end{eqnarray*} ~ \subsection{Asymptotic nonzero quantum rate for the platonic family of quantum error-correcting codes} ~ \begin{rem} \label{thm:The-average-combined-1}The quantum rate of the platonic family of quantum error-correcting codes approaches $\frac{1}{3}$, for $p$ odd prime. ~ \end{rem} \begin{eqnarray*} lim_{p\rightarrow\infty} & \frac{e'_{p}-(f'_{p}-1)-(v'_{p}-1)}{e'} & =\\ lim_{p\rightarrow\infty} & 1-\frac{f'_{p}+v'_{p}+2}{e'_{p}} & =\\ lim_{p\rightarrow\infty} & 1-\frac{\frac{p^{2}-1}{2}+\frac{p^{3}-p}{6}+2}{\frac{p^{3}-p}{4}} & =\\ & \frac{1}{3}\end{eqnarray*} ~ \subsection{Sparsity Analysis for the Platonic quantum LDPC error-correcting codes} $\:$ \begin{rem} Let $w_{f}$ be the weight of the $Z^{face}$ check operators of a dual Platonic quantum LDPC error-correcting code, and let $e_{p}$ be the corresponding number of encoding qubits for prime $p$, then $\frac{w_{f}}{e_{p}}$ converges to a $c.p^{-2}$. ~ \begin{eqnarray*} lim_{p\rightarrow\infty} & \frac{p}{e_{p}} & =\\ lim_{p\rightarrow\infty} & \frac{p}{\frac{v_{p}.p}{2}} & =\\ lim_{p\rightarrow\infty} & \frac{p}{\frac{p^{2}-1}{4}p} & =\\ & c.p^{-2}\end{eqnarray*} \end{rem} $\:$ \begin{rem} Let $w_{v}=3$ be the weight of the $Z^{vertex}$ check operators of a dual Platonic quantum LDPC error-correcting code, and let $e_{p}$ be the corresponding number of encoding qubits for prime $p$, then $\frac{w_{v}}{e_{p}}$ converges to zero. ~ \begin{eqnarray*} lim_{p\rightarrow\infty} & \frac{3}{e_{p}} & =\\ & 0\end{eqnarray*} \end{rem} ~ \section{\label{sec:Shortest-non-contractible-cycle}Shortest non-contractible cycle bound for the dual Platonic surfaces $snc(\pi_{p}^{'})$} $\;$ We show that the shortest non-contractible cycle of the family of dual platonic graphs $\pi'_{p}$ grows logarithmically in the size of their genus. In order to improve the distance of $\pi_{p}$ we obtain subfamilies of Platonic codes by subtessellating them up to $log(p)$ levels of recursion. See decoding simulation section. ~ We derive the $\pi'_{p}$ bound by regarding these graphs as quotient of $T_{3},$ the infinite cubic tree \cite{Biggs-1}. Vertices in $T_{3}$ are labeled with unordered triplets of irreducible rational numbers, $\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right)$. This labeling is known as a $Farey$ $Tree$. See figure 1 . ~ \begin{defn} We define the following binary tree $B.$ The root of $B$ is $\left(\left({0\atop 1}\right)\left({1\atop 2}\right)\left({1\atop 1}\right)\right).$ For a vertex $\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right)$ in $B$, its left child is $\mbox{\ensuremath{\left(\mbox{\ensuremath{\left({a\atop b}\right)\left({a+c\atop b+d}\right)\left({c\atop d}\right)}}\right)}}$ and its right child is $\left(\left({c\atop d}\right)\left({c+e\atop d+f}\right)\left({e\atop f}\right)\right)$. \end{defn} ~ \begin{defn} $T_{3}$ is defined recursively by generalizing the labels of the following rooted binary tree $B.$ $B_{0}$ is $B$ and $B_{n}$ is obtained from $B$ by adding $n$ to the pairs, i.e. $\left({a\atop b}\right)$ is relabeled as $\left({(a+n)\atop b}\right).$ $T_{3}$ is obtained by adjoining the root of a copy $B_{n}$ to $\left(\left({1\atop 0}\right)\left({n\atop 1}\right)\left({n+1\atop 1}\right)\right)$. ~ % \begin{figure} \includegraphics[scale=0.47]{figures/fareytree} \caption{Farey Tree} % \end{figure} \end{defn} ~ In the girth of a family of 3-regular graphs, the triplets $T(p)$, by mapping each pair $\left({a\atop b}\right)$ to $a.b^{-1}mod$ p. If b = 0, then $a.b^{-1}mod$~p is mapped to $\infty.$ We obtain the dual Platonic graphs $\pi'$ from $T_{3}$ under the equivalence $\left({a\atop b}\right)\sim\mbox{\ensuremath{\left({-a\atop -b}\right)}}mod\; p$. Using $T_{3},$ we show that the shortest non-contractible cycle in the graph, for large $p$ prime, is bounded by $p^{2}\leq Fibonacci(snc(\pi'_{p})+2)$. We provide lemmas about the rooted binary tree $B$ and prove a lemma about a needed symmetry of the tree before proving the distance theorem. ~ \begin{lem} \label{lem:For-any-vertex}For any vertex $\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right)$ in $B$, \begin{eqnarray*} b\centerdot c-a\centerdot d & = & d\centerdot e-c\centerdot f=1.\end{eqnarray*} \end{lem} \begin{cor} For each pair $\left({a\atop b}\right),$ \begin{eqnarray*} gcd(a,b) & = & 1.\end{eqnarray*} \end{cor} \begin{lem} \label{lem:The-largest-fib}The largest $b$ in a pair $\left({a\atop b}\right)$ at level $r$, is $Fibonacci(r+2).$ ~ \end{lem} In addition we further observe that there is a symmetry of the tree $B$ that preserves the level of the vertices and induces a reflection on the tree. The symmetry is given by $\left({b-a\atop b}\right)$ on each pair. In the following lemma we use $x,$ as short for $\left({a\atop b}\right),$ and $\left(1-x\right)$ as short for $\left({b-a\atop b}\right).$ ~ \begin{lem} \label{lem:6 symmetry}Let $\left(\left(x\right)\left(y\right)\left(z\right)\right)$ be a vertex $v$, then the involution $i$ that takes $v$ to $\left(\left(1-z\right)\left(1-y\right)\left(1-x\right)\right)$ is a reflection of the tree $B$. \end{lem} ~ Proof. We prove this lemma by induction. Note that the root of $B$, $\left(\left({0\atop 1}\right)\left({1\atop 2}\right)\left({1\atop 1}\right)\right)$, is a fixed point of the symmetry. Assume that the symmetry holds for all vertices in $B$ at levels less than $n.$ Let $v=\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right),$ be a vertex at level $n-1.$ Denote the involution on $v$, as $i(v)=\left(\left({f-e\atop f}\right)\left({d-c\atop d}\right)\left({b-a\atop b}\right)\right).$ Denote the left descendant of $v$ as $v_{left}$, and the right descendant as $v_{right}.$ Then, \begin{eqnarray*} v_{left} & = & \left(\left({a\atop b}\right)\left({a+c\atop b+d}\right)\left({c\atop d}\right)\right)\end{eqnarray*} and \begin{eqnarray*} v_{right} & = & \left(\left({c\atop d}\right)\left({c+e\atop b+f}\right)\left({e\atop f}\right)\right)\end{eqnarray*} Under the involution, the results are: \begin{eqnarray*} i(v_{left}) & = & \left(\left({d-c\atop d}\right)\left({b+d-c-a\atop b+d}\right)\left({b-a\atop b}\right)\right)\end{eqnarray*} and \begin{eqnarray*} i(v_{right}) & = & \left(\left({f-e\atop f}\right)\left({b+f-c-e\atop b+f}\right)\left({d-c\atop d}\right)\right)\end{eqnarray*} which implies that $i(v_{left})=(i(v))_{right}$, and $i(v_{right})=(i(v))_{left}$.~ ~ \begin{thm} For large $p$ prime, $p^{2}\leq$Fibonacci ($snc(\pi_{p}^{'})$+2). ~ \end{thm} Proof. Because $\pi'_{p}$ is vertex transitive, we consider only the cycles from $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$. A set of three pairs $\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right)$ corresponds to a vertex in $\pi'_{p}$ and a face in $\pi_{p}.$ Each individual pair corresponds to a vertex in $\pi_{p}.$ The order of the pairs within a set does not matter. Therefore, there are six ways in which a vertex in $T_{3}$ can reduce to $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$, that is all 6 permutations of 3 pairs. In addition, the reflection proved in lemma \ref{lem:6 symmetry} allows us to consider only 4 cases. Note that under this symmetry, the following cases are equivalent $\left(\left({0\atop 1}\right)\left({1\atop 1}\right)\left({1\atop 0}\right)\right)$ $\sim$ $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right),$ and $\left(\left({1\atop 1}\right)\left({0\atop 1}\right)\left({1\atop 0}\right)\right)$ $\sim$ $\left(\left({1\atop 0}\right)\left({1\atop 1}\right)\left({0\atop 1}\right)\right).$ ~ Case $\left(\left({0\atop 1}\right)\left({1\atop 0}\right)\left({1\atop 1}\right)\right)$ ~ \[ \left(\begin{array}{c} a\centerdot p+e\centerdot p+1\\ f\centerdot p+b\centerdot p+1+g\end{array}\right)\] In order for this pair to reduce to $\left({1\atop 0}\right)$, we have that $g=-1.$ By applying lemma \ref{lem:For-any-vertex}, we get a contradiction. ~ Case $\left(\left({1\atop 0}\right)\left({1\atop 1}\right)\left({0\atop 1}\right)\right)$ ~ We get a similar reduction to the previous case ~ Case $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$ ~ A vertex that reduces to $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$ must be of the form: \[ \left(\left({a\centerdot p\mp1\atop b\cdot p}\right)\left(\begin{array}{c} a\centerdot p+e\centerdot p\\ b\centerdot p+f\centerdot p\mp1\end{array}\right)\left(\begin{array}{c} e\centerdot p\mp1\\ f\centerdot p\mp1\end{array}\right)\right)\] ~ For simplicity let $c=a+e$ and $d=b+f.$ Then by applying lemma \ref{lem:For-any-vertex} to the first two pairs, we get: \[ b\centerdot c\centerdot p^{2}-(a\centerdot p\pm1)\centerdot(dp\mp1)=1\] which implies that \[ \mp d=(a\centerdot d-b\centerdot c)\centerdot p\mp a\] Let $a\centerdot d-b\centerdot c=g.$ Then a vertex that reduces to $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$ has the following form: \[ \left(\left({a\centerdot p\pm1\atop b\centerdot p}\right)\left({c\centerdot p\atop g\centerdot p^{2}\mp a\centerdot p\mp1}\right)\left({e\centerdot p\mp1\atop f\centerdot p\mp1}\right)\right)\] ~ Case $\left(\left({1\atop 1}\right)\left({1\atop 0}\right)\left({0\atop 1}\right)\right)$ ~ We get a similar reduction. ~ Therefore by lemma \ref{lem:For-any-vertex} \[ p^{2}\leq Fibonacci(girth(\pi'_{p})+2)\] Therefore for large $p,$ $girth(\pi'_{p})