Number Theory and Quasicrystals

Q1) Can you make a periodic structure? Try clicking on any of the grid points. Periodicity should be easiest to see for points near the bottom left (the origin).

Q2) What property of a gradient determines whether it forms periodic structures? Rationality - i.e. the gradient being written as a fraction of finite integers. Since the gradient is the number of steps up divided by the number of steps along, any line connecting two grid points has a rational gradient. If we hit the point $(q,p)$ (starting from $(0,0)$), we get a gradient of $\frac{p}{q}$, and the same holds in reverse: a gradient of $\frac{p}{q}$ must hit $(q,p)$.

Q3) How does the gradient determine how many atoms appear in a periodic crystal before it begins to repeat? If we look at the staircase representation, we can see the total number of atoms is given by the number of steps up, plus the number along, meaning there will always be $p+q$ atoms per repetition (or 'in the unit cell').

Q4) Is this representation unique? The fraction $p \over q$, corresponding to hitting the point $(q,p)$, isn't unique - we could multiply top and bottom by an integer, and find another point the line hits ($np \over nq$ and $(nq,np)$).

Q5) What additional requirement could you add to make it unique? If we want to find a unique point corresponding to any gradient, we can always simplify $\frac{p}{q}$ by cancelling all common factors between $p$ and $q$, corresponding to finding the first point we hit as we move out from the origin.

Q6) Do all possible gradients correspond to a point on the lattice in this way? What does this mean for forming non-periodic crystals? We know all rational gradients correspond to a point, so the only remaining gradients to account for are irrational ones (meaning they can't be written $p \over q$, where $p$ and $q$ are finite integers - say like $\pi$, $\phi$, $\sqrt{2}$, or $\sqrt[7]{5}$)?
Our 'point-based' representation requires that we hit a point aside from $(0,0)$. But hitting any other point $(q,p)$ forces the gradient to be $\frac{p}{q}$. Since this can't be the case for irrational numbers, irrational numbers never hit a point, and can't be represented in this way.
Since the graient needs to hit a point other than $(0,0)$ to be periodic, and these never do, irrational numbers form non-periodic structures. This isn't enough to be a quasicrystal though, so learning about the number of consecutive repetitions of parts of a crystal will therefore be a major focus for us.

Q1) Can you spot the relationship between the pattern of atoms/steps and the sequence of 'S's and 'L's on the right? For gradients less than 1, we tend to label the atoms based on whether they correspond to short (S) or long (L) gaps. This corresponds to steps up on the staircase corresponding to the letter S, and steps along corresponding to the letter L.

Q2) Does this still hold if we increase the gradient past 1? When the gradient is 1, using 'S' for short segments and 'L' for long segments poses a problem: steps up and along are both the same length. For gradients greater than 1, steps up are now the longer ones, and vice versa. In order to maintain some sense of continuity, however, we remain labelling steps up (such as the first point) with an S, even for gradients greater than 1. Practically, the exact spacing can be accounted for in other ways, and often isn't used, so the letters are mostly arbitrary. A more consistent definition is to, think of S as steps up, and L as steps along.

Q3) Can you spot any rough pattern between the length of runs of the same letter (known as that letter's power), and the gradient? You might have also seen that the letter S will have a power of the gradient rounded either down or up. This turns out to generalise to the powers of more complicated structures, as we'll see later, and is part of how we'll prove aperiodicity.

Q4) Pick a simple rational number for the gradient - say something like $1 \over 3$. By how much do you have to change the offset before atoms begin to jump? For a fraction simplified to $p \over q$, we need to increase the offset to at least $1 \over q$ for the first hop to occur. The graph of these distances is known as Thomae's function, or the popcorn function. To a physicist's eye, this function is truly an abomination, it has the property that, despite being continuous almost everywhere, it's never continuous over any finite range (it's discontinuous at every rational number). It's a great example of why calculus and number theory tend to be so disjoint - good luck trying to write a differential equation which describes this!

