Applied Category Theory 2019

7 February, 2019

I hope to see you at this conference, which will occur right before the associated school meets in Oxford:

Applied Category Theory 2019, July 15-19, 2019, Oxford, UK.

Applied category theory is a topic of interest for a growing community of researchers, interested in studying systems of all sorts using category-theoretic tools. These systems are found in the natural sciences and social sciences, as well as in computer science, linguistics, and engineering. The background and experience of our members is as varied as the systems being studied. The goal of the ACT2019 Conference is to bring the majority of researchers in the field together and provide a platform for exposing the progress in the area. Both original research papers as well as extended abstracts of work submitted/accepted/published elsewhere will be considered.

There will be best paper award(s) and selected contributions will be awarded extended keynote slots.

The conference will include a business showcase and tutorials, and there also will be an adjoint school, the following week (see webpage).

Important dates

Submission of contributed papers: 3 May
Acceptance/Rejection notification: 7 June

Submissions

Prospective speakers are invited to submit one (or more) of the following:

• Original contributions of high quality work consisting of a 5-12 page extended abstract that provides sufficient evidence of results of genuine interest and enough detail to allow the program committee to assess the merits of the work. Submissions of works in progress are encouraged but must be more substantial than a research proposal.

• Extended abstracts describing high quality work submitted/published elsewhere will also be considered, provided the work is recent and relevant to the conference. These consist of a maximum 3 page description and should include a link to a separate published paper or preprint.

The conference proceedings will be published in a dedicated Proceedings issue of the new Compositionality journal:

http://www.compositionality-journal.org

Only original contributions are eligible to be published in the proceedings.

Submissions should be prepared using LaTeX, and must be submitted in PDF format. Use of the Compositionality style is encouraged. Submission is done via EasyChair:

https://easychair.org/conferences/?conf=act2019

Program chairs

John Baez (U.C. Riverside)
Bob Coecke (University of Oxford)

Program committee

Bob Coecke (chair)
John Baez (chair)
Christina Vasilakopoulou
David Moore
Josh Tan
Stefano Gogioso
Brendan Fong
Steve Lack
Simona Paoli
Joachim Kock
Kathryn Hess Bellwald
Tobias Fritz
David I. Spivak
Ross Duncan
Dan Ghica
Valeria de Paiva
Jeremy Gibbons
Samuel Mimram
Aleks Kissinger
Jamie Vicary
Martha Lewis
Nick Gurski
Dusko Pavlovic
Chris Heunen
Corina Cirstea
Helle Hvid Hansen
Dan Marsden
Simon Willerton
Pawel Sobocinski
Dominic Horsman
Nina Otter
Miriam Backens

Steering committee

John Baez (U.C. Riverside)
Bob Coecke (University of Oxford)
David Spivak (M.I.T.)
Christina Vasilakopoulou (U.C. Riverside)


Fermat Primes and Pascal’s Triangle

5 February, 2019

If you take the entries Pascal’s triangle mod 2 and draw black for 1 and white for 0, you get a pleasing pattern:

The 2^nth row consists of all 1’s. If you look at the triangle consisting of the first 2^n rows, and take the limit as n \to \infty, you get a fractal called the Sierpinski gasket. This can also be formed by repeatedly cutting triangular holes out of an equilateral triangle:

Something nice happens if you interpret the rows of Pascal’s triangle mod 2 as numbers written in binary:

1 = 1
11 = 3
101 = 5
1111 = 15
10001 = 17
110011 = 51
1010101 = 85
11111111 = 255
100000001 = 257

Notice that some of these rows consist of two 1’s separated by a row of 0’s. These give the famous ‘Fermat numbers‘:

11 = 3 = 2^{2^0} + 1
101 = 5 = 2^{2^1} + 1
10001 = 17 = 2^{2^2} + 1
10000001 = 257 = 2^{2^3} + 1
1000000000000001 = 65537 = 2^{2^4} + 1

The numbers listed above are all prime. Based on this evidence Fermat conjectured that all numbers of the form 2^{2^n} + 1 are prime. But Euler crushed this dream by showing that the next Fermat number, 2^{2^5} + 1, is not prime.

