Compositional Frameworks for Open Systems

Here are the slides of Blake Pollard’s talk at the Santa Fe Institute workshop on Statistical Physics, Information Processing and Biology:

• Blake Pollard, Compositional frameworks for open systems, 17 November 2016.

He gave a really nice introduction to how we can use categories to study open systems, with his main example being ‘open Markov processes’, where probability can flow in and out of the set of states. People liked it a lot!

Monoidal Categories of Networks

Here are the slides of my colloquium talk at the Santa Fe Institute at 11 am on Tuesday, November 15th. I’ll explain some not-yet-published work with Blake Pollard on a monoidal category of ‘open Petri nets’:

• Monoidal categories of networks.

Nature and the world of human technology are full of networks. People like to draw diagrams of networks: flow charts, electrical circuit diagrams, chemical reaction networks, signal-flow graphs, Bayesian networks, food webs, Feynman diagrams and the like. Far from mere informal tools, many of these diagrammatic languages fit into a rigorous framework: category theory. I will explain a bit of how this works and discuss some applications.

There I will be using the vaguer, less scary title ‘The mathematics of networks’. In fact, all the monoidal categories I discuss are symmetric monoidal, but I decided that too many definitions will make people unhappy.

The main new thing in this talk is my work with Blake Pollard on symmetric monoidal categories where the morphisms are ‘open Petri nets’. This allows us to describe ‘open’ chemical reactions, where chemical flow in and out. Composing these morphisms then corresponds to sticking together open Petri nets to form larger open Petri nets.

Compositionality Workshop

I’m excited! In early December I’m going to a workshop on ‘compositionality’, meaning how big complex things can be built by sticking together smaller, simpler parts:

• Compositionality, 5-9 December 2016, workshop at the Simons Institute for the Theory of Computing, Berkeley. Organized by Samson Abramsky, Lucien Hardy and Michael Mislove.

In 2007 Jim Simons, the guy who helped invent Chern–Simons theory and then went on to make billions using math to run a hedge fund, founded a research center for geometry and physics on Long Island. More recently he’s also set up this institute for theoretical computer science, in Berkeley. I’ve never been there before.

‘Compositionality’ sounds like an incredibly broad topic, but since it’s part of a semester-long program on Logical structures in computation, this workshop will be aimed at theoretical computer scientists, who have specific ideas about compositionality. And these theoretical computer scientists tend to like category theory. After all, category theory is about morphisms, which you can compose.

Here’s the idea:

The compositional description of complex objects is a fundamental feature of the logical structure of computation. The use of logical languages in database theory and in algorithmic and finite model theory provides a basic level of compositionality, but establishing systematic relationships between compositional descriptions and complexity remains elusive. Compositional models of probabilistic systems and languages have been developed, but inferring probabilistic properties of systems in a compositional fashion is an important challenge. In quantum computation, the phenomenon of entanglement poses a challenge at a fundamental level to the scope of compositional descriptions. At the same time, compositionally has been proposed as a fundamental principle for the development of physical theories. This workshop will focus on the common structures and methods centered on compositionality that run through all these areas.

So, some physics and quantum computation will get into the mix!

A lot of people working on categories and computation will be at this workshop. Here’s what I know about the talks so far. If you click on the talk titles you’ll get abstracts, at least for most of them.

The program

 

Monday, December 5th, 2016

9 – 9:20 am		Coffee and Check-In
9:20 – 9:30 am		Opening Remarks
9:30 – 10:30 am		Compositionally, Adequacy, and Full Abstraction Gordon Plotkin, University of Edinburgh
10:30 – 11 am		Break
11 – 11:35 am		An Operadic Approach to Compositionality David Spivak, MIT
11:40 am – 12:15 pm		Data Structures for Quasistrict Higher Categories Jamie Vicary, University of Oxford
12:20 – 2 pm		Lunch
2 – 2:35 pm		From Linearizability to Eventual Consistency Radha Jagadeesan, DePaul University
2:40 – 3:15 pm		Compositionality and Session Types Nobuko Yoshida, Imperial College London
3:30 – 4 pm		Break
4 – 5 pm		Discussion
5 – 6 pm		Reception

 

Tuesday, December 6th, 2016

9 – 9:30 am		Coffee and Check-In
9:30 – 10:30 am		The Mathematics of Networks John Baez, UC Riverside
10:30 – 11 am		Break
11 – 11:35 am		Composition in Categorical Distributional Models of Natural Language Mehrnoosh Sadrzadeh, Queen Mary University of London
11:40 am – 12 pm		Modelling Interconnected Systems with Decorated Corelations Brendan Fong, University of Pennsylvania
12:05 – 12:25 pm		Custom Compact Closed Categories via Relations Dan Marsden, University of Oxford
12:30 – 2 pm		Lunch
2 – 2:35 pm		Some Thoughts on Inferring System Structure Tobias Fritz, Max Planck Institute, Leipzig
2:40 – 3:15 pm		TBD Alexandra Silva, University College London
3:30 – 4 pm		Break
4 – 5 pm		Discussion

 

