Applied Category Theory 2023

You can now submit a paper if you want to give a talk here:

• 6th Annual International Conference on Applied Category Theory (ACT2023), University of Maryland, July 31 — August 4, 2023

The Sixth International Conference on Applied Category Theory will take place at the University of Maryland from 31 July to 4 August 2023, preceded by the Adjoint School 2023 from 24 to 28 July. This event will be hybrid.

This conference follows previous events at Strathclyde (UK), Cambridge (UK), Cambridge (MA), Oxford (UK) and Leiden (NL). Applied category theory is important to a growing community of researchers who study computer science, logic, engineering, physics, biology, chemistry, social science, systems, linguistics and other subjects using category-theoretic tools. The background and experience of our members is as varied as the systems being studied. The goal of the Applied Category Theory conference series is to bring researchers together, strengthen the applied category theory community, disseminate the latest results, and facilitate further development of the field.

Submissions

There are three submission formats:

1. Conference Papers should present original, high-quality work in the style of a computer science conference paper (up to 12 pages, not counting the bibliography; more detailed parts of proofs may be included in an appendix for the convenience of the reviewers). Such submissions should not be an abridged version of an existing journal article although pre-submission arXiv preprints are permitted. These submissions will be adjudicated for both a talk and publication in the conference proceedings.

2. Talk proposals not to be published in the proceedings, e.g. about work accepted/submitted/published elsewhere, should be submitted as abstracts, one or two pages long. Authors are encouraged to include links to any full versions of their papers, preprints or manuscripts. The purpose of the abstract is to provide a basis for determining the topics and quality of the anticipated presentation.

3. Software demonstration proposals should also be submitted as abstracts, one or two pages. The purpose of the abstract is to provide the program committee with enough information to assess the content of the demonstration.

The original conference papers will ultimately be published with EPTCS, and authors are advised to use the style files available at style.eptcs.org.

Please submit your papers and talk proposals here:

• OpenReview.

You will need to create an account or log in. Please tell OpenReview as much as you can about yourself, and your past papers, because it uses this to automatically calculate conflict of interest. (Reviewing is single-blind, and we are not making public the reviews, reviewer names, the discussions nor the list of under-review submissions. This is the same as previous instances of ACT.) The exact deadline time on these dates is given by anywhere on earth (AoE).

Important dates

The following dates are all in 2023, and Anywhere On Earth.

• Submission Deadline: Wednesday 3 May

• Author Notification: Wednesday 7 June

• Camera-ready version due: Tuesday 27 June

• Conference begins: 31 July

Program committee

Benedikt Ahrens

Mario Álvarez Picallo

Matteo Capucci

Titouan Carette

Bryce Clarke

Carmen Constantin

Geoffrey Cruttwell

Giovanni de Felice

Bojana Femic

Marcelo Fiore

Fabio Gadducci

Zeinab Galal

Richard Garner

Neil Ghani

Tamara von Glehn

Amar Hadzihasanovic

Masahito Hasegawa

Martha Lewis

Sophie Libkind

Rory Lucyshyn-Wright

Sandra Mantovanni

Jade Master

Konstantinos Meichanetzidis

Stefan Milius

Mike Mislove

Sean Moss

David Jaz Myers

Susan Niefield

Paige Randall North

Jason Parker

Evan Patterson

Sophie Raynor

Emily Roff

Morgan Rogers

Mario Román

Maru Sarazola

Bas Spitters

Sam Staton (co-chair)

Dario Stein

Eswaran Subrahmanian

Walter Tholen

Christina Vasilakopoulou (co-chair)

Christine Vespa

Simon Willerton

Glynn Winskel

Vladimir Zamdzhiev

Fabio Zanasi

Organizing committee

James Fairbanks, University of Florida

Joe Moeller, National Institute for Standards and Technology, USA

Sam Staton, Oxford University

Priyaa Varshinee Srinivasan, National Institute for Standards and Technology, USA

Christina Vasilakopoulou, National Technical University of Athens

Steering committee

John Baez, University of California, Riverside

Bob Coecke, Cambridge Quantum

Dorette Pronk, Dalhousie University

David Spivak, Topos Institute

Mathematics for Humanity

We discussed this here earlier, but now it’s actually happening!

The International Centre for Mathematical Sciences, or ICMS, in Edinburgh, will host a new project entitled ‘Mathematics for Humanity’. This will be devoted to education, research, and scholarly exchange having direct relevance to the ways in which mathematics can contribute to the betterment of humanity. Submitted proposals are due on June 1st, 2023.