Q5) Are atoms conserved as we change the offset? Atoms are, in fact, conserved (meaning this can happen in real quasicrystals - it's called a 'phason'). From the perspective of the staircase, moving past a point corresponds from changing an along-then-up (i.e. LS) to an up-then-along (SL).

Q6) How far do you have to move the offset now, before atoms begin to jump (and how do you think this would change if we could zoom as far out as we liked)? For irrational numbers, any finite movement, however small, will correspond to a jump - it might just be really far away! Compared to rational numbers, where numbers of the form $p \over q$ change after a shift by $1 \over q$, irrational numbers can roughly be thought of as having infinite $p$ and $q$, so ${1 \over q} = 0$.

Q7) Are the first atoms to move near to the origin, or far away? Why? Aside from the hop precisely at the origin, for irrational numbers, the first hops are always a long way away. A rough argument for this is that a change in structure near the origin would require, as we lift up our line, that it crosses a point near the origin before any further away, implying that the best approximation to the gradient is near the origin. However, this implies that there even exists a best rational approximation to a particular irrational number, and it should be fairly easy to convince yourself that given any rational approximation, we can always build another, better one.

Q8) If I suggest that you can view a change in offset as moving our origin to a new latice point, am I right or wrong? Does your answer depend on whether or not the crystal is rational? As it turns out, only certain offsets correspond directly to a shift in our perspective. Specifically, it's those offsets which have just caused an atom to jump: our line now crosses through the atom which just jumped, and it's therefore equivalent to our origin. Hence, in the case of an irrational number, where any finite movement produces jumps, continuously changing the offset is equivalent to pinging us wildly across our infinite, non-periodic, crystal.

Q1) Given the structure of a particular irrational number (say $\phi^{-1}$), can you find a series of rational gradients (and therefore periodic structures, known as approximants) which tend towards $\phi^{-1}$ (you can do this roughly, visually, or mathematically)? One answer to this is to base this off all the truncated decimal expansions of $\phi^{-1}$, so: $${0 \over 1},{6 \over 10},{61 \over 100},{618 \over 1000},{61803 \over 100000},...$$ Which, cancelling common factors, gives: $${0 \over 1},{3 \over 5},{61 \over 100},{309 \over 500},{61803 \over 100000},...$$

Q2) Is this sequence unique? Series of rational numbers approaching $\phi^{-1}$ are far from unique: sequences don't even need to get closer at every step, so there are lots of ways one can safely add or remove points from a sequence without damaging its convergence. (That's not to say the points we could add are unconstrained - if you added $\frac{1}{1}$ after every approximant to $\phi^{-1}$, there would still be parts of your sequence which wouldn't get closer, breaking convergence.)

Q3) If I add the condition that we have to get closer with every term added, and that we never add a fraction with a higher denominator if one with a lower denominator could do a better job, how does that narrow down your choices? Two sequences which satisfy this condition for $\phi^{-1}$ can be expressed particularly nicely in terms of the Fibonacci numbers. $${1 \over 1},{1 \over 2},{2 \over 3},{3 \over 5},{5 \over 8},{8 \over 13},{13 \over 21},...$$ $${1 \over 1},{2 \over 3},{5 \over 8},{13 \over 21},...$$ In general, this condition will narrow down your options a lot, but it will be far from unique, so these aren't the only options you could have picked. If you didn't find any sequences like these, I'd suggest checking these out and getting a sense of their properties. In particular, the first one will be key later on, whilst the second may provide an interesting lens with which to contrast the decisions we take when introducing continued fractions, later.

Q4) [Something of an extension, for those interested in adding rigor to the idea of strings 'converging']: In what sense are these good approximations, and why might not all ways to define 'closeness to our limit' agree on whether or not we converge? When we say a list of things converges to something, we mean that, as we move throughout a list, we can say that all future values in the list have a 'distance to our limit' less than some number, and that, as we move throughout our list, that 'distance' drops to zero. Basing approximants around convergent gradients essentially asks the question 'Within the first period of our approximant, what's the length of the longest continuous subsequence which matches the limit?', defining 'distance to the limit' as the inverse of this answer. For an example, compare the respective limit and approximant

