# Quasiperiodicity of the Fibonacci chain

I am interested in finding an intuitive way to show that the Fibonacci chain is quasiperiodic (and not simply random). Or put differently, how can I tell from just looking at a given chain whether or not it is quasiperiodic?

Let us consider the construction of the Fibonacci chain. We act with the following substitution rule \begin{eqnarray} S &\rightarrow& L\\ \nonumber L &\rightarrow& LS \end{eqnarray} many times on a starting letter, e.g. $L$, in order to construct a long word (=chain). The second line means the replacement of one letter $L$ by two letters ($L$ and $S$). This leads to the aperiodic word (Fibonacci chain) of the following form \begin{eqnarray} L \rightarrow LS \rightarrow LSL \rightarrow LSLLS \rightarrow LSLLSLSL \rightarrow LSLLSLSLLSLLS \rightarrow \dots \end{eqnarray}

I can prove that this word is indeed aperiodic (see also this question). Also, it is clear that it is not random since we used a rule (not a random number generator) to construct the sequence.

Now I am going convert this word into a (fictious) physical atomic structure ('quasicrystal'). The atoms sit in between the long ($L$) and short ($S$) segments.

How can I easily show that it is quasiperiodic?

I know that quasicrystals are defined by having sharp diffraction peaks. So I can numerically (or analytically) calculate the diffraction pattern from the Fibonacci chain. In this case I calculated the Fourier transform of a Fibonacci chain with 21 segments, namely $$L, S, L, L, S, L, S, L, L, S, L, L, S, L, S, L, L, S, L, S, L$$ with $S = 1$, $L =$ golden mean and I see it has sharp peaks:

Then I compare it to that of a pseudorandom chain $$S, L, S, S, S, S, L, S, S, S, L, L, S, L, S, L, S, L, S, S, S$$ which is generated randomly.

Ok, one could argue these peaks are not as 'sharp' as in the QC case but this depends a lot on the definition of 'sharp' (or, rather, 'discrete'). Also, I know that my example is probably not very well-defined because on a 21-long chain the difference between random and quasiperiodic might be hard to pin down. However, it would be nice to find a more elegant argument without me having to zoom into the diffraction pattern of extremely long Fibonacci/random chains (which cost a lot of numerical effort) to show the difference.

For example, could there be an argument along the lines of 'almost periodic' which is nicely illustrated here, section 5.2?

I would like to keep self-similarity out of the discussion here because, in principle, any Fibonacci sequence (not just the typical self-similar one I took with $S = 1$ and $L$ = golden mean) should be quasiperiodic.

• Would this be a question for Math SE? – Steeven Sep 7 '18 at 15:08
• @Steeven yeah, maybe. But I was also hoping for some intuitive argument from the physics point of view. Also, quasicrystals were studied in material science, crystallography, physics, chemistry, maths, etc. so I felt physics is the most general audience. But if I don't get anywhere here I may post it on Math SE. – Quasilattice Sep 7 '18 at 15:48
• The crystallographic part of this question places it within physics, although the theoretical work on quasicrystal (including the diffraction) is squarely math. Suggest OP start by searching work by M. Baake or Uwe Grimm, or Suck, J-B., Michael Schreiber, and Peter Häussler, eds. Quasicrystals: An introduction to structure, physical properties and applications. Vol. 55. Springer Science & Business Media, 2013. – ZeroTheHero Sep 8 '18 at 12:02
• @ZeroTheHero thanks for the literature recommendation. The mathematical works on QC that include randomness (e.g. arxiv.org/abs/math-ph/9901014, section 13) are largely focussed on the famous 'stability problem' (Are quasicrystals energy- or entropy-stabilised?). It even mentions my random chain example but simply states 'the [random] ensemble is so random that the typical ensemble member does no longer show sharp diffraction peaks'. That is precisely the questions: Does or does it not show sharp diffraction peaks? And why? – Quasilattice Sep 8 '18 at 18:13

I do not know the answer, but this could be a potential start for a further discussion.
If anything I do think it helps in giving an intuitive picture.

I am not going to look at the diffraction patterns, just as the sequence of $L$ and $S$ that you are quoting. Though I am $90$%$^\ast$ sure that you can apply what I've done here to your diffraction pattern just by applying a Fourier transform.

A typical statement that it is made about quasicrystals is the following$^{\dagger}$:
in a regular crystals, you know that you are going to get the exact same patch $\mathcal{P}$ if you look $n\cdot$lattice spacings away, or if you rotate by the required angle.
In quasicrystals, the "order" that you introduce with the matching rule results in you being able to find the same patch $\mathcal{P}$ elsewhere in your pattern, but not knowing where exactly.

In this context, let me proceed.

The following was generated with Mathematica code, and let me thank @Henrik Schumacher from the Mathematica Stack Exchange for helping me get my ideas to fruition.

• a) $LS$ series constructed from your rules (up to the 11th generation): $$L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,S,L,L,S,L,L,S,L,S,L,L,S,L,L,S$$

• b) $LS$ series constructed from a random generator (RandomChoice), with the same number of elements as above ($= \frac{F_n + L_n}{2}$, F and L):

$$S,S,L,S,S,S,S,L,S,L,S,L,S,L,L,L,S,S,S,S,S,S,L,S,S,S,S,S,S,L,S,L,L,L,L,L,L,S,S,L,S,S,S,L,S,S,S,S,S,L,L,L,L,L,S,S,S,L,S,S,S,S,S,L,S,S,S,S,S,S,L,S,L,L,S,L,S,S,L,L,S,L,L,S,S,S,S,S,S,S,L,S,S,L,L,L,S,S,L,L,S,L,L,S,S,S,L,S,S,L,L,L,S,L,L,S,L,L,L,S,L,L,L,L,L,L,S,L,L,L,L,L,L,S,S,S,L,L,S,S,S,L,S,L,L,L,L,L,L,L,S,L,L,S,L,L,S,S,S,L,S,L,L,S,S,L,S,S,S,S,L,L,S,L,L,S,S,L,L,S,L,S,L,S,S,S,S,L,S,L,S,S,L,L,S,L,S,L,S,L,S,S,S,S,L,L,S,L,L,L,S,L,L,S,S,L,S,S,S,L,S,L,S,S,L,S,S,L,S,S,L,L,L$$

• Now I am going to search through both sets for a string that I know occurs in (a), say ${L, L, S, L, L, S, L, S, L, L, S, L, S}$.

I find that it occurs $12$ times in (a), and never in (b)

• Let me now try with a shorter string, so that I can find something in (b) as well, say ${L, L, S, L, L}$.

I find that this string occurs $21$ times in (a) and $6$ times in (b).

However, if I count the number of letters between each block occurrence of the string, I see that:

• in a: ${9, 4, 9, 9, 4, 9, 4, 9, 9, 4, 9, 9, 4, 9, 4, 9, 9, 4, 9, 4}$

• in b: ${66, 65, 21, 4, 30}$

which I think gives an intuitive idea that we have "recovered" which of the two series was built based on rules and which was generated at random. Though I have not though about it too much, I don't know why the series of $9$ and $4$ seems to be periodic...

$\ast$: arbitrary
$\dagger{}$: proper reference needed

There are also some arguments here which might be useful in seeing how there are "rules" and determinism behind the Fibonacci chain.