Wednesday, December 7th, 2016

9 – 9:30 am		Coffee and Check-In
9:30 – 10:30 am		Compositional Thermodynamics Giulio Chiribella, The University of Hong Kong
10:30 – 11 am		Break
11 – 11:20 am		Composition and Quantum Theory: A Conjecture, and How it Could Fail Markus Mueller, Western University
11:25 – 11:45 am		Multipartite Composition of Contextuality Scenarios Ana Belen Sainz, University of Bristol
11:50 am – 12:25 pm		Compositionality in Categorical Quantum Computing Ross Duncan, University of Strathclyde
12:30 – 2 pm		Lunch

 

Thursday, December 8th, 2016

9 – 9:30 am		Coffee and Check-In
9:30 – 10:05 am		Canonical Representations of Measurements for Contextuality Analysis Ehtibar Dzhafarov, Purdue University
10:10 – 10:30 am		TBD Rui Soares Barbosa, University of Oxford
10:35 – 11 am		Break
11 – 11:20 am		Modelling Interfaces in Distributed Systems: Some First Steps David Pym, University College London
11 am – 11:45 am		Compositionality in Cybersecurity Pasquale Malacaria, Queen Mary University of London
11 am – 12:10 pm		A Topological Approach for Exploiting Compositionality in Complex Systems Emanuela Merelli, University of Camerino
12 pm – 2 pm		Lunch
2 – 2:35 pm		Nominal Games: A Semantics Paradigm for Effectful Languages Nikos Tzevelekos, Queen Mary University of London
2:40 – 3:15 pm		Probabilistic Call By Push Value Christine Tasson, Université Paris Diderot
3 pm – 3:50 pm		Break
3:50 – 4:25 pm		TBD Kohei Kishida, University of Oxford
4:30 – 4:50 pm		Linear Logic, Session Types and Deadlock-Freedom Simon Gay, University of Glasgow

 

Friday, December 9th, 2016

9:30 – 10:05 am		Composing Schema Mappings: An Overview Phokion Kolaitis, UC Santa Cruz and IBM Research – Almaden
10 am – 10:45 am		TBD Val Tannen, University of Pennsylvania
10:50 – 11:20 am		Break
11:20 – 11:55 am		A Compositional Quantum Programming Language Peter Selinger, Dalhousie University
12 – 12:35 pm		Programming Recurrence Relations Pawel Sobocinski, University of Southampton
12:40 – 2 pm		Lunch
2 – 3 pm		Discussion
3 – 3:40 pm		TBD Dana Scott, Carnegie Mellon University

Open and Interconnected Systems

Brendan Fong finished his thesis a while ago, and here it is!

• Brendan Fong, The Algebra of Open and Interconnected Systems, Ph.D. thesis, Department of Computer Science, University of Oxford, 2016.

This material is close to my heart, since I’ve informally served as Brendan’s advisor since 2011, when he came to Singapore to work with me on chemical reaction networks. We’ve been collaborating intensely ever since. I just looked at our correspondence, and I see it consists of 880 emails!

At some point I gave him a project: describe the category whose morphisms are electrical circuits. He took up the challenge much more ambitiously than I’d ever expected, developing powerful general frameworks to solve not only this problem but also many others. He did this in a number of papers, most of which I’ve already discussed:

• Brendan Fong, Decorated cospans, Th. Appl. Cat. 30 (2015), 1096–1120. (Blog article here.)

• Brendan Fong and John Baez, A compositional framework for passive linear circuits. (Blog article here.)

• Brendan Fong, John Baez and Blake Pollard, A compositional framework for Markov processes. (Blog article here.)

• Brendan Fong and Brandon Coya, Corelations are the prop for extraspecial commutative Frobenius monoids. (Blog article here.)

• Brendan Fong, Paolo Rapisarda and Paweł Sobociński,
A categorical approach to open and interconnected dynamical systems.

But Brendan’s thesis is the best place to see a lot of this material in one place, integrated and clearly explained.

I wanted to write a summary of his thesis. But since he did that himself very nicely in the preface, I’m going to be lazy and just quote that! (I’ll leave out the references, which are crucial in scholarly prose but a bit off-putting in a blog.)

Preface

This is a thesis in the mathematical sciences, with emphasis on the mathematics. But before we get to the category theory, I want to say a few words about the scientific tradition in which this thesis is situated.

Mathematics is the language of science. Twinned so intimately with physics, over the past centuries mathematics has become a superb—indeed, unreasonably effective—language for understanding planets moving in space, particles in a vacuum, the structure of spacetime, and so on. Yet, while Wigner speaks of the unreasonable effectiveness of mathematics in the natural sciences, equally eminent mathematicians, not least Gelfand, speak of the unreasonable ineffectiveness of mathematics in biology and related fields. Why such a difference?

