A remarkable computation

Today I watched, on Natalia Maslova’s on-line seminar from Yekaterinburg, a talk by Sergey Shpectorov from Birmingham, on the non-existence of a strongly regular graph with parameters (84,14,3,2): this is a graph with 84 vertices, regular with valency 14, and with two vertices having three or two neighbours according as whether they are adjacent or not.

What was remarkable about the proof is the hugeness of the computation involved: Sergey used 96 cores at the University of Birmingham for well over a year to get the result. This is not how I prefer to prove theorems, but I take off my hat to Sergey for having done it!

The strategy was to analyse the trillions of configurations for a 30-vertex subgraph consisting of the neighbourhood of a maximal clique of size 3, to decide whether the image under projection onto one of the eigenspaces of the adjacency matrix is positive semidefinite (as it must be if the graph exists). This eliminated all possibilities except a very small number (in double figures) which required further analysis.

A lot of clever trickery went into the proof; some of it, I admit, I didn’t really understand. But an impressive piece of work anyway.

In a way I was reminded of something that happened during the classification of finite simple groups. Charles Sims was reported to have said, at some point, that if he were given a million dollars, he could construct the Lyons group. In the end he constructed it much more cheaply than that!

Posted in exposition | Tagged , | Leave a comment

The Universe according to Leibniz?

I have just been reading Lee Smolin’s recent book Einstein’s Unfinished Revolution.

My sources for what is going on deep in theoretical physics are Carlo Rovelli (whom I met at How the Light Gets In some years ago), Lee Smolin, and for a different angle Rob Wilson, my former colleague who tends to snipe at physicists for misunderstanding group theory. I really enjoyed a couple of Smolin’s earlier books (Three Roads to Quantum Gravity and The Trouble with Physics), but I have found his more recent books less satisfactory.

In the present book, he explains attempts to go beyond quantum mechanics to produce a theory to satisfy someone like himself who, in philosophical terms, is a realist. I must admit that I don’t really understand that term.

In brief, according to Smolin, quantum mechanics has two rules. Rule 1 says that the wave function evolves in a purely deterministic way, as determined by Schrödinger’s equation; Rule 2 says that something quite different happens when we make a measurement on the system: the wave function instantly changes into an eigenfunction of an operator associated with the quantity we are measuring, and the result of the measurement is the corresponding eigenvalue. Now apparently a realist can accept Rule 1 but not Rule 2; and there are problems, since Rule 1 is time-symmetric whereas the Universe appears not to be.

Smolin begins by tantalising us with the promise of a workable, fullly realist proposal towards the end of the book. But most of the book is taken up with various realist alternatives which have been proposed, most notably pilot wave theory by de Broglie and Bohm, and Everett’s Many Worlds theory. Pilot wave theory proposes that both the particle and the wave are real; the wave satisfies Rule 1, and the particle moves on a trajectory determined by the wave (maybe “steepest ascent”). Aside from other drawbacks, this violates Newton’s third law; the wave affects the particle but the particle has no effect on the wave. Strikingly, when two particles collide, they don’t actually collide at all, but pass through one another without noticing; the waves interact according to the rules of quantum mechanics and then carry the particles with them.

According to Everett’s theory, every time an event occurs with more than one possible outcome, the universe splits into many universes, each of which realises one of the outcomes. I am not sure how this claims to be a realist theory, given the amount of science fiction this idea has powered; but it has other drawbacks too, for example all these universes “really” exist, there are no probabilities in the theory.

Smolin discusses the many attempted fixes for these and other theories, and concludes that none of them are really satisfactory.

Eventually we get his own theory, which he claims is based on ideas due to Leibniz. The Universe is made of atoms called “nads” (so-called because they share some of the properties of Leibniz’s monads), which satisfy various relations. It is not made entirely clear whether these are all binary relations; I will assume so for simplicity. So the Universe is a huge network.