Indeed, even today, no other Fermat numbers are known to be prime! People have checked all of them up to 2^{2^{32}} + 1. They’ve even checked a few bigger ones, the largest being

2^{2^{3329780}} + 1

which turns out to be divisible by

193 \times 2^{3329782} + 1

Here are some much easier challenges:

Puzzle 1. Show that every row of Pascal’s triangle mod 2 corresponds to a product of distinct Fermat numbers:

1 = 1
11 = 3
101 = 5
1111 = 15 = 3 × 5
10001 = 17
110011 = 51 = 3 × 17
1010101 = 85 = 5 × 17
11111111 = 255 = 3 × 5 × 17
100000001 = 257

and so on. Also show that every product of distinct Fermat numbers corresponds to a row of Pascal’s triangle mod 2. What is the pattern?

By the way: the first row, 1, corresponds to the empty product.

Puzzle 2. Show that the product of the first n Fermat numbers is 2 less than the next Fermat number:

3 + 2 = 5
3 × 5 + 2 = 17
3 × 5 × 17 + 2 = 257
3 × 5 × 17 × 257 + 2 = 65537

and so on.

Now, Gauss showed that we can construct a regular n-gon using straight-edge and compass if n is a prime Fermat number. Wantzel went further and showed that if n is odd, we can construct a regular n-gon using straight-edge and compass if and only if n is a product of distinct Fermat primes.

We can construct other regular polygons from these by repeatedly bisecting the angles. And it turns out that’s all:

Gauss–Wantzel Theorem. We can construct a regular n-gon using straight-edge and compass if and only if n is a power of 2 times a product of distinct Fermat primes.

There are only 5 known Fermat primes: 3, 5, 17, 257 and 65537. So, our options for constructing regular polygons with an odd number of sides are extremely limited! There are only 2^5 = 32 options, if we include the regular 1-gon.

Puzzle 3. What is a regular 1-gon? What is a regular 2-gon?

And, as noted in The Book of Numbers by Conway and Guy, the 32 constructible regular polygons with an odd number of sides correspond to the first 32 rows of Pascal’s triangle!

1 = 1
11 = 3
101 = 5
1111 = 15 = 3 × 5
10001 = 17
110011 = 51 = 3 × 17
1010101 = 85 = 5 × 17
11111111 = 255 = 3 × 5 × 17
100000001 = 257
1100000011 = 771 = 3 × 257
10100000101 = 1285 = 5 × 257
101010010101 = 3855 = 3 × 5 × 257

and so on. Here are all 32 rows, borrowed from the Online Encylopedia of Integer Sequences:

Click to enlarge! And here are all 32 odd numbers n for which we know that a regular n-gon is constructible by straight-edge and compass:

1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765, 4294967295

So, the largest known odd n for which a regular n-gon is constructible is 4294967295. This is the product of all 5 known Fermat primes:

4294967295 = 3 × 5 × 17 × 257 × 65537

Thanks to Puzzle 2, this is 2 less than the next Fermat number:

4294967295 = 2^{2^5} - 1

We can construct a regular polygon with one more side, namely

4294967296 = 2^{2^5}

sides, because this is a power of 2. But we can’t construct a regular polygon with one more side than that, namely

4294967297 = 2^{2^5} + 1

because Euler showed this Fermat number is not prime.

So, we’ve hit the end of the road… unless someone discovers another Fermat prime.


From Classical to Quantum and Back

30 January, 2019

Damien Calaque has invited me to speak at FGSI 2019, a conference on the Foundations of Geometric Structures of Information. It will focus on scientific legacy of Cartan, Koszul and Souriau. Since Souriau helped invent geometric quantization, I decided to talk about this. That’s part of why I’ve been writing about it lately!

I’m looking forward to speaking to various people at this conference, including Mikhail Gromov, who has become interested in using category theory to understand biology and the brain.

Here’s my talk:

From classical to quantum and back.

