Oct 312014

As you may have noticed, a comment on the previous post inspired me to adjust the post. (Actually, it raised an issue that will deserve a post of its own.)

Since I would like this blog to be useful to a wide audience, I appreciate comments, corrections, suggestions, criticisms, etc., either posted on this blog or emailed to me. After all, I should be described (to paraphrase Jane Austen) as a partial, prejudiced & ignorant crystallographer, and I would like to keep posts as correct as possible.

(Comments, by the way, do not appear on the main page; notice at the upper right hand corner of this post, just right of the headline in small gray type next to two small gray bubbles, is a note about comments for that post. To see comments for a post, or to post a comment, click the headline of the post, and at the bottom of this new page are comments and a form for entering comments.)

Unfortunately, most comments entered come from spambots, programs that surf the web, looking for sites like this one to post ads for X-rated products, post links in order to inflate their own page rank, etc. In order to prevent this blog from being weighed down by this kind of nonsense, comments are moderated. That means that a comment is entered, it sits in a “pending” folder until I get to it and approve it.

I try to check the pending folder daily, but if you posted a comment and it doesn’t appear within a day or so, feel free to email to me. (Feel free to email me about this site in any case: I appreciate the feedback.)

I apologize for the inconvenience, but I think that this is the least inconvenient system for the situation we have.

Oct 292014

Let’s start with crystal structure prediction. Suppose that you would like a crystal with various properties (it’s purple, porous with channels two nanometers wide, nonconductive, etc.). Traditionally, finding such a crystal would involve synthesizing many novel chemicals and annealing them, and hopefully a sequence of increasingly successful combinations would ultimately lead to success. This was the method that the alchemists employed in their pursuit of the Philosopher’s Stone, and whose modern, automated incarnation is called Combinatorial Chemistry. It may have been good enough for Paracelsus and Robert Boyle, but it is expensive and frustrating.

More to the point, this is not what engineers and architects do. In construction and industry, someone composes a set of blueprints specifying the final product and (hopefully) intermediate steps, and then someone (often someone else) uses those blueprints to construct the desired product – which, no coincidence, satisfies the original specifications. Chemists should be able to do that.

The general project is crystal engineering, which Wikipedia defines as “the design and synthesis of molecular solid-state structures with desired properties, based on an understanding and exploitation of intermolecular interactions.” Wikipedia says that the oldest reference to the term is G. M. J. Schmidt, Photodimerization in the Solid State in Pure & Applied Chemistry 27:4 (1971), pp. 647 – 678, but Web of Science says oldest reference they have is an abstract for a paper presented to the American Physical Society meeting in Mexico City, Mexico, August, 1955 by R. Pepinsky entitled Crystal Engineering – A New Concept in Crystallography, abstract published (but not posted!) in the Physical Review 100:3 (1955), p. 971. There being nothing new under the sun, the notion probably has been floating around since the beginning of the 20th century.

In the last few decades, crystal engineering has become of field of its own: on October 23, Web of Science listed 2,520 hits from all databases, and now the subject has its own textbook: Crystal Engineeering : A Textbook by Gautam Desiraju, Jagadese Vittal, and Arunachalam Ramanan.

The growth of the field is a little more problematic. Here are the 2,520 hits in the Web of Science by date:

Notice that after Pepinsky’s 1955 talk, Web of Science has no hits until 1976 (Schmidt’s 1971 paper did not have “crystal engineering” in any of the fields Web of Science checks – a warning to people who rely on such databases), and things really didn’t get going until 1991. Most of the growth was during the 1990s: a linear regression shows that publication growth during 2001 to 2013 has been nearly linear, an average additional 3.3 papers a year, or less than 3 % growth per year. Growth in citations looks more exponential, which shows that crystal engineering has been gaining a higher profile lately, but the number of citations has been flattening out during the last few years:

Let’s take a closer look.

In 1988, John Maddox wrote an op-ed in Nature:

A new calculation of the polymorphs of silica appears to have broken new ground in deriving crystal structure from chemical composition. But X-ray crystallographers need not worry — yet.

and grumped that “[o]ne of the continuing scandals in physical sciences is that it remains in general impossible to predict the structure of even the simplest crystallographic solids from knowledge of their chemical composition.” This is an intermediate position: he is complaining that as of then, a chemist couldn’t choose a random small molecule and predict the structure (or structures!) exhibited by its crystal.