A contrast between physics and biology is that while physical systems can often be studied in isolation—the proverbial particle in a vacuum—biological systems are necessarily situated in their environment. A heart belongs in a body, an ant in a colony. One of the first to draw attention to this contrast was Ludwig von Bertalanffy, biologist and founder of general systems theory, who articulated the difference as one between closed and open systems:

Conventional physics deals only with closed systems, i.e. systems which are considered to be isolated from their environment. […] However, we find systems which by their very nature and definition are not closed systems. Every living organism is essentially an open system. It maintains itself in a continuous inflow and outflow, a building up and breaking down of components, never being, so long as it is alive, in a state of chemical and thermodynamic equilibrium but maintained in a so-called ‘steady state’ which is distinct from the latter.

While the ambitious generality of general systems theory has proved difficult, von Bertalanffy’s philosophy has had great impact in his home field of biology, leading to the modern field of systems biology. Half a century later, Dennis Noble, another great pioneer of systems biology and the originator of the first mathematical model of a working heart, describes the shift as one from reduction to integration.

Systems biology […] is about putting together rather than taking apart, integration rather than reduction. It requires that we develop ways of thinking about integration that are as rigorous as our reductionist programmes, but different. It means changing our philosophy, in the full sense of the term.

In this thesis we develop rigorous ways of thinking about integration or, as we refer to it, interconnection.

Interconnection and openness are tightly related. Indeed, openness implies that a system may be interconnected with its environment. But what is an environment but comprised of other systems? Thus the study of open systems becomes the study of how a system changes under interconnection with other systems.

To model this, we must begin by creating language to describe theinterconnection of systems. While reductionism hopes that phenomena can be explained by reducing them to “elementary units investigable independently of each other” (in the words of von Bertalanffy), this philosophy of integration introduces as an additional and equal priority the investigation of the way these units are interconnected. As such, this thesis is predicated on the hope that the meaning of an expression in our new language is determined by the meanings of its constituent expressions together with the syntactic rules combining them. This is known as the principle of compositionality.

Also commonly known as Frege’s principle, the principle of compositionality both dates back to Ancient Greek and Vedic philosophy, and is still the subject of active research today. More recently, through the work of Montague in natural language semantics and Strachey and Scott in programming language semantics, the principle of compositionality has found formal expression as the dictum that the interpretation of a language should be given by a homomorphism from an algebra of syntactic representations to an algebra of semantic objects. We too shall follow this route.

The question then arises: what do we mean by algebra? This mathematical question leads us back to our scientific objectives: what do we mean by system? Here we must narrow, or at least define, our scope. We give some examples. The investigations of this thesis began with electrical circuits and their diagrams, and we will devote significant time to exploring their compositional formulation. We discussed biological systems above, and our notion of system includes these, modelled say in the form of chemical reaction networks or Markov processes, or the compartmental models of epidemiology, population biology, and ecology. From computer science, we consider Petri nets, automata, logic circuits, and the like. More abstractly, our notion of system encompasses matrices and systems of differential equations.

Drawing together these notions of system are well-developed diagrammatic representations based on network diagrams— that is, topological graphs. We call these network-style diagrammatic languages. In abstract, by ‘system’ we shall simply mean that which can be represented by a box with a collection of terminals, perhaps of different types, through which it interfaces with the surroundings. Concretely, one might envision a circuit diagram with terminals, such as

or

The algebraic structure of interconnection is then simply the structure that results from the ability to connect terminals of one system with terminals of another. This graphical approach motivates our language of interconnection: indeed, these diagrams will be the expressions of our language.

We claim that the existence of a network-style diagrammatic language to represent a system implies that interconnection is inherently important in understanding the system. Yet, while each of these example notions of system are well-studied in and of themselves, their compositional, or algebraic, structure has received scant attention. In this thesis, we study an algebraic structure called a ‘hypergraph category’, and argue that this is the relevant algebraic structure for modelling interconnection of open systems.

Given these pre-existing diagrammatic formalisms and our visual intuition, constructing algebras of syntactic representations is thus rather straightforward. The semantics and their algebraic structure are more subtle.

In some sense our semantics is already given to us too: in studying these systems as closed systems, scientists have already formalised the meaning of these diagrams. But we have shifted from a closed perspective to an open one, and we need our semantics to also account for points of interconnection.

Taking inspiration from Willems’ behavioural approach and Deutsch’s constructor theory, in this thesis I advocate the following position. First, at each terminal of an open system we may make measurements appropriate to the type of terminal. Given a collection of terminals, the universum is then the set of all possible measurement outcomes. Each open system has a collection of terminals, and hence a universum. The semantics of an open system is the subset of measurement outcomes on the terminals that are permitted by the system. This is known as the behaviour of the system.