SLSLLSLSLLSLLSLSLLSL...

SLSLLSLL|SLSLLSLL|...

The bar denotes the periods of the approximant, and the bold section is the longest continuous subsequence. It has 7 letters, and hence the 'distance' is $\frac{1}{7}$. If, instead, we defined the 'distance' based around asking 'What proportion of the infinite periodic sequence and the limit match?', the question of convergence might be far less clear, and certainly would be beyond the scope of this introduction. It's these sorts of details us physicists like to ignore which really wind up the mathematicians, so they're good things to look out for.

Q5) How does the distribution of approximants change for other irrational numbers (say $\sqrt{2}$)? For $\phi^{-1}$, it seems like there's a nice (and maybe even complete, in some sense, in the set that a large class of other sets can be constructed from it) set of approximants meeting the condition that each gets progressively closer to $\phi^{-1}$, given earlier by: $${1 \over 1},{1 \over 2},{2 \over 3},{3 \over 5},{5 \over 8},{8 \over 13},{13 \over 21},...$$ And, if you try to find these on the graph, you'll find they alternate. For $\sqrt{2}$, however, if we try to find something similar, we might find something like: $$\frac{1}{1},\frac{3}{2},\frac{4}{3},\frac{7}{5},...$$ Which contains, close to the origin, a point which breaks the pattern of alternation: $(3,4)$, or $4 \over 3$. We'll see later that the sequence for $\phi^{-1}$ generalises nicely to other irrational numbers, but should always remember that, unlike in the case of $\phi^{-1}$, there in general may also be other numbers which could fit into our sequence, with different properties. They won't cause us any problems, but their existence is worth remembering.

Q1) Consider slowly moving the graph from a rational point near the origin to any other further out: When, visually, will a given atom hop? (Hint: This is similar to what we found when adjusting the offset earlier). The structure changes whenever the gradient line crosses a lattice point.

Q2) Where does the structure change the least? Is it close to the origin, or further away? As we saw earlier when varying the offset, the number of lattice points close to the line is the lowest near the origin, meaning changes to the gradient will cross the fewest points, such that changes in the gradient are understood most simply, there.

Q3) Focusing now on the first period of the final structure, what determines how many changes occur between the two lines (i.e., how many times do atoms jump position as we move?). The number of changes between the two lines will depend slightly on if you're moving up or down. If you're moving up (i.e. $1 \over 1$ to $17 \over 16$, both approximations to $\sqrt[12]{2}$, the frequency multiplier for a semitone on a typical piano), you will instantly push out the staircase at all points corresponding to the first approximant, $1 \over 1$ (i.e. $(n,n)$), whilst moving the gradient downwards by a small amount makes no instant change at these points (this is all simply based on how the staircase structure was defined). Otherwise, the number of changes from a smaller approximant to a larger approximant within the first period is simply the number of points between those lines, plus those points possibly corresponding to the approximants themselves.

Q4) Consider our approximants to $\phi^{-1}$, as chosen above: how many points in the first period (as well as which points) change as we move between approximants (particularly successive approximants) from the sequence below? $${1 \over 1},{1 \over 2},{2 \over 3},{3 \over 5},{5 \over 8},{8 \over 13},{13 \over 21},...$$ This sequence has the property (as for why this is the case, we'll find this out later) that the only changes within the first period of the larger approximation are those corresponding to the approximants themselves - there are no points between the lines until we get to much higher denominators (again, we'll prove this later). Therefore, there should be one change every time the line is moved, each time at the site of one of the approximants.

