#LyX 1.3 created this file. For more info see http://www.lyx.org/ \lyxformat 221 \textclass article \language english \inputencoding auto \fontscheme default \graphics default \paperfontsize default \spacing single \papersize Default \paperpackage a4 \use_geometry 0 \use_amsmath 0 \use_natbib 0 \use_numerical_citations 0 \paperorientation portrait \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \defskip medskip \quotes_language english \quotes_times 2 \papercolumns 1 \papersides 1 \paperpagestyle default \layout Title \noun on Paperfolding \noun default \noun on Sequences \newline and quasicrystals \layout Author David Longbottom \layout Abstract The purpose of this project is to look at the paper-folding sequence, and how aperiodic sequences can be used in the study of quasicrystals. I start by describing what the paper-folding sequence is and how to generate it. I then show how the sequence is used to draw dragon curves, and discuss some of the curve's properties. I talk about an application of one of the properties of the sequence in the expansion of continued fractions before moving on to describing aperiodic sequences and their use in quasicrystal theory. The appendix describes the computer code created for this project. \layout Standard \begin_inset LatexCommand \tableofcontents{} \end_inset \layout Section Introduction \layout Subsection Outline \layout Standard This project will investigate some of the interesting mathematical properties of paperfolding sequences. This will include an analysis of how the paperfolding sequence is generated, its fractal nature, and its relation to continued fractions and other aperiodic sequences such as the Fibonacci sequence and Rudin-Shapiro sequences. Then we will discuss how they may be used in the study of one dimensional quasicrystals. \layout Subsection Introduction \layout Standard It is common knowledge that a piece of paper cannot be folded in half more than eight times. It is less well known that the actual maximum is 12 times \begin_inset LatexCommand \cite{maxpaper} \end_inset . This project takes as its model the idea of folding a long strip off paper in half, several times over. When the paper is unfolded, a series of hills and valleys are revealed. It is this sequence of hills and valleys that will be studied. Note, that the limit on how many times a real piece of paper can be folded is not the point here, and will be ignored. We assume that we have an \begin_inset Quotes eld \end_inset ideal \begin_inset Quotes erd \end_inset piece of paper that we can fold as many times as we like. \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename figures/paper_example.fig \end_inset \layout Caption \begin_inset LatexCommand \label{cap:Paper-after-unfolding.} \end_inset Example of Paper after unfolding. \end_inset \layout Section Notation \layout Subsection Language \layout Standard Throughout this paper, \emph on folding \emph default will be used to describe the act of folding the paper, while \emph on creases \emph default will be used to describe the series of folds left in the paper when unfolded. \layout Subsection Alphabets and Words \layout Standard \begin_inset LatexCommand \label{sub:Alphabets-&-Words} \end_inset The sequence of \begin_inset Quotes eld \end_inset hills & valleys \begin_inset Quotes erd \end_inset is a binary sequence. Thus it is natural to represent the sequence by a word made up from an alphabet of only two letters. Let \begin_inset Formula $A$ \end_inset be an alphabet (i.e. a finite set), and let \begin_inset Formula $A^{*}$ \end_inset be the set of all words made up of letters from \begin_inset Formula $A$ \end_inset . Thus a paperfolding sequence is a subset of \begin_inset Formula $A^{*}$ \end_inset . In this project we shall usually use \begin_inset Formula $A=\{0,1\}$ \end_inset , though sometimes \begin_inset Formula $A=\{-1,+1\}$ \end_inset will be looked at, depending on which is most appropriate. So, the above diagram (figure \begin_inset LatexCommand \ref{cap:Paper-after-unfolding.} \end_inset ) could be represented by the word \begin_inset Formula $0010011\in A^{*}$ \end_inset . Note that we could also use alphabets like \begin_inset Formula $\{ a,b\}$ \end_inset or \begin_inset Formula $\{\vee,\wedge\}$ \end_inset or even \begin_inset Formula $\{\textrm{jack},\textrm{jill}\}$ \end_inset , it doesn't really matter as they are simply labels. It is useful to sometimes use the alphabets made of numbers though, especially for when we come to functional equations. \layout Standard The folding instructions (and unfolding instructions) can also be represented by a similar binary sequence, usually using the same alphabet. \layout Subsection Polynomials \layout Standard It can also be useful to represent the sequence (of length \begin_inset Formula $n$ \end_inset ) by a polynomial of the form: \begin_inset Formula \[ f(x)=\sum_{k=0}^{n-1}a_{k}x^{k}=a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{n}x^{n-1}\] \end_inset \layout Standard where \begin_inset Formula $(a_{k})\epsilon\{0,1\}$ \end_inset or alternatively \begin_inset Formula $(a_{k})\epsilon\{-1,+1\}$ \end_inset . (See section \begin_inset LatexCommand \ref{sub:Alphabets-&-Words} \end_inset ) In this case, for each element in the polynomial, the power of \begin_inset Formula $x$ \end_inset represents the position of its coefficient in the word describing the sequence. So \begin_inset Formula $0010011\equiv f(x)=x^{2}+x^{5}+x^{6}$ \end_inset . Alternatively, if we use the alphabet \begin_inset Formula $\{-1,+1\}$ \end_inset , we have the polynomial \begin_inset Formula $f(x)=-1-x+x^{2}-x^{3}-x^{4}+x^{5}+x^{6}$ \end_inset . \newline We can convert between the two systems. Say \begin_inset Formula $f(x)$ \end_inset uses coefficients \begin_inset Formula $a_{k}\epsilon\{0,1\}$ \end_inset , then the equivalent function with coefficients \begin_inset Formula $\{-1,+1\}$ \end_inset is \begin_inset Formula $\sum_{k=0}^{n-1}(-1)^{a_{k}+1}x^{k}$ \end_inset . To go the other way (with \begin_inset Formula $f(x)$ \end_inset using coefficients \begin_inset Formula $b_{k}\epsilon\{-1,+1\}$ \end_inset ) we get \begin_inset Formula $\sum_{k=0}^{n-1}\frac{1}{2}(1+b_{k})x^{k}$ \end_inset . \layout Section Folding Operation \layout Standard When the paper is folded in half, an alternating series of creases is placed between the existing folds, as we see in section \begin_inset LatexCommand \ref{sub:Folding-Algorithm} \end_inset . Whether this alternating series of folds begins with a 0 or a 1 depends on which way the paper is folded. Remember, one can either fold the paper right over left, or left over right. Also, one can simply turn the paper around or over between each folding. Thus, the way we fold the paper can be described by a series of folding instructions \begin_inset Formula $\in A^{*}$ \end_inset For the moment, we shall only consider folding the paper the same way each time, i.e. the folding instructions are \begin_inset Formula $0000\ldots$ \end_inset . \layout Subsection Folding Algorithm \layout Standard \begin_inset LatexCommand \label{sub:Folding-Algorithm} \end_inset It can be seen that the following sequence of creases are observed for each fold: \begin_inset Float table placement H wide false collapsed true \layout Caption Folding \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard number of folds \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \end_inset \end_inset \layout Standard If one imagines that one side (say the top side) of the paper is black, and the other side is white, one can then see that folding the paper will cause it to alternate black/white side up. That is, a new fold will always cause a same-coloured face to fold onto itself, so the first half of the side will now be one way up, and the second half the opposite way up. So, given this stack of alternating faces up, the folding operation would cause new creases in all these faces. The white faces would obtain creases in one direction, and the black faces would obtain creases in the opposite direction. Since the white and black faces are alternating, the new creases will alternate in the same way. \layout Standard So a folding instruction of 0 would inserts 0 1 0 1 0 1 .... between the existing creases, while a folding instruction of 1 would insert 1 0 1 0 1 0 ... between the existing creases. \layout Subsubsection \begin_inset LatexCommand \label{sub:Total-Number-of} \end_inset Total Number of Creases in a sequence \layout Standard Given \begin_inset Formula $l_{n}$ \end_inset creases in the \begin_inset Formula $n$ \end_inset -th fold, the \begin_inset Formula $(n+1)$ \end_inset th fold will have \begin_inset Formula $l_{n}+1$ \end_inset more creases than in the \begin_inset Formula $n$ \end_inset -th. This is because one new crease will appear to the left of each old crease, and a final one to the right of the last old crease. So we have the recurrence relation \begin_inset Formula $l_{n+1}=2l_{n}+1$ \end_inset . Since, on no folds we have no creases, \begin_inset Formula $l_{0}=0$ \end_inset . Solving this recurrence relation gives \begin_inset Formula $l_{n}=2^{n}-1$ \end_inset \begin_inset Foot collapsed true \layout Standard \begin_inset Formula $l_{n}=2l_{n-1}+1=2(2l_{n-2}+1)+1=4l_{n-2}+2+1=\ldots=2^{n}l_{0}+2^{n-1}+2^{n-2}\ldots+4+2+1=2^{n}l_{0}+2^{n}-1=2^{n}-1$ \end_inset \end_inset . \layout Standard Note - this means that the number of creases is always odd, and (except for the zeroth fold) the number of new creases is always even, with an equal number of ones and zeros added. \layout Subsubsection The Algorithm \layout Standard \begin_inset LatexCommand \label{sub:algoritm1} \end_inset Given a sequence of creases, another fold would introduce creases in between the existing creases. Each existing crease would mean the the new creases on either side of it were opposite in nature. Our folding instruction defines the first new crease, and the subsequent new creases will alternate in sign, until we reach the last new crease, which will be opposite in sign from the first new crease \begin_inset Foot collapsed true \layout Standard Except for the first fold, which simply introduces a single 0 or 1 (depending on which way one folds it) \end_inset . \layout Subsection Folding Operators \layout Standard \begin_inset LatexCommand \label{sub:Folding-Operators} \end_inset We can now express folding as the following folding operators: \begin_inset Formula $P_{0},P_{1}:A^{*}\longrightarrow A^{*}$ \end_inset for \begin_inset Formula $n>0$ \end_inset defined as \begin_inset LatexCommand \cite{fibonaccipdf} \end_inset : \layout Standard \begin_inset Formula $P_{0}(a_{0}\cdots a_{n})=0a_{0}1a_{1}0\cdots a_{n}1$ \end_inset \layout Standard \begin_inset Formula $P_{1}(a_{0}\cdots a_{n})=1a_{0}0a_{1}1\cdots a_{n}0$ \end_inset \layout Standard Where \begin_inset Formula $P_{i}$ \end_inset is a folding instruction of \begin_inset Formula $i$ \end_inset . (Trivially, \begin_inset Formula $P_{i}(\emptyset)=i$ \end_inset ) Thus the folding instructions \begin_inset Formula $101$ \end_inset can be executed as \begin_inset Formula $P_{1}\circ P_{0}\circ P_{1}\circ\emptyset\equiv P_{1}(P_{0}(P_{1}(\emptyset)))=P_{1}(P_{0}(1))=P_{1}(011)=1001110$ \end_inset \layout Subsection Polynomial Equations \layout Standard Given a sequence \begin_inset Formula $f(x)=a_{0}+a_{1}x+\ldots+a_{n}x^{n}$ \end_inset , the folding operator will insert new folds between the existing, so we separate out the existing folds using \begin_inset Formula $xf(x^{2})=a_{0}x+a_{1}x^{3}+\ldots+a_{n}x^{2n+1}$ \end_inset . Now what we do depends on which way we fold, and which alphabet we are using (see section \begin_inset LatexCommand \ref{sub:Alphabets-&-Words} \end_inset ): \layout Subsubsection \begin_inset Formula $A=\{0,1\}$ \end_inset \layout Standard \begin_inset LatexCommand \label{sub:-A={0,1}} \end_inset In the case of a \begin_inset Formula $0$ \end_inset -fold we add \begin_inset Formula $0+x^{2}+0+x^{6}+0+\ldots+0+x^{2n+2}=\sum_{k=0}^{n/2}x^{4k+2}$ \end_inset to \begin_inset Formula $xf(x)$ \end_inset . In the case of a \begin_inset Formula $1$ \end_inset -fold, we add \begin_inset Formula $1+x^{4}+\ldots+0+x^{2n}+0=\sum_{k=0}^{n/2}x^{4k}$ \end_inset . So \begin_inset Formula $T_{0}(f(x))=xf(x^{2})+\sum_{k=0}^{n/2}x^{4k+2}$ \end_inset and \begin_inset Formula $T_{1}(f(x))=xf(x^{2})+\sum_{k=0}^{n/2}x^{4k}$ \end_inset . \layout Subsubsection \begin_inset Formula $A=\{-1,+1\}$ \end_inset \layout Standard instead, we would add \begin_inset Formula $-1+x^{2}-x^{4}+\cdots-x^{2n}+x^{2n+2}=\sum_{k=0}^{n+1}(-1)^{k}x^{2k}$ \end_inset in the case of a \begin_inset Formula $0$ \end_inset -fold. In the case of a \begin_inset Formula $1$ \end_inset -fold we add \begin_inset Formula $1-x^{2}+x^{4}-\cdots+x^{2n}-x^{2n+2}=\sum_{k=0}^{n+1}-(-1)^{k}x^{2k}$ \end_inset . So \begin_inset Formula $T_{-1}(f(x))=xf(x^{2})+\sum_{k=0}^{n}(-1)^{k}x^{2k}$ \end_inset and \begin_inset Formula $T_{+1}(f(x))=xf(x^{2})-\sum_{k=0}^{n}(-1)^{k}x^{2k}$ \end_inset \layout Subsection Building up the sequence \layout Standard \begin_inset LatexCommand \label{sub:algoritm2} \end_inset The paperfolding sequence becomes interesting once we start to look at the different ways in which it can be built up. For repeated 0-folds, the sequence looks like this: \layout Standard \begin_inset Float table placement h wide false collapsed true \layout Caption \begin_inset LatexCommand \label{cap:Folds-&-Seqence} \end_inset Folds and Sequences \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard folds \end_inset \begin_inset Text \layout Standard sequence \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\emptyset$ \end_inset \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 001 \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard 0010011 \end_inset \begin_inset Text \layout Standard 4 \end_inset \begin_inset Text \layout Standard 001001100011011 \end_inset \begin_inset Text \layout Standard 5 \end_inset \begin_inset Text \layout Standard 0010011000110110001001110011011 \end_inset \end_inset \end_inset Looking at the pattern indicates another algorithm that can be used to build up the paperfolding sequence. It appears that when we fold the paper, the next sequence will start with the old sequence, add a 0, and then the old sequence reversed and inverted. So, say \begin_inset Formula $\overrightarrow{w_{n}}$ \end_inset is word describing the sequence after the \begin_inset Formula $n$ \end_inset -th fold, and \begin_inset Formula $\overleftarrow{w_{n}}^{\dagger}$ \end_inset is the mirrored inverse of it (e.g. \begin_inset Formula $\overleftarrow{001}^{\dagger}=\overrightarrow{011}$ \end_inset ). \begin_inset Formula \[ \overrightarrow{w_{n+1}}=\overrightarrow{w_{n}}0\overleftarrow{w_{n}}^{\dagger}\] \end_inset \layout Standard To explain this, instead of folding our paper a finite number of times, we could unfold it a finite number of times instead. So, after the \begin_inset Formula $n$ \end_inset -th unfolding, we have the word \begin_inset Formula $\overrightarrow{w}$ \end_inset say. Then, upon unfolding again, we would have the word \begin_inset Formula $\overrightarrow{w}0\overleftarrow{w}^{\dagger}$ \end_inset (assuming, without loss of generality, that this was a \begin_inset Formula $0$ \end_inset -fold). The pattern in table \begin_inset LatexCommand \ref{cap:Folds-&-Seqence} \end_inset is explained as follows: if we fold the same way each time (i.e. folding instructions 0000...), on the n-th fold, the left hand side will behave as if it's been folded n-1 times. \layout Standard We can generalise this idea, and define an operator \begin_inset Formula $p_{i}:A^{*}\longrightarrow A^{*}$ \end_inset , \begin_inset Formula $p_{i}(\overrightarrow{w})=\overrightarrow{w}i\overleftarrow{w}^{\dagger}$ \end_inset where \begin_inset Formula $i\in A^{*}$ \end_inset is a word. So a \begin_inset Formula $0$ \end_inset -fold is the operation \begin_inset Formula $p_{0}$ \end_inset and a \begin_inset Formula $1$ \end_inset -fold is the operation \begin_inset Formula $p_{1}$ \end_inset . These will be the same as the operators from section \begin_inset LatexCommand \ref{sub:Folding-Operators} \end_inset , but in reverse order. \layout Subsection Functional Equation \layout Standard We have observed that the first half of the sequence for \begin_inset Formula $n+1$ \end_inset folds is the same as the sequence for \begin_inset Formula $n$ \end_inset folds. This can be expressed using the polynomial notation \begin_inset Formula $\{0,1\}$ \end_inset , and \begin_inset Formula $f_{0}(x)=0$ \end_inset : \layout Standard \begin_inset Formula \[ f_{n+1}(x)=f_{n}(x)+x^{2^{n+1}}\left(\frac{x^{-2^{n+1}+2}-x}{1-x}-f_{n}(x^{-1})\right)\] \end_inset \begin_inset Foot collapsed true \layout Standard note \begin_inset Formula $\frac{x^{-2^{n+1}+2}-x}{1-x}=x^{-(2^{n+1}-2)}+x^{-(2^{n+1}-2)+1}+\cdots+x^{2}+x+1$ \end_inset where the length of the sequence is \begin_inset Formula $2^{n+1}-1$ \end_inset \end_inset or with \begin_inset Formula $\{-1,+1\}$ \end_inset , \begin_inset Formula $f_{0}(x)=-1$ \end_inset : \layout Standard \begin_inset Formula \[ f_{n+1}(x)=f_{n}(x)-x^{2^{n}}-x^{2^{n+1}}f_{n}(x^{-1})\] \end_inset So it is possible, under folding instructions of 000... (or 111....), to let \begin_inset Formula $n$ \end_inset go to infinity. That is \begin_inset Formula $\lim_{n\rightarrow\infty}f_{n}(x)=f(x)$ \end_inset . If we apply the folding operation to \begin_inset Formula $f(x)$ \end_inset we will obtain \begin_inset Formula $f(x)$ \end_inset as \begin_inset Formula $f(x)$ \end_inset is a stationary point of the folding operation. \layout Standard \begin_inset Float table placement H wide false collapsed true \layout Caption Observation 2 \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $f(x)$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\equiv$ \end_inset \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard ... \end_inset \begin_inset Text \layout Standard - \end_inset \begin_inset Text \layout Standard \begin_inset Formula $f(x^{2})$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\equiv$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard ... \end_inset \begin_inset Text \layout Standard = \end_inset \begin_inset Text \layout Standard \begin_inset Formula $x^{2}+x^{6}+\dots$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\equiv$ \end_inset \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard ... \end_inset \end_inset \end_inset That is, in functional notation, \layout Standard \begin_inset Formula \[ f(x)-f(x^{2})=x^{2}+x^{6}+...=\frac{x^{2}}{1-x^{4}}\] \end_inset \layout Standard As \begin_inset Formula $(1-x^{4})(x^{2}+x^{6}+x^{10}+\dots)=x^{2}-x^{6}+x^{6}-x^{10}+x^{10}+\dots=x^{2}$ \end_inset . This equation is the same as the one in section \begin_inset LatexCommand \ref{sub:-A={0,1}} \end_inset , but with the limit \begin_inset Formula $n\rightarrow\infty$ \end_inset . \layout Subsection Automata \layout Standard The above fact means that, if we 0-fold each time, the sequence of creases will start the exact same way after each fold. This indicates that it may be possible to generate the creases sequence using a automata or a tag machine. \layout Subsubsection 2-Automaton \layout Standard \begin_inset LatexCommand \label{sub:2-Automaton} \end_inset The total number of creases in a sequence is given by \begin_inset Formula $l_{n}=2^{n}-1$ \end_inset (see section \begin_inset LatexCommand \ref{sub:Total-Number-of} \end_inset ). This indicates that it would be a good idea to index each crease in a sequence in binary. Thus the first crease is always labeled by \begin_inset Formula $1$ \end_inset and the last crease \begin_inset Formula $11\ldots11$ \end_inset . It is useful to associate with each label the number of 0s from the right of the binary number before the first 1, i.e. the highest power of 2 this number is divisible by (I will call this value the \emph on order \emph default ). \layout Standard \begin_inset Float table placement H wide false collapsed true \layout Caption 1 fold \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard position \end_inset \begin_inset Text \layout Standard crease \end_inset \begin_inset Text \layout Standard order \end_inset \begin_inset Text \layout Standard 01 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \end_inset \end_inset \begin_inset Float table placement H wide false collapsed true \layout Caption 2 folds \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard position \end_inset \begin_inset Text \layout Standard crease \end_inset \begin_inset Text \layout Standard order \end_inset \begin_inset Text \layout Standard 001 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 010 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 011 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \end_inset \end_inset \begin_inset Float table placement H wide false collapsed true \layout Caption 3 folds \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard position \end_inset \begin_inset Text \layout Standard crease \end_inset \begin_inset Text \layout Standard order \end_inset \begin_inset Text \layout Standard 0001 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0010 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0011 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0100 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 0101 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0110 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0111 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \end_inset \end_inset \begin_inset Float table placement H wide false collapsed true \layout Caption 4 folds \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard position \end_inset \begin_inset Text \layout Standard crease \end_inset \begin_inset Text \layout Standard order \end_inset \begin_inset Text \layout Standard 0001 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0010 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0011 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0100 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 0101 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0110 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0111 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1000 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard 1001 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1010 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1011 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1100 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 1101 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1110 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1111 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \end_inset \end_inset \layout Standard \begin_inset LatexCommand \label{order} \end_inset The order of each crease corresponds to the number of folds since that crease was introduced. In polynomial notation, on folding, crease \begin_inset Formula $ax^{k}$ \end_inset is moved to \begin_inset Formula $xa(x^{2})^{k}=ax^{2k+1}$ \end_inset . So its position, which was \begin_inset Formula $k+1$ \end_inset , will now be \begin_inset Formula $2(k+1)$ \end_inset , i.e. doubled, which is an extra order in binary. Note that this is true no matter what folding instructions are used. In fact the order of the number will tell us what instruction was used on that fold. If the order is greater than zero, then we know that the creases on either side were only introduced this last fold \layout Standard Let us observe what happens when we divide each binary index by \begin_inset Formula $2^{o}$ \end_inset , where \begin_inset Formula $o$ \end_inset is the order of the number): \layout Standard \begin_inset Float table placement H wide false collapsed true \layout Caption Corrected by order \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard index - \begin_inset Formula $2^{o}$ \end_inset \end_inset \begin_inset Text \layout Standard crease \end_inset \begin_inset Text \layout Standard 00 01 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 00 01 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 00 11 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 00 01 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 01 01 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 00 11 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 01 11 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 00 01 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 10 01 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 01 01 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 10 11 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 00 11 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 11 01 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 01 11 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 11 11 \end_inset \begin_inset Text \layout Standard 1 \end_inset \end_inset \end_inset Observation indicates that, if this new index ends in 01, the crease is 0, and if it ends in 11 the crease is 1. This is because, on the next fold, pairs of hills & valleys are introduced on either side of the odd existing creases. 01 tells us that this crease was before one of these odd creases, so is a valley, and 11 indicates that it came after such a crease, so is a hill. Therefore our 2-automaton must take the binary index as input (reading right to left), ignore all the zeros until it reaches a 1, then check the next binary-digit after that to decide what the crease is like: \layout Standard \begin_inset Float figure placement H wide false collapsed true \layout Standard \begin_inset Graphics filename /home/pumaman/math-project/figures/2automaton.fig scale 80 keepAspectRatio \end_inset \layout Caption 2-Automaton for 000... folding \end_inset \layout Standard Example: to find if the 6th crease is a hill or valley. 6 is 00110 in binary. Note, there are actually an infinite number of zero digits on the left hand side, we just don't normally write them. Our automaton reads the digits from right to left. It begins at the node marked \begin_inset Quotes eld \end_inset Start \begin_inset Quotes erd \end_inset , and reads the \begin_inset Quotes eld \end_inset 0 \begin_inset Quotes erd \end_inset instruction, so follows the arrow marked \begin_inset Quotes eld \end_inset 0 \begin_inset Quotes erd \end_inset , and returns to the \begin_inset Quotes eld \end_inset Start \begin_inset Quotes erd \end_inset node. The next instruction to be read off is a \begin_inset Quotes eld \end_inset 1 \begin_inset Quotes erd \end_inset , so we follow the \begin_inset Quotes eld \end_inset 1 \begin_inset Quotes erd \end_inset arrow to the next node (the one with no label). The next instruction is also a \begin_inset Quotes eld \end_inset 1 \begin_inset Quotes erd \end_inset , so we follow that arrow to reach the node marked \begin_inset Quotes eld \end_inset hill \begin_inset Quotes erd \end_inset . From there all the rest of the instructions (0000...) will keep it at this node, and the automaton's output is that the 6th crease is a hill. \layout Subsubsection What about other folding instructions? \layout Standard \begin_inset LatexCommand \label{peanoinstr} \end_inset Instead of folding in the same direction each time, we could alternate the folding instructions, i.e. 0101010101... So the sequence would evolve as follows: \begin_inset Float table placement h wide false collapsed true \layout Caption Alternating Folding Instructions \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard folding instruction \end_inset \begin_inset Text \layout Standard sequence \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 100 \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0110001 \end_inset \begin_inset Text \layout Standard 4 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 100111001000110 \end_inset \end_inset \end_inset \layout Standard In a similar way to before, we have table \begin_inset LatexCommand \ref{cap:Alternating-Folding-Instructions} \end_inset . It shows what happens after folding the strip 4 times. The first column indexes the 15 creases, the second column shows the patter of hills (1) and valleys (0) when using 0101 as the folding instructions, and the next column when we use 0000. \begin_inset Quotes eld \end_inset Same? \begin_inset Quotes erd \end_inset checks if these two columns give the same result for that crease (XOR). Order is the order as described above in section \begin_inset LatexCommand \ref{order} \end_inset , and the final column shows what folding instruction was used when that crease was introduced. \begin_inset Float table placement h wide false collapsed true \layout Caption Alternating Folding Instructions, \begin_inset Formula $n=4$ \end_inset \begin_inset LatexCommand \label{cap:Alternating-Folding-Instructions} \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard crease \end_inset \begin_inset Text \layout Standard instructions 0101 \end_inset \begin_inset Text \layout Standard instructions 0000 \end_inset \begin_inset Text \layout Standard same? \end_inset \begin_inset Text \layout Standard order, \begin_inset Formula $o$ \end_inset \end_inset \begin_inset Text \layout Standard folding instruction ( \begin_inset Formula $n-o$ \end_inset ) \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard y \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 4 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 5 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 6 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard y \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 7 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 8 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard y \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 9 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 10 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard y \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 11 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 12 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 13 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 14 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard y \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 15 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard n \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \end_inset \end_inset \layout Standard So, by looking at the order (see section \begin_inset LatexCommand \ref{order} \end_inset ), one knows what folding instruction was used for that fold. If it was a 0, then one knows that the crease will be the same as that for the basic 0000... instructions. On the other hand, if is was a 1, then the crease will be opposite. \layout Standard A folding instruction of 1 can be thought of as folding the paper in an opposite way to a 0-fold. Instead it could be thought of as turning the paper over, then folding the same way as a 0-fold. Turning the paper over serves to invert the sequence. i.e., if the sequence is \begin_inset Formula $\overrightarrow{w}\in\{-1,1\}^{*}$ \end_inset then turning it over gives \begin_inset Formula $-\overrightarrow{w}$ \end_inset . Then we can apply the second folding algorithm as before (see section \begin_inset LatexCommand \ref{sub:algoritm2} \end_inset ): put a zero onto the end of the sequence, and then put the sequence reversed and inverted onto the end. \layout Subsection Another method \layout Standard If folding instructions \begin_inset Formula $i_{1}i_{2}i_{3}\cdots i_{n}\in A^{*}$ \end_inset are used to create the paperfolding sequence \begin_inset Formula $a_{1}a_{2}a_{3}\cdots a_{2^{n}-1}\in A^{*}$ \end_inset with \begin_inset Formula $A=\{-1,+1\}$ \end_inset then we know that certain crease \begin_inset Formula $a_{k}$ \end_inset will be the same as the folding instruction \begin_inset Formula $i_{j}$ \end_inset . In fact \begin_inset Formula $a_{2^{k}}=i_{n-k}$ \end_inset . \layout Standard By the first algorithm (section \begin_inset LatexCommand \ref{sub:Folding-Operators} \end_inset ), when we fold, the existing creases will move to positions with double the index. So \begin_inset Formula $a_{2^{k}}\rightarrow a_{2^{k+1}}$ \end_inset . After \begin_inset Formula $n$ \end_inset folds, a crease \begin_inset Formula $a_{2^{k}}$ \end_inset was introduced \begin_inset Formula $k$ \end_inset folds ago. So, after only \begin_inset Formula $n-k$ \end_inset folds our crease would have been the first crease \begin_inset Formula $a_{0}$ \end_inset . From section \begin_inset LatexCommand \ref{sub:Folding-Operators} \end_inset , we know this would be same as the folding instruction used at that point, which is instruction \begin_inset Formula $i_{n-k}$ \end_inset . \layout Standard So the middle crease \begin_inset Formula $a_{2^{n}/2}=a_{2^{n-1}}=i_{n-(n-1)}=i_{1}$ \end_inset is the first fold, and the first crease \begin_inset Formula $a_{1}=a_{2^{0}}=i_{n-0}=i_{n}$ \end_inset is the latest fold, as expected. Now, all the creases introduced on fold \begin_inset Formula $k$ \end_inset will depend on instruction \begin_inset Formula $i_{k}$ \end_inset . These creases start with the one indexed by \begin_inset Formula $2^{k}$ \end_inset , and every \begin_inset Formula $2^{k+1}$ \end_inset th after that. These crease alternate \begin_inset Formula $(-1)^{j}$ \end_inset to the first. This is exactly what was described above in section \begin_inset LatexCommand \ref{sub:2-Automaton} \end_inset . Therefore: \begin_inset Formula \[ a_{2^{k}+j2^{k+1}}=(-1)^{j}i_{n-k}\] \end_inset \layout Standard With \begin_inset Formula $k=0,\ldots,n-1$ \end_inset and \begin_inset Formula $j=0,\ldots,2^{n-k-1}-1$ \end_inset . Also, given an arbitrary paperfolding sequence \begin_inset Formula $a_{0}a_{1}a_{2}a_{3}\cdots$ \end_inset we can determine the unfolding instructions by looking at the \begin_inset Formula $2^{k}$ \end_inset th terms, that is the unfolding instructions \begin_inset Formula $j_{0}j_{1}j_{2}j_{3}\cdots=a_{1}a_{2}a_{4}a_{8}\cdots$ \end_inset . \layout Subsection Tag Machine \layout Standard Consider an infinite tape, a reading head (that reads symbols from the tape), and a writing head (that writes symbols/words to the tape, according to rules, depending on what is read from the tape). The reading head moves along the tape, telling the writing head what to write down. The symbols written on the tape can then be converted to the paperfolding sequence (the symbols on the tape are not necessarily binary). \layout Standard Because of the properties described in section \begin_inset LatexCommand \ref{sub:Total-Number-of} \end_inset , it makes sense to start the tape off with 0 (or 1), and have the rules such that two symbols are written for each one read. That way, each iteration, when the machine reads the new symbols, the machine will write enough symbols to provide the next paperfolding sequence. Investigation shows that an alphabet of 4 for the symbols is appropriate: \layout Standard \begin_inset Float table placement H wide false collapsed true \layout Caption Tag Machine \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard a \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 01 \end_inset \begin_inset Text \layout Standard b \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard c \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 001 \end_inset \begin_inset Text \layout Standard 0011 \end_inset \begin_inset Text \layout Standard b \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard a \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard d \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard c \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0010011 \end_inset \begin_inset Text \layout Standard 00011011 \end_inset \begin_inset Text \layout Standard b \end_inset \begin_inset Text \layout Standard a \end_inset \begin_inset Text \layout Standard b \end_inset \begin_inset Text \layout Standard c \end_inset \begin_inset Text \layout Standard d \end_inset \begin_inset Text \layout Standard a \end_inset \begin_inset Text \layout Standard d \end_inset \begin_inset Text \layout Standard c \end_inset \end_inset \end_inset \layout Standard So the following rules control the tag machine: \layout Standard \begin_inset Formula $a\mapsto bc$ \end_inset , \begin_inset Formula $c\mapsto dc$ \end_inset , \begin_inset Formula $d\mapsto da$ \end_inset , \begin_inset Formula $b\mapsto ba$ \end_inset \newline With the change of symbols: \layout Standard \begin_inset Formula $a,b\mapsto0$ \end_inset , \begin_inset Formula $c,d\mapsto1$ \end_inset \newline to obtain the desired paperfolding sequence. \layout Subsection Substitution rules \layout Standard \begin_inset LatexCommand \label{sub:Substitution-rules} \end_inset This is a bit like the tag machine, but instead of extending the sequence with the new symbols, the new symbols \emph on are \emph default the next iteration of the sequence (note, this time iterations do not correspon d to folds). The paperfolding sequence is described by the function: \layout Standard \begin_inset Formula $a\mapsto ab$ \end_inset , \begin_inset Formula $b\mapsto cb$ \end_inset , \begin_inset Formula $c\mapsto ad$ \end_inset , \begin_inset Formula $d\mapsto cd$ \end_inset \layout Standard With the change of symbols: \layout Standard \begin_inset Formula $a,b\mapsto0$ \end_inset (valley), \begin_inset Formula $c,d\mapsto1$ \end_inset (hill) \layout Standard This is illustrated in table \begin_inset LatexCommand \ref{cap:Substitution-Rules} \end_inset : \begin_inset Float table placement h wide false collapsed true \layout Caption Substitution Rules \begin_inset LatexCommand \label{cap:Substitution-Rules} \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard iteration \end_inset \begin_inset Text \layout Standard symbols \end_inset \begin_inset Text \layout Standard transformation \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $a$ \end_inset \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $ab$ \end_inset \end_inset \begin_inset Text \layout Standard 00 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $abcd$ \end_inset \end_inset \begin_inset Text \layout Standard 0010 \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $abcbadcb$ \end_inset \end_inset \begin_inset Text \layout Standard 00100110 \end_inset \begin_inset Text \layout Standard 4 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $abcbadcbabcdadcb$ \end_inset \end_inset \begin_inset Text \layout Standard 0010011000110110 \end_inset \end_inset \end_inset \layout Standard As each substitution is of length 2, the substitution rules can be converted into a 2-automaton, as shown in figure \begin_inset LatexCommand \ref{cap:Alternative-2-Automaton} \end_inset : \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename /home/pumaman/math-project/figures/2automaton2.fig \end_inset \layout Caption Alternative 2-Automaton \begin_inset LatexCommand \label{cap:Alternative-2-Automaton} \end_inset \end_inset \layout Standard For example, the fifth value in the sequence is the \begin_inset Formula $101$ \end_inset st value in binary. Starting from the node marked \emph on a \emph default , and reading the binary instruction right-to-left, our instructions take us from \emph on a \emph default to \emph on b \emph default (1), from \emph on b \emph default to \emph on c \emph default (0) and finally from \emph on c \emph default to \emph on d \emph default (1). Since we end up at \emph on d \emph default , our transformation tells us that this is a hill. \layout Section Dragon Curves \layout Standard If we take our sequence of creases, and fold them at 90 degree angles, we find that certain patterns emerge. \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename /home/pumaman/math-project/figures/fold1dragon.fig \end_inset \layout Caption Folding paper into a dragon curve \end_inset \layout Standard In order to view the complex patters that emerge, we need to fold the paper many times over. By using the automata described in section \begin_inset LatexCommand \ref{sub:2-Automaton} \end_inset , we can write a computer program that will create the paperfolding creases. We can then write another program that will interpret this sequence of creases as instructions to turn left or right. \layout Subsection Fractals \layout Standard When we display the images formed, it is startling to see the fractals that are produced. \layout Standard \begin_inset Float figure placement H wide false collapsed true \layout Standard \begin_inset Graphics filename /home/pumaman/math-project/fractal.png \end_inset \layout Caption Fractal \begin_inset LatexCommand \label{cap:Fractal} \end_inset \end_inset \layout Subsubsection 1st Method for generating dragon curve \layout Standard The first method is to take our dragon curve, and to obtain the next iteration, `fold it' by inserting new corners between the existing ones. See figure \begin_inset LatexCommand \ref{cap:Dragon-Folding-1} \end_inset . \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename figures/dragon_folding.fig lyxscale 50 scale 50 \end_inset \layout Caption Dragon Folding 1 \begin_inset LatexCommand \label{cap:Dragon-Folding-1} \end_inset \end_inset \layout Standard We can see this more clearly by rotating the next iteration by \begin_inset Formula $\pi/2$ \end_inset , scaling by \begin_inset Formula $\sqrt{2}$ \end_inset , and overlaying it on top of the current iteration, as in figure \begin_inset LatexCommand \ref{cap:Dragon-Folding-2} \end_inset . \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename figures/dragon_folding2.fig lyxscale 50 scale 50 keepAspectRatio \end_inset \layout Caption Dragon Folding 2 \begin_inset LatexCommand \label{cap:Dragon-Folding-2} \end_inset \end_inset \layout Standard That is, the new curve alternates about the previous curve, with the initial new corner corresponding to the folding instruction. This is equivalent to the statement made in section \begin_inset LatexCommand \ref{sub:algoritm1} \end_inset . \layout Subsubsection 2nd Method for generating dragon curve \begin_inset LatexCommand \label{sub:dragon-fold-method-2} \end_inset \layout Standard One can also extend the dragon curve using the second method: make a copy of the curve, place it over the old one, and rotate at the end point by \begin_inset Formula $\pi/2$ \end_inset in the direction given by the unfolding instruction, see figure \begin_inset LatexCommand \ref{cap:Dragon-Folding-3} \end_inset . \begin_inset Float figure wide false collapsed true \layout Standard \begin_inset Graphics filename figures/dragon_folding3.fig lyxscale 50 scale 50 keepAspectRatio \end_inset \layout Caption \begin_inset LatexCommand \label{cap:Dragon-Folding-3} \end_inset Dragon Folding 3 \end_inset \layout Standard As per the properties of the paperfolding sequence detailed above, these two methods are equivalent. \layout Subsection Simple \layout Standard \begin_inset LatexCommand \label{sub:Simple} \end_inset All dragon curves are simple, that is they have no multiple edges, and are not closed. The proof of this is as follows: Let \begin_inset Formula $d(i)=(x_{i},y_{i})$ \end_inset be the coordinates of the \begin_inset Formula $i$ \end_inset -th corner (the start of the strip of paper is the \begin_inset Formula $0$ \end_inset -th corner). If the curve were not simple, then for some \begin_inset Formula $m,n\in\mathbb{Z}$ \end_inset (without loss of generality, let \begin_inset Formula $m \begin_inset Text \layout Standard year \end_inset \begin_inset Text \layout Standard sequence \end_inset \begin_inset Text \layout Standard number of rabbits \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $B$ \end_inset \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $A$ \end_inset \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $AB$ \end_inset \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $ABA$ \end_inset \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard 4 \end_inset \begin_inset Text \layout Standard \begin_inset Formula $ABAAB$ \end_inset \end_inset \begin_inset Text \layout Standard 5 \end_inset \end_inset \end_inset \layout Standard Note, the number of rabbits satisfies the recurrence relation \begin_inset Formula $f_{k}=f_{k-1}+f_{k-2}$ \end_inset as \begin_inset Formula $f_{k-2}$ \end_inset will give the number of adult rabbits in year \begin_inset Formula $k-1$ \end_inset , so the number this year ( \begin_inset Formula $k$ \end_inset ) will be the number last year plus the number of babies born to adult rabbits. \layout Standard So we can let the number of adults and number of babies in the sequence after \begin_inset Formula $k$ \end_inset iterations (years) be represented by the vector \begin_inset Formula $\left(\begin{array}{c} \textrm{number of adults}\\ \textrm{number of babies}\end{array}\right)_{k}=\left(\begin{array}{c} f_{k}\\ f_{k-1}\end{array}\right)$ \end_inset , and therefore the recurrence relation by: \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Formula $\left(\begin{array}{c} f_{k}\\ f_{k-1}\end{array}\right)$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)\left(\begin{array}{c} f_{k-1}\\ f_{k-2}\end{array}\right)$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)^{k-1}\left(\begin{array}{c} f_{1}\\ f_{0}\end{array}\right)$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \end_inset \end_inset \layout Standard The eigenvalues of the matrix \begin_inset Formula $\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)$ \end_inset are \begin_inset Formula $\frac{1\pm\sqrt{5}}{2}$ \end_inset . Note that \begin_inset Formula $\phi=\frac{1+\sqrt{5}}{2}$ \end_inset is the golden ratio. \layout Standard Assume \begin_inset Formula $f_{k}/f_{k-1}$ \end_inset tends to a limit, i.e. \begin_inset Formula $\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)\left(\begin{array}{c} f_{k-1}\\ f_{k-2}\end{array}\right)=\left(\begin{array}{c} f_{k}\\ f_{k-1}\end{array}\right)=\lambda\left(\begin{array}{c} f_{k-1}\\ f_{k-2}\end{array}\right)$ \end_inset . Obviously \begin_inset Formula $\phi$ \end_inset is an eigenvalue of the matrix, and as the Fibonacci sequence is positive, \begin_inset Formula $\lim_{k\rightarrow\infty}f_{k}/f_{k-1}=\frac{1+\sqrt{5}}{2}=\phi$ \end_inset , i.e. the golden ratio. \layout Standard Also, note that the Fibonacci sequence is a sturmian sequence with \begin_inset Formula $\alpha=\phi-1=\frac{\sqrt{5}-1}{2}$ \end_inset and \begin_inset Formula $\beta=0$ \end_inset . \layout Subsection Rudin-Shapiro \begin_inset LatexCommand \label{sub:Rubin-shapiro} \end_inset \layout Standard The Rudin-Shapiro sequence gives the parity of the number of \begin_inset Formula $11$ \end_inset blocks in a binary number. For example (if we want the sequence given using \begin_inset Formula $\{0,1\}$ \end_inset ), the \begin_inset Formula $27$ \end_inset th term, which is \begin_inset Formula $11011$ \end_inset in binary, has two \begin_inset Formula $11$ \end_inset s in it, so has a value of \begin_inset Formula $0$ \end_inset in the sequence. On the other hand \begin_inset Formula $26$ \end_inset is \begin_inset Formula $11010$ \end_inset in binary, has one \begin_inset Formula $11$ \end_inset , so has a value of \begin_inset Formula $1$ \end_inset . See table \begin_inset LatexCommand \ref{cap:Rudin-Shapiro} \end_inset . \begin_inset Float table placement h wide false collapsed true \layout Caption Rudin-Shapiro \begin_inset LatexCommand \label{cap:Rudin-Shapiro} \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard term in sequence \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 3 \end_inset \begin_inset Text \layout Standard 4 \end_inset \begin_inset Text \layout Standard 5 \end_inset \begin_inset Text \layout Standard 6 \end_inset \begin_inset Text \layout Standard 7 \end_inset \begin_inset Text \layout Standard 8 \end_inset \begin_inset Text \layout Standard 9 \end_inset \begin_inset Text \layout Standard 10 \end_inset \begin_inset Text \layout Standard in binary \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 10 \end_inset \begin_inset Text \layout Standard 11 \end_inset \begin_inset Text \layout Standard 100 \end_inset \begin_inset Text \layout Standard 101 \end_inset \begin_inset Text \layout Standard 110 \end_inset \begin_inset Text \layout Standard 111 \end_inset \begin_inset Text \layout Standard 1000 \end_inset \begin_inset Text \layout Standard 1001 \end_inset \begin_inset Text \layout Standard 1010 \end_inset \begin_inset Text \layout Standard number of \begin_inset Formula $11$ \end_inset s \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 2 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard modulo 2 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard sequence in \begin_inset Formula $\{-1,+1\}$ \end_inset \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \end_inset \end_inset \layout Standard The last row in this table is the Rudin-Shapiro sequence. It can also be built up by alternating self addition, see table \begin_inset LatexCommand \ref{cap:Rudin-Shapiro-2} \end_inset for an illustration (this time using \begin_inset Formula $\{1,-1\}$ \end_inset as the alphabet for the sequence): \begin_inset Float table placement h wide false collapsed true \layout Caption Rudin-Shapiro 2 \begin_inset LatexCommand \label{cap:Rudin-Shapiro-2} \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard Rudin-Shapiro sequence \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard alternating self addition \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard -(1) \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard -(-1) \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard -(1) \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard the Rudin-Shapiro sequence again! \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \end_inset \end_inset \layout Standard This is summarised in the following recurrence relation, where \begin_inset Formula $r_{k}\in\{-1,1\}$ \end_inset is the \begin_inset Formula $k$ \end_inset th term in the sequence, \begin_inset Formula $k\geq0$ \end_inset : \layout Standard \begin_inset Formula $r_{0}=1$ \end_inset \layout Standard \begin_inset Formula $r_{2k}=r_{k}$ \end_inset (first line of table \begin_inset LatexCommand \ref{cap:Rudin-Shapiro-2} \end_inset ) Note, this also means that \begin_inset Formula $r_{2^{n}}=r_{0}$ \end_inset for \begin_inset Formula $n\geq0$ \end_inset . \layout Standard \begin_inset Formula $r_{2k+1}=(-1)^{k}r_{k}$ \end_inset (second line of table \begin_inset LatexCommand \ref{cap:Rudin-Shapiro-2} \end_inset ) \layout Standard This is expressed in the functional equation (for the infinite sequence), where \begin_inset Formula $R(x)=\sum_{k=0}^{\infty}r_{k}x^{k}$ \end_inset , \layout Standard \begin_inset Formula \[ R(x)=R(x^{2})+xR(-x^{2})\] \end_inset \layout Standard Or, for the \begin_inset Formula $n$ \end_inset th iteration, where \begin_inset Formula $R_{n}(x)=\sum_{k=0}^{2^{n}-1}r_{k}x^{k}$ \end_inset , we have the recurrence relation \layout Standard \begin_inset Formula \[ R_{n+1}(x)=R_{n}(x^{2})+xR_{n}(-x^{2})\] \end_inset \layout Subsubsection Automation \layout Standard This sequence is described by the substitution rules in a similar way to section \begin_inset LatexCommand \ref{sub:Substitution-rules} \end_inset . The rules are \begin_inset LatexCommand \cite{quantum} \end_inset : \layout Standard \begin_inset Formula $a\mapsto ab$ \end_inset , \begin_inset Formula $b\mapsto ac$ \end_inset , \begin_inset Formula $c\mapsto db$ \end_inset , \begin_inset Formula $d\mapsto dc$ \end_inset \layout Standard With the change of symbols: \layout Standard \begin_inset Formula $a,b\mapsto0$ \end_inset (or \begin_inset Formula $1$ \end_inset ), \begin_inset Formula $c,d\mapsto1$ \end_inset (or \begin_inset Formula $-1$ \end_inset ) \layout Standard This has the equivalent automaton shown in figure : \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename /home/pumaman/math-project/figures/2automaton3.fig \end_inset \layout Caption Rudin-Shapiro 2-Automaton \end_inset \layout Subsubsection Properties \layout Standard Consider the exponential sum and the integral \begin_inset Formula \[ \sum_{k=0}^{n-1}\pm e^{ik\theta}\] \end_inset \begin_inset Formula \[ \int_{0}^{2\pi}\left|\sum_{k=0}^{n-1}\pm e^{ik\theta}\right|^{2}d\theta=n\] \end_inset \layout Standard regardless of the choice of sign \begin_inset Formula $\pm$ \end_inset . It then follows that \begin_inset Formula \[ \sup_{0\leq\theta\leq2\pi}\left|\sum_{k=0}^{n-1}\pm e^{ik\theta}\right|\geq\sqrt{n}\] \end_inset \layout Standard One of the properties of the Rudin-Shapiro sequence \begin_inset Formula $\{ r_{k}\}$ \end_inset is that for all \begin_inset Formula $n$ \end_inset (using the alphabet \begin_inset Formula $r_{k}\in\{-1,1\}$ \end_inset ) \begin_inset LatexCommand \cite{folds} \end_inset \begin_inset Formula \[ \sup_{0\leq\theta\leq2\pi}\left|\sum_{k=0}^{n-1}r_{k}e^{ik\theta}\right|\leq(2+\sqrt{2})\sqrt{n}\] \end_inset \layout Section More on Dragon Curves \layout Subsection Space filling \layout Standard \begin_inset LatexCommand \label{sub:Space-filling} \end_inset In section \begin_inset LatexCommand \ref{Observation-space-filling} \end_inset we observed that dragon curves somehow fill out an area of the plane. We will now formalise this concept. A normal curve should be one-dimensional, but our dragon curves will, with a suitable definition of dimension, turn out to be two-dimensional. \layout Standard Given a curve \begin_inset Formula $\Gamma$ \end_inset , let the set \begin_inset Formula $\Gamma(\epsilon)=\left\{ y\,:\, distance(y,x)<\epsilon;\forall x\in\Gamma\right\} $ \end_inset . This is giving our curve \begin_inset Formula $\Gamma$ \end_inset some \emph on thickness \emph default \begin_inset Formula $\epsilon$ \end_inset - see figure \begin_inset LatexCommand \ref{cap:Epsilonised-peano-curve} \end_inset . \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename /home/pumaman/math-project/figures/peanoepsilon.fig \end_inset \layout Caption Epsilonised Peano curve \begin_inset LatexCommand \label{cap:Epsilonised-peano-curve} \end_inset \end_inset \layout Standard We will actually consider the limit where \begin_inset Formula $\Gamma$ \end_inset is infinitely long (i.e. is an infinite paperfolding curve). Now also consider the area common to \begin_inset Formula $\Gamma(\epsilon)$ \end_inset and a disk (centered at the origin) of radius \begin_inset Formula $R$ \end_inset , and call it \begin_inset Formula $\Gamma(\epsilon;R)$ \end_inset . Then we can define our dimension as: \begin_inset Formula \[ \textrm{dim}\,\Gamma(\epsilon,R)=\frac{\log\Gamma(\epsilon;R)}{\log R}\] \end_inset \layout Standard where \begin_inset Formula $\log$ \end_inset is the natural logarithm, and we take the limits \begin_inset Formula $\lim_{R\rightarrow\infty}$ \end_inset and \begin_inset Formula $\lim\epsilon\rightarrow0$ \end_inset . This equation can be rearranged as \begin_inset Formula $\Gamma(\epsilon;R)=R^{\textrm{dim}\,\Gamma}$ \end_inset . This would indicate that \begin_inset Formula $1\leq\textrm{dim}\,\Gamma\leq2$ \end_inset as the common area would be between \begin_inset Formula $R^{1}$ \end_inset and \begin_inset Formula $R^{2}$ \end_inset . For a simple line, \begin_inset Formula $\Gamma(\epsilon;R)\approx R$ \end_inset , so the dimension would be 1. We will now show that the dimension for a dragon curve is 2. \layout Standard First we must consider the dragon curve lying in the complex plane, with the \begin_inset Formula $k$ \end_inset th corner having coordinates \begin_inset Formula $z_{k}=x_{k}+iy_{k}$ \end_inset (let \begin_inset Formula $z_{0}=0$ \end_inset and \begin_inset Formula $z_{1}=1$ \end_inset ). We will now split the turning instructions into a pair of sequences describing the horizontal and vertical moves . This is done by keeping track of the cumulative difference in instructions to turn left and to turn right. If the paperfolding sequence uses the alphabet \begin_inset Formula $\{-1,+1\}$ \end_inset then the count, \begin_inset Formula $c_{k}=\sum_{j=0}^{k}crease_{j}$ \end_inset . The even counts \begin_inset Formula $c_{2k}$ \end_inset define the horizontal movements and the odd counts \begin_inset Formula $c_{2k+1}$ \end_inset describe the vertical movements. The count is useful as it can be decoded as follows: \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Formula $c_{2k}\equiv0\textrm{mod}4$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\rightarrow$ \end_inset instruction to move right \end_inset \begin_inset Text \layout Standard \begin_inset Formula $c_{2k}\equiv2\textrm{mod}4$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\leftarrow$ \end_inset instruction to move left \end_inset \begin_inset Text \layout Standard \begin_inset Formula $c_{2k+1}\equiv1\textrm{mod}4$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\uparrow$ \end_inset instruction to move up \end_inset \begin_inset Text \layout Standard \begin_inset Formula $c_{2k+1}\equiv3\textrm{mod}4$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\downarrow$ \end_inset instruction to move down \end_inset \end_inset \layout Standard Table \begin_inset LatexCommand \ref{cap:Count} \end_inset shows how the count is calculated, and how it is decoded into the directions of each segment of the dragon curve. Note, the first segment is set to be \begin_inset Formula $\rightarrow$ \end_inset . The table also shows what happens when we represent the the horizontal and vertical movements by the numbers \begin_inset Formula $0\equiv\rightarrow\equiv\downarrow$ \end_inset and \begin_inset Formula $1\equiv\leftarrow\equiv\uparrow$ \end_inset respectively. \begin_inset Float table placement h wide false collapsed true \layout Caption Count \begin_inset LatexCommand \label{cap:Count} \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard sequence \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard +1 \end_inset \begin_inset Text \layout Standard +1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard +1 \end_inset \begin_inset Text \layout Standard +1 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard +1 \end_inset \begin_inset Text \layout Standard +1 \end_inset \begin_inset Text \layout Standard count \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard -2 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard -1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\rightarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\downarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\rightarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\uparrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\rightarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\downarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\leftarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\downarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\rightarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\downarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\rightarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\uparrow$ \end_inset \end_inset \begin_inset Text \layout Standard horizontal \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard vertical \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard combined \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 0 \end_inset \begin_inset Text \layout Standard 1 \end_inset \end_inset \end_inset \layout Standard It is interesting to note that the combined sequence is the Rudin-Shapiro sequence as described in section \begin_inset LatexCommand \ref{sub:Rubin-shapiro} \end_inset . Even more interestingly, if we let \begin_inset Formula $\rightarrow=A$ \end_inset , \begin_inset Formula $\downarrow=B$ \end_inset , \begin_inset Formula $\uparrow=C$ \end_inset and \begin_inset Formula $\leftarrow=D$ \end_inset then we have the Rudin-Shapiro sequence as generated by its substitution rules (i.e. before the change of symbols). \layout Standard We can now define the direction function \begin_inset Formula $D(x)$ \end_inset , the functional equation with real coefficients describing the horizontal movements, and imaginary ones describing the vertical movements. If the \begin_inset Formula $k$ \end_inset th horizontal move and \begin_inset Formula $k$ \end_inset th vertical moves are described by \begin_inset Formula $h_{k},v_{k}\in\{0,1\}$ \end_inset respectively, then the count can be decoded by \begin_inset Formula $i^{c_{2k}}=(-1)^{h_{k}}$ \end_inset and \begin_inset Formula $i^{c_{2k+1}}=-i(-1)^{v_{k}}$ \end_inset . The direction function is then: \layout Standard \begin_inset Formula \[ D(x)=\sum_{k\geq0}i^{c_{k}}x^{k}=\sum_{k\geq0}(-1)^{h_{k}}x^{2k}-i\sum_{k\geq0}(-1)^{v_{k}}x^{2k+1}\] \end_inset \layout Standard So, from the example in table \begin_inset LatexCommand \ref{cap:Count} \end_inset , \begin_inset Formula $D(x)=1-ix+x^{2}+ix^{3}+x^{4}-ix^{5}-x^{6}-\ldots$ \end_inset . Now, if given a paper folding sequence defined by the folding instructions \begin_inset Formula $(\epsilon_{1},\epsilon_{2},\ldots,\epsilon_{n})$ \end_inset , where \begin_inset Formula $\epsilon_{j}\in\{-1,+1\}$ \end_inset and \begin_inset Formula $\epsilon_{n}$ \end_inset was the first folding instruction (or last unfolding instruction), and produces a sequence of length \begin_inset Formula $2^{n}-1$ \end_inset . This sequence is made up of the previous sequence repeated and folded about \begin_inset Formula $\epsilon_{1}$ \end_inset (see section \begin_inset LatexCommand \ref{sub:dragon-fold-method-2} \end_inset ). The reverse of this is a matter of cutting the paper in half (at fold \begin_inset Formula $\epsilon_{1}$ \end_inset ), thus loosing the first folding instruction. the second half of the paper is the mirror image of the first, so its central fold is the reverse of the one in the first half. So the first half of the sequence given by instructions \begin_inset Formula $(\epsilon_{1},\epsilon_{2},\ldots,\epsilon_{n})$ \end_inset is given by \begin_inset Formula $(\epsilon_{2},\ldots,\epsilon_{n})$ \end_inset , and the second half by \begin_inset Formula $(-\epsilon_{2},\ldots,\epsilon_{n})$ \end_inset . Each of these halves is a sequence of length \begin_inset Formula $2^{n-1}-1$ \end_inset . So we can write the following recurrence relation for the \begin_inset Formula $D(x)$ \end_inset functional equation. \layout Standard \begin_inset Formula \[ D(\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n};x)=D(\epsilon_{2},\dots,\epsilon_{n};x)+i^{\epsilon_{1}+\epsilon_{2}}x^{2^{n-1}}D(-\epsilon_{2},\dots,\epsilon_{n};x)\] \end_inset \layout Standard With \begin_inset Formula $D(\epsilon_{n};x)=1+i^{\epsilon_{n}}x$ \end_inset (and \begin_inset Formula $D(\emptyset;x)=1$ \end_inset ). Note the orientation of the second half is determined by a rotation \begin_inset Formula $i^{c_{2^{n-1}}}=i^{\epsilon_{1}+\epsilon_{2}}$ \end_inset . So \begin_inset Formula $\epsilon_{1}+\epsilon_{2}=c_{2^{n-1}}$ \end_inset . It is interesting to note that we can draw dragon curves with angles other than \begin_inset Formula $\pi/2\rightarrow e^{i\pi/2}=i$ \end_inset by replacing \begin_inset Formula $i$ \end_inset in the equation with \begin_inset Formula $e^{i\theta}$ \end_inset , where \begin_inset Formula $\theta$ \end_inset is the angle. \layout Standard The functional equation can represented by the matrix identity: \layout Standard \begin_inset Formula \[ \left(\begin{array}{c} D(\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n};z)\\ D(-\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n};z)\end{array}\right)=\left(\begin{array}{cc} 1 & i^{\epsilon_{1}+\epsilon_{2}}z^{2^{n-1}}\\ 1 & -i^{\epsilon_{1}+\epsilon_{2}}z^{2^{n-1}}\end{array}\right)\times\left(\begin{array}{c} D(\epsilon_{2},\dots,\epsilon_{n};z)\\ D(-\epsilon_{2},\dots,\epsilon_{n};z)\end{array}\right)\] \end_inset \layout Standard By repeatedly halving, we get the identity: \layout Standard \begin_inset Formula \[ \left(\begin{array}{c} D(\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n};z)\\ D(-\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n};z)\end{array}\right)=\prod_{k=1}^{n-1}\left(\begin{array}{cc} 1 & i^{\epsilon_{n-k}+\epsilon_{n-k-1}}z^{2^{k}}\\ 1 & -i^{\epsilon_{n-k}+\epsilon_{n-k-1}}z^{2^{k}}\end{array}\right)\times\left(\begin{array}{c} 1+i^{\epsilon_{n}}\\ 1-i^{\epsilon_{n}}\end{array}\right)\] \end_inset \layout Standard By setting \begin_inset Formula $\left|z\right|=1$ \end_inset , so that \begin_inset Formula $D(z)$ \end_inset gives the complex position of the end of the dragon curve, the norm of the matrix operators on the right are \begin_inset Formula $\sqrt{2}$ \end_inset , so the norm \begin_inset Formula $\left|D(\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n};z)\right|\leq\sqrt{2}^{n}=2^{n/2}$ \end_inset . So, the end of the dragon curve is less than or equal to \begin_inset Formula $\sqrt{2}^{n}$ \end_inset from the origin. Now, if we go back to our definition of dimension \begin_inset Formula $\textrm{dim}\,\Gamma(\epsilon,R)=\ln\Gamma(\epsilon;R)/\ln R$ \end_inset , we have \begin_inset Formula $R=2^{n/2}$ \end_inset , and \begin_inset Formula $\Gamma(\epsilon;R)=2^{n}$ \end_inset as there are \begin_inset Formula $2^{n}$ \end_inset line segments of length \begin_inset Formula $1$ \end_inset (since there are \begin_inset Formula $2^{n}-1$ \end_inset creases) in the circle of radius \begin_inset Formula $R$ \end_inset . So \begin_inset Formula $\textrm{dim}\,\Gamma(\epsilon,R)=\ln2^{n}/\ln2^{n/2}=2\ln2^{n}/\ln2^{n}=2$ \end_inset , the dimension of a dragon curve is 2, as desired. \layout Subsection Dimension \layout Standard Mandelbrot defined a fractal to be a set with Hausdorff dimension strictly exceeding the topological dimension. This definition is the generally accepted one, though it does fail in some cases with sets that we would like to be included as a fractal. \layout Standard Normally dimension would just mean: zero dimensional points; one dimensional lines; two dimensional shapes; three dimensional object etc. It is defined iteratively, that is a three dimensional space is contained in a two dimensional surface; a two dimensional shape is contained in by a one dimensional boundary etc. Other definitions of dimension, however, can have non-integer values. The motivation for this is seen, for example, if we take the boundary of our dragon fractal. It is not one-dimensional as if we measure the length of the boundary it is infinite, but it is nether two-dimensional as if we measure the area of the boundary, it is zero! Compare this, say, with a square. It has a one dimensional boundary as we can measure its length easily enough (but one would not measure the area of the boundary). Thus, as we will soon find, the boundary of the dragon curve has a dimension somewhere between one and two. \layout Standard First one must define an iterated function system. If in a metric space \begin_inset Formula $S$ \end_inset we have a list of functions \begin_inset Formula $(f_{1},f_{2},\cdots,f_{n})$ \end_inset , associated with a ratio list \begin_inset Formula $(r_{1},r_{2},\cdots,r_{n})$ \end_inset , with \begin_inset Formula $f_{i}:S\rightarrow S$ \end_inset , and each \begin_inset Formula $f_{i}$ \end_inset has a similarity ratio \begin_inset Formula $r_{i}$ \end_inset , a non-empty set \begin_inset Formula $K\subseteq S$ \end_inset is an invariant set for the iterated function system iff \begin_inset Formula $K=f_{1}[K]\cup f_{2}[K]\cup\cdots\cup f_{n}[K]$ \end_inset . These iterated function systems can be represented using Maudlin-Williams graphs, which show how the functions act, and the edges are labeled with the similarity ratio. The graph is made up of a set of vertices \begin_inset Formula $V$ \end_inset , with directed edges \begin_inset Formula $E$ \end_inset joining pairs of vertices. Each function is associated with each edge, and the edge is labeled by the appropriate ratio. \layout Standard For example, a square's graph would look like figure \begin_inset LatexCommand \ref{fig:Mauldin-Williams-square} \end_inset . It is made up of four functions, each of which produce a square \begin_inset Formula $\frac{1}{2}$ \end_inset the size of the original. For the dragon curve, it has two functions, each of which is made up of a dragon curve \begin_inset Formula $\frac{1}{\sqrt{2}}$ \end_inset the size of the original. \layout Standard \begin_inset Float figure wide false collapsed true \layout Standard \begin_inset Graphics filename figures/simple_Mauldin-Williams.fig \end_inset \layout Caption \begin_inset LatexCommand \label{fig:Mauldin-Williams-square} \end_inset Maudlin-Williams graph for a square \end_inset \layout Subsubsection Similarity Dimension \layout Standard One of the simplest dimensions to understand is the similarity dimension. It is defined as the (unique) number \begin_inset Formula $s>0$ \end_inset such that \begin_inset Formula $\sum_{i=1}^{n}r_{i}^{s}=1$ \end_inset is satisfied. \layout Standard For the square we need to solve \begin_inset Formula $4(\frac{1}{2})^{s}=1$ \end_inset , which gives \begin_inset Formula $s=\frac{\log4}{\log2}=2$ \end_inset , as expected for a two-dimensional shape. For the (interior) of the dragon fractal we need to solve \begin_inset Formula $2(\frac{1}{\sqrt{2}})^{s}=1$ \end_inset , which gives \begin_inset Formula $s=\frac{\log2}{\log\sqrt{2}}=2$ \end_inset . This agrees with section \begin_inset LatexCommand \ref{sub:Space-filling} \end_inset . \layout Subsubsection Boundary of Dragon Curve \layout Standard \begin_inset LatexCommand \label{sub:Boundary-of-Dragon} \end_inset While the interior of the dragon curve is an area, the boundary of the curve is a fractal. It is drawn using an iterated function system. Figure \begin_inset LatexCommand \ref{fig:Fractle-Boundary} \end_inset shows how the system will have to work. \layout Standard \begin_inset Float figure wide false collapsed true \layout Standard \begin_inset Graphics filename figures/fractal_boundary.eps \end_inset \layout Caption \begin_inset LatexCommand \label{fig:Fractle-Boundary} \end_inset Fractal Boundary \end_inset \layout Standard The curve is made up of two parts: \begin_inset Formula $A$ \end_inset and \begin_inset Formula $B$ \end_inset . \begin_inset Formula $A$ \end_inset is made up of an \begin_inset Formula $A$ \end_inset and a \begin_inset Formula $B$ \end_inset , each shrunk by a factor of \begin_inset Formula $\sqrt{2}$ \end_inset . \begin_inset Formula $B$ \end_inset is made up of two copies of \begin_inset Formula $A$ \end_inset , each shrunk by a factor of \begin_inset Formula $2$ \end_inset , but with one \begin_inset Formula $A$ \end_inset turned upside down. The iterated function system is defined by four functions \begin_inset Formula $f_{1}:A\rightarrow A$ \end_inset , \begin_inset Formula $f_{2}:A\rightarrow B$ \end_inset , \begin_inset Formula $f_{3}:B\rightarrow A$ \end_inset and \begin_inset Formula $f_{4}:B\rightarrow A$ \end_inset . This is summarised in the Maudlin-Williams graph as shown in figure \begin_inset LatexCommand \ref{graph:Mauldin-Williams-Graph} \end_inset . Note that each edge is labeled with the factor by which \begin_inset Formula $f_{i}$ \end_inset scales by. \layout Standard \begin_inset Float figure wide false collapsed true \layout Standard \begin_inset Graphics filename figures/Mauldin-Williams.fig \end_inset \layout Caption \begin_inset LatexCommand \label{graph:Mauldin-Williams-Graph} \end_inset Maudlin-Williams Graph \end_inset \layout Standard So, the similarity dimension is found found by solving \begin_inset Formula $1=2\left(\frac{1}{\sqrt{2}}\right)^{s}+2\left(\frac{1}{2}\right)^{s}$ \end_inset . We can do this if we let \begin_inset Formula $x=\left(\frac{1}{\sqrt{2}}\right)^{s}$ \end_inset , and solving for positive \begin_inset Formula $x$ \end_inset . Then the equation becomes \begin_inset Formula $\frac{1}{2}=x+x^{2}$ \end_inset , which gives \begin_inset Formula $x=\frac{\sqrt{3}-1}{2}$ \end_inset and so \begin_inset Formula $s=-\frac{\log x}{\log\sqrt{2}}=2.900$ \end_inset . \layout Subsubsection Perron Number \layout Standard To find the Hausdorff dimension of the boundary of the dragon curve, first we must calculate the Perron number. It is defined as follows: if \begin_inset Formula $s$ \end_inset is a positive real number, then \begin_inset Formula $s-$ \end_inset dimensional Perron numbers for the graph are positive numbers \begin_inset Formula $q_{v}$ \end_inset (for each vertice \begin_inset Formula $v$ \end_inset in the graph) such that \begin_inset Formula \[ q_{u}^{s}=\sum_{\begin{array}{c} v\in V\\ e\in E_{uv}\end{array}}r_{e}^{s}q_{v}^{s}\] \end_inset \layout Standard Thus for our square we need to solve \begin_inset Formula $q^{s}=4\times(\frac{1}{2}\times q)^{s}$ \end_inset . If we let \begin_inset Formula $q=1$ \end_inset , we have \begin_inset Formula $1=\frac{4}{2^{s}}$ \end_inset which is solved to give dimension \begin_inset Formula $s=\frac{\ln4}{\ln2}=2$ \end_inset . For the dragon curve boundary we need to solve the equations \begin_inset Formula \[ q_{A}^{s}=\left(\frac{1}{\sqrt{2}}\right)^{s}q_{A}^{s}+\left(\frac{1}{\sqrt{2}}\right)^{s}q_{B}^{s}\] \end_inset \begin_inset Formula \[ q_{B}^{s}=2\left(\frac{1}{2}\right)^{s}q_{A}^{s}\] \end_inset \layout Standard This is done, like for the similarity dimension, by letting \begin_inset Formula $\lambda=\sqrt{2}^{s}$ \end_inset , \begin_inset Formula $x=q_{A}^{s}$ \end_inset and \begin_inset Formula $y=q_{B}^{s}$ \end_inset . Then the equations become \begin_inset Formula $x=\frac{x+y}{\lambda}$ \end_inset , \begin_inset Formula $y=2\frac{x}{\lambda^{2}}$ \end_inset . If we let \begin_inset Formula $y=1$ \end_inset we have \begin_inset Formula $x(1-\lambda)+1=0$ \end_inset and \begin_inset Formula $2x=\lambda^{2}$ \end_inset . Combining these gives \begin_inset Formula $\lambda^{2}(1-\lambda)+2=0\Rightarrow\lambda^{3}-\lambda^{2}-2=0$ \end_inset . The positive root of this equation \begin_inset Foot collapsed true \layout Standard Calculated using the Newtonian method. That is the roots of \begin_inset Formula $f(x)=0$ \end_inset can be found by setting \begin_inset Formula $x_{n+1}=x_{n}-\frac{f(x)}{f'(x)}$ \end_inset . \end_inset is \begin_inset Formula $\lambda=1.69562$ \end_inset . So \begin_inset Formula $s=\frac{\ln\lambda}{\ln\sqrt{2}}=1.52363\approx1.52$ \end_inset . This is between 1 and 2 as expected - the length of the boundary is infinite, but it has zero area, so the dimension must be \begin_inset Formula $\geq1$ \end_inset but \begin_inset Formula $\leq2$ \end_inset \layout Subsubsection Hausdorff Dimension \layout Standard The Hausdorff dimension is defined as follows: If \begin_inset Formula $U$ \end_inset is a non-empty subset of \begin_inset Formula $\mathbb{R}^{n}$ \end_inset , the diameter of \begin_inset Formula $U$ \end_inset is defined as \begin_inset Formula $\left|U\right|=\sup\left\{ \left|x-y\right|:x,y\in U\right\} $ \end_inset , that is the furthest distance between any two points in \begin_inset Formula $U$ \end_inset . If \begin_inset Formula $\{ U_{i}\}$ \end_inset is a countable collection of sets of diameter \begin_inset Formula $|U_{i}|\leq\delta$ \end_inset that cover \begin_inset Formula $F$ \end_inset (that is \begin_inset Formula $F\subset\bigcup_{i}U_{i}$ \end_inset ) and we say that \begin_inset Formula $\{ U_{i}\}$ \end_inset is a \begin_inset Formula $\delta$ \end_inset -cover of \begin_inset Formula $F$ \end_inset . Suppose \begin_inset Formula $F\subset\mathbb{R}^{n}$ \end_inset and \begin_inset Formula $s$ \end_inset a non-negative number. For any \begin_inset Formula $\delta>0$ \end_inset with \begin_inset Formula $\left\{ U_{i}\right\} $ \end_inset as a \begin_inset Formula $\delta$ \end_inset -cover for \begin_inset Formula $F$ \end_inset define \begin_inset Formula \[ \mathcal{H}_{\delta}^{s}(F)=\inf\left\{ \sum_{i}\left|U_{i}\right|^{s}\right\} \] \end_inset \layout Standard Then take the limit \begin_inset Formula $\mathcal{H}^{s}(F)=\lim_{\delta\rightarrow0}\mathcal{H}_{\delta}^{s}(F)$ \end_inset . The Hausdorff dimension \begin_inset Formula $s$ \end_inset is the value for for which \begin_inset Formula \[ \mathcal{H}^{s'}(F)=\{\begin{array}{ccc} \infty & \, & s'>s\\ 0 & \, & s' \begin_inset Text \layout Standard \begin_inset Formula $\left[c_{0},\overrightarrow{w},x-\frac{q_{n-1}}{q_{n}}\right]$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\leftrightarrow\left(\begin{array}{cc} p_{n} & p_{n-1}\\ q_{n} & q_{n-1}\end{array}\right)\left(\begin{array}{cc} x-\frac{q_{n-1}}{q_{n}} & 1\\ 1 & 0\end{array}\right)$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\left(\begin{array}{cc} xp_{n}-\left(p_{n}q_{n-1}-p_{n-1}q_{n}\right)/q_{n} & p_{n}\\ xq_{n} & q_{n}\end{array}\right)$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\left(\begin{array}{cc} xp_{n}-\left(-1\right)^{n+1}/q_{n} & p_{n}\\ xq_{n} & q_{n}\end{array}\right)$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\leftrightarrow\frac{xp_{n}+\left(-1\right)^{n}/q_{n}}{xq_{n}}$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\frac{p_{n}}{q_{n}}+\frac{\left(-1\right)^{n}}{xq_{n}^{2}}$ \end_inset \end_inset \end_inset \layout Standard But \begin_inset Formula $x-\frac{q_{n-1}}{q_{n}}=x-\frac{1}{q_{n}/q_{n-1}}=\left[x,-\overleftarrow{w}\right].$ \end_inset So \begin_inset Formula \[ \left[c_{0},\overrightarrow{w},x-\frac{q_{n-1}}{q_{n}}\right]=\left[c_{0},\overrightarrow{w},x,-\overleftarrow{w}\right]=\frac{p_{n}}{q_{n}}+\frac{\left(-1\right)^{n}}{xq_{n}^{2}}\] \end_inset \layout Standard Note that \begin_inset Formula $\overrightarrow{w},x,-\overleftarrow{w}$ \end_inset reminds us of our folding operation (see section \begin_inset LatexCommand \ref{sub:algoritm2} \end_inset ). \layout Subsection Paperfolding \layout Standard It is not generally easy to find a continued fraction representation of any number, but there are some (infinitely many, but not all of \begin_inset Formula $\mathbb{R}$ \end_inset ) that, with the help of our beloved paperfolding sequence, we can. Proposition, if we have the paperfolding instructions \begin_inset Formula $\epsilon_{0}\epsilon_{1}\epsilon_{2}\cdots$ \end_inset ( \begin_inset Formula $\epsilon_{k}\in\{-1,+1\}$ \end_inset ), then any number of the form \begin_inset Formula $x\sum_{k=0}^{n}\epsilon_{k}x^{-2^{k}}$ \end_inset has the continued fraction expansion \begin_inset Formula \[ x\sum_{k=0}^{n}\epsilon_{k}x^{-2^{k}}=\left[\epsilon_{0},T_{-\epsilon_{n}x}\cdots T_{-\epsilon_{3}x}\circ T_{-\epsilon_{2}x}(\epsilon_{1}x)\right]\] \end_inset \layout Standard For \begin_inset Formula $n=1,3,4,\cdots$ \end_inset and where \begin_inset Formula $T_{i}$ \end_inset is similar to our folding operation defined in section \begin_inset LatexCommand \ref{sub:algoritm2} \end_inset , and is defined as \begin_inset Formula $T_{\overrightarrow{p}}(\overrightarrow{w})=\overrightarrow{w},\overrightarrow{p},-\overrightarrow{w}$ \end_inset . For example \begin_inset Formula $T_{-\epsilon_{2}x}(\epsilon_{1}x)=\epsilon_{1}x,-\epsilon_{2}x,-\epsilon_{1}x$ \end_inset . \layout Standard Our proof is by induction. First we show it is true for \begin_inset Formula $n=1$ \end_inset . For LHS we have \begin_inset Formula \[ x\sum_{k=0}^{1}\epsilon_{k}x^{-2^{k}}=\epsilon_{0}+\frac{\epsilon_{1}}{x}=[\epsilon_{0},\frac{x}{\epsilon_{1}}]=[\epsilon_{0},\epsilon_{1}x]\] \end_inset \layout Standard ( \begin_inset Formula $1/\epsilon_{k}=\epsilon_{k}$ \end_inset as \begin_inset Formula $\epsilon_{k}\in\{-1,+1\}$ \end_inset ). RHS is \begin_inset Formula $\left[\epsilon_{0},\epsilon_{1}x\right]$ \end_inset so our proposition is true for \begin_inset Formula $n=1$ \end_inset . Also \begin_inset Formula $[\epsilon_{0},\epsilon_{1}x]=p_{1}/q_{1}$ \end_inset ( \begin_inset Formula $p_{i}$ \end_inset , \begin_inset Formula $q_{i}$ \end_inset \begin_inset Formula $\in\mathbb{Z}$ \end_inset ). Let \begin_inset Formula $q_{1}=x$ \end_inset . Now, we assume it is true for a \begin_inset Formula $n$ \end_inset , that is: \layout Standard \begin_inset Formula \[ \epsilon_{0}+\frac{\epsilon_{1}}{x}+\frac{\epsilon_{2}}{x^{3}}+\dots+\frac{\epsilon_{n}}{x^{2^{n}-1}}=[1,\overrightarrow{w}]=\frac{p_{n}}{q_{n}}\] \end_inset \layout Standard Since \begin_inset Formula $\left|\overrightarrow{w}\right|=n$ \end_inset is odd, \begin_inset Formula $(-1)^{n}=-1$ \end_inset (see section \begin_inset LatexCommand \ref{sub:Total-Number-of} \end_inset ). As the biggest denominator is \begin_inset Formula $x^{2^{n}-1}$ \end_inset , we can take \begin_inset Formula $q_{n}=x^{2^{n}-1}$ \end_inset . We will want the \begin_inset Formula $q_{n+1}$ \end_inset to be \begin_inset Formula $x^{2^{n+1}-1}=xx^{2^{n+1}-2}=xx^{2(2^{n}-1)}=xq_{n}^{2}$ \end_inset . So for \begin_inset Formula $n+1$ \end_inset we have, using the property in section \begin_inset LatexCommand \ref{sub:Properties} \end_inset , \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Formula $\epsilon_{0}+\frac{\epsilon_{1}}{x}+\dots+\frac{\epsilon_{n}}{x^{2^{n}-1}}+\frac{\epsilon_{n+1}}{x^{2^{n+1}-1}}$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\frac{p_{n}}{q_{n}}+\frac{\epsilon_{n+1}}{xq_{n}^{2}}$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\frac{p_{n}}{q_{n}}+\frac{(-1)^{n}}{-\epsilon_{n+1}xq_{n}^{2}}$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=[1,\overrightarrow{w},-\epsilon_{n+1}x,-\overleftarrow{w}]$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=[1,T_{-\epsilon_{n+1}x}(\overrightarrow{w})]$ \end_inset \end_inset \end_inset \layout Standard So we have proved our proposition by induction. \layout Section Quasi-Crystals \layout Standard Before beginning the analysis of one dimensional crystals we will first look at the definitions of periodic and aperiodic sequences, before looking at how they are related to crystals. \layout Subsection Periodic Sequences \layout Standard A [complex] function \begin_inset Formula $f(x)$ \end_inset is said to be periodic iff \begin_inset Formula \[ f(x+n\tau)=f(x)\] \end_inset \layout Standard For some \begin_inset Formula $n\in\mathbb{Z}$ \end_inset . \begin_inset Formula $\tau$ \end_inset is said to be the period of \begin_inset Formula $f(x)$ \end_inset (note we choose the lowest such value of \begin_inset Formula $\tau$ \end_inset as any integer multiple of \begin_inset Formula $\tau$ \end_inset would also satisfy the condition). \layout Subsection Fourier Transform and Series \layout Standard The [one dimensional] Fourier transform is defined by \begin_inset Formula \[ F(u)=\mathcal{F}(f(x),u)=\int_{-\infty}^{\infty}f(x)e^{-i2\pi ux}dx\] \end_inset \layout Standard It maps a function in normal space to one in Fourier, or reciprocal, space. A single point in the function will correspond to a wave with a frequency of that point in wave space, and a wave in the function will be a single point in wave space. The proof of the statement follows: \layout Standard If \begin_inset Formula $f(x)$ \end_inset is a single point at \begin_inset Formula $x_{0}$ \end_inset , we have \begin_inset Formula $f(x)=\delta(x-x_{0})$ \end_inset . Then \begin_inset Formula $F(u)=\int_{-\infty}^{\infty}\delta(x-x_{0})e^{-i2\pi ux}dx=e^{-2\pi ix_{0}u}$ \end_inset , that is a wave of frequency \begin_inset Formula $x_{0}$ \end_inset . Conversely, if \begin_inset Formula $f(x)$ \end_inset is a wave, that is \begin_inset Formula $f(x)=e^{2\pi iu_{0}x}$ \end_inset we have \begin_inset Formula $F(u)=\int_{-\infty}^{\infty}e^{2\pi i(u_{0}-u)x}dx=\delta(u_{0}-u)$ \end_inset . \layout Standard Periodic function can be expressed as a Fourier series \begin_inset Formula \[ f(x)=\sum_{k=0}^{\infty}c_{k}e^{ikx}\] \end_inset \layout Standard where \begin_inset Formula $c_{k}\in\mathbb{C}$ \end_inset ,are unique, and can be calculated as \begin_inset Formula $c_{k}=\frac{1}{\tau}\int_{0}^{\tau}f(x)e^{-ikx}dx$ \end_inset due to orthogonality: \begin_inset Formula $\int_{0}^{\tau}e^{inx}e^{-mx}dx=\tau\delta_{n,m}$ \end_inset \begin_inset Foot collapsed true \layout Standard \begin_inset Formula $\int_{0}^{\tau}e^{inx}e^{-mx}dx=\int_{0}^{\tau}e^{i(n-m)x}dx=[\frac{e^{i(m-n)x}}{i(m-n)}]_{0}^{\tau}=0$ \end_inset if \begin_inset Formula $m\neq n$ \end_inset , but if \begin_inset Formula $m=n$ \end_inset we get \begin_inset Formula $\int_{0}^{\tau}e^{i(n-m)x}dx=\int_{0}^{\tau}e^{0}dx=\int_{0}^{\tau}1dx=\tau$ \end_inset . \end_inset . Note, we could choose a scale for \begin_inset Formula $x$ \end_inset such that \begin_inset Formula $\tau=2\pi$ \end_inset . Fundamentally, the series is a sum of waves of period \begin_inset Formula $\tau$ \end_inset and its harmonies. As a periodic function is made up of a sum of distinct frequencies, its Fourier transform will be a set of distinct points. As all the frequencies (of which there are countably many) are harmonies on one base frequency, the points in wave space will display certain symmetries. \layout Subsection Aperiodic Sequences \layout Standard If our function is over a metric space, we can define a distance between two function \begin_inset Formula $\rho(f(x),g(x))$ \end_inset . The metric will be defined as \begin_inset Formula $\rho(f(x),g(x))=\sup_{x}\left|f(x)-g(x)\right|$ \end_inset . We will consider functions defined by finite sums \begin_inset Formula \[ f(x)=\sum_{k=0}^{N}c_{k}e^{i\lambda_{k}x}\] \end_inset \layout Standard where \begin_inset Formula $\lambda_{k}\in\mathbb{R}$ \end_inset . In the special case that the set \begin_inset Formula $\{\lambda_{k}\}$ \end_inset correspond to a single frequency and its harmonies, we one again have the Fourier series, and so a periodic function. First we shall consider the functions \begin_inset Formula $f(x)=e^{i\lambda_{1}x}+e^{i\lambda_{2}x}$ \end_inset . If \begin_inset Formula $\frac{\lambda_{1}}{\lambda_{2}}$ \end_inset is rational, then we have the periodic Fourier case again, but if it is irrational then the function is not periodic, but it can be shown that there are arbitrarily great integers \begin_inset Formula $n_{1}$ \end_inset , \begin_inset Formula $n_{2}$ \end_inset such that \begin_inset Formula $\left|\frac{n_{1}}{\lambda_{1}}-\frac{n_{2}}{\lambda_{2}}\right|<\epsilon$ \end_inset for any given \begin_inset Formula $\epsilon>0$ \end_inset . Now, if we let \begin_inset Formula $\tau$ \end_inset be a number which is \emph on near \emph default (say between) \begin_inset Formula $\frac{n_{1}}{\lambda_{1}}$ \end_inset and \begin_inset Formula $\frac{n_{2}}{\lambda_{2}}$ \end_inset then \begin_inset Formula $\tau$ \end_inset is \emph on almost \emph default a period of \begin_inset Formula $e^{i\lambda_{1}x}$ \end_inset and \begin_inset Formula $e^{i\lambda_{2}x}$ \end_inset . Thus the difference \begin_inset Formula $f(x+\tau)-f(x)$ \end_inset is very small \begin_inset Formula $\forall x$ \end_inset . Note that for a periodic function we can choose \begin_inset Formula $\tau$ \end_inset so that this difference is zero. A real number \begin_inset Formula $\tau$ \end_inset is called a \emph on translation number \emph default of \begin_inset Formula $f(x)$ \end_inset if \begin_inset Formula $\left|f(x+\tau)-f(x)\right|\leq\epsilon$ \end_inset for a given \begin_inset Formula $\epsilon>0$ \end_inset . \begin_inset Formula $\tau$ \end_inset is determined by \begin_inset Formula $\epsilon$ \end_inset , so \begin_inset Formula $\tau=\tau(\epsilon)$ \end_inset . It can be proved that \begin_inset Formula $\tau(\epsilon_{1})+\tau(\epsilon_{2})=\tau(\epsilon_{1}+\epsilon_{2})$ \end_inset , \begin_inset Formula $\tau=-\tau$ \end_inset and so \begin_inset Formula $\tau(\epsilon_{1})-\tau(\epsilon_{2})=\tau(\epsilon_{1}+\epsilon_{2})$ \end_inset \begin_inset Foot collapsed true \layout Standard See reference \begin_inset LatexCommand \cite{aperiodic} \end_inset for details and proofs. \end_inset . \layout Standard To define an aperiodic function we need one more element. For each \begin_inset Formula $\epsilon$ \end_inset there a set of real translation numbers \begin_inset Formula $T$ \end_inset . In order for the functions described by translation number to remain closed under sensible things like addition, we require that \begin_inset Formula $T$ \end_inset be \emph on relatively dense \emph default . That is, a length \begin_inset Formula $L$ \end_inset exists (for each \begin_inset Formula $\epsilon$ \end_inset ) such that any interval of that length from the real line contains at least one translation number [from \begin_inset Formula $T$ \end_inset ]. \layout Standard For example, for a periodic function of period \begin_inset Formula $\tau$ \end_inset , the translation numbers can be taken to be \begin_inset Formula $E=\{\lambda_{k}\}=\{ k\tau\}$ \end_inset . Then the length \begin_inset Formula $L$ \end_inset can be taken to be any number greater than \begin_inset Formula $\tau$ \end_inset , so \begin_inset Formula $E$ \end_inset is relatively dense. \layout Standard The definition: A continuous function \begin_inset Formula $f(x)$ \end_inset is aperiodic iff, for any given \begin_inset Formula $\epsilon>0$ \end_inset , a relatively dense set of translation number of \begin_inset Formula $f(x)$ \end_inset (corresponding to \begin_inset Formula $\epsilon$ \end_inset ) exists. \layout Standard Note, periodic function are a [special] subset of aperiodic functions, and that its Fourier transform will be a discrete set of \begin_inset Formula $N$ \end_inset points corresponding to the frequencies \begin_inset Formula $\lambda$ \end_inset . Thus it is understanding the Fourier transform of a function that is crucial in determining if a function is aperiodic/periodic or not. \layout Subsection Lattice \layout Standard \begin_inset LatexCommand \label{sub:Lattice} \end_inset A lattice is a set of points in space. It is a discrete set of points, determined by a finite set of basis vectors. Every point in the lattice can be represented by a linear combination of these vectors, with whole number coefficients. For example, if in two dimensional space we had the basis vectors \begin_inset Formula $\left(\begin{array}{c} 1\\ 0\end{array}\right)$ \end_inset and \begin_inset Formula $\left(\begin{array}{c} 0\\ 1\end{array}\right)$ \end_inset , this would generate the lattice shown in figure \begin_inset LatexCommand \ref{fig:lattices} \end_inset . The other lattice was generated with basis vectors \begin_inset Formula $\left\{ \left(\begin{array}{c} 1\\ 0\end{array}\right),\left(\begin{array}{c} 1/2\\ 1\end{array}\right)\right\} $ \end_inset . \layout Standard associated \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Graphics filename figures/lattice1.fig lyxscale 50 scale 50 \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/lattice3.fig lyxscale 50 scale 50 \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\left\{ \left(\begin{array}{c} 1\\ 0\end{array}\right),\left(\begin{array}{c} 0\\ 1\end{array}\right)\right\} $ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\left\{ \left(\begin{array}{c} 1\\ 0\end{array}\right),\left(\begin{array}{c} 1/2\\ 1\end{array}\right)\right\} $ \end_inset \end_inset \end_inset \layout Caption \begin_inset LatexCommand \label{fig:lattices} \end_inset Lattices \end_inset \layout Subsection Delone Sets \layout Standard A set of points \begin_inset Formula $\Lambda$ \end_inset in euclidean space is a \emph on Delone set \emph default iff it is \emph on discrete \emph default and \emph on relatively dense \emph default . Here discrete means that the points in the set cannot be arbitrarily close together: \begin_inset Formula $\exists$ \end_inset a radius \begin_inset Formula $r>0$ \end_inset such that for every \begin_inset Formula $x,y\in\Lambda$ \end_inset , \begin_inset Formula $\left|x-y\right|\geq r$ \end_inset . Relatively dense in euclidean space means that the points cover the space: \begin_inset Formula $\exists$ \end_inset a radius \begin_inset Formula $R>0$ \end_inset such that every sphere (or circle etc) of radius \begin_inset Formula $\geq R$ \end_inset in space contain at least one point in \begin_inset Formula $\Lambda$ \end_inset . \layout Standard For example, in \begin_inset Formula $\mathbb{R}$ \end_inset , the set \begin_inset Formula $\Lambda=\{\frac{1}{n},n:n\in\mathbb{Z}\}$ \end_inset is relatively dense as any line segment of size \begin_inset Formula $1$ \end_inset or greater in \begin_inset Formula $\mathbb{R}$ \end_inset contains at least one point of \begin_inset Formula $\Lambda$ \end_inset . However, since the points \begin_inset Formula $\frac{1}{n}$ \end_inset converge to zero, we can alway find an \begin_inset Formula $\epsilon$ \end_inset such that \begin_inset Formula $\left|x-y\right|<\epsilon$ \end_inset , therefore the set is not discrete, and thus not a Delone set. The set \begin_inset Formula $\Lambda\{\pm n^{2}:n\in\mathbb{Z}\}$ \end_inset is discrete (let \begin_inset Formula $r=1$ \end_inset ), but it is not relatively dense as, for any finite length, there will always be a line line segment that does not include \begin_inset Formula $\Lambda$ \end_inset as \begin_inset Formula $(n+1)^{2}-n^{2}\rightarrow\infty$ \end_inset . \layout Standard A normal crystal lattice is always a Delone set. This follows from the construction of the lattice from a set of basis vectors: the distance between any two points is no less than the size of the smallest basis vector etc. \layout Standard The \begin_inset Formula $r$ \end_inset -star ( \begin_inset Formula $r>0$ \end_inset ) is the point set \begin_inset Formula $\overline{B}(x,r)\cap\Lambda$ \end_inset where \begin_inset Formula $x\in\Lambda$ \end_inset and \begin_inset Formula $\overline{B}(x,r)$ \end_inset is the closed ball of radius \begin_inset Formula $r$ \end_inset centered at \begin_inset Formula $x$ \end_inset . The \begin_inset Formula $r$ \end_inset -star will contain only a finite number of points as \begin_inset Formula $\Lambda$ \end_inset is discrete. \begin_inset Formula $\Lambda$ \end_inset is a \emph on regular set \emph default iff the \begin_inset Formula $r$ \end_inset -stars of \begin_inset Formula $\Lambda$ \end_inset are congruent for every \begin_inset Formula $r>0$ \end_inset (congruency means that it is identical under translation, rotations, and reflections). Thus the crystal lattice is a regular, or periodic, Delone set. \layout Subsection Voronoi Cells \layout Standard The crystal lattices can be thought of as being made up from identical \emph on cells \emph default , which are tiled together to form the lattice. The \emph on unit cell \emph default is defined to have edges which are parallel to the basis (see section \begin_inset LatexCommand \ref{sub:Lattice} \end_inset ). The unit cell will depend on the choice of basis used, and not all choices of cell will demonstrate the symmetry of the full lattice. Figure \begin_inset LatexCommand \ref{cap:Unit-Cell} \end_inset shows two possible unit cells for the same lattice. \layout Standard \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename figures/unit_cell.fig \end_inset \layout Caption \begin_inset LatexCommand \label{cap:Unit-Cell} \end_inset Unit Cell \end_inset \layout Standard The \emph on Voroni cell \emph default , on the other hand,will always display the symmetry of the lattice, and is independent of the chosen basis. It is defined to be the set of points centered about a lattice point such that they are closer to the center lattice point than to any other lattice point. Formally, this can be written \begin_inset Formula $\forall x\in\Lambda$ \end_inset as \begin_inset Formula \[ V(x)=\left\{ u\in\mathbb{R}^{n}\;:\;\left|x-u\right|\leq\left|y-u\right|\;\forall y\in\Lambda\right\} \] \end_inset \layout Standard It is constructed by drawing lines between all the lattice points and the center one. These lines are then bisected at right angles by drawing other lines (lines in two dimensions, planes in three dimension etc.). The Voroni cell is the smallest area (or volume etc.) bounded by the other lines (or planes etc.). See figure \begin_inset LatexCommand \ref{cap:Voronoi-Cell} \end_inset for an example. \layout Standard \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename figures/voronoi_cell.fig \end_inset \layout Caption \begin_inset LatexCommand \label{cap:Voronoi-Cell} \end_inset Voronoi Cell \end_inset \layout Subsection Isometries \layout Standard An isometry is a transformation that preserves distance and between points (and angles between lines). Isometries in two dimensions can be translations, rotations and reflections. Reflections and rotations also fix the origin. \layout Standard With an appropriate basis, the isometries that fix the origin (these are called linear isometries) can be represented by a \begin_inset Formula $n\times n$ \end_inset matrix (in \begin_inset Formula $n$ \end_inset -dimensional space) of the form \begin_inset Formula \[ \left(\begin{array}{cccc} A_{1} & 0 & 0 & 0\\ 0 & A_{2} & 0 & 0\\ 0 & 0 & \ddots & 0\\ 0 & 0 & 0 & A_{k}\end{array}\right)\] \end_inset \layout Standard where each \begin_inset Formula $A_{i}$ \end_inset is either \begin_inset Formula $1$ \end_inset , \begin_inset Formula $-1$ \end_inset or \begin_inset Formula $\left(\begin{array}{cc} \cos\theta & -\sin\theta\\ \sin\theta & \cos\theta\end{array}\right)$ \end_inset (which rotates by an angle \begin_inset Formula $\theta$ \end_inset ). From the definition of lattice, with respect to that basis the points must have integer co-ordinates, so our linear isometries can be represented by a (finite) subgroup of \begin_inset Formula $\textrm{GL}(n,\mathbb{Z})$ \end_inset , the general linear group of matrices of degree \begin_inset Formula $n$ \end_inset with integer elements and determinant \begin_inset Formula $\pm1$ \end_inset . \layout Subsubsection The Crystallographic Restriction \layout Standard \begin_inset LatexCommand \label{sub:restriction} \end_inset Now, any linear isometry acting on our crystal lattice can, depending on the basis chosen, be represented by either the former of latter form of matrix. As these matrices are the same but for a change of basis, they are conjugate, and thus have the same trace. For \begin_inset Formula $2$ \end_inset -dimensions, the \begin_inset Formula $\textrm{trace}(\textrm{GL}(n,\mathbb{Z}))\in\mathbb{Z}$ \end_inset , but the \begin_inset Formula $\textrm{trace}\left(\begin{array}{cc} \cos\theta & -\sin\theta\\ \sin\theta & \cos\theta\end{array}\right)=2\cos\theta$ \end_inset . As \begin_inset Formula $\left|\cos\theta\right|\leq1$ \end_inset (and assume \begin_inset Formula $0\leq\theta<2\pi$ \end_inset ), we have \begin_inset Formula $\cos\theta=\{0,\pm\frac{1}{2},\pm1\}$ \end_inset , so \begin_inset Formula $\theta=\{\frac{\pi}{2},\frac{\pi}{3},2\frac{\pi}{3},0,\pi\}$ \end_inset . Thus the only rotational symmetry that a crystal can have is that of order 4,6,3 and 2 (that is its point group contains rotations of order 2,3,4 and 6). There are similar restrictions for higher dimensional crystals. \layout Standard Point groups containing the rotations of order 5, 7, 8 etc will be called \emph on quasi-crystallographic \emph default . \layout Subsection Quasicrystals \layout Standard It was once thought that the long range order could only be due to periodicity. However in 1984 a crystal with long range symmetry was found that did not have a periodic structure. Such crystals were named \emph on quasicrystals \emph default . A quasicrystal is a peculiar form of solid in which the atoms of the solid are arranged in a seemingly regular, yet non-repeating structure. This kind of structure had actually been seen before in other places, in particular Penrose tiles \begin_inset LatexCommand \cite{quasicrystal} \end_inset . \layout Standard A periodic crystal is one that has translational symmetry (in all \begin_inset Formula $n$ \end_inset dimensions). An aperiodic crystal is one which has no translational symmetry. (Crystals which are only periodic in some of the \begin_inset Formula $n$ \end_inset directions, but aperiodic in the others are called subperiodic). The quasicrystal is defined as an aperiodic crystal which exhibits a diffractio n pattern forbidden for crystals.For example a 5-fold rotational symmetry in its diffraction pattern is forbidden for a crystal, see section \begin_inset LatexCommand \ref{sub:restriction} \end_inset . \layout Subsection X-Ray Diffraction \layout Standard Crystals are studied by looking at their x-ray diffraction patters, see figure \begin_inset LatexCommand \ref{fig:x-ray-diffraction} \end_inset . They can be used to find Bragg peaks, and determine information about the crystal's structure. The diffraction of x-rays in crystals can be modelled by Fraunhofer diffraction due to the following approximations: the light [x-ray] source is assumed to be very far away from the subject, so the incoming light rays can be assumed to be parallel; the detection screen is far enough away that light leaving the subject at the same angle meet at the same point on the screen; and only one frequency of light is used (not a spectrum). \layout Standard \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename figures/x-raydiffraction.eps \end_inset \layout Caption \begin_inset LatexCommand \label{fig:x-ray-diffraction} \end_inset x-ray diffraction \end_inset \layout Standard By observing that a disc as the subject will create a diffraction pattern of a spot whose radius is inversely proportional to the original disc (see figure \begin_inset LatexCommand \ref{cap:DiffractionCircle} \end_inset ), we can assume that the limit of a point would produce a diffraction pattern of constant intensity over the whole screen. If we let \begin_inset Formula $\overrightarrow{s}$ \end_inset be the point on the screen, \begin_inset Formula $J(\overrightarrow{s})$ \end_inset the intensity at that point, then we have \begin_inset Formula $J(\overrightarrow{s})\equiv1$ \end_inset . Also define the amplitude \begin_inset Formula $A(\overrightarrow{s})$ \end_inset at that point so that \begin_inset Formula $J(\overrightarrow{s})=\left|A(\overrightarrow{s})\right|^{2}$ \end_inset . Since \begin_inset Formula $\left|A(\overrightarrow{s})\right|=1$ \end_inset , \begin_inset Formula $A(\overrightarrow{s})=e^{-i2\pi f(\overrightarrow{s})}$ \end_inset where \begin_inset Formula $f(\overrightarrow{s})$ \end_inset is some real values function, which can be determined by considering two points. \layout Standard \begin_inset Float figure placement !h wide false collapsed true \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Graphics filename figures/circles/big_circle.pgm scale 50 \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/circles/small_circle.pgm scale 50 \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/circles/big_circle_fourier.pgm scale 50 \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/circles/small_circle_fourier.pgm scale 50 \end_inset \end_inset \begin_inset Text \layout Standard big circle \end_inset \begin_inset Text \layout Standard small circle \end_inset \end_inset \layout Caption \begin_inset LatexCommand \label{cap:DiffractionCircle} \end_inset Diffraction Patterns of Circles \end_inset \layout Standard Let the two points be separated by \begin_inset Formula $\overrightarrow{d}$ \end_inset . From our assumptions, light wave from the two points will leave the points in phase, but will arrive at the point \begin_inset Formula $\overrightarrow{s}$ \end_inset out of phase by an amount determined by the separation of the two points. This phase will be given by \begin_inset Formula $\overrightarrow{s}.\overrightarrow{d}$ \end_inset . This will cause the two light rays to constructively interfere at points where the phase is an integer multiple of the wavelength \begin_inset Formula $\overrightarrow{s}.\overrightarrow{d}=n\lambda$ \end_inset , but to cancel each other at \begin_inset Formula $\overrightarrow{s}.\overrightarrow{d}=(n+\frac{1}{2})\lambda$ \end_inset ( \begin_inset Formula $n\in\mathbb{Z}$ \end_inset ).Thus the diffraction pattern will go from light to dark with period inversely proportional to the distance \begin_inset Formula $\left|\overrightarrow{d}\right|$ \end_inset between the points. \layout Standard Now, the amplitude is additive, so \begin_inset Formula $A(\overrightarrow{s})=A_{0}(\overrightarrow{s})+A_{1}(\overrightarrow{s})$ \end_inset where \begin_inset Formula $A_{k}(\overrightarrow{s})$ \end_inset is the amplitude function from the respective point. As \begin_inset Formula $A_{1}(\overrightarrow{s})$ \end_inset is just \begin_inset Formula $A_{0}(\overrightarrow{s})$ \end_inset with a phase shift of \begin_inset Formula $\overrightarrow{s}.\overrightarrow{d}$ \end_inset , we should let \begin_inset Formula $A_{1}(\overrightarrow{s})=e^{2\pi i\overrightarrow{s}.\overrightarrow{d}}A_{0}(\overrightarrow{s})$ \end_inset . So \begin_inset Formula $A(\overrightarrow{s})=A_{0}(\overrightarrow{s})(1+e^{2\pi i\overrightarrow{s}.\overrightarrow{d}})$ \end_inset , and therefore \begin_inset Formula $J(\overrightarrow{s})=\left|A(\overrightarrow{s})\right|^{2}=\left|A_{0}(\overrightarrow{s})\right|^{2}(1+e^{2\pi i\overrightarrow{s}.\overrightarrow{d}})(1+e^{-2\pi i\overrightarrow{s}.\overrightarrow{d}})=2(1+cos(2\pi\overrightarrow{s}.\overrightarrow{d}))$ \end_inset . \begin_inset Formula $|\overrightarrow{s}.\overrightarrow{d}|=|\overrightarrow{d}|$ \end_inset so the period of the intensity is inversely proportional to the distance between the two points. \layout Standard For an arbitrary number of points, \begin_inset Formula $N$ \end_inset say, we have \begin_inset Formula $A(\overrightarrow{s})=A_{0}(\overrightarrow{s})+A_{1}(\overrightarrow{s})+\cdots A_{N-1}(\overrightarrow{s})=A_{0}(\overrightarrow{s})\sum_{k=0}^{N-1}e^{2\pi i\overrightarrow{s}.\overrightarrow{d_{k}}}$ \end_inset where \begin_inset Formula $\overrightarrow{d_{k}}$ \end_inset are the positions of each point, with \begin_inset Formula $\overrightarrow{d_{0}}=0$ \end_inset . So the intensity will be: \begin_inset Formula \[ J(\overrightarrow{s})=\left|A(\overrightarrow{s})\right|^{2}=\sum_{j=0}^{N-1}\sum_{k=0}^{N-1}e^{2\pi i\overrightarrow{s}.(\overrightarrow{d_{j}}-\overrightarrow{d_{k}})}=N+1+2\sum_{j=1}^{N-1}\sum_{k \begin_inset Text \layout Standard \begin_inset Graphics filename figures/dirac_comb/dirac_comb.pgm scale 60 \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/dirac_comb/dirac_comb_fourier.pgm scale 60 \end_inset \end_inset \end_inset \layout Caption \begin_inset LatexCommand \label{cap:Dirac-Comb} \end_inset Dirac Comb \end_inset \layout Subsubsection The Diffraction Condition \layout Standard A Delone set is a crystal if its diffraction pattern has a countably infinite discrete component. \layout Subsection The One Dimensional Case \layout Standard An infinite ordered set \begin_inset Formula $\{ x_{k}\}=\dots,x_{-1},x_{0},x_{1},\dots$ \end_inset , \begin_inset Formula $x_{k} \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence1/random.pgm scale 75 \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence1/random_fourier.pgm scale 75 \end_inset \end_inset \begin_inset Text \layout Standard random \end_inset \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence1/nonrandom.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence1/nonrandom_fourier.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard periodic \end_inset \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence1/fibonacci.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence1/fibonacci_fourier.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard Fibonacci \end_inset \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence1/paper.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence1/paper_fourier.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard paper-folding \end_inset \end_inset \layout Caption \begin_inset LatexCommand \label{cap:method1transforms} \end_inset One Dimensional Lattices and their Fourier transforms \end_inset \layout Standard All Fourier transforms have a bright point in the centre. The random case has a more continuous diffraction pattern than the periodic and Fibonacci cases. The bright peaks for these two correspond to Bragg peaks. Under this method the paper-folding lattice gives a very similar pattern to the random case. \layout Subsubsection Method 2 \layout Standard The letters in the sequence determine if there is a point or not on a regular interval. The results for the four sequences used are in figure \begin_inset LatexCommand \ref{cap:method2transforms} \end_inset (see appendix \begin_inset LatexCommand \ref{app:Commands-Used} \end_inset for commands used). \layout Standard \begin_inset Float figure placement !h wide false collapsed true \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence2/random.pgm scale 75 \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence2/random_fourier.pgm scale 75 \end_inset \end_inset \begin_inset Text \layout Standard random \end_inset \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence2/nonrandom.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence2/nonrandom_fourier.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard periodic \end_inset \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence2/fibonacci.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence2/fibonacci_fourier.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard Fibonacci \end_inset \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence2/paper.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Graphics filename figures/sequence2/paper_fourier.pgm scale 75 keepAspectRatio \end_inset \end_inset \begin_inset Text \layout Standard paper-folding \end_inset \end_inset \layout Caption \begin_inset LatexCommand \label{cap:method2transforms} \end_inset One Dimensional Lattices and their Fourier transforms \end_inset \layout Standard Again the random case has a more continuous diffraction pattern than the others. The periodic almost has no continuous nature. Both the Fibonacci and paper-folding patterns have discrete bright peaks. \layout Section The Tight-Binding Model \layout Standard \begin_inset LatexCommand \label{sec:The-Tight-Binding-Model} \end_inset This is a quantum model to describe a lattice of atoms, where we take the case where the atoms are all considered separately, and consider what happens if the wavefunctions overlap a little. The time-independent Schr \begin_inset ERT status Collapsed \layout Standard \backslash "o \end_inset dinger equation in Dirac notation is \begin_inset Formula \[ \mathcal{H}\left|\Psi\right\rangle =E\left|\Psi\right\rangle \] \end_inset \layout Standard where \begin_inset Formula $\mathcal{H}$ \end_inset is an \emph on operator \emph default acting on the \emph on eigenfunction \emph default \begin_inset Formula $\Psi$ \end_inset which has \emph on eigenenergy \emph default \begin_inset Formula $E$ \end_inset . \begin_inset Formula $\Psi$ \end_inset is a \emph on wavefunction \emph default which represents everything that we can know about the state of the system. In the \emph on tight-binding method \emph default \begin_inset LatexCommand \cite{quantum,physics} \end_inset , we let \begin_inset Formula $\mathcal{H}=\sum_{n}V_{n}a_{n}^{\dagger}a_{n}+\sum_{n}\sum_{m\neq n}t_{m,n}a_{m}^{\dagger}a_{n}$ \end_inset , where \begin_inset Formula $V_{n}$ \end_inset is the potential at site \begin_inset Formula $n$ \end_inset , and \begin_inset Formula $t_{m,n}$ \end_inset corresponds the overlap mentioned above. \begin_inset Formula $a_{n}^{\dagger}$ \end_inset and \begin_inset Formula $a_{n}$ \end_inset are the creation and annihilation operators respectively for the site \begin_inset Formula $n$ \end_inset . \begin_inset Formula $a_{n}^{\dagger}|0\rangle=|n\rangle$ \end_inset and \begin_inset Formula $\langle0|a_{n}=\langle n|$ \end_inset . \begin_inset Formula $|0\rangle$ \end_inset represent the vacuum state, where all the atoms are in their ground state. Thus we can represent the wavefunction as \begin_inset Formula \[ |\Psi\rangle=\sum_{k}c_{k}a_{k}^{\dagger}|0\rangle\equiv\sum_{k}c_{k}|k\rangle\] \end_inset \layout Standard and if we multiple the Schr \begin_inset ERT status Collapsed \layout Standard \backslash "o \end_inset dinger equation on the left by \begin_inset Formula $\langle0|a_{n}\equiv\langle n|$ \end_inset we have, on the RHS, \begin_inset Formula $\langle n|E\left|\Psi\right\rangle =E\sum_{k}c_{k}\langle n|k\rangle=E\sum_{k}c_{k}\delta_{n,k}=Ec_{n}$ \end_inset . For the LHS start with \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Formula $\mathcal{H}|\Psi\rangle$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\sum_{k}\sum_{l}c_{k}(V_{l}a_{l}^{\dagger}+\sum_{m\neq l}t_{l,m}a_{m}^{\dagger})a_{l}a_{k}^{\dagger}|0\rangle$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\sum_{k}c_{k}V_{k}a_{k}^{\dagger}|0\rangle+\sum_{l}\sum_{m\neq k}c_{m}t_{l,m}a_{l}^{\dagger}|0\rangle$ \end_inset \end_inset \end_inset \layout Standard Now when we multiply on the left by \begin_inset Formula $\langle n|\equiv\langle0|a_{n}$ \end_inset we get \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Formula $\langle n|\mathcal{H}|\Psi\rangle$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\sum_{k}c_{k}V_{k}a_{k}^{\dagger}\langle0|a_{n}a_{k}^{\dagger}|0\rangle+\sum_{l}\sum_{m\neq l}c_{m}t_{l,m}\langle0|a_{n}a_{l}^{\dagger}|0\rangle$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\sum_{k}c_{k}V_{k}\delta_{n,k}+\sum_{l}\sum_{m\neq l}c_{m}t_{l,m}\delta_{n,l}$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=V_{n}c_{n}+\sum_{m}t_{m,n}c_{m}$ \end_inset \end_inset \end_inset \layout Standard So we have (with \begin_inset Formula $t_{m,n}=0$ \end_inset for \begin_inset Formula $n=m$ \end_inset ) \begin_inset Formula \[ V_{n}c_{n}+\sum_{m}t_{m,n}c_{m}=Ec_{n}\] \end_inset \layout Standard In the on-site diagonal model, we choose \begin_inset Formula $t_{m,n}$ \end_inset such that \begin_inset Formula \[ V_{n}c_{n}+t(c_{n+1}+c_{n-1})=Ec_{n}\] \end_inset \layout Standard that is, only the closest two atoms affect each atom. We can write this in matrix form: \begin_inset Formula $\left(\begin{array}{c} c_{n+1}\\ c_{n}\end{array}\right)=T_{n}\left(\begin{array}{c} c_{n}\\ c_{n-1}\end{array}\right)$ \end_inset where \begin_inset Formula $T_{n}=\left(\begin{array}{cc} (E-V_{n})/t & -1\\ 1 & 0\end{array}\right)$ \end_inset . Then, if we let \begin_inset Formula $R_{n}=T_{n}T_{n-1}\cdots T_{2}T_{1}$ \end_inset we have \begin_inset Formula $c_{n}$ \end_inset in terms of \begin_inset Formula $c_{0}$ \end_inset & \begin_inset Formula $c_{1}$ \end_inset . Thus \begin_inset Formula \[ \left(\begin{array}{c} c_{n}\\ c_{n-1}\end{array}\right)=R_{n-1}\left(\begin{array}{c} c_{1}\\ c_{0}\end{array}\right)\] \end_inset \layout Standard Now, we consider the case when the potentials \begin_inset Formula $\{ V_{n}\}$ \end_inset are ordered in some aperiodic sequence. That is, given a sequence \begin_inset Formula $\{ a_{k}\}$ \end_inset of some alphabet, be associate a potential with each letter of the alphabet. for a binary alphabet, for example, we could have \begin_inset Formula $0\longleftrightarrow+V$ \end_inset , \begin_inset Formula $1\longleftrightarrow-V$ \end_inset . \layout Subsection Spectrum of the Model \layout Standard \begin_inset LatexCommand \label{sub:Spectrum} \end_inset The spectral theory associated to this model is different for the diffraction patterns obtained in the aperiodic lattice model. The spectrum for an operator \begin_inset Formula $\mathcal{H}$ \end_inset is defined as the complement of the set of energies for which the operator \begin_inset Formula $(\mathcal{H}-E)^{-1}$ \end_inset is bounded, that is \begin_inset Formula \[ \sigma(\mathcal{H})=\overline{\left\{ E\in\mathbb{R}:(\mathcal{H}-E)^{-1}\textrm{is bounded}\right\} }\] \end_inset \layout Standard If one thinks of the operators as matrices, the spectrum corresponds to the eigenvalues \begin_inset Formula $E$ \end_inset for which \begin_inset Formula $\mathcal{H}-EI$ \end_inset has an inverse, that is its determinant is non-zero. For the operator found above this is the same as the set of values of \begin_inset Formula $E$ \end_inset for which the operator \begin_inset Formula $\mathcal{H}$ \end_inset is polynomial bounded \begin_inset LatexCommand \cite{quantum} \end_inset . That is \begin_inset Formula \[ \sigma(\mathcal{H})=\overline{\left\{ E\in\mathbb{R}:\mathcal{H}(c_{n})=Ec_{n}\textrm{and}\left|c_{n}\right|\leq C\left|n\right|^{a}\forall n\in\mathbb{Z}\right\} }\] \end_inset \layout Standard This spectrum is composed of three parts: the pure point , the absolutely continuous, and the singular continuous. The pure point corresponds to the allowed energy eigenvalues of the equation, the absolutely continuous part is a closed set with non-empty interior, while the singular continuous is what is left. \layout Subsection Bloch Condition \layout Standard If the wave function were periodic, it would satisfy the Bloch condition \begin_inset LatexCommand \cite{physics} \end_inset : \layout Standard \begin_inset Formula \[ \Psi_{n}(\mathbf{r})=\sum_{R}e^{ik.R}\Psi_{n}(\mathbf{r}-\mathbf{R})\] \end_inset \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \begin_inset Formula $\Psi(\mathbf{r}+\mathbf{R})$ \end_inset \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=\sum_{R^{'}}e^{ik.R^{'}}\Psi_{n}(\mathbf{r}+\mathbf{R}^{'}-\mathbf{R})$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=e^{ik.R}\sum_{R^{'}}e^{ik.(R^{'}-R)}\Psi_{n}(\mathbf{r}-(\mathbf{R}^{'}-\mathbf{R}))$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=e^{ik.R}\sum_{R^{'}}e^{ik.R^{''}}\Psi_{n}(\mathbf{r}-\mathbf{R}^{''})$ \end_inset \end_inset \begin_inset Text \layout Standard \end_inset \begin_inset Text \layout Standard \begin_inset Formula $=e^{ik.R}\Psi(\mathbf{r})$ \end_inset \end_inset \end_inset \layout Standard In the aperiodic case it would approximately satisfy the Bloch condition. In terms of the co-efficients \begin_inset Formula $c_{k}$ \end_inset this condition is \layout Standard \begin_inset Formula \[ c_{j+n}=e^{ikn}c_{j}\] \end_inset \layout Standard Here, the period of the wavefunction is \begin_inset Formula $n$ \end_inset , compare with the value \begin_inset Formula $R$ \end_inset above. If the period was \begin_inset Formula $1$ \end_inset , i.e. \begin_inset Formula $V_{n}=V\;\forall n$ \end_inset then we have \begin_inset Formula $c_{j+1}=e^{ik}c_{j}$ \end_inset . Substituting this into \begin_inset Formula $V_{n}c_{n}+t(c_{n+1}+c_{n-1})=Ec_{n}$ \end_inset then dividing through by \begin_inset Formula $c_{n}$ \end_inset gives us \begin_inset Formula $V+t(e^{ik}+e^{-ik})=E$ \end_inset , that is \begin_inset Formula $(E-V)/t=2\cos k$ \end_inset . To the trace \begin_inset Formula $\textrm{tr}T=2\cos k$ \end_inset . In which case the energy spectrum is \begin_inset Formula $\sigma(\mathcal{H})=\{ E\in\mathbb{R}\,:\,|\textrm{tr}T|\leq2\}$ \end_inset Similarly, for the case with period \begin_inset Formula $n$ \end_inset we have \begin_inset Formula $\textrm{tr}R_{n}=2\cos kn$ \end_inset , so the energy spectrum is \begin_inset Formula $\sigma(\mathcal{H})=\{ E\in\mathbb{R}\,:\,|\textrm{tr}R_{n}|\leq2\}$ \end_inset . \layout Standard For the aperiodic case, we consider a section of the sequence of length \begin_inset Formula $n$ \end_inset as the basis for a periodic sequence, then let \begin_inset Formula $n\rightarrow\infty$ \end_inset . This spectrum is called the \emph on dynamical \emph default spectrum. \layout Subsection Fibonacci Sequence \layout Standard To calculate the energy spectrum of the Fibonacci sequence, note that due to the way the sequence is constructed, \begin_inset Formula $R_{n}=R_{n-2}R_{n-1}$ \end_inset . From this equation, we find a trace map for the Fibonacci model: \begin_inset Formula \[ \textrm{tr}R_{n}=\textrm{tr}R_{n-2}.\textrm{tr}R_{n-1}-\textrm{tr}R_{n-3}\] \end_inset \layout Standard This map can then be used to find dynamical energy spectrum. This is beyond the scope of this project. \layout Standard Then, given the energy spectrum, that is the allowed energies, we can then find the corresponding wavefunctions. This can be done using the recurrence relation \begin_inset Formula \[ c_{n+1}=c_{n}(E-V_{n})/t-c_{n-1}\] \end_inset \layout Standard As we can take the allowed values for \begin_inset Formula $E$ \end_inset from the dynamical spectrum, and the values of \begin_inset Formula $V_{n}$ \end_inset are given by our chosen aperiodic sequence. The wavefunction is then given by \begin_inset Formula \[ |\Psi\rangle=\sum_{k}c_{k}a_{k}^{\dagger}|0\rangle\equiv\sum_{k}c_{k}|k\rangle\] \end_inset \layout Subsection The Wavefunctions Obtained \layout Standard We can calculate the wavefunctions for each energy. Not all energies are allowed; the spectrum, as described in section \begin_inset LatexCommand \ref{sub:Spectrum} \end_inset , tells us which energies will give us a bounded wavefunction. If a disallowed energy value is used, the wavefunction will just tend to infinity. For periodic case I found periodic wavefunction like the one show in figure \begin_inset LatexCommand \ref{cap:Wavefunction-for-Periodic} \end_inset . I was unable to find suitable energies for the aperiodic cases however. This is because the allowed energies are not continuous, but a \emph on cantor dust \emph default . Thus the accuracy of the energy value used becomes very import and the slightest difference will not be an allowed energy. Figure \begin_inset LatexCommand \ref{cap:Wavefunction-for-Paper} \end_inset shows, for a disallowed energy, how the wavefunction grows unbounded. \layout Standard \begin_inset Float figure placement H wide false collapsed true \layout Standard \begin_inset Graphics filename c/spectrums/spectrum3.ps lyxscale 50 scale 40 rotateAngle 270 \end_inset \layout Caption \begin_inset LatexCommand \label{cap:Wavefunction-for-Periodic} \end_inset Wavefunction for Periodic potential \end_inset \begin_inset Float figure placement H wide false collapsed true \layout Standard \begin_inset Graphics filename c/spectrums/spectrum7.ps lyxscale 50 scale 40 rotateAngle 270 \end_inset \layout Caption \begin_inset LatexCommand \label{cap:Wavefunction-for-Paper} \end_inset Wavefunction for paperfolding potential \end_inset \layout Section Conclusion \layout Standard We have seen that the paperfolding sequence has several interesting properties, especially when expressed as a dragon curve. We have also seen how it can be used with continued fractions and that it could have applications in the study of quasicrystals. Unfortunately I was not able to graph the wavefunction in the case of the [Fibonacci or] paperfolding sequence. \layout Subsection Acknowledgments \layout Standard I would like to thank Dr Chris J Smyth for his invaluable help in my undertaking of this project. \layout Section \start_of_appendix Source Code \layout Standard Attached is the source code for the programs that I wrote to generate the diagrams used in this project. fourier.c and points2image.c are based on a program fourier.c in \begin_inset LatexCommand \cite{quasicrystal} \end_inset . \layout Paragraph C programs: \layout List \labelwidthstring 00.00.0000 project.h A header file common to most of the c programs. Contains some constants and macros. \layout List \labelwidthstring 00.00.0000 dragonplot.c Takes a binary series as instruction to turn left/right when drawing a dragon curve. See section \begin_inset LatexCommand \ref{cap:Fractal} \end_inset . Outputs a .pgm image. \layout List \labelwidthstring 00.00.0000 dragonplot2.c As above, but outputs an xfig .fig file. \layout List \labelwidthstring 00.00.0000 fibbonacci.c Generates the Fibonacci sequence. Uses the method described for the Sturmien sequence. \layout List \labelwidthstring 00.00.0000 fold.c Outputs a paperfolding sequence based on the folding instructions given. \layout List \labelwidthstring 00.00.0000 fourier.c Ouputs an image of the fourier transform of a given set of points. \layout List \labelwidthstring 00.00.0000 image2dat1d.c Creates a graph of the horizontal cross-section of a given image. \layout List \labelwidthstring 00.00.0000 image2fourier.c Calculates the fourier transform of the input image. Uses \emph on fftw \emph default : the \begin_inset Quotes eld \end_inset Fastest Fourier Transform in the West \begin_inset Quotes erd \end_inset (sic) \layout List \labelwidthstring 00.00.0000 newton.c Calculates the solution to \begin_inset Formula $\lambda^{3}-\lambda^{2}-2=0$ \end_inset using Newton's method. \layout List \labelwidthstring 00.00.0000 nonrandom.c Generates the sequence \begin_inset Formula $ababababa\dots$ \end_inset \layout List \labelwidthstring 00.00.0000 points2image.c Draws a picture of points in space given by the input. \layout List \labelwidthstring 00.00.0000 random.c Generates a random binary sequence. \layout List \labelwidthstring 00.00.0000 sequence2points.c Calculates positions of points based on method 1, see section \begin_inset LatexCommand \ref{sub:make1dlattice} \end_inset . \layout List \labelwidthstring 00.00.0000 sequence2points2.c Calculates positions of points based on method 2, see section \begin_inset LatexCommand \ref{sub:make1dlattice} \end_inset . \layout List \labelwidthstring 00.00.0000 sequence2spectrum.c Graphs the wavefunction with the potential \begin_inset Formula $V_{n}$ \end_inset determined by the sequence given, see section \begin_inset LatexCommand \ref{sec:The-Tight-Binding-Model} \end_inset . \layout Paragraph Logo Programs: \layout List \labelwidthstring 00.00.0000 heighway.lg Used to draw the dragon curve's boundary. Can also draw the dragon curve itself. \layout Subsection How they work \layout Standard I made the programs very modular to that I could use pipes to create a variety of different configurations to try out. Most of the programs work by taking information in from the standard input ( \emph on stdin \emph default ), processing it, and then outputting different data to the standard out ( \emph on stdout \emph default ). \emph on Pipes \emph default are used to link together these programs in a `chain'. \layout Standard For example, if I want to see what the dragon curve looks like, I use \emph on echo \emph default to create the folding instructions \begin_inset Formula $aaaaaaaaaaaa$ \end_inset , then pipe this into the folding program \emph on fold \emph default . It outputs the paper-folding sequence, which I pipe into \emph on dragonplot \emph default to draw the dragon curve, and display the result using \emph on xv \emph default . The command for this would be \layout Quote echo aaaaaaaaaaaaa | ./fold | ./dragonplot 400 500 2 100 150 | xv - \layout Standard Which would generate the image show in figure \begin_inset LatexCommand \ref{cap:./dragonplot} \end_inset . The options dragonplot is called with set the size of the output image etc. \layout Standard \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename figures/dragonplot.png lyxscale 50 scale 40 \end_inset \layout Caption \begin_inset LatexCommand \label{cap:./dragonplot} \end_inset ./dragonplot \end_inset \layout Subsubsection Commands Used \layout Standard \begin_inset LatexCommand \label{app:Commands-Used} \end_inset The commands used to generate the images in figure \begin_inset LatexCommand \ref{cap:method1transforms} \end_inset are \layout Quotation random 65 |sequence2points 25 |points2image 480 50 |xv - \layout Quotation random 65 |sequence2points 25 |fourier 480 50 96 2 |xv - \layout Quotation nonrandom 65 |sequence2points 25 |points2image 480 50 |xv - \layout Quotation nonrandom 65 |sequence2points 25 |fourier 480 50 96 2 |xv - \layout Quotation fibbonacci 58 |sequence2points 25 |points2image 480 50 |xv - \layout Quotation fibbonacci 58 |sequence2points 25 |fourier 480 50 96 2 |xv - \layout Quotation paper 6 |sequence2points 25 |points2image 480 50 |xv - \layout Quotation paper 6 |sequence2points 25 |fourier 480 50 96 2 |xv - \layout Standard and for figure \begin_inset LatexCommand \ref{cap:method2transforms} \end_inset \layout Quotation random 100 |sequence2points2 25 |points2image 480 50 |xv - \layout Quotation random 100 |sequence2points2 25 |fourier 480 50 96 2 |xv - \layout Quotation nonrandom 100 |sequence2points2 25 |points2image 480 50 |xv - \layout Quotation nonrandom 100 |sequence2points2 25 |fourier 480 50 96 2 |xv - \layout Quotation fibbonacci 100 |sequence2points2 25 |points2image 480 50 |xv - \layout Quotation fibbonacci 100 |sequence2points2 25 |fourier 480 50 96 2 |xv - \layout Quotation paper 7 |sequence2points2 25 |points2image 480 50 |xv - \layout Quotation paper 7 |sequence2points2 25 |fourier 480 50 96 2 |xv - \layout Subsubsection fold.c \layout Standard This program implements the 2-automaton described in section \begin_inset LatexCommand \ref{sub:2-Automaton} \end_inset , but with the modification for other folding instructions, as described in section \begin_inset LatexCommand \ref{peanoinstr} \end_inset . \layout Subsubsection fibonacci.c \layout Standard The Fibonacci sequence is a Sturmian sequence. This program uses the method described in section \begin_inset LatexCommand \ref{sub:Sturmian} \end_inset , with \begin_inset Formula $\alpha=\phi-1=\frac{\sqrt{5}-1}{2}$ \end_inset and \begin_inset Formula $\beta=0$ \end_inset as per section \begin_inset LatexCommand \ref{sub:Fibonnaci} \end_inset . \layout Subsubsection newton.c \layout Standard This solves the equation \begin_inset Formula $g(\lambda)=\lambda^{3}-\lambda^{2}-2=0$ \end_inset . Let \begin_inset Formula $g(x)/g^{'}(x)=\frac{x^{3}-x^{2}-2}{3x^{2}-3x}$ \end_inset . Then define the recurrence relation \begin_inset Formula $x_{k+1}=x_{k}-g(x_{k})/g^{'}(x_{k})$ \end_inset . With a suitible choice for \begin_inset Formula $x_{0}$ \end_inset , \begin_inset Formula $\lim_{k\rightarrow\infty}x_{k}=\lambda$ \end_inset where \begin_inset Formula $\lambda$ \end_inset is a solution to \begin_inset Formula $g(\lambda)=0$ \end_inset . That is what newton.c does. Running ./newton has the following output: \layout Quotation x0 = 3.000000 \layout Quotation x1 = 2.238095 \layout Quotation x2 = 1.839868 \layout Quotation x3 = 1.709679 \layout Quotation x4 = 1.695773 \layout Quotation x5 = 1.695621 \layout Quotation x6 = 1.695621 \layout Quotation x7 = 1.695621 \layout Quotation x8 = 1.695621 \layout Quotation x9 = 1.695621 \layout Standard So the solution we are looking for is 1.69562 to six decinal places. \layout Subsection Logo \layout Standard The logo programming language is well suited to drawing the dragon curves in this project. The language works by imagining that there is a turtle, with a pen taped to it, on a piece of paper. The language is made up of instruction like \begin_inset Quotes eld \end_inset forward 50 \begin_inset Quotes erd \end_inset and \begin_inset Quotes eld \end_inset left 45 \begin_inset Quotes erd \end_inset . This tells the `turtle' to move, and so draw out a line on the paper. The logo interpreter xlogo is shown in figure \begin_inset LatexCommand \ref{cap:xlogo.jar} \end_inset . \layout Standard \begin_inset Float figure placement h wide false collapsed true \layout Standard \begin_inset Graphics filename figures/xlogo.png lyxscale 50 scale 40 \end_inset \layout Caption \begin_inset LatexCommand \label{cap:xlogo.jar} \end_inset xlogo.jar \end_inset \layout Standard They way my logo program \emph on heighway.lg \emph default draws the graphs is very simple. It is basically the Maudlin-Williams graph with information about \emph on direction \emph default as well as scale. Using this, and only this, the turtle will draw out the desired fractals. For example, the boundary is made up of two segments, \emph on a \emph default and \emph on b \emph default (see section \begin_inset LatexCommand \ref{sub:Boundary-of-Dragon} \end_inset ). \emph on a \emph default itself is made up of a copy of \emph on a \emph default and of \emph on b \emph default , \begin_inset Formula $\frac{1}{\sqrt{2}}$ \end_inset the length of the original \emph on a \emph default , but at a \begin_inset Formula $45^{o}$ \end_inset degree angle to the original \emph on a. b \emph default is made up of two half-size \emph on a \emph default s, but with one pointing in the opposite direction. \layout Section Software \layout List \labelwidthstring 00.00.0000 Gentoo This project was done on my PC running Gentoo GNU/Linux (http://www.gentoo. org) \layout List \labelwidthstring 00.00.0000 LyX This project was written using the LyX word processor (http://www.lyx.org/) \layout List \labelwidthstring 00.00.0000 xfig Figures were drawn using xfig (http://www.xfig.org) \layout List \labelwidthstring 00.00.0000 gimp Some diagrams were drawn/edited using the gimp (http://www.gimp.org/) \layout List \labelwidthstring 00.00.0000 imagemagick Batch image manipulation (http://www.imagemagick.org/) \layout List \labelwidthstring 00.00.0000 xv Image viewing and manipulation (http://www.trilon.com/xv/) \layout List \labelwidthstring 00.00.0000 a2ps Used to format source code for printing \layout List \labelwidthstring 00.00.0000 logo Berkeley Logo interpreter (UCBLogo) (http://www.cs.berkeley.edu/~bh/) \layout List \labelwidthstring 00.00.0000 xlogo Colourful java logo interpreter (http://xlogo.free.fr/) \layout List \labelwidthstring 00.00.0000 fftw The \begin_inset Quotes eld \end_inset Fastest Fourier Transform in the West \begin_inset Quotes erd \end_inset (http://www.fftw.org) \layout Bibliography \bibitem [1]{folds} \emph on Macquarie Mathematics Report - \begin_inset Quotes eld \end_inset Folds! \begin_inset Quotes erd \end_inset \emph default - Michel Dekking, Michel Mendes France, Alf van der Poorten (1982) \layout Bibliography \bibitem [2]{maxpaper} \emph on How To Fold Paper in Half Twelve Times \emph default - Britney Gallivan ( http://www.osb.net/Pomona/12times.htm) \layout Bibliography \bibitem [3]{fibonaccipdf} \emph on Fibonacci Sequences Arising From Paperfolding \emph default - Anna Rodenhausen (http://www.mevis.de/~anna/publications/goslar.pdf ) \layout Bibliography \bibitem [4]{fractions} \emph on Folded Continued Fractions \emph default - A. J. van der Poorten and J. Shallit (http://www-centre.mpce.mq.edu.au/alfpapers/a098.pdf) \layout Bibliography \bibitem [5]{automata} \emph on Finite Automata and Arithmetic \emph default - J.-P. Allouche (http://www.emis.de/journals/SLC/opapers/s30allouche.pdf) \layout Bibliography \bibitem [6]{quantum} \emph on Aperiodically Ordered Structures in One Dimension \emph default - Michael Hornquist (http://www.ifm.liu.se/~micho/phd/dissertation.html) \layout Bibliography \bibitem [7]{jurassic} \emph on Jurassic Park \emph default - Michael Crichton \layout Bibliography \bibitem [8]{Fractal Geometry} \emph on Fractal Geometry \emph default - Kenneth Falconer \layout Bibliography \bibitem [9]{Measure} \emph on Measure, Topology, and Fractal Geometry \emph default - Gerald A. Edgar \layout Bibliography \bibitem [10]{quasicrystal} \emph on Quasicrystals and Geometry \emph default - Marjorie Senechal \layout Bibliography \bibitem [11]{aperiodic} \emph on Almost Periodic Sequnces \emph default - Harald Bohr \layout Bibliography \bibitem [12]{physics} \emph on Solid State Physics \emph default - Neil W. Ashcroft & N. David Mermin \layout Bibliography \bibitem [13]{mathworld} http://www.mathworld.com \layout Bibliography \bibitem [14]{wikipedia} http://www.wikipedia.org \layout Bibliography \bibitem [15]{scienceworld} http://www.scienceworld.com \layout Bibliography \bibitem [16]{fourier} \emph on School of Physics: The Fourier Transform (What you need to know) \emph default - (http://www.ph.ed.ac.uk/~wjh/teaching/Fourier/) \the_end