For example, consider a resistor of resistance This has two terminals—the two ends of the resistor—and at each terminal, we may measure the potential and the current. Thus the universum of this system is the set where the summands represent respectively the potentials and currents at each of the two terminals. The resistor is governed by Kirchhoff’s current law, or conservation of charge,
and Ohm’s law. Conservation of charge states that the current flowing into one terminal must equal the current flowing out of the other terminal, while Ohm’s law states that this current will be proportional to the potential difference, with constant of proportionality Thus the behaviour of the resistor is the set

Note that in this perspective a law such as Ohm’s law is a mechanism for partitioning behaviours into possible and impossible behaviours.

Interconnection of terminals then asserts the identification of the variables at the identified terminals. Fixing some notion of open system and subsequently an algebra of syntactic representations for these systems, our approach, based on the principle of compositionality, requires this to define an algebra of semantic objects and a homomorphism from syntax to semantics. The first part of this thesis develops the mathematical tools necessary to pursue this vision for modelling open systems and their interconnection.

The next goal is to demonstrate the efficacy of this philosophy in applications. At core, this work is done in the faith that the right language allows deeper insight into the underlying structure. Indeed, after setting up such a language for open systems there are many questions to be asked: Can we find a sound and complete logic for determining when two syntactic expressions have the same semantics? Suppose we have systems that have some property, for example controllability. In what ways can we interconnect controllable systems so that the combined system is also controllable? Can we compute the semantics of a large system quicker by computing the semantics of subsystems and then composing them? If I want a given system to achieve a specified trajectory, can we interconnect another system to make it do so? How do two different notions of system, such as circuit diagrams and signal flow graphs, relate to each other? Can we find homomorphisms between their syntactic and semantic algebras? In the second part of this thesis we explore some applications in depth, providing answers to questions of the above sort.

Outline of the thesis

The thesis is divided into two parts. Part I, comprising
Chapters 1 to 4, focuses on mathematical foundations. In it we develop the theory of hypergraph categories and a powerful tool for constructing and manipulating them: decorated corelations. Part II, comprising Chapters 5 to 7, then discusses applications of this theory to examples of open systems.

The central refrain of this thesis is that the syntax and semantics of network-style diagrammatic languages can be modelled by hypergraph categories. These are introduced in Chapter 1. Hypergraph categories are symmetric monoidal categories in which every object is equipped with the structure of a special commutative Frobenius monoid in a way compatible with the monoidal product. As we will rely heavily on properties of monoidal categories, their functors, and their graphical calculus, we begin with a whirlwind review of these ideas. We then provide a definition of hypergraph categories and their functors, a strictification theorem, and an important example: the category of cospans in a category with finite colimits.

A cospan is a pair of morphisms

with a common codomain. In Chapter 2 we introduce the idea of a ‘decorated cospan’, which equips the apex with extra structure. Our motivating example is cospans of finite sets decorated by labeled graphs, as in this picture:

Here graphs are a proxy for expressions in a network-style diagrammatic language. To give a bit more formal detail, let be a category with finite colimits, writing its as coproduct as and let be a braided monoidal category. Decorated cospans provide a method of producing a hypergraph category from a lax braided monoidal functor

The objects of these categories are simply the objects of while the morphisms are pairs comprising a cospan in together with an element in —the so-called decoration. We will also describe how to construct hypergraph functors between decorated cospan categories. In particular, this provides a useful tool for constructing a hypergraph category that captures the syntax of a network-style diagrammatic language.

Having developed a method to construct a category where the morphisms are expressions in a diagrammatic language, we turn our attention to categories of semantics. This leads us to the notion of a corelation, to which we devote Chapter 3. Given a factorisation system on a category we define a corelation to be a cospan such that the copairing of the two maps, a map is a morphism in Factorising maps using the factorisation system leads to a notion of equivalence on cospans, and this helps us describe when two diagrams are equivalent. Like cospans, corelations form hypergraph categories.

In Chapter 4 we decorate corelations. Like decorated cospans,
decorated corelations are corelations together with some additional structure on the apex. We again use a lax braided monoidal functor to specify the sorts of extra structure allowed. Moreover, decorated corelations too form the morphisms of a hypergraph category. The culmination of our theoretical work is to show that every hypergraph category and every hypergraph functor can be constructe using decorated corelations. This implies that we can use decorated corelations to construct a semantic hypergraph category for any network-style diagrammatic language, as well as a hypergraph functor from its syntactic category that interprets each diagram. We also discuss how the intuitions behind decorated corelations guide construction of these categories and functors.

Having developed these theoretical tools, in the second part we turn to demonstrating that they have useful applications. Chapter 5 uses corelations to formalise signal flow diagrams representing linear time-invariant discrete dynamical systems as morphisms in a category. Our main result gives an intuitive sound and fully complete equational theory for reasoning about these linear time-invariant systems. Using this framework, we derive a novel structural characterisation of controllability, and consequently provide a methodology for analysing controllability of networked and interconnected systems.