But even if Maddox was taking an intermediate position, he had launched the verb, and it was quickly associated not only with predicting what crystal a given molecule would produce, but what crystal structures could exist. During the past few decades, chemists have explored the possibility of taking the desired properties as a list of specifications, designing a crystal at the molecular or atomic level that will satisfy those specifications, generating a synthesis process from the design, and synthesizing the crystal – which will satisfy the specifications. As of 22 July 2014, Google Scholar listed 3,450 hits for “crystal structure prediction”, and on 25 June 2015, Web of Science reported rapid growth in the field since the mid-nineties:

Notice that unlike crystal engineering, there has been no recent growth slowdown. (Although I have heard chemists and crystallographers use the phrases “crystal enumeration” and “crystal structure enumeration”, and I have seen those phrases in print, Web of Science reports no hits for either one.)

As of 19 October 2014, Web of Science listed 702 hits for either “crystal prediction” or “crystal structure prediction”, and the journals that had published at least twenty articles in the subject were:

Journal Hits
Crystal Growth & Design 64
CrystEngComm 47
Physical Chemisty / Chemical Physics 33
Physical Review B 30
Journal of Chemical Physics 25
Journal of Physical Chemistry 25

And this is just those articles for which one of the two phrases is picked up by the Web of Science topics field.

Crystal structure prediction is new enough so that one can’t say what the fundamental mathematical issue is, but one could start with the work of Alexander Wells, whose book on Three dimensional nets and polyhedra presents the notion of a net, i.e. a finite or infinite graph embedded in three dimensional space. The vertices of this graph are points in space, while the edges are line segments (or curves) whose endpoints are vertices; typically, we all edge intersections should be at vertices.

(“Nets” might also be called “Euclidean graphs” or “geometric graphs” as they are graphs embedded in a Euclidean space.)

A net could represent a material structure by having the vertices represent atoms or molecular building blocks and having the edges represent chemical bonds or linkers. (We sidestep the issue of whether we believe in chemical bonds.) Then a (classical) crystal may be represented by a periodic graph, i.e. a graph with translational symmetries in three axial directions. We have reached the formulation of “crystal nets” as described in Michael O’Keeffe and Bruce Hyde’s Crystal Structures I : Patterns and Symmetry.

In mathematics, once you get your paws on a definition you can do things with it. We have a definition of the word “periodic graph”, which is the central mathematical notion in what Omar Yaghi calls reticular chemistry. A mathematician then mimics Stewart Robertson’s agenda and proposes the following:

  • Let P be the set of all periodic graphs. Since P itself has a geometric and topological structure, we might call P the space of all periodic graphs.
  • We usually regard two periodic graphs as being the “same” if one is the result rigidly moving the other around, so we can define the equivalence relation ≅, where “AB” means that the periodic graph A is the result of moving B. Given a periodic graph A, its equivalence class is the set [A] = { B : AB}. It is this equivalence class that fixes the size and shape of the structure, so once could say that the space of these equivalence classes, which we denote P/≅, are the models of (classical) crystal structures.
  • This is not quite how periodic graphs are currently specified in, say, the Reticular Chemistry Structure Resource (RCSR). Current practice is to specify periodic graphs by isomorphism type. Call two periodic graphs A and B isomorphic if there is a one-to-one correspondence between their vertices such that that there is an edge connecting two vertices of A if and only if there is an edge connecting the corresponding two vertices of B. If two periodic graphs A and B are isomorphic, write AB, and the isomorphism type of A is [A] = {B : AB}. We could denote the entire space of periodic graph isomorphism types by P/∼, and RCSR has a catalogue of periodic graph isomorphism types.

As Igor Barburin observed (see his comment below, which inspired a revision of this post), the situation is a bit more subtle than this. While two periodic graphs are often considered to be the “same” if they are isomorphic, a database like RCSR may have, for each periodic graph listed, a particular periodic graph in its catalogue, listed as a geometric object with geometric properties. For example, while pcu comes in many shapes and sizes, RCSR lists a particular geometric realization of pcu (of maximal symmetry). The infinitely many other geometric realizations of pcu are themselves classifiable by geometric properties (including symmetries) – and topological issues like chirality.

