# Why do quasicrystals have well-defined Fourier transforms?

I was recently reading about quasicrystals, and I was really surprised to learn that even though they do not have a periodic structure, and only have long range order in a very different sense to the usual one, they can still be detected via crystallographic techniques that involve Bragg diffraction patterns.

More specifically, quasicrystals are like Penrose tilings in that

It is self-similar, so the same patterns occur at larger and larger scales. Thus, the tiling can be obtained through "inflation" (or "deflation") and any finite patch from the tiling occurs infinitely many times.

The emphasized text also means that if I have a finite patch of quasicrystal to which I want to add atoms to make the full pattern, then there will be an infinite number of different ways to do this. Therefore, the process of adding atoms to a finite patch is not deterministic: it is constrained by certain rules but there is always some choice.

To be more precise about what weirds me out, I feel this 'skips' an intermediate step. I can imagine there being a tiling which is not periodic but which is nevertheless deterministic in that given a starting 'seed' patch the whole pattern is determined. In such a pattern there is no translation invariance but there is nevertheless a very rigid sense of long-range order.

Edit:

I was recently shown a construction that falls in this case. Consider the discrete one-dimensional point set $\mathbb Z\cup r\mathbb Z=\{\ldots,-1,0,1,\ldots,\ldots,-r,0,r,\ldots\}$ where $r$ is irrational. This set is not periodic (although any finite patch has infinite other patches that are arbitrarily similar to it), but it does have a well-defined Fourier transform: it is simply the sum of the transforms of $\mathbb Z$ and $r\mathbb Z$, which are single peaks. However, given an initial patch of length bigger than $r$ and $1$, the rest of the pattern is completely determined, and the long-range order is "rigid" without the pattern being periodic.

For quasicrystals, on the other hand, the local orders of two distant patches are definitely correlated but only loosely so. This being the case, I'm having some trouble visualizing how it is possible to obtain diffraction patterns from them, and understanding whether they have well-defined Fourier transforms.

To bring this question to a more, precise footing then, let me ask this: given a starting patch of quasicrystal and a (non-deterministic) rule for adding atoms to it, is the Fourier transform of the full, infinite pattern well defined? If so, what's the intuition that allows this to happen?

If this is actually way more complicated than I realize I would also be OK with a reference to an entry-level resource on the subject, but I would really like a nice explanation of this.

-
Here is a nice article. ams.org/notices/200608/whatis-senechal.pdf – MBN Oct 30 '13 at 17:35
We can produce quasiperiodic tilings by projecting a hypersurface in a higher dimensional crystal (real, not quasi) lattice onto suitable hyperplane. This does allow calculation of Fourier spectra analytically. – user23660 Oct 31 '13 at 7:18
@user23660 Have you got a good reference for that? – Emilio Pisanty Oct 31 '13 at 12:54
One place to start is Gahler, Rhyner. J. of Phys. A, 19.2 (1986): 267. (doi:10.1088/0305-4470/19/2/020) online. It is somewhat dated, but has both construction of tilings and Fourier transform. – user23660 Oct 31 '13 at 13:36
Probably off-topic for your particular question, but this Wiki paragraph is interesting . I find also this recent presentation, and this curious article. – Trimok Feb 6 '14 at 19:37

[I am not really the best person to answer this, but since nobody else is answering here is my best shot]

given a starting patch of quasicrystal and a (non-deterministic) rule for adding atoms to it, is the Fourier transform of the full, infinite pattern well defined?

In summary it depends on the rule. [It may also be a tautology since quasi-crystals are required to have well defined discrete spectra by definition, but I assume that is not important here]