Chapter 6 studies passive linear networks. Passive linear networks are used in a wide variety of engineering applications, but the best studied are electrical circuits made of resistors, inductors and capacitors. The goal is to construct what we call the ‘black box functor’, a hypergraph functor from a category of open circuit diagrams to a category of behaviours of circuits. We construct the former as a decorated cospan category, with each morphism a cospan of finite sets decorated by a circuit diagram on the apex. In this category, composition describes the process of attaching the outputs of one circuit to the inputs of another. The behaviour of a circuit is the relation it imposes between currents and potentials at their terminals. The space of these currents and potentials naturally has the structure of a symplectic vector space, and the relation imposed by a circuit is a Lagrangian linear relation. Thus, the black box functor goes from our category of circuits to the category of symplectic vector spaces and Lagrangian linear relations. Decorated corelations provide a critical tool for constructing these hypergraph categories and the black box functor.

Finally, in Chapter 7 we mention two further research directions. The first is the idea of a ‘bound colimit’, which aims to describe why epi-mono factorisation systems are useful for constructing corelation categories of semantics for open systems. The second research direction pertains to applications of the black box functor for passive linear networks, discussing the work of Jekel on the inverse problem for electric circuits and the work of Baez, Fong, and Pollard on open Markov processes.

Complex Adaptive System Design (Part 2)

Yesterday Blake Pollard and I drove to Metron’s branch in San Diego. For the first time, I met four of the main project participants: John Foley (math), Thy Tran (programming), Tom Mifflin and Chris Boner (two higher-ups involved in the project). Jeff Monroe and Tiffany Change give us a briefing on Metron’s ExAMS software. This lets you design complex systems and view them in various ways.

The most fundamental view is the ‘activity trace’, which consists of a bunch of parallel rows, one for each ‘performer’. Each row has a bunch of boxes which represent ‘activities’ that the performer can do. Two boxes are connected by a wire when one box’s activity causes another to occur. In general, time goes from left to right. Thus, if B can only occur after A, the box for B is drawn to the right of the box for A.

The wires can also merge via logic gates. For example, suppose activity D occurs whenever A and B but not C have occurred. Then wires coming out of the A, B, and C boxes merge in a logic gate and go into the A box. However, these gates are a bit more general than your ordinary Boolean logic gates. They may also involve ‘delays’, e.g. we can say that A occurs 10 minutes after B occurs.

I would like to understand the mathematics of just these logic gates, for starters. Ignoring delays for a minute (get the pun?), they seem to be giving a generalization of Petri nets. In a Petri net we only get to use the logical connective ‘and’. In other words, an activity can occur when all of some other activities have occurred. People have considered various generalizations of Petri nets, and I think some of them allow more general logical connectives, but I’m forgetting where I saw this done. Do you know?

In the full-fledged activity traces, the ‘activity’ boxes also compute functions, whose values flow along the wires and serve as inputs to other box. That is, when an activity occurs, it produces an output, which depends on the inputs entering the box along input wires. The output then appears on the wires coming out of that box.

I forget if each activity box can have multiple inputs and multiple outputs, but that’s certainly a natural thing.

The fun part is that one one can zoom in on any activity trace, seeing more fine-grained descriptions of the activities. In this more fine-grained description each box turns into a number of boxes connected by wires. And perhaps each wire becomes a number of parallel wires? That would be mathematically natural.

Activity traces give the so-called ‘logical’ description of the complex system being described. There is also a much more complicated ‘physical’ description, saying the exact mechanical functioning of all the parts. These parts are described using ‘plugins’ which need to be carefully described ahead of time—but can then simply be used when assembling a complex system.

Our little team is supposed to be designing our own complex systems using operads, but we want to take advantage of the fact that Metron already has this working system, ExAMS. Thus, one thing I’d like to do is understand ExAMS in terms of operads and figure out how to do something exciting and new using this understanding. I was very happy when Tom Mifflin embraced this goal.

Unfortunately there’s no manual for ExAMS: the US government was willing to pay for the creation of this system, but not willing to pay for documentation. Luckily it seems fairly simple, at least the part that I care about. (There are a lot of other views derived from the activity trace, but I don’t need to worry about these.) Also, ExAMS uses some DoDAF standards which I can read about. Furthermore, in some ways it resembles UML and SySML, or more precisely, certain parts of these languages.

In particular, the ‘activity diagrams’ in UML are a lot like the activity traces in ExAMS. There’s an activity diagram at the top of this page, and another below, in which time proceeds down the page.

So, I plan to put some time into understanding the underlying math of these diagrams! If you know people who have studied them using ideas from category theory, please tell me.

Complex Adaptive System Design (Part 1)

In January of this year, I was contacted by a company called Metron Scientific Solutions. They asked if I’d like to join them in a project to use category theory to design and evaluate complex, adaptive systems of systems.

What’s a ‘system of systems’?