Abstract. Edward Nelson famously claimed that quantization is a mystery, not a functor. In other words, starting from the phase space of a classical system (a symplectic manifold) there is no functorial way of constructing the correct Hilbert space for the corresponding quantum system. In geometric quantization one gets around this problem by equipping the classical phase space with extra structure: for example, a Kähler manifold equipped with a suitable line bundle. Then quantization becomes a functor. But there is also a functor going the other way, sending any Hilbert space to its projectivization. This makes quantum systems into specially well-behaved classical systems! In this talk we explore the interplay between classical mechanics and quantum mechanics revealed by these functors going both ways.

For more details, read these articles:

  • Part 1: the mystery of geometric quantization: how a quantum state space is a special sort of classical state space.
  • Part 2: the structures besides a mere symplectic manifold that are used in geometric quantization.
  • Part 3: geometric quantization as a functor with a right adjoint, ‘projectivization’, making quantum state spaces into a reflective subcategory of classical ones.
  • Part 4: making geometric quantization into a monoidal functor.
  • Part 5: the simplest example of geometric quantization: the spin-1/2 particle.
  • Part 6: quantizing the spin-3/2 particle using the twisted cubic; coherent states via the adjunction between quantization and projectivization.
  • Part 7: the Veronese embedding as a method of ‘cloning’ a classical system, and taking the symmetric tensor powers of a Hilbert space as the corresponding method of cloning a quantum system.
  • Part 8: cloning a system as changing the value of Planck’s constant.

  • Systems as Wiring Diagram Algebras

    28 January, 2019

     

    Check out the video of Christina Vasilakopoulou’s talk, the third in the Applied Category Theory Seminar here at U. C. Riverside! It was nicely edited by Paola Fernandez and uploaded by Joe Moeller.

    Abstract. We will start by describing the monoidal category of labeled boxes and wiring diagrams and its induced operad. Various kinds of systems such as discrete and continuous dynamical systems have been expressed as algebras for that operad, namely lax monoidal functors into the category of categories. A major advantage of this approach is that systems can be composed to form a system of the same kind, completely determined by the specific way the composite systems are interconnected (‘wired’ together). We will then introduce a generalized system, called a machine, again as a wiring diagram algebra. On the one hand, this abstract concept is all-inclusive in the sense that discrete and continuous dynamical systems are sub-algebras; on the other hand, we can specify succinct categorical conditions for totality and/or determinism of systems that also adhere to the algebraic description.

    Reading material:

    • Patrick Schultz, David I. Spivak and Christina Vasilakopoulou, Dynamical systems and sheaves.

    • David I. Spivak, The operad of wiring diagrams: formalizing a graphical language for databases, recursion, and plug-and-play circuits.

    • Dmitry Vagner, David I. Spivak and Eugene Lerman, Algebras of open dynamical systems on the operad of wiring diagrams.


    Symposium on Compositional Structures 3

    28 January, 2019

    One of the most lively series of conferences on applied category theory is ‘SYCO’: the Symposium on Compositional Structures. And the next one is coming soon!

    Symposium on Compositional Structures 3, University of Oxford, 27-28 March, 2019.

    The Symposium on Compositional Structures (SYCO) is an interdisciplinary series of meetings aiming to support the growing community of researchers interested in the phenomenon of compositionality, from both applied and abstract perspectives, and in particular where category theory serves as a unifying common language. The first SYCO was in September 2018 at the University of Birmingham. The second SYCO was in December 2019, at the University of Strathclyde, each attracting about 70 people.

    We welcome submissions from researchers across computer science, mathematics, physics, philosophy, and beyond, with the aim of fostering friendly discussion, disseminating new ideas, and spreading knowledge between fields. Submission is encouraged for both mature research and work in progress, and by both established academics and junior researchers, including students.

    Submission is easy, with no format requirements or page restrictions. The meeting does not have proceedings, so work can be submitted even if it has been submitted or published elsewhere. Think creatively—you could submit a recent paper, or notes on work in progress, or even a recent Masters or PhD thesis.

    While no list of topics could be exhaustive, SYCO welcomes submissions with a compositional focus related to any of the following areas, in particular from the perspective of category theory:

    • logical methods in computer science, including classical and quantum programming, type theory, concurrency, natural language processing and machine learning;

    • graphical calculi, including string diagrams, Petri nets and
    reaction networks;

    • languages and frameworks, including process algebras, proof nets, type theory and game semantics;

    • abstract algebra and pure category theory, including monoidal
    category theory, higher category theory, operads, polygraphs, and
    relationships to homotopy theory;

    • quantum algebra, including quantum computation and representation theory;

    • tools and techniques, including rewriting, formal proofs and proof assistants, and game theory;

    • industrial applications, including case studies and real-world
    problem descriptions.

    This new series aims to bring together the communities behind many previous successful events which have taken place over the last decade, including “Categories, Logic and Physics”, “Categories, Logicand Physics (Scotland)”, “Higher-Dimensional Rewriting and Applications”, “String Diagrams in Computation, Logic and Physics”, “Applied Category Theory”, the “Simons Workshop on Compositionality”, and the “Peripatetic Seminar in Sheaves and Logic”.

    SYCO will be a regular fixture in the academic calendar, running
    regularly throughout the year, and becoming over time a recognized venue for presentation and discussion of results in an informal and friendly atmosphere. To help create this community, and to avoid the need to make difficult choices between strong submissions, in the event that more good-quality submissions are received than can be accommodated in the timetable, the programme committee may choose to defer some submissions to a future meeting, rather than reject them. This would be done based largely on submission order, giving an incentive for early submission, but would also take into account other requirements, such as ensuring a broad scientific programme. Deferred submissions can be re-submitted to any future SYCO meeting, where they would not need peer review, and where they would be prioritised for inclusion in the programme. This will allow us to ensure that speakers have enough time to present their ideas, without creating an unnecessarily competitive reviewing process. Meetings will be held sufficiently frequently to avoid a backlog of deferred papers.

    Invited speakers

    • Marie Kerjean, INRIA Bretagne Atlantique

    • Alessandra Palmigiano, Delft University of Technology and University of Johannesburg

    Important dates

    All times are anywhere-on-earth.

    • Submission deadline: Friday 15 February 2019
    • Author notification: Wednesday 27 February 2019
    • Registration deadline: Wednesday 20 March 2019
    • Symposium dates: Wednesday 27 and Thursday 28 March 2019

    Submissions

    Submission is by EasyChair, via the following link:

    https://easychair.org/conferences/?conf=syco3

    Submissions should present research results in sufficient detail to allow them to be properly considered by members of the programme committee, who will assess papers with regards to significance, clarity, correctness, and scope. We encourage the submission of work in progress, as well as mature results. There are no proceedings, so work can be submitted even if it has been previously published, or has been submitted for consideration elsewhere. There is no specific formatting requirement, and no page limit, although for long submissions authors should understand that reviewers may not be able to read the entire document in detail.

    Financial support

    Some funding is available to cover travel and subsistence costs, with a priority for PhD students and junior researchers. To apply for this funding, please contact the local organizers Antonin Delpeuch (antonin.delpeuch@cs.ox.ac.uk) or Ben Musto (benjamin.musto@cs.ox.ac.uk) with subject line “SYCO 3 funding request” by March 6, with a short statement of your current status, travel costs and funding required.

    Programme committee

    Fatimah Ahmadi, University of Oxford
    Corina Cirstea, University of Southampton
    Bob Coecke, University of Oxford
    Carmen Maria Constantin, University of Oxford
    Antonin Delpeuch, University of Oxford
    Brendan Fong, Massachusetts Institute of Technology
    Dan Ghica, University of Birmingham
    Giuseppe Greco, Utrecht University
    Helle Hvid Hansen, Delft University
    Jules Hedges, University of Oxford
    Chris Heunen, University of Edinburgh
    Dominic Horsman, University of Grenoble
    Dimitri Kartsaklis, Apple
    Aleks Kissinger, Radboud University Nijmegen
    Alexander Kurz, Chapman University
    Jean-Simon Lemay, University of Oxford
    Martha Lewis, University of Amsterdam
    Dan Marsden, University of Oxford
    Samuel Mimram, École Polytechnique
    Nina Otter, UCLA
    Simona Paoli, University of Leicester
    Robin Piedeleu, University of Oxford
    David Reutter, University of Oxford
    Christine Tasson, Paris Diderot University
    Jamie Vicary, University of Birmingham
    Tamara von Glehn, University of Cambridge
    Quanlong Wang, University of Oxford
    Gijs Wijnholds, Queen Mary University of London
    Philipp Zahn, University of St.Gallen


    Classification Problems in Symplectic Linear Algebra

    21 January, 2019

     

    Last week Jonathan Lorand spoke at the Applied Category Theory Seminar here at UCR. Check out the video of his talk above, and also his talk slides.

    Abstract. In this talk we will look at various examples of classification problems in symplectic linear algebra: conjugacy classes in the symplectic group and its Lie algebra, linear lagrangian relations up to conjugation, tuples of (co)isotropic subspaces. I will explain how many such problems can be encoded using the theory of symplectic poset representations, and will discuss some general results of this theory. Finally, I will recast this discussion from a broader category-theoretic perspective.

    Here are some papers to read for more detail:

    • Jonathan Lorand, Classifying linear canonical relations.

    • Jonathan Lorand and Alan Weinstein, Decomposition of (co)isotropic relations.

    Lorand is working on a paper with Weinstein and Christian Herrman that delves deeper into these topics. I first met him at the ACT2018 school in Leiden, where we worked along with Blake Pollard, Fabrizio Genovese (shown below) and Maru Sarazola on biochemical coupling through emergent conservation laws. Right now he’s visiting UCR and working with me to dig deeper into these questions using symplectic geometry! This is a very tantalizing project that keeps on not quite working…


    Geometric Quantization (Part 8)

    21 January, 2019

     

    Let’s start with a puzzle:

    Puzzle. You measure the energy and frequency of some laser light trapped in a mirrored box and use quantum mechanics to compute the expected number of photons in the box. Then someone tells you that you used the wrong value of Planck’s constant in your calculation. Somehow you used a value that was twice the correct value! How should you correct your calculation of the expected number of photons?

    I’ll give away the answer to the puzzle below, so avert your eyes if you want to think about it more.

    This scenario sounds a bit odd—it’s not very likely that your table of fundamental constants would get Planck’s constant wrong this way. But it’s interesting because once upon a time we didn’t know about quantum mechanics and we didn’t know Planck’s constant. We could still give a reasonably good description of some laser light trapped in a mirrored box: there’s a standing wave solution of Maxwell’s equations that does the job. But when we learned about quantum mechanics we learned to describe this situation using photons. The number of photons we need depends on Planck’s constant.

    And while we can’t really change Planck’s constant, mathematical physicists often like to treat Planck’s constant as variable. The limit where Planck’s constant goes to zero is called the ‘classical limit’, where our quantum description should somehow reduce to our old classical description.

    Here’s the answer to the puzzle: if you halve Planck’s constant you need to double the number of photons. The reason is that the energy of a photon with frequency \nu is h \nu. So, to get a specific total energy E in our box of light of a given frequency, we need E/h \nu photons.

    So, the classical limit is also the limit where the expected number of photons goes to infinity! As the ‘packets of energy’ get smaller, we need more of them to get a certain amount of energy.

    This has a nice relationship to what I’d been doing with geometric quantization last time.

    I explained how we could systematically replace any classical system considering by a ‘cloned’ version of that system: a collection of identical copies constrained to all lie in the same state. The set of allowed states is the same, but the symplectic structure is multiplied by a constant factor: the number of copies. We can see this as follows: if the phase space of our system is an abstract symplectic manifold M its kth power M^k is again a symplectic manifold. We can look at the image of the diagonal embedding

    \begin{array}{rcl}  \Delta_k \colon M &\to & M^k \\          x & \mapsto & (x,x,\dots, x)  \end{array}

    The image is a symplectic submanifold of M^k, and it’s diffeomorphic to M, but \Delta_k is not a symplectomorphism from M to its image. The image has a symplectic structure that’s k times bigger!

    What does this mean for physics?

    If we act like physicists instead of mathematicians for a minute and keep track of units, we’ll notice that the naive symplectic structure in classical mechanics has units of action: think \omega = dp \wedge dq. Planck’s constant also has units of action, so to get a dimensionless version of the symplectic structure, we should use \omega/h. Then it’s clear that multiplying the symplectic structure by k is equivalent to dividing Planck’s constant by k!

    So: cloning a system, multiplying the number of copies by k, should be related to dividing Planck’s constant by k. And the limit k \to \infty should be related to a ‘classical limit’.

    Of course this would not convince a mathematician so far, since I’m using a strange mix of ideas from classical mechanics and quantum mechanics! But our approach to geometric quantization makes everything precise. We have a category \texttt{Class} of classical systems, a category \texttt{Quant} of quantum systems, a quantization functor

    Q \colon \texttt{Class} \to \texttt{Quant}

    and a functor going back:

    P \colon \texttt{Quant} \to \texttt{Class}

    which reveals that quantum systems are special classical systems. And last time we saw that there are also ways to ‘clone’ classical and quantum systems.

    Our classical systems are more than mere symplectic manifolds: they are projectively normal subvarieties of \mathbb{C}\mathrm{P}^n for arbitrary n. So, we clone a classical system by a trick that looks more fancy than the diagonal embedding I mentioned above: we instead use the kth Veronese embedding, which defines a functor

    \nu_k \colon \texttt{Class} \to \texttt{Class}

    But this cloning process has the same effect on the underlying symplectic manifold: it multiplies the symplectic structure by k.

    Similarly, we clone a quantum system by replacing its set of states \mathrm{P}(\mathbb{C}^n) (the projectivization of the Hilbert space \mathbb{C}^n) by \mathrm{P}(S^k(\mathbb{C}^n)), where S^k is the kth symmetric power. This gives a functor

    S^k \colon \texttt{Quant} \to \texttt{Quant}

    and the ‘obvious squares commute’:

    \texttt{Q} \circ v_k = S^k \circ \texttt{Q}
    \texttt{P} \circ S^k = v_k \circ \texttt{P}

    All I’m doing now is giving this math a new physical interpretation: the k-fold cloning process is the same as dividing Planck’s constant by k!

    If this seems a bit elusive, we can look at an example like the spin-j particle. In Part 6 we saw that if we clone the state space for the spin-1/2 particle we get the state space for the spin-j particle, where j = k/2. But angular momentum has units of Planck’s constant, and the quantity j is really an angular momentum divided by \hbar. So this process of replacing 1/2 by k/2 can be reinterpreted as the process of dividing Planck’s constant by k: if Planck’s constant is smaller, we need j to be bigger to get a given angular momentum! And what we thought was a single spin-1/2 particle in the state \psi becomes k spin-1/2 particles in the ‘cloned’ state \psi \otimes \psi \otimes \cdots \otimes \psi. As explained in Part 6, we can reinterpret this as a state of a single spin-k/2 particle.

    Finally, let me point out something curious. We have a systematic way of changing our description of a quantum system when we divide Planck’s constant by an integer. But we can’t do it when we divide Planck’s constant by any other sort of number! So, in a very real sense, Planck’s constant is quantized.


    Part 1: the mystery of geometric quantization: how a quantum state space is a special sort of classical state space.

    Part 2: the structures besides a mere symplectic manifold that are used in geometric quantization.

    Part 3: geometric quantization as a functor with a right adjoint, ‘projectivization’, making quantum state spaces into a reflective subcategory of classical ones.

    Part 4: making geometric quantization into a monoidal functor.

    Part 5: the simplest example of geometric quantization: the spin-1/2 particle.

    Part 6: quantizing the spin-3/2 particle using the twisted cubic; coherent states via the adjunction between quantization and projectivization.

    Part 7: the Veronese embedding as a method of ‘cloning’ a classical system, and taking the symmetric tensor powers of a Hilbert space as the corresponding method of cloning a quantum system.

    Part 8: cloning a system as changing the value of Planck’s constant.