Q5) Can you find another sequence where even fewer points change between each step? It turns out, at least one point always has to change as we move from rational approximant to rational approximant. However, we can find a sequence with this minimum number of points changing, but which converges faster. As an example, what if we choose approximants which converge from above, rather than alternating, such as the other series we found earlier for $\phi^{-1}$: $${1 \over 1},{2 \over 3},{5 \over 8},{13 \over 21},...$$ It's worth noting the reason we're able to make this gain to convergence, which we can see if we move from $5 \over 8$ down to $8 \over 13$ and back up to $13 \over 21$, whilst paying attention to, rather than the first period of $8 \over 13$, the first period of $13 \over 21$. The act of moving down to hit $8 \over 13$ changes one point, but moving back up to $13 \over 21$ undoes that change straight after.

Q6) Two approximants for $\sqrt{2}$ are given by $7 \over 5$, and $17 \over 12$, do the changes as you move between these two fit your intuition from $\phi^{-1}$? For the approximants of $\sqrt{2}$ given, something different does happen, although you may or may not have already built this into your model. The distance between the two approximants is sufficiently large that two points corresponding to the $7 \over 5$ approximant occur before $17 \over 12$ (specifically, the points $(5,7)$ and $(10,14)$), meaning that rather than one point hopping, as in the case of $\phi^{-1}$, we see two points hopping, instead.

Q1) By editing the coefficients of the continued fraction, convince yourself that, as you move down the fraction, increasing the coefficients alternately increases and decreases the value of the continued fraction. Can you work out why this is? Increasing the first (or, I guess, zeroth) coefficient of the continued fraction has a fairly obvious effect - we're just increasing a number out the front of the fraction: $$a_0+m+\frac{1}{a_1+...}$$ will always increase as $m$ increases - which holds even if $m$ isn't an integer. If we add $m$ to $a_1$, which gives us: $$a_0+\frac{1}{a_1+m+...}$$ increasing it increases something we're dividing by, and so decreases the result. What if we go deeper? Increasing $a_2$ gives: $$a_0+\frac{1}{a_1+\frac{1}{a_2+m+...}}$$ Increasing $m$ increases the amount we're dividing by in the fraction $\frac{1}{a_2+m+...}$, decreasing it and $a_1+\frac{1}{a_2+m+...}$, which in turn increases $\frac{1}{a_1+\frac{1}{a_2+m+...}}$. And if we add it deeper, the pattern repeats - every layer deeper we move, this same pattern happens, and adding something to the coefficient has the same alternating effect.

Q2) What's special about the value of the continued fraction at $r=0$ and $r=\infty$? Consider: $$F_2(r)=a_0+\frac{1}{a_1+\frac{1}{a_2+r}}$$ When $r=0$, this just gives us the second convergent fraction, $F_2$. However, when $r \rightarrow \infty$, $a_2+r \rightarrow \infty$, meaning that $\frac{1}{a_2+r} \rightarrow 0$, leaving us with $F_2(\infty) \rightarrow a_0+\frac{1}{a_1+0}=F_1$.

In other words, increasing $r$ sweeps out all gradients between the two approximants.

Q3) Does the resulting gradient for any other $r$ ever have a simpler fractional form (i.e. first hitting a point closer to the origin than those for $r=0$ and $r=\infty$)? Values of $r$ aside from $0$ and $\infty$ can never result in a simpler form. If $r$ has a fractional part, it simply adds extra depth to the continued fraction, forcing us to expand more terms, increasing complexity. If $r$ is, instead, a positive integer, increasing it increases the very first term we multiply up, increasing the first denominator and all which follow. No matter what we pick, the resulting fraction is more complicated.

Q4) As we move the remainder between $0$ and $\infty$, what changes occur in the structure (as usual, deduced from the first period) of the approximant we added the remainder to? As the slider is moved from $0$ to $\infty$, it never passes through a point between the two approximants aside from points corresponding to the approximants themselves, meaning the only change is the instant we decrease from $\infty$ (in general, depending on the order of approximant at which we dropped in the remainder, we might instead get a change when we hit the point $r=0$).

