Quasicrystals and the Dual grid method [Archive]

tessel@tum.bot

Jun24-04, 06:31 AM

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>On Sat, 12 Jun 2004, BA wrote:\n\n> I\'m looking for an analytic expression for the diffraction (Fourier\n> transform) of 2D quasicrystals genertaed by the Dual Grid Method.\n\nI\'m curious to know more about your interest in "quasicrystals" and the\n"dual grid method"! Are you more interested in the mathematical aspects\n(e.g. connections with ergodic theory, noncommutative geometry, and\nlogic), or in physical quasicrystalline materials?\n\nI assume you know that there is no universally accepted mathematical\ndefinition of a "quasicrystal", and also that what you call the "dual grid\nmethod" is identical with the "multigrid method" for obtaining "Sturmian\ntilings" (aka "generalized Penrose tilings") which was introduced by de\nBruijn:\n\nauthor = {N. G. de Bruijn},\ntitle = {Algebraic Theory of {P}enrose Tilings of the Plane},\njournal = {Indagationes Mathematicae},\nvolume = 43,\nyear = 1981,\npages = {38--66}}\n\nauthor = {N. G. de Bruijn},\ntitle = {Dualization of Multigrids},\njournal = {Journal de physique},\nvolume = 47,\nyear = 1986,\npages = {9--18}}\n\nIf so, you are no doubt aware of the "projection method", but perhaps not\nof a third equivalent method, the "oblique tiling method", which was\nintroduced in\n\nauthor = {Christophe Oguey and Michel Duneau and Andre Katz},\ntitle = {A Geometrical Approach of Quasiperiodic Tilings},\njournal = {Communications in Mathematical Physics},\nvolume = 118,\nyear = 1988,\npages = {99-118}}\n\nThe oblique tiling is a -periodic- tiling (-not- a "face-to-face"\ntiling!); its "prototiles" consist of a finite list of parallelotopes\n(multidimensional generalization of rhombus) in a higher dimensional\neuclidean space, and then taking slices parallel to certain of the faces\nof the tiles. (See the picture in the above mentioned paper to see,\nliterally, why the slices are -quasiperiodic-!)\n\nAll three methods involve the choice of an n-dimensional subspace W of E^r\n(where r > n). The orthogonal subspace W^perp also plays a critical role.\nFor example, in the projection method, the "window" is a polytope in\nE^(r-n), but the tiling itself lives in E^n.\n\nEach tiling constructed by any of the three methods belongs to a certain\ntiling space. All of the tilings contained in a given tiling space are\n"locally indistinguishable" (which is why these tilings provide, for Alain\nConnes, key examples of "noncommutative geometries"). In particular, they\nall have the same infinite list of "allowed patches" and the same patch\nfrequencies (this notion does make sense, but justifying this takes some\nexplanation, which I\'ll omit).\n\nAt a still higher level of structure, we can consider the "superspace" of\nall tiling spaces associated with the choice of a particular n-dimensional\nsubpace W of E^r, for particular positive integers (n,r) where r > n, and\nit is then natural to ask how properties of the tiling spaces vary as we\nvary our choice of W, i.e. as we move through this superspace.\n\nThe hillman mathbot (of which I am a dumbed down "student version"!) wrote\na Ph.D. dissertation on Sturmian tiling spaces (aka "generalized Penrose\ntiling spaces"), principally relying on the oblique tiling construction.\nI don\'t have a copy of this document at hand, but IIRC it\n\n1. carefully distinguished various levels of structure which are often\nconfused in the literature, including:\n\na. measure-theoretic features (e.g. frequencies of allowed patches) versus\nunderlying combinatorial features (e.g. allowed versus forbidden "patches"\nof tiles),\n\nb. translation by R^n versus vectors arising from a certain algebraic\nnumber field over Q defined by a given Sturmian tiling space,\n\nc. protopatches versus patches, and in particular protoempires versus\nempires,\n\n2. discussed various "organizing principles", including:\n\na. a natural hierarchy of smaller dimensional Sturmian tiling spaces\nobtained from the "walls" of the tilings contained in a given tiling space\n(walls are the natural multidimensional generalization of "ribbons", for\nwhich see the discussion in Grunbaum and Sheppard),\n\nb. the empire/cylinder duality, which is completely general (i.e. applies\nto a very general notion of "symbolic dynamics"),\n\nc. another elementary "duality" defined between certain Sturmian\nsuperspaces,\n\n3. answered some natural questions:\n\na. characterize the types of "singular tilings" which can arise in\nSturmian tiling spaces, and construct explicitly examples illustrating\neach possibility,\n\nb. characterize the types of "periodicities" which can arise (some\nSturmian tilings are periodic along certain directions--- if so they are\ngenerally "transversely periodic"), and construct explicitly examples\nillustrating each possibility,\n\n(this turns out to related to the problem: characterize the types of\n"rotational symmetry" which can arise, and construct explicitly examples\nillustrating each possibility),\n\nand partially answered some further questions, including:\n\nd. characterize the types of "inflation maps" which can arise, and\nconstruct explicit examples illustrating each possibility,\n\ne. at the level of combinatorial structure, characterize for example the\ntypes of allowed patches which can arise, construct explicit examples\nillustrating each possibility, and explain how these vary (in particular,\ncharacterize the bifurcations) as you move through the appropriate\nSturmian superspace,\n\nf. at the level of statistical (measure-theoretic) structure, characterize\nfor example the patch frequencies which can arise, construct explicit\nexamples illustrating each possibility, and explain how these vary (in\nparticular, characterize the bifurcations) as you move through the\nsuperspace,\n\n4. discussed various open problems, of which I now remember only an\namusing problem involving the causal structure of two dimensional\ncombinatorial spacetimes obtained from Penrose tilings.\n\nNow, the obvious "running example" in any discussion of Sturmian tilings\nis of course provided by Penrose tilings, so I should say something about\nhow the above works out for this example.\n\nThe Sturmian tiling space of Penrose tilings contains precisely the\ntilings obtained by Penrose\'s original construction via "inflation", or\nfrom any of the three constructions above. In particular, it is\nassociated with a particular oblique tiling, a periodic tiling of E^5.\nBut the Penrose tiling space is very special in that, as just mentioned,\nit admits an "inflation map" associated with a linear operator acting on\nE^5. This is closely connected to another special feature: the five-fold\n"local rotational symmetry" which is obvious upon inspection of any (=\nall!) Penrose tiling. Both phenomena reflect the fact that the oblique\ntiling for the Penrose tiling space can be defined from the invariant\nsubspaces of the obvious "five-cycle" R on E^5. This linear operator\npossesses an invariant line and two invariant two-planes in which R\neffects a 1/5 and 2/5 turn respectively. The tiles of the periodic\noblique tiling have edges contained, up to translation, in these invariant\nspaces, and the R^2 in which the actual Penrose tilings are constructed\ncorresponds to the two-dimensional invariant subspace in which R effects a\n1/5 turn.\n\nThe "dual" of the Penrose tiling space is a Sturmian tiling space of 3d\ntilings which are -periodic- in one direction, but transversely\nquasiperiodic. As such, it actually belongs to another Sturmian\nsuperspace, the one in which n, r-n have switched roles. (Physicists\nmight say that "window space" and "physical space" are interchanged by the\nduality we are discussing.) In the Penrose example, this duality is again\nvery closely connected to the "local rotational symmetry" and the\n"inflation map", but duals are defined for any Sturmian tiling space, and\nthere are neat relationships between the singularities, periodicities (and\nother combinatorial/statistical features) of a Sturmian tiling space and\nits dual.\n\nNow for some more generalities: as you may know, it turns out that one\ndimensional Sturmian tilings have a very close connection with simple\ncontinued fractions and the Euclidean algorithm (greatest common divisor).\nThe hierarchy of walls mentioned above generalizes this to any Sturmian\ntiling space. For example, simple continued fractions and ribbons give\nthe whole story on finding constructively, explicitly, and even\nefficiently, the "magic shifts" (aka "almost periods") of a given Sturmian\ntiling space (all tilings in a given space share the same magic shifts).\nHere, the magic shifts form an infinite sequence of longer and longer\ntranslations (parallel to the edges of the tiles) which mimic true\nperiodicity better and better, in the sense that if you translate any\nPenrose tiling by p[n], you will observe agreement over 85% of the plane,\nand if you translate by p[n+1], over 95% of the plane, and so forth.\n\nOne can also construct a sequence of periodic approximations to any\nSturmian tiling. Here, the tiles themselves are not quite isometric to\nthe original tiles, but at the combinatorial level one could use the\noriginal tiles, so that one can think of these as periodic approximations\nin the sense of symbolic dynamics. For example, one can find a -periodic-\nrhomb tiling which, up to a certain size of patches, has precisely the\nsame tile frequencies (measure-theory level) and allowed patches\n(underlying combinatorial level) as the real thing, but if you examine\nlarger patches you can find patches which are (at the combinatorial level)\nforbidden in genuine Penrose tilings. "Later" periodic approximations in\nthe sequence are perfect mimics (combinatorially) within -larger- windows,\nand you can go as far as you like.\n\nThe more general notion of "combinatorial approximations" goes to the very\nheart of symbolic dynamics and the combinatorial content of Shannon\'s\ninformation theory. See also\n\nauthor = {William Geller and Jim Propp},\ntitle = {The Projective Fundamental Group of a \\$\\Z^2\\$-Shift},\njournal = {Ergodic Theory and Dynamical Systems},\nyear = 1995,\npages = {1091--1118}}\n\nbut note that it is perhaps more natural to study non-Hausdorff sheaves,\nrather than the branched manifolds considered by Geller and Propp. Among\nother things, this should facilitate a very general notion of symbolic\ndynamics in which we will find many connections with topos theory, logic,\nand other things of current interest to certain mathematicians,\nphysicists, and philosophers.\n\nTo sum up: Sturmian tilings are essentially a geometric realization of\ndiophantine phenomena which arise in studying multidimensional rational\napproximations of linear relationships. (This characterization can be\ntraced back to work of Klein and Minkowski at the turn of the last\ncentury; their work far anticipated the quasicrystal craze.) Of course,\nthis is in some sense already obvious from the original paper by de Bruijn\nintroducing the general multigrid construction!\n\nI should mention one more generality: at the cost of losing the\nequivalence between the projection, multigrid, and oblique tiling methods,\nwe can greatly generalize the projection method to construct more general\nquasiperiodic tiling spaces. One way of doing this is closely related to\nMeyer\'s beautiful theory of "harmonic sets" (the same notion which\neventually turned out to be needed for "wavelets"); see\n\nauthor = {Robert V. Moody},\ntitle = {{M}eyer Sets and their Duals},\nbooktitle = {The Mathematics of Long-Range Aperiodic Order},\nnote = {Proceedings of the NATO Advanced Study Institute, The Fields\nInstitute, Waterloo, Ontario, Canada, August 21-- Sept. 1, 1995},\neditor = {Robert V. Moody},\npublisher = {Kluwer},\naddress = {Boston},\nyear = 1997}}\n\nBTW, in this paper, Moody states an interesting problem (AFAIK still open)\nwhich should appeal to anyone who follows John Baez\'s "This Week" series:\nwrite down an appropriate definition of a "morphism" which turns harmonic\nsets into "objects" in a useful/interesting category.\n\nOK, now for the bad news: I might be able to help with some of the above,\nbut unfortunately, I don\'t know very much about -diffraction phenomena- in\nquasicrystals. Fortunately, diffraction is probably the aspect of\nquasicrystals which has been most studied in the literature. I suggest\nthat you try to contact these approachable experts: Michael Baake,\nCharles Radin, and Boris Solomyak. Baake is a mathematical physicist;\nRadin and Solomyak are ergodic theorists.\n\nAt a more elementary level, the discussion of diffraction in the\nundergraduate textbook\n\nauthor = {Marjorie Senechal},\ntitle = {Quasicrystals and Geometry},\nnote = {Beware of the uncorrected hardcover edition},\nedition = {Paperback},\npublisher = {Cambridge University Press},\nyear = 1996}\n\nmight be useful. (This book also has a large bibliography.)\n\nYou can also search the ArXiv, e.g. I just found this fairly recent paper:\n\nhttp://xxx.lanl.gov/abs/math-ph/0105010\n\nI haven\'t had a chance to look at it, but I\'d guess there should be some\nconnection with the ideas discussed by Moody in the paper I cited above.\n\n"T. Essel" (hiding somewhere in cyberspace)\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>On Sat, 12 Jun 2004, BA wrote:

> I'm looking for an analytic expression for the diffraction (Fourier
> transform) of 2D quasicrystals genertaed by the Dual Grid Method.

I'm curious to know more about your interest in "quasicrystals" and the
"dual grid method"! Are you more interested in the mathematical aspects
(e.g. connections with ergodic theory, noncommutative geometry, and
logic), or in physical quasicrystalline materials?

I assume you know that there is no universally accepted mathematical
definition of a "quasicrystal", and also that what you call the "dual grid
method" is identical with the "multigrid method" for obtaining "Sturmian
tilings" (aka "generalized Penrose tilings") which was introduced by de
Bruijn:

author = {N. G. de Bruijn},
title = {Algebraic Theory of {P}enrose Tilings of the Plane},
journal = {Indagationes Mathematicae},
volume = 43,
year = 1981,
pages = {38--66}}

author = {N. G. de Bruijn},
title = {Dualization of Multigrids},
journal = {Journal de physique},
volume = 47,
year = 1986,
pages = {9--18}}

If so, you are no doubt aware of the "projection method", but perhaps not
of a third equivalent method, the "oblique tiling method", which was
introduced in

author = {Christophe Oguey and Michel Duneau and Andre Katz},
title = {A Geometrical Approach of Quasiperiodic Tilings},
journal = {Communications in Mathematical Physics},
volume = 118,
year = 1988,
pages = {99-118}}

The oblique tiling is a -periodic- tiling (-not- a "face-to-face"
tiling!); its "prototiles" consist of a finite list of parallelotopes
(multidimensional generalization of rhombus) in a higher dimensional
euclidean space, and then taking slices parallel to certain of the faces
of the tiles. (See the picture in the above mentioned paper to see,
literally, why the slices are -quasiperiodic-!)

All three methods involve the choice of an n-dimensional subspace W of E^r
(where r > n). The orthogonal subspace W^{perp} also plays a critical role.
For example, in the projection method, the "window" is a polytope in
E^(r-n), but the tiling itself lives in E^n.

Each tiling constructed by any of the three methods belongs to a certain
tiling space. All of the tilings contained in a given tiling space are
"locally indistinguishable" (which is why these tilings provide, for Alain
Connes, key examples of "noncommutative geometries"). In particular, they
all have the same infinite list of "allowed patches" and the same patch
frequencies (this notion does make sense, but justifying this takes some
explanation, which I'll omit).

At a still higher level of structure, we can consider the "superspace" of
all tiling spaces associated with the choice of a particular n-dimensional
subpace W of E^r, for particular positive integers (n,r) where r > n, and
it is then natural to ask how properties of the tiling spaces vary as we
vary our choice of W, i.e. as we move through this superspace.

The hillman mathbot (of which I am a dumbed down "student version"!) wrote
a Ph.D. dissertation on Sturmian tiling spaces (aka "generalized Penrose
tiling spaces"), principally relying on the oblique tiling construction.
I don't have a copy of this document at hand, but IIRC it

1. carefully distinguished various levels of structure which are often
confused in the literature, including:

a. measure-theoretic features (e.g. frequencies of allowed patches) versus
underlying combinatorial features (e.g. allowed versus forbidden "patches"
of tiles),

b. translation by R^n versus vectors arising from a certain algebraic
number field over Q defined by a given Sturmian tiling space,

c. protopatches versus patches, and in particular protoempires versus
empires,

2. discussed various "organizing principles", including:

a. a natural hierarchy of smaller dimensional Sturmian tiling spaces
obtained from the "walls" of the tilings contained in a given tiling space
(walls are the natural multidimensional generalization of "ribbons", for
which see the discussion in Grunbaum and Sheppard),

b. the empire/cylinder duality, which is completely general (i.e. applies
to a very general notion of "symbolic dynamics"),

c. another elementary "duality" defined between certain Sturmian
superspaces,

3. answered some natural questions:

a. characterize the types of "singular tilings" which can arise in
Sturmian tiling spaces, and construct explicitly examples illustrating
each possibility,

b. characterize the types of "periodicities" which can arise (some
Sturmian tilings are periodic along certain directions--- if so they are
generally "transversely periodic"), and construct explicitly examples
illustrating each possibility,

(this turns out to related to the problem: characterize the types of
"rotational symmetry" which can arise, and construct explicitly examples
illustrating each possibility),

and partially answered some further questions, including:

d. characterize the types of "inflation maps" which can arise, and
construct explicit examples illustrating each possibility,

e. at the level of combinatorial structure, characterize for example the
types of allowed patches which can arise, construct explicit examples
illustrating each possibility, and explain how these vary (in particular,
characterize the bifurcations) as you move through the appropriate
Sturmian superspace,

f. at the level of statistical (measure-theoretic) structure, characterize
for example the patch frequencies which can arise, construct explicit
examples illustrating each possibility, and explain how these vary (in
particular, characterize the bifurcations) as you move through the
superspace,

4. discussed various open problems, of which I now remember only an
amusing problem involving the causal structure of two dimensional
combinatorial spacetimes obtained from Penrose tilings.

Now, the obvious "running example" in any discussion of Sturmian tilings
is of course provided by Penrose tilings, so I should say something about
how the above works out for this example.

The Sturmian tiling space of Penrose tilings contains precisely the
tilings obtained by Penrose's original construction via "inflation", or
from any of the three constructions above. In particular, it is
associated with a particular oblique tiling, a periodic tiling of E^5.
But the Penrose tiling space is very special in that, as just mentioned,
it admits an "inflation map" associated with a linear operator acting on
E^5. This is closely connected to another special feature: the five-fold
"local rotational symmetry" which is obvious upon inspection of any (=
all!) Penrose tiling. Both phenomena reflect the fact that the oblique
tiling for the Penrose tiling space can be defined from the invariant
subspaces of the obvious "five-cycle" R on E^5. This linear operator
possesses an invariant line and two invariant two-planes in which R
effects a 1/5 and 2/5 turn respectively. The tiles of the periodic
oblique tiling have edges contained, up to translation, in these invariant
spaces, and the R^2 in which the actual Penrose tilings are constructed
corresponds to the two-dimensional invariant subspace in which R effects a
1/5 turn.

The "dual" of the Penrose tiling space is a Sturmian tiling space of 3d
tilings which are -periodic- in one direction, but transversely
quasiperiodic. As such, it actually belongs to another Sturmian
superspace, the one in which n, r-n have switched roles. (Physicists
might say that "window space" and "physical space" are interchanged by the
duality we are discussing.) In the Penrose example, this duality is again
very closely connected to the "local rotational symmetry" and the
"inflation map", but duals are defined for any Sturmian tiling space, and
there are neat relationships between the singularities, periodicities (and
other combinatorial/statistical features) of a Sturmian tiling space and
its dual.

Now for some more generalities: as you may know, it turns out that one
dimensional Sturmian tilings have a very close connection with simple
continued fractions and the Euclidean algorithm (greatest common divisor).
The hierarchy of walls mentioned above generalizes this to any Sturmian
tiling space. For example, simple continued fractions and ribbons give
the whole story on finding constructively, explicitly, and even
efficiently, the "magic shifts" (aka "almost periods") of a given Sturmian
tiling space (all tilings in a given space share the same magic shifts).
Here, the magic shifts form an infinite sequence of longer and longer
translations (parallel to the edges of the tiles) which mimic true
periodicity better and better, in the sense that if you translate any
Penrose tiling by p[n], you will observe agreement over 85% of the plane,
and if you translate by p[n+1], over 95% of the plane, and so forth.

One can also construct a sequence of periodic approximations to any
Sturmian tiling. Here, the tiles themselves are not quite isometric to
the original tiles, but at the combinatorial level one could use the
original tiles, so that one can think of these as periodic approximations
in the sense of symbolic dynamics. For example, one can find a -periodic-
rhomb tiling which, up to a certain size of patches, has precisely the
same tile frequencies (measure-theory level) and allowed patches
(underlying combinatorial level) as the real thing, but if you examine
larger patches you can find patches which are (at the combinatorial level)
forbidden in genuine Penrose tilings. "Later" periodic approximations in
the sequence are perfect mimics (combinatorially) within -larger- windows,
and you can go as far as you like.

The more general notion of "combinatorial approximations" goes to the very
heart of symbolic dynamics and the combinatorial content of Shannon's
information theory. See also

author = {William Geller and Jim Propp},
title = {The Projective Fundamental Group of a $\Z^2$-Shift},
journal = {Ergodic Theory and Dynamical Systems},
year = 1995,
pages = {1091--1118}}

but note that it is perhaps more natural to study non-Hausdorff sheaves,
rather than the branched manifolds considered by Geller and Propp. Among
other things, this should facilitate a very general notion of symbolic
dynamics in which we will find many connections with topos theory, logic,
and other things of current interest to certain mathematicians,
physicists, and philosophers.

To sum up: Sturmian tilings are essentially a geometric realization of
diophantine phenomena which arise in studying multidimensional rational
approximations of linear relationships. (This characterization can be
traced back to work of Klein and Minkowski at the turn of the last
century; their work far anticipated the quasicrystal craze.) Of course,
this is in some sense already obvious from the original paper by de Bruijn
introducing the general multigrid construction!

I should mention one more generality: at the cost of losing the
equivalence between the projection, multigrid, and oblique tiling methods,
we can greatly generalize the projection method to construct more general
quasiperiodic tiling spaces. One way of doing this is closely related to
Meyer's beautiful theory of "harmonic sets" (the same notion which
eventually turned out to be needed for "wavelets"); see

author = {Robert V. Moody},
title = {{M}eyer Sets and their Duals},
booktitle = {The Mathematics of Long-Range Aperiodic Order},
note = {Proceedings of the NATO Advanced Study Institute, The Fields
Institute, Waterloo, Ontario, Canada, August 21-- Sept. 1, 1995},
editor = {Robert V. Moody},
publisher = {Kluwer},
address = {Boston},
year = 1997}}

BTW, in this paper, Moody states an interesting problem (AFAIK still open)
which should appeal to anyone who follows John Baez's "This Week" series:
write down an appropriate definition of a "morphism" which turns harmonic
sets into "objects" in a useful/interesting category.

OK, now for the bad news: I might be able to help with some of the above,
but unfortunately, I don't know very much about -diffraction phenomena- in
quasicrystals. Fortunately, diffraction is probably the aspect of
quasicrystals which has been most studied in the literature. I suggest
that you try to contact these approachable experts: Michael Baake,
Charles Radin, and Boris Solomyak. Baake is a mathematical physicist;
Radin and Solomyak are ergodic theorists.

At a more elementary level, the discussion of diffraction in the
undergraduate textbook

author = {Marjorie Senechal},
title = {Quasicrystals and Geometry},
note = {Beware of the uncorrected hardcover edition},
edition = {Paperback},
publisher = {Cambridge University Press},
year = 1996}

might be useful. (This book also has a large bibliography.)

You can also search the ArXiv, e.g. I just found this fairly recent paper:

http://xxx.lanl.gov/abs/http://www.arxiv.org/abs/math-ph/0105010

I haven't had a chance to look at it, but I'd guess there should be some
connection with the ideas discussed by Moody in the paper I cited above.

"T. Essel" (hiding somewhere in cyberspace)