It’s a system made of many disparate parts, each of which is a complex system in its own right. The biosphere is a system of systems. But so far, people usually use this buzzword for large human-engineered systems where the different components are made by different organizations, perhaps over a long period of time, with changing and/or incompatible standards. This makes it impossible to fine-tune everything in a top-down way and have everything fit together seamlessly.

So, systems of systems are inherently messy. And yet we need them.

Metron was applying for a grant from DARPA, the Defense Advanced Research Projects Agency, which funds a lot of cutting-edge research for the US military. It may seem surprising that DARPA is explicitly interested in using category theory to study systems of systems. But it actually shouldn’t be surprising: their mission is to try many things and find a few that work. They are willing to take risks.

Metron was applying for a grant under a DARPA program run by John S. Paschkewitz, who is interested in

new paradigms and foundational approaches for the design of complex systems and system-of-systems (SoS) architectures.

This program is called CASCADE, short for Complex Adaptive System Composition and Design Environment. Here’s the idea:

Complex interconnected systems are increasingly becoming part of everyday life in both military and civilian environments. In the military domain, air-dominance system-of-systems concepts, such as those being developed under DARPA’s SoSITE effort, envision manned and unmanned aircraft linked by networks that seamlessly share data and resources in real time. In civilian settings such as urban “smart cities”, critical infrastructure systems—water, power, transportation, communications and cyber—are similarly integrated within complex networks. Dynamic systems such as these promise capabilities that are greater than the mere sum of their parts, as well as enhanced resilience when challenged by adversaries or natural disasters. But they are difficult to model and cannot be systematically designed using today’s tools, which are simply not up to the task of assessing and predicting the complex interactions among system structures and behaviors that constantly change across time and space.

To overcome this challenge, DARPA has announced the Complex Adaptive System Composition and Design Environment (CASCADE) program. The goal of CASCADE is to advance and exploit novel mathematical techniques able to provide a deeper understanding of system component interactions and a unified view of system behaviors. The program also aims to develop a formal language for composing and designing complex adaptive systems. A special notice announcing a Proposers Day on Dec. 9, 2015, was released today on FedBizOpps here: http://go.usa.gov/cT7uR.

“CASCADE aims to fundamentally change how we design systems for real-time resilient response within dynamic, unexpected environments,” said John Paschkewitz, DARPA program manager. “Existing modeling and design tools invoke static ‘playbook’ concepts that don’t adequately represent the complexity of, say, an airborne system of systems with its constantly changing variables, such as enemy jamming, bad weather, or loss of one or more aircraft. As another example, this program could inform the design of future forward-deployed military surgical capabilities by making sure the functions, structures, behaviors and constraints of the medical system—such as surgeons, helicopters, communication networks, transportation, time, and blood supply—are accurately modeled and understood.”

CASCADE could also help the Department of Defense fulfill its role of providing humanitarian assistance in response to a devastating earthquake, hurricane or other catastrophe, by developing comprehensive response models that account for the many components and interactions inherent in such missions, whether in urban or austere environs.

“We need new design and representation tools to ensure resilience of buildings, electricity, drinking water supply, healthcare, roads and sanitation when disaster strikes,” Paschkewitz said. “CASCADE could help develop models that would provide civil authorities, first responders and assisting military commanders with the sequence and timing of critical actions they need to take for saving lives and restoring critical infrastructure. In the stress following a major disaster, models that could do that would be invaluable.”

The CASCADE program seeks expertise in the following areas:

• Applied mathematics, especially in category theory, algebraic geometry and topology, and sheaf theory

• Operations research, control theory and planning, especially in stochastic and non-linear control

• Modeling and applications responsive to challenges in battlefield medicine logistics and platforms, adaptive logistics, reliability, and maintenance

• Search and rescue platforms and modeling

• Adaptive and resilient urban infrastructure

Metron already designs systems of systems used in Coast Guard search and rescue missions. Their grant proposal was to use category theory and operads to do this better. They needed an academic mathematician as part of their team: that was one of the program’s requirements. So they asked if I was interested.

I had mixed feelings.

On the one hand, I come from a line of peaceniks including Joan Baez, Mimi Fariña, their father the physicist Albert Baez, and my parents. I don’t like how the US government puts so much energy into fighting wars rather than solving our economic, social and environmental problems. It’s interesting that ‘systems of systems engineering’, as a field, is so heavily dominated by the US military. It’s an important subject that could be useful in many ways. We need it for better energy grids, better adaptation to climate change, and so on. I dream of using it to develop ‘ecotechnology’: technology that works with nature instead of trying to battle it and defeat it. But it seems the US doesn’t have the money, or the risk-taking spirit, to fund applications of category theory to those subjects.

On the other hand, I was attracted by the prospect of using category theory to design complex adaptive systems—and using it not just to tackle foundational issues, but also concrete challenges. I liked the idea of working with a team of people who are more practical than me. In this project, a big part of my job would be to write and publish papers: that’s something I can do. But Metron had other people who would try to create prototypes of software for helping the Coast Guard design search and rescue missions.

