Aperiodic structures and notions of order and disorder
Shelomo I. BEN-ABRAHAM
Department of Physics, Ben-Gurion University,
IL-84105 Beer-Sheba, IsraelandAlexander QUANDT
Department of Physics, Ernst-Moritz-Arndt Universität,
D-17487 Greifswald, Germany

Abstract
Artificial aperiodic structures have been recently the subject of extensive andintensive research resulting in layered quasiregular heterostructures as well as
photonic and phononic metamaterials with possible applications as optical andacoustic bandpassfilters and much more. Our main interest focuses on fundamental
questions about determinism, order vs. disorder, their possible quantification,complexity and entropy and beyond. We construct a two-dimensional instance of theProuhet-Thue-Morse system and compute its line complexity; it is at mostpolynomial and hence the entropy vanishes. We point out that the perfectly
deterministic Champernowne sequence has entropy ln 2 and hence entropy cannot
serve as an unqualified measure of disorder. Thus there remain many unansweredquestions.

1. Introduction
The motivation of our research is twofold: (1) Artificial aperiodic structures, suchas layered quasiregular heterostructures, have been the subject of intensive research
activities. Considerable progress has been achieved in recent years, where some of themost promising physical realizations of structures are photonic or phononic
metamaterials, mainly being applied as optical and acoustical bandpassfilters. The
fabrication of such structures is mostly governed by algorithms based on substitution
sequences (cf. [1, 2]).
(2) Our main interest focuses on fundamental questions about determinism, ordervs. disorder, complexity, entropy and beyond. The commonplace notions of "order"and "disorder" are heavily context-dependent and rather subjective. Even though inmost cases their meaning might be more or less clear, they are, in fact, not defined atall. In order to gain more insight into these fundamental issues, we undertook a studyof double-sided substitution sequences and their multidimensional generalizations.
The main topic of our analysis is their degrees of order vs. disorder. A rough measureis the topological entropy, but better insight might be provided by the symboliccomplexity. While in for the standard one-dimensional sequences these functions arewell known, little is known about their multidimensional counterparts (cf. [3-5]).
Here we present a generic instance of the two-dimensional Prouhet-Thue-Morsesystem (PTM) and compute its line complexity. It turns out to be at most polynomialand hence its entropy vanishes. We also briefly mention the more general notions ofrectangle as well as lattice-animals (polyominoes) complexity. For comparison wealso show a periodic example of 2D PTM.

Ben-Abraham, Quandt: Aperiodic structures and notions of order and disorder12. The algorithm
To construct our multidimensional sequences we essentially apply a recursivealgorithm put forward by Barbé and von Haeseler [6] but we significantly simplify it.
The recurrence equations for the one-dimensional double-sided PTM sequencewith the alphabet {1, −1}aret("2x) = t(x) ,(1)t("2x + 1) = "t(x) , x # Z ,t(0) = "1 , t(1) = 1 .
These equations can be readily generalized to n dimensions. For a start (and for acurrent experiment) we stay in 2D. We choose an expanding matrix M, a shift vectors and an entry x ∈ Z . !
The recurrence equations then aret(Mx) = t(x) ,(2)!

t(Mx + s) = t(x) , x " Z 2 ,t(0, 0) = #1 .

The particular instance of the sequence thus produced depends on the matrix M . For
the present example we choose#"1 "1&!
M=%(3)(.
$ 1 "1'After 13 iterations this produces a patch shown in Fig.1. It contains 213 = 8192
points. It is chiral and anorthotropic; it should be noted that this is the generic case.
The patch is also fractal; that! is intrinsic to the algorithm which jumps back and forthand leaves holes to be filled in later stages.

Fig.1. Patch of 2D PTM after 13 iterations containing 213 = 8192 points.
This example is generic, anorthotropic and fractal.

Ben-Abraham, Quandt: Aperiodic structures and notions of order and disorder2

To construct a periodic 2D PTM structure just change the matrix M to#0 "2&
M=%
(4)
(.
$1 "1'
After 13 iterations this produces a patch shown in Fig.2. It contains 213 = 8192
points. It is also chiral and anorthotropic and fractal..

!

Fig.2. Patch of 2D PTM after 13 iterations containing 213 = 8192 points.
This example is periodic, anorthotropic and fractal.
As an illustration of the possibility to generalize to higher dimensions we show inFig.3 a three-dimensional example.

Fig.3. A 3D example of PTM.

Ben-Abraham, Quandt: Aperiodic structures and notions of order and disorder33. Determinism, order and disorder
Physicists, chemists and material scientists often loosely speak of "order" and"disorder". In most cases it is more or less clear what is meant. Yet, these terms,
while being rather intuitive, are strongly context-dependent and, in fact, not defined atall. They somewhat resemble the notions of "hot" and "cold". Yet hot electrons arequite different from hot tea or a hot onsen (with apologies for the double adjective).
Cold atoms are not the same as cold weather, and even that is different in
Ouagadougou, Kyoto and Oymekon. Hence, "cold and hot" have been quantified
long ago. They can be given a precise meaning by defining temperature, which, ofcourse, can be equivalently measured in units of energy, frequency or wave number.
The concept of entropy as a measure of disorder was invented in the 19th century
by Clausius and interpreted in statistical terms by Boltzmann and later introduced into
the mathematical literature by Kolmogorov. We note in passing that there are several
slightly different definitions of entropy. Strictly speaking, here we deal with
topological entropy. Again, instead of entropy one might use the concept ofinformation equivalent to negentropy invented by Shannon.
Unfortunately, it turns out that entropy is insufficient to characterize the structuresin question. More revealing and detailed is symbolic complexity, a function pS(n)counting the number of words of length n in a given sequence S [7-10].
In terms of complexity the entropy is defined asln pS (n)H ( S ) := lim
(4)
.
n !"
nLet us quote a few simple examples of sequences with low complexity. For thesequences 1010… (abbreviated to 10), Fibonacci (F) and Golay-Rudin-Shapiro (GRS)
we, respectively, have:(5)

p1010…(n) = 2 for all n ,(6)pF = n + 1 for all n ,(7)pGRS = 8(n – 1) for n ≥ 8 .

On the other hand, the perfectly deterministic Champernowne (Ch) sequence hascomplexity(8)npCh = 2 for all n ,the same as fair Bernoulli and hence the entropy of both is H(B) = H(Ch) = ln 2. This
seems to be a paradox. It was explained by Baake: the structure of Ch is byconstruction such that all permutations of any length n must appear in it [11]. The
Champernowne number, i.e. the sequence Ch interpreted as the representation of anumber is a normal number that is one where (in the given representation) all digits
are uniformly distributed [12, 13]. The notion of a normal number is by itself
somewhat paradoxical: a generic real number is supposed to be normal but it is hard
to find one.
Thus we are confronted with a number of challenging questions. Is determinism
equivalent to order and in what sense? In crystallography, according to the current
consensus, long range order of structure is defined as the presence of a pure point partin the diffraction spectrum which reflects the existence of a non-vanishing two-pointautocorrelation. In our opinion, this definition is not general enough. It excludes, forinstance, the PTM case (cf. [14]).

Ben-Abraham, Quandt: Aperiodic structures and notions of order and disorder4

On the other hand, we see that entropy cannot distinguish between genuine
stochastic disorder and deterministic deviation from uniformity, at least in some cases.
Moreover, entropy is blind to dimension; for instance, all Bernoulli structures on anyd have the same entropy ln 2 . Thus we need a more revealing global measure ofdeviation from uniformity as well as clear-cut measure of stochasticity versus
determinism.

4. Complexity of PTM − an example
Eventually we computed the symbolic complexity of the generic example shownin Fig.1. We started by exploring lattice animals (alias polyominoes) on the structure.
We quickly learned a few things. Already some animals of low order appeared only
in one enantiomer and/or either in horizontal or vertical position. Thus the pattern
was indeed proven to be chiral and anorthotropic.
However, the numeric effort to find animals of higher order proved to be quitedisproportional. Thus we compromised and restricted our search to the complexityp(m, n) of rectangles of size N = m× n [15, 16]. Moreover, to gain rapid insight wefocused on the complexity of lines p ℓ (N), i.e. rows p r (N, 1) and columns p c (1, N).
The computed results again confirmed the anorthotropy of the pattern. The recursion
makes the pattern fractal. The computed complexity up to N = 20 is shown in theTable. The complexity turns out to be approximately quadratic and thus polynomial
at most; hence the entropy vanishes.
The result again raises some questions. Does the complexity depend on theparticular instance of 2D PTM? The answer seems to be positive. If so, how does it
depend on the particular class of realizations (cf. [6]), or else, on the choice of thegenerating matrix M ? Is there a canonical instance of 2D PTM?

Ben-Abraham, Quandt: Aperiodic structures and notions of order and disorder5

Table – Symbolic complexity of 2D PTM.

Nrows
p r (N,1)

columnsp c (1,N)

total lines
p ℓ (N)N2123
456789101112131415
16
171819202∗
46810141824
283440
4652
60
68
76
84
94
104
122

2∗
4610142026
34
42
52
70
90
108
130
156
186
208
236
264
292

2∗
81218
2434
44
58
70
86
110
136
160
190
224
262
292
330
368
414

1
4
916253649
64
81
100
121
144
169
196
225
256
289
324
361
400

∗) The entries for N = 1 are exceptional since rows and columns are the same: (1,1).

4. Conclusions and outlook
The symbolic complexity of the two-dimensional Prouhet-Thue-Morse structure is
at most polynomial. This is probably so in higher dimensions as well. Hence theentropy of 2D PTM vanishes and we conjecture that this is also true for nD PTM.
We are presently working on other instances of PTM, other 2D sequences and try toextend the study to higher dimensions. And, of course, we intend to extend thecomputation of complexity to higher N and non-trivial rectangles. We will also try
other algorithms, mainly direct substitution.
Our study raises more questions than answers. Can one find put forward acanonical instance of 2D PTM (or any other multidimensional substitution system) ?
If so, can we find a formula for the complexity ? And most important of all: improve
our understanding of determinism, order, disorder, stochasticity and their proper
quantification.

Ben-Abraham, Quandt: Aperiodic structures and notions of order and disorder

6

References[1] García-Moliner F., Quasiregular heterostructures,
Microelectronics J. 36 (2005) 870-876.
[2] Steurer W., Sutter-Widmer D., J. Phys. D: Photonic and phononic quasicrystals,J. Appl. Phys. 40 (2007) R229-R247.
[3] Allouche J.-P., Shallit J., Automatic sequences: Theory, applications,generalizations, Cambridge University Press, New York 2003.
[4] Sloane N.J.A., On-line encyclopedia of integer sequences,
http://www.research.att.com/~njas/sequences/.
[5] Baake M., Grimm U., Theory of aperiodic order − a mathematical invitation,
Cambridge University Press, New York (in preparation).
[6] Barbé A., von Haeseler F., Correlation and spectral properties ofmultidimensional Thue-Morse sequences,[7] Berthé V., Conditional entropy of some automatic sequences,J. Phys. A: Math. Gen. 27 (1994) 7993-8006.
[8] Berthé V., Entropy in deterministic and random systems,
in Beyond quasicrystals, F. Axel and D. Gratias (eds.),
Springer-Verlag, Berlin-Heidelberg-New York / EDP Sciences, Les Ulis 1995.
[9] Ferenczi S., Complexity of sequences and dynamical systems,
Discrete Math. 206 (1999) 145-154.
[10] Berthé V., Vuillon L., Suites doubles de basse complexité,J. Théor. Nombres Bordeaux 12 (2000) 179-208.
[11] Baake M., Comment at ICQ11 Satellite Mathematics of quasiperiodic order,
Kyoto, June 2010.
[12] Borel E., Les probabilités dénombrables et leur applications,Rendiconti del Circolo Matematico di Palermo 27 (1909) 247-271.
[13] Champernowne D.G., The construction decimals normal in the scale of ten,J. London Math. Soc. 8 (1933) 254-260.
[14] van Enter A.C.D., Miękisz J., How should one define a (weak) crystal ?,J. Stat. Phys. 66 (1992) 1147-1153.
[15] Sander J.W., Tijdeman R., The complexity of functions on two-dimensionallattices, Theor. Comp. Sci. 246 (2000) 195-225.
[16] Sander J.W., Tijdeman R., The rectangle complexity of functions on lattices,Theor. Comp. Sci. 270 (2002) 857-863.

Ben-Abraham, Quandt: Aperiodic structures and notions of order and disorder7