Q1) As we hop from approximant to approximant, how can we work out the structure of the next approximant from the previous, as well as from the continued fraction? We've already discussed this a bit, but now we have convergents available on which to base our approximants, we can be a little more specific. Most points don't shift as we move from approximant $(q_1,p_1)$ to approximant $(q_2,p_2)$, aside from points corresponding to one or other of the approximants (either $(q_2,p_2)$, itself, or $(nq_1,np_1)$, for integer $n$ such that $nq_1 \lt q_2$, as we found previously). Aside from these points (which we'll cover later), the structure of the next approximant is given by repeating the previous structure a certain number of times: $$W_{n+1} \approx \textrm{repeat} \; W_n \; \textrm{for} \; L_{n+1} \; \textrm{letters}$$ These approximant points are very significant in the early iterations, if you check this for yourself, but once the length of the word starts getting larger, they become less and less significant. In terms of scale, since the length of $W_n$ only ever increases with $n$, which means that deeper coefficients control the maximum power (number of consecutive repetitions) of subsequences at ever larger scales.

Q2) Thinking about your answer to the previous question, how do the coefficients of a continued fraction relate to the number of times we find repetitions of different lengths? When we create $W_{n+1}$, the previous word ($W_n$) will repeat $a_{n+1}$ times, before being cut-off part way through the next repetition, meaning that $W_n$ will repeat $a_{n+1}$ times consecutively. In fact, it turns out it can actually repeat more than this, but only twice more at most, corresponding to getting lucky with the structures which end up surrounding it on both sides, which, although they do break off the periodicity, may allow a single additional repetition on each side. For intuition, I'd suggest messing around with: $$W_{n+1}=W_nW_{n-1}$$ $$W_0=\textrm{LS}$$ $$W_1=\textrm{LSL}$$ where you can find that LSL will be repeated at most 3 times, for the same reason as above. We'll find out later that this particular example is actually equivalent to a quasicrystal with a gradient of $\phi^{-1}$.

Q3) Aperiodicity requires that no part of a structure, on any scale, repeats an arbitrarily large number of times. Why does this make the structure generated by $\phi^{-1}$ aperiodic? The continued fraction for $\frac{e-2}{3-e}$ is given by $$\frac{e-2}{3-e}=2+\frac{1}{1+\frac{1}{1+\frac{1}{4+\frac{1}{1+\frac{1}{1+\frac{1}{6+...}}}}}}$$ Is the structure generated by $e$ aperiodic? $\phi^{-1}$ is nice and aperiodic - its continued fraction contains only coefficients of 1, meaning that at most we can ever find 3 consecutive repetitions of any part of it. The fact that it has such an upper bound means that we've found a quasicrystal (it happens to be a hugely relevant quasicrystal, too, central to patterns in the Penrose tiling).

$\frac{e-2}{3-e}$ is not aperiodic, since it has arbitrarily large coefficients. Hence, whatever upper bound someone proposes for consecutive repetitions, by looking down the continued fraction, I can find a coefficient larger than that, corresponding to more consecutive repetitions. As a result, there's no upper bound on the number of repetitions in the structure of $\frac{e-2}{3-e}$, meaning its resulting structure isn't aperiodic.

Q4) Why might it sometimes be useful to view rational numbers as having a continued fraction truncated by a coefficient of $\infty$ (see below)? $$3+\frac{1}{7+\frac{1}{7+\frac{1}{\infty+...}}}=3.14$$ It doesn't matter what follows the $\infty$ (as long as it's positive or finite, anyway, which it will be for all continued fractions), since $\frac{1}{\infty+x}$ is definitely $0$. The reason this might be intuitively useful is that periodicity at particular scales is determined by continued fraction coefficient. A coefficient of $\infty$ for rational numbers makes it clear they repeat an infinite number of consecutive times by the same rules we use to judge maximum consecutive repetitions for irrational gradients.