Now a feature of such discrete models is that we have the possibility that space will arise as am emergent property: if we look at the network from so far away that we can’t see details of the nads, it should look like a manifold. The problem is that nobody has yet devised a satisfactory model in which the three dimensions of space arise naturally in this way. (We can do it synthetically, by starting with the desired manifold and sprinkling nads from a “nad sprinkler”, a Poisson process; but that is cheating.) So when later Smolin claims that he can derive the Schrödinger equation in one of his models, it seems to me that there is an unexplained gap.

The two principles he takes from Leibniz are, first, that two objects with identical properties are equal, and second, that our world is the best of all possible worlds.

The first principle is fine in set theory: two sets which contain the same elements are equal. But nads, unlike sets, have no internal structure, and are defined solely by their relations with the other nads. So this principle forbids “twin nads”. Smolin extends this by saying that a nad has a “view” of the universe, consisting of its neighbours out to some specified distance in the network, without telling us what this specified distance is. Now two nads are close together if their views are very similar (they can’t be identical, by the first principle). This explains the phenomenon of non-locality: two nads can be close in this sense, and so influence one another, even if they are far apart in the actual universe (like entangled particles in quantum mechanics which have moved apart).

There is a problem here. Two nads are identical if they have identical views of the Universe, in other words, the things they can see are identical. But there is a vicious circle there. Smolin claims that his principle implies that the network has no symmetry, because two nads related by a symmetry would be identical. But I don’t get this.

The second, Panglossian principle asserts that there is a function, called “perfection”, and the law governing the Universe is that it changes so as to maximise “perfection”. He identifies “perfection” with action (or, strictly, its negative), and so comes close to one of the standard formulations of mechanics, the Principle of Least Action.

However, there is a difficulty for those, like me, who think of symmetry as a kind of perfection. I can’t now remember who suggested to me that homogeneous structures such as the countable random graph have maximum symmetry: any two finite subsets with identical internal structure are equivalent under a global symmetry. (The fact that the random graph is homogeneous can be expressed by the Leibnizian statement “The best of all possible worlds is also the most probable”.) So a universe without symmetry seems to me to be not as nice as one with a lot of symmetry. This may just be a personal prejudice; but perhaps, as I argued above, the proof of “no symmetry” is not valid, and the Universe could have symmetry after all.

Never mind; it is fun to speculate, and I did enjoy the book.

Posted in exposition, Uncategorized | Tagged , , , , | 3 Comments

New diamond journal

Welcome to a new diamond open access journal, JoNAS (the Journal of Non-Associative Structures).

From the web page:

JoNAS, the Journal of Non-Associative Structures, is a diamond open-access, electronic, international research journal that publishes research and survey articles in mathematics since 2026. It is dedicated to publishing high-quality original research articles in non-associative algebra and its applications to geometry, combinatorics, mathematical analysis, mathematical physics, and other areas of pure and applied mathematics. The journal does not charge author processing fees of any sort, and all published articles are available for free.

This led me to wonder about the term “non-associative”, which could have two possible meanings: not necessarily associative, or definitely not associative. In terms of things that are much studied, there seem three different cases:

  • Non-associative except in very degenerate special cases, such as Lie algebras.
  • Mostly non-associative, but associative in some very interesting special cases, such as loops. (Though only an extremist would consider group theory to be a subdiscipline of loop theory!)
  • Mostly associative, but non-associative in some very interesting special cases. Stretching the meaning a bit, I would put Jordan algebras here. Most of them are built from associative algebras using the Jordan product, but there are exceptional Jordan algebras.

I am guessing that they would welcome papers on Jordan algebras but not hard-core group theory.

Posted in Uncategorized | Tagged , , , , | 2 Comments

Another misunderstood song?

Another Bob Dylan song. Apologies, I will get back to mathematics soon, I promise …

I stumbled on the wikipedia page for “Desolation Row” recently, and was surprised to learn how many people had identified it with a particular street in a particular (usually North American) town. Even Dylan himself played this game, though of course he was well known for winding up the press. People talk as if Desolation Row is a street where all these bizarre things happen. But that is not it.

To unpick this, let’s turn back to a similar song on Dylan’s previous album, “Gates of Eden”. It is clear, even from the title, that inside the Gates of Eden is a kind of nirvana-like place (if that makes any sense) where there are no kings(!), no trials, no sins, reality doesn’t matter; but outside the Gates of Eden, there are no truths. (I suppose all is fake news.) All the bizarre action of the song takes place outside the Gates.

