I wrote a little book about entropy; here’s the current draft:

• What is Entropy?

If you see typos and other mistakes, or have trouble understanding things, please let me know!

An alternative title would be 92 Tweets on Entropy, but people convinced me that title wouldn’t age well: in decade or two few people may remember what ‘tweets’ were.

Here is the foreword, which explains the basic idea.

Foreword

Once there was a thing called Twitter, where people exchanged short messages called ‘tweets’. While it had its flaws, I came to like it and eventually decided to teach a short course on entropy in the form of tweets. This little book is a slightly expanded version of that course.

It’s easy to wax poetic about entropy, but what is it? I claim it’s the amount of information we don’t know about a situation, which in principle we could learn. But how can we make this idea precise and quantitative? To focus the discussion I decided to tackle a specific puzzle: why does hydrogen gas at room temperature and pressure have an entropy corresponding to about 23 unknown bits of information per molecule? This gave me an excuse to explain these subjects:

• information
• Shannon entropy and Gibbs entropy
• the principle of maximum entropy
• the Boltzmann distribution
• temperature and coolness
• the relation between entropy, expected energy and temperature
• the equipartition theorem
• the partition function
• the relation between expected energy, free energy and entropy
• the entropy of a classical harmonic oscillator
• the entropy of a classical particle in a box
• the entropy of a classical ideal gas.

I have largely avoided the second law of thermodynamics, which says that entropy always increases. While fascinating, this is so problematic that a good explanation would require another book! I have also avoided the role of entropy in biology, black hole physics, etc. Thus, the aspects of entropy most beloved by physics popularizers will not be found here. I also never say that entropy is ‘disorder’.

I have tried to say as little as possible about quantum mechanics, to keep the physics prerequisites low. However, Planck’s constant shows up in the formulas for the entropy of the three classical systems mentioned above. The reason for this is fascinating: Planck’s constant provides a unit of volume in position-momentum space, which is necessary to define the entropy of these systems. Thus, we need a tiny bit of quantum mechanics to get a good approximate formula for the entropy of hydrogen, even if we are trying our best to treat this gas classically.

Since I am a mathematical physicist, this book is full of math. I spend more time trying to make concepts precise and looking into strange counterexamples than an actual ‘working’ physicist would. If at any point you feel I am sinking into too many technicalities, don’t be shy about jumping to the next tweet. The really important stuff is in the boxes. It may help to reach the end before going back and learning all the details. It’s up to you.

I have a short piece at Quanta Magazine this week, about a physics-y end of the world as we know it called vacuum decay.

For science-minded folks who want to learn a bit more: I have a sentence in the article mentioning other uncertainties. In case you’re curious what those uncertainties are:

Gamma () here is the decay rate, its inverse gives the time it takes for a cubic gigaparsec of space to experience vacuum decay. The three uncertainties are from experiments, the uncertainties of our current knowledge of the Higgs mass, top quark mass, and the strength of the strong force.

Occasionally, you see futurology-types mention “uncertainties in the exponent” to argue that some prediction (say, how long it will take till we have human-level AI) is so uncertain that estimates barely even make sense: it might be 10 years, or 1000 years. I find it fun that for vacuum decay, because of that , there is actually uncertainty in the exponent! Vacuum decay might happen in as few as years or as many as years, and that’s the result of an actual, reasonable calculation!

For physicist readers, I should mention that I got a lot out of reading some slides from a 2016 talk by Matthew Schwartz. Not many details of the calculation made it into the piece, but the slides were helpful in dispelling a few misconceptions that could have gotten into the piece. There’s an instinct to think about the situation in terms of the energy, to think about how difficult it is for quantum uncertainty to get you over the energy barrier to the next vacuum. There are methods that sort of look like that, if you squint, but that’s not really how you do the calculation, and there end up being a lot of interesting subtleties in the actual story. There were also a few numbers that it was tempting to put on the plots in the article, but turn out to be gauge dependent!

Another thing I learned from those slides how far you can actually take the uncertainties mentioned above. The higher-energy Higgs vacuum is pretty dang high-energy, to the point where quantum gravity effects could potentially matter. And at that point, all bets are off. The calculation, with all those nice uncertainties, is a calculation within the framework of the Standard Model. All of the things we don’t yet know about high-energy physics, especially quantum gravity, could freely mess with this. The universe as we know it could still be long-lived, but it could be a lot shorter-lived as well. That in turns makes this calculation a lot more of a practice-ground to hone techniques, rather than an actual estimate you can rely on.

Every now and then, I get a question from a reader that I suspect many other readers share. When possible, I try to reply to such questions here, so that the answer can be widely read.

Here’s the question for today:

I do have one question that I couldn’t find the answer to in your book. Maybe I missed it, but here it is:

You explained what the strong force does (encapsulate the quarks and gluons within the proton), but what is the source of the strong force’s agency? I know it has energy used to hold the protons and neutrons together, but where does that force originate? It seems counter-intuitive, given the electromagnetic forces that pull particles apart due to equal charges — but how and why did the strong force come about? — Jeff Cox

Below I give a qualitative answer, and then go on to present a few more details. Let me know in the comments if this didn’t satisfactorily address the question!

I was in a coffeeshop in Berkeley, CA when Joe Biden announced he wouldn’t be running for re-election. I kind of wanted to talk to somebody about it but it wasn’t clear anybody else knew it had happened. At the next table there was a young couple with a toddler in a stroller who were talking to each other in a language other than English, but at some point I heard “foreign words foreign words CONTESTED CONVENTION foreign words” so I felt authorized to strike up a conversation. They were naturalized Americans originally from Lithuania and they were one-issue anti-Trump voters — they said Putin could have tanks in Vilnius in a half an hour and that they didn’t believe Trump would raise a hand to stop it. I asked them what they thought about Harris. The mom, who did most of the talking, was somewhat concerned about Harris’s electability. She liked Gavin Newsom a lot and saw him as a prime example of what she considered an electable US politician. The dad chimed in to mention Newsom’s hair, which he saw as a plus. The mom said her real concern about Harris is that she seemed like more of a politician, lacking a real governing of philosophy of her own to offer, by contrast with the political figure she really liked and admired, Hillary Clinton.

Later that morning I talked to three women from Missouri, probably in their 60s, who were from Missouri. They all agreed that they were sad that Biden had dropped out of the race. But it wasn’t clear they thought it was the wrong decision, just that they felt sad about it. One brought up the comparison with taking an older relative’s keys away. “But we’re 100% Kamala,” one of them said, and they all nodded.

Update (July 24): Remember the quest that Adam Yedidia and I started in 2016, to find the smallest n such that the value of the n^th Busy Beaver number can be proven independent of the axioms of ZF set theory? We managed to show that BB(8000) was independent. This was later improved to BB(745) by Stefan O’Rear and Johannes Riebel. Well, today Rohan Ridenour writes to tell me that he’s achieved a further improvement to BB(643). Awesome!

With yesterday’s My Prayer, for the first time I can remember in two decades of blogging, I put up a new post with the comments section completely turned off. I did so because I knew my nerves couldn’t handle a triumphant interrogation from Trumpist commenters about whether, in the wake of their Messiah’s (near-)blood sacrifice on behalf of the Nation, I’d at last acquiesce to the dissolution of America’s constitutional republic and its replacement by the dawning order: one where all elections are fraudulent unless the MAGA candidate wins, and where anything the leader does (including, e.g., jailing his opponents) is automatically immune from prosecution. I couldn’t handle it, but at the same time, and in stark contrast to the many who attack from my left, I also didn’t care what they thought of me.

With hindsight, turning off comments yesterday might be the single best moderation decision I ever made. I still got feedback on what I’d written, on Facebook and by email and text message and in person. But this more filtered feedback was … thoughtful. Incredibly, it lowered the stress that I was feeling rather than raising it even higher.

For context, I should explain that over the past couple years, one or more trolls have developed a particularly vicious strategy against me. Below my every blog post, even the most anodyne, a “new” pseudonymous commenter shows up to question me about the post topic, in what initially looks like a curious, good-faith way. So I engage, because I’m Scott Aaronson and that’s what I do; that’s a large part of the value I can offer the world.

Then, only once a conversation is underway does the troll gradually ratchet up the level of crazy, invariably ending at some place tailor-made to distress me (for example: vaccines are poisonous, death to Jews and Israel, I don’t understand basic quantum mechanics or computer science, I’m a misogynist monster, my childhood bullies were justified and right). Of course, as soon as I’ve confirmed the pattern, I send further comments straight to the trash. But the troll then follows up with many emails taunting me for not engaging further, packed with farcical accusations and misreadings for me to rebut and other bait.

Basically, I’m now consistently subjected to denial-of-service attacks against my open approach to the world. Or perhaps I’ve simply been schooled in why most people with audiences of thousands or more don’t maintain comment sections where, by default, they answer everyone! And yet it’s become painfully clear that, as long as I maintain a quasi-open comment section, I’ll feel guilty if I don’t answer everyone.

So without further ado, I hereby announce my new comment policy. Henceforth all comments to Shtetl-Optimized will be treated, by default, as personal missives to me—with no expectation either that they’ll appear on the blog or that I’ll reply to them.

At my leisure and discretion, and in consultation with the Shtetl-Optimized Committee of Guardians, I’ll put on the blog a curated selection of comments that I judge to be particularly interesting or to move the topic forward, and I’ll do my best to answer those. But it will be more like Letters to the Editor. Anyone who feels unjustly censored is welcome to the rest of the Internet.

The new policy starts now, in the comment section of this post. To the many who’ve asked me for this over the years, you’re welcome!

Our 6-week Edinburgh meeting for creating category-based software for agent-based models is done, yet my collaborators are still busy improving and expanding this software. I want to say more about how it works. I have a lot of catching up to do!

Today I mainly want to announce that Kris Brown has made a great page explaining our software through a working example:

• Conway’s Game of Life.

His explanation uses an idea interesting in its own right: ‘literate programming’, where the code is not merely documented, but worked into a clear explanation of the code in plain English. I would copy it all onto this blog, but that’s not extremely easy—so just go there!

His explanation is a good alternative or supplement to mine. This is how my explanation went:

• Part 9: The theory of ‘stochastic C-set rewriting systems’. This is our framework for describing agents using somewhat general but still simple data structures that randomly change state at discrete moments in time.

• Part 10: Here I describe a choice of category C suitable for the Game of Life. For this choice, C-sets describe living and dead cells, and the edges connecting them.

• Part 11: Here I explain stochastic C-set rewrite rules that describe time evolution in the Game of Life.

• Part 12: Here I describe the formalism of ‘attributed C-sets’. In the Game of Life we merely use these a way to assign coordinates to cells: they don’t affect the running of the game, only how we display it. But in other agent-based models they become much more important: for example, some agents might have a ‘weight’ or ‘height’ or other quantitative information attached to them, which may change with time, and these are treated as ‘attributes’.

So, there’s plenty you can read about our approach to the Game of Life.

But as I mentioned before, the Game of Life is a very degenerate example of a stochastic C-set rewriting system, because it’s actually deterministic! What if we want a truly stochastic example?

It’s easy. I’ll talk about that next time.

The mass of a single proton, often said to be made of three quarks, is almost 1 GeV/c². To be more precise, a proton’s mass is 0.938 GeV/c², while that of a neutron is 0.939 GeV/c².

But the masses of up and down quarks, found in protons and neutrons, are each much less than 0.01 GeV/c². In short, the mass of each quark is less than one percent of a proton’s or neutron’s mass. If a proton were really made from three quarks, then there would seem to be a huge mismatch.

(Here and below, by “mass” I mean “rest mass” — an object’s intrinsic mass, which does not change with speed. It is sometimes called “invariant mass”. [Particle physicists usually just call it “mass”, though.])

Part of the explanation for the apparent discrepancy is that a proton or neutron is, in fact, made from far more than just three quarks. In its interior, one would find many gluons and a variety of quarks and anti-quarks. However, that doesn’t resolve the issue.

• Gluons, like photons, have zero rest mass, so they don’t help at all, naively speaking.
• The typical number of quarks and anti-quarks inside a proton, while more than three, is too small to add up to the proton’s full mass;

And thus one cannot explain the proton or neutron’s large mass as simply the sum of the masses of the objects inside it. The discrepancy remains.

Moreover, as can be verified using either strong theoretical arguments in analogous systems or direct numerical simulations, protons and neutrons would still have a substantial mass even if the quarks and anti-quarks they contain had none at all! Mass — from no mass.

Clearly, then, the solution to the puzzle lies elsewhere.

Mass is Not “Conserved”

The essential point is that the mass of an object is not the sum of the masses of the objects that it contains. In physics-speak, mass is not conserved. Did you learn otherwise in chemistry class? Well, certain lessons of chemistry class are not exactly right, and in particle physics — and specifically, within your own body and within every object around you — they often do not apply.

There’s already a subtle clue in the mass of a simple hydrogen atom, made of just one electron and one proton. It differs very slightly, by about one part in 100 million, from what you’d get if you added together the mass of an electron and the mass of a proton.

Admittedly, it’s not obvious this has anything to do with the issues inside a proton. After all,

• the hydrogen atom’s mass is very slightly less than the sum of the masses of the electron and the proton;
• the proton’s mass is much greater than the sum of the masses of the objects inside it.

Nevertheless, these two facts are indeed closely related. I’ll go through the first one before explaining the second.

Both Einstein’s relativity and quantum physics are involved. We must keep track of the fact that electrons and quarks are not really “particles” — at least, not as we mean the word in English, when we apply it to specks of dust or particles of smoke. Instead, they have many wave-like properties. I often prefer to refer to them as “wavicles”, a term which was invented about 100 years ago, and I’ll do so in this post.

• Wavicles, unlike ordinary particles, are vibrations; like any wave, they can have a vibrational frequency f, but unlike usual waves, they have an energy E that is proportional to that frequency. This is represented in the quantum formula: E=fh, where h is Planck’s constant, a constant of nature that serves as a conversion factor between E and f.
  
  
• We must also accurately account for Einstein’s relativity equation, E=mc², a formula that relates the energy stored within an object to its rest mass m — and where c, the cosmic speed limit (also known as “the speed of light”), again serves as a conversion factor between E and m.

The key intuition we need is this: in contrast to an ordinary particle, a wavicle has the property that its frequency grows — and therefore its energy grows — when its container shrinks.

For instance, a wavicle in a hole has energy that depends on the width of the hole, as well as on the depth of the hole. This is unlike a particle’s energy, which depends only on the depth. As a result, a wavicle in a well will lose energy if the well is made deeper, yet it will gain energy if the well is made narrower. Both for atoms and for protons, this is crucially important.

Why is this true? If you want the back-story, you should read my two earlier posts comparing ordinary particles and wavicles:

• The first post highlights key differences between particles, waves and wavicles.
• The second post points out a consequence of these differences: a particle in a collapsing well will remain there to the end, while a wavicle will escape before the well collapses completely.

Atoms

Within a hydrogen atom, made of nothing but one electron and one proton, the proton pulls the electron toward it via the electric force. The smaller the distance between them, the stronger the pull.

This makes the electron behave as though it is on a edge of a very deep and steep 3-dimensional hole, with the proton at its center. I’ve sketched this in Figure 1. The horizontal direction represents the distance of the electron from the proton, while the vertical direction in the drawing showing the energy-depth of the “hole”. The little flat area is the location of the proton, where the hole terminates. (It is not to scale; the hole should extend off the bottom of your screen.)

If the electron were really a particle that could fall to the bottom of a hole, it would fall toward the proton until it reached the proton’s edge. After radiating away some excess energy, it would eventually settle down there, as in Fig. 2.

The electron’s energy would then have been reduced by the depth of the hole. And how deep would that be? Well, the electron’s internal mc² energy is about 0.000511 GeV. But in this hole, it would lose more than that, several times over! This means that the combined proton-electron system would have a smaller mass than the proton does on its own. (You can rightly worry about what that might lead to…)

But this is all heading in the wrong direction. An electron isn’t a particle, not of the conventional sort, anyway. It’s a wavicle. Squeezing it into a small region increases its frequency, and therefore its energy. As a result, its energy wouldn’t actually be reduced if it were shoved down into a deep but narrow hole; the energy would actually increase! And so an electron, unlike an ordinary particle, simply won’t allow itself to be forced into such a predicament; it won’t fall into the hole in Fig. 1.

What ensues is a competition between two effects:

• the hole is trying to pull the electron in and reduce its energy,
• but the further the electron goes into the hole, the narrower the space available to it, which increases its frequency and therefore its energy.

As shown in Fig. 3, these two effects balance, and a hydrogen atom forms, when the electron just dips its toe into the hole. In protonic terms, it ends up occupying a gigantic region — with a volume about 1,000,000,000,000,000 times larger than the volume of a proton! Said another way, the diameter of the electron, and thus of the hydrogen atom, is about 100,000 times larger than a proton’s diameter; the atom is 10^-10 meters across, while a proton’s diameter is a tiny 10^-15 meters.

Note: this is different from what happens to a wavicle in a well with vertical walls, which I covered in a recent post. In a straight-walled hole, it’s largely all or nothing; either the wavicle is confined in the hole, or it isn’t. But here, the walls of the “hole” tail off very gradually, which permits the electron to spread out far and yet remain attached to the hole.

As is true for any object, the mass of the atom is its internal energy, divided by c². Most of the atom’s energy is obtained by adding the internal energy of the proton (0.938 GeV) to that of the electron (0.000511 GeV). But because the electron is (barely) inside the well created by the proton, just below the “level ground” that it would sit on if it were isolated, it has lost a tiny amount of energy: a mere 13.6 eV = 0.0000000136 GeV. (This is called the atom’s “binding energy.”) That in turn means that a hydrogen atom’s mass is 13.6 eV/c² less than the sum of the masses of the electron and proton.

It’s a tiny reduction, but without it, the hydrogen atom wouldn’t be stable — it wouldn’t remain intact. To break the atom apart, “ionizing” it so that the proton and electron separate from one another, requires 13.6 eV of energy be added to it. And so, unless and until someone or something provides that energy, the proton and electron will remain together in atomic form.

[Note: if you’ve seen this argued in terms of the uncertainty principle rather than using the approach I’ve used here, be reassured: these are two complementary views of the same phenomena, and they do not contradict one another.]

Seeing how an atom works now raises a puzzle. If the atom is stable because its energy is lower than that of its constituent parts, how can a proton, whose energy is higher than that of its constituent parts, be stable? I’ll answer that at the very end.

Click here for more mathy details on atoms

First, let’s see that the energy of an electron particle sitting on a proton would be reduced by more than its energy. The electrostatic energy of an electron near a proton can be written

which is just a rewriting of the usual expression seen in first-year physics; here is a number, approximately 0.007. If we put meters, the radius of a proton, then

which is a reduction in energy about three times larger than the electron’s .

Now let’s consider the electron as a wavicle in a box of length . The Compton wavelength of the electron is

The energy of a wavicle in a box of length is roughly

where I am not keeping track of factors of 2 and other details, but just capturing the essence of the phenomena. If the box is large, with , then the first term is larger than the second, and we can approximate the electron’s energy using the fact that if , then

and so

Maybe this reminds you of the expresssion for a slow particle’s energy in special relativity, where the second term is the particle’s kinetic energy, written in terms of its speed

Indeed, we should understand the second term as a wavicle’s kinetic energy, where is replaced by . This is how quantum physics works; this conversion from speed to shape underlies the Schrodinger equation.

If the electron is roughly at a distance from the proton on average, then perhaps we can think of it as being in a box of size , with a depth ? We should not expect this to be strictly accurate! A hole shaped like the one in Figure 3 is far from a simple box! Nevertheless, keeping this in mind, let’s proceed.

The total energy of the electron, under this guess, is then

The first term is independent of . The second grows positive when is small, while the third grows negative when is small. The balance point between these last two effects, where is smallest, is at

or, being careless with factors of 2 and

This answer turns out to be too big, by about a factor of a few, mainly because our approximation, in which we treated the hole as though it were a simple box, isn’t sufficiently valid; there are some factors to account for. But it captures the essence of the physics — the atom forms through a balancing act that prevents the wavicle from sinking to the bottom of the hole.

To check this reasoning is really correct, it’s time to sit down and solve quantum physics equations and do some hard work. At the end of that effort, one does indeed find detailed energy levels, and an atomic radius, that matches precisely with experiments on hydrogen.

See also this argument which gets the same answer, within a factor of 2, via an even simpler approach.

One more thing: What would hydrogen be like in a universe with electrons of even lower mass? Such electrons would spread out even further, and the decrease in their energy would be less. The smaller the mass of an electron, the larger its atoms, and the less energy would be required to ionize them.

This means that electrons with zero rest mass could not form atoms at all! They would be infinitely large and infinitely easy to ionize.

And that, in turn, is why the Higgs field is so important for our existence. Without it, electrons would have no rest mass, and stable atoms would not exist.

Protons

A proton presents a puzzle. We’ve seen that the electric pull of the proton on an electron lowers the electron’s energy. How can we use a pull to hold an object together and yet give a wavicle higher energy, and lots of it?

Within a proton, the quarks, gluons and anti-quarks are all pulling on each other via the strong nuclear force. When the distances between them are much smaller than a proton, the strong nuclear force is similar to the electric force, only somewhat stronger: it makes them behave as though they are within a deep, narrow “hole”, where their energy falls rapidly as they approach each other.

But when they try to separate from one another, something new happens; the hole’s walls, rather than sloping gradually outward as in Fig. 3, extend upward, preventing any escape, as in Fig. 5. The quarks and gluons are trapped.

[A reminder about what is plotted in Fig. 5, as in Figs. 1 and 3: the horizontal direction represents the distance between a quark and, say, an anti-quark, but the vertical direction represents energy, not a vertical direction of space. So the picture conveys that the energy between the quark and anti-quark is growing very rapidly as they separate… very different from the gradual die-off of the energy seen in Fig. 3 that allows an electron to move far from a proton.]

The high wall changes everything. The “hole” that contains the wavicles is very narrow, and if the walls were absent or low, the quarks and gluons would easily escape, or at least spread out, as in Fig. 3. But thanks to these walls, the quarks and gluons find themselves stuck inside the hole.

Moreover, the trap remains extremely narrow as one climbs the walls, which the wavicles, figuratively speaking, attempt to do. This raises their energy to the point that it’s the width of the trap, not the masses that the quarks themselves carry, that determines how much energy the quarks have — and it greatly exceeds their E=mc² energy! Gluons, which have no mass, get all their energy from the trap.

[Specifically, the trap is much narrower than the Compton wavelength of the quarks. This is unlike the situation for an electron in an atom, where the electron can spread to an extent much larger than its Compton wavelength. The math of this is discussed in an aside below.]

In other words, it is the trap’s effects on the wavicles, not the masses of those wavicles, that provides the majority of the proton’s internal energy. That’s why a proton’s mass can be so much larger than the mass of the objects that it contains.

In fact, inside this trap, a quark’s energy would be almost unchanged even if its mass were zero. Since both gluons and quarks would still have a plenty of energy, a proton would still have mass even if its quarks had none! All that’s needed to generate considerable energy for the wavicles in the “hole”, and thus mass for the full collection of wavicles that make up a proton, is that the “hole” be narrow and that it have high walls that prevent the wavicles from escaping. And that’s what the strong nuclear force achieves.

Such are the deep secrets that lie at the heart of every atom. Without them, the proton and neutron would be a shadow of their true selves. Our existence depends upon this remarkable, intricate interplay of the strong nuclear force, Einstein’s relativity and quantum physics.

Click here to see more mathy details for the proton

You’ll want to look first at the related discussion about electrons in atoms, located at the end of the “Atoms” section.

The main difference for what happens in a proton versus what happens in an atom is that here the box is smaller than the quarks’ Compton wavelength. As a result, in the expression for the energy of a wavicle in a box,

the second term is now much larger than the first. Expanding the square root as before, but in the opposite way, gives us

The contribution of the first term involves the diameter of the proton, which is approximately meters, and gives us an energy per wavicle that corresponds to a good fraction of the mass of a proton! (As for electrons in atoms, this gives a bit of an over-estimate, thanks again to some 2’s and ‘s.)

The second term is zero for gluons, and for quarks, it is so small by comparison to the first term that it can be largely ignored. Almost all the energy is coming just from the fact that is small.

As before, this estimate, while far from precise, captures the heart of the phenomenon: merely by creating a small box for the quarks and gluons to live in, the strong nuclear force produces a proton with a mass much larger than the masses of its ingredients.

To conclude, here are answers to two questions that I’m sure many readers will ask.

Wait! What About The Other Picture of a Proton?

Those of you who’ve read my book, or read elsewhere on this website about protons, will no doubt have noticed that this picture looks very different from the one I usually present, in which the inside of a proton is a maelstrom of quarks, gluons and antiquarks running about at or nearly at the cosmic speed limit, smashing into each other, and appearing and disappearing.

The difference between them is a classic example of how one transitions from a particle picture to a wavicle picture.

There’s an analogue here for atoms, too. Before the correct picture of an atom, shown in Fig. 4, was discovered, there was the Bohr model of the atom, which captured some of its properties. This model is presented in any first-year physics class (sometimes without explaining its limitations!) In that early picture of an atom, an electron is a particle, not a wavicle; it travels on a path that orbits the proton, and so its behavior is somewhat like a planet orbiting a star, except that it has to follow strange, inexplicable rules. One can go from the Bohr picture to the true, quantum picture in stages; the Bohr view is a good stepping stone, but it has flaws that are uncorrectable in the end.

The picture I usually give of a proton is somewhat like the Bohr model of the atom: it treats the quarks, gluons and anti-quarks as though they were particles, not wavicles. Like the Bohr model, it captures some of the story. In particular, it correctly illustrates these points:

• a proton is far more complicated than an atom;
• the energy of particles inside the proton is far greater than their E=mc² energy;
• it is impossible to say how many quarks, gluons or anti-quarks are inside a proton
  • though there are always three more quarks than anti-quarks

But as with the Bohr model of the atom, the reasons it gives to explain these three key facts are not complete or accurate. The correct picture is only obtained by treating the quarks, anti-quarks and gluons as the wavicles that they truly are. Then one learns that:

• it is the strong nuclear interactions among the wavicles that make the proton complicated and turn it into a prison;
• the reason that the wavicles inside a proton have so much energy is that the proton, for them, is a tiny prison, far smaller than their Compton wavelengths;
• the patterns of wavicle interactions (which can create or destroy gluons, and convert quark/anti-quark pairs to gluons and vice versa), combined with a quantum physics effect known as “superposition”, assure that a proton simply does not have a definite number of quarks, of anti-quarks, or of gluons
  • nevertheless, the number of quarks minus the number of antiquarks is definite, and equal to three.

Why did I leave this important story out of my book? The reason is simple: there wasn’t room for it. But… that’s why I have a website! What couldn’t fit in the book fits here.

Wait! Why is the Proton Stable?

Now we know why the proton is greater than the sum of its parts: the strong nuclear forces among those wavicles creates a high-walled, narrow trap. But why doesn’t the proton fall apart? If the energy of the individual quarks and gluons is smaller than that of a proton, how can the latter be stable?

This is far from obvious, and is directly related to why the walls of the hole stretch so far upward. Understanding how the strong nuclear force does this has been worthy of Nobel Prizes.

It turns out — I have written about this before — that it is impossible to isolate a quark on its own. If you try to isolate a quark, you will have to supply a huge amount of energy — so much that nature will co-opt it. Despite your best efforts, nature will take some of that energy and spontaneously create additional quarks and gluons and antiquarks in the vicinity of the quark you’re trying to isolate. In this way, nature itself assures that your effort will fail!

This effect is sometimes (and somewhat incorrectly) called “quark confinement” (for in truth it involves confinement of the strong-nuclear-electric field, or “chromoelectric” field.) The existence of the high walls in Fig. 5 is itself a consequence of this effect.

What this means is that a quark or gluon is never found outside a narrow deep “hole” with high walls… and therefore, all objects made from quarks, anti-quarks and gluons have mass greater than the masses of the quarks and anti-quarks that they contain.

Again, this cannot happen for atoms. You couldn’t have a hydrogen atom with more energy than an electron and a proton have separately, because the atom would instantly disintegrate; the electron and positron could reduce their energy by rushing apart from one another. But the quarks and gluons in a proton cannot escape each other; when they try, more quarks and gluons are made, requiring even more energy. Consequently, a proton cannot break into its component parts, even though those parts, treated individually, have less mass than does the proton itself.

read more

I wrote a little book about entropy; here’s the current draft:

• What is Entropy?

If you see typos and other mistakes, or have trouble understanding things, please let me know!

An alternative title would be 92 Tweets on Entropy, but people convinced me that title wouldn’t age well: in decade or two few people may remember what ‘tweets’ were.

Here is the foreword, which explains the basic idea.

Foreword

Once there was a thing called Twitter, where people exchanged short messages called ‘tweets’. While it had its flaws, I came to like it and eventually decided to teach a short course on entropy in the form of tweets. This little book is a slightly expanded version of that course.

It’s easy to wax poetic about entropy, but what is it? I claim it’s the amount of information we don’t know about a situation, which in principle we could learn. But how can we make this idea precise and quantitative? To focus the discussion I decided to tackle a specific puzzle: why does hydrogen gas at room temperature and pressure have an entropy corresponding to about 23 unknown bits of information per molecule? This gave me an excuse to explain these subjects:

• information
• Shannon entropy and Gibbs entropy
• the principle of maximum entropy
• the Boltzmann distribution
• temperature and coolness
• the relation between entropy, expected energy and temperature
• the equipartition theorem
• the partition function
• the relation between expected energy, free energy and entropy
• the entropy of a classical harmonic oscillator
• the entropy of a classical particle in a box
• the entropy of a classical ideal gas.

I have largely avoided the second law of thermodynamics, which says that entropy always increases. While fascinating, this is so problematic that a good explanation would require another book! I have also avoided the role of entropy in biology, black hole physics, etc. Thus, the aspects of entropy most beloved by physics popularizers will not be found here. I also never say that entropy is ‘disorder’.

I have tried to say as little as possible about quantum mechanics, to keep the physics prerequisites low. However, Planck’s constant shows up in the formulas for the entropy of the three classical systems mentioned above. The reason for this is fascinating: Planck’s constant provides a unit of volume in position-momentum space, which is necessary to define the entropy of these systems. Thus, we need a tiny bit of quantum mechanics to get a good approximate formula for the entropy of hydrogen, even if we are trying our best to treat this gas classically.

Since I am a mathematical physicist, this book is full of math. I spend more time trying to make concepts precise and looking into strange counterexamples than an actual ‘working’ physicist would. If at any point you feel I am sinking into too many technicalities, don’t be shy about jumping to the next tweet. The really important stuff is in the boxes. It may help to reach the end before going back and learning all the details. It’s up to you.

In these unsettling and trying times, I wanted to write about the physics of a challenge I'm facing in my professional life: super squeaky shoes.  When I wear a particularly comfortable pair of shoes at work, when I walk in some hallways in my building (but not all), my shoes squeak very loudly with every step. How and why does this happen, physically?  

The shoes in question.

To understand this, we need to talk a bit about a friction, the sideways interfacial force between two surfaces when one surface is sheared (or attempted to be sheared) with respect to the other.  (Tribology is the study of friction, btw.)  In introductory physics we teach some (empirical) "laws" of friction, described in detail on the wikipedia page linked above as well as here:

1.  For static friction (no actual sliding of the surfaces relative to each other), the frictional force \(F_{f} \le \mu_{s}N\), where \(\mu_{s}\) is the "coefficient of static friction" and \(N\) is the normal force (pushing the two surfaces together).  The force is directed in the plane and takes on the magnitude needed so that no sliding happens, up to its maximum value, at which point the surfaces start slipping relative to each other.
2. For sliding or kinetic friction, \(F_{f} = \mu_{k}N\), where \(\mu_{k}\) is the coefficient of kinetic or sliding friction, and the force is directed in the plane to oppose the relative sliding motion.  The friction coefficients depend on the particular materials and their surface conditions.
3. The friction forces are independent of the apparent contact area between the surfaces.  
4. The kinetic friction force is independent of the relative sliding speed between the surfaces.

Shoe squeaking happens because of what is called "stick-slip" motion.  When I put my weight on my right shoe, the rubber sole of the shoe deforms and elastic forces (like a compressed spring) push the rubber to spread out, favoring sliding rubber at the rubber-floor interface.  At some point, the local static friction maximum force is exceeded and the rubber begins to slide relative to the floor.  That lets the rubber "uncompress" some, so that the spring-like elastic forces are reduced, and if they fall back below \(\mu_{s}N\), that bit of sole will stick on the surface again.  A similar situation is shown in this model from Wolfram, looking at a mass (attached to an anchored spring) interacting with a conveyer belt.   If this start/stop cyclic motion happens at acoustic sorts of frequencies in the kHz, it sounds like a squeak, because the start-stop motion excites sound waves in the air (and the solid surfaces).  This stick-slip phenomenon is also why brakes on cars and bikes squeal, why hinges on doors in spooky houses creak, and why that one board in your floor makes that weird noise.  It's also used in various piezoelectric actuators. 

Macroscopic friction emerges from a zillion microscopic interactions and is affected by the chemical makeup of the surfaces, their morphology and roughness, any adsorbed layers of moisture or contaminants (remember: every surface around you right now is coated in a few molecular layers of water and hydrocarbon contamination), and van der Waals forces, among other things.  The reason my shoes squeak in some hallways but not others has to do with how the floors have been cleaned.  I could stop the squeaking by altering the bottom surface of my soles, though I wouldn't want to use a lubricant that is so effective that it seriously lowers \(\mu_{s}N\) and makes me slip.  

Friction is another example of an emergent phenomenon that is everywhere around us, of enormous technological and practical importance, and has some remarkable universality of response.  This kind of emergence is at the heart of the physics of materials, and trying to predict friction and squeaky shoes starting from elementary particle physics is just not do-able. 

You might think I’m about to tell a joke. But no, not me. This is serious physics, folks!

Suppose a particle falls into a hole, and, as in a nightmare (or as in a certain 1970s movie featuring light sabers), the walls of the hole start closing in. The particle will just stay there, awaiting the end. But if the same thing happens to a wavicle, the outcome is very different. Like a magician, the wavicle will escape!

Today I’ll explain why.

As I described last time, stationary particles, waves and wavicles differ in their basic properties.

	stationary particle	standing wave	standing wavicle
location	definite	indefinite	indefinite
energy	definite, container-independent	adjustable	definite, fixed by frequency
frequency	none	container-dependent	container-dependent
amplitude	none	adjustable	fixed by frequency & container

Stationary particles can have a fixed position and energy. Stationary (i.e. standing) waves have a definite frequency, but variable amplitude and energy. And standing wavicles are somewhere in between, with no fixed position, but with a definite frequency and energy. Let’s explore an important consequence of these differences.

The Collapsing Well

Imagine that we place a tiny object at the bottom of a deep but wide well. Then we bring the walls of the well together, making it narrower and narrower. What happens?

A particle will just sit patiently at the bottom of the well, even as the walls close in, seemingly unaware of or unconcerned about its impending doom (Fig. 1).

A wavicle, by contrast, can’t bear this situation (Fig. 2). Inevitably, as the walls approach each other, the wavicle will always leap bodily out of the well, avoiding ever being trapped.

The only way to keep a wavicle inside a collapsing well would be to extend the walls of the well upward, making them infinitely high.

This difference between particles and wavicles has a big impact on our world, and on the atoms and subatomic “particles” out of which we are made.

Energy Between Walls

In my last post I discussed what happens to a particle located between two walls that are separated by a distance L, as in Fig. 3. If the particle has rest mass m and is stationary, it will have energy E=mc², no matter what L is.

A wavicle standing between two walls is different, because the energy of the wavicle grows when L decreases, and vice versa. A wavicle of mass m will therefore have energy larger than mc².

The energy will be just a little larger than mc² if the distance L is long, specifically much longer than the wavicle’s “Compton wavelength” h / m c (where h, Planck’s constant, is a constant of nature, like c). But if L is much shorter than the Compton wavelength, then the wavicle’s energy can greatly exceed mc².

Click here for a math formula showing some details.

Throughout this post I’m going to be quantitatively imprecise, keeping only those conceptual and mathematical features which are needed for the conceptual lessons. A complete mathematical treatment is possible, but I think it would be less instructive and more confusing.

Roughly speaking, the formula for the wavicle’s energy is

Notice that

• if is infinite,
• if is large, , just slightly larger than
• if is small, , much larger than

Energy in a Well

Now let’s imagine digging a hole that has a width W and a depth D, as shown in Fig. 5. Let’s first imagine the well is quite wide, so W is relatively large.

If we put a stationary particle of mass m in the well, it just sits at the bottom. How much energy does it have?

If a particle placed at ground level, outside the well, has energy E=mc², then a particle below ground level at a depth D has energy

• ,

where g is the acceleration of objects due to the Earth’s gravity. The energy has been reduced by the lowering of the particle’s altitude; the larger is D, the greater the reduction. (This reflects the fact that in a hole of greater depth, it would take more energy to lift the particle out of the hole.) But the particle’s energy shows no dependence on W.

Suppose we instead put a stationary wavicle of mass m in a wide well. It too sits inside the well, but it’s different in detail. It vibrates as a standing wave whose length is set by W, and whose frequency f therefore also depends on W. Since a wavicle’s energy and frequency are proportional, via the Planck-Einstein quantum formula E=fh, that means its energy depends on W too.

Being in the well, at a reduced altitude, reduces its energy by the same factor m g D that applies for the particle. As before, the larger is D, the greater the reduction.

But the wavicle’s energy gets a boost, relative to that of the particle in the well, because the finite width of the well increases its frequency. The smaller is W, the larger the energy boost from the narrowness of the well.

Thus there is a competition between the well’s depth, which lowers the wavicle’s energy as it does the particle’s, and the well’s width, which raises the wavicle’s energy relative to the particle.

Click here for a math formula showing how this works

Specifically, inside a well of width W and depth D, its energy is approximately

• 

So what happens, now, if the well starts collapsing and the walls close in? What do the particle and wavicle do as W decreases?

Leaping Out of the Well?

As the well becomes narrower, the particle does nothing. Its energy doesn’t depend on the width W of the well, and so the particle doesn’t care how far apart the walls are until they actually come in contact with it. The particle’s energy is always less than the mc² energy of a particle sitting on the ground outside the hole. That means that the particle never has sufficient energy to leave the hole on its own.

The wavicle is quite another matter. As W decreases, the energy of the wavicle increases. And at some point, when W is small enough, the energy of the wavicle in the well becomes greater than the energy of the wavicle that extends outside the well.

To keep things simple, let’s imagine L to be very large, so large that when outside the well, both the particle’s and wavicle’s energy are almost exactly equal to mc². In that context, consider Fig. 7, where I show the W-dependence of the energy of four objects:

• the wavicle and particle outside the well (blue), whose energy is independent of D and W,
• the particle in the well (orange), whose energy depends on D but not W,
• the wavicle in the well (green), whose energy depends on both D and W.

Only the last of these depends appreciably on W, which is why the blue and orange lines are straight.

When W is large (at right in the plot,) then the fact that the well is deep assures that the energy of the wavicle in the well (green) is lower than the energy of the wavicle that sits on the ground (blue), filling the whole space. That implies that the wavicle will remain within the well, just as a particle in the well would.

But inevitably, when W is small enough (at left in the plot,) the situation reverses! (How small exactly? It depends on details, specifically on both the mass m and the hole’s depth D.) The wavicle in the narrow well, unlike a wavicle in a wide well, has energy greater than a wavicle outside the well. That means that the wavicle in the narrow well has sufficient energy to leave the well entirely, and to become a standing wave that sits on the ground, occupying the whole region between the outer walls.

Notice this is completely general! No matter how deep we make the well, as long as the depth is finite, there is always a small enough width for which the wavicle’s escape becomes possible.

Wavicles Push Back; Particles Don’t

To say this another way, a wavicle in a narrow well has more energy than one in a wide well. Therefore, squeezing a well with a wavicle in it costs energy, whereas to squeeze a well with a mere particle inside costs none. As we shrink W, adding more and more energy to the system, there will always come a point where the wavicle will have enough energy to pop out of the hole. It’s almost as though the wavicle is springy and resists being compressed. A particle in a well, by contrast, is completely inert.

This remarkable property of wavicles, related to Heisenberg’s uncertainty principle, has enormous implications for atomic physics and subatomic physics. In my next post, we’ll see examples of these implications, ones of central importance in human existence.

———-

Aside: We can also compare wavicles with ordinary, familiar waves. We’ve seen how important it is that shortening a wavicle increases its energy. What about the waves on a guitar string? Can they, too, hop out of a hole?

A vibrating guitar string has a standing wave on it that produces sound waves at a particular frequency, heard as a particular musical note. A guitar player, by shortening the string with one finger, can make the frequency of the wave increase, which makes the musical note higher. But doing so need not increase the energy of the string’s vibration! There is no relation between energy and frequency for an ordinary wave, because the number of wavicles that makes up that wave can change. The frequency might increase, but if the number of wavicles decreases, then the energy could stay the same, or even decrease.

It’s only when the vibrating string’s standing wave consists of a single wavicle (or an unchangeable number of wavicles) that energy must be added to increase frequency.

For this same reason, a large wave in a well need not pop out of the well as its walls contract, because shrinking the well’s size, which may increase the wave’s frequency, need not increase its energy.

Quantum mechanics is famously unintuitive, but the most intuitive way to think about it is probably the path integral. In the path integral formulation, to find the chance a particle goes from point A to point B, you look at every path you can draw from one place to another. For each path you calculate a complex number, a “weight” for that path. Most of these weights cancel out, leaving the path the particle would travel under classical physics with the biggest contribution. They don’t perfectly cancel out, though, so the other paths still matter. In the end, the way the particle behaves depends on all of these possible paths.

If you’ve heard this story, it might make you feel like you have some intuition for how quantum physics works. With each path getting less likely as it strays from the classical, you might have a picture of a nice orderly set of options, with physicists able to pick out the chance of any given thing happening based on the path.

In a world with just one particle swimming along, this might not be too hard. But our world doesn’t run on the quantum mechanics of individual particles. It runs on quantum field theory. And there, things stop being so intuitive.

First, the paths aren’t “paths”. For particles, you can imagine something in one place, traveling along. But particles are just ripples in quantum fields, which can grow, shrink, or change. For quantum fields instead of quantum particles, the path integral isn’t a sum over paths of a single particle, but a sum over paths traveled by fields. The fields start out in some configuration (which may look like a particle at point A) and then end up in a different configuration (which may look like a particle at point B). You have to add up weights, not for every path a single particle could travel, but every different set of ways the fields could have been in between configuration A and configuration B.

More importantly, though, there is more than one field! Maybe you’ve heard about electric and magnetic fields shifting back and forth in a wave of light, one generating the other. Other fields interact like this, including the fields behind things you might think of as particles like electrons. For any two fields that can affect each other, a disturbance in one can lead to a disturbance in the other. An electromagnetic field can disturb the electron field, which can disturb the Higgs field, and so on.

The path integral formulation tells you that all of these paths matter. Not just the path of one particle or one field chugging along by itself, but the path where the electromagnetic field kicks off a Higgs field disturbance down the line, only to become a disturbance in the electromagnetic field again. Reality is all of these paths at once, a Rube Goldberg machine of a universe.

In such a universe, intuition is a fool’s errand. Mathematics fares a bit better, but is still difficult. While physicists sometimes have shortcuts, most of the time these calculations have to be done piece by piece, breaking the paths down into simpler stories that approximate the true answer.

In the path integral formulation of quantum physics, everything happens at once. And “everything” may be quite a bit larger than you expect.

Many modern mathematical proofs are a combination of conceptual arguments and technical calculations. There is something of a tradeoff between the two: one can add more conceptual arguments to try to reduce the technical computations, or vice versa. (Among other things, this leads to a Berkson paradox-like phenomenon in which a negative correlation can be observed between the two aspects of a proof; see this recent Mastodon post of mine for more discussion.)

In a recent article, Heather Macbeth argues that the preferred balance between conceptual and computational arguments is quite different for a computer-assisted proof than it is for a purely human-readable proof. In the latter, there is a strong incentive to minimize the amount of calculation to the point where it can be checked by hand, even if this requires a certain amount of ad hoc rearrangement of cases, unmotivated parameter selection, or otherwise non-conceptual additions to the arguments in order to reduce the calculation. But in the former, once one is willing to outsource any tedious verification or optimization task to a computer, the incentives are reversed: freed from the need to arrange the argument to reduce the amount of calculation, one can now describe an argument by listing the main ingredients and then letting the computer figure out a suitable way to combine them to give the stated result. The two approaches can thus be viewed as complementary ways to describe a result, with neither necessarily being superior to the other.

In this post, I would like to illustrate this computation-outsourced approach with the topic of zero-density theorems for the Riemann zeta function, in which all computer verifiable calculations (as well as other routine but tedious arguments) are performed “off-stage”, with the intent of focusing only on the conceptual inputs to these theorems.

Zero-density theorems concern upper bounds for the quantity for a given and large , which is defined as the number of zeroes of the Riemann zeta function in the rectangle . (There is also an important generalization of this quantity to -functions, but for simplicity we will focus on the classical zeta function case here). Such quantities are important in analytic number theory for many reasons, one of which is through explicit formulae such as the Riemann-von Mangoldt explicit formula

Clearly is non-increasing in . The Riemann-von Mangoldt formula, together with the functional equation, gives us the asymptotic

Experience has shown that the most important quantity to control here is the exponent , defined as the least constant for which one has an asymptotic

In between the papers of Huxley and Guth-Maynard are dozens of additional improvements on , though it is only the Guth-Maynard paper that actually lowered the supremum norm . A summary of most of the state of the art before Guth-Maynard may be found in Table 2 of this recent paper of Trudgian and Yang; it is complicated, but it is easy enough to get a computer to illustrate it with a plot:

(For an explanation of what is going on under the assumption of the Lindelöf hypothesis, see below the fold.) This plot represents the combined effort of nearly a dozen papers, each one of which claims one or more components of the depicted piecewise smooth curve, and is written in the “human-readable” style mentioned above, where the argument is arranged to reduce the amount of tedious computation to human-verifiable levels, even if this comes the cost of obscuring the conceptual ideas. (For an animation of how this bound improved over time, see here.) Below the fold, I will try to describe (in sketch form) some of the standard ingredients that go into these papers, in particular the routine reduction of deriving zero density estimates from large value theorems for Dirichlet series. We will not attempt to rewrite the entire literature of zero-density estimates in this fashion, but focus on some illustrative special cases.

— 1. Zero detecting polynomials —

As we are willing to lose powers of here, it is convenient to adopt the asymptotic notation (or ) for , and similarly for .

The Riemann-von Mangoldt formula implies that any unit square in the critical strip only contains zeroes, so for the purposes of counting up to errors, one can restrict attention to counting sets of zeroes whose imaginary parts are -separated, and we will do so henceforth. By dyadic decomposition, we can also restrict attention to zeroes with imaginary part comparable to (rather than lying between and .)

The Riemann-Siegel formula, roughly speaking, tells us that for a zero as above, we have

Unfortunately, the particular choice of zero detecting polynomials described above, while simple, is not useful for applications, because the polynomials with very small values of , say , will basically obey the largeness condition (6) a positive fraction of the time, leading to no useful estimates. (Note that standard “square root ” heuristics suggest that the left-hand side of (6) should typically be of size about .) However, this can be fixed by the standard device of introducing a “mollifier” to eliminate the role of small primes. There is some flexibility in what mollifier to introduce here, but a simple choice is to multiply (5) by for a small , which morally speaking has the effect of eliminating the contribution of those terms with , at the cost of extending the range of slightly from to , and also introducing some error terms at scales between and . The upshot is that one then gets a slightly different set of zero-detecting polynomials: one family (often called “Type I”) is basically of the form

One can sometimes squeeze a small amount of mileage out of optimizing the parameter, but for the purpose of this blog post we shall just send to zero. One can then reformulate the above observations as follows. For given parameters and , let denote the best non-negative exponent for which the following large values estimate holds: given any sequence of size , and any -separated set of frequencies for which

As we shall see, the Type II task of controlling for small is relatively well understood (in particular, (10) is already known to hold for all , so in some sense the “Type II” half of the density hypothesis is already established); the main difficulty is with the Type I task, with the main difficulty being that the parameter (representing the length of the Dirichlet series) is often in an unfavorable location.

Remark 1 The approximate functional equation for the Riemann zeta function morally tells us that , but we will not have much use for this symmetry since we have in some sense already incorporated it (via the Riemann-Siegel formula) into the condition .

The standard mean value theorem for Dirichlet series tells us that a Dirichlet polynomial with has an mean value of on any interval of length , and similarly if we discretize to a -separated subset of that interval; this is easily established by using the approximate orthogonality properties of the function on such an interval. Since an interval of length can be subdivided into intervals of length , we see from the Chebyshev inequality that such a polynomial can only exceed on a -separated subset of a length interval of size , which we can formalize in terms of the notation as

Here we see that the bound for oscillates between the density hypothesis prediction of (which is attained when ), and a weaker upper bound of , which thanks to (7), (8) gives the upper bound that was first established in 1937 by Ingham (in the style of a human-readable proof without computer assistance, of course). The same argument applies for all , and gives rise to the bound in this interval, beating the trivial von Mangoldt bound of :

The method is flexible, and one can insert further bounds or hypotheses to improve the situation. For instance, the Lindelöf hypothesis asserts that for all , which on dyadic decomposition can be shown to give the bound

In fact, as observed by Hálasz and Turán in 1969, the Lindelöf hypothesis also gives good Type II control in the regime . The key point here is that the bound (13) basically asserts that the functions behave like orthogonal functions on the range , and this together with a standard duality argument (related to the Bessel inequality, the large sieve, or the method in harmonic analysis) lets one control the large values of Dirichlet series, with the upshot here being that

While we are not close to proving the full strength of (13), the theory of exponential sums gives us some relatively good control on the left-hand side in some cases. For instance, by using van der Corput estimates on (13), Montgomery in 1969 was able to obtain an unconditional estimate which in our notation would be

In particular, the density hypothesis is now established for all . But one can do better. Consider for instance the case of . Let us inspect the current best bounds on from the current tools:

Here we immediately see that it is only the case that is preventing us from improving the bound on to below the density hypothesis prediction of . However, it is possible to exclude this case through exponential sum estimates. In particular, the van der Corput inequality can be used to establish the bound for , or equivalently that

One can continue importing in additional large values estimates into this framework to obtain new zero density theorems. For instance, one could insert the twelfth moment estimate of Heath-Brown, which in our language asserts that ; one could also insert variants of the van der Corput estimate, such as bounds coming from other exponent pairs, the Vinogradov mean value theorem or (more recently) the resolution of the Vinogradov main conjecture by Bourgain-Demeter-Guth using decoupling methods, or by Wooley using efficient congruencing methods. We close with an example from the Guth-Maynard paper. Their main technical estimate is to establish a new large values theorem (Proposition 3.1 from their paper), which in our notation asserts that

This is not the most difficult (or novel) part of the Guth-Maynard paper – the proof of (20) occupies about 34 of the 48 pages of the paper – but it hopefully illustrates how some of the more routine portions of this type of work can be outsourced to a computer, at least if one is willing to be convinced purely by numerically produced graphs. Also, it is possible to transfer even more of the Guth-Maynard paper to this format, if one introduces an additional quantity that tracks not the number of large values of a Dirichlet series, but rather its energy, and interpreting several of the key sub-propositions of that paper as providing inequalities relating and (this builds upon an earlier paper of Heath-Brown that was the first to introduce non-trivial inequalities of this type).

The above graphs were produced by myself using some quite crude Python code (with a small amount of AI assistance, for instance via Github Copilot); the code does not actually “prove” estimates such as (19) or (21) to infinite accuracy, but rather to any specified finite accuracy, although one can at least make the bounds completely rigorous by discretizing using a mesh of rational numbers (which can be manipulated to infinite precision) and using the monotonicity properties of the various functions involved to control errors. In principle, it should be possible to create software that would work “symbolically” rather than “numerically”, and output (human-readable) proof certificates of bounds such as (21) from prior estimates such as (20) to infinite accuracy, in some formal proof verification language (e.g., Lean). Such a tool could potentially shorten the primary component of papers of this type, which would then focus on the main inputs to a standard inequality-chasing framework, rather than the routine execution of that framework which could then be deferred to an appendix or some computer-produced file. It seems that such a tool is now feasible (particularly with the potential of deploying AI tools to locate proof certificates in some tricky cases), and would be useful for many other analysis arguments involving explicit exponents than the zero-density example presented here (e.g., a version of this could have been useful to optimize constants in the recent resolution of the PFR conjecture), though perhaps the more practical workflow case for now is to use the finite-precision numerics approach to locate the correct conclusions and intermediate inequalities, and then prove those claims rigorously by hand.

It is the duty of good people, always and everywhere, to condemn, reject, and disavow the use of political violence.

Even or especially when evildoers would celebrate the use of political violence against us.

It is our duty always to tell the truth, always to play by the rules — even when evil triumphs by lying, by sneeringly flouting every rule.

It appears to be an iron law of Fate that whenever good tries to steal a victory by evil means, it fails. This law is so infallible that any good that tries to circumvent it thereby becomes evil.

When Sam Bankman-Fried tries to save the world using financial fraud — he fails. Only the selfish succeed through fraud.

When kind, nerdy men, in celibate desperation, try to get women to bed using “Game” and other underhanded tactics — they fail. Only the smirking bullies get women that way.

Quantum mechanics is false, because its Born Rule speaks of randomness.

But randomness can’t explain why a bullet aimed at a destroyer of American democracy must inevitably miss by inches, while a bullet aimed at JFK or RFK or MLK or Gandhi or Rabin must inevitably meet its target.

Yet for all that, over the millennia, good has made actual progress. Slavery has been banished to the shadows. Children survive to adulthood. Sometimes altruists become billionaires, or billionaires altruists. Sometimes the good guy gets the girl.

Good has progressed not by lucky breaks — for good never gets lucky breaks — but only because the principles of good are superior.

There’s a kind of cosmic solace that could be offered even to the Jewish mother in the gas chamber watching her children take their last breaths, though the mother could be forgiven for rejecting it.

The solace is that good will triumph — if not in the next four years, then in the four years after that.

Or if not in four, then in a hundred.

Or if not in a hundred, then in a thousand.

Or if not in the entire history of life in on this planet, then on a different planet.

Or if not in this universe, then in a different universe.

Let us commit to fighting for good using good methods only. Fate has decreed in any case that, for us, those are the only methods that work.

Let us commit to use good methods only even if it means failure, heartbreak, despair, the destruction of democratic institutions and ecosystems multiplied by a thousand or a billion or any other constant — with the triumph of good only in the asymptotic limit.

Good will triumph, when it does, only because its principles are superior.

Endnote: I’ve gotten some pushback for this prayer from one of my scientific colleagues … specifically, for the part of the prayer where I deny the universal validity of the Born rule. And yet a less inflammatory way of putting the same point would simply be: I am not a universal Bayesian. There are places where my personal utility calculations do a worst-case analysis rather than averaging over possible futures for the world.

Endnote 2: It is one thing to say, never engage in political violence because the expected utility will come out negative. I’m saying something even stronger than that. Namely, even if the expected utility comes out positive, throw away the whole framework of being an expected-utility maximizer before you throw away that you’re never going to endorse political violence. There’s a class of moral decisions for which you’re allowed to use, even commendable for using, expected-utility calculations, and this is outside that class.

Endnote 3: If you thought that Trump’s base was devoted before, now that the MAGA Christ-figure has sacrificed his flesh — or come within a few inches of doing so — on behalf of the Nation, they will go to the ends of the earth for him, as much as any followers did for any ruler in human history. Now the only questions, assuming Trump wins (as he presumably will), are where he chooses to take his flock, and what emerges in the aftermath for what we currently call the United States. I urge my left-leaning American friends to look into second passports. Buckle up, and may we all be here to talk about it on the other end.

Perhaps like the poor current President of the United States, I can feel myself fading, my memory and verbal facility and attention to detail failing me, even while there’s so much left to do to battle the nonsense in the world. I started my career on an accelerated schedule—going to college at 15, finishing my PhD at 22, etc. etc.—and the decline is (alas) also hitting me early, at the ripe age of 43.

Nevertheless, I do seem to remember that this was once primarily a quantum computing blog, and that I was known to the world as a quantum computing theorist. And exciting things continue to happen in quantum computing…

First, a company in the UK called Oxford Ionics has announced that it now has a system of trapped-ion qubits in which it’s prepared two-qubit maximally entangled states with 99.97% fidelity. If true, this seems extremely good. Indeed, it seems better than the numbers from bigger trapped-ion efforts, and quite close to the ~99.99% that you’d want for quantum fault-tolerance. But maybe there’s a catch? Will they not be able to maintain this kind of fidelity when doing a long sequence of programmable two-qubit gates on dozens of qubits? Can the other trapped-ion efforts actually achieve similar fidelities in head-to-head comparisons? Anyway, I was surprised to see how little attention the paper got on SciRate. I look forward to hearing from experts in the comment section.

Second, I almost forgot … but last week Quantinuum announced that it’s done a better quantum supremacy experiment based on Random Circuit Sampling with 56 qubits—similar to what Google and USTC did in 2019-2020, but this time using 2-qubit gates with 99.84% fidelities (rather than merely ~99.5%). This should set a new standard for those looking to simulate these things using tensor network methods.

Third, a new paper by Schuster, Haferkamp, and Huang gives a major advance on k-designs and pseudorandom unitaries. Roughly speaking, the paper shows that even in one dimension, a random n-qubit quantum circuit, with alternating brickwork layers of 2-qubit gates, forms a “k-design” after only O(k polylog k log n) layers of gates. Well, modulo one caveat: the “random circuit” isn’t from the most natural ensemble, but has to have some of its 2-qubit gates set to the identity, namely those that straddle certain contiguous blocks of log n qubits. This seems like a purely technical issue—how could randomizing those straddling gates make the mixing behavior worse?—but future work will be needed to address it. Notably, the new upper bound is off from the best-possible k layers by only logarithmic factors. (For those tuning in from home: a k-design informally means a collection of n-qubit unitaries such that, from the perspective of degree-k polynomials, choosing a unitary randomly from the collection looks the same as choosing randomly among all n-qubit unitary transformations—i.e., from the Haar measure.)

Anyway, even in my current decrepit state, I can see that such a result would have implications for … well, all sorts of things that quantum computing and information theorists care about. Again I welcome any comments from experts!

Incidentally, congratulations to Peter Shor for winning the Shannon Award!

guest post by Wilf Offord

One of the earliest and most well-studied definitions in “higher” category theory is that of a monoidal category. These have found ubiquitous applications in pure mathematics, physics, and computer science; from type theory to topological quantum field theory. The machine making them tick is MacLane’s coherence theorem: if anything deserves to be called “the fundamental theorem” of monoidal categories, it is this. As such, numerous other proofs have sprung up in recent years, complementing MacLane’s original one. One strategy with a particularly operational flavour uses rewriting systems: the morphisms of a free monoidal category are identified with normal forms for some rewriting system, which can take the form of a logical system as in (UVZ20,Oli23), or a diagrammatic calculus as in (WGZ22). In this post, we turn to skew-monoidal categories, which no longer satisfy a coherence theorem, but nonetheless can be better understood using rewriting methods.

Monoidal Categories

Monoidal categories are categories equipped with a “product” of objects, which is associative and unital “up to isomorphism” in a specified sense. An example is the category of sets with its cartesian product: while the sets $(X\times Y)\times Z$ and $X\times(Y\times Z)$ are not technically equal, they are isomorphic, via an isomorphism which is in some sense canonical. More precisely:

Definition: A monoidal category $(\mathcal{C},\otimes,I,\alpha,\lambda,\rho)$ consists of the following data:

• A category $\mathcal{C}$
• A functor $\otimes : \mathcal{C}\times\mathcal{C}\to\mathcal{C}$
• An object $\operatorname{I}\in\mathcal{C}$
• Isomorphisms $\alpha_{x,y,z} : (x\otimes y)\otimes z \to x\otimes(y\otimes z)$ natural in $x,y,z$
• Isomorphisms $\lambda_x : \operatorname{I}\otimes x \to x$ and $\rho_x : x \to x\otimes\operatorname{I}$natural in $x$

such that the following $5$ diagrams commute:

(for $f:x_0\to x_1$ and $y\in\mathcal{C}$, we write $f\otimes y$ to mean $f\otimes\operatorname{id}_y: x_0\otimes y \to x_1\otimes y$, and similarly for $y\otimes f$)

Remark: The above is MacLane’s original definition of a monoidal category. It was later shown that the last three equations follow from the first two, but we include them since this does not hold for skew-monoidal categories, as we will present below.

The coherence theorem for monoidal categories can be stated in terms of the free monoidal category on a set $S$ of objects. We will not go into the formal definition, but this is the category whose objects are “formal products” of the elements of $S$ (e.g. $\operatorname{I}$, $s_0\otimes s_1$, $(s_0 \otimes s_1)\otimes (s_2\otimes s_0)$ etc.), and whose morphisms are only those built from $\alpha$, $\lambda$, $\rho$, $\operatorname{id}$, $\circ$ and $\otimes$ subject to the equations above and no other “accidental” equations. The coherence theorem is then:

Theorem: (MacLane’s coherence theorem) The free monoidal category on a set of objects is a preorder. That is, any two morphisms built from $\alpha$, $\lambda$, $\rho$, $\operatorname{id}$, $\circ$ and $\otimes$ between the same two objects are equal.

The above theorem is incredibly powerful, and implies that the equations listed above are strong enough to imply any other well-typed equation we could dream up in the language of monoidal categories. It was first proved in (Mac63), but we will investigate a few modern proof strategies later on in this post. First, though, we turn to skew-monoidal categories.

Skew-monoidal Categories

The above definition reflects a general pattern in higher category theory: equalities get replaced by isomorphisms. Let us explain what we mean by this. In a monoid, there is a product operation that is associative and unital on the nose, but when we “categorify” this definition, these associativity and unitality laws are promoted to pieces of the structure in their own right: the associator and unitor isomorphisms. This opens up an interesting direction for generalisation: what happens if we do not require the maps $\alpha$, $\lambda$, and $\rho$ to be invertible? The definition given above is phrased so as to still make sense once we drop the invertibility constraint, and doing so we obtain the definition of skew-monoidal categories.

Clearly every monoidal category is a skew-monoidal category, but we can also give some examples illustrating the new freedom that dropping the invertibility restraint allows.

Example: (Pointed Sets) Consider the category of sets with a chosen base point. Setting $\operatorname{I} = (1,\star)$, and $(X,x_0)\otimes(Y,y_0) = (X\sqcup Y,x_0)$, there is an obvious choice for $\alpha$, $\lambda$, and $\rho$ (exercise: find these!) defining a skew-monoidal structure. Note the asymmetry in the definition of $\otimes$: due to this, $\lambda$ is not injective and $\rho$ is not surjective! However, in this case we nevertheless have that $\alpha$ is invertible.

Example: ($\mathbb{N}$) We can put a skew-monoidal structure on $\mathbb{N}$, considered as a category whose objects are non-negative integers, and where there is exactly one morphism $n\to m$ if $n\leq m$. In fact, there are countably many such structures, one for each $k\in\mathbb{N}$. We define:

• $\operatorname{I} = k$
• $m\otimes n = (m\dot - n) + k$, where $m\dot - n = \max(m-n,0)$.

$\lambda$, $\rho$, and $\alpha$ are now the assertions that, for any $x,y,z\in\mathbb{N}$:

• $(k\dot- k)+x = x \leq x$ (so $\lambda$ is invertible)
• $x \leq (x\dot- k) + k$ ($\rho$ is not in general invertible)
• $((x\dot - k) + y) \dot- k + z \leq x \dot- k + (y \dot- k) + z$

The next example requires a bit of background knowledge on Kan extensions, and can be skipped.

Example: Let $J:\mathcal{C}\to\mathcal{D}$ be a functor, where $\mathcal{C}$ is small and $\mathcal{D}$ is cocomplete, so that all left Kan extensions of functors $F:\mathcal{C}\to\mathcal{D}$ along $J$ exist. We can put a skew-monoidal structure on the functor category $[\mathcal{C},\mathcal{D}]$, where $F\otimes G=\operatorname{Lan}_J F \circ G$. The monoidal unit is $J$. The universal property of left Kan extensions ensures we have natural morphisms:

• $\lambda_F : \operatorname{Lan}_J J\circ F \to F$
• $\rho_F : F \to \operatorname{Lan}_J F \circ J$
• $\alpha_{F,G,H} : \operatorname{Lan}_J(\operatorname{Lan}_J F \circ G)\circ H \to \operatorname{Lan}_J F \circ (\operatorname{Lan}_J G \circ H)$

If $J$ is fully faithful, then $\rho$ is an isomorphism. If $J$ is dense, meaning $\operatorname{Lan}_J J\cong \operatorname{id}$, then $\lambda$ is an isomorphism. If $\operatorname{Lan}_J F$ is absolute for all $F$, meaning the Kan extension is preserved by all functors, then $\alpha$ is an isomorphism, and so in the case where all three of these properties hold, the above gives an ordinary monoidal category. However, we see that the most general case of this construction, involving only Kan extensions which are ubiquitous in category theory, naturally gives us not a monoidal category but a skew-monoidal one.

While the definitions of monoidal and skew-monoidal categories are not so different, they behave in very different ways. The most obvious question we can ask about skew-monoidal categories is whether a theorem like the coherence theorem holds. The answer turns out to be “no”: for instance, in the free skew-monoidal category generated by just the object $\operatorname{I}$, the morphisms $\rho_I\circ\lambda_I$ and $\operatorname{id}_{I\otimes I}$ are not equal! If we want to understand the coherence morphisms of skew-monoidal categories, we will need a more nuanced approach.

Some modern approaches to the proof of the coherence theorem characterise coherences in monoidal categories as normal forms of some rewriting system; by showing that there is exactly one normal form of each given type, the coherence theorem is proved. But this approach can also be used to study skew-monoidal categories: while the example above shows we have no hope of having unique normal forms of each type, we can still get a much better picture of the structure by implementing it as a rewriting system. It is to these rewriting systems that we now turn.

Multicategories and Graphical Calculus

The rewriting systems we describe are all based on (skew) multicategories, which we will briefly introduce. The motivating idea is that while the morphisms of categories have one input and one output, the morphisms of multicategories have multiple inputs and one output. More precisely:

Definition: A multicategory consists of:

• A class $\mathcal{C}$ of objects.
• For each pair of a (possibly empty) list $\overline{A}=A_1,\dots,A_n$ of objects and an object $B$, a class $\mathcal{C}(A_1,\dots,A_n;B)$ of multimorphisms from $\overline{A}$ to $B$.
• For each object $A$, an element $\operatorname{id}_A\in\mathcal{C}(A;A)$.
• Operations $$\circ_k:\mathcal{C}(\overline{A};C)\times\mathcal{C}(\overline{B};A_k)\to\mathcal{C}(A_1,\dots,A_{k-1},\overline{B},A_{k+1},\dots,A_n;C)$$

$\circ_k$ is to be thought of as precomposition on the $k$th input. These data are subject to equations that are analogues of associativity and unitality for ordinary categories, but these are best described using the graphical calculus for multicategories, which we now introduce.

Our graphical calculus is to be read top-to-bottom, and so we draw a multimorphism from $\overline{A}$ to $B$ as:

Identity morphisms are not drawn; the following represents $\operatorname{id}_A$:

We denote the composite $g\circ_k f$ by:

The unitality and associativity laws are then immediate from the graphical calculus, for instance $(f\circ_1 g)\circ_2 h = (f\circ_2 h)\circ_1 g$ is an equation that holds in the theory of multicategories for $f : A_1,A_2 \to C$, $g : B_1\to A_1$, $h : B_2\to A_2$, and this equation holds in the graphical calculus up to planar isotopy of diagrams (or, less formally, “wiggling things around”):

The reason for introducing multicategories is that they are intimately linked to monoidal categories. Given the structure of a monoidal category, the idea of “multiple inputs” can be encoded using the monoidal product, for instance $f:(A_1\otimes(\dots\otimes A_n)\dots)\to B$. Indeed, every monoidal category $\mathcal{C}$ can be given the structure of a multicategory $\operatorname{M}(\mathcal{C})$. The difference between the two notions is that not all multicategories arise this way. Not all are “representable”, in the sense that there is a single object $A_1\otimes\dots\otimes A_n$ which encodes all the information about multimorphisms out of $A_1,\dots A_n$. To this end, we define:

Definition: A representable multicategory is a multicategory $\mathcal{C}$ equipped with, for each list $A_1,\dots,A_n$ of objects of $\mathcal{C}$:

• An object $A_1\otimes\dots\otimes A_n$. (When $\overline{A}$ is empty, we denote this by $\operatorname{I}$)
• A multimorphism $\theta_{\overline{A}}:A_1,\dots,A_n\to A_1\otimes\dots\otimes A_n$.

Such that $$-\circ_k\theta_{\overline{B}} : \mathcal{C}(A_1,\dots A_{k-1},\otimes\overline{B},A_{k+1},\dots,A_m;C)\to\mathcal{C}(A_1,\dots A_{k-1},\overline{B},A_{k+1},\dots,A_m;C)$$ is always an isomorphism.

The above definition is justified by the following:

Theorem: A multicategory $\mathcal{C}$ is isomorphic to $\operatorname{M}(\mathcal{D})$ for some monoidal category $\mathcal{D}$ if and only if it is representable.

(we have not technically defined isomorphism of multicategories: for details see Chapter 2 of (Lei03)). The above theorem, together with the fact that monoidal categories are isomorphic iff the corresponding multicategories are, imply a $1-1$ correspondence between representable multicategories and monoidal categories.

Given the additional structure of representability, we can add more power to our graphical calculus. We draw $\theta_{\overline{A}}$ as:

To express that $-\circ_k\theta_{\overline{B}}$ is invertible, we represent the inverse, a map $$\mathcal{C}(A_1,\dots A_{k-1},\overline{B},A_{k+1},\dots,A_m;C)\to\mathcal{C}(A_1,\dots A_{k-1},\otimes\overline{B},A_{k+1},\dots,A_m;C)$$ as:

In the case where $\overline{B}$ is empty, we write the above as:

The above is subject to the equations expressing invertibility:

We now have a diagrammatic equational theory for represntable multicategories, and hence monoidal categories. Thus, all the coherences of a monoidal category should be expressible diagrammatically, along with the equations between them. For instance, the following represent the associator, left and right unitors:

And their inverses as the vertically reflected versions:

And the following is a derivation of $\lambda_{\operatorname{I}} \circ\rho_{\operatorname{I}} = \operatorname{id}_{\operatorname{I}}$, for instance:

In fact, the above graphical calculus is exactly the same as that described in (WGZ22), although the way the authors arrive at it is completely different, having nothing to do with multicategories. Instead, they consider the strictification of a monoidal category. Moreover, they show using graphical methods that every diagram of the same type is equal, proving theorem the coherence theorem.

The strictification theorem for monoidal categories doesn’t have an analogue for skew-monoidal categories, and so the approach taken in (WGZ22) is not suitable to be adapted to this case. However, there is an analogue of multicategories, skew multicategories, defined in (BL18), to which we now turn.

Skew Multicategories

The idea of skew multicategories is that there are two kinds of multimorphisms, “tight” and “loose”, which behave differently with respect to composition. Loose morphisms behave like ordinary multimorphisms in a multicategory. Tight morphisms, on the other hand, can only be composed together on the leftmost input, via $\circ_1$, and this is what leads to the asymmetry.

Definition: A skew multicategory consists of:

• A class $\mathcal{C}$ of objects.
• For each (possibly empty) list $\overline{A}$ of objects, and object $B$, a class $\mathcal{C}_l(\overline{A};B)$ of loose multimorphisms.
• For each nonempty list $\overline{A}$ of objects, and object $B$, a class $\mathcal{C}_t(\overline{A};B)$ of tight multimorphisms.
• Maps $\gamma : \mathcal{C}_t(\overline{A};B) \to \mathcal{C}_l(\overline{A};B)$, allowing tight multimorphisms to be viewed as loose ones.
• Tight identity multimorphisms $\operatorname{id}_A\in\mathcal{C}_t(A;A)$.
• Composition operations: $$\begin{aligned} &\circ_k:\mathcal{C}_l(\overline{A};C)\times\mathcal{C}_l(\overline{B};A_k)\to\mathcal{C}_l(A_1,\dots,A_{k-1},\overline{B},A_{k+1},\dots,A_n;C) \\ &\circ_1:\mathcal{C}_t(\overline{A};C)\times\mathcal{C}_t(\overline{B};A_1)\to\mathcal{C}_t(\overline{B},A_2,\dots,A_n;C)\\ &\circ_k:\mathcal{C}_t(\overline{A};C)\times\mathcal{C}_l(\overline{B};A_k)\to\mathcal{C}_t(A_1,\dots,A_{k-1},\overline{B},A_{k+1},\dots,A_n;C)\quad \text{ (for }\,k\gt 1\text{)} \end{aligned}$$

These are subject to equations, which we once again postpone until we set up our graphical calculus.

Warning: The graphical calculus for skew multicategories presented below, and representable skew multicategories presented later, is ongoing work, and a formal correspondence between the calculus and the theory of (left representable) skew multicategories is yet to be proven. The calculus can thus for the moment be taken as a pedagogical tool for the exposition of skew multicategories, and a formal proof of its correctness is left as future work.

We graphically depict tight versus loose multimorphisms using two colours:

The placement of the colours ensures that the composition operations behave as above: for instance, the following ways of composing tight with tight multimorphisms, and tight with loose multimorphisms, yield tight multimorphisms:

Identities are depicted similarly:

While the map $\gamma$ is represented as:

In addition to the equations holding by vitue of isotopy of diagrams, we also impose:

Once again, there is a relationship between skew-monoidal categories and skew multicategories. Given a skew-monoidal category $\mathcal{C}$, we define a skew-monoidal structure $\operatorname{S}(\mathcal{C})$ with:

• $\operatorname{S}(\mathcal{C})_t(A_1,\dots,A_n;B)=\mathcal{C}((A_1\otimes(\dots A_n)\dots),B)$.
• $\operatorname{S}(\mathcal{C})_l(A_1,\dots,A_n;B)=\mathcal{C}((\operatorname{I}\otimes(A_1\otimes(\dots A_n)\dots),B)$.
• $\gamma$ is defined by precomposition with $\lambda$.

The authors check that this gives a skew multicategory in (BL18).

Once again, the skew multicategories that arise from skew-monoidal categories in the above way can be characterised via a representability property:

Definition: A skew multicategory $\mathcal{C}$ is left representable if there is:

• An object $\operatorname{I}$, together with a loose morphism $\theta_\varnothing\in\mathcal{C}_l(\ ;\operatorname{I})$
• For every list $A_1\dots A_n$ of objects, an object $A_1\otimes\dots\otimes A_n$ together with a tight multimorphism $\theta_{\overline{A}}\in\mathcal{C}_t(A_1,\dots,A_n;A_1\otimes\dots\otimes A_n)$ such that the maps: $$\begin{aligned} -\circ_1\theta_{\overline{A}} &: \mathcal{C}_t(\otimes \overline{A},\overline{B};C)\to\mathcal{C}_t(\overline{A},\overline{B};C) \\ \gamma(-)\circ_1\theta_\varnothing &: \mathcal{C}_t(I,\overline{A};B)\to\mathcal{C}_l(\overline{A};B) \end{aligned}$$ are always invertible.

Once again, we depict $\theta_\varnothing$ and $\theta_{\overline{A}}$ as:

And the inverses to $-\circ_1\theta_{\overline{A}}$ and $\gamma(-)\circ_1\theta_\varnothing$ as:

imposing the equations:

And we have the following:

Theorem: A skew multicategory $\mathcal{C}$ is isomorphic to $\operatorname{S}(\mathcal{D})$ for some skew-monoidal category $\mathcal{D}$ if and only if it is left representable.

implying $1-1$ correspondence between skew-monoidal categories and left representable skew multicategories.

As a sanity check, we can construct the coherences $\alpha$, $\lambda$, and $\rho$ in our graphical calculus as:

but now we cannot construct any diagrams of the opposite type!

Modulo the warning given above, left representable skew multicategories and their graphical calculus now give us a way to understand and manipulate coherences in a free skew-monoidal category. While we no longer have uniqueness of diagrams of the same type, we now can get some visual intuition for why, for instance, $\rho_I\circ\lambda_I\neq\operatorname{id}_{I\otimes I}$:

Sequent Calculus for (Skew) Multicategories

While diagrammatic calculi like those presented above make reasoning intuitive and visual, the formal properties of such rewrite systems can be hard to rigorously understand and implement. A step towards an even more operational understanding of coherences in (skew-)monoidal categories is implementing their theory as a deductive system akin to those found in formal logic.

We present here the sequent calculus developed in (UVZ20) for (skew-)monoidal categories, which itself is inspired by the work of (BL18), and can be seen more explicitly as a calculus for left representable skew multicategories. First, we treat the ordinary (non-skew) case:

Definition: (Sequent Calculus for Multicategories) Fix an alphabet $\mathcal{A}$ of object variables. The sequent calculus for multicategories has, as its judgements, sequents of the form $A_1,\dots,A_n\to B$, where $A_1,\dots,A_n,B\in\mathcal{A}$. We use greek metavariables $\Gamma,\Delta,$ etc. for the lists of objects appearing on the left hand side. Its derivation rules are:

We identify derivations of the sequent calculus with morphisms in the free multicategory on $\mathcal{A}$. The above rules clearly correspond to the existence of identity morphisms, and composition in a multicategory. We must, however, impose associativity and unitality equations, for instance:

We omit the full rules: they can be easily derived from the axioms of a multicategory.

To capture the morphisms of a free representable multicategory, we must increase the expressive power. “Objects” appearing on each side of the sequent will no longer be simple variables, but now bracketed lists of variables delimited by $\otimes$, for instance $A\otimes(B\otimes C)$, or $A\otimes \operatorname{I}\otimes A$, writing $\operatorname{I}$for the empty list. We add the following four rules:

These can be interpreted as, respectively:

• $\otimes$R: the existence of the maps $\theta_{\overline{A}}$, coupled with composition.
• $\otimes$L: the inverses to $-\circ_k\theta_{\overline{A}}$
• $\operatorname{I}$R: the map $\theta_\varnothing : \ \to \operatorname{I}$
• $\operatorname{I}$L: the inverse to $-\circ_k\theta_\varnothing$

and as such they are subject to more equations, similarly derived from the axioms of a representable multicategory. We have:

Theorem: There is a bijection between derivations of the above sequent calculus, up to the equational theory hinted at above, and the morphisms of a free representable multicategory (and hence a free monoidal category).

Moreover, these equations can be given a direction such that they implement a confluent rewriting system with unique normal forms of each type, giving another proof of theorem the coherence theorem.

The authors of (UVZ20) adapt the above sequent calculus to work for skew multicategories as follows. To capture the asymmetry inherent in the definition, judgements are now of the form $\operatorname{S} \operatorname{|} \Gamma \to A$, where $\Gamma$ is a list of objects as before, $A$ is an object, and $\operatorname{S}$ is a “stoup”: a new privileged first position which can either be a single object, or empty (written $-\operatorname{|}\Gamma\to A$ in the second case). We will identify tight morphisms with derivations of sequents with nonempty stoup, and loose morphisms with derivations of sequents with empty stoup. We define:

Definition: (Sequent Calculus for Skew Multicategories) We replace the rules of the sequent calculus for multicategories with the following:

which correspond, respectively, to:

• (tight) identity morphisms,
• the map $\gamma$,
• composition $\circ_1$
• composition $\circ_k$

These are again subject to equations which are listed in full in (UVZ20), based on the axioms of skew multicategories. For instance, the equation expressing compatibility of $\gamma$ with composition becomes:

To augment this into a sequent calculus for left representable skew multicategories, we once again add four new rules, which now make key use of the stoup:

These correspond to:

• Composition with the maps $\circ_k$
• The inverse to $-\circ_1\theta_{\overline{A}}$
• The map $\theta_\varnothing$
• The inverse to $\gamma(-)\circ_1\theta_\varnothing$

And are subject to rules listed in (UVZ20). This finally gives us:

Theorem: There is a bijection between derivations of $A_1\operatorname{|} A_2,\dots A_n \to B$ of the above sequent calculus, up to the equational theory given in (UVZ20), and tight morphisms $A_1,\dots, A_n\to B$ of a free left representable skew multicategory. In the case where $n=1$, we have that derivations of $A\operatorname{|}\to B$ up to the equational theory are in bijection with morphisms from $A$ to $B$ in a free skew-monoidal category.

For instance, a derivation corresponding to the associator is:

Moreover, the authors show that these equational rules can be directed, giving a confluent terminating rewriting system, and thus equality of coherences in a skew-monoidal category can be decided using the above logical system.

What’s more, we may be interested in asking whether there exists a coherence morphism between two objects, and enumerating such morphisms. The authors in (UVZ20) also provide an algorithm to do this, by adapting the above sequent calculus to a so-called “focused” version.

Conclusion and future work

While the coherence theorem of MacLane no longer holds for skew-monoidal categories, rewriting approaches like those investigated above can provide a way to get to grips with these complex structures. There is much more room for investigation of related structures, such as skew-closed categories, and braided skew-monoidal categories, where the above approaches could also be fruitful. In addition, there is future work in a more rigorous analysis of the graphical calculus presented above for skew-monoidal categories.

References

• {#UVZ20} [[Tarmo Uustalu, Niccolò Veltri, Noam Zeiberger]], The Sequent Calculus of Skew Monoidal Categories 2020 (arXiv:2003.05213)

• {#Oli23 [[Federico Olimpieri]], Coherence by Normalization for Linear Multicategorical Structures 2023 (arXiv:2302.05755)

• {#WGZ22} [[Paul Wilson, Dan Ghica, and Fabio Zanasi]], String diagrams for non- strict monoidal categories 2022 (arXiv:2201.11738)

• {#Mac63} [[Saunders Maclane]], Natural Associativity and Commutativity 1963 (pdf)

• {#Lei03} [[Tom Leinster]], Higher Operads, Higher Categories 2003 (arXiv)

• {#BL18} [[John Bourke and Stephen Lack]], Skew monoidal categories and skew multicategories 2017 (arXiv:1708.06088)

Real life continues to make itself felt in various ways this summer (and that's not even an allusion to political madness), but here are three papers (two from others and a self-indulgent plug for our work) you might find interesting.

• There has been a lot of work in recent years particularly by the group of Andrea Cavalleri, in which they use infrared light to pump particular vibrational modes in copper oxide superconductors (and other materials) (e.g. here).  There are long-standing correlations between the critical temperature for superconductivity, \(T_{c}\), and certain bond angles in the cuprates.  Broadly speaking, using time-resolved spectroscopy, measurements of the optical conductivity in these pumped systems show superconductor-like forms as a function of energy even well above the equilibrium \(T_{c}\), making it tempting to argue that the driven systems are showing nonequilibrium superconductivity.  At the same time, there has been a lot of interest in looking for other signatures, such as signs of the ways uperconductors expel magnetic flux through the famous Meissner effect.  In this recent result (arXiv here, Nature here), magneto-optic measurements in this same driven regime show signs of field build-up around the perimeter of the driven cuprate material in a magnetic field, as would be expected from Meissner-like flux expulsion.  I haven't had time to read this in detail, but it looks quite exciting.  
• Optical trapping of nanoparticles is a very useful tool, and with modern techniques it is possible to measure the position and response of individual trapped particles to high precision (see here and here).  In this recent paper, the group of David Moore at Yale has been able to observe the recoil of such a particle due to the decay of a single atomic nucleus (which spits out an energetic alpha particle).  As an experimentalist, I find this extremely impressive, in that they are measuring the kick given to a nanoparticle a trillion times more massive than the ejected helium nucleus.  
• From our group, we have published a lengthy study (arXiv here, Phys Rev B here) of local/longitudinal spin Seebeck response in VO2, a material with an insulating state that is thought to be magnetically inert.  This corroborates our earlier work, discussed here.  In brief, in ideal low-T VO2, the vanadium atoms are paired up into dimers, and the expectation is that the unpaired 3d electrons on those atoms form singlets with zero net angular momentum.  The resulting material would then not be magnetically interesting (though it could support triplet excitations called triplons).  Surprisingly, at low temperatures we find a robust spin Seebeck response, comparable to what is observed in ordered insulating magnets like yttrium iron garnet.  It seems to have the wrong sign to be from triplons, and it doesn't seem possible to explain the details using a purely interfacial model.  I think this is intriguing, and I hope other people take notice.

A loose rule of thumb: PhD candidates in the US are treated like students. In Europe, they’re treated like employees.

This does exaggerate things a bit. In both Europe and the US, PhD candidates get paid a salary (at least in STEM). In both places, PhD candidates count as university employees, if sometimes officially part-time ones, with at least some of the benefits that entails.

On the other hand, PhD candidates in both places take classes (albeit more classes in the US). Universities charge both for tuition, which is in turn almost always paid by their supervisor’s grants or department, not by them. Both aim for a degree, capped off with a thesis defense.

But there is a difference. And it’s at its most obvious in how applications work.

In Europe, PhD applications are like job applications. You apply to a particular advisor, advertising a particular kind of project. You submit things like a CV, cover letter, and publication list, as well as copies of your previous degrees.

In the US, PhD applications are like applications to a school. You apply to the school, perhaps mentioning an advisor or topic you are interested in. You submit things like essays, test scores, and transcripts. And typically, you have to pay an application fee.

I don’t think I quite appreciated, back when I applied for PhD programs, just how much those fees add up to. With each school charging a fee in the $100 range, and students commonly advised to apply to ten or so schools, applying to PhD programs in the US can quickly get unaffordable for many. Schools do offer fee waivers under certain conditions, but the standards vary from school to school. Most don’t seem to apply to non-Americans, so if you’re considering a US PhD from abroad be aware that just applying can be an expensive thing to do.

Why the fee? I don’t really know. The existence of application fees, by itself, isn’t a US thing. If you want to get a Master’s degree from the University of Copenhagen and you’re coming from outside Europe, you have to pay an application fee of roughly the same size that US schools charge.

Based on that, I’d guess part of the difference is funding. It costs something for a university to process an application, and governments might be willing to cover it for locals (in the case of the Master’s in Copenhagen) or more specifically for locals in need (in the US PhD case). I don’t know whether it makes sense for that cost to be around $100, though.

It’s also an incentive, presumably. Schools don’t want too many applicants, so they attach a fee so only the most dedicated people apply.

Jobs don’t typically have an application fee, and I think it would piss a lot of people off if they did. Some jobs get a lot of applicants, enough that bigger and more well-known companies in some places use AI to filter applications. I have to wonder if US PhD schools are better off in this respect. Does charging a fee mean they have a reasonable number of applications to deal with? Or do they still have to filter through a huge pile, with nothing besides raw numbers to pare things down? (At least, because of the “school model” with test scores, they have some raw numbers to use.)

Overall, coming at this with a “theoretical physicist mentality”, I have to wonder if any of this is necessary. Surely there’s a way to make it easy for students to apply, and just filter them down to the few you want to accept? But the world is of course rarely that simple.

Guest post by Matt Kukla and Tanjona Ralaivaosaona

Double limits capture the notion of limits in double categories. In ordinary category theory, a limit is the best way to construct new objects from a given collection of objects related in a certain way. Double limits, extend this idea to the richer structure of double categories. For each of the limits we can think of in an ordinary category, we can ask ourselves: how do these limits look in double categories?

In ordinary category theory, many results can be extended to double categories. For instance, in an ordinary category, we can determine if it has all limits (resp. finite limits) by checking if it has all products and equalizers (resp. binary products, a terminal object, and equalizers) (see Thm 5.1.26 in [3]). In a double category, we need to introduce a new notion of limit, known as a tabulator. One of the main theorems by Grandis and Paré states that a double category has all small double limits if and only if it has small double products, double equalizers, and tabulators. Therefore, these components are sufficient to construct small double limits. To explain this concept thoroughly, we will introduce their definitions in this post. There are various definitions depending on your focus, but for the sake of simplicity, this guide aims to be accessible to anyone with a background in category theory. For an introduction to double categories, see here.

We give an overview of how limits behave in this two-dimensional setting, following Grandis and Paré’s “Limits in double categories.” In particular, we make several definitions more explicit for use in further computations.

Introduction

Recall that double categories consist of two types of morphisms, horizontal and vertical, which interact in a compatible way. Often, composition of one arrow type is weaker than the other. Therefore, we may also think of limits in two different directions. However, limits with respect to the weaker class of morphisms tend to be badly behaved. Hence, in this post, we will only focus on horizontal double limits.

Throughout this article, we will refer to the class of morphisms with strong composition as “arrows,” written horizontally, with composition denoted by $\circ$. The weaker arrows will be called “proarrows,” written as vertical dashed arrows, and with composition denoted by $\bullet$. Identity arrows/proarrows for an object $X$ will be written $\mathbf{1}_X$ and $\mathbf{1}_X^\bullet$ respectively. Sometimes, we will also refer to the identity cell associated to an arrow $f:X \to Y$. This is obtained by taking both proarrow edges to be the respective vertical identities on objects:

There’s an analogous construction for proarrows, but we won’t need it in this article.

Double limits are defined for double diagrams and a double diagram is a double functor from an indexing double category $\mathbb{I}$ to an arbitrary double category $\mathbb{A}$. A limit for a given double diagram $D$ is a universal double cone over $D$. This is a very high-level definition, but we will try to explain each unfamiliar term and illustrate it with examples.

The first thing we need to understand is a double diagram for which we take the limits.

Diagrams

A double diagram in $\mathbb{A}$ of shape $\mathbb{I}$ is a double functor $F: \mathbb{I}\to \mathbb{A}$ between double categories $\mathbb{I}$ and $\mathbb{A}$. In strict double categories, a double functor is simultaneously a functor on the horizontal and vertical structures, preserving cells as well as their vertical compositions, horizontal compositions, identities. That is, for every cell $\alpha: u\to v$,

and for every composable pair of cells $\alpha: u\to v$ and $\beta: v\to w$

1. preserve horizontal compositions of cells: $F (\beta \circ \alpha) = F(\beta) \circ F(\alpha)$,

2. preserve vertical compositions of cells: $F (\gamma \bullet \alpha) = F(\gamma) \bullet F(\alpha)$,

3. preserve cell-wise horizontal identity: for each proarrow $u: A\nrightarrow B$, $F(1_u) = 1_{F u}$,

4. preserve cell-wise vertical identity: for each arrow $f: A\to A'$,\ $F(1^{\bullet}_f) = 1^{\bullet}_{F f}$,

We will also need the notion of a double natural transformation. These are defined componentwise, much in the same way as ordinary natural transformations. For double functors $F, G: \mathbb{I} \to \mathbb{A}$, a horizontal transformation $H: F \Rightarrow G$ is given by the following data:

• horizontal $\mathbb{A}$-arrows $Hi: Fi \to Gi$ for every object $i \in \mathbb{I}$

• an $\mathbb{A}$-cell $Hu$ for every proarrow $u:i \nrightarrow j$ in $\mathbb{I}$ of the shape

  ![[3.png]]

• Identities and composition are preserved.

• For every cell $\alpha \in \mathbb{I}$ with proarrow edges $u, v$ and arrow edges $f, g$, the component cells of $u$ and $v$ satisfy $(F\alpha | Hv) = (Hu|G\alpha)$

Vertical transformations satisfy analogous requirements with respect to vertical morphisms, given Section 1.4 of [1].

We will also use the notion of a modification to define double limits. Suppose we have double functors $F, F', G, G': \mathbb{I} \to \mathbb{A}$, horizontal transformations $H:F \Rightarrow G, K: F' \Rightarrow G'$ and vertical transformations $U:F \Rightarrow F', V: G \Rightarrow G'$. A modification is an assignment of an $\mathbb{A}$-cell $\mu i$ to each object $i \in \mathbb{I}$:

such that, for every horizontal $f:i \to j$, $(\mu i| Vf) = (Uf|\mu j)$:

Double limits will be defined as a universal double cone. But what are cones or double cones in double categories? You may ask.

Like ordinary categories, cones for a functor $F$ in double categories also consist of an object $X$ and morphisms from $X$ to the objects $Fi$, for each object $i$ of $\mathbb{I}$. Note that there two types of morphisms, those of horizontal direction or arrows and those of vertical direction or proarrows. The morphisms involved in cones are the horizontal ones but must be compatible with vertical ones. Let’s dive into the definition to see how that works.

A double cone for a double functor $F: \mathbb{I}\to \mathbb{A}$ consists of an $X$ with arrows $pi: X\to Fi$ for each object $i$ of $\mathbb{I}$, and cells $pu: \mathbf{1}^{\bullet}_X \to Fu$ for each every proarrow $u:i\nrightarrow j$, satisfying the following axioms:

1. for each object $i$ in $\mathbb{I}$, $$p(\mathbf{1}^{\bullet}_i)= \mathbf{1}^{\bullet}_{pi}$$

2. for each composable pair of proarrows $u$ and $v$ in $\mathbb{I}$, $$p(v\bullet u)=pv\bullet pu$$

3. for every cell $\alpha: u\to v$ in $\mathbb{I}$, $$(pu | F\alpha) = pv$$

Note that this implies that $Ff\circ p_i = p_j$ and $Fg\circ p_k = p_l$. We can observe that the cells $pu$ for every $u$ are made of two green arrows and $Fu$, which is indeed a cell such that the horizontal source of $pu$ is the identity proarrow $\mathbf{1}^{\bullet}_{X}$.

For example, let’s take cones for the functor $F$ from an indexing double category which is the discrete double category (made of only two objects $i$ and $j$), to an arbitrary double category, defined such that $Fi= A$ and $Fj= B$. Then, a double cone $X$ for $F$ is a candidate product for $A$ and $B$.

Notice that the above description of a double cone satisfies the requirements of a horizontal transformation. We can consider a constant functor $DA: \mathbb{I} \to \mathbb{A}$ at an object $A$ of $\mathbb{A}$, then the data of a double cone with vertex $A$ is determined by a horizontal transformation $x:DA \Rightarrow F$. The componentwise definition of $x$ unrolls to precisely the conditions specified above.

We have now all the setup needed for defining double limits, since as we mentioned above, double limits are universal double cones. That is, a double cone for an underlying functor $F$ through which any other double cones factor.

Double Limits

Limits

Let $F: \mathbb{I} \to \mathbb{A}$ be a double functor. The (horizontal) double limit of $F$ is a universal cone $(A,x)$ for $F$.

Explicitly, this requires several things:

• For any other double cone $(A', x')$, there exists a unique arrow $c:A' \to A$ in $\mathbb{A}$ with $x \circ Dc = x'$ (where $D$ is the constant functor at the vertex of $A$)

• Let $(A', x'), (A'', x'')$ be double cones with a proarrow $u: A' \nrightarrow A''$. For every collection of cell $\eta_i$ where $i$ is an object of $\mathbb{I}$, associated to components of each cone, which organize into a modification, there exists a unique $\mathbb{A}$-cell $\tau$ such that $(\tau | xi) = \eta_i$:

In other words, a cell built from a proarrow and the components of two cones (viewed as natural transformations) can be factored uniquely via $\tau$ and $1^\bullet$.

To get a better feel for double limits in practice, let’s examine (binary) products in a double category. Just as in 1-category theory, products are constructed as the double limit of the diagram $\bullet \ \bullet$ (two discrete objects). Spelling out the universal properties of a double limit, the (double) product of objects $A, B \in \mathbb{A}$ consists of an object $A \times B$ which satisfies the usual requirements for a product with respect to horizontal morphisms (with projection maps $\pi_A, \pi_B$. Additionally, given cells $\alpha, \beta$ as below:

there exists a unique cell $\alpha \times \beta$ such that

An identical condition must also hold for $B$ and $\pi_B$.

Equalizers can be extended to the double setting in a similar manner. Taking the double limit of the diagram $\bullet \rightrightarrows \bullet$ yields double equalizers. For horizontal $f,g: A \rightrightarrows B$ in $\mathbb{A}$, the double equalizer of $f$ and $g$ consists of an object $Eq(f,g)$ equipped with a horizontal arrow $e:Eq(f,g) \to A$, which is the equalizer of $f,g$ in the ordinary sense with respect to horizontal arrows. Additionally, for every cell $\eta$ with $(\eta | \mathbf{1}^\bullet_f) = (\eta | \mathbf{1}^\bullet_g)$, there exists a unique $\tau$ such that $(\tau | \mathbf{1}^\bullet) = \eta$:

Tabulators

Until now, we have considered examples of double limits of diagrams built from horizontal morphisms. Tabulators bring proarrows into the mix. They are an interesting case obtained as the limit over the diagram consisting of a single proarrow: $\bullet \nrightarrow \bullet$.

Suppose that $u:A \nrightarrow B$ is a proarrow. The tabulator of $u$ is the double limit of the diagram consisting of just $u$. Unrolling the limit, this amounts to an object $Tu$ along with a cell $\tau$:

such that, for any cell $\eta$ of the following shape,

there exists a unique horizontal morphism $f: C \to T$ such that $(1^\bullet_f | \tau) = \eta$:

Additionally, any proarrow $v: C \nrightarrow D$ with horizontal morphisms to $A$ and $B$ forming a tetrahedron can be uniquely factored through $Tu$:

In an ordinary category, the existence of all finite products and equalizers is enough to guarantee the existence of all limits. However, in the double setting, we need something extra: tabulators. The following result gives us a similar condition for limits in double categories.

Theorem (5.5 in [1]): A double category $\mathbb{A}$ has all small double limits if and only if it has small double products, equalizers, and tabulators.

Examples in $\mathbb{R}\text{elset}$

In this section, we consider the double category $\mathbb{R}\text{elset}$ of sets with functions as horizontal morphisms and relations as vertical morphisms, for more information see [1].

Tabulators

A tabulator for a proarrow or relation $R\subseteq A\times B$ is $R$ itself with the projection maps $p_1: R\to A$ and $p_2: R\to B$. For every other double cone $(C, q)= (C,q_1,q_2)$ of $R$, there exists a unique function or arrow $h= \langle q_1, q_2\rangle : C\to TR$ ($TR= R$), such that $q_i = p_i\circ h$; and for every relation $S\subseteq C\times D$ and such that $(D, t)= (D,t_1,t_2)$ is also a double cone for $R$, there exists a unique cell $\eta = (S R): S\to \mathbf{1}^{\bullet}_{R}$, such that $(\eta | pR) = q_1 \nrightarrow t_2$.

Product

The double product of two sets $A$ and $B$ is the cartesian product with the usual projection maps and we also have the following:

References

[1] Grandis, Marco, and Robert Paré. "Limits in double categories." Cahiers de topologie et géométrie différentielle catégoriques 40.3 (1999): 162-220.

[2] Patterson, Evan. “Products in double categories, revisited.” arXiv preprint arXiv:2401.08990 (2024).

[3] Leinster, Tom. “Basic category theory.” arXiv preprint arXiv:1612.09375 (2016).|

In Michael Sipser’s Introduction to the Theory of Computation textbook, he has one Platonically perfect homework exercise, so perfect that I can reconstruct it from memory despite not having opened the book for over a decade. It goes like this:

• Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.)

The correct answer is that yes, f is computable. Why? Because the constant 1 function is computable, and so is the constant 0 function, so if f is one or the other, then it’s computable.

If you’re still tempted to quibble, then consider the following parallel question:

• Let n equal 3 if God exists, or 5 if God does not exist. Is n prime?

The answer is again yes: even though n hasn’t been completely mathematically specified, it’s been specified enough for us to say that it’s prime (just like if we’d said, “n is an element of the set {3,5}; is n prime?”). Similarly, f has been specified enough for us to say that it’s computable.

The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers. Relatedly, and even more to the point: computability is about whether a computer program exists to map inputs to outputs in a specified way; it says nothing about how hard it might be to choose or find or write that program. Writing the program could even require settling God’s existence, for all the definition of computability cares.

Dozens of times in the past 25 years, I’ve gotten some variant on the following question, always with the air that I’m about to bowled over by its brilliance:

• Could the P versus NP question itself be NP-hard, and therefore impossible to solve?

Every time I get this one, I struggle to unpack the layers of misconceptions. But for starters: the concept of “NP-hard” applies to functions or languages, like 3SAT or Independent Set or Clique or whatnot, all of which take an input (a Boolean formula, a graph, etc) and produce a corresponding output. NP-hardness means that, if you had a polynomial-time algorithm to map the inputs to the outputs, then you could convert it via reductions into a polynomial-time algorithm for any language or function in the class NP.

P versus NP, by contrast, is an individual yes-or-no question. Its answer (for all we know) could be independent of the Zermelo-Fraenkel axioms of set theory, but there’s no sense in which the question could be uncomputable or NP-hard. Indeed, a fast program that correctly answers the P vs. NP question trivially exists:

• If P=NP, then the program prints “P=NP.”
• If P≠NP, then the program prints “P≠NP.”

In the comments of last week’s post on the breakthrough determination of Busy Beaver 5, I got several variants on the following question:

• What’s the smallest n for which the value of BB(n) is uncomputable? Could BB(6) already be uncomputable?

Once again, I explained that the Busy Beaver function is uncomputable, but the concept of computability doesn’t apply to individual integers like BB(6). Indeed, whichever integer k turns out to equal BB(6), the program “print k” clearly exists, and it clearly outputs that integer!

Again, we can ask for the smallest n such that the value of BB(n) is unprovable in ZF set theory (or some other system of axioms)—precisely the question that Adam Yedidia and I did ask in 2016 (the current record stands at n=745, improving my and Adam’s n=8000). But every specific integer is “computable”; it’s only the BB function as a whole that’s uncomputable.

Alas, in return for explaining this, I got more pushback, and even ridicule and abuse that I chose to leave in the moderation queue.

So, I’ve come to think of this as the Zombie Misconception of Theoretical Computer Science: this constant misapplication of concepts that were designed for infinite sequences and functions, to individual integers and open problems. (Or, relatedly: the constant conflation of the uncomputability of the halting problem with Gödel incompleteness. While they’re closely related, only Gödel lets you talk about individual statements rather than infinite families of statements, and only Turing-computability is absolute, rather than relative to a system of axioms.)

Anyway, I’m writing this post mostly just so that I have a place to link the next time this pedagogical zombie rises from its grave, muttering “UNCOMPUTABLE INTEGERRRRRRS….” But also so I can query my readers: what are your ideas for how to keep this zombie down?

In my role as a teacher and explainer of physics, I have found that the ambiguities and subtleties of language can easily create confusion. This is especially true when well-known English words are reused in scientific contexts, where they may or may not be quite appropriate.

The word “particle”, as used to describe “elementary particles” such as electrons and quarks and photons, is arguably one such word. It risks giving the wrong impression as to what electrons etc. are really like. For this reason, I sometimes replace “particle” with the word “wavicle”, a word from the 1920s that has been getting some traction again in recent years. [I used it in my recent book, where I also emphasized the problems of language in communicating science.]

In today’s post I want to contrast the concepts of particle, wave and wavicle. What characterizes each of these notions? Understanding the answer is crucial for anyone who wants to grasp the workings of our universe.

Why “Wavicle”?

What I like about the word “wavicle” is this.

• First, as a speaker of English or a related language, you may think you know what the word “particle” means. By contrast, you’re probably sure that you don’t know what “wavicle” means. And that’s a good thing! Since electrons’ and photons’ properties are quite unfamiliar, it’s better to bring as few preconceptions along as possible when one first seeks to understand them.
• Second, the word “wavicle” suggests that electrons and photons are more like waves than like dots. That’s true, and important, as we’ll see both today and in the next couple of posts.

Normally the word “particle” in English refers to a little ball or grain, such as a particle of sand or dust, and so an English speaker is imediately tempted to imagine an “elementary particle” as though it were roughly the same thing, only insanely small. But that’s not what electrons are like.

Wavicles are different from particles in several ways, but perhaps the most striking is this: The behavior and the energy of a wavicle are far more sensitive to the wavicle’s surroundings than would be the case for an ordinary particle. That is certainly true of electrons, photons and quarks. Let me show you what I mean.

Side Remark: Is the word “wavicle” really needed?

[An aside: Some might complain that the word “wavicle” is unnecessary. For example, one might propose to use “quantum particle” instead. I’m not convinced that’s any clearer. One could also just use the word “quantum”, the name that Einstein initially suggested. That potentially causes problems, because any vibration, not just waves, may be made from quanta. Well, terminology is always subject to debate; we can discuss this further in the comments if you like.]

A Stationary Particle in a Constrained Space

Let’s imagine a flat surface bounded by two walls a distance L apart, as in Fig. 1, and place a particle at point A, leaving it stationary. Since the particle is sitting on the ground and isn’t moving, it has the lowest energy it can possibly have.

Why does the particle have its lowest possible energy?

• It’s stationary. If it were to start to move, it would then have additional motion energy.
• It’s at the lowest possible point. If it were lifted up, it would have more energy stored: if it were then released, gravity would convert that stored energy to motion-energy.

How much energy does it have? It has only its internal energy E=mc², where m is the particle’s mass (specifically, its rest mass), and c is the cosmic speed limit, often called “the speed of light”.

Notice that the particle’s energy doesn’t depend on how far apart the walls are. If we doubled or halved the distance L between the walls, the particle wouldn’t care; it would still have the same energy.

The energy also doesn’t depend on the particle’s distance from the wall. If we placed the particle at point B instead, it would have the same energy. In fact there are an infinite number of places to put the particle that will all have this same, minimal amount of energy.

Such are the properties of a stationary particle. It has a location. It has an energy, which depends only on its local environment and not on, say, faraway walls.

Side Remark: Doesn’t gravity from the walls affect the particle and its energy?

Yes, it does, so my statements above are not exactly true. To be pedantic yet again: the walls have extremely tiny gravitational effects on the particle that do depend on the particle’s location and the distance L. But I have a more important point to make that is independent of these effects, so I’m going to ignore them.

Side Remark: Can all this about “lowest possible energy” really be true? Aren’t speed and energy perspective-dependent?

Total energy, like speed, is indeed a relative concept. So to be pedantically precise: the particle isn’t moving relative to us, and therefore, from our perspective, it has the lowest energy it can possibly have. That’s enough for today; we’ll be sticking with our own perspective throughout this post.

A Standing Wave in a Constrained Space

Waves, in contrast to tiny particles, are often exceedingly sensitive to their size and shape of their containers.

Although we often encounter waves that travel from place to place — ocean waves, earthquake waves, and light waves in empty space — there also stationary waves, known as standing waves, that don’t go anywhere. They stand still, just waving in place, going through a cycle of up-and-down-and-up-again over and over. A famous example of a standing wave would be that on a plucked string, sketched in Fig. 3.

The number of cycles performed by the wave each second is called its frequency. Crucially, if the string’s length is shortened, the frequency of the string’s vibration increases. (This is the principle behind playing guitars, violins, and similar instruments, which play higher musical notes, at higher frequencies, when their strings are made shorter.) In short, the standing wave on a string is sensitive to the length of the string.

More generally, a standing wave has several important properties:

• It has a frequency; the number of back-and-forth cycles per second. In general, if the wave’s container grows wider, the frequency decreases.
  
  
• It has a wavelength — the distance between highpoints on the wave — which will increase if the container widens. (I won’t discuss wavelength here, as it doesn’t play a role in what follows.)
  
  
• It has an amplitude (or “height”) — which describes how far the wave extends away from its midpoint during each cycle. Unlike frequency and wavelength, which are determined in part by the container’s size, the amplitude is independent of the container and is adjustable. For instance, for the string in Fig. 3, the amplitude (the vibrating string’s maximum extension in the vertical direction) depends on how firmly the string was plucked, not on the string’s length.

For instance, if we take the two walls of Fig. 1 a distance L apart, and we put a simple standing wave there, we will find that the frequency decreases with L, the wavelength increases with L, and the amplitude and energy depend on how “high” the wave is, which has nothing to do with L.

Unlike particles, waves have neither a definite location nor a determined energy.

• A standing wave has no definite location; it is inevitably spread out.
• A standing wave has an adjustable energy; if one increases or decreases the wave’s amplitude, its energy will similarly increase or decrease. (For instance, plucking a guitar string harder puts more energy into the vibration of the string, and leads to a standing wave with a larger amplitude and energy — one which will in turn create a louder sound.)

Particles, meanwhile, have neither frequency, amplitude nor wavelength.

A Standing Wavicle in a Constrained Space

Wavicles differ from both waves and particles. Like a wave, a wavicle is spread out, and can have a definite frequency, unlike a particle. But unlike a wave, a wavicle’s amplitude and energy are not adjustable, and so, like a particle, it can have a definite, fixed energy.

In particular, thanks to a formula that Max Planck guessed and Albert Einstein correctly reinterpreted, a wavicle’s energy and frequency are precisely proportional; if you know one, you know the other. The formula?

• E = f h

where E is the wavicle’s energy, f its frequency, and h is called Planck’s constant. (I sometimes refer to this constant as the cosmic certainty limit, in parallel to c being the cosmic speed limit; but that’s a personal quirk of mine.)

Photons, electrons and quarks are all wavicles, and they share many properties. There is, however, a crucial difference between them: the rest mass of a photon is zero, while that of an electron or quark is positive. This difference affects how their frequency and energy depend on L when they form standing waves in a box. (The differences between the standing waves for these two types of wavicles are shown in this article.)

Let’s look at photons first, and then at electrons.

Photon in a Box

If a photon is trapped in a box, forming a standing wave much like a standing wave on a guitar string, then the minimum frequency of that photon is set by the size of the box L and the cosmic speed limit:

• f = c / L

(Here I’m slightly over-simplifying; since the box is really three-dimensional, not one-dimensional as I’ve drawn it, the formula is slightly more elaborate. See below for the more complete math formulas if you want them.)

But the energy of the photon is also determined, because of the formula E = f h, which implies

• E = h c / L

Therefore, as L shrinks, E rises: the smaller the box, the larger the frequency and energy of the photon.

If the box’s size goes to infinity, the photon’s frequency and energy both go to zero. This reflects the fact that light on its own, isolated from other objects such as a box, cannot form a standing wave. In empty space, light and the photons that make it up are always traveling waves; they can only stand when inside a container.

Click here for more complete formulas for a photon in a box

A three-dimensional, the box has a length, width and height , and the photon’s frequency is



If the box is a cube with sides of equal length , then



The relation is still true, so

I claimed earlier that the energy of a wave is adjustable, while that of a wavicle is not. In this context, that means that the energy of a laser beam can be adjusted, but the energy of the individual photons that make up the laser beam cannot be. How does this work?

Let’s combine N photons of frequency f together. Then we get a wave of frequency f, with energy N times larger than that of a single photon.

• E = N f h

And thus, by adjusting N, making the wave’s amplitude larger, we can adjust the energy E if the wave. (How big might N be? HUGE. If you turn a laser pointer on for one second, the wave emitted by the pointer will typically have N somewhere in the range of a million billion or more.)

By contrast, a single photon corresponds to N = 1. Nothing else can be adjusted; if the photon has frequency f, its energy is fixed to be f h. That energy cannot be changed without also changing f.

Electron in a Box

An electron, unlike a photon, can be a standing wave (and thus stationary) even outside a box. This is a point I emphasized in this post, where I described a type of standing wave that can exist without walls, i.e., without a container.

Such an electron, sitting still and isolated out in empty space, has energy

• E = mc²

where m is the electron’s mass. But since it is a wavicle, E = f h; and so [as discussed further in the book, chapter 17] its frequency is

• f = E / h = m c² / h

Again, the idea that an electron has a frequency makes sense only because it is a wavicle; were it really a particle, we would be hard pressed to understand why it would have a frequency.

When the electron is placed inside a box of length L, its energy and frequency increase, just as is the case for a photon. However, whether the increase is large or small depends on whether the box is larger or smaller than a certain length, known as the electron’s Compton wavelength L_e . That length is

• L_e = h c / m = 2 x 10^-12 meters

This distance is much smaller than an atom but much larger than a proton or neutron; specifically, it is about a hundredth of the radius of an atom, and about a thousand times larger than the radius of a proton.

Much depends upon the relation between L and L_e.

• In a small box, where L is much less than L_e , the effect of the box on the electron’s frequency and energy can be very large. In particular, it can make E much bigger than mc² !!
• In a large box, where L is much greater than L_e, then E will be only slightly bigger than mc².

This behavior of the frequency (and thus the energy) of an electron, as a function of L, is shown in Fig. 5, along with the different behavior of the frequency for a photon. (These two types of behavior of frequency as a function of box size were also shown in this article.) We’ll come back to this in a later post, when we see how it is relevant for atoms.

Click here for the more complete formulas for an electron in a box

Compare the following with the complete formulas for a photon, given above. The electron’s frequency in a box whose sides have different lengths is



If the box is a cube whose sides have equal length , then



The relation is still true, so

Thus if , then is very slightly larger than , whereas if then , just as for a photon.

Something similar is true for the up and down quarks, and indeed for any “elementary particle” that has a non-zero rest mass. This has relevance for protons and neutrons, a point to be addressed in a later post.

One last point about electrons. If the box is huge — if L is much, much greater than L_e — then the electron can exist for a very long time as a localized standing wave, occupying only a small part of its box. This allows it to behave more like the particle in Fig. 1, tightly localized at a point, than like the wave of Fig. 4, which entirely fills the box. (Again, see this post on unfamiliar standing waves.) In that circumstance, the electron won’t have the lowest energy it can possibly have — to reach that low enerrgy would require filling the entire box — but its energy will still exceed mc² by only a minuscule amount.

This illustrates another crucial fact: wavicles with rest mass can sometimes be much more particle-like than wavicles without rest mass, with an approximate location as well as an almost definite energy. It’s another reason why scientists initially thought electrons were particles (in the usual sense of the word) and were slow to understand their wave-like properties.

A Comparison

To sum up, particles don’t have frequency, and waves don’t have their energy tied to their frequency; it’s having both frequency and specific associated energy that makes wavicles special. A key feature of a wavicle is that when you make it stationary and put it in a box, its frequency and energy generally increase; the smaller the box, the greater the effect. As seen in Fig. 5, the increase is particularly dramatic if the box is comparable to or smaller than the particle’s Compton wavelength.

To help you remember the differences, here’s a table summarizing the properties of these objects.

	stationary particle	standing wave	standing wavicle
location	definite	indefinite	indefinite
energy	definite, container-independent	adjustable	definite, fixed by frequency
frequency	none	container-dependent	container-dependent
amplitude	none	adjustable	fixed by frequency & container

The Old and New(er) Quantum Physics

Niels Bohr was one of the twentieth century’s greatest physicists and one of the founders of quantum physics. Back in the late 1920s and early 1930s, in his attempt to make sense of the confusions that quantum physics generated among the experts, he declared that electrons are both wave and particle — that depending upon context, sometimes one must view an electron as a wave, and sometimes one must view it as a particle. (This “wave-particle duality” lies at the heart of what came to be called the “Copenhagen interpretation of quantum physics.”)

But this was back in the days before quantum field theory, when quantum physics was very new. The quantum theory of the 1920s did indeed treat electrons as particles — with positions, yet described by a wave-function. It didn’t treat photons in the same way. It was only later, in the middle of the century, that quantum field theory came along. Quantum field theory put electrons and photons on exactly the same footing, treating both as wavicles, described by a single, overall wave-function. (Important! be sure not to confuse wavicles with the wave-function; they are completely different beasts!!)

This quantum field theory viewpoint didn’t really fit with Bohr’s vision. But it’s quantum field theory that agrees with experiment, not the quantum physics of Bohr’s era. Nevertheless, Bohr’s interpretation persisted (and still persists) in many textbooks and philosophy books. I learned about it myself at the age of sixteen in a class on the philosophy of science. That was several years before I learned the mathematics of quantum field theory and began to question Bohr’s thinking.

From the perspective of quantum field theory, as I’ve outlined here, a wavicle does have features of both waves and particles, but it also lacks features of both waves and particles. For this reason, I would personally prefer to say that it is neither one. I don’t think it’s useful to say that it is both wave and particle, or to say that it is sometimes wave and sometimes particle. It’s simply something else.

But this is something we could debate, and perhaps some readers will disagree with me. I’m happy to discuss this in the comments.

That said, however, I do want to emphasize strongly that using “wavicle” does not in any way help resolve the most confusing issues with quantum physics. Adopting “wavicle” does not make it any easier to understand, for instance, the quantum double slit experiment or the issue of entanglement’s “spooky action at a distance”. I do think quantum field theory has the advantage of removing certain unnecessary confusions, making it somewhat easier to state the problems of quantum physics. But this makes them no easier to resolve.

Such issues, however, are a topic for another time.

read more

guest post by Leonardo Luis Torres Villegas and Guillaume Sabbagh

Introduction

String diagrams are ubiquitous in applied category theory. They originate as a graphical notation for representing terms in monoidal categories and since their origins, they have been used not just as a tool for researchers to make reasoning easier but also to formalize and give algebraic semantics to previous graphical formalisms.

On the other hand, it is well known the relationship between simply typed lambda calculus and Cartesian Closed Categories(CCC) throughout Curry-Howard-Lambeck isomorphism. By adding the necessary notation for the extra structure of CCC, we could also represent terms of Cartesian Closed Categories using string diagrams. By mixing these two ideas, it is not crazy to think that if we represent terms of CCC with string diagrams, we should be able to represent computation using string diagrams. This is the goal of this blog, we will use string diagrams to represent simply-typed lambda calculus terms, and computation will be modeled by the idea of a sequence of rewriting steps of string diagrams (i.e. an operational semantics!).

Outline of this blog

Throughout this blog post, we will present many of the ideas in the paper “String Diagrams for lambda calculi and Functional Computation” by Dan R. Ghica and Fabio Zanasi from 2023. In the first section, we will recall the untyped lambda and simply typed lambda calculus. In the next section, we will review the basic concepts and notation of string diagrams for monoidal categories. Then, we will extend our graphical language with the necessary notation to represent terms in a Cartesian Closed Category. Finally, in the last section, we will present the operational semantics for lambda calculus based on string diagrams and study a case example of arithmetics operations and recursion.

Lambda calculus quick quick crash course

We will start by reviewing one of the first and more “simple” models of computation: The lambda calculus. The lambda calculus was originally developed by Alonzo Church when he was studying problems on the foundations of mathematics. Alan Turing proposed almost simultaneously its famous model of computation based on an abstract machine that moves along an infinite tape. The lambda calculus is equivalent to Turing’s model. If we would like to have an intuition about the difference between the two models we would say that the lambda calculus is closer to the idea of software while Turing machines are closer to hardware. The lambda calculus has had a huge influence and applications to different areas of Computer science, logic, and mathematics. In particular to functional programming languages, as lambda calculus provides the foundational theoretical framework upon which functional programming languages are built.

Lambda-calculus is based on a rewrite system. Every term in lambda calculus is morally a function, you can apply functions and abstract functions.

More precisely, a lambda term is defined inductively as follows:

• A variable $x,y,z, \cdots$ is a lambda term;
• Given two lambda terms $f$ and $x$, $(fx)$ is a lambda term representing the application of $f$ to $x$;
• Given a variable $x$ and a lambda term $t$, $(\lambda x. t)$ is a lambda term representing the function taking an $x$ as input and returning $t$ where $x$ is a bound variable in $t$, this is called an abstraction.

Function application is left-associative by convention.

Three reductions are usually defined on lambda terms, $\alpha$-conversion allows to change bound variables names to avoid naming conflicts, $\beta$-reduction apply a function to its argument by replacing the bound variable with the argument, and $\eta$-reduction which identifies two functions if they give the same output for every input.

We will focus on $\beta$-reduction as we don’t aim for a super formal approach, and $\alpha$-conversion can be avoided in different ways (using De Bruijn index notation, for instance). $\beta$-reduction is confluent when working up to $\alpha$-conversion, so that is what we are going to assume throughout this blog.

How to represent simple data types in untyped lambda calculus? Since in untyped lambda calculus everything is a function, the idea is to encode simple data types using only functions in a consistent way. For instance, we can define booleans in the following manner: $True$ := $(\lambda x. \lambda y. x)$ and $False$ := $(\lambda x. \lambda y. y)$.

The idea is that a boolean is meant to be used in a if-then-else statement, let $T$ be the ‘then’ expression and $E$ be the ‘else’ expression, the if-then-else statement can be expressed with $BTE$ where $B$ is a boolean. Indeed, if $B = True$ then we have $TrueTE$ which is equal by definition to $(\lambda x. \lambda y. x)TE$ which reduces to $T$. If $B = False$, then $FalseTE = (\lambda x. \lambda y. y)TE$ yields $E$ after two $\beta$-reduction.

Logical connectors ‘and’, ‘or’, ‘implies’, ‘not’, can be implemented using if-then-else statements, for example $and := (\lambda B1. \lambda B2. B1 B2 False)$ which reads if $B1$ is true then return $B2$ else return $False$.

We can also represent natural numbers by successive application of a function, these are the Church numerals:

• 0 := $(\lambda f. \lambda x. x)$ a function which applies $f$ 0 time;
• 1 := $(\lambda f. \lambda x. f x)$ a function which applies $f$ 1 time;
• 2 := $(\lambda f. \lambda x. f (f x))$ a function which applies $f$ 2 times;
• $n+1$ := $(\lambda f. \lambda x. f (n f x))$ recursively, the successor of a number $n$ applies $f$ one more time to $x$ than $n$.

We can define usual functions on numbers:

• $succ$ := $(\lambda n.(\lambda f. \lambda x. f (n f x)))$
• + := $(\lambda n. \lambda m. \lambda f. \lambda x. m f (n f x))$
• * := $(\lambda n. \lambda m. \lambda f. \lambda x. m (n f) x)$ and so on

What we described above is untyped lambda calculus, but it lacks certain properties due to its computability power. For example, it allows paradoxes such as Kleene-Rosser paradox and Curry’s paradox. To have a better rewriting system, Alonzo Church introduced simply typed lambda calculus.

The idea is to give a type to variables to prevent self application of function. To this end, we consider a typing environment $\Gamma$ and typing rules:

• $\frac{x:t \in \Gamma}{\Gamma \vdash x : t}$ This means that a typing assumption in the typing environment should be in the typing relation;

• $\frac{\text{c is a constant of type t}}{\Gamma \vdash c : t}$ This means that terms constant have appropriate base types (e.g. 5 is an integer);

• $\frac{\Gamma, x:t_1 \vdash y:t_2}{\Gamma \vdash (\lambda x:t_1 . y) : (t_1 \to t_2)}$ This means that if $y$ is of type $t_2$ when $x$ is of type $t_1$, then the $\lambda$ abstraction $(\lambda x:t_1. y)$ is of the function type $(t_1 \to t_2)$;

• $\frac{\Gamma \vdash x : t_1 \to t_2 \quad \Gamma \vdash y : t_1}{\Gamma \vdash (xy) : t_2}$ This means that when you apply a function of type $t_1 \to t_2$ to an argument of type $t_1$ it gives a result of type $t_2$.

When writing $\lambda$ terms, we now have to specify the type of the variables we introduce. The examples above now become:

• 0 := $(\lambda f : t \to t. \lambda x : t. x)$
• 1 := $(\lambda f : t \to t . \lambda x : t. f x$
• 2 := $(\lambda f : t \to t . \lambda x : t. f (f x)$
• $succ$:= $(\lambda n : (t \to t) \to (t \to t) .(\lambda f : t \to t . \lambda x : t. f (n f x)))$
• + := $(\lambda (t \to t) \to (t \to t). \lambda (t \to t) \to (t \to t). \lambda f : t \to t. \lambda x : t. m f (n f x))$
• * := $(\lambda n : (t \to t) \to (t \to t). \lambda m : (t \to t) \to (t \to t). \lambda f : t \to t. \lambda x : t. m (n f) x)$

Crucially, we can no longer apply a function to itself: let’s suppose $x$ has type $t_1$, then $xx$ would mean that $x$ must be a function taking $t_1$ as an argument, so $t_1 \to t_2$, but it now means that $x$ should take an argument of type $t_1 \to t_2$ so $x$ would be of type $(t_1 \to t_2) \to t_3$ and so on which is impossible.

Because we can no longer apply a function to itself, simply typed $\lambda$ calculus is no longer Turing complete and every program eventually halts. It is therefore less powerful but has nicer properties than untyped $\lambda$ calculus. From now on, we will work with simply typed $\lambda$ calculus not just because of its rewrite properties but also because of its strong connections with category theory.

Everything we have explained in a very hurried and informal manner in this section, can be fully formalized and treated with mathematical rigor. The objective of this section is to ensure that those not familiar with lambda calculus do not find it an impediment to continue reading. If the reader wishes to delve deeper or see a more formal treatment of what has been explained and defined in this section, they can refer to “Lambda calculus and combinator: an introduction” by Hindley and Seldin for a classical and treatment or to “Introduction to Higher order categorical logic” by Lambek and Scott for a more categorical approach.

String diagrams

String diagrams for monoidal categories

Why use symmetric monoidal categories? Monoidal categories arise all the time in mathematics and are one of the most studied structures in category theory. In the more applied context, a monoidal category is a suitable algebraic structure if we want to express processes with multiple inputs and multiple outputs.

String diagrams are nice representations of terms in a symmetric monoidal category which exploits our visual pattern recognition of a multigraph’s topology to our advantage.

As a quick reminder, a monoidal category is a sextuplet $(\mathcal{C}, \otimes : \mathcal{C} \times \mathcal{C} \to \mathcal{C}, I, \alpha : (- \otimes -) \otimes - \implies - \otimes (- \otimes -), \lambda : (I \otimes -) \implies -, \rho : (- \otimes I) \implies -)$ where:

• $\mathcal{C}$ is a category;
• $\otimes$ is a bifunctor called a tensor product;
• $I$ an object called the unit;
• $\alpha$ is a natural isomorphism called the associator;
• $\lambda, \rho$ are natural isomorphisms called respectively the left and right unitor;

such that the triangle and the pentagon diagrams commute:

A strict monoidal category is a monoidal category where the associator and the unitors are identities, every monoidal category is equivalent to a strict one so we may use strict monoidal categories from now on.

With string diagrams, the objects of the category are represented as labelled wires, the morphisms as named boxes and the composition of two morphisms is the horizontal concatenation of string diagrams and the tensor product of two objects/morphisms the vertical juxtaposition:

We already see the usefulness of string diagrams when seeing the interchange law. The interchange law states that $(\forall f,g,h,i \in Ar(\mathcal{C}))\quad (f;g) \otimes (h;i) = (f \otimes h) ; (g \otimes i)$.

It becomes trivial when seen as a string diagram:

A symmetric monoidal category is a monoidal category equipped with a natural isomorphism $\sigma$ called a braiding such that $\sigma_{A,B} ; \sigma_{B,A} = Id_{A \otimes B}$. We will represent the braiding morphisms are as follows:

Again the topology of the string diagram’s underlying multigraph reflects the properties of the braiding when the monoidal category is symmetric.

To put it in a nutshell, string diagrams are great visualization tools to represent morphisms in a symmetric monoidal category because they exploit our visual pattern recognition of the topology of a graph: we intuitively understand how wiring boxes work.

Functors boxes

So far, we have reviewed the standard notation for string diagrams on monoidal categories. Now we will introduce how to represent functors in our graphical language.

Let $\mathcal{C}$ and $\mathcal{D}$ be two categories. And let $F: \mathcal{C} \to \mathcal{D}$ be a functor between them. Then the functor F applied to a morphism f is represented as an F-labelled box:

Intuitively, the box acts as a kind of boundary. What it is inside the functor box (wires and boxes) lives in $\mathcal{C}$, while the outside lives in $\mathcal{D}$.

As an example, the composition law of functors would look like this using the above notation:

Adjoint and abstraction

One of the categorical constructions we will use the most throughout this blog is adjunctions, so we would like to represent them in our graphical notation. In particular, we will make use of the unit/counit definition. The reason for doing this, is, first because the unit and counit of the particular adjunction pair that we are interested in will play an important role, and second because the unit/counit presentation is arguably the best when using string diagrams.

What should we add to represent adjunctions in our graphical notation? Well… nothing! We already have a notation for functors. Natural transformations, from the point of view of string diagrams, are just collections of morphisms, so the components of a natural transformation are represented as boxes, just like any other morphism in the category. However, since the unit and counit will play a fundamental role, it will be convenient for us to have a special notation for both.

We will represent the unit as a right-pointing half-circle with the object components in the middle. For the counit, it is analogous but points to the left.

Now the equations look like this:

The particular pair of adjoints that we are interested in is the pair consisting of the tensor product functor $F_X (A) = A \otimes X:\mathcal{C} \to \mathcal{C}$ and its right adjoint $G_X(A)$ which we write as $X \multimap A$, where $\mathcal{C}$ is a monoidal category. This adjunction is also usually written as $- \otimes X \vdash X \multimap -$

When the functor $- \otimes B : \mathcal{C} \to \mathcal{C}$ has a right adjoint $B \multimap - : \mathcal{C} \to \mathcal{C}$ we say that $\mathcal{C}$ is a closed monoidal category.

The importance of this pair of adjoints lies in their counit and unit, which allow us to represent the idea of application and abstraction, that one we presented in the previous section, respectively.

The first one makes total sense because if we analyze the form of the counit, we will discover that it perfectly matches the function application form: $$\epsilon_A: F( G A) \to A$$

$$\epsilon_A: (X \multimap A) \otimes X \to A$$

On the other hand, the counit has the following form:

$$\eta_A : A \to G (F A)$$

$$\eta_A : A \to X \multimap (A \otimes X)$$

If we mix the counit with the $X \multimap -$ functor we can do abstraction of morphisms and currying (note that abstraction is currying with the unit: $(I \otimes A \to B) \mapsto (I \to (A \multimap B))$). So for any morphism $f: X \otimes A \to Y$ we will denote its abstraction as $\Lambda_X(f): A \to X \multimap Y$

We will use this construction a lot so we will use a syntactic sugar to denote it in our graphical formalism.

Notice that this syntactic sugar is quite suggestive since the hanging wire gives us the idea of a quantified variable waiting to be used, but it is important to note that this is just a graphical convention.

Another usual notation is the clasp of the Rosetta Stone paper by Baez and Stay:

Now Cartesian

We finish this section with the last ingredient necessary to represent graphically the terms of a Cartesian Closed Category, which is the product object. The motivation for having this construction is that, in our simple programming language, we would like to be able to represent functions that take more than one parameter. Similarly, it would be useful to have the ability to duplicate the output of a function or discard it (yes, this is no quantum computing!), which is directly related to the previous point.

With this in mind, we introduce two natural transformations $\delta_A: A \to A \otimes A$ and $\omega_A: A \to I$, which we call copy and delete, respectively. Before giving the equations necessary to call a category $\mathcal{C}$ “cartesian”, as we mentioned before, these natural transformations represent the ideas of duplicating and discarding the output of a function.

Since these two constructions will play a fundamental role in our task of representing functional programs, we will give them a special syntax:

And as we ask them to be natural, the naturality condition looks like this:

So finally, we will say that a symmetric monoidal tensor is a Cartesian product if, for each object $A$ in the category, the above-mentioned monoidal transformations $\delta_A$ and $\omega_A$ exist such that:

Note how we are expressing the properties directly using string diagrams! Just in case you’d like to see how these properties look in classical notation, here they are:

$$\omega_{A \otimes B} =\omega_A \otimes \omega_B$$

$$\delta_{A \otimes B} = \delta_A \otimes \delta_B; id_A \otimes \sigma_{A,B} \otimes id_B$$

$$\delta; id \otimes \omega = \delta; \omega \otimes id = id$$