In more detail the Fourier transform or spectrum of a pattern is only a function of the pattern, regardless of how it was produced. The question is how do the rules constrain the possible final configurations and thus their Fourier transforms. A non deterministic process can conceivably produce a perfectly regular pattern with a simple spectrum. If a process is sufficiently nondeterministic it may lead to perfectly regular on some runs and wildly complex patterns on others, in which case the rules of the process would not really tell us anything about the final spectrum. At another extreme the process may be such that the final pattern is the same regardless of the non deterministic choices made along the way which only affect the order in which the pattern is produced, in which case the spectrum is fixed by the rules of the process. In between you get systems where the space of final patterns is large but has regularities which are reflected in the spectra. Real process have probabilities associated with their nondeterministic choices, which leads to a probability density function on the final patterns and on the spectra. Probabilistic rule lead statistical regularities in the produced patterns and their spectra. The classic examples of this are white, pink and brown noise. These are random processes whose final pattern in the time domain is unpredictable but their spectra are well defined and have a high degree of regularity in that their amplitude-frequency relationships follow specific power laws. I do not know how the processes producing quasi-crystals produce the particular spectra they do, except that they must be biased to producing paterns with approximate symmetries that cannot be realized exactly by regular crystals, @user23660's comment and reference look like promising pointers

Edit

Some examples to illustrate the ideas described above, as requested in the comments:

For a very simple example of an eventually/asymptically deterministic system start with a square lattice that has an "atom" at the origin. The rule is to put an atom on an empty spot next to an existing atom with equal probability. In the long run you will end up with a mostly symmetric, mostly convex blob around the origins with some variations in the exact shape of the boundary between runs, but for very long runs the result will be essentially the same.

For types of stochastic patterns where all indidviduals are distinct but have large scale regularities which produce recognizable spectra consider natural patterns sand dunes, tree bark, girraffe spots, finger prints and other kinds of textures. Quasicrystals & Penrose tilings are vaguely similar to this, but that they are made of components that are perfectly regular.

For a system that can produce any kind of pattern, simple or complex, you can take the rule to put an atom anywhere. You can then put the atoms in a regular arrangement or chaotically. This is a cheat though becauuse if you made the rule probabilistic the probaility of getting a regular pattern is virtually 0. You would almost certainly get a random pattern, but I think it would still have a well defined spectrum the same way white noise does.

Unfortunately I do not have a good simple example of a probabilistic system that is likely to produce both complex and regular patterns with significant probability. Fluid dynamics is a real systems that is somewhat like that: you get laminar flow at low Reynolds number but become increasingly turbulent as Reynolds number increases. It may also help to think about Conway's Life. It is deterministic, of course, but depending on the starting configuration it can produce almost any kind of behaviour, so the rules do not really tell you what kind of pattern, and thus spectrum, you will get in the long run and, since Life is actually Turing complete, you can not predict the eventual patterns even if you have the initial configuration, except by essentially running the rules. This is due to the undecidability the reachability problem for Turing machines.

It may help to look at (stochastic, asynchronous) cellular automata. Stephen Wolfram's New Kind of Science has many examples of discrete systems on the order chaos boundary. Here is also a talk by Wolfram.

-
I see. So one thing I had wrong, then is that even with different, nondeterministic choices, you can still always end up with the same global pattern. Could you add in examples for the different classes of processes you describe? – Emilio Pisanty Feb 7 '14 at 19:11
Ok, but that was just meant as an abstract pedagogical example. Real quasicrystals are not like that. They are more like the noise examples where the patterns differ in detail but statistically show global regularities between runs. – Daniel Mahler Feb 7 '14 at 19:18
To be honest, I'm equally puzzled both by real quasicrystals as idealized mathematical ones. I'm not sure, though whether my assertion that things like the Penrose tiling is in fact nondeterministic. Is that the case? (or how does that work, if not?) – Emilio Pisanty Feb 7 '14 at 19:57
I believe the rules for building up Penrose tilings are usually non-deterministic. One kind of Penrose tiling has rhombus shaped tiles with some curves drawn on top of them and you have to attach each tile in a way that makes the adjacent curves line up. You can locally attach tiles in different ways, but as long as you satisfy the constraint the global structure will be a aperiodic.The wikipedia article on Penrose tilings seems to have good examples. – Daniel Mahler Feb 7 '14 at 20:25