Now I contend that the same is true of Desolation Row. The first stanza makes clear that the singer and his lady are looking out from Desolation Row and watching the things to be described. Moreover, Ophelia, whose profession is her lifeless religion, spends her time peeking in; Einstein used to play electric violin there but now is a drainpipe-sniffing bum outside; you have to lean a long way out to hear the piping of Dr Filth’s sinister medical practice; and so on. People try to escape to Desolation Row, but insurance agents are directed to stop them, and if they succeed, they are punished. (You have to face reality, yes?) We learn that the Good Samaritan is going to a carnival on Desolation Row, but never find out whether he gets there.

Having two songs with such similar messages makes one inevitably look for a third to complete the trilogy. I used to think that the third is “Visions of Johanna”, where the immaterial visions play the role of the paradise safe from the outside world. (Johanna herself never puts in an appearance.) This is likely true, but there is a much later song, “Blind Willie McTell”, where Willie McTell’s blues songs seem to play the same role, insulating you from the chain gangs and bootleggers of reality. Perhaps he is accompanied by Einstein on violin?

Two final notes. First, I didn’t realise that the first line of the song is based on a real, dark incident in American history, where three black men where lynched by a mob of thousands in Duluth and hanged before they could be tried, and postcards were produced to commemorate the event.

Second, in my opinion, another Dylan song misrepresented by those who only hear the title is “Dear Landlord”; but I won’t go on to that now.

Posted in Uncategorized | Tagged , , , , | Leave a comment

Old year thoughts

Sorry for a self-indulgent post. My daughter turns 50 today. And if it is a milestone for her, it is one for me as well.

Indeed, it has been a year of milestones: two grandchildren became legally adult this year; and of course I retired. After quite a stressful time, I have kept my office and access to the library and network, but lost funding for gold open access. My last PhD student submitted his thesis last month.

Next year, if I am spared, I will pass the age at which my father died.

Of course, in other ways, things continued as usual: the ADE book was published, and the Shrikhande graph book is in press; I continue to accumumuulate co-authors (though I am slowing down enough that I cannot keep up with all of them all the time); and I can continue to do mathematics (and talk about some of it here) and publish in diamond open-access journals.

So on to whatever comes next!

Posted in Uncategorized | Leave a comment

Hard rain

The older I get, the more I think that “A hard rain’s a-gonna fall” is one of the greatest songs ever written.

Bob Dylan has said that he wrote it in 1962, at the time of the Cuban missile crisis, when it seemed that we were on a knife-edge and mightn’t wake up in the morning. So people who haven’t really listened to it think that the hard rain is a rain of bombs, or perhaps a nuclear winter. Perhaps ten thousand miles in the mouth of a graveyard reinforces this view.

But it is a lot more to it, and much of what it says is coming to pass.

Moreover, it is not complicated stuff that needs to be interpreted. The message is very simple. Let me give a few examples.

  • hard rain, a black branch: floods and fires in many different parts of the world.
  • sad forests, dead oceans, the pellets of poison are flooding their waters: we’ve seen the effects of acid rain, and of plastics, chemicals and human excrement in our rivers and seas.
  • ten thousand talkers whose tongues were all broken: tyrants of every stripe imprison and torture those who disagree with them.
  • guns and sharp swords in the hands of young children: think of the child soldiers in wars in east Africa, or the American school shootings.
  • the roar of a wave that could drown the whole world: the Indian Ocean tsunami of 2004 was a hint about this.
  • a white man who walked a black dog: remember the pictures from Abu Ghraib after the invasion of Iraq.
  • I met one man who was wounded in hatred: enough said; do we have enough sympathy for all the victims?
  • the people are many and their hands are all empty: clear enough, I think.
  • reflect on the mountains so all souls can see it: the mountains show us very clearly what’s happening, with the shrinking glaciers and disappearing snow caps.
  • I’ll stand on the ocean until I start sinking: this line makes me think of the picture of a polar bear on a totally inadequate ice floe which will surely melt under it soon.

It is not quite all doom and gloom: a highway of diamonds, I met a young girl who gave me a rainbow. But the predictions are all there. It is surely clear by now that pumping more oil, or shooting people who are slightly different from us, will not make us happy and prosperous.

Posted in Uncategorized | Tagged , , , , , | 3 Comments

Ramsey, Fraïssé, and orders

In the 1980s, Jarik Nešetřil investigated Ramsey classes: these are classes of structures over a fixed relational language satisfying the condition that, for any structures A,B, there exists C such that, if the embeddings AC are coloured red and blue, there is an embedding BC such that the embeddings of A into the image of the embedding of B are monochromatic. (This generalises the classical Ramsey theorem.)

Among his discoveries was the fact that the structures in a nontrivial Ramsey class form a Fraïssé class (and so have a countable homogeneous Fraïssé limit), and are rigid (they have trivial automorphism group).

This was subsequently explained by the celebrated theorem of Kechris, Pestov and Todorčević, which uses topological dynamics (specifically, the automorphism group of the Fraïssé limit is extremely amenable) to show that this group has a total order as a reduct, and hence the structures in the class are totally ordered (and hence rigid).

Early in this story, I observed that there exist Fraïssé classes of rigid structures which have no “natural” total order, and wondered whether they could be Ramsey classes, and (after the KPT theorem showed that they were not) whether one could find explicit failures of the Ramsey property.

Siavash Lashkarighouchani and I have just done this. The paper is on the arXiv, at 2512.05684.

Posted in exposition, mathematics | Tagged , , , , , | Leave a comment

GitHub

GitHub saved my bacon a couple of years ago when the University decided to close down personal web pages. At a colleague’s suggestion, I moved everything to GitHub, and there it has stayed since.

At that time I just dumped everything there. Now I have decided that I should put a bit of order into the chaos. In the process, I have discovered that GitHub is one of the worst pieces of software I have ever had to use. I just note some “features”:

  1. There is no manual, and no online help. This is compounded by the cryptic names given to the commands, of which “Commit” for “Save” is one of the mildest. So later on, when I say “X is not possible”, you should read it as “I can’t find out how to do X, see Point 1”.
  2. You can move a file down, into a subfolder (bizarrely, this is done by editing the file, even if it is a binary file which can’t be edited); but you can’t move it up or sideways.
  3. You can upload something, but you can’t download. There is a glitch here too: you can upload a folder by dragging it into a window, but not by selecting it.
  4. If you make a mistake, as I did (I accidentally deleted my entire talks directory) you can, by clicking everything clickable until something you want happens, get back to the situation before you deleted it; but you can’t tell GitHub to reset this as the current version. I had a very stressful couple of hours trying to figure out how to do that, and didn’t succeed.
  5. And on top of this, there is the very annoying three minute wait after every change. It doesn’t tell you when it has finished doing what it does. And sometimes this is crucial, and not waiting is disastrous; sometimes it gives you a stern warning “Run Cancelled” but in fact everything is fine; and sometimes it seems not to be necessary to wait at all.

Later I remembered that GitHub is owned by Microsoft, and all became clear.

My web pages exist because I have a possibly exaggerated belief that some people find them useful. But if they ever start charging for GitHub, I will probably decide that I am not going to pay to use that rubbish, and pull the plug on it.

Posted in the Web | Tagged , , | 7 Comments

Manifesto

Here is a preliminary version of something I am intending to put on my web page soon. Comments welcome!

“You are old, Father William,” the young man said,
“And your brain has become very slow;
Yet the purpose of life is conjecture and proof –
Pray how will you put stuff on show?”

(after Lewis Carroll and Paul Erdős)

A large part of the pleasure of mathematics research is communicating it to others, either verbally or by writing interesting papers. This is why I believe in open-access publication.

Unfortunately, now I am retired, I no longer have access to funds to pay the expensive page charges for gold open access in commercial journals. Moreover, “green open access” is not open access at all, but just weasel words of bureaucrats under pressure from big publishers. (At a minimum, open access should mean that the digital object identifier for a paper should lead you to a freely available version of the paper.)

So from now, my protocol for my own papers will be, first to put them on the arXiv, where they are freely available to all; and then, if I want them published, to submit them to one of the growing number of good diamond open-access journals (free to authors and readers).

How does this affect you, other than hopefully making it easier for you to read the papers?

  • If you are my coauthor (actual or potential), I will probably suggest publication in a diamond journal. Maybe you have reasons not to publish in such a place: perhaps those who assess your research are prejudiced against diamond journals. In that case, if you have access to funds for APC, I will ask you to be corresponding author; if not, if you insist, then we will have to forgo proper open access and use the so-called “green route”.
  • If you are an editor of a commercial OA or hybrid journal, and you want me to submit a paper to your journal, unless you give me a waiver for the APC I will not even consider it. Moreover, I will be reluctant to referee papers for a journal in which I cannot publish myself.

However, circumstances alter cases, and I am not making an irrevocable commitment. For an issue of a journal celebrating a friend of mine, I would certainly try to find alternative arrangements, even considering the “green” route if necessary. And I am not asking anyone else to make a commitment either. But if you approve of my decision, let me know; and if you are in my position, you might even adopt a similar manifesto. I think it is important to let the community know how we feel!

A list of diamond mathematics journals is here. Let me know if there is a better list somewhere!

Posted in publishing | Tagged , | 1 Comment

Why transformation monoids are harder than permutation groups

For permutation groups (or transformation monoids), we don’t need to assume the associative law, since composition of functions is always associative. So a permtation group is a set of mappings satisfying the identity, inverse and closure axioms. This implies that its orbit structure (given by the relation “lie in the same orbit”) is reflexive, symmetric, and transitive. You get from x to x by the identity; if you can get from x to y, then you can get back again by the inverse; and if you can get from x to y and from y to z, then you can get from x to z by composition.

Now a reflexive, symmetric and transitive relation is an equivalence relation, and its job is simple: it partitions the domain into equivalence classes, which are the orbits of the group. There is the first structure theorem for group actions.

Around the 1960s, various people took this further. How do we describe the action of a group on the ordered pairs of elements of its domain? I will use the terminology that Donald Higman brought in then. The set of ordered pairs is, of course, partitioned into orbits. The set of orbits has three further properties: the diagonal is a union of orbits; the set of orbits is closed under transposition; and there is a counting condition, asserting that given three orbits Oi, Oj, Ok, and a pair (x,y) in the third orbit, the number of points z for which (x,z) lies in the first orbit and z,y in the second depends only on i,j,k and not on the choice of x and y. This leads to the possibility of using algebraic and combinatorial methods in the study, which Higman and others did very successfully.

The orbits of a group on ordered pairs are called the orbitals of the group.

Monoids, on the other hand, satisfy the closure and identity laws but not the inverse law. How does this change things?

We see that the orbit structure of a monoid is a reflexive and transitive relation which is not necessarily symmetric. Such a relation is called a partial preorder or preferential arrangement. (You are comparing various things; some pairs may be incomparable, but you may be indifferent about the relation of other pairs.) A partial preorder is significantly more complicated than a partition or equivalence relation. That is why transformation monoids are harder! Partial preorders are equivalent to topologies on a finite set.

But something can be done. Call two elements equivalent if the relation holds between them both ways round. Now it is not hard to show that this equivalence is an equivalence relation, so it does partition the domain; moreover, the equivalence classes (which are called indifference classes) are partially ordered by the relation.

So can we copy what Higman and the others did for the action on ordered pairs? I think there might be an interesting research project here, if someone wants to take it up.

First off, we have a partition of the ordered pairs into equivalence classes. It is easy to see that the first two conditions for a coherent configuration are ssatisfied. Does the third also hold? I haven’t thought carefully about this; it may be quite an easy question, but it is one that I don’t know the answer to.

Then we have the partial order on the indifference classes or orbitals, as we may call them. How do these structures fit together? Can one define the monoid analogue of Higman’s coherent configurations including this extra structure? What properties does it have? Is there interesting combinatorics there?

Posted in doing mathematics, exposition, open problems | Tagged , , , | 1 Comment