The activities of the program will revolve around three interrelated themes:

A. Integrating the global research community (GRC)

B. Mathematical challenges for humanity (MCH)

C. Global history of mathematics (GHM)

Development of the three themes will facilitate the engagement of the international mathematical community with the challenges of accessible education, knowledge-driven activism, and transformative scholarship.

For theme A, a coherent plan of activities for an extended period can be presented (at least 2 weeks, and up to to 3 months), comprising courses and seminars bringing together researchers from at least two different regions, which should be combined with networking activities and hybrid dissemination. Themes B and C would also comprise individual collaborative events.

Within each of the three themes, researchers can apply for one of the following activities:

1. Research-in-groups. This is a proposal for a small group of 3 to 6 researchers to spend from 2 weeks to 3 months in Edinburgh on a reasonably well-defined research project. The researchers will be provided working space and funds for accommodation and subsistence.

2. Research course or seminar. A group of researchers can propose a course or a seminar on topics relevant to one of the three themes. These should be planned as hybrid events with regular meetings in Edinburgh that can also be accessed online. Proposals should come with a detailed plan for attracting interest and for the dissemination of ideas.

3. Research workshops. These are 5-day workshops in the standard ICMS format, of course with a focus on one of the three themes.

4. Research school. These are hybrid schools of two-weeks length on one of the themes. These should come with substantial planning, a coherent structure, and be aimed towards post-graduate students and early career researchers.

The ICMS expects that up to 30 researchers will be in residence in Edinburgh at any given time over a 9-month period, which might be divided into three terms, mid-September to mid-December, mid-January to mid-April, and mid-April to mid-July. Every effort will be made to provide a unified facility for the activities of all groups working on all three themes, thereby encouraging a synergistic exchange of ideas and vision. The proposals will be reviewed twice a year soon after the spring deadline of 15 April and the autumn deadline of 15 November.

Project Summary

Submission Guidelines

Scientific Committee

Queries about the project should be sent to ICMS director Minhyong Kim or deputy director Beatrice Pelloni, who will be aided by the Scientific Committee in the selection of proposals:

• John Baez (UC Riverside)                            • Karine Chemla (Paris)

• Sophie Dabo-Niang (Lille)                           • Reviel Netz (Stanford)

• Bao Chau Ngo (Chicago and VIASM)            • Raman Parimala (Emory)

• Fernando Rodriguez Villegas (ICTP, Trieste)  • Terence Tao (UCLA)

A Curious Integral

On Mathstodon, Robin Houston pointed out a video where Oded Margalit claimed that it’s an open problem why this integral:

is so absurdly close to but not quite equal.

They agree to 41 decimal places, but they’re not the same!

while

So, a bunch of us tried to figure out what was going on.

Jaded nonmathematicians told us it’s just a coincidence, so what is there to explain? But of course an agreement this close is unlikely to be “just a coincidence”. It might be, but you’ll never get anywhere in math with that attitude.

We were reminded of the famous cosine Borwein integral

which equals for up to and including 55, but not for any larger

But it was Sean O who really cracked the case, by showing that the integral we were struggling with could actually be reduced to an version of the cosine Borwein integral, namely

The point is this. A little calculation using the Weierstrass factorizations

lets you show

and thus

Then, a change of variables on the right-hand side gives

So, showing that

is microscopically less than is equivalent to showing that

is microscopically less than

This sets up a clear strategy for solving the mystery! People understand why the cosine Borwein integral

equals for up to 55, and then drops ever so slightly below The mechanism is clear once you watch the right sort of movie. It’s very visual. Greg Egan explains it here with an animation, based on ideas by Hanspeter Schmid:

• John Baez, Patterns that eventually fail, Azimuth, September 20, 2018.

Or you can watch this video, which covers a simpler but related example:

• 3Blue1Brown, Researchers thought this was a bug (Borwein integrals).

So, we just need to show that as the value of the cosine Borwein integral doesn’t drop much more! It drops by just a tiny amount: about

Alas, this doesn’t seem easy to show. At least I don’t know how to do it yet. But what had seemed an utter mystery has now become a chore in analysis: estimating how much

drops each time you increase a bit.

At this point if you’re sufficiently erudite you are probably screaming: “BUT THIS IS ALL WELL-KNOWN!”

And you’re right! We had a lot of fun discovering this stuff, but it was not new. When I was posting about it on MathOverflow, I ran into an article that mentions a discussion of this stuff:

• Eric W. Weisstein, Infinite cosine product integral, from MathWorld—A Wolfram Web Resource.

and it turns out Borwein and his friends had already studied it. There’s a little bit here:

• J. M. Borwein, D. H. Bailey, V. Kapoor and E. W. Weisstein, Ten problems in experimental mathematics, Amer. Math. Monthly 113 (2006), 481–509.

and a lot more in this book:

• J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics: Computational Paths to Discovery, Wellesley, Massachusetts, A K Peters, 2004.

In fact the integral

was discovered by Bernard Mares at the age of 17. Apparently he posed the challenge of proving that it was less than Borwein and others dived into this and figured out how.

But there is still work left to do!

As far as I can tell, the known proofs that

all involve a lot of brute-force calculation. Is there a more conceptual way to understand this difference, at least approximately? There is a clear conceptual proof that

That’s what Greg Egan explained in my blog article. But can we get a clear proof that

for some small constant say or so?

One can argue that until we do, Oded Margalit is right: there’s an open problem here. Not a problem in proving that something is true. A problem in understanding why it is true.

Guillotine Partitions and the Hipparchus Operad

If you dissect a square into n similar rectangles, what proportions can these rectangles have? Folks on Mathstodon figured this out for n ≤ 7, and I blogged about it here recently. But I was left feeling that some deeper structure governed this problem.

Various people on Mathstodon, including Steven Stanicki, David Eppstein and Rahul Narain, convinced me of the importance of a certain class of dissections called ‘guillotine partitions’. I started suspecting that these were connected to an operad I once blogged about here: the ‘Hipparchus operad’. And last night I put some of the pieces together… though there is still more to do.

Last night I had insomnia, worrying about my aunt in a nursing home. To lull myself to sleep I thought about math. I had an idea about guillotine partitions.

In a ‘guillotine partition’ of a square you repeatedly slice off and remove rectangular pieces by cutting vertically or horizontally all the way through what’s left:

• Wikipedia, Guillotine partition.

There are 6 types of guillotine partition where you make 2 cuts, so we say the 2nd Schröder number is 6:

The first few Schröder numbers go like this:

etc. For example, since there are 22 types of guillotine partition of a square with 3 cuts, as shown below:

We can arrange it so the cuts always go through equally spaced points lying on a diagonal line. This is a cheap way to make the idea of ‘type’ precise: we only count guillotine partitions with this property.

(It’s probably better to define a ‘type’ of guillotine partition as an equivalence class under a certain equivalence relation. Briefly: if you start with a guillotine partition, and move a horizontal cut up or down without it hitting another horizontal cut, or move a vertical cut right or light without it hitting another vertical cut, you get a guillotine partition of the same type. The trick with equally spaced points is just a way to choose one representative guillotine partition of each type.)

You can read more about the Schröder numbers here:

• Wikipedia, Schröder number.

If we demand that the first cut be vertical we get half as many guillotine partitions… except when there are no cuts at all. This gives the ‘little Schröder numbers’:

etc. For example if we take the guillotine partitions with 3 cuts, and cross out those where the first cut is horizontal, we’re left with 11 of them:

You can read about the little Schröder numbers here:

• Wikipedia, Schröder–Hipparchus number.

The little Schröder numbers are now also called ‘Schröder–Hipparchus numbers’, because sometime between 50 and 120 AD Plutarch wrote:

Chrysippus says that the number of compound propositions that can be made from only ten simple propositions exceeds a million. Hipparchus, to be sure, refuted this by showing that on the affirmative side there are 103,049 compound statements….”

This was utterly mysterious until 1994, when David Hough, a math grad student, realized that 103,049 is the 9th little Schröder number!

Why was Hipparchus messing around with the little Schröder numbers around 150 BC?

It turns out the (n-1)st little Schröder number is also the number of planar trees with n leaves where each node has 0, or 2, or 3, or 4, or 5, etcetera, children. Anything but one child!

For example this tree with 8 leaves is one of 4279 such trees, since the 7th little Schröder number, , is 4279:

Hipparchus was probably studying such trees with 10 leaves! There are 103,049 of them.

But wait! Why is the nth little Schröder number both:

the number of types of guillotine partition of a square with n cuts, where the first cut is vertical

and

the number of planar trees with n+1 leaves where each node has any number of children except 1

?

This is what I figured out in my bout of insomnia, after connecting little Schröder numbers to guillotine partitions.

Here’s a better way to phrase the question: why is

the number of types of guillotine partition of a square into n rectangles, where the first cut is vertical

equal to

the number of planar trees with n leaves where each node has any number of children except 1

?

There’s a nice bijective proof. Here’s how you can set up a 1-1 correspondence between such trees and such types of guillotine partitions:

Each node of your tree corresponds to a rectangle. The top node corresponds to the whole square you are partitioning. Then, when a node has n children, you cut its rectangle into n smaller rectangles using parallel lines any way you want. These are the node’s children.

As you work down the tree you first cut with vertical lines, then horizontal, then vertical, etc.

So, the first cuts are always vertical!

Using this correspondence, types of guillotine partitions of a square into n rectangles where the first cut is vertical correspond to trees with n leaves where each node that’s not a leaf has at least two children!

Almost a decade ago, I noticed that such trees are also operations in the free operad on one operation of arity 2, one operation of arity 3, etc. You could say this is the operad for ‘unbiased magmas’. I wrote about this here, and I called it the ‘Hipparchus operad’:

• John Baez, The Hipparchus operad, April 1, 2013.

This blog post was a ‘meta-April-fool’s joke’, since it was strange, with a few jokes thrown in, but true in all important respects.

The Hipparchus operad has nice connections to other branches of math, as discussed in comments. For example the little Schröder numbers count the trees appearing when you barycentrically subdivide Stasheff’s associahedra! There are 11 trees here:

Each of these trees gives a type of guillotine partition of the square where the first cut is vertical.

So, there’s a lot to play with here!

I’m hoping this will help us understand this problem:

• John Baez, Dividing a square into similar rectangles.

This only works for similar rectangles forming a guillotine partition of the square. But those are very interesting! For those, I think we just need to take a tree of the sort I’m describing, and label each leaf with ‘vertical’ or ‘horizontal’, to say whether that rectangle is tall and skinny, or short and squat. But some more thought is required.

This is the sort of thing that happens sometimes when I try to fall asleep by diverting my mind away from more unpleasant subjects. Does something like this happen to you too?

Anyway, I called my aunt today and she’s actually doing okay. I forgot to do it yesterday, on Christmas day. Aargh!!!

Sometimes I think pure math is just an elaborate trick to avoid confronting reality.

Acknowledgements

The pictures of guillotine partitions were drawn by Robertd and put on Wikicommons under a Creative Commons Attribution 3.0 Unported license. The picture of a tree is from Etienne Ghys’ article Quand beaucoup de courbes se rencontrent. The picture of a barycentrically subdivided Stasheff pentagon is from Tom Leinster’s book Higher Operads, Higher Categories.

Dividing a Square into Similar Rectangles

If you divide a square into some fixed number of similar rectangles, what proportions can these rectangles have? We’ve been having fun thinking about this on Mathstodon, and here is a report.

If you divide a square into 3 similar rectangles, what proportions can these rectangles have? There are three options. The third is more complicated than the first two:

• We can divide the square into three rectangles that are 1/3 as long in one direction as the other, as in the first picture.

• We can divide it into three rectangles that are 2/3 as long in one direction as the other, as in the second picture.

• We can divide it into three rectangles that are x times as long in one direction as the other, as in the third picture.

What’s x? The yellow rectangle has height 1 and width x, so the blue rectangle has width 1-x and height x(1-x), while the red one has width 1-x and height (1-x)/x. The heights of the blue and red rectangles must sum to 1, so

x(1-x) + (1-x)/x = 1

or

x²(1-x) + (1-x) = x

x² – x³ + 1 – x = x

x³ – x² + 2x – 1 = 0

and the solution of this cubic is

so

x ≈ 0.56984

The reciprocal of this number is the square of a famous constant: the plastic ratio, ρ. This is like a cheap imitation of the golden ratio, with

ρ³ = ρ + 1

Why is the third option so much more complicated than the other two? As we’ll see, it’s because the first two have all the rectangles ‘pointing the same way’, while the third does not: it has a mix of rectangles ‘standing up’ and ‘lying down’.

To see the pattern, it helps to do a harder problem.

If you divide a square into 4 similar rectangles, what proportions can these rectangles have? A lot of people on Mathstodon worked on this puzzle! Here Dan Piker lists the 11 options we’ve found:

Note: there are more than 11 ways to divide a square into 4 similar rectangles, since you can rotate and reflect these pictures, and also rearrange the rectangles in some of them. But we’ve only found 11 possible proportions for the rectangles. Stefano Gogioso has sketched a proof that these are all the options, and Rahul Narain has given a computerized proof that these are all the options obtained from ‘guillotine cuts’:

• Wikipedia, Guillotine partition.

A ‘guillotine cut’ is a straight line going from one edge of an existing polygon to the opposite edge. And I believe there’s no way to dissect a square into 4 rectangles that doesn’t use guillotine cuts.

In the process of listing the options, we discovered something interesting: the rectangles have rational proportions only in options 1, 4, 7, 10 and 11 here:

And these are precisely the options where all the rectangles are pointing the same way! (They happen to all be lying down, wider than they are tall. But of course they’d all be standing up if we rotated the pictures.)

Puzzle 1. Show that if you subdivide a square into n similar rectangles that are all pointing the same way, the ratio x of their short side to their long side must be a rational number.

Puzzle 2. Show that the converse is not true.

We also discovered another pattern, too: when x is not rational, it is the solution to a cubic equation with integer coefficients.

Does that pattern persist when we subdivide a square into 5 similar rectangles? No, alas! Ian Henderson and Rahul Narain seem to have shown that exactly 51 proportions are possible when we subdivide a square into 5 similar rectangles. Henderson drew them:

while Narain listed the polynomial equations obeyed by the 51 possible proportions. Some obey a quartic equation with integer coefficients, not a cubic.

To be honest, Narain only considered ways of subdividing a square into 5 similar rectangles using guillotine cuts. But this should be okay, since I believe there’s just one way to subdivide a square into 5 rectangles that cannot be done using guillotine cuts. It’s shown here in a paper by Robert Dawson, in fact:

However, when we try to make all 5 rectangles similar, the central one shrinks to a point.

Ian Henderson also believes that when you subdivide a square into 6 similar rectangles, 245 proportions of rectangles are possible:

And for subdivisions of a square into 7 similar rectangles, he believes 1371 proportions are possible:

You can click to enlarge these last two pictures.

However, he adds, “I’m not 100% confident in these numbers.” So, someone should check his work.

Puzzle 3. Show that you can divide a square into 6 similar rectangles in a way that cannot be done via guillotine cuts.

Okay, back to something simpler: what proportions are possible when we divide a square into 4 similar rectangles? Let’s work it out!

For each option we get a number 0 < x ≤ 1 describing the proportion of the rectangles that subdivide the square. This number is the length of the short side divided by the length of the long side. The 11 options below are listed from the smallest possible value of x to the largest.

1) Option 1 is to divide the 1 × 1 square into 4 rectangles that are 1/4 as tall as they are wide. So, the number we get from this option is 1/4.

Note that if we rotated this option we’d get tall skinny rectangles, but the number would still be 1/4.

2) In option 2, the bottom two rectangles have width 1 and height x. Thus the top two have height 1-2x.

Since the green rectangle is x times as tall as it is wide, its width must be (1-2x)/x. The yellow rectangle thus has width

1 – (1-2x)/x = 1 − x⁻¹ + 2 = 3 – x⁻¹

Its height is this divided by x, namely 3x⁻¹ – x⁻². But we know its height is 1-2x, so

1-2𝑥 = 3x⁻¹ – x⁻²

or

2x³ – x² + 3x – 1 = 0

so

x ≈ 0.34563

3) For option 3 the red rectangle has height x, so the blue one has height 1-x and width x(1-x) = x−x², so the other two have width 1-(x−x²) = 1-x+x² and height x−x²+x³. The total height of red, green and yellow is 1 so x + 2(x−x²+x³) = 1 or

2x³ – 2x² + 3x – 1 = 0

This gives

x ≈ 0.39661

4) Option 4 is nice: it has left-right symmetry, and its rectangles can be rearranged to give another option with left-right symmetry.

The red and blue rectangles have height x. The green and yellow ones thus have height 1-2x, and thus width (1-2x)/x. But by symmetry we know they must have width 1/2, so

(1-2x)/x = 1/2

or

1-2x = x/2

or

1 = 5x/2

or

x = 2/5 = 0.4

Not a cubic equation this time—linear! So x is rational.

Notice that options 3, 5, 6, and 7 are all topologically the same! They were analyzed by Lisanne, and her work helped me a lot.

5) In option 5 the red rectangle has height x, so the blue has height 1-x and thus width (1-x)/x. The yellow and green thus have width 1 – (1-x)/x = 2 – x⁻¹, hence height (2 – x⁻¹)/x = 2x⁻¹ – x⁻² .

The heights of yellow, green and red must sum to 1:

2(2x⁻¹ – x⁻²) + x = 1

so we get a cubic:

x³ − x² + 4x – 2= 0

and the solution is

x ≈ 0.53318

6) In option 6 the red rectangle again has height x, so the blue again has height 1-x and width (1-x)/x.

The yellow and green again have width 1 – (1-x)/x = 2 – x⁻¹, but now they’re different: the yellow has height x(2 – x⁻¹) while the blue has height (2 – x⁻¹)/x.

The heights of yellow, green and red sum to 1:

x(2 – x⁻¹) + (2 – x⁻¹)/x + x = 1

so

3x³ – 2x² + 2x – 1 = 0

or

x ≈ 0.55232

7) In option 7, like options 5 and 6, the red rectangle has height x, so the blue has height 1-x and width (1-x)/x.

Thus, the yellow and green again have width 1 – (1-x)/x = 2 – x⁻¹. But this time both have height x(2 – x⁻¹).

Yet again, the heights of yellow, green and red sum to 1:

x + 2x(2 – x⁻¹) = 1

so

5x = 3

and

x = 3/5 = 0.6

The equation was linear, so x is rational!

Options 8, 9, and 10 are also all topologically the same.

8) In option 8 the red rectangle has height x so the blue has height 1-x and width (1-x)/x. The green and yellow also have height 1-x, but width x(1-x).

The widths of blue, green and yellow sum to 1:

(1-x)/x + 2x(1-x) = 1

so

2x³ − 2x² + 2x −1 = 0

and

x ≈ 0.64780

9) In option 9 the red rectangle has height x so the blue and green have height 1-x and width (1-x)/x. The yellow also has height 1-x, but width x(1-x).

The widths of blue, green and yellow sum to 1:

2(1-x)/x + x(1-x) = 1

so

2x⁻¹ – 2 + x – x² = 1

or

x³ – x² + 3x – 2 = 0

so

x ≈ 0.71523

10) Option 10 is more symmetrical than 8 or 9 since all three rectangles on top are congruent.

The red rectangle has height x so the blue, green and yellow all have height 1-x and thus width (1-x)/x.

The widths of blue, green and yellow sum to 1:

3(1-x)/x = 1

so

3(1-x) = x

or

3 = 4x

or

x = 3/4 = 0.75

Another linear equation, with a rational solution!

11) Finally, option 11 is the second one where all four rectangles are congruent. This time they’re squares! Clearly

x = 1

So, we see in these examples that x is rational precisely when all rectangles are ‘pointing the same way’: in the way Dan drew them, they’re all at least as wide as they are tall.

I’m not quite sure where to go with this research next. But I think the connection to double categories, hinted at in this paper with the picture of the pinwheel configuration, is interesting:

• Robert Dawson, A forbidden-suborder characterization of binarily-composable diagrams in double categories, Theory and Applications of Categories 1 (1995), 146–153.

Maybe we should seriously study the double category where 2-cells are rectangles that are subdivided into smaller rectangles by guillotine cuts!

But I also keep hoping there’s some interesting number-theoretic significance to the proportions that come up when we divide a square into the similar rectangles. Can anyone see interesting patterns in Rahul Narain’s table of the polynomials obeyed by these ratios when we divide a square into 5 similar rectangles? His u is my 1/x:

u - 5
u^3 - 4*u^2 + u - 3
u^3 - 4*u^2 + 2*u - 4
2*u - 7
u^3 - 4*u^2 + 3*u - 3
2*u^3 - 6*u^2 + u - 2
u^3 - 3*u^2 + 2*u - 5
u^3 - 3*u^2 + 2*u - 4
2*u^3 - 6*u^2 + 2*u - 2
u^3 - 3*u^2 + u - 1
3*u - 8
u^3 - 3*u^2 + 3*u - 5
2*u^3 - 5*u^2 + u - 2
u^5 - 3*u^4 + 3*u^3 - 4*u^2 + u - 1
-2*u^2 + 6*u - 3
2*u^3 - 5*u^2 + 2*u - 3
3*u - 7
u^4 - 3*u^3 + 3*u^2 - 4*u + 2
2*u^3 - 5*u^2 + 3*u - 3
u^3 - 3*u^2 + 4*u - 4
-u^2 + 4*u - 4
4*u - 8
3*u^3 - 6*u^2 + u - 1
2*u^3 - 4*u^2 + 2*u - 3
u^3 - 2*u^2 + 3*u - 5
3*u^3 - 6*u^2 + 2*u - 2
u^5 - 2*u^4 + 3*u^3 - 5*u^2 + u - 1
2*u^3 - 4*u^2 + 3*u - 4
4*u - 7
u^3 - 2*u^2 + 4*u - 6
-u^3 + 3*u^2 - 4*u + 3
2*u^3 - 5*u^2 + 4*u - 2
2*u^3 - 4*u^2 + 3*u - 3
3*u^3 - 5*u^2 + 2*u - 3
5*u - 8
u^5 - 2*u^4 + 3*u^3 - 4*u^2 + u - 1
-3*u^2 + 6*u - 2
2*u^4 - 4*u^3 + 3*u^2 - 3*u + 1
3*u^3 - 5*u^2 + 2*u - 2
4*u^3 - 6*u^2 + u - 1
-2*u^3 + 4*u^2 - 3*u + 2
2*u^3 - 3*u^2 + 3*u - 4
u^5 - 2*u^4 + 3*u^3 - 4*u^2 + 2*u - 1
5*u - 7
u^3 - 2*u^2 + 3*u - 3
2*u^3 - 3*u^2 + 2*u - 2
-u^3 + 2*u^2 - 4*u + 4
3*u^3 - 5*u^2 + 3*u - 2
3*u^3 - 4*u^2 + u - 1
4*u^3 - 6*u^2 + 2*u - 1
4*u - 5
2*u^3 - 3*u^2 + 4*u - 4
-5*u + 6
6*u - 7

Free Idempotent Rigs and Monoids

I’ve been having a lot of fun on Mathstodon lately, and here’s an example.

A rig R has a commutative associative addition, an associative multiplication that distributes over addition, an element 0 with r+0 = r and for all r ∈ R and an element 1 with 1r = r = r1 for all r ∈ R

A rig is idempotent if r r = r for all r ∈ R.

Is the free idempotent rig on 2 generators finite? If so, how many elements does it have?

Morgan Rogers raised this issue on the Category Theory Community server, and after a bit of progress I posed this as a puzzle on Mathstodon. By now three people there independently figured out the answer.

I’ll let you think about the free idempotent rig on 1 generator.

The free idempotent rig on 2 generators, say and has at most 4⁷ elements. To see this, first consider the free idempotent monoid on 2 generators, say This is the free monoid on 2 generators modulo relations saying that everything squared is itself. This has 7 elements:

Starting from this we can form the free idempotent rig on and by taking linear combinations. But notice that in an idempotent rig we have

1 + 1 + 1 + 1 = (1 + 1)² = 1 + 1

or 4 = 2 for short. We thus get 5 = 3, 6 = 4 = 2, etc. So, these are all the elements we get by repeatedly adding 1:

0, 1, 2, and 3

Just 4 elements! It follows that when we start adding any element 4 of the free idempotent rig on 2 generators to itself, we get at most 4 different elements:

0, r, 2r and 3r

Since has 7 elements, it follows that the free idempotent rig on 2 generators has at most 4⁷ = 16384 elements.

But in fact it has far fewer, because there are a lot of other relations. For example we have

because both sides equal More surprisingly, MathCuddler discovered that

because

but also

so they’re equal.

Nonetheless, three people on Mastodon have worked through the maze of relations with the help of a computer: Alex Gunning, Greg Egan and Simon Frankau.

They all concluded that the free idempotent rig on 2 generators has 284 elements!

You can see a list of the elements on Simon’s github, along with his code, and another list of the elements on Alex’s github. On his github, Greg Egan has posted a list of the elements together with all ways of writing each element as a linear combination of the 7 elements of

The next question: how many elements does the free idempotent rig on 3 generators have?

This is more interesting. When I said the free idempotent monoid on 2 generators has 7 elements, you may have just looked at this:

and accepted it, because these are clearly all the 7 ‘square-free words’ on two letters. A square-free word is one that don’t contain a nonempty repeated subword. For example is a square-free word on 3 letters, while is not.

But something more interesting happens for the free idempotent monoid generators. When there are infinitely many square-free words on n letters, and yet the the free idempotent monoid on n generators is still finite!

I don’t actually understand this. I would guess that a rewrite rule like WW → W to remove repeated subwords would be terminating and confluent, and thus allow us to reduce any element of the free idempotent monoid on n generators to a ‘normal form’ which is a square-free word. If this were true, I think the free idempotent monoid on n generators would be infinite — because there are infinitely many square-free words on n letters. So it seems this algorithm cannot actually be confluent! But I haven’t found a case of non-confluence. Can you help straighten me out here?

Anyway, the fact that the free idempotent monoid on n generators is finite implies that the free idempotent rig on n generators is also finite. For example, the Online Encyclopedia of Integer Sequences assures us that the free idempotent monoid on 3 generators has 160 elements. Given this, the free idempotent rig on 3 generators must have ≤ 4¹⁶⁰ elements, by the same argument I gave for 2 generators. But in fact it should have far fewer.

Is anyone brave enough to compute the number?

Adjoint School 2023

Are you interested in applying category-theoretic methods to problems outside of pure mathematics? Apply to the Adjoint School!

Apply here. And do it soon.

• January 9, 2023. Application Due.

• February – July, 2023. Learning Seminar.

• July 24 – 28, 2023. In-person Research Week at University of Maryland, College Park, USA

Participants are divided into four-person project teams. Each project is guided by a mentor and a TA. The Adjoint School has two main components: an online learning seminar that meets regularly between February and June, and an in-person research week held in the summer adjacent to the Applied Category Theory Conference.

During the learning seminar you will read, discuss, and respond to papers chosen by the project mentors. Every other week a pair of participants will present a paper which will be followed by a group discussion. After the learning seminar each pair of participants will also write a blog post, based on the paper they presented, for The n-Category Café. 

Projects and Mentors: 

• Message passing logic for categorical quantum mechanics – Mentor: Priyaa Srinivasan
• Behavioural metrics, quantitative logics and coalgebras – Mentor: Barbara König
• Concurrency in monoidal categories – Mentor: Chris Heunen
• Game comonads and finite model theory – Mentor: Dan Marsden

See more information about research projects at https://adjointschool.com/2023.html.

Organizers:

• Ana Luiza Tenorio 
• Angeline Aguinaldo
• Elena Di Lavore 
• Nathan Haydon

This Week’s Finds – Lecture 10

 

This was the last of this year’s lectures on This Week’s Finds. You can see all ten lectures here. I will continue in September 2023.

This time I spoke about quaternions in physics and Dyson’s ‘three-fold way’: the way the real numbers, complex numbers and quaternions interact. For details, try my paper Division algebras and quantum theory.

One cute fact is how an electron is like a quaternion! More precisely: how quaternions show up in the spin-1/2 representation of SU(2) on ℂ².

Let me say a little about that here.

We can think of the group SU(2) as the group of unit quaternions: namely, 𝑞 with |𝑞| = 1. We can think of the space of spinors, ℂ², as the space of quaternions, ℍ. Then acting on a spinor by an element of SU(2) becomes multiplying a quaternion on the left by a unit quaternion!

But what does it mean to multiply a spinor by 𝑖 in this story? It’s multiplying a quaternion on the right by the quaternion 𝑖. Note: this commutes with left multiplications by all unit quaternions.

But there are some subtleties here. For example: multiplying a quaternion on the right by 𝑗 also commutes with left multiplication by unit quaternions. But 𝑗 anticommutes with 𝑖:

𝑖𝑗 = −𝑗𝑖

So there must be an ‘antilinear’ operator on spinors which commutes with the action of SU(2): that is, an operator that anticommutes with multiplication by 𝑖. Moreover this operator squares to -1.

In physics this operator is usually called ‘time reversal’. It reverses angular momentum.

You should have noticed something else, too. Our choice of right multiplication by 𝑖 to make the quaternions into a complex vector space was arbitrary: any unit imaginary quaternion would do! There was also arbitrariness in our choice of 𝑗 to be the time reversal operator.

So there’s a whole 2-sphere of different complex structures on the space of spinors, all preserved by the action of SU(2). And after we pick one, there’s a circle of different possible time reversal operators!

So far, all I’m saying is that quaternions help clarify some facts about the spin-1/2 particle that would otherwise seem a bit mysterious or weird.

For example, I was always struck by the arbitrariness of the choice of time reversal operator. Physicists usually just pick one! But now I know it corresponds to a choice of a second square root of -1 in the quaternions, one that anticommutes with our first choice: the one we call 𝑖.

At the very least, it’s entertaining. And it might even suggest some new things we could try: like ‘gauging’ time reversal symmetry (changing its definition in a way that depends on where we are), or even gauging the complex structure on spinors.

This Week’s Finds – Lecture 9

 

In this talk I explained the quaternions and octonions, and showed how to multiply them using the dot product and cross product of vectors.

For more details, including a proof that octonion multiplication obeys |ab|=|a||b|, go here:

• Octonions and the Standard Model (Part 2).

This was one of a series of lectures based on my column This Week’s Finds.

 

 

This Week’s Finds – Lecture 8

 

In this talk I explained the E₈ root lattice and how it gives rise to the ‘octooctonionic projective plane’, a 128-dimensional manifold on which the compact Lie group called E₈ acts as symmetries. I also discussed how some special root lattices give various notions of ‘integer’ for the real numbers, complex numbers, quaternions and octonions.

For more, read my paper Coxeter and Dynkin diagrams.

This was one of a series of lectures based on my column This Week’s Finds.