So I was torn.

In fact, because of my qualms, I’d already turned down an offer from another company that was writing a proposal for the CASCADE program. But the Metron project seemed slightly more attractive—I’m not sure why, perhaps because it was described to me in a more concrete way. And unlike that other company, Metron has a large existing body of software for evaluating complex systems, which should help me focus my theoretical ideas. The interaction between theory and practice can make theory a lot more interesting.

Something tipped the scales and I said yes. We applied for the grant, and we got it.

And so, an interesting adventure began. It will last for 3 years, and I’ll say more about it soon.

Topological Crystals (Part 4)

Okay, let’s look at some examples of topological crystals. These are what got me excited in the first place. We’ll get some highly symmetrical crystals, often in higher-dimensional Euclidean spaces. The ‘triamond’, above, is a 3d example.

Review

First let me remind you how it works. We start with a connected graph This has a space of 0-chains, which are formal linear combinations of vertices, and a space of 1-chains, which are formal linear combinations of edges.

We choose a vertex in Each path in starting at this vertex determines a 1-chain namely the sum of its edges. These 1-chains give some points in These points are the vertices of a graph called the maximal abelian cover of The maximal abelian cover has an edge from to whenever the path is obtained by adding an extra edge to We can think of this edge as a straight line segment from to

So, we get a graph sitting inside But this is a high-dimensional space. To get something nicer we’ll project down to a lower-dimensional space.

There’s boundary operator

sending any edge to the difference of its two endpoints. The kernel of this operator is the space of 1-cycles, There’s an inner product on the space of 1-chains such that edges form an orthonormal basis, so we get an orthogonal projection

We can use this to take the maximal abelian cover and project it down to the space of 1-cycles. The hard part is checking that is one-to-one on But that’s what I explained last time! It’s true whenever our original graph has no bridges: that is, edges whose removal would disconnect our graph, like this:

So, when is a bridgeless graph, we get a copy of the maximal abelian cover embedded in This is our topological crystal.

Let’s do some examples.

Graphene

I showed you this one before, but it’s a good place to start. Let be this graph:

Since this graph has 3 edges, its space of 1-chains is 3-dimensional. Since this graph has 2 holes, its 1-cycles form a plane in that 3d space. If we take paths in starting at the red vertex, form the 1-chains and project them down to this plane, we get this:

Here the 1-chains are the white and red dots. They’re the vertices of the maximal abelian cover while the line segments between them are the edges of Projecting these vertices and edges onto the plane of 1-cycles, we get our topological crystal:

This is the pattern of graphene, a miraculous 2-dimensional form of carbon. The more familiar 3d crystal called graphite is made of parallel layers of graphene connected with some other bonds.

Puzzle 1. Classify bridgeless connected graphs with 2 holes (or more precisely, a 2-dimensional space of 1-cycles). What are the resulting 2d topological crystals?

Diamond

Now let’s try this graph:

Since it has 3 holes, it gives a 3d crystal:

This crystal structure is famous! It’s the pattern used by a diamond. Up to translation it has two kinds of atoms, corresponding to the two vertices of the original graph.

Triamond

Now let’s try this graph:

Since it has 3 holes, it gives another 3d crystal:

This is also famous: it’s sometimes called a ‘triamond’. If you’re a bug crawling around on this crystal, locally you experience the same topology as if you were crawling around on a wire-frame model of a tetrahedron. But you’re actually on the maximal abelian cover!

Up to translation the triamond has 4 kinds of atoms, corresponding to the 4 vertices of the tetrahedron. Each atom has 3 equally distant neighbors lying in a plane at 120° angles from each other. These planes lie in 4 families, each parallel to one face of a regular tetrahedron. This structure was discovered by the crystallographer Laves, and it was dubbed the Laves graph by Coxeter. Later Sunada called it the ‘ lattice’ and studied its energy minimization properties. Theoretically it seems to be a stable form of carbon. Crystals in this pattern have not yet been seen, but this pattern plays a role in the structure of certain butterfly wings.

Puzzle 2. Classify bridgeless connected graphs with 3 holes (or more precisely, a 3d space of 1-cycles). What are the resulting 3d topological crystals?

Lonsdaleite and hyperquartz

There’s a crystal form of carbon called lonsdaleite that looks like this:

It forms in meteor impacts. It does not arise as 3-dimensional topological crystal.

Puzzle 3. Show that this graph gives a 5-dimensional topological crystal which can be projected down to give lonsdaleite in 3d space:

Puzzle 4. Classify bridgeless connected graphs with 4 holes (or more precisely, a 4d space of 1-cycles). What are the resulting 4d topological crystals? A crystallographer with the wonderful name of Eon calls this one hyperquartz, because it’s a 4-dimensional analogue of quartz:

All these classification problems are quite manageable if you notice there are certain ‘boring’, easily understood ways to get new bridgeless connected graphs with holes from old ones.

Platonic crystals

For any connected graph there is a covering map

The vertices of come in different kinds, or ‘colors’, depending on which vertex of they map to. It’s interesting to look at the group of ‘covering symmetries’, consisting of all symmetries of that map vertices of same color to vertices of the same color. Greg Egan and I showed that if has no bridges, also acts as symmetries of the topological crystal associated to This group fits into a short exact sequence:

where is the group of all symmetries of Thus, every symmetry of is covered by some symmetry of its topological crystal, while acts as translations of the crystal, in a way that preserves the color of every vertex.

For example consider the triamond, which comes from the tetrahedron. The symmetry group of the tetrahedron is this Coxeter group:

Thus, the group of covering symmetries of the triamond is an extension of by Beware the notation here: this is not the alternating group on the 3 letters. In fact it’s the permutation group on 4 letters, namely the vertices of the tetrahedron!

We can also look at other ‘Platonic crystals’. The symmetry group of the cube and octahedron is the Coxeter group

Since the cube has 6 faces, the graph formed by its vertices and edges a 5d space of 1-cycles. The corresponding topological crystal is thus 5-dimensional, and its group of covering symmetries is an extension of by Similarly, the octahedron gives a 7-dimensional topological crystal whose group of covering symmetries, an extension of by

The symmetry group of the dodecahedron and icosahedron is

and these solids give crystals of dimensions 11 and 19. If you’re a bug crawling around on the the second of these, locally you experience the same topology as if you were crawling around on a wire-frame model of a icosahedron. But you’re actually in 19-dimensional space, crawling around on the maximal abelian cover!

There is also an infinite family of degenerate Platonic solids called ‘hosohedra’ with two vertices, edges and faces. These faces cannot be made flat, since each face has just 2 edges, but that is not relevant to our construction: the vertices and edges still give a graph. For example, when we have the ‘hexagonal hosohedron’:

The corresponding crystal has dimension and its group of covering symmetries is an extension of by The case gives the graphene crystal, while gives the diamond.

Exotic crystals

We can also get crystals from more exotic highly symmetrical graphs. For example, take the Petersen graph:

Its symmetry group is the symmetric group It has 10 vertices and 15 edges, so its Euler characteristic is which implies that its space of 1-cycles is 6-dimensional. It thus gives a 6-dimensional crystal whose group of covering symmetries is an extension of by

Two more nice examples come from Klein’s quartic curve, a Riemann surface of genus three on which the 336-element group acts as isometries. These isometries preserve a tiling of Klein’s quartic curve by 56 triangles, with 7 meeting at each vertex. This picture is topologically correct, though not geometrically:

From this tiling we obtain a graph embedded in Klein’s quartic curve. This graph has edges and vertices, so it has Euler characteristic It thus gives a 61-dimensional topological crystal whose group of covering symmetries is extension of by

There is also a dual tiling of Klein’s curve by 24 heptagons, 3 meeting at each vertex. This gives a graph with 84 edges and 56 vertices, hence Euler characteristic From this we obtain a 29-dimensional topological crystal whose group of covering symmetries is an extension of by

The packing fraction

Now that we’ve got a supply of highly symmetrical crystals in higher dimensions, we can try to study their structure. We’ve only made a bit of progress on this.

One interesting property of a topological crystal is its ‘packing fraction’. I like to call the vertices of a topological crystal atoms, for the obvious reason. The set of atoms is periodic. It’s usually not a lattice. But it’s contained in the lattice obtained by projecting the integral 1-chains down to the space of 1-cycles:

We can ask what fraction of the points in this lattice are actually atoms. Let’s call this the packing fraction. Since acts as translations on both and we can define it to be

For example, suppose is the graph that gives graphene:

Then the packing fraction is 2/3, as can be seen here:

For any bridgeless connected graph it turns out that the packing fraction equals

where is the set of vertices and is the set of spanning trees. The main tool used to prove this is Bacher, de la Harpe and Nagnibeda’s work on integral cycles and integral cuts, which in turn relies on Kirchhoff’s matrix tree theorem.

Greg Egan used Mathematica to count the spanning trees in the examples discussed above, and this let us work out their packing fractions. They tend to be very low! For example, the maximal abelian cover of the dodecahedron gives an 11-dimensional crystal with packing fraction 1/27,648, while the heptagonal tiling of Klein’s quartic gives a 29-dimensional crystal with packing fraction 1/688,257,368,064,000,000.

So, we have some very delicate, wispy crystals in high-dimensional spaces, built from two simple ideas in topology: the maximal abelian cover of a graph, and the natural inner product on 1-chains. They have intriguing connections to tropical geometry, but they are just beginning to be understood in detail. Have fun with them!

For more, see:

• John Baez, Topological crystals.

Read the whole series

• Part 1 – the basic idea.

• Part 2 – the maximal abelian cover of a graph.

• Part 3 – constructing topological crystals.

• Part 4 – examples of topological crystals.