We will discuss issues in classifying and cataloguing periodic graphs in later posts…beginning with the question of exactly why Dr. Baburin’s comment inspired me to replace the word “classify” with the word “specify”.

Anyway, two of the central problems of crystal structure prediction is the generation and classification of periodic graphs by rigid motion equivalence relations, by isomorphism types, and by other criteria. But even that is not enough. The Atlas of Prospective Zeolites Structures has over five million nets, but few of them have been synthesized. If crystal structure prediction is to be more than a recreational activity, it must include designing the synthesis process. After all, the purpose of a blueprint is to provide a roadmap for building the structure.

But at present, most of the activity seems to be in generating periodic graphs. But before we survey that activity, we should follow Socrates’ advice and get a handle on what it is we are talking about. So what do we know about periodic graphs…?

Oct 152014

A bit over a century ago, the scientific community had decided what a crystal was. A crystal was a material whose atomic or molecular arrangement (this was the same era during which atoms and molecules were finally accepted) repeated periodically in three axial directions. Sir William Bragg and his son developed x-ray crystallography, and crystallographers could develop good descriptions of what these repeating “unit cells” looked like.

This was probably a necessary step. Socrates would say that if we are going to study crystals, we must first decide what a “crystal” is.

Socrates’ is not a universal sentiment. To paraphrase Ludwig Wittgenstein, to teach a student what a crystal is, one presents the student with a diamond and say, “crystal”, and then with a large salt cube and say, “crystal”, and then with a lump of amethyst and say, “crystal”, and then the student starts getting the idea. In real life, Wittgenstein is right: definitions (and food fights over definitions) emerge from catalogues of examples and counterexamples.

That does not mean that definitions are a waste of the taxpayer’s money. Consider my current obsession: predicting crystals. Crystal prediction requires software, software requires theory, and theory requires definition. If one is to predict crystals, one needs to know precisely what crystals are. For crystals (as they were understood over most of the Twentieth century), one will probably wind up doing a variant of one of the following:

  • Design a crystal by assembling a structure within the space of a unit cell. One takes a generic parallelopiped, with side (vectors) labeled x, y, and z, as in this picture…

    …and then one identifies the three pairs of opposing faces of the unit cell, so that a fly buzzing into one face will then buzz out of the opposing face in the same direction. Within this unit cell, one assembles a structure, possibly adjusting the shape of the cell (i.e. adjusting x, y and z) en route. (References for this sort of topology includes Michael Henle’s Combinatorial Course in Topology and Hajime Sato’s Algebraic Topology : An Intuitive Approach.)

  • Assembling a structure by taking some kind of fragment or collection of fragments, and then attaching them one to another to another, all monitored by a device that can recognize when a unit cell or equivalent has been assembled. (References for this sort of group theory include John Meier’s Groups, Graphs and Trees.) This is the approach I proposed in my presentation to the MathCryst commission.

(All this also requires linear algebra – see, e.g. Hoffman & Kunze’s Linear Algebra – and abstract algebra – see, e.g. Israel Herstein’s Topics in Algebra.)

Both of the above approaches presumes a definition of “crystal” that is somewhat like this:

  • A crystal is a material composed of a finite number of types of constituents, and whose structure admits a symmetry from any constituent to any other constituent of the same type.

This is the fundamental classical definition based on nanoscopic structure, and it is the one that a mathematician might start with. But this definition is not the definition that emerged from Eighteenth and Nineteenth centuries and held sway until the 1980s. For the more popular definition, I’ll quote from Charles Kittel’s Introduction to Solid State Physics (2nd ed.):

  • A perfect crystal is considered to be constructed by the infinite regular repetition in space of identical structural units or building blocks.

This definition is at least as old as Kepler, and may go back to the Greek atomists. Mathematically, these two definitions are equivalent, a fact that one might regard as the Fundamental Theorem of [Classical] Mathematical Crystallography: A material is composed of a finite number of types of constituents such that its structure admits a symmetry from any constituent to any other constituent of the same type if and only if it is constructed by the infinite regular repetition in space of identical structural units or building blocks.

Yet Kittel was typical in starting with the second definition, and the first definition – if it is mentioned at all – is mentioned as a rationale for the second. In practice, these two classical definitions above are quite different.

  1. The first definition arises from the apparent homogeneity of crystals, that is, it is about an observable property of crystals. Thus it is somewhat like what computer scientists call a specification: given a crystal, this is the “spec” that it has to satisfy. A specification may not say very much about what the object is so much as how it behaves.
  2. The second definition is closer to what applied mathematicians call a model. It is both descriptive (giving a better idea of how to recognize a crystal if you encounter one) and prescriptive (giving a better idea of how to construct one, if only out of styrofoam balls and toothpicks).

(Of course, the first definition is rather model-ish. We will see more pure specifications in a moment. In general, there is a spectrum from specification-ish to model-ish.)

Perhaps the main theme of the 2014 IUCr Congress is that old definitions have been replaced by new ones, thanks to quasicrystals and the like. Very roughly, the new definitions can be associated with the work of Dan Schechtman (who won the 2011 Nobel Prize in Chemistry) and of Aloysio Janner and Ted Janssen (who shared the 2014 Ewald Prize), respectively:

  1. From the IUCr Online Dictionary: A material is a crystal if it has essentially a sharp diffraction pattern… (the rest of the entry devoted to what “essentially” means). In Volume C of the IUCr tables, Janner, Janssen, Looijenga-Vos and Wolff restrict this definition to require that “… its diffraction pattern is characterized by a discrete set of resolved Bragg peaks, which can be indexed accordingly by a set of n integers …”. These definitions are specifications, pure and simple. They impose criteria that must be satisfied in order for an object to be a quasicrystal, but they does not tell us what quasicrystals are.
  2. There are a number of mathematical models of crystals. For example…
    • One model is the cut-and-slice model, which I can oversimplify as follows. Given an n-dimensional lattice L, and one creates a slice consisting of an k-dimensional subspace S and a n- k – dimensional “window” W, to get the n-dimensional slice W × S. Project all points of L in the slice orthogonally onto S, and the projected points give the positions of the atoms (see, e.g. Marjorie Senechal’s Quasicrystals and Geometry).
    • Another popular model is called inflation, which is a higher dimensional (and geometric) analogue of what computer scientists call a grammar. A grammar consists of several rules for replacing individual letters with strings of letters. For example, the grammar defined by a → a, a → bab generates strings from a of the form b…bab…b, with equal numbers of b’s on both sides of the a. Notice there is no rule for replacing b’s: in inflation, many sets of substitution rules have at least one rule for each letter. One can go beyond strings of letters to geometric shapes, replacing a shape (or tile) with some configuration of several tiles, and then “inflating” the configuration until the new tiles are the same size as the original ones, and repeating (see, e.g. Michael Baake and Uwe Grimm’s Aperiodic Order I: A Mathematical Invitation).

    Such models give us visualizations of what a quasicrystal is. Cognitive scientists claim that we think in metaphors, and that is what makes these definitions valuable.

Having a lot of definitions suggests that a field is new and practitioners have not settled on a definition to inflict on students. We can ask mathematicians for a new Fundamental Theorem, but it is possible that the situation is more complicated. For example, in 2000, Jeffrey Lagarias asked eleven questions about the relations between various definitions. At the 2014 IUCr Congress, Lorenzo Sadun (with Johannes Kellendock) announced that the answer to Problem 4.10 was “no”, suggesting that the world is a little more complicated than anticipated. (See also Lagarias’s short paper on these definitions. I’d like to thank Lorenzo for helping me with some of these definitions.)

If we have several definitions, and if they are not equivalent, then we have a problem. Outside of encouraging food fights, definitions provide a methodological anchor. But it would be helpful if we could settle on what the subject of our endeavor is.

Often (as in classical crystallography), the goal is a single widely usable definition. In logic, a notion is robust if it is expressible in many different but straightforward ways. In mathematics, a representation theorem says that two different notions are actually equivalent. The Fundamental Theorem of [Classical] Mathematical Crystallography is such a representation theorem – and a particularly important one, since it connects a specification with a model. So some of us may hope for a demonstrably robust notion, whose robustness can be demonstrated by a representation theorem.

But that may not be in the cards. Sometimes the universe is messy, and what we really need is a catalog. We may then hope that organizing principles will arise out of the mounds of data, like quarks arising from the heaps of subatomic particles in the early 1960s.

Either way, we don’t seem to be there yet. And that means that the paradigm shift presided over by Shechtman, Janssen and Janner is still underway.