Q1) What happens to these points when we move along by two approximants? (If you have been keeping track of what rounding up, rather than down, when generating a continued fraction, does, then think how this might relate to that). As we move from, say, $\frac{2}{3}$ to $\frac{3}{5}$ in the convergents of $\phi^{-1}$, we notice all the structure of $\frac{2}{3}$ is retained perfectly, aside from a single letter change corresponding to us hitting $\frac{3}{5}$. However, the second we move back up from $\frac{3}{5}$ to start moving towards $\frac{5}{8}$, that point gets crossed again, this time in the other direction. Intuitively, we could imagine that, rather than hitting $\frac{3}{5}$, we merely skim close to it, before returning back, never quite touching it. As a result, flipping points corresponding to the approximants of $\frac{3}{5}$ never actually make a difference. And the same will be true of any point: since we always return closer to $\phi^{-1}$ afterwards, meaning that the largest number of points we could ever be dealing with is simply $a_{n+1}$, the number of points equivalent to our current convergent before the next. As we find larger and larger structures, these at most $a_{n+1}$ points make up less and less of our overall structure, meaning we can, hope to be able to ignore it. (To be more precise, the first point where occurs tends towards being infinitely far away for irrational numbers).

Q2) Argue why, when we repeat this process many times, the number of points remaining affected should be bounded for quasicrystals, and that thus we should, roughly, find every other structure to be increasingly similar to: $$W_{n+1} = \textrm{repeat} \; W_n \; \textrm{for} \; L_{n+1} \; \textrm{letters}$$ Following on from the previous question, we simply repeat the previous structure $W_n$ until we reach the end of the first period of the next structure, which is at $L_{n+1}$. $$W_{n+1} = \textrm{repeat} \; W_n \; \textrm{for} \; L_{n+1} \; \textrm{letters}$$ The only difficulty arises from, as we've seen a few times now, points corresponding to either the current or previous convergent. Fortunately, we just showed that the problems due to these points don't accumulate, and so we only need to worry about points corresponding to either this or the previous convergent - in quasicrystals, the distance between these two (and hence the number of points corresponding to the simpler approximant) is bounded, and so the proportion of such points is $0$ as we tend to $\infty$.

Q3) Given $L_{n+1}=a_{n+1}L_n+L_{n-1}$, this corresponds to: $$W_{n+1} = W_n^{a_{n+1}} \; (\textrm{truncate} \; W_n \; \textrm{after} \; L_{n-1} \; \textrm{letters})$$ Why does this then give: $$W_{n+1} = W_n^{a_{n+1}}W_{n-1}$$ For this final step, note that, since: $$W_{n+1} = W_n^{a_{n+1}} \; (\textrm{truncate} \; W_n \; \textrm{after} \; L_{n-1} \; \textrm{letters})$$ then (just using $n-1$): $$W_n = W_n^{a_n} \; (\textrm{truncate} \; W_{n-1} \; \textrm{after} \; L_{n-2} \; \textrm{letters})$$ Substituting one into the other: $$W_{n+1} = W_n^{a_{n+1}} \; (\textrm{truncate} \; (W_n^{a_n} \; (\textrm{truncate} \; W_{n-1} \; \textrm{after} \; L_{n-2} \; \textrm{letters})) \; \textrm{after} \; L_{n-1} \; \textrm{letters})$$ This might not look much better, until we note that we're truncating something which begins with $W_{n-1}$ after $L_{n-1}$ letters. That's exactly the length of $W_{n-1}$, and hence that whole truncation just gives $W_{n-1}$: $$W_{n+1} = W_n^{a_{n+1}}W_{n-1}$$

Q4) In the case of $\phi^{-1}$, why might the resulting lattice be called the 'Fibonacci lattice'? For $\phi^{-1}$, after the initial $a_0=0$, all $a_n$ are equal to 1, meaning that we have: $$W_{n+1} = W_nW_{n-1}$$ or, in other words, the next word is the concatenation of the previous two, just as, for the Fibonacci numbers, the next number is the sum of the previous two (this also means the length